Make subtree index upgrade compatible with lightwalletd back-tracking algorithm

[teor2345]

Motivation

lightwalletd needs subtree indexes to be continuous from the tip backwards. This is a requirement of its back-tracking algorithm. The requirement applies even while Zebra is upgrading its state format and rebuilding subtrees.

Since the upgrade takes longer than 5 minutes, we can't rebuild subtrees from the genesis block forwards. That would create a gap between the first subtree, and any subtrees added by new blocks. These gaps would provide incorrect data to wallets.

Specifications

Zebra currently adds new subtrees if the tip block completes them. This is the correct behaviour for new blocks, regardless of whether the state also needs an upgrade.

For subtree state upgrades, Zebra can either:

1. upgrade the indexes live in reverse height order.
2. rebuild the index completely, then enable the index. For example, do the entire upgrade inside a single database transaction.

Anything else is out of scope, our priority is to have working code and tests.

Complex Code or Requirements

The indexes are upgraded concurrently with adding new subtrees at the tip.

This ticket does not need a state version bump, because it only changes the order that indexes are rebuilt in. (Once the index rebuild is complete, the order of the rebuild is irrelevant.)

Testing

Depending on the implementation chosen, either:

1. During the upgrade, test that there is a continuous range from the tip subtree to the most recently added subtree.
2. Test that the upgrade is fast, or that adding new tip subtrees isn't blocked by the database transaction. This can be done by checking the log times for the start and end of the upgrade. Any time under 10 minutes is acceptable.

Related Work

• Add note subtree indexes to the finalized and non-finalized state #6953

Follow-Up

only if the note commitment tree rebuild is extremely slow (10+ minutes)

Performance / Completion

Avoid rebuilding trees that are already in the database, so partial upgrades are not wasted. This allows Zebra instances that only run for a few minutes at a time to eventually finish the rebuild.

[mpguerra]

Hey team! Please add your planning poker estimate with Zenhub @arya2 @oxarbitrage @teor2345 @upbqdn

[teor2345]

I have confirmed that this fix is required by testing the upgrade code.

The upgrade takes approximately:

• 1 second per subtree
• 1 minute per 10,000 spam blocks

So I estimate it will take around an hour.

[teor2345]

zcashd does not seem to implement this behaviour correctly.

For example with zcashd 84% rebuilt I see this output, with the last 20 subtrees missing, but the first ~1000 matching:

$ zcash-rpc-diff 28232 z_getsubtreesbyindex sapling 1050                                                                                                                                
Checking first node release info...                                                                                                                                                                        
Checking second node release info...                                                                                                                                                                       
Connected to zebrad (port 28232) and zcashd (zcash-cli zcash.conf port).                                                                                                                                   
                                                                                                                                                                                                           
Checking zebrad network and tip height...                                                                                                                                                                  
Checking zcashd network and tip height...
                                                  
WARNING: comparing RPC responses from different heights:                          
zebrad is at: 2215780       
zcashd is at: 1870453
                                                  
Request:                                                                                             
z_getsubtreesbyindex sapling 1050
                                                  
Querying zebrad main chain at height >=2215780...
                                                                                                     
real    0m0.009s            
user    0m0.003s
sys     0m0.005s
                                                                                                     
Querying zcashd main chain at height >=1870453...
                                                  
real    0m0.030s
user    0m0.005s                                                                                     
sys     0m0.003s            
                                                  
                                                  
Response diff between zebrad and zcashd:                                                             
--- /run/user/1000/tmp.2BOxiMDnql.rpc-diff/zebrad-main-2215780-z_getsubtreesbyindex.json        2023-09-05 09:31:56.490275500 +1000
+++ /run/user/1000/tmp.2BOxiMDnql.rpc-diff/zcashd-main-1870453-z_getsubtreesbyindex.json        2023-09-05 09:31:56.520275284 +1000
@@ -173,86 +173,6 @@
     {                                                                                               
       "root": "bf299f8446bea806854e9b363ed890f83423cececd53293c81df92ff112aa43f",
       "end_height": 1866377
-    },
-    {                                                                                               
-      "root": "4a4778e6242b3e708f040b4a373c8cdedd14c5c415ab20f32e46430507b1a346",
-      "end_height": 1889548
-    },
-    {
-      "root": "c1cffa22d637cb194102a1b02a57d2b47c67f54094f6773a38b2e53d3becb45f",
-      "end_height": 1997495
-    },
-    {
-      "root": "0ee7328354ad588ee9581b25a3e2b94dbb03db647b79538c8805d793c61b822d",
-      "end_height": 2056616
-    },
-    {
-      "root": "e23000c83def6dfca2ce6bf9078ecb6c7c7f09d8362766bcb01b4ecb2795c72b",
-      "end_height": 2110988
-    },
-    {
-      "root": "5d0bbd5a96921454d858da75d6eef831ba4ab9a33503a5238aacda53e5c98d23",
-      "end_height": 2112879
-    },
-    {
-      "root": "ec7dad95a5f433e5beec92ba5233d6a7c3ee622801ad14fed5bf7fabe4e02e41",
-      "end_height": 2114682
-    },
-    {
-      "root": "4e43c53574bf22e08b861c22b32c3dc21a7564afa51848ddfbbb59f354001522",
-      "end_height": 2116534
-    },
-    {
-      "root": "6a4c0c17d1fc94d974492e4f64212def6eb56b71f66b8adb6cfa7770f6cefb38",
-      "end_height": 2118375
-    },
-    {
-      "root": "312ca9d7778035a9aa633c78e45986727e1a314a5d201ced44d17448e3977d59",
-      "end_height": 2120216
-    },
-    {
-      "root": "3e6c6698c4fafd383ebdc4da1c94783e24d16d52437c7e727e43eaf812c23a30",
-      "end_height": 2122527
-    },
-    {
-      "root": "8d21051ace3dcfcca6a4395a71e31f007c28e3ec7a021203f6f070f94e2ea50d",
-      "end_height": 2140728
-    },
-    {
-      "root": "98b45bc06517b39a7f441d7e2d24abada98ba958c610f0b5e1f08d0906565e68",
-      "end_height": 2153477
-    },
-    {
-      "root": "9791560af82690ea65b11d0d302b7f401b37f9ee884f8c15d0d1427d2c6ab64a",
-      "end_height": 2157035
-    },
-    {
-      "root": "9f7be903ecb0b46b0f561341798d2ed860a9d3c3fa89a3b5f9222157e48fd15e",
-      "end_height": 2162496
-    },
-    {
-      "root": "5a531fd3b9bd298bfa68ad7f797e7b316a4e0cdf2d492d2ea9fb90d3d673070d",
-      "end_height": 2165311
-    },
-    {
-      "root": "77a297054ddbe7513d7f707292f0b9ab8baceca11f560a775035b2b86450e545",
-      "end_height": 2167936
-    },
-    {
-      "root": "7f60e5af3cb59606e0fae45263f0bab50c0de7e66916d67ffae8557465faa85f",
-      "end_height": 2170564
-    },
-    {
-      "root": "8e290f672b57a62cdb1df4ce7afb49e80b08653f636c95391eb0d45d18feea11",
-      "end_height": 2174211
-    },
-    {
-      "root": "cf7607c617e7eecc9a7cd35a276b9faa360acd207987a6098374bd0f914e9f58",
-      "end_height": 2177477
-    },
-    {
-      "root": "ba391f92d9f6f13ffa0a9be8f09e113dd528f28d64e3fa82a9841c3871f5711e",
-      "end_height": 2195522
     }
   ]
 }

[teor2345]

(I'm checking with the zcashd developers now, it's also possible I used the wrong upgrade instructions, or it's a technical limitation of `zcashd.)

[teor2345]

zcashd does not seem to implement this behaviour correctly.

This is a technical limitation of their reindex mode:
https://discord.com/channels/809218587167293450/809251012610752513/1148454649884586074

We should still do it correctly if it's relatively easy to implement.