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
|
Delivery-date: Thu, 16 May 2024 08:22:01 -0700
Received: from mail-oo1-f60.google.com ([209.85.161.60])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBAABBEOJTCZAMGQEZVEJGWI@googlegroups.com>)
id 1s7cvh-0003hq-8Z
for bitcoindev@gnusha.org; Thu, 16 May 2024 08:22:01 -0700
Received: by mail-oo1-f60.google.com with SMTP id 006d021491bc7-5aa3282100bsf11644887eaf.2
for <bitcoindev@gnusha.org>; Thu, 16 May 2024 08:22:00 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1715872915; cv=pass;
d=google.com; s=arc-20160816;
b=kzRsUNwL9rtl9vJI1uDwBrMg91i9+5ZeCG/aZRYkEibJo6XLEKWAnRznrNnlNrBcxN
q0WBXEckuRsaDL9yTSpqU6mo1P/An3SIQqajNLfvsulaEFTTuGBL/4/HaSNboSrKK5p3
5L/8KfNaZSKb8XuI6iPIEyPlpUPSsnWbHSnua0Fmk9mIJ2Um/0Zv+K09x2jpEHxv/k05
64TS5lkh1iMZlBHmyQXSyErlbouW4kU2CQGBcjWPocQNyW0/h1WlePAIH5Oq59dCRVhn
k7mG5z0fmjeBud1rAEcMopo0YHJnXTHXPUjVYgGrVlA/CBIznQ82RdJqDso8MGjyvVP2
4+Lw==
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:reply-to:mime-version:feedback-id
:references:in-reply-to:message-id:subject:cc:from:to:date
:dkim-signature;
bh=XdJzM5Iq51iZmcvpOPFbiRjuCVNUrJBXjhiuegfhoUc=;
fh=R1P5fZT/l600POvZYzxVaOoWzcocz3EFeAN4nvRHgNc=;
b=JH412MoowgtLh+lDJFUlNhADKUZryGydDrVB1SIicao1xlcHiVGRS9jrIPWAOozHjI
NZAgz52oaPpsUpt27gTL+SWtJ5KU5QLNKAc/SoIsH8u6Rc4MSkMN2Fap4cg+aVpuZ9vX
xJD36F+n1aEcqC2YGMUS6142qW7/83ZbIT9PMGubm6k/O5ApRHUack5OB665aiW48AnC
NnzF1fXcPIVA38wx4lCsw2M0ZBKrfKUyK/gQECMTDLgSOPGwHO5OUIf+/zmmX7TypMtV
d0PlcyZP31S73s6EtY0V2XjrohzY6KCmZD3KQKI9aMqcQ8/3g/o8suzY+BNoyVVVhgha
glQQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=7yc4puoanzc73c7hlibfdlziku.protonmail header.b="d/XLHUhI";
spf=pass (google.com: domain of ganrama@proton.me designates 185.70.43.19 as permitted sender) smtp.mailfrom=ganrama@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715872915; x=1716477715; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:cc:from:to
:date:from:to:cc:subject:date:message-id:reply-to;
bh=XdJzM5Iq51iZmcvpOPFbiRjuCVNUrJBXjhiuegfhoUc=;
b=eVMkHX4QqdRTZm8d0JW1DGttPgI0fpQdxUpaiW65UhH+9uZOg0nZpheHm81PZBB1GT
WdSaYHObFR/kH630ZRJvE2PhjwE9yXHrLpBIuGKmcNc4/0nvJBpzA9HRjR0/LNYyJ7rA
fbVc/EeEQi+7TjCQs0yLAwmWS5L9dDmXHveq58LHVcxcB8t0ERshOq5DxLHGQSIIeAZG
vN4lh+L1P2kOeUBdYAz5T9T6we3WZcvx5PLSGbc+QGwMiFedXOeci1w5y3ConXuRQMLs
u6XjzjXY4seWdj2WcjY/2wDnXWC7BiYVjDpXr2R9dh7da3G5XxsJeIEpy5zbUsaNHhl4
MYcQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715872915; x=1716477715;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:cc:from:to
:date:x-beenthere:x-gm-message-state:from:to:cc:subject:date
:message-id:reply-to;
bh=XdJzM5Iq51iZmcvpOPFbiRjuCVNUrJBXjhiuegfhoUc=;
b=hkjE84LvdrbAebX624QZWtkI+M6U8Ec3NLB2l0HLEhy5jGuM01/5Y/snFR9hAYwAL+
2t6H3ycV9vGoy9aPj9lc+9pXe3igk9VjjBDVcrCBzvi6hqARuNspGaK6aFt2WY5R6XOF
2OZkDSaWueu/izP3QHgo7z++pbWS7zAipmFEORKsOl84UUuanbk7jNBzrn8rmgwCrptU
NIo2QlYHw2KxYQqVZAhTW98ekUXIaUkIu7A/jxaE20SJAXhZBACwQ1N//4uqCGDMWujZ
GQh7OnL8zWviZRxNxxTnuH/hKBoBwJ70UnjBqFnrL1Ziu3wTQle6rvBMG+CPgZXq62iu
LThw==
X-Forwarded-Encrypted: i=2; AJvYcCX4dWKhyiDFtllB9NaCaCHHbM15xi73sI9N+/y3YPyLyXyxVRoah7GQm6Du6UuVX+8qkVN75RVpK2BlTEMDixP1hbahr+8=
X-Gm-Message-State: AOJu0Yy2w1g5hx43/s5L9hHb8m2I5DXjhXlhQWXnTSp0ikKkreYtqYok
xoBr68LRgsrQY+bIM7bQZeZ7Vky+GJB4KQDoUUTUJ1o0jo+EIwnz
X-Google-Smtp-Source: AGHT+IFBmsP4dt1m6bpZYWLH35h62s3tQUOtp5tMQIruxYX+RhnU/Ish+5L7o62ziJQ7Gmx/2PrIKw==
X-Received: by 2002:a05:6358:904d:b0:186:1c42:7240 with SMTP id e5c5f4694b2df-193bb51a4efmr2121492755d.12.1715872914766;
Thu, 16 May 2024 08:21:54 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:ac8:7e95:0:b0:43b:86e:665c with SMTP id d75a77b69052e-43decf2915cls6652561cf.0.-pod-prod-09-us;
Thu, 16 May 2024 08:21:53 -0700 (PDT)
X-Received: by 2002:a05:622a:2998:b0:43e:e6e:21c0 with SMTP id d75a77b69052e-43e0e6e23e4mr9146861cf.7.1715872913401;
Thu, 16 May 2024 08:21:53 -0700 (PDT)
Received: by 2002:a05:620a:4409:b0:790:efaf:f1f8 with SMTP id af79cd13be357-792bcb87de5ms85a;
Thu, 16 May 2024 00:43:37 -0700 (PDT)
X-Received: by 2002:a2e:a417:0:b0:2d8:713c:8313 with SMTP id 38308e7fff4ca-2e5205ec6dbmr112918061fa.45.1715845415560;
Thu, 16 May 2024 00:43:35 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1715845415; cv=none;
d=google.com; s=arc-20160816;
b=DcflMOdA8xp0CdI66+aavpkjtfxlTEcvArFlzrURAxnZ4yK5ki3Ga12ke1TZzEmWJs
vPWUiJ/DcL/V9JhbSUBCgT/k2IJpX9LQUYsNuZtTm6AgZ98vZJc4j+CRETq5+fuMcbgu
6hyX8Y13mlhNdy8ygrxRD6+9IBSQ+9KjVslJmK53nv+u7/VTyMI/ZYd/Wk/Xst70iUHQ
G4A4SqZw7d62vmnVtrV7GF4QCaQe9xUlmHhBmS3ScGDkoydcGzB/KXPMauDZlZ2TV7ac
/xRhGEutw/7r39n1vZIvodzSusfmKQp05QhDa3f4B3ApIfDNsoqK6ir/FMvUj6KSwaQC
omUA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816;
h=content-transfer-encoding:mime-version:feedback-id:references
:in-reply-to:message-id:subject:cc:from:to:date:dkim-signature;
bh=4+Zh0yuiywUTg3A0lvD9hVXB+1J39fl+s0n5ILGarL4=;
fh=OfJO9UbfJJMWyNfR6ZYY8yzp2YD4Z+A+tUdE5xF3F34=;
b=JMaR/TYKGlNwm9q3JjguI72X32qxklBBS+A6D7ufVqS6TsVXsfn+CKwz6ifMGJ24yf
KrHmSNMEPGkjm4nqTXx6AKIAEqXnu7kJ/ctoTozOKOI4cx+DCmpkTuOcJZBEg6tt9J6X
izlBePBcW7qrsCu3Nh74jkuyBxr8kXVwamrGExZeDVXmuCVddPa5Yex5C82YVyYbn0TU
ymGJpXZF14esJWHs9U7Sr3zsjK6PYCtZz5ycZ4D4++NMqff9j/PVCbT02XcCX7Z5i763
v1o1LxTXtioTDpjeL2uJ3Aja1RRn5/p7MNjnSCBIe/C5Ybvj2vNzsylS9EIb9OLSq8NH
GW9w==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=7yc4puoanzc73c7hlibfdlziku.protonmail header.b="d/XLHUhI";
spf=pass (google.com: domain of ganrama@proton.me designates 185.70.43.19 as permitted sender) smtp.mailfrom=ganrama@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
Received: from mail-4319.protonmail.ch (mail-4319.protonmail.ch. [185.70.43.19])
by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-2e4d0bbe1bfsi4259331fa.2.2024.05.16.00.43.35
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Thu, 16 May 2024 00:43:35 -0700 (PDT)
Received-SPF: pass (google.com: domain of ganrama@proton.me designates 185.70.43.19 as permitted sender) client-ip=185.70.43.19;
Date: Thu, 16 May 2024 07:43:29 +0000
To: Andrew Poelstra <apoelstra@wpsoftware.net>
From: "'Rama Gan' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: "bitcoindev@googlegroups.com" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Penlock, a paper-computer for secret-splitting BIP39
seed phrases
Message-ID: <e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y=@proton.me>
In-Reply-To: <ZkNqVZFNBNTq7mAL@camus>
References: <9bt6npqSdpuYOcaDySZDvBOwXVq_v70FBnIseMT6AXNZ4V9HylyubEaGU0S8K5TMckXTcUqQIv-FN-QLIZjj8hJbzfB9ja9S8gxKTaQ2FfM=@proton.me> <ZkIYXs7PgbjazVFk@camus> <GqYxqTBUgHl6yq1UAaOc2O9Ea4-5yKnM-jGZzGaKC19c-k3KcUN_Bo2e7XPYUrNaX3NMJC0tCMudgSl0_l1BCRUz4DIYBR1ecL2ifopzs98=@proton.me> <ZkNqVZFNBNTq7mAL@camus>
Feedback-ID: 79991369:user:proton
X-Pm-Message-ID: 510855c8d324ad192a00850138185ab8d5eae9b9
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Original-Sender: ganrama@proton.me
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@proton.me header.s=7yc4puoanzc73c7hlibfdlziku.protonmail
header.b="d/XLHUhI"; spf=pass (google.com: domain of ganrama@proton.me
designates 185.70.43.19 as permitted sender) smtp.mailfrom=ganrama@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
X-Original-From: Rama Gan <ganrama@proton.me>
Reply-To: Rama Gan <ganrama@proton.me>
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: -1.0 (-)
I don't know if you have seen my previous email describing how 2-of-M is
implemented in Penlock? I sent two mails the same day, I suspect that the second
one went unnoticed; My reply below could be confusing without that piece of
context.
> FYI even in GF(P), you can do multiplication and division using slide wheels.
> I'm not sure if doing so would interfere with your other multipurpose volvelle
> constructions. (Every nonzero number in your field is 2^n for some n, so you
> can do multiplication/division by adding in the exponent.)
>
> The resulting slide wheel would not have a natural ordering.
I used this for the (K>2)-of-M case. In fact, by mapping the recovery symbols to
the right values, it is possible to achieve natural ordering (which is indeed
faster to compute). For Penlock, I used numbers instead of symbols and the
mapping `n -> (2^n) % 29`.
[1]: Recovery "symbols" mapping:
https://github.com/penlock-io/beta.penlock.io/blob/master/sdk/data/penlock-bip39.js#L92
[2]: "fusion" is done by summing the exponents using the big wheel:
https://beta.penlock.io/kofm-wheels.html
> Interesting that the splitting and recovery processes take such a long time.
> 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.
> 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
> 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?
-- Rama Gan
--
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/e1V4sbaLiJ4XGzEEEnr7lg2O1h3OxQabGcSoeTmDeo8bLVgIGhz9HHo3qtGQIVi-5aoU4xc2Kdj_qcC8Rt_xtFvQDahhXcIg4V0raMJxh2Y%3D%40proton.me.
|
