Source code for error correction? #54
Comments
|
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. |
|
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.
Does that mean error correction implementations:
|
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. |
|
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) |
|
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 But I don't know how to set some of the constants to be codex32 appropriate like:
and possibly some in Is this something that is too difficult for me to do in a day without advanced mathematical knowledge even if I know the codex32 |
Related to this, I set the 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. |
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.
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.
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. |
|
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: Trying to make those 20-bits do as much work as possible with following options:
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.
The hex to bech32 conversion should be preferred. There's pros and cons to 1 vs 3. Pros to
Cons:
Pros to
Cons:
|
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? |
|
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 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 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. |
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.
A hand-computed
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.)
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 |
I converted I think the issue lies in the So I believe
I'd like to get it to work. I'm highly motivated because it makes codex32 secret recovery faster and much more confidence inspiring.
|
|
besides the 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 |
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). |
|
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. |
|
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. 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 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. |
|
Nice! When we implement error correction in rust-bech32 we'll have some numbers to beat. |
|
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. |
|
Found two omissions in the BIP for error correction implementation recommendations:
It is missing the burst erasure correction case:
It is also missing the combination case:
Correctable Combination Examples:
|
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. |
|
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.) |
Is there a patch yet with error correction capability I could test? |
|
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 -- rust-bitcoin/rust-bech32#180 |
|
@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 If you know the location of some errors (i.e. they are erasures) then you can call Then you can get all the errors -- erasures and substitutions -- by calling the 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.) |
|
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:
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?
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: 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. |
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.
Yes, you have an allocator unless you bend over backward to disable it.
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. |
Screencast.from.2024-10-02.15-33-38.webm |
|
How can you tell that the FHFE segment is wrong when you only have 32 characters of input? |
|
Thank you for answering those questions. I'll continue tinkering.
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.
Of course. |
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.. |
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 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. |
Has a reference implementation for erasure correction or error correction in codex32 strings been written?
The text was updated successfully, but these errors were encountered: