Upgrade to Pro — share decks privately, control downloads, hide ads and more …

PWL SF 03/18 > Cathie Yun on "Bulletproofs: Sho...

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/

Papers_We_Love

March 30, 2018
Tweet

More Decks by Papers_We_Love

Other Decks in Technology

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. 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
  3. 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.
  4. “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
  5. Problem We need a method to have network enforce ledger

    integrity
 without compromising privacy of the participants. 6
  6. 10 Commitment properties Hiding: a commitment Com(m) does not reveal

    m Binding: can not open Com(m) to a different message m’
  7. 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
  8. 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
  9. 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
  10. 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!
  11. 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.
  12. 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).
  13. 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⟩
  14. 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
  15. 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)
  16. 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
  17. 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
  18. 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.
  19. 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
  20. 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:
  21. 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:
  22. 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)
  23. 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)
  24. ⟨ 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)
  25. 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
  26. 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))
  27. 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
  28. 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).
  29. 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
  30. 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'
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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.
  37. 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!
  38. 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⟩
  39. 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)
  40. 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).
  41. 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
  42. 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!
  43. 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
  44. 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.
  45. 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:
  46. 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
  47. 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.
  48. 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
  49. 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