APK proofs is a protocol, designed (2) and carried out (4) by Web3 Basis Researchers, that permits 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 supplied 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 may cut back the signature knowledge value from M to 1 signature. Nonetheless, the verifier nonetheless wants the general public keys from each sub-committee member, which requires the record of N public keys on change of the committee. Moreover, it includes a computation of 𝓞 (M) complexity on every aggregation.
The fascinating facet 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. Much like many different succinct arguments, APK proofs advantages from the magic of SNARKs to realize this. SNARKs have been the principle 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 article to satisfy the course requirement for acquiring the Ninja standing but additionally make APK proofs extra accessible to different researchers and builders who may profit from this protocol of their techniques.
Throughout my examine of the course, I learn and loved the “PLONK by Hand” collection ((3)) and I considered utilizing the identical idea to elucidate 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 resolve. 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 must take to run the APK proofs to ascertain the validity of the toy instance.
1. The Aim
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)
Due to this fact when the verifier is given σ (Msg) and the appropriate apkₛ, they’ll merely confirm the signature by working:
the place e is a bilinear pairing perform outlined on the elliptic curve.
However the entire query is how one can ensure that a given apkₛ is the proper one. In a world by which we’ve no knowledge and computation complexity considerations, we may simply re-run and confirm Equation 1 to ensure that 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 ensure 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 an alternative 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. Much like PLONK, Nᵗʰ roots of unity in some appropriate prime subject shall 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 are able to specify our auxiliary polynomials as follows:
and recuperate them utilizing Lagrange interpolation.
Those which can 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 appropriately carried out, we give some instinct right here however for a rigorous proof it is advisable to verify the APK proofs’s paper (2).
Id₅ simply makes certain that the prover solely used a real boolean vector for b. Id₄ makes certain that the preliminary and and closing values of kaccx and kaccy match the values identified to the verifier (h and apk).
Id₁ and Id₂ are coming from Elliptic curve addition formulation and mainly 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 certainly one 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 drawback mathematically.
3.1 Selecting Elliptic Curves
First suppose that BLS public keys are outlined over curve Eᵢₙₙₑᵣ (𝔽q). Which means that pkxᵢ and pkyᵢ s are parts of 𝔽q. So when we’re going to run Lagrange interpolation to recuperate 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 is just not identified by anybody. Then one “evaluates P at τ” by
the place the addition is completed on the elliptic curve subgroup generated by G. As such, we’d like to have the ability to interpret aᵢ’s because the scalars of Eₒᵤₜₑᵣ}’s prime subgroup. Due to this fact, 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 concept we may 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. Nevertheless, nowhere in working APK proofs do we have to confirm the BLS signature itself. We solely confirm that an mixture public key is definitely aggregated appropriately, 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 key’s appropriate. So we are able to 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 take care of now’s that we’d like to have the ability to get 3 distinct public keys, one for every committee member and one additional level h in 𝓖 ⊲ Eᵢₙₙₑᵣ beside the identification level at infinity (as a result of we wish to keep on with 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 𝔽₁₇ may very well 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 major subgroup of a decent measurement.
We ran a script to generate all curves outlined over 𝔽₁₇ and settled on y² = x³ + 2 x + 2 which has | 𝓖 | = | Eᵢₙₙₑᵣ (𝔽₁₇) | = 19. This permits 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 may be an embedding from this curve into 𝔽17⁹ which isn’t insanely large.
>>>
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 are able to 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 must know members’ non-public 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 may consider that polynomial relationships in 2 truly maintain. The main points of how that is carried out in APK proofs is introduced within the subsequent chapter.
4. Show and Confirm the APK
First we have to make our analysis area express. Now we 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 decide the arbitrary h = (hx, hy) = (3, 1) utilizing a uniformly random sampling (observe that we’ve chosen a major ordered curve so there isn’t a alternative of h ∈ Eᵢₙₙₑᵣ 𝓖ᵢₙ) and so we are able to 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’ve all our auxiliary polynomials we are able to 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’ve 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 vary(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 must 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 are able to 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 ensure that idᵢ is zero on all parts of Ω. That is the Zero Take a look at 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 quick. The process is comparable for all the remaining and within the precise protocol the prover performs this for a linear mixture of idᵢ’s as an alternative 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 an alternative 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 prone 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 sincere with the opening worth. That is carried out by the KZG pairing take a look at. This may be batched and carried out 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 offers:
>>>
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) (observe 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 prolong 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 all 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 best hand aspect:
>>>
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 consider the opening values for all of them at 10. Due to this fact they’ll confidently compute the proper 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 take a look at to confirm that id₁ is divisible by X⁴ — 1
Now we have the left aspect equal to fifteen. So we’re going to compute the best hand aspect:
So by the Schwartz-Zippel lemma it is extremely possible that id₁ vanishes on Ω . Following the identical course of on the remainder of idᵢ’s, the verifier will 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 checks and the verifying all of the idᵢ’s will be batched and every will be carried out in a single take a look at. 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 techniques 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 Applied sciences Basis. Apk proofs: absolutely 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.