Technical Dry Goods | Deep Understanding of Zcash's Zero-Knowledge Proof System

Foreword

It mainly shares the protocol details of the Zcash Sapling version. A lot of advice ^ _ ^! !! !!

Zcash

So far, Zcash has experienced three iterations in total. The fourth version upgrade time is expected to be 12.11.2019. According to the official introduction, this update is mainly to shorten the block production time. For details, see Zcash network information .

As a successful application of zero-knowledge proof, let us study the mechanism of Zcash with the following questions:

1. How does Zcash hide the sender? 2. How does Zcash hide the receiver? 3. How does Zcash hide the transaction amount?

• Opinion: Three Common Misunderstandings of Blockchain Technology
• BTC and the "Great Wealth Transfer" of Millennials
• Bitcoin only rises when 60% of people are losing money

** Suggestions: Before reading this article, you should have already understood: 1. the concept of note; 2. the basic concepts of zero-knowledge proof;

Sapling

This article mainly shares the main details of the Zcash Sapling version agreement. Compared with the Sprout version, many modifications and optimizations have been made, and no detailed comparative analysis is made here. Back to the general direction, whether it is the Sapling version or the Sprout version, the overall process of the transaction can be briefly summarized in the following three steps: 1. The trader initiates the transaction; 2. The trader generates zk-proof, and signature, and the verifier verifies ; 3. The receiver receives the transaction;

Next, we will try to dig every step carefully to explore how it achieves these three points.

Transaction

Here, we do not describe in detail how the transaction initiator initiated a transaction. We directly introduce the transaction structure in Sapling, as shown in the figure:

In fact, the content of Sapling's transaction structure is more than this. Here are just some of the fields unique to Sapling and the corresponding explanations. The complete transaction structure is described in detail in Section 7.1 of the protocol specification.

In Sapling, transactions are composed of Spend Transfer and Output Transfer, which correspond to hidden inputs and hidden outputs, respectively. SpendDescription and output Description are used to describe the data fields of Spend Transfer and Output Transfer, respectively. They are encoded and expressed as vShieldSpend and The vShieldOutput field is stored in the transaction structure. Next, focus on the content represented by the four fields vShieldSpend, vShieldOutput, valueBlance, and bindingSig.

VShieldSpend

A vShiledSpend corresponds to a SpendDescription, and a reliable SpendDescription represents the effective cost of a note. It contains the following content:

cv: a promise to Inpunote's value. The so-called promise is actually a concealment of the v value. This concealment is one-way, irreversible, and cannot be forged; anchor: the root of the cm Merkel tree, used for verification The existence and validity of inputnote; nullifier: the unique identifier of the note, used to prevent the same note from being spent repeatedly; rk: used to verify the consumption authorization signature; zkproof: zero-knowledge evidence, proof without revealing the corresponding privacy The validity of the note, the right to spend the note, and the validity of a private address

VShieldOutput

Similarly, a vShiledOutput corresponds to an OutputDescription, and a reliable OutputDescription indicates the validity of the new note generated. It contains the following content:

cv: commitment to the value of outputnote, also meets one-way, unforgeable; cmu: commitment to outputnote, the mathematical form of the commitment is a point (u, v) on the curve, cmu is the u coordinate of the point; ephemeralKey : Temporary public key, used to calculate the decryption key encCiphertext: the ciphertext of noteplaint, noteplaint is the specific content of note; outCiphertext: the information ciphertext used to calculate the shared key, which can be used to recover noteplaint information Prove the validity of the newly generated note without revealing any privacy

3. valueBlance

valueBalance represents the change amount of this transparent value pool, which is obtained by subtracting the sum of v of Output Transferd from the sum of v of Spend Transfer. When the valueBalance is positive, it means that the valueBalance is transferred from the Sapling value pool to the transparent value pool. If the valueBalance is negative, the opposite operation is performed. valueBalance will be used in bindingSig to verify the balance property of the transaction.

4. bindingSig

In Sapling, bingingSig serves two purposes. First, the balance property of the transaction is guaranteed; second, the signature private key is generated by calculating the random number rcv of the input and output note cv to prevent the outputDescription from being replayed by the attacker. Guarantee)

Zk-proof and Signature

In Sapling, traders need to generate two zkproof (spend zkproof & output zkproof) and two signatures (spendAuthSig & bindingSig). The following are introduced one by one.

1. spend zk-proof

spend zkproof is mainly to realize that txsender has the right to spend some notes in a scenario without exposing any private information, and these notes are valid. The input is divided into two parts, one is the primary input and the other is the Auxiliary input. Primary input is public input information, and Auxiliary input is private input information, only txsender knows. The specific content is shown in the following figure:

According to the above figure, spend zkproof proves the following points in total: Note commitment integrity: the integrity of the inputnode's commitment, which proves that cm is indeed calculated according to v, rcm, gd, pkd; Merkle path validity: Merkel tree verification path Validity, proves that cm exists on the Merkel tree and is a valid cm; Value commitment integruty: the commitment integrity of inputnote v, which proves that cv is indeed calculated based on rcv, v; Small order checks: proves the private parameters, gd and ak are legal; Nullifier integrity: the unique identification of the Note, proving that nf is indeed calculated based on nsk, cm, pos; Spend authority: the spending power of Note, which proves that it has the private parameters required to spend the note; Diversified address integrity: Computational integrity of one-time addresses. If the above equations are all satisfied, it means that txsender has the right to spend the corresponding note, because equations 4, 6, and 7 are valid; the notes it spends are valid, because 1, 2, 3, and 5 are true.

2. output zkproof

The output zkproof mainly implements to make the validator believe that the new note generated by txsender is valid without exposing any private information. The input is still divided into two parts, one is the primary input and the other is the Auxiliary input. Primary input is public input information, and Auxiliary input is private input information, only txsender knows. The specific content is shown in the following figure:

According to the above figure, the output zkproof proves a few points in total: Note commitment integrity: the integrity of the outputnode's commitment, prove that cm is indeed calculated according to v, rcm, gd, pkd; Value commitment integruty: the commitment of inputnote v Integrity, to prove that cv is indeed calculated according to rcv, v; Small order checks: Prove that the private parameters, gd is legal; Ephemeral public key integrity: The computational integrity of the temporary public key. If the above equations are all satisfied, the new note generated by txsender is valid, because equations 1, 2, and 3 are all true; equation 4 is true to ensure that txreceiver can parse the encrypted data based on its own ivk key and epk. Np and save it to the local collection.

3. spendAuthSig

The meaning of spendAuthSig can be described in two scenarios. First: txsender generates zkproof by itself, and then signs the spendDescription. At this time, if there is an attacker who wants to perform a replay attack on the spendDescription, it needs to be re-signed, and rk will be replaced. Then the verifier will fail the verification when verifying the spend zkproof. If the attacker does not replace rk, Then the verification of pendAuthSig will fail. Therefore, the existence of pendAuthSig effectively avoids replay attacks of pendDescription. Second: txsender calls a third party to generate zkproof, and then signs pendDescription on its own. This is allowed by Sapling. Some wallets with limited computing power can also support private transactions, even if this loses privacy, because all auxiliary inputs need to be sent to a third party. Therefore, in this case, in order to prevent third parties from maliciously generating effective zkproof, txsender needs to sign the spendDescription. It should be noted that the txsender signature uses ask, and the zkproof's proof authority in the zkproof uses ak (ak It can be calculated by ask), so the third party cannot generate a valid signature, which effectively avoids the replay attack of spendDescription. The signature flow of spendAuthSig is shown in the following figure:

4. bindingSig

As mentioned earlier, bindingSig mainly implements two functions. First: the transaction balance is guaranteed without exposing the v values ​​of the spend transfer and output transfer; second: the outputDescription is prevented from being replayed by the attacker, mainly using the random numbers corresponding to the spinDescription and outputDescription used to calculate the cv rcv is used to generate the signature private key bsk, which prevents the attacker from doing evil. Therefore, the signature verification public key is generated using the cv corresponding to the spendDescription and outputDescription. The attacker cannot change the cv, otherwise zkproof will fail the verification. The bindingSig signature verification process is shown in the following figure:

Receive Transation

The general steps of txReceiver to receive transactions are: The receiver traverses the outputDes of each transaction, and uses its own ivk and epk in outputDes to try to decrypt each Cenc. If the return is successful, the received note is added to the local receiveSets. So what is Cenc? How to use ivk and epk to decrypt Cenc?

1. What is Cenc?

Cenc is encCiphertext, which is the ciphertext information encrypted by noteplaint with a symmetric key. Noteplaint refers to the content of the newly generated note of the transaction, and these contents are private. The composition of np and the encryption process of Cenc are shown in the following figure:

The related fields are explained as follows: DiverfiedHash: one-time parameter generator, input d, output gd, each call is different; esk, epk: one-time private key, public key, meet epk = esk * gd; pkd: one-time transmission address ; Np: noteplaint {memo, rcm, v, d} => note information {special field, used by the sender and receiver of the transaction through consensus, generating a random number of cm, denomination of note, diversifier}; KA.DerivePublic: calculation Public key; KA.Agree: calculate shared key; KDF: key acquisition function to get the final encryption key Kenc; Sym.Encrypt: one-time symmetric encryption function; where Kenc is a one-time symmetric encryption key and Penc is the encoding After Cenc. It can be seen from the transaction structure that Kenc is not directly transmitted as clear text. So how does the transaction receiver obtain Kenc and encrypt it?

2. How do I decrypt Cenc with ivk and epk?

First, let's focus on two equations: pkd = ivk * gd esk * gd = epk In the encryption process, the input parameters of KA.Agree are pkd and esk, and pkd * esk = ivk * gd * esk = ivk * epk, so in the decryption process, if ivk and epk can be entered, then KA.Agree (pkd, esk) == KA.Agree (ivk, epk). Understand this, let's take a closer look at the decryption process of Cenc, as shown below:

The relevant fields are explained as follows:

NoteCommit: cm calculation function, the original input is np data; cm: note promise; Extractor: extractor, returns the u coordinate of cm, cm form (u, v); if the returned cmu is the same as in outputDes, then explain The prover has private data for calculating cm;

to sum up

1. Sapling's understanding of the sendAuthSig in the sendDescrption section.

a. Purpose: To prove that someone has the right to spend on inputnote, that is, to have a spendKey

b. Question: In zkproof of spendDes, the proof of spending power is as follows:

spend authority: rk = spendAuthSig.RandomizePublic (a, ak) (1)

Because a and ak are Auxiliary inputs, they are private data. And ak = spendAuthSig.DerivePublic (ask) (2), ask is also private data, so if formula (1) holds, it means that the person has the corresponding spending power. So what is the significance of the presence of spinAuthSig?

c. Solution: In the sapling version, considering that some wallets with limited computing power and limited memory space do not have the ability to generate proof, third-party agents may be required to generate them. The data is disclosed to a third party, which will lose the privacy. In this case, in order to ensure that the third party cannot generate a valid zkproof at will, the transaction initiator needs to sign the entire spendDes with a private key. One point to note is that generating akproof requires ak, does not require ask, and ask is used when signing. Therefore, a third party cannot generate a valid signature.

2. Why evolved from sprout's joinsplit transfer to sapling's spend transfer & output transfer.

a. The size of the generated proof has become smaller, joinsplit [1698bytes]> spend [384bytes] + output [948bytes]

b. Balance proof is not implemented in zkproof, reducing circuit complexity and improving generation and verification performance

3. Both spend and output proof verify the balance property, how to ensure the overall value balance.

The pederson value commitment method is used, which has a homomorphic addition property, that is, without exposing the value of v, verify:

Σvold-Σvold = vbalance

4. How Sapling recipients receive notes.

The receiver traverses the outputDes of each transaction and attempts to decrypt each Cenc with the epk in ivk and outputDes. If it succeeds, it calculates the note and adds it to the receiveSets

5. BindingSig.

Regarding the implementation of this signature, you can refer to Section 4.12 of the protocol description document. The key pair is not regenerated, but based on the generation relationship between cv and rcv to implement the signature verification process

6. How to hide the sender of the transaction?

The verification public key of each transaction is a one-time temporary public key, so the miner does not know the transaction initiator.

7. How to hide transaction recipients?

The address information of the transaction receiver does not exist in the transaction structure. The private address of the transaction receiver is used to generate a symmetric key, and a Cenc is generated. The transaction receiver receives the transaction by using the method in question 4. And the address of the same transaction receiver exposed to different transaction initiators is different, in order to prevent collusion between the transaction initiators.

8. How to hide the v value?

Use pederson value commitment for homomorphic hiding.

The above is personal understanding. If you make a mistake, I hope readers will criticize and correct it. . Thank you ^ _ ^. Finally, I attach an overall structure diagram, hoping to help everyone understand.

The picture is more than 2M, if necessary, you can read the information and personally trust me.

appendix

1. ZCASH official protocol specification https://github.com/zcash/zips/blob/master/protocol/protocol.pdf

We will continue to update Blocking; if you have any questions or suggestions, please contact us!