Box

This article open source 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 problem as a black box and try to develop some intuition around how we use them. We will also showcase a simple application of integrating zk-SNARKs in Ethereum in a recent work.

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, known as the witness, without the need for the prover to reveal 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 objective is to prove that given a specific public input x, 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#

Suppose Bob has obtained a hash H of some value and he wants to have evidence that Alice knows the value s that hashes to H. Typically, 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 s to Bob, but only wants to prove that she knows the value. 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, the 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, 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 very secure process to ensure that no one knows and keeps the parameters. This is why the Zcash team performed an extremely complex ceremony to generate the proving and verification keys while ensuring that the "toxic waste" lambda is destroyed during the process.

zk-SNARKs for the Example Program#

In practice, how would Alice and Bob use zk-SNARKs to prove that Alice knows the secret value in the example mentioned 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 and uses it as input:

(pk, vk) = G(C, lambda)

Care must be taken 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 the value s with a hash known as 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 convinced 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 retains 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 separate from Alice and Bob can run the generator to create the proving key pk and the verification key vk, and do so without anyone knowing lambda.

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 construction module of the verification algorithm as a precompiled contract in Ethereum. The process is as follows: run the generator off-chain to generate the proving key and the verification key. 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, the verification key, and the public input as input parameters. Then, you can use the result of the verification algorithm to trigger other on-chain activities.

Example: Confidential Transactions#

Here is a simple example that illustrates how zk-SNARKs can help improve privacy in Ethereum. Suppose 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 will not 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 transfer tokens from one account to another. Both the sender and receiver will create a proof.

Typically, in a token contract, to make a transaction of a certain value valid, 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 is 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 proofs and verification keys for our zk-SNARKs. We will call them confTxSenderPk, confTxSenderVk, confTxReceiverPk, and confTxReceiverVk. confTxSenderPk and confTxReceiverPk will be used to generate the 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 is updated on the blockchain is the hash of the balance, not the balance itself. However, we can know that all balances have been correctly updated because we can verify the proofs ourselves.

Through 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 the confidentiality of the data. We only know that a transaction has occurred between the two parties, but we don't know the specific transaction amount, which guarantees the privacy of the transaction.

Further Details#

The confidential transaction scheme mentioned above 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-byte 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.