## 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...

## 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, ...

## Catalano-Fiore Vector Commitments

A vector commitment (VC) scheme allows a prover with access to a vector $\mathbf{v} = [ v_1, \dots, v_n ]$ to convince any verifier that position $i$ in $\mathbf{v}$ stores $v_i$ for any index $i\in[n]$.
Importantly, verifers only store a succinct digest of the vector (e.g., a 32-byte hash) rather than the full vector $\mathbf{v}$.

## 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.

## Cryptographic Assumptions in Hidden-Order Groups

In this post, we summarize some of the cryptographic hardness assumptions used in hidden-order groups.

## Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments

Kate, Zaverucha and Goldberg introduced a constant-sized polynomial commitment scheme in 20101.
We refer to this scheme as KZG and quickly introduce it below.
Prerequisites:
Pairings (or bilinear maps)
Polynomials
Trusted setup
To commit to degree $\le \ell$ polynomials, need $\ell$-SDH public parameters:
\((g,g^\tau,g^{\tau^2},\dots,g...

## 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...

## Bilinear Accumulators for Cryptocurrency Enthusiasts

tl;dr: We give on overview of bilinear accumulators, a more communication-efficient alternative to Merkle Hash Trees (MHTs) that comes at an increase in computation.
Put simply, bilinear accumulators are commitments to sets with constant-sized (non)membership proofs.
For more details, see this full post on Decentralized Thoughts.

18 post articles, 3 pages.