Module storage_proofs::circuit::apex_commitment

ApexCommitment

ApexCommitment is a vector commitment which can be verified in a circuit more cheaply than a merkle tree, provided that there will be many inclusion proofs, and that each element is likely to be included in at least one proof.

The name and interface reflect the intended purpose, as a replacement for the top (apex) of a merkle tree. Instead of proving inclusion of a leaf within a singular root, prove the leaf is included in the apex commitment at a given position. The 'position' is specified as the unused remainder of the merkle path once the merkle inclusion proof has reached the apex row included in the commitment.

A one-time hashing cost of all the values is amortized over cheaper individual inclusion proofs, which require no hashing. See tests for more detail, but the short version is that each proof uses a number of constraints which is exponential in the length of the elided path: (2 * size + length) - 1 = (2^L + L) - 1.

This sets an uppper bound on the size of the apex. When the cost of including another row in the apex exceeds the cost (in constraints) of one hash, there's no potential savings. (Reference: 1 32-byte pedersen hash requires ~1152 constraints).

Structs

FlatApexCommitment

Enums

BinaryApexCommitment

Traits

ApexCommitment