The cartoon on the left from the WallStreet Journal is worth a thousand words. It illustrates how voting by mail in the 2020 election “is flirting with disaster”.
The undemocratic nature of the physical US voting system is grabbing headlines, as the US Postal Services might not be able to handle the mail-in ballots and people have to stand in line for 10 hours for early voting.
This blog highlights state-of-the-art advances from our consortium with applications to e-voting and other forms of online transactions.
Recent results by PRIViLEDGE partners have led to significant privacy improvements in transaction, computation and storage techniques for DLTs. Privacy in distributed ledger technologies comes in several forms: transactions can be public or private, the inputs to a smart contract computation can be public or private and storage can be public or private as well. (Note that this is not exhaustive. Other privacy aspects in DLTs, such as network level privacy, are important but not covered here.)
This blog highlights some of the PRIViLEDGE consortium’s results to introduce you to the broad progress in this field.
Transactions: Privacy-preserving Proof-of-Stake
The first result I will highlight is Ouroboros Crypsinous, a privacy-preserving Proof-of-Stake based ledger, by the University of Edinborough (UEDIN) and others (see paper [KKKZ19]).
Proof-of-Stake protocols are touted as the next important advance in real-world distributed ledger systems. It is increasing in relevance because it resolves the energy consumption issue of Proof-of-Work based systems. Examples of PoW-based systems are Bitcoin and Ethereum before its current upgrade. Current PoS-based systems that are well-known are Algorand, Cardano and Polkadot.
In the words of our PRIViLEDGE partners from UEDIN, typically “the transaction ledger is a public resource and thus information about the way the transaction issuers operate may be leaked to an adversary”. Crypsinous ensures privacy for transaction issuers. The work on Crypsinous ensures that the proof of stake leadership election can run with a provably secure, privacy-preserving transaction scheme.
The core principle of Ouroboros Crypsinous is combining the strengths of both Ouroboros Genesis, an earlier construction by the same team, and Zerocash protocols: Each coin is eligible to be a leader if a pseudorandom value meets some target. Instead of revealing the coin’s value, however, in Crypsinous parties produce a (non-interactive zero-knowledge) proof of this, as well as proving that the respective coin is unspent.
The result is highly relevant: Bitcoin at its inception, did not have a formal proof of its security. The beauty of this design is that it does. It is so-called “universally composable”, a formal definition of its security model, as well as “forward-secure”. I.e., it ensures that privacy, as well as consistency and liveness, are preserved independently of any other protocols running concurrently with our ledger implementation, and even under active (“adaptive”) corruption.
Computation: Smart contracts and zk-SNARKs
Let’s shift our focus to smart contracts, a popular function of blockchains that executes application logic triggered by a transaction. I.e., it enables deeper interaction between users of a blockchain.
A recent research result [K19] by colleagues from the University of Tartu focuses on blockchains that enable privacy-preserving smart-contracts. One particular example is the Hawk system, which uses formally secure (“universally composable”) zk-SNARKs to provide anonymous interaction and payments.
What is a zk-SNARK? This is a concept that is trending within and outside blockchain circles, and refers to “zero knowledge succinct, non-interactive argument of knowledge.” Informally speaking, it enables a prover to proof he knows the answer to a question, without having to reveal that answer.
I will not go into the details in this blog, but recent developments in SNARKs are what have accelerated privacy advances in DLTs. They are also pivotal for the Crypsinous example discussed above.
The succinctness and efficiency of verification are what make zk-SNARKs popular. They offer computational resource efficiencies, while they offer a very powerful functionality at the same time.
The result from the UTartu PRIViLEDGE team is to make a particularly efficient recent SNARK construction, by Groth et al., available to Hawk by defining it in the UC security model.
Computation: Sonic zk-SNARK
Another contribution by the UEDIN team, together with colleagues from the Electric Coin Company and University College London, that gathered a lot of attention is Sonic [MBKM19]: A new zk-SNARK for general arithmetic circuit satisfiability. Sonic requires a trusted setup, but unlike conventional SNARKs the structured reference string supports all circuits (up to a given size) and is also updatable, so that it can be continually strengthened. This addresses many of the practical challenges and risks surrounding zk-SNARKs.
Sonic’s structured reference string is linear in size with respect to the size of supported circuits, as opposed to the scheme by Groth et al., which scales quadratically.
Storage: E-voting security
The final example is a result by the University of Tartu (UTartu) in the field of e-voting. E-voting security is a broad academic topic. Most of the e-voting literature assumes that election data is stored either in a single server or that there exists a distributed ledger, typically called a bulletin board (BB).
In the words of our UTartu colleagues: “One of the most promising of the existing candidates is the bulletin board construction by Culnane and Schneider [CS14b]”, which proposes a construction for a distributed fault-tolerant system. However, researchers found that they could corrupt the BB system, even if less than one-third of the BB peers were corrupted.
The result [K17] introduces the first cryptographic security definition for e-voting bulletin boards capturing:
(i)confirmable liveness – meaning that BB protocol will eventually terminate, and any honest voter will be provided with a valid receipt;
(ii)(confirmable) persistence – it is impossible to remove items from the BB and items can be posted only through a legitimate posting procedure.
The main idea of their construction is that malicious peers are forced to either reveal themselves in which case they can be ignored, or to behave benignly.
What do these advances by PRIViLEDGE partners enable?
These results should not be understated: These and related advances enable privacy-preserving PoS-based ledgers and digital currencies.
But also, more interactive applications, such as blind auctions or insurance innovations. One particular use-case PRIViLEDGE partners are exploring is to facilitate outcome-based costing between health care providers and health insurers that is both privacy-preserving and verifiable (tamper proof). PRIViLEDGE partners are also exploring recording and verifying personal attributes, such as diplomas, in a secure way.
And last but not least: secure e-voting systems, which can be very valuable in practice, as alluded to in the introduction, witnessing the slippery slope of voter obstruction in the US elections.
Written by Toon Segers, PhD researcher at Eindhoven University of Technology and Head of Product at Roseman Labs. Contact: firstname.lastname@example.org.
Image credit: WSJ.com ‘Mail-In Voting Could Deliver Chaos’, (link)
[CS14b] Chris Culnane and Steve A. Schneider. A Peered Bulletin Board for Robust Use in Verifiable Voting Systems. In CSF 2014, pages 169–183, Vienna, Austria, July 19–22, 2014. IEEE Computer Society.
[K17] Annabell Kuldmaa: On Secure Bulletin Boards for E-Voting, 2017
[K19] Karim Baghery: On the Efficiency of Privacy-Preserving Smart Contract Systems, Cryptology ePrint Archive, Report 2019/480
[KKKZ19] Thomas Kerber, Aggelos Kiayias, Markulf Kohlweiss, Vassilis Zikas: Ouroboros Crypsinous: Privacy-Preserving Proof-of-Stake. IEEE Symposium on Security and Privacy 2019: 157-174
Bonus: The video of Toon Segers giving his speech at the PRIViLEDGE workshop “Data Sharing and Privacy – What Has Changed in the Era of COVID? A Deep Dive into Policy Dilemmas and New Technological Solutions” is available below.