MIME-Version: 1.0
In-Reply-To: <CAMZUoKkXhyGcHs3z-qq-eVwnTg3oqZf3dO25BtBY=PvTnOoucg@mail.gmail.com>
References: <CABuOfuhMGFGc1tyjcOmnUk1OrWp2d6ppKc8phLT9pXCj8vs+qg@mail.gmail.com>
	<FE65454B-B30A-4CEF-B568-B2746BD2BC0B@jonasschnelli.ch>
	<E449A58B-08C4-4A1C-8109-38C800B718AF@jonasschnelli.ch>
	<CAPg+sBiL9S29MV-cxrqGMeaWADO5-C3ejmxY21V_qUGHjhDHGw@mail.gmail.com>
	<CAMZUoKkXhyGcHs3z-qq-eVwnTg3oqZf3dO25BtBY=PvTnOoucg@mail.gmail.com>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Sat, 23 Jun 2018 12:49:54 -0700
Message-ID: <CAPg+sBihc83xBNCRR37-F2hnJ8Rs3C5pkWutF8iGdKAkDFcvKg@mail.gmail.com>
To: "Russell O'Connor" <roconnor@blockstream.io>
Content-Type: text/plain; charset="UTF-8"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] New serialization/encoding format for key material
Precedence: list

On Fri, Jun 15, 2018 at 8:54 AM, Russell O'Connor
<roconnor@blockstream.io> wrote:
>
>> For codes designed for length 341 (the first length enough to support
>> 512 bits of data):
>> * correct 1 error = 3 checksum characters
>> * correct 2 errors = 7 checksum characters
>> * correct 3 errors = 11 checksum characters
>> * correct 4 errors = 15 checksum characters
>> * correct 5 errors = 19 checksum characters
>> * ...
>> * correct 7 errors = 26 checksum characters (~ length * 1.25)
>> * correct 13 errors = 51 checksum characters (~ length * 1.5)
>> * correct 28 errors = 102 checksum characters (~ length * 2)
>>
>> So it really boils down to a trade-off between length of the code, and
>> recovery properties.
>
>
> At the risk of making the proposal more complex, I wonder if it might be
> better to support multiple checksum variants?  The trade-off between code
> length and recovery seems to be largely determined by the user's medium of
> storage, which is likely to vary from person to person.  I personally would
> probably be interested in the 51 or even 102 character checksums variants.

Here are some more numbers then. It's important to note that the
number of correctable errors includes errors inside the checksum
characters themselves. So if you want to aim for a certain percentage
of correctable characters, the numbers go up much more dramatically.

For codes restricted to 341 characters total (including the checksum
characters), and assuming 103 data characters (enough for 512 bits):
* With 26 checksum characters (adding 25%, 20% of overall string), 7
errors can be corrected (5% of overall string)
* With 62 checksum characters (adding 60%, 38% of overall string), 17
errors can be corrected (10% of overall string)
* With 116 checksum characters (adding 113%, 53% of overall string),
33 errors can be corrected (15% of overall string)
* With 195 checksum characters (adding 189%, 65% of overall string),
60 errors can be corrected (20% of overall string)

For codes restricted to 1023 characters total (including the checksum
characters), and assuming 103 data characters (enough for 512 bits):
* With 27 checksum characters (adding 26%, 21% of overall string), 7
errors can be corrected (5% of overall string)
* With 64 checksum characters (adding 62%, 38% of overall string), 17
errors can be corrected (10% of overall string)
* With 127 checksum characters (adding 123%, 57% of overall string),
36 errors can be corrected (15% of overall string)
* With 294 checksum characters (adding 285%, 74% of overall string),
80 errors can be corrected (20% of overall string)
* With 920 checksum characters (adding 893%, 90% of overall string),
255 errors can be corrected (25% of overall string)

I'll gladly construct reference source code for any of these.

Cheers,

-- 
Pieter