The Zerocash paper followed by an actual implementation by the Zcash cryptocurrency, created a lot of interest around zero-knowledge methods and systems. Since then many advancements were done both in research and in practical applications.
This post will briefly overview the requirements from a general zero-knowledge system and how it can be used to construct a ledger based coin with privacy assurances.
What is a zero-knowledge proof system?
zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x.
More specifically:
According to ZKProof security track proceedings :
The relation R specifies which pairs (x,w) are considered related to each other, and which are not related to each other. The relation defines a matching language L consisting of instances x that have a witness w in R. A statement is a claim x ∈ L, which can be true or false.
The relation R can, for instance, be specified as a program (e.g. in C or Java), which given inputs x and w decides to accept, meaning (x,w) ∈ R, or reject, meaning w is not a witness to x in L. … In the academic literature, relations are often specified either as RAM programs or through boolean and arithmetic circuits, which we describe below.
Example
def eval(x,w):
g = 0x06cdb238b2f9c9ff32dbcca964593c5836ddd9...
return x-g**w
here x serves as the public input and w as the witness, the purpose is
to prove that we know w such that
x-g^w=0
or
x=g^w
for specific public input x - knowledge of exponent for the discrete log problem.
the specified program will be compiled into an arithmetic circuit C, which can be used to define both the relation R and the language L:
R=\{(x,w)\in\mathbb{F}^n \times\mathbb{F}^h:\, C(x,w)=0\}\\ L=\{x\in\mathbb{F}^n:\exists w\in\mathbb{F}^h \, s.t.\, C(x,w)=0\}
We will use those definitions to informally define a generic proof system:
A proof system (for a relation R defining a language L) is a protocol between a prover and a verifier sending messages to each other. The prover and verifier are defined by two algorithms, which we call Prove and Verify. The algorithms Prove and Verify may be probabilistic and may keep internal state between invocations. Specifically
KeyGen(\lambda ,C)\rightarrow(pk,vk) On input a security parameter \lambda and circuit C, the key generator samples a proving key pk and a verification key vk. Both are published as public parameters and can be used, any number of times, to prove/verify membership in L. For more information about the generation of those parameters check out the trusted setup blog post. This step is optional and is not required for some proof system such as Bulletproofs and STARKs.
Prove(pk,x,w) \rightarrow\pi On input a proving key pk and any (x,w)\in R the prover outputs a non-interactive proof \pi for the statement x\in L
Verify(vk,x,\pi) \rightarrow b On input a verification key vk, an input x, a proof \pi the verifier outputs b=1 if he is convinced that x\in L
For a live demo of the specified circuit and in-browser implementation, check out the awesome web-assembly ZK demo and the related post.
Minimal Privacy Coin
We will use the primitives to construct a minimal privacy coin, which will demonstrate how zero-knowledge proof system can be used. This construction is a modified version based on step 1-2 in the Zerocash paper.
- In this simple construction, all coins have the same value.
- This construction makes use of any general zero-knowledge proof system, which satisfies the requirements from above (with or without the KeyGen step).
- This construction makes use of a commitment scheme. Namely, given a collision-resistant hash function CRH, randomness r and message m:
c:=COMM_r(m)=CRH(r||m)
c is opened by revealing r and m, and one can verify that COMM_r(m) = c - The construction is created on top of an append-only style distributed ledger, i.e. Bitcoin.
- The construction makes use of pseudo random function, a deterministic function that maps two distinct sets (domain and range) and looks like a truly random function. i.e PRF_x(y) will create a random looking number for value y and seed x.
- each user u_i samples a secret key and calculates it’s own public address by pk_i=PRF_{sk_i}(0)
Minimal privacy coin data structures:
CMLIST - a list of all coin commitment on the ledger.
Minimal privacy coin operations:
-
MINT - tx_{mint}, a user u_1 owns the key tuple (sk_1,pk_1), samples a random number \rho_1 and a randomness r_1, computes a coin commitment cm:=COMM_r(pk_1||\rho_1) and serial number n:=PRF_{sk_1}(\rho_1), the coin is represented as c_1:=(pk_1,\rho_1,r_1,cm_1). The actual mint transaction to the ledger will contain cm and n (but not r_1 or \rho_1) and a payment of 1 value unit (say 1 BTC) to a pool of value. Mint transaction is a certificate of deposit, backed by the underlying currency.
-
TRANSFER - tx_{transfer}, user u_1 may transfer his coin c_1 to user u_2 by creating a new coin c_2:
in order to create the new coin c_2, u_1 calculates:
- sample random number \rho_2,random number r_2
- the commitment for the new coin cm_2:=COMM_{r_2}(pk_2||\rho_2) for the public key of user u_2
- the new coin is represented by c_2=(pk_2,\rho_2,r_2,cm_2) and the values need to be secretly transferred to the recipient user u_2
a zero-knoledge proof \pi of the NP statements:
- Coins c_1,c_2 are well formed: cm_i=COMM_{r_i}(pk_i||\rho_i) for i\in\{1,2\}
- cm_1 included in CMLIST
- User u_1 have an access to its own private key, namely: pk_1=PRF_{sk}(0)
- The published serial number is indeed driven from \rho_1, namely: n_1=PRF_{sk}(\rho_1)
The actual tx that is sent to the ledger is tx_{transfer}:=(n_1,cm_1,cm_2,\pi)
assuming that n_1 does not already appear as part of a previous transfer transaction and the proof is valid, the receiving user can redeem the underlying currency from the backing pool or transfer it again.
the following applies:
- User anonymity is achieved because the proof \pi is zero-knowledge: while n has revealed, no information about r is, and finding which commitment in CMLIST corresponds to a particular transfer transaction is equivalent to inverting f(x):=COMM_x(y) which considered infeasible.
- The sending user cannot spend or track the new coin c_2 since he cannot calculate the serial number n_2, doing so required knowledge of users u_2 secret key since n_2=PRF_{sk_2}(\rho_2)
improvements:
- CMLIST should be changed to a Markle tree, which will allow for practical proof for a much bigger list of commitment.
- Support notes with arbitrary value v. Refer to the complete Zerocash construction for more info.
- Support transfer of the secret values of the newly created coin c_2=(pk_2,\rho_2,r_2,cm_2) via the blockchain.
- Many others, suggestions are welcome, especially how to make it even more minimal.
For more information about various proof systems:
More Information about various constructions:
- Zcash sapling - the new and improved construction of Zcash
- Miximus - an Ethereum mixer based on zkSnarks.
- Semaphore - an anonymous voting system construction.
- Roll up - Ethereum scalability solution with zkSnarks
- Coda protocol - a project that uses recursive composition of zk-SNARKs to compress the whole blockchain down to the size of a few tweets.
- Please suggest more.
A curated list of zero-knowledge resources: