Skip to content

APK Proofs

Consensus proofs consist of signatures from a supermajority subset of the entire validator set. This can result in the cost of verifying consensus proofs scaling linearly with the size of the validator set. However, the BLS signature scheme overcomes this limitation by enabling the aggregation of signatures and public keys, reducing verifier complexity to a single pairing check. Unfortunately, this comes at the cost of being unable to confirm the identity of each individual signer. The apk proofs[1]^{[1]} scheme reintroduces accountability in this regard at the extra cost of verification of a single SNARK proof.

The SNARK achieves this by constraining the elliptic curve addition of BLS public keys in order to produce a proof that a given aggregate public key is the result of the aggregation of a subset of a known set. You can see how this is useful for consensus proofs produced by a known validator set in POS consensus. This is done with the aid of half-cycles of elliptic curves. These half-cycles allow for embedding the field elements of an inner curve (which represents the public keys) within the scalar field of the outer curve. Where you can do polynomial commitments and opening proofs for the SNARK proof. Cycles of curves were first introduced for the purpose of recursive SNARK proof verification.


I refer to the inner curve which is the native curve of the public keys as EinnE_{inn}. For an elliptic curve half-cycle, it should be the case that the characteristic of the base field of the inner curve Einn(Fp)E_{inn}(\mathbb{F}_p) is the same as the scalar field of the outer curve Eout(Fr)E_{out}(\mathbb{F}_r). Let HH be a suitably chosen multiplicative subgroup in the scalar field of the outer curve Eout(Fr)E_{out}(\mathbb{F}_r) .


First we need to arithmetise elliptic curve point addition. Recall the elliptic curve addition formula P+Q=RP+ Q = R for a short weierstrass curve, The slope λ\lambda between the two points is given as

λ=y2y1x2x1\lambda = \frac{y_2-y_1}{x_2-x_1}

Such that:

x3=λ2x1x2y3=λ(x1x3)y1\begin{split} x_3 &= \lambda^2 - x_1 - x_2 \\ y_3 &= \lambda(x_1-x_3) - y_1 \end{split}

Substituting λ\lambda we get

x3=(y2y1x2x1)2x1x2x1+x2+x3=(y2y1x2x1)2(x1+x2+x3)(x2x1)2(y2y1)2=0\begin{split} x_3 = (\frac{y_2-y_1}{x_2-x_1})^2 - x_1 - x_2 \\ x_1 + x_2 +x_3 = (\frac{y_2-y_1}{x_2-x_1})^2 \\ (x_1 + x_2 +x_3)(x_2 - x_1)^2 - (y_2-y_1)^2 = 0 \end{split}

In the same manner, we constrain the value for y3y_3

y3=(y2y1x2x1)(x1x3)y1y1+y3=y2y1x2x1(x1x3)(y1+y3)(x2x1)(y2y1)(x1x3)=0\begin{split} y_3 = (\frac{y_2-y_1}{x_2-x_1})(x_1-x_3) - y_1 \\ y_1 + y_3 = \frac{y_2-y_1}{x_2-x_1} \cdot (x_1-x_3)\\ (y_1 + y_3)(x_2-x_1) - (y_2-y_1)(x_1-x_3) = 0 \end{split}

The goal is to show that apk=i=0n1pkibiapk = \sum^{n-1}_{i=0} pk_i \cdot b_i, where pkpk is a vector of known public keys and bb is a bitvector indicating the signers. We’ll do so by means of an accumulator. Observe that we can write

(kaccxi+1,kaccyi+1)=(kaccxi,kaccyi)bi(pkxi,pkyi)(kaccx_{i+1}, kaccy_{i + 1}) = (kaccx_{i}, kaccy_{i}) \oplus b_i \cdot (pkx_i, pky_i)

Where pk{x,y}pk\{x,y\} are the affine coordinates of the potential signers and kacc{x,y}kacc\{x,y\} is the accumulator sum.

APK Proof Circuit

constraining with bb we get:

b((y2y1)2(x1+x2+x3)(x2x1)2)+(1b)(y3y1)=0b((y2y1)(x1x3)(y1+y3)(x2x1))+(1b)(x3x1)=0b((y_2-y_1)^2 - (x_1 + x_2 +x_3)(x_2 - x_1)^2) + (1-b)(y_3 - y_1) = 0 \\ b((y_2-y_1)(x_1-x_3) - (y_1 + y_3)(x_2-x_1)) + (1-b)(x_3-x_1) = 0

Lifting these equations to polynomial constraints:

id1(X)=(Xωn1)(b(X)((pky(X)kaccy(X))2(kaccx(X)+pkx(X)+kaccx(ωX))(pkx(X)kaccx(X))2)+(1b(X))(kaccy(ωX)kaccy(X)))id2(X)=(Xωn1)(b(X)((pky(X)kaccy(X))(kaccx(X)kaccx(ωX))(kaccy(X)+kaccy(ωX))(pkx(X)kaccx(X)))+(1b(X))(kaccx(ωX)kaccx(X)))\begin{split} id_1(X) &= (X-\omega^{n-1})(b(X)((pky(X)-kaccy(X))^2 - (kaccx(X) + pkx(X) + kaccx(\omega \cdot X))(pkx(X) - kaccx(X))^2) + (1-b(X))(kaccy(\omega \cdot X) - kaccy(X))) \\ id_2(X) &= (X-\omega^{n-1})(b(X)((pky(X)-kaccy(X))(kaccx(X)-kaccx(\omega \cdot X)) - (kaccy(X) + kaccy(\omega \cdot X))(pkx(X)-kaccx(X))) + (1-b(X))(kaccx(\omega \cdot X)- kaccx(X))) \end{split}


pkx(X)=Li(X)pkxipky(X)=Li(X)pkyikaccx(X)=Li(X)kaccxikaccy(X)=Li(X)kaccyib(X)=Li(X)bi\begin{split} pkx(X) &= \mathcal{L}_i(X) \cdot pkx_i \\ pky(X) &= \mathcal{L}_i(X) \cdot pky_i \\ kaccx(X) &= \mathcal{L}_i(X) \cdot kaccx_i \\ kaccy(X) &= \mathcal{L}_i(X) \cdot kaccy_i \\ b(X) &= \mathcal{L}_i(X) \cdot b_i \\ \end{split}

Assume Li(X)\mathcal{L}_i(X) are Lagrange polynomials in the domain HH. The verifier has commitments to CpkxC_{pkx} and CpkyC_{pky}. They’ll receive the commitments and opening proofs for the polynomials, Ckaccx,CkaccyC_{kaccx}, C_{kaccy} and CbC_b. Which allows them to check the above polynomial constraints. Next we need to constrain the circuit inputs. We initialise the accumulator with a chosen point hEinnh \in \mathbb{E}_{inn}. Such that:

(kaccx0,kaccy0)=(hx,hy)(kaccxn1,kaccyn1)=(apkx,apky)(hx,hy)(kaccx_0, kaccy_0) = (h_x, h_y) \\ (kaccx_{n-1}, kaccy_{n-1}) = (apk_x, apk_y) \oplus (h_x, h_y)

We’ll constrain using these equations.

(kaccx0hx)+(kaccxn1(apkx+hx))=0(kaccy0hy)+(kaccyn1(apky+hy))=0(kaccx_0 - h_x) + (kaccx_{n-1} - (apk_x + h_x)) = 0 \\ (kaccy_0 - h_y) + (kaccy_{n-1} - (apk_y + h_y)) = 0

Lifting to polynomial constraints

id3(X)=L0(X)(kaccx(X)hx)+Ln1(kaccx(X)(apkx+hx))id4(X)=L0(X)(kaccy(X)hy)+Ln1(kaccy(X)(apky+hy))id_3(X) = \mathcal{L}_0(X)(kaccx(X) - h_x) + \mathcal{L}_{n-1} (kaccx(X) - (apk_x + h_x)) \\ id_4(X) = \mathcal{L}_0(X)(kaccy(X) - h_y) + \mathcal{L}_{n-1} (kaccy(X) - (apk_y + h_y))

Finally the prover has to show that each bi{0,1}b_i \in \{0, 1\}. They’ll do so using the polynomial constraint

id5(X)=b(X)(1b(X))id_5(X) = b(X)(1 - b(X))

In the Basic Accountable scheme, the bitvector is represented using individual field elements of the inner curve. This can be particularly expensive. In order to reduce space complexity of the bitlist and produce proofs of larger sets, it becomes necessary for the prover to represent the signers using the binary representation of each field element. This is more compact and saves significant communication complexity when dealing with signers of size 2202^{20} and above.

The paper introduces two new polynomials in it’s Packed Accountable Ranged scheme. First we must understand that any number zz can be re-written as an inner product of its binary representation and powers of 2. This also known as binary decomposition.

z=2i,zi=i=0n12izi\begin{split} z &= \langle2^i, z_i \rangle \\ &= \sum^{n -1}_{i = 0} 2^i \cdot z_i \\ \end{split}

First we define blockblock as the maximum number of bits in the binary representation in the field element we’ll use to represent chunks of our bitlist. The verifier can simply check that the pre-approved number of bits are used on in each of the field elements provided by the prover.

0countOnes(b)<block0 \le countOnes(b^\prime) < block

In order to use binary decomposition tricks, it’s necessary blockblock is a power of 2. ie block=2k<nblock = 2^k < n. Rather than a bitlist, the prover provides a vector of field elements bb^\prime

b=(b0,,bnblock1)\begin{split} b^\prime &= (b^\prime_0, \dots, b^\prime_{\frac{n}{block} - 1})\\ \end{split}

where each bjEinn(Fp)b^\prime_j \in E_{inn}(\mathbb{F}_p) can be seen as

bj=i=0block12ib(blockj)+ib^\prime_j = \sum^{block - 1}_{i = 0} 2^i \cdot b_{(block \cdot j) + i}

The verifier wants to know that the bitlist encoded in the binary representation of bb^\prime is equal to b(X)b(X). We do so by means of a range proof. Observe that

sum=j=0nblock1bjrj=j=0nblock1(i=0block12ib(blockj)+i)rj=i=0n12imodblockbiri÷block\begin{split} sum &= \sum^{\frac{n}{block} - 1}_{j = 0} b^\prime_j \cdot r^j \\ &= \sum^{\frac{n}{block} - 1}_{j = 0} (\sum^{block - 1}_{i = 0} 2^i \cdot b_{(block \cdot j) + i} ) \cdot r^j \\ &= \sum^{n - 1}_{i = 0} 2^{i \mod{block}} \cdot b_i \cdot r^{i \div block} \end{split}

We begin by decomposing the final equation. First lets define a selector polynomial aux(X)aux(X)

aux(X)=i=0n1auxiLi(X)aux(X) = \sum^{n - 1}_{i = 0} aux_i \cdot \mathcal{L}_i(X)

Where auxiaux_i is given as

auxi={1iblock0iblockaux_i = \begin{cases} 1 & i \mid block \\ 0 & i \nmid block \end{cases}

Note that 0 is divisible by any xx. Next we define

ca(X)=i=0n1ca,iLi(X)c_a(X) = \sum^{n - 1}_{i = 0} c_{a,i} \cdot \mathcal{L}_i(X)


ca,i=2imodblockriblockc_{a,i} = 2^{i \mod{block}} \cdot r^{\frac{i}{block}}

The prover must then show that the following polynomial is zero over HH

id6(X)=ca(ωX)ca(X)(2+(r2block12)aux(ωX))(1rnblock)Ln1(X)\begin{split} id_{6}(X) = c_a(\omega \cdot X) - c_a(X) \cdot (2 + (\frac{r}{2^{block - 1}} - 2) \cdot aux(\omega \cdot X)) - (1 - r^{\frac{n}{block}}) \cdot \mathcal{L}_{n-1}(X) \end{split}

Lets consider the case when iblocki \nmid block , we have that:

id6(ωi)=ca(ωωi)(ca(ωi)2)=(2(imodblock)+1riblock)((2imodblockriblock)2)=riblock(2(imodblock)+12(imodblock)+1)\begin{split} id_{6}(\omega^i) &= c_a(\omega \cdot \omega^i) - (c_a(\omega^i) \cdot 2) \\ &= (2^{(i \mod{block}) + 1} \cdot r^{\frac{i}{block}}) - ((2^{i \mod{block}} \cdot r^{\frac{i}{block}}) \cdot 2) \\ &= r^{\frac{i}{block}}(2^{(i \mod{block}) + 1} - 2^{(i \mod{block}) + 1}) \\ \end{split}

Lets consider the second case when iblocki \mid block , we have that:

id6(ωi)=ca(ωωi)ca(ωi)(2+(r2block12))1=(20r(iblock)+1)(2block1riblock)(r2block1)=r(iblock)+1r(iblock)+1\begin{split} id_{6}(\omega^i) &= c_a(\omega \cdot \omega^i) - c_a(\omega^i) \cdot (2 + (\frac{r}{2^{block - 1}} - 2)) \cdot 1 \\ &= (2^0 \cdot r^{(\frac{i}{block}) + 1}) - (2^{block - 1} \cdot r^{\frac{i}{block}}) \cdot (\frac{r}{2^{block - 1}}) \\ &= r^{(\frac{i}{block}) + 1} - r^{(\frac{i}{block}) + 1} \end{split}

Finally lets consider the case where i=n1i = n-1, It’s easy to see that ca,0=1c_{a,0} = 1. Therefore

id6(ωn1)=1(2block1rnblock1)(2+(r2block12)1)(1rnblock)1=(1rnblock1r)(1rnblock)=(1rnblock)(1rnblock)\begin{split} id_{6}(\omega^{n-1}) &= 1 - (2^{block-1} \cdot r^{\frac{n}{block} - 1}) \cdot (2 + (\frac{r}{2^{block - 1}} - 2) \cdot 1) - (1 - r^{\frac{n}{block}}) \cdot 1 \\ &= (1 - r^{\frac{n}{block} - 1} \cdot r) - (1 - r^{\frac{n}{block}}) \\ &= (1 - r^{\frac{n}{block}}) - (1 - r^{\frac{n}{block}}) \end{split}

The polynomial id6(X)id_6(X) constrains the form of cai[0,(2imodblockriblock)]i[0,n1)c_{a_i} \in [0, (2^{i \mod{block}} \cdot r^{\frac{i}{block}})] \forall i \in [0, n-1). Next we introduce an accumulator polynomial for ca,ic_{a, i}.

acca(X)=acca,iLi(X)acc_a(X) = acc_{a, i} \cdot \mathcal{L}_i(X)

where acca,iacc_{a, i} are the components of the vector:

[0,bitica,0,(bit0ca,0)+(bit1ca,1),,i=0n2(bitica,i)][0, bit_i \cdot c_{a, 0}, (bit_0 \cdot c_{a,0}) + (bit_1 \cdot c_{a,1}), \dots, \sum^{n-2}_{i = 0}(bit_i \cdot c_{a, i})]

The prover must show that the following polynomial evaluates to zero over HH

id7(X)=acca(ωX)acca(X)(b(X)ca(X))+sumLn1(X)\begin{split} id_7(X) = acc_a(\omega \cdot X) - acc_a(X) - (b(X) \cdot c_a(X)) + sum \cdot \mathcal{L}_{n-1}(X) \end{split}

Observe that

acca(ωX)acca(X)=bitica,i=b(X)ca(X)\begin{split} acc_a(\omega \cdot X) - acc_a(X) &= bit_i \cdot c_{a, i} \\ &= b(X) \cdot c_a(X) \end{split}


id7(ωi)=(b(ωi)ca(ωi))(b(ωi)ca(ωi))\begin{split} id_7(\omega^i) = (b(\omega^i) \cdot c_a(\omega^i)) - (b(\omega^i) \cdot c_a(\omega^i)) \end{split}

Considering the case when i=n1i =n-1

id7(ωn1)=0(i=0n2(bitica,i))(b(ωn1)ca(ωn1))+sum1=sum+sum\begin{split} id_7(\omega^{n-1}) &= 0 - (\sum^{n-2}_{i = 0}(bit_i \cdot c_{a, i})) - (b(\omega^{n-1}) \cdot c_a(\omega^{n-1})) + sum \cdot 1 \\ &= -sum + sum \end{split}

This convinces the verifier that b(X)b(X) is equivalent to bb^\prime. Finally the apk proof constraint polynomial t(X)t(X) is given as:

t(X)(Xn1)=id1(X)(Xωn1)+αid2(X)(Xωn1)+α2id3(X)+α3id4(X)+α4id5(X)+α5id6(X)+α6id7(X)\begin{split} t(X)(X^n-1) &= id_1(X)(X- \omega^{n-1}) + \alpha \cdot id_2(X)(X-\omega^{n-1}) + \alpha^2 \cdot id_3(X) + \alpha^3 \cdot id_4(X) + \alpha^4 \cdot id_5(X)+ \alpha^5 \cdot id_6(X)+ \alpha^6 \cdot id_7(X) \\ \end{split}

Or in expanded form

t(X)(Xn1)=(Xωn1)(b(X)((pky(X)kaccy(X))2(kaccx(X)+pkx(X)+kaccx(ωX))(pkx(X)kaccx(X))2)+(1b(X))(kaccy(ωX)kaccy(X)))+α(Xωn1)[b(X)((pky(X)kaccy(X))(kaccx(X)kaccx(ωX))(kaccy(X)+kaccy(ωX))(pkx(X)kaccx(X)))+(1b(X))(kaccx(ωX)kaccx(X))]+α2[L0(X)(kaccx(X)hx)+Ln1(kaccx(X)(apkx+hx))]+α3[L0(X)(kaccy(X)hy)+Ln1(kaccy(X)(apky+hy))]+α4[b(X)(1b(X))]+α5[ca(ωX)ca(X)(2+(r2block12)aux(ωX))(1rnblock)Ln1(X)]+α6[acca(ωX)acca(X)(b(X)ca(X))+sumLn1(X)]\begin{split} t(X)(X^n-1) &= (X-\omega^{n-1})(b(X)((pky(X)-kaccy(X))^2 - (kaccx(X) + pkx(X) + kaccx(\omega \cdot X))(pkx(X) - kaccx(X))^2) + (1-b(X))(kaccy(\omega \cdot X) - kaccy(X))) \\ &+ \alpha (X-\omega^{n-1}) \cdot [b(X)((pky(X)-kaccy(X))(kaccx(X)-kaccx(\omega \cdot X)) - (kaccy(X) + kaccy(\omega \cdot X))(pkx(X)-kaccx(X))) + (1-b(X))(kaccx(\omega \cdot X)- kaccx(X)) ] \\ &+ \alpha^2 \cdot [\mathcal{L}_0(X)(kaccx(X) - h_x) + \mathcal{L}_{n-1} (kaccx(X) - (apk_x + h_x)) ] \\ &+ \alpha^3 \cdot [\mathcal{L}_0(X)(kaccy(X) - h_y) + \mathcal{L}_{n-1} (kaccy(X) - (apk_y + h_y)) ] \\ &+ \alpha^4 \cdot [b(X)(1 - b(X))] \\ &+ \alpha^5 \cdot [c_a(\omega \cdot X) - c_a(X) \cdot (2 + (\frac{r}{2^{block - 1}} - 2) \cdot aux(\omega \cdot X)) - (1 - r^{\frac{n}{block}}) \cdot \mathcal{L}_{n-1}(X)] \\ &+ \alpha^6 \cdot [acc_a(\omega \cdot X) - acc_a(X) - (b(X) \cdot c_a(X)) + sum \cdot \mathcal{L}_{n-1}(X)] \\ \end{split}

Where αEout(Fr)\alpha \in E_{out}(\mathbb{F}_r) is a value chosen by the verifier. Given this constraint polynomial, it’s trivial to lift this further into SNARK using the PLONK protocol or any of it’s variants.


[1]^{[1]} Accountable Light Client Systems for PoS Blockchains, Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, and Sergey Vasilyev.