Home

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

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.

In this post, we summarize some of the cryptographic hardness assumptions used in hidden-order groups.

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

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

tl;dr: We give on overview of bilinear accumulators, a more communication-efficient alternative to Merkle Hash Trees (MHTs) that comes at an increase in computation. Put simply, bilinear accumulators are commitments to sets with constant-sized (non)membership proofs. For more details, see this full post on Decentralized Thoughts.

These are some notes on how to efficiently multiply a Toeplitz matrix by a vector. I was writing these for myself while implementing the new amortized KZG proofs by Feist and Khovratovich, but I thought they might be useful for you too.

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} For example, $\phi = [1, 10, 9]$ is a degree 2 polynomial. Also, $\phi’ = [1, 10, 9, 0, 0, 0]$ is also a degree 2 polynomial, since the zero coefficients at the end do not count. But $\phi’’ = [...