[v5] Statediff builder unit test for internalized leaf nodes #338

New Issue

2023-03-15T22:53:50Z

i-norden commented

2023-03-15 22:53:50 +00:00

A leaf node is internalized only if its length is <= 32 bytes. This is possible in the storage tries but not the state trie (state account object is always >32 bytes). A leaf node consists of two members: the partial path and the value stored by the leaf node. This means that just because a stored value is less than 32 bytes does not mean that the leaf node will be less than 32 bytes. This makes it more difficult to devise a simple ChainMaker test chain to setup this scenario, because for shallow tries the partial path is long (the node's position in the trie is very close to the root, so the remaining partial path corresponding to the rest of the leaf key is long).

We must store at least one byte in the leaf node, or else it is removed (or never inserted). So in practice what this means is we need to create a ChainMaker test chain that has a branch node at least 4 hex steps down the trie (less than 4 hex steps means the partial path is still 61+ nibbles, meaning the remaining partial path is 31+ bytes; add 1 byte for the terminator flag and 1 byte for the value and we are greater than 32 bytes). This isn't that deep in the trie, but it is difficult to devise a set of transactions that will lead to a branch node that includes an internalized leaf node at the 4th level down in the trie with a minimal number of total nodes in the trie. It's important to try to keep that number minimal, because we have to write out the expected node objects manually to test against since there is no other code to produce these objects to validate against.

A leaf node is internalized only if its length is <= 32 bytes. This is possible in the storage tries but not the state trie (state account object is always >32 bytes). A leaf node consists of two members: the partial path and the value stored by the leaf node. This means that just because a stored value is less than 32 bytes does not mean that the leaf node will be less than 32 bytes. This makes it more difficult to devise a simple `ChainMaker` test chain to setup this scenario, because for shallow tries the partial path is long (the node's position in the trie is very close to the root, so the remaining partial path corresponding to the rest of the leaf key is long). We must store at least one byte in the leaf node, or else it is removed (or never inserted). So in practice what this means is we need to create a `ChainMaker` test chain that has a branch node at least 4 hex steps down the trie (less than 4 hex steps means the partial path is still 61+ nibbles, meaning the remaining partial path is 31+ bytes; add 1 byte for the terminator flag and 1 byte for the value and we are greater than 32 bytes). This isn't that deep in the trie, but it is difficult to devise a set of transactions that will lead to a branch node that includes an internalized leaf node at the 4th level down in the trie with a minimal number of total nodes in the trie. It's important to try to keep that number minimal, because we have to write out the expected [node objects manually to test against](https://github.com/cerc-io/go-ethereum/blob/v1.11.2-statediff-v4/statediff/builder_test.go) since there is no other code to produce these objects to validate against.

i-norden commented

2023-03-15 22:58:55 +00:00

I'm 99% sure we are supporting internalized leaf nodes correctly now but I can't verify that yet without this or another test.

i-norden commented

2023-03-28 16:04:30 +00:00

Correction: we need a branch at the 6th level or lower, because there is an additional byte overhead when encoding a list as RLP bytes.

i-norden commented

2023-03-28 16:16:27 +00:00

slot1: 0x000000000000000000000000000000000000000000000000000000000000142f
slot2: 0x0000000000000000000000000000000000000000000000000000000000003095
key1: 010a08010b0d0c0d050803050b090b070a0a0d0f03070e070d020e040e0f080c0409010d030a040403040b0707070f0c0e0b0d0900020304050b080f0a070b0d
key2: 010a08010b0d00020703030b050a040c0c040b0b060302070505010508050b060602050c06030c0008020d09000704030c0b0a05040e04020200070a0e070600
key1str: 0x1a81bdcd5835b9b7aadf37e7d2e4ef8c491d3a4434b777fcebd902345b8fa7bd
key2str: 0x1a81bd02733b5a4cc4bb6327551585b6625c63c082d90743cba54e42207ae760

slot1: 0x000000000000000000000000000000000000000000000000000000000000142f slot2: 0x0000000000000000000000000000000000000000000000000000000000003095 key1: 010a08010b0d0c0d050803050b090b070a0a0d0f03070e070d020e040e0f080c0409010d030a040403040b0707070f0c0e0b0d0900020304050b080f0a070b0d key2: 010a08010b0d00020703030b050a040c0c040b0b060302070505010508050b060602050c06030c0008020d09000704030c0b0a05040e04020200070a0e070600 key1str: 0x1a81bdcd5835b9b7aadf37e7d2e4ef8c491d3a4434b777fcebd902345b8fa7bd key2str: 0x1a81bd02733b5a4cc4bb6327551585b6625c63c082d90743cba54e42207ae760

i-norden commented

2023-03-28 16:18:20 +00:00

This corresponds to slots 5167 and 12437

i-norden commented

2023-03-28 16:43:51 +00:00

Wrong again, it needs to be less-than 32 bytes, not less-than-or-equal-to (Why? I don't know. If it is 32 bytes it is the same size as a hash so why wouldn't it minimize num of nodes in the trie/on disc by storing it directly?). I don't think this is accurately documented anywhere. This means we need a branch at the 8th level or below.

Wrong again, it needs to be _less-than_ 32 bytes, not _less-than-or-equal-to_ (Why? I don't know. If it is 32 bytes it is the same size as a hash so why wouldn't it minimize num of nodes in the trie/on disc by storing it directly?). I don't think this is accurately documented anywhere. This means we need a branch at the 8th level or below.

i-norden commented

2023-03-28 16:57:10 +00:00

slot1: 0x0000000000000000000000000000000000000000000000000000000000009dac
slot2: 0x0000000000000000000000000000000000000000000000000000000000019c5e
key1: 0f0209010603010c0d0007070b0b0c0905010a00040502090d0e0f0c01050d0a080c00060e0402070c0d0e000d070a010409090c05000907050b0b0e080a0a0b
key2: 0f0209010603010c000c06020508060c01080b0f010e0c0f0d0a0106010c0e0d0307040b070a0809040603000e020d0b0402060801040c02040e050d04020a0f
key1str: 0xf291631cd077bbc951a04529defc15da8c06e427cde0d7a1499c50975bbe8aab
key2str: 0xf291631c0c62586c18bf1ecfda161ced374b7a894630e2db426814c24e5d42af

Intersect to 0f0209010603010c

Corresponding to slots 40364 and 105566

slot1: 0x0000000000000000000000000000000000000000000000000000000000009dac slot2: 0x0000000000000000000000000000000000000000000000000000000000019c5e key1: 0f0209010603010c0d0007070b0b0c0905010a00040502090d0e0f0c01050d0a080c00060e0402070c0d0e000d070a010409090c05000907050b0b0e080a0a0b key2: 0f0209010603010c000c06020508060c01080b0f010e0c0f0d0a0106010c0e0d0307040b070a0809040603000e020d0b0402060801040c02040e050d04020a0f key1str: 0xf291631cd077bbc951a04529defc15da8c06e427cde0d7a1499c50975bbe8aab key2str: 0xf291631c0c62586c18bf1ecfda161ced374b7a894630e2db426814c24e5d42af Intersect to 0f0209010603010c Corresponding to slots 40364 and 105566

i-norden commented

2023-03-28 16:58:56 +00:00

Now lets see if we can even deploy a contract with an array[105566]... might be higher than normal block gas limits, requiring it to be built up by pushing to a dynamic array over multiple blocks... which would make the unit test impossible to write (would have to manually write out a trie with 105566 leafs in it lol), defeating the purpose of this endeavor.

i-norden commented

2023-03-28 17:26:15 +00:00

We can deploy it 🙏

Sign in to join this conversation.

Branches Tags

v1.11.6-statediff-v5

v1.10.26-statediff-4.2.2-alpha

jenkins_reborn

v1.10.25-statediff-v4

v1.10.25-statediff-v4-wip

cerc_refactor

release-v1.10.23-statediff-4.2.0-alpha

v1.10.23-statediff-v4

v1.10.23-statediff-v4-wip

v1.10.22-statediff-v4-wip

v1.10.22-statediff-v4

v1.10.21-statediff-v4

linter_updates_wip

release-v1.10-21-statediff-4.1.2-alpha

release-v1.10.21-statediff-4.1.2-alpha

v1.10.20-statediff-v4

v1.10.19-statediff-v4

statediff

1 Participants

Notifications

Due Date

No due date set.

Dependencies

No dependencies set.

Reference: cerc-io/go-ethereum#338