Home

Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation

tl;dr: We build an authenticated dictionary (AD) from Catalano Fiore vector commitments that has constant-sized, aggregatable proofs and supports a stronger notion of cross-incremental proof disaggregation. Our AD could be used for stateless validation in cryptocurrencies with smart contract execution. In a future post, we will extend this AD wi...

Read more

RSA Accumulators

An RSA accumulator is an authenticated set built from cryptographic assumptions in hidden-order groups such as $\mathbb{Z}_N^*$. RSA accumulators enable a prover, who stores the full set, to convince any verifier, who only stores a succinct digest of the set, of various set relations such as (non)membership, subset or disjointness. For example, ...

Read more

Linear Diophantine Equations

Equations of the form $\sum_i a_i x_i = 0$ where the $x_i$’s are integer unknowns are called linear Diophantine equations. Their integer solutions can be computed using greatest common denominator (GCD) tricks. In this post, we go over a few basic types of such equations and their integer solutions.

Read more

Aggregatable Subvector Commitments for Stateless Cryptocurrencies (from Lagrange polynomials)

tl;dr: We build a vector commitment (VC) scheme from KZG commitments to Lagrange polynomials that has (1) constant-sized, aggregatable proofs, which can all be precomputed in $O(n\log{n})$ time, and (2) linear public parameters, which can be derived from any “powers-of-tau” CRS in $O(n\log{n})$ time. Importantly, the auxiliary information needed...

Read more