Ethereum Vote Aggregation

Overview

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)

• the contract has a commitment to all the balances B = Commitment([500, 25, 376, 29, ...])
• and a commitment to all the corresponding votes V = Commitment([+1, -1, -1, +1, ...])
• the dot product of these is the final tally T = 500 - 25 - 376 + 29 + ...
• anyone could calculate that value offline and present it to the contract
• the contract would just need to check the equation to validate T

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.

Background

Kate Polynomial Commitments

The scheme is defined here. In short:

• A polynomial can be defined by its coefficient terms (ie. the a_i values in P(x) = a₀ + a₁·x + a₂·x² + ... )
  • We could also define a polynomial by its evaluations [ Q(0)=a₀; Q(1)=a₁; Q(2)=a₂; ...]
  • I learned this topic from ultra Ethereum researcher Justin Drake who claims that we can work in evaluation form more easily, but I couldn't understand how the "dot product" or "bitmap" (explained below) would work, so I'm going to continue describing this scheme using coefficients
• Note that in this context, a polynomial is just a mechanism to manipulate and reason about a large number of arbitrary different values. In our case, we're interested in performing aggregate operations on votes.
• There is a mechanism to commit to a polynomial. The final result is a constant-sized element. I will denote a commitment to a polynomial P(x) as P(x).
• Given a commitment, you can reveal any subset of points on the polynomial, along with another proof element. Assuming supporting infrastructure (the ability to do an elliptic curve pairing), we can check consistency of these values in constant time.
• The commitments combine linearly:
  • eg. 2·P(x) + 3·Q(x) == (2·P(x) + 3·Q(x))
  • note: the notation I'm using is a little deceptive because the actual mathematical operations are slightly more complex, but I don't think it effects the bottleneck of the overall design.
• We can quickly validate any claimed quadratic term:
  • given a, b and c we can check whether a·b == c

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 S_sum. We can also add all the public keys to get a combined public key PK_sum. 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) = x^N-d·P(x) and Q(x). The smart contract can use the commitments to validate the relationship (ie. that Q(x) = x^N-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 a_i, 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) + a_i·xⁱ + xⁱ⁺¹·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 a_i.

Dot product

Consider two quadratic polynomials

• a(x) = a₀ + a₁x + a₂x²
• b(x) = b₀ + b₁x + b₂x²

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

(a₀ + a₁x + a₂x²)·(b₂ + b₁x + b₀x²)
= [ lower degree terms ] + (a₀b₀ + a₁b₁ + a₂b₂)·x² + [ higher degree terms ]

This term is the dot product between a and b.

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

Obligatory XKCD:

Bitmap

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·x² + 0·x¹ + 1·x⁰, 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.

• BLS_KEYS is a commitment to the BLS public keys of all known users. This defines an index for each identity (eg. the fifth coefficient corresponds to identity number 5). It is initialized to zero.
• SEQUENCES is a commitment to the sequence numbers associated with the identities (to prevent replay attack). They are listed in the same order as the corresponding owner identities in BLS_KEYS. It is initialized to zero.
• BALANCES is a commitment to the token balances. They are listed in the same order as the corresponding owner identities in BLS_KEYS. It is initialized to zero.

Registering

To add a public key to BLS_KEYS:

• the user picks a zero coefficient on the polynomial (say position i) and constructs a proof that reveals it (to be zero)
• the user sends this proof and a new public key PK to the contract
• the contract validates the proof
• the contract constructs a commitment to xⁱ·PK
• the contract updates BLS_KEYS = BLS_KEYS + xⁱ·PK

Mint

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

• the user constructs proofs to reveal
  • the current balance at position i of BALANCES
  • the public key at position j of BLS_KEYS
  • the sequence number at position j of SEQUENCES
• the user constructs a message consisting of these proof and the number of new tokens t
• the user signs the message and sends it to the contract
• the contract validates the proofs and signature
• the contract validates that identity j can mint tokens to position i
• the contract checks to see if the balance would overflow
• the contract constructs a commitment to xⁱ·t
• the contract updates BALANCES = BALANCES + xⁱ·t
• the contract retrieves the commitment to x^j
• the contract updates SEQUENCES = SEQUENCES + x^j

Burn

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

Transfer

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

Vote Initialization

To initialize a vote:

• the contract saves a copy of BALANCES. This effectively creates a snapshot that can be used for voting, while the original commitment can still be updated to allow token transfers.
• the contract creates a commitment HAS_VOTED and initializes it to zero.
• the contract creates a tally variable and initializes it to zero.

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:

• every user i publishes a message containing their vote (eg. "On question abcd, I vote +1"), along with their signatures S_i
• an aggregator takes an arbitrary subset of the ballots and divides them by the particular vote (the -1s are together, the +1s are together)
• the aggregator creates SELECTION₊₁ and SELECTION_-1 polynomials that "select" the corresponding identities.
  • these are both bitmap polynomials, where a coefficient of 1 implies the identity matches the polynomial
  • the coefficients are specified in reverse order, so they can be used in a dot product (explained above)
• the aggregator creates commitments to SELECTION₊₁ and SELECTION_-1
• the aggregator creates proofs that they are bitmaps
• the aggregator creates a commitment to a SIGNATURES polynomial that contains all the signatures in the same order as BLS_KEYS (unused signatures can be set to zero)
• note that the dot product between SIGNATURES and SELECTION₊₁ will be the sum of the signatures of the +1 voters. They all voted on the same message so BLS signature aggregation would apply. Similarly, the dot product between BLS_KEYS and SELECTION₊₁ will be the sum of their public keys. The same analysis applies to the -1 voters using the SELECTION_-1 polynomial. The aggregator calculates all these values, as well as the commitments required to prove that they're accurate (SIGNATURES·SELECTION₊₁, BLS_KEYS·SELECTION₊₁, SIGNATURES·SELECTION_-1, BLS_KEYS·SELECTION_-1)
• similarly, the dot product between BALANCES and (SELECTION₊₁ - SELECTION_-1) is the signed sum of the votes, weighted by the corresponding balances. In other words, it's the tally represented by this subset of votes. The aggregator calculates this value and the proof element BALANCES·(SELECTION₊₁ - SELECTION_-1)
• the aggregator sends all these values, commitments and proofs to the contract
• the contract verifies all the proofs
• the contract updates HAS_VOTED = HAS_VOTED + SELECTION₊₁ + SELECTION_-1
  • note that the selection polynomials have reversed coefficients so the identities are marked off in reverse order. That's okay because we're just looking for duplicates.
• the contract verifies that HAS_VOTED is still a bitmap (otherwise, a voter will be double-counted)
• the contract verifies both of the aggregated BLS signatures
• the contract verifies that the expected message was signed by both groups
• the contract scales the selection polynomial commitments by their values and combines them:
  • APPROVE = SELECTION₊₁
  • REJECT = -SELECTION_-1
  • VOTE = APPROVE + REJECT
• the contract confirms this is consistent with the tally proof
• the contract updates the tally variable accordingly

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:

• it is the same size as the original commitment, so blinding has minimal impact on bandwidth and computational requirements
• a user can reveal r, which allows anyone else to recover P(x)
• it is binding. The user can't later "reveal" a different random value in order to retroactively change the commitment.
• mathematically, it is equivalent to P(x) + λr, where λ is unknown (it's an intrinsic property of the trusted setup)

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

• instead of revealing r, the user could reveal an unblinding commitment 0|-r. This could be added to the original commitment to recover P(x). This allows for aggregate unblinding operations.
• if the user revealed a different blinding factor x with the same format (0|x), they cannot control (except by trial and error) the "recovered" P(x). So if P(x) has enough structure that random modifications would be detectable, a malicious user could not change their commitment.
• however, if a malicious user revealed an arbitrary unblinding commitment (with no enforced structure) that was naively added to their original commitment, they could control the "recovered" value, thereby changing their commitment.
• therefore, the contract needs to validate the structure of unblinding commitments.

Procedure

To conduct a vote:

• the user with identity i in BLS_KEYS hashes a message containing their vote (eg. "On question abcd, I vote +1") and uses this as the coefficient in a single-term polynomial with degree i (ie. P_i(x) = H(m)·xⁱ)
• they publish the blinded commitment P_i(x)|r_i
• they also publish a low-degree and high-degree proof that the commitment only affects one term
• any subset α of users can coordinate offline to sum their commitments to create VOTES_α|r_α and sign the result
  • this will be a polynomial where the coefficient of the i^th term is user i's blinded vote
  • since blinded votes will all be unique, users cannot aggregate their signatures if they only sign their component. This is why they sign the whole polynomial, which requires more coordination. If some users are non-cooperative, they can be excluded from the subset.
  • users will need to check the degree proofs to ensure other users are not interfering with their own term in the polynomial
• as before (see Option 1 for details)
  • an aggregator creates a SELECTION polynomial that "selects" the corresponding identities, and a SIGNATURES polynomial with all the signatures in the relevant positions
  • they provide all the necessary commitments and proofs so that the contract can verify (in aggregate) all relevant voter signatures and that HAS_VOTED is updated accordingly
• Ideally, as each subset γ of votes is submitted, the contract can add them to a global VOTES|r commitment
  • however, we need to ensure VOTES_γ|r_γ doesn't affect any other voters
  • this seems like it should be possible, but my current design has a flaw:
    • the contract constructs INVERTED_SELECTION_γ, which flips the bits of SELECTION_γ (see the Bitmap section above)
    • the users proves (and the contract validates) that the dot product INVERTED_SELECTION_γ·VOTES_γ|r_γ is zero
    • this limits the attacks but does not prove these values are zero, because they may be non-zero values that add to zero
  • if this cannot be resolved, we could require voter reveals to occur within their initial commitment subset
    • this would add some storage overhead because we would need to save the individual SELECTION_γ and VOTES_γ|r_γ commitments, and handle them separately
    • fortunately, it may not increase the number of elliptic curve pairing and BLS signature operations because an aggregate reveal that spans multiple SELECTION_γ polynomials would involve checking multiple polynomial equations, and these can be pseudorandomly combined into a single equation:
      • ie. for any two equations a·b == c and x·y == z, the contract could generate a pseudorandom r and then combine them into a·b + r(x·y) == c + rz
• In the REVEAL phase, any subset of voters can coordinate offline to sign and reveal their unblinding commitment
  • the aggregator should supply selection polynomials SELECTION₊₁ and SELECTION_-1 that select the users within each voting category. The overall SELECTION is the sum of these two values.
  • we can use the same techniques to validate the signatures, prevent double-counting (with a HAS_REVEALED bitmap) and ensure users don't interfere with other votes within the same subset
    • as before, we may need to save each revealed subset to prevent users affect votes outside their subset
    • however, in this phase, it may be unnecessary because tampered votes are recoverable:
      • tampering with votes that have already been revealed has no effect, since the vote has already been counted
      • assuming the consistency checks hold, tampering with a masked vote commitment i simply adds a public value to the existing random blinding factor r_i. This value could be incorporated into the subsequent unblinding commitment.
  • as noted above, the contract needs to confirm that the unblinding commitment has the form 0|r(x)
    • the user just needs to supply r(x) and prove that 0|r(x) == 0|1·r(x)
    • note that both sides of this equation are equivalent to λ·r(x)
  • the contract can unblind the subset of votes by adding the unblinding commitment to VOTES|r
  • the aggregator can reveal and prove the sum of SELECTION₊₁, which is the number of voters p in this subset who voted Approve. Similarly, they can reveal and prove the number of voters n who voted Reject.
  • the aggregator should also provide proofs that
    • SELECTION₊₁·VOTES == p·H("On question abcd, I vote +1")
    • SELECTION_-1·VOTES == p·H("On question abcd, I vote -1")
    • theoretically, multiple users could coordinate so none of their commitments are valid, but they still add to the sum of valid commitments. This is fine - they still need to choose their votes beforehand. Moreover, they can't use this technique to hijack an unwilling voter's ballot because all users in the SELECTION need to sign the reveal
  • as before, the contract can update tally with BALANCES.(SELECTION₊₁ - SELECTION_-1)