We want to be able to read L1-to-L2 messages from both private and public contracts. The way we currently read messages in private contracts might not be acceptable in public contracts.
Reminder: private execution and proof-generation is performed client-side (in the PXE), but public execution and is performed by a Sequencer and proven by a Prover.
Today, if a private contract reads an L1-to-L2 message, it calls an oracle and provides the message key. The PXE checks its database for a message with matching key. If an entry for the key is found, the full message and its sibling path are returned and become circuit inputs.
In public, if an AVM opcode (READL1TOL2MESSAGE(key)) existed to do this same thing, it would somehow need to require that the sequencer/prover prove non-existence of key, otherwise the sequencer could return empty/no-message without proof. Non-membership proofs (given only a leaf value) are not feasible in an ordinary (non-sparse/indexed) merkle tree.
I believe are options are the following:
Modify the l1tol2message tree to be an âindexedâ merkle tree so that such membership checks are feasible.
Require that the READL1TOL2MESSAGE opcode accepts leafIndex as argument. Then it would be the responsibility of private execution to determine the leaf index of a message and forward it to an enqueued public call via calldata.
Expanding in the second option: For a non-indexed tree you can always ask for âwhatâs inside this indexâ, so you require the sequencer always provide a valid membership proof of the leaf at index N, and then you check if the leaf matched the value you wanted. But the problem is that then you require passing the index along with the leaf you expect.
The main difference on this topic between public and private is that the PXE is assumed to be collaborative with the user, since itâs owned by him, but the sequencer can be adversarial
The L1-to-L2 messages currently support duplicate messages to ensure that same messages can be inserted. To allow this for the nullifier, nullifier computations depends on its index in the tree as well. That way two notes with same message can still both be nullified.
An issue I see with the indexed tree would be that notes are computed outside of the computation that is inserting them into the tree, so if you can cause it to fail, you could either brick the state transition or you could have people lose their funds because it was not inserted because already in there. You could include the index as part of the hash computation and thereby include it in the leaf-value which might solve that though. In the current model, that would not work, but in the one @jaosef and I have been working on ordering is known at time of hash computation so it could work there.
In both cases (the old and the proposed new) nullifying would depend on knowing the index either as part of the note itself or for the nullifier computation so seems fair to use leafIndex as argument from that. Right now the private execution is anyway responsible of determining the leaf, it is just done when it is getting a hold of the membership proof etc
Ah, good point about supporting duplicate messages @LasseAztec.
One of the hopes for aztec.nr was that we could abstract-away the need for devs to think about the protocolâs merkle trees. With that in mind, Iâd be keen to find a solution that doesnât require a user to explicitly pass a leaf_index as an argument to their public functions to consume l1-to-l2 messages, if we can.
Ideally, we want the developers and users to say âthis is my âmessage structâ, please read itâ, without any explicit mention of a leafIndex.
I see some ways of achieving this:
Use an indexed merkle tree, and have the user provide a message struct. To overcome duplicates:
a. We could either include a leaf index in the message struct (in which case we may as well use option 2 because itâs simpler)
b. We could include some other uniqueness inside the message struct, to enable dupicates. Thereâs not much uniqueness that a Solidity tx can access. You could maybe use the signature values r,s,v. But that seems ugly.
Include a leaf_index field in the l1-to-l2 message struct, and have the âreadâ opcode extract that leaf index behind the scences, and use it in checking the leaf value at that leaf index.
These two options are almost the same as what David wrote initially, but Option 2 is subtly reframed here, in that if you include the leaf_index as a data member of a âmessage structâ, then devs can just handle this opaque struct instead of explicitly having to also handle a separate leaf index.
tl;dr: option 2 (but nesting the leaf index within the message struct) does indeed seem best.
Follow-up Q though: Is there a use case where an app might wish to prove that a message doesnât exist within the l1 to l2 messages tree? If so, an indexed merkle tree is back on the cards.
