Send fails: Tree does not contain a root at address

[HonzaR]

In the Android SDK, which is operating upon the new SbS sync and the sync is in progress, we can reproduce RuntimeException: Error while creating transaction: An error occurred in querying or updating a note commitment tree: Tree does not contain a root at address Address { level: Level(0), index: 127765 }, which comes from the Rust layer of the SDK.

Full log:

TransactionEncoderImpl.createSpend(): creating transaction to spend Zatoshi(value=50) zatoshi to ****rgd9 with memo: test send
SaplingParamTool.validate$zcash_android_sdk_1_20_0_beta01_release(): Param files  both exist!
TransactionEncoderImpl.createSpend(): params exist! attempting to send...
TransactionEncoderImpl.createSpend(): Caught exception while creating transaction.
java.lang.RuntimeException: Error while creating transaction: An error occurred in querying or updating a note commitment tree: Tree does not contain a root at address Address { level: Level(0), index: 127765 }
	at cash.z.ecc.android.sdk.internal.jni.RustBackend.createToAddress(Native Method)
	at cash.z.ecc.android.sdk.internal.jni.RustBackend.access$createToAddress(RustBackend.kt:19)
	at cash.z.ecc.android.sdk.internal.jni.RustBackend$Companion.createToAddress(Unknown Source:0)
	at cash.z.ecc.android.sdk.internal.jni.RustBackend$Companion.access$createToAddress(RustBackend.kt:369)
	at cash.z.ecc.android.sdk.internal.jni.RustBackend$createToAddress$2.invokeSuspend(RustBackend.kt:303)
	at kotlin.coroutines.jvm.internal.BaseContinuationImpl.resumeWith(ContinuationImpl.kt:33)
	at kotlinx.coroutines.DispatchedTask.run(DispatchedTask.kt:106)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1137)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:637)

Here are a few more hints:

• reproducible on the Testnet
• with SbS sync in progress
• old/new wallet makes no difference

[nuttycom]

This should be fixed by #894; @HonzaR please confirm now that it has been merged.

The error recurred after #894, and inspection of the wallet database revealed that this is related to an error in the construction of the scan queue:

sqlite> select shard_index, subtree_end_height from sapling_tree_shards;
0|490074
1|
sqlite> select * from scan_queue;
490074|2000000|50
2000000|2050910|10
2050910|2051010|10
2051010|2051110|10
2051110|2051210|10
2051210|2051310|10
2051310|2051410|10
2051410|2051510|10
2051510|2051610|10
2051610|2051710|10
2051710|2051810|10
2051810|2051910|10
2051910|2052010|10
2052010|2052110|10
2052110|2052210|10
2052210|2052310|10
2052310|2052410|10
2052410|2052510|10
2052510|2052610|10
2052610|2472895|50
sqlite> select * from v_sapling_shard_unscanned_ranges;
0|0|65536|280000|490074||490074|2000000|50
sqlite> select tx, output_index, is_change, spent, commitment_tree_position from sapling_received_notes WHERE spent IS NULL;
4|0|0||122848

The scan queue is missing the unscanned range from the Sapling activation height at 65536 to the end of the first subtree at height 490074. Also, it's unclear why the scan range from 490074..2000000 has ChainTip priority (#897).

EDIT: Something that I realized much later was that this issue is appearing because the wallet birthday is being set to a height that is greater than the height at which the first note was received by the wallet.

[nuttycom]

@LukasKorba reports that this error is still occurring in the IOS wallet, which means that even after #903 notes are still being selected in circumstances where either the subtree containing the note or the subtree containing the anchor are incomplete.

[nuttycom]

Additional triage:

Database state:

sqlite> select id_note, tx, block, output_index, value, is_change, spent from sapling_received_notes JOIN transactions on tx = id_tx;
1|1|2176960|1|1000000000|0|4
2|2|2177894|0|10681694|0|4
3|3|2178252|0|16521749|1|5
4|4|2179048|0|10680694|1|
5|5||0|16511749|1|
sqlite> select shard_index, subtree_end_height from sapling_tree_shards;
0|490074
1|
sqlite> select min(height), max(height) from blocks;
2170000|2183409
sqlite> select * from scan_queue ;
280000|490074|0
490074|2170000|50
2170000|2179110|10
... contiguous 10-block ranges elided here ...
2183310|2183410|10
2183410|2489003|50

Notes:

• This wallet was created prior to the introduction of account birthdays, so a lot has changed in librustzcash since the last report of this error. The birthday_height and recover_until_height columns are absent from the accounts table.
• This wallet was initialized with a birthday height of 2170000. All received notes are above that height.
• The scan queue prioritizes the range prior to the birthday height, 490074..2170000 at ChainTip priority. If a bug existed in the note selection query that caused notes in the second subtree to be selected without complete witness information available, it would explain this behavior.
• After zcash_client_backend: Add account birthday management to the Data Access API #907 the 490074.2170000 range should be prioritized as Ignore as it is prior to the wallet birthday and it should no longer be necessary to scan this range to construct witnesses.
• Given the changes in zcash_client_backend: Add account birthday management to the Data Access API #907, it is likely that the conditions that permitted this bug to appear no longer apply, given the new approach to account birthday initialization and the related changes to note selection.

[nuttycom]

So much has changed that directly affects the conditions of this bug that I'm going to mark it closed for now, and then if it recurs we'll reopen this and figure out how I was wrong.