## Why you should probably never sort your Merkle tree's leaves

tl;dr: …because (1) they are only secure when the tree is correctly-computed (e.g., secure with BFT consensus, but insecure in single-server transparency logs), (2) you cannot efficiently insert or delete leaves, and (3) they have worse proof sizes. What does that mean? Never implement one. Stick to Merkle tries (a.k.a., Merkle prefix trees). Or...

## Pairings or bilinear maps

tl;dr: Pairings, or bilinear maps, are a very powerful mathematical tool for cryptography.
Pairings gave us our most succinct zero-knowledge proofs[^GGPR12e]$^,$[^PGHR13e]$^,$[^Grot16], our most efficient threshold signatures[^BLS01], our first usable identity-based encryption (IBE)[^BF01] scheme, and many other efficient cryptosystems[^KZG10].
...

## Hyperproofs: Faster Merkle proof aggregation without SNARKs

tl;dr: For now, see our Hyperproofs paper[^SCPplus22].

## Lagrange interpolation

Recall from our basics discussion that a polynomial $\phi$ of degree $d$ is a vector of $d+1$ coefficients:
\begin{align}
\phi &= [\phi_0, \phi_1, \phi_2, \dots, \phi_d]
\end{align}
How to compute a polynomial’s coefficients from a bunch of its evaluations
Given $n$ pairs $(x_i, y_i)_{i\in[n]}$, one can compute or interpolate a degree...

## Feist-Khovratovich technique for computing KZG proofs fast

tl;dr: Given a polynomial $f(X)$ of degree $m$, can we compute all $n$ KZG proofs for $f(\omega^k), k\in[0,n-1]$ in $O(n\log{n})$ time, where $\omega$ is a primitive $n$th root of unity?
Dankrad Feist and Dmitry Khovratovich[^FK20] give a resounding ‘yes!’

## Basic number theory

Multiplicative inverses modulo $m$
The multiplicative group of integers modulo $m$ is defined as:
\begin{align}
\Z_m^* = \{a\ |\ \gcd(a,m) = 1\}
\end{align}
But why?
This is because Euler’s theorem says that:
\begin{align}
\gcd(a,m) = 1\Rightarrow a^{\phi(m)} = 1
\end{align}
This in turn, implies that every element in $\Z_m^*$ has an invers...

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

25 post articles, 4 pages.