BlockstreamResearch / codex32

A paper computer for Shamir's Secret Sharing over the Bech32 alphabet.
79 stars 23 forks source link

Source code for error correction? #54

Open BenWestgate opened 1 year ago

BenWestgate commented 1 year ago

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

apoelstra commented 1 year ago

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 commented 1 year ago

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 https://github.com/sipa/bech32/issues/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:

apoelstra commented 1 year ago

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:

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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.

    1. 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):

Cons:

Pros to hash160(sha256(public_masterkey):

Cons:

roconnor-blockstream commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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
roconnor-blockstream commented 1 year ago
residue = 0x23181b3

Be aware that in the Codex32 spec, we precomputed the hrp and folded it into that constant. If you are going to compute the hrp yourself you'd start the residue at 1 instead (and then after processing the hrp, you should end up at 0x23181b3).

roconnor-blockstream commented 1 year ago

But yes, the constants in the syndrome need to be replaced with codex32 specific constants by someone who knows what the constants mean and how to compute them.

BenWestgate commented 1 year ago

Here is a naive brute force error correction implementation that assumes only 48-character strings are valid and then corrects any distance 2 edits, and some distance 3, 4 and 5 edits when they involve multiple inserted characters. The corrections arrive in reasonable time, ranging between instant for single corrections, 1.5 seconds or 10 seconds for two corrections and max 26 seconds for a couple triple edit corrections on my i5-1135G7.

https://github.com/BenWestgate/Bails/blob/master/lib/python3.9/site-packages/codex32/naive_ms32_ecc.py

I optimized it to look for faster correcting and more probable errors before slower and less likely ones. And to speed up a bit when a valid_identifier is known, It might help to use multiple cores to get/check candidates faster but I'm new to that sort of programming.

One thing I didn't see mentioned earlier was correcting insertion errors is twice as fast as substitutions or deletions.

Correcting 5 insertion errors is faster than 2 deletion or 2 substitution. I did not see any invalid correction suggestions. The GUI that uses this library asks for confirmation, although I still must implement highlighting of the corrections during recovery.

apoelstra commented 1 year ago

Nice! When we implement error correction in rust-bech32 we'll have some numbers to beat.

BenWestgate commented 1 year ago

I should have used a lookup table for correcting substitutions and erasures (also deletions), as you suggested. It would spare the CPU some work and may perform better. Insertion errors still need brute force.

BenWestgate commented 1 year ago

Found two omissions in the BIP for error correction implementation recommendations:

We do not specify how an implementation should implement error correction. However, we recommend that:

If a string with 8 or fewer erasures can have those erasures filled in to make a valid codex32 string, then the implementation suggests such a string as a correction. If a string consisting of valid bech32 characters in the proper case can be made valid by substituting 4 or fewer characters, then the implementation suggests such a string as a correction.

It is missing the burst erasure correction case:

It is also missing the combination case:

floor((1 - (contiguous_erasures / 13 + non_contiguous_erasures / 8)) * 4) = remaining_error_correction_capacity

Correctable Combination Examples:

BenWestgate commented 1 year ago

During initial wallet setup, behave like bech32: you can highlight substitution errors, but don't correct anything.

In my implementation, I display the uppercase codex32 string with space every 4th character for legibility.

After display, the confirm written string entry dialog has 12 four character boxes horizontally. The typing flows box to box as if it were one field.

Currently, if there is a substitution error in a full box, the text in that box turns red, and if a full box contains the correct characters, it is disabled from editing.

One UX issue this causes is an early insertion or deletion error will cause every full box afterward to turn red due to the shift, which is non-intuitive because only the 1st red box has the typo.

Is there any issue with highlighting red the groups of 4 with insertion and deletion errors as well as substitutions and not highlighting error free but shifted boxes?

(Ofc, they won't lock until they are correct AND "typo-free")

I know the checksum can't guarantee detecting these errors but for the backup creation phase the codex32 string is still in memory so every kind of diff can be detected and highlighted to help them correct their handwriting faster.

apoelstra commented 1 year ago

Even with the backup in memory there's a little bit of ambiguity between insertion/deletion errors and substitutions, but this sounds like a great idea to me. Assuming you think there's a deletion error, I'd show the offending 4-group box is red and with only 3 characters in it. Simililarly if there's an insertion, show the box in red with all 5 characters in it. No need to flag any other boxes as red. (I think this is what you're describing.)

BenWestgate commented 3 weeks ago

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.

Is there a patch yet with error correction capability I could test?

apoelstra commented 3 weeks ago

Still no -- it's probably 80% done but I haven't worked on it in a little while.

I'll leave this tab open until I get a chance to work on it.

FWIW I did PR and merge some prepatory work -- https://github.com/rust-bitcoin/rust-bech32/pull/180

apoelstra commented 1 week ago

@BenWestgate if you want to try playing with this, I have a branch now which can do error correction, you can try https://github.com/apoelstra/rust-bech32/tree/2024-03--error-correction2/

The "real" API isn't really done at all. But basically to use it, you try parsing as normal, then if the checksum is wrong, you unwrap the error then call .correction_context() on it (you'll need to import a trait). Then if there was a checksum error, this will return a "correction context".

If you know the location of some errors (i.e. they are erasures) then you can call .add_erasures on the context. You have to give the locations as indexes from the end of the string -- 0 is the last character, 1 the second to last, etc. Also if there are ?s or something in the string it won't parse. You have to search-and-replace them with q or something beforehand. (My plan before releasing is to add a new parsing API which interprets invalid characters as erasures.)

Then you can get all the errors -- erasures and substitutions -- by calling the .bch_errors() on the context. It will return the location as indexes from the end of the string.

It can't handle burst errors yet (not totally obvious how to do this because there isn't a unique way to handle them except when the user knows exactly where the burst error is and knows that every other character is correct), and doesn't try at all to handle insertions or deletions (this will require brute forcing I think, and again the result isn't guaranteed to be unique).

(The suggested correction also isn't guaranteed to be correct; if there are more than 4 errors it might return a "correction" that leads to a wrong string. This is inherent to error-correcting codes, but sometimes the corrector can detect this, and I have a bug right now where sometimes it doesn't detect this case and it should.)

BenWestgate commented 3 days ago

I've built your branch and ran the tests. I've never used rust before. Now I want to give it my own strings. So I'm stuck at:

you try parsing as normal

There's no CLI for that right? I have to make a rust file and import rust-bech32?

Then do we or do we not have an "allocator" for a codex32 string?

Non-segwit stuff and you do not have an allocator, use the CheckedHrpstring type for decoding. For encoding we provide various top level functions of the form encode*_to_fmt. To define your own checksum algorithm implement Checksum

Then I presume I also have to use this Checkum "trait" (had to look this up too, collection of methods) to make it use the codex32 checksum.

Once I've got it telling me error locations for arbitrary codex32 data the rest will go fast and will also have

Brute force search to correct other types of errors: 5 single bit symbol errors swaps (a special case of insertion and deletion where insert equals deleted) duplicates (a special case of insertion where the last char was repeated) insert/delete Validating candidate secret's Fingerprint. Validating candidate's CRC-7 when it knows it should pass Reject corrections that change an already accepted header or length

Each of the error types has a certain correction search space. I search smallest to largest using all CPUs for 10 seconds and return the smallest "edit distance" correction found, if any. Considering adding the option to let it keep searching with an infinite progress bar and maybe some text saying what error pattern it's currently checking if users would like to heat their apartment in the winter with bad typing. This is more or less your "list decoder" (brute force search of ever more insertions and deletions without a time limit) but using a fingerprint rather than an address.

apoelstra commented 3 days ago

There's no CLI for that right? I have to make a rust file and import rust-bech32?

Correct. I don't know of any CLI that can do this.

It should be possible to make Python bindings to my Rust code, though I haven't done that before.

Then do we or do we not have an "allocator" for a codex32 string?

Yes, you have an allocator unless you bend over backward to disable it.

Each of the error types has a certain correction search space. I search smallest to largest using all CPUs for 10 seconds and return the smallest "edit distance" correction found, if any.

For substitutions and erasures, this should take a few microseconds, not seconds :). And my understanding from the UX RFC that we developed way back when, is that substitutions and erasures are the only things that MUST be correctable. While additional stuff are "nice to haves" and I don't want to hold up adoption of codex32 based on them.

An open-ended list decoder like you're describing would probably deserve its own project. It would be much more complex than rust-bech32, would probably want to support a lot of "ad-hoc" things like providing different distance criteria, different "hints" like fingerprints and addresses, support trying to correct multiple strings at once, etc. And it would be an open-ended research project to speed it up.

BenWestgate commented 3 days ago

Screencast from 2024-10-02 15-33-38.webm

apoelstra commented 3 days ago

How can you tell that the FHFE segment is wrong when you only have 32 characters of input?

BenWestgate commented 3 days ago

Thank you for answering those questions. I'll continue tinkering.

For substitutions and erasures, this should take a few microseconds, not seconds :).

Yes. Brute force can check every candidate's codex32 ECC correction to find the closest correction when it's out of time. Deletions can be filled with erasures now. Can remove ins+del patterns from the search that create 1-4 substitution errors.

And my understanding from the UX RFC that we developed way back when, is that substitutions and erasures are the only things that MUST be correctable. While additional stuff are "nice to haves" and I don't want to hold up adoption of codex32 based on them.

Of course.

BenWestgate commented 3 days ago

How can you tell that the FHFE segment is wrong when you only have 32 characters of input?

This is the Display and Confirm dialog when generating backups. Notice advice about how to hide the written copy that's partly cut off after it's confirmed successfully.

So the script was called with the correct string, it doesn't do any error detection with the checksum just uses "difflib" to find the edit locations for highlighting wrong boxes..

BenWestgate commented 3 days ago

Notice advice about how to hide the written copy that's partly cut off after it's confirmed successfully.

The other question you'd have to ask was:

How did it know this was "codex32 share 1 of 2" when I hadn't typed MS12 yet?

Different dialogs for backup confirmation and import. They both use groups of 4 though but my recovery dialog doesn't have a length limit (besides 513).

It also doesn't highlight particular parts of the string when it's wrong, if ECC can find a correction it offers to show it.

I think highlighting particular groups was riskier for accepting a false correction, because it draws the eyes towards the red parts while the real mistakes (vs the correct paper copy) may be in black. Ultimately the whole suggestion should be checked against the paper so there's no need to highlight anything.