How blockchains can actually help elections

This midterm election season, some in the press are calling blockchain the next big thing, enabling online voting and generally being a key part of solving all election security and transparency problems. I caution everyone to be exceptionally skeptical when a single technology is touted to solve such a complex issue.

The vast majority of these claims are wrong, and I should know. I was part of the Scantegrity team who ran the first election to utilize a blockchain in 2011.

Experts like Matt Blaze are fighting these claims, but forums like twitter (above) lack nuance. While the experts are generally right on this issue, it is incorrect to say blockchains have no uses in civil elections. I also disagree that this is the least interesting part of the voting problem. Let's set the record straight!

Properties Elections Need

Election Properties

The exact, well-defined properties of voting systems [1] can vary, but there is wide agreement at a high level:

Valid voter participation. The voters participating in the election are valid voters, and no voters can vote twice.
Secret Ballots. Voters vote in private. No one else learns how they voted and they cannot prove how they voted to others (or sell their vote).
Well-formed ballots. The ballots clearly express the intent of the voter, and the voter can verify that before casting the ballot.
Cast as Marked. You can detect if a ballot was recorded improperly (for example, you can look at a ballot and tell if an optical scanner misread the intent of the voter).
Collected as Cast. The collection and storage of the ballots guarantees that ballots are the same set as those that were recorded by the voter (i.e.,consistency).
Counted as Collected. Cast ballots are tallied as recorded and collected.

As shown in the above illustration, the biggest problem is keeping consistency between voting, casting, and counting. It is very difficult to make sure all the voters are valid and they have only voted once, especially as the process decentralizes into more polling places (or, the most difficult scenario, to the internet). Once you solve that, the system must make sure valid votes are recorded, then keep those records consistent until they can all be tallied.

Solutions to keeping consistency typically compromise the secret ballot, and these issues are more formally defined as coercion resistance [2]. Any devices used in voting or artifacts created (such as physical paper ballots) are subject to identifying marks and pattern voting attacks. Even assuming all of the hardware and software used in the election is software independent [3], simple things like publishing ballots in the order they were cast can violate voter privacy. It is also becoming increasing impossible to stop voters from recording a voting session.

Properties Provided by Blockchains

While exact properties vary, most blockchain platforms provide an immutable ledger for transactions, a mechanism for smart contracts, and the ability to mint or mine new tokens. None of these are new when taken indvidually, and the inventions date back to the 80s and 90s—David Chaum arguably invented the first blockchain [4], and to my knowledge the digital timestamping system Surety is the longest running. The key difference between then and now is the implementation of all of these features in a continuously running, decentralized, global platform with no single points of control.

Most discussion focuses on the immutable ledger, which enables one to post data and prove that it has not been changed. While any hash chain can do this, blockchain platforms—particularly proof of work based platforms—also allow anyone to verify the order and estimate the time the transaction occurred.

The problem with immutable ledgers occur when a record can violate ballot secrecy. For example, you cannot record ballots to the blockchain in the order they are cast. Nor can you post ballot images or machine records without being very careful. What you can do is post checkpoints of the election—validation of pre-election audits, certification events, ballot hashes that can be verified later, etc.

Smart contracts automate algorithmic rules in contracts, and this is useful to document and enforce compliance with a protocol. Examples include documenting transactions of property, performing an audit protocol, or the generation of a random data set. While you can use different machines and verify the protocols that way, blockchains provide a ready made public platform that is easy for remote observers to verify. You also cannot use smart contracts when an operation must be kept secret.

Minting or mining functionality in the blockchain could be used to create and track ballots, voter identities, and machine credentials. Again, extreme care would need to be taken to avoid ballot secrecy violations.

Hopefully, you are seeing the pattern here that blockchain creates ballot privacy problems. These concerns are not theoretical either, as delegated proof of stake systems have been shown to be susceptible to "Dark DAO" attacks [5]. The only safe way to use blockchains in elections is to limit use to the publicly verifiable actions required to run them.

What blockchains can do for an Election, as shown by CommitCoin

Scantegrity used CommitCoin [6] to post pre-election commitments on Oct 18, 2011 for the municipal election of Takoma Park, MD held on Nov 08, 2011. The Bitcoin blockchain shows BTC0.01 was sent to the hash of 6 files, which are still available for download.

I'll let CommitCoin's FAQ explain the rest:

How do you build a voting system from this?

The verifiable voting example is 95% Scantegrity and only 5% CommitCoin. We are only adding a small amount of additional verification for a particular corner case in Scantegrity.

Scantegrity is an electronic optical scan voting system. You vote on paper and the paper is collected, but it is also scanned electronically (the tallies from both should match and this is standard optical scan). But even if someone were able to modify both the paper ballots and hack the database, Scantegrity will be able to detect it; it uses an additional layer of verification based on crypto.

CommitCoin is used only once in the election. It is used to commit to some election auditing data that must have been generated before the election starts for the audit to be valid. Since CommitCoin allows you to "carbon date" messages, you can come along after the election and be sure the election data was fixed prior to the voting period.

It is not the case that every voter is sending their votes into the block chain (although this could be an interesting modification).

Can you have both secret ballots and verifiable results?

Yes. Crypto can do seemingly impossible things. One of those things is having a voting system where ballot is anonymous (you can't prove how you voted) and yet you can make sure that your ballot is included unmodified in the final tally! Crypto voting systems are often called E2E or end-to-end verifiable. Scantegrity is one, there are others. Scantegrity is the only one that has been used in an actual governmental election (two municipal elections in Takoma Park, Maryland, USA).

Is carbon dating just a fancy way of saying timestamping?

No, carbon dating is a different concept. The block chain does both timestamping and carbon dating. Transactions are time-stamped and other nodes do some general vetting of the timestamp before accepting it for inclusion into the block chain. So if you generally trust the bitcoin network, the timestamp is enough.

But let's say you didn't trust the network at all (even in the extreme case of a 51% attack). If I show that we've put a commitment into block 145535 (which we did), there have been tens of thousands of blocks created since then. Even if I controlled the network, there is no way I could actually compute all those blocks in any time less than a certain amount of time (based on how much computational power you think I have). It would take on the order of months.

The accumulation of blocks after something is inserted is akin to the accumulation of carbon on a physical object. You have a sense of the rate of accumulation (and this can't be arbitrarily changed), you know how much accumulation there has been, and so you can estimate a date. It will be fuzzy. But its enough to distinguish, for example, something that happened a month before an election from something that happened a day after the election (if you are making the decision a few days after the election).

Conclusion

When someone like Matthew Green says blockchains don't solve the voting problem, they are absolutely right and anyone who says otherwise is lying. That said, a careful application of this technology can provide useful features and I would not call those features peripheral.

Blockchain ultimately provides a public bulletin board over the internet. The ability of external observers to validate an election remotely is signficant. Yes, there are other ways to do it, and no, there aren't any other platforms in use that are doing it right now. That is why a blockchain platform can be useful.