feat: add an RFC 6962 compliant Merkle tree with flat memory representation #554
Conversation
0935104 to
52f3eeb
Compare
| pub fn from_leaves<I, B>(iter: I) -> Self | ||
| where | ||
| I: IntoIterator<Item = B>, | ||
| B: AsRef<[u8]>, | ||
| { | ||
| let mut tree = Self::new(); | ||
| for item in iter { | ||
| tree.push(item.as_ref()); | ||
| } | ||
| tree | ||
| } |
There was a problem hiding this comment.
since push updates the tree every time it's called, it would be nice to have a from_leaves function that doesn't call push, but just constructs the tree directly from all the leaves. this way, we can do 1 bigger allocation at once since we know the final tree size, and don't have to hash intermediates unnecessarily. thoughts?
There was a problem hiding this comment.
I would love to have that, but to really benefit from this we would need to walk the tree level by level and bottom to top, and only update branches at each level.
But the math comes out a bit annoying and is IMO out of scope for this PR. I would want to spend some time thinking about how to do that.
A thought: according the indexing scheme the trailing set bits indicate the depth of the subtree. So the root for a tree of depth D has a binary representation of 011...1 with D-1 ones. This extends to every subtree. This means we should in principle be able to walk the tree by "roots-of-subtrees" by fixing the number of trailing 1s for each level.
fb7db52 to
7556b7b
Compare
noot
left a comment
There was a problem hiding this comment.
a few minor comments, approving since overall looks good and don't want to block. great work!!
37b7894 to
7cfc304
Compare
84a57da to
3dca99a
Compare
itamarreif
left a comment
There was a problem hiding this comment.
Look good. Only note would be that we should eventually write a from_leaves() method that's more efficient with the memory allocations, as @noot mentioned. But this could easily be added later.
Block data construction seems solid and largely matches our spec as described in data flow and verification. Only thing that should be updated there is the types: we no longer have InclusionProof, instead we have merkle::Proof.
Another note is that we should probably also add a document in the specs directory for how the Merkle tree implementation works. This information largely lives as docstrings in the astria-merkle crate in this PR which is also fine, though.
…ntation, rewrite all crates in terms of it.
aff5474 to
5796f0e
Compare
* main: feat: add an RFC 6962 compliant Merkle tree with flat memory representation (#554)
## Summary Enforce invariants when constructing sequencer blobs. ## Background The sequencer blob type `SequencerNamespaceData` that was written to and read from celestia was treated as a dumb container, delegating consistency checks to downstream users (for example, to the `block_verifier` module in `astria-conductor`). In the spirit of making invalid states unrepresentable, this patch introdues a `RawSequencerNamespaceData` as the dumb (de)serialization container, from which a verified `SequencerNamespaceData` can be built. In particular, the following invariants are upheld at construction, rejecting a conversion otherwise (`SMD` stands for `SequencerNamespaceData` and `SMD.field` refers to the `field` of the same): 1. `SMD.header.data_hash` must be set 2. `SMD.block_hash` must match the result of `SMD.header.hash()` 3. `SMD.action_tree_root` and `SMD.action_tree_root_inclusion_proof` must verify against `SMD.data_hash` 4. The Merkle tree hash built from `SMD.rollup_chain_ids` must match `SMD.chain_ids_commitment` 5. The `SMD.chain_ids_commitment` and `SMD.chain_ids_commitment_proof` must verifiy against `SMD.data_hash` With these changes conductor's `BlockVerifier` can be simplified significantly and is now only responsible for checking the validity of a given sequencer blob against the remote sequencer. ## Changes - Introduce `RawSequencerNamespaceData` type - Make all `SequencerNamespaceData` fields private, add read-only getters - Change `SequencerNamespaceData` serialization to be in terms of the `Raw*` type - Enforce sequencer blob invariants by introducing `SequencerNamespaceData::try_from_raw` as the only fallible constructor - Add a `SMD::data_hash` getter for convenience which panics if the invariants are violated - Streamline `BlockVerifier` by removing all checks that now happen during `SequencerNamespaceData` construction ## Testing How are these changes tested? ## Related Issues This is done as part of #356 Blocked on #554 being merged
Summary
Implement a RFC 6962 compliant merkle tree with flat memory representation, remove ct-merkle.
Background
We want to use a merkle tree that minimizes allocations because constructing merkle trees is a hot operation that happens every time new blocks are generated or verified. Worse, for blocks containing transactions for several distinct rollups a merkle Tree is created per rollup. Finally, Astria wants a minimal API that is tailored exactly to its needs to make audits as simple as possible.
The implementation of this merkle tree library does not allocate space for its leaves but only stores leaf and branch hashes in a flat, one dimensional array. Furthermore, it only supports sha256 hashes. For background reading refer to the following links:
Changes
astria-merklecrate implementing a flat merkle tree.Testing
Breaking Changelist