PWL SF 03/18 > Cathie Yun on "Bulletproofs: Short Proofs for Confidential Transactions and More"

Cathie Yun on "Bulletproofs: Short Proofs for Confidential Transactions and More"

https://crypto.stanford.edu/bulletproofs/

Cathie tells us: "Bulletproofs is exciting because it enables us to do faster zero knowledge range proofs, making it more feasible to implement practical confidential assets for blockchain transactions!"

Cathie's bio
Cathie Yun is a software engineer working on applied cryptography at Chain. She received her bachelor's and master's degrees in computer science from MIT, with a focus on computer systems engineering. When she isn't designing better blockchain protocols, she can be found climbing mountains and practicing aerial silks.

https://www.meetup.com/papers-we-love-too/events/248613430/

Transcript

1. Paper by Bünz, Bootle, Boneh, Poelstra, Wuille, Maxwell
 Presentation by Cathie Yun, software engineer at Chain M A R C H 2 9 , 2 0 1 8 Bulletproofs
2. 2 Agenda Motivation Bulletproofs Intro Bulletproofs Deep Dive Implementation Recap 1 2 3 4 5
3. 3 What are Bulletproofs? • Efficient zero knowledge proof system designed by Bünz, Bootle, Boneh, Poelstra, Wuille, Maxwell • Builds on earlier techniques of Bootle, Cerulli, Chaidos, Groth, Petit (EUROCRYPT’16) • Key building block of both papers is an efficient inner product argument
4. 4 Zero knowledge proofs • “I know a secret but I won’t tell you!” • Prove a statement is true, without revealing the secret that the statement is about. • Properties of a ZK proof: • Completeness: If the statement is true, the honest verifier will be convinced of it. • Soundness: If the statement is false, no-one can convince the verifier that it is true. • Zero-knowledge: The verifier learns nothing other than the truth of the statement.
5. “Traditional ledgers achieve privacy by limiting access to the parties involved.
 By contrast, the blockchain requirement to announce all transactions
 to all network participants precludes this method.” Bitcoin whitepaper 5
6. Problem We need a method to have network enforce ledger integrity
 without compromising privacy of the participants. 6
7. Cleartext transaction 7 $5 $4 $3 $6 INPUTS OUTPUTS $5 + $4 $3 + $6
8. Confidential transaction 8 A B C D INPUTS OUTPUTS A + B C + D
9. 9 Building block: Commitments m Com(m) commit m Com(m) open
10. 10 Commitment properties Hiding: a commitment Com(m) does not reveal m Binding: can not open Com(m) to a different message m’
11. 11 Additively homomorphic commitment if A + B = C + D Com(A) + Com(B) = Com(C) + Com(D) then 2·E = F 2·Com(E) = Com(F) then if
12. Confidential transaction 12 A = Com(5) B = Com(4) C = Com(3) D = Com(6) INPUTS OUTPUTS A + B C + D Com(x) is an additively homomorphic commitment
13. Confidential transaction 13 A = Com(5) B = Com(4) C = Com(-100) D = Com(109) INPUTS OUTPUTS A + B C + D Commitments that we use are in finite field, allowing “negative values” $100 created out of nowhere
14. Confidential transaction 14 A = Com(5) B = Com(4) C = Com(3) proof1 D = Com(6) proof2 INPUTS OUTPUTS A + B C + D ZK proofs that amount is in range This is where Bulletproofs comes in -
 efficient zero knowledge proofs!
15. 15 Bulletproofs in blockchain applications Good properties: • Compact - easy to transmit and store • Fast verification - all parties should verify all proofs • No trusted setup - allows ad-hoc proofs ZK proofs can be used to prove statements about values, value flows, and contracts.
16. 16 Agenda Motivation Bulletproofs Intro Bulletproofs Deep Dive Implementation Recap 1 2 3 4 5
17. 17 Bulletproof building block: inner products Given vectors a and b of length n = 2k, we want to prove that c = ⟨a,b⟩ = a1×b1 + ··· + an×bn The inner product argument allows proving this without sending a and b. 0 1 Prover commits to a and b Prover uses the verifier’s challenges to compress a,b
 into vectors of length n/2, sends 2 points to the verifier k } The proof size is O(log(n)) instead of O(n).
18. 18 Bulletproof rangeproofs math & crypto To do this in zero knowledge, we add many, many blinding factors, but this is the key idea. 0≤v<2n How do we express a range as an inner product? t=⟨l,r⟩
19. 19 Agenda Motivation Bulletproofs Intro Bulletproofs Deep Dive Implementation Recap 1 2 3 4 5
20. Range Proof from first principles
21. 21 Bulletproof rangeproofs To do this in zero knowledge, we add many, many blinding factors, but this is the key idea. 0≤v<2n How do we express a range as an inner product? t=⟨l,r⟩ math & crypto
22. Proving binary structure 22 Statement to prove: Break v up into bits: = ⟨bits,2n⟩ Notation: 0 1 1 0 0 1 1 1 … 1 v = Σ x 20 21 22 23 24 25 26 27 … 2n-1 0 ≤ v < 2n 1) Prove v = ⟨bits,2n⟩ 2) Prove bits of v are actually bits (0s or 1s)
23. Proving bits of v are actually bits 23 0 1 1 0 0 1 1 1 … 1 v = Σ x 20 21 22 23 24 25 26 27 … 2n-1 Let’s call the vector of bits aL Let’s make a vector aR that is aL - 1n. aL = bits of v aR = bits of v - 1n = aL - 1n Iff the bits of v are actually bits (0s or 1s), then this will be true: aL ∘aR = 0n -1 0 0 -1 -1 0 0 0 … 0 0 1 1 0 0 1 1 1 … 1 0 0 0 0 0 0 0 0 … 0
24. Putting it together 24 0 ≤ v < 2n We want to prove: We can do this by proving: 1) v = ⟨aL,2n⟩
 2) aL ∘aR = 0n 
 3) aR = aL - 1n binary structure of v bits are actually bits (0s or 1s) relation between bit representations
25. Recap 25 0≤v<2n t=⟨l,r⟩ v = ⟨aL,2n⟩
 aL∘aR = 0n 
 aR = aL - 1n
26. Building block: combining statements 26 Prover wants to prove that: Verifier provides a random challenge scalar Prover combines the original statements: Since the prover cannot predict x, if the latter statement holds then with probability 1-1/p the first statements hold.
27. Building block: combining statements 27 Prover wants to prove that: Prover combines the original statements: Since the prover cannot predict y, if the latter statement holds then with probability 1-n/p the first statements hold. This can also be written as: This can also be written as: Verifier provides a random challenge scalar
28. Combining vector statements 28 Previous equations: Rewritten: Combined into inner product: v = ⟨aL,2n⟩
 aL ∘aR = 0n 
 aR = aL - 1n aL ∘aR = 0n 
 aL - 1n - aR = 0n ⟨aL ∘aR , yn⟩= 0
 ⟨aL - 1n - aR , yn⟩ = 0 Verifier provides a random challenge scalar y:
29. Combining vector statements: again! 29 Combined into one equation: Previous equations: v = ⟨aL,2n⟩
 ⟨aL ∘aR , yn⟩= 0
 ⟨aL - 1n - aR , yn⟩ = 0 z2·⟨aL,2n⟩ + 
 z·⟨aL ∘aR , yn⟩ +
 ⟨aL - 1n - aR , yn⟩ 
 = z2·v Verifier provides a random challenge scalar z:
30. Re-arranging the terms 30 Rewritten: just a lot of
 annoying algebra Previous equations: z2·⟨aL,2n⟩ + 
 z·⟨aL ∘aR , yn⟩ +
 ⟨aL - 1n - aR , yn⟩ 
 = z2·v ⟨aL-z·1n, aR ∘yn + z2 ·2n+z·yn⟩ = z2·v + (y, z)
31. Recap 31 0≤v<2n t=⟨l,r⟩ v = ⟨aL,2n⟩
 aL∘aR = 0n 
 aR = aL - 1n ⟨aL-z·1n, aR ∘yn + z2 ·2n+z·yn⟩ 
 = z2·v + (y, z)
32. ⟨ aL-z·1n , aR ∘yn + z2 ·2n+z·yn ⟩ = z2·v + (y, z) Pieces of the inner product statement 32 f(aL) g(aR) h(v)
33. 33 Additively homomorphic commitment if A + B = C + D Com(A) + Com(B) = Com(C) + Com(D) then 2·E = F 2·Com(E) = Com(F) then if
34. Convert into commitments 34 aL aR v Com(aL) Com(aR) Com(v) ⟨ f(aL) , g(aR) ⟩ = h(v) This works if we have an additively homomorphic commitment scheme ⟨ f(Com(aL)) , g(Com(aR)) ⟩ = h(Com(v))
35. Omitted details 35 • How the challenge scalars are actually generated (Fiat-Shamir) • How the commitments work (Pedersen Commitments, homomorphism) • How the values are blinded, and how we commit to the blinding factors
36. Inner Product Proof
37. 37 Bulletproof building block: inner products Given vectors a and b of length n = 2k, we want to prove that c = ⟨a,b⟩ = a1×b1 + ··· + an×bn The inner product argument allows proving this without sending a and b. 0 1 Prover commits to a and b Prover uses the verifier’s challenges to compress a,b
 into vectors of length n/2, sends 2 points to the verifier k } The proof size is O(log(n)) instead of O(n).
38. 38 a b c = <a, b> alo ahi bL bR a' b' c' = <a', b'> a' = aL·x + aR·x-1 b' = bL·x-1 + bR·x c' = < aL·x2 + aR·x-2, bL·x-2 + bR·x2 > = <aL, bL> + <aR, bR>
 + x2·<aL, bR>
 + x-2·<aR, bL>
 c' = c + x2·L + x-2·R let’s call this L let’s call this R Prover sends L, R to verifier Repeat! Prover gets random challenge scalar x from verifier same as c
39. 39 a b c = <a, b> Prover sends a', b', c' to verifier Base Case: Prover a' b' c' = a'·b' Verifier checks 
 c' == a'·b'
40. Omitted details 40 • How the challenge scalars are actually generated (Fiat-Shamir) • All operations are actually over commitments instead of plain values • How we can use multi-exponentiation to acheive faster verification
41. 41 Agenda Motivation Bulletproofs Intro Bulletproofs Deep Dive Implementation Recap 1 2 3 4 5
42. Group • Bulletproofs requires a prime-order group • Can use a prime-order elliptic curve (e.g. secp256k1) • Existing implementation by Poelstra, Wuille in C 42 https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs
43. Performance For blockchain applications: want to minimize bandwidth & verification time • secp256k1 implementat 43
44. Group • Bulletproofs requires a prime-order group • Can use a prime-order elliptic curve (e.g. secp256k1) • Can’t directly use a non-prime-order elliptic curve (e.g. curve25519) • Edwards curves are non-prime-order but faster • Abstraction mismatch between prime-order group and non-p curve 44 https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs
45. Decaf & Ristretto • Decaf - Hamburg ’15 • Fixes abstraction mismatch between 
 prime-order group and non-prime-order curve • Ex. cofactor 4 reduction: rotate into one quadrant • We used Curve25519, has cofactor 8 • Use a variant of Decaf, called Ristretto, works with cofactor 8 • Fast, pure-Rust AVX2 implementation of the parallel formulas of Hisil, Wong, Carter, Dawson ’08 in curve25519-dalek 45 Decaf: https://eprint.iacr.org/2015/673.pdf
 curve25519-dalek: https://doc-internal.dalek.rs/curve25519_dalek/backend/avx2/index.html
 HWCD: https://www.iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
46. Rust • Rust iterators are lazy and zero-cost* • Can build up points & scalars using rust iterators &
 pass them into the multiscalar API to inline computation • Don’t have to do extra allocations or manage temporaries • Memory-safe and thread-safe • Powerful type system • Fast to learn & code in 46 * except for build times
47. 47 Agenda Motivation Bulletproofs Intro Bulletproofs Deep Dive Implementation Recap 1 2 3 4 5
48. 48 Zero knowledge proofs • “I know a secret but I won’t tell you!” • Prove a statement is true, without revealing the secret that the statement is about. • Properties of a ZK proof: • Completeness: If the statement is true, the honest verifier will be convinced of it. • Soundness: If the statement is false, no-one can convince the verifier that it is true. • Zero-knowledge: The verifier learns nothing other than the truth of the statement.
49. Confidential transaction 49 A = Com(5) B = Com(4) C = Com(3) proof1 D = Com(6) proof2 INPUTS OUTPUTS A + B C + D ZK proofs that amount is in range This is where Bulletproofs comes in -
 efficient zero knowledge proofs!
50. 50 Bulletproof rangeproofs math & crypto To do this in zero knowledge, we add many, many blinding factors, but this is the key idea. 0≤v<2n How do we express a range as an inner product? t=⟨l,r⟩
51. Bulletproof rangeproofs 51 0≤v<2n t=⟨l,r⟩ v = ⟨aL,2n⟩
 aL∘aR = 0n 
 aR = aL - 1n ⟨aL-z·1n, aR ∘yn + z2 ·2n+z·yn⟩ 
 = z2·v + (y, z)
52. 52 Bulletproof building block: inner products Given vectors a and b of length n = 2k, we want to prove that c = ⟨a,b⟩ = a1×b1 + ··· + an×bn The inner product argument allows proving this without sending a and b. 0 1 Prover commits to a and b Prover uses the verifier’s challenges to compress a,b
 into vectors of length n/2, sends 2 points to the verifier k } The proof size is O(log(n)) instead of O(n).
53. crypto tricks
54. 54 Additively homomorphic commitment if A + B = C + D Com(A) + Com(B) = Com(C) + Com(D) then 2·E = F 2·Com(E) = Com(F) then if
55. Confidential transaction 55 A = Com(5) B = Com(4) C = Com(3) proof1 D = Com(6) proof2 INPUTS OUTPUTS A + B C + D ZK proofs that amount is in range This is where Bulletproofs comes in -
 efficient zero knowledge proofs!
56. Convert into commitments 56 aL aR v Com(aL) Com(aR) Com(v) ⟨f(Com(aL),g(Com(aR)⟩ = h(Com(v)) ⟨f(aL),g(aR)⟩ = h(v) This works if we have an additively homomorphic commitment scheme
57. Building block: combining statements 57 We want to prove that: Let us get a random challenge scalar Combine the original statements: Since you cannot predict x, if the latter statement holds then with probability 1-1/p the first statements hold.
58. Combining vector statements 58 Previous equations: Rewritten: Combined into inner product: v = ⟨aL,2n⟩
 aL ∘aR = 0n 
 aR = aL - 1n aL ∘aR = 0n 
 aL - 1n - aR = 0n ⟨aL ∘aR , yn⟩= 0
 ⟨aL - 1n - aR , yn⟩ = 0 Get a random challenge scalar y:
59. Combining vector statements: again! 59 Combined into one equation: Previous equations: Get a random challenge scalar z: v = ⟨aL,2n⟩
 ⟨aL ∘aR , yn⟩= 0
 ⟨aL - 1n - aR , yn⟩ = 0 z2·⟨aL,2n⟩ + 
 z·⟨aL ∘aR , yn⟩ +
 ⟨aL - 1n - aR , yn⟩ 
 = z2·v
60. 60 Bulletproof circuits Beyond range proofs, Bulletproofs can prove arithmetic circuit satisfiability. An arithmetic circuit is a graph of arithmetic operations describing a computation. A set of inputs and outputs satisfies the circuit if the inputs evaluate to the outputs. × + × × x x8+9x4 9 This allows Bulletproofs to prove more general statements.
61. Further Reading Bulletproofs paper: 
 https://eprint.iacr.org/2017/1066.pdf Blockstream blog post on Bulletproofs implementation: 
 https://blockstream.com/2018/02/21/bulletproofs-faster-rangeproofs-and- much-more.html A helpful writeup explaining Bulletproofs: 
 https://github.com/AdamISZ/from0k2bp Chain will release our notes and implementation soon:
 Stay posted! 61
62. Thanks for listening :) 62 @oleganza Oleg Andreev @cathieyun Cathie Yun @hdevalence Henry de Valence Chain is hiring!
 We’ll be going to Victory Hall afterwards, if you have any further questions