Merge bitcoin/bitcoin#36032: rpc: avoid quadratic output lookups
What the developer wrote
Authored by Ava Chow
Merge bitcoin/bitcoin#36032: rpc: avoid quadratic output lookups
747cff842481153357199bf9a81b5a4d82ea91fb rpc: avoid quadratic output lookups (Lőrinc)
Pull request description:
**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>
```cpp
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:
```python
Before ████████████████████ 1.80 s
After █████▒░░░░░░░░░░░░░░ 0.50 s -72%
```
Related to #35889
ACKs for top commit:
achow101:
ACK 747cff842481153357199bf9a81b5a4d82ea91fb
jonatack:
ACK 747cff842481153357199bf9a81b5a4d82ea91fb
jeanpablojp:
tACK 747cff842481153357199bf9a81b5a4d82ea91fb
hodlinator:
ACK 747cff842481153357199bf9a81b5a4d82ea91fb
Tree-SHA512: 154c9f583f6e7f4154882aeb1ae11c40b327d0ef04147e12a0fee749494ae95314cdfc56baad78723f3383f225d752654be0ae9ed7458b1c73f7a6a80922e3ef
What changed, and why it matters
This change fixes a performance bug in Bitcoin Core's RPC (remote procedure call) handling where creating a transaction with many outputs could take much longer than necessary. An authenticated RPC user could send a specially crafted request with thousands of outputs and temporarily slow down or stall a server worker. The fix makes the output parsing run in linear time instead of quadratic time, and removes a wallet-lock delay in the `sendmany` RPC. It is a denial-of-service improvement rather than a code-execution or theft bug.
Treat as a routine performance and DoS-hardening fix. No emergency response is warranted. Users running RPC services should include this fix in their normal upgrade cycle, especially if they expose RPC to multiple authenticated clients.
Security signals we found
Denial-of-service vector: authenticated RPC client can tie up a worker with a large request
Algorithmic complexity reduction from quadratic to linear output parsing
Wallet lock contention reduction for `sendmany`
No memory safety, authentication bypass, or confidentiality impact evident
Evidence from the diff
The patch modifies ParseOutputs() in src/rpc/rawtransaction_util.cpp. Previously the code iterated over outputs.getKeys() and then re-looked up each value via outputs[name_], which for UniValue objects is an O(n) scan, yielding O(n²) total parsing time. The patch retrieves the key and value arrays once (getKeys() and getValues()) and indexes them in parallel, making parsing O(n). The PR description notes that sendmany held the wallet lock during this parsing, so the quadratic behavior also blocked other wallet operations.
Changed components
src/rpc/rawtransaction_util.cppRPC transaction-creation endpoints using ParseOutputssendmany RPCInspect captured patch +7 / −3
### src/rpc/rawtransaction_util.cpp
@@ -105,19 +105,23 @@ std::vector<std::pair<CTxDestination, CAmount>> ParseOutputs(const UniValue& out
std::set<CTxDestination> destinations;
std::vector<std::pair<CTxDestination, CAmount>> parsed_outputs;
bool has_data{false};
- for (const std::string& name_ : outputs.getKeys()) {
+ const auto& keys{outputs.getKeys()};
+ const auto& values{outputs.getValues()};
+ for (size_t i{0}; i < keys.size(); ++i) {
+ const auto& name_{keys[i]};
+ const auto& value{values[i]};
if (name_ == "data") {
if (has_data) {
throw JSONRPCError(RPC_INVALID_PARAMETER, "Invalid parameter, duplicate key: data");
}
has_data = true;
- std::vector<unsigned char> data = ParseHexV(outputs[name_].getValStr(), "Data");
+ std::vector<unsigned char> data = ParseHexV(value.getValStr(), "Data");
CTxDestination destination{CNoDestination{CScript() << OP_RETURN << data}};
CAmount amount{0};
parsed_outputs.emplace_back(destination, amount);
} else {
CTxDestination destination{DecodeDestination(name_)};
- CAmount amount{AmountFromValue(outputs[name_])};
+ CAmount amount{AmountFromValue(value)};
if (!IsValidDestination(destination)) {
throw JSONRPCError(RPC_INVALID_ADDRESS_OR_KEY, std::string("Invalid Bitcoin address: ") + name_);
}Why this scored 59/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.