Fuzz tests for `commitment` packages and check in corpus

[AlexeyAkhunov]

Assuming that the implementation of hex_patricia_hashed is now correct (it correctly calculates state root for all block up to 5.2m on Ethereum main net so far), we can autogenerate tests for coverage, similar to how it is done in other packages, like patricia: https://github.com/ledgerwatch/erigon-lib/blob/92fc7215c8ec918603bf43e7a284d54e12b06111/patricia/patricia_fuzz_test.go#L27

The main task is to come with the deserialisation of a string of bytes into input key/value pairs, and apply the logic like this in this test: https://github.com/ledgerwatch/erigon-lib/blob/92fc7215c8ec918603bf43e7a284d54e12b06111/commitment/hex_patricia_hashed_test.go#L378

Then select the corpus of tests that gives a good coverage (fuzz does it automatically) and then convert them into regular tests and assert the result of invocation of hph.Root()

[awskii]

Created fuzz test which spotted and exploited just one bug:

• call of ProcessUpdate with single update on empty HexPatriciaHashed trie will produce root hash of 33 bytes instead of 32, until first branch will be created

• applying updates one by one never produces equal root hash to batch applying (except when batchsize is 1) and generates two different trie

  sequential trie trace of adding two balance updates:

  plainKey=[ba], hashedKey=[02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f], currentKey=[], update=Flags: [+Balance], Balance: [27526]
  needUnfolding root, rootChecked = false
  unfold 1: activeRows: 0
  root, touched false, present true
  needUnfolding cell (0, 2), currentKey=[], depth=1, cell.h=[]
  updateBalance [ba] [02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f] = 27526, activeRows = 1
  updateAccount setting (0, 2), depth=1
  set downHasheKey=[040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f]
  fold: activeRows: 1, currentKey: [], touchMap: 0000000000000100, afterMap: 0000000000000100
  upcell is root
  touchMap[0]=0000000000000100, afterMap[0]=0000000000000100
  foldRoot: activeRows: 0
  plainKey=[f4], hashedKey=[080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403], currentKey=[], update=Flags: [+Balance], Balance: [4]
  needUnfolding root, rootChecked = true
  updateBalance [f4] [080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403] = 4, activeRows = 0
  set downHasheKey=[080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403]
  foldRoot: activeRows: 0
  1. Trie sequential update generated following branch updates
  => touchMap 0000000000000001, afterMap 0000000000000001
  0 => {accountPlainKey=[f4]}

batch trie trace with same updates:

plainKey=[ba], hashedKey=[02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f], currentKey=[], update=Flags: [+Balance], Balance: [27526]
needUnfolding root, rootChecked = false
unfold 1: activeRows: 0
root, touched false, present true
needUnfolding cell (0, 2), currentKey=[], depth=1, cell.h=[]
updateBalance [ba] [02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f] = 27526, activeRows = 1
updateAccount setting (0, 2), depth=1
set downHasheKey=[040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f]
plainKey=[f4], hashedKey=[080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403], currentKey=[], update=Flags: [+Balance], Balance: [4]
needUnfolding cell (0, 8), currentKey=[], depth=1, cell.h=[]
updateBalance [f4] [080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403] = 4, activeRows = 1
updateAccount setting (0, 8), depth=1
set downHasheKey=[0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403]
fold: activeRows: 1, currentKey: [], touchMap: 0000000100000100, afterMap: 0000000100000100
upcell is root
touchMap[0]=0000000100000100, afterMap[0]=0000000100000100
0: empty(0,0)
1: empty(0,1)
accountLeafHashWithKey for [040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f10]=>[f84680826b86a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
2: computeCellHash(0,2,depth=1)=[a0cab176e7f8841d33b60e6b5625ed3a77de76dceaab54a66d45ed049d258c5416]
3: empty(0,3)
4: empty(0,4)
5: empty(0,5)
6: empty(0,6)
7: empty(0,7)
accountLeafHashWithKey for [0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e040310]=>[f8448004a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
8: computeCellHash(0,8,depth=1)=[a09390e6391b83ad925ee835ab2f3214caafd91c0ca582697cce19e1665626ba92]
9: empty(0,9)
a: empty(0,a)
b: empty(0,b)
c: empty(0,c)
d: empty(0,d)
e: empty(0,e)
f: empty(0,f)
10: empty(0,10)
} [49c8975606069c822008439254369cd56aa38a94ff3a9e4c0b05d5346201daa6]
fold: update key: , branchData: [010401040201ba0201f4]
foldRoot: activeRows: 0
2. Trie batch update generated following branch updates
 => touchMap 0000000100000100, afterMap 0000000100000100
   2 => {accountPlainKey=[ba]}
   8 => {accountPlainKey=[f4]}

and hashes they produces:

-([]uint8) (len=33) sequential {
- 00000000  a0 56 e8 1f 17 1b cc 55  a6 ff 83 45 e6 92 c0 f8  |.V.....U...E....|
- 00000010  6e 5b 48 e0 1b 99 6c ad  c0 01 62 2f b5 e3 63 b4  |n[H...l...b/..c.|
- 00000020  21                                                |!|
+([]uint8) (len=32) batch {
+ 00000000  49 c8 97 56 06 06 9c 82  20 08 43 92 54 36 9c d5  |I..V.... .C.T6..|
+ 00000010  6a a3 8a 94 ff 3a 9e 4c  0b 05 d5 34 62 01 da a6  |j....:.L...4b...|
 }

Deep dive shown that problem is hidden in process of obtaining cell.downHashKey by root when root child is accountLeaf. I'm not finished research yet but think that hash is copied with offset=1 from somewhere, producing hashKey of length 65 which is passed to

https://github.com/ledgerwatch/erigon-lib/blob/92fc7215c8ec918603bf43e7a284d54e12b06111/commitment/hex_patricia_hashed.go#L722 when depth is 0. But from the other hand, seems like hashes of size 65 are expected too.

Another suspect is hph.fold() function. It's called both after applying one update and applying batch update, but produces different results since two different aftermaps provided after updates, which led us to case 1 (leaf or extension) at https://github.com/ledgerwatch/erigon-lib/blob/92fc7215c8ec918603bf43e7a284d54e12b06111/commitment/hex_patricia_hashed.go#L1177 when applying one by one, while update by batch led us to default section of that switch, where correct node hash is evaluated.

[awskii]

Firstly, hash of length 33 is returned by RootHash() only if root is nil and first byte is 0x80+hashLen. Not clear if we should pass this into keccak2 again (since branch hash evaluation does and I suppose that's branch-specific).

After I noticed that sequential apply led to different tree due to usage of root node as a leaf. I decided instead of putting first update into root create branch with one leaf - and test on Unique Representation has passed for two updates applied sequentially/by batch.

Adding third update to test case led to hash mismatch because sequential insert of third element into a branch changes hash of node inserted right before current, and leaving very first hash unchanged:

sequential update

right after second update

 2: computeCellHash(0,2,depth=1)=[a0cab176e7f8841d33b60e6b5625ed3a77de76dceaab54a66d45ed049d258c5416]
 8: computeCellHash(0,8,depth=1)=[a09390e6391b83ad925ee835ab2f3214caafd91c0ca582697cce19e1665626ba92]

right after third update

2: computeCellHash(0,2,depth=1)=[a03e50b32edd2572ce845292aa8cf87fc2bc4b7abc6170fb0d66473febe7ea7ac9]
8: computeCellHash(0,8,depth=1)=[a09d811ad24d0f682f491597b0dd1cf13738d11f17f5a13eddfd22b5db32d38ac4]
b: computeCellHash(0,b,depth=1)=[a05bf0f6a004c2b503c0cecc3020261d1606195e5588290477234dd7f58279023f]

batch update

2: computeCellHash(0,2,depth=1)=[a0cab176e7f8841d33b60e6b5625ed3a77de76dceaab54a66d45ed049d258c5416]
8: computeCellHash(0,8,depth=1)=[a09390e6391b83ad925ee835ab2f3214caafd91c0ca582697cce19e1665626ba92]
b: computeCellHash(0,b,depth=1)=[a05bf0f6a004c2b503c0cecc3020261d1606195e5588290477234dd7f58279023f]

As i understand, adding new neighbour should not change old neighbours hash, but change overall branch hash, but maybe i'm wrongly read trace log and that is how it should be.

traces

=== RUN   TestHexPatriciaHashed_ProcessUpdates_UniqueRepresentation
-- sequential update trace --
plainKey=[ba], hashedKey=[02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f], currentKey=[], update=Flags: [+Balance], Balance: [27526]
needUnfolding root, rootChecked = false
unfold 1: activeRows: 0
root, touched false, present true
needUnfolding cell (0, 2), currentKey=[], depth=1, cell.h=[]
updateBalance [ba] [02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f] = 27526, activeRows = 1
updateAccount setting (0, 2), depth=1
set downHasheKey=[040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f]
fold: activeRows: 1, currentKey: [], touchMap: 0000000000000100, afterMap: 0000000000000100
upcell is root
touchMap[0]=0000000000000100, afterMap[0]=0000000000000100
foldRoot: activeRows: 0
plainKey=[f4], hashedKey=[080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403], currentKey=[], update=Flags: [+Balance], Balance: [4]
needUnfolding root, rootChecked = true
updateBalance [f4] [080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403] = 4, activeRows = 0
updateAccount setting (0, 8), depth=1
set downHasheKey=[0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403]
fold: activeRows: 1, currentKey: [], touchMap: 0000000100000100, afterMap: 0000000100000100
upcell is root
touchMap[0]=0000000100000100, afterMap[0]=0000000100000100
0: empty(0,0)
1: empty(0,1)
accountLeafHashWithKey for [040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f10]=>[f84680826b86a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
2: computeCellHash(0,2,depth=1)=[a0cab176e7f8841d33b60e6b5625ed3a77de76dceaab54a66d45ed049d258c5416]
3: empty(0,3)
4: empty(0,4)
5: empty(0,5)
6: empty(0,6)
7: empty(0,7)
accountLeafHashWithKey for [0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e040310]=>[f8448004a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
8: computeCellHash(0,8,depth=1)=[a09390e6391b83ad925ee835ab2f3214caafd91c0ca582697cce19e1665626ba92]
9: empty(0,9)
a: empty(0,a)
b: empty(0,b)
c: empty(0,c)
d: empty(0,d)
e: empty(0,e)
f: empty(0,f)
10: empty(0,10)
} [49c8975606069c822008439254369cd56aa38a94ff3a9e4c0b05d5346201daa6]
fold: update key: , branchData: [010401040201ba0201f4]
foldRoot: activeRows: 0
plainKey=[00], hashedKey=[0b0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a], currentKey=[], update=Flags: [+Balance], Balance: [6]
needUnfolding root, rootChecked = true
unfold 1: activeRows: 0
root, touched true, present true
cell (0, 2) depth=1, hash=[], a=[ba], s=[], ex=[]
accountFn[ba] return balance=27526, nonce=0
cell (0, 8) depth=1, hash=[], a=[f4], s=[], ex=[]
accountFn[f4] return balance=4, nonce=0
needUnfolding cell (0, b), currentKey=[], depth=1, cell.h=[]
updateBalance [00] [0b0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a] = 6, activeRows = 1
updateAccount setting (0, b), depth=1
set downHasheKey=[0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a]
fold: activeRows: 1, currentKey: [], touchMap: 0000100000000000, afterMap: 0000100100000100
upcell is root
touchMap[0]=0000100000000000, afterMap[0]=0000100100000100
0: empty(0,0)
1: empty(0,1)
accountLeafHashWithKey for [040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f10]=>[f84680826b86a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a00000000000000000000000000000000000000000000000000000000000000000]
2: computeCellHash(0,2,depth=1)=[a03e50b32edd2572ce845292aa8cf87fc2bc4b7abc6170fb0d66473febe7ea7ac9]
3: empty(0,3)
4: empty(0,4)
5: empty(0,5)
6: empty(0,6)
7: empty(0,7)
accountLeafHashWithKey for [0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e040310]=>[f8448004a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a00000000000000000000000000000000000000000000000000000000000000000]
8: computeCellHash(0,8,depth=1)=[a09d811ad24d0f682f491597b0dd1cf13738d11f17f5a13eddfd22b5db32d38ac4]
9: empty(0,9)
a: empty(0,a)
accountLeafHashWithKey for [0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a10]=>[f8448006a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
b: computeCellHash(0,b,depth=1)=[a05bf0f6a004c2b503c0cecc3020261d1606195e5588290477234dd7f58279023f]
c: empty(0,c)
d: empty(0,d)
e: empty(0,e)
f: empty(0,f)
10: empty(0,10)
} [fcc95ba48ddee008155a5cfcf78c8493b6834c6760aba2131422854caf5db9ec]
fold: update key: , branchData: [08000904020100]
foldRoot: activeRows: 0
1. Trie sequential update generated following branch updates
 => touchMap 0000100000000000, afterMap 0000100100000100
   b => {accountPlainKey=[00]}

-- batch update trace --
plainKey=[ba], hashedKey=[02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f], currentKey=[], update=Flags: [+Balance], Balance: [27526]
needUnfolding root, rootChecked = false
unfold 1: activeRows: 0
root, touched false, present true
needUnfolding cell (0, 2), currentKey=[], depth=1, cell.h=[]
updateBalance [ba] [02040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f] = 27526, activeRows = 1
updateAccount setting (0, 2), depth=1
set downHasheKey=[040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f]
plainKey=[f4], hashedKey=[080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403], currentKey=[], update=Flags: [+Balance], Balance: [4]
needUnfolding cell (0, 8), currentKey=[], depth=1, cell.h=[]
updateBalance [f4] [080d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403] = 4, activeRows = 1
updateAccount setting (0, 8), depth=1
set downHasheKey=[0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e0403]
plainKey=[00], hashedKey=[0b0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a], currentKey=[], update=Flags: [+Balance], Balance: [6]
needUnfolding cell (0, b), currentKey=[], depth=1, cell.h=[]
updateBalance [00] [0b0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a] = 6, activeRows = 1
updateAccount setting (0, b), depth=1
set downHasheKey=[0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a]
fold: activeRows: 1, currentKey: [], touchMap: 0000100100000100, afterMap: 0000100100000100
upcell is root
touchMap[0]=0000100100000100, afterMap[0]=0000100100000100
0: empty(0,0)
1: empty(0,1)
accountLeafHashWithKey for [040e00030902060e0207020d030101020e0a0c0e08080e080d00040300030e0208070d05010507010407050e020303040304060d0c0c06090f02010004010f10]=>[f84680826b86a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
2: computeCellHash(0,2,depth=1)=[a0cab176e7f8841d33b60e6b5625ed3a77de76dceaab54a66d45ed049d258c5416]
3: empty(0,3)
4: empty(0,4)
5: empty(0,5)
6: empty(0,6)
7: empty(0,7)
accountLeafHashWithKey for [0d09030a0c0306010502070a090d06000e0d080d0a0f0b0d060308090e050001050a080b00000a010d0105030c03060e090c0504050a000a080102060e040310]=>[f8448004a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
8: computeCellHash(0,8,depth=1)=[a09390e6391b83ad925ee835ab2f3214caafd91c0ca582697cce19e1665626ba92]
9: empty(0,9)
a: empty(0,a)
accountLeafHashWithKey for [0c03060708090e070a010e0208010403060406040202090802080f0801070d060601020f070b0407070d06060509010f0f09060a090e0006040b0c0c09080a10]=>[f8448006a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470]
b: computeCellHash(0,b,depth=1)=[a05bf0f6a004c2b503c0cecc3020261d1606195e5588290477234dd7f58279023f]
c: empty(0,c)
d: empty(0,d)
e: empty(0,e)
f: empty(0,f)
10: empty(0,10)
} [26a45d73a3d881d669308d6e8b3d2f54508a0181bc4af6f90febb243643da239]
fold: update key: , branchData: [090409040201ba0201f4020100]
foldRoot: activeRows: 0
2. Trie batch update generated following branch updates
 => touchMap 0000100100000100, afterMap 0000100100000100
   2 => {accountPlainKey=[ba]}
   8 => {accountPlainKey=[f4]}
   b => {accountPlainKey=[00]}

Error:          Not equal: 
    Diff:
    --- Expected
    +++ Actual
    @@ -1,4 +1,4 @@
     ([]uint8) (len=32) {
    - 00000000  fc c9 5b a4 8d de e0 08  15 5a 5c fc f7 8c 84 93  |..[......Z\.....|
    - 00000010  b6 83 4c 67 60 ab a2 13  14 22 85 4c af 5d b9 ec  |..Lg`....".L.]..|
    + 00000000  26 a4 5d 73 a3 d8 81 d6  69 30 8d 6e 8b 3d 2f 54  |&.]s....i0.n.=/T|
    + 00000010  50 8a 01 81 bc 4a f6 f9  0f eb b2 43 64 3d a2 39  |P....J.....Cd=.9|
     }
Test:           TestHexPatriciaHashed_ProcessUpdates_UniqueRepresentation
Messages:       expected equal roots
--- FAIL: TestHexPatriciaHashed_ProcessUpdates_UniqueRepresentation (0.00s)