rpc: avoid quadratic output lookups

[l0rinc]

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:

parse_outputs test

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);
    }
}

E.g. on my M4 Max:

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

Related to #35889

[DrahtBot]

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

Code Coverage & Benchmarks

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

Reviews

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

Type	Reviewers
Concept ACK	jonatack

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

[maflcko]

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.

[DrahtBot]

🚧 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.}

Hints

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.

[maflcko]

unrelated comment: wen c++23?

src/univalue/include/univalue.h
@@ -12,0 +13 @@
+#include <ranges>
@@ -119,0 +120,5 @@ public:
+    auto getObjectItems() const
+    {
+        checkType(VOBJ);
+        return std::views::zip(keys, values);
+    }

[l0rinc]

Yeah, was also wondering about the same :)

[jonatack]

Concept ACK

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

test diff

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()

---

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 @ 747cff8

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

[l0rinc]

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.