Introduction to zk-SNARKs with examples (translation)

Hi, Habr! I present to your attention the translation of the article “ Introduction to zk-SNARKs with examples” by Christian Lundkvist.

In this article we will try to give an overview of zk-SNARKs from a practical point of view. We will consider the mathematics used as a black box, but we will try to show a little intuition to understand how this technology can be used, and we will show a simple application based on the recent integration of zk-SNARKs into Ethereum .

Evidence with zero disclosure

The goal of zero-disclosure evidence is that the verifier can verify that the verifier has knowledge of a secret parameter, called evidence, satisfying certain relationships, without disclosing the evidence to the verifier or anyone else.

If we go to the specifics, imagine that we have a program called C , which takes two parameters: C(x, w) . The parameter x is the public value, and w is the secret value of the certificate. The program returns a boolean value, that is, either true or false . The goal is to get such a public value of x so that you can be sure that the person being checked knows a secret value of w , such that C(x,w) == true .

We will specifically discuss non-interactive evidence with zero disclosure, which means that the proof itself is a block of data that can be verified without any interaction with the verifier.

Sample program

Suppose that Bob received a hash H some value, and he wants to get evidence that Alice knows the value of s , whose hash is equal to H Alice usually proves this by giving s Bob, after which Bob computes the hash and checks that it is equal to H

However, suppose Alice does not want to disclose the valuable value of s Bob, instead she just wants to prove that she knows the value of s . For this, it can use zk-SNARKs.

We can describe this script using the following program, described below as a Javascript function:

 function C(x, w) { return ( sha256(w) == x ); } 

In other words: the program takes the public hash x and the secret value w and returns, true if the SHA-256 hash w is x .

Having described Alice’s problem using the C(x,w) function C(x,w) we see that Alice needs to create a proof that she has s such that C(H, s) == true , without revealing the value of s . This is a common problem that zk-SNARKs solve.

Zk-SNARKs definition

Generator (C circuit, λ is ️):
(pk, vk) = G (λ, C)
Prover (x pub inp, w sec inp):
π = P (pk, x, w)
Verifier:
V (vk, x, π) == (∃ w st C (x, w))

The definition is given on twitter :)

Zk-SNARKs consists of three algorithms G, P, V defined as follows:
The key generator G takes the secret parameter lambda and program C , and generates two public keys: an evidentiary key pk , and a verification key vk . These keys are public parameters that need to be created only once for a given C program.

The prover algorithm P takes as input values ​​the key pk , the public value x and the secret value w . The algorithm generates a proof prf = P(pk, x, w) that the prf = P(pk, x, w) knows the secret value of w and that the secret value satisfies program C

The checking algorithm V computes V(vk, x, prf) result of which is true if the proof is true and false otherwise. Thus, this function returns true if the verifier knows that the secret value w satisfies C(x,w) == true .

Note the secret parameter lambda used in the generator. This option sometimes makes it difficult to use zk-SNARKs in real-world applications. The reason for this is that anyone who knows this parameter can generate bogus evidence. In particular, for any C program and public x person who knows lambda but does not know the secret w can create a proof of fake_prf , to which the algorithm V(vk, x, fake_prf) returns true .

Thus, starting the generator should be a safe process, protected from being able to find out or steal the lambda parameter. This caused an extremely complex ceremony , conducted by the Zcash team to create an evidentiary key and a verification key, with all lambda “toxic waste” destroyed.

Zk-SNARKs for our sample program

How would Alice and Bob use zk-SNARKs in practice so that Alice could prove that she knows the secret value in the example above?

First of all, as discussed above, we will use the program defined by the following function:

 function C(x, w) { return ( sha256(w) == x ); } 

The first step, Bob starts the generator G to create an evidence key pk , and a verification key vk . This is done by randomly generating lambda and using this value as input:

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

As discussed above, the lambda parameter must be handled with utmost care, because if Alice finds out lambda , she can create fake evidence. Next, Bob shares pk and vk with Alice.

Now Alice will play the role of proving. She needs to prove that she knows the secret value of s whose hash is H It runs the proving algorithm, P using the inputs pk, H s to generate the proof prf:
prf = P(pk, H, s)

Alice then presents the proof of prf Bob, he performs the checking function V(vk, H, prf) , which returns true in this case, since Alice really knows the secret value s . Now Bob can be sure that Alice knows the secret value, while Alice did not need to reveal the secret to Bob.

Reusable checks and evidence keys

In our example above, zk-SNARKs cannot be used if Bob wants to prove to Alice that he knows the secret value. This is due to the fact that Alice cannot be sure that Bob did not save the lambda parameter, and therefore Bob can forge evidence.

If the program is used by many people (for example, Zcash), a trusted independent group, apart from Alice and Bob, can start the generator and create an evidentiary key pk , and a verification key vk so that no one will know about the lambda parameter.

Anyone who trusts this group can use these keys for future interactions.

zk-SNARKs in Ethereum

Developers have already begun to integrate zk-SNARKs into Ethereum. What does this look like? The verification algorithm blocks are added to Ethereum as precompiled contracts. The following is used: the generator is started outside the blockchain to create an evidence key and a verification key. Anyone proving can then use an evidence key to create evidence, also offline. Then, the general verification algorithm can be executed inside a smart contract, using proof, a verification key and a public value as input parameters. The result of the verification algorithm can then be used to launch other actions on the blockchain.

Example: Confidential Transactions

Here is a simple example of how zk-SNARKs can help in privacy in Ethereum. Suppose we have a simple token contract . Typically, a token contract would include address matching with residuals:

 mapping (address => uint256) balances; 

We are going to keep the base core, but replace the balance sheets with the hash balance sheets:

 mapping (address => bytes32) balanceHashes; 

We are not going to hide the sender or the recipient of transactions, but we will be able to hide balances and amounts sent. This is sometimes referred to as confidential transactions.

Two zk-SNARKs will be used to send tokens from one account to another, one proof will be created by the sender, and one will be created by the recipient.

Usually in a token contract for a transaction whose size must be value , we need to check the following condition:

 balances[fromAddress] >= value 

Thus, we need to make sure that our zk-SNARKs prove that the condition is met, and that the updated hashes correspond to the updated balance sheets.

The basic idea is that the sender will use his initial balance and transaction value as secret values, and hashes of initial, final balance sheets and transaction costs as public values. Similarly, the recipient will use the opening balance and transaction costs as secret values, and the hashes of the initial, final balances, and transaction costs as public values.

Below is the program that we will use for the sender zk-SNARKs, where, as before, x represents the public value and w represents the secret value.

 function senderFunction(x, w) { return ( w.senderBalanceBefore > w.value && sha256(w.value) == x.hashValue && sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore && sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter ) } 

The program used by the recipient is shown below:

 function receiverFunction(x, w) { return ( sha256(w.value) == x.hashValue && sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore && sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter ) } 

The programs check that the balance of the sender is greater than the value being sent, and also check that all the hashes match. The trusted community of people will generate an evidence key and a verification key for our ZK-SNARKs, let's denote them: confTxSenderPk, confTxSenderVk, confTxReceiverPk confTxReceiverVk .

Using zk-SNARKs in a token contract will look something 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 updates on the blockchain are hashes of balances, and not the balances themselves. However, we can know that all balances are updated correctly, because we can verify that the evidence is correct.

Details

The above confidential transaction scheme basically gives a practical example of how zk-SNARKs can be used in Ethereum. To create a reliable secret transaction scheme based on this, we will need to solve a number of problems:

• Users will need to keep track of their client-side balance sheets, and if you lose the balance, you will not be able to recover these tokens. Perhaps balances can be stored in encrypted form in the blockchain, using the key obtained with the signature key.
• Balances should use 32 bytes of data and encode entropy in terms of balance in order to prevent the possibility of matching hashes to calculate balance values.
• It is necessary to decide what to do in the case of sending to an unused address.
• To send the sender you need to interact with the recipient. It would be possible to create a system in which the sender uses his evidence to initiate a transaction, and the recipient can see in the blockchain that he has a “pending incoming transaction” and complete it.