Devcon3 took place at the beginning of November 2017 where many presenters showcased the power of the Ethereum blockchain. The presentations that really blew me away, and that I’d like to write about today, were around a concept called zero-knowledge proofs or more specifically zkSnarks and zkStarks. Although these technologies are not exclusive to blockchains, they complement their decentralised nature.
History of Cryptography
The invention of computers and subsequent birth of more sophisticated encryption algorithms has allowed messages between two parties to be encrypted with greater security than ever before. The downside of symmetric cryptography however is that a secret key needs to be exchanged securely before the first secret message can be transferred.
In 1976, Whitfield Diffie and Martin Hellman[1] invented the revolutionary Diffie-Helman key exchange protocol which used asymmetric cryptography to exchange a secret key. This invention and other similar protocols enabled two parties who had never met before, to communicate securely without first sharing a secret key.
The secret key was replaced by a public and private key pair. As the name suggests, the public key can be shared without fear that the encrypted message will be intercepted and compromised. Asymmetric cryptography has been widely used since then to secure many protocols and data formats for example HTTPs, email encryption, digital signatures and the protection of blockchain transactions.
Cryptography on Blockchains
Blockchains rely heavily on asymmetric cryptography to keep the value they store secure. Only the person in possession of the private key can craft a transaction that can spend the funds. However, there are a few drawbacks to the way blockchains such as Bitcoin and Ethereum store their transactions. All transactions are public and visible to everyone. This is necessary so that transactions can be verified to ensure that there are enough funds available to complete the transaction or, in the case of Ethereum, all the conditions in a smart contract are met.
The transparent nature of these blockchains inherently allows transactions to be traced throughout the network. While one cannot easily determine who is creating these transactions, it is possible to trace their history throughout the network. The value stored is therefore not 100% fungible. Transactions can be censored based on the recipient or they can be traced back to some illegal activity with dire consequences for the current owner.
Zero-knowledge proofs
This now brings me to the zero-knowledge proof (ZKP) technology in zkSnarks and its newer cousin zkStarks. As the name suggests, a zero-knowledge proof enables a verifier to confirm a proof without gaining any knowledge of the original secret or statement[2]. This sounds counter-intuitive, but this property allows sensitive data to remain protected and at the same time, the prover’s statement can be verified.
Research into zero-knowledge proofs was motivated to allow one party to authenticate to another without revealing any secret authentication information such as a password[3]. This prevents an attacker from gaining access to the user’s private credentials if the communication is intercepted by the attacker.
Safe-keeping of sensitive data
Zero-knowledge proofs are an important tool to preserve the privacy and confidentiality of sensitive data. With more regulations on how user data can be stored and used, this technology could save a company significant fines and reputational damage following any data breaches. It also protects users against identity theft as the user’s identity may never be transmitted in the first place.
Some use cases for zero-knowledge proofs include: authentication, health records, patent databases, DNA databases and voting systems.
In the blockchain world, zkSnarks is being used in cryptocurrencies such as zCash to protect the confidentiality and integrity of transactions[4]. This is done by providing a zero-knowledge proof on the blockchain that the sender has the authority to spend the funds from an existing commitment (shielded UTXO), while creating a new commitment to the recipient that they can now spend the funds. Nobody looking at this blockchain will be able to determine who the sender or recipients are, their balances or the amount that was transferred, but they will be able to prove that the transaction is valid. This provides fungibility to zCash, unlike Bitcoin or Ethereum, and at the same time providing privacy to the parties involved.
ZkSnarks on Ethereum
However, as I learned at Devcon3, the latest release of Ethereum has added new instruction primitives to make it easier to run the verifications of zkSnark proofs on the Ethereum blockchain[5]. This not only means that Ethereum can now provide ‘shielded’ fund transfers similar to zCash, but any computation that can be done on Ethereum could now be done in such a way that nobody will know what the computation is actually computing. At most they can just verify that the transaction is a valid one. I know this sounds a little counter-intuitive, but the zkSnarks protocol unlocks some truly amazing use cases directly on the blockchain.
Zero-knowledge proofs can now be broadcast on the blockchain for anyone to anonymously interact with, without exposing the data they are protecting. For example, a user could provide proof that their membership to a loyalty programme is valid, without exposing their identity to a merchant. Another example is where a person can proof that they have the necessary minimum balance in their bank account without revealing their actual bank balance or statement.
One ‘side effect’ of zero-knowledge proofs however, is that it takes shorter to verify the proof of a computation than actually running the computation itself[6]. Put another way, it may be quicker to prove that you exist in a database than it takes to search the database for your record. Again, this also sounds counter-intuitive, but it could have a bigger impact on the blockchain world than the privacy properties zkSnarks provides.
For Ethereum, it means that the gas usage for an Ethereum smart contract could be much less in terms of verifying the proof, compared to the actual contract itself. The computational heavy lifting now shifts to the prover. The prover must not only compute the statement, but also the verification proof function. However, this only holds true for large computations and could increase the gas usage of simple contracts that require the privacy features.
The evolution of cryptography now finally allows for the ability to share proofs without sharing data – the data can now be stored securely, but the proofs can be shared publicly.
[1] https://www-ee.stanford.edu/~hellman/publications/24.pdf
[2] https://en.wikipedia.org/wiki/Zero-knowledge_proof
[3] https://en.wikipedia.org/wiki/Zero-knowledge_proof#Applications
[4] https://z.cash/technology/index.html
[5] https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b
[6] https://eprint.iacr.org/2013/879.pdf
For Ethereum, it means that the gas usage for an Ethereum smart contract could be much less in terms of verifying the proof, compared to the actual contract itself. The computational heavy lifting now shifts to the prover. The prover must not only compute the statement, but also the verification proof function. However, this only holds true for large computations and could increase the gas usage of simple contracts that require the privacy features.
The evolution of cryptography now finally allows for the ability to share proofs without sharing data – the data can now be stored securely, but the proofs can be shared publicly.
by Chris Tsimogiannis
