Merkle Tree
A Merkle tree serves as a cryptographic commitment mechanism, particularly in the context of validity proof systems. With a Merkle tree of a certain depth, it's possible to store up to $2^{depth}$ values, and the proofs of membership for these values are efficiently compact, proportional to the depth. The construction of a Merkle tree begins at the leaves, where each value in the set is hashed using a secure, collision-resistant hash function. These hashed values are then recursively combined and hashed in pairs, moving up the tree level by level. This process continues until a single hash, known as the Merkle root, is derived at the top of the tree. The Merkle root serves as the commitment to the entire set of values. Consider a set ${v1, v2, ..., v7}$ and assume $H$ and $C$ (both of them could be same as well) is our chosen hash and compression functions. Each value $v_i$ is hashed to initiate the tree's leaf nodes. These are then recursively compressed in pairs, forming the subsequent levels of the tree.
image
Merkle Tree in STARKs
A Merkle Tree is utilized to commit various components in a STARK, specifically the execution trace, quotient composition polynomial chunks, and the intermediate stages of the FRI folding rounds. These components are inherently matrix-like structures, with the execution trace and quotient composition polynomial chunks typically consisting of multiple columns. In a straightforward, unoptimized approach, the prover would create individual Merkle trees for each column of these matrices. Each tree's root along with some paths would then be sent to the verifier, serving as a commitment to the corresponding column. However, this method presents a significant challenge in terms of proof size, as the number of Merkle trees scales with the number of columns in the matrices.
To address this scalability issue, a more efficient strategy is employed in production. Rather than creating a separate Merkle tree for each column, a single Merkle tree is constructed for the entire matrix. This is achieved by aggregating all the field elements in each row of the matrix and sequentially hashing them to form a single leaf node of the Merkle tree. This approach dramatically reduces the number of required Merkle trees to just one. A verifier can efficiently check the proof of any specific row by performing a single Merkle path verification, corresponding to the leaf of that row.