rpc: avoid quadratic output lookups #36032

Problem: Transaction-creation RPCs currently take quadratic time to parse outputs. An authenticated RPC client can therefore tie up a worker with a large request. sendmany also holds the wallet lock while parsing, delaying other operations on the same wallet.

Fix: Parse transaction outputs in linear time by reading corresponding keys and values by index instead of looking up each value by key.

Reproducer: Run time build/bin/test_bitcoin --run_test=rpc_tests/parse_outputs before and after the fix:

<details> <summary>parse_outputs test in `rpc_tests.cpp`</summary>

BOOST_AUTO_TEST_CASE(parse_outputs)
{
    constexpr size_t OUTPUT_COUNT{10'000};
    UniValue outputs{UniValue::VOBJ};
    for (size_t i{0}; i < OUTPUT_COUNT; ++i) {
        auto destination{EncodeDestination(WitnessV0ScriptHash{CScript{} << i})};
        outputs.pushKVEnd(destination, ValueFromAmount(i + 1));
    }

    const auto parsed_outputs{ParseOutputs(outputs)};
    BOOST_REQUIRE_EQUAL(parsed_outputs.size(), OUTPUT_COUNT);
    for (size_t i{OUTPUT_COUNT}; i > 0; --i) {
        std::pair expected{CTxDestination{WitnessV0ScriptHash{CScript{} << (i - 1)}}, static_cast<CAmount>(i)};
        BOOST_CHECK(parsed_outputs[i - 1] == expected);
    }
}

</details> E.g. on my M4 Max with `debug` build:

Before  ████████████████████  1.80 s
After   █████▒░░░░░░░░░░░░░░  0.50 s  -72%

Related to #35889

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/36032.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline and AI policy for information on the review process.

If your review is incorrectly listed, please copy-paste <code>&lt;!--meta-tag:bot-skip--&gt;</code> into the comment that the bot should ignore.

<!--5faf32d7da4f0f540f40219e4f7537a3-->

Is the test needed? I don't think it adds any new coverage, so it may be better to just drop it in a GitHub comment, or in the pull description. This way, reviewers can use it, if they want, or ignore it, if they want.

<!--85328a0da195eb286784d51f73fa0af9-->

🚧 At least one of the CI tasks failed. _{Task previous releases: https://github.com/bitcoin/bitcoin/actions/runs/32340471906/job/96338383005} _{LLM reason (✨ experimental): CI failed to compile tests because rpc_tests.cpp uses BOOST_CHECK(parsed_outputs[i - 1] == expected) with mismatched types (no valid operator== for the compared values), causing a C++ build error in test_bitcoin.}

<details><summary>Hints</summary>

Try to run the tests locally, according to the documentation. However, a CI failure may still happen due to a number of reasons, for example:

• Possibly due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

• A sanitizer issue, which can only be found by compiling with the sanitizer and running the affected test.

• An intermittent issue.

Leave a comment here, if you need help tracking down a confusing failure.

</details>

Concept ACK

Is this test placement what you suggest / did? I had to add a couple of header includes to have it compile.

<details><summary>test diff</summary><p>

diff --git a/src/test/rpc_tests.cpp b/src/test/rpc_tests.cpp
index d574e1e2d3a..e3a64177080 100644
--- a/src/test/rpc_tests.cpp
+++ b/src/test/rpc_tests.cpp
@@ -4,9 +4,11 @@
 
 #include <core_io.h>
 #include <interfaces/chain.h>
+#include <key_io.h>
 #include <node/context.h>
 #include <rpc/blockchain.h>
 #include <rpc/client.h>
+#include <rpc/rawtransaction_util.h>
 #include <rpc/server.h>
 #include <rpc/util.h>
 #include <test/util/common.h>
@@ -676,4 +678,21 @@ BOOST_AUTO_TEST_CASE(rpc_arg_helper)
     CheckRpc(params, UniValue{JSON(R"([5, "hello", 4, "test", true, 1.23, "world"])")}, check_positional);
 }
 
+BOOST_AUTO_TEST_CASE(parse_outputs)
+{
+    constexpr size_t OUTPUT_COUNT{10'000};
+    UniValue outputs{UniValue::VOBJ};
+    for (size_t i{0}; i < OUTPUT_COUNT; ++i) {
+        auto destination{EncodeDestination(WitnessV0ScriptHash{CScript{} << i})};
+        outputs.pushKVEnd(destination, ValueFromAmount(i + 1));
+    }
+
+    const auto parsed_outputs{ParseOutputs(outputs)};
+    BOOST_REQUIRE_EQUAL(parsed_outputs.size(), OUTPUT_COUNT);
+    for (size_t i{OUTPUT_COUNT}; i > 0; --i) {
+        std::pair expected{CTxDestination{WitnessV0ScriptHash{CScript{} << (i - 1)}}, static_cast<CAmount>(i)};
+        BOOST_CHECK(parsed_outputs[i - 1] == expected);
+    }
+}
+
 BOOST_AUTO_TEST_SUITE_END()

</p></details>

Edit:

Test results with the above diff on an M1 Max

master

0.24s user 0.02s system 96% cpu 0.271 total
0.24s user 0.01s system 97% cpu 0.260 total
0.24s user 0.01s system 97% cpu 0.260 total
0.24s user 0.01s system 97% cpu 0.260 total

this branch @ 747cff842481153357199bf9a81b5a4d82ea91fb

0.14s user 0.03s system 77% cpu 0.220 total
0.14s user 0.01s system 96% cpu 0.162 total
0.14s user 0.01s system 97% cpu 0.159 total
0.14s user 0.01s system 96% cpu 0.163 total

Thanks for the review and reproducer! Yes, the test you added is what I meant (didn't want to add a huge diff to the PR details). And it seems you compiled with release - I did debug since my laptop is not representative of an average node.

ACK 747cff842481153357199bf9a81b5a4d82ea91fb

Tested with a regular (non-debug) build (see my previous comment) on an M1 Max from 2022.

Did some mutating/tweaking of ParseOutputs() as a sanity check that our functional tests catch it.