This article repository address.
This article is translated from Consensys.
Translator: @BoxMrChen
In this article, our goal is to provide an overview of zk-SNARKs from a practical perspective. We will treat the actual mathematical problems as a black box and try to develop some intuition around how we can use them. We will also showcase a simple application of recent work on integrating zk-SNARKs in Ethereum.
Zero-Knowledge Proofs#
The goal of zero-knowledge proofs is to allow a verifier to be convinced that a prover possesses a secret parameter that satisfies some relation, called a witness, without the prover revealing this witness to the verifier or anyone else.
We can think of it more concretely as a program, denoted as C, that takes two inputs: C(x, w)
. The input x is the public input, while w is the secret witness input. The program outputs a boolean value, either true or false. The goal is to prove, given a specific public input x, that the prover knows a secret input w such that C(x,w) == true
.
We will specifically discuss non-interactive zero-knowledge proofs. This means that the proof itself is a piece of data that can be verified without any interaction from the prover.
Example Program#
Let's assume Bob has obtained a hash H of some value and he wants to have evidence that Alice knows a value s that hashes to H. Normally, Alice would prove this by giving Bob s, and then Bob would compute the hash and check if it matches H.
However, let's say Alice doesn't want to reveal the value of s to Bob, but only wants to prove that she knows it. She can use zk-SNARKs to achieve this.
We can describe Alice's scenario using the following program, written in the form of a JavaScript function:
function C(x, w) { return ( sha256(w) == x );}
This program doesn't involve any ZK content, it is just used to represent what we want to achieve. We can think of it as a black box, and we will discuss how to use zk-SNARKs to build such a program in the next section.
In other words, this program takes a public hash x and a secret value w, and returns true if the SHA-256 hash of w equals x.
Translating Alice's problem into the function C(x,w)
, we can see that Alice needs to create a proof that she possesses s such that C(H, s) == true
, without revealing s. This is the general problem that zk-SNARKs solve.
Definition of zk-SNARKs#
A zk-SNARK consists of three algorithms: G, P, and V, defined as follows:
-
The key generator G consists of a secret parameter
lambda
and a program C, and generates two publicly available keys, a proving key pk and a verification key vk. These keys are public parameters and only need to be generated once using the program C. -
The prover P takes the proving key pk, a public input x, and a witness w as inputs. The algorithm generates a proof
prf = P(pk, x, w)
, where the prover knows a witness w that satisfies the program's requirements. -
The verifier V computes
V(vk, x, prf)
, and if the proof is correct, it returns true; otherwise, it returns false. Thus, if the prover knows a witness w that satisfies C(x,w) == true, this function will return true.
Note the use of the secret parameter lambda in the generator. This parameter sometimes makes it tricky to use zk-SNARKs in real-world applications because anyone who knows this parameter can generate fake proofs. Specifically, given any program C and public input x, someone who knows lambda can generate a proof fake_prf such that V(vk, x, fake_prf)
evaluates to true without knowing the secret w.
Therefore, running the generator in practice requires a highly secure process to ensure that nobody knows and keeps the parameters. This is why the Zcash team performs an elaborate ceremony to generate proving and verification keys while ensuring the "toxic waste" lambda is destroyed during the process.
zk-SNARKs for the Example Program#
In practice, how do Alice and Bob use zk-SNARKs to prove that Alice knows the secret value in the example above? First, as mentioned earlier, we will use the program defined by the following function:
function C(x, w) {
return sha256(w) == x;
}
First, Bob needs to run the generator G to create the proving key pk and the verification key vk. To do this, he randomly generates lambda as input:
(pk, vk) = G(C, lambda)
Be careful with the parameter lambda, as if Alice knows its value, she would be able to create fake proofs. Bob will share pk and vk with Alice.
Alice now takes on the role of the prover. She needs to prove that she knows a value s that hashes to a known hash H. She runs the proof algorithm P, using the inputs pk, H, and s, to generate the proof prf:
prf = P(pk, H, s)
Next, Alice presents the proof prf to Bob, who runs the verification function V(vk, H, prf)
. In this case, since Alice correctly knows the secret s, it will return true. Bob can be confident that Alice knows this secret without Alice revealing it to him.
Reusable Proving and Verification Keys#
In our example above, if Bob wants to prove to Alice that he knows a secret, he cannot use zk-SNARKs because Alice cannot know if Bob keeps the lambda parameter. Bob could easily forge evidence.
If a program is useful for many people (like in the case of Zcash), a trusted independent team can run the generator to create the proving and verification keys, and no one will know the lambda parameter.
Anyone who trusts that the team did not cheat can use these keys in future interactions.
zk-SNARKs in Ethereum#
Developers have started integrating zk-SNARKs into Ethereum. What does this look like? Specifically, you can add the building blocks of the verification algorithm as a precompiled contract in Ethereum. Here's how it works: run the generator off-chain to generate the proving and verification keys. Then, any prover can use the proving key to create a proof, which is also done off-chain. Then, you can run a generic verification algorithm inside a smart contract, using the proof, verification key, and public input as input parameters. You can then use the result of the verification algorithm to trigger other on-chain activities.
Example: Confidential Transactions#
Here's a simple example to illustrate how zk-SNARKs can help improve privacy in Ethereum. Let's say we have a simple token contract. Typically, the core of a token contract is mapping addresses to balances:
mapping (address => uint256) balances;
We will keep the same basic core but replace the balances with hashes of the balances:
mapping (address => bytes32) balanceHashes;
We won't hide the sender or receiver of the transaction. But we will hide the balances and the amount being sent. This property is sometimes referred to as confidential transactions.
We will use two zk-SNARKs to send tokens from one account to another. Both the sender and receiver will create a proof.
Typically, in a token contract, to make a transfer of a value, we need to verify the following:
balances[fromAddress] >= value
Our zk-SNARKs need to prove this, as well as that the updated hash matches the updated balance.
The main idea is that the sender will use their initial balance and value as private data. The initial balance, final balance, and hash of the value will be used as public data. Similarly, the receiver will use their initial balance and value as private data. The initial balance, final balance, and hash of the value will be used as public data.
Here's the zk-SNARK program for the sender, where x represents the public data and w represents the private data.
/**
* @param x Public data
* @param w Private data
*/
function senderFunction(x, w) {
return (
w.senderBalanceBefore > w.value && // Ensure the sender has enough balance
sha256(w.value) == x.hashValue && // Ensure the sent value matches the public hash value
sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore && // Ensure the sender's initial balance matches the public hash value
sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter // Ensure the sender's final balance matches the public hash value
);
}
The receiver's zk-SNARK program is as follows:
/**
* @param x Public data
* @param w Private data
*/
function receiverFunction(x, w) {
return (
sha256(w.value) == x.hashValue &&
sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
);
}
These programs check if the sender's balance is greater than the value being sent and if all the hashes match. A trusted set of individuals will generate the proving and verification keys for our zk-SNARKs. Let's call them confTxSenderPk, confTxSenderVk, confTxReceiverPk, and confTxReceiverVk. confTxSenderPk and confTxReceiverPk will be used to generate proofs, while confTxSenderVk and confTxReceiverVk will be used to verify the proofs.
Using zk-SNARKs in the token contract might look like this:
function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
bytes32 hashReceiverBalanceBefore = balanceHashes[_to];
bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);
bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);
if(senderProofIsCorrect && receiverProofIsCorrect) {
balanceHashes[msg.sender] = hashSenderBalanceAfter;
balanceHashes[_to] = hashReceiverBalanceAfter;
}
}
Thus, the only thing that gets updated on the blockchain is the hash of the balance, not the balance itself. However, we can know that all balances have been updated correctly because we can verify the proofs ourselves.
From the above example, we can also see that on the blockchain, we only store the hash of the balance, not the actual balance, which ensures confidentiality of the data. We know that a transaction has occurred between the two parties, but we don't know the specific transaction amount, thus ensuring privacy of the transaction.
Further Details#
The above example of confidential transactions is mainly to provide a practical example of how we can use zk-SNARKs in Ethereum. To create a robust confidential transaction scheme, we need to address some issues:
-
Users need to track their balances in the client, as losing balance data means losing control of the account. Balances could potentially be encrypted with a key derived from a signing key and stored on-chain.
-
Balances need to be encoded with 32 bytes of data and entropy encoded to prevent reverse engineering the hash to compute the balance.
-
Edge cases need to be handled for sending to unused addresses.
-
Senders need to interact with receivers to send. We might have a system where senders can initiate a transaction with their proof. Then, receivers can see they have a "pending incoming transaction" on the blockchain and complete it.