Proving the Existence of Logs to the Blockchain

Question

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?

Answer 1

Update: https://github.com/PISAresearch/event-proofs has some code. From its readme:

Event proofs

A POC to explore how Ethereum logs could be verified in a smart contract. Proofs are generated using eth-proof and verified using the Merkle Patricia Tree implementation from Peace Relay. If running the tests against Infura be patient with them as generating proofs requires a lot of rpc calls.

---

Original answer:

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

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

Answer 3

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

Answer 4

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.