6

To preface this: I'm not entirely sure this question makes any sense. Just a thought I had that I wanted to check the feasibility of.

I'm pretty sure it is possible to use a Merkle proof to show that a transaction was included in some block, and I wonder if this is also possible with logs.

Essentially, would it be possible to prove that a log was generated by including a Merkle proof of either 1) the transaction that generated the log or 2) the log (I know logs are stored differently than transactions, so I'm not sure this is possible at all).

Essentially could there be a proof provided to a contract that some log was generated by some transaction in some block?

8

Yes, a Merkle proof of a transaction receipt can be used to verify the existence of logs.

An Ethereum block header has the Merkle root of the (transaction) receipts trie.

A transaction receipt has all the logs.

By hashing the transaction receipt, and the hashes comprising the Merkle proof, the resulting hash can be compared against the Merkle root in the header. A match would indicate that the log exists.

Description from the Yellow Paper:

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...:

In https://blog.ethereum.org/2015/11/15/merkling-in-ethereum Vitalik Buterin gave an example of using receipts, as well as other examples that can be answered with Merkle proofs:

  • Has this transaction been included in a particular block?
  • Tell me all instances of an event of type X (eg. a crowdfunding contract reaching its goal) emitted by this address in the past 30 days
  • What is the current balance of my account?
  • Does this account exist?
  • Pretend to run this transaction on this contract. What would the output be?

The first is handled by the transaction tree; the third and fourth are handled by the state tree, and the second by the receipt tree. The first four are fairly straightforward to compute; the server simply finds the object, fetches the Merkle branch (the list of hashes going up from the object to the tree root) and replies back to the light client with the branch.

The fifth is also handled by the state tree, but the way that it is computed is more complex. Here, we need to construct what can be called a Merkle state transition proof...

Vitalik also gave a presentation at DevCon1 and a section on logs:

https://www.youtube.com/watch?v=gjwr-7PgpN8&t=2106

2

I was trying to solve this exact problem and wrote a proof of concept that can do this:

https://github.com/figs999/Ethereum/blob/master/EventStorage.sol

Basically, you need two components: 1: A way to read and confirm the validity of a block header 2: A way to check the bloom filter for the presence of a log entry

In my proof of concept, in order to ingest a log entry and confirm it's validity a client calls a method and passes in both the RLP encoded block header that the log is from and the contents of the log itself.

The RLP encoded header is decoded in the contract. Once it's decoded, the correct block hash for that block can be retrieved via block.blockhash. You then just compare the keccak256 hash of the rlp encoded header bytes and the real hash, if they match the header is valid.

Once you have a valid header, you can read the logs bloom from it. The logs bloom is a 256 byte number which can be checked to confirm the existence of a log as long as you know the address of the contract that wrote the log, the signature of the log event, and any topics that the log included.

The trick to validating a specific blob of log data from this is to include the logged data blob as the log value AND as an indexed topic. When you include it as an indexed topic the keccak256 hash of the blob will be present in the logs bloom.

Checking the presence of a specific log in the logs bloom is relatively simple, but requires some funky bit math which is a bit tricky to do efficiently in solidity. My example was forced to fall back on assembly for this part of it.

The process is as follows:

  1. Get the three hashes that should be in the logs bloom: the hash of the contract address, the hash of the hash of the event signature [keccak256(keccak256("DataStored(bytes,bytes)"], and the hash of the hash of the logged data.
  2. For each of the hashes extract the first three pairs of bytes. Lets call these [B1,B2,B3]
  3. For each byte-pair B, check the presence of the marker bit (m) in the logs bloom, where m = 1<<(B%2048).
  4. If the logs bloom contains all 9 of the bits that you check, the log is (most likely) valid.

Using this method you can ingest historical logs into a smart contract in order to validate data or to act as a lower gas cost storage space. The tradeoff is that the gas cost of the data retrieval/validation is significantly higher.

  • I would recommend against using the bloom filter as evidence that eventshappened. Bloom filters are prone to false positives. They're useful to avoid scanning transactions in a block if the it won't have the event you're looking for, but it's possible that the bloom filter will indicate an event happened when it didn't. For event scanning that means you scan the transactions and find nothing, wasting time. If you use it as proof that something happened it could be wrong. Someone could craft a few logs to make the bloom filter produce a false positive, compromising your security deliberately. – AusIV Apr 6 '18 at 16:38
  • It’s true that bloom filters can have false positives, but I believe that the rate of collision for this particular use case will be sufficiently low. The bloom filters used for Ethereum logs are relatively large, while the number of transactions that will be processed in a single block will be relatively low. Add to this the contract’s format requirements for the logged message, and the fact that you are checking for the presence of the hash said log in the bloom, and the likelihood someone will find a meaningful collision becomes close to nil. – Chance Wees Apr 8 '18 at 7:07
  • That said, AusIV is correct that this cannot provide cryptographic PROOF that the log is present, so you must weigh the chance that a collision is found against how mission critical your use case is. There are some techniques one can use to further secure against collisions, such as making sure there is no field in your log format which could be used as a nonce (which would allow for variations on a false log to be checked for collision by an attacker), or, requiring the hashed size of the log to also be included in the topics. – Chance Wees Apr 8 '18 at 7:09
  • If you're using the block bloom filter it doesn't matter if the events in the bloom filter came from your contract. Someone could construct a contract that emits arbitrary events which get added to the bloom filter. Since there's 9 bits to check they could craft 9 events, each of which will set one pertinent bit (and 8 irrelevant bits). Inputs to the events could be calculated off-chain pretty cheaply, and then the bloom filter would give a false-positive that the contract's event was present. You're probably pretty safe from probablistic collisions, but it would be easy to craft collisions. – AusIV Apr 9 '18 at 16:33
2

You can easily achieve this using ProvenDB. Here is an example code written in Go to continuously prove your logs' existence and ownership on Blockchain: https://github.com/SouthbankSoftware/provenlogs. Hope it helps :P

1

Transactions contain references to any logs emitted during their execution, so I think proving the existence or location of the transaction itself would be enough.

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.