This article is a personal proof of zero knowledge, mainly the notes of zkSNARKs, the writing is a little messy, the content is long, recording a lot of questions and thoughts. TornadoCash will be compared with ETH and BTC’s semi-centralised namesakes, which are TornadoCash and CoinJoin.
Asymmetric Encryption: Naive “Zero-knowledge Proof”
What if I want to prove to you that I have a “Secret” but I don’t want to tell you directly?
Asymmetric cryptography can publicly prove that I have a private key without disclosing the private key, because only the private key can generate ciphertext, which can only be unlocked by the corresponding public key.
For example, in an encrypted signed email, I also need to tell the other party my public key fingerprint. But I don’t even want that presupposition, and the naive zero-knowledge proof of a public-private key proves nothing but the fact that I have a public key corresponding to my private key.
ZkSNARKs: I understand
What do you mean, “I have a secret”? What is the definition of secret in the context of our zero-knowledge proof? A secret is a solution to a “problem” that is described by a program consisting of a series of assertions. We take the secret answer back to the original problem program, all the assertions are true, and the program passes. So we can determine in plain text that our secret is correct, that it is the “secret” that the verifier wants.
Now, we don’t want to use plaintext authentication, and we certainly don’t want the verifier to know the secret plaintext. There are a lot of popular science articles for zero knowledge proof in the metaphor, such as what “can’t distinguish the virtual world of + time back machine”, “, a cave, there is a loop the loop in the middle there is a door “, I think these metaphors are excessively abstract (simulator is correct metaphor but too abstract), and there is no close to the mathematical characteristics of zero knowledge proof.
My favorite analogy is the sudoku verifier analogy:
A sudoku murder
Xiao Ming does sudoku. Xiao Ming does not want to tell Xiao Hong the answer directly. Instead, he designs a set of determination procedures based on the nature of sudoku: every row, column and nine squares must contain 1-9, or the sum of elements must be equal to 45. The reduce process completely eliminates the possibility of restoring the original problem solution. Then the two run the verification process interactively, and make it into an automated verification machine, which requires input of the original problem solution and then outputs a paper bag for external verification.
Although this program is not the real zero knowledge proof program, but it has given us the general process has been said. The following content is for personal understanding, referring to a series of articles:
zhuanlan.zhihu.com/p/99260386
And Vitalik’s article:
medium.com/@VitalikBut…
But I really think they are still very difficult to understand.
From programmatic circuits (R1CS) to polynomials (QAP)
One question: Is the program we want to verify Turing-complete?
Of course not! Because we can never verify an infinite number of constraint assertions. So the program must eventually stop and return ACC, or assert not to return REJ.
And we don’t need to, because the secret solution can be designed to be of fixed length, so the number of validation operations that can be performed on it should be limited.
zhuanlan.zhihu.com/p/102090192
Each program instruction can be expressed as the left operand operator and the right operand = output. There are many different variables that can occur at the three positions of the left-hand and right-hand operand outputs. We use variable polynomials (which are either positive or 0 when x is a natural number) to control whether a variable appears at a certain point in the program.
The process of assigning a value to a variable (entering information about the secret solution) is to multiply the polynomial of the variable by the global coefficient so that it is the desired value where it should appear and 0 where it does not.
Add up all the assigned variable polynomials to get L, R, and O.
L x R – O = h x t
Why can I just add and multiply? Because we want to make sure that the program is consistent, we multiply; And since variable polynomials set all irrelevant variables to 0, the product of the values of L and R at the point x= a natural number is the corresponding program instruction.
T polynomial means that this polynomial program has n roots from x from 1 to n, which means that all n program constraints are true.
What’s the POINT?
The sole purpose of the system is:
Verifier can determine whether the polynomial LR-O assigned by Prover is indeed in 1, 2, 3… They all have roots at D. That is, whether LR -o = ht holds for any point x = s, where t(x) = (x-1)(x-2)…. (x-d), h is (LR-o)/t
Process:
Prover: I have the solution to the circuit problem you provided.
Verifier: I have a complete Setup process that can be proved to me using the values provided.
Prover: I use the circuit you provide (as well as the corresponding has entered to point s value of the variable polynomial) and can only be done on their overall multiplied by the coefficient of the assignment (Prover can’t change a variable specific polynomial), and I can only use them to corresponding to generate my L, R, O, cannot exchange or replacement, because I don’t know the alpha, Failed to generate alpha relation; You also provide encrypted powers of some random number s (taking random points) s1, S2… Sd, which allows me to compute h of s based on my h of x.
Key content: Prover To make it easier for you to verify that a variable I used in the proof is consistent with your plaintext, I will divide LRO into half you and half ME and provide you with the encrypted values of L, R, O of my half input values, and the encrypted values of the full input h, as well as the corresponding alpha transformation version, and the encrypted values of a beta-gamma checksum gZ. You can generate your L, R, and O for your half of the input values and verify that the sum L, R, and O, plus the calculated h, satisfies the relation L x R – O = HT at some random point that no one knows. P does have 1, 2, 3… D the roots, which means that the assignment input of the polynomial THAT I have, does allow all the assertions in your circuit to pass, and the input values that belong to your half are really the plaintext values that you know, and the program accepts my input!
Prover: In addition, due to your constraints, I cannot swap variable polynomials or change their combination or order, nor assign two values to the same variable that does not appear in the same position (L, R, O), because I do not know the beta that locks L, R, and O respectively, so I cannot generate beta relations. Also, because of the Gamma relationship, the proof process has been eliminated malleability, and I can’t exploit the known alpha beta encryption values to generate alpha beta relationships.
Prover: I’m going to introduce multiple random numbers, which doesn’t break all the mathematical relationships above, although you can still verify, but you can’t deduce any of my original assignments from the relationship between the cryptography values I gave you, because they’re just like a few random numbers.
Note: An input (L, R, O, h) that can go to the end to verify the equality must have been subjected to polynomial constraints, non-commutative constraints, consistency constraints, etc. At this point, L, R, and O must be assigned by the input of the circuit generated in Setup (which has taken a random point S). There is a very important sentence in the whole process of constraint: Without knowing the plain text and only the ciphertext, you Prover cannot generate constraint relations, but can only inherit this relationship from somewhere, and the other Verifier can use this constraint relationship to force you to operate or obey a certain rule. If your input does not guarantee or meet this constraint relationship, I know you are trying to cheat. Here, the encrypted value gt(s) of t(s) can also be regarded as a constraint relation! Because t(x) is open plaintext, but if you plug in SK it becomes GT (s), the fundamental reason is that S is unknown. It is similar to alpha and beta gamma, but the underlying nature of this relation lies in the inherent property of LR-O, namely the ability to factor t(x), and has nothing to do with the h produced by computation. The random number S is the sampling point generated during the Setup phase, after which S is unknown and t(s) always appears in ciphertext. Prover cannot create a T (s) relation out of thin air (and can not pass other constraints), nor can it create its inverse relation (can not generate an illegal LR-O that can pass the previous constraint detection, and then force a false H (s) to fool the calculation check). Prover can only first ensure that rxlx-ox = h(x) t(x), for every x (legal); Then, the t(s) relation (from general to special) on the paired operation is obtained by substituting the encrypted value of the power of S and the variable polynomial containing S respectively. Thus, a fixed but unknown s behaves as if it were picked randomly every time. Therefore, by sampling a random point S unknown to Prover, rxlx-ox = h(x) t(x) can be guaranteed with great probability for every x!
Anonymous technology: CoinJoin, Zerolink protocol (blind signature)
Wasabi Wallet’s CoinJoin technology uses Zerolink protocol to sever the relationship between input and output transactions, completely removing trust but remaining semi-centralized due to the scheduling server. The core technology is blind signature and blind transform (a homomorphic encryption, allowing the signature in ciphertext, the inverse blind transform signature is still valid after decryption). This model of anonymised technology is what I call the “ride-sharing model”. Process:
- Input registration stage: the user registers a deposit with the server with tor identity Alice, including the UTXO to be input, the input proof generated with the unlock private key signature of these UTXOs, the plaintext change address, and the blind change of the withdrawal address.
- The server checks a series of inputs, then signs the blind withdrawal address, returns the signature to the user, and gives the user a uniqueID.
- The output registration phase: the user changes into a new TOR identity Bob and gives the server the plaintext withdrawal address and decrypted blind signature.
- Signature stage: the user changes tor identity to Zlice, the server generates a multi-signature transaction, he confirms the integrity of the transaction input, and his input and output are included, and then signs the transaction. Send the above uniqueID, transaction signature, and index of the UXTO entered back to the server.
- Broadcast phase: The transaction is signed by all participants and the server starts broadcasting the transaction to the chain.
Tornado.Cash principle source code interpretation
Tornado Cash’s business logic is as follows:
deposit
The local JS generates random numbers secret and Nullifier, and then generates a deposit object containing preimage, Secret, Nullifier, nullifierHash, and Commitment. Call the main contract deposit function, submit the deposit object and send the corresponding number of ETH; The user is returned with a Note for withdrawal. In Tornado. Sol, check whether commitment has been submitted. If not, insert Merkle Tree to update Root. A Deposit event is generated for external JS to access. MerkleTreeWithHistory. Sol: The Merkle Tree contract on the chain only maintains the latest Root, Root history (length: 100), The subscript index of the current Commitment, the FilledSubtree used to update the Merkle Root layers (the contents of the sibling nodes of each node on the path from Leaf to Root), which means that the Merkle Tree on the chain only has a series of increments. Full information depends on JS to access the history of blockchain events to build a full Merkle Tree.
withdrawals
The user only has a Note, what information is in the Note? In fact, only Preimage (Nullifier + Secret) is really useful for us to withdraw money. The zero-knowledge proof process proves that the user knows a Commitment already stored on the blockchain and knows its corresponding Preimage, its Hash = Commitment. However, I can’t directly tell the contract that my Commitment is no. 1 on the blockchain! It’s like identifying yourself. Anonymity is gone. So what to do? We needed to find a way to prove with zero-knowledge proof that convinced the verifier contract that we had a Commitment committed to the main contract that was already on-chain.
zhuanlan.zhihu.com/p/40142647
This is where the purpose of “quick check whether part of the data is in the overall data” is used. Part of the data is our Commitment, and the overall data is all the Commitment on the chain. The latest 100 Root (in case of network delay) maintained by MerkleTreeWithCommitment contract (the parent of the main contract) determines what is the “official and correct Root of the whole data” at the contract level, and the user has to build a complete MerkleTree locally. Figuring out a Root, passing Root checks at the contract level, and generating Merkle Proof (the path, and the Hash of the subtree on the other side of each completed path for each parent) is Proof that my Commitment is actually on the chain.
Nullifier Secret Root and the above Merkle Proof input circuit will generate SnarkProof, and the user or Relayer will initiate a transaction to pay the Gas fee, call the master and withdraw functions, and attach the Proof data.
The master contract ensures that Nullifier Hash is never used or spent, and that the Root provided by the user is actually the Root that they know represents the complete record. The host enters the Nullifier Hash and Root, and the user enters the Proof Recipient Fee, and enters the Verifier contract. The contract can prove the following based on input Proof:
- Merkle Proof did provide a path between user-provided Nullifier and Secret generated Commitment and user-provided Root.
- The Nullifier and Secret provided by the user actually correspond to the Commitment Hash (the user is the owner of the Commitment)
Also because of zero-knowledge Proof, the contract does not know specifically about user-submitted Merkle Proof and Secret. 3. During the generation of Proof, Fee and Recipientare locked in the form of square constraint. If an attacker hijces the Proof, tells the contract to give himself money, and tries to squeeze out other transactions with a high Fee, the Proof process will not pass.
The difference between the two
You can see the difference.
- CoinJoin is a “group carpool mode”. The mixed currency process is centered on the dispatch of the server, with a “group” as the basic unit. When the car is full, the server starts broadcasting transactions. Tornado Cash as “listed claim model”, the user submits input into block record a commitment on the chain, the user through the way of zero knowledge proof prove effective in chain, and know the cipher text on the listing, but he doesn’t need to tell the details of which contract, there is no this “group” grid.
- The blind signature technique used by CoinJoin requires the server to hold the private key and actively sign the blind, which is not possible with smart contracts on the blockchain. The CoinJoin architecture always requires a server to act as the host for each group session and then broadcast the transaction to the chain; Tornado Cash Smart contract does not need a server, but only requires blockchain database, smart contract and DApp to interact with the contract. All keys and Secret are only in the hands of users.
** Note: ** Recently Wasabi Wallet urgently fixed the DoS vulnerability, which allows an attacker to construct malicious transactions at no cost to crack the blind signature private key held by the scheduling server and generate the plaintext address after the signature; Other group participants paid Input, but were impostor, will refuse to sign the transaction, resulting in group carpool failure. The root cause of the vulnerability is the reuse of a secret Nonce that should be strictly one secret at a time.
- Obviously, Tornado Cash is more convenient and faster than CoinJoin in obtaining anonymity, because CoinJoin can only obtain a small anonymous set for each group, and mixed currency only occurs when group transactions take place. But Tornado Cash happens all the time: there is no certainty at all when a user will withdraw his or her money. An observer can only know that a depositor must withdraw some time after the deposit, but for each withdrawal, you don’t know which deposit it corresponds to before. If deposits and withdrawals are active and average in the contract, the anonymous set may remain at a high level.
Note: Anonymous sets can be harmed in the short term by users who simply withdraw them. Consider a situation like this: In a contract with a denomination of 1 ETH, users withdraw faster than they deposit. Finally, there is only 1 ETH left in the contract. At this point, there are 5000 deposits in the past. But when he takes it out, ETH in the contract goes to zero, so does the anonymous set, because any subsequent withdrawals cannot correspond to deposits prior to that point in time; Even if some users continue to deposit, the probability of a withdrawal corresponding to deposits before this point in time will be extremely low, equal to the effect of the accumulated anonymous set will be greatly weakened. 4. All deposit commitments in Tornado Cash occupy space on the chain, and due to the merkle Tree depth limit of 20, each contract can only accommodate 1 million deposits, and the contract must be replaced after reaching the limit, and the original contract will be invalid. CoinJoin doesn’t have this problem.
The problem summary
1. How does Tornado Cash prevent replay, Forerun and double flower?
All the variables once the input circuit generates Proof you can’t work backwards. But zero-knowledge Proof internal variables can lock external variables to make them consistent, and external variables can lock their internal variables to make them consistent with external variables.
Zhuanlan.zhihu.com/p/103530121 “public input and 1” part
This essentially takes some variables out of the hands of the Prover and into the hands of the verifier while maintaining equality. Thus, valid calculation checks remain valid only if the same values are used in the prover and verifier inputs.
require(verifier.verifyProof(_proof, [uint256(_root), uint256(_nullifierHash), uint256(_recipient), uint256(_relayer), _fee, _refund]), “Invalid withdraw proof”);
Zero-knowledge Proof actually bundles the following information: Root generated on the user side, Nullifier Hash provided by the user, user-selected payee address, user-selected Relayer, user-selected tip fee for Relayer, (If you want to withdraw ERC20 Token, and refund for ETH change, you can use it to pay Gas in the future. Thus eliminating the need for Relayer). The contract ensures that the Nullifier Hash has not been used and that Root is a self-generated Root. The zero-knowledge verification process also ensures that the Nullifier Hash submitted by the user corresponds to the Nullifier text input when Proof is generated. You cannot submit a fake Nullifier at the contract layer, because this will make you fail zero-knowledge verification. This zero-knowledge Proof also ensures that the cleartext received by the contract (receiver, tip, Relayer address, Refund change) has not been tampered with. Because this information is bound to Proof during Proof generation (internal variables lock external variables), if someone tampers with this content, the validation will fail. Relayer can’t charge high tips, but has to turn down requests for lower tips.
Why do JS, Circom and Solidity each have an implementation for Merkle Tree?
JS requires Merkle Tree to calculate the local Root; Circom needs Merkle Tree for zero-knowledge Proof and Merkle Proof to prove that there is indeed a path from Leaf to root. The Merkle Tree maintained by Solidity only maintains the necessary incremental information to provide “what is the official full Root” and update Root.
C: Why do JS, Circom, Solidity each have a zkSNARKs and circuit implementation?
JS: You need to input the user into the input circuit to generate Proof; Circom is the source file for the circuit itself, generating the JS version of the circuit and a Solidity contract version verification code; The Solidity contract version of the Verifier, generated from the Circom source file, provides on-chain Proof that Proof actually works and is responsible for returning the results of the master pact.
Refund for money exchange
This mechanic has never been officially mentioned in user-facing articles. Withdrawals can be made either by the user himself or by trusting Relayer with a tip. Withdrawal means initiating a transaction and using ETH to pay for Gas. If a user pays with a non-anonymous ETH (if you buy privately from someone else, it also reduces anonymity), it reduces their anonymity. If you are accessing ETH, then once you use a Relayer you get an anonymous ETH and you don’t need a Relayer anymore. But what if you are accessing ERC20 Token and entrust Relayer with the Token to pay the tip (reimburse Relayer for the Gas spent), this process does not give you ETH, and the user still cannot send the withdrawal transaction independently, and always has to rely on Relayer? There is a Refund mechanism for the withdrawal of ERC20 in Tornado Cash main contract, that is, Relayer pays Refund to the contract, and then the contract gives Refund to the receiving address, so that the user can get a part of ETH change to pay for future Gas transactions. Of course, the code is the rule, and Relayer needs to figure out whether sending a transaction is a loss or not. If the tip paid by the user is not enough to cover Refund, Gas and its own fees, Relayer can choose not to do so.
Circom personal understanding:
The Private Signal and Public Signal are not object – oriented visibility. The Private Signal is an assignment given by only Prover, and the Public Signal is an assignment given by Verifier. The term “Signal is considered Private by default” also means that all Intermediate signals generated in an operation are signals that only Prover (in Witness) gives. If the Main function (component) is specified, all input/output signals specified as Private are Private signals. The Public keyword is rarely used. An Witness includes all signals. However, when Witness was used, together with encryption Proving Key in Setup, a zero-knowledge Proof (including only the PRIVATE signal L, R, O and h generated with all variables) was generated, and those Public signals were given separately in clear text. Withdraw. Circom
signal input recipient; //public signal recipientSquare; //intermediate, "private" recipientSquare <== recipient * recipient; //prevent optimizer removingCopy the code, which ensures that The Recipient and Proof are bound, and the verification contract verifies this. This code itself is an assignment + constraint assertion and should not be viewed in a conventional way. In fact, it is not surprising that as long as there is a constraint in the circuit, no matter what form it is, it can verify internal and external consistency. Prover could of course assign a random value to this statement, but the constraints and the Public Signal attribute give outsiders a chance to verify that the plaintext they get is the same as the one Prover used to generate Proof.