Remove data leaf from fuel-merkle BMT proofs
#501
Assignees
Labels
breaking
A breaking api change
bug
Something isn't working
documentation
Improvements or additions to documentation
fuel-merkle
Related to the `fuel-merkle` crate.
Comments
bvrooman
added
bug
bvrooman
changed the title
fuel-merkleBMT proofsfuel-merkle BMT proofs
This was referenced Jul 11, 2023
bvrooman
pushed a commit
to FuelLabs/fuel-specs
that referenced
this issue
Jul 14, 2023
Related issues: - FuelLabs/fuel-vm#501 (comment) This PR gives the Fuel specs its own Merkle tree specification, and removes links to the archived Celestia spec. This gives Fuel ownership over its own Merkle tree specification and allows us to adapt it to our design. Specifically, this PR copies the specification for the binary and sparse Merkle trees as described in the Celestia spec. Additional comments are my own, and describe in more detail topics like the BMT proof format. Lastly, this PR removes the specification for the binary Merkle sum tree (BMST). The BMST is currently not supported by Fuel and does not fall under the Fuel specification at this time.
|
All subtasks are now complete - closing this issue as complete. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Currently, Merkle proofs generated by the
fuel-merklebinary Merkle tree include the hashed leaf data for the leaf being proven in the proof set. This means that the proof set starts with the hashed leaf data and continues with side node data until reaching the root.The
fuel-merkle-solverifyfunction expects binary Merkle tree proofs to provide a proof set that contains only the side node data, and the unhashed leaf data separately. This represents a discrepancy between the proof format thatfuel-merklegenerates and the proof format thatfuel-merkle-solexpects.This discrepancy results from having a lack of clear specification on the format in the
fuel-specs. To provide a definitive specification, we can defer to RFC 6962 that defines the binary Merkle tree algorithm that we already use for roots. This RFC describes "audit paths" which are analogous to the proof sets we already use. According to this RFC, audit paths do not include the leaf data for the leaf being proven. Therefore, we can adapt ourfuel-merklelibrary to follow this RFC.Tasks:
provealgorithm in thefuel-merkleBMT to omit the leaf data from the Merkle proofs (bug: Remove leaf data from BMT proofs #502)verifyfunction infuel-merkle'stest-helpersto use the updated proof format (bug: Remove leaf data from BMT proofs #502)fuel-merkle(bug: Remove leaf data from BMT proofs #502)fuel-merkle-sol(chore: Update BMT data-driven proof tests fuel-merkle-sol#28)The text was updated successfully, but these errors were encountered: