How to Safeguard Elections With Crypto
This article is the second in a two-part series about whether crypto can help secure elections. For the first part, click here .
As we look back on the recent failures of technology to secure our elections, from failing in Iowa to a few days later leaking millions of voter re leaking millions of voter records in Israel, we are reminded that technology, especially in the hands of smaller contractors, can be fallible, and lead to massive data leaks. Crypto and Byzantine Consensus was supposed to save us from this, but Bitcoin and Ethereum have not been scalable enough to handle millions of people paying – or voting – at once.
But something exciting has been happening in the last few years. Amid the speculation on ICOs and launches of tokens that can barely be spent, there is a new generation of open source innovation and protocols is being built, such as Intercoin, MaidSAFE and Holochain. The goal is to build provably secure infrastructure, that is endlessly scalable by design, and can finally handle voting and economies at scale.
These new protocols are not based around a monolithic blockchain and do not have a central bottleneck such as a “miner” or a “mining pool”. Instead, each individual entity (a coin, a file, or group activity) is secured by only a small subset of the whole network, called a “shard” or a “section”. Mathematical results from 2009 prove that the number of nodes needed to secure a consensus for most purposes is around 30, with rapidly diminishing returns — as shards with 100 or 1,000 nodes quickly approach extreme overkill.
Much of this technology is not new — in fact it predates Bitcoin. BitTorrent and other peer-to-peer file sharing systems are based on a technique called Kademlia, developed in 2004 by Petar Maymounkov. These kinds of sharded networks can scale indefinitely, their embarrassingly parallel architecture supporting a practically unlimited number of simultaneous transactions — not just peer to peer but with the ability to aggregate results for voting and other community applications. And all of this is done without “layer 2” solutions, which are almost always centralized “cop-outs” that of zero-trust infrastructure.
So What’s The Secret?
As we noted at the outset of the previous article, the problems begin when trust is concentrated in a single place — whether money, data or votes. This makes it economically attractive for both external and internal actors to try to subvert the guarantees we have come to rely on. Dillinger didn’t waste his time robbing piggy banks. Brands won’t buy personal data from random sites with 20 users.
A Bitcoin wallet contains endlessly divisible Unspent Transaction Outputs (“UTXOs”). Because of this endless division, each full node must hold the entire history of every transaction, just in case some of those UTXOs may have come from fake transactions.
An Ethereum wallet contains token balances stored inside a Smart Contract on an Ethereum network. As more and more money is exchanged for this token, its total supply becomes very valuable and the smart contract becomes an attractive target for malicious actors. This is why it has been so hard to shard Ethereum. If, for example, each smart contract was only secured by a few nodes, then at some point it could become economically attractive to attack this consensus, either to change some balances or just prevent further progress and kill the token. Either way — a bad outcome for the network.
Intercoin wallets, on the other hand, would hold coins, each one worth very little, and watched by a small, effectively random group of nodes. Paying exact change is achieved by coins of denominations of 1/2, 1/4 and so on down, and interacting with “change bots” — accounts that exchange a coin for an equal amount of change. Coins on the MaidSAFE network (called “safecoins”) work similarly.
The key is that, in the other direction, there is a natural limit on how much individual coins are worth. There are no UTXOs or Token Balances worth $50 Million. To attack the consensus an attacker would have to infiltrate and subvert most or all of the nodes in one particular shard (called a “section” in MaidSAFE), but all they would take over is one tiny coin. To gain any significant amount of value, they’d need to attack a proportional amount of the network. Each individual attack becomes more and more difficult as the network grows, let alone the combined attacks to net anything of value.
All this means, however, that large transactions must involve large transfers of coins, just as ransom and drug deals in movies are done with large suitcases of $100 bills, each one presumably not trivial to obtain. Thus, such networks are suited for smaller, everyday payments with proportional fees, rather than storing an transferring huge amounts of value for a fixed fee. Where Bitcoin and Ethereum help store value, Intercoin and Maidsafe enable the other side of money — a scalable means of exchange.
How to Fix Voting
So what of our original question — can crypto technology ever become good enough to let us trust our elections to an app? The answer turns out to be YES, BUT! Blockchain technology is not enough — you need to string together several solutions at once:
- Tokens must be given out to ensure that each participant can vote only once. This is essential to any election, and is the only part that has to be done by a centralized agency.
- Results must be recorded in a Merkle Tree, aggregating individual results into precincts, precincts into districts, and so on. Anyone is able to check whether their vote was properly counted, by simply verifying the corresponding Merkle Branch, a quick operation (done in log N time) that is done by BitTorrent clients to check whether the chunk they are about to download belongs to a particular file.
- At each level of the Merkle Tree, there must be multiple independent (and likely mutually distrusting) parties signing off on the result being entered into the record. This is akin to how multiple parties and observers are present when counting votes in real elections. In the crypto world, we call this a Byzantine Fault Tolerant Consensus, and developers have discovered many ways to achieve it.
- Client software must be produced by a variety of independent vendors, so the voter can check, from several different “user agents”, their vote that is about to be committed into the Merkle Tree. More vendors of client apps and more people checking exponentially lower the chances that all the vendors at every level of the stack have colluded to fool our voters and record malicious results.
- Every participant — whether a voter, an overseer, etc. has a private key that they use for the election, which never leaves their personal device. Users owning multiple devices can authorized and deauthorize them by eg scanning QR codes.
The crypto community has already implemented much of this machinery to secure much more valuable things than a single vote. Ethereum, for example, is built on a blockchain secured by many mutually distrusting parties. People may trust their favorite wallet client, but they will also verify using another wallet or a web based blockchain explorer such as Etherscan. The chances of all these entities colluding to steal someone’s tokens become smaller as more clients software is released and more miners secure the back-end network.
Towards the bottom of the Merkle Tree, on the level of individual precincts, individual results do not represent juicy targets to subvert. The payoff is small - 1% of an Iowa delegate, perhaps. By the time the results have been entered on higher levels of the tree, though, they have been checked by a growing pyramid of multiple distrusting parties on every lower level, and fixed in a way that by then is mathematically infeasible to reverse.
The official result of the election does not need to contain how everyone voted, just a short string of text with the final cryptographic hash of all the results. Each individual voter would be able to record their Merkle Branch, in order to check that their vote was recorded and counted correctly. At each level in the tree, mutually distrusting witnesses agreed that they came together and recorded a result correctly. With information being deleted at every step, no one can verify how someone else voted, unless that other person chooses to reveal their vote and Merkle branch. A system could even be constructed where voters can furnish confidential zero-knowledge proofs of how they voted, without the recipients being able to prove it to anyone else.
In a way, Bitcoin and Ethereum are like MySpace and Friendster — the first iterations of a new industry that will tackle trustless computing in increasingly sophisticated things. Ethereum’s blockchain is monolithic, completely public and anyone can check anything. But if new technology will bring down the cost of running elections you can trust, then every organization large and small will want to do one. And they may not want everyone to know the results — they may want privacy inside the organization.
This set of requirements for privacy calls for additional innovations which are now starting to be implemented by the crypto community (here “crypto” is being used in its original sense, meaning cryptography):
- Group encryption. Only certain members of a particular shard or section can decrypt and see what is happening in a specific shard or section.
- Group signatures. Many new techniques have been developed whereby members can vote without knowing how others voted.
- End to end encryption and homomorphic encryption. Research is ongoing about how to efficiently perform mathematical operations on encrypted data without knowing the original values. This can already be done on a large enough scale to do run anonymous elections in medium-sized organizations.
We may never completely get away from having to trust some entity that tries to ensure each person isn’t using multiple identities to vote, but studies have shown that this happens exceedingly rarely when people vote in person. As people are able to vote from their couch, away from prying eyes, we may come to rely more and more on “verified identity” services to solve this remaining security issue. Efforts to standardize and innovate in this area are ongoing and perhaps one day we will even be able to obviate this final need to trust third parties.
But until then, projects like Intercoin, Holochain and MaidSAFE represent a way forward for decentralized crypto infrastructure to finally let us as a society engage in payments, voting, governance, and other scalable activities. Technology and crypto can liberate people to form communities and get things done without needing to hand over massive amounts of trust and control to third parties.
