* [bitcoin-dev] No Order Mnemonic
@ 2022-07-07 14:33 Anton Shevchenko
2022-07-07 17:36 ` Bram Cohen
0 siblings, 1 reply; 14+ messages in thread
From: Anton Shevchenko @ 2022-07-07 14:33 UTC (permalink / raw)
To: bitcoin-dev
Hello,
I am new to this list, sorry if it's been discussed earlier.
I made a python implementation for a different mnemonic encoding. The encoding requires user to remember words but not the order of those words.
The code is open (MIT license) at https://github.com/sancoder/noomnem
-- Anton Shevchenko
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-07 14:33 [bitcoin-dev] No Order Mnemonic Anton Shevchenko
@ 2022-07-07 17:36 ` Bram Cohen
2022-07-07 17:52 ` Pavol Rusnak
0 siblings, 1 reply; 14+ messages in thread
From: Bram Cohen @ 2022-07-07 17:36 UTC (permalink / raw)
To: Anton Shevchenko, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 672 bytes --]
On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> I made a python implementation for a different mnemonic encoding. The
> encoding requires user to remember words but not the order of those words.
> The code is open (MIT license) at https://github.com/sancoder/noomnem
Thanks Anton. There's an interesting mathematical question of whether it's
possible to make a code like this which always uses the BIP-39 words for
the same key as part of its encoding, basically adding a few words as error
correction in case the order is lost or confused. If the BIP-39 contains a
duplicate you can add an extra word.
[-- Attachment #2: Type: text/html, Size: 1059 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-07 17:36 ` Bram Cohen
@ 2022-07-07 17:52 ` Pavol Rusnak
2022-07-07 17:58 ` Anton Shevchenko
2022-07-08 1:47 ` Bram Cohen
0 siblings, 2 replies; 14+ messages in thread
From: Pavol Rusnak @ 2022-07-07 17:52 UTC (permalink / raw)
To: Bitcoin Protocol Discussion, Bram Cohen
[-- Attachment #1: Type: text/plain, Size: 1272 bytes --]
There is. Just encode the index of permutation used to scramble the
otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3
words should be enough.
Repetitions make this more difficult, though.
On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> I made a python implementation for a different mnemonic encoding. The
>> encoding requires user to remember words but not the order of those words.
>> The code is open (MIT license) at https://github.com/sancoder/noomnem
>
>
> Thanks Anton. There's an interesting mathematical question of whether it's
> possible to make a code like this which always uses the BIP-39 words for
> the same key as part of its encoding, basically adding a few words as error
> correction in case the order is lost or confused. If the BIP-39 contains a
> duplicate you can add an extra word.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--
Best Regards / S pozdravom,
Pavol "stick" Rusnak
Co-Founder, SatoshiLabs
[-- Attachment #2: Type: text/html, Size: 2491 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-07 17:52 ` Pavol Rusnak
@ 2022-07-07 17:58 ` Anton Shevchenko
2022-07-08 1:47 ` Bram Cohen
1 sibling, 0 replies; 14+ messages in thread
From: Anton Shevchenko @ 2022-07-07 17:58 UTC (permalink / raw)
To: Pavol Rusnak, Alfred Hodler, Bram Cohen
[-- Attachment #1: Type: text/plain, Size: 1445 bytes --]
But this will require user to distinguish 12 words from error correcting words. Which is another hassle.
On Thu, Jul 7, 2022, at 10:52 AM, Pavol Rusnak wrote:
> There is. Just encode the index of permutation used to scramble the otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3 words should be enough.
>
> Repetitions make this more difficult, though.
>
> On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>>> I made a python implementation for a different mnemonic encoding. The encoding requires user to remember words but not the order of those words.
>>> The code is open (MIT license) at https://github.com/sancoder/noomnem
>>
>> Thanks Anton. There's an interesting mathematical question of whether it's possible to make a code like this which always uses the BIP-39 words for the same key as part of its encoding, basically adding a few words as error correction in case the order is lost or confused. If the BIP-39 contains a duplicate you can add an extra word.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> --
>
> Best Regards / S pozdravom,
>
> Pavol "stick" Rusnak
> Co-Founder, SatoshiLabs
[-- Attachment #2: Type: text/html, Size: 3225 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-07 17:52 ` Pavol Rusnak
2022-07-07 17:58 ` Anton Shevchenko
@ 2022-07-08 1:47 ` Bram Cohen
2022-07-08 2:19 ` Eric Voskuil
1 sibling, 1 reply; 14+ messages in thread
From: Bram Cohen @ 2022-07-08 1:47 UTC (permalink / raw)
To: Pavol Rusnak; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1591 bytes --]
Part of the rules of my challenge is that the 'new' words need to be in the
same pool as the 'old' words, so any ordering is okay. Without that
requirement it's mathematically very straightforward.
On Thu, Jul 7, 2022 at 10:52 AM Pavol Rusnak <stick@satoshilabs•com> wrote:
> There is. Just encode the index of permutation used to scramble the
> otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3
> words should be enough.
>
> Repetitions make this more difficult, though.
>
> On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
>> bitcoin-dev@lists•linuxfoundation.org> wrote:
>>
>>> I made a python implementation for a different mnemonic encoding. The
>>> encoding requires user to remember words but not the order of those words.
>>> The code is open (MIT license) at https://github.com/sancoder/noomnem
>>
>>
>> Thanks Anton. There's an interesting mathematical question of whether
>> it's possible to make a code like this which always uses the BIP-39 words
>> for the same key as part of its encoding, basically adding a few words as
>> error correction in case the order is lost or confused. If the BIP-39
>> contains a duplicate you can add an extra word.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists•linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
> --
> Best Regards / S pozdravom,
>
> Pavol "stick" Rusnak
> Co-Founder, SatoshiLabs
>
[-- Attachment #2: Type: text/html, Size: 2943 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-08 1:47 ` Bram Cohen
@ 2022-07-08 2:19 ` Eric Voskuil
2022-07-08 4:35 ` vjudeu
0 siblings, 1 reply; 14+ messages in thread
From: Eric Voskuil @ 2022-07-08 2:19 UTC (permalink / raw)
To: Bram Cohen, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 2168 bytes --]
Without a performance requirement there is no reason you can’t store the BIP39 words in any order you want. So it’s certainly possible, just brute force the recovery. If you have less than a second vs. a few days then it’s a different question.
e
> On Jul 7, 2022, at 18:48, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> Part of the rules of my challenge is that the 'new' words need to be in the same pool as the 'old' words, so any ordering is okay. Without that requirement it's mathematically very straightforward.
>
>> On Thu, Jul 7, 2022 at 10:52 AM Pavol Rusnak <stick@satoshilabs•com> wrote:
>> There is. Just encode the index of permutation used to scramble the otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3 words should be enough.
>>
>> Repetitions make this more difficult, though.
>>
>>> On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>>>> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
>>>
>>>> I made a python implementation for a different mnemonic encoding. The encoding requires user to remember words but not the order of those words.
>>>> The code is open (MIT license) at https://github.com/sancoder/noomnem
>>>
>>> Thanks Anton. There's an interesting mathematical question of whether it's possible to make a code like this which always uses the BIP-39 words for the same key as part of its encoding, basically adding a few words as error correction in case the order is lost or confused. If the BIP-39 contains a duplicate you can add an extra word.
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists•linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>> --
>> Best Regards / S pozdravom,
>>
>> Pavol "stick" Rusnak
>> Co-Founder, SatoshiLabs
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[-- Attachment #2: Type: text/html, Size: 3839 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-08 2:19 ` Eric Voskuil
@ 2022-07-08 4:35 ` vjudeu
2022-07-08 9:12 ` Paul Sztorc
0 siblings, 1 reply; 14+ messages in thread
From: vjudeu @ 2022-07-08 4:35 UTC (permalink / raw)
To: Eric Voskuil <eric@voskuil•org>,
Bitcoin Protocol Discussion, Bram Cohen,
Bitcoin Protocol Discussion
Isn't it enough to just generate a seed in the same way as today, then sort the words alphabetically, and then use that as a seed? I know, the last word is a checksum, but there are only 2048 words, so it is not a big deal to get any checksum we want. If that is insecure, because of lower possible combinations, then it is always possible to increase the number of words to compensate that.
On 2022-07-08 04:27:21 user Eric Voskuil via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
Without a performance requirement there is no reason you can’t store the BIP39 words in any order you want. So it’s certainly possible, just brute force the recovery. If you have less than a second vs. a few days then it’s a different question.
e
On Jul 7, 2022, at 18:48, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
Part of the rules of my challenge is that the 'new' words need to be in the same pool as the 'old' words, so any ordering is okay. Without that requirement it's mathematically very straightforward.
On Thu, Jul 7, 2022 at 10:52 AM Pavol Rusnak <stick@satoshilabs•com> wrote:
There is. Just encode the index of permutation used to scramble the otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3 words should be enough.
Repetitions make this more difficult, though.
On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote:
I made a python implementation for a different mnemonic encoding. The encoding requires user to remember words but not the order of those words.
The code is open (MIT license) at https://github.com/sancoder/noomnem
Thanks Anton. There's an interesting mathematical question of whether it's possible to make a code like this which always uses the BIP-39 words for the same key as part of its encoding, basically adding a few words as error correction in case the order is lost or confused. If the BIP-39 contains a duplicate you can add an extra word.
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists•linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-08 4:35 ` vjudeu
@ 2022-07-08 9:12 ` Paul Sztorc
2022-07-08 14:08 ` James MacWhyte
0 siblings, 1 reply; 14+ messages in thread
From: Paul Sztorc @ 2022-07-08 9:12 UTC (permalink / raw)
To: vjudeu, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3901 bytes --]
What do you do if the "first" word (of 12), happens to be the last word in
the list alphabetically? So that seems like a dead end.
Since users are never expected to memorize the "whole list" (of 2048 words)
in any case, it seems that the smarter thing to do (if this "order"
criterion is desirable) may have been to just make the whole list 12x
longer and cut it into 12 sections. Each of the 12 slots would have 2048
distinct words. Then the computer would handle the order; the user could
neglect it.
I can guess why people weren't particularly interested in this: words
always have to be written down in some order or another. Even if you write
them down in a 3x4 grid, there are very few combinations needed to guess
the one true ordering. I wonder how obscure the words would have to be, by
the 12th list of 2048? But still it might be fun - the 4th word might
always be a nautical word, the 5th word a farm word, etc. And no one would
confuse it with a bip39 phrase -- in fact since they are just lists of
integers 1 to 2048, it would be pretty easy to make them interoperable.
Very easy but perhaps still not worth doing.
Paul
On Fri, Jul 8, 2022, 4:48 AM vjudeu via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:
> Isn't it enough to just generate a seed in the same way as today, then
> sort the words alphabetically, and then use that as a seed? I know, the
> last word is a checksum, but there are only 2048 words, so it is not a big
> deal to get any checksum we want. If that is insecure, because of lower
> possible combinations, then it is always possible to increase the number of
> words to compensate that.
>
>
> On 2022-07-08 04:27:21 user Eric Voskuil via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>
> Without a performance requirement there is no reason you can’t store the
> BIP39 words in any order you want. So it’s certainly possible, just brute
> force the recovery. If you have less than a second vs. a few days then it’s
> a different question.
>
>
> e
>
>
> On Jul 7, 2022, at 18:48, Bram Cohen via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
> Part of the rules of my challenge is that the 'new' words need to be in
> the same pool as the 'old' words, so any ordering is okay. Without that
> requirement it's mathematically very straightforward.
>
>
> On Thu, Jul 7, 2022 at 10:52 AM Pavol Rusnak <stick@satoshilabs•com>
> wrote:
> There is. Just encode the index of permutation used to scramble the
> otherwise sorted list. For 12 words you need to store 12! = ~32 bits so 3
> words should be enough.
>
>
> Repetitions make this more difficult, though.
>
>
> On Thu 7. 7. 2022 at 19:41, Bram Cohen via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
> On Thu, Jul 7, 2022 at 7:43 AM Anton Shevchenko via bitcoin-dev <
> bitcoin-dev@lists•linuxfoundation.org> wrote:
> I made a python implementation for a different mnemonic encoding. The
> encoding requires user to remember words but not the order of those words.
> The code is open (MIT license) at https://github.com/sancoder/noomnem
>
>
>
> Thanks Anton. There's an interesting mathematical question of whether it's
> possible to make a code like this which always uses the BIP-39 words for
> the same key as part of its encoding, basically adding a few words as error
> correction in case the order is lost or confused. If the BIP-39 contains a
> duplicate you can add an extra word.
> _______________________________________________
> 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: 5378 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-08 9:12 ` Paul Sztorc
@ 2022-07-08 14:08 ` James MacWhyte
2022-07-09 20:31 ` Zac Greenwood
0 siblings, 1 reply; 14+ messages in thread
From: James MacWhyte @ 2022-07-08 14:08 UTC (permalink / raw)
To: Paul Sztorc, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 773 bytes --]
> 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
[-- Attachment #2: Type: text/html, Size: 1096 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-08 14:08 ` James MacWhyte
@ 2022-07-09 20:31 ` Zac Greenwood
2022-07-09 22:21 ` James MacWhyte
2022-07-09 23:46 ` Anton Shevchenko
0 siblings, 2 replies; 14+ messages in thread
From: Zac Greenwood @ 2022-07-09 20:31 UTC (permalink / raw)
To: Bitcoin Protocol Discussion, James MacWhyte
[-- Attachment #1: Type: text/plain, Size: 1359 bytes --]
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
>
[-- Attachment #2: Type: text/html, Size: 2433 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-09 20:31 ` Zac Greenwood
@ 2022-07-09 22:21 ` James MacWhyte
2022-07-09 23:46 ` Anton Shevchenko
1 sibling, 0 replies; 14+ messages in thread
From: James MacWhyte @ 2022-07-09 22:21 UTC (permalink / raw)
To: Zac Greenwood; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1727 bytes --]
Thanks, Zac!
I indeed did get the napkin math very wrong. I now get around 10^30 total
possible phrases, which would take an impossibly long time to brute force.
So, it is less entropy but probably still sufficient for low-stakes usage.
James
On Sat, Jul 9, 2022 at 10:31 PM Zac Greenwood <zachgrw@gmail•com> 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
>>
>
[-- Attachment #2: Type: text/html, Size: 3122 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-09 20:31 ` Zac Greenwood
2022-07-09 22:21 ` James MacWhyte
@ 2022-07-09 23:46 ` Anton Shevchenko
2022-07-11 13:11 ` Erik Aronesty
1 sibling, 1 reply; 14+ messages in thread
From: Anton Shevchenko @ 2022-07-09 23:46 UTC (permalink / raw)
To: Alfred Hodler
[-- Attachment #1: Type: text/plain, Size: 2260 bytes --]
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
>
[-- Attachment #2: Type: text/html, Size: 4541 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-09 23:46 ` Anton Shevchenko
@ 2022-07-11 13:11 ` Erik Aronesty
2022-07-11 13:18 ` Erik Aronesty
0 siblings, 1 reply; 14+ messages in thread
From: Erik Aronesty @ 2022-07-11 13:11 UTC (permalink / raw)
To: Anton Shevchenko, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3068 bytes --]
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: 5468 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] No Order Mnemonic
2022-07-11 13:11 ` Erik Aronesty
@ 2022-07-11 13:18 ` Erik Aronesty
0 siblings, 0 replies; 14+ messages in thread
From: Erik Aronesty @ 2022-07-11 13:18 UTC (permalink / raw)
To: Anton Shevchenko, Bitcoin Protocol Discussion
[-- 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 --]
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2022-07-11 13:18 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-07-07 14:33 [bitcoin-dev] No Order Mnemonic Anton Shevchenko
2022-07-07 17:36 ` Bram Cohen
2022-07-07 17:52 ` Pavol Rusnak
2022-07-07 17:58 ` Anton Shevchenko
2022-07-08 1:47 ` Bram Cohen
2022-07-08 2:19 ` Eric Voskuil
2022-07-08 4:35 ` vjudeu
2022-07-08 9:12 ` Paul Sztorc
2022-07-08 14:08 ` James MacWhyte
2022-07-09 20:31 ` Zac Greenwood
2022-07-09 22:21 ` James MacWhyte
2022-07-09 23:46 ` Anton Shevchenko
2022-07-11 13:11 ` Erik Aronesty
2022-07-11 13:18 ` Erik Aronesty
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox