Re: [bitcoin-dev] No Order Mnemonic

From: Erik Aronesty <erik@q32•com>
To: Anton Shevchenko <anton@sancoder•com>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] No Order Mnemonic
Date: Mon, 11 Jul 2022 09:18:14 -0400	[thread overview]
Message-ID: <CAJowKgLRMyXQ27-m9-ud9F8Qu=6dkcfJHjoxLJh4LKyU8Nf9pw@mail.gmail.com> (raw)
In-Reply-To: <CAJowKgJq23W3yq91pF+xm6CMjOy+tXz=zxkMVRPqCY_zWsBdiQ@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 3430 bytes --]

Sorry, I totally forgot the checksum.

You can take my ops-per-second and multiply it by about 16 (because of the
4 check bits), making a delete + two swaps or 4 swaps, etc. still pretty
reasonable.

On Mon, Jul 11, 2022 at 9:11 AM Erik Aronesty <erik@q32•com> wrote:

> 1. You can swap two positions, and then your recovery algorithm can
> brute-force the result by trying all 132 possible swaps.
> 2. You can make a single deletion and only have to brute 2048
> 3. You can keep doing these, being aware that it becomes geometrically
> more difficult each time (deletion + swap = 270k ops)
> 4. A home PC can make 20k secpk256 operations per second per core, so try
> to keep your number under a few million ops and it's still a decent UX
> (under a minute)
>
>
> On Sat, Jul 9, 2022 at 8:01 PM Anton Shevchenko via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> 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
>>
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>

[-- Attachment #2: Type: text/html, Size: 6152 bytes --]