Expand description
This module provides the arithmetisation of the Merkle tree inclusion proof.
It defines the constraint system, witness filling, and boundary construction for verifying Merkle tree paths using Groestl-256 as the compression function.
The main components are:
MerkleTreeCS: The constraint system for the Merkle tree, including all tables and channels.NodesTableandRootTable: Table definitions for Merkle path steps and root checks.- Table filling logic for witness generation.
- Boundary construction for circuit input/output consistency.
The module is designed to be used in tests and as a reference for implementing Merkle tree inclusion proofs in the Binius M3 framework.
Structsยง
- Merkle
Boundaries - Struct representing the boundary values of merkle tree inclusion proof statement.
- Merkle
Path - A type alias for the Merkle path, which is a vector of tuples containing the root ID, index, leaf, and the siblings on the path to the root from the leaf.
- Merkle
Path Event - A table representing a step in verifying a merkle path for inclusion.
- Merkle
Root Event - A table representing the final step of comparing the claimed root.
- Merkle
Tree - Merkle tree implementation for the model, assumes the leaf layer consists of 32 byte blobs. The tree is built in a flattened manner, where the leaves are at the beginning of the vector and layers are placed adjacent to each other.
- Merkle
Tree Channels - A struct whose fields contain the channels involved in the trace to verify merkle paths for a binary merkle tree
- Merkle
Tree Trace - Struct representing the trace of the merkle tree inclusion proof statement.
- Node
Flush Token - Signature of the Nodes channel: (Root ID, Data, Depth, Index)
- Root
Flush Token - Signature of the Roots channel: (Root ID, Root digest)