Recently, a few friends of mine have come back to me after reading my previous articles about elections on the Blockchain (part 1 and part 2 ). They were wondering how feasible it would be to implement a voting scheme that works in the real world.
Some of the requirements I got from them are the following:
- The voting platform must scale on the number of voters.
- The whole voting process must support short-lived elections, i.e. a few hours or, in some extreme cases, even minutes (think of a poll in a TV show).
- Minimal to no trust should be put in any of the party involved in the voting process.
- It must not be possible to trace the ballots back to the actual individual voters.
- Honest voters must be ensured that their vote will be taken into account during the final tallying.
As you can see, these requirements are pretty challenging: while the “no trust” requirement would make us lean towards a Blockchain-based solution, the possibility to scale to thousands of transactions per seconds seems to rule it out.
As a first attempt, we will go then for a hybrid solution based, both on a centralized setup (for scalability) and a public Blockchain (to keep integrity and auditability) as well as on a private Blockchain to reach consensus on the final results. To design the solution, I took inspiration from the Google’s Certification Transparency Initiative and this paper by Liu et al which introduced the concept of Linkable Spontaneous Anonymous Group (LSAG) signatures.
For the time being, we won’t take into account the problem of vote-selling or vote-coercion.
Electronic voting: still a Chimera
A huge caveat to this article. Full electronic voting has still a lot of road to do. Many problems found a solutions but issues are still standing out there.
One of the trickiest is software integrity: How do we ensure that the software you are using for voting (e.g. an app on a smartphones or a tablet in the polling station) has not been tampered with by an attacker? Marking a ballot with an “X” is a lot easier to verify than checking that an encrypted vote is actually the one you intended to cast. On this topic, I would suggest reading a nice essay by Ronald L. Rivest.
Linkable Spontaneous Anonymous Group (LSAG) signatures
A cornerstone of the solution described in this article are LSAG signatures. In practical terms, a LSAG signature allows to hide the signer’s identity among a group of other identities. A verifier will not be able to identify the actual signer but be sure that the signature has been performed by one of the group members. In addition, an LSAG signature scheme allows a verifier to “link” signatures that have been generated by the same identity which, nevertheless, remains anonymous (or pseudonymous). A LSAG signature has this form:
where s is the signature of message m, G is the group of identities among which the actual signer is concealed, L is the “signer’s link” which is uniquely bound to the signer without revealing her/his real identity, i.e. it cannot be changed by the signer but the signer’s identity cannot be (computationally) derived from L. In this article we will refer to the LSAG as described in Monero’s Confidential Transactions paper by Noether. Specifically, L will not depend on G.
Crypto-currencies and e-voting: a difference in scope
Double spending and double voting seem to be pretty much the same problem: you don’t want a party to spend the same coin twice, the same way you don’t want a voter to cast two or more (possibly contradictory) ballots.
Nevertheless, there are two important differences:
- Commutativity. There are no specific ordering requirements for the votes expressed during an elections. In the end, the final result doesn’t depend on whether vote A arrived before vote B (or viceversa).
- Independence. Casting a ballot by a voter is done in isolation: the ballot cast by a voter is not influenced by the ballots previously sent by any other voter. On the other way around, in the context of payments, a coin can be spent only if previously received by another party (or mined).
Somewhat, between payments and voting, there is a difference in scope. Spending is a global-scope activity: everybody must be informed of a party spending a coin to avoid double spending. This holds true also in non blockchain-based financial systems: the global scope is usually maintained in a few core systems, like TARGET2 in the Euro area.
Conversely, voting is basically local-scope: casting a vote doesn’t have any dependency on the other castings performed by the community, the only requirement being that the tallying authority must be able to rule out double votes, either by prevention or by detection.
This difference in scope allows an election to be split into independent sub-elections. By the way, this is not different from what’s happening in the real world where voters express their ballot into different and independent polling stations. Also, the final aggregation does not depend on the order in which votes are received: they are thrown into a voting box where order is not preserved.
On top of that, we will see that the local-scope of voting scheme allows to defer the consensus phase at a later stage, just before the tallying.
A practical scheme
Environment
In the environment where the elections take place the following components are available:
- The Authoritative Node. This is a server that is publicly accessible and is designated in this role by the party that is starting the election, the Polling Authority.
- Witness Nodes. These are a number of servers that are publicly accessible. The Witness Nodes is an open set and any party is invited to join.
- A public Blockchain. All the parties have complete and unrestricted access to a public, non-permissioned Blockchain (e.g. Ethereum). The messages sent to the Blockchain cannot be tampered with by any of the parties involved in the election process. Also, the Blockchain is acting like a provable public clock with time provided in the form of the block number and proof as the block digests.
- The Polling Authority. This party designates the Authoritative Node and ensures the registration of Voters and the Witness Nodes. Also, the Polling Authority transitions the election process into the different phases and, finally, declares the outcome of the election. The public key of the Polling Authority is known to all the parties.
We also assume that all communications between the parties happens in an anonymous fashion, e.g. using the Tor mixing network.
Registration phase
First of all, the Polling Authority publishes in the Authoritative Node a random number, the PollID, that uniquely identifies the current election, along with a public key, the Poll Public Key . Also, the Polling Authority publishes the list of the possible votes that can be selected by the voters for the current election. For this article we will assume a referendum-like election, i.e. the voter can choose only between two mutually-exclusive votes, indicated as 0 and 1. The PollID, the Poll Public Key and the choices are signed by the Polling Authority.
In this phase, Voters go to the Polling Authority and present their identity along with a public key in order to be registered as voters. The Polling Authority has the right to reject a Voter if she/he is not eligible to vote in the current election. Upon successful registration, the Polling Authority releases a signed Registration Receipt to the Voter containing:
- The Voter’s identity.
- The Voter’s public key.
- The PollID.
- The current time from the public Blockchain.
Also, in this phase, the Witness Nodes are registered with the same mechanism: an identity and a public key is provided by the party managing the Witness Node and a signed Registration Receipt is released with the same elements as above. For the Witness Nodes, a publicly accessible URI is provided which will be later used during the voting phase by the Voters.
After the registration phase ends, the Polling Authority publishes the list of Voters and the list of Witness Nodes in the Authoritative Node, both in terms of identity and public key. For the Witness Node, the voting URI is also published.
Merkle Tree Hashes of the list of Voters and the Witness Nodes are published to the Blockchain, along with the PollID and the possible votes. These digests are signed by the Polling Authority. For now on, Merkle Trees contain leaves represented by the pair (n,L) where n is the position of the node L in the list.
In case a Voter or a Witness Node is not appearing in the published lists, she/he can use the Registration Receipt to object. Also, the honest Polling Authority can always provide a membership proof for a Voter or Witness Node that can be publicly verified in order to counteract false claims of registration rejections.
After this phase and at a convenient time, the Polling Authority declares the opening of the election. This transition is signaled to the public Blockchain.
Voting phase
A Voter encodes a message containing his voting preference following these steps:
- The Voter accesses the Authoritative Node to pick randomly N identities from the public list of Voters. For each identity, the information received from the Authoritative Node is the public key and a membership proof based on the Merkle Tree Hash published in the public Blockchain by the Polling Authority that the identities are actually in the list of Voters. We call this set the Signature Group. Notice that, by using membership proofs, the voter avoids downloading the whole list of voters just to pick some identities randomly. In fact, the voter inquiries the Authoritative Node (via a proper API) and can be ensured that the identities retrieved are part of the list of Voters. In addition, this information must be publicly available, i.e. there must be no need to provide an authenticated identity to perform queries to the Authoritative Node. In this way, we avoid identity fingerprinting by the composition of the group G in the LSAG. Finally, the Authoritative Node must return exactly those identity requested by the voter: recall that the leaves of the corresponding Merkle Tree contains, indeed, the position of the leaf in the tree.
- The Voter selects a number of Witness Nodes from the list published in the Authoritative Node. Like in the previous step, the Voter receives the public keys and the membership proof that the selected Witness Nodes are registered as such in the Authoritative Node, consistently with the Merkle Tree Hashes published in the Blockchain.
- The Voter gathers the possible votes that are available for this election from the Authoritative Node along with the Poll Public Key.
- The information gathered in 1, 2 and 3 are checked for authenticity against the Polling Authority’s public key. Information gathered in 1 and 2 are also verified for integrity using the Merkle Tree Hashes published in the public Blockchain.
- The Voter pick one of the votes, encrypts it with the Poll Public Key along with a random nonce (to ensure uniqueness of the encrypted vote) and prepares an LSAG signature using the Signature Group as defined in 1. These information, together, form the ballot.
- The Voter sends her/his ballot to the Authoritative Node and to all the Witness Nodes selected in 2.
- The Voter receives back a signed Ballot Receipt which acknowledges that the ballot was received by the Authoritative/Witness Node. Among the other information in the receipt, the Voter receives the ID of the block in which his ballot was inserted and the position k in the sequence of ballot in the block (see later).
When the Authoritative/Witness Node receives the ballot from the Voter:
- It checks the eligibility of the identities in the Signature Group by looking up the list of voters. Alternatively, the voter can provide the membership proofs received previously by the Authoritative Node.
- It checks the validity of the LSAG signature.
- It checks that no previous ballot was received from the same voter by looking up the signer’s link in the LSAG signature in the cast ballots. Notice that the anonymity of the voter is still preserved even if two such ballots are found.
- It inserts the ballot in the current partial block of ballots.
- Prepares and signs a Ballot Receipt with the following information:
- the current time (taken from the public Blockchain) when the vote was received by the Authoritative/Witness Node,
- the unique ID of the current partial block,
- the position k in the block in which the ballot is inserted,
- a signed digest obtained by hashing these information along with the ballot and the LSAG signature.
- Upon receiving the Ballot Receipt, the Voter checks the authenticity, the integrity and the freshness of the receipt.
- The Authoritative/Witness Node finalizes the current partial block of ballots by sending the Merkle Tree Hash to the Blockchain, along with the block ID and the identity of the Authoritative/Witness Node. The Voter can request a membership proof of her/his vote from the Authoritative Node and the Witness Nodes. This request is performed by specifying the index k provided in step 5. The anonymity of the Voter is preserved since this information can be publicly inquired.
After a certain amount of time the Election Authority declares that the election is over by signaling this in the Blockchain.
Consensus phase
In this phase, the Authoritative Node and the Witness Nodes cooperates to reach consensus on the complete list of the ballots received for the election. In principle, the Authoritative Node should already have all the ballots expressed by the voters Nevertheless, we cannot exclude a malicious behavior of the Authoritative Node, considering that the Polling Authority knows the votes contained in the ballots received. The Authoritative Node cannot, of course, forge the ballots nor change their content but it may still be able to omit a ballot.
Let’s then suppose that a Voter sends her/his ballot to the Authoritative Node. The Voter receives back the Ballot Receipt and, once the Merkle Tree Hash of the block containing the node has been published to the public Blockchain, the Voter inquiry the Authoritative Node to check that in position k of block N her/his vote has been actually included.
What happens if the Authoritative Node returns a membership proof that doesn’t match the Ballot Receipt? The Voter may be willing to raise an objection, maybe going to higher level authorities. But, doing so, the Voter must be obliged to disclose her/his identity in reference to that particular ballot, something that the Voter is unwilling to do. The Authoritative Node may then play with this fact to actually try and omit that ballot.
To avoid this situation, the Witness Nodes come to play. If a ballot is received by multiple Witness Nodes, we hope that at least one of them notices that the vote has been omitted, trying and reinserting it in the final set of tallied ballots: this way, the Voter doesn’t need to disclose her/his identity. Notice that a Witness Node doesn’t know the Poll Private Key and cannot decrypt the votes. In addition, we assume that the Witness Nodes have different and conflicting interests. For example, the Witness Nodes can be run by the different parties running in an election and by the press that is following the event.
One may also argue that receiving the Ballot Receipt and the subsequent membership proof is pointless with this scheme. In a sense, this is true but they can be used by the Voter to sequentially select the Witness Nodes until one of those confirms that the ballot has been received. Basically, the Voter retrieves the first Witness Node and sends the ballot to it. After the Witness Node publishes the hash of the corresponding block to the public Blockchain, the Voter check that her/his ballot has actually been inserted in the block. If it is, the Voter stops. If not, the Voter select another Witness Node and tries again.
Let’s see how the consensus is reached on the list of ballots. The consensus algorithm works as follows:
- Each ballots is assigned to a group. The group the ballot is assigned to is determined by taking the n least significant bits of the digest produced from the ballot using a cryptographic one-way hashing function H, i.e. LSBn(H(ballot)).
- For each group of ballots, a private/permissioned proof-of-authority Blockchain is setup among the Authoritative Nodes and the Witness Nodes. The blocks are built as follows:
- The genesis blockchain block is proposed by the Authoritative Node. The genesis block contains all the ballots in the group along with: 1) the ballot hash H, 2) the block ID N of the block published to the public Blockchain by the Authoritative Node that contains the ballot, 3) the position k of the ballot in block N.
- The subsequent blocks are appended by the Witness Nodes and contain the ballots that are missing from the previous blocks (if any) and belongs to the current group, along with the H, N and k for the Witness Node. These latter information is also provided for all the ballots in the previous blocks.
- As soon as all the Witness Nodes appended a block or when a certain point in time has been reached, the Authoritative Node append a closing block to the Blockchain. The content of the closing block is just the current block digest in the public Blockchain.
Practically, there would be a number of private/permissioned blockchains running in parallel. Once consensus has been reached in all blockchains, the ballots received are then used by the Authoritative/Witness Nodes to calculate the Merkle Tree Hashes for each block generated by the Authoritative Node and the Witness Nodes and comparing the hashes with the ones published in the public Blockchain.
Tallying phase
The Authoritative Node activates the tallying by publishing the Poll Private Key in the public Blockchain. At this point, the Witness Nodes and the Authoritative Node decrypt the votes in the ballots and start the tallying. At the end, the Authoritative Node declares the final winner. If this declaration is in contrast with the set of ballots agreed upon by the Authoritative Nodes and the Witness Nodes during the consensus phase, any Witness Node can always publicly object.
That’s it!
Next steps
This scheme will be analyzed in terms of attack scenarios in a later article. In addition, variations of the scheme will be presented.