Add BIP 350 (bech32m) #1056

 118 | +    return (data[0], decoded)
 119 | +</pre>
 120 | +
 121 | +'''Error locating'''
 122 | +
 123 | +Bech32m, like Bech32m, does support locating<ref>'''What about error correction?''' As explained in BIP173, introducing error correction reduces the ability to detect errors. While it is technically possible to correct a small number of errors due to Bech32(m)'s nature as a BCH code, implementations should refrain from using this for more than indicating where an error may be present.</ref> the positions of a few substitution errors. To combine this functionality with

andrewtoth commented at 4:24 PM on January 29, 2021:

Bech32m, like Bech32, does support locating<ref>'''What about error correction?''' As explained in BIP173, introducing error correction reduces the ability to detect errors. While it is technically possible to correct a small number of errors due to Bech32(m)'s nature as a BCH code, implementations should refrain from using this for more than indicating where an error may be present.</ref> the positions of a few substitution errors. To combine this functionality with

 217 | +
 218 | +For Bech32m, we aim to retain Bech32's guarantees for substitution errors, but make sure that other common errors don't perform worse than a hash function-based checksum would. To make sure the new standard is easy to implement, we restrict the design space to only amending the final constant that is xored in, as it was [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-December/017521.html observed] that that is sufficient to mitigate the 'q' insertion issue while retaining the intended substitution error detection. In what follows, we explain how the new constant ''0x2bc830a3'' was chosen.
 219 | +
 220 | +===Error patterns & detection probability===
 221 | +
 222 | +We define an error pattern as a sequence of first one or more deletions, then swaps of adjacent characters, followed by substitutions, insertions, and duplications, in that order, all in specific positions, applied to a string with valid checksum that is otherwise randomly chosen. For insertions and substitutions we assume a uniformly random new character. For example, "delete the 17th character, swap the 11th character with the 12th character, and insert a random character in the 24th position" is an error pattern. "Replace the 43th through 48th character with 'aardvark'" is not a valid error pattern, because the new characters are not random and there is no reason why this particular string is more likely than any other to be substituted.

andrewtoth commented at 4:25 PM on January 29, 2021:

We define an error pattern as a sequence of first one or more deletions, then swaps of adjacent characters, followed by substitutions, insertions, and duplications, in that order, all in specific positions, applied to a string with valid checksum that is otherwise randomly chosen. For insertions and substitutions we assume a uniformly random new character. For example, "delete the 17th character, swap the 11th character with the 12th character, and insert a random character in the 24th position" is an error pattern. "Replace the 43rd through 48th character with 'aardvark'" is not a valid error pattern, because the new characters are not random and there is no reason why this particular string is more likely than any other to be substituted.

 231 | +The table below shows the error detection properties of Bech32m, and a comparison with Bech32. The code used for this analysis can be found [https://gist.github.com/sipa/14c248c288c3880a3b191f978a34508e#file-const_analysis-cpp here]. Every row specifies one error pattern via the constraints in the left four columns. The remaining columns report what percentage of those patterns have certain probabilities of not being detected. The columns are:
 232 | +
 233 | +* '''errors''' The maximum number of individual errors considered
 234 | +* '''of type''' What type of errors are considered (either "subst. only" for just substitutions, or "any" to also include deletions, swaps, insertions, and duplications)
 235 | +* '''window''' The maximum size of the window in which the errors have to occur<ref>'''What is an error pattern’s window size?''' The window size of an error pattern is the length of the smallest consecutive range of characters that contains all modified characters (on input or output; whichever is larger). For example, an error pattern that turns "abcdef" into "accdbef" has a window size of 4, as it is replacing "bcd" with "ccdb", a 4 character string. Window size is only meaningful when the pattern consists of two or more errors.</ref>
 236 | +* '''code/verifier''' Whether it about Bech32 or Bech32m encoded strings, and whether they are evaluated regarding their probability of being accepted by either a Bech32 or a Bech32m verifier.<ref>'''Why do we care about probability of accepting Bech32m strings in Bech32 verifiers?''' For applications where Bech32m replaces an existing use of Bech32 (such as segregated witness addresses), we want to make sure that a Bech32m string created by new software won’t be erroneously accepted by old software that assumes Bech32 - even when a small number of errors were introduced as well.</ref><ref>'''Should we also take into account failures that occur due to taking a valid Bech32m string, and after errors it becoming acceptable to a Bech32 verifier?''' This situation may in theory occur for segregated witness addresses when errors occur that change the version number in a v1+ address to v0. Due to the specificity of this type of error, plus the additional constraints that apply for v0 addresses, this is both unlikely and hard to analyze.</ref>

andrewtoth commented at 4:26 PM on January 29, 2021:

* '''code/verifier''' Whether it is about Bech32 or Bech32m encoded strings, and whether they are evaluated regarding their probability of being accepted by either a Bech32 or a Bech32m verifier.<ref>'''Why do we care about probability of accepting Bech32m strings in Bech32 verifiers?''' For applications where Bech32m replaces an existing use of Bech32 (such as segregated witness addresses), we want to make sure that a Bech32m string created by new software won’t be erroneously accepted by old software that assumes Bech32 - even when a small number of errors were introduced as well.</ref><ref>'''Should we also take into account failures that occur due to taking a valid Bech32m string, and after errors it becoming acceptable to a Bech32 verifier?''' This situation may in theory occur for segregated witness addresses when errors occur that change the version number in a v1+ address to v0. Due to the specificity of this type of error, plus the additional constraints that apply for v0 addresses, this is both unlikely and hard to analyze.</ref>