Research Summary: Zerocash: Decentralized Anonymous Payments from Bitcoin

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
      1. Setup: A trusted party creates 2 public keys: (1) proving key pk and (2) verification key vk.
      2. The proving key pk enables anyone to produce a fixed size proof π that x ∈ L
      3. Anyone can use the verification key vk to verify the proof π
  • 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
    • 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
  • 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
    • 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)
  • 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:

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
  • 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
    • 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)
  • 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
7 Likes

Given the shenanigans we’re seeing in the American stock market, which come from information asymmetry and narratives spun in that vacuum, do we want to have decentralized anonymous transactions? Having a completely transparent ledger could be Bitcoin’s biggest asset.

2 Likes

There are payments for various use cases that require privacy such as insurance and payments that are commercial confidential. One should be able to choose freely which kind of privacy he/she wants for different scenarios:)

1 Like

@tina1998612 After reading through this, and knowing a bit about zk-SNARKs, I was wondering what your thoughts are about the PIVX Shield protocol? I personally don’t know much about it but from my understanding, it is the first crypto utilizing PoS to implement zk-SNARKS on their mainnet. With Zerocash being PoW and PIVX being PoS, I was wondering what your thoughts are when comparing the two projects?

3 Likes

I personally think that changes in the consensus layer (PoS) don’t affect the privacy preserving part that much. It would possible for Zerocash to migrate to PoS as discussed in this thread.

2 Likes

Proof of knowledge
If the verifier accepts a proof, the prover must know what a is.

A simple correction: zk-SNARKs stands for zero-knowledge Succinct [ARguments of Knowledge] for a reason.

Although this difference is kinda trival in a sense that people often mixed up both terms, they actually have quite different implicit meanings.

Argument of knowledge:
Assuming the adversary to be computationally bounded (polynomially-time bounded).

Proof of knowledge:
Assuming the adversary to be computationally unbounded.

A zk-PoK scheme, therefore, has a stronger security property than a zk-SNARK scheme.

5 Likes

@tina1998612 have you read some of the new posts about REDSHIFT and PlonK, where does this piece fit in with those two?

3 Likes

@jmcgirk REDSHIFT and PlonK are both zk-SNARK based privacy-preserving methods. I think PlonK is more possible to fit in this structure. PlonK using different commitments mechanisms in the trusted setup step. In this step, it can pick bitcoin transaction information as parameters and verify the transaction on the top of the bitcoin layer. It’s like proof-of-existance.

REDSHIFT removes the trusted setup parts, so there are no bitcoin transaction information can put into here as parameter.

3 Likes

@Sean1992076, @tina1998612 mentioned that it might be interesting to see a chart comparing the transaction speed and other costs of Zcash with other privacy methods – is this something you might want to try doing?

3 Likes

This is an ancient (for crypto) paper! How much have zkSNARKS changed in the last seven years or so? @Jerry_Ho @Sean1992076

1 Like

To put it simple but possibly inaccurate:
The Zerocash system mentioned in the 2014 paper can be called “sprout”, and the current version of Zcash can be called “sapling” - a much more advanced and sophisticated version.

If you were to check this very, very detailed spec documentation:

In the index, you can see that sprout references are still everywhere in the docs, even 5 years after the 2016 upgrade, for the reference. Without them, people will be confused.

Recently (Oct, 2021), the mainnet is said to be upgraded to the NU5 version, which supported Orchard protocol, and moving the proving system from zk-sNARK to HALO2, where the arithmetization of circuit is partially based on Plonk(ultraplonk).

The history graph of the evolution can be seen here: Schedule - Zcash

3 Likes

This paper mentions that using zk-SNARKs trusted setup as Zerocash’s parameter to link to the bitcoin main chain. Those years zk-SNARKs is trying to use different commitments as a trusted setup. Also, change the mathematic to compute faster when generating the proof such as Plonk.

2 Likes