search

BenWestgate / bails-wallet

Auditable Implementation for creating & importing Codex32 backups to Bitcoin Core
MIT License
2 stars 0 forks source link

Correct 2-4 erasures with a lookup table and highlight correction #12

Open BenWestgate opened 11 months ago

BenWestgate commented 11 months ago

All possible permutations of error patterns or characters that could have been erased can be checked for a good checksum.

A more efficient algorithm later will allow correcting 4 substitution errors and 8 random erasures or 13 contiguous erases.

Write this in python and add to my codex32/ms32.py library

Consider testing performance of even more error/erasure correcting ability but if it does not run in Real time do not use.

BenWestgate commented 11 months ago

Consider searching for errors incrementally, first try all possible permutations of 1 error, then 2 errors, then 3 ...

BenWestgate commented 11 months ago

all naive implementations correct 2 edits in 5-60 seconds which is too slow for restoring a wallet, in most cases the user could correct their mistakes off paper much faster than that defeating the point.

A separate utility can do deeper error correction for those needing to wait because their shares can't be read or were legitimately wrote down wrong.

However the real-time implementation may be able to do a final 1 delete pass on all candidate strings > VALID_LENGTH after the single edit is exhausted. delete is 32 times cheaper than insert and 30 times cheaper than substitution. This should run in about 1 second, which is perfect.

BenWestgate commented 11 months ago

The error correction is working well for all 2 and some 3 error patterns.

The GUI needs to be beautified with color to highlight the suggested corrections vs what they input and the old dialogs should still give feedback., might need some sleep commands or to refactor input_share

BenWestgate commented 11 months ago

Erasure correction by marking illegible characters with "?" and characters outside of the bech32 CHARSET has not been implemented and should be.

BenWestgate commented 11 months ago

Also while waiting for the ECC to run, highlight the easily known wrong characters: ? , wrong case, non-bech32 CHARSET, wrong hrp, wrong separator, wrong threshold, wrong identifier, repeated share index, mark these as erasures for the ECC processor or substitute the correct or probably correct value (B=8, last valid share's threshold & identifier, the correct case.)

Display and highlight the initial corrections. So it's similar to the next dialog that highlights the corrections.

This dialog displays how the user typed it, the next one with the corrections is ALL CAPS.

Use the same color to mark the location of mistakes that can't be easily corrected as used in create seed which only shows locations of wrong characters not the correction.