34

As stated in the yellow paper:

Transaction Receipt. In order to encode information about a transaction concerning which it may be useful to form a zero-knowledge proof, or index and search, we encode a receipt of each transaction containing certain information from concerning its execution. Each receipt, denoted BR[i] for the ith transaction) is placed in an index-keyed trie and the root recorded in the header as He.

The transaction receipt is a tuple of four items comprising the post-transaction state, R, the cumulative gas used in the block containing the transaction receipt as of immediately after the transaction has happened, Ru, the set of logs created through execution of the transaction, Rl and the Bloom filter composed from information in those logs, Rb:

R = (R;Ru;Rb;Rl)

Can anyone give more details of how this Rl (logs) is structured and how the Rb (bloom filters) are constructed from it?

I've been doing some research about bloom filters and Broder and Mitzenmacher state that:

Wherever a list or set is used, and space is at a premium, consider using a Bloom filter if the effect of false positives can be mitigated.

So how does this relates to Ethereum's design rational?

Improve this question

1 Answer 1

Reset to default
48

Events in the ethereum system must be easily searched for, so that applications can filter and display events, including historical ones, without undue overhead. At the same time, storage space is expensive, so we don't want to store a lot of duplicate data - such as the list of transactions, and the logs they generate. The logs bloom filter exists to resolve this.

When a block is generated or verified, the address of any logging contract, and all the indexed fields from the logs generated by executing those transactions are added to a bloom filter, which is included in the block header. The actual logs are not included in the block data, to save space.

When an application wants to find all the log entries from a given contract, or with specific indexed fields (or both), the node can quickly scan over the header of each block, checking the bloom filter to see if it may contain relevant logs. If it does, the node re-executes the transactions from that block, regenerating the logs, and returning the relevant ones to the application.

Improve this answer
11
  • 1
    Yeah, that's the problem. I can't make any sense from the definition from the yellow paper. I was hopping to get something "for dummies". Anyway, I'll keep digging. Thank you very much!
    – Henrique Barcelos
    Apr 28, 2016 at 14:17
  • 4
    @HenriqueBarcelos It's fairly straightforward: For the address, and each of the indexed topics, Keccac-256 hash them, then take the first 11 bits of each of the three least significant pairs of bytes of the hash. These are the indexes of the 3 bits in the bloom filter that you should set.
    – Nick Johnson
    Apr 28, 2016 at 14:32
  • 1
    @HenriqueBarcelos k hashes, and k distinct subsets of a larger hash, are equivalent to each other, because all the bits of a hash are independent.
    – Nick Johnson
    Apr 28, 2016 at 18:09
  • 1
    @NickJohnson: Are you aware of any simple code that would take an address and the bloom filter from the block head and return true/false if the address is in the bloom filter?
    – Thomas Jay Rush
    Oct 10, 2016 at 0:01
  • 1
    Isn't relevant logs downloaded under each block without any executing (miners already generated the output of the Tx results)? Does Bloom Filer also used for other tries (state, transaction and receipt)? @Nick Johnson
    – alper
    Dec 13, 2017 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.