bug: some subtrees have incorrect end heights after a full sync

[teor2345]

Steps to fix

• Fix the bug
• Remove different code for full sync and upgrading legacy states
• Remove different code for end of block and middle of block Edit: this is tricky to do
• Test using sapling and orchard
• Optionally: test using full sync (+restart Zebra) and legacy upgrades
• Revert PR fix(ci): Temporarily disable panic on subtree validation failure #7555

What happened?

I expected to see this happen:

Subtree end heights should be the block they are completed in.
Subtrees should match zcashd.

Instead, this happened:

Subtree end heights were 1 more than they should be, under these conditions:

• the subtree was completed at the end of a block, and
• the subtree was created by a newly synced tip block (not an upgrade).

Some subtrees won't match zcashd after a full Zebra sync.

What were you doing when the issue happened?

Testing PR #7531 on my local machine.

Zebra logs

The application panicked (crashed).
Message:  already checked that the block completed a subtree: 
updated subtree:
index: Some(NoteCommitmentSubtreeIndex(0))
remaining notes: 0
is complete: true
original subtree:
index: NoteCommitmentSubtreeIndex(0)
remaining notes: 3
is complete: false
Location: zebra-state/src/service/finalized_state/disk_format/upgrade/add_subtrees.rs:599
Metadata:
version: 1.2.0+46.g8e74e49.modified
Zcash network: Mainnet 
running state version: 25.2.1
initial disk state version: 25.2.0                                                                                                                                                                         
features: default,getblocktemplate_rpcs,metrics_exporter_prometheus,prometheus,release_max_level_info 
branch: upgrade-subtrees-backwards
git commit: 8e74e49

Zebra Version

zebrad 1.2.0 commit 8e74e49

Which operating systems does the issue happen on?

• Linux
• macOS
• Windows
• Other OS

OS details

local machine

Additional information

This bug would have been caught by ticket #7446, but only if we found a test vector for "Completed Subtree at the end of the block", and "subtrees added with new tip blocks", and ran it on a full sync Zebra state.

The best way to detect this bug is a manual zcash-rpc-diff after a full sync of a new state, I'll add a check to ticket #7450.

In PR #7531, I refactored the upgrade and tip block subtrees to use the same code, which is how I found this bug. So a similar bug shouldn't happen again.

[teor2345]

We have what looks like an instance of this bug in CI:
#7349 (comment)

add_subtrees: bad sapling subtree end height subtree.end=Height(670210) height=Height(670209) index=1 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(780365) height=Height(780364) index=2 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(839996) height=Height(839994) index=3 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(916407) height=Height(916404) index=4 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(985994) height=Height(985993) index=5 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1056198) height=Height(1056197) index=6 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1109362) height=Height(1109360) index=7 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1169472) height=Height(1169471) index=8 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1256933) height=Height(1256932) index=9 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1363038) height=Height(1363036) index=10 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1703172) height=Height(1703171) index=17 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1806987) height=Height(1806985) index=867 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1857529) height=Height(1857525) index=1090 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1889551) height=Height(1889548) index=1093 is_complete=true
add_subtrees: bad sapling subtree end height subtree.end=Height(1997498) height=Height(1997495) index=1094 is_complete=true
add_subtrees: missing or bad sapling subtrees subtree_count=1095 first_incomplete_subtree_index=1095
add_subtrees: bad orchard subtree end height subtree.end=Height(1888930) height=Height(1888929) index=338 is_complete=true
add_subtrees: missing or bad orchard subtrees subtree_count=585 first_incomplete_subtree_index=585

[teor2345]

Here are the corresponding zcashd test vectors:

Sapling

sapling 0-10

$ zcash-cli z_getsubtreesbyindex sapling 0 11
{
  "pool": "sapling",
  "start_index": 0,
  "subtrees": [
    {
      "root": "754bb593ea42d231a7ddf367640f09bbf59dc00f2c1d2003cc340e0c016b5b13",
      "end_height": 558822
    },
    {
      "root": "03654c3eacbb9b93e122cf6d77b606eae29610f4f38a477985368197fd68e02d",
      "end_height": 670209
    },
    {
      "root": "e2bf698f5ac10b44da560d11a5e1d5c191a82a968a2be0a6948aa8748b545160",
      "end_height": 780364
    },
    {
      "root": "e71be1fd3963a2d700ed374d01fdd4a70d8dda8189a8f6602e5fe66c2c66a11d",
      "end_height": 839994
    },
    {
      "root": "f1c57245fff8dbc2d3efe5a0953eafdedeb06e18a3ad4f1e4042ee76623f8032",
      "end_height": 916404
    },
    {
      "root": "ea8a275c49b47f4658fa4947bbac027bb1981e3009f292916cb1f7a93ac82c08",
      "end_height": 985993
    },
    {
      "root": "891b1e6bfec42e97c79ec505c7ae1b584cf47d4ed8f6cdfcad815b02a5496f67",
      "end_height": 1056197
    },
    {
      "root": "163838d11a0525898f410397ae6ec627fa18b3184a021e088806947b3c5ca718",
      "end_height": 1109360
    },
    {
      "root": "089a1f9d50a037cc66aba4400b1703bcbb66f5f2993fd0dd3bb726e359409167",
      "end_height": 1169471
    },
    {
      "root": "0fc8a6ad74e65764d9bc2fcd13866b994731dfda821e6618a1a308bb1eccf51a",
      "end_height": 1256932
    },
    {
      "root": "cdd92a1e884cf1914dae8345423203832ec7bbf9d95ae50b82e4327b39d6d912",
      "end_height": 1363036
    }
  ]
}

$ zcash-cli z_getsubtreesbyindex sapling 17 1
{
  "pool": "sapling",
  "start_index": 17,
  "subtrees": [
    {
      "root": "89ac51fcf846eacb2e7bca32d9bf3793792d2d952c1fec11e52b56d7674c1c36",
      "end_height": 1703171
    }
  ]
}

$ zcash-cli z_getsubtreesbyindex sapling 867 1
{
  "pool": "sapling",
  "start_index": 867,
  "subtrees": [
    {
      "root": "3440a17e58fa1e00e598b1de14aa555373b6531a07305b3066414f0099610f58",
      "end_height": 1806985
    }
  ]
}

sapling 1090-1095

$ zcash-cli z_getsubtreesbyindex sapling 1090 6
{
  "pool": "sapling",
  "start_index": 1090,
  "subtrees": [
    {
      "root": "507ebccc63e2ca45bd254975ca2b75f2a221a0167d514077472dc7ef1e04a638",
      "end_height": 1857525
    },
    {
      "root": "0240b333e243a38583b692b9ce5b2fbdfde41cfdd3f3067b5c7d94fda5387666",
      "end_height": 1860908
    },
    {
      "root": "bf299f8446bea806854e9b363ed890f83423cececd53293c81df92ff112aa43f",
      "end_height": 1866377
    },
    {
      "root": "4a4778e6242b3e708f040b4a373c8cdedd14c5c415ab20f32e46430507b1a346",
      "end_height": 1889548
    },
    {
      "root": "c1cffa22d637cb194102a1b02a57d2b47c67f54094f6773a38b2e53d3becb45f",
      "end_height": 1997495
    },
    {
      "root": "0ee7328354ad588ee9581b25a3e2b94dbb03db647b79538c8805d793c61b822d",
      "end_height": 2056616
    }
  ]
}

Orchard

$ zcash-cli z_getsubtreesbyindex orchard 338 1
{
  "pool": "orchard",
  "start_index": 338,
  "subtrees": [
    {
      "root": "52c8d1ea6ef49c6e0d6bb6fef4520e1e3851895a04b52bfac1b1cc0fbbb3f709",
      "end_height": 1888929
    }
  ]
}

$ zcash-cli z_getsubtreesbyindex orchard 585 1
{
  "pool": "orchard",
  "start_index": 585,
  "subtrees": [
    {
      "root": "43c86869520ada7a2cd0deeecf3650f337f90bd4328b16144b0a278ad9fdaa08",
      "end_height": 2000126
    }
  ]
}

It is ok for a subtree to be incomplete if the state hasn't fully synced yet.