ethereum / go-verkle Goto Github PK

View Code? Open in Web Editor NEW

192.0 16.0 50.0 1.37 MB

A go implementation of Verkle trees

License: The Unlicense

Go 99.89% MATLAB 0.11%

go-verkle's Introduction

go-verkle

A Go implementation of Verkle Tree datastructure defined in the spec.

Test & Benchmarks

To run the tests and benchmarks, run the following commands:

$ go test ./...

To run the benchmarks:

go test ./... -bench=. -run=none -benchmem

Security

If you find any security vulnerability, please don't open a GH issue and contact repo owners directly.

LICENSE

License.

go-verkle's People

Contributors

Stargazers

Watchers

go-verkle's Issues

should the commitment be stored into the db along with its hash?

In the db, an internal node is serialized as its hash, as a reference to a different node. When that internal node is reloaded, only the hash of its children is available. This is a problem if the commitment of a child node need to be accessed without loading that child node.

My gut feeling is that this can't happen. This issue serves as a reminder to ensure that is the case.

rebase branch after the merge of "the merge" PR

Depends on gballet/go-ethereum#39, which touches the same location - no need to force a rebase in that PR as well.

Update proof format to that of rust-verkle

`TestProcessStateless` failing

panic: verkle payload is too short, need at least 160 and only have 137, payload = 024c45c4a3ff68689f9fbabb787c0346a6e381993bb6f20dc7a7798dfe4bce85f000000000000000000000000000000000000000000000000000000000000000000de08490dd58e6320000000000000003000000000000000000000000000000000000000000000000c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (verkle payload is too short) [recovered]
        panic: verkle payload is too short, need at least 160 and only have 137, payload = 024c45c4a3ff68689f9fbabb787c0346a6e381993bb6f20dc7a7798dfe4bce85f000000000000000000000000000000000000000000000000000000000000000000de08490dd58e6320000000000000003000000000000000000000000000000000000000000000000c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 (verkle payload is too short)

goroutine 25 [running]:
testing.tRunner.func1.2(0xa005c0, 0xc000033ae0)
        /usr/local/go/src/testing/testing.go:1143 +0x332
testing.tRunner.func1(0xc000083b00)
        /usr/local/go/src/testing/testing.go:1146 +0x4b6
panic(0xa005c0, 0xc000033ae0)
        /usr/local/go/src/runtime/panic.go:965 +0x1b9
github.com/ethereum/go-ethereum/core.GenerateVerkleChain.func1(0x0, 0xc00010c120, 0xc0000b4000, 0x6f8ce080ccea15ff, 0xbbead0, 0xc0000bf620, 0x0)
        /datadrive/projects/go-ethereum-verkle/core/chain_makers.go:316 +0xae5
github.com/ethereum/go-ethereum/core.GenerateVerkleChain(0xc0000c8b00, 0xc00010c120, 0xbc2fd8, 0xc0001162a0, 0xbc4918, 0xc000119dc0, 0x1, 0xc000107e40, 0x0, 0x0, ...)
        /datadrive/projects/go-ethereum-verkle/core/chain_makers.go:338 +0x2b5
github.com/ethereum/go-ethereum/core.TestProcessStateless(0xc000083b00)
        /datadrive/projects/go-ethereum-verkle/core/state_processor_test.go:367 +0x82d
testing.tRunner(0xc000083b00, 0xb109a0)
        /usr/local/go/src/testing/testing.go:1193 +0xef
created by testing.(*T).Run
        /usr/local/go/src/testing/testing.go:1238 +0x2b3
exit status 2
FAIL    github.com/ethereum/go-ethereum/core    0.923s

Implement proofs of absence

This depends on #105, and is one of the two fixes needed for #108. At the moment, proving a missing key will panic. This should not happen, and in place the proof should prove that one of the child has commitment 0.

Charge witness write costs

ensure pedersen_commitments replace sha256

decomission to32

to32 was introduced during the switch from KZG to IPA. It presents the problem that, when the value is 0 and no bytes are used, it will panic. Fr.ToBytes() is preferred.

Invalidate cached commitment only when necessary

In #33 we invalidate the cached commitment as soon as an insertion/modification operation is started, even if it isn't successful or ends in a modified tree.

How should the commitments be serialized in r calculation?

In the current code base, during the calculation of r, commitment C_n is serialized as H(serialize(C_n)). To my knowledge, this hasn't been specified anywhere, hence this tracking issue.

Upgrade go-kzg to use the primitive root 7 instead of 5

Investigate why bignum_hbls fails

Using -tags bignum_kilic works, and -tags bignum_hbls doesn't (this is the default behavior).

An hypothesis is that bls.FrFrom32 will not correctly process hashes whose u256 values are above the modulus.

Move AccessWitness to StateDB

Place the start of the storage and code chunks into the account suffix tree

The EIP reserves 128 leaves in the account suffix tree for the first 128 chunks of storage, and 64 chunks for the first 64 chunks of code. This isn't implemented at the moment.

cleanup PR before merge back into geth

Remove all the TODOs and address the "notes to self"

Slice bounds out of range when chunking code at contract creation time

Stacktrace, courtesy @jwasinger:

ERROR[10-28|07:17:54.980] RPC method eth_sendTransaction crashed: runtime error: slice bounds out of range [:31] with capacity 5
goroutine 142 [running]:
github.com/ethereum/go-ethereum/rpc.(*callback).call.func1(0xc001aa42e8, 0x13, 0xc00109fd58)
        github.com/ethereum/go-ethereum/rpc/service.go:200 +0xbd
panic(0x15d7d40, 0xc001aa4660)
        runtime/panic.go:965 +0x1b9
github.com/ethereum/go-ethereum/core/vm.(*EVMInterpreter).Run(0xc001a22400, 0xc001a6e540, 0x0, 0x0, 0x0, 0x14200, 0x0, 0x0, 0x0, 0x0, ...)
        github.com/ethereum/go-ethereum/core/vm/interpreter.go:227 +0x14bc
github.com/ethereum/go-ethereum/core/vm.(*EVM).create(0xc00132b500, 0x18f2d40, 0xc001aa4540, 0xc00109e980, 0x14263, 0xc001a9af80, 0x7c527789dd18b7e, 0xb0796ad971d3b4e, 0xf03795c2af, 0x440c5b, ...)
        github.com/ethereum/go-ethereum/core/vm/evm.go:479 +0x7bb

Properly handle witness touching for EVM code executing in EOA context

Do not accumulate executing EVM bytecode into the witness while in the context of the contract-deployment call.

onLeaf callback isn't called in (*VerkleTrie).Commit

As described here, the onLeaf callback isn't called in (*VerkleTrie).Commit. This ins't ciritcal as I believe it's only used for metrics accounting, but it is still necessary to fix it before merging into master.

proof of absence: add missing case in which a stem is present

The only type of proof of absence that currently exists, is that where a child is missing in an InternalNode. There is also a case in which a LeafNode is present, but the stems are different, i.e. n.key != key.

fix invalid inserted merkle root in verkle miner test

From the source code:

		// TODO this produces invalid merkle roots when attempting to insert.
			// investigate.
			if _, err := chain.InsertChain([]*types.Block{block}); err != nil {
				t.Fatalf("failed to insert new mined block %d: %v", block.NumberU64(), err)
			}
			*/

Sending a zero-valued transaction panics

This is due to the fact that a state object whose value doesn't change, will not cause a tree update in updateStateObject, but the AccessWitness will contain the key and so an attempt will be made to create a proof for this leaf.

Include witnesses for Uncle blocks

The miner should also touch/access the necessary witnesses for the receipients of uncle block rewards.

Use a pool of hashers

In the current codebase, a new hasher is allocated every time a hash needs to be computed. Use the pool from geth instead.

Ensure that witness costs are charged per-tx and not per-block

The EIP definitions have changed, and the witness costs have to be charged per-transaction. We need to ensure that this is what the code does, because the old behavior was to charge said costs per-block.

Tests fail with go-kzg version > v0.0.0-20210303133630-8ecf92125769

I had to revert c5459480173d2fb25acfb293633d78afbc35bd58 because of this. To be investigated.

Make sure verkle witness building is only enabled if Geth is constructing blocks with Cancun activated.

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

type inheritance breaks golangci-lint

The linter in geth fails with the following messages. Most of them (presumably all of them, I haven't confirmed that) come from the following situation:

type A struct {
 // some fields
}

func (a *A) SomeMethod() {
 // some code
}

type B struct {
  *A
  // more fields
}

func (b *B) SomeFunc() {
 // typecheck will claim that b has no member SomeMethod
 b.SomeMethod()
}

If the call to SomeMethod is replaced with b.A.SomeMethod(), the linter will not fail. What's weird is that it fails with the verkle PR, but not in geth's master.

Output obtained by running golangci-lint on the verkle branch in geth:

> go run build/ci.go lint
build/cache/golangci-lint-1.42.0-freebsd-amd64.tar.gz is up-to-date
>>> build/cache/golangci-lint-1.42.0-freebsd-amd64/golangci-lint run --config .golangci.yml ./...
cmd/ethkey/message_test.go:38:11: generate.Expect undefined (type *testEthkey has no field or method Expect) (typecheck)
	generate.Expect(`
	         ^
cmd/ethkey/message_test.go:43:25: generate.ExpectRegexp undefined (type *testEthkey has no field or method ExpectRegexp) (typecheck)
	_, matches := generate.ExpectRegexp(`Address: (0x[0-9a-fA-F]{40})\n`)
	                       ^
cmd/ethkey/message_test.go:45:11: generate.ExpectExit undefined (type *testEthkey has no field or method ExpectExit) (typecheck)
	generate.ExpectExit()
	         ^
cmd/ethkey/message_test.go:49:7: sign.Expect undefined (type *testEthkey has no field or method Expect) (typecheck)
	sign.Expect(`
	     ^
cmd/ethkey/message_test.go:53:20: sign.ExpectRegexp undefined (type *testEthkey has no field or method ExpectRegexp) (typecheck)
	_, matches = sign.ExpectRegexp(`Signature: ([0-9a-f]+)\n`)
	                  ^
cmd/ethkey/message_test.go:55:7: sign.ExpectExit undefined (type *testEthkey has no field or method ExpectExit) (typecheck)
	sign.ExpectExit()
	     ^
cmd/ethkey/message_test.go:59:22: verify.ExpectRegexp undefined (type *testEthkey has no field or method ExpectRegexp) (typecheck)
	_, matches = verify.ExpectRegexp(`
	                    ^
cmd/ethkey/message_test.go:65:9: verify.ExpectExit undefined (type *testEthkey has no field or method ExpectExit) (typecheck)
	verify.ExpectExit()
	       ^
cmd/ethkey/run_test.go:36:5: tt.Run undefined (type *testEthkey has no field or method Run) (typecheck)
	tt.Run("ethkey-test", args...)
	   ^
cmd/evm/t8n_test.go:178:6: tt.Run undefined (type *testT8n has no field or method Run) (typecheck)
		tt.Run("evm-test", args...)
		   ^
cmd/evm/t8n_test.go:179:6: tt.Logf undefined (type *testT8n has no field or method Logf) (typecheck)
		tt.Logf("args: %v\n", strings.Join(args, " "))
		   ^
cmd/evm/t8n_test.go:186:15: tt.Output undefined (type *testT8n has no field or method Output) (typecheck)
			have := tt.Output()
			           ^
cmd/evm/t8n_test.go:195:6: tt.WaitExit undefined (type *testT8n has no field or method WaitExit) (typecheck)
		tt.WaitExit()
		   ^
cmd/evm/t8n_test.go:196:23: tt.ExitStatus undefined (type *testT8n has no field or method ExitStatus) (typecheck)
		if have, want := tt.ExitStatus(), tc.expExitCode; have != want {
		                    ^
cmd/evm/t8n_test.go:257:6: tt.Run undefined (type *testT8n has no field or method Run) (typecheck)
		tt.Run("evm-test", args...)
		   ^
cmd/evm/t8n_test.go:258:6: tt.Logf undefined (type *testT8n has no field or method Logf) (typecheck)
		tt.Logf("args:\n go run . %v\n", strings.Join(args, " "))
		   ^
cmd/evm/t8n_test.go:265:15: tt.Output undefined (type *testT8n has no field or method Output) (typecheck)
			have := tt.Output()
			           ^
cmd/evm/t8n_test.go:275:6: tt.WaitExit undefined (type *testT8n has no field or method WaitExit) (typecheck)
		tt.WaitExit()
		   ^
cmd/evm/t8n_test.go:276:23: tt.ExitStatus undefined (type *testT8n has no field or method ExitStatus) (typecheck)
		if have, want := tt.ExitStatus(), tc.expExitCode; have != want {
		                    ^
cmd/geth/accountcmd_test.go:47:7: geth.ExpectExit undefined (type *testgeth has no field or method ExpectExit) (typecheck)
	geth.ExpectExit()
	     ^
cmd/geth/accountcmd_test.go:53:13: geth.ExpectExit undefined (type *testgeth has no field or method ExpectExit) (typecheck)
	defer geth.ExpectExit()
	           ^
cmd/geth/accountcmd_test.go:55:8: geth.Expect undefined (type *testgeth has no field or method Expect) (typecheck)
		geth.Expect(`
		     ^
cmd/geth/accountcmd_test.go:61:8: geth.Expect undefined (type *testgeth has no field or method Expect) (typecheck)
		geth.Expect(`
		     ^
cmd/geth/accountcmd_test.go:71:13: geth.ExpectExit undefined (type *testgeth has no field or method ExpectExit) (typecheck)
	defer geth.ExpectExit()
	           ^
cmd/geth/accountcmd_test.go:72:7: geth.Expect undefined (type *testgeth has no field or method Expect) (typecheck)
	geth.Expect(`
	     ^
cmd/geth/accountcmd_test.go:80:7: geth.ExpectRegexp undefined (type *testgeth has no field or method ExpectRegexp) (typecheck)
	geth.ExpectRegexp(`
	     ^
cmd/geth/accountcmd_test.go:196:29: geth.StderrText undefined (type *testgeth has no field or method StderrText) (typecheck)
		if !strings.Contains(geth.StderrText(), m) {
		                          ^
cmd/geth/accountcmd_test.go:239:29: geth.StderrText undefined (type *testgeth has no field or method StderrText) (typecheck)
		if !strings.Contains(geth.StderrText(), m) {
		                          ^
cmd/geth/accountcmd_test.go:257:29: geth.StderrText undefined (type *testgeth has no field or method StderrText) (typecheck)
		if !strings.Contains(geth.StderrText(), m) {
		                          ^
cmd/geth/accountcmd_test.go:282:7: geth.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	geth.SetTemplateFunc("keypath", func(file string) string {
	     ^
cmd/geth/accountcmd_test.go:320:7: geth.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	geth.SetTemplateFunc("keypath", func(file string) string {
	     ^
cmd/geth/consolecmd_test.go:59:7: geth.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	geth.SetTemplateFunc("goos", func() string { return runtime.GOOS })
	     ^
cmd/geth/consolecmd_test.go:126:15: attach.ExpectExit undefined (type *testgeth has no field or method ExpectExit) (typecheck)
	defer attach.ExpectExit()
	             ^
cmd/geth/consolecmd_test.go:127:9: attach.CloseStdin undefined (type *testgeth has no field or method CloseStdin) (typecheck)
	attach.CloseStdin()
	       ^
cmd/geth/consolecmd_test.go:130:9: attach.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	attach.SetTemplateFunc("goos", func() string { return runtime.GOOS })
	       ^
cmd/geth/consolecmd_test.go:131:9: attach.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	attach.SetTemplateFunc("goarch", func() string { return runtime.GOARCH })
	       ^
cmd/geth/consolecmd_test.go:132:9: attach.SetTemplateFunc undefined (type *testgeth has no field or method SetTemplateFunc) (typecheck)
	attach.SetTemplateFunc("gover", runtime.Version)
	       ^
cmd/geth/consolecmd_test.go:143:9: attach.Expect undefined (type *testgeth has no field or method Expect) (typecheck)
	attach.Expect(`
	       ^
cmd/geth/consolecmd_test.go:155:9: attach.ExpectExit undefined (type *testgeth has no field or method ExpectExit) (typecheck)
	attach.ExpectExit()
	       ^
cmd/geth/dao_test.go:118:73: runGeth(t, "--datadir", datadir, "--networkid", "1337", "init", json).WaitExit undefined (type *testgeth has no field or method WaitExit) (typecheck)
		runGeth(t, "--datadir", datadir, "--networkid", "1337", "init", json).WaitExit()
		                                                                      ^
cmd/geth/dao_test.go:122:72: runGeth(t, append(args, ([]string literal)...)...).WaitExit undefined (type *testgeth has no field or method WaitExit) (typecheck)
		runGeth(t, append(args, []string{"--exec", "2+2", "console"}...)...).WaitExit()
		                                                                     ^
cmd/geth/genesis_test.go:84:50: runGeth(t, "--datadir", datadir, "init", json).WaitExit undefined (type *testgeth has no field or method WaitExit) (typecheck)
		runGeth(t, "--datadir", datadir, "init", json).WaitExit()
		                                               ^
cmd/geth/genesis_test.go:91:8: geth.ExpectRegexp undefined (type *testgeth has no field or method ExpectRegexp) (typecheck)
		geth.ExpectRegexp(tt.result)
		     ^
cmd/geth/les_test.go:26:9: g.geth.Kill undefined (type *testgeth has no field or method Kill) (typecheck)
	g.geth.Kill()
	       ^
cmd/geth/les_test.go:32:10: g.geth.Fatalf undefined (type *testgeth has no field or method Fatalf) (typecheck)
		g.geth.Fatalf("callRPC %v: %v", method, err)
		       ^
cmd/geth/les_test.go:37:9: g.geth.Logf undefined (type *testgeth has no field or method Logf) (typecheck)
	g.geth.Logf("%v.addPeer(%v)", g.name, peer.name)
	       ^
cmd/geth/les_test.go:42:10: g.geth.Fatalf undefined (type *testgeth has no field or method Fatalf) (typecheck)
		g.geth.Fatalf("subscribe %v: %v", g.name, err)
		       ^
cmd/geth/les_test.go:50:10: g.geth.Logf undefined (type *testgeth has no field or method Logf) (typecheck)
		g.geth.Logf("%v received event: type=%v, peer=%v", g.name, ev.Type, ev.Peer)
		       ^
cmd/geth/les_test.go:52:10: g.geth.Fatalf undefined (type *testgeth has no field or method Fatalf) (typecheck)
		g.geth.Fatalf("%v sub error: %v", g.name, err)
		       ^
cmd/geth/les_test.go:54:10: g.geth.Error undefined (type *testgeth has no field or method Error) (typecheck)
		g.geth.Error("timeout adding peer after", dur)
		       ^
util.go:46: exit status 1
exit status 1

"leveldb not found" after sealing a block with a contract

After a contract was created and the block containing the tx is successfully mined, the database seems not to recover from this.

INFO [11-04|20:33:56.085] Successfully sealed new block            number=13 sealhash=f75770..070802 hash=423fd5..083e0f elapsed=2.627s
INFO [11-04|20:33:56.086] 🔗 block reached canonical chain          number=6  hash=4e30af..28ecda
ERROR[11-04|20:33:56.086] Failed to reset txpool state             err="leveldb: not found"
INFO [11-04|20:33:56.086] 🔨 mined potential block                  number=13 hash=423fd5..083e0f
ERROR[11-04|20:33:56.086] Failed to create mining context          err="leveldb: not found"
WARN [11-04|20:33:58.842] Served eth_getBalance                    conn=127.0.0.1:13356 reqid=785371150672057 t="90.153µs" err="leveldb: not found"
WARN [11-04|20:33:58.843] Served eth_getBalance                    conn=127.0.0.1:13356 reqid=785371150672058 t="58.119µs" err="leveldb: not found"
WARN [11-04|20:34:00.834] Served eth_getBalance                    conn=127.0.0.1:13356 reqid=3021791296      t="93.081µs" err="leveldb: not found"
WARN [11-04|20:34:02.881] Served eth_getBalance                    conn=127.0.0.1:13356 reqid=3021791306      t="91.924µs" err="leveldb: not found"

fix random tx failure in verkle miner test

From the merged source code:

	/*
		// TODO this causes a failure, but shouldn't.  investigate.
		b.txPool.AddLocal(b.newRandomTx(true))
		b.txPool.AddLocal(b.newRandomTx(false))
		w.postSideBlock(core.ChainSideEvent{Block: b.newRandomUncle()})
		w.postSideBlock(core.ChainSideEvent{Block: b.newRandomUncle()})
	*/

rebase branch

singleton allocation of proof parameters

#15 introduced the possibility to switch the node width. As a result, the omegas and other proof parameters are often recalculated each time a new tree is calculated, which is a problem for storage.

A better method would be a singleton that allocates the data once and for all, for a given width.

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.

Kilic and Herumi give different root commitments

When comparing mainnet state conversion performed with kililc and herumi for #37, I noticed that the root commitments were different.

Kilic	Herumi	`multiExpThreshold`	`width`
`e22e60…8e593c`	`f559f5…54e691`	26	10

Both pass tests, so the offending sequence needs to be extracted from mainnet 😐

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

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?

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.

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.

use Kawashima's database rewrite instead of the snapshot

In the current prototype, the snapshot is used as a "flat database". This has the problem that the nodes are currently written to the db "the old fashioned way", and never pruned.

An alternative, would be to mimic Mr Kawashima's PR and storing the nodes by path directly in the db/snapshot.

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.

Update commitment on insert

Currently, the commitment is calculated once and for all. Insertion ends up being faster, however this is a problem for stateless execution, as data is missing from the tree.

A previous implementation existed, which was KZG-based, and would have to be rewritten to work with IPA. The idea is to introduce a new internal node type, that maintains a map[byte]VerkleNode instead of an array.

Move node serialization to client code

#12 has introduced a Serialize method, for practical purposes. This library shouldn't be concerned with serialization, so it should be removed in the future.

Add an Update function

As described in #19, Insert currently performs two functions: inserting new values and updating keys. A new Update functions should be created, so as to reflect the differing semantics.

This is likely useful for #23 which will introduce a dirty flag.

Reduce signature changes

Now that AccessWitness is passed in StateDB, there is no more need to change the function signatures to return it.

use a pool for polynomial allocations

In the new version of LeafNodes, an array of values needs to be allocated each time a new last-level node is created.

values:     make([][]byte, n.treeConfig.nodeWidth),

In the case of InsertOrdered, a performance gain could be realized by reusing a pool of nodes. This also works for children in InternalNode.

Proof element deduplication

Internal children histogram

During discussions about the multiExpThreshold I got curious as to how dense the tree actually gets. My thinking was we don't need LinCombG1 because most nodes will be sparse anyway. So I collected some data on Goerli and was surprised with the result. We seem to have more dense nodes than I thought. The data is for the two-layer storage layout (i.e. storage trees are subtrees of the account tree) and a width of 10.

There were a total of 7163171 internal nodes. 99% percent have at most 30 children and 99.9% at most 662. That still leaves ~7000 nodes with even more than 662 children. You can see the histogram below (note y axis is in log scale):

I might add more data later on from mainnet and the one-layer storage layout, otherwise we can close the issue.

Don't return cached commitment in ComputeCommitment.

As discovered here, ComputeCommitment will cache the output, and calling it a second time will return the same value.

This is a problem, because when the tree is updated, it will still serve the old value instead of computing the new one. Furthermore, serving the cached version is the purpose of GetCommitment so there is no reason for this to happen in this function.

I'm opening an issue as a reminder to first ensure that this invalid behavior is not assumed anywhere in the code. One instance is that Hash will assume that.

Test embedding small storage into account leaf

This is a tracking issue: In a model in which storage trees are subtries of their accounts, speed might be gained by not saving the subtree and instead recalculating the storage root commitment each time the tree is accessed. This is meant to save on IOs and disk space.

Implement the unified trie

Modify Verkle trees to support the scheme described here