TLDR:
 Bitcoin transactions are recorded in a publicly transparent ledger, making privacy impossible. ZeroCash, a new privacy preserving digital currency leveraging zkSNARKs, 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 deanonymize.

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 zeroknowledge 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.

zkSNARK is a noninteractive zeroknowledge 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 deanonymized, 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.
 Zksnark 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 NPhard 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: keyprivate EllipticCurve 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 zkSNARK
 Modify bitcoind to generate blocks stochastically and run private testnets
 Simulate the network: run 200 Amazon EC2 generalpurpose 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
 zkSNARK 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 zkSNARKs 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 & Followups
 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 builtin anonymity and the block time is 8 times faster than Bitcoin.
 Disadvantages:
 All transactions incur the cost of generating a zkSNARK 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.
 zkSNARK 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 zkSNARK 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 zkSNARK 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 CRHbased 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: