A go implementation of Verkle trees

Overview

go-verkle

A very experimental implementation of Verkle trees. When production-ready, the code is to be split between go-kzg and go-ethereum.

Notes

  • Nodes have 1024 children. More size should be supported, but it hasn't been tested. #7946dbeb
  • Generated proofs are currently incorrect. #794f78fb
  • Proofs are given in pi and rho form, not sigma form #79570617

Running the tests

$ go test .

The test called TestProofVerifyTwoLeaves is currently broken, all other tests should pass.

Comments
  • Figure out why Kilic is so slow

    Figure out why Kilic is so slow

    A mainnet tree conversion with kilic is ~2x as slow as with herumi. I doubt it's entirely due to the library being slower. This is a tracking issue to figure out if the problem is indeed on the kilic side or if it's based on our usage of it.

    question 
    opened by gballet 6
  • kililc give different commitments depending on the value of multiExpThreshold

    kililc give different commitments depending on the value of multiExpThreshold

    multiExpThreshold == 45:

    INFO [05-18|19:42:21.287] Iterating state snapshot                 accounts=114215117 slots=400207177 elapsed=12h21m26.912s eta=2.205s
    INFO [05-18|19:42:21.537] Iterated snapshot                        accounts=114215117 slots=400223042 elapsed=12h21m27.162s
    INFO [05-18|19:42:21.537] Computed verkle tree                     root hash="542518…3afdb6"
    INFO [05-18|19:42:21.539] Number of nodes written to DB
               nodes=174639610
    

    multiExpThreshold == 20:

    INFO [05-19|04:00:27.202] Iterating state snapshot                 accounts=114215117 slots=400208359 elapsed=15h45m18.981s eta=3.19s
    INFO [05-19|04:00:27.785] Iterated snapshot                        accounts=114215117 slots=400223042 elapsed=15h45m19.564s
    INFO [05-19|04:00:27.785] Computed verkle tree                     root hash="2c9607…dcf64f"
    INFO [05-19|04:00:27.787] Number of nodes written to DB
               nodes=689077769
    

    Looks the same number of nodes didn't get written to othe db, which certainly explains the time difference. Is it also the reason for obtaining different roots?

    bug 
    opened by gballet 5
  • Unrelated tests failing in geth CI

    Unrelated tests failing in geth CI

    See [this build failure]https://ci.appveyor.com/project/ethereum/go-ethereum/builds/41512143/job/ef4490waxtngwnpy)

    For instance, we have the following issues:

    --- FAIL: TestCheckpointRegister (0.01s)
    panic: undefined value in witness [recovered]
    	panic: undefined value in witness
    goroutine 11 [running]:
    

    Other tests point to an uninitialized AccessWitness

    bug 
    opened by gballet 4
  • BlockCancun commit had to be reverted after switch to IPA

    BlockCancun commit had to be reverted after switch to IPA

    After the switch to IPA, the changes introduced in 688952b18b56dcdcf1bb90ab7646b1a8f330214f seem to no longer work.

    In particular, the following command

    rm -rf .verkle && go build -tags bignum_kilic ./cmd/geth/... && ./geth init genesis_verkle.json && ./geth --datadir=.verkle --nodiscover --mine --miner.threads=1 --http --http.corsdomain="*" --networkid 86 --http.rpcprefix="/verkle" --miner.etherbase=0x617661d148A52bef51a268C728b3A21B58f94306
    

    fails during the init stage, because it tries to (de)serialize a verkle node as a regular MPT node. Not sure why this failed, but I had to revert it in d95451bdba7a4ebc825e7423e01ad0f0af4ffe6d in order to be able to run it.

    bug 
    opened by gballet 4
  • Contract creation fails

    Contract creation fails

    Sending a transaction to create a contract causes a panic:

    panic: trying to produce a commitment for an empty subtree
    
    goroutine 62 [running]:
    github.com/gballet/go-verkle.Empty.GetCommitmentsAlongPath(...)
    	/home/gballet/go/pkg/mod/github.com/gballet/[email protected]/tree.go:857
    github.com/gballet/go-verkle.(*InternalNode).GetCommitmentsAlongPath(0xc0006ac410, {0xc0128788c0, 0x20, 0x20})
    	/home/gballet/go/pkg/mod/github.com/gballet/[email protected]/tree.go:580 +0xcc
    github.com/gballet/go-verkle.GetCommitmentsForMultiproof({0x75ad18, 0xc0006ac410}, {0xc00030b040, 0xd, 0xd})
    	/home/gballet/go/pkg/mod/github.com/gballet/[email protected]/proof.go:189 +0x20a
    github.com/gballet/go-verkle.MakeVerkleMultiProof({0x75ad18, 0xc0006ac410}, {0xc00030b040, 0xd, 0xd})
    	/home/gballet/go/pkg/mod/github.com/gballet/[email protected]/proof.go:207 +0xc5
    github.com/ethereum/go-ethereum/trie.(*VerkleTrie).ProveAndSerialize(0xc0000c0768, {0xc00030b040, 0xd, 0xd}, 0xc012d8cba0)
    	/usr/home/gballet/src/go-ethereum/trie/verkle.go:187 +0x76
    github.com/ethereum/go-ethereum/miner.(*worker).commit(0xc0000b1b00, {0xc0000709a0, 0x0, 0x2}, 0x0, 0x1, {0xc056bd6b867e7087, 0xbac6fadd9d5, 0x20f5c40})
    	/usr/home/gballet/src/go-ethereum/miner/worker.go:1038 +0x22d
    github.com/ethereum/go-ethereum/miner.(*worker).commitNewWork(0xc0000b1b00, 0xc012631f98, 0x1, 0x617a7e16)
    	/usr/home/gballet/src/go-ethereum/miner/worker.go:1022 +0x13c5
    github.com/ethereum/go-ethereum/miner.(*worker).mainLoop(0xc0000b1b00)
    	/usr/home/gballet/src/go-ethereum/miner/worker.go:460 +0x505
    created by github.com/ethereum/go-ethereum/miner.newWorker
    	/usr/home/gballet/src/go-ethereum/miner/worker.go:232 +0x817
    
    bug 
    opened by gballet 3
  • Proof verification fails at higher powers of z

    Proof verification fails at higher powers of z

    VerifyVerkleProof seems unable to accept proofs made by MakeVerkleProofOneLeaf when the polynomial is at a higher degree.

    In practice, the values generated for y_is in the verifier are different from the ones generated in the prover. Injecting the y_is from the prover into the verifier solve the problem.

    bug 
    opened by gballet 3
  • Measure impact of Bandersnatch optimizations in go-verkle

    Measure impact of Bandersnatch optimizations in go-verkle

    This PR is only to show and test further the impact of the optimization I proposed in https://github.com/crate-crypto/go-ipa/pull/18 for this repo, since most of the heavy lifting comes from using that dependency for the Bandersnatch elliptic curve implementation.

    Here's a bench comparison between master (i.e: current Bandersnatch implementation):

    name                                        old time/op    new time/op    delta
    ProofCalculation-16                            18.2s ± 1%      6.6s ± 1%  -63.85%  (p=0.002 n=5+8)
    ProofVerification-16                          34.9ms ± 1%    30.3ms ± 1%  -13.23%  (p=0.002 n=5+8)
    CommitLeaves/insert/leaves/1000-16             212ms ± 3%      81ms ± 2%  -62.04%  (p=0.002 n=5+8)
    CommitLeaves/insertOrdered/leaves/1000-16      214ms ± 0%      81ms ± 1%  -62.31%  (p=0.002 n=5+8)
    CommitLeaves/insert/leaves/10000-16            2.10s ± 0%     0.77s ± 1%  -63.37%  (p=0.006 n=4+7)
    CommitLeaves/insertOrdered/leaves/10000-16     2.13s ± 1%     0.78s ± 1%  -63.52%  (p=0.002 n=5+8)
    CommitFullNode-16                             40.6ms ± 2%    14.9ms ± 2%  -63.36%  (p=0.002 n=5+8)
    ModifyLeaves-16                                2.72s ± 1%     1.64s ± 0%  -39.74%  (p=0.003 n=5+7)
    
    name                                        old alloc/op   new alloc/op   delta
    ProofCalculation-16                           5.05GB ± 0%    2.75GB ± 0%  -45.56%  (p=0.002 n=5+8)
    ProofVerification-16                          7.48MB ± 0%    0.17MB ± 0%  -97.72%  (p=0.004 n=5+6)
    CommitLeaves/insert/leaves/1000-16            58.8MB ± 0%    34.2MB ± 0%  -41.81%  (p=0.002 n=5+8)
    CommitLeaves/insertOrdered/leaves/1000-16     58.9MB ± 0%    34.3MB ± 0%  -41.77%  (p=0.002 n=5+8)
    CommitLeaves/insert/leaves/10000-16            562MB ± 0%     324MB ± 0%  -42.32%  (p=0.002 n=5+8)
    CommitLeaves/insertOrdered/leaves/10000-16     563MB ± 0%     325MB ± 0%  -42.28%  (p=0.002 n=5+8)
    CommitFullNode-16                             13.4MB ± 0%     8.0MB ± 0%  -40.38%  (p=0.002 n=5+8)
    ModifyLeaves-16                                740MB ± 0%     319MB ± 0%  -56.83%  (p=0.002 n=5+8)
    
    name                                        old allocs/op  new allocs/op  delta
    ProofCalculation-16                            30.0M ± 0%      1.3M ± 0%  -95.68%  (p=0.003 n=5+7)
    ProofVerification-16                            115k ± 0%        1k ± 0%  -99.28%  (p=0.003 n=5+7)
    CommitLeaves/insert/leaves/1000-16              328k ± 0%       15k ± 0%  -95.39%  (p=0.002 n=5+8)
    CommitLeaves/insertOrdered/leaves/1000-16       331k ± 0%       18k ± 0%  -94.56%  (p=0.000 n=5+8)
    CommitLeaves/insert/leaves/10000-16            3.18M ± 0%     0.14M ± 0%  -95.50%  (p=0.002 n=5+8)
    CommitLeaves/insertOrdered/leaves/10000-16     3.21M ± 0%     0.17M ± 0%  -94.64%  (p=0.002 n=5+8)
    CommitFullNode-16                              71.2k ± 0%      3.3k ± 0%  -95.36%  (p=0.002 n=5+8)
    ModifyLeaves-16                                5.95M ± 0%     0.22M ± 0%  -96.32%  (p=0.002 n=5+8)
    

    TL;DR for proof calculation:

    • A reduction of 63.85% in computation time, most coming from avoiding 95.68% allocations.
    • Indirectly, we reduced 45.56% memory usage.

    TL;DR for proof verification:

    • A reduction of 13.23% in computation time, most coming from avoiding 99.28% allocations.
    • Indirectly, we reduced 97.72% memory usage.

    I wonder if there's any other way the performance of this repo is being measured. This branch is totally open to exploring that if feels that the work on the elliptic curve implementation can be considered to be merged.

    opened by jsign 2
  • Helper functions for flushing nodes to disk during conversion

    Helper functions for flushing nodes to disk during conversion

    In order not to run out of memory, be a tad more aggressive when flushing a node. This means that deeper nodes will have to be reloaded from the DB, but the memory should remain below 16GB.

    This is one of 3 methods that are considered. The other two will receive their own PRs.

    opened by gballet 2
  • Question about make and verify proof

    Question about make and verify proof

    Thanks for the implementation of verkle tree. It is very helpful for me to understand how verkle tree works.

    I have some questions about how to correctly make and verify proof (using MakeVerkleMultiProof and VerifyVerkleProof).

    How can I commit to a leaf node (value) and verify its proof? Say if the verifier only has root.ComputeCommitment(), and then the prover send them the (key, value) pair and its proof. How could the verifier make sure the (key, value) is valid?

    opened by saideng 2
  • ensure that IsCancun is used as much as possible

    ensure that IsCancun is used as much as possible

    In many instances, evm.txContext.Accesses != nil can be replaced by a call to IsCancun(), we should strive for using this, in order to make it easier for reviewers to figure out that this code will not activate outside of a verkle tree-enabled context, even if Accesses are somehow activated.

    opened by gballet 2
  • rebuild stateless tree from proof

    rebuild stateless tree from proof

    PR #144 implements a stateless verkle tree, but is missing the critical feature of rebuilding the tree from a proof. Modify the API to be able to do this.

    enhancement 
    opened by gballet 2
  • Rename ComputeCommitment to Commitment

    Rename ComputeCommitment to Commitment

    This PR is the first step in implementing batch inserts. It cleans up the API by separating the commitment getter from the function compuring it (code sold separately).

    TODO

    • [ ] Rewrite InsertStemOrdered to support diff-insert, so it no longer relies on ComputeCommitment to get its value
    opened by gballet 0
  • perform batch insertions

    perform batch insertions

    With InsertAtStem, multiple values are inserted into the same extension-and-suffix-tree. This is nice, because the cost of updating the commitments along the path are shared.

    Insertions should be batched so that the same technique can be used at all levels, and particularly at the root.

    enhancement 
    opened by gballet 0
  • save on commitment calculations when inserting multiple intermediate branch nodes

    save on commitment calculations when inserting multiple intermediate branch nodes

    The recursive algorithm has the problem that, in a differential insertion context, a recursive insertion requires the creation of a commitment that needs to be updated immediately. This is costly and should be avoided.

    enhancement 
    opened by gballet 0
  • Measure performance with only 2 account header leaves instead of 5

    Measure performance with only 2 account header leaves instead of 5

    In verkle trees, the account header consists of 5 leaves (version, balance, nonce, code keccak and code size), each of which takes 32 bytes. This means that calculating the commitment of a value costs at least 10 exponentiations (each value is split in 2 16-bytes value). Most of these values do not require 32 bytes (version, nonce, code size, let alone balance), and it would therefore be possible to pack some of them into a single 32-byte value in order to save on exponentiation costs.

    enhancement 
    opened by gballet 0
  • remove committer from node

    remove committer from node

    The commiter is a singleton, and KZG are no longer seriously considered as a candidate for verkle trees. Other parts of the code have already been simplified and only accept IPA-based primitives. The committer is a leftover from the time that it was possible to use both KZG commitments and IPA. It no longer makes sense to maintain this interface, and therefore readability would be improved if all references to it were removed from the code.

    enhancement 
    opened by gballet 0
Releases(banderwagonv2)
  • banderwagonv2(Jun 30, 2022)

    The curve was changed from Bandersnatch to Banderwagon. This release provides the pre-computed Lagrange points. Drop the precomp file in the directory that your program is running in, in order to avoid the file generation on the first run.

    Source code(tar.gz)
    Source code(zip)
    precomp(127.51 MB)
  • banderwagon(May 26, 2022)

    The curve was changed from Bandersnatch to Banderwagon. This release provides the pre-computed Lagrange points. Drop the precomp file in the directory that your program is running in, in order to avoid the file generation on the first run.

    Source code(tar.gz)
    Source code(zip)
    precomp(127.51 MB)
Owner
Guillaume Ballet
Guillaume Ballet
A Left-Leaning Red-Black (LLRB) implementation of balanced binary search trees for Google Go

GoLLRB GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language. Overview As of this writing and to

Petar Maymounkov 733 Sep 24, 2022
Golang implementation of Radix trees

go-radix Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Armon Dadgar 752 Sep 26, 2022
A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees

radixs A Go implementation of a radix tree, that uses binary searches to speed up insert, retrieve and delete operations on dense trees. This implemen

Bruno Moura 0 Feb 14, 2022
Adaptive Radix Trees implemented in Go

An Adaptive Radix Tree Implementation in Go This library provides a Go implementation of the Adaptive Radix Tree (ART). Features: Lookup performance s

Pavel Larkin 246 Sep 16, 2022
Generic types that are missing from Go, including sets, trees, sorted lists, etc.

go-typ Generic types that are missing from Go, including sets, trees, sorted lists, etc. All code is implemented with 0 dependencies and in pure Go co

null 14 Jul 26, 2022
A generic Go library for implementations of tries (radix trees), state commitments and proofs of inclusion

trie.go Go library for implementations of tries (radix trees), state commitments and proof of inclusion for large data sets. It implements a generic 2

IOTA 5 Aug 3, 2022
Go implementation of Count-Min-Log

Count-Min-Log Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier TL;DR: Count-Min-Log Sketch

Seif Lotfy 58 Sep 26, 2022
A Go implementation of the Elias-Fano encoding

go-ef A Go implementation of the Elias-Fano encoding Example package main import ( "fmt" "github.com/amallia/go-ef" "os" ) func main() {

Antonio Mallia 24 Sep 26, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 49 Aug 2, 2022
A skip list implementation in Go

About This is a library implementing skip lists for the Go programming language (http://golang.org/). Skip lists are a data structure that can be used

Ric (Ryszard) Szopa 236 Sep 21, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 165 Sep 26, 2022
Go implementation to calculate Levenshtein Distance.

levenshtein Go package to calculate the Levenshtein Distance The library is fully capable of working with non-ascii strings. But the strings are not n

Agniva De Sarker 236 Sep 30, 2022
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 377 Sep 24, 2022
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 28 Aug 22, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 128 Sep 26, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 21 Jul 22, 2022
A Go library for an efficient implementation of a skip list: https://godoc.org/github.com/MauriceGit/skiplist

Fast Skiplist Implementation This Go-library implements a very fast and efficient Skiplist that can be used as direct substitute for a balanced tree o

Maurice Tollmien 227 Sep 7, 2022
A slice-based implementation of a stack. In Go!

Stackgo Stackgo is a slice-based implementation of a simple stack in Go. It uses a pre-alloc pagination strategy which adds little memory overhead to

Alessandro Diaferia 15 Dec 13, 2021
gtreap is an immutable treap implementation in the Go Language

gtreap gtreap is an immutable treap implementation in the Go Language Overview gtreap implements an immutable treap data structure in golang. By treap

Steve Yen 84 May 17, 2022