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
137
138
139
140
141
142
143
144
145
146
|
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 756DA907
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 3 Jun 2018 19:23:19 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ot0-f172.google.com (mail-ot0-f172.google.com
[74.125.82.172])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id F35CF6EE
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 3 Jun 2018 19:23:18 +0000 (UTC)
Received: by mail-ot0-f172.google.com with SMTP id i19-v6so4494434otk.10
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 03 Jun 2018 12:23:18 -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;
bh=8Cy2FdPHE5LD3+ExzdIC83Sxgg+dsA8kdY0XmaZmHRo=;
b=fj6XF7OyVdTw38F9mt8VRAp9zpNLFjsu5JFOSDb5dgIF+83+2u9cn5TQrr3vii5NgC
m7cGbMB9XbDJUK7qMZzJ+9GeCDT2OQ9rLgx4tA64iPzZBQgnQryIGcBVBluow/1j5Meb
sGTZSITS4fGBKBOW2ybTzLrRMK0fn36jXsMyoH1SYfEM+zJCamYgSE60J+CLC65lEyVz
7XOZvWwOy6q2RY+b8C0MP6FdnZyslh435lotrq9Nn4bKht4W8c40iw24zAWxX4gVXv/F
befsv0enY+8k1h3Q5MuP50vSz1Nngr27MnhyukCY6R75kGBHQif63ixGL/1vg/5x9jsf
bMTg==
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;
bh=8Cy2FdPHE5LD3+ExzdIC83Sxgg+dsA8kdY0XmaZmHRo=;
b=iPeRwAXh8KzduI8t6LykR/tusVA+jQw1QJTS4EfkCHKFk0UJv4/w8+lhutuwVLzZas
ZcmqmnQO6dKaCUdkqJYeXyQcFRJP1rdWSfBGf88zdZRB40L6/BwEWmZai0rFs0QT+Z9L
5jNuFGL01zOzj1e3/PLhgmC1Jd8mL7OPhuul1rwiZLwRIT7bX69xGfvZr82qzDSVhQEr
46JDGT3GcTUYrwdZS3E35Pozf3uh32/FK7cifwTy+YlX9pDDMgpg1wyvc4k+/qkZlz6Q
OengveTlqkozHLiHzubjx8poFz1MExQxBC4wcOePuJGIA2bCOpVsBER5BAF61BXrPjef
bkLQ==
X-Gm-Message-State: ALKqPwfIR0f59rf9eE/9KGqOCU2/DHKCYhRXEPOKCziWt6kwZSAXet2w
OEAJ9Q8+a/oWHLoQK7RiLFqplEVr08Tq3FmHqUKuJw==
X-Google-Smtp-Source: ADUXVKJgOlounZeJGN5TkBX5e3GZt9h91M9n70ebzDKmCQPobq16/a+L3qR+Y4/eBLYFV10/jjsNct2YzImyRWx5HCQ=
X-Received: by 2002:a9d:4361:: with SMTP id
y30-v6mr13362649oti.170.1528053797920;
Sun, 03 Jun 2018 12:23:17 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a4a:6ac8:0:0:0:0:0 with HTTP;
Sun, 3 Jun 2018 12:23:17 -0700 (PDT)
In-Reply-To: <E449A58B-08C4-4A1C-8109-38C800B718AF@jonasschnelli.ch>
References: <CABuOfuhMGFGc1tyjcOmnUk1OrWp2d6ppKc8phLT9pXCj8vs+qg@mail.gmail.com>
<FE65454B-B30A-4CEF-B568-B2746BD2BC0B@jonasschnelli.ch>
<E449A58B-08C4-4A1C-8109-38C800B718AF@jonasschnelli.ch>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Sun, 3 Jun 2018 12:23:17 -0700
Message-ID: <CAPg+sBiL9S29MV-cxrqGMeaWADO5-C3ejmxY21V_qUGHjhDHGw@mail.gmail.com>
To: Jonas Schnelli <dev@jonasschnelli.ch>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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
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: Sun, 03 Jun 2018 19:23:19 -0000
On Sun, Jun 3, 2018 at 9:51 AM, Jonas Schnelli via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hi
>
> The BIP proposal is now available here:
> https://gist.github.com/jonasschnelli/68a2a5a5a5b796dc9992f432e794d719
>
> Reference C code is available here:
> https://github.com/jonasschnelli/bech32_keys
>
> Feedback, criticism, etc. welcome!
First of all, thanks for working on this.
I have some concerns about the use of Bech32. It is designed for
detecting 3 errors up to length 1023 (but is then picked specifically
to support 4 errors up to length 89). However, for error correction
this translates to just being able to efficiently correct 1 error
(3/2, rounded down) up to length 1023. You can of course always try
all combinations of up to N changes to the input (for any N), testing
the checksum, and comparing the results against the UTXO set or other
wallet information that may have been recovered. However, the checksum
at best gives you a small constant speedup here, not a fundamentally
improved way for recovery.
However, we can design other base32 BCH codes easily with different
properties. As we mostly care about efficient algorithms for recovery
(and not just error detection properties), it seems more important to
have good design strength (as opposed to picking a code from a large
set which happens to have better properties, but without efficient
algorithm, like Bech32).
This is what I find for codes designed for length 93 (the first length
for which efficient codes exist with length long enough to support 256
bits of data):
* correct 1 error = 3 checksum characters
* correct 2 errors = 6 checksum characters
* correct 3 errors = 10 checksum characters
* correct 4 errors = 13 checksum characters
* correct 5 errors = 16 checksum characters
* ...
* correct 8 errors = 26 checksum characters (~ length * 1.5)
* correct 11 errors = 36 checksum characters (~ maximum length without
pushing checksum + data over 93 characters)
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.
These two sets of codes are distinct (a code designed for length 93
has zero error correction properties when going above 93), so either
we can pick a separate code for the two purposes, or be limited to the
second set.
If there is interest, I can construct a code + implementation for any
of these in a few days probably, once the requirements are clear.
Cheers,
--
Pieter
|
