Zcash is one of the first privacy preserving cryptocurrencies using ZK and FHE

---

Introduction to Zero Knowledge

It is a proof that there exists or that we know something, plus a zero knowledge aspect, that is the person verifying the proof only gains one piece of information that the proof is valid or invalid.

Actors in a Zero Knowledge Proof System

Creator, Prover and Verifier

Proving Systems

A statement is a proposition we want to prove. It depends on:

• Instance variables, which are public.

• Witness variables, which are private.

Given the instance variables, we can find a short proof that we know witness variables that make the statement true (possibly without revealing any other information).

Imagine you have a locked treasure chest (the statement) that you claim to have the key to (the witness variables). The treasure chest is placed in a public square, where everyone can see it (the instance variables). Now, you want to prove to everyone that you have the key to open the chest, but you don’t want to reveal the key itself or any other information.

In zero-knowledge terms, instead of showing the key to everyone or revealing the combination to the lock (which would expose your private information), you perform a magic trick. You take the chest into a private room, open it using your key, and bring it back outside with the chest still locked but the treasure inside rearranged in a specific, agreed-upon way.

---

Introduction to ZK-Snarks

Currently zkSNARKS are the most common proof system being used, for example they form the basis for the privacy provided in ZCash.

The S here stands for succinctness, which means that verifying time scales poly-logarithmically in n (without demanding quasi-linear proving time) and the N means non-interactive, which means that after a pre-processing phase (which may be non-transparent), the proof system cannot allow any further interaction. Notice that according to this definition a non-succinct trusted setup phase is allowed, and, generally speaking, the system need not be transparent, but it must be noninteractive

A zk-SNARK consists of three algorithms \(C, P, V\) defined as follows:

The Creator takes a secret parameter \(\lambda\) and a program \(C\), and generates two publicly available keys:

1. \(Proving~Key~(pk)\)

2. \(Verification~Key~(vk)\)

These keys are public parameters that only need to be generated once for a given program \(C\). They are also known as the Common Reference String.

The prover Peggy takes a proving key \(pk\), a public input \(x\) and a private witness \(w\). Peggy generates a proof \(pr = P(pk, x, w)\) that claims that Peggy knows a witness \(w\) and that the witness satisfies the program \(C\).

The verifier Victor computes \(V(vk, x, pr)\) which returns \(True\) if the proof is correct, and \(False\) otherwise. Thus this function returns true if Peggy knows a witness \(w\) satisfying .

Toxic Waste

Note the secret parameter \(\lambda\) in the setup, this parameter sometimes makes it tricky to use zk-SNARK in real-world applications. The reason for this is that anyone who knows this parameter can generate fake proofs. Specifically, given any program C and public input x a person who knows lambda can generate a proof \(pr2\) such that \(V(vk, x, pr2)\) evaluates to \(True\) without knowledge of the secret \(w\).

Trusted Setups

"SNARKs require something called “the public parameters” . The SNARK public parameters are numbers with a specific cryptographic structure that are known to all of the participants in the system. They are baked into the protocol and the software from the beginning.

The obvious way to construct SNARK public parameters is just to have someone generate a public/private keypair, similar to an ECDSA keypair, (See ZCash explanation) and then destroy the private key.

The problem is that private key. Anybody who gets a copy of it can use it to counterfeit money. (However, it cannot violate any user’s privacy — the privacy of transactions is not at risk from this.)"

ZCash used a secure multiparty computation in which multiple people each generate a “shard” of the public/private keypair, then they each destroy their shard of the toxic waste private key, and then they all bring together their shards of the public key to to form the SNARK public parameters. If that process works — i.e. if at least one of the participants successfully destroys their private key shard — then the toxic waste byproduct never comes into existence at all.

---

FHE - Fully Homomorphous Encryption

[TODO - light explainer]

Homomorphic additive properties:

Given an encrypting function \(F\), we can then perform addition like this:

$$F(x) + F(y) = F(x+y)$$

This property allows us to verify if \(F(x) + F(y)\) is indeed \(F(x+y)\)without having to know the value of \(x\) and \(y\)

---

ZCASH

Zcash is an implementation of the Decentralized Anonymous Payment scheme Zerocash, with security fixes and improvements to performance and functionality. It bridges the existing transparent payment scheme used by Bitcoin with a shielded payment scheme secured by zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs).

Value in Zcash is either transparent or shielded. Transfers of transparent value work essentially as in Bitcoin and have the same privacy properties.

ZCASH ADDRESSES

Addresses which start with "t" behave similarly to Bitcoin, exposing addresses and balances on the blockchain and we refer to these as "transparent addresses". Addresses which start with "z" or "zc" or "zs" include the privacy enhancements provided by zk-proofs and we refer to these as "shielded addresses". It is possible to send ZEC between these two address types.

TRUSTED SETUP

"In order to ensure the toxic waste did not come into existence, our team designed multi-party computation (MPC) protocols which allowed multiple independent parties to collaboratively construct the parameters. These protocols had the property that, in order to compromise the final parameters, all of the participants would have had to be compromised or dishonest. Through 2018, Zcash had created two distinct sets of public parameters. The first ceremony happened in October 2016 just before the launch of Zcash Sprout. The second was generated in2018, anticipating the Sapling network upgrade later that year."

---

ZCASH DESIGN

UTXO MODEL

Imagine Alice has control of Note1, via her secret key $ska$

Alice $(sk_a) -> Note1$

She could send the Note1 to Bob by giving him the secret key sk that controls Note1, but then she would still have control of it. A better idea is Alice signs a transaction to cancel Note1 and allow Bob to create Note2 of the same value

Alice $(sk_a)$ cancel $Note1$

Bob $(sk_b)$ -> $Note2$

Then Bob has control of the new Note.

ZCash follows the UTXO model and develops it further,

1. to the note we add a random value r as an identifier

2. rather than storing these values directly, we store a hash of those values. In order to cancel the notes we introduce the notion of a nullifier

The Commitment / Nullifier

Commitments

A commitment scheme is defined by algorithms Commit and Open Given a message m and randomness r, compute as the output a value c

$$⁍$$

A commitment scheme has 2 properties:

1. Binding: Given a commitment c, it is hard to compute a different pair of message and randomness whose commitment is c. This property guarantees that there is no ambiguity in the commitment scheme, and thus after c is published it is hard to open it to a different value.

2. Hiding: It is hard to compute any information about m given c.

In ZCash Pedersen hashes are used to create the commitments using generator points on an elliptic curve Given a value v which we want to commit to, and some random number r, commitment c:

$$c = v ∗ Gv + r ∗ Gr$$

Where Gv and Gr are generator points on an elliptic curve.

Nullifiers

Nullifiers are used to signal that a note has been spent. Each note can deterministically produce a unique nullifier.

The nullifier is designed to uniquely identify a note when it is spent, without revealing which note it is or to whom it belongs. To achieve this, Zcash uses the spending key and a note-specific value (typically called ρ or rho).

$$nullifier=PRF_{spendingkey}(ρ)$$

PRF (Pseudo-Random Function): This function is keyed by the spending key and takes the note-specific value ρ as input. The output is the nullifier, which is unique to this specific note and the associated spending key

When spending a note,

1. The nullifier set is checked to ascertain whether that note has already been spent.

2. If no nullifier exists for that note, the note can be spent

3. Once the note has been spent its nullifier is added to the nullifier set

---

STORING DETAILS OF NOTES AND NULLIFIERS

To each note there is cryptographically associated a note commitment . Once the transaction creating a note has been mined, the note is associated with a fixed note position in a tree of note commitments.

Computing the nullifier requires the associated private spending key. It is infeasible to correlate the note commitment or note position with the corresponding nullifier without knowledge of at least this key.

An unspent valid note, at a given point on the block chain, is one for which the note commitment has been publically revealed on the block chain prior to that point, but the nullifier has not.

---

TRANSACTIONS

Each transaction has a list of Spend and Output Descriptions

We also create zkps to prove existence of the note in the merkle tree, and ownership of the note

Spend Descriptions spend existing notes , the spender needs to show that

1. The note exists

2. The spender owns the note

3. The note has not been spent before, by computing a nullifier unique to that note and checking this against the nullifier set.

The Spend description commits to a value commitment of the note and all necessary public parameters needed to verify the proof. The proof is constructed on private parameters to validate note ownership and spendability. Output Descriptions create new notes

• Only the sender’s outgoing view key and recipient’s incoming view key can decrypt the details

• Only the recipient can spend the new note

• Which note was used is not revealed

• Who the sender, recipient, or the amount is not revealed

• The nullifier is unique to each note, and is revealed when spent

The nullifiers are necessary to prevent double-spending: each note on the block chain only has one valid nullifier, and so attempting to spend a note twice would reveal the nullifier twice, which would cause the second transaction to be rejected.

---

ENCRYPTION/DECRYPTION OF NOTES IN ZCASH

Key Components and Address Derivation

• Spending Key ($sk$): This is the root private key, randomly generated.

• Full Viewing Key ($vk$): Derived from $sk$, includes components such as $ak$ (authorizing key) and $nk$ (nullifier key).

• Incoming Viewing Key ($ivk$): Derived from $vk$, used to derive the diversified public key.

• Diversified Public Key ($pk_d$):

  $$pk_d=ivk×G$$

  where G is the base point on the elliptic curve.

• Diversifier (d): A small value used to derive distinct addresses from the same root key.

• Shielded Address ($z-addr$):

$$z-addr=(d,pk_d)$$

Encryption by Sender

Step 1: Generate Ephemeral Key Pair

• The sender generates an ephemeral private key $esk$ (ephemeral secret key).

• The ephemeral public key $epk$ is then computed as:

$$epk=esk×G$$

Step 2: Compute the Shared Secret

• The shared secret $K_{shared}$ is computed using the sender's ephemeral secret key $esk$ and the recipient's diversified public key $pk_d$:

$$K_{shared}=esk×pk_d$$

• Since $pk_d$ is $ivk \times G$, this can also be expressed as:

$$K_{shared}=esk×(ivk×G)=(esk×ivk)×G$$

Step 3: Derive the Symmetric Encryption Key

• The shared secret $K_{\text{shared}}$ is passed through a key derivation function (KDF) to produce a symmetric encryption key $k_{\text{enc}}$:

$$k_{enc} = KDF(K_{shared})$$

Step 4: Encrypt the Note

• The note $m$ (which contains the value, ρ, and other relevant data) is encrypted using the symmetric key $k_{\text{enc}}$:

$$c=Encrypt(k_{enc},m)$$

where $c$ is the cyphertext

Decryption by Receiver

Step 1: Compute the Shared Secret

The recipient computes the shared secret $K_{\text{shared}}$ using their private key associated with $pk_d$ (denoted as $sk$) and the sender's ephemeral public key $epk$:

$$K_{shared}=sk×epk$$

Since $epk$ is $esk \times G$, this can be expressed as:

$$K_{shared}=skd×(esk×G)=(skd×esk)×G$$

Step 2: Derive the Symmetric Decryption Key

• The recipient derives the symmetric decryption key $k_{\text{enc}}$ using the same key derivation function:

$$k_{enc}=KDF(K_{shared})$$

Step 3: Decrypt the Note

• The recipient uses $k_{enc}$ to decrypt the ciphertext c:

$$m=Decrypt(k_{enc},c)$$

This begs, the question if only the recipient and sender can decrypt the note, then how is this transaction verified by the Blockchain validators? That takes us into the next section.

---

TRANSACTION CREATION AND VERIFICATION IN DETAIL

Alice wants to send 5 ZEC to Bob.

Step 1: Alice Selects the UTXO to Spend

• Alice selects a note she owns, say with value 5 ZEC and unique identifier $ρ_A$. This note has been committed to in the blockchain with a commitment $C_A$.

• This note is associated with a nullifier $N_A$, which is derived from Alice's spending key and $ρ_A$:

$$N_A=PRF_{sk_A}(ρA)$$

Step 2: Alice Creates the New Note for Bob

• Alice generates a new note for Bob with:

  • Value: 5 ZEC

  • Unique identifier: $ρ_B$ (randomly generated by Alice)

  • Recipient's public key: $pk_{d_B}$

• Alice generates the note commitment for this new note:

$$C_B = Commit(5, \rho_b, pk_{d_b})$$

where $Commit$ is the commitment function. (Pederson Hash is used for ZCash Commitment)

Step 3: Alice Encrypts the Note for Bob

• Same as Explain above using $Bob's$ zk-addr

Step 4: Alice Prepares the Transaction

• Inputs: The transaction includes:

  • The nullifier $N_A$ of the note Alice is spending.

  • The encrypted note $c_B$ for Bob.

  • The ephemeral public key $epk_A$.

• Outputs: The transaction also includes:

  • The commitment $C_B$ of the new note for Bob.

• zk-SNARK Proof ($pr$): Alice generates a zk-SNARK proof $pr$ that proves:

  • The sum of inputs equals the sum of outputs (i.e., 5 ZEC = 5 ZEC).

  • Alice has the right to spend the note associated with $N_A$.

  • The commitment $C_B$ is correctly formed.

Verification by the Validator

When the transaction is included in the blockchain, the validator performs the following checks:

Step 1: Verify the zk-SNARK Proof

• The validator runs the zk-SNARK verification function $V$ to verify the proof $pr$:

$$V(pr,(N_A,C_B))=True~or~False$$

If $V$ returns $True$, the transaction passes the zk-SNARK verification.

Step 2: Check the Nullifier Set

• The validator checks whether $N_A$ is in the global nullifier set:

• If $N_A$ is already in the set, the transaction is invalid (double-spending attempt).

• If $N_A$ is not in the set, the validator adds $N_A$ to the nullifier set to mark the note as spent

Step 3: Check the Commitment

• The validator checks that the new note commitment $C_B$ is valid and correctly formed (as proven by the zk-SNARK proof)

• The proof $pr$ already guarantees this, so the validator relies on the zk-SNARK proof for this verification.

This process shows how Alice can create a transaction for Bob, and how the validator verifies the transaction, ensuring that all cryptographic conditions are met and that privacy is preserved.

---

Commitment Scheme and Homomorphic Properties

Zcash uses a Pedersen commitment scheme, which has homomorphic properties. A Pedersen commitment allows you to commit to a value (like a note value) while keeping it hidden. The key property of Pedersen commitments is that they are additively homomorphic. This means that the commitments can be combined in a way that the result is a commitment to the sum of the committed values

Homomorphic Property

The homomorphic property of Pedersen commitments means that:

$$C(v1​,r1​)+C(v2​,r2​)=C(v1​+v2​,r1​+r2​)$$

In other words, the commitment to the sum of two values is the same as the sum of the commitments to each value.

APPLICATION IN ZCASH TRANSACTION

In a Zcash transaction, the goal is to prove that the sum of the inputs (the notes being spent) equals the sum of the outputs (the notes being created) without revealing the actual values of the inputs and outputs.

1. Commitments to Individual Notes:

• Suppose you have two notes with values $v_1$ and $v_2$, and randomness $r_1$ and $r_2$, respectively.

• The Pedersen commitments to these notes are:

$$C_1=v_1⋅G+r_1⋅H$$

$$C_2=v_2⋅G+r_2⋅H$$

• Here, G and H are fixed generators on the elliptic curve used in the commitment scheme.

1. Adding the Commitments:

• You can add the commitments of the two notes:

$$C_1+C_2=(v_1⋅G+r_1⋅H)+(v_2⋅G+r_2⋅H)$$

• Simplifying this gives:

$$C_1+C_2=(v_1+v_2)⋅G+(r_1+r_2)⋅H$$

• This sum is a new commitment $C_3$

$$C_3=(v_1+v_2)⋅G+(r_1+r_2)⋅H$$

The resulting commitment $C_3$ is a commitment to the sum of the values $v_1 + v_2$ using the combined randomness $r_1 + r_2$

1. Output Note Commitment:

• When you create an output note with a value $v_3$ (which should equal $v_1 + v_2$) and randomness $r_3$ (which should equal $r_1 + r_2$), its commitment $C_3$ would be:

$$C3​=v3​⋅G+r3​⋅H$$

• If $v_3 = v_1 + v_2$ and $r_3 = r_1 + r_2$, then the output commitment $C_3$ will exactly match the sum of the input commitments.

$$C_3 = C_1 + C_2$$

1. Adjusting for randomness in Zcash

The randomness value $r$ for each note (which is part of the Pedersen commitment) is typically generated randomly and independently for each new note. This raises an important question: how can the sum of the input commitments match the output commitments if the r values are generated randomly?

Basically,

$$r3 \neq r1 + r2$$

Therefore:

$$C3 \neq C1 + C2$$

This is because in practice $r_3$ is generated independently for $r_1$ and $r_2$.

The zk-SNARK proof plays a critical role here by ensuring that the commitments are correctly formed even though the randomness values are different. The proof guarantees that:

1. Value Conservation: The sum of the input values equals the sum of the output values, i.e., $v_1 + v_2 = v_3$.

2. Correctness of Commitments: The commitments are correctly formed, taking into account the new randomness for the output note.

To account for the difference in randomness, the transaction may include an adjustment factor. Here's how it works:

• Adjustment Factor:

  • The zk-SNARK proof ensures that an additional term (let's call it $R_{adj}$) is introduced to account for the difference in randomness:

$$R_{adj}=(r1+r2−r3)⋅H$$

• The commitments are then adjusted as part of the proof to ensure that:

$$C_1+C_2=C3+R{adj}$$

• This ensures that even though r_3 is randomly chosen and independent, the overall commitment equation holds.

---

Summary

Zero-knowledge proofs allow one to prove knowledge of information without revealing the information itself, ensuring privacy in cryptographic systems. zk-SNARKs are a widely used zero-knowledge proof system, particularly in Zcash, where they enable privacy-preserving transactions. Zcash combines the UTXO model with zk-SNARKs to create shielded transactions that hide the sender, recipient, and transaction amount. Commitments and nullifiers are key cryptographic tools in Zcash, ensuring that notes (UTXOs) can be committed to securely and spent only once. Pedersen commitments, which have homomorphic properties, allow the sum of commitments to be verified without revealing the underlying values. Despite the randomness in these commitments, zk-SNARKs ensure the integrity of the transactions by accounting for differences in randomness. The "trusted setup" phase in zk-SNARKs is crucial for generating secure public parameters, with careful handling required to prevent misuse. Zcash’s design effectively balances privacy with transaction integrity, using advanced cryptographic techniques. Homomorphic encryption in Zcash allows operations on encrypted data, maintaining privacy while enabling verification. The combination of zk-SNARKs and homomorphic properties makes Zcash a powerful tool for secure, private digital transactions.

---