Research Update: APK Proofs By Hand and Sage
APK proofs is a protocol, designed [2] and implemented [4] by Web3 Foundation Researchers, that allows a verifier to verify a statement signed by a subset of a signatory committee (e.g. set of validators) without knowing the individual public key of each member. Indeed, if we assume that the verifier has received a (constant size) verified commitment to the public keys of the members of the committee, then the only information the verifier needs to verify the correctness of an aggregated signature is an indication of who has participated in the signing plus a constant size proof provided by this protocol.
Note that in APK proofs the commitment to all committee keys is simply two points on an elliptic curve which is of constant length no matter how many members the committee has.
Using mainstream Web2.0 digital signature algorithms such as ed25519, one needs to know all N public keys of the committee members if the committee has N members, plus M signatures when M is the number of members in the signatory sub-committee. Using constant length aggregatable signature schemes such as BLS, one could reduce the signature data cost from M to 1 signature. Nonetheless, the verifier still needs the public keys from every sub-committee member, which requires the list of N public keys on change of the committee. Additionally, it involves a computation of 𝓞 (M) complexity on each aggregation.
The fascinating aspect of APK proofs is that they reduce both of these costs to 𝓞 (1) in addition to an N-bit vector indicating who has participated in signing of the message. Similar to many other succinct arguments, APK proofs benefits from the magic of SNARKs to achieve this. SNARKs were the main focus of the ZK Learning MOOC course([5]) that I attended during the winter 2023 semester. The SNARKs employed in APK proofs are inspired by PLONK (introduced in Lecture 5 of ZK MOOC course) and its predecessor AIR[1]. So I thought digging into the details and explaining the nuts and bolts of APK proofs SNARK would not only make a good article to fulfill the course requirement for obtaining the Ninja status but also make APK proofs more accessible to other researchers and developers who might benefit from this protocol in their systems.
During my study of the course, I read and enjoyed the “PLONK by Hand” series ([3]) and I thought of using the same concept to explain APK proofs. With the caveat that I am going to use SageMath[6] as a calculator for anything that requires algebra peripherally to the mathematics of interactive proofs. I am also going to piggyback on PLONK by Hand[3]’s computation and borrow the parts that I can use here without recomputing them.
The rest of this article is organized as follows: In Section 1, I describe the problem that APK proofs solve. Section 2 describes the details of the polynomial IOP used in APK proofs. In 3, I explain the toy example we try to prove and verify in this article. Finally in Section 4 I explain and compute every step the prover and verifier need to take to run the APK proofs to establish the validity of the toy example.
1. The Goal
We already informally discussed the purpose of APK proofs protocol as providing a succinct proof that a “specific” (as opposed to any) M-member subcommittee of an N member committee has signed a particular message. To formalize this we introduce the following notations.
First we assume that the committee is represented by the following set:
And their public keys are represented as:
Where each pair represents the x and y coordinates of the points on the elliptic curves corresponding to the public key of member i. Let S be the subcommittee whose member has signed message Msg and
Be the aggregated signature of them:
Where σⱼ (Msg) is the signature corresponding to member j ∈S. To identify S and to indicate who has signed the message Msg we use the bit-vector b = (bᵢ) :i ∈ {0, …, N-1} such that
Accordingly aggregated public key of the signers is computed as
(1)
Therefore when the verifier is given σ (Msg) and the correct apkₛ, they can simply verify the signature by running:
where e is a bilinear pairing function defined on the elliptic curve.
But the whole question is how to make sure that a given apkₛ is the correct one. In a world in which we have no data and computation complexity concerns, we could easily re-run and verify Equation 1 to make sure that apkₛ is correct. But our verifier is data-wise and computationally restrained and we would like to verify Equation 1 without receiving all pkᵢ’s. Here, foreseeably, SNARKs are coming to the rescue.
2. The APK proofs’ SNARKs
APK proofs SNARKs are based on a polynomial protocol and polynomial commitments. So we are going to define a set of polynomial relationships between the coordinates of the public key points of the committee members. If the prover is able to convince the verifier that these relationships hold, then the verifier can be sure that the aggregated public key of the subcommittee is correct.
First thing first, we need to mathematically re-label each member of the committee instead of {0,1, 2, …, N — 1 } to make verification of those polynomial relationships more efficient. This relabeled set is called “evaluation domain” in zk-SNARK jargon. Similar to PLONK, Nᵗʰ roots of unity in some suitable prime field will be our choice and we assume that N is actually a power of 2. We fix a primitive Nᵗʰ root of unity ω and accordingly we label the committee member i ∈ C with ωⁱ .
Now we can specify our auxiliary polynomials as follows:
and recover them using Lagrange interpolation.
The ones that are more tricky are kaccx (X) and kaccy (X) which are those tracking the aggregation of the subcommittee public keys. First we define
where (hₓ, hᵧ) is a random point on the curve which should either reside outside of the public key subgroup or it should be chosen randomly by the verifier after the commitment to committee keys has been computed. Then we define (kaccxᵢ, kaccyᵢ) recursively as
where the ⊕ addition happens on the elliptic curve group where the public keys live on. So the corresponding polynomials are defined as
Are our remaining auxiliary polynomials. Having all of our auxiliary polynomials set, the prover needs to prove that the following polynomials:
(2)
are vanishing over
As to why this is enough to prove that that aggregation has been correctly done, we give some intuition here but for a rigorous proof you need to check the APK proofs’s paper [2].
Id₅ just makes sure that the prover only used a true boolean vector for b. Id₄ makes sure that the initial and and final values of kaccx and kaccy match the values known to the verifier (h and apk).
Id₁ and Id₂ are coming from Elliptic curve addition formulas and basically tracking changes (or not) to the aggregated key at every step of aggregation one public key at the time.
We are finally ready to get our hands dirty, instantiate our system using concrete numbers and generate a proof of an apkₛ in the next sections.
3. Setting up
We are going to make an APK proof for a committee of 3 signers where one of them has been absent and has not participated in the signing of the message. As BLS signatures and the KZG polynomial commitment scheme used in APK proofs are both defined over elliptic curves groups we need to choose some curves before we model our problem mathematically.
3.1 Choosing Elliptic Curves
First suppose that BLS public keys are defined over curve Eᵢₙₙₑᵣ (𝔽q). This means that pkxᵢ and pkyᵢ s are elements of 𝔽q. So when we are going to run Lagrange interpolation to recover our auxiliary polynomials they will be naturally defined over 𝔽q. Now suppose we want to commit to polynomial P (x)
using KZG commitment. KZG commitment is performed by choosing a secret value τ, computing points of { τ G, …, τⁿ G } on some elliptic curve Eₒᵤₜₑᵣ (𝔽q’)} and for forgetting τ afterward. So the discrete logarithm of these points is not known by anyone. Then one “evaluates P at τ” by
where the addition is done on the elliptic curve subgroup generated by G. As such, we need to be able to interpret aᵢ’s as the scalars of Eₒᵤₜₑᵣ}’s prime subgroup. Therefore, Eₒᵤₜₑᵣ needs to have a subgroup of size equal to | 𝔽q | = q. Moreover, Eₒᵤₜₑᵣ needs to be a pairing friendly so the verifier is actually able to verify the KZG commitments using pairing. This is similar to the situation that arose and is described in lecture 10 of the course [5] in the design of recursive SNARKs).
To piggyback on the PLONK by hands blog post[3], we are going to use the same elliptic curve they have prepared for KZG commitment as Eₒᵤₜₑᵣ:
defined over 𝔽₁₀₁ which has a subgroup of prime order 17. So q = 17 and q’ = 101. As a 16ᵗʰ-root of unity is a generator of the multiplicative group of 𝔽₁₇, in theory we could have a committee of at most 15 validator size. But in our example we only have a 3-member committee where 2 of them have signed the statement. So 𝔽₁₇ is more than enough for us.
Now with us using BLS signatures, we also need that Eᵢₙₙₑᵣ to be a pairing friendly curve as BLS signatures are also being verified using pairing functions. However, nowhere in running APK proofs do we need to verify the BLS signature itself. We only verify that an aggregate public key is actually aggregated correctly, which only requires addition functionality on Eᵢₙₙₑᵣ and the verifier never actually needs to use the pairing functionality (on Eᵢₙₙₑᵣ) until after they have verified that the aggregated public key is correct. So we can safely go ahead and choose a curve which gives us a big enough subgroup and not be worried if it is pairing friendly or not.
All we care for now is that we need to be able to get 3 distinct public keys, one for each committee member and one extra point h in 𝓖 ⊲ Eᵢₙₙₑᵣ beside the identity point at infinity (because we want to stick to affine representation of the curve in our computations). So the size of 𝓖 should be greater than 4. This should not be a problem as the size of the elliptic curves over 𝔽₁₇ could be as big 17 + 2 × 4 + 1 = 26 by Hesse’s lemma. So we just try random curves on Sage till we hit one with a prime subgroup of a respectable size.
We ran a script to generate all curves defined over 𝔽₁₇ and settled on y² = x³ + 2 x + 2 which has | 𝓖 | = | Eᵢₙₙₑᵣ (𝔽₁₇) | = 19. This allows us to have distinct public keys for each members of a committee of maximum size which is 15 because we are tagging the members with roots of unities in 𝔽q = 𝔽₁₇. Moreover it is a prime ordered elliptic curve so we don’t need to worry about falling out of the subgroup. And it actually has the embedding degree of 9 because 17⁹ — 1 = 19 × 6241467184. So if we need to actually verify a BLS signature it is a doable task as there is an embedding from this curve into 𝔽17⁹ which is not insanely huge.
>>>
E_inner = EllipticCurve([GF(17)(2),GF(17)(2)])
>>>E_inner
y² = x³ + 2 x + 2
>>>E_inner.abelian_group()
ℤ 19 ℤ
>>>E_inner.points()
[ (0 : 1 : 0), (0 : 6 : 1), (0 : 11 : 1), (3 : 1 : 1), (3 : 16 : 1), (5 : 1 : 1), (5 : 16 : 1), (6 : 3 : 1), (6 : 14 : 1), ( 7 : 6 : 1 ), (7 : 11 : 1), (9 : 1 : 1), (9 : 16 : 1), (10 : 6 : 1), (10 : 11 : 1), (13 : 7 : 1), (13 : 10 : 1), (16 : 4 : 1), (16 : 13 : 1) ]
>>>
We choose an arbitrary generator < 3, 1 > and we set 𝓖in = < (3, 1) >we can then produce the logarithm table for 𝓖in:
>>>for i in range(0,20):
print(i,"(3,1):",i*E_inner(3,1))
0 (3,1): (0 : 1 : 0)
1 (3,1): (3 : 1 : 1)
2 (3,1): (13 : 7 : 1)
3 (3,1): (0 : 11 : 1)
4 (3,1): (10 : 11 : 1)
5 (3,1): (5 : 1 : 1)
6 (3,1): (9 : 16 : 1)
7 (3,1): (7 : 6 : 1)
8 (3,1): (16 : 4 : 1)
9 (3,1): (6 : 14 : 1)
10 (3,1): (6 : 3 : 1)
11 (3,1): (16 : 13 : 1)
12 (3,1): (7 : 11 : 1)
13 (3,1): (9 : 1 : 1)
14 (3,1): (5 : 16 : 1)
15 (3,1): (10 : 6 : 1)
16 (3,1): (0 : 6 : 1)
17 (3,1): (13 : 10 : 1)
18 (3,1): (3 : 16 : 1)
19 (3,1): (0 : 1 : 0)
>>>
3.2 Statement of the Toy Problem
Evidently we do not need to know members’ private keys to be able to generate and verify the aggregation. So we choose 3 points with small coordinates on Eᵢₙₙₑᵣ as the public key of the members
>>>
pk=[E_inner(5,1),E_inner(7,6), E_inner(6,3)]
>>>
We then suppose that the member with index 1 has been absent from signing and hence:
>>>
apk=pk[0]+pk[2]
>>>apk
(10 : 6 : 1)
>>>
And for the prover to prove that indeed
they need to compute the auxiliary polynomials, commit to them and open them at random points at the request of the verifier, so the verifier could believe that polynomial relationships in 2 actually hold. The details of how this is done in APK proofs is presented in the next chapter.
4. Prove and Verify the APK
First we need to make our evaluation domain explicit. We have 3 members and we need to represents them with various 4ᵗʰ root of unity in 𝔽₁₇. This has been computed in [3] and similarly we choose:
so
Now we are ready to interpolate our auxiliary polynomials, we start with b (X) :
>>>
omega = GF(17)(4)
>>>
b = [1,0,1]
>>>
points = [(omega^i, b[i]) for i in range(3)]
>>>
R.<X> = GF(17)[]
>>>
b_poly = R.lagrange_polynomial(points)
>>>points
[(1, 1), (4, 0), (16, 1)]
>>>b_poly
9 X² + 9
>>>
Similarly we compute pkx (X) and pky (X):
>>>
pkx = [ 5, 7, 6]
>>>
pky = [ 1, 6, 3]
>>>
points = [(omega^i, pkx[i]) for i in range(3)]
>>>points
[(1, 5), (4, 7), (16, 6)]
>>>
pkx_poly = R.lagrange_polynomial(points)
>>>pkx_poly
11 X² + 8 X + 3
>>>
points = [(omega^i, pky[i]) for i in range(3)]
>>>points
[(1, 1), (4, 6), (16, 3)]
>>>
pky_poly = R.lagrange_polynomial(points)
>>>pky_poly
13 X² + 16 X + 6
>>>
Now we compute the recursive auxiliary polynomials kaccx (X) and kaccy (X). The verifier pick the arbitrary h = (hx, hy) = (3, 1) using a uniformly random sampling (note that we have chosen a prime ordered curve so there is no choice of h ∈ Eᵢₙₙₑᵣ \𝓖ᵢₙ) and so we can compute kaccxᵢ and kaccyᵢ:
>>>
h = E_inner(3,1)
>>>
kacc = [h]
>>>
for i in range(1,4):
kacc.append(kacc[i-1]+b[i-1]*pk[i-1])>>>kacc
[(3 : 1 : 1), (9 : 16 : 1), (9 : 16 : 1), (0 : 6 : 1)]
>>>
Now we are able to interpolate kaccx and kaccy
>>>
points = [(omega^i, kacc[i][0]) for i in range(4)]
>>>
kaccx_poly = R.lagrange_polynomial(points)
>>>kaccx_poly
16 X³ + 5 X² + 15 X + 1
>>>
points = [(omega^i, kacc[i][1]) for i in range(4)]
>>>
kaccy_poly = R.lagrange_polynomial(points)
>>>kaccy_poly
2 X³ + 3 X² + 16 X + 14
>>>
Now that we have all our auxiliary polynomials we can commit to them and send the commitment to the verifier.
We are using the same SRS as in [3] which has a secret τ = 2. The maximum degree polynomial we are working with is of degree 12 (though we actually commit to polynomials of at most degree 8). So a SRS of size 13 should suffice. So we have our prover key as follows:
>>>
E_outer = EllipticCurve([GF(101)(0), GF(101)(3)])
>>>E_outer
y² = x³ + 3
>>>
G1Gen = E_outer(1,2)
>>>
tau = 2
>>>
SRS = [tau^i*G1Gen for i in range(13)]
>>>SRS
[(1 : 2 : 1), (68 : 74 : 1), (65 : 98 : 1), (18 : 49 : 1), (1 : 99 : 1), (68 : 27 : 1), (65 : 3 : 1), (18 : 52 : 1), (1 : 2 : 1), (68 : 74 : 1), (65 : 98 : 1), (18 : 49 : 1), (1 : 99 : 1)]
>>>
We write a snippet for KZG commitment so we don’t need to repeat it:
>>>
def kzg_commit_to(p):
return sum([p.coefficients(sparse=false)[i]*SRS[i] for i in range(p.degree()+1)])>>>
Now we can commit to all five auxiliary polynomials:
>>>
commitment_to_b_poly = kzg_commit_to(b_poly)
>>>commitment_to_b_poly
(32 : 59 : 1)
>>>
commitment_to_pkx_poly = kzg_commit_to(pkx_poly)
>>>commitment_to_pkx_poly
(12 : 69 : 1)
>>>
commitment_to_pky_poly = kzg_commit_to(pky_poly)
>>>commitment_to_pky_poly
(12 : 32 : 1)
>>>
commitment_to_kaccx_poly = kzg_commit_to(kaccx_poly)
>>>commitment_to_kaccx_poly
(18 : 52 : 1)
>>>
commitment_to_kaccy_poly = kzg_commit_to(kaccy_poly)
>>>commitment_to_kaccy_poly
(32 : 42 : 1)
>>>
We are sending all above commitments to the verifier to prepare for the next step.
Now the verifier needs to make sure that idᵢ is zero on all elements of Ω. This is the Zero Test described in lecture 5 of the course [5] and boils down to proving that id₁ is divisible by X⁴ — 1 = ∏i =0 ³ X — ωⁱ. The prover does that by computing the quotient and committing to it:
We only perform this procedure for id₁ to keep this guide simple and short. The procedure is similar for all the rest and in the actual protocol the prover performs this for a linear combination of idᵢ’s instead of doing it one by one. We recall
>>>
id_1 = (X — omega³)*(b_poly(X)*((kaccx_poly(X)-pkx_poly(X))²*(kaccx_poly(X)+pkx_poly(X)+kaccx_poly(omega*X))-(pky_poly(X)-kaccy_poly(X))²)+(1-b_poly(X))*(kaccy_poly(omega*X)-kaccy_poly(X)))
>>>id_1
10 X¹² + 4 X¹¹ + 15 X¹⁰ + 3 X⁹ + 9 X⁸ + 7 X⁷ + 7 X⁶ + 15 X⁵ + X⁴ + 6 X³ + 12 X² + 16 X + 14
>>>
q_1 = id_1/(X⁴-1)
>>>q_1.denominator()
1
>>>
q_1_poly = q_1.numerator()
>>>q_1_poly
10 X⁸ + 4 X⁷ + 15 X⁶ + 3 X⁵ + 2 X⁴ + 11 X³ + 5 X² + X + 3
>>>
The q₁ is too big to be sent to the verifier, so instead first the prover sends a commitment to q₁.
>>>
commitment_to_q_1_poly = kzg_commit_to(q_1_poly)
>>>commitment_to_q_1_poly
(32 : 42 : 1)
>>>
And then the verifier asks us to open id₁ and q₁ at a random point r and if the equality of q₁ (r) =id₁ (r)/(r⁴ — 1) holds then by Schwartz-Zippel lemma it is likely to be true for any X:
>>>GF(17).random_element()
10
>>>
Because the verifier only has a commitment to the auxiliary polynomials and q₁ they ask us to open all these polynomials in the random point they have chosen and then compute id₁ at that point themselves.
So the prover then opens all 6 polynomials at 10:
>>>b_poly(10), pkx_poly(10), pky_poly(10), kaccx_poly(10), kaccy_poly(10), q_1_poly(10)
(8, 10, 4, 8, 9, 5)
>>>
The verifier needs to verify that the prover has been honest with the opening value. This is done by the KZG pairing test. This can be batched and done all at once but we only perform it for kaccx to keep the procedure simple. The prover needs to compute the quotient:
>>>
q_accx_10 = (kaccx_poly(X)-kaccx_poly(10))/(X-10)
>>>q_accx_10.denominator()
1
>>>
q_accx_10 = q_accx_10.numerator()
>>>q_accx_10
16 X² + 12 X + 16
>>>
Now the verifier does not have the polynomials so they need to verify it using KZG pairing. For that they need a commitment to qaccx∘10 which the provers provides:
>>>
commitment_to_q_accx_10 = kzg_commit_to(q_accx_10)
>>>commitment_to_q_accx_10
(68 : 74 : 1)
>>>
The idea is that if
Where e is a pairing function on Eₒᵤₜₑᵣ .}
For which we need to compute (τ — 10) G 2 Gen which require the verification key τ G 2 Gen, G2Gen which has been computed as part of the ceremony in [3] (note there is a typo there mixing up G2Gen’s coordinates) . G 2 Gen is the prime order group of Eₒᵤₜₑᵣ (𝔽₁₇ (u)) such that u² + 2 = 0. So to get G2 we need to extend the elliptic curve group to contain points with coordinates in 𝔽₁₇(u):
>>>
FU.<U> = GF(101)[]
>>>
Fu.<u> = GF(101).extension(U² + 2)
>>>
Eu_outer = E_outer.base_extend(Fu)
>>>
G2Gen = Eu_outer(36,31*u)
>>>
SRS_verify_key = [G2Gen, tau*G2Gen]
>>>SRS_verify_key
[(36 : 31*u : 1), (90 : 82*u : 1)]
>>>
Now having the SRS verifying key, the verifier can go ahead and use pairing to verify prover’s claim:
We are going to compute each side of the above equation separately and make sure they are equal. We are going to use Tate pairing but any other pairing function should work:
>>>
P = Eu_outer(commitment_to_q_accx_10)
>>>
Q = SRS_verify_key[1] — 10*SRS_verify_key[0]
>>>P.tate_pairing(Q, 17, 2) #= e(P,Q) : 17=ord(P) and 2 is embedding degree of P
28 u + 7
>>>
And then we compute the right hand side:
>>>
P = Eu_outer(commitment_to_kaccx_poly — kaccx_poly(10)*G1Gen)
>>>
Q = SRS_verify_key[0]
>>>P.tate_pairing(Q, 17, 2)
28 u + 7
>>>
So we assume the verifier does the same for the rest of the auxiliary polynomials and q₁ and so they know and believe the opening values for all of them at 10. Therefore they can confidently compute the correct value for id₁ (10) using those:
>>>
id_1_at_10 = (10 — omega³)*(b_poly(10)*((kaccx_poly(10)-pkx_poly(10))²*(kaccx_poly(10)+pkx_poly(10)+kaccx_poly(omega*10))-(pky_poly(10)-kaccy_poly(10))²)+(1-b_poly(10))*(kaccy_poly(omega*10)-kaccy_poly(10)))
>>>id_1_at_10
15
>>>
Now the verifier has everything they need to complete the Zero test to verify that id₁ is divisible by X⁴ — 1
We have the left side equal to 15. So we are going to compute the right hand side:
So by the Schwartz-Zippel lemma it is very likely that id₁ vanishes on Ω . Following the same process on the rest of idᵢ’s, the verifier can be convinced that all are vanishing on Ω and hence the apk is the true aggregation of the public keys of members 0 and 2.
In practice all of the KZG pairing tests and the verifying all the idᵢ’s can be batched and each can be done in a single test. Here, we skipped that optimization in favor of simplicity.
Bibliography
[1]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable zero knowledge with no trusted setup. In Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39, pages 701–732. Springer, 2019.
[2]
Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, and Sergey Vasilyev. Accountable light client systems for pos blockchains. Cryptology ePrint Archive, Paper 2022/1205, 2022. https://eprint.iacr.org/2022/1205.
[3]
Joshua Fitzgerald. Plonk by hand. 2022. https://research.metastate.dev/plonk-by-hand-part-1/.
[4]
Web3.0 Technologies Foundation. Apk proofs: fully succinct bls signature aggregation. 2023. https://github.com/w3f/apk-proofs.
[5]
Zero knowledge proofs MOOC 2023. https://zk-learning.org/.
[6]
The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.8). 2023. https://www.sagemath.org.
