Home

tl;dr: “If you thought before that science is certain, well, that’s just an error on your part.” – Richard Feynman

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

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

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

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

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

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

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!’