Source code for error correction?

[BenWestgate]

Has a reference implementation for erasure correction or error correction in codex32 strings been written?

[apoelstra]

Afraid not. Though if you want to correct 1 or 2 errors a simple way to approach it would be to just generate residues for every possible error pattern and then do a lookup table based on that.

My plan for this is to continue an ongoing project to rewrite rust-bech32 so that it will work with arbitrary BCH codes; then this library will depend on that for all the coding theory stuff, and only implement the Lagrange polynomial stuff. And we can implement error correction there, so we'll get it simultaneously for codex32, bech32, the descriptor checksum, the checksum used by Liquid/Elements addresses, etc.

[BenWestgate]

The specs guarantee correction of up to 4 substitution errors. Is there any relationship to how many insertion or deletion errors can be safely corrected?

I'm thinking there are no guarantees at all because Bech32 had a weakness to insertion/deletion errors.

Bech32 has an unexpected sipa/bech32#51: whenever the final character is a 'p', inserting or deleting any number of 'q' characters immediately preceding it does not invalidate the checksum.

Does that mean error correction implementations:

• SHOULD NOT attempt to correct any random insertions and deletions
• SHOULD attempt to correct them but fewer, say 2 instead of 4
• MAY attempt to correct 4 random subsitutions, insertions or deletions and rely on the user's confirmation of the corrected string to protect against accepting a wrong but valid codex32 string?

[apoelstra]

I'm thinking there are no guarantees at all because Bech32 had a weakness to insertion/deletion errors.

Yeah, that's the right intuition. There are no mathematically guaranteed-detectable errors. But in practice for I'd expect that you usually could, and for one or two it'd be fairly cheap to try. The reason is that you know the expected length of your string (in the common case that you are using 128/256/512-bit seeds and not something in between, which I think we technically support but nobody would ever do), so you know how many insertions/deletions have happened, on net.

If you have a 47-character string but were expecting a 48 character string, you can just try inserting a blank in every possible position, running error correction (a variant where you can specify known error locations, which makes it able to succeed with up to 8 missing tiles rather than just 4), and seeing if it succeeds. With overwhelming probability, but not a guarantee, if you actually have a small random set of errors that include insertions/deletions, you'll find the corrected string, and only the corrected string.

Like with bech32, there are non-random "structured" errors that will cause error correction to yield a bad result. But like bech32m, and unlike bech32, these "structured" errors cannot be found by a single fat-finger.

Adding to this the rules for seeds and the rules for addresses are a bit different. With addresses if you are unsure at all, you should throw the address away and re-request it, because there is no harm in throwing it away and catastrophic harm (burned coins) if you send coins to a bad address. With seeds, during generation, the same story applies. But during recovery it's kinda the opposite...if you are uncertain, it's easy to check (just try to derive a known address that you received coins at before, or any address with a balance, you won't find one that's not yours), and if you throw your result away there may be nobody to "re-request it" from.

So in summary, error correction implementations:

• During initial wallet setup, behave like bech32: you can highlight substitution errors, but don't correct anything.
• During recovery, then do whatever you can, including grinding for insertions/deletions, to find the seed. Then show the user the set of corrections and make them re-enter the corrected string (in the hope that they'll make a new corrected backup) before using it.

Let me bug some people on IRC before making RFC-style SHOULD NOT/SHOULD/MUST/MUST NOT/MAY proclamations. We may want to update the BIP with this sort of text.

[roconnor-blockstream]

Some further comments I have: BIP-32 defines a seed as a "byte sequence S of a chosen length (between 128 and 512 bits; 256 bits is advised) from a (P)RNG.", that is a number of bytes between 16 and 64. Because of this, I wanted our standard to be able to support everything that BIP-32 supports. That said, (and maybe we should make this clear in our spec) I strongly advise only using 16, 32, and 64 byte secrets (and between those choices strongly preferring 8 with a robust source of entropy when doing any hand computations). To the point of perhaps suggesting that BIP-32 be amended to require using only 16, 32, or 64 byte secrets. I'm not aware of any system doing otherwise anyways.

This way, inserting and removing just a few characters is detectable. That said, the error correction procedure is only designed to explicitly correct substitution errors.

(Ninja edited)

[BenWestgate]

With my naive implementation, I could only correct a single edit in real-time. 2 edits takes a few seconds to check every possible error pattern.

As it is common for my testers to make more than a single error during recovery, I wanted to try to modity this bech32_ecc.js because I remember it was much faster to find 2 error locations:
https://github.com/sipa/bech32/blob/master/ecc/javascript/bech32_ecc.js

But I don't know how to set some of the constants to be codex32 appropriate like:

var GF1024_EXP
var GF1024_LOG

and possibly some in
function syndrome (residue)
function locate_errors (residue, length)

Is this something that is too difficult for me to do in a day without advanced mathematical knowledge even if I know the codex32 GENERATOR and MS32_CONST?

[BenWestgate]

But during recovery it's kinda the opposite...if you are uncertain, it's easy to check (just try to derive a known address that you received coins at before, or any address with a balance, you won't find one that's not yours), and if you throw your result away there may be nobody to "re-request it" from.

Related to this, I set the identifier characters to hash160(seed)[:4] and the payload padding bits of the codex32 secret to double_sha256(seed)[0] (like truncating the WIF serialization) so have an additional 22/24-bits of error detection for 128/256-bit seeds.

This can't be hand calculated and breaks plausible deniability of a "decoy" share but improves the chances of detecting errors from wrong but valid strings, even without a known address.

Is this a good idea for electronic implementations of codex32 backup generators?

Asking the user to choose a 4 character bech32 identifier seemed like too much work for them.

[apoelstra]

Is this something that is too difficult for me to do in a day without advanced mathematical knowledge even if I know the codex32 GENERATOR and MS32_CONST?

I'm not sure. You can see the different constants all laid out here or by checking the BIP (I think they're in slightly different formats in the BIP vs that source code, so not sure which version you need). But where you'll run into trouble is that the codex32 checksum is 65 bits meaning that it won't fit into a single 64-bit word. Bech32 has a 30-bit checksum, so implementations have a habit of using 32-bit words to implement them ... and then a "just change the constants" conversion runs into trouble if you don't have any uint128_t type in your language.

But in principle it should work.

Related to this, I set the identifier characters to hash160(seed)[:4] and the payload padding bits of the codex32 secret to double_sha256(seed)[0] (like truncating the WIF serialization) so have an additional 22/24-bits of error detection for 128/256-bit seeds.

This is a pretty neat idea. Yeah, I think it's worth suggesting that people do this, if they are using an electronic means of generation and they don't otherwise want to override the name.

Asking the user to choose a 4 character bech32 identifier seemed like too much work for them.

This is fair, but it is important that they be able to distinguish different seeds, so that e.g. if they have a shares from multiple friends, they don't get them mixed up. Using psuedorandom characters might make that harder.

[roconnor-blockstream]

Since the master seed is thrown away in many implementations, it might make more sense to hash the master private key instead when generating an identifier in a deterministic manner.

[BenWestgate]

Since the master seed is thrown away in many implementations, it might make more sense to hash the master private key instead when generating an identifier in a deterministic manner.

That's true, unless something like #55 gets done.

And if you know the master private key, what use is knowing which codex32 set corresponds to it? You can already spend... Unless trying to create a new codex32 backup for an existing master seed with a higher threshold, but the assumption usually made is codex32 backups are "set in stone" (perhaps literally) and may not be able to be destroyed.

A more useful option may be the master pubkey hash: [81fefeef/44'/0'/0'] so the recovery codes can be matched to their watch-only wallet as well. "To recover, find your recovery codes beginning with 'ms1_81fe'... and import them to your external signer" (i'd need to use bech32, this is a quick example)

Trying to make those 20-bits do as much work as possible with following options:

1. master seed hash - hash160(seed)
2. master extended private key hash - double_sha256(extended_private_masterkey)
3. master public key hash - hash160(sha256(public_masterkey))

The best choice also depends where plausible deniability, if any, should be: User selects, every level is deniable. Seed hash, every level is deniable except after a threshold of shares is compromised. Xprv hash deniable link until spending is compromised. Master pubkey hash no deniability between a watch-only wallet and its recovery shares.

1. Legacy Bitcoin Core wallets calling getwalletinfo display:
   "hdseedid": "1b50a849a48ddabb9763bd12c11942233a2d21f2"
   which is hash160(hdseed) and was my original deterministic identifier to keep it consistent.

2. Descriptor wallets seem to discard this if they even generate a seed at all. But calling listdescriptors true displays:
   "desc": "...(xprv.../<purpose>'/0'/0'/.../*)#...",
   which is the extended private masterkey in each descriptor but not in an identifier safe format, except the last 4-bytes of the xprv serialization which is the double SHA-256 checksum. So a base58 decoder is required instead of hex in option 1 and 3.

3. Alternatively, calling listdescriptors displays:
   "desc": "...([f4617790/<purpose>'/0'/0']xpub.../.../*)#..."
   which is the hash160(sha256(public_masterkey)[:4] prepended to each child extended public key, also known as the master public key fingerprint.

The hex to bech32 conversion should be preferred. There's pros and cons to 1 vs 3.

Pros to hash160(seed):

• Keeps compromised descriptor wallets and k-1 compromised shares plausibly deniable from each other.
• Detects errors from wrong but valid codex32 strings (malicious tampering of k-1 shares).

Cons:

• Pseudo-random characters without any reference stored make shares easier to mix up
• Requires entering master seed on a trusted device to detect wallet tampering
• Can't detect errors from by hand computation of private or public masterkeys
• Worse manual error correction as identifier is not stored in the watch-only descriptor

Pros to hash160(sha256(public_masterkey):

• Allows watch-only wallets to give recovery instructions with a suggested identifier to look for.
• Requires work to grind a valid identifier to tamper a 'private keys enabled' wallet
• Detects errors from wrong but valid codex32 strings (malicious tampering of k-1 shares)
• Detects errors in any future by hand computation of public or private master keys
• Better error correction as a watch-only wallet can provide the correct identifier

Cons:

• May not want a compromised share's identifier to reveal it likely belongs to a 1,000 BTC watch-only wallet or vice versa.
• 20-bits isn't much work to make an xprv's master pubkey fingerprint match the codex32 identifier
• Requires entering xprv on a trusted device to derive the fingerprint to detect wallet tampering
• If Use case: Derive X BIP32 keys from a paper seed #55 implemented, only one wallet gets an intelligible connection to the identifier

[roconnor-blockstream]

And if you know the master private key, what use is knowing which codex32 set corresponds to it?

I was imagining the scenario: Hey I found these shares in my closet that I forgot about. What are they for again? Are they for my existing wallet I'm using or for something else?

[apoelstra]

This is a good list of pros and cons. I'd also add that if #55 were somehow implemented, we'd have a hand-computed RNG, and maybe using that in place of sha2 would be nicer. (Though it would pretty-much force us to use hash(seed) since public_masterkey can't be determined by hand.)

I'd also note that any of these choices achieve the "detect errors from wrong but valid codex32 strings" benefit, though all of them require recovering the seed to do the check.

Then as for what the best thing to recommend, my intuition is that the better UX outweighs the concerns about deniability, and that hash160(public_masterkey) is the better way to go. It lets wallets provide the most useful instructions to users without needing to access (or even being able to access) secret key data. Remember that even the "public masterkey" is still an xpub and never appears on-chain, so the privacy loss is somewhat limited. It's not like visitors can find your shares, see the ID, then go home and scan the blockchain to discover how many coins you (or your friends) have.

My feeling is that people who want deniability are free to make up their own key IDs, or to copy key IDs from other peoples' xpubs they somehow come across, or whatever they want to do.

[BenWestgate]

I was imagining the scenario: Hey I found these shares in my closet that I forgot about. What are they for again? Are they for my existing wallet I'm using or for something else?

With option 3 this question could be answered with the master pubkey fingerprint from your watch-only wallet.

Do you see appreciable value in keeping the association between shares and an existing wallet a secret without the pin or wallet passphrase?

Option 1 would not be helpful to this situation without a full seed restore & wallet import so add this to its list of cons.

Though it would pretty-much force us to use hash(seed) since public_masterkey can't be determined by hand.

A hand-computed hash(seed) identifier would be better if one is implemented as it offer's option 1's pro of detecting k-1 maliciously tampered yet valid shares without electronics.

Remember that even the "public masterkey" is still an xpub and never appears on-chain, so the privacy loss is somewhat limited. It's not like visitors can find your shares, see the ID, then go home and scan the blockchain to discover how many coins you (or your friends) have.

Right, it requires the compromise of the watch-only wallet AND shares to give thieves useful information. And they still could be misled as long as implementations allow creating codex32 backups with chosen identifiers. (mine does not but it's not hard to add.)

My feeling is that people who want deniability are free to make up their own key IDs, or to copy key IDs from other peoples' xpubs they somehow come across, or whatever they want to do.

I agree, the perfect deniability of choosing an identifier is better than the limited deniability of hash(seed) since it allows for decoy shares, seeds and wallets.

So there is no reason to use 1 over "choose an identifier" unless such a hand-computable hash is implemented. Then that could still be a special case of "choose an identifier" that people doing hand computations wanting to detecting malicious tampering of k-1 shares may choose.

Regarding plausible deniability between watch-only wallets and hash160(public_masterkey) identified shares, it is easy to put fake master pubkey fingerprints in descriptors, if desired, to break the relationship and you can plausibly claim you did this, even when you did not. While option 2 has no way to plausibly deny shares when their identifier in the wallet, compromised spending, is possible.

[BenWestgate]

But where you'll run into trouble is that the codex32 checksum is 65 bits meaning that it won't fit into a single 64-bit word. Bech32 has a 30-bit checksum, so implementations have a habit of using 32-bit words to implement them ... and then a "just change the constants" conversion runs into trouble if you don't have any uint128_t type in your language.

I converted bech32_ecc.js it to python and added the codex32 constants provided from lib.rs. It successfully locates the error positions in bech32 addresses! But returns {'error': 'Invalid checksum', 'data_pattern': None} for codex32 strings, valid or invalid, which means residue != 0: which means polymod(hrpExpand(hrp) + data) ^ const != 0 and I am using the proper codex32 CONST and GENERATOR.

I think the issue lies in the def syndrome(residue): function, I notice all the values it it is bitwise xoring with are smaller than the maximum value for the 30-bit checksum.

So I believe def syndrome(residue) needs to bitwise xor with longer 65-bit numbers when encoding == encodings["CODEX32"]: but where do I come up with these numbers?

But in principle it should work.

I'd like to get it to work. I'm highly motivated because it makes codex32 secret recovery faster and much more confidence inspiring.

delete codeblock for readability

[BenWestgate]

besides the syndrome(residue) function appearing to be 30-bit specific, I also need to use ms32_polymod in the codex32 case not the one in the code above as the bitshifts are 6 character / 30-bit specific

def ms32_polymod(values):
    GEN = [
        0x19dc500ce73fde210,
        0x1bfae00def77fe529,
        0x1fbd920fffe7bee52,
        0x1739640bdeee3fdad,
        0x07729a039cfc75f5a,
    ]
    residue = 0x23181b3
    for v in values:
        b = (residue >> 60)
        residue = (residue & 0x0fffffffffffffff) << 5 ^ v
        for i in range(5):
            residue ^= GEN[i] if ((b >> i) & 1) else 0
    return residue