Fix Sprout anchors check

[conradoplg]

Motivation

There are at least two blocks with transactions that fail to validate the Sprout anchor check.

We disabled the check for now, but we must investigate the issue, fix it, and restore the check.

One of the transactions is https://explorer.zcha.in/transactions/5e53ebca23efd85774677f342e8dca5493865b3892dcf344c94284fa50d11102, the fifth tx in block 1_047_908, which fails to find the anchor 019c435cd1e8aca9a4165f7e126ac6e548952439d50213f4d15c546df9d49b61 for its second JoinSplit.

Another missing anchor is 3ad623811ffa4fe8498b23f3d6bb4e086dca32269afef6c8e572fd9ee6d0c0ea which seems to be used in a block near 1_057_736.

Specifications & Solutions

We currently fetch the output note commitment tree from the most recently validated block, and we build the interstitial note commitment tree by adding note commitments from the JoinSplits in the tx being currently validated by following the linear order of the JoinSplits in the tx. This turns out to be incorrect.

The issue is that we should look up and fetch the tree that the anchor of the previous JoinSplit refers to, and add the commitments of the previous JoinSplit to this tree. The root of this new tree is available for a check against the anchor of the current JoinSplit. This new tree is also available for the next JoinSplit. (Since the anchor of the current JoinSplit might refer to it, and the current JoinSplit will become the previous one for the next JoinSplit).

Spec:

For a reference, here's a transaction builder: https://github.com/zcash/zcash/blob/2cee089697ef817ca5c3d26d0c5db973e009037f/src/transaction_builder.cpp#L622. The relevant code is between lines 622 and 655.

The solution will require fetching a note commitment tree for each Sprout anchor. Note that multiple anchors might refer to the same tree since the roots of non-interstitial note commitment trees are stored on a per-block basis. We discussed that storing the trees only for the anchors in the non-finalized state might be sufficient. We don't need to store multiple trees for Sapling or Orchard because these shielded pools don't require fetching the trees according to anchors.

Consensus rules:

[mpguerra]

Hey team! Please add your planning poker estimate with ZenHub @conradoplg @dconnolly @jvff @oxarbitrage @teor2345 @upbqdn