verifier misses a path

[gballet]

Continuing my investigation for #48 I have found another error in the verification.

The panic message is no entry found for key and the location is, /rust-verkle/verkle-trie/src/proof/verifier.rs:207:37

Proof:

0300000072d308302f37eb372570431b23ca3fc7cc855b4325f4cb4f2af79cefe34bf7a2323ef19c876997a1e14eddc3f2a2ef55b1ee9252ab06471b78c4930e1f90a7bd4c3f752d09cb3d5b1f7dc594a260c03a7982c54639f0b68d50686b62d50b00000012101110101209091010080f000000f65af722896840956ce43fde8e34972fb03633ec035cd1785ff8f263a8e3e4c7b4d9bcf98de967e9031e91d35c3a7133904e145f69e5c130b3ccbeac20710c0483c83d96e13589c180778a5d237d5b4fa751704c49908dfaca4bfb0bcf155f9d1f28bf2b14ed760e9542bbc9f1cd31157413ae4ba9da60f54baff4e7069707055d82f34c08f53cddf80799918d793ac9787f99ac7df626456a74795986d45eee2229c094f5ec8bb95fbb03c2d5359c6ef3f5c8f0c9691a8f0b2b248aef93f1471acc106b9b4e67fb5eae8dc3e6ac6d5b13afab843549f276b2c4b728dfdcc397612ec643f355305380356fa0ae20137d8eb85c97422091771bfa1e7fa911a70dd171aeccced3f46425cc2f0741016e296141911b95448be1b7023df32ddf5b0231fe60c2577efe3fcf50b9a4d488e6330054864ef8e0e9052cb772855f37f290c43fd9f13ab6f97bd39ad3f69f8d3b5ea1e1686f6cbc33879730fbc4464e22c75d204ae30b7ba8f12f36547996d96edab72cf8b54b5b253570217bc22cd57416f9bcfb9ff60dedcc6fcc3518e5e29e53799a4e154df515f500d171b5bbcf35ce9c286fb81eab42daee4f9f9931e59aceedc17bbb6adca9902b3bdffc035f2006f9328970202baa809217b11253117d2ea01f54d11a1bac77fe6b949dadc75ac33c2dbe870f9fd13f1fdeccde90272c8a5862dde7cb52d98c0fb10356c1b576e50e17849254dc3a36327d826d0b4dc158566dc8d0a30b0de6708c00e5cb99a461a7f9c2cd084d48f489ff46873ef6f22a734e0cc9d2dbb2dcd6468eef0ed51c8efa98de6b6da0c3a3281f2a4a623912654ac9c0899278b07b0f7f91369f214332e7eba73f454471995e422029e2756087873066f6be55eca972d30c19a1dc58afb0437ce2a9d67a2798ff80e2ce2789d422d17487a3458112c5bfe4efdb3afc5534286613676e318dc61624320dbfc952004f4d3e33fb615624f9aca016f51cbe93e4c12425fdbca48513d88220394531d0b5143eebdca4cb80ab94e4ca16c9d72035c0657cc3d931329a5cd4786ba65073e4d51b78e3998fc9c1b5e13aa510b020286dd29e929324def28a9f717c28a2672db392903975c0fef84c4159f599612075550baa680cebabe99d85d676d43227c78d6e2eb841f3d4abe2035ed6a0eb199a11f5b7718258224c69f5425cd7a0e66445d747c2cd95562b2a3de540a14b491a61eef00322fe7f025afa0c19947297f0b5cd9335381dd7aad0f0765ccbf13acd54cc964ba72439e779b9b357fcbca81f3ad6cce8dfd46ebc68e5228f15727f14b67fa34ca2d525b5b30325ef94258e2e9629685c0bab3259773fb4d5c101435d562173d153506461d72f0c94146030935deb07e89d27392a79cfc2cc36aec336788489a3b6e85689f3b4c55ba2efb980b04a56f363afa559c99a621ebdca3fb5887bb31363989b38086c294be492d524d09dba56a294e8846106ba81f011

(key, value) set:

Key	Value
0x6766d007d8fd90ea45b2ac9027ff04fa57e49527f11010a12a73f58ffa580800	0x0000000000000000000000000000000000000000000000000000000000000000
0x6766d007d8fd90ea45b2ac9027ff04fa57e49527f11010a12a73f58ffa580801	0x581cf7e55c9c41151e0200000000000000000000000000000000000000000000
0x6766d007d8fd90ea45b2ac9027ff04fa57e49527f11010a12a73f58ffa580802	0xe713000000000000000000000000000000000000000000000000000000000000
0x6766d007d8fd90ea45b2ac9027ff04fa57e49527f11010a12a73f58ffa580803	0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
0x6766d007d8fd90ea45b2ac9027ff04fa57e49527f11010a12a73f58ffa580804	0x0000000000000000000000000000000000000000000000000000000000000000
0x695921dca3b16c5cc850e94cdd63f573c467669e89cec88935d03474d6bdf900	0x
0x695921dca3b16c5cc850e94cdd63f573c467669e89cec88935d03474d6bdf901	0x
0x695921dca3b16c5cc850e94cdd63f573c467669e89cec88935d03474d6bdf902	0x
0x695921dca3b16c5cc850e94cdd63f573c467669e89cec88935d03474d6bdf903	0x
0x695921dca3b16c5cc850e94cdd63f573c467669e89cec88935d03474d6bdf904	0x
0x72d3a39289440880f00c43c3a07274147ef417d3f51d84f8dd514fd5c82eda00	0x
0x72d3a39289440880f00c43c3a07274147ef417d3f51d84f8dd514fd5c82eda02	0x
0x72d3a39289440880f00c43c3a07274147ef417d3f51d84f8dd514fd5c82eda03	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f700	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f701	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f702	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f703	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f704	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f750	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f780	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f781	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f782	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f783	0x
0x7339a1c3fc6815bf464e8fd75cb38f825c2999429aa2e63e11d026e4cfb4f784	0x
0x8cbef1db2d70a48f58505953351092c37f903bcf78b0aff05b1d544609fb8900	0x
0x8cbef1db2d70a48f58505953351092c37f903bcf78b0aff05b1d544609fb8901	0x
0x8cbef1db2d70a48f58505953351092c37f903bcf78b0aff05b1d544609fb8902	0x
0x8cbef1db2d70a48f58505953351092c37f903bcf78b0aff05b1d544609fb8903	0x
0x8cbef1db2d70a48f58505953351092c37f903bcf78b0aff05b1d544609fb8904	0x
0x9f2a59ea98d7cb610eff49447571e1610188937ce9266c6b4ded1b6ee37ecd00	0x0000000000000000000000000000000000000000000000000000000000000000
0x9f2a59ea98d7cb610eff49447571e1610188937ce9266c6b4ded1b6ee37ecd01	0xe0bf4c19a6bb42ba443c00000000000000000000000000000000000000000000
0x9f2a59ea98d7cb610eff49447571e1610188937ce9266c6b4ded1b6ee37ecd02	0x0200000000000000000000000000000000000000000000000000000000000000
0x9f2a59ea98d7cb610eff49447571e1610188937ce9266c6b4ded1b6ee37ecd03	0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
0xa224332ab199ac9ff2df3cbe09ea05072abab149f9f16c9e0d1306a03c493d00	0x
0xa224332ab199ac9ff2df3cbe09ea05072abab149f9f16c9e0d1306a03c493d02	0x
0xa224332ab199ac9ff2df3cbe09ea05072abab149f9f16c9e0d1306a03c493d03	0x
0xa713d3ff205f09ed8899e1c0ede2c29dce9583242552d9ffdc24e41a2d0fe2aa	0x
0xb4eff45b8a49c8eb73206bf7aaa7cabf59ac8b224e655251baed1f96dff14900	0x
0xb4eff45b8a49c8eb73206bf7aaa7cabf59ac8b224e655251baed1f96dff14901	0x
0xb4eff45b8a49c8eb73206bf7aaa7cabf59ac8b224e655251baed1f96dff14902	0x
0xb4eff45b8a49c8eb73206bf7aaa7cabf59ac8b224e655251baed1f96dff14903	0x
0xb4eff45b8a49c8eb73206bf7aaa7cabf59ac8b224e655251baed1f96dff14904	0x
0xc5532944608c13a47b9225d1863069a53b35cb1ebeafd218317ccdf028996c00	0x
0xc5532944608c13a47b9225d1863069a53b35cb1ebeafd218317ccdf028996c02	0x
0xc5532944608c13a47b9225d1863069a53b35cb1ebeafd218317ccdf028996c03	0x
0xe4f88f8c09077a0f433ce5873ae741ede1ff4577cc4198b3a4a0f880a6cc8f00	0x
0xe4f88f8c09077a0f433ce5873ae741ede1ff4577cc4198b3a4a0f880a6cc8f02	0x
0xe4f88f8c09077a0f433ce5873ae741ede1ff4577cc4198b3a4a0f880a6cc8f03	0x

The proof doesn't seem able to reconstruct the tree, it fails when trying to read path [105, 89] from commitments_by_path. The address is absent, and the depth is 2 in the proof.

The explorer is able to rebuild that tree (albeit also with a bug, subtree 0xe4... is missing from the picture), the corresponding key is absent and the depth is 2.

[gballet]

after investigation, there seems to be an issue with the proof as produced by go-verkle, because the depths given in the proof map to more commitments. I'm leaving this issue open until it's fully resolved, though.

EDIT: the missing commitment is actually 0, so nothing is missing. the problem occurs in rust-verkle, when rebuilding path [105, 89], which is represented in the previous picture. This is a misunderstanding between go-verkle and rust-verkle, but it's not currently clear to me why the misunderstanding happens.

[gballet]

See gballet/go-ethereum/pull/96 for more details.

[kevaundray]

Closing this issue as its a deduplication of #50