A Unicorn Walks Into A Bar…

1

Or….

Accumulators for UTXOs
Benedikt Bünz
Joint work with:Ben Fisch and Dan Boneh2

Stanford Blockchain Conference• (Formerly BPASE)• Conference: Jan. 30 - Feb 1, 2019. (three days)• Only technical submissions• Submission: October 16th, 2018
• https://cyber.stanford.edu/sbc19• Videos: https://tinyurl.com/bpasevideos• Part of the Stanford Center for Blockchain Research(@CBRStanford)

UTXO Set: A Growing Problem

4

UTXOsprev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )Look up TXO from head:O(n) block headers (O(log(n) with Flyclient)
UTXO

Look up UTXO: All transactions

5

UTXO Commitments [Miller,Todd,Dryja,…]
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )utxos: H( )utxos: H( )utxos: H( )Consensus ensures:
All UTXO committed here6

Merkle Trees
prev: H( )trans: H( )utxos: H( )Inclusion: O(log(n))

H( ) H( )Exclusion: O(log(n))1

H( ) H( )H( ) H( )Update: O(log(n))
1 If sorted

UTXO

UTXO

UTXO

UTXO
7

Stateless Full Nodes/Mining
prev: H( )prev: H( )prev: H( )trans: H( )trans: H( )trans: H( )utxos: H( )utxos: H( )utxos: H( )TX:
Spend UTXO 426
Proof: !

Looks good8

Problems with Merkle Trees• Log(n) inclusion proof per transaction• Inclusion proofs can hardly be aggregated• 600 GB naïvely
• 160 GB with many optimizations• Verification not that cheap• Full node sync too slow
• Proposed for only old transactions
9

RSA Accumulators [CL02 …]
Setup:• Choose N=pq where p, q are secret primes• !: Hash function to primes in [0, 2# ]• $% = ' ∈ )* (initial state)
Add($+ , x)0(2)• $+./ = $+Del($+ , x)//0(2)• $+./ = $+State after set S added:

u= ∏7∈8 9$: = ' ;10Accumulator Proofs
InclusionProof(A,x):$%• !=# ∈'• Computed using trapdoor(p,q) Or (( * )Verify(A, x, !)• !/ = #Efficient stateless updates:[LiLiXue07]

Exclusion(A, x)• # = 01• 2 ⋅ 4 + 6 ⋅ 7 = gcd(4, 7)=1 See [LiLiXue07]
11

RSA = Trusted Setup?
N=p*q, p,q unknown

Efficient delete needs trapdoor
You can find Ns in the wild
(Ron Rivest Assumption)
12

Class Groups [BW88,L12]
CL(Δ       ℚ
Δ = −% (a large random prime)

ΔProperties• Element representation: integer pairs (', ))' ≈ ) ≈ −Δ
No trustedsetup• Tasks believed to be hard to compute:
Odd prime roots
Group order• Δ ≈ 1536 )012 ⇒ 128 bit security

13

RSA Accumulator State of ArtPositives• Constant size inclusion proofs (≈ 3000 bits)
Better than Merkle tree for set size > 4000
• Dynamic stateless adds (can add elements w/o knowing set)
• Decentralized storage (no need for full node storage)
Ø Users maintain their own UTXOs and membership proofs
Room for improvement? This work
• Aggregate/batch inclusion proofs (many at cost of one)
• Stateless deletes• Faster (batch) verification
14

Aggregate Inclusion Proofs(!"# = %, !' = %)ℎ+,-. / 0 1.-23:+⋅5+7⋅8 =1!",' = !": !';#⋅(!",' = %All inclusion proofs per block: 1.5kb
All inclusion proofs ever: 160GB -> 1.5kb
15

Stateless Deletion
Delete with trapdoor(!" , $):*+• %&'( = %&Delete with inclusion proof(A- , x, /)• %&'( = /;BatchDelete(A- , x, y, /(, /1)
2⋅4• Compute /(,1 s.t. /(,1 = %&• %&'( = /(,1Using knowledgeof p, q6/ = g2

No State,no Trapdoor,
asynchronous16

Too slow?
• Openssl 2048 bit RSA:
• 219 updates per second• Verification/Full sync would be problematic• Class groups: No good benchmarks yet

17Wesolowski Proof [Wesolowski’18]'!, #, $ : ! & = #yPeggy
Computes
q,r s.t.
2+ = , ⋅ . + 0 and0≤0<.

Random ) bit prime l
4 = !5VictorComputes
0 = 2+ 678 .
Checks:49!: = #'! 5⋅9 ! : = ! &Proof of Exponentiation!, #, $ : ! & = #yPeggy
Computes
q,r s.t.
$ = ) ⋅ + + - and 0 ≤-<+

Random ( bit prime l
1 = !2

VictorComputes- = $ 345 +Checks:16!7 = #! 2⋅6 ! 7 = ! &Proof of Exponentiation Efficiency!, $, ( : ! " = $Direct
Verification:!" = $ ∈ &PoE Verify:* = ( +,- .
/ 0 12

Exponentiation in & vs. 128 bit long-division:
5000x difference for 128 bit security
20Fast Block Verification
Header:TXs: Spent s, new N
BLS *!
!"!

$"#%

Remove s
Add N!

$"#%!"#$, '()$, !
"#% "#$

Verify *∏.∈0 1
Verify PoE(! + = A4 )"#,∏5∈6 7PoE(!

+"#,= A4#$)21

Performance
Macbook, Java BigInteger, JDK HashMerkle Tree: 26 x SHA-256:
8.5 !sAdd: gx mod N, |x|=256 bit |N|=3072:
1535 !sVerify: x mod l, |x|=256 bit |l|=128 bit
0.3 !sClassgroups?

22

Vector Commitments
VC=Commit( !", !$, !%, … , !' )( =Open(VC,!* , +)Verify(,-, (, !* , +) = {0,1}

Merkle trees
are VCs notjust accums!
Classical VCs: Verifier
requires GBs of memory
New VCs: Zero-memory
23

Short IOPs (STARKs etc.)

MT=Commit(Long Proof)!", … , !%&'( , … , &') and Merkle Paths
24Short IOPs (STARKs etc.)

VC=Commit(Long Proof)!", … , !%&'( , … , &') and 1 VC Opening

200kb
vs.
600kb
25

A Unicorn Walks Into A Bar…
Accumulators, Unions, Wesolowski, IOPs, Aggregation and Blockchains26

References• CL02: Camenisch Lysanskaya 2002 Dynamic Accumulators• LiLiXue07: Li, Li, Xue 2007 Universal Accumulators• CF: Catalone Fiore: Vector Commitments• Todd: https://petertodd.org/2016/delayed-txocommitments#further-work• MMR:
https://github.com/opentimestamps/opentimestampsserver/blob/master/doc/merkle-mountain-range.md• UTXO: https://bitcointalk.org/index.php?topic=101734.0• BW88: Buchmann and Williams27