This article is part two in a series about cryptography and blockchain technology. Click here to read part one about public key cryptography, hashing, and Merkle trees.
Zero-knowledge Proofs & zk-SNARKs
In the simplest terms, a zero-knowledge proof (or zero-knowledge protocol) is a cryptographic method where one person can prove to another person that they know something without revealing what that something is.
To explain a zero-knowledge proof, let’s say you have two balls that are physically the same except one is white and one is black. How would you prove to a blind person that the balls have different colors without telling them the actual colors?
To prove it, you ask the blind person to hide both balls under a table and bring one ball back up for you to see. Then the blind person returns the ball under the table and either decides to show the same ball or the other one. You will be able to convince the blind person that the balls are different colors by saying whether the balls were switched out or not.
If the blind person is not convinced yet as you may have had a lucky guess, the test can be repeated any amount of times and the probability of consistently guessing will be halved each time. Eventually the blind person will have to accept that the balls have different colors without having any clue what those colors are. This is a simple example of a zero-knowledge proof.
A zero-knowledge proof has 3 requirements that must be met for validity:
- Completeness: If the input is true, the zero-knowledge proof always returns “true”.
- Soundness: If the input is false, there is no way to trick the zero-knowledge proof to return “true”.
- Zero-knowledge: The input cannot be obtained by the verifier or any other party.
Zero-knowledge proofs can be used to enable privacy for blockchain transactions. A successful zero-knowledge transaction would produce an outcome where others know that a valid transaction has taken place, but know nothing about the sender, receiver, or transaction amount.
Zcash is the largest cryptocurrency that makes use of zero-knowledge proofs to enable transactional privacy. Zcash uses a mechanism called “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge”, or zk-SNARK for short, in their shielded (private) transactions.
Zk-SNARKs are essentially a zero-knowledge proof that can be verified within a few milliseconds with a proof length of a few hundred bytes even for statements about very large programs. This is where the “succinct” term in zk-SNARK comes from.
The “non-interactive” term in zk-SNARK means that the proof consists of a single message sent from prover to verifier, whereas the first zero-knowledge protocols required the prover and verifier to communicate in multiple rounds.
Zcash uses zk-SNARKs to prove that the conditions for a valid transaction have been satisfied without revealing any information about the addresses or values involved. The shielded transaction sender constructs a proof to show that:
- The input values sum to the output values for each shielded transfer.
- The sender proves that they have the private spending keys of the input notes, giving them the authority to spend.
- The private spending keys of the input notes are cryptographically linked to a signature over the whole transaction, in such a way that the transaction cannot be modified by a part who did not know these private keys.
Shielded transactions must satisfy some other conditions as well - for more detailed information on how zk-SNARKs operate for Zcash shielded transactions, click here.
Ring Signatures & Ring Confidential Transactions
Ring signatures are a type of cryptographic digital signature invented in 2001 by Ron Rivest, Adi Shamir, and Yael Tauman and first introduced at Asiacrypt. Their original concept was to have ring signatures function as a method to leak secret information (i.e. from government officials) without revealing who signed the message.
Ring signatures are similar to the cryptographic method of group signatures except with more privacy for the user.
In a peer-to-peer transaction format, ring signatures protect the sender by obscuring the input side of the transaction. A ring signature is a message singed by someone in a particular group of people, however it is computationally infeasible to determine which of the group’s members’ keys was used to produce the signature.
Ring confidential transactions (abbreviated as Ring CTs) add to the concept of ring signatures by enabling privacy for both the sender and recipient with modifications like hiding the amount being transacted.
There are multiple privacy-oriented cryptocurrencies that make use of ring signatures and ring CTs to enable transactional privacy. The most notable coins are Monero and Bytecoin, which are both powered by CryptoNote – an application layer protocol that aims to solve the privacy issues associated with Bitcoin.
The name Mimblewimble originates from the Harry Potter series as a spell used to tongue-tie victims. The protocol as it relates to Bitcoin was first proposed by an anonymous user who sent a link to the Mimblewimble whitepaper in a Bitcoin developer chatroom.
Every Bitcoin transaction reveals both the sender’s and receiver’s addresses and the exact amount of BTC sent. This mechanism ensures security as anyone can confirm the correct amount of BTC being transacted or in a specific address at any given time.
Mimblewimble attempts to hide the amount of cryptocurrency in a transaction while still allowing others to prove the transaction is valid. Mimblewimble transactions are a derivation of another transaction type known as confidential transactions, originally proposed by former Bitcoin developer Adam Back.
Confidential transactions allow the sender to encrypt the amount of BTC they send by using a blinding factor. This blinding factor is a random numerical value used to encrypt the BTC amount without affecting the input and output of the transaction.
For the Mimblewimble protocol, these blinding factors are big numbers called Pedersen Commitments. A Mimblewimble transaction has two Pedersen Commitments: one for the amount going into the transaction plus the sender’s public key, and one for the amount that comes out plus the recipient’s public key.
For example, if the sender’s wallet is going to deduct 5 coins and the recipient’s wallet will add 5 coins, the process looks like this:
However, the input and output steps can be combined to cancel out the -5 and 5 amounts:
Which means the top merged amount-part becomes 0, and the transaction is left with:
Thus, the true amount of the transaction is never disclosed to the public. The reason the coin amount disappeared is because the input and the output are equal, if this was not the case then the merged amount-part would not be 0 and the protocol would reject the transaction.
The protocol will also check that the resulting number is divisible by both the sender and receiver’s keys, which will always be the case for a valid transaction due to the properties of multiplication and division. If this condition is met, and the input-output pair cancels to 0, the protocol accepts the transaction as valid without displaying any revealing information to the public.
Two projects attempting to integrate Mimblewimble into blockchain protocols are Grin and Beam, which both recently released their own unique cryptocurrencies. Monero also has plans to implement Mimblewimble on a sidechain named Tari. Charlie Lee, in the quest to pursue fungibility and privacy solutions for Litecoin, is exploring Mimblewimble as well.
The Dandelion Protocol is a lightweight network layer anonymity solution first proposed in 2017 to help enable privacy on the Bitcoin blockchain.
Before diving into the Dandelion Protocol it’s important to understand how Bitcoin transactions work. When a user broadcasts a Bitcoin transaction from a node, it propagates to connected nodes called peers. From there a process called diffusion propagates the transaction in a chain reaction with independent and exponential delays between the communicating nodes.
However, the transaction source node can often be figured out with “spy” nodes that use a network analysis to retrace the transaction’s propagation. This is done by observing the timing of each broadcast and the structure of relays.
Dandelion aims to make it more complicated for people to trace Bitcoin transactions by altering the transaction relaying process. The Dandelion protocol has two distinct phases called the Stem Phase and Fluff Phase.
Instead of immediately broadcasting the transaction to connected nodes like a traditional Bitcoin transaction, the Stem Phase (or anonymity phase) relays the transaction to a random node on the network. This node then sends the transaction to another random node, and the process continues until eventually (and randomly) one of the nodes broadcasts the message to its connected nodes instead of a random one.
The Fluff Phase (or spreading phase) is initiated when this specific node chooses to broadcast the message to its peers, and the transaction is diffused through the network in a traditional manner. Implementing the Stem Phase is what makes Dandelion transactions difficult to reverse engineer for obtaining the sender’s IP address.
A visualization of Dandelion’s two phases is shown below:
Source: Giulia Fanti’s Presentation in Lisbon
An improved version of the Dandelion Protocol was proposed in May 2018 with the name Dandelion++. To read more about Dandelion++, click here.
Although Bitcoin is dubbed to be pseudo-anonymous, it has been proven that transactions can be traced back to the senders’ IP address. There are privacy-oriented cryptocurrencies such as Zcash and Monero that add layers of privacy through cryptographic techniques like ring signatures and zero knowledge proofs, but they require the use of a whole different blockchain.
Mimblewimble and the Dandelion Protocol are two relatively new privacy protocols that function in very different ways. Mimblewimble has recently been implemented in the cryptocurrencies Grin and Beam, while Dandelion was implemented into Zcoin in 2018.
It will be interesting to see if these coins grow over time or if faults in their respective privacy protocols are discovered. As Bitcoin will probably need to adopt a privacy layer in the coming years, it will also be interesting to see if the community chooses Mimblewimble, Dandelion, or another protocol yet to be created.
* The information contained in this article is for education purpose only and not financial advice. Do your own research before making any investment decisions.
This article is contributed by Victor Lai with the help of our Senior Analyst Kieran O'Day.