Rehash for `172129258` round has failed

imalygin commented 3 months ago

Description

Rehash validation failed for 172129258 round.

Here is an example: https://github.com/hashgraph/hedera-state-validator/actions/runs/9236431995/job/25412277720

We need to figure out why exactly it has failed

Steps to reproduce

Download 172129258 round for any node.
Download validator-0.49.jar
Run java -jar validator-0.49.jar /path/to/round/171851985 rehash

Additional context

Validation of the next backup passed successfully

https://github.com/hashgraph/hedera-state-validator/actions/runs/9236565102/job/25412557889

Hedera network

mainnet

Version

v0.49

Operating system

None

imalygin commented 3 months ago

One more round failed similarly - 172327696

Here is an example -https://github.com/hashgraph/hedera-state-validator/actions/runs/9258363503/job/25468331276

imalygin commented 3 months ago

Another attempt of running the validation failed for the same round - https://github.com/hashgraph/hedera-state-validator/actions/runs/9271340422/job/25506576839

So, it's not the artifact of incomplete download.

imalygin commented 3 months ago

Here is the hash info diff that is in produced by validation of 172327696 round (see here https://github.com/hashgraph/hedera-state-validator/actions/runs/9276595809/job/25524033185):

{deltas=[
 [ChangeDelta, position: 0, lines: 
    [(root) State /rubber-connect-slush-blood,0 MerkleHederaState /0 reduce-volcano-awkward-remain] to 
    [(root) State /tennis-exhibit-much-flee,0 MerkleHederaState /0 alley-wheel-paddle-rice]],

[ChangeDelta, position: 71, lines: 
   [23 VirtualMap ScheduleService.SCHEDULES_BY_EQUALITY/0/23consider-staff-shoot-laundry] to 
   [23 VirtualMap ScheduleService.SCHEDULES_BY_EQUALITY/0/23attack-quarter-slam-canal]],

 [ChangeDelta, position: 73, lines:
   [ 1 VirtualRootNode /0/23/1brown-horn-nuclear-give, 24 VirtualMap ScheduleService.SCHEDULES_BY_EXPIRY_SEC/0/24save-winter-blossom-account] to
   [ 1 VirtualRootNode /0/23/1service-spy-combine-potato, 24 VirtualMap ScheduleService.SCHEDULES_BY_EXPIRY_SEC/0/24faint-proud-chalk-twist]
 ],
 [ChangeDelta, position: 76, lines:
   [ 1 VirtualRootNode /0/24/1swift-phone-nose-tell, 25 VirtualMap ScheduleService.SCHEDULES_BY_ID/0/25noble-raw-theory-mail] to 
   [ 1 VirtualRootNode /0/24/1extra-drill-trust-quick, 25 VirtualMap ScheduleService.SCHEDULES_BY_ID/0/25divert-huge-erase-route]],
 [ChangeDelta, position: 79, lines: 
[ 1 VirtualRootNode /0/25/1sting-camera-ethics-icon] to 
[ 1 VirtualRootNode /0/25/1eager-cotton-ribbon-prize]]
]}

artemananiev commented 3 months ago

I was able to reproduce this issue using a slightly modified VirtualMap benchmark. After endless runs, the root cause was found:

at some point (let's call it version 1), the virtual map contains only two elements, so the virtual tree is just a root node and two leafs
a virtual map copy (version 2) is made, the previous copy (version 1) is hashed
then one of the elements is removed
current code in VirtualRootNode doesn't make any changes to the node cache (moving leaves, invalidating paths, etc.), it only updates the leaf range to (1, 1)
another copy (version 3) is made
when copy 2 is hashed, VirtualHasher accepts a list of dirty leaves in this version, however the list is empty, nothing was marked as dirty
as a result, the copy gets the same hash as the previous copy (version 1)
then the map is serialized and deserialized
when the node cache is deserialized, it correctly identifies the leaf at path 1 as dirty
when the deserialized copy is hashed, the hash is different, as the root hash is now a combination of leaf 1 hash and an empty hash (at path 2), while previously it was a combination of two leaf hashes

So the problem is not with serialization/deserialization, but with hashing.

artemananiev commented 3 months ago

The fix is straightforward. When leaf 2 is removed, explicitly mark leaf 1 as dirty, despite it hasn't actually changed (neither leaf data, nor leaf path). Now I'm trying to understand if a similar problem may be observed, when the last leaf is removed

hashgraph / hedera-services