Vector Commitment Scheme

In STARK protocols, the prover first interpolates the computation trace as polynomials over some domain, then evaluates those interpolated polynomials over a larger domain. Finally, the prover commits to those evaluations using a vector commitment scheme.

Stwo uses a Merkle tree-based vector commitment scheme that enables efficient commitment to multiple columns of data and generation of Merkle proofs for queried elements. This section covers the complete workflow: from hash function implementations to the commitment and decommitment processes.

This section is organized as follows:

• Hash Functions: Overview of the hash function traits and implementations used in Merkle trees.
• Merkle Prover: The commitment process that builds Merkle trees from column data and the decommitment process that generates proofs for queried elements.
• Merkle Verifier: The verification process that checks the validity of Merkle proofs against a committed root.