Invalid state root calculation

[frisitano]

I am running into what appears to be an invalid state root calculation when executing the following transaction.

Transaction trace:

    {
        "traces": {
            "0x19f3febd63c61d7f9073da6cd58c75cd31aae8b3": {
                "storage_read": [
                    "0x0000000000000000000000000000000000000000000000000000000000000000",
                    "0x0000000000000000000000000000000000000000000000000000000000000001"
                ],
                "storage_written": {
                    "0x0000000000000000000000000000000000000000000000000000000000000000": "0xf687e5472aca4a84ec17ee74ebae5f8f00815aed",
                    "0x0000000000000000000000000000000000000000000000000000000000000001": "0xdac17f958d2ee523a2206206994597c13d831ec7"
                },
                "code_usage": {
                    "write": "0x608060405234801561001057600080fd5b50600436106100625760003560e01c8063715018a6146100675780638da5cb5b14610071578063a98ad46c1461009a578063dafa5b8c146100ad578063e1c9b414146100c0578063f2fde38b146100d3575b600080fd5b61006f6100e6565b005b6000546001600160a01b03165b6040516001600160a01b03909116815260200160405180910390f35b60015461007e906001600160a01b031681565b61006f6100bb36600461063e565b6100fa565b61006f6100ce3660046106aa565b610406565b61006f6100e13660046106c3565b6104d2565b6100ee610548565b6100f860006105a2565b565b8281146101595760405162461bcd60e51b815260206004820152602260248201527f50617965657320616e6420616d6f756e7473206c656e677468206d69736d61746044820152610c6d60f31b60648201526084015b60405180910390fd5b6000805b8281101561019357838382818110610177576101776106f3565b90506020020135826101899190610709565b915060010161015d565b506001546040516323b872dd60e01b8152336004820152306024820152604481018390526001600160a01b03909116906323b872dd906064016020604051808303816000875af11580156101eb573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061020f9190610730565b61025b5760405162461bcd60e51b815260206004820152601f60248201527f4661696c656420746f2073656e64205553445420746f20636f6e7472616374006044820152606401610150565b60005b848110156103fe576001546001600160a01b031663a9059cbb878784818110610289576102896106f3565b905060200201602081019061029e91906106c3565b8686858181106102b0576102b06106f3565b6040516001600160e01b031960e087901b1681526001600160a01b03909416600485015260200291909101356024830152506044016020604051808303816000875af1158015610304573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906103289190610730565b6103745760405162461bcd60e51b815260206004820152601960248201527f4661696c656420746f20646973747269627574652055534454000000000000006044820152606401610150565b858582818110610386576103866106f3565b905060200201602081019061039b91906106c3565b6001600160a01b0316307fddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef8686858181106103d8576103d86106f3565b905060200201356040516103ee91815260200190565b60405180910390a360010161025e565b505050505050565b61040e610548565b60015460405163a9059cbb60e01b8152336004820152602481018390526001600160a01b039091169063a9059cbb906044016020604051808303816000875af115801561045f573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104839190610730565b6104cf5760405162461bcd60e51b815260206004820152601760248201527f4661696c656420746f20726574726965766520555344540000000000000000006044820152606401610150565b50565b6104da610548565b6001600160a01b03811661053f5760405162461bcd60e51b815260206004820152602660248201527f4f776e61626c653a206e6577206f776e657220697320746865207a65726f206160448201526564647265737360d01b6064820152608401610150565b6104cf816105a2565b6000546001600160a01b031633146100f85760405162461bcd60e51b815260206004820181905260248201527f4f776e61626c653a2063616c6c6572206973206e6f7420746865206f776e65726044820152606401610150565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b60008083601f84011261060457600080fd5b50813567ffffffffffffffff81111561061c57600080fd5b6020830191508360208260051b850101111561063757600080fd5b9250929050565b6000806000806040858703121561065457600080fd5b843567ffffffffffffffff8082111561066c57600080fd5b610678888389016105f2565b9096509450602087013591508082111561069157600080fd5b5061069e878288016105f2565b95989497509550505050565b6000602082840312156106bc57600080fd5b5035919050565b6000602082840312156106d557600080fd5b81356001600160a01b03811681146106ec57600080fd5b9392505050565b634e487b7160e01b600052603260045260246000fd5b8082018082111561072a57634e487b7160e01b600052601160045260246000fd5b92915050565b60006020828403121561074257600080fd5b815180151581146106ec57600080fdfea26469706673582212208afd8e591f48aba9b13aa3fe5b1d4bff1e39aa61ba3f8c461f9f3d6ae4680f5364736f6c63430008180033"
                }
            },
            "0x1f9090aae28b8a3dceadf281b0f12828e676c326": {
                "balance": "0x4667a49b9875452a"
            },
            "0xf687e5472aca4a84ec17ee74ebae5f8f00815aed": {
                "balance": "0x224555d3b7f449",
                "nonce": "0x2"
            }
        },
        "meta": {
            "byte_code": "0x02f908ed010183f4e32f8509ce7da5288308004f8080b90894608060405234801561001057600080fd5b5060405161087438038061087483398101604081905261002f916100ad565b6100383361005d565b600180546001600160a01b0319166001600160a01b03929092169190911790556100dd565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b6000602082840312156100bf57600080fd5b81516001600160a01b03811681146100d657600080fd5b9392505050565b610788806100ec6000396000f3fe608060405234801561001057600080fd5b50600436106100625760003560e01c8063715018a6146100675780638da5cb5b14610071578063a98ad46c1461009a578063dafa5b8c146100ad578063e1c9b414146100c0578063f2fde38b146100d3575b600080fd5b61006f6100e6565b005b6000546001600160a01b03165b6040516001600160a01b03909116815260200160405180910390f35b60015461007e906001600160a01b031681565b61006f6100bb36600461063e565b6100fa565b61006f6100ce3660046106aa565b610406565b61006f6100e13660046106c3565b6104d2565b6100ee610548565b6100f860006105a2565b565b8281146101595760405162461bcd60e51b815260206004820152602260248201527f50617965657320616e6420616d6f756e7473206c656e677468206d69736d61746044820152610c6d60f31b60648201526084015b60405180910390fd5b6000805b8281101561019357838382818110610177576101776106f3565b90506020020135826101899190610709565b915060010161015d565b506001546040516323b872dd60e01b8152336004820152306024820152604481018390526001600160a01b03909116906323b872dd906064016020604051808303816000875af11580156101eb573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061020f9190610730565b61025b5760405162461bcd60e51b815260206004820152601f60248201527f4661696c656420746f2073656e64205553445420746f20636f6e7472616374006044820152606401610150565b60005b848110156103fe576001546001600160a01b031663a9059cbb878784818110610289576102896106f3565b905060200201602081019061029e91906106c3565b8686858181106102b0576102b06106f3565b6040516001600160e01b031960e087901b1681526001600160a01b03909416600485015260200291909101356024830152506044016020604051808303816000875af1158015610304573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906103289190610730565b6103745760405162461bcd60e51b815260206004820152601960248201527f4661696c656420746f20646973747269627574652055534454000000000000006044820152606401610150565b858582818110610386576103866106f3565b905060200201602081019061039b91906106c3565b6001600160a01b0316307fddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef8686858181106103d8576103d86106f3565b905060200201356040516103ee91815260200190565b60405180910390a360010161025e565b505050505050565b61040e610548565b60015460405163a9059cbb60e01b8152336004820152602481018390526001600160a01b039091169063a9059cbb906044016020604051808303816000875af115801561045f573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104839190610730565b6104cf5760405162461bcd60e51b815260206004820152601760248201527f4661696c656420746f20726574726965766520555344540000000000000000006044820152606401610150565b50565b6104da610548565b6001600160a01b03811661053f5760405162461bcd60e51b815260206004820152602660248201527f4f776e61626c653a206e6577206f776e657220697320746865207a65726f206160448201526564647265737360d01b6064820152608401610150565b6104cf816105a2565b6000546001600160a01b031633146100f85760405162461bcd60e51b815260206004820181905260248201527f4f776e61626c653a2063616c6c6572206973206e6f7420746865206f776e65726044820152606401610150565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b60008083601f84011261060457600080fd5b50813567ffffffffffffffff81111561061c57600080fd5b6020830191508360208260051b850101111561063757600080fd5b9250929050565b6000806000806040858703121561065457600080fd5b843567ffffffffffffffff8082111561066c57600080fd5b610678888389016105f2565b9096509450602087013591508082111561069157600080fd5b5061069e878288016105f2565b95989497509550505050565b6000602082840312156106bc57600080fd5b5035919050565b6000602082840312156106d557600080fd5b81356001600160a01b03811681146106ec57600080fd5b9392505050565b634e487b7160e01b600052603260045260246000fd5b8082018082111561072a57634e487b7160e01b600052601160045260246000fd5b92915050565b60006020828403121561074257600080fd5b815180151581146106ec57600080fdfea26469706673582212208afd8e591f48aba9b13aa3fe5b1d4bff1e39aa61ba3f8c461f9f3d6ae4680f5364736f6c63430008180033000000000000000000000000dac17f958d2ee523a2206206994597c13d831ec7c001a00608b7af7fb07a8173a583b1919a51bd48f94b5c07266a646379fdfe94e4bf96a039489cda1da03ccee301827f34ec5621d37699b4271409e97bf7a39388f1d66e",
            "new_txn_trie_node_byte": "0x02f908ed010183f4e32f8509ce7da5288308004f8080b90894608060405234801561001057600080fd5b5060405161087438038061087483398101604081905261002f916100ad565b6100383361005d565b600180546001600160a01b0319166001600160a01b03929092169190911790556100dd565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b6000602082840312156100bf57600080fd5b81516001600160a01b03811681146100d657600080fd5b9392505050565b610788806100ec6000396000f3fe608060405234801561001057600080fd5b50600436106100625760003560e01c8063715018a6146100675780638da5cb5b14610071578063a98ad46c1461009a578063dafa5b8c146100ad578063e1c9b414146100c0578063f2fde38b146100d3575b600080fd5b61006f6100e6565b005b6000546001600160a01b03165b6040516001600160a01b03909116815260200160405180910390f35b60015461007e906001600160a01b031681565b61006f6100bb36600461063e565b6100fa565b61006f6100ce3660046106aa565b610406565b61006f6100e13660046106c3565b6104d2565b6100ee610548565b6100f860006105a2565b565b8281146101595760405162461bcd60e51b815260206004820152602260248201527f50617965657320616e6420616d6f756e7473206c656e677468206d69736d61746044820152610c6d60f31b60648201526084015b60405180910390fd5b6000805b8281101561019357838382818110610177576101776106f3565b90506020020135826101899190610709565b915060010161015d565b506001546040516323b872dd60e01b8152336004820152306024820152604481018390526001600160a01b03909116906323b872dd906064016020604051808303816000875af11580156101eb573d6000803e3d6000fd5b505050506040513d601f19601f8201168201806040525081019061020f9190610730565b61025b5760405162461bcd60e51b815260206004820152601f60248201527f4661696c656420746f2073656e64205553445420746f20636f6e7472616374006044820152606401610150565b60005b848110156103fe576001546001600160a01b031663a9059cbb878784818110610289576102896106f3565b905060200201602081019061029e91906106c3565b8686858181106102b0576102b06106f3565b6040516001600160e01b031960e087901b1681526001600160a01b03909416600485015260200291909101356024830152506044016020604051808303816000875af1158015610304573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906103289190610730565b6103745760405162461bcd60e51b815260206004820152601960248201527f4661696c656420746f20646973747269627574652055534454000000000000006044820152606401610150565b858582818110610386576103866106f3565b905060200201602081019061039b91906106c3565b6001600160a01b0316307fddf252ad1be2c89b69c2b068fc378daa952ba7f163c4a11628f55a4df523b3ef8686858181106103d8576103d86106f3565b905060200201356040516103ee91815260200190565b60405180910390a360010161025e565b505050505050565b61040e610548565b60015460405163a9059cbb60e01b8152336004820152602481018390526001600160a01b039091169063a9059cbb906044016020604051808303816000875af115801561045f573d6000803e3d6000fd5b505050506040513d601f19601f820116820180604052508101906104839190610730565b6104cf5760405162461bcd60e51b815260206004820152601760248201527f4661696c656420746f20726574726965766520555344540000000000000000006044820152606401610150565b50565b6104da610548565b6001600160a01b03811661053f5760405162461bcd60e51b815260206004820152602660248201527f4f776e61626c653a206e6577206f776e657220697320746865207a65726f206160448201526564647265737360d01b6064820152608401610150565b6104cf816105a2565b6000546001600160a01b031633146100f85760405162461bcd60e51b815260206004820181905260248201527f4f776e61626c653a2063616c6c6572206973206e6f7420746865206f776e65726044820152606401610150565b600080546001600160a01b038381166001600160a01b0319831681178455604051919092169283917f8be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e09190a35050565b60008083601f84011261060457600080fd5b50813567ffffffffffffffff81111561061c57600080fd5b6020830191508360208260051b850101111561063757600080fd5b9250929050565b6000806000806040858703121561065457600080fd5b843567ffffffffffffffff8082111561066c57600080fd5b610678888389016105f2565b9096509450602087013591508082111561069157600080fd5b5061069e878288016105f2565b95989497509550505050565b6000602082840312156106bc57600080fd5b5035919050565b6000602082840312156106d557600080fd5b81356001600160a01b03811681146106ec57600080fd5b9392505050565b634e487b7160e01b600052603260045260246000fd5b8082018082111561072a57634e487b7160e01b600052601160045260246000fd5b92915050565b60006020828403121561074257600080fd5b815180151581146106ec57600080fdfea26469706673582212208afd8e591f48aba9b13aa3fe5b1d4bff1e39aa61ba3f8c461f9f3d6ae4680f5364736f6c63430008180033000000000000000000000000dac17f958d2ee523a2206206994597c13d831ec7c001a00608b7af7fb07a8173a583b1919a51bd48f94b5c07266a646379fdfe94e4bf96a039489cda1da03ccee301827f34ec5621d37699b4271409e97bf7a39388f1d66e",
            "new_receipt_trie_node_byte": "0xb9018b02f901870183d9d5feb9010020000000000000000000000000000000000000000000000000800000000000000000000001000000000000000000000000000000000000000000000000000000000000080000002000000000000000100001000000000000000000000000000000000000020000000000000000000800000000000000000000000000000000400040000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000f87df87b9419f3febd63c61d7f9073da6cd58c75cd31aae8b3f863a08be0079c531659141344cd1fd0a4f28419497f9722a3daafe3b4186f6b6457e0a00000000000000000000000000000000000000000000000000000000000000000a0000000000000000000000000f687e5472aca4a84ec17ee74ebae5f8f00815aed80",
            "gas_used": 519080
        }
    },

Logs:

2024-04-30T13:23:43.982229Z TRACE evm_arithmetization::witness::transition: Cycle 165842, ctx=0, pc=49234, below mpt_hash, instruction=Pop, stack=[32, 45292, 20747057556740084191565756506147561343411763904031675508514173368541962094140, 947]    
2024-04-30T13:23:43.982236Z TRACE evm_arithmetization::witness::transition: Cycle 165843, ctx=0, pc=49235, below mpt_hash, instruction=Jump, stack=[45292, 20747057556740084191565756506147561343411763904031675508514173368541962094140, 947]    
2024-04-30T13:23:43.982243Z TRACE evm_arithmetization::witness::transition: Cycle 165844, ctx=0, pc=45292, below check_state_trie, instruction=Push(5), stack=[20747057556740084191565756506147561343411763904031675508514173368541962094140, 947]    
2024-04-30T13:23:43.982249Z TRACE evm_arithmetization::witness::transition: Cycle 165845, ctx=0, pc=45298, below check_state_trie, instruction=MloadGeneral, stack=[21474836490, 20747057556740084191565756506147561343411763904031675508514173368541962094140, 947]    
2024-04-30T13:23:43.982256Z TRACE evm_arithmetization::witness::transition: Cycle 165846, ctx=0, pc=45299, below check_state_trie, instruction=BinaryArithmetic(Sub), stack=[33415929476338771969812384727988613276028748161968222960723827695904653733886, 20747057556740084191565756506147561343411763904031675508514173368541962094140, 947]    
2024-04-30T13:23:43.982265Z TRACE evm_arithmetization::witness::transition: Cycle 165847, ctx=0, pc=45300, below check_state_trie, instruction=Push(3), stack=[12668871919598687778246628221841051932616984257936547452209654327362691639746, 947]    
2024-04-30T13:23:43.982274Z TRACE evm_arithmetization::witness::transition: Cycle 165848, ctx=0, pc=45304, below check_state_trie, instruction=Jumpi, stack=[60128, 12668871919598687778246628221841051932616984257936547452209654327362691639746, 947]    
2024-04-30T13:23:43.982284Z  WARN evm_arithmetization::witness::transition: Kernel panic at panic    
Error: Fatal operation error: KernelPanic in kernel at pc=panic, stack=[947], memory=[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 246, 135, 229, 71, 42, 202, 74, 132, 236, 23, 238, 116, 235, 174, 95, 143, 0, 129, 90, 237, 95, 191, 112, 221, 134, 221, 131, 203, 129, 6, 195, 95, 128, 203, 72, 178, 153, 178, 128, 88, 135, 193, 191, 206, 51, 183, 158, 95, 248, 194, 128, 116]

[Nashtare]

How did you obtain the trace? I believe this block is part of the ones @praetoriansentry ran (fetching block traces from Jerigon) and it got proven fine, at least on a given version of zk_evm. Can you share your setup with commit revisions for which it is failing?

[frisitano]

I generated the trace using the native tracer I am developing. zk_evm I am using is from this PR: https://github.com/0xPolygonZero/zk_evm/pull/157.

[Nashtare]

I just tested against the mentioned Jerigon witness we used previously and latest zk_evm@develop backend prover, and I didn't encounter any issue with this txn:

2024-04-30T16:06:04.309309Z  INFO p_gen: evm_arithmetization::generation::state: CPU halted after 177526 cycles     id="b19240674 - 144"
2024-04-30T16:06:04.311728Z  INFO p_gen: ops: txn proof (f272b5c901812d981a57ee366d0b25cb68835be82fe25068f99f763b5e0bc3ef) took 159.025625ms id="b19240674 - 144"

so the issue may be coming from your end. I'll have a look. Would you happen to have the block trace / kernel trace logs?

[frisitano]

Kernel trace logs for this transaction:

transaction.log.zip

Will produce block trace now.

Yep, sounds like its something on my end.

[Nashtare]

It seems you're not having a valid state trie to begin with (although you are passing to the kernel witness that reconstructs the same trie).

Cycle 28699, ctx=0, pc=45084, below hash_initial_tries, instruction=MloadGeneral, stack=[21474836487, 15624320678034521268530137619419123205812357239735782298755735174456886811719, 911]    
Cycle 28700, ctx=0, pc=45085, below hash_initial_tries, instruction=BinaryArithmetic(Sub), stack=[15624320678034521268530137619419123205812357239735782298755735174456886811719, 15624320678034521268530137619419123205812357239735782298755735174456886811719, 911]    

Your state trie root pre-txn execution is 156243206780345212685301376194191232058123572397357822987557351744568868117191.

On Jerigon side, it is

Cycle 28699, ctx=0, pc=45084, below hash_initial_tries, instruction=MloadGeneral, stack=[21474836487, 95304458244551979935727276103143456771384068114772563680996672004691695516135, 911]     id="b19240674 - 144"
Cycle 28700, ctx=0, pc=45085, below hash_initial_tries, instruction=BinaryArithmetic(Sub), stack=[95304458244551979935727276103143456771384068114772563680996672004691695516135, 95304458244551979935727276103143456771384068114772563680996672004691695516135, 911]     id="b19240674 - 144"

i.e. 95304458244551979935727276103143456771384068114772563680996672004691695516135.

I've attached the jerigon block payload and txn trace. traces.zip

[frisitano]

Hmm that is peculiar. I'll try and investigate what is going on. I've attached the native block witness. It's hard to compare the tx_infos as it looks like jerigon includes storage writes in which the value is the same as the original value in the slot so it is in essence a noop - the native tracer does not do this.

b19240674_native.json

[Nashtare]

jerigon includes storage writes in which the value is the same as the original value

I may be wrong on this, but I believe the underlying reason is because if we need to perform a SSTORE (regardless of the value), we'll need to access the storage slot and hence need to provide its witness.

[frisitano]

I may be wrong on this, but I believe the underlying reason is because if we need to perform a SSTORE (regardless of the value), we'll need to access the storage slot and hence need to provide its witness.

Yeah we certainly need to include it in the state witness (which we do in the native tracer) but I don't think we need to include it in storage_writes of tx info. I believe in some cases it also includes nonce even when it doesn't change.

[frisitano]

I think there may be a bug in the mpt_trie implementation. I have two partial tries with the same initial root. I perform the same operations on both tries (one insertion and one deletion) and after the operations the two tries yield different roots. It looks like it's the delete operation that is responsible for the divergence. The difference between the two tries is that the native trie has a hash node in the place of a leaf node for the jerigon trie but other than that they are the same.

I have attached a zip with the source code used to run this test along with the jerigon and native tries. You can compile and run with: cat jerigon_storage_tree.json | ./target/release/trie_test and cat native_storage_tree.json | ./target/release/trie_test.

Logs

❯ cat jerigon_storage_tree.json | ./target/release/trie_test
initial hash: 0xcfc5…dc6b
insert_key: Nibbles { count: 64, packed: "0xe7c11d5270a96d8ff353e9c32fc53375eaeedd3efe2be73798d560e1d8c1f299" }
insert_value: [137, 14, 108, 227, 242, 56, 61, 189, 73, 108]
do insert
hash after insert: 0xb93f…8fa9
delete_key: Nibbles { count: 64, packed: "0xcec0d88d45c06fe2864991abe6cf6a1fbbd064d8166c0c24cd36eeb1016f9282" }
value in slot before delete: Some([136, 10, 0, 98, 2, 82, 207, 242, 133])
hash after delete: 0x26ea…7af6
❯ cat native_storage_tree.json | ./target/release/trie_test
initial hash: 0xcfc5…dc6b
insert_key: Nibbles { count: 64, packed: "0xe7c11d5270a96d8ff353e9c32fc53375eaeedd3efe2be73798d560e1d8c1f299" }
insert_value: [137, 14, 108, 227, 242, 56, 61, 189, 73, 108]
do insert
hash after insert: 0xb93f…8fa9
delete_key: Nibbles { count: 64, packed: "0xcec0d88d45c06fe2864991abe6cf6a1fbbd064d8166c0c24cd36eeb1016f9282" }
value in slot before delete: Some([136, 10, 0, 98, 2, 82, 207, 242, 133])
hash after delete: 0xd578…7641

Source

trie_test.zip

[Nashtare]

@BGluth I haven't followed this topic very closely. Have we started investigating the cause of the mpt_trie issue? Do we know where this is coming from / has it been fixed already?

[BGluth]

Yeah sorry, I probably should have posted an update here. This was discussed on Slack with @frisitano, and the cause is the infamous issue of the full node providing this:

  B
 /  \
L    H

when a txn ends up deleting the leaf L and collapsing it into an extension node. In this case, an extension node E pointing to a hash node won't allow us to collapse it if the hash node happens to be a leaf node (since we have no idea what type of node got hashed). Since E --> L produces a different hash than a collapsed node L', we produce the wrong hash.

So yeah. I guess in short, this is an issue with the full node and I think we're good to close this. As an aside, we really need to document this somewhere as this is not very obvious and critical for full node implementators.

[frisitano]

I think you had proposed raising an error in the case in which we do not have sufficient information to collapse the branch node instead of producing an incorrect trie. Has this error logic been implemented?

[BGluth]

Ah right, that did come up. I haven't impled this yet, but I opened an issue (#237).

[Nashtare]

It may be happening with Jerigon as well. The state trie obtained after application of the deltas of the first txn in this block below is invalid. Testable with the feat/cancun branch. witness-0014.json