49196 Commits

Author SHA1 Message Date
David Gumberg
8b68287bf9 test: Make torcontrol max line length test stricter and test boundaries.
Adds a check that at the boundary of MAX_LINE_LENGTH, no disconnect
occurs.

Also makes the overlength test message exactly MAX_LINE_LENGTH + 1 to
test the boundary.

Drops the redundant node liveness check, which is covered by the later
check that the node reconnects.
2026-04-17 11:53:17 -07:00
stickies-v
c5ec2d5313 logging: replace FormatLogStrInPlace with Format
Return a new string built left-to-right instead of mutating one
with repeated insert(0, ...). Take a const log::Entry ref since
both call sites now have an Entry available. Also move
LogEscapeMessage inside so callers don't need to pre-escape.
2026-04-17 16:09:51 +01:00
stickies-v
3b92ec2036 logging: replace BufferedLog with log::Entry
Avoids duplication and ensures timestamp and mocktime are captured
at the same time.
2026-04-17 16:09:51 +01:00
Alexander Wiederin
07b9b13b45 doc: add integer type conventions in btck api remarks 2026-04-17 16:48:09 +02:00
Matthew Zipkin
f49a2afd94 test: interface_http follow-ups
- Only one node needed for test
- Use ascii encoding instead of utf-8
- Make tests independent of each other
- Expect HTTP error code 413 for too-large request
- Clarify python client race condition in comment
2026-04-17 10:45:03 -04:00
Alexander Wiederin
ba6287a449 kernel: align height parameters to int32_t in btck API
Aligns btck_chain_get_height and btck_chain_get_by_height to use int32_t
for height parameters and return values. Updates the C++ wrapper
accordingly.
2026-04-17 16:35:31 +02:00
Peter Zafonte
df44afdc98 kernel: expose btck_block_tree_entry_get_ancestor
Allows callers to jump to any ancestor of a block tree entry by height
using the skiplist-backed GetAncestor, which runs in O(log N) rather
than walking back one entry at a time with btck_block_tree_entry_get_previous.

Includes a C++ convenience wrapper and tests in btck_block_tree_entry_tests.
2026-04-17 09:23:22 -04:00
stickies-v
8115001cd4 logging: pass log::Entry through to logging functions
Use the entry's timestamp and thread_name, captured at the call
site, instead of re-capturing them in the logger.
2026-04-17 14:11:07 +01:00
stickies-v
b414913c73 util: add timestamp and thread_name to log::Entry 2026-04-17 14:03:29 +01:00
stickies-v
8a55b17751 util: make SourceLocation constructor explicit
Follow CppCoreGuidelines C.46:
https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#rc-explicit
2026-04-17 14:02:05 +01:00
fanquake
b02d6b0567 ci: drop -lstdc++ usage in msan fuzz job 2026-04-17 13:45:12 +01:00
fanquake
655a39ee14 ci: use llvm 22.1.3 2026-04-17 13:45:11 +01:00
merge-script
1fa34f90a2 Merge bitcoin/bitcoin#35095: doc: fix typos and minor formatting issues
bdc8e496da doc: fix typos and formatting in CONTRIBUTING, i2p, bitcoin-conf, files (Guillermo Fernandes)

Pull request description:

  Fix four small documentation issues found in actively maintained files:

  - `CONTRIBUTING.md`: "Valid areas as:" → "Valid areas are:" (grammar)
  - `doc/i2p.md`: remove double space after period
  - `doc/bitcoin-conf.md`: "some negating some lists" → "some negating lists" (duplicate word)
  - `doc/files.md`: missing space after comma in `**macOS**,the`

ACKs for top commit:
  maflcko:
    lgtm ACK bdc8e496da
  NellyNakhero:
    ACK bdc8e496da

Tree-SHA512: 15a5e284d517f7311a8c7c02a17292504a9eeafbaa81dc12a63a22fa1d49122e437e5647d9d0fbf397b5d150d0586632daccf0d2a7e7775a9bfd38083f0dfdcd
2026-04-17 10:05:35 +01:00
Guillermo Fernandes
bdc8e496da doc: fix typos and formatting in CONTRIBUTING, i2p, bitcoin-conf, files
- CONTRIBUTING.md: "Valid areas as" -> "Valid areas are"
- doc/i2p.md: remove double space after period
- doc/bitcoin-conf.md: "some negating some lists" -> "some negating lists"
- doc/files.md: missing space after comma in "macOS,the"
2026-04-16 23:18:20 -04:00
David Gumberg
ab5889796f refactor: torcontrol add connection checks to restart_with_mock 2026-04-16 18:11:44 -07:00
Hennadii Stepanov
e7d647388c Merge bitcoin/bitcoin#34923: depends: remove workaround for Make older than 4.2.90
f1e14dfbe9 depends: remove workaround for Make older than 4.2.90 (fanquake)

Pull request description:

  This was introduced for distros shipping older `make`, such as Ubuntu `20.04` (`4.2.1`). It's likely that any distros being used for Darwin and Windows cross compilation, are shipping a newer make at this point.

ACKs for top commit:
  hebasto:
    ACK f1e14dfbe9, I have reviewed the code and it looks OK.

Tree-SHA512: bb5d785e4804f0b0d51c5abba31ee4537cf04247801edef51a5da728c7df7fff1189625d222f91b8f5896f9ec71dc8dbd11614a69e13e0dcad6017cab7dd5874
2026-04-16 17:19:16 +01:00
merge-script
c4361e53cd Merge bitcoin/bitcoin#34757: guix: re-enable riscv exported symbol checking
19e99be011 guix: remove riscv exclusion from symbol check (fanquake)
47b7a9f666 guix: binutils 2.46.0 (fanquake)

Pull request description:

  Switching to binutils `2.46.0` fixes the spurious exported symbols (2.45.1 was still broken).

  The relevant upstream change is https://sourceware.org/git/?p=binutils-gdb.git;a=commit;h=9e10fcf71c1101fb6422d0f52de5e615ed8df71d.

  Fixes #28095.

ACKs for top commit:
  hebasto:
    re-ACK 19e99be011, only rebased and properly adjusted since my recent [review](https://github.com/bitcoin/bitcoin/pull/34757#pullrequestreview-4015011610).

Tree-SHA512: 5673e8df8e2297e41c3f50fbe87ee506684a7dd7e8be27fc5613853ace9732d92616c10870614f6b196ca71a581470eb6f432cfd102e1fce58bbaf18c599342e
2026-04-16 13:46:04 +01:00
MarcoFalke
fa16bc53d7 test: Require named arg for create_block ntime arg
The named arg is useful, so that the two integral args (possibly
integral literals) `height` and `ntime` are not confused.
2026-04-16 14:08:56 +02:00
MarcoFalke
fab352053d test: Remove unused create_coinbase imports 2026-04-16 14:08:53 +02:00
MarcoFalke
fad6deb3cb scripted-diff: Use new create_block height option
-BEGIN VERIFY SCRIPT-

 # Replace single-arg create_coinbase calls ...
 # ... followed by ntime arg
 sed --in-place --regexp-extended 's/create_block\((.+), create_coinbase\(([^,]+)\), /create_block(\1, height=\2, ntime=/g' $( git grep -l 'create_block(' )
 # ... not followed by any other args
 sed --in-place --regexp-extended 's/create_block\((.+), create_coinbase\(([^,]+)\)\)/create_block(\1, height=\2)/g'        $( git grep -l 'create_block(' )

-END VERIFY SCRIPT-
2026-04-16 14:08:33 +02:00
MarcoFalke
fa5eb74b96 test: Allow to set height in create_block
Previously, it was only possible to set the height indirectly by calling
create_coinbase outside the create_block function. This is fine, but
verbose and not needed.

Just like hashprev can be set directly (instead of using the value from
tmpl), allow height to be set directly.

Also, use it in one place. The other places are done in a scripted-diff.

Also, add a unit test for the new feature.
2026-04-16 14:08:17 +02:00
Torkel Rogstad
c54f37c1ba cli, rpc: add -rpcid option for custom request IDs
Add a -rpcid CLI argument to bitcoin-cli that allows setting a custom
string as the JSON-RPC request ID instead of the hardcoded default of 1.
This enables correlating requests and responses when debugging or when
multiple clients are making concurrent calls.

On the server side, include the request ID in the RPC debug log line
when it differs from the default value of 1, so that custom IDs are
visible in the debug.log output.
2026-04-16 12:58:49 +02:00
fanquake
4d040b7d62 doc: archive release notes for v31.0 2026-04-16 09:22:29 +01:00
merge-script
44ac0c32b9 Merge bitcoin/bitcoin#34401: kernel: add serialization method for btck_BlockHeader API
577a3e74c8 test: Add check for return type in `HasToBytes` concept (yuvicc)
1ad551281a kernel: Add Block Header serialization method (yuvicc)
86662623ec Add `SpanWriter` class for zero-allocation stream writing (yuvicc)

Pull request description:

  This adds serialization for `btck_BlockHeader` API. Also, updated the `CheckHandle` to compare the byte content instead of size.

  The changes here is done in two commits. First commit adds the `SpanWriter` class and next one moves the block header serialization to `SpanWriter`. See commit message for more details.

  Follow-up to #33822 .

ACKs for top commit:
  stickies-v:
    re-ACK 577a3e74c8
  alexanderwiederin:
    ACK 577a3e74c8
  theStack:
    Code-review ACK 577a3e74c8
  w0xlt:
    ACK 577a3e74c8

Tree-SHA512: 1eda5b204588ccb23e9357f68c5529474e7d248736a371c47d8db71ba6ca95e121869514478ad7a519d190e4c30725f64fd1ef4dd9f97d2627dc4441e51458e0
2026-04-15 15:47:33 +01:00
merge-script
53f4743c21 Merge bitcoin/bitcoin#35080: test: Add missing self.options.timeout_factor scale in tool_bitcoin_chainstate.py
fa02eb87df test: Add missing self.options.timeout_factor scale in tool_bitcoin_chainstate.py (MarcoFalke)

Pull request description:

  Without the factor, the test may fail when run cross-arch, possibly with sanitizers. E.g. in qemu-aarch64 in docker in a x86-VM.

ACKs for top commit:
  fanquake:
    ACK fa02eb87df

Tree-SHA512: 7dbf492de7478bcc95a62576499947fa83031c43496700657014aa9b29f6665c2a226b71287b71b8cd7a5240036c00f069f12ab231539e3387fe86ca298d6933
2026-04-15 15:13:41 +01:00
merge-script
edcf84c73a Merge bitcoin/bitcoin#35077: kernel: build: remove unused serfloat dependency
49895b9cbd kernel: build: remove unused serfloat dependency (Sebastian Falbesoner)

Pull request description:

  The serfloat module (more concretely, its two functions `{Encode,Decode}Double`) is only used for [fee estimation](7844a2f083/src/policy/fees/block_policy_estimator.cpp (L21)), which is not included in the bitcoinkernel library, so the linking dependency can be removed.

  (Not terribly important in practice, but: this reduces the static library size by ~1.5 KB (~2.7 KB unstripped) on my arm64 Linux machine.)

ACKs for top commit:
  davidgumberg:
    ACK 49895b9cbd
  stickies-v:
    ACK 49895b9cbd

Tree-SHA512: c3b4feec55cdc7476f54185db95c94e7365f5feadf09d3740d51dce32a1ceeef4d38ecf5c8cf7ca4ed326a12dab386bb104da978ff06bdf739889b2cfa81603d
2026-04-15 09:18:00 +01:00
MarcoFalke
fa02eb87df test: Add missing self.options.timeout_factor scale in tool_bitcoin_chainstate.py
Apply the timeout factor inside the add_block function.

Also, force named args for the two expected strings.

Also, add trailing comma for style.
2026-04-15 09:32:01 +02:00
Sebastian Falbesoner
49895b9cbd kernel: build: remove unused serfloat dependency
The serfloat module is only used for fee estimation, which is not
included in the bitcoinkernel library, so the dependency can be removed.
2026-04-14 23:57:37 +02:00
yuvicc
577a3e74c8 test: Add check for return type in HasToBytes concept
Add return type check for `ToBytes()` which should be convertible to
`std::span<const std::byte>`.
2026-04-14 19:19:41 +05:30
yuvicc
1ad551281a kernel: Add Block Header serialization method
Add `btck_block_header_to_bytes` serialization method to serialize a
`btck_BlockHeader` into an 80-byte buffer using `SpanWriter` to ensure
zero-allocation serialization.
2026-04-14 19:19:41 +05:30
yuvicc
86662623ec Add SpanWriter class for zero-allocation stream writing
Co-authored-by: stickies-v <stickies-v@protonmail.com>
2026-04-14 19:19:37 +05:30
David Gumberg
fbffe8a64a bench: improve VerifyNestedIfScript benchmark precision (make stack clearing untimed)
on `master`:

|               ns/op |                op/s |    err% |          ins/op |          cyc/op |    IPC |         bra/op |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|           19,890.59 |           50,275.02 |    1.3% |      673,992.65 |       85,238.74 |  7.907 |     143,404.89 |    0.0% |      0.01 | `VerifyNestedIfScript`

vs this commit:

|           ns/script |            script/s |    err% |      ins/script |      cyc/script |    IPC |     bra/script |   miss% |     total | benchmark
|--------------------:|--------------------:|--------:|----------------:|----------------:|-------:|---------------:|--------:|----------:|:----------
|           12,089.00 |           82,719.83 |    0.4% |      375,703.00 |       51,987.00 |  7.227 |      69,249.00 |    0.2% |      0.00 | `VerifyNestedIfScript`

Co-authored-by: Lőrinc <pap.lorinc@gmail.com>
2026-04-14 13:33:22 +02:00
Sebastian Falbesoner
616ee6fe74 bench: add script verification benchmark for P2TR script-path spends
To reflect the likely most common real-world scenario, a single
OP_CHECKSIG is contained in the Tapscript leaf.

While touching this benchmark, also set the operation unit to "script"
and do some minor refactorings to deduplicate code and improve readability.

Co-authored-by: David Gumberg <davidzgumberg@gmail.com>
Co-authored-by: Lőrinc <pap.lorinc@gmail.com>
2026-04-14 13:31:08 +02:00
merge-script
7844a2f083 Merge bitcoin/bitcoin#34772: test: modernize interface_http and cover more libevent behavior
422ca211ec test: ensure HTTP server enforces limits on headers and body size (Matthew Zipkin)
0c1a07e890 test: ensure HTTP server timeout is not caused by a delayed response (Matthew Zipkin)
f06de5c1ea test: clean up and modernize interface_http (Matthew Zipkin)

Pull request description:

  This is a follow-up to https://github.com/bitcoin/bitcoin/pull/32408 and a new prerequisite for #32061 in response to a few review comments there.

  ### New test: `check_server_busy_idle_timeout()`

  In https://github.com/bitcoin/bitcoin/pull/32061#discussion_r2872150590 it is pointed out that the idle timeout set by `-rpcservertimeout` could disconnect a client unfairly if it was the server that was taking too long to process a response. That misbehavior was confirmed and #32061 was updated to match current libevent behavior. This PR asserts the current libevent behavior by adding another test using RPC `waitforblock` past the `-rpcservertimeout` value and then verifying that the HTTP connection is still open.

  ### Expanded tests: `check_excessive_request_size()` and `check_chunked_transfer()`

  https://github.com/bitcoin/bitcoin/pull/32061#discussion_r2941508964 made me realize that I was not testing HTTPRequest body size at all, and that headers size was being tested one line at a time but not in total. The libevent server does both things so that behavior is asserted in these expanded tests, and the mechanism in #32061 was improved to match.

  ### Clean up `interface_http.py`

  Since I am extending this test module again I refactored the monolithic test to resemble the current functional test style in the repository, de-duplicating HTTP connection code with a helper class and separating individual test cases into functions.

ACKs for top commit:
  fjahr:
    ACK 422ca211ec
  Bortlesboat:
    re-ACK 422ca211ec. Checked out the rebased branch and ran interface_http.py locally, passes clean. Went through all three commits -- the helper class deduplication reads well and check_server_busy_idle_timeout is a nice addition from the #32061 discussion. One minor note inline.
  hodlinator:
    Concept ACK 422ca211ec
  theStack:
    ACK 422ca211ec

Tree-SHA512: 1165c9c49c8b1ae5a40a15e1d0f8275bb4d5e08a5eea7ae8b9d900bb34a85b29ba89c728b5e0866fbf289dd49aa5ece0af63e410e64aee70c89a19759c5ea3ff
2026-04-14 12:08:41 +01:00
optout
6ac49373aa test: Add clean shutdown to Socks5Server
The `Socks5Server` utility handles multiple incoming connections,
which are handled in separate background threads.
The `stop()` method unblocks and waits for the main background thread
cleanly, but it doesn't attempt to wait for any handler threads.
This change stores handler threads and connections, and attempts
to shut them down before `stop()` returns.

Co-authored-by: vasild <vd@FreeBSD.org>
Co-authored-by: w0xlt <94266259+w0xlt@users.noreply.github.com>
2026-04-13 16:35:52 +02:00
Ryan Ofsky
976985eccd Merge bitcoin/bitcoin#34124: validation: make CCoinsView a pure virtual interface
8783cc8056 refactor: inline `CCoinsViewBacked` implementation (Lőrinc)
86296f276d coins: make `CCoinsView` methods pure virtual (Lőrinc)
b637566c8d coins: add explicit `CoinsViewEmpty` noop backend (Lőrinc)
90c635c01c fuzz: keep backend assertions aligned to active backend (Lőrinc)
a9f92e3497 refactor: normalize CCoinsView whitespace and signatures (Lőrinc)
38a99f3344 scripted-diff: normalize `CCoinsView` naming (Lőrinc)
06172ef0d5 refactor: rename `hashBlock` to `m_block_hash` to avoid shadowing (Lőrinc)

Pull request description:

  ### Problem
  `CCoinsView` is the coins view interface, but historically it also provided built-in no-op behavior:

  * It provided default no-op implementations (returning `std::nullopt`, `uint256()`, `false`, or `nullptr`) instead of being pure virtual.
  * Callers could instantiate a bare `CCoinsView` and get silent no-op behavior.
  * Mixing the interface definition with a built-in dummy implementation blurred the abstraction boundary.

  ### Context
  This is part of the ongoing coins caching cleanup in #34280.

  ### Fix
  This PR separates the interface from no-op behavior and makes `CCoinsView` pure virtual in incremental steps:
  * Add `CoinsViewEmpty` as an explicit no-op coins view for tests, benchmarks, and temporary backends.
  * Replace direct bare-`CCoinsView` test and dummy instantiations with `CoinsViewEmpty`.
  * Make all `CCoinsView` methods pure virtual (`PeekCoin`, `GetCoin`, `HaveCoin`, `GetBestBlock`, `GetHeadBlocks`, `BatchWrite`, `Cursor`, `EstimateSize`).
  * Remove the legacy default implementations from `coins.cpp`.
  * Update fuzz and dummy backends to use `CoinsViewEmpty` explicitly.

ACKs for top commit:
  w0xlt:
    reACK 8783cc8056
  ryanofsky:
    Code review ACK 8783cc8056. Just updated comments and variable name since last review. The fuzz test code is much clearer now IMO
  andrewtoth-exo:
    ACK 8783cc8056
  ajtowns:
    ACK 8783cc8056

Tree-SHA512: cfc831578aa309788c1b5dafbfecca3de388cc4215534c3f3df24f90d7770ed37b1fd7aa134df91d611d0a1ca75929accb98d5ed7df7b52851c259e04f08e4a3
2026-04-13 08:40:36 -04:00
Hennadii Stepanov
09c0e37789 ci: Rename vcpkg binary cache entity to force rebuild 2026-04-13 12:32:36 +01:00
MarcoFalke
fa1015bbcb refactor: Use NodeClock::time_point for m_connected
Also, increase the precision to the native one, over prescribing second
precision.
2026-04-13 09:49:13 +02:00
merge-script
7aa033d3d4 Merge bitcoin/bitcoin#34773: test: migrate functional test equality asserts to assert_equal
3fd68a95e6 scripted-diff: replace remaining Python test equality asserts (Lőrinc)
301b1d7b1f test: add missing `assert_equal` imports (Lőrinc)
06a4176c42 test: convert truthy asserts in `wallet_miniscript` and `rpc_psbt` (Lőrinc)
d9a3cf20a4 test: convert simple equality asserts in excluded files (Lőrinc)
23c06d4e6d test: convert equality asserts with comments or special chars (Lőrinc)
dcd90fbe54 test: prep manual equality assert conversions (Lőrinc)
4f4516e3f6 test: split equality asserts joined by `and` (Lőrinc)
76a5570b36 test: use `in` for two-value equality asserts (Lőrinc)

Pull request description:

  ### Problem
  Plain `assert x == y` is a poor fit for this test framework, `assert_equal()` gives more useful failure output and keeps equality checks consistent with the rest of the functional tests.

  ### Design
  A simple scripted diff cannot safely rewrite all of them because many files use `==` inside larger expressions, such as chained conditions, comprehensions, and other compound assertions. That makes a one-shot mechanical conversion either incorrect or harder to review.

  ### Fix
  This series first rewrites the non-mechanical cases into standalone assertions so patterns are easier to identify, then applies a scripted diff to the remaining cases that are safe to convert mechanically.

  Partially fixes https://github.com/bitcoin/bitcoin/issues/23119 by adjusting the `==` case only (which is similar to the `BOOST` alternatives so it's expected to be uncontroversial).

ACKs for top commit:
  maflcko:
    review ACK 3fd68a95e6 🚆
  rkrux:
    lgtm ACK 3fd68a95e6
  theStack:
    ACK 3fd68a95e6

Tree-SHA512: 6950ffa044db72d6235305f4c0247254e7e8f57ee1c8300e553953963914a6360ca71569fe315ecb333cf0e62f78b3a24603717f64229783761f8c1b5958fc12
2026-04-13 15:36:21 +08:00
merge-script
34c3279d25 Merge bitcoin/bitcoin#34623: Update secp256k1 subtree to latest master
dfd54c959e Squashed 'src/secp256k1/' changes from 57315a6985..7262adb4b4 (fanquake)

Pull request description:

  https://github.com/bitcoin-core/secp256k1/pull/1760 was merged upstream, which improves test parallelism, and reduces overall runtime. Our longest running tests are secp256k1 tests (`secp256k1_tests`), so we might want to pull this down, to speedup all of our ctest invocations.

  The new upstream code increases output verbosity, i.e the test list is now ~330, and we have output like:
  ```bash
  Label Time Summary:
  secp256k1_exhaustive        =  19.52 sec*proc (1 test)
  secp256k1_noverify_tests    =  45.65 sec*proc (91 tests)
  secp256k1_tests             =  90.55 sec*proc (91 tests)
  ```
  maybe we can/should mute that somewhat?

ACKs for top commit:
  hebasto:
    ACK b7f9178976.

Tree-SHA512: 098a8b54d3a489e6ad7866f4e5152a5bc6a0e1da69b2a84d8795423e64faa42772cbcb194feac228a547869d2b3be2198aaf96a5e1bb7d45a2e385fd5e78bafd
2026-04-13 15:24:24 +08:00
merge-script
7e3e22e1f7 Merge bitcoin/bitcoin#35047: doc: fix typo 'parlor' to 'parlance' in developer-notes
ea893cff07 doc: fix typo 'parlor' to 'parlance' in developer-notes (ArvinFarrelP)

Pull request description:

  Fix a small typo in doc/developer-notes.md.

  Replace "parlor" with "parlance" to use the correct term in the context of C++ terminology.

ACKs for top commit:
  maflcko:
    lgtm ACK ea893cff07
  l0rinc:
    ACK ea893cff07

Tree-SHA512: 5437e0eb1b40aa1eafe8a0482350ed6259ec3492f64e7ba8d046358a3dd9cf95bfc38825b781350fd321c453cc23dddb6a14fe7f5087e56c77a17e3d3e233de4
2026-04-10 22:45:03 +08:00
ArvinFarrelP
ea893cff07 doc: fix typo 'parlor' to 'parlance' in developer-notes 2026-04-10 16:05:47 +07:00
Torkel Rogstad
701bc2dc02 contrib: Fix NameError in signet miner gbt()
The logging.warning call referenced `bci["bestblockhash"]`, a variable
from the calling scope `do_generate()` that is not available inside the
`Generate.gbt()` method. This would crash with a NameError when
getblocktemplate returned a template based on an unexpected previous
block.

Use the `bestblockhash` parameter that was already being passed in and
used correctly in the comparison on the line above.

The bug was introduced in 7b31332370 when the gbt logic was extracted
into its own method — the if-condition was updated but the logging
call was not.
2026-04-10 10:23:30 +02:00
Murch
7249b376a0 opt: Skip UTXOs with worse waste, same eff_value
When two successive UTXOs differ in waste but match in effective value,
we can skip the second if the first is not selected, because all input
sets we can generate by swapping out a less wasteful UTXOs with a more
wastefull UTXO of matching effective value would be strictly worse.

Also expand documentation of Branch and Bound.
2026-04-09 16:48:10 -07:00
Murch
5204291860 opt: Skip evaluation of equivalent input sets
When two successive UTXOs match in effective value and weight, we can
skip the second if the prior is not selected: adding it would create an
equivalent input set to a previously evaluated.

E.g. if we have three UTXOs with effective values {5, 3, 3} of the same
weight each, we want to evaluate
{5, _, _}, {5, 3, _}, {5, 3, 3}, {_, 3, _}, {_, 3, 3},
but skip {5, _, 3}, and {_, _, 3}, because the first 3 is not selected,
and we therefore do not need to evaluate the second 3 at the same
position in the input set.

If we reach the end of the branch, we must SHIFT the previously selected
UTXO group instead.
2026-04-09 16:47:47 -07:00
Murch
ba1807b981 coinselection: Track effective_value lookahead
Introduces a dedicated data structure to track the total
effective_value available in the remaining UTXOs at each index of the
UTXO pool. In contrast to the original approach in BnB, this allows us
to immediately jump to a lower index instead of visiting every UTXO to
add back their eff_value to the lookahead.
2026-04-09 16:46:17 -07:00
Murch
fa226ab902 coinselection: BnB skip exploring high waste
At high feerates adding more inputs will increase the waste score. If
the current waste is already higher than the best selection’s we cannot
improve upon the best selection. All solutions that include the current
selection with more additional inputs must be worse than the best
selection so far: SHIFT

This optimization only works at high feerates, because at low feerates,
adding more inputs decreases waste, so this condition would exit
prematurely. We would never attempt input sets with higher weight than
the prior best selection, even though we would prefer those at low
feerates.
2026-04-09 16:42:15 -07:00
Murch
7ecea1dc5d coinselection: Track whether BnB completed
BnB may not be able to exhaustively search all potentially interesting
combinations for large UTXO pools, so we keep track of whether the
search was terminated by the iteration limit.
2026-04-09 16:41:48 -07:00
Murch
3ca0f36164 coinselection: rewrite BnB in CoinGrinder-style
In the original implementation of BnB, the state of the search is
backtracked by explicitly walking back to the omission branch and then
testing again. This retests an equivalent candidate set as before, e.g.,
after backtracking from {ABC}, it would evaluate {AB_}, before trying
{AB_D}, but {AB_} is equivalent to {AB} which was tested before.

CoinGrinder tracks the state of the search instead by remembering which
UTXO was last added and explicitly shifting from that UTXO directly to
the next, so after {ABC}, it will immediately move on to {AB_D}. We
replicate this approach here.

The description of the two optimizations is removed from the
documentation as they will only be implented in a later commit.
2026-04-09 16:41:22 -07:00
Murch
2e73739837 coinselection: Track BnB iteration count in result
The expected iteration count demonstrates how the following improvements
reduce iterations will help catch any regressions in the future.
2026-04-09 16:37:50 -07:00