APK proofs is a protocol, designed [2] and applied [4] by Web3 Basis Researchers, that enables a verifier to confirm a press release signed by a subset of a signatory committee (e.g. set of validators) with out realizing the person public key of every member. Certainly, if we assume that the verifier has obtained a (fixed measurement) verified dedication to the general public keys of the members of the committee, then the one info the verifier must confirm the correctness of an aggregated signature is a sign of who has participated within the signing plus a continuing measurement proof offered by this protocol.
Word that in APK proofs the dedication to all committee keys is just two factors on an elliptic curve which is of fixed size regardless of what number of members the committee has.
Utilizing mainstream Web2.0 digital signature algorithms akin to ed25519, one must know all N public keys of the committee members if the committee has N members, plus M signatures when M is the variety of members within the signatory sub-committee. Utilizing fixed size aggregatable signature schemes akin to BLS, one might cut back the signature information value from M to 1 signature. Nonetheless, the verifier nonetheless wants the general public keys from each sub-committee member, which requires the listing of N public keys on change of the committee. Moreover, it entails a computation of 𝓞 (M) complexity on every aggregation.
The fascinating side of APK proofs is that they cut back each of those prices to 𝓞 (1) along with an N-bit vector indicating who has participated in signing of the message. Just like many different succinct arguments, APK proofs advantages from the magic of SNARKs to realize this. SNARKs have been the primary focus of the ZK Studying MOOC course([5]) that I attended through the winter 2023 semester. The SNARKs employed in APK proofs are impressed by PLONK (launched in Lecture 5 of ZK MOOC course) and its predecessor AIR[1]. So I believed digging into the small print and explaining the nuts and bolts of APK proofs SNARK wouldn’t solely make an excellent article to satisfy the course requirement for acquiring the Ninja standing but in addition make APK proofs extra accessible to different researchers and builders who would possibly profit from this protocol of their methods.
Throughout my research of the course, I learn and loved the “PLONK by Hand” sequence ([3]) and I considered utilizing the identical idea to clarify APK proofs. With the caveat that I’m going to make use of SageMath[6] as a calculator for something that requires algebra peripherally to the arithmetic of interactive proofs. I’m additionally going to piggyback on PLONK by Hand[3]’s computation and borrow the elements that I can use right here with out recomputing them.
The remainder of this text is organized as follows: In Part 1, I describe the issue that APK proofs remedy. Part 2 describes the small print of the polynomial IOP utilized in APK proofs. In 3, I clarify the toy instance we attempt to show and confirm on this article. Lastly in Part 4 I clarify and compute each step the prover and verifier have to take to run the APK proofs to determine the validity of the toy instance.
1. The Objective
We already informally mentioned the aim of APK proofs protocol as offering a succinct proof {that a} “particular” (versus any) M-member subcommittee of an N member committee has signed a selected message. To formalize this we introduce the next notations.
First we assume that the committee is represented by the next set:
And their public keys are represented as:
The place every pair represents the x and y coordinates of the factors on the elliptic curves akin to the general public key of member i. Let S be the subcommittee whose member has signed message Msg and
Be the aggregated signature of them:
The place σⱼ (Msg) is the signature akin to member j ∈S. To determine S and to point 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)
Subsequently when the verifier is given σ (Msg) and the appropriate apkₛ, they will merely confirm the signature by operating:
the place e is a bilinear pairing perform outlined on the elliptic curve.
However the entire query is easy methods to make it possible for a given apkₛ is the right one. In a world during which we have now no information and computation complexity issues, we might simply re-run and confirm Equation 1 to make it possible for apkₛ is appropriate. However our verifier is data-wise and computationally restrained and we wish to confirm Equation 1 with out receiving all pkᵢ’s. Right here, foreseeably, SNARKs are coming to the rescue.
2. The APK proofs’ SNARKs
APK proofs SNARKs are primarily based on a polynomial protocol and polynomial commitments. So we’re going to outline a set of polynomial relationships between the coordinates of the general public key factors of the committee members. If the prover is ready to persuade the verifier that these relationships maintain, then the verifier can make certain that the aggregated public key of the subcommittee is appropriate.
Very first thing first, we have to mathematically re-label every member of the committee as a substitute of {0,1, 2, …, N — 1 } to make verification of these polynomial relationships extra environment friendly. This relabeled set is known as “analysis area” in zk-SNARK jargon. Just like PLONK, Nᵗʰ roots of unity in some appropriate prime subject can be our alternative and we assume that N is definitely an influence of two. We repair a primitive Nᵗʰ root of unity ω and accordingly we label the committee member i ∈ C with ωⁱ .
Now we will specify our auxiliary polynomials as follows:
and get well them utilizing Lagrange interpolation.
Those which might be extra difficult are kaccx (X) and kaccy (X) that are these monitoring the aggregation of the subcommittee public keys. First we outline
the place (hₓ, hᵧ) is a random level on the curve which ought to both reside exterior of the general public key subgroup or it must be chosen randomly by the verifier after the dedication to committee keys has been computed. Then we outline (kaccxᵢ, kaccyᵢ) recursively as
the place the ⊕ addition occurs on the elliptic curve group the place the general public keys reside on. So the corresponding polynomials are outlined as
Are our remaining auxiliary polynomials. Having all of our auxiliary polynomials set, the prover must show that the next polynomials:
(2)
are vanishing over
As to why this is sufficient to show that that aggregation has been accurately performed, we give some instinct right here however for a rigorous proof you want to verify the APK proofs’s paper [2].
Id₅ simply makes positive that the prover solely used a real boolean vector for b. Id₄ makes positive that the preliminary and and ultimate values of kaccx and kaccy match the values recognized to the verifier (h and apk).
Id₁ and Id₂ are coming from Elliptic curve addition formulation and principally monitoring adjustments (or not) to the aggregated key at each step of aggregation one public key on the time.
We’re lastly able to get our fingers soiled, instantiate our system utilizing concrete numbers and generate a proof of an apkₛ within the subsequent sections.
3. Organising
We’re going to make an APK proof for a committee of three signers the place one in every of them has been absent and has not participated within the signing of the message. As BLS signatures and the KZG polynomial dedication scheme utilized in APK proofs are each outlined over elliptic curves teams we have to select some curves earlier than we mannequin our downside mathematically.
3.1 Selecting Elliptic Curves
First suppose that BLS public keys are outlined over curve Eᵢₙₙₑᵣ (𝔽q). Because of this pkxᵢ and pkyᵢ s are parts of 𝔽q. So when we’re going to run Lagrange interpolation to get well our auxiliary polynomials they are going to be naturally outlined over 𝔽q. Now suppose we wish to decide to polynomial P (x)
utilizing KZG dedication. KZG dedication is carried out by selecting a secret worth τ, computing factors of { τ G, …, τⁿ G } on some elliptic curve Eₒᵤₜₑᵣ (𝔽q’)} and for forgetting τ afterward. So the discrete logarithm of those factors shouldn’t be recognized by anybody. Then one “evaluates P at τ” by
the place the addition is finished on the elliptic curve subgroup generated by G. As such, we want to have the ability to interpret aᵢ’s because the scalars of Eₒᵤₜₑᵣ}’s prime subgroup. Subsequently, Eₒᵤₜₑᵣ must have a subgroup of measurement equal to | 𝔽q | = q. Furthermore, Eₒᵤₜₑᵣ must be a pairing pleasant so the verifier is definitely capable of confirm the KZG commitments utilizing pairing. That is just like the state of affairs that arose and is described in lecture 10 of the course [5] within the design of recursive SNARKs).
To piggyback on the PLONK by fingers weblog publish[3], we’re going to use the identical elliptic curve they’ve ready for KZG dedication as Eₒᵤₜₑᵣ:
outlined 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 principle we might have a committee of at most 15 validator measurement. However in our instance we solely have a 3-member committee the place 2 of them have signed the assertion. So 𝔽₁₇ is greater than sufficient for us.
Now with us utilizing BLS signatures, we additionally want that Eᵢₙₙₑᵣ to be a pairing pleasant curve as BLS signatures are additionally being verified utilizing pairing capabilities. Nonetheless, nowhere in operating APK proofs do we have to confirm the BLS signature itself. We solely confirm that an mixture public key is definitely aggregated accurately, which solely requires addition performance on Eᵢₙₙₑᵣ and the verifier by no means truly wants to make use of the pairing performance (on Eᵢₙₙₑᵣ) till after they’ve verified that the aggregated public secret’s appropriate. So we will safely go forward and select a curve which supplies us a sufficiently big subgroup and never be frightened whether it is pairing pleasant or not.
All we look after now’s that we want to have the ability to get 3 distinct public keys, one for every committee member and one additional level h in 𝓖 ⊲ Eᵢₙₙₑᵣ beside the id level at infinity (as a result of we wish to follow affine illustration of the curve in our computations). So the scale of 𝓖 must be larger than 4. This shouldn’t be an issue as the scale of the elliptic curves over 𝔽₁₇ could possibly be as massive 17 + 2 × 4 + 1 = 26 by Hesse’s lemma. So we simply attempt random curves on Sage until we hit one with a main subgroup of a good measurement.
We ran a script to generate all curves outlined over 𝔽₁₇ and settled on y² = x³ + 2 x + 2 which has | 𝓖 | = | Eᵢₙₙₑᵣ (𝔽₁₇) | = 19. This enables us to have distinct public keys for every members of a committee of most measurement which is 15 as a result of we’re tagging the members with roots of unities in 𝔽q = 𝔽₁₇. Furthermore it’s a prime ordered elliptic curve so we don’t want to fret about falling out of the subgroup. And it truly has the embedding diploma of 9 as a result of 17⁹ — 1 = 19 × 6241467184. So if we have to truly confirm a BLS signature it’s a doable process as there’s an embedding from this curve into 𝔽17⁹ which isn’t insanely big.
>>>
E_inner = EllipticCurve([GF(17)(2),GF(17)(2)])
>>>E_inner
y² = x³ + 2 x + 2
>>>E_inner.abelian_group()
ℤ 19 ℤ
>>>E_inner.factors()
[ (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 select an arbitrary generator < 3, 1 > and we set 𝓖in = < (3, 1) >we will then produce the logarithm desk for 𝓖in:
>>>for i in vary(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 Assertion of the Toy Downside
Evidently we don’t have to know members’ personal keys to have the ability to generate and confirm the aggregation. So we select 3 factors with small coordinates on Eᵢₙₙₑᵣ as the general 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 therefore:
>>>
apk=pk[0]+pk[2]
>>>apk
(10 : 6 : 1)
>>>
And for the prover to show that certainly
they should compute the auxiliary polynomials, decide to them and open them at random factors on the request of the verifier, so the verifier might imagine that polynomial relationships in 2 truly maintain. The main points of how that is performed in APK proofs is offered within the subsequent chapter.
4. Show and Confirm the APK
First we have to make our analysis area express. We now have 3 members and we have to represents them with varied 4ᵗʰ root of unity in 𝔽₁₇. This has been computed in [3] and equally we select:
so
Now we’re able to interpolate our auxiliary polynomials, we begin with b (X) :
>>>
omega = GF(17)(4)
>>>
b = [1,0,1]
>>>
factors = [(omega^i, b[i]) for i in vary(3)]
>>>
R.<X> = GF(17)[]
>>>
b_poly = R.lagrange_polynomial(factors)
>>>factors
[(1, 1), (4, 0), (16, 1)]
>>>b_poly
9 X² + 9
>>>
Equally we compute pkx (X) and pky (X):
>>>
pkx = [ 5, 7, 6]
>>>
pky = [ 1, 6, 3]
>>>
factors = [(omega^i, pkx[i]) for i in vary(3)]
>>>factors
[(1, 5), (4, 7), (16, 6)]
>>>
pkx_poly = R.lagrange_polynomial(factors)
>>>pkx_poly
11 X² + 8 X + 3
>>>
factors = [(omega^i, pky[i]) for i in vary(3)]
>>>factors
[(1, 1), (4, 6), (16, 3)]
>>>
pky_poly = R.lagrange_polynomial(factors)
>>>pky_poly
13 X² + 16 X + 6
>>>
Now we compute the recursive auxiliary polynomials kaccx (X) and kaccy (X). The verifier choose the arbitrary h = (hx, hy) = (3, 1) utilizing a uniformly random sampling (be aware that we have now chosen a main ordered curve so there isn’t any alternative of h ∈ Eᵢₙₙₑᵣ 𝓖ᵢₙ) and so we will compute kaccxᵢ and kaccyᵢ:
>>>
h = E_inner(3,1)
>>>
kacc = [h]
>>>
for i in vary(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’re capable of interpolate kaccx and kaccy
>>>
factors = [(omega^i, kacc[i][0]) for i in vary(4)]
>>>
kaccx_poly = R.lagrange_polynomial(factors)
>>>kaccx_poly
16 X³ + 5 X² + 15 X + 1
>>>
factors = [(omega^i, kacc[i][1]) for i in vary(4)]
>>>
kaccy_poly = R.lagrange_polynomial(factors)
>>>kaccy_poly
2 X³ + 3 X² + 16 X + 14
>>>
Now that we have now all our auxiliary polynomials we will decide to them and ship the dedication to the verifier.
We’re utilizing the identical SRS as in [3] which has a secret τ = 2. The utmost diploma polynomial we’re working with is of diploma 12 (although we truly decide to polynomials of at most diploma 8). So a SRS of measurement 13 ought to suffice. So we have now 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 dedication so we don’t have to repeat it:
>>>
def kzg_commit_to(p):
return sum([p.coefficients(sparse=false)[i]*SRS[i] for i in vary(p.diploma()+1)])
>>>
Now we will decide to all 5 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’re sending all above commitments to the verifier to arrange for the following step.
Now the verifier must make it possible for idᵢ is zero on all parts of Ω. That is the Zero Check described in lecture 5 of the course [5] and boils all the way 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 solely carry out this process for id₁ to maintain this information easy and brief. The process is analogous for all the remainder and within the precise protocol the prover performs this for a linear mixture of idᵢ’s as a substitute of doing it one after the other. 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 just too massive to be despatched to the verifier, so as a substitute first the prover sends a dedication to q₁.
>>>
commitment_to_q_1_poly = kzg_commit_to(q_1_poly)
>>>commitment_to_q_1_poly
(32 : 42 : 1)
>>>
After which the verifier asks us to open id₁ and q₁ at a random level r and if the equality of q₁ (r) =id₁ (r)/(r⁴ — 1) holds then by Schwartz-Zippel lemma it’s more likely to be true for any X:
>>>GF(17).random_element()
10
>>>
As a result of the verifier solely has a dedication to the auxiliary polynomials and q₁ they ask us to open all these polynomials within the random level they’ve chosen after which compute id₁ at that time 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 must confirm that the prover has been trustworthy with the opening worth. That is performed by the KZG pairing check. This may be batched and performed unexpectedly however we solely carry out it for kaccx to maintain the process easy. The prover must 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 doesn’t have the polynomials so they should confirm it utilizing KZG pairing. For that they want a dedication to qaccx∘10 which the provers supplies:
>>>
commitment_to_q_accx_10 = kzg_commit_to(q_accx_10)
>>>commitment_to_q_accx_10
(68 : 74 : 1)
>>>
The concept is that if
The place e is a pairing perform on Eₒᵤₜₑᵣ .}
For which we have to compute (τ — 10) G 2 Gen which require the verification key τ G 2 Gen, G2Gen which has been computed as a part of the ceremony in [3] (be aware there’s 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 have to lengthen the elliptic curve group to comprise factors 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 forward and use pairing to confirm prover’s declare:
We’re going to compute both sides of the above equation individually and ensure they’re equal. We’re going to use Tate pairing however another pairing perform ought to 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 a couple of is embedding diploma of P
28 u + 7
>>>
After which we compute the fitting hand facet:
>>>
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 identical for the remainder of the auxiliary polynomials and q₁ and they also know and imagine the opening values for all of them at 10. Subsequently they will confidently compute the right worth for id₁ (10) utilizing these:
>>>
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 every part they should full the Zero check to confirm that id₁ is divisible by X⁴ — 1
We now have the left facet equal to fifteen. So we’re going to compute the fitting hand facet:
So by the Schwartz-Zippel lemma it is rather seemingly that id₁ vanishes on Ω . Following the identical course of on the remainder of idᵢ’s, the verifier may be satisfied that every one are vanishing on Ω and therefore the apk is the true aggregation of the general public keys of members 0 and a couple of.
In apply the entire KZG pairing assessments and the verifying all of the idᵢ’s may be batched and every may be performed in a single check. Right here, we skipped that optimization in favor of simplicity.
Bibliography
[1]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable zero information with no trusted setup. In Advances in Cryptology–CRYPTO 2019: thirty ninth Annual Worldwide Cryptology Convention, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Half III 39, pages 701–732. Springer, 2019.
[2]
Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, and Sergey Vasilyev. Accountable mild consumer methods for pos blockchains. Cryptology ePrint Archive, Paper 2022/1205, 2022. https://eprint.iacr.org/2022/1205.
[3]
Joshua Fitzgerald. Plonk by hand. 2022. https://analysis.metastate.dev/plonk-by-hand-part-1/.
[4]
Web3.0 Applied sciences Basis. Apk proofs: totally succinct bls signature aggregation. 2023. https://github.com/w3f/apk-proofs.
[5]
Zero information proofs MOOC 2023. https://zk-learning.org/.
[6]
The Sage Builders. SageMath, the Sage Arithmetic Software program System (Model 9.8). 2023. https://www.sagemath.org.
