path: root/c7/2cd846ec78eaadf34a1c633462c4b1d08910fa

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">--&nbsp; 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 &lt;<=
a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@list=
s.linuxfoundation.org</a>&gt; 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&nbsp;once you rearrange your 12 wor=
ds alphabetically.<br></div><div><br></div><div>However!&nbsp;<br></div>=
</div><div><div><br></div><div>(@vjudeu) Choosing 11 random words and th=
en sorting them alphabetically before assigning&nbsp;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&nbsp;+ 1 checksum. I'm not the best at napkin math, but I=
 think that leaves you with around&nbsp;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--