In this research article, I review what is perhaps the most important SNARK in modern blockchain systems, the APK Proofs scheme. Which in combination with aggregatable BLS signatures, produces proof-of-stake (POS) consensus proofs with the cheapest known verifier complexity.
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 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 . For an elliptic curve half-cycle, it should be the case that the characteristic of the base field of the inner curve is the same as the scalar field of the outer curve . Let be a suitably chosen multiplicative subgroup in the scalar field of the outer curve .
First we need to arithmetise elliptic curve point addition. Recall the elliptic curve addition formula for a short weierstrass curve, The slope between the two points is given as
Substituting we get
In the same manner, we constrain the value for
The goal is to show that , where is a vector of known public keys and is a bitvector indicating the signers. We’ll do so by means of an accumulator. Observe that we can write
Where are the affine coordinates of the potential signers and is the accumulator sum.
constraining with we get:
Lifting these equations to polynomial constraints:
Assume are Lagrange polynomials in the domain . The verifier has commitments to and . They’ll receive the commitments and opening proofs for the polynomials, and . 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 . Such that:
We’ll constrain using these equations.
Lifting to polynomial constraints
Finally the prover has to show that each . They’ll do so using the polynomial constraint
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 and above.
The paper introduces two new polynomials in it’s Packed Accountable Ranged scheme. First we must understand that any number can be re-written as an inner product of its binary representation and powers of 2. This also known as binary decomposition.
First we define 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.
In order to use binary decomposition tricks, it’s necessary is a power of 2. ie . Rather than a bitlist, the prover provides a vector of field elements
where each can be seen as
The verifier wants to know that the bitlist encoded in the binary representation of is equal to . We do so by means of a range proof. Observe that
We begin by decomposing the final equation. First lets define a selector polynomial
Where is given as
Note that 0 is divisible by any . Next we define
The prover must then show that the following polynomial is zero over
Lets consider the case when , we have that:
Lets consider the second case when , we have that:
Finally lets consider the case where , It’s easy to see that . Therefore
The polynomial constrains the form of . Next we introduce an accumulator polynomial for .
where are the components of the vector:
The prover must show that the following polynomial evaluates to zero over
Considering the case when
This convinces the verifier that is equivalent to . Finally the apk proof constraint polynomial is given as:
Or in expanded form
Where 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.