Merkle Tree & Merkle Proof
Merkle Tree and Merkle Proof are large-scale data validation methods and are used in a variety of fields. You can find verified code for them in OpenZeppelin, and you can find related material on Wikipedia and other websites. This page briefly describes Merkle Tree and Merkle Proof, and covers their use in OpenCohort.
Waht is Merkle Proof?
Merkle Proof is a method for verifying the integrity of data using a Merkle Tree. By organizing a large set of data into a binary tree structure (a Merkle tree), you can efficiently and securely verify that a particular piece of data is included in this large set. For example, in distributed systems like blockchains, Merkle Proof is used to verify whether a transaction is included in a particular block. The advantage of this method is that it allows verification using only a few hash values, without needing to download the entire dataset or check all nodes.
The Concept of Merkle Tree
A Merkle Tree is a data structure that organizes data into a binary tree structure. The basic concepts are as follows:
Leaf Node: The lowest node in the tree, each of which contains a hash value of raw data (such as a transaction or file block).
Parent Node: These nodes are calculated by combining the hash values of two child nodes, representing higher levels in the tree.
Root Hash: The node at the top of the tree, representing the hash value of the entire tree. It plays a key role in ensuring the integrity of the entire dataset.
How Merkle Proof Works
Merkle Proof allows verification of whether a particular leaf node (an address or identity in OpenCohort) is part of the Merkle Tree using only a few hash values. The process works as follows:
Data to be verified (Leaf Node): The hash of the data to be verified is provided.
Proof Path: Hash values along the path to the root hash are provided. This includes the hash values of sibling nodes along the path.
Root Hash: The root hash representing the entire Merkle Tree is provided.
The verifier then uses the provided data and proof path to compute the root hash. If the computed root hash matches the provided root hash, it proves that the data is part of the Merkle Tree.
Benefits of Merkle Proof
Increased Verification Efficiency: Merkle Proof enables fast verification of large datasets using only a few hash values, reducing the need to download the entire dataset. This helps significantly reduce network costs and verification time.
Ensured Data Integrity: Merkle Proof efficiently verifies data without tampering. If the provided root hash and proof path do not match, the verification fails, ensuring the integrity of the data.
Merkle Tree in OpenCohort
In OpenCohort, Merkle Trees play a crucial role. A 'Cohort' contains a Merkle Root Hash representing the aggregated dataset for each time frame in a rollup. This enables reference to the aggregated data for all times, making it accessible for smart contracts on the blockchain to use any point-in-time data.
Standard Implementation
OpenCohort uses the Merkle Proof implementation from OpenZeppelin.
The method for constructing Merkle Trees in OpenCohort adopts Uniswap’s approach:
It hashes the index, bytes(20), and weight to prevent '64 bytes attack'.
OpenCohort provides a distribution logic forked from Uniswap, utilizing Merkle Tree and Merkle Proof mechanisms for efficient allocation.
Address & Identity
In OpenCohort, Merkle Leaves are not limited to representing addresses with bytes(20). This opens up vast possibilities for bridging the legacy world and blockchain.
Bytes(20) not restricted to addresses may require additional signatures for proof verification.
For further details, refer to the Address & Identity section.
References
Last updated
