← Watch feed
Merge bitcoin/bitcoin#36096: rpc: avoid quadratic JSON construction when keys are unique
Public commit record
91/100 · Strong
What the developer wrote
Authored by merge-script
Merge bitcoin/bitcoin#36096: rpc: avoid quadratic JSON construction when keys are unique
74ddf1c0a0ef8447686f59044b2fc2ee8d78c0e4 refactor: use structured bindings for map entries (Lőrinc)
21d5d5cb739062d40182cab66abac8eaf87a3c25 rpc: append unique container keys directly (Lőrinc)
23e512a58e69e16ede660ea46d0f6e15408bb371 rpc: avoid quadratic prioritised transaction JSON (Lőrinc)
Pull request description:
**Problem:** `getprioritisedtransactions` lets node operators inspect fee adjustments.
While building the response, the RPC checks each transaction ID against all previous IDs, even though duplicates are impossible.
The same unnecessary search appears in a few other RPC responses built directly from `std::map` or `std::set` keys.
**Fix:** Each changed response key comes from a `std::map` or `std::set`, where keys are unique, so insertion can skip the linear `findKey()` call.
**Reproducer:** On a RPi 4, the test below took almost a minute before the fix and about half that time after.
The other changed map and set loops perform the same per-key search, so their response construction has the same quadratic-to-linear scaling as the number of entries grows.
<details>
<summary>Reproducer commands</summary>
```patch
diff --git a/test/functional/mining_prioritisetransaction.py b/test/functional/mining_prioritisetransaction.py
--- a/test/functional/mining_prioritisetransaction.py
+++ b/test/functional/mining_prioritisetransaction.py
@@ -11,6 +11,7 @@ from test_framework.blocktools import NORMAL_GBT_REQUEST_PARAMS
from test_framework.messages import (
COIN,
MAX_BLOCK_WEIGHT,
+ ser_uint256,
)
from test_framework.test_framework import BitcoinTestFramework
from test_framework.util import (
@@ -215,4 +216,10 @@ class PrioritiseTransactionTest(BitcoinTestFramework):
assert_raises_rpc_error(-1, "getprioritisedtransactions",
self.nodes[0].getprioritisedtransactions, True)
+ self.log.info("Test getprioritisedtransactions order")
+ txids = [ser_uint256(i).hex() for i in range(20_000, 0, -1)]
+ self.nodes[0].batch([self.nodes[0].prioritisetransaction.get_request(txid, 0, 1) for txid in txids])
+ assert_equal(list(self.nodes[0].getprioritisedtransactions()), txids[::-1])
+ self.clear_prioritisation(self.nodes[0])
+
# Test `prioritisetransaction` invalid `txid`
```
</details>
ACKs for top commit:
sedited:
ACK 74ddf1c0a0ef8447686f59044b2fc2ee8d78c0e4
hodlinator:
re-ACK 74ddf1c0a0ef8447686f59044b2fc2ee8d78c0e4
Tree-SHA512: 0e9204a3dab448f370c37f668dc877c689b6cfd273242ab72fc54551717f58fec00ff6f199b009d8980a5549f1cea1607f91c6afc1e06e6aa86c154d2a15cb0d
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Mentions testing or verification✓ Links an issue, advisory, or supporting reference
What changed, and why it matters
This change is a performance improvement, not a security fix. It replaces a slow method for building JSON responses in several Bitcoin RPC commands with a faster one. The old method could waste CPU time when returning very large responses because it unnecessarily checked for duplicate keys in containers that cannot have duplicates. The new method skips that check, making large responses faster to generate. There is no indication this change fixes a vulnerability or can be directly exploited.
Recommended action
Treat as a routine performance optimization. No security response is needed. Operators running nodes with very large mempools or many prioritised transactions may benefit from lower RPC latency after upgrading, but this is not a security patch.
Security signals we found
01
Performance-only refactor with no semantic change to returned data
02
No input validation, memory safety, or authorization changes
03
No CVE, advisory, or vendor security framing in commit or PR description
04
No bug class such as buffer overflow, injection, or DoS vector is introduced or fixed
Evidence from the diff
The commit changes multiple RPC handlers to use UniValue::pushKVEnd() instead of UniValue::pushKV() when inserting keys sourced from std::map or std::set containers. pushKV() performs a linear findKey() lookup to reject duplicates, which yields quadratic O(n²) JSON construction time for unique-key containers. The patch converts these to linear O(n) appends. Affected RPCs include getblockstats, getmempoolancestors, getmempooldescendants, getprioritisedtransactions, getpeerinfo, and decodepsbt. The PR description frames this as a performance/reproducer issue (RPi 4 test time drops from ~60s to ~30s for 20,000 prioritised transactions).
Changed components
src/rpc/blockchain.cppsrc/rpc/mempool.cppsrc/rpc/mining.cppsrc/rpc/net.cppsrc/rpc/rawtransaction.cppUniValue JSON constructionInspect captured patch +22 / −20
### src/rpc/blockchain.cpp
@@ -2213,7 +2213,7 @@ static RPCMethod getblockstats()
if (value.isNull()) {
throw JSONRPCError(RPC_INVALID_PARAMETER, strprintf("Invalid selected statistic '%s'", stat));
}
- ret.pushKV(stat, value);
+ ret.pushKVEnd(stat, value);
}
return ret;
},
### src/rpc/mempool.cpp
@@ -788,7 +788,7 @@ static RPCMethod getmempoolancestors()
const CTxMemPoolEntry &e = *ancestorIt;
UniValue info(UniValue::VOBJ);
entryToJSON(mempool, info, e);
- o.pushKV(e.GetTx().GetHash().ToString(), std::move(info));
+ o.pushKVEnd(e.GetTx().GetHash().ToString(), std::move(info));
}
return o;
}
@@ -853,7 +853,7 @@ static RPCMethod getmempooldescendants()
const CTxMemPoolEntry &e = *descendantIt;
UniValue info(UniValue::VOBJ);
entryToJSON(mempool, info, e);
- o.pushKV(e.GetTx().GetHash().ToString(), std::move(info));
+ o.pushKVEnd(e.GetTx().GetHash().ToString(), std::move(info));
}
return o;
}
### src/rpc/mining.cpp
@@ -606,7 +606,7 @@ static RPCMethod getprioritisedtransactions()
if (delta_info.in_mempool) {
result_inner.pushKV("modified_fee", *delta_info.modified_fee);
}
- rpc_result.pushKV(delta_info.txid.GetHex(), std::move(result_inner));
+ rpc_result.pushKVEnd(delta_info.txid.GetHex(), std::move(result_inner));
}
return rpc_result;
},
### src/rpc/net.cpp
@@ -293,16 +293,18 @@ static RPCMethod getpeerinfo()
obj.pushKV("minfeefilter", ValueFromAmount(statestats.m_fee_filter_received));
UniValue sendPerMsgType(UniValue::VOBJ);
- for (const auto& i : stats.mapSendBytesPerMsgType) {
- if (i.second > 0)
- sendPerMsgType.pushKV(i.first, i.second);
+ for (const auto& [message_type, total_bytes] : stats.mapSendBytesPerMsgType) {
+ if (total_bytes > 0) {
+ sendPerMsgType.pushKVEnd(message_type, total_bytes);
+ }
}
obj.pushKV("bytessent_per_msg", std::move(sendPerMsgType));
UniValue recvPerMsgType(UniValue::VOBJ);
- for (const auto& i : stats.mapRecvBytesPerMsgType) {
- if (i.second > 0)
- recvPerMsgType.pushKV(i.first, i.second);
+ for (const auto& [message_type, total_bytes] : stats.mapRecvBytesPerMsgType) {
+ if (total_bytes > 0) {
+ recvPerMsgType.pushKVEnd(message_type, total_bytes);
+ }
}
obj.pushKV("bytesrecv_per_msg", std::move(recvPerMsgType));
obj.pushKV("connection_type", ConnectionTypeAsString(stats.m_conn_type));
### src/rpc/rawtransaction.cpp
@@ -1164,8 +1164,8 @@ static RPCMethod decodepsbt()
// Unknown data
UniValue unknowns(UniValue::VOBJ);
- for (auto entry : psbtx.unknown) {
- unknowns.pushKV(HexStr(entry.first), HexStr(entry.second));
+ for (auto [key, value] : psbtx.unknown) {
+ unknowns.pushKVEnd(HexStr(key), HexStr(value));
}
result.pushKV("unknown", std::move(unknowns));
@@ -1272,7 +1272,7 @@ static RPCMethod decodepsbt()
if (!input.ripemd160_preimages.empty()) {
UniValue ripemd160_preimages(UniValue::VOBJ);
for (const auto& [hash, preimage] : input.ripemd160_preimages) {
- ripemd160_preimages.pushKV(HexStr(hash), HexStr(preimage));
+ ripemd160_preimages.pushKVEnd(HexStr(hash), HexStr(preimage));
}
in.pushKV("ripemd160_preimages", std::move(ripemd160_preimages));
}
@@ -1281,7 +1281,7 @@ static RPCMethod decodepsbt()
if (!input.sha256_preimages.empty()) {
UniValue sha256_preimages(UniValue::VOBJ);
for (const auto& [hash, preimage] : input.sha256_preimages) {
- sha256_preimages.pushKV(HexStr(hash), HexStr(preimage));
+ sha256_preimages.pushKVEnd(HexStr(hash), HexStr(preimage));
}
in.pushKV("sha256_preimages", std::move(sha256_preimages));
}
@@ -1290,7 +1290,7 @@ static RPCMethod decodepsbt()
if (!input.hash160_preimages.empty()) {
UniValue hash160_preimages(UniValue::VOBJ);
for (const auto& [hash, preimage] : input.hash160_preimages) {
- hash160_preimages.pushKV(HexStr(hash), HexStr(preimage));
+ hash160_preimages.pushKVEnd(HexStr(hash), HexStr(preimage));
}
in.pushKV("hash160_preimages", std::move(hash160_preimages));
}
@@ -1299,7 +1299,7 @@ static RPCMethod decodepsbt()
if (!input.hash256_preimages.empty()) {
UniValue hash256_preimages(UniValue::VOBJ);
for (const auto& [hash, preimage] : input.hash256_preimages) {
- hash256_preimages.pushKV(HexStr(hash), HexStr(preimage));
+ hash256_preimages.pushKVEnd(HexStr(hash), HexStr(preimage));
}
in.pushKV("hash256_preimages", std::move(hash256_preimages));
}
@@ -1448,8 +1448,8 @@ static RPCMethod decodepsbt()
// Unknown data
if (input.unknown.size() > 0) {
UniValue unknowns(UniValue::VOBJ);
- for (auto entry : input.unknown) {
- unknowns.pushKV(HexStr(entry.first), HexStr(entry.second));
+ for (auto [key, value] : input.unknown) {
+ unknowns.pushKVEnd(HexStr(key), HexStr(value));
}
in.pushKV("unknown", std::move(unknowns));
}
@@ -1567,8 +1567,8 @@ static RPCMethod decodepsbt()
// Unknown data
if (output.unknown.size() > 0) {
UniValue unknowns(UniValue::VOBJ);
- for (auto entry : output.unknown) {
- unknowns.pushKV(HexStr(entry.first), HexStr(entry.second));
+ for (auto [key, value] : output.unknown) {
+ unknowns.pushKVEnd(HexStr(key), HexStr(value));
}
out.pushKV("unknown", std::move(unknowns));
}Risk score
Our methodology →Why this scored 20/100
Human-validated context
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
No validated notes yet.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.