Alin Tomescu - page 12

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!’ There may now be improvements over FK that are faster[^CJLplus24e]$^,$[^LJGK25e]. This bl...

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

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.

A few research problems that I wish I had time to work more on… Efficient Homomorphic Merkle (Herkle) trees A homomorphic Merkle tree, or a Herkle tree has an extremely useful property: given a change $\Delta$ to one of its leaves $\ell$, every node in the tree can be updated homomorphically, knowing only the change $\Delta$ and the leaf $\ell...

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

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