## Kate-Zaverucha-Goldberg (KZG) Constant-Sized Polynomial Commitments

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:
Pairings (or bilinear maps)
Polynomials
Trusted setup
To commit to degree $\le \ell$ polynomials, need $\ell$-SDH public parameters:
Here, $\tau$ is called the t...

## Aggregatable Subvector Commitments for Stateless Cryptocurrencies (from Lagrange polynomials)

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

## Bilinear Accumulators for Cryptocurrency Enthusiasts

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.

## Multiplying a Toeplitz matrix by a vector

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.

## Basics of Polynomials for Cryptography

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’’ = [...

## Towards Scalable Verifiable Secret Sharing and Distributed Key Generation

tl;dr: We “authenticate” a polynomial multipoint evaluation using Kate-Zaverucha-Goldberg (KZG) commitments.
This gives a new way to precompute $n$ proofs on a degree $t$ polynomial in $\Theta(n\log{t})$ time, rather than $\Theta(nt)$.
\
The key trade-off is that our proofs are logarithmic-sized, rather than constant-sized.
Nonetheless, we use o...

## Fast and Scalable BLS Threshold Signatures

tl;dr: We use $O(t\log^2{t})$-time algorithms to interpolate secrets “in the exponent.”
This makes aggregating $(t,n)$ BLS threshold signatures much faster, both at small and large scales.
The question of scaling threshold signatures came to us at VMware Research after we finished working on SBFT1, a scalable Byzantine Fault Tolerance (BFT) pro...

## Range Proofs from Polynomial Commitments, Re-explained

This is a re-exposition of a post by Dan Boneh, Ben Fisch, Ariel Gabizon on how to obtain a constant-sized range proof from constant-sized polynomial commitments.
This post was moved to Decentralized Thoughts.

13 post articles, 2 pages.