diff options
author | Pieter Wuille <pieter@wuille.net> | 2021-01-29 11:33:27 -0800 |
---|---|---|
committer | Pieter Wuille <pieter@wuille.net> | 2021-01-29 13:41:08 -0800 |
commit | d3874ff3ec0ca090a12a0f48560f3d819d9bee10 (patch) | |
tree | d39cb3ce0cc1f2e1f97891dd37e638f0afb82bf2 /bip-0350.mediawiki | |
parent | e192983f5b1fc7a2a0739906103fd6ed8f383c8d (diff) |
Update bip-0350.mediawiki
Co-authored-by: andrewtoth <andrewstoth@gmail.com>
Diffstat (limited to 'bip-0350.mediawiki')
-rw-r--r-- | bip-0350.mediawiki | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/bip-0350.mediawiki b/bip-0350.mediawiki index 3ad41c8..d09ae6b 100644 --- a/bip-0350.mediawiki +++ b/bip-0350.mediawiki @@ -220,7 +220,7 @@ For Bech32m, we aim to retain Bech32's guarantees for substitution errors, but m ===Error patterns & detection probability=== -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. +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. A hash function-based checksum design with a 30-bit hash would have a probability of incorrectly accepting equal to ''2<sup>-30</sup>'', for every error pattern. Bech32 has a probability of 0 to incorrectly accept error patterns consisting of up to 4 substitutions—they are always detected. The 'q'-insertion issue shows that for Bech32 a simple error pattern ("insert a random character in the penultimate position") with probability ''2<sup>-10</sup>'' exists: it requires the final character to be 'p' (leaving only 1 in 32 strings), and requires the inserted character to be 'q' (permitting only 1 of 32 possible inserted characters). |