experiment: collect state witness data for EVM cross validation

[karalabe]

There are various ways to collect the necessary witness data for EVM cross validations. Doing it at high level in the trie seems a bit brittle, it's a lot of ops that must be correct. A better alternative is to hook into one layer lower at the storage retrieval site and capture an audit trail for the accessed data items. That ensures nothing goes missing.

[holiman]

My branch https://github.com/holiman/go-ethereum/tree/witness_experiments_2 has some experiments on it.

• For 'trie-backed' excution, the tracer inside a trie is used to soup up the nodes.
• For 'snapshot-backed' execution, the trie prefetcher has been rewritten, so that it always completes: instead of just aborting it, the caller needs to wait for it to finish it's tasks. Inside it, the same trie.tracer is used. The prefetcher delivers the trie to the caller, who proceeds to use it for updates, thus adding any extra sibling-nodes that are required to produce the poststate.
• At this point, I have not added reads. I therefore expect the 'trie-backed' witness to differ from the 'snapshot-backed' witness.

It can be tested with e.g. blockchain tests

[user@work go-ethereum]$ go run  ./cmd/evm/  --json --dump blocktest ./tests/testdata/BlockchainTests/GeneralStateTests/stCallCodes/callcall_00.json  2>&1  | grep witness | head -n 20
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
[witness] Root ae67c412e08547562faf01687b0881f8bd873913f3610a8f11e531f3f1870fbb
[witness] Owner 0x0000000000000000000000000000000000000000000000000000000000000000, 5 entries: 
[witness] - '0x0c': 0xf869a035b6e52f52fba98eb72592089d858d06f258aba915c994662489a03e35e97cc8b846f8448080a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a05566b23433ebe4760cced954cd4416fe4dac80925794b857dc0543b9150a18c7
[witness] - '': 0xf891a0784817176baf8005fc2e6438e8ecc5f8aa896e82ada0c7506abad768d7fd75958080a05d53e51757bd1ac9dc53fd330a19afe11ea5b6f86095372ffec4246f418b26fc8080808080808080a0d13f3d81d1de21e71fc77ca5bd72e36e25d68ba4b00549d6bbc999e323a602bc80a085e69184ea38227c33cf3291651e5d3a8b8f3f2b3e9183b25b4a220c31efe1e48080
[witness] - '0x00': 0xf871a033601462093b5945d1676df093446790fd31b20e7b12a2e8e5e09d068109616bb84ef84c80880de0b6b3a7640000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
[witness] - '0x0e': 0xf871a03e51ea7e15b3ec83d9e87eac953fcb2444be7f09e9b1e6e02a47fe32c5a9163ab84ef84c80880de0b6b3a7640000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c2688c82aba81dcb585a1c48e70b72b372db0e918e71803b43c9aed25f59e38f
[witness] - '0x03': 0xf871a03ed02be1e351ddbcc2bf3ffafc25fb42a533df024b33c85f9805e17b60f7230cb84ef84c80880de0b6b3a7640000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0298cfc41a13d4d9675691303d2b73e1551b3f2721254099297bd0bc73807b432
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421
[witness] Root 56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421

[jwasinger]

I think witnesses/values for storage writes are getting omitted on your branch @holiman . I modified your test case to only include a single block (here).

I get this output:

{"pc":0,"op":96,"gas":"0x74f18","gasCost":"0x3","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"PUSH1"}
{"pc":2,"op":67,"gas":"0x74f15","gasCost":"0x2","memSize":0,"stack":["0x1"],"depth":1,"refund":0,"opName":"NUMBER"}
{"pc":3,"op":1,"gas":"0x74f13","gasCost":"0x3","memSize":0,"stack":["0x1","0x1"],"depth":1,"refund":0,"opName":"ADD"}
{"pc":4,"op":96,"gas":"0x74f10","gasCost":"0x3","memSize":0,"stack":["0x2"],"depth":1,"refund":0,"opName":"PUSH1"}
{"pc":6,"op":85,"gas":"0x74f0d","gasCost":"0x5654","memSize":0,"stack":["0x2","0x3"],"depth":1,"refund":0,"opName":"SSTORE"}
{"pc":7,"op":0,"gas":"0x6f8b9","gasCost":"0x0","memSize":0,"stack":[],"depth":1,"refund":0,"opName":"STOP"}
{"output":"","gasUsed":"0x565f"}
[witness] Root acfaacb83fca36d0e28369d094c540a0b039d7d2e5ed9afd9e607e34336a87fa
[witness] Owner 0x0000000000000000000000000000000000000000000000000000000000000000, 3 entries: 
[witness] - '0x07': 0xf870a03e91b73c40b10d3db7d6f1e95a20128007b7d0515e67883b2cfeca677513f4e7b84df84b8087038d7ea4c68000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
[witness] - '': 0xf85180808080808080a0b1263ce38393b294b55d4586bda8cfb8728c91960f8b315b0a9b9495f373622e808080a09270c5393e3eb442efd9afaa80ab1cc81d8b432061558c0e6a45256b4ccd3c628080808080
[witness] - '0x0b': 0xf869a033fb41728cbe42c8656b870e369da9973184c2139a7086b00cc1baaf82da2869b846f8448001a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a044aa0b3c7fb11f6e679edbd0f8a21d9d59c140641d01a21d33ee7a652e2fd567

That's one branch node and two leaf nodes corresponding to the two accounts.

[holiman]

For a single block, the storage root is emptyHash to begin with, and the evm doesn't need to do any reads. You need to use at least two blocks (or make it so aaStorage is actually set in genesis for that account)

[jwasinger]

Ahhh that would explain it.