Apk Proofs

Do not index

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.

Preliminaries

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 .

APK Proofs

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

Such that:

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:

Where

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

Where

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

Observe that

Therefore

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.

References

Accountable Light Client Systems for PoS Blockchains, Oana Ciobotaru, Fatemeh Shirazi, Alistair Stewart, and Sergey Vasilyev.