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

## Pairing-based anonymous credentials and the power of re-randomization

tl;dr: Pointcheval-Sanders (PS) signatures[^PS16] are incredibly powerful: (1) they can sign Pedersen commitments directly and (2) they can be re-randomized together with the signed commitment. This enables very simple schemes for proving yourself anonymously. For example, an authority can give you a PS signature on a commitment of your age and ...

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

## Are there cryptographic accumulators without trusted setup?

tl;dr: Yes, there are: Merkle-based, RSA-or-class-group based and lattice-based ones.

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

27 post articles, 4 pages.