Repository: zcash/zcash (language: rust)

Issue:
Add an RPC method to expose 2^16 subtree roots
In order to use `shardtree` efficiently in a mobile client, `lightwalletd` needs to be able to supply it with information about roots of 2<sup>16</sup> subtrees within the commitment tree. We need `zcashd` to supply this information.

The usage pattern for this data is likely to be:
- Light client starts up.
- Light client requests latest height
  - `lightwalletd` returns it.
- Light client requests all 2<sup>16</sup> roots since height X (<= where they are synced up to).
  - `lightwalletd` returns a stream of:
    - Index of the subtree
    - Root of the subtree
    - Height of block that completed this subtree
      - The light client can use this `position : height` map to perform a reverse lookup from nullifiers -> block heights -> 2<sup>16</sup> subtree ranges, in order to learn what to query.
- When a newly-created note is detected (either by decrypting a received tx or nullifier lookups to find txs to trial decrypt), the light client queries for all note commitments within the 2<sup>16</sup> subtree that the new note falls within. It does this by making a `getblocks` request filtered to note commitments, for a range of blocks that spans the 2<sup>16</sup> subtree (or whatever fraction thereof it needs, modulo privacy), which it can determine from the height:position map.
  - `lightwalletd` responds with a stream of:
    - Block height
    - Block hash
    - Starting block position
    - List of:
      - List of:
        - Note commitment
      - (Note: we don't include any transaction metadata like txindex, we just use its implicit tx_index within the block).

The latter information can be produced by `lightwalletd` filtering down the `CompactBlock`s it already obtains. So all we need is a new `zcashd` RPC that takes a starting height, and returns a JSON object of a list of objects containing the per-subtree data we need.


Discussion / hints:

Fix patch:
diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp
index f9b91e53c15..238f978f900 100644
--- a/src/rpc/blockchain.cpp
+++ b/src/rpc/blockchain.cpp
@@ -275,6 +275,26 @@ UniValue blockToJSON(const CBlock& block, const CBlockIndex* blockindex, bool tx
     valuePools.push_back(ValuePoolDesc("orchard", blockindex->nChainOrchardValue, blockindex->nOrchardValue));
     result.pushKV("valuePools", valuePools);
 
+    {
+        UniValue trees(UniValue::VOBJ);
+
+        SaplingMerkleTree saplingTree;
+        if (pcoinsTip != nullptr && pcoinsTip->GetSaplingAnchorAt(blockindex->hashFinalSaplingRoot, saplingTree)) {
+            UniValue sapling(UniValue::VOBJ);
+            sapling.pushKV("size", (uint64_t)saplingTree.size());
+            trees.pushKV("sapling", sapling);
+        }
+
+        OrchardMerkleFrontier orchardTree;
+        if (pcoinsTip != nullptr && pcoinsTip->GetOrchardAnchorAt(blockindex->hashFinalOrchardRoot, orchardTree)) {
+            UniValue orchard(UniValue::VOBJ);
+            orchard.pushKV("size", (uint64_t)orchardTree.size());
+            trees.pushKV("orchard", orchard);
+        }
+
+        result.pushKV("trees", trees);
+    }
+
     if (blockindex->pprev)
         result.pushKV("previousblockhash", blockindex->pprev->GetBlockHash().GetHex());
     CBlockIndex *pnext = chainActive.Next(blockindex);
@@ -747,7 +767,7 @@ UniValue getblock(const UniValue& params, bool fHelp)
             "      \"chainValueZat\": xxxxxx,   (numeric, optional) total chain supply after this block, in " + MINOR_CURRENCY_UNIT + "\n"
             "      \"valueDelta\": xxxxxx,      (numeric, optional) change to the chain supply produced by this block, in " + CURRENCY_UNIT + "\n"
             "      \"valueDeltaZat\": xxxxxx,   (numeric, optional) change to the chain supply produced by this block, in " + MINOR_CURRENCY_UNIT + "\n"
-            "  }\n"
+            "  },\n"
             "  \"valuePools\": [            (array) information about each value pool\n"
             "      {\n"
             "          \"id\": \"xxxx\",            (string) name of the pool\n"
@@ -757,7 +777,15 @@ UniValue getblock(const UniValue& params, bool fHelp)
             "          \"valueDelta\": xxxxxx,      (numeric, optional) change to the amount in the pool produced by this block, in " + CURRENCY_UNIT + "\n"
             "          \"valueDeltaZat\": xxxxxx,   (numeric, optional) change to the amount in the pool produced by this block, in " + MINOR_CURRENCY_UNIT + "\n"
             "      }, ...\n"
-            "  ]\n"
+            "  ],\n"
+            "  \"trees\": {                 (object) information about the note commitment trees\n"
+            "      \"sapling\": {             (object, optional)\n"
+            "          \"size\": n,             (numeric) the total number of Sapling note commitments as of the end of this block\n"
+            "      },\n"
+            "      \"orchard\": {             (object, optional)\n"
+            "          \"size\": n,             (numeric) the total number of Orchard note commitments as of the end of this block\n"
+            "      },\n"
+            "  },\n"
             "  \"previousblockhash\" : \"hash\",  (string) The hash of the previous block\n"
             "  \"nextblockhash\" : \"hash\"       (string) The hash of the next block\n"
             "}\n"
@@ -1423,6 +1451,80 @@ UniValue z_gettreestate(const UniValue& params, bool fHelp)
     return res;
 }
 
+UniValue z_getsubtreesbyindex(const UniValue& params, bool fHelp)
+{
+    if (fHelp || params.size() < 2 || params.size() > 3) {
+        auto strHeight = strprintf("%d", libzcash::TRACKED_SUBTREE_HEIGHT);
+        throw runtime_error(
+            "z_getsubtreesbyindex \"pool\" start_index ( limit )\n"
+            "Returns roots of subtrees of the the given pool's note commitment tree. Each value returned\n"
+            "in the `subtrees` field is the Merkle root of a subtree containing 2^"+strHeight+" leaves.\n"
+            "\nArguments:\n"
+            "1. \"pool\"        (string, required) The pool from which subtrees should be returned. Either \"sapling\" or \"orchard\".\n"
+            "2. start_index   (numeric, required) The index of the first 2^"+strHeight+"-leaf subtree to return.\n"
+            "2. limit         (numeric, optional) The maximum number of subtree values to return.\n"
+            "\nResult:\n"
+            "{\n"
+            "  \"pool\" : \"sapling|orchard\", (string) The shielded pool to which the subtrees belong\n"
+            "  \"start_index\": n,      (numeric) The index of the first subtree\n"
+            "  \"subtrees\": [          (array) A sequential list of complete subtrees\n"
+            "    {\n"
+            "      \"root\": \"hash\",    (string) Merkle root of the 2^"+strHeight+"-leaf subtree\n"
+            "      \"end_height\": n,   (numeric) height of the block containing the note that completed this subtree\n"
+            "    }, ...\n"
+            "  ]\n"
+            "}\n"
+            "\nExamples:\n"
+            + HelpExampleCli("z_getsubtreesbyindex", "\"sapling\", 0")
+            + HelpExampleRpc("z_getsubtreesbyindex", "\"orchard\", 3, 7")
+        );
+    }
+
+    auto strPool = params[0].get_str();
+    ShieldedType pool;
+    if (strPool == "sapling") {
+        pool = SAPLING;
+    } else if (strPool == "orchard") {
+        pool = ORCHARD;
+    } else {
+        throw JSONRPCError(RPC_INVALID_PARAMETER, "Requested pool must be \"sapling\" or \"orchard\"");
+    }
+
+    libzcash::SubtreeIndex startIndex = params[1].get_int();
+    std::optional<uint64_t> limit = std::nullopt;
+    if (params.size() > 2) {
+        limit = params[2].get_int();
+    }
+
+    LOCK(cs_main);
+
+    UniValue subtrees(UniValue::VARR);
+    uint64_t count = 0;
+    for (libzcash::SubtreeIndex index = startIndex; ; index++) {
+        if (limit.has_value() && count >= limit.value()) {
+            break;
+        }
+
+        auto subtreeData = pcoinsTip->GetSubtreeData(pool, index);
+        if (!subtreeData.has_value()) {
+            break;
+        }
+
+        UniValue subtree(UniValue::VOBJ);
+        subtree.pushKV("root", HexStr(subtreeData->root));
+        subtree.pushKV("end_height", subtreeData->nHeight);
+        subtrees.push_back(subtree);
+        count++;
+    }
+
+    UniValue res(UniValue::VOBJ);
+    res.pushKV("pool", strPool);
+    res.pushKV("start_index", startIndex);
+    res.pushKV("subtrees", subtrees);
+
+    return res;
+}
+
 UniValue mempoolInfoToJSON()
 {
     UniValue ret(UniValue::VOBJ);
@@ -1545,6 +1647,7 @@ static const CRPCCommand commands[] =
     { "blockchain",         "getblockheader",         &getblockheader,         true  },
     { "blockchain",         "getchaintips",           &getchaintips,           true  },
     { "blockchain",         "z_gettreestate",         &z_gettreestate,         true  },
+    { "blockchain",         "z_getsubtreesbyindex",   &z_getsubtreesbyindex,   true  },
     { "blockchain",         "getdifficulty",          &getdifficulty,          true  },
     { "blockchain",         "getmempoolinfo",         &getmempoolinfo,         true  },
     { "blockchain",         "getrawmempool",          &getrawmempool,          true  },
diff --git a/src/rpc/common.h b/src/rpc/common.h
index 563833708de..29e114f280b 100644
--- a/src/rpc/common.h
+++ b/src/rpc/common.h
@@ -59,6 +59,7 @@ static const CRPCConvertTable rpcCvtTable =
     { "getblockchaininfo",           {{}, {}} },
     { "getchaintips",                {{}, {}} },
     { "z_gettreestate",              {{s}, {}} },
+    { "z_getsubtreesbyindex",        {{s, o}, {o}} },
     { "getmempoolinfo",              {{}, {}} },
     { "invalidateblock",             {{s}, {}} },
     { "reconsiderblock",             {{s}, {}} },


Test patch:
diff --git a/qa/rpc-tests/finalorchardroot.py b/qa/rpc-tests/finalorchardroot.py
index 5aefb1b5815..2551e5e0c21 100755
--- a/qa/rpc-tests/finalorchardroot.py
+++ b/qa/rpc-tests/finalorchardroot.py
@@ -50,6 +50,7 @@ def run_test(self):
         # Verify genesis block doesn't contain the final orchard root field.
         blk = self.nodes[0].getblock("0")
         assert "finalorchardroot" not in blk
+        assert "orchard" not in blk["trees"]
         treestate = self.nodes[0].z_gettreestate("0")
         assert_equal(treestate["height"], 0)
         assert_equal(treestate["hash"], self.nodes[0].getblockhash(0))
@@ -75,6 +76,7 @@ def run_test(self):
         for height in range(1, blockcount + 1):
             blk = self.nodes[0].getblock(str(height))
             assert "finalorchardroot" not in blk
+            assert "orchard" not in blk["trees"]
 
             treestate = self.nodes[0].z_gettreestate(str(height))
             assert_equal(treestate["height"], height)
@@ -102,6 +104,7 @@ def run_test(self):
         for height in range(200, 211):
             blk = self.nodes[0].getblock(str(height))
             assert_equal(blk["finalorchardroot"], ORCHARD_TREE_EMPTY_ROOT)
+            assert_equal(blk["trees"]["orchard"]["size"], 0)
 
             treestate = self.nodes[0].z_gettreestate(str(height))
             assert_equal(treestate["height"], height)
@@ -120,6 +123,11 @@ def run_test(self):
             assert_equal(treestate["orchard"]["commitments"]["finalRoot"], ORCHARD_TREE_EMPTY_ROOT)
             assert_equal(treestate["orchard"]["commitments"]["finalState"], "000000")
 
+        # Verify that there are no complete Orchard subtrees.
+        subtrees = self.nodes[0].z_getsubtreesbyindex('orchard', 0)
+        assert_equal(subtrees['pool'], 'orchard')
+        assert_equal(subtrees['start_index'], 0)
+        assert_equal(len(subtrees['subtrees']), 0)
 
         # Node 0 shields some funds
         taddr0 = get_coinbase_address(self.nodes[0])
@@ -146,6 +154,7 @@ def run_test(self):
         # Verify there is a Orchard output description (its commitment was added to tree)
         result = self.nodes[0].getrawtransaction(mytxid, 1)
         assert_equal(len(result["orchard"]["actions"]), 2)
+        assert_equal(blk["trees"]["orchard"]["size"], 2)
 
         # Since there is a now orchard shielded input in the blockchain,
         # the orchard values should have changed
@@ -162,7 +171,9 @@ def run_test(self):
         self.sync_all()
         self.nodes[0].generate(1)
         self.sync_all()
-        assert_equal(root, self.nodes[0].getblock("212")["finalorchardroot"])
+        blk = self.nodes[0].getblock("212")
+        assert_equal(root, blk["finalorchardroot"])
+        assert_equal(blk["trees"]["orchard"]["size"], 2)
 
         # Mine a block with a transparent tx and verify the final Orchard root does not change
         taddr1 = self.nodes[1].getnewaddress()
@@ -187,9 +198,11 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("214")["tx"]), 2)
+        blk = self.nodes[0].getblock("214")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[0].z_getbalance(zaddr0), Decimal("37.66"))
-        assert_equal(root, self.nodes[0].getblock("214")["finalorchardroot"])
+        assert_equal(root, blk["finalorchardroot"])
+        assert_equal(blk["trees"]["orchard"]["size"], 2)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["orchard"]["commitments"]["finalRoot"], root)
@@ -210,9 +223,11 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("215")["tx"]), 2)
+        blk = self.nodes[0].getblock("215")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[1].z_getbalance(saplingAddr1), Decimal("2.34"))
-        assert_equal(root, self.nodes[0].getblock("215")["finalorchardroot"])
+        assert_equal(root, blk["finalorchardroot"])
+        assert_equal(blk["trees"]["orchard"]["size"], 2)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["orchard"]["commitments"]["finalRoot"], root)
@@ -237,13 +252,15 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("216")["tx"]), 2)
+        blk = self.nodes[0].getblock("216")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[1].z_getbalance(orchardAddr1), Decimal("2.34"))
-        assert root != self.nodes[0].getblock("216")["finalorchardroot"]
+        assert root != blk["finalorchardroot"]
 
         # Verify there is a Orchard output description (its commitment was added to tree)
         result = self.nodes[0].getrawtransaction(mytxid, 1)
         assert_equal(len(result["orchard"]["actions"]), 2)  # there is Orchard shielded change
+        assert_equal(blk["trees"]["orchard"]["size"], 4)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["sprout"], treestate["sprout"])
@@ -265,13 +282,15 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("217")["tx"]), 2)
+        blk = self.nodes[0].getblock("217")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[0].z_getbalance(taddr2), Decimal("2.34"))
-        assert root != self.nodes[0].getblock("217")["finalorchardroot"]
+        assert root != blk["finalorchardroot"]
 
         # Verify there is a Orchard output description (its commitment was added to tree)
         result = self.nodes[0].getrawtransaction(mytxid, 1)
         assert_equal(len(result["orchard"]["actions"]), 2)  # there is Orchard shielded change
+        assert_equal(blk["trees"]["orchard"]["size"], 6)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["sprout"], treestate["sprout"])
@@ -281,6 +300,11 @@ def run_test(self):
         assert_equal(len(new_treestate["orchard"]["commitments"]["finalRoot"]), 64)
         assert_equal(len(new_treestate["orchard"]["commitments"]["finalState"]), 260)
 
+        # Verify that there are still no complete subtrees (as we have not created 2^16 notes).
+        subtrees = self.nodes[0].z_getsubtreesbyindex('orchard', 0)
+        assert_equal(subtrees['pool'], 'orchard')
+        assert_equal(subtrees['start_index'], 0)
+        assert_equal(len(subtrees['subtrees']), 0)
 
 
 if __name__ == '__main__':
diff --git a/qa/rpc-tests/finalsaplingroot.py b/qa/rpc-tests/finalsaplingroot.py
index 4261bccdc6a..5593d12aca7 100755
--- a/qa/rpc-tests/finalsaplingroot.py
+++ b/qa/rpc-tests/finalsaplingroot.py
@@ -50,6 +50,7 @@ def run_test(self):
         # Verify genesis block contains null field for what is now called the final sapling root field.
         blk = self.nodes[0].getblock("0")
         assert_equal(blk["finalsaplingroot"], NULL_FIELD)
+        assert "sapling" not in blk["trees"]
         treestate = self.nodes[0].z_gettreestate("0")
         assert_equal(treestate["height"], 0)
         assert_equal(treestate["hash"], self.nodes[0].getblockhash(0))
@@ -75,6 +76,7 @@ def run_test(self):
         for height in range(1, blockcount + 1):
             blk = self.nodes[0].getblock(str(height))
             assert_equal(blk["finalsaplingroot"], SAPLING_TREE_EMPTY_ROOT)
+            assert_equal(blk["trees"]["sapling"]["size"], 0)
 
             treestate = self.nodes[0].z_gettreestate(str(height))
             assert_equal(treestate["height"], height)
@@ -92,6 +94,12 @@ def run_test(self):
             assert "skipHash" not in treestate["orchard"]
             assert_equal(treestate["orchard"]["commitments"]["finalRoot"], NULL_FIELD)
 
+        # Verify that there are no complete Sapling subtrees.
+        subtrees = self.nodes[0].z_getsubtreesbyindex('sapling', 0)
+        assert_equal(subtrees['pool'], 'sapling')
+        assert_equal(subtrees['start_index'], 0)
+        assert_equal(len(subtrees['subtrees']), 0)
+
         # Node 0 shields some funds
         taddr0 = get_coinbase_address(self.nodes[0])
         saplingAddr0 = self.nodes[0].z_getnewaddress('sapling')
@@ -113,6 +121,7 @@ def run_test(self):
         # Verify there is a Sapling output description (its commitment was added to tree)
         result = self.nodes[0].getrawtransaction(mytxid, 1)
         assert_equal(len(result["vShieldedOutput"]), 1)
+        assert_equal(blk["trees"]["sapling"]["size"], 1)
 
         # Since there is a now sapling shielded input in the blockchain,
         # the sapling values should have changed
@@ -129,7 +138,9 @@ def run_test(self):
         self.sync_all()
         self.nodes[0].generate(1)
         self.sync_all()
-        assert_equal(root, self.nodes[0].getblock("202")["finalsaplingroot"])
+        blk = self.nodes[0].getblock("202")
+        assert_equal(root, blk["finalsaplingroot"])
+        assert_equal(blk["trees"]["sapling"]["size"], 1)
 
         # Mine a block with a transparent tx and verify the final Sapling root does not change
         taddr1 = self.nodes[1].getnewaddress()
@@ -154,9 +165,11 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("204")["tx"]), 2)
+        blk = self.nodes[0].getblock("204")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[0].z_getbalance(zaddr0), Decimal("37.66"))
-        assert_equal(root, self.nodes[0].getblock("204")["finalsaplingroot"])
+        assert_equal(root, blk["finalsaplingroot"])
+        assert_equal(blk["trees"]["sapling"]["size"], 1)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["sapling"]["commitments"]["finalRoot"], root)
@@ -177,13 +190,15 @@ def run_test(self):
         self.nodes[0].generate(1)
         self.sync_all()
 
-        assert_equal(len(self.nodes[0].getblock("205")["tx"]), 2)
+        blk = self.nodes[0].getblock("205")
+        assert_equal(len(blk["tx"]), 2)
         assert_equal(self.nodes[1].z_getbalance(saplingAddr1), Decimal("2.34"))
-        assert root != self.nodes[0].getblock("205")["finalsaplingroot"]
+        assert root != blk["finalsaplingroot"]
 
         # Verify there is a Sapling output description (its commitment was added to tree)
         result = self.nodes[0].getrawtransaction(mytxid, 1)
         assert_equal(len(result["vShieldedOutput"]), 2)  # there is Sapling shielded change
+        assert_equal(blk["trees"]["sapling"]["size"], 3)
 
         new_treestate = self.nodes[0].z_gettreestate(str(-1))
         assert_equal(new_treestate["sprout"], treestate["sprout"])
@@ -213,6 +228,7 @@ def run_test(self):
         blk = self.nodes[0].getblock("206")
         root = blk["finalsaplingroot"]
         assert root != self.nodes[0].getblock("205")["finalsaplingroot"]
+        assert_equal(blk["trees"]["sapling"]["size"], 5)
 
         # Verify there are two Sapling output descriptions.
         result = self.nodes[0].getrawtransaction(mytxid, 1)
@@ -241,6 +257,12 @@ def run_test(self):
         assert_equal(new_treestate["orchard"]["commitments"]["finalState"], "000000")
         pass
 
+        # Verify that there are still no complete subtrees (as we have not created 2^16 notes).
+        subtrees = self.nodes[0].z_getsubtreesbyindex('sapling', 0)
+        assert_equal(subtrees['pool'], 'sapling')
+        assert_equal(subtrees['start_index'], 0)
+        assert_equal(len(subtrees['subtrees']), 0)
+
 
 if __name__ == '__main__':
     FinalSaplingRootTest().main()