Batching Techniques for Accumulators: Applications to IOPs and Blockchains
This presentation discusses batching techniques for accumulators in the context of IOPs and blockchains. It covers challenges with UTXO sets, Merkle trees, and RSA accumulators, proposing solutions and improvements. The content explores problems with Merkle trees, benefits of RSA accumulators, and efficient stateless updates within the blockchain ecosystem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Batching Techniques for Accumulators with Applications to IOPs and Blockchains Benedikt B nz Joint work with: Ben Fisch and Dan Boneh 1
UTXOs prev: 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 4
UTXO Commitments [Miller,Todd,Dryja,] prev: H( ) prev: H( ) prev: H( ) trans: H( ) utxos: H( ) trans: H( ) utxos: H( ) trans: H( ) utxos: H( ) Consensus ensures: All UTXO committed here 5
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)) UTXO UTXO UTXO UTXO 1 If sorted 6
Stateless Full Nodes/Mining prev: H( ) prev: H( ) prev: H( ) trans: H( ) utxos: H( ) trans: H( ) utxos: H( ) trans: H( ) utxos: H( ) Looks good TX: Spend UTXO 426 Proof: ? 7
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 8
RSA Accumulators [CL02 ] Setup: Choose N=pq where p, q are secret primes ?: Hash function to primes in [0, 2?] ?0= ? ??(initial state) State after set S added: Add(??,x) ??+1= ?? ?(?) u= ? ?? ??= ?? Del(??,x) ??+1= ?? 1/?(?) 9
Accumulator Proofs InclusionProof(A,x): 1 ? ? Computed using trapdoor(p,q) Or ?( ? ) ? = ? Verify(A,x,?) ??= ? Efficient stateless updates: [LiLiXue07] Exclusion(A,x) ? = ?? ? ? + ? ? = gcd(?,?)=1 See [LiLiXue07] 10
RSA = Trusted Setup? N=p*q, p,q unknown Efficient delete needs trapdoor You can find Ns in the wild (Ron Rivest Assumption) 11
Class Groups [BW88,L12] CL( ) - Class group of quadratic number field = ? (a large random prime) Properties Element representation: integer pairs (?,?) ? ? No trusted setup Tasks believed to be hard to compute: Odd prime roots Group order 1536 ???? 128 bit security 12
RSA Accumulator State of Art Positives 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 13
Aggregate Inclusion Proofs ? ???? ? ?????: ? ? + ? ? = 1 ?1,2= ?1 ? ?= ? ?= ? ?= ?,?2 ?1,2 ?1 ??2 ? All inclusion proofs per block: 1.5kb All inclusion proofs ever: 160GB -> 1.5kb 14
Stateless Deletion Delete with trapdoor(??,?): 1 ? Using knowledge of p, q ??+1= ?? Delete with inclusion proof(At,x,?) ??+1= ?; ? ? ? = g BatchDelete(At,x,y,?1,?2) Compute ?1,2 s.t. ?1,2 ??+1= ?1,2 ? y= ?? No State, no Trapdoor, asynchronous 15
Too slow? Openssl 2048 bit RSA: 219 updates per second Verification/Full sync would be problematic Class groups: No good benchmarks yet 16
Wesolowski Proof [Wesolowski18] ?,?,? :?2?= ? y Peggy Random ? bit prime Victor Computes q,r s.t. 2?= ? + ? and 0 ? < Computes ? = 2? ??? Checks: ? ??= ? ?? ??= ?2? ? = ??
Proof of Exponentiation (PoE) ?,?,? :??= ? y Peggy Random ? bit prime Victor Computes q,r s.t. ? = ? + ? and 0 ? < Computes ? = ? ??? Checks: ? ??= ? ?? ??= ?? ? = ??
PoE Efficiency ?,?,? :??= ? Direct Verification: ??= ? ? PoE Verify: ? = ? ??? ? ???? Exponentiation in ? vs. 128 bit long-division: 5000x difference for 128 bit security 19
Fast Block Verification Header: TXs: Spent s, new N BLS ? ??+1 2,??+1,??? ??+1 Verify ? Remove s ?? 2 ? ??= At) Verify PoE(??+1 ? ??= At+1) ??+1 2 Add N ??+1 PoE(??+1 2 2 20
Performance Macbook, Java BigInteger, JDK Hash Merkle Tree: 26 x SHA-256: 8.5 ?s Add: gx mod N, |x|=256 bit |N|=3072: 1535 ?s Verify: xmod l, |x|=256 bit |l|=128 bit 0.3 ?s Classgroups? 21
Proof of Exponentiation (PoE) ?,?,? :??= ? y Peggy Random ? bit prime Victor Computes q,r s.t. ? = ? + ? and 0 ? < Computes ? = ? ??? Checks: ? ??= ? ?? ??= ?? ? = ?? V knows x
Knowledge of Exponent (PoKE*) ?;? :??= ? g is encoded in CRS y Peggy Random ? bit prime Victor Computes q,r s.t. ? = ? + ? and 0 ? < Checks: ? = ??,? ? ? ??= ? ?? ??= ?? ? rational -> ? ???
Knowledge of Exponent (PoKE) ?,?;? :??= ? ?,? = ?? Peggy Random ? bit prime Victor Computes q,r s.t. ? = ? + ? and 0 ? < Checks: ??= ??,??= ??,? ? ?? ?? ??= ? ??= ?
Vector Commitments Merkle trees are VCs not just accums! VC=Commit( ) ?1,?2,?3, ,?? Classical VCs: Linear CRS ? =Open(VC,??,?) New VCs: Constant CRS, batch openings Built from PoKE and batch proofs Verify(??,?,??,?) = {0,1} 25
Short IOPs (STARKs etc.) MT=Commit( ) Long Proof ?1, ,?? ??1, ,??? and Merkle Paths 26
Short IOPs (STARKs etc.) VC=Commit( ) Long Proof ?1, ,?? 200kb vs. 600kb ??1, ,??? and 1 VC Opening 27
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-txo- commitments#further-work MMR: https://github.com/opentimestamps/opentimestamps- server/blob/master/doc/merkle-mountain-range.md UTXO: https://bitcointalk.org/index.php?topic=101734.0 BW88: Buchmann and Williams 29
