BIP93: Fix checksum selection bounds and restrict `ms` sizes #2258

Motivation

BIP93 currently admits expanded codewords beyond the checksum’s stated period, so its detection guarantee no longer applies to the complete codeword. This is a problem for a generic codex32_decode function in later PRs. Both regular and long checksums permitted codewords in excess of their period.

Meanwhile, fixing the above will invalidate very uncommon ms strings or leave an ugly disjoint checksum selection rule for len(hrp) == 2. A better solution is immediately follow up with by restricting master seeds to the most commonly used seed and entropy sizes. This reduces target length ambiguity for optional insert/delete correcting wallets and my benchmarks show improvements in both false-correction risk and performance at the same indel search depths.

Changes

• ms32_verify_checksum and ms32_create_checksum now include the expanded "ms" HRP length when selecting regular vs. long checksums.
• ms32_create_checksum uses if 5 + len(data) > 80: as the switch to ms32_create_long_checksum.
• added ms32_create_regular_checksum and ms32_verify_regular_checksum.
• The Python reference code, specification, rationale, and vectors are updated.
• ms32_decode enforces the new ms string lengths.
• Obsolete tests/vectors from the seed size restrictions are removed.

codex32 lengths:

• Regular codewords will now be <= 93 expanded values
• Long codewords will now be >= 96 and <= 1023 expanded values

invalid codex32 lengths:

• Expanded values 94, 95 and > 1023.

codex32-encoded master seed sizes:

• 16-, 20-, 24-, 28-, 32- and 64-bytes

unsupported ms sizes:

• All from 16- to 64-bytes besides the six above.

Compatibility

This is a breaking change for old strings encoding deprecated byte-length seeds. However the authors do not see this is a problem due to the exceedingly rare possibility these have ever been created and used.

Testing

Thoroughly reviewed the complete diff. Checked the new vectors. Checked that expanded length 1023 verifies and 1024 fails. Checked that the legacy short-checksum vectors should fail. Checked that ms32_decode rejects newly invalid lengths, even when they have valid header, incomplete group and checksum.

Discussion

Proposal: #2040 (comment) cACK #2040 (comment) Reference impl issue: https://github.com/BlockstreamResearch/codex32/issues/75 rust-codex32 PR: https://github.com/BlockstreamResearch/codex32/pull/76 Restrict ms sizes suggestion: #2258 (comment)

LGTM!

— specification-consistent correction of the boundary issue discussed in "PR #2040" (https://github.com/bitcoin/bips/pull/2040).

Checksum selection must use the expanded codeword length, including the fixed "ms" HRP’s five-value expansion.

· Regular: ≤93 · Invalid: 94–95 · Long: 96–1023

This matches the 43-byte regular / 44–46-byte long boundary.

Intentional consequence: legacy regular-checksum encodings of 44–46-byte seeds become invalid and must use the long checksum.

Remaining gate: reproducible boundary vectors.

cc: @roconnor-blockstream, @apoelstra

Remaining gate: reproducible boundary vectors.

I added "reproducible boundary vectors."

Edit: Unsure if I should have done this to satisfy a review comment that was later marked "low quality".

For vectors, we need at minimum:

• add regular checksum 44-, 45-, and 46-byte seeds to These examples use the wrong checksum for their given data sizes
• add Expanded values 94, 95 and > 1023 to These examples have improper lengths
• remove any vectors that are now accepted

Willing to revert the "reproducible" vectors added in a9d8246244c06b4143b280844e7b8cf7215fe8f9 if reviews also find it overkill or open to another suggestion.

What I would keep: Separated checksum verification into regular/long primitives that check expanded length is within the checksum period and residue is valid. While ms32_verify_checksum owns the switch to long primitive at 96 expanded symbol codewords and calls the above.

Similarly ms32_create_regular_checksum creates the short checksum for data, while ms32_create_checksum selects the required checksum by expanded codewode length and creates it.

It should be easier to generate test vectors and test them now, as well as to reuse our checksums for non-codex32 data.

Based on my comment at #2040 (comment) which received some thumbs up by all parties here, I wonder if it everyone would find it preferable to simply restrict BIP-93 to seed lengths 128, 160, 192, 224, 256 and 512. I think I slightly prefer that, and if we are going to make such a change it would be better to do it from the get go.

cACK

simply restrict BIP-93 to seed lengths 128, 160, 192, 224, 256 and 512. I think I slightly prefer that, and if we are going to make such a change it would be better to do it from the get go.

To prepare to generalize BIP-93 we still must also correct the checksum-period coverage or it leaves the unsafe checksum-selection question for every later application:

For an ms application to restrict to these lengths, codex32_decode must verify the separator, header and checksum, then return HRP and u5 data. If expanded codewords may exceed the checksum period, detection guarantees won't apply, risking undetected cross-application/profile confusion.

Since restricting ms seed lengths can simplify the test vectors, rationale and compatibility sections I will add it here as a separate commit rather than revive #2077.

• Checksum verification primitives enforce their maximum 93/1023 periods.
• Checksum verification selects Long from 96 expanded length.
• Checksum creation selects Long above 80 expanded hrp plus data length.
• Master seed format rules will update and state its valid lengths.
• “Long codex32 only for 512 bits” is an ms-profile rule, not a general rule.
• Compatibility mentions the removed previously valid non-multiple of 4-byte and 33-63-byte sizes and their previous checksum selections.
• SLIP-0039 permits additional lengths, compatibility needs "interconvertible with SLIP-0039 master seeds of supported lengths".
• 43–47-byte master-seed vectors will be removed.
• Checksum-layer assertions for 93/94/95/96/1023/1024 will be added while ms tests will enforce the six seed lengths.

c2015366046de35785f5b69e56d6b3227bb34232 is ready for review. I drafted the next commit "BIP93: Restrict ms seed lengths", working on the vectors.

Each commit is stand alone complete.

ACK 5117f5831bcbf0485949e5951d2954b792eded28

This looks good to me! Lol I think my hideous BIP39->codex32 conversion scheme is now permissible under "application-specific rules".

This looks good to me! Lol I think my hideous BIP39->codex32 conversion scheme is now permissible under "application-specific rules".

It indeed is! I used your bip39_12w profile's non-byte aligned payload as a major consideration here and in my rewrite of #1958. (payload length parameter, not a byte length) And for bip39_24w our regular checksum fully covers the codewords.

I had thought that SLIP-0039 supported just 128 and 256, but now I see that it supports lengths [128,144,160,176,192,208,224,240,256].

This PR for BIP-93 supports [128, 160, 192, 224, 256] (and 512).

I think we should at give some consideration in our discussion here in supporting all SLIP-39 lengths. It would cause no problems for us regarding long and short codex32 checksums. It would make insertion and deletion recovery somewhat more difficult.

With the full SLIP-93 lengths [128,144,160,176,192,208,224,240,256] we would have codex32 encodings of lengths [48,51,54,58,61,64,67,70,74] with gaps of 3 or 4 characters between valid lengths.

Thinking out loud, if you take a 160 bit, 54 length ms codex32 string and delete 3 random characters, can you actually able to recover that by trial and error inserting 3 characters? There are 54 choose 3 positions to try inserting, and 32^3 combinations to try in each position which is a total of 812 777 472 possible combinations to try. That does seem to be a feasible number to try, especially since you are looking for one with a valid checksum.

So we are considering a trade off here of enhanced SLIP-39 compatibility for secret lengths that probably no one ever uses versus allowing recovering an from up to 3 characters being omitted from a codex32 string, which feels like also an unlikely number of characters to forget to jot down.

I'm genuinely torn here. What are the thoughts of other folks here?

Maybe another angle to consider is, would users want to try 144 bit secrets with codex32? The argument is that Bitcoin has 128-bit security so you really want to debias your dice / entropy source when making a 128 bit secret. An alternative would be to make a longer secret and avoid debiasing your entropy with the idea that your longer secret would still contain 128-bits of entropy. This was my main motivation for considering 160 bit secrets (which was the next step up in BIP-39 secret sizes). But shorter is better because it is less work to create checksums and fewer characters means fewer errors to correct.

The question is can users use regular biased dice to get 128 bits of entropy in 144 bits?

The AI machine suggests an air bubble trapped in a cheap opaque die could bias one face up to 25% of the time. If the distribution were [25%, 16.75%, 16.75%, 16.75%, 16.75%, 8%], that would reduce the entropy of the dice from 2.58 bits per roll to 2.518 bits per roll. If the distribution were even more unreasonable at [33%, 16.66%, 16.66%, 16.66%, 16.66%, 0%] (this is also a fair die with one number repeated on a face). We'd have 2.25 bits per roll. Treating that die as fair would leave you with only than 125 bits of entropy in a 144 bit secret, but would give you 138 bits for a 160 bit secret.

So I don't know. Maybe 144 bits is still to small to eliminate debiasing?

As a point of information, as a child I had a PC game of monopoly where the RNG had an off by 1 error and 6s were never rolled. This gives a "five" sided dice with entropy of 2.32 per roll, which gives just over 128 bits of entropy for a 144 bit secret. We did eventually notice the missing 6, but it took quite a surprising amount of time to realize.

I think I'd argue that 144 bit is inadequate for generating 128 bits of entropy using dice without debiasing.

As counter argument for why 144 bits could be adequate, if you are building a 2 out of n secret share, you are xoring 2 biases secrets together which, generally speaking, reduces the bias of the resulting master secret.

That is to say that while generating a 144 bit master secret form a plausibly biased die seems too close to borderline unsafe, generating a 144-bit master secret from 2 randomly generated shares feels a lot safer.

(As a counter-counter argument, leaking k-1 shares reduces the security back down to a single share, though that involves the attacker both loading the dice and accessing k-1 shares).

We could consider a compromise where ms secrets are limited to between 128 and 256 bits (i.e. 16-32 bytes) (plus the 512 bit long format), but generating bit sizes outside [128, 160, 192, 224, 256] is discouraged? I don't know if that is sensible.

We could consider a compromise where ms secrets are limited to between 128 and 256 bits (i.e. 16-32 bytes) (plus the 512 bit long format), but generating bit sizes outside [128, 160, 192, 224, 256] is discouraged? I don't know if that is sensible.

Adding 160, 192 and 224 already required my single threaded python indel correction to search 160, 192 and 224 one indel less deeply to stay under 10 seconds on my laptop.

It can fill 4 omissions in 44 character observed in about 5 seconds. Since omissions are marked as erasures and algebraically solved, its only 149k combinations of 4 in 45 since deletions are marked as erasures and algebraically solved. 250k for 4 in 51 and 1.1 million for 4 in 71. (128, 160 and 256-bit respectively)

The limit for filling omissions is false-correction. Intuitively it feels wrong to correct more deletions than substitutions so I prefer the symmetric "up to 4 extra or omitted characters, and mixtures" I.e. I+O <= 4.

Removing inserted characters is faster and CPU limited rather than accuracy limited.

I will simulate how much adding the 4 extra lengths increases ambiguity assuming non 128 and 256 remain searched to 3 indels.

Lastly we say "we do not recommend interconversion and suggest users generate a fresh master seed" so this potentially harms an optional feature to better support a not recommended feature.

We said wallets may assume the true length is 48 or 74. But if weird lengths get corrected to 48 or 74 they're not well supported so they need to be checked at some depth before "assuming 48 or 74".

For avoiding transcription errors and having fast corrections of them, the best recommendation is avoid generating sizes besides 128-bit, the 4-indel correction is necessarily slower on 256-bit and they've more chances to make mistakes, we already say " shorter strings are better."

However if not generating 128-bit, 256-bit is the next best size to reduce search ambiguity.

SLIP 39 requires 128 and 256 and requires 16-bit multiples so if the argument is slip39 compatibility, its either 128 and 256 alone or every even byte size 16-64, not just those 16-32.

I had thought that SLIP-0039 supported just 128 and 256, but now I see that it supports lengths [128,144,160,176,192,208,224,240,256].

It supports all even byte lengths 16-64 inclusive.

It would cause no problems for us regarding long and short codex32 checksums. It would make insertion and deletion recovery somewhat more difficult.

One of these lengths switched checksums in my first commit here.

I will test indel recovery, if it's not meaningfully worse than the 6 lengths in my 2nd commit, I have no objection.

gaps of 3 or 4 characters between valid lengths.

Thinking out loud, if you take a 160 bit, 54 length ms codex32 string and delete 3 random characters, can you actually able to recover that by trial and error inserting 3 characters? There are 54 choose 3 positions to try inserting, and 32^3 combinations to try in each position which is a total of 812 777 472 possible combinations to try.

Only the positions need search, the characters are marked erasures and filled without brute force.

3 is very fast, 4 omitted is seconds on a laptop.

So we are considering a trade off here of secret lengths that probably no one ever uses versus allowing recovering an from up to 3 characters being omitted from a codex32 string, which feels like also an unlikely number of characters to forget to jot down.

Its possible to recover from 5 omitted characters too if 0.1% chance of false corrections is acceptable. Limiting to 4 is safer.

We dont recommend interconversion, indel recovery is optional.

We could use a new profile SLIP39_EMS and let that one support every even byte length and also the passphrase feature from SLIP39, while using our SSS and checksums.

I also don't oppose every even byte length if indel recovery is unharmed.

Maybe another angle to consider is, would users want to try 144 bit secrets with codex32?

I dont think a lower bound can be assumed on biased entropy. If the goal is less work, more efficient entropy extractors and 128-bit secrets are better.

But shorter is better because it is less work to create checksums and fewer characters means fewer errors to correct.

Fewer lengths means fewer length errors to correct, fewer worksheets to print.

The question is can users use regular biased dice to get 128 bits of entropy in 144 bits?

This would require modifying the "uniform random" part of share generation.

So I don't know. Maybe 144 bits is still to small to eliminate debiasing?

Biased shares means we can't say nothing is learned about the secret at K-1, if smallest strings are better, so is debasing.

Debiasing doesn't take too long. I can generate 128-bits with a quarter in 1/2 hour. But I would not trust 160 or even 256 flips to be 128-bit entropy.

xoring 2 biases secrets together which, generally speaking, reduces the bias of the resulting master secret.

My thought experiment was if my dice only give 1s and 2s treating that like log2(6) bits and xoring with another share produced with only 1s and 2s is not going to improve much. they're biased in the same way so entropy does not increase.

I had thought that SLIP-0039 supported just 128 and 256, but now I see that it supports lengths [128,144,160,176,192,208,224,240,256].

It supports all even byte lengths 16-64 inclusive.

Ah, my whole premise was mistaken then. Okay, I'm less inclined to support the full range of SLIP-39 seeds. The most common sizes of 128-bit and 256-bit seeds will still be interconvertable. And, as noted in this PR, all of the seed sizes supported by this amendment, are also interconvertable.

Now I'm inclined to keep this aspect of the PR as is.

I got a bunch of emails from @BenWestgate last Wednesday on this PR but that do not appear here. I'm very confused.

@roconnor Sorry for the confusion. I clicked something in GitHub Copilot thinking it would offer a second opinion on your review, but instead it posted several You're Absolutely Right™ AI-slop replies. I deleted them; they were prohibited by Bitcoin Core's AI policy. That's why they appeared in email notifications but no longer appear here.

For the remaining review comments, I plan to open a cleanup PR based on https://github.com/bitcoin/bips/commit/5117f5831bcbf0485949e5951d2954b792eded28 containing the refactor, typo fixes, and your bits-vs-bytes consistency improvements.

#2258 (review) is already covered by #2040, so I can rebase #2040 onto that cleanup and reopen it afterward.

That leaves ms32_encode as the only unresolved review: #2258 (review)

You suggested returning None when the constructed string has an invalid length. I think the low-level encoder should remain permissive, like bech32_encode, with application-specific validity enforced by the decoder or a higher-level encoder. Keeping the low-level encoder permissive is also useful for generating invalid test vectors.

The Bech32 reference implementation follows this pattern: bech32_encode simply constructs the checksummed string, while the higher-level Segwit encode function validates its result by decoding it.

We could similarly add a higher-level master-seed encoder in the Master seed section:

def encode(threshold, identifier, seed):
    """Encode a master seed in codex32."""
    header = threshold + identifier + "s"
    data = [CHARSET.find(x) for x in header.lower()]
    ret = ms32_encode(data + convertbits(seed, 8, 5))
    return ret if ms32_decode(ret) is not None else None

That function would be more useful alongside #2040, where a generalized low-level codex32_decode(codex) can no longer enforce application-specific ms length rules. Shares need a different encoder, though, so I'd rather include both or omit both encoders from the BIP text.

BIP173 takes the latter approach: its text specifies the checksum primitives but leaves bech32_encode and bech32_decode to the reference implementations. Perhaps BIP93 should do the same.

Shares need a different encoder, though

This is a subtle property @apoelstra and I missed in our first implementations, if API users have a way to construct shares from bytes, or decode bytes from shares, they abuse it.

If shares are constructed from bytes with deterministic or otherwise non-random padding, the final u5 value is not uniformly random. This can leak information about the secret given k - 1 shares.

There need not really be a share_encode function. A create_share or generate_share function would be safer:

import secrets


def create_share(threshold, identifier, share_idx, payload_len):
    """Generate a codex32 share with a uniformly random payload."""
    header = threshold + identifier + share_idx
    payload = [secrets.randbelow(32) for _ in range(payload_len)]
    data = [CHARSET.find(x) for x in header.lower()] + payload
    ret = ms32_encode(data)
    return ret if ms32_decode(ret) is not None else None

Thanks. I have no further comments.

This is a subtle property @apoelstra and I missed in our first implementations, if API users have a way to construct shares from bytes, or decode bytes from shares, they abuse it.

Yeah, we probably want to update the BIP with some cautionary text about this. But the existing BIP has no mention of converting bytes to shares (or to seeds for that matter), only of converting seeds to bytes. So I think we can defer this to a later PR.

I'd really like to get this one in. It's small and targeted and I'd like not to have another multi-month conversation with 1000s of words of tricky/subtle analysis that aren't even directly related to the issue at hand. (And I'm sure our BIP maintainers agree.)

Oh, I see, the existing text does say "Set the payload to a bech32 encoding of the secret data, padded with arbitrary bits" for "converting from an existing share".

We should maybe update this to say "pad uniformly", which will be safe if users blindly reuse this logic to convert bytes to shares, and we should also add some cautionary text saying not to convert bytes to shares and not to provide APIs to do this.

But different PR please.

LGTM

FYI my ACK above applies to the latest commit. I think we are good to merge.

Great! Thanks @BenWestgate for your persistence as well as for the review @roconnor and @apoelstra.

@roconnor Sorry for the confusion. I clicked something in GitHub Copilot thinking it would offer a second opinion on your review, but instead it posted several You're Absolutely Right™ AI-slop replies. I deleted them; they were prohibited by Bitcoin Core's AI policy. That's why they appeared in email notifications but no longer appear here.

Thanks for removing the slop comments. I figured that I should point out that while for historical reasons the BIPs repository is part of the Bitcoin Core organization, BIPs are not considered part of Bitcoin Core and its policy does not apply here.

Also, while this proposal is currently published in Draft status and therefore doesn’t yet require a Changelog, you could consider adding one to mention these recent changes, if you feel that this was significant enough to record.