Error verifying proof when two missing values lead to the same empty slot.

[gballet]

Update to #49 and #48.

Proof:

00000000040000000a0a08080400000064dfc427f68e431244fae8433636dac858e017b777fa580123e17e412d52280671dbf2a761349bbb017ad625d1eef5c204109ab5bcf55054c10636d8f32fab6b087ad43bd1039a39ec46c5b66d8938f068f063e2ec82202d856eeb4a9d48771445d081501b91696e187c70d693ff3caddbe629ec33a134cc66a0c46c95c1c39510349e03b2caa23e82f0d5e0fedf963c223f1093ee7542a04b7f3373496b47f74b4cbaf2d2f1bafc25dbcd20f53d777e587bc1e557ba5d452a207b7617c112e84da7165ccb186272b071d4ea63373b0a8749f55ec68991b180395ed32c0102172c22106bb370a7def8822347e6872b37c564e663a74fc75db47ed9bb46e5d25a6f7ed2fb65c120e31d115f72872e96bcfeddf4688c6e7db61471f87e55ef871d183a23897e9d5b2791c639f5b88062a9b0951a9177ae0e6e44ca83d23b423e6432e3cdf6bef6795b85c43c3dec87122831fdb4e6d49873248771b956c7282be51889380fb7d0a386720a4cc6584e9e7811aef735a599d0631d2617db8b77e5d41d1e0b30ee956e299f9f1a9687c601dc52308270f7b152eede120e69fb3f40dc4f0d8d7439c3b115ba96921f7e30726727ba5ee320d659cc9cca33d7b2ca5c3b6d17d954fe88fd482410f947afef80453332d2c5bce5d3c533b270317c5c53ad54a7fa2c3c9611bccf44aa48e47affee6e4b480ed271fbd0738bee1827bfcac23a92a812bd70a427a701225dca3c150578f00151dd6cc45d50109b05b418bab7707c3c61b441671cf4d59b2e9cf3bc93d0f5c2a7b54940fd105b5df0ace79eeb3dde9a3946fe54872e13c3a59ef44b2ad672965dfff30f630408de78f4c3399d528361de40f1c2369ccad78fb571dc6ef504994e721efcf632fe316ff1e271c363a3f3b127196af15c50d5c6612ab1bfc82aae15a767f4b2d7903341b762428d9f5b17569c6997eb137bf1b4674772e9b76011c69db468e69c993c70c3afef02

Keys:

    [
      [
        5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a00,
        0000000000000000000000000000000000000000000000000000000000000000,
      ],
      [
        5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a01,
        41831c33dafdb76b050000000000000000000000000000000000000000000000,
      ],
      [
        5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a02,
        4300000000000000000000000000000000000000000000000000000000000000,
      ],
      [
        5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a03,
        c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470,
      ],
      [
        5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a04,
        0000000000000000000000000000000000000000000000000000000000000000,
      ],
      [
        9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60100,
        0000000000000000000000000000000000000000000000000000000000000000,
      ],
      [
        9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60101,
        4a6126f36ac715120f4000000000000000000000000000000000000000000000,
      ],
      [
        9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60102,
        0100000000000000000000000000000000000000000000000000000000000000,
      ],
      [
        9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60103,
        c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470,
      ],
      [
        ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df00,
        "",
      ],
      [
        ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df01,
        "",
      ],
      [
        ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df02,
        "",
      ],
      [
        ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df03,
        "",
      ],
      [
        ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df04,
        "",
      ],
      [
        ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb00,
        "",
      ],
      [
        ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb01,
        "",
      ],
      [
        ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb02,
        "",
      ],
      [
        ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb03,
        "",
      ],
      [
        ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb04,
        "",
      ],
      [
        ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70800,
        "",
      ],
      [
        ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70801,
        "",
      ],
      [
        ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70802,
        "",
      ],
      [
        ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70803,
        "",
      ],
      [
        ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70804,
        "",
      ],
    ],

The root has no 0xee child, and this block contains two stems whose absence is proven by a None extension status: ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df and ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb.

[gballet]

So 5 stems are declared in the proof, but the proof only contains 4 "extension status"es, since one of them is de-duplicated.

In order to reproduce the issue, I used my verkle block testing utility with the following arguments:

./verkle-block-sample -f block_190.rlp -p 6d55c53323eb0297ceb13ab4960def5a8bd5567b9a8602161175c3f4b7587b05

This command verifies most blocks (all of them until block 190, in fact).

output:

de-serialized block:
- parent hash: 7591d546a02b1c947fa6f639890bee6c38ce4b2aed2908fb405e989c0da66b3d
- storage root: 1f23cbaaf0c5f5b1b8e0026919b35ca6f19754e79ed2a3335e764ad2f3271d16
- block number: be
- key, value list:
	5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a00 => 0000000000000000000000000000000000000000000000000000000000000000
	5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a01 => 41831c33dafdb76b050000000000000000000000000000000000000000000000
	5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a02 => 4300000000000000000000000000000000000000000000000000000000000000
	5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a03 => c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
	5f7452bfe7d9397974506432eaac93dc856e39cb375ebc3ba355fd3590b31a04 => 0000000000000000000000000000000000000000000000000000000000000000
	9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60100 => 0000000000000000000000000000000000000000000000000000000000000000
	9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60101 => 4a6126f36ac715120f4000000000000000000000000000000000000000000000
	9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60102 => 0100000000000000000000000000000000000000000000000000000000000000
	9661ae0db10ecdb9bea3ef0c5fb46bb233cb6ed7404b77e7b0732512ecc60103 => c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
	ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df00 is absent
	ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df01 is absent
	ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df02 is absent
	ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df03 is absent
	ee390d5f79a75e40f22942a639ffa7b982e3de2b3e8927919210cf252355df04 is absent
	ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb00 is absent
	ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb01 is absent
	ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb02 is absent
	ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb03 is absent
	ee9707ef2846473a6fe4e10781a3b8b225ea950a7c89fb88f01c3544a41dfb04 is absent
	ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70800 is absent
	ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70801 is absent
	ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70802 is absent
	ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70803 is absent
	ef866912039f3bf5768ce2af85a24615841fee4139b76bd83bc3d2dc0bc70804 is absent
proof=Verkle proof:
 * verification hints: 1 1 1 1 Present Present None None 
 * commitments: 64dfc427f68e431244fae8433636dac858e017b777fa580123e17e412d522806 71dbf2a761349bbb017ad625d1eef5c204109ab5bcf55054c10636d8f32fab6b 087ad43bd1039a39ec46c5b66d8938f068f063e2ec82202d856eeb4a9d487714 45d081501b91696e187c70d693ff3caddbe629ec33a134cc66a0c46c95c1c395 
thread 'main' panicked at 'no entry found for key', /home/gballet/.cargo/git/checkouts/rust-verkle-3d526f4348360e3c/5812004/verkle-trie/src/proof/verifier.rs:59:32
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Note that "storage root" corresponds to the post state, the pre state is 6d55c53323eb0297ceb13ab4960def5a8bd5567b9a8602161175c3f4b7587b05

[gballet]

Finally managed to attach the block file:

block_190.rlp.gz

[gballet]

Mandatory picture of a reconstructed tree

[gballet]

Added go-verkle test for this use case in this commit

[gballet]

And the corresponding rust version is found in this PR it fails, because the number of extension statuses is 2 instead of 1

[kevaundray]

I have modifed the PR to include the optimisation, so that the tests pass.

From my understanding, we reduce the amount of space needed but increase the compute time and code complexity for the prover and verifier.

I wonder if we can use a simpler compression algorithm, that does not rely on the keys being sorted in the verkle trie algorithm.

For example, given VerificationHint : 1,1,1,1 Present, Present, None, None

We could compress it by doing:

04 01 02 Present 02 None

The 04 states that a depth of 01 has been deduplicated four times.
The 02 states that the ExtStatus Present has been deduplicated twice.
The last 02 states that the ExtStatus None has been dedupliated twice.

This is just a suggestion, I don't think this is the best algorithm, though I found it beneficial to compare the two algorithms.

The benefit of this algorithm that for large duplications, this gives a lot of savings and does not care about which stem/key it is doing the compression for so it can be done in a modular way; the keys can be sorted but this is a protocol level decision that can be done somewhere else up the protocol stack, instead of inside the verkle trie protocol itself.

This algorithm does not however give as much savings as the algorithm implemented in the PR due to the fact that there is a "marker/length" byte in the suggested algorithm. Also the worse case for the suggested algorithm is not great in terms of space, though I'm not sure it can come up, we can also mitigate the worse case by having a byte which turns off the optimisation, but this increases code complexity.

I think a difference between the two algorithms is that the one I outlined, is doing compression based on the structure, while the one in the PR is doing compression based on verkle trie specific features. The former could be added to the serialisation layer while the latter would not be suited to go there.

In general compression algorithms for sending bytes over the wire, that work on the structure of the bytes are much nicer to implement and seem less ad-hoc imo. Though I'd like to check whether we need optimisations like these in the first place, ie how much it is really saving in terms of bytes versus the complexity being added. As an example, if its 10 bytes per block, then with roughly 2 million blocks a year, this PR would save 20MB a year