As a team, we need infrastructure for proving message inclusion within a given aggregate root

[alexwhte]

From epic #1808

What is?

We need off-chain infrastructure to handle generating proofs for messages which lighthouse will submit to proveAndProcess on destination chains.

How does the on-chain infrastructure work?

Update interface

Here is the new interface for proveAndProcess:

  function proveAndProcess(
    Proof[] calldata _proofs,
    bytes32[32] calldata _aggregatorPath,
    uint256 _aggregatorIndex
  ) external {

The Proof struct in proveAndProcess args is a proof submitted for each message in the batch.

  struct Proof {
    bytes message;
    bytes32[32] path;
    uint256 index;
  }

(NOTE regarding batching: Each batch of messages must share a common root (outboundRoot or inboundRoot, depending on the chain in question): meaning they must all come from the same origin chain. We don't really need to worry about batching for rn, just call proveAndProcess and pass just a singular [Proof] as first arg for each message as they come in lighthouse.)

Review of message lifecycle

There's an outboundRoot coming from an origin chain that contains a bunch of messages going to various other spoke chains. Each of these messages, when they were dispatched, had an index in the root.

The outboundRoot is bridged to hub's RootManager where it is aggregated into an aggregate tree (which is new behavior in this branch).

When you call propagate, RootManager is going to send out the aggregate tree's current top root, which will include every origin chain's outboundRoots that have been thus far aggregated in the hub. So any given outboundRoot will be a leaf in the aggregate tree.

When this happens, an event is emitted:

  event RootAggregated(uint32 domain, bytes32 receivedRoot, uint256 index);

^ the origin domain of the outboundRoot, the outboundRoot itself, and the index of the outboundRoot in the aggregate tree.

In order to prove any given valid message using <SpokeChain>SpokeConnector.proveAndProcess(...), you need to provide:

• The message bytes, Proof.message
• Message Proof.path (AKA the proof), which should be 'instructions' on how to find the message in the originRoot
• Message Proof.index in the originRoot
• aggregatorPath, which is the proof of inclusion of the originRoot
• aggregatorIndex, which comes from the bold text I highlighted above ^^

Generating the proof

For generating the Proof.path and the aggregatorPath, you can use SparseMerkleTree (in utils package, under packages/utils/src/helpers/merkle.ts).

One key component here is that in order to generate the path/proof you need, you need to have a "snapshot" of the merkle tree when roots get sent/propagated.

So, if an outboundRoot containing 20 messages is sent from a given spoke chain, we'll need to take a snapshot of that current tree (i.e. the one where outboundRoot == tree.root) in order to generate a proof of inclusion for each of those 20 messages. Fortunately this is pretty easy - details below on how to do this!

We'll need to also take a snapshot of the aggregate tree whenever a propagate occurs. If there's 10 domains in total that we're servicing, that means we'll need to generate 10 proofs - one for each outboundRoot that's included in the aggregateRoot.

(NOTE: if you've already proven an outboundRoot exists in an aggregateRoot, you don't have to prove it twice. In fact, you can just leave _aggregatorPath and _aggregatorIndex args blank in that case.)

Implementation

• [ ] SparseMerkleTree currently accepts a stub handler for a database, which it consults to pull node/leaf information in generating proofs. What this database should ideally have stored pertains to 2 things:
  • For message proofs:
    • index (number) => messageHash (string) : The node index mapped to the message hash corresponding to that index.
    • outboundRoot (string) => count (number) : Each published outboundRoot (published = just the ones sent to mainnet) mapped to the number of nodes when that root was published; AKA the index belonging to the last message that was dispatched before the outboundRoot got sent.
  • For aggregation proofs:
    • index (number) => outboundRoot (string) : The node index mapped to the outboundRoot that was aggregated into the aggregate tree on the hub chain.
    • aggregateRoot (string) => count (number) : Again, the number of nodes when the aggregate root was propagated to all the spoke chains. Getting this is as easy as just getting the index param from the last RootAggregated event when it was emitted (maybe we could just track that in the subgraph?).
• [ ] Link up the utility (class or method, idk) in the lighthouse to generate proofs as needed for a given message at a given index. Verify that the proof is correct (using the same utility class, SparseMerkleTree). This proof will be the Proof.path argument.
• [ ] Repeat the previous step but for calculating the proof of inclusion of the outboundRoot in the aggregate tree given the outboundRoot and its index in the aggregate tree. Additionally, verify that the proof is correct. This proof will be the _aggregatorPath argument.
• [ ] Create gelato task that will process a message when ready..?

More Details

Details on steps for implementation see https://discord.com/channels/992549151134982234/1021615595474649158/1023786395237617735

[jakekidd]

this should just be the offchain component, related to #1729

~~should use the merkletreelib.js library to generate proofs~~

EDIT: should NOT use the merkletreejs library, see edited og comment

[alexwhte]

Please add your planning poker estimate with Zenhub @rhlsthrm