From: Pieter Wuille <bitcoin-dev@wuille•net>
To: Rusty Russell <rusty@rustcorp•com.au>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Progress on bech32 for future Segwit Versions (BIP-173)
Date: Wed, 28 Oct 2020 00:20:40 +0000 [thread overview]
Message-ID: <p6i6YqXjOBastpss12gNUcJGGqomgPiLXOIyob71VptqVwJwcFwrd4m8Mad4RDnAhSyFXAZqsD67fW0kS3NayQ6k6dB-h2_V7vl7RBxmvvA=@wuille.net> (raw)
In-Reply-To: <87imblmutl.fsf@rustcorp.com.au>
On Wednesday, October 7, 2020 5:21 PM, Rusty Russell via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
> I propose an alternative to length restrictions suggested by
> Russell in https://github.com/bitcoin/bips/pull/945: use the
> https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb variant,
> unless the first byte is 0.
Hi all,
starting a slight side-thread here.
The discussion here made me realize that as we're introducing (at some point) a new checksum scheme, we don't just care about the new scheme's own error detection capabilities, but also about the probability that a new style address + errors is incorrectly accepted as an old style address.
Clearly these properties are less of a priority than just the new-style + error being misinterpreted as a new-style address, as problems will only occur when entering a new address with errors in old software that supports the old scheme (which this thread shows, is not very common). Still, all other things being equal, it can't hurt to see if some choices are better than others.
https://gist.github.com/sipa/a9845b37c1b298a7301c33a04090b2eb suggested the use of constant M = 0x3FFFFFFF. It turns out this is slightly suboptimal in two ways:
* It's possible to take a new-style address with that constant, make 3 substitution errors, and obtain an old-style address.
* If a new-style address ends with '7', inserting 'g78u' just before it will result in a valid old-style address (ignoring length constraints).
I don't think either of these is serious, but it's possible to improve upon them:
* Guaranteeing that 4 substitution errors are always detected while switching schemes seems impossible, but a constant can be picked that guarantees 3 errors always are.
* Insertion/deletion errors can be restricted to patterns that require 6 fixed characters (which, assuming uniformly random characters, implies a probability of 2^-30).
It seems M=0x3ffeffff has both these properties.
I'm going to do some more analysis (swapping, and insertion/erasure near the start), and then update my gist, but so far it seems this is a strictly (albeit only slightly) better choice.
Cheers,
--
Pieter
next prev parent reply other threads:[~2020-10-28 0:20 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-08 0:21 Rusty Russell
2020-10-08 14:59 ` David A. Harding
2020-10-08 15:21 ` Russell O'Connor
2020-10-15 1:40 ` Rusty Russell
2020-10-16 21:09 ` Pieter Wuille
2020-10-19 0:49 ` Rusty Russell
2020-10-19 22:55 ` Pieter Wuille
2020-10-20 0:42 ` Rusty Russell
2020-10-20 3:31 ` Rusty Russell
2020-10-20 9:21 ` Riccardo Casatta
2020-10-20 10:29 ` David A. Harding
2020-10-20 20:12 ` Pieter Wuille
2020-10-20 23:52 ` Mike Schmidt
2020-10-21 4:51 ` Rusty Russell
2020-11-06 19:49 ` Mike Schmidt
2020-12-05 23:10 ` Pieter Wuille
2020-12-06 13:04 ` David A. Harding
2020-12-06 20:43 ` Pieter Wuille
2020-12-08 17:39 ` Ryan Grant
2020-12-18 2:02 ` Pieter Wuille
2020-10-21 3:05 ` ZmnSCPxj
2020-10-21 4:39 ` Rusty Russell
2020-10-28 0:20 ` Pieter Wuille [this message]
2020-12-05 22:59 ` Pieter Wuille
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='p6i6YqXjOBastpss12gNUcJGGqomgPiLXOIyob71VptqVwJwcFwrd4m8Mad4RDnAhSyFXAZqsD67fW0kS3NayQ6k6dB-h2_V7vl7RBxmvvA=@wuille.net' \
--to=bitcoin-dev@wuille$(echo .)net \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=rusty@rustcorp$(echo .)com.au \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox