23

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?

32

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.

  • thank's =]. Do you know where I can find some material defining how is this bloom filter created and how ethereum deals with false positives? – Henrique Barcelos Apr 28 '16 at 14:06
  • 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 '16 at 14:17
  • 3
    @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 '16 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 '16 at 18:09
  • 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 '17 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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