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
|
Return-Path: <anton@sancoder.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
by lists.linuxfoundation.org (Postfix) with ESMTP id B9F2BC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Jul 2022 23:46:47 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 6A3A640471
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Jul 2022 23:46:47 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 6A3A640471
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key, unprotected) header.d=sancoder.com
header.i=@sancoder.com header.a=rsa-sha256 header.s=fm3 header.b=UaBL/Mgj;
dkim=pass (2048-bit key,
unprotected) header.d=messagingengine.com header.i=@messagingengine.com
header.a=rsa-sha256 header.s=fm3 header.b=MrvXKW8O
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.799
X-Spam-Level:
X-Spam-Status: No, score=-2.799 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001,
RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001,
RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id Yy5AkqRRmFpf
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Jul 2022 23:46:46 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org E8BB3401C2
Received: from out4-smtp.messagingengine.com (out4-smtp.messagingengine.com
[66.111.4.28])
by smtp2.osuosl.org (Postfix) with ESMTPS id E8BB3401C2
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Jul 2022 23:46:45 +0000 (UTC)
Received: from compute2.internal (compute2.nyi.internal [10.202.2.46])
by mailout.nyi.internal (Postfix) with ESMTP id 16D245C00B9
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Jul 2022 19:46:41 -0400 (EDT)
Received: from imap46 ([10.202.2.96])
by compute2.internal (MEProxy); Sat, 09 Jul 2022 19:46:41 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sancoder.com; h=
cc:content-type:date:date:from:from:in-reply-to:in-reply-to
:message-id:mime-version:references:reply-to:sender:subject
:subject:to:to; s=fm3; t=1657410401; x=1657496801; bh=/Khr+1LVOE
AJthJ0VRj31NOZWAuvTa3kBUSKzUDD+yI=; b=UaBL/MgjnJ71+eDwMGwU7qJSUN
6wmyWoXE6zKqBsKUFXOK0cP7/u870LEgamPBt6R4n0DUmZ038yjTDew8pv9CKHqR
EcGe+geOK22hy5fZwlVfyx5/0tuPIgYIU6DwuvrlV69L0xZjBWl5R+KOosDq/VJc
cPTtswy2mSHQctAlz2SVPGEPt9iFzVyYEUz8X9mug6yzM96LV9O4Imbt4aDK2n0t
Uc6OEOKWzHgf4pHDqBBPufIsMECh9jIN9GbBsReq5fRvFXVAeQQth3GHKdtddNG3
THCHyNT9eTSNKtemndB42pybYTciyEglZKpM0pHJaxcF4FBVwPoMoRG+HDjw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=
messagingengine.com; h=cc:content-type:date:date:feedback-id
:feedback-id:from:from:in-reply-to:in-reply-to:message-id
:mime-version:references:reply-to:sender:subject:subject:to:to
:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=
fm3; t=1657410401; x=1657496801; bh=/Khr+1LVOEAJthJ0VRj31NOZWAuv
Ta3kBUSKzUDD+yI=; b=MrvXKW8OkJfYEFMCkUFiGbqoFUWTkYmTfFRjcdaBoalf
N1EKEQz1fPS7AOMIiLVI7eWhNB7j1AQtFJTeIUc6vrgKWVGctZe1dJXLbVmlocyf
lTuBWMXvNjcaUx8eYfqaAFcBaNAWLGFcMy8lz+75zYQeVTz+HbW0IL1AfyzCG5gq
BcqGxNm2ACryfMjxEjRCw0RjP2k96EA+jCNn44KMvtPmRCGk+b0y4ndgZJl1tJ+N
fLS6K2ZkDqiVOWr/mrodKUrDKLxHAwlq/XM+LX7I0GV7W96oCCCVhotohQulBPHu
E4FaS1mD+2zC7McGheZA+jiOnfkFVo/Fs3OSJwf/ZA==
X-ME-Sender: <xms:YBPKYuUzXfSSb6SE4ST3JyVrHbIwsPOcXBbiXG-visDaPd3MMH1DMw>
<xme:YBPKYqnyYH3M23YMVLE5ZtYz1d4GI8Hvvz1_HG7XdgXSuPSSg9nrhpSCJ3iB4rzeG
DlsnpjL99xVsGih>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedvfedrudejtddgvdeiucetufdoteggodetrfdotf
fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen
uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtsegrtd
erreerredtnecuhfhrohhmpedftehnthhonhcuufhhvghvtghhvghnkhhofdcuoegrnhht
ohhnsehsrghntghouggvrhdrtghomheqnecuggftrfgrthhtvghrnhepgfdtieejgfdvhf
fhfefgffeigfeghfekveefvdffvdekuefhveejgfdvffetffdunecuffhomhgrihhnpehl
ihhnuhigfhhouhhnuggrthhiohhnrdhorhhgnecuvehluhhsthgvrhfuihiivgeptdenuc
frrghrrghmpehmrghilhhfrhhomheprghnthhonhesshgrnhgtohguvghrrdgtohhm
X-ME-Proxy: <xmx:YBPKYiaAd7Wx1E45FJX43ARzAdivkyShjTV4PGPIsmVOOy-77frepQ>
<xmx:YBPKYlUg7_xrq2pqirWYAEx81HZMBOQVwHgzQ4z0eDIN5hGW1cOcwg>
<xmx:YBPKYonmfElTJHO4BIG73luhcjitxf8KOw-o4Y6BHrmWj0VwENGaFA>
<xmx:YRPKYkxWqKqwccZQYl4T6Aen9d254R6-R48XV60au3bQO5JtfTLTEQ>
Feedback-ID: i4779463d:Fastmail
Received: by mailuser.nyi.internal (Postfix, from userid 501)
id A0EE32A20075; Sat, 9 Jul 2022 19:46:40 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.7.0-alpha0-720-gbf5afa95ff-fm-20220708.001-gbf5afa95
Mime-Version: 1.0
Message-Id: <bf3b36b1-e999-43bf-88d4-3aab19d10e9d@www.fastmail.com>
In-Reply-To: <CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
References: <3D3BFE9C-CFF3-49FF-840F-063B52C69A42@voskuil.org>
<164256450-0ee6752f92c0be297952fc72b59076df@pmq5v.m5r2.onet>
<CA+XQW1iKVRmEnyP-CGM2Fo4qHi3SQHUfjEmKftDdju-uxHViJg@mail.gmail.com>
<CAH+Axy4X+uQG5Vw0Efiz6AtNyK=++h-jDeZL1ZxpVJus8BVKeA@mail.gmail.com>
<CAJ4-pEA7WJpbExcsgdPWVNuZLrbDDhVYr37g6_6NSf7t41eB4w@mail.gmail.com>
Date: Sat, 09 Jul 2022 16:46:19 -0700
From: "Anton Shevchenko" <anton@sancoder.com>
To: "Alfred Hodler" <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary=d0015dfb91e24b9e844e02c78a424d02
X-Mailman-Approved-At: Sun, 10 Jul 2022 00:01:00 +0000
Subject: Re: [bitcoin-dev] No Order Mnemonic
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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, 09 Jul 2022 23:46:47 -0000
--d0015dfb91e24b9e844e02c78a424d02
Content-Type: text/plain
I would say removing ordering from 12-word seed reduces 25 bits of entropy, not 29. Additional 4 bits come from checksum (12 words encode 132 bits, not 128).
My idea [for developing this project] was to feed its output to some kind of AI story generator (GPT-3 based?) so a user can remember a story, not ordered words. But as others pointed out, having 12 words without order is probably good enough. So at this point there's not much sense of using the proposed encoding. Unless a remembered story has wholes/errors. In this case recovering few words would be easier with unordered encoding. Any thoughts?
-- Anton Shevchenko
On Sat, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-dev wrote:
> Sorting a seed alphabetically reduces entropy by ~29 bits.
>
> A 12-word seed has (12, 12) permutations or 479 million, which is ln(469m) / ln(2) ~= 29 bits of entropy. Sorting removes this entropy entirely, reducing the seed entropy from 128 to 99 bits.
>
> Zac
>
>
> On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>>> What do you do if the "first" word (of 12), happens to be the last word in the list alphabetically?
>>
>> That couldn't happen. If one word is the very last from the wordlist, it would end up at the end of your mnemonic once you rearrange your 12 words alphabetically.
>>
>> However!
>>
>> (@vjudeu) Choosing 11 random words and then sorting them alphabetically before assigning a checksum would reduce entropy considerably. If you think about it, to bruteforce the entire keyspace one would only need to come up with every possible combination of 11 words + 1 checksum. I'm not the best at napkin math, but I think that leaves you with around 10 trillion combinations, which would only take a couple months to exhaust with hardware that can do 1 million guesses per second.
>>
>>
>> James
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--d0015dfb91e24b9e844e02c78a424d02
Content-Type: text/html
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE html><html><head><title></title><style type=3D"text/css">p.Mso=
Normal,p.MsoNoSpacing{margin:0}</style></head><body><div style=3D"font-f=
amily:helvetica, arial, sans-serif;"><div style=3D"font-family:helvetica=
, arial, sans-serif;">I would say removing ordering from 12-word seed re=
duces 25 bits of entropy, not 29. Additional 4 bits come from checksum (=
12 words encode 132 bits, not 128).<br></div><div style=3D"font-family:h=
elvetica, arial, sans-serif;"><br></div><div style=3D"font-family:helvet=
ica, arial, sans-serif;">My idea [for developing this project] was to fe=
ed its output to some kind of AI story generator (GPT-3 based?) so a use=
r can remember a story, not ordered words. But as others pointed out, ha=
ving 12 words without order is probably good enough. So at this point th=
ere's not much sense of using the proposed encoding. Unless a remembered=
story has wholes/errors. In this case recovering few words would be eas=
ier with unordered encoding. Any thoughts?<br></div></div><div style=3D"=
font-family:helvetica, arial, sans-serif;"><br></div><div id=3D"sig12710=
3648"><div class=3D"signature">-- Anton Shevchenko<br></div></div>=
<div style=3D"font-family:helvetica, arial, sans-serif;"><br></div><div =
style=3D"font-family:helvetica, arial, sans-serif;"><br></div><div>On Sa=
t, Jul 9, 2022, at 1:31 PM, Zac Greenwood via bitcoin-dev wrote:<br></di=
v><blockquote type=3D"cite" id=3D"qt" style=3D""><div dir=3D"auto">Sorti=
ng a seed alphabetically reduces entropy by ~29 bits.<br></div><div dir=3D=
"auto"><br></div><div dir=3D"auto">A 12-word seed has (12, 12) permutati=
ons or 479 million, which is ln(469m) / ln(2) ~=3D 29 bits of entropy. S=
orting removes this entropy entirely, reducing the seed entropy from 128=
to 99 bits.<br></div><div dir=3D"auto"><br></div><div dir=3D"auto">Zac<=
br></div><div><div><br></div><div class=3D"qt-gmail_quote"><div dir=3D"l=
tr" class=3D"qt-gmail_attr"><br></div><div dir=3D"ltr" class=3D"qt-gmail=
_attr">On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <<=
a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@list=
s.linuxfoundation.org</a>> wrote:<br></div><blockquote class=3D"qt-gm=
ail_quote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;ma=
rgin-left:0.8ex;border-left-width:1px;border-left-style:solid;padding-le=
ft:1ex;border-left-color:rgb(204, 204, 204);"><div dir=3D"ltr"><div dir=3D=
"ltr"><br></div><div class=3D"qt-gmail_quote"><blockquote class=3D"qt-gm=
ail_quote" style=3D"margin-top:0px;margin-right:0px;margin-bottom:0px;ma=
rgin-left:0.8ex;border-left-width:1px;border-left-style:solid;padding-le=
ft:1ex;border-left-color:rgb(204, 204, 204);"><div dir=3D"auto">What do =
you do if the "first" word (of 12), happens to be the last word in the l=
ist alphabetically?<br></div></blockquote><div><br></div><div><div>That =
couldn't happen. If one word is the very last from the wordlist, it woul=
d end up at the end of your mnemonic once you rearrange your 12 wor=
ds alphabetically.<br></div><div><br></div><div>However! <br></div>=
</div><div><div><br></div><div>(@vjudeu) Choosing 11 random words and th=
en sorting them alphabetically before assigning a checksum would re=
duce entropy considerably. If you think about it, to bruteforce the enti=
re keyspace one would only need to come up with every possible combinati=
on of 11 words + 1 checksum. I'm not the best at napkin math, but I=
think that leaves you with around 10 trillion combinations, which =
would only take a couple months to exhaust with hardware that can do 1 m=
illion guesses per second.<br></div></div></div></div><div dir=3D"ltr"><=
div class=3D"qt-gmail_quote"><div><br></div><div><br></div><div>James<br=
></div></div></div><div>_______________________________________________<=
br></div><div> bitcoin-dev mailing list<br></div><div> <a href=3D"mailto=
:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">bitcoin-dev@li=
sts.linuxfoundation.org</a><br></div><div> <a href=3D"https://lists.linu=
xfoundation.org/mailman/listinfo/bitcoin-dev" rel=3D"noreferrer" target=3D=
"_blank">https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<=
/a><br></div></blockquote></div></div><div>_____________________________=
__________________<br></div><div>bitcoin-dev mailing list<br></div><div>=
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lis=
ts.linuxfoundation.org</a><br></div><div><a href=3D"https://lists.linuxf=
oundation.org/mailman/listinfo/bitcoin-dev">https://lists.linuxfoundatio=
n.org/mailman/listinfo/bitcoin-dev</a><br></div><div><br></div></blockqu=
ote><div style=3D"font-family:helvetica, arial, sans-serif;"><br></div><=
/body></html>
--d0015dfb91e24b9e844e02c78a424d02--
|