Ethereum Vote Aggregation


Standard Ethereum voting contracts could benefit from a mechanism to aggregate votes offline and efficiently validate and tally them on-chain. Here is a proposed design based on the Kate Polynomial Commitment scheme and BLS signatures, which are both gaining traction in the Ethereum community. I'm a few steps out of my depth, and there are parts of the design that need to be hardened, so feedback and corrections are most welcome.

The core idea is that if (somehow)

In this way, the contract does not need to know or handle individual balances or votes, saving storage and computation costs. The rest of this proposal just describes a mechanism to construct those commitments correctly and securely.


Kate Polynomial Commitments

The scheme is defined here. In short:

The general strategy is to require users to pre-compute all relevant values (balances, votes, signatures, etc) and let the smart contract use these properties to verify that the equations hold and the values were calculated correctly.

There is a trusted setup that limits the maximum number of terms in the polynomial, but the linearity condition means we can mostly work around this by treating large polynomials as a psuedorandom combination of small polynomials.

BLS Signatures

This scheme requires users to sign messages with a BLS key pair. Signatures on the same message obey linearity, so if multiple users sign the same message, we can add all the signatures to get a combined signature Ssum. We can also add all the public keys to get a combined public key PKsum. We only need to check the combined signature against the combined public key in order to demonstrate that all the signatures were valid.

Polynomial Tricks

Low-degree proofs

The trusted setup guarantees an upper limit N to the degree of a committed polynomial. In order to prove that a committed polynomial P(x) has a lower degree d, the user can calculate Q(x) = xN-d·P(x) and Q(x). The smart contract can use the commitments to validate the relationship (ie. that Q(x) = xN-d·P(x)). This proves that the degree of Q(x) is limited to N, so the degree of P(x) must be limited to d.

Revealing a coefficient

We have a mechanism to reveal a particular point on the polynomial, but in this design, we don't care about any of the point evaluations, we only care about the coefficients.

If we have a commitment to the polynomial P(x) and we want to reveal some coefficent ai, we can think of the polynomial as being comprised of three parts: the lower-degree terms, the target term and the higher degree terms P(x) = L(x) + ai·xi + xi+1·H(x). If the user creates a commitment to L(x) and H(x) and proves they have the right degree, the smart contract can check the equation, which validates the revealed ai.

Dot product

Consider two quadratic polynomials

We can reverse the order of coefficients in one of them, multiply the result by the other, and then investigate the second degree term:

(a0 + a1x + a2x2)·(b2 + b1x + b0x2)
= [ lower degree terms ] + (a0b0 + a1b1 + a2b2)·x2 + [ higher degree terms ]

This term is the dot product between a and b.

More generally, given commitments to a and breversed, where both polynomials have degree d that is half the trusted setup size, a user can calculate and commit to a·breversed. This value can be checked by the smart contract. The user can then reveal the dth coefficient, which will correspond to the dot product between a and b.

Obligatory XKCD:

Obligatory XKCD


Consider a commitment to a polynomial P(x) whose coefficients are claimed to be either 0 or 1. How can we test this claim?

The polynomial can be thought of as a bitmap, and P(2) would evaluate to the number that the bitmap represents. The Kate scheme allows the user to reveal that value directly.

For example, if P(x) = 1·x2 + 0·x1 + 1·x0, then P(2) = 5, which is 101 in binary.

Let's define F(x) as the polynomial with coefficients that are all 1. Then Q(x) = -P(x) + F(x) should be the polynomial that inverts the coefficients of P(x) (all the 1s become 0s and vice versa).

The smart contract can use linearity to calculate Q(x), and the user can reveal Q(2). If P(x) is a bitmap, then Q(2) will be the bitwise inverse of P(2).

Moreover, if P(x) and Q(x) are bitmaps, P(1) and Q(1) are the number of non-zero coefficients in each of the polynomials respectively. They should sum to F(1).

⚠️ WARNING: I have not been able to construct a non-bitmap polynomial that passes both of these tests, but that's not a proof, of course. If this scheme turns out to be viable, it will require an efficient way to test if a polynomial is a bitmap. The one I described here may be suitable. In the rest of the document I will assume such a test exists.

Sum all coefficients

Given a commitment to a polynomial P(x), the Kate scheme allows a user to reveal P(1). This will correspond to the sum of all the coefficient terms.

The protocol

Global state

The protocol state is comprised of three polynomial commitments. For simplicity, I will assume the polynomial sizes are unbounded, or equivalently, the number of identities is less than half the size of the trusted setup. We should be able to handle more identities with another layer of complexity.


To add a public key to BLS_KEYS:


To mint tokens for the identity at position i, using the identity at position j:


The mechanics of burning tokens is the same as minting them except the token commitment is subtracted from BALANCES instead of added.


A token transfer can be thought of as a burn and mint operation.

Vote Initialization

To initialize a vote:

Public Voting (Option 1)

I will assume each vote can be represented by -1 or 1 and that the final result is the sum of these votes, weighted by the balances. Note that using linearity, it's easy to map a simple set like this into a different set (eg. we can take 0s and 1s and map them to -1 and 1s). The scheme can also be extended with more options.

To conduct a vote:

The advantage of this scheme is that all the relevant calculations are performed off-chain by the aggregator. The contract can validate the effect a large number of ballots with a small number of constant-sized proof elements and constant-time checks. It should also be noted that this scheme is still censorship resistant because each update only requires a subset of the votes. Any votes that are ignored by the aggregator can be submitted in their own update.

Hidden Voting (Option 2)

The previous option only works if we're willing to aggregate votes in the open, which means voters can be influenced by the ballots of other voters. Many existing systems use a commit-reveal process to temporarily hide the votes. To that end, it's worth noting that the original Kate paper includes a mechanism for masking a commitment and then revealing it. Our additional constraint is that the different terms in the eventual VOTE polynomial correspond to different voters, so they need to be masked and unmasked individually without sacrificing the ability to perform aggregate calculations.

Pedersen construction

If the trusted setup supports it, it's possible to include a random number along with a Kate commitment in order to hide the commitment. I'll denote a blinded commitment to P(x) with a blinding factor r as P(x)|r. For our purposes, there are a few important properties of this blinded commitment:

Additionally, if I understand the mathematics correctly (which should be validated by a mathematician):


To conduct a vote: