TLDR:
- Bitcoin transactions are recorded in a publicly transparent ledger, making privacy impossible. ZeroCash, a new privacy preserving digital currency leveraging zk-SNARKs, is proposed as a solution.
Citation
- Sasson, Eli Ben, et al. “Zerocash: Decentralized anonymous payments from bitcoin.” 2014 IEEE Symposium on Security and Privacy. IEEE, 2014.
Link
Core Research Question
- Can we form true anonymous decentralized payment schemes with competitive verification speed and transaction size?
Background
-
Bitcoin fails to offer privacy provided by traditional payment systems, as the transaction sender, receiver, and amount are publicly visible and easily de-anonymize.
-
Mix can obfuscate transactions by allowing users to entrust a set of coins to a pool and then retrieve different coins after some time interval. This is usually operated centrally.
-
Zerocoin is a decentralized mix for Bitcoin that uses zero-knowledge proofs to prevent transaction graph analyses.
-
Zero knowledge proof: a cryptography protocol where one party can prove to the other that they know a value x without revealing any other information.
-
zk-SNARK is a non-interactive zero-knowledge proof of knowledge that is succinct. Succinct means proofs are very short and easy to verify.
- Steps
- Setup: A trusted party creates 2 public keys: (1) proving key pk and (2) verification key vk.
- The proving key pk enables anyone to produce a fixed size proof π that x ∈ L
- Anyone can use the verification key vk to verify the proof π
- Steps
-
Commitment scheme is defined as follows:
- For a random r and message m, a commitment c = f(r, m), a function of r and m.
- c can be computed given r and m
- Given c, it is impossible to reverse compute m.
Summary
- Bitcoin can be easily de-anonymized, yet alternative solutions such as mixers and Zerocoin have multiple drawbacks.
- Mixer’s drawbacks: (1) not having enough coins to mix, (2) usually centralized, blackbox operations, (3) the mixer knows the sender’s identity, (4) users need extra effort to use the mixer.
- Zerocoin’s drawbacks: (1) the proof is inefficient, it’s 45+ kB in size and requires 450 ms to verify, (2) has limited functionality that can only “wash” coins periodically but not for payments in exact values and specific receivers, (3) it can only unlink a payment transaction from its origin address but cannot hide the value or metadata transferred along.
- Zk-snark can avoid those issues
- It is similar to the “arithmetic circuit satisfiability problem”, which means: “can you find the input that satisfies the arithmetic logic circuit?”
- For example, for (¬a ∨ ¬b ∨ c)∧(a ∨ ¬c)=true, can you find a, b, c?
- Given the output, it’s an NP-hard problem to solve the input.
- Three main functions
- KeyGen(lambda, C) → (pk, vk):
- lambda: security parameter
- C: arithmetic circuit
- pk: proving key
- vk: verification key
- Prove(pk, x, a) → π
- pk: proving key
- (x, a): any pair that satisfies circuit(x, a) = 0
- π: the proof
- Verify(vk, x, π) → b
- vk: verification key
- x: the input to be checked
- b: = 1 if there exists a such that circuit(x, a) = 0
- KeyGen(lambda, C) → (pk, vk):
- The properties
- Completeness
- Prover can “convince” the verifier that x satisfies certain conditions Prover does not have to know exactly what x is.
- Succinctness
- The proof has size < some function of lamba & verify time < some function of lambda and the input x
- Proof of knowledge
- If the verifier accepts a proof, the prover must know what a is
- Perfect zero knowledge
- The proof does not reveal any additional information other than convincing the verifier
- Completeness
- It is similar to the “arithmetic circuit satisfiability problem”, which means: “can you find the input that satisfies the arithmetic logic circuit?”
- The authors describe the functions of a decentralized payment scheme
- Setup
- (lambda) → (public params)
- only done once by a trusted party
- lambda: security parameter
- public params: published for everyone
- (lambda) → (public params)
- Create address
- (public params) → (private key, public key)
- Mint coin
- (public params, coin value, address to sent) → (coin c, mint tnx)
- Pour coin
- (public params, old coin, old secret key, the way to authenticate this, new public key) → (new coin c1’ c2’, pour tnx)
- transfers value from input coins into new output coins
- Verify transaction
- (public params, mint/pour tnx, current ledger) → (if thnx is valid)
- Receive coin
- (receiving address, ledger) → (unspent coins)
- Setup
- Zerocash properties
- Hash function: SHA256
- Level of security: 128 bits
- Max coin value: 2^64
- Signature scheme: ECDSA
- Block verification time: ~75 seconds
- Encryption scheme: key-private Elliptic-Curve Integrated Encryption Scheme
- Compatibility: Zerocash can be deployed atop any ledger (also any centralized one) or just standalone as an independent altcoin
- Time complexity: polylogarithmic, and constant in the number of coins
- They use a commitment scheme (background provided above) to hide the send address and amount information. More on how this works can be found in the last section “Further detail about the Algorithm”.
Method
- Build on top of existing implementations of zk-SNARK
- Modify bitcoind to generate blocks stochastically and run private testnets
- Simulate the network: run 200 Amazon EC2 general-purpose m1.medium instances
- On each instance, deploy 5 instances of modified bitcoind.
- Measure with 1000 nodes (⅓ reachable nodes in Bitcoin)
- Each node has ~32 randomly selected peers
Results
- zk-SNARK prover running time: few minutes and verifier running time: few milliseconds
- Performance of Zerocash overview
Discussion & Key Takeaways
- In summary, Zerocash uses (1) commitment scheme to hide user identities, transaction amounts, account balances, and to make broadcasted transactions irreversible, and (2) uses zk-SNARKs to generate verifiable proofs of transaction validity without revealing the underlying information
- Generating proofs takes few minutes while verification takes only few milliseconds
- Zerocash can be built on top of existing blockchains as an extra layer of security or be a standalone coin
- Currently Zerocash has almost all functionality that Bitcoin has, except a scripting language. However, it has a larger block size than Bitcoin.
- Comparison between Bitcoin and Zerocash:
- Transaction size: 250 bytes / 1 KB
- Block time: 10 minutes / 1.25 minutes (history block time chart)
Implications & Follow-ups
- How do you include scripting languages in Zerocash with fast verification times?
- Though the verification time is fast, it is relatively slow to generate proofs.
- Zerocash requires a trusted party to do the initial setup, this centrality can be solved by letting multiple parties to setup together
Applicability
- There are two ways to use Zerocash:
- Use it as an independent payment scheme modified from Bitcoin.
- It can be used as a cryptocurrency that can hide payment information.
- Advantages:
- The payment scheme has built-in anonymity and the block time is 8 times faster than Bitcoin.
- Disadvantages:
- All transactions incur the cost of generating a zk-SNARK proof
- The scripting feature of Bitcoin is lost
- Bitcoin’s ability to spend unconfirmed transactions is lost
- Use it as an extension of Bitcoin with a new transaction type called Zerocash transactions.
- It can be used as a parallel ledger that exists alongside Bitcoin and the currency can be converted freely between the two.
- Advantages:
- The functionalities of Bitcoin are unaltered, such as scripting
- Disadvantages:
- The performance of the network will not be as good as using the independent Zerocash
- Use it as an independent payment scheme modified from Bitcoin.
- To ensure complete anonymity, users need to use anonymity networks like Tor to hide network traffic data. Because Zerocash only anonymizes the transaction ledger but not the network traffic.
- zk-SNARK can be applied in many different ways, such as: a user can prove that he paid his taxes on all transactions without revealing information.
Further detail about the Algorithm
- The simplest way to hide the payment origin with proof time complexity = log(number of coins):
- Mint new coin:
- The user samples a random serial number sn as the ID of coin and generate a random number r
- The user computes a coin commitment cm = f(sn, r)
- A mint transaction that contains cm is sent to the ledger after the user has paid 1 BTC to an escrow pool (like a certificate of deposit)
- All cm on the ledger form a CMList
- Only cm is publicly known, not sn and r.
- Spend the coin:
- The user submits a send transaction that contains (1) sn, the ID of the coin, and (2) a zk-SNARK proof π, proving that he or she knows r.
- proof π: I know r such that cm = f(sn, r) is in the CMList.
- If sn is not already on the ledger, the user can send the coin.
- The sent transaction is confirmed on the ledger that reveals sn and π
- Now sn is revealed, but r is not.
- Finding which commitment cm is associated with this send transaction is impossible
- The user submits a send transaction that contains (1) sn, the ID of the coin, and (2) a zk-SNARK proof π, proving that he or she knows r.
- Now we have 2 problems:
- time complexity of this proof verification algorithm grows linearly with CMList
- Spent coin’s cm cannot be dropped from CMList for anonymity
- The authors propose to use the data structure CRH-based Merkle tree for CMList
- It is known that time complexity of updating the root hash when inserting new nodes = tree depth = log(CMList size)
- Mint new coin:
- However, the above scheme only works for the same token minter and sender, we need modification to the original algorithm to allow sending from A to B:
- Reason: The serial number sn is already known to A, it’s hard for B to ensure that A does not spend before him using sn
- Solution: use pseudorandom functions to generate sn based on a seed x
- Mint new token:
- The user generates an address key pair (public key, private key). Public key = function of private key(0)
- The user selects a seed x and generate sn = function of private key(x)
- cm and sn are generated like the following diagram (c and d)
- The new cm is added to the Merkle tree
- Since sn (the coin’s ID) is calculated from the private key, only the owner of the coin can track it. Also, the coin can only be sent from someone with the private key
- Full algorithm:
- Send V amount of coin A to two new addresses and two new coin B and C (each with amount v1 and v2, where v1 + v2 = V):
- sent transaction is:
- No sent value is revealed
- No original cm is revealed
- No the 2 receiving addresses are revealed
- sent transaction is: