From d3874ff3ec0ca090a12a0f48560f3d819d9bee10 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 29 Jan 2021 11:33:27 -0800 Subject: Update bip-0350.mediawiki Co-authored-by: andrewtoth --- bip-0350.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'bip-0350.mediawiki') 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-30'', 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-10'' 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). -- cgit v1.2.3