Cryptography for Blockchainsbeyond ECDSA and SHA256
S I G N AT U R E S A N D Z E R O K N O W L E D G E P R O O F S
Benedikt Bünz
Stanford University

Overview
1. Signatures
1. ECDSA
2. BLS
3. Threshold Signatures
4. Ring Signatures
5. Blind Signatures
2. Zero-Knowledge Proofs
1. An illustrative example (SUDOKU)
2. Sigma protocols
3. SNARKs
4. PCPs, CS-Proofs and STARKs
5. Bulletproofs

Signatures
Did Bob or Bart
say this?

Send 1 BTC to Alice

BobAliceBart

Signatures
Did Bob or Bart
say this?

Send 1 BTC to Alice
BobBobAliceBart

Signature (Formal Definiton)• Keygen→ (sk,pk)• Sign (sk,m) → 𝜎• Verify(pk, 𝜎,m) →{0,1}• Correctness: Verify(PK,SIGN(SK,M),M)=1• SECURITY: After seeing n signatures no adversary
can create a signature on new message

Signature (Diagram)(sk,pk)←Keygen𝜎 ←Sign(sk,m)pkm, 𝜎Verify(pk, m, 𝜎)Signature (ECDSA)• Used in Bitcoin (and other Cryptocurrencies)• Designed because of a patent conflict• Malleable: Given (pk,𝜎,m)-> 𝜎 % with Verify(pk,𝜎 % ,m)• -> Transaction malleability• -> Fooled Mt. Gox Cash Out Twice• After seeing n signatures no adversary can create a newsignature on any message

Preliminaries: Discrete Log and Pairings• Random 𝑥 ∈ ℤ∗*• Given 𝑔, 𝑔 . ∈ 𝔾 it’s hard to produce 𝑥• Pairing (Bilinear Map) 𝑒: 𝔾,−> 𝔾 4 , 𝔾 is a special elliptic curve• 𝑔5 , 𝑔6 ∈ 𝔾, 𝑒 𝑔5 , 𝑔6 = 𝑒 𝑔, 𝑔 5∗6• 𝑒 𝑔5 , ℎ = 𝑒 𝑔, ℎ5 = 𝑒 𝑔, ℎ 5• 𝑒(𝑔, 𝑢 ∗ 𝑣) = 𝑒(𝑔, 𝑢) ∗ 𝑒(𝑔, 𝑣)

BLS: Signatures• Eliptic curve 𝔾 with pairing e and generator 𝑔• H is a hash function that hashes into 𝔾• Setup: 𝑥 ←< ℤ* . 𝑠𝑘: 𝑥, 𝑝𝑘: 𝑔, 𝑔 .
• Sign(x,m): 𝜎 = 𝐻 𝑚 .
• Verify(𝑔, 𝑔 . , 𝜎,m):• 𝑒 𝜎, 𝑔 =?

BLS: Signatures• Eliptic curve 𝔾 with pairing e and generator 𝑔• H is a hash function that hashes into 𝔾• Setup: 𝑥 ←< ℤ* . 𝑠𝑘: 𝑥, 𝑝𝑘: 𝑔, 𝑔 .
• Sign(x,m): 𝜎 = 𝐻 𝑚 .
• Verify(𝑔, 𝑔 . , 𝜎,m):• 𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .
• 𝑒 𝜎, 𝑔BLS: Signatures• Eliptic curve 𝔾 with pairing e and generator 𝑔• H is a hash function that hashes into 𝔾• Setup: 𝑥 ←< ℤ* . 𝑠𝑘: 𝑥, 𝑝𝑘: 𝑔, 𝑔 .
• Sign(x,m): 𝜎 = 𝐻 𝑚 .
• Verify(𝑔, 𝑔 . , 𝜎,m):• 𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .
• 𝑒 𝜎, 𝑔 = 𝑒 𝐻 𝑚 . , 𝑔

BLS: Signatures• Eliptic curve 𝔾 with pairing e and generator 𝑔• H is a hash function that hashes into 𝔾• Setup: 𝑥 ←< ℤ* . 𝑠𝑘: 𝑥, 𝑝𝑘: 𝑔, 𝑔 .
• Sign(x,m): 𝜎 = 𝐻 𝑚 .
• Verify(𝑔, 𝑔 . , 𝜎,m):• 𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .
• 𝑒 𝜎, 𝑔 = 𝑒 𝐻 𝑚 . , 𝑔 = 𝑒 𝐻 𝑚 , 𝑔 .

BLS: Signatures• Eliptic curve 𝔾 with pairing e and generator 𝑔• H is a hash function that hashes into 𝔾• Setup: 𝑥 ←< ℤ* . 𝑠𝑘: 𝑥, 𝑝𝑘: 𝑔, 𝑔 .
• Sign(x,m): 𝜎 = 𝐻 𝑚 .
𝜎 is 32 bytes!
• Verify(𝑔, 𝑔 . , 𝜎,m):• 𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .
• 𝑒 𝜎, 𝑔 = 𝑒 𝐻 𝑚 . , 𝑔 = 𝑒 𝐻 𝑚 , 𝑔 . = 𝑒 𝐻 𝑚 , 𝑔 .

BLS Properties: Deterministic
m
𝐻 𝑚 .
x

No randomness,
impossible to have two valid signatures
for a message, public key pair

BLS Properties: Signature aggregation• 𝑝𝑘D , 𝑚D , 𝜎D and 𝑝𝑘E , 𝑚E , 𝜎E
• Aggregate signature 𝜎 = 𝜎D ∗ 𝜎E
• Verify(𝑔, 𝑝𝑘D , 𝑝𝑘E , 𝑚D , 𝑚E , 𝜎):• 𝑒 𝜎, 𝑔 =𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .

BLS Properties: Signature aggregation• 𝑝𝑘D , 𝑚D , 𝜎D and 𝑝𝑘E , 𝑚E , 𝜎E
• Aggregate signature 𝜎 = 𝜎D ∗ 𝜎E
• Verify(𝑔, 𝑝𝑘D , 𝑝𝑘E , 𝑚D , 𝑚E , 𝜎):• 𝑒 𝜎, 𝑔 = 𝑒 𝐻 𝑚D , 𝑝𝑘D 𝑒(𝐻(𝑚E ), 𝑝𝑘E )• 𝑒 𝜎, 𝑔 = 𝑒 𝜎D 𝜎E , 𝑔𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .

BLS Properties: Signature aggregation• 𝑝𝑘D , 𝑚D , 𝜎D and 𝑝𝑘E , 𝑚E , 𝜎E
𝑒 𝜎, 𝑔 =? 𝑒 𝐻(𝑚), 𝑔 .
• Aggregate signature 𝜎 = 𝜎D ∗ 𝜎E
• Verify(𝑔, 𝑝𝑘D , 𝑝𝑘E , 𝑚D , 𝑚E , 𝜎):• 𝑒 𝜎, 𝑔 = 𝑒 𝐻 𝑚D , 𝑝𝑘D 𝑒(𝐻(𝑚E ), 𝑝𝑘E )• 𝑒 𝜎, 𝑔 = 𝑒 𝜎D 𝜎E , 𝑔 = 𝑒 𝜎D , 𝑔 𝑒 𝜎E , 𝑔• 𝑒 𝜎D , 𝑔 = 𝑒 𝐻 𝑚D , 𝑝𝑘D• 𝑒 𝜎E , 𝑔 = 𝑒 𝐻 𝑚E , 𝑝𝑘E• 𝑒 𝜎D , 𝑔 𝑒 𝜎E , 𝑔 = 𝑒 𝐻 𝑚D , 𝑝𝑘D 𝑒 𝐻 𝑚E , 𝑝𝑘E

BLS Properties: Signature aggregation• Take n signatures under n public keys on n messages and create asingle small signature• Each Bitcoin transaction includes public key and is message• Take all Bitcoin transactions in a block and create a single signature• Take all Bitcoin transactions in the blockchain and have a singlesignature• 32 bytes!

Threshold Signature (Diagram)
Different frommultisig (1 pk)(sk1 ,…,skn ,pk )←Keygen(t,n)

pk𝜎 ←Sign(sk1 ,… ,skt ,m)m, 𝜎

Verify(pk,m, 𝜎)Threshold• Difficult for ECDSA (Gennaro et al. 16)• Easy for Schnorr, BLS• Indistinguishable from normal signature (privacy benefits)• Can support 1000s of keys/ signatures don’t grow with (t,n)

Threshold signature from Shamir secret sharing

Ring Signature (Diagram)(sk1 ,…,skn ,pk )←Keygen(t,n)

𝜎 ←Sign(ski,m)pkm, 𝜎𝜎 hides iVerify(pk,m, 𝜎)Ring Signatures• Used in Monero to hide sender• Monero’s signatures are linear in n
• Can be logarithmic in n (Bootle et al. 2015)

Blind Signature (Diagram)(sk ,pk )←Keygen(t,n)

pkcb←BlindSign(sk,c)bc=Commit(m;r)

𝜎 =Unblind(pk,b,r)s.t. Verify(pk,m, 𝜎)=1

Blind Signature
Separate Custodian fromtransaction details

Zero Knowledge Proofs of Knowledge
S U D O K U S , S N A R K S , S TA R K S A N D B U L L E T S

Zero Knowledge Proof of Knowledge“I know the solution to this complex equation”“Prove it”
ChallengeResponse

No idea what
the solution is
But Alice must
know itZero Knowledge Proof of Knowledge Applications
••••
•
••
•
•

Confidential Transactions
Mimblewimble
ZeroCash
Hawk
Zero-Knowledge contingent payments
Proofs of Solvency for Bitcoin Exchanges
Confidential Payment Channels
Blockchain compression…

SUDOKU
2173 8561 3
9 8 1
2 5 7
3 1
8982
56 9 7 8 442 5

SUDOKU
2 4 9 5 7 1 6 3 88 6 1 4 3 2 9 7 55 7 3 9 8 6 1 4 2
7 2 5 6 9 8 4 1 36 9 8 1 4 3 2 5 7
3 1 4 7 2 5 8 6 99 3 7 8 1 4 2 5 61 5 2 3 6 9 7 8 4
4 8 6 2 5 7 3 9 1

Zero-Knowledge SUDOKU”Can you help me with this Sudoku?”“If you pay me!”“Prove that you know the solution first”“Ok”

Zero-Knowledge SUDOKU (Gradwohl et al. ‘05)
2 4 9 5 7 1 6 3 88 6 1 4 3 2 9 7 55 7 3 9 8 6 1 4 2
7 2 5 6 9 8 4 1 3
6 9 8 1 4 3 2 5 73 1 4 7 2 5 8 6 99 3 7 8 1 4 2 5 61 5 2 3 6 9 7 8 44 8 6 2 5 7 3 9 11 52 63 74 15 36 97 48 89 26 1 2 3 4 5 9 7 88 9 5 1 7 6 2 4 3
3 4 7 2 8 9 5 1 64 6 3 9 2 8 1 5 7
9 2 8 5 1 7 6 3 4
7 5 1 4 6 3 8 9 22 7 4 8 5 1 6 3 95 3 6 7 9 2 4 8 1
1 8 9 6 3 4 7 2 5

Zero-Knowledge SUDOKU

Open Row 4

Zero-Knowledge SUDOKU

Open Column 2Zero-Knowledge SUDOKU

Open Box 1

Zero-Knowledge SUDOKUShow original puzzle

Zero-Knowledge SUDOKU Analysis
P[Cheating]≤

Open Row/Column/Box/Original

EFEGZero-Knowledge SUDOKU Amplifying

RepeatOpen Row/Column/Box/Original

1 try: 0.964
2 tries: 0.929
10 tries: 0.695
100 tries: 0.02
1000 tries: 2IJE

Problem: Bob learns solution

RepeatNew permutation in every round

Open Row/Column/Box/Original

1 try: 0.964
2 tries: 0.929
10 tries: 0.695
100 tries: 0.02
1000 tries: 2IJE

1 try: 0.964
2 tries: 0.929
10 tries: 0.695
100 tries: 0.02
1000 tries: 2IJE

Zero-Knowledge

RepeatNew permutation in every round

Open Row 1

1 try: 0.964
2 tries: 0.929
10 tries: 0.695
100 tries: 0.02
1000 tries: 2IJE

Zero-Knowledge

RepeatNew permutation in every round

Open Row 1

1 try: 0.964
2 tries: 0.929
10 tries: 0.695
100 tries: 0.02
1000 tries: 2IJE

Zero-Knowledge

RepeatNew permutation in every round

Open Box 2

Zero-Knowledge for public keys (Sigma protocol)
I know x such that gx =y𝑟 ← ℤ*

𝐴 = 𝑔<𝑐𝑠 =𝑟+𝑐∗𝑧𝑠𝑐 ← ℤ*𝑔 P =?

Zero-Knowledge for public keys (Sigma protocol)
I know x such that gx =y𝑟 ← ℤ*

𝐴 = 𝑔<𝑐𝑠 =𝑟+𝑐∗𝑧𝑠𝑐 ← ℤ*𝑔 P =? A ∗ y SA ∗ y S = 𝑔< ∗ 𝑔 .∗S𝑔< ∗ 𝑔 .∗S = 𝑔<T.∗S

Non-Interactive Zero-Knowledge (NIZK)I know x such that gx =y𝑟 ← ℤ*

𝐴 = 𝑔<
𝑐𝑠 =𝑟+𝑐∗𝑧𝑠𝑐 ← ℤ*𝑔 P =? A ∗ y SA ∗ y S = 𝑔< ∗ 𝑔 .∗S𝑔< ∗ 𝑔 .∗S = 𝑔<T.∗S

Non-Interactive Zero-Knowledge (NIZK)I know x such that gx =y𝑟 ← ℤ*

𝐴 = 𝑔<
𝑐𝑠 =𝑟+𝑐∗𝑧

𝑠𝑐 ← ℤ*𝑔 P =? A ∗ y S
A ∗ y S = 𝑔< ∗ 𝑔 .∗S𝑔< ∗ 𝑔 .∗S = 𝑔<T.∗S

Non-Interactive Zero-Knowledge (NIZK)I know x such that gx =y𝑟 ← ℤ*

𝐴 = 𝑔<
𝑐 = 𝐻(𝐴, 𝑦)𝑠 =𝑟+𝑐∗𝑧𝑠

𝑔 P =? A ∗ y S
A ∗ y S = 𝑔< ∗ 𝑔 .∗S𝑔< ∗ 𝑔 .∗S = 𝑔<T.∗S

Non-Interactive Zero-Knowledge (NIZK)I know x such that gx =y𝑟 ← ℤ*
𝐴 = 𝑔<
𝑐 = 𝐻(𝐴, 𝑦)𝑠 =𝑟+𝑐∗𝑧𝜋 = (𝐴, 𝑐, 𝑠)

𝑔 P =? A ∗ y S
𝑐 =? 𝐻(𝐴, 𝑦)Schnorr signature
I know x such that gx =y𝑟 ← ℤ*
𝐴 = 𝑔<
𝑐 = 𝐻(𝐴, 𝑦)𝑠 =𝑟+𝑐∗𝑧𝜋 = (𝐴, 𝑐, 𝑠)

𝑔 P =? A ∗ y S
𝑐 =? 𝐻(𝐴, 𝑦)Schnorr signature
I know x such that gx =y𝑟 ← ℤ*
𝐴 = 𝑔<
𝑐 = 𝐻(𝐴, 𝑦, 𝑀)
𝑠 =𝑟+𝑐∗𝑧

𝜎 = 𝐴, 𝑐, 𝑠 , 𝑀

𝑔 P =? A ∗ y S
𝑐 =? 𝐻(𝐴, 𝑦, 𝑀)

Sigma protocols• Good for NIZKs in public key systems• Range proofs• Proofs of solvency (Dagher et al. 15)• Not good for more complicated statements

Proofs for complex statement
I know x such that H(x)=y/This is the correct blockchain𝜋Goal: Succinct proofs
I know x such that H(x)=y/This is the correct blockchain𝜋

Proof is a 100 bytes no matter
what the statement isVerifying it takes ms

Preprocessing SNARKOpen Row 7

Preprocessing SNARK: Idea sent queries once

This can be reused
Open Row 7,Row 13, Column 4, Box 1 and the perm

Special compressionfunction to compressanswers (Pairing)Compressed response: 𝜋Preprocessing SNARK: Idea sent queries onceThis can be reused
Open Row 7,Row 13, Column 4, Box 1 and the perm

Special compressionfunction to compress
answers (Pairing)

If Alice knows queries
She can cheat

Compressed response: 𝜋Preprocessing SNARK: Encrypt queriesThis can be reused
Open Row 7,Row 13, Column 4, Box 1 and the perm

Special compressionfunction to compress
answers (Pairing)

If Alice knows queries
She can cheat

Compressed response: 𝜋Preprocessing SNARK: Encrypt queriesThis can be reused
Open Row 7,Row 13, Column 4, Box 1 and the perm

Special compressionfunction to compress
answers (Pairing)Compressed response: 𝜋Preprocessing SNARK: Trusted Setup
Encrypted
Queries

Short
Encrypted
Answers

Setup slow
Special compressionfunction to compress
answers (Pairing)
Proving slow

Compressed response: 𝜋

Verify 𝜋
Using encrypted
answers
Verification fastPreprocessing SNARK: Malicious Setup
Encrypted
Queries

Short
Encrypted
Answers

Can create cheating proofs
Special compressionfunction to compress
answers (Pairing)Compressed response: 𝜋

Verify 𝜋
Using encrypted
answersPreprocessing SNARK: Use multiple parties
Short
EncryptedAnswers

Encrypted
QueriesSpecial compressionfunction to compressanswers (Pairing)

ZCash did thisCompressed response: 𝜋

Verify 𝜋
Using encryptedanswers

PCP Theorem

Open 2 fields
PCP Theorem:
For any sized Sudoku,
P[Cheating]<= 1/3

CS-Proofs (use Fiat-Shamir) (Micali 91)

Commit:Open 2 fields=H(commit)
PCP Theorem:
For any sized Sudoku,
P[Cheating]<= 1/3

CS-Proofs (use Fiat-Shamir) (Micali 91)

Commit:Open 2 fields=H(commit)
Not practical

STARKs (Ben-Sasson 17)

Commit:Open 2 fields=H(commit)

Making strides
2DX cycles
131 GB Ram usage
1.8 MB proofs

Dreaming of STARKs• ZCash without trusted setup• Blockchain aggregation (doesn’t need Zero-Knowledge)• Confidential smart contracts• Resolving verifiers dilema• Generic verifiable computation (Outsourcing)• Very active research area but still not thereBulletproofs (Short proofs but linear verification)• Bünz et al. 17 based on Bootle et al. 16• Proofs are very short (log(n) for statement of size n)• Verification is like proving (slow)• Replacement for Sigma protocols• No trusted setup!
• Just discrete log assumption

Bulletproofs (What is it good for?)• Range proofs for confidential transactions/Mimblewimble• 670 bytes instead of 4 KB per range proof• Aggregation: Two range proofs 736 bytes vs. 8 KB
• 16 range proofs 928 bytes vs. 61KB
• Mimblewimble size: 17 GB vs 160 GB• Built in: simple CoinJoin protocol for combining confidential transactions• Solvency proofs• Verifiable shuffles• NIZKs for Smart Contracts• …
• http://web.stanford.edu/~buenz/pubs/bulletproofs.pdf

References (Signatures)••••

BLS https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
ECDSA Threshold: https://eprint.iacr.org/2016/013.pdf
BLS/Schnorr Threshold: https://dl.acm.org/citation.cfm?id=359176
Ring Signatures:https://www.iacr.org/archive/asiacrypt2001/22480516.pdf• Blind Signatures:
http://blog.koehntopp.de/uploads/Chaum.BlindSigForPayment.1982.PDF

References (Proofs)
••
••
•
•

•
•
•
•

Provisions: https://eprint.iacr.org/2015/1008.pdf
Zero-Knowledge contingent payments: http://stevengoldfeder.com/papers/ZKCSP.pdf
Zero-cash: http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf
ZK-SUDOKU: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku_abs.html
Sigma Protocols: ftp://ftp.inf.ethz.ch/pub/crypto/publications/CraDam98.pdf
SNARKs:• http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf (Groth first SNARK)• https://eprint.iacr.org/2012/215.pdf (GGPR SNARKs of today)• https://eprint.iacr.org/2013/279.pdf (Pinocchio the most used)• https://eprint.iacr.org/2013/507 (SNARKs for C)
PCPs: http://people.eecs.berkeley.edu/~alexch/classes/CS294-S2017.html
CS Proofs: https://www.computer.org/csdl/proceedings/focs/1994/6580/00/0365746.pdf
STARKs: https://cyber.stanford.edu/sites/default/files/elibensasson.pdf
Bulletproofs: http://web.stanford.edu/~buenz/pubs/bulletproofs.pdf

Thank you!
B U E N Z @ C S . S TA N F O R D . E D U

http://web.stanford.edu/~buenz/pubs/bulletproofs.pdf