summaryrefslogtreecommitdiff
path: root/bip-0350.mediawiki
diff options
context:
space:
mode:
authorPieter Wuille <pieter@wuille.net>2021-01-29 11:33:27 -0800
committerPieter Wuille <pieter@wuille.net>2021-01-29 13:41:08 -0800
commitd3874ff3ec0ca090a12a0f48560f3d819d9bee10 (patch)
treed39cb3ce0cc1f2e1f97891dd37e638f0afb82bf2 /bip-0350.mediawiki
parente192983f5b1fc7a2a0739906103fd6ed8f383c8d (diff)
downloadbips-d3874ff3ec0ca090a12a0f48560f3d819d9bee10.tar.xz
Update bip-0350.mediawiki
Co-authored-by: andrewtoth <andrewstoth@gmail.com>
Diffstat (limited to 'bip-0350.mediawiki')
-rw-r--r--bip-0350.mediawiki2
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).