Zero-Knowledge Proofs in Blockchain Applications

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS DR JOHN T. H. YUEN UNIVERSITY OF HONG KONG Summer Summit on Cryptocurrency and Blockchain Technologies 2019

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS Introduction Simple ZK proof Blockchain and ZK Bulletproof zkSNARK

ZERO KNOWLEDGE PROOFS Goldwasser, S.; Micali, S.; Rackoff, C. (1989), "The knowledge complexity of interactive proof systems" (PDF), SIAM Journal on Computing, 18 (1): 186 208,

ZERO KNOWLEDGE PROOFS I know which ball is red and which ball is green Colour blindness Round 1: Shuffled or not? Round 1: No Round 2: Shuffled or not? Round 2: Yes N rounds accept or reject Zero knowledge of the colour of each ball is leaked to Bob.

PROPERTIES OF ZKP Completeness: if the statement is true, the honest verifier will be convinced of this fact by an honest prover. accept Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability. false

PROPERTIES OF ZKP Zero-knowledge: if the statement is true, no verifier learns anything other than the fact that the statement is true. xxxxx yyyyy = green She knows which ball is green/red zzzzz = red Formalized by showing that every verifier has some simulator that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the verifier in question. xxxxx yyyyy simulator zzzzz

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS Introduction Simple ZK proof Blockchain and ZK Bulletproof zkSNARK

SIMPLE ZK PROOF: DISCRETE LOGARITHM I know the secret key x for the public key ? = ?? I know a public key (?,?) 1. Pick ? ??? ? = ?? 2. Pick ? ??? ? 3. Compute z = r + ?? mod p ? Accept iff ??= R?? I know Alice has a secret key for the public key (?,?)

VARIANT: NON-INTERACTIVE ZK I know the secret key x for the public key ? = ?? I know a public key (?,?) 1. Pick ? ???, compute ? = ?? 2. Pick ? = ??? (?,?,?) 3. Compute z = r + ?? mod p Compute R = ??? ? ?,? Accept iff ? = ??? (?,?,?) I know Alice has a secret key for the public key (?,?)

ZK PROOFS FOR NP AND MORE All problems in NP have zero-knowledge proofs if one-way function exists. There exists a ZK proof system for the NP-complete graph colouring problem with three colours [1]. The graph non-isomorphism problem has a zero-knowledge proof. This problem is in co-NP, but is not currently known to be in either NP or any practical class. [1] Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). "Proofs that yield nothing but their validity". Journal of the ACM. 38 (3): 690 728.

ZK PROOFS FOR NP AND MORE Can build (almost) any combination of statements like: (? ? = ? OR ? ? = ?) AND G ? = ?AND . 0 ? 10000 (range proof)

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS Introduction Simple ZK proof Blockchain and ZK Bulletproof zkSNARK

PRIVACY Blockchain Distributed Ledger Consensus Single version of history Immutable Transparent Unforgeable (signature) Transparency is good for some use cases, e.g., supply chain management Transparency is not desirable for sensitive information, e.g., transaction details between two banks should not be known to other banks

PRIVACY-PRESERVING CRYPTOCURRENCY 3 Types of Privacy: ?? Sender anonymity Recipient anonymity Confidential transaction Monero (#13) Sender anonymity: linkable ring signature Recipient anonymity: Diffie- Hellman key exchange Confidential transaction: Pederson commitment + range proof Dash (#12) Mixing a few transactions input and output together Zcash (#26) Use zero knowledge proof of circuit zk-SNARK to achieve all 3 types of privacy Based on IEEE SP 2014 paper Can be extended to zk-smart contract (IEEE SP 2016) 1. Prove time = 30 sec. 2. Require trusted setup Quite Practical Not scalable for sender anonymity Practical Limited anonymity

PRIVACY-PRESERVING CRYPTOCURRENCY Privacy: Popular among both researchers and practitioners Zero-knowledge proof approach: zk-SNARK is implemented on top of Ethereum (#2) and JP Morgan s Quorum platform Very active research area, 10+ papers in top conferences since 2014 Linkable Ring Signature + Confidential Transaction approach: Confidential transaction is used by top startups such as Blockstream and Chain.com Monero developers proposed to use new scheme to improve the scalability of linkable ring signature Coin-shuffling approach: Improved in applications, such as SharedCoins, Dark Wallet. CoinShuffle paper in ESORICS 2014, works for bitcoin

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS Introduction Simple ZK proof Blockchain and ZK Bulletproof (The case of Monero) Zk-SNARK (The case of Zcash)

SENDER ANONYMITY BY RING SIGNATURES Prove in ZK that I know the secret key of Alice or Bob or Carol

LINKABLE RING SIGNATURE Problem of using ring signature for sender anonymity: Cannot detect double spending, because the sender is perfectly anonymous! Use Linkable Ring Signature : Detect when if someone signed twice with the same secret key ZK: I know the sk of Alice or Bob or Carol ? F: deterministic one-way function of sk Linkable Ring Sign Tag = F(sk) ? ZK: sk used to compute Tag = sk used in ?

LINKABLE RING SIGNATURE IN MONERO Monero s limitation: Signature size is O(N), where N = number of public keys (PKs) to hide the signer not scalable Goal: Signature size is O(log N) Method 1: One-out-of-many commitment approach View the public key as a commitment of zero, where the randomness is the secret key the set of public keys signer index secret key Pk = Com(0; sk)

One-out-of-many commitment approach Proof size = O(log (N)) Remark: this is ring signature only. Need to add linkability J. Groth, M. Kohlweiss. One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin. Eurocrypt 2015.

O(LOG N)-SIZE RING SIGNATURE Method 2: Bulletproof approach (inner product argument) Define: Then we have a commitment of the signer public key ?? as: We need a ZK proof for the above statement with size O(log n)! Inner product argument T. H. Yuen, S. Sun, J. K. Liu, M. H. Au, M. F. Esgin, Q. Zhang, D. Gu. RingCT 3.0 for Blockchain Confidential Transaction: Shorter Size and Stronger Security. ePrint 2019:508

Inner product argument approach ZK proof for Proof size = O(log (N)) B. B nz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. 2018. Bulletproofs: Short Proofs for Confidential Transactions and More. In IEEE SP 2018.

CONFIDENTIAL TRANSACTION IN MONERO The input and output transaction amount is hidden by using Pedersen commitment The correctness (= balance) of the input and output amount is guaranteed by the additive homomorphic property of using Pedersen commitment. But we still need to ensure that for every transaction amount M: 0 ? < ??? We need a (compact) zero-knowledge range proof for all transaction amount M! We can also use inner product argument (Bulletproof) Represent each amount M as a binary vector (?1,?2, , ??) showed in ZK that M = (?1,?2, , ??) (1,2, 4, 8, , 2? 1) 0 ? < 2?

ZERO KNOWLEDGE IN BLOCKCHAIN APPLICATIONS Introduction Simple ZK proof Blockchain and ZK Bulletproof (The case of Monero) zk-SNARK (The case of Zcash)

ZK-SNARK Zero-Knowledge Succinct Non-Interactive Argument of Knowledge Used in ZCash Prove in ZK that I know a SK, where the hash of the corresponding PK (= address) is included in a Merkle tree (of a block of transactions). ZK involving hash function is complicated zk-SNARK The high level steps for generating a zero-knowledge proof by zk-SNARK: Computation Arithmetic Circuit R1CS QAP zk-SNARK Let s understand it by an example: Prove that I know x such that ?3+ ? + 5 = 35

ZK-SNARK Computation Arithmetic Circuit R1CS QAP zk-SNARK Prove that I know x such that ?3+ ? + 5 = 35 Computation Arithmetic Circuit: Give a circuit for the expression (x * x)*x + x + 5 ????? x ? ???_1 x ? ?????? = 35 + ???_2 + ??? 5

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS R1CS: Rank 1 Constraint System check that the values are traveling correctly in the circuit Define a vector ? representing <'one', 'x', 'out', 'sym_1', 'y', 'sym_2 > The correct (hidden) intermediate values ? = <1,3,35,9,27,30> ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS Define a vector ? representing the left input wire to a logic gate. Define a vector ? representing the right input wire to a logic gate. Define a vector ? representing the output wire to a logic gate. We get the relation: ? ? ? ? ? ? = 0 ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS Check the relation: ? ? ? ? ? ? = 0 Recall vector ? representing <'one', 'x', 'out', 'sym_1', 'y', 'sym_2 >= <1,3,35,9,27,30> For the first logic gate: a = [0, 1, 0, 0, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 1, 0, 0] ? ? ? ? ? ? = 3 3 9 = 0 ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS Check the relation: ? ? ? ? ? ? = 0 Recall vector ? representing <'one', 'x', 'out', 'sym_1', 'y', 'sym_2 >= <1,3,35,9,27,30> For the 2nd logic gate: a = [0, 0, 0, 1, 0, 0] b = [0, 1, 0, 0, 0, 0] c = [0, 0, 0, 0, 1, 0] ? ? ? ? ? ? = 9 3 27 = 0 ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS Check the relation: ? ? ? ? ? ? = 0 Recall vector ? representing <'one', 'x', 'out', 'sym_1', 'y', 'sym_2 >= <1,3,35,9,27,30> For the 3rd logic gate: a = [0, 1, 0, 0, 1, 0] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 0, 0, 0, 1] ? ? ? ? ? ? = (3 + 27) 1 30 = 0 ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK Arithmetic Circuit R1CS Check the relation: ? ? ? ? ? ? = 0 Recall vector ? representing <'one', 'x', 'out', 'sym_1', 'y', 'sym_2 >= <1,3,35,9,27,30> For the 4th logic gate: a = [5, 0, 0, 0, 0, 1] b = [1, 0, 0, 0, 0, 0] c = [0, 0, 1, 0, 0, 0] ? ? ? ? ? ? = (5 + 30) 1 35 = 0 ????? x ? 3 ???_1 9 x ? 27 ?????? = 35 + ???_2 30 + ??? 5 35

ZK-SNARK: R1CS Computation Arithmetic Circuit R1CS QAP zk-SNARK The complete R1CS put together is: A [0, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0] [0, 1, 0, 0, 1, 0] [5, 0, 0, 0, 0, 1] B R1CS: Rank 1 Constraint System check that the values are traveling correctly in the circuit [0, 1, 0, 0, 0, 0] [0, 1, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0] C [0, 0, 0, 1, 0, 0] [0, 0, 0, 0, 1, 0] [0, 0, 0, 0, 0, 1] [0, 0, 1, 0, 0, 0]

ZK-SNARK: QAP Computation Arithmetic Circuit R1CS QAP zk-SNARK R1CS QAP (Quadratic Arithmetic Programs): implements the exact same logic except using polynomials instead of dot products E.g., four groups of three vectors (A, B, C) of length six six groups of three degree- 3 polynomials. When evaluating the polynomials at x=1, we get the first set of vector. When evaluating the polynomials at x=2, we get the 2nd set of vector Transformation can be done by Lagrange interpolation Use Fast Fourier Transform to optimize

ZK-SNARK: QAP Computation Arithmetic Circuit R1CS QAP zk-SNARK After some computations A results at x=1 0 1 0 0 0 0 A polynomials [-5.0, 9.166, -5.0, 0.833] [8.0, -11.333, 5.0, -0.666] [0.0, 0.0, 0.0, 0.0] [-6.0, 9.5, -4.0, 0.5] [4.0, -7.0, 3.5, -0.5] [-1.0, 1.833, -1.0, 0.166] 0.833 x3 - 5x2 + 9.166 x - 5 B results at x=1 0 1 0 0 0 0 B polynomials [3.0, -5.166, 2.5, -0.333] [-2.0, 5.166, -2.5, 0.333] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] -0.333 x3 + 2.5x2 - 5.166 x + 3 Put x =1 C results at x=1 0 0 0 1 0 0 C polynomials [0.0, 0.0, 0.0, 0.0] [0.0, 0.0, 0.0, 0.0] [-1.0, 1.833, -1.0, 0.166] [4.0, -4.333, 1.5, -0.166] [-6.0, 9.5, -4.0, 0.5] [4.0, -7.0, 3.5, -0.5] 0.166 x3 - x2 + 1.833 x - 1

ZK-SNARK: QAP Computation Arithmetic Circuit R1CS QAP zk-SNARK Now we get inner product of ? with polynomial a polynomial t(x) t(x) is divisible by the minimal polynomial Z(x) = (x - 1) * (x - 2) * (x - 3) * (x - 4) = t(x) ? ? ?

ZK-SNARK: QAP Computation Arithmetic Circuit R1CS QAP zk-SNARK For example, A . s = [43.0, -73.333, 38.5, -5.166] degree 3 polynomial B . s = [-3.0, 10.333, -5.0, 0.666] C . s = [-41.0, 71.666, -24.5, 2.833] t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444] degree 6 polynomial Z = [24, -50, 35, -10, 1] degree 4 polynomial t / Z = [-3.666, 17.055, -3.444] degree 2 polynomial with no remainder If the value of s is incorrect, t/Z will have a reminder

ZK-SNARK Computation Arithmetic Circuit R1CS QAP zk-SNARK QAP zk-SNARK Remember that the solution to a QAP is a set of polynomials (A, B, C, H) such that A(x) * B(x) - C(x) = H(x) * Z(x), where: A is a linear combination of a set of polynomials {A_1 A_m} B is the linear combination of {B_1 B_m} with the same coefficients C is a linear combination of {C_1 C_m} with the same coefficients The sets {A_1 A_m}, {B_1 B_m} and {C_1 C_m} and the polynomial Z are part of the problem statement. The final ZK proof for (A, B, C, H) consists of 3 steps.

ZK-SNARK PROOF 1 Computation Arithmetic Circuit R1CS QAP zk-SNARK Setup: The following ECC points are given: [A_i(t)]G, [k_a A_i(t)]G, [B_i(t)]G, [k_b B_i(t)]G, [C_i(t)]G, [k_c C_i(t)]G, for i=1, ,m. Here t, k_a, k_b and k_c are secret numbers chosen by a trusted party. Proof 1: Knowledge of exponent By using the linear combination of polynomials A, B, C, the prover can compute: _a = [A(t)]G, _a = [k_a A(t)]G _b = [B(t)]G, _b = [k_b B(t)]G _c = [C(t)]G, _c = [k_c C(t)]G e( _a,[k_a]G) ?= e( _a, G) e( _b,[k_b]G) ?= e( _b, G) e( _c,[k_c]G) ?= e( _c, G) Verify

ZK-SNARK PROOF 2 Computation Arithmetic Circuit R1CS QAP zk-SNARK Additional setup: The following ECC points are given: [(A_i(t) + B_i(t) + C_i(t)) * ?] G, ??G, ?G. Here ?,? are secret numbers chosen by a trusted party. Proof 2: make sure that all three linear combinations have the same coefficients _k = [(A(t) + B(t) + C(t)) * ?] G Verify e( _k, ?G) ?= e( _a + _c, ??G) e(??G, _b)

ZK-SNARK PROOF 3 Computation Arithmetic Circuit R1CS QAP zk-SNARK Additional setup: the values G, [t]G, [t2]G, are given in system parameter the values G, [Z(t)]G are also given in system parameter Proof 3: QAP divisibility A(x) * B(x) C(x) = H(x) * Z(x) _h = [H(t)] G Verify e( _a, _b) / e( _c, G) ?= e( _h, [Z(t)]G) Sum up: Computation Arithmetic Circuit R1CS QAP zk-SNARK Proof is 8 ECC points: _a, _a, _b, _b , _c, _c , _k, _h = 288 bytes, no matter how large is the circuit!

USAGE OF ZK-SNARK Shielded transaction in Zcash creating a shielded Zcash transaction can take up to 40 seconds, while verifying that a transaction is valid only takes milliseconds Can be applied to smart contract zk-SNARK is implemented on top of Ethereum and JP Morgan s Quorum platform

THANK YOU!