[Open Source] Coin Flipped Seed (coin flip, dice roll, rubik's cube mixing)

[BlackHatCoiner]

Coin Flipped Seed

This program may be considered as "useless" by some people. In a way, it doesn't provide anything different rather than a strong proof of the randomness. I got inspired by MrFreeDragon on his visual private key generator. Flipping a coin 256 times is a little too much, but the problem was that you could only create one address at a time. Instead of tossing a coin for one address, it'd better to do it for the seed's entropy. Thus, you can now derive a nearly unlimited number of addresses by only tossing a coin 128 times. Without having to worry about RNGs and their strength.
[Concern about RNG]

Introducing: Coin Flipped Seed.



Release (v0.3) • Source code

By default, I've set to derive the first 20 addresses and at the moment you can only create a mnemonic that is twelve words long.

[LoyceV]

I've often thought about creating my own seed from dice or coins, but never done it. I tried to find a list with 2048 seed words with binary numbers, but found Learnmeabitcoin.com instead.
If I'd really use this, I would like to use more than one piece of software to check if it gives the same results. The seed words I can check manually, but not the address derivation. I'd want to check this for 2 reasons:

• Can a different piece of software recover the same private keys?
• Am I sure this software doesn't just give me pre-created compromised private keys that aren't derived from my seed?

So far, all my tests with recovering private keys worked as expected. It's comforting to know my thorough checks weren't needed (but I'll keep doing it anyway).

The usual disclaimer: don't use any online site to create private keys for storing real coins!

[baro77]

Nice, thanks for sharing.. but why not using Bip39Tool? https://iancoleman.io/bip39/

- if you tick "Show entropy details" you can input your own entropy in many ways
- you can choose many derivation paths
- QR generation
- fully auditable (you can download sources from github and use it offline after compiling)
- hashed releases: for each new version, the author publishes the compiled page hash on twitter (so a different medium, an attacker has compromise two different platforms accounts to forge a fake release)

I don't want to devalue your software but I have thought it's important for you (and us ) to know about others as well

best regards

EDIT
LoyceV stressed the importance of double checking with different softwares ....Got it... so my two cents for a mixed use with Bip39Tool (I'm not linked with BIP39Tool, I just honestly think it's a very good product)

[BlackHatCoiner]

I've often thought about creating my own seed from dice

How could this be done with a dice? I guess by representing every dice result to binary. I don't know if this is a solution, mainly because 128 isn't divisible with 3. (128/3 = 42.66)
Dice results in binary:

Code:

001
010
011
100
101
110

Assuming that your results are "1" 42 times on row, then you'd get:

Code:

001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001

Which is 126 bits. Sure, the computer could generate randomly the two remaining bits, but it ruins the purpose of this software. The other, better, solution is to differentiate 1-3 and 4-6 as ones and zeroes for the last two bits. I'm not sure, but I think that this isn't that strong since "000" and "111" can't be inserted (that easily). If you've found a way to achieve this theoretically, by having the same strength with the coin, tell me and I'll implement it.

Edit: This can't work since 128 ones or 128 zeroes will never come up.

I'd want to check this for 2 reasons

I understand that anyone who would try a newly written software would be afraid of these reasons. Yes, I said newly written. You would never do that on electrum. Instead, you'd use electrum to confirm that my software works properly.

That's okay, where there are bitcoins, there should always be a double-check of the funds' safety with the older programs that have gained the users' trust. I'll answer to both of your questions, even if I don't tend to use this phrase when I want to convince someone:  The software is open-source and simple. Everyone is allowed to read it and judge it. I'm using the popular NBitcoin C# library, which has been used in the past for a lot of bitcoin applications. Focus on "simple". My code is literally only 174 lines long. I didn't intend to attract those that have no experience on coding, but even those can understand that the private keys generated derived by Coin Flipped Seed aren't compromised.

Nice, thanks for sharing.. but why not using Bip39Tool? https://iancoleman.io/bip39/

Well, iancoleman surely provides better functionalities than my newly written program. I may add such features in the future, although I doubt. I don't compete ian. Sure, implementing an app that is useful is a pleasure, but even if it's not that useful, it was fun doin' it.  

[LoyceV]

How could this be done with a dice? I guess by representing every dice result to binary. I don't know if this is a solution, mainly because 128 isn't divisible with 3. (128/3 = 42.66)
Dice results in binary:

Code:

01
10
11
00

(code in quote edited)
I can think of different ways, the easiest is probably to just omit the 5 and 6, and interpret 1-4 as binary. That's still a bit faster than coin flips.

I'd want to check this for 2 reasons

I understand that anyone who would try a newly written software would be afraid of these reasons. Yes, I said newly written. You would never do that on electrum. Instead, you'd use electrum to confirm that my software works properly.

I've also checked addresses generated by a hardware wallet using Ian Coleman's site (running from RAM offline of course). For Electrum (or Mycelium, or Coinomi) I don't bother indeed, but I only use those for daily spending amounts.

[o_e_l_e_o]

How could this be done with a dice?

If you use iancoleman's site with the "Show entropy details" checked you can see that he maps it as follows:

Code:

1 = 01
2 = 10
3 = 11
4 = 0
5 = 1
6 = 00

The reason 00 appears at the end is because it is based on the Base 6 encoding which has 0 = 00, which makes more logical sense.

This is a more random way of doing things than the way of mapping a 3 bit number to 6 possibilities, since you were missing out the possibilities of 000 and 111, and therefore reducing the randomness of your entropy.

[BlackHatCoiner]

Major update:

Added dice roll option.

Each dice result corresponds to its analogous bits, exactly as o_e_l_e_o wrote. I consider this, a better solution than the coin flip. You'll need to roll between 64 and 128 times. Specifically, you have 33.3% chance for 5 and 6 that will add only 1 bit and 66.6% chance for 1, 2, 3 and 6 that will add 2 bits. Thus, on average you'll have to roll 64 + (1/3)*64 ~= 85.3 times.

Release (binaries): CoinFlippedSeed-v0.2.zip (0.98MB)
SHA-1: AC4FB9FE510D067F759B1D36CE67263A38D83866

Code:

-----BEGIN SIGNED MESSAGE-----
I, BlackHatCoiner, publish the v0.2 of CoinFlippedSeed in 20th of March 2021.
SHA-1: AC4FB9FE510D067F759B1D36CE67263A38D83866
-----BEGIN SIGNATURE-----
advance concert visit awesome neglect fire dizzy club deny danger disease sign rebel donkey tone educate dumb desert mosquito happy crane jungle grit near
IEAdSD1AxjsB0CzTdrQPmCLpRD4yh5iffOaH1lNWp54dbPq8KHATJI7LKiaiIR0LUNT78jbv8hAXEBubyQgxX/g=
-----END SIGNED MESSAGE-----

[o_e_l_e_o]

Great work!

Thus, on average you'll have to roll 64 + (1/3)*64 ~= 85.3 times.

I'm being completely pedantic here, but isn't it 76.8 rolls on average? Given that each roll will add an average of 1.666... bits of entropy, then 128/1.666... = 76.8 rolls.

For the future, you can use this same method of assigning different amounts of bits to different rolls/flips/results/etc to incorporate anything which has an even number of potential outcomes. For a 10 sided die, for example, you can use the 8 possibilities of 3 bits plus the 2 possibilities of a single bit. For a 20 sided die, the 16 possibilities for 4 bits plus the 4 possibilities of two bits. iancoleman goes as far as allowing a deck of cards by using the 32 possibilities of 5 bits, the 16 possibilities of 4 bits, and the 4 possibilities of 2 bits. 32+16+4 = 52.

Somewhat off topic, but note the issue with using a deck of cards being that after every card you draw, you should reinsert that card back in to the deck and shuffle the entire deck again before drawing the next card. Drawing 30 cards in a row from a deck without the possibility of duplication becomes less and less random as you go since you are removing a potential string of bits with every card you draw.

[LoyceV]

Somewhat off topic, but note the issue with using a deck of cards being that after every card you draw, you should reinsert that card back in to the deck and shuffle the entire deck again before drawing the next card. Drawing 30 cards in a row from a deck without the possibility of duplication becomes less and less random as you go since you are removing a potential string of bits with every card you draw.

If you go for a deck of cards, you don't need to stop at 30: after a proper shuffle you can just use all cards as a seed. That gives 225.58 bits of entropy.

[o_e_l_e_o]

If you go for a deck of cards, you don't need to stop at 30: after a proper shuffle you can just use all cards as a seed. That gives 225.58 bits of entropy.

Well, it depends on how you are calculating your entropy. If you are using iancoleman's method as I detailed above, then there is a total of 32*5 + 16*4 + 4*2 = 232 bits from drawing an entire deck of cards. However, this will not be equal to 232 bits of entropy for the reason I've detailed above - with every card you draw you remove a string of either 2, 4, or 5 bits of entropy from the remaining "pool", and that string will never be reused. So the further through the deck you go, the less entropy each additional bit contributes.

You can see this if you use logarithms to calculate the entropy instead, which is how we reach the 225.58 bits of entropy number you quoted. log₂(52!) = 225.58. But if we look at individual cards using this method, you can see how the entropy reduces as time goes on. Picking one card from a deck generates log₂(52) = 5.70 bits. Picking the next card from the deck generates log₂(51) = 5.67. And so on. The decrease in entropy with each subsequent card increases exponentially. By the 20th card, you are generating 5.04 bits, by the 40th card 3.70 bits, and by the 50th card only 1.58 bits.

Either way, if you use the full deck of cards as an entropy source to generate a 128 bit seed phrase, then that is more than enough. But if you only draw cards until you hit 128 bits of entropy on paper, than in reality your entropy will actually be weaker than that.

[BlackHatCoiner]

I'm being completely pedantic here, but isn't it 76.8 rolls on average? Given that each roll will add an average of 1.666... bits of entropy, then 128/1.666... = 76.8 rolls.

Without pedantry, there's no perfection. Yes, you're right, if half of the dice results returned 1 bit, then it'd be 1.5 bits of entropy on average. Thus, it's 2 - 1/3 = 1.66. I don't even understand why I multiplied 64 with 1/3 on my previous post.

Somewhat off topic, but note the issue with using a deck of cards being that after every card you draw, you should reinsert that card back in to the deck and shuffle the entire deck again before drawing the next card. Drawing 30 cards in a row from a deck without the possibility of duplication becomes less and less random as you go since you are removing a potential string of bits with every card you draw.

It's not off topic, it'd actually be nice to implement the same thing with a deck of 52 cards. (And it'd also take less time compared with the dice)

It kinda spoils me the fact that you'll have to put it back and shuffle again once you draw it. Unfortunately there's isn't a way to do it otherwise. But I want you to tell me your opinion about my thought:  Creating the entropy from a mixed Rubik's cube (3x3). The cube is consisted of six faces, each one has a different color (just like a dice with numbers). Every face has 9 colored blocks. If you count white as "01", yellow as "10", red as "11", blue as "0", green as "1" and orange as "00", then you have 108 bits pretty quickly. The problem, that I'm trying to figure out a solution, is how you'll get the 20 remaining...

The current color scheme of a Rubik's Cube ^{(with 4.3 x 10^19 different combinations)}:

Either way, if you use the full deck of cards as an entropy source to generate a 128 bit seed phrase, then that is more than enough.

I don't understand this. Why doesn't a full deck reduce the randomness while you're picking cards but it does when it's not a full deck?

[o_e_l_e_o]

But I want you to tell me your opinion about my thought:  Creating the entropy from a mixed Rubik's cube (3x3).

Now this is a very interesting idea. There are a couple of issues that spring to mind.

First of all, the way a Rubik's cube works is that the center of each 3x3 face never actually changes; it's just all the other layers which rotate around the 6 centers. So you would need to make sure this is no bias in selecting the face you are using. Secondly, there is obviously a finite number of each color and each color is on a block with either 1 or 2 other colors. For example, if the first corner on the face I am reading is red, and it is the red corner which is also attached to the green and white corners, then it means the next corner has a 4/21 chance of being blue, orange, or yellow, but only a 3/21 chance of being red, green, or white. This will be compounded as you progress through the cube, much like with the deck of cards, with the remaining options becoming more and more limited.

A solution to this would be to read a single face for an average of 15 bits of entropy, and then scramble the cube completely and read another face, and repeat until the desired entropy had been achieved. Although it doesn't completely remove the issues I've mentioned above, it certainly mitigates them to a large degree.

I don't understand this. Why doesn't a full deck reduce the randomness while you're picking cards but it does when it's not a full deck?

They both reduce the randomness. What I meant was that if you draw all 52 cards to reach in the region of 225 bits of entropy, then even with the problems described above you definitely have more than enough entropy to safely create a 128 bit seed phrase.

[BlackHatCoiner]

Although it doesn't completely remove the issues I've mentioned above, it certainly mitigates them to a large degree.

You're right, it can't work that way. The Rubik's cube doesn't achieve much randomness and it sounds complicated, if we're going to count every face. Although, I believe that it'd be really cool. I imagine myself mixing it for 5 minutes straight to prevent any "Rubik's cube brute forces".  

I don't want to give it up that easily. I was thinking of something else. Each face has 9 colored blocks and the one in the center never changes, as you said. This is what I propose:  Excluding the center block we end up with 8 blocks. The users will choose a face of the cube that will be the only one counted on this procedure. On each mix, the users will count every block except the middle one. Once they complete one mix and write the results on the program, they can mix it again until they've reached 128 bits.

These would be the bits of a solved face with the color white:

Code:

0101010101010101

Each face can result from 8 to 16 bits which means 128/14 ~= 9.1 bits on average. Pretty faster than the 1.66 bits with the dice.

(I'd rather discussing it first, before implementing it)

[LoyceV]

I imagine myself mixing it for 5 minutes straight to prevent any "Rubik's cube brute forces".  
~
Pretty faster than the 1.66 bits with the dice.

This seems like a terrible method if speed is what you want.
For speed, I would use a (leather) dice cup, with 6 dices. Then I'd use a ruler to move them (without looking), so they're all in one line to prevent any bias picking them. Start writing them down from the top.

[baro77]

If the goal is to squeeze every bit of entropy from a stochastic process, I think coin tossing and dice runs  are more reliable than cards or Rubik cube...

that's because the first two don't need a manual setup operation like shuffling cards or Rubik tesserae where biases (so entropy reduction) could nest: for example mixing cards usually doesn't mix touching cards as easily as distant ones, and how to consider Rubik shuffling enough if not checking by eyes (and subjectively).

This of course open a bigger OT point: if we live in a deterministic world (at least at our scale) where coin and dice randomness comes from? I think the current accepted answer is something like: from the chaotic dependence  of each run from uncontrolled boundary conditions, so these could be the recipe for seeking other sources

[BlackHatCoiner]

For speed, I would use a (leather) dice cup, with 6 dices.

Yes, this is surely faster.

where coin and dice randomness comes from?

That's a really nice question. I'd say from the fact that the person doesn't know the final result until he tosses the coin/rolls the dice (assuming, of course, that he/she has made no calculations). The final result is unpredictable, but in the coin, for example, there can only be two different results. If you toss it 1,000 times, you'll realize that on average half of the times you get "Heads". There isn't such thing as "randomness". Is it?

so these could be the recipe for seeking other sources

Can you explain me this part? What other resources can they seek?

[baro77]

That's a really nice question. I'd say from the fact that the person doesn't know the final result until he tosses the coin/rolls the dice

I'm not an expert but I think common words are risky here. So let's try to define what random could mean:

    given a potential string s[n] of n bits , s[n] is said to be random if its actual realization has the SAME probability to represent ANY number between 0 and (2^n)-1

if we agree about this definition (I think it's reasonable for the discussed goal), unpredictability is a weaker condition than randomness, because the latter is unpredictability driven by a specific outcomes distribution.

Example:
"00" @25%, "01" @25%, "10" @25%, "11" @25% is unpredictable and random
"00" @1%, "01" @49%, "10" @49%, "11" @1% is still unpredictable but definitely not random

What I want to say is that I think we cannot belittle "randomness" to "not knowing": it seems more subtle, it's "not knowing the actual realization" together with "strong confidence about statistical distribution of potential realizations".... so something in between completely knowing and completely not knowing...

so these could be the recipe for seeking other sources

Can you explain me this part? What other resources can they seek?

I only wanted to say that if we like the "randomness quality" of coin tossing or dice run, if we identify the causes of that quality (e.g. the "chaotic dependence  of each run from uncontrolled boundary conditions") we can use them as an heuristic to identify other good sources of randomness (ones regulated by laws of the same kind). I don't have an usable example, but I think weather seems a phenomenon of that kind....

[o_e_l_e_o]

I imagine myself mixing it for 5 minutes straight to prevent any "Rubik's cube brute forces".

5 minutes would probably be overkill. Any one of the 43 quintillion possible configurations of a Rubik's cube can be reached by no more than 20 moves. Assuming you can make 2 turns per second, then 30 seconds of scrambling would be more than enough.

Excluding the center block we end up with 8 blocks.

You don't need to exclude the center block altogether, but rather just ensure their is no bias in picking the side to use (or indeed, which one of the 4 orientations of that side to use). Perhaps rolling the cube across the table and using the side that lands face up, or throwing it in the air and using the side facing you when you catch it.

Each face can result from 8 to 16 bits which means 128/14 ~= 9.1 bits on average.

Again, I don't follow your math here. With 1.666... bits per square and 8 squares being counted, that would 13.333... bits per side.

For speed, I would use a (leather) dice cup, with 6 dices. Then I'd use a ruler to move them (without looking), so they're all in one line to prevent any bias picking them.

A simpler method is to get 6 dice of different colors, and determine the order you will read them before you start rolling. Obviously following the wavelength of light makes the most sense - red, orange, yellow, green, blue, purple.

[BlackHatCoiner]

"00" @1%, "01" @49%, "10" @49%, "11" @1% is still unpredictable but definitely not random

It is definitely not random, but predicting the result is easier comparing with the previous example, so it's not the same predictable as well. Randomness is the lack of predictability and as long as flipping a coin can result in two different values, 50% chance each, then it's fully unpredictable.

5 minutes would probably be overkill. Any one of the 43 quintillion possible configurations of a Rubik's cube can be reached by no more than 20 moves. Assuming you can make 2 turns per second, then 30 seconds of scrambling would be more than enough.

The problem with the Rubik's cube is that it's not random and what we want here is randomness (completely unpredictable). The user makes the turns of the cube, which doesn't differ that much from adding every bit by himself. It's a little worst than creating the entropy from the mouse's movement. The user knows very well what he/she is doing and thus the bits aren't added randomly.

Again, I don't follow your math here. With 1.666... bits per square and 8 squares being counted, that would 13.333... bits per side.

Yes, my mistake again, I thought that by dividing 128 with the middle number of the middle number between 8 and 16, it'd be correct. I am now rethinking that this is 1/4 and not 1/3.

[o_e_l_e_o]

The problem with the Rubik's cube is that it's not random and what we want here is randomness (completely unpredictable). The user makes the turns of the cube, which doesn't differ that much from adding every bit by himself. It's a little worst than creating the entropy from the mouse's movement. The user knows very well what he/she is doing and thus the bits aren't added randomly.

This is true, but I would argue that unless you are a very well practiced Rubik's cube solver, then you will find predicting where a single square will end up (let alone multiple squares) after only a handful of moves incredibly difficulty, and certainly not something you could work out in the space of a few seconds as you are making those moves. With 20 moves being enough to reach any configuration of the cube, I think my suggestion which would include 60 moves is enough to ensure sufficient entropy. Still, if you are concerned about the amount of entropy then you can just continue to scramble for a few minutes as you suggest, and even better to do it without looking at the cube/with your eyes closed.