Cryptography building blocks

Provably V2 has been redesigned from scratch, and it has been implemented in the Rust programming language using well-known, open-source cryptographic libraries. Provably V2 itself will be open-sourced after its release. It is based upon the following building blocks.

Vector commitments: A vector commitment (VC) scheme allows one to prove that a committed vector contains given values in specified positions. VC schemes are used to prove the correctness of a query answer. Provably V2 uses a state-of-the-art VC scheme called Linear-map Vector Commitment (LVC) that has very desirable properties like aggregation, upgradeability, and linearity that allow it to reduce the space requested for the database commitments, to efficiently support data updates, and to prove linear functions over data.

Set accumulators: A set accumulator (SA) scheme allows a compact representation of a set of values, and it is used to prove the completeness of a query answer. Provably V2 deploys an SA scheme based on the well-known KZG polynomial commitment scheme.

A remarkable consequence of our approach is that Provably V2 requires a single setup phase that coincides with the very well-known 'powers of tau' KZG setup, which is a quite standard and widely implemented procedure that has already been deployed multiple times (e.g., by Ethereum and Filecoin trusted setup ceremonies).