VIDEO
HIGHLIGHT
Log InSign up
Zero Knowledge Proofs Class 3: Tornado Cash Whitepaper
SummaryTranscriptChat

Zero Knowledge Proofs Class 3: Tornado Cash Whitepaper

Introduction and Goal

In this section, the speaker introduces themselves and their goal for the session.

  • The speaker greets the audience and introduces themselves.
  • They confirm if everyone can hear them.
  • The goal of the session is to read Tornado Cash white paper and understand its zero-knowledge privacy solution.

Protocol Description

In this section, the speaker describes the functionality of Tornado Cash protocol.

Inserting and Depositing Money

  • Users can insert and deposit money into a smart contract with a fixed amount of ether called a coin.
  • Depositing should be done with a uniform amount of ether to make it harder to know who's who on withdrawal later.

Removing and Withdrawing Money

  • Users can remove or withdraw money from the smart contract either through a layer or directly.
  • If users go through a layer, they pay a fee F to the relayer for helping out.
  • If users go directly, they have to pay gas fees.

Deposit Process

In this section, the speaker explains how users can deposit coins into Tornado Cash protocol.

  • To deposit a coin, users generate two random numbers K and R in this field.
  • Then compute C as equal to hash function of K and R bitwise put next to each other.
  • Send an Ethereum transaction with an eth value interpreted as an unsigned 256-bit integer if the tree is not full.
  • The contract accepts the transaction and adds C to the tree as a new non-zero leaf.

Tornado Cash: Deposit and Withdrawal

In this section, the speaker explains how deposit and withdrawal work in Tornado Cash. They also discuss the Merkle tree and the nullifier hash.

Deposit

  • To deposit, select a root R for the tree among the stored ones in the contract.
  • Compute an opening that ends with R.
  • Prove that your value is in the tree.
  • Fiat deposit pick two numbers to withdraw later.
  • Remember them to withdraw.

Withdrawal

  • Provide recipient address A and fee value.
  • Prove that your value was in the tree at this position using a Merkle tree root.
  • Compute nullifier hash to prevent double spending attacks by remembering hashes of all K values that have successfully withdrawn so far.
  • Verify proof and uniqueness of nullifier hash before sending money to you and fee to layer.

Implementation Details

This section covers implementation details of cryptographic functions used in Tornado Cash.

Cryptographic Functions

  • Four libraries are used, two written by item three and two by Tornado Cash.
  • MC sponge contract is a common hash function, circum is what will be learned next week.

Security Claims

  • Only coins deposited in the contract can be withdrawn.
  • No coin can be withdrawn twice due to nullifier hash usage.
  • Any coin can be withdrawn once if parameters KR are known unless a coin with same K has already been deposited and withdrawn.
  • Randomly generate K so it's not picked by someone else.
  • Big 256 bit values should provide enough room for unique picks.
  • If K or R is unknown, a coin cannot be withdrawn.
  • Attacker cannot prevent one who knows KR from withdrawing coin even if K is unknown to attacker.
  • Transaction cannot be front run due to zero knowledge proofs.

Security Claims and Implementation

In this section, the speaker discusses the security claims and implementation of Tornado Cash.

Cryptographic Primitives Used by Tornado Cash

  • The cryptographic primitives used by Tornado Cash have at least 126-bit security, except for the curve of the discrete logs which has 100 bits.
  • The security does not degrade because of their composition.

Combining Secure Encryption Methods

  • It is fine to combine less secure encryption methods with more secure ones as long as they are used together.
  • Each withdrawal and deposit since the last moment when the contract has zero ether till the formation of the root can be a potential coin.
  • Some coins are more likely to be withdrawn depending on user behavior.

User Behavior and Privacy Risks

  • Users can mess up using Tornado Cash if their behavior is not normal.
  • If a user withdraws immediately after depositing a large amount, it may reveal their identity.

Groth16 ZK-SNARK

In this section, the speaker talks about Groth16 ZK-SNARK.

Most Common ZK-SNARK

  • Groth16 is referred to commonly as Groth 16 and is the most common ZK-SNARK used in most applications.

Understanding Groth16

  • The speaker will go into more detail later on how Groth16 works because it's so common.

Setup

In this section, we learn about setting up Tornado Cash.

Defining Terms

  • B is equal to a set of zero and one.
  • E is a pairing operation used in snark proofs which is defined over the group's Prime order Cube.
  • H1 from B to zp is a Pederson hash function defined in Peterson's paper.
  • H2 from zp zp be the mem C hash function to find some MC permutation in five still mode and sponge mode of operation.

Merkle Tree

  • T is a Merkel tree of height 20 where each non-leaf value node hashes its two children with H2.
  • Mimsy hash function will be used later for our Merkle tree.

Initializing Memc

  • Memc is initialized with all leaves being zero values later zero values are gradually added.

Conclusion

Tornado Cash uses cryptographic primitives that have at least 126-bit security, except for the curve of the discrete logs which has 100 bits. Combining less secure encryption methods with more secure ones is fine as long as they are used together. User behavior can reveal their identity if not normal. Groth16 ZK-SNARK is the most common ZK-SNARK used in most applications. Setting up Tornado Cash involves defining terms such as Pederson hash function and Merkel tree, and initializing Memc with all leaves being zero values later zero values are gradually added.

Introduction to Tornado Cash

In this section, the speaker introduces the concept of Tornado Cash and explains how it works.

How Tornado Cash Works

  • Users pick a nullifier and randomness randomly.
  • The user proves that they know K and R such that H(K,R,L,O) is the hash of K, O is the opening of hash 2 of KNR at position L to R.
  • The user reveals H as a public parameter.
  • The user shows that K and R are inside their tree at root r.

Merkle Tree

  • A Merkle tree is used to store values in Tornado Cache.
  • The Merkel tree root by itself doesn't really tell you what's in the tree.

ZK Snark from Grot16 Proving Verifying Key Pair for S

  • D is equal to DP and DV be the ZK snark from grot16 proving verifying key pair for S created using some trusted setup procedure.

Ethereum Address of Coin Recipient and Fee

  • Ethereum address of coin recipient (A), and fee (F), are included in zero-knowledge proof but not used on the right-hand side.

Introduction to Zero Knowledge Proofs

In this section, the speaker introduces the concept of zero knowledge proofs and how they can be used to prevent front-running attacks.

How Zero Knowledge Proofs Prevent Front-Running

  • A coin cannot be front-run from an attacker if the withdrawing address is included in the zero knowledge proof.
  • Including the receiving address inside the zero knowledge proof prevents front-running.
  • Zero knowledge proofs can be useful in preventing front-running when withdrawing transactions.

MEV and Minor Extractable Value

This section explains what MEV (Minor Extractable Value) means and how it relates to blockchain transactions.

MEV Explained

  • MEV stands for Minor Extractable Value or Maximum Extractable Value. It refers to validators moving transactions around for profit.
  • Ethereum doesn't have minors anymore because it's not proof of work, but people still use the term loosely to refer to bots that benefit from having their transactions placed at a specific index in black arbitrage liquidation, front-run, sandwich, etc.

Withdrawing Transactions Anonymously

This section explains how anonymity is maintained when withdrawing transactions using Tornado Cash.

Withdrawing Transactions Anonymously

  • To maintain anonymity when withdrawing, deposit money with a fixed amount of ether and withdraw one ether at a time.
  • Depositing 10 ether into a tree where everyone else is also depositing 10 ether will help maintain anonymity when withdrawing large amounts of money.

Trusted Setup Procedure

This section explains the concept of a trusted setup procedure and how it relates to zero knowledge proofs.

Trusted Setup Procedure

  • DP and DV are public parameters created from a trusted setup procedure.
  • The term "key pair" is not accurate for DP and DV since they are public parameters, not secret or private keys.

MEV Bots

This section explains what MEV bots are and how they benefit from having their transactions placed at specific indexes in blockchain transactions.

MEV Bots Explained

  • MEV bots refer to bots that benefit from having their transactions placed at specific indexes in blockchain transactions.

Anonymity in Tornado Cash

In this section, the speaker discusses how to maintain anonymity while using Tornado Cash.

Maintaining Anonymity

  • To maintain anonymity, wait until other people are using Tornado Cash before making a transaction. This makes it less clear who is who.
  • The larger pools in Tornado Cash are likely used by only a few people, so they may not be as anonymous.

Trusted Setup and ZK Snarks

  • Groth16 requires a trusted setup that needs to be done before defining proof of values and outputting a proof.
  • The math behind Groth16 is not necessary to understand for building zero-knowledge proof applications but understanding why they're useful is important.

Storing Recent Root Values

  • A smart contract stores the last 100 root values in the history array for the latest Merkel tree T and also stores the values of nodes on the path from the last added leaf to the root that are necessary to compute the next root. This helps generate proofs when someone goes to withdraw.

Using Tornado Cash on L2

  • Using Tornado Cash on L2 can help with anonymity and efficiency as long as there are enough users. However, if there's only one main tornado cash everyone uses on Ethereum and then multiple L2s make their own versions of tornado cash, each L2 may not have as many users which could impact privacy.

Tornado Cash Overview

In this section, the speaker explains how Tornado Cash works and how it prevents double spending.

How Tornado Cash Works

  • When someone pays into Tornado Cash, the tree is updated.
  • The verification process checks that the submitted public values match the electric proof P.
  • If verification succeeds, the contractor releases minus f e to address a and Phi f e to really error address t.
  • To prevent double spending, the nullifier hash from the proof must not have appeared before.

Bridging Deposits to Anonymous Chains

  • If deposits were bridged to another anonymous chain or Monero and back, it would not be anonymous on Tornado if there was only one depository.
  • Timing attacks are a problem with relayers like Tor Browser because transactions can be linked based on timing.
  • Bouncing something through a bridge and back within the same transaction would not add privacy.

Summary of Tornado Cash

  • Deposits can be made into Tornado Cash and withdrawn later using a Merkle tree data structure.
  • A proof is required for withdrawal from the Merkle tree.
  • There's nothing too specific about each hash function used in Tornado Cash.

Understanding Tornado Cash

In this section, the speaker explains how Tornado Cash works and clarifies some of the terminology used in relation to it.

Nodes and Coins

  • Each coin is a deposit of one ether.
  • The smart contract and each of the Tornado Cash users are important, not individual nodes.
  • The consensus algorithm and different nodes are not too important at this level of abstraction.

On-chain Identity Verification

  • EK snarks can be used for on-chain identity verification.
  • Zero knowledge identity and CK identity can prove certain facts about yourself without revealing too much information.
  • It's unclear whether Tornado Cash has any direct identity implications.

Merkle Trees

  • Each tree node is a coin in Tornado Cash.
  • The nodes in the Merkle tree are each like one saved coin.
  • A transaction follows a Merkle tree by remembering your path to the top of the tree to prove that your leaf node is a member of this tree.

Combining with an Integrated DEX

  • There is no immediate benefit to combining Tornado Cash with an integrated DEX.
  • It's better to let each thing do its own thing properly and use them separately.

Size Constraints

  • The size of the Merkle tree is fixed at inception by the number of leaves.
  • The height of 20 means we can include 2^20 transactions because it's a binary tree.
  • Only a million people would be able to use Tornado Cash at once due to space constraints on Ethereum.

Anonymity

  • Transactions come from Ethereum nodes, so you have to insert your transaction into the mempool.
  • At that time, they could log where that transaction is coming from.
  • Use Tor Browser or other methods for anonymity when depositing native cash transactions.

Matching Withdrawals with Deposits

  • The original deposit generates two random numbers K and R.
  • Tornado Cash is only given the hash of K and R, which is used to compute C.
  • There is no direct way to match withdrawals with deposits.

Tornado Cash and QAP Reduction

In this section, the speaker explains how Tornado Cash works and how it uses zero-knowledge proofs to maintain privacy. They also briefly introduce QAP reduction and explain how it is used in Graph 16 protocol.

Tornado Cash

  • Tornado Cash uses zero-knowledge proofs to maintain privacy.
  • The smart contract has a balance of ether from different people, but when one ether is withdrawn, you don't know which person it came from.
  • Tornado Cash is a famous example of a zero-knowledge proof application.

QAP Reduction

  • Graph 16 protocol is the most used case in Arc out there. Zcash used it, and many people have used the tornado cache who used it.
  • The qap reduction starts with magic polynomials that encode the problem.
  • Special polynomials are built, multiplied, combined, and added to generate a big polynomial.
  • A times B equals C plus H times E.

Checking on Chat

In this section, the speaker quickly checks on chat.

Checking on Chat

  • No significant content in this section.

Smart Contract Tornado Cash

In this section, the speaker discusses the Smart Contract Tornado Cash and its deletion from GitHub.

Smart Contract Tornado Cash

  • The Smart Contract Tornado Cash has been deleted from GitHub.
  • The speaker suggests discussing it in another class.
  • No further discussion of the topic is planned for today's class.

QAP Stands for Quadratic Arithmetic Programs Zero to Hero

In this section, the speaker introduces QAP and explains how it relates to quadratic arithmetic programs.

QAP Stands for Quadratic Arithmetic Programs Zero to Hero

  • QAP stands for Quadratic Arithmetic Programs.
  • The goal is to get from computation into QAP with all polynomials and create a proof.
  • The process involves breaking down each step slowly and translating from each layer to the next.
  • Limited operations are available: add, subtract, multiply, divide, and constant power explanation.

Computing a Function

In this section, the speaker explains how to compute a function using limited operations.

Computing a Function

  • To compute a function with limited operations:
  • Encode it in a format that's nice
  • Prove some facts about it
  • Break down each step one at a time
  • Work with limited operations (add, subtract, multiply, divide)

Flattening Steps One at a Time

In this section, the speaker breaks down flattening steps one at a time.

Flattening Steps One at a Time

  • Flattening involves breaking down each step one at a time.
  • Simple variables are introduced to slow down the process.
  • Gate to R1CS involves three vectors: A, B, and C.
  • The solution vector s satisfies the equation s dot a times s dot b minus s dot c is equal to zero.

R1CS and QAP

In this section, the speaker explains how to convert a program into polynomials using R1CS (Rank-1 Constraint System) and then use those polynomials in a Quadratic Arithmetic Program (QAP) to create a zero-knowledge proof.

Converting Program to Polynomials

  • Create arrays with columns for one, X, out, symbol one, Y, and symbol two.
  • Use matrices to represent computations step by step.
  • Convert matrices into polynomials.
  • Mix polynomials together and prove facts about them.

R1CS and QAP

  • R1CS is commonly used in converting programs into polynomials.
  • QAP uses the polynomials created from R1CS to create a zero-knowledge proof.
  • Read through articles for more detailed explanations on how the coefficients are formed in creating the polynomial.
  • The speaker will discuss R1CS further on Thursday's session.