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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
|
Delivery-date: Thu, 16 May 2024 08:22:07 -0700
Received: from mail-qv1-f62.google.com ([209.85.219.62])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBF6JTCZAMGQETWMP4KI@googlegroups.com>)
id 1s7cvm-0003hv-OV
for bitcoindev@gnusha.org; Thu, 16 May 2024 08:22:07 -0700
Received: by mail-qv1-f62.google.com with SMTP id 6a1803df08f44-6a113df8f57sf98749196d6.2
for <bitcoindev@gnusha.org>; Thu, 16 May 2024 08:22:06 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1715872920; cv=pass;
d=google.com; s=arc-20160816;
b=VYZKExPvOy3XK7oyFrUj26OlRTscE5HR3Qet7AEzeqEMMhyuui7zUGoLJBYIlwx0KX
voBOvU4QO5CX2Qu/yII+y1HhxpMuKhJMB0VKLHUlPF1a/lnePyBml4uXBlqjyJFhE+gu
z4HuozQRUXXa2pHv0Q+DfAt3b1vX7AaDvyStWbL9NpcxOivZBjxXkKvfa9eC0QAJBX3j
CPmbQrcypAZf/yWGUGFMfkf/7uIZEg2oBrBoLhXe18gCl5aIkx0OjizP1IWNEKHt7iD+
rPQMA9okVdaROkAOQiPF/IfNN579UGa0BM6jUbt9G+3CCoBynsTXsR4RfdDc4Bb4K6sX
gVMw==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:in-reply-to:content-disposition
:mime-version:references:message-id:subject:cc:to:from:date:sender
:dkim-signature;
bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=;
fh=UZ/LGnt8Hig7Mx3rVNkYrlx58qfpXmjhdNfiq6UfyOQ=;
b=qNPtzEpE3EeaOWGr1sGc6M2/ikgqRjGL8I4406Ck7DBFg64qNuqk7issROeYEHZoQZ
NU4qZlci8Gqj5jSMqXvpaRooSnExtAydNU4IC9Ksdjyam6Ll/SQvGoAKa9/QeJ87WeTx
rVwVPZGyT1RjVPTgTnSMl/croCMHvf3Y+yxSTr1Cy3fG121r4W4dVp4z0pO6ZUJnnBNz
kDtLZhubSND25MKNqLFmjqXkYVxUB1MaXAcjPfdvglVCRF/2plL0E94HOktVcbJiAz2d
/k9foRQ/k41i8RY12LrD6nfrNpJBlQDkYc25ENgygER57f5BfDSpbQqwfEJwE/DNK4h0
VtBg==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715872920; x=1716477720; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=;
b=WzzCgZ//sxZjoqoZHyiT5GwkHo5/PmXcNrsyQzQAf4vAGy8YO2rAsVXdqXxZhVoCjS
0RnKIersEdywFMNEfzqzA5FeRNEZKp4PJlZHM+IJ8IaDoiJ7xvroPUgKOQ8RAz5K2dzz
J5NH4xPpAfiyq8TeMovJGyCpPb3rGD6bhQPB8pGEtSatKGaAnsHAm55zK01HSbjcwMwh
E40PjPi0GJczMUHhHnQGI99rxusapIU9bgwPZOloXt3dAGYi/z8B04NuMQr1gdM25Xo3
d3rQqY0TGrZ/iczwUgIC0WMOJAYoTwvTuXIzNf3Pihfc3GdlGzFG/6t7NEO0Ju1H4K+H
l+WA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715872920; x=1716477720;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:content-disposition:mime-version
:references:message-id:subject:cc:to:from:date:x-beenthere
:x-gm-message-state:sender:from:to:cc:subject:date:message-id
:reply-to;
bh=xMm5+ccbRXueM3c/+wXZZyx5llQpe/YYSKWHev+O3WI=;
b=TXuHv0/VcwQlLQuQmox1fyKX9VxuIZRvwmgkL5Z+bm1MS/j4vCsc1y82I3B9A/hwR1
hBfcvuafwPP07rilHk+xogOHczd+VFHdYo67lJpSAEZeEeEmdeeIZaMV5JwPE7pV9143
Nbk94Rgfjt2MBNVnFEwoEDHagpemqFUW2lWbfFvxtutfDrjQPmh6vJ2Ua9LY6mkQyJNA
8Avjt4wOD/JrZCFn0A86/OtPlQcyNTil5e+MbQcUpVKJANF9NCzWpnDB4ASr0JNZrNtH
NYVmoytI7scglRcoM2aSEvCMX+NBH0rWy05wkZQKYGEnxcboENH7LBxnHVJ7zZ563ngS
uA7g==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCVX4wAAUUykxDIi43XI99LUQeQJKI360Ik6+BdT1cnlvjHXrY0vCI+Wsb4sENiQOIUbalfV4RZIu4MBVpurCSbhU5XdTqA=
X-Gm-Message-State: AOJu0YwF2eSjxa5MeNN6HHQbEGRVqOIzFUePL1nx0aFkEyJ9rP/93Zad
W+GxUg/GVVGlIgkrRn+Bo8HccvShK/s8931CT+TjePqgm4Mrc8h2
X-Google-Smtp-Source: AGHT+IFRdHZyOzOFXhn1auSZSb8dpsUmymfek1w09HDqLA0x+fG3l92moKISjzDtb2afn3kYpGNYxg==
X-Received: by 2002:a05:6214:3383:b0:6a3:58d1:ff6f with SMTP id 6a1803df08f44-6a358d20220mr46100756d6.57.1715872920342;
Thu, 16 May 2024 08:22:00 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:ad4:4ea5:0:b0:69b:1803:6ad6 with SMTP id 6a1803df08f44-6a15d23a3a8ls134793326d6.0.-pod-prod-06-us;
Thu, 16 May 2024 08:21:59 -0700 (PDT)
X-Received: by 2002:ad4:5fcf:0:b0:69b:7323:1ada with SMTP id 6a1803df08f44-6a16820a493mr3852516d6.11.1715872919227;
Thu, 16 May 2024 08:21:59 -0700 (PDT)
Received: by 2002:a05:620a:40c1:b0:792:a4c6:e0f4 with SMTP id af79cd13be357-792c6fe5026ms85a;
Thu, 16 May 2024 06:28:00 -0700 (PDT)
X-Received: by 2002:a67:ef44:0:b0:486:3434:a30c with SMTP id ada2fe7eead31-4863434a3d9mr719670137.16.1715866079127;
Thu, 16 May 2024 06:27:59 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1715866079; cv=none;
d=google.com; s=arc-20160816;
b=FtxK7yF05VxUskha7ssqyJUN1P8s4ZwCBIXO7jLedspdMIpmQBE5+IEsL26wdXTbnA
eI+ni9Xv5ADeLi0f/cJkuuipzOEc+9F4kol8iyDBn1TU47spfQW6J+1YFivY9P/ygWzQ
Cz3BoiKvkPuUMLI/awEE9TleAc1chyZv+BLDZGB49DCRuF5KPbr/+cCJh6t1f3au7Vao
rvhcEINviKub+XiAnyKdr7c/XDRD+iv9eodlfrJIX3+uatu7/MQHY3jOVQDryXO/mETU
RMu6WjhlZ5GX1GcB2lRhB3fz3wt98fnAhHnvVGgMlbSrAlZPhccD1P7oMMRfH8svycld
3oaA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=in-reply-to:content-disposition:mime-version:references:message-id
:subject:cc:to:from:date:dkim-signature;
bh=CX+rEKGzodS3sO6tOqVpUY9oxboJgzwsR1lk8hCqayA=;
fh=cahZDgTdN45RG3UsKThsxzoXgKY9yWPedXjgzYAIiH8=;
b=a2+iSU+iTdnBC0as/b/DBsxP+G5d99QAfyzQWrqAOXDKHlpfHO/fN4ke9qqOvnX4dT
89P5jj1fardybm9hozbscHDybWYakOGvUVBUiLqtcIspWfxqkUWoOhHhow5TXyIK+CCy
ctQG/BZx+/G35KrHeIZgzu1LveZU8YwBI2cF4DOnakwpDJUcnobEd73zHG2/txb5MPFY
DCb+RjMF/aBlZRXIuqil/Gqb1HJ+pvwBEJLtyAy3TlaHynFWa8Iag6+N4B+GAvzNOF3n
Sli0/BkqNzCgZ/VcQIuDEhZ3967zw6QaL+x1Y6l8u6nDXL6tMaVn88mv5obBzqQBo2VR
6nUA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
Received: from mail.wpsoftware.net ([66.183.0.205])
by gmr-mx.google.com with ESMTP id ada2fe7eead31-4858569b305si94144137.1.2024.05.16.06.27.58
for <bitcoindev@googlegroups.com>;
Thu, 16 May 2024 06:27:58 -0700 (PDT)
Received-SPF: pass (google.com: domain of apoelstra@wpsoftware.net designates 66.183.0.205 as permitted sender) client-ip=66.183.0.205;
Received: from camus (camus-andrew.lan [192.168.0.190])
by mail.wpsoftware.net (Postfix) with ESMTPSA id C530040102;
Thu, 16 May 2024 13:27:56 +0000 (UTC)
Date: Thu, 16 May 2024 13:27:55 +0000
From: Andrew Poelstra <apoelstra@wpsoftware.net>
To: Rama Gan <ganrama@proton.me>
Cc: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
seed phrases
Message-ID: <ZkYJ21cloqyvT93G@camus>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me>
<ZkIYXs7PgbjazVFk@camus>
<GqYxqTBUgHl6yq1UAaOc2O9Ea4-5yKnM-jGZzGaKC19c-k3KcUN_Bo2e7XPYUrNaX3NMJC0tCMudgSl0_l1BCRUz4DIYBR1ecL2ifopzs98=@proton.me>
<ZkNqVZFNBNTq7mAL@camus>
<e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="0W3JydEiLSLDNNv1"
Content-Disposition: inline
In-Reply-To: <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
X-Original-Sender: apoelstra@wpsoftware.net
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@mail.wpsoftware.net header.s=default header.b=HmnlLgio;
spf=pass (google.com: domain of apoelstra@wpsoftware.net designates
66.183.0.205 as permitted sender) smtp.mailfrom=apoelstra@wpsoftware.net;
dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=wpsoftware.net
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)
--0W3JydEiLSLDNNv1
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
On Thu, May 16, 2024 at 07:43:29AM +0000, Rama Gan wrote:
> > But I guess this is explained by the large number of characters produced by
> > the checksum.
>
> For clarity, 45 mins was from a benchmark in real conditions. It includes the
> whole process of copying the seed phrase, checksumming it, generating the random
> share A, checksumming it, deriving both shares B and C, verifying the checksums
> and finally correcting a few mistakes. Recovery took 20 minutes.
>
> The checksum is the second source of inefficiency, the first one being that
> BIP39 isn't compact. GF(29) can encode 128 bits within 7 words, and the checksum
> would cost 7 more words. In comparison, BIP39 low density of information costs
> 10 more words (5 data + 5 checksum). With a compact data format, the entire
> 2-of-3 split process would take less than 30 minutes; and recovery with
> verification would be under 15 minutes. I don't know if it can be optimized
> further, but we're already looking at figures that the general public might find
> acceptable.
>
With BIP39 density you have 24 words (96 characters). With GF29
compaction you could get this down to 14 words (56 characters). But
codex32 does the same in 45 characters, plus a fixed/preprinted HRP.
(And 6 of those 45 are a header which is usually faster to deal with
since you're always dealing with the same characters.)
In your case, since there's no way to get down to 48 characters, I
wouldn't bother trying to compress any further. Either you fit in one
side of a cryptosteel (no) or you fit in two sides of a cryptosteel or
into a tube (yes, even without compression).
And I agree that the existing figures are not bad, especially because
the checksumming (which is the most common and also the least fun) is so
fast.
I think if you were able to squeeze an extra word of header data or
version info, that would be worth doing, but probably not at the expense
of making the user do a re-encoding phase. Which I suspect would be
needed to try to get more information density out of your characters.
> > Very cool. Though you say "single wheel" but you actually need two -- one to
> > get the solving window and one to actually do the recovery. If I understand
> > correctly, the "solving window" is equivalent to a "recovery symbol" in
> > codex32.
>
> The solving window is the is the distance between two shares, and not a Lagrange
> basis (to the best of my knowledge). It can be determined from the same single
> wheel, that already implements subtraction.
>
> [3]: The 2-of-M wheel "Recovery" window shows the distance between two shares:
> https://beta.penlock.io/2ofm-wheel.html
>
Ah, I understand. Looking again at your wheel, I see that it's a
combination slide wheel (for addition/subtraction) and slide chart (for
"recovery windows").
What I'm saying is that you don't need to have extra cutout windows for
the recovery windows. You should be able to just label the characters on
the inner wheel with them, similar to how you have already labeled =
with (1).
> > If so, despite the simple interpretation as "the difference between the
> > shares", this object is secretly a Lagrange polynomial and you can _also_
> > compute it using a slide wheel rather than a full lookup-table volvelle.
>
> I'm not sure if I understand that, but it sounds like I missed an optimization
> opportunity there. Can I ask you to develop that point a little?
>
I don't think this discussion of Lagrange polynomials is relevant
actually. My point is that you don't need the cutout squares, and I
think this is clearer if you think in terms of share index differences
than if you think in terms of Lagrange polynomials.
But. What I'm saying is that if you do the Lagrange polynomial
calculation using the formula from Wikipedia, magically your differences
will appear. They're the same thing, just expressed differently.
--
Andrew Poelstra
Director, Blockstream Research
Email: apoelstra at wpsoftware.net
Web: https://www.wpsoftware.net/andrew
The sun is always shining in space
-Justin Lewis-Webster
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/ZkYJ21cloqyvT93G%40camus.
--0W3JydEiLSLDNNv1
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQEzBAEBCAAdFiEEkPnKPD7Je+ki35VexYjWPOQbl8EFAmZGCdsACgkQxYjWPOQb
l8EHqQf8D7rFLlb9u92OB1SkmeAm5UhZx5Gt7NlJyGg1pfkm3I3P5vrqJNfjmO4v
nMP4bWruJ6DlINYkEAmi034nm+gbkWfzzFB+cW5Adx1iSCXVFepChaMAmY0GCKPh
g9cXf4wNlkDeqy3tX2ZUeXYVuB0DBKwePGHrQXgN/g1zKyAX92OhSggzNsLhzq2r
zv65QBC9o213OlXmeuxmq5AqH6btpWnN1Bdx+O2/TEOTiT9zgZQU21ojfyPOkPbz
Qe4DIlML56ga3IoS75MgDl4ae54eLl+jnZWQ6QvalsjQhvejzpaxRx+04dRnx6ft
/eMPKoDd4jo3MTfcSu/P4hbtXEVHmg==
=fvPO
-----END PGP SIGNATURE-----
--0W3JydEiLSLDNNv1--
|
