In the Renaissance Italy, duels between mathematicians were common, but not by crossing steels, but by solving difficult problems. One of the hardest bones to crack at the time was the cubic equations. Knowing the method for their resolution conferred an enormous advantage in these duels, in which the two mathematicians played not only their prestige but also juicy rewards and sometimes even the professorship.
One of the most famous confrontations was between the mathematicians Niccolo Fontana, nicknamed Tartaglia because of his stutter, and Girolamo Cardano. In 1535, Tartaglia, in a duel against another mathematician, Antonio Maria del Fiore, crushed his rival after solving 30 questions related to cubic equations, while del Fiore did not solve a single one of his 30 problems. It was clear beyond all reasonable doubt, that Tartaglia knew a method for solving cubic equations without having revealed the method itself. Impressed by his victory, Cardano offered Tartaglia to find him a patron if he would reveal the precious method of solving cubic equations. Tartaglia agreed in 1539, under the promise that he would never publish it. Six years later, Cardano published it in his work Ars Magna, claiming that he had learned it from another mathematician, Scipione del Ferro, and triggering Tartaglia’s anger. He then challenged Cardano to a mathematical duel, which was attended by his disciple, Lodovico Ferrari, who defeated Tartaglia. As a result, Tartaglia ended up with no prestige and completely broke.
In the world of information security, a multitude of similar scenarios arise in which one entity knows a secret and needs to prove to another entity that it knows it, but it is not appropriate for it to reveal the secret or any partial information about the secret:
- Who earns more money, you or your brother-in-law? How can you prove it to the satisfaction of the whole family without either of you revealing the amount?
- How to prove the legitimacy of a transaction in a public Blockchain without revealing either the sender, the receiver or the value transferred?
- How can you prove to an app installed on your smartphone that you know the password to authenticate yourself to a website without providing the password itself to that app, to your smartphone, or even to the website?
- How can you prove that you are not underage to access an adult service without revealing your age?
- How can you prove that you are an EU citizen to access an EU health service without disclosing your nationality?
- How can you convince a payment app that you have sufficient funds in your account for a transaction without disclosing your balance?
- How can a country convince others that it has destroyed its nuclear military arsenal without letting neutral inspectors into their facilities?
- How do you vote electronically so that your vote is counted without knowing who you voted for?
- How do you prove that a theorem is correct without providing its mathematical proof?
- How to prove that you know the solution to the most complicated sudoku in the world without revealing it?
Fortunately, cryptography provides an answer to these and many other similar dilemmas: the Zero-Knowledge Proof (ZKP). Let’s see with two mundane examples how these proof work.
Interactive and Non-Interactive Zero-Knowledge Proof
Your brother-in-law claims to be able to distinguish Lourdes’ holy water from tap water at a glance, but the truth is that you don’t trust his mystical powers very much. Imagine that you have two glasses full of water, one from Lourdes and one from the tap. How can your brother-in-law prove to you that he knows which is which without even revealing which is which? Very easy! Just follow these steps:
- You blindfold him and flip a coin. If it comes out heads, you exchange the position of the glasses; if it comes out tails, you leave them as they are.
- You remove the blinders and ask him if the glasses have been exchanged or are still in the same place.
Obviously, it’s not enough to challenge your brother-in-law just once, as he might get it right by pure chance 50% of the time. But if he is truly clairvoyant, he will be right 100% of the time. Therefore, if you repeat the two steps of the test
n times, the probability that your brother-in-law always gets it right by pure chance is reduced to
p = (1/2)n. For example, if it’s New Year’s Eve and there’s nothing on TV, you could repeat the test 100 times, what it would be
p = 7,38×10‒31 practically zero.
This protocol for identifying the glasses is an example of an interactive proving system: a tester (your brother-in-law) and a verifier (you) exchange multiple messages (challenges and answers), typically dependent on random numbers (ideally, the results of untricked coin tosses), until the tester convinces (tests the verifier) of the truth of a statement, with an overwhelming probability.
One problem (or advantage, depending on how you look at it) with these interactive proofs is that only the verifier is convinced by the proof. Your sister may think that you and your brother-in-law have conspired to cheer the New Year’s Eve dinner up and have agreed in advance on the exchange of glasses. The only way for the tester to proof another person who knows the secret is for that other person to act as a tester, proposing random glass exchanges. And so on with each and every person your brother-in-law wants to convince that he knows the secret. That sounds exhausting, right? So, how to convince everyone at once in one step?
There are other, more efficient protocols that allow the proving of knowledge of secrecy in a single step and to the satisfaction of an arbitrary number of observers. These are known as non-interactive zero-knowledge proofs.
For example, imagine that a million-dollar prize is offered for solving a sudoku and you have solved it already! But your brother-in-law, who is after glory more than money, is willing to pay you double for the solution. How can you prove to him and all his relatives that you know the solution without showing them before paying? Do you have some deck of cards? Then it’s easy!
In a sudoku there are nine rows, nine columns and nine boxes. In each of these groups the nine values from 1 to 9 must appear. In total, each number appears 9 times. If you have seven identical decks you can select 27 cards for each number, regardless of suit: 27 aces, 27 twos, …, 27 nines, a total of 243 cards.
- You draw with indelible marker on the grandmother’s tablecloth the sudoku of the competition, so that on each given number (they are the clues or known numbers) you place three cards face up of the corresponding value.
- You ask everyone to leave the room and secretly place three cards with the appropriate value face down on each square to be solved. Once all the piles of three cards have been laid, you ask everyone to come in again and the magic begins!
- First, you remove one card from each row and make nine piles with the nine cards in each row.
- Then you take a card from each column and make nine piles with the nine cards in each column.
- Finally, you make nine piles with the nine cards in each box.
- You shuffle each of the 27 piles separately and lay the cards from each pile face up on the table. If you knew the solution to sudoku, each of the 27 piles will contain nine cards from 1 to 9!
Overjoyed, your brother-in-law pays his debt and Grandma forgets the mishap with the tablecloth.
This example shows how a non-interactive zero-knowledge proof works in practice. Crucial when you want a large number of testers to efficiently verify a proof.
All this is good fun for entertaining the family on New Year’s Eve, but how can we apply it in the real world?
The idea of ZKP was proposed more than 30 years ago by the cryptographers Goldwasser, Micali and Rackoff of MIT. It was considered so revolutionary that it won the first Gödel Prize in 1993 and the Turing Prize in 2012. However, it saw no practical application in industry – until today! ZKP was for decades a powerful hammer in search of nails and finally nails are appearing with the progressive decentralisation of services thanks to block chains (blockchain).
Block Chains and Zero-Knowledge Proofs in the Real World
No, Bitcoin, Litecoin, Ethereum, even Monero, are not anonymous like cash, but pseudo-anonymous, meaning that the transactions leave a trail in the public block chain. However, not all cryptocurrencies are pseudo-anonymous: the most prominent use of ZKP so far is ZCash, one of the most popular cryptocurrencies, which allows anonymous transactions. Specifically, ZCash uses Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge (zkSNARK) which allows the knowledge of a secret to be proofed in milliseconds by means of a single message sent by the tester to the verifier. Thanks to zkSNARK, the only information recorded in ZCash after a payment, is that a valid transaction has been made: no information remains about the sender, the recipient or the amount.
Ethereum has also begun to integrate the zkSNARK, specifically in the form of pre-compiled contracts. A smart contract is basically a deposit of funds that is activated once a certain task is performed. For example, your brother-in-law puts 100 ETH into a smart contract with you, so that when you complete the agreed task, you get the 100 ETH from the smart contract. But what if the task you have to do is confidential and you don’t want to reveal its details to your brother-in-law? Thanks to zkSNARK, Ethereum proves that the smart contract task has been completed without revealing its details.
For a start, zkSNARK can be applied to any type of blockchain, in a security layer of zero-knowledge (ZSL), useful in many cases for any company. One of the most interesting ones is the decentralised identity.
Blockchain, Decentralized Identity and Zero-Knowledge Proof
Our personal data has become a commodity for the technological giants to trade with in order to manipulate our behaviour through advertising and social networks. The zkSNARK and Blockchain can work very well together, providing privacy, security and transparency when exchanging and verifying information, in areas such as health care, communications and finance
The trick is identity solutions based on block chains. Traditionally, a myriad of servers belonging to public or private organisations store and share your data, such as your ID card, date of birth, bank account balance, password (or hash), degree of disability, nationality, contacts, phone number, etc
In a decentralised solution, on the other hand, verifiable credentials are stored: they allow simple operations to be carried out on them, but without seeing their value. For example: Are you an adult? Can you park in the disabled parking space? Do you have funds for this payment? Can you fly to this country? Do you know the password to log in? And so on. In this way, the service does not gain any knowledge about yourself, because your personal information is not sent at any time!
Therefore, it cannot be stolen, it cannot be illegally shared, it cannot be traded. You are the owner and master of your data. Corda by R3 is a good example of the work being done in this line.
Consolidating the Future of the ZKP
Don’t think that all that glitters is gold. The zkSNARK also have their weaknesses, among them, the three biggest are the following ones:
- They depend on an initial configuration of trust between tester and verifier: a set of public parameters is required to build the zero-knowledge proofs and, therefore, private transactions. These parameters are so critical that they are usually generated by a very small group in which absolute trust is placed, creating a potential centralisation problem. For example, in Zcash this initial configuration phase is known as The Ceremony.
- The scalability of zkSNARK can be improved: as the execution time increases, the time needed to generate increases does too, especially for verifying the proofs.
- The underlying cryptography is based on elliptic curves, which makes them vulnerable to quantum computing.
These weaknesses were overcome in 2018 by cryptographer Eli-Ben Sasson, the inventor of the Zero-Knowledge Scalable Transparent ARguments of Knowledge (zkSTARK). These proofs are transparent in the sense that they do not require an initial configuration of confidence because they are based on simpler cryptography through collision-resistant hash functions. This approach is also computationally less expensive and therefore more scalable. And it is also resistant to attacks from future quantum computers because it relies on post-quantum cryptography. One of its drawbacks is that the size of the prooft is larger, which could be limiting depending on which applications. Sasson has founded a company around the zkSTARK, STARKWARE, to improve the scalability and privacy of block chain technologies.
Of course, block chains are not the only scope of application of the zero-knowledge proof. ZKProof, an open initiative bringing together academia and industry, was recently established to promote the safe, efficient and interoperable use of zero-knowledge proving technologies. Its main mission is to standardise protocols to facilitate their implementation by industry.
Data Finally Under the Control of the User
Zero-knowledge proofs hold immense potential to put people back in control of their data, allowing others to verify certain attributes of that data without revealing the data itself. There is no doubt that current and future ZKPs will have a huge impact on finance, health care and other industries by allowing all types of transactions while safeguarding data privacy.