Deterministic, Order-Independent Coin Selection for Privacy Wallets

Abstract

Coin selection is the step in which a wallet chooses which of its spendable outputs to spend in order to fund a transaction. A privacy-motivated chooser treats the outputs of one key as a single all-or-nothing unit, so that assembling a payment from several keys does not disclose more of the holder's balance than it has to, and it randomises its choice among the sufficient subsets so that the selection carries no fixed pattern. A wallet does not observe the chain itself: it learns which outputs it holds from a source that returns them in some order, and that source chooses the order. This BRC shows that if the chooser's randomised search walks the candidate outputs in the order the source enumerates them, the source keeps a channel into the result. It can bias which of the holder's keys are spent together, and so publicly linked, in one transaction, and two spends built from the same set of outputs can differ when the set is enumerated in two different orders. This BRC requires that coin selection be a pure function of the candidate output set and a wallet-held secret, invariant under every permutation of the order in which the candidates are enumerated. It gives a conforming construction, specified to the byte: a canonical serialisation of an outpoint, a canonical order over candidates and over the all-or-nothing groups derived from that serialisation, a pseudo-random source seeded from the canonical serialisation of the set and the wallet secret, and a search that runs over the canonical order so that no step can see the enumeration order. It states a conformance test, that one output set enumerated in any order yields one selection, and it states what is left to the implementation: the objective that ranks sufficient subsets, and the construction of change. Test vectors fix a candidate set, a wallet secret and several target amounts, and show the selection is identical across a batch of input permutations.

Motivation

A wallet funding a transaction holds a pool of candidate outputs and must choose a subset that covers the amount to be paid plus the fee. The cheapest rule by fee alone would consolidate many small outputs, but that discloses the holder's balance and links keys that need not be linked, so a privacy-motivated chooser does something else. It groups the candidates so that all the outputs controlled by one key form a single unit that is spent all or nothing, because a part-spend of a key both reveals that the key held more and leaves change that ties the remaining outputs of that key to the spend. Among the subsets of groups that are sufficient it samples, with a pseudo-random source, rather than always taking a fixed shape, and it prefers a result whose change resembles an ordinary payment over one that stands out. The intent of all of this is that an observer of the chain should learn as little as possible about the holder from the shape of a spend and from which keys appear together in it.

A wallet does not read the chain directly. It learns which outputs it owns from a source: an overlay service, a basket kept by a storage provider, or a direct delivery. BRC-192 describes exactly this arrangement, an application runtime that "learns about Bitcoin outputs from overlays, wallet baskets and direct delivery" through replaceable source adapters, and it is explicit that the order in which a source reports outputs is the source's own: "Off-chain output/withdraw/re-entry order is per source generation and sequence, not Bitcoin transaction order", and "Presentation sorting is not an event order". The order a wallet sees its candidates in is therefore chosen by the source, and the source may be hostile, or merely stale after a resync, or simply a different source than last time.

If the chooser's randomised search walks the candidates, or the groups, in the order they were enumerated, that order reaches the result. The failure is quiet. A wallet that seeds its pseudo-random source from the candidates still looks deterministic in a single test, because the same source returns the same order twice, so the defect does not appear until the order changes. It has two consequences.

1. Key-linkage steering. A common search samples a permutation of the candidate groups, walks it, and stops at the first prefix that is sufficient. If the groups are indexed in enumeration order, the map from an index to a group is a function of that order, so the prefix the search stops on, and therefore which keys are spent together in one transaction, is a function of the enumeration order even when the pseudo-random stream is not. The party that controls the order thus keeps a residual hand in which of the holder's keys are publicly linked in a single spend. That is the precise thing a privacy chooser exists to decide, so leaving any of it to an outside party defeats the chooser.

2. Non-reproducibility. The guarantee a privacy chooser wants to make, that the same candidate set always funds a payment with the same outputs, fails across a resync or across two sources that return the candidates in two orders. A wallet that re-derives a change key, re-attempts a broadcast, or rebuilds a stuck transaction after a resync then selects a different set of inputs for what the holder means as one payment. The two attempts spend overlapping but unequal inputs, which an observer correlates, and any change key committed to one attempt is now exposed by a second.

Seeding the pseudo-random source from a function of the candidates that ignores their order, for example from their outpoints sorted and concatenated, is necessary and is not enough on its own. It fixes the random stream, but if the search still walks the candidates in enumeration order, the subset the stream selects is still read off an order-dependent arrangement. Both the seed and the order of the candidates the search walks must be functions of the set alone. This BRC requires both.

No existing standard constrains the choice. BRC-1 and BRC-100 specify how an application requests a transaction and how the wallet returns it, and require only that the wallet "unlock a sufficient number of UTXOs to fund the transaction"; neither says how the candidates are chosen. BRC-177 refers to "ordinary wallet coin selection" as a process already present in a wallet and places "allocation algorithms" among implementation details. BRC-228 makes a payment's remittance unlinkable from the sender's long-term identity, yet it leaves the inputs to "the sender's normal BRC-100 wallet" and states that observers "analyzing the full transaction, including shared inputs, change patterns, timing, and amounts, may still correlate payments", with no mitigation offered. The unlinkability that standard builds at the remittance is undone at the inputs if the input choice leaks. A single requirement on the selection, stated once and testable, closes the channel for every one of these.

Scope and conformance

This BRC specifies one property of a coin selector and one construction that has it. Section 2 states the threat precisely, as the thing conformance defends against. Section 3 is the normative requirement: the output of selection is a pure function of the candidate output set and a wallet-held secret, and is invariant under any reordering of the candidates. Section 4 gives a construction that meets it, specified to the byte: a canonical outpoint serialisation (4.1), a canonical order over candidates and groups (4.2), a pseudo-random source (4.3), its seed (4.4), the order-dependent search run over the canonical order (4.5), and a keyed tie-break over the candidate subsets so the final choice among equally good subsets is order-independent and unpredictable to an observer without the secret (4.6). Section 5 is the conformance test. Section 6 lists what is out of scope, and section 7 lists every requirement by role.

Out of scope are the objective function that ranks one sufficient subset above another (a chooser is free to prefer fewer inputs, change that resembles the payment, or any other goal), the construction of change (how many change outputs a spend has, their amounts, and any rounding), the fee rate and the dust limit, how a wallet obtains and validates its candidate set, and how a caller pins a particular output to be spent rather than leaving the choice to the wallet (BRC-164). This BRC constrains how the candidates are chosen when the choice is the wallet's; it does not constrain what a chosen subset is then used to build.

The key words MUST, MUST NOT, SHOULD, SHOULD NOT and MAY are to be interpreted as described in RFC 2119 and RFC 8174 when, and only when, they appear in capitals. Three roles are used: a chooser selects a subset of the candidates to fund a transaction, an enumerator is the source that supplies the candidate outputs to the chooser in some order (a source adapter, a basket, a cache, or an in-memory list filled from any of these), and a verifier checks that a chooser is order-independent (a test harness, or a reviewer).

Relationship to existing standards

Where the candidates come from: BRC-46, BRC-45 and BRC-192

BRC-46 tracks a wallet's spendable outputs in baskets, and BRC-45 frames each such output as a token the wallet holds; together they are the usual origin of the candidate set a chooser is handed. BRC-192 is the general case: a runtime that learns its outputs from replaceable sources and states, as quoted in the Motivation, that the order a source reports outputs in is the source's own and is not a chain order. This BRC takes the candidate set from any such origin and requires the chooser to depend on the set and not on the order the origin reported it in.

Coin selection left unspecified: BRC-1, BRC-100 and BRC-177

BRC-1 (historical, now the createAction family of BRC-100) specifies the request for a transaction and the returned transaction, and requires sufficient funding and change capture, but gives no selection algorithm. BRC-177 names "ordinary wallet coin selection" and leaves "allocation algorithms" to the implementation. This BRC adds one requirement to that unspecified step without changing any request or response shape: the step must be order-independent. A wallet can conform to this BRC and to each of those without altering its interface.

Choosing among many, against targeting one: BRC-164

BRC-164 lets an application tag a held output with a stable id: key so it can later name that one output for spending through standard list and spend targeting. That is targeting a known output. This BRC governs the complementary case, when the caller has not named an output and the wallet must choose among its candidates. A wallet honours a BRC-164 target by spending the named output and applies this BRC to whatever further candidates it must add to reach a sufficient amount. The two do not conflict and address different moments.

A privacy goal this completes: BRC-228

BRC-228 makes a payment's remittance unlinkable from the sender's identity key but, as quoted in the Motivation, leaves the inputs to the ordinary wallet and acknowledges that shared inputs and change can still correlate payments. The input choice is one of the correlating surfaces it names. A chooser that conforms to this BRC removes the enumerator's influence over that surface; it does not by itself make inputs unlinkable, which the Privacy Considerations treat.

Outpoint format: BRC-36

BRC-36 writes an outpoint in JSON as the string "<txid>.<vout>" and in binary as the 32 bytes of the transaction id followed by the output index. Section 4.1 fixes one serialisation of an outpoint for use as a sort key and a seed input, consistent with that binary layout, and the test vectors give both forms for every candidate.

Specification

1. Terminology

• Candidate output (or candidate): a spendable output the wallet holds and may spend, identified by its outpoint and carrying a value in satoshis and a group key (below).
• Outpoint: the pair of a 32-byte transaction id and an output index, identifying one output of one transaction. Outpoints are globally unique: no two distinct candidates share one.
• Candidate set: the set of candidate outputs offered to the chooser for one transaction. It is a set: membership is what matters, and the order in which its members are presented is the enumeration and is not part of the set.
• Enumeration: a particular ordering of the candidate set, as supplied by an enumerator. A permutation of an enumeration is another enumeration of the same set.
• Group: a maximal subset of the candidate set that shares a group key and is spent all or nothing. A privacy chooser groups by the key that controls the output, so that a group is "every candidate of one key"; the group key is opaque to this BRC, which requires only that grouping depend on the candidates and not on their enumeration.
• Group key: the opaque value by which candidates are grouped, equal for two candidates that must be spent together or not at all, and distinct otherwise.
• Target amount R: the least total value a selected subset must reach to be sufficient, inclusive of the fee the resulting transaction will owe. How R is computed is out of scope; a chooser evaluates sufficiency against it.
• Sufficient: a set of groups is sufficient when the sum of the values of its members is at least R.
• Selection: the subset of the candidate set the chooser returns, as a set of candidates (equivalently, of outpoints). It is the chooser's output and the object on which order-independence is required.
• Wallet secret: a high-entropy byte string held by the wallet, stable over the life of the wallet, specific to coin selection, and not derivable from the candidate set by an observer. It keys the pseudo-random source and is the whole basis of the selection's unpredictability (section 4.4, the Mathematical and cryptographic basis).
• Pseudo-random source (PRNG): the deterministic byte source of section 4.3, seeded once per selection.

Hex strings below are byte strings in the order their bytes appear.

2. Threat model

The chooser does not choose the order in which it receives its candidates; an enumerator does (section 1, and BRC-192). The enumerator may be adversarial, or stale, or simply different from one selection to the next. The property this BRC defends is that nothing the enumerator chooses reaches the selection. Concretely, an order-dependent chooser gives the enumerator two capabilities, and a conforming chooser denies both.

1. Steering which keys are linked. The enumerator, by choosing the order, influences which groups the chooser spends together, and so which of the holder's keys are co-spent in one transaction and thereby publicly linked on the chain. A hostile enumerator aims a spend's input set at keys it wishes to see associated; a stale one does so by accident. Either way the holder's privacy decision, which keys to link, is partly the enumerator's.

2. Forcing two selections of one set to differ. The enumerator, by returning the same candidate set in two different orders at two times, causes an order-dependent chooser to select two different subsets for what the holder means as one payment. This breaks reproducibility across a resync and across a change of source, with the input-correlation and change-exposure consequences of the Motivation.

A chooser is conforming when its selection is a pure function of the candidate set and the wallet secret, so that an enumerator's only influence is over which candidates exist, never over the order, and so has neither capability.

3. The determinism requirement

Let C be the candidate set, w the wallet secret, and R the target amount. Write choose(C, w, R) for the selection a chooser returns.

• R1. A conforming chooser's selection MUST be a pure function of C, w and R. For any two enumerations E and E' of the same set C, with the same w and R, a chooser MUST return the same selection: choose(E, w, R) = choose(E', w, R) as sets of outpoints. Equivalently, the selection MUST be invariant under every permutation of the candidate enumeration.
• R2. A conforming chooser MUST NOT read, as an input to any decision that affects the selection, the position of a candidate in the enumeration, an index assigned to a candidate by its position in the enumeration, the identity or address of the enumerator, a wall-clock time, a process-local random seed, or any other value outside C, w and R. In particular it MUST NOT iterate a hash-keyed collection of candidates, groups or candidate subsets in the collection's native iteration order, because that order is not a function of C alone (section 4.6).
• R3. The grouping of candidates (section 1) MUST itself be a pure function of C: two candidates are grouped together on the basis of their group keys and the group a candidate falls in MUST NOT depend on the enumeration.
• R4. The wallet secret w MUST key the pseudo-random source, MUST carry at least 256 bits of entropy, MUST be specific to coin selection and derived so that it is not equal to, and not efficiently related to, any key the wallet uses to sign, encrypt, or authenticate, and MUST be stable over the life of the wallet so that R1's "same selection" holds across time for one wallet. A chooser that leaves the source unkeyed makes the selection a public function of C, which an observer who learns the candidate set can both predict and, by varying which candidates it offers, steer (the Mathematical and cryptographic basis, Security Considerations); such a mode is a degraded mode that keeps order-independence but forfeits unpredictability, and a profile that permits it MUST say so.
• R12. A chooser MUST treat an enumeration that presents one outpoint more than once as malformed, and MUST reject it or reduce it to the set by a rule that reads only the members; it MUST NOT carry both copies, which would leave the canonical order of 4.1 undefined.
• R13. When a builder serialises the selected candidates into a transaction, it MUST order the inputs by a fixed function of the outpoints (the canonical order of 4.1 serves), so that the serialised input order does not re-admit the enumeration the selection removed.

R1 is the whole requirement. Sections 4.1 to 4.6 are one way to meet it; any construction that meets R1 to R13 conforms, whether or not it is the construction below. Determinism is required within one wallet (a fixed w); this BRC does not require two independent implementations to agree on the selection, only that each be a pure function of (C, w, R) and invariant under enumeration order.

4. A conforming construction

The construction has three ideas. First, derive from each outpoint a fixed byte string, so that outpoints have a canonical total order (4.1). Second, put the candidates and the groups in that order, and seed the pseudo-random source from the set in that order together with the wallet secret, so that both the search space and the random stream are functions of the set and not of the enumeration (4.2 to 4.4). Third, run the ordinary order-dependent search over this canonical arrangement, and iterate the resulting candidate subsets in a canonical order too, so that no step reads the enumeration (4.5, 4.6).

4.1 Canonical outpoint serialisation

The canonical serialisation of an outpoint is the 32-byte transaction id in internal byte order, the order in which the id is hashed and stored, followed by the output index as an unsigned 32-bit little-endian integer: 36 bytes in all. Write ser(o) for the serialisation of outpoint o. The display form of a transaction id, as written in BRC-36's "<txid>.<vout>", is the reverse of the internal byte order; an implementation that holds ids in display form MUST reverse them before serialising.

The canonical order of two outpoints is the ascending lexicographic order of ser(o) compared as unsigned bytes. Because outpoints are globally unique, this is a strict total order on any candidate set: no two distinct candidates compare equal. A chooser MUST use this order, or any other order that is a fixed function of the outpoints alone and is a strict total order on every candidate set, wherever a canonical order over candidates is called for below (R5).

4.2 Canonical group and candidate order

The chooser forms groups by group key (section 1, R3). Each group is given a group sort key equal to the least canonical serialisation among its members, min_{o in g} ser(o). The groups are placed in ascending order of their group sort keys. Because every outpoint is unique, no two groups share a group sort key, so this order is a strict total order and is a function of the candidate set alone (R6). The groups in this order are indexed 0, 1, ..., m-1; these indices are the only indices the search of 4.5 uses, and they are derived from the set, never from the enumeration.

Within a group, the members are placed in ascending canonical order of their outpoints. This matters only where a group is split for presentation or where equal-valued items are compared; the group is spent all or nothing regardless.

4.3 The pseudo-random source

The pseudo-random source is an HMAC-SHA256 keyed stream (RFC 2104, FIPS 180-4), keyed by the seed-derived key K of section 4.4. Using HMAC, rather than a bare hash chain, is what makes the stream a pseudo-random function of the wallet secret and so unpredictable to an observer who does not hold it (the Mathematical and cryptographic basis).

• Let block[i] = HMAC-SHA256(key = K, msg = DST_stream || LE64(i)) for i = 0, 1, 2, ..., where DST_stream is the ASCII bytes "bsv/coin-selection/v1/stream" and LE64(i) is i as an unsigned 64-bit little-endian integer. The stream is block[0] || block[1] || ..., consumed strictly forward: a request for n bytes returns the next n bytes of the stream and advances the position by n, and no byte is ever returned twice. Reads join seamlessly across block boundaries. An implementation MAY instead instantiate HMAC_DRBG (NIST SP 800-90A) from K with no additional input; the counter form here is the minimal pin.
• randint(a, b) returns an integer in the half-open interval from a to b. Let span = b - a. Let width be the least non-negative integer with 256^width >= span. Read width bytes from the stream, read them as a big-endian unsigned integer d, and return a + (d mod span). The number of bytes a draw consumes is fixed by span and not by the value drawn, so the stream position after a draw is a function of the draws requested, not of their results; this is what keeps every later draw reproducible. The modular reduction accepts a small bias deliberately, because a rejection loop would consume a variable number of bytes and change every later draw.
• shuffle(x) permutes a list x in place by the downward Fisher-Yates walk: for i from len(x)-1 down to 1, let j = randint(0, i+1) and exchange x[i] with x[j]. The walk direction and the draw order are part of the result and MUST be as stated, because they decide which permutation a given stream yields.

A conforming construction MUST consume the stream in a fixed sequence of draws that depends only on the canonical arrangement of 4.2 and on the group values, never on the enumeration (R7).

4.4 Seeding

Let B be the concatenation, in the canonical order of 4.2 taken over the candidates (equivalently, the ascending order of ser(o)), of the canonical serialisations of every candidate's outpoint. The seed-derived key is

K = HMAC-SHA256( key = w, msg = DST_seed || B ),     DST_seed = "bsv/coin-selection/v1/seed",

32 bytes, with the wallet secret w as the HMAC key and DST_seed || B as the message. B is a function of the candidate set alone, so K is a function of the set and the wallet secret alone (R8). Keying w with B as the message (rather than hashing w || B) removes any ambiguity about where w ends and B begins and admits no length extension on the concatenation. The pseudo-random source is seeded once, from K, before the search begins, and is not reseeded during a selection. Binding w through K makes the whole selection unpredictable to an observer who knows the candidate set but not w; a source left unkeyed (an empty w, or a seed that is a bare hash of the set) keeps order-independence but makes the selection a public, grindable function of the set (R4, Security Considerations).

4.5 The search over the canonical order

The objective that ranks sufficient subsets is out of scope (section 6); this subsection fixes only that the search reads the canonical arrangement and the seeded stream, and nothing else. A conforming search proceeds as follows, with m the number of groups.

1. For each group index i in 0 .. m-1, if the single group {i} is sufficient, record the subset {i}.
2. Let attempts = max(0, min(100, (m-1)*10 + 1)) (the max(0, ...) matters only at m = 0, the empty set, where no group exists, the selection is empty, and the chooser reports insufficient funds for any R > 0). Hold one list P = [0, 1, ..., m-1]. Repeat attempts times: shuffle(P) in place (4.3), carrying the same P forward from one attempt to the next so that each attempt's order depends on the last; then walk P from the front, accumulating groups, and at the first prefix that is sufficient record the subset equal to that prefix's group indices and go to the next attempt. If an attempt walks all of P without reaching sufficiency, the candidate set is insufficient and the chooser MUST report insufficient funds and select nothing.
3. For each recorded subset, reduce it by strip_unneeded: sort its groups in ascending order of value by a stable sort, then, scanning from the cheapest, drop a group whenever the groups after it are still sufficient, stopping at the first group that cannot be dropped; the kept groups are that group and all after it in the value order. This drops the cheapest redundant groups while keeping sufficiency, and the stable sort keeps the result a function of the canonical order where values tie.

The parameters 100 and (m-1)*10 + 1 are the construction's own and are not required by R1; a different attempt count still conforms as long as it is a function of m, not of the enumeration. What R1 requires is that steps 1 to 3 read only the canonical group order (4.2), the group values, and the seeded stream (4.3), which depend only on C, w and R.

4.6 Canonical candidate iteration and tie-break

Steps 1 to 3 produce a collection of candidate subsets, each a set of group indices. A chooser scores each with its objective (out of scope) and returns the best. Two parts of this MUST NOT leak the enumeration.

• R9. The chooser MUST iterate the candidate subsets in a canonical order that is a function of their contents, for example ascending lexicographic order of each subset's sorted tuple of group indices. It MUST NOT iterate them in the native order of a hash-keyed set or map, because that order is not a fixed function of C, and iterating it is a second enumeration-order channel equivalent to the one the rest of this construction closes.
• R10. Where two or more subsets tie for best under the objective, the chooser MUST break the tie with the seed key, not by a public order: serialise each tied subset canonically as the ascending concatenation of its groups' sort keys (the least outpoint serialisation of each group, section 4.2), compute HMAC-SHA256(key = K, msg = DST_tiebreak || serialisation) with DST_tiebreak = "bsv/coin-selection/v1/tiebreak", and return the subset whose HMAC value, read as an unsigned big-endian integer, is the smallest. The tie-break is therefore a function of C, w and R and not of the enumeration, and it is where the wallet secret enters the output: among two or more equally good selections, which one is published depends on the keyed K that an observer without w cannot compute, so it is unpredictable to that observer while a wallet holding w reproduces it. Where the objective determines a single best subset there is no tie, no HMAC is taken, and the selection is a public function of C and R. Breaking the tie by a public order of the subsets' contents would keep order-independence but make the choice public, so that an observer who knows the set could precompute it (the Mathematical and cryptographic basis).

The returned selection is the set of outpoints of the candidates in the winning subset's groups, which a builder serialises in the canonical input order of R13.

5. Conformance test

A verifier establishes R1 by exercising it, because a single run never reveals an order dependence. The test is:

1. Fix a candidate set C, a wallet secret w and a target amount R for which C is sufficient.
2. Compute choose(C, w, R) for the candidates in some order, and record the selection as a set of outpoints.
3. For a batch of distinct permutations of the candidate order, the more the stronger, compute choose again with the same w and R and the candidates in the permuted order, and record each selection as a set of outpoints.
4. The chooser conforms on this input only if every recorded selection is equal, as a set of outpoints, to the selection of step 2.

A verifier SHOULD include at least a candidate set with more than one group, at least one target that no single group satisfies (so the selection has more than one group), and at least one target that exactly one single group satisfies. A verifier MUST test more than one permutation; a test that re-runs a single order, as a naive determinism test does, cannot detect an order dependence and MUST NOT be relied on (R11). The Test Vectors below are such a test, carried out.

6. Out of scope

This BRC does not specify the objective function that ranks sufficient subsets (section 4.5 and 4.6 treat it as a given), the construction of change outputs (their number, their amounts, and any rounding meant to make change resemble a payment), the fee rate, the dust limit, how a wallet obtains and validates its candidate set, or how a caller names a specific output to spend (BRC-164). A chooser meets this BRC by meeting R1 to R11 whatever objective and change construction it uses. The objective and the change construction are nonetheless bound by R1 in one way: anything about the selection that they influence MUST also be a function of C, w and R alone, so a change amount or an objective score MUST NOT be computed from a candidate's enumeration position.

7. Summary of requirements

Test Vectors

The vectors fix a candidate set, a wallet secret, and five target amounts, and for each target give the selection the construction of section 4 returns and confirm that the selection is identical across a batch of input permutations. They were generated by a reference implementation of section 4 and checked for order-invariance by re-running each target over 200 distinct permutations of the candidate order; every run returned the selection listed. The objective used to rank subsets, which section 4.5 leaves open, is fixed here so the vectors are reproducible: a subset is scored by the pair (number of groups, total value), lower is better, and where two or more subsets tie the winner is the one with the least HMAC-SHA256(K, DST_tiebreak || serialisation) under the seed key (section 4.6, R10). The last target exercises that keyed tie-break, and a following subsection shows that a second wallet secret then selects the other tied subset.

Wallet secret and candidate set

The wallet secret is a test value and protects nothing: w = SHA-256("deterministic coin selection test vector: wallet secret"), which is

w = 85fc3115e1e2e44ad77e058bfa51cbe99560dcfd82fcd766369e1368399ff921

Each candidate's transaction id is the SHA-256 of a label, the UTF-8 string coin: followed by the candidate's name, taken as the internal byte order. The display outpoint is "<txid>.<vout>" with the id in display order (the reverse). ser is the 36-byte canonical serialisation of section 4.1. The group key names the key that controls the candidate; candidates with the same group key are spent all or nothing.

The total value of the set is 21200 satoshis.

Canonical order and seed

In ascending canonical order of ser the candidates are echo, bravo, foxtrot, charlie, delta, alpha. The seed input B is the concatenation of their serialisations in that order:

B = 020900971f1d8de12cc826be6cddbfc5daa49f5f9f4d7770608008a7b5c916b900000000
    0b4b17ad1c04a695a5fabca7cadf8e1b2d2b980ac7a17d93954f260b50c85ef401000000
    640597bc40cbca9b3014d9e1184070c73979cb50ed776da01a3f0ed12fd3d54c07000000
    8d0b322962f4674f6761faf9a0f7fabe8e76f55792fb0d1848128dd5da3b019400000000
    8f132df4ce3dc571bc228ce57a87bc02e16e0a59161ae18e1aceb6e0aa4ead3002000000
    c8e1f9e98f4b6bb5083422cea542ac3933ef308dbb0db0c5055ef46a87afc36000000000

(written on six lines for the page; B is their concatenation with no separators, 216 bytes). The seed-derived key is K = HMAC-SHA256(key = w, msg = DST_seed || B) with DST_seed = "bsv/coin-selection/v1/seed", and the first block of the pseudo-random stream is block[0] = HMAC-SHA256(key = K, msg = DST_stream || LE64(0)) with DST_stream = "bsv/coin-selection/v1/stream":

K        = 4a22662a1d001beffbe5a1c5912036401979242467c6d0bcc8a81d711c17bd20
block[0] = 492821268e4d64a8bbd5de58352c16d7c9cc7c4624bff598b804db3a6fadbcf4

The groups, in the canonical order of section 4.2, are:

Selections

For R = 6000 one group, K4, is sufficient on its own and is the fewest-input result. For R = 9000 no single group reaches the target, and the two cheapest groups whose combined value clears it, K1 and K3 at 4500 each, are spent whole, which shows the all-or-nothing grouping: both of K1's candidates and both of K3's appear, and the selection is exactly 9000. For R = 9700 two two-group sets tie for best, K2 with K3 and K1 with K2, each of two groups and each totalling 9700; the keyed tie-break of R10 picks the one with the least HMAC under the seed key, and with this wallet secret it is K2 with K3 (the next subsection shows a second secret picking the other). For R = 12000 the only sufficient two-group set is K4 with K2. For R = 20000 every group is required. In every row the selection was identical across all 200 permutations of the input order.

The keyed tie-break selects on the wallet secret

The R = 9700 target has two equally good selections, {K2, K3} and {K1, K2}, both of two groups and both totalling 9700. R10 picks the one with the least HMAC-SHA256(K, DST_tiebreak || serialisation) under the seed key K, so which equally good selection is published depends on the wallet secret. With a second test secret

w2 = SHA-256("deterministic coin selection test vector: second wallet secret")
   = 7ab8de6385196422...        (the key feeds HMAC as in section 4.4)

the construction returns the other tied subset, {K1, K2}, that is alpha, bravo, charlie, again totalling 9700, while the first secret returns {K2, K3}, that is charlie, echo, delta. The candidate set, the groups, and the two tied subsets are identical in both runs; only the secret differs, and the published selection differs with it. This is the unpredictability the keying buys: an observer who knows the candidate set but not the secret cannot tell which of the two equally good selections the wallet will publish. For the other four targets exactly one subset is best, so no tie-break is taken and the selection does not depend on the secret.

Insufficient funds

With the same set and R = 999999, which exceeds the total available value of 21200, the construction's search (section 4.5, step 2) walks a whole permutation without reaching sufficiency and the chooser reports insufficient funds, selecting nothing. This outcome is likewise a function of the set and R and does not depend on the enumeration.

Implementations

A reference implementation of section 4 exists in a privacy wallet, where the chooser groups a wallet's candidate outputs by the key that controls them, spends each group all or nothing, seeds the pseudo-random source from the wallet secret and the canonical serialisation of the candidate set, orders the groups by least outpoint, and scores sufficient subsets by an objective that penalises additional inputs and change that does not resemble the payment. An earlier form of the same chooser seeded its pseudo-random source from the candidates in sorted order but still walked the groups in the order its storage returned them, and a review found that the selection then depended on that order, so that the selection differed when the same candidate set was enumerated in different orders, and a source that returned the candidates in an order of its choosing could influence which keys were spent together. The fix was the canonical group order of section 4.2 and the canonical subset iteration of section 4.6, after which the selection became invariant across input permutations, as the Test Vectors show. The implementation's prior determinism test re-ran one order and so had not caught the dependence; it was changed to permute the input order, which is requirement R11.

Mathematical and cryptographic basis

This section has two halves. The mathematical half models the candidate set, its enumerations, and the selection as formal objects, states R1 as an invariance property, and proves that the construction of section 4 has it; order-independence is combinatorial and needs no cryptography. The cryptographic half states the second property a privacy chooser needs, that an observer who knows the candidate set cannot predict or steer which keys are spent together, shows it requires a keyed pseudo-random function, and pins one. It uses the names of section 3: C the candidate set, w the wallet secret, R the target; |X| is the size of a finite set, and byte strings compare unsigned, most-significant byte first.

Candidates, outpoints, and the set model

Let O be the set of all outpoints. An outpoint o = (txid, vout) pairs a 32-byte transaction id with a 32-bit index, and section 4.1's ser(o) writes it as the 32 id bytes in internal order followed by vout little-endian, 36 bytes. ser is injective: the layout splits back into its fields in one way, so distinct outpoints have distinct serialisations. A candidate c carries an outpoint o(c), a value v(c), and a group key g(c). The candidate set C is a finite set of candidates with distinct outpoints:

for c, c' in C,   c != c'  =>  o(c) != o(c').          (uniqueness)

This global uniqueness of outpoints is the one axiom the rest rests on. Write n = |C|. C is a set: it has no first member and no order. What an enumerator hands the chooser is a listing of C, and the listing has an order the set does not.

Enumerations and the symmetric group

An enumeration of C is a bijection e : {0, ..., n-1} -> C, a sequence in which each member appears once. Let Enum(C) be the set of enumerations; |Enum(C)| = n!. The symmetric group S_n acts on Enum(C) by permuting positions, (pi . e)(i) = e(pi^{-1}(i)). The action is free and transitive: for any two enumerations there is exactly one pi taking one to the other, so Enum(C) is a single orbit (a torsor under S_n) and the orbit space is one point,

Enum(C) / S_n  =  { C }.

Forgetting the order of an enumeration is exactly the quotient map, whose one value is the set C. Order-independent means constant on this orbit, that is, a function of the quotient.

The selection function and the invariance requirement

A chooser is handed an enumeration, so it is a map F : Enum(C) x W x N -> P(O), returning a set of outpoints. R1 says F is constant on each S_n orbit:

R1:   for all pi in S_n,   F(pi . e, w, R) = F(e, w, R).

Equivalently F factors through the quotient: there is a function f on sets with F(e, w, R) = f(set(e), w, R), so choose(C, w, R) := f(C, w, R) is well defined. R1 is the whole requirement; the construction's task is to exhibit an F that factors this way.

The canonical order and the canonical sequence

Order outpoints by their serialisations, o <= o' iff ser(o) <=_lex ser(o'). Because all serialisations are 36 bytes and ser is injective, this is a strict total order on any C, with no ties. So there is exactly one enumeration listing C in ascending order; call it kappa(C), the canonical sequence, and it depends only on the set:

kappa(set(e)) = kappa(set(pi . e))   for every e and pi.

kappa is a section of the quotient: out of the n! enumerations it names one, by a rule that reads only the members. This is the device that removes order dependence. Any order-sensitive procedure becomes order-independent the moment it runs on kappa(C) rather than on the enumeration supplied.

Grouping and the canonical order on groups

The group key partitions C into blocks by c ~ c' iff g(c) = g(c'); the partition is a function of C and g only, so a candidate's group does not depend on the enumeration (R3). The selection spends whole blocks, so the search ranges over subsets of blocks. Give each block Gr the sort key kg(Gr) = min over c in Gr of ser(o(c)). The minima of two distinct blocks are serialisations of two distinct outpoints, so by injectivity kg is injective: the blocks have a strict total order with no ties, yielding a unique canonical group sequence gamma(C), again a function of C. The indices of section 4.2 are the positions in gamma(C). A block's value is the sum of its candidates' values, and a set of blocks is sufficient iff its total value is at least R.

The seed as a set invariant

Section 4.4's seed input is the concatenation, in canonical order, of every candidate's 36-byte serialisation:

B(C) = ser(o(kappa(C)_0)) || ... || ser(o(kappa(C)_{n-1})).

B reads only the members and their canonical order, both functions of the set, so B(set(e)) = B(set(pi . e)): B is a set invariant, and the pseudo-random source, being a fixed function of w and B(C), is a function of (w, C) and of nothing else.

Permutation-invariance of the construction

Theorem. The chooser F of section 4 satisfies R1, so F(e, w, R) = choose(set(e), w, R) for a well-defined choose.

Proof. Let e and e' = pi . e enumerate one set C. Follow every value the construction reads. (1) The partition into blocks is a function of C, so the groups are the same. (2) gamma(C) is fixed by kg, a function of C, so each block's index is the same. (3) B(C) is a set invariant, so the seed and the whole byte stream are identical. (4) Each draw reads a number of stream bytes fixed by its bound, and the shuffle makes a sequence of draws fixed by the number of blocks, so the draws and their results are identical; a draw's byte count never depends on a value drawn, which keeps every later draw aligned. (5) The search reads only the group order of (2), the group values of (1), and the stream of (3), all equal, so the recorded subsets agree as sets of indices. (6) Scoring iterates the subsets in the canonical content order (R9) and, where subsets tie for best, breaks the tie by the least HMAC-SHA256(K, DST_tiebreak || serialisation) of each tied subset (R10); the iteration order is a function of the subsets' contents, and K is a function of (C, w), so the winner is a function of (C, w, R) and agrees for e and e'. (7) The output is the outpoints of the winner's blocks, which agree. Hence F(e, w, R) = F(e', w, R). QED.

The proof names the only three places the enumeration could enter: the group order (2), the seed (3), and the subset iteration (6). The construction sends each through a canonical order that is a function of C (requirements R6, R8, R9). Drop any one, index groups by their position in the enumeration, seed from the candidates in the order received, or iterate subsets in a hash set's native order, and that value stops being a function of C, F comes to depend on pi, and the channel of section 2 reopens.

No channel: zero bits of mutual information

Section 2 claims the enumerator's only influence is over which candidates exist, never over their order. Fix C, w, R, and a reference enumeration e0, and model the enumerator as a source emitting a permutation pi from any distribution it likes, possibly encoding a message. The output is Y = F(pi . e0, w, R). By the theorem Y = choose(C, w, R), a constant in pi, so

I( pi ; Y | C, w, R ) = 0.

The order carries zero bits to the output; no encoding of pi, and no repetition over many selections on the same set, moves one bit past the chooser. The only channel from the enumerator to Y is membership. R2's list of forbidden inputs (a position, an index, a clock, a process-local seed) is the complement: feed one in and Y becomes a non-constant function of something the environment varies, and the channel exists.

The keyed source: a deterministic pseudo-random function

Order-independence holds for any seed that is a function of the set. The second property, that an observer who knows C and R but not w cannot predict or steer which keys are spent together, needs cryptography, and it enters the output at one precise point: the tie-break among equally ranked subsets (R10). The source MUST be a keyed deterministic pseudo-random function (PRF) F_w, giving two properties at once: determinism, so a fixed w makes the same C and R yield the same selection (needed to re-broadcast, rebuild, or restore a payment, R1); and unpredictability of the tie-break, so that when the objective leaves two or more subsets equally good, which one is published is, to any party without w, computationally indistinguishable from a uniform choice among them. Be precise about the limit: where the objective determines a single best subset, that subset is a pure function of C and R, and no keying makes it unpredictable; an observer who can compute the objective's optimum learns it regardless of w. The secret buys unpredictability exactly over the degrees of freedom the objective leaves open, which is where a privacy chooser's discretion over which keys to link actually lives. The keyed stream additionally keeps the search's internal exploration opaque, so an observer cannot reproduce which sufficient subsets the chooser considered.

Why a bare hash of the set is not enough

An unkeyed source (an empty secret, or a bare hash of the set) makes the whole selection, including the tie-break, a public function of C and R, and opens two attacks on the chooser's discretion. Prediction: anyone who learns the holder's candidate set computes, for any R, exactly which keys the wallet will co-spend, the forced part and the tie-break part alike. Grinding: this BRC cannot stop an enumerator from adding or withholding candidates it controls, and with a fully public selection function an enumerator that varies which candidates it presents can evaluate that function itself and present the set whose selection co-spends, and so publicly links, the keys it wants linked. Keying the tie-break removes the enumerator's handle on the discretionary part: it cannot compute tie(sub) without w, so among equally good selections it cannot predict or steer the chooser's choice, and its residual lever over membership drives only the objective-forced part that is public to everyone in any case. An empty or absent w is therefore a degraded mode that keeps order-independence while forfeiting this unpredictability, and a profile that permits it MUST say so.

A construction to pin: HMAC-SHA256

The normative construction of the source is HMAC-SHA256 (RFC 2104, FIPS 180-4), a PRF under standard assumptions with a 256-bit key. It supersedes any prefix-keyed hash H(w || B), which over a Merkle-Damgard hash is not a general PRF and admits length extension, and any unkeyed chain block[i+1] = SHA-256(block[i]), whose every block past the first is a public function of the first. Fix version-pinned domain-separation tags, the ASCII labels DST_seed = "bsv/coin-selection/v1/seed", DST_stream = "bsv/coin-selection/v1/stream" and DST_tiebreak = "bsv/coin-selection/v1/tiebreak". These tags carry no BRC number, so the assigned number never enters the keyed inputs and the test vectors are stable across numbering. With B the canonical serialisation of section 4.4:

K        = HMAC-SHA256( key = w, msg = DST_seed || B )                 (32 bytes)
block[i] = HMAC-SHA256( key = K, msg = DST_stream || LE64(i) )         i = 0,1,2,...
stream   = block[0] || block[1] || block[2] || ...
tie(sub) = HMAC-SHA256( key = K, msg = DST_tiebreak || ser(sub) )      per tied subset

The stream is consumed strictly forward as section 4.3 specifies and drives the search's shuffles; the tie-break (R10) is a separate keyed hash, not a stream draw, so it needs no fixed stream position and the winner among equally ranked subsets is the one whose tie(sub) is least, where ser(sub) is the ascending concatenation of the subset's groups' sort keys. An implementation MAY instead use HMAC_DRBG (NIST SP 800-90A) instantiated from K for the stream; the counter form above is the minimal pin. If HMAC-SHA256 is a PRF, K is indistinguishable from a random key to an adversary without w, both the stream and each tie(sub) are indistinguishable from random to that adversary, and so the choice the tie-break makes among equally ranked subsets is unpredictable to it; where the objective leaves a single best subset the selection is instead a public function of (C, R) that no keying hides.

The wallet secret

The secret w is the whole basis of unpredictability. It MUST carry at least 256 bits of entropy and SHOULD be one HMAC-SHA256 key width (32 bytes); a low-entropy w is grindable offline against a known C. It MUST be specific to this use and derived so that it is not equal to, and not efficiently related to, any key the wallet uses to sign, encrypt, or authenticate, for example w = HKDF-SHA256(ikm = master_secret, info = "bsv/coin-selection/v1/wallet-secret"). It MUST NOT be a signing key, nor derived such that learning w endangers one, since reuse would couple two independent failure domains and expose signing material to a chain-published selection oracle. It MUST be stable for the wallet's life, so reproducibility holds across time; rotating w silently re-randomises future selections, which is safe but loses reproducibility against any pre-rotation attempt.

Failure modes and modular bias

An empty or unkeyed seed makes the selection a public function of C (prediction and grinding above). A prefix-keyed H(w || B) is not a proven PRF and admits length extension. An unkeyed stream makes every block past the first public. A w that is a signing key or a reused secret couples failure domains. A low-entropy w is offline-grindable although the construction looks keyed. The entropy floor, domain separation, and HMAC pin above address these. On modular bias: randint returns a + (d mod span) from ceil(log_256(span)) stream bytes, accepting a bias of at most span / 256^width (below 1/256 of a draw's range, usually far smaller) rather than rejection-sampling, so the byte count per draw is fixed and later draws stay reproducible. Because the pre-reduction bytes are PRF output, this bias is a tiny, w-independent skew in an already-unpredictable stream, not a channel; the trade of determinism over a vanishing bias is deliberate.

Edge cases

Duplicate or colliding outpoints would make ser non-injective on C, leave the canonical order undefined, and break every argument above, so a chooser MUST treat an enumeration that presents one outpoint more than once as malformed: reject it, or reduce it to the set by a rule that reads only the members, and MUST NOT carry both copies. The empty set gives one (empty) enumeration, no block, and an empty selection reported as insufficient funds for any R > 0; invariance holds vacuously. The one hazard there is arithmetic: the inner formula (m-1)*10 + 1 is negative at m = 0, which is why section 4.5 writes attempts = max(0, min(100, (m-1)*10 + 1)), so the empty set runs zero search attempts and reports insufficient funds for any positive target. Every order used for canonicalisation is strict and descends from ser, so two blocks of equal value keep the definite order their least outpoints give, and where value does sort (the trimming step of section 4.5) a stable sort preserves the canonical order among equal values. The final choice among subsets that tie for best under the objective is settled by the keyed HMAC-SHA256 of each tied subset (R10), whose 32-byte values collide only with negligible probability, so choose returns exactly one selection, a single value rather than a set of candidates, which is what R1 presupposes.

Security Considerations

What order-independence secures. A conforming chooser denies an enumerator any influence over the selection beyond the membership of the candidate set (section 2). The chooser still depends on which candidates exist, which the enumerator can affect by withholding or adding candidates it is able to; this BRC does not and cannot prevent that, and a wallet that validates its candidates (out of scope here) limits it. What the BRC removes is the subtler and otherwise invisible channel of ordering, which affects the selection without changing the set and so leaves no trace in the candidate set a later audit would see.

The failure is quiet, so the test is normative. An order dependence produces correct-looking output in any single run and in a determinism test that re-runs one order. It shows only when the order changes, which in deployment is a hostile source or a resync, not a test. For that reason R11 makes a multi-permutation test the way conformance is established, and the Test Vectors are that test performed on the reference construction.

Both halves are required. Seeding the pseudo-random source from an order-independent function of the candidates (section 4.4) is necessary and is not sufficient (Motivation). A chooser that fixes its random stream but still indexes groups or candidates by enumeration position, or iterates a hash-keyed collection of subsets in native order (R9), still leaks the order. A conforming chooser canonicalises the seed, the group order, and the subset iteration; R8, R6 and R9 each state one of these, and dropping any one reopens the channel.

The secret, predictability, and grinding. An unkeyed source (an empty secret, or a seed that is a bare hash of the set) makes the selection a public function of the candidate set: anyone who learns the set computes which coins the wallet will spend together for a given target, and an enumerator that can add or withhold candidates it controls can grind over the memberships it is able to offer and present the one whose public selection links the keys it wants linked. Keying the tie-break with a stable, high-entropy wallet secret (R4) makes the chooser's choice among equally good selections unpredictable to an observer who does not hold the secret, so the enumerator cannot evaluate that choice and its residual control over membership drives only the objective-forced part of the selection, which is public to everyone in any case, while the whole selection stays reproducible for the wallet that holds the secret. The secret keys an HMAC pseudo-random function (section 4.4); it is not revealed by the published selection, and it MUST NOT be a signing key or a secret efficiently related to one, so that this chain-published selection oracle lives in its own key space (R4).

Scope of the guarantee. Order-independence is a property of the input choice alone. It does not make the inputs unlinkable to each other or to the holder, does not constrain the change (out of scope), and does not address timing, amounts, or network-level correlation. It removes one specific channel, the enumerator's hand in the input choice, and the other surfaces are the subject of the objective function, of change construction, and of standards such as BRC-228.

Privacy Considerations

A privacy chooser's purpose is to control what a spend discloses about its holder, chiefly which of the holder's keys are linked by appearing as inputs of one transaction. An order-dependent chooser hands part of that control to whoever orders its candidates, which for most wallets is an external source that may be hostile or stale (section 2). A conforming chooser keeps the whole of that control: the keys it links are a function of the candidate set, the wallet secret, and the amount, and of nothing an outside party can vary without also changing the set. The reproducibility a conforming chooser gains, one candidate set funding one payment with one input set, is itself a privacy property, because it means a resync, a retried broadcast, or a rebuilt transaction does not spend a second, overlapping input set that an observer can correlate with the first, and does not expose a change key committed to an earlier attempt.

The construction also bears on what an observer who watches the candidate set can predict. An unkeyed source would make the whole selection public given the set; keying the tie-break with the wallet secret (R4, and the Security Considerations) makes the chooser's choice among equally good selections unpredictable to anyone who does not hold the secret, so an observer who can see the holder's candidate outputs cannot compute in advance which equally good selection the wallet will publish, though a selection the objective determines uniquely stays computable from the set. None of this makes the inputs of a spend unlinkable once the spend is on the chain; the links a conforming chooser does create are permanent and public, and which links to create is the objective function's concern, left open here. This BRC ensures only that the enumerator is not among the parties that decide them.

References

• [BRC-1] Transaction Creation. wallet/0001.md
• [BRC-36] Format for Bitcoin Outpoints. outpoints/0036.md
• [BRC-45] Definition of UTXOs as Bitcoin Tokens. tokens/0045.md
• [BRC-46] Wallet Transaction Output Tracking (Output Baskets). wallet/0046.md
• [BRC-100] Unified, Vendor-Neutral, Unchanging, and Open BSV Blockchain Standard Wallet-to-Application Interface. wallet/0100.md
• [BRC-164] Output Identity Tags for BRC-100 Wallets. wallet/0164.md
• [BRC-177] Wallet-Enforced Expiry for noSend Actions. wallet/0177.md
• [BRC-192] Application Output Knowledge and Source Adapters. apps/0192.md
• [BRC-228] Unlinkable Payments under the Identity Paradigm. payments/0228.md
• [RFC2119] S. Bradner, Key words for use in RFCs to Indicate Requirement Levels. https://www.rfc-editor.org/rfc/rfc2119
• [RFC8174] B. Leiba, Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words. https://www.rfc-editor.org/rfc/rfc8174
• [FIPS180-4] NIST, Secure Hash Standard (SHS), FIPS PUB 180-4 (SHA-256). https://doi.org/10.6028/NIST.FIPS.180-4
• [RFC2104] H. Krawczyk, M. Bellare, R. Canetti, HMAC: Keyed-Hashing for Message Authentication. https://www.rfc-editor.org/rfc/rfc2104
• [RFC5869] H. Krawczyk, P. Eronen, HMAC-based Extract-and-Expand Key Derivation Function (HKDF). https://www.rfc-editor.org/rfc/rfc5869
• [SP800-90A] NIST, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, SP 800-90A Rev. 1 (HMAC_DRBG). https://doi.org/10.6028/NIST.SP.800-90Ar1