zk-SNARKs Explained
Last Updated: 19th December 2018
zk-SNARKs are a novel form of zero-knowledge cryptography that is intended to enhance the privacy of users transacting on the Zcash blockchain. With cryptocurrencies such as Bitcoin, an individual can identify user addresses and track the movement of value between transacting parties on the blockchain. In this case, Bitcoin only provides users with pseudonymous protection, rather than complete anonymity. zk-SNARKs are designed to solve this problem, by completely encrypting user transaction information on the Zcash blockchain.
zk-SNARK is an acronym for ‘Zero-Knowledge Succint Non-Interactive Argument of Knowledge’.
Zero-knowledge refers to a proof of construction where an individual can prove possession of information, without having to reveal that piece of information. In other words, with zk-SNARKs, one party (the prover) can convince the other party (the verifier), that a statement is true, without revealing any information beyond the validity of the statement. For example, Bob could prove to Alice that the hash value of a random number existed, without revealing what that random number was.
Succinct indicates that the zero-knowledge proof can be verified quickly. This includes proofs with statements that are large. With previous zero-knowledge protocols, the prover and the verifier had to engage in multiple rounds of communication in order to validate a proof.
Non-interactive means that the verifier does not have to interact with the prover in order to validate a zero-knowledge proof. Instead, the prover can publish their proof in advance, and a verifier can ensure its correctness.
Argument of Knowledge means a proof of knowledge of some defined computation.
Parameter Generation
The generation of zero-knowledge proofs rely on a set of public parameters that allow users to construct and verify private transactions. These parameters are constructed by sampling some random numbers, which are known as ‘toxic waste’. If an individual had access to the randomness that was used to generate these public parameters, they would be able to generate false proofs that would appear valid from the perspective of the verifier. Thus, this individual would be able to create counterfeit coins in the Zcash network.
To prevent any one individual from being able to access this secret randomness (and to destroy this toxic waste), Zcash makes use of its multi-party computation (MPC) ceremonies. These ceremonies allow multiple independent parties to collaboratively construct the public parameters. This means that, in order for an individual to breach these public parameters, all of the participants would have to be compromised. To date, the Zcash network has generated two distinct sets of public parameters. The first ceremony occurred in October 2016, which involved six participants. The generation of Zcash’s second set of public parameters was divided into two phases: Powers of Tau and Sapling MPC. The Powers of Tau ceremony took place in early 2018 and involved 87 participants. The Sapling MPC ended in August 2018 and saw the participation of 90 individuals.
zk-SNARKs & The Zcash Protocol
In incorporating zk-SNARKs into the Zcash blockchain, the function that determines the correctness of a transaction, in accordance with consensus rules, must return the answer of whether or not that transaction is valid, without disclosing any of the information with which it performed calculations. This is accomplished by encoding some Zcash consensus rules into zk-SNARKs themselves.
With the Bitcoin protocol, transactions are validated by linking the sender address, receiver address, and input, and output values. This is in contrast to the Zcash protocol, which uses zk-SNARKs to prove that the rules for a valid transaction have been satisfied without disclosing any information pertaining to the transaction itself, such as user addresses and transaction value. Instead, a user constructs a proof to show that, with high probability:
- The input values sum to the output values for each transaction.
- The sender proves that they have the private keys of the input, which gives a user the authority to spend.
- The private spending keys of the input are cryptographically linked to a signature that pertains to the entire transaction, in a manner in which a transaction cannot be modified by a party who did not know these private keys.
With Bitcoin, unspent transaction outputs (UTXOs) are tracked in order to determine which transactions contain spendable outputs. The equivalent of a UTXO on the Zcash network is known as a ‘commitment’, and spending a commitment involves revealing a ‘nullifier’. Zcash nodes maintain a list of all commitments that have been created and all nullifiers that have been revealed on the network. Commitments and nullifiers are stored as hashes to prevent information leakage about commitments, and to ensure that nullifiers and commitments cannot be linked by any individual.
When a shielded payment is initiated, a commitment hash consisting of: the payment address, the amount being sent, a secret number ‘rho’ (which is unique to the payment) and a random nonce is created. When a shielded transaction is spent, the sender utilizes their spending key to publish a nullifier, this nullifier is a hash of the secret unique number (‘rho’) from an existing unspent commitment. The nullifier also provides a zero-knowledge proof signifying that the user is authorized to spend the funds.
Commitment = HASH(recipient address, amount, rho, r)
Nullifier = HASH(spending key, rho)
