BLS based universal accumulator

This write-up follows this following paper.

Intro

In this write-up, we will discuss the practical implementation of a pairing based (bls12-381) dynamic universal accumulator. This basically means the ability to succinctly commit to a set of unique elements onchain, and prove (non)-membership (making it universal), while maintaining the ability to add and remove elements (making it dynamic). This all in the trustless setting of a plutus script (this design does use a trusted setup, which can be generated via an MPC). The nice thing about this approach is that the homomorphic property of the pairing, naturally allows for the batching of either membership or non-membership proofs, while keeping the proof size constant.

The intuition behind the Pairing

The fundamental property of the pairing that allows us to do interesting stuff is the possibility to multiply polynomials and compare them in a hidden way that ensures correctness. For this, we need a trusted setup of a secret value

$\tau$ and its powers that no one knows. This setup is often called a common reference string, and we denote it with

$CR{S}_{G_1}=\{g_1,g_1^{\tau },g_1^{{\tau }^2},...,g_1^{{\tau }^d}\}$, and similar for

$CR{S}_{G_2}$. We can use these

$G_1$ and

$G_2$ points to evaluate any polynomial in this secret value. This is done by calculating the coefficients of the polynomial and evaluating this via the common reference string in the secret value tau. As an example, consider the polynomial,

$$f(x)=5x^3+2x^2+x+10$$
We can then evaluate it in

$\tau$ over G1 via its values

$CR{S}_i$

$$Acc=CR{S}_3^5+CR{S}_2^2+CR{S}_1+CR{S}_0^{10}$$
Since

$$Acc=(g_1^{{\tau }^3}{)}^5+(g_1^{{\tau }^2}{)}^2+(g_1^{{\tau }^1})+(g_1^{{\tau }^0}{)}^{10}=g^{5{\tau }^3+2{\tau }^2+\tau +10}=g^{f(\tau )}$$

Now, besides this, there is a canonical way of multiplying polynomials and equating them to others via a pairing. In math notation, this means that if we have the three polynomials

$f(x)$,

$r(x)$ and

$h(x)$ and the statement

$f(x)=r(x)h(x)$, then we can prove this equality without providing the coefficients by first calculating

$$l_1=g_1^{f(\tau )}\text{, }{r}_1=g_1^{h(\tau )}\text{ and }{r}_2=g_2^{r(\tau )}$$
via the

$CRS$ as above. And then we can check via fixed sized commitments that

$$e(l_1,g_2)\stackrel{?}{=}e(r_1,r_2)$$
To prove that

$f(x)=r(x)h(x)$. In expanded form, this would be

$$e(g_1^{f(\tau )},g_2)\stackrel{?}{=}e(g_1^{h(\tau )},g_2^{r(\tau )})$$
And it checks that the constructed commitments over the CRS are equal in

$\tau$,

$$f(\tau )\stackrel{?}{=}h(\tau )r(\tau )$$
Now this last line is of course true if indeed

$f(x)=r(x)h(x)$, and the converse of this statement is also true via Schwartz–Zippel lemma in this setting. This theorem basically says that the chance of this evaluation being correct in a random point

$\tau$ that no one knows, is negligible.

So to reiterate and conclude, via the pairing we can commit to polynomials without providing the full polynomial, this while maintaining the ability to multiply them and equating them.

Setup for an accumulator

The basic idea of this accumulator is to represent the set of members as a polynomial with zero-point matching the set. So for a set of

$n$ unique element

$S=\{x_1,x_2,...,x_n\}$ we have the accumulation polynomial

$$Acc(x)=\prod _{i=1}^n(x+x_i)$$
making each

$-x_i$ a non-degenerate zero point of

$Acc(x)$. Using a trusted setup (a power of tau) given by

$CR{S}_{G2}=\{g_2,g_2^{\tau },g_2^{{\tau }^2},...,g_2^{{\tau }^d}\}$ where

$d>n$, we can calculate the coefficients of

$Acc(x)$ and map these over the G2 points in the

$CR{S}_{G2}$. As an example, consider the set

$S=\{2,3,5,7,11\}$, then we have that

$$(x+2)(x+3)(x+5)(x+7)(x+11)=x^5+28x^4+288x^3+1358x^2+2927x+2310$$
So

$$Acc=g^{Acc(\tau )}=CR{S}_5+CR{S}_4^{28}+CR{S}_3^{288}+CR{S}_2^{1358}+CR{S}_1^{2927}+CR{S}_0^{2310}$$
here

$CR{S}_i=g_2^{{\tau }^i}$.

Prove membership

Say now we want to prove for a set

$S=\{x_1,x_2,...,x_n\}$, that a set

$s=\{x_{s_1},x_{s_2},...,x_{s_k}\}$ is a subset of

$S$, then we can use the polynomial remainder theorem to do so. This theorem relates a divider of a polynomial with the remainder and the quotient. That is, for any polynomial

$f(x)$ and

$h(x)$, we have that

$$f(x)=q(x)h(x)+r(x)$$
where

$q(x)$ is the unique quotient and

$r(x)$ the remainder of a division of

$f(x)$ with

$h(x)$. Moreover, this theorem says that

$r(x)$ is zero, if all zero points of

$h(x)$ are also zero points of

$f(x)$. So to use this to our advantage for a subset

$s$, we construct the polynomial

$$h(x)=\prod _{i=1}^k(x+x_{s_i})$$
then the polynomial remainder theorem gives us that there exist another unique polynomial

$q(x)$ such that

$$f(x)=h(x)q(x)$$
And given the definition of

$f(x)$, it is clear that the only possible definition of this divisor should be the accumulation polynomial over the set

$S\setminus s$. So

$$q(x)=\prod _{x_i\in S\setminus s}(x+x_i)$$
because clearly,

$$f(x)=\prod _{i=1}^n(x+x_i)=(\prod _{x_i\in S\setminus s}(x+x_i))\ast (\prod x_j\in s(x+x_j))+0=q(x)\ast h(x)+r(x)$$
And since our subset is indeed a proper subset,

$h(x)$ and

$f(x)$ divide without a remainder (

$r(x)=0$). Now, using the trick where we evaluate these polynomials over the CRS and compare them using the pairing, we can prove onchain membership. That is, given a commitment of set

$Acc$ in G2, we calculate

$$proof=g_2^{q(\tau )}=\sum _{i}CR{S}_i^{c_i}$$
and verify that for the coefficients

$e_i$ of the polynomial

$h(x)=\prod _{i=1}^k(x+x_{s_i})$

$$e(g_1,Acc)\stackrel{?}{=}e(\sum _{j}CR{S}_j^{e_i},proof)$$
Note that if you do this onchain, you need to perform

$n+1$ G1 addition and scalar multiplication, as the sum is performed onchain.

Prove non-membership

Say now we want to prove for a set

$S=\{x_1,x_2,...,x_n\}$, that a set

$s=\{x_{s_1},x_{s_2},...,x_{s_k}\}$ is not a subset of

$S$, then we can use Bézout's identity. This relates the zero points of two polynomials by saying that the greatest common divisor between them is precisely their overlap in zero points. Moreover, for

$f(x)$ and

$h(x)$, there exist an

$a(x)$ and

$b(x)$ so that

$$gcd(f(x),h(x))=f(x)\ast a(x)+h(x)\ast b(x)$$
Now if there is no overlap in zero points, the gcd is one, which is something we can verify succinctly via the pairing check! This

$a(x)$ and

$b(x)$ can be calculated via the extended Euclidean algorithm for polynomials. And thus, given this setup, we can prove non membership via

$$e(g_1,g_2)=e(Acc,A)\ast e(\sum _{j}CR{S}_j^{e_i},B)$$
Here

$A$ and

$B$ are the polynomials found by the extended Euclidean algorithm committed over the CRS. The sum of coefficients of our disjoint set is the same as in the membership proofs. This above equation thus checks that

$$1\stackrel{?}{=}acc(\tau )\ast a(\tau )+h(\tau )\ast b(\tau )$$

Discussion

The above two ways of proving (non)-membership can be combined to make a dynamic onchain accumulator. For removal of a set a membership proof has to be provided, and since the proof is precisely the remainder of the accumulated set without the subset that is being proved, this proof can be used as the new accumulator.

For adding a set of elements, one first has to prove that the elements were not a member, after which the found commitment to the disjoint set can be multiplied with the old accumulator. This effectively is a membership proof of the new state with as proof the old accumulator (the reverse of removal).

We see that in the removal case, this method is highly efficient as there is no overhead since the proof is the new state. For the addition, this unfortunately requires both kind proofs.