## What is a Merkle tree?

tl;dr: In this post, we demystify Merkle trees for beginners.
We give simple, illustrated explanations, we detail applications they are used in and reason about their security formally.
For more details, see this full post on Decentralized Thoughts.

## 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:
Cyclic groups of prime order and finite fields $\Zp$
Pairings (or bilinear maps)
Polynomials
Trusted setup
To commit to degree $\le \ell$ polynomials, need $\ell...

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

19 post articles, 3 pages.