1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8B4462C
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 23 Jun 2018 19:49:56 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f45.google.com (mail-oi0-f45.google.com
[209.85.218.45])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 23D235E2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 23 Jun 2018 19:49:56 +0000 (UTC)
Received: by mail-oi0-f45.google.com with SMTP id e8-v6so9081240oii.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 23 Jun 2018 12:49:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to
:cc; bh=TgoK/pxyFIbdgkd/V1RngUyZJm0p0aXy29cHGyGLDBQ=;
b=C3jSBBRVa/rkW783IqGeO3VFMkkRq8C0SnooYlkfQVcV1RU35iVbHmAk842ft1HrUf
WVxF4jzkzJdpu2dfVVbyB2ZL7qoLEXJ5e2lEBYEVFTR4s7heB2KFIXN2aIcCz1eRu8aq
YnqsXwZnpdCbmWItNpWtnmFjNoxCHwtKAKQ7pUiDx3akxI2xB8R41FNyBoHpE0cFMqXK
TH7YO0T+LKCUjUXUSrtLd5UKoJ0o7FkptyR9YgriMr36CnNqTc4JUnsX+f2Fj/bjtUOL
R0mYUv7Qkbh2zNb7sBO+STLSV86AIcL0fa928n1oWArnlX5A7EVdRM3+eI/McyvbXTnZ
756A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to:cc;
bh=TgoK/pxyFIbdgkd/V1RngUyZJm0p0aXy29cHGyGLDBQ=;
b=XVe/5hCgtEciLXSOsSw78u1CpDnUNwoXwO9ajefrGzYESbRZZlRPYnlhZlByLfyWS/
l4EDP3kMYHS72MM+H9ByHXd3WeJj1LubbTGG8d5NbPGBkYrPXi3nnD2WESM3wM2yXOgS
DcdJNQmdANP+vfHJPMASepojq+frcSUsFF0eMMHoqIKsz/kSGflvWeAbY3LjwaZXg0nw
ixLu1v0kPvU++7zE5sITAiwhlL+jpHfDQ4u6rSLvjk22PjqRjTXCSqCVaDE0omHS0ZHm
ien4uqqPbwTviYm4/WGeRqLY6aMVY2lWy+WHlSBSafNssAv88Inx/BXojDoWjbE0rVq+
OG+A==
X-Gm-Message-State: APt69E1SjtOqiE8HDelbguCicKCnWcvHyPD4FjOSu9dBnP7CrdGsBCn0
To3VNUpnL5kGMtgz25ODOYLTL8A1YFGfXQhCrW/gdA==
X-Google-Smtp-Source: ADUXVKJvsMItY6eTks/z6TpFulxDM+q+fVXl7uDWVgGFqQhtv8ElF6nEPgXHaMc8z3nRT0d5P7jTDJCF5DclThnrsso=
X-Received: by 2002:aca:5887:: with SMTP id
m129-v6mr3636617oib.76.1529783395263;
Sat, 23 Jun 2018 12:49:55 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a4a:6a89:0:0:0:0:0 with HTTP; Sat, 23 Jun 2018 12:49:54
-0700 (PDT)
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"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] New serialization/encoding format for key material
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 23 Jun 2018 19:49:56 -0000
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
|
