Merkle'ized Event Proofs

[AlexHentschel]

For each computed chunk, an Execution Node includes a hash of all events in its Execution Result.

However, at the moment, we simply hash the list of all events in its entirety. This makes it very expensive to prove that a specific event was emitted during a block's computation, because the prover needs to transmit all events from the specific chunks to the recipient, as there are generally lots of events emitted within a chunk.

Formally, lets denote the set of all events emitted during chunk i as S_i. We want to prove that a certain even s was emitted in chunk i, i.e. s ∈ S_i. At the moment, such a proof requires a lot of data to be sent over the network, as we need to submit S_i in its entirety.

Goal

Reducing the proof size for s ∈ S_i:

• we assume the client has a verified block header.
• to proof to the client that s ∈ S_i, the client would need
  1. verify that the full block includes a Seal to Execution Result E (might require some auxiliary data to be provided by the prover):
     • the block Payload already contains a merkle'ized set commitment for the seals.
     • We would need to transmit a
       • Seal for result E
       • merkle path to the seal
       • the root hashes for the other payload categories (Guarantees, Receipts, Results).
  2. At the moment, the client requires the entire execution receipt. This is practical at the moment, because the blocks contain only a moderate number of collections. However, there is room for optimization, by merkle'izing the Chunks and not including them verbatim in the Execution Result.
  3. 🔧 Now, we need to convince the client that the event s is part of the EventCollection. At the moment, the EventCollection is the hash of a flat list, i.e. the proof is very space-inefficient.

Out of scope:

• here, we assume that the client already knows the finalized block headers
• and we assume that the client is aware of the finalization status for each block (or only considers finalized blocks)

[github-actions[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[AlexHentschel]

superseded by Clover - Verifiable Events with Multiple Indices design