Topic: [Open Source] Coin Flipped Seed (coin flip, dice roll, rubik's cube mixing) (Read 505 times)

No.

There are 4 corners in each color. 4 red, 4 orange, 4 blue, 4 green, 4 yellow, 4 white. Your first corner will be one of these, a 4 in 24 chance of each color. By the time you get to the second corner, you have used up one corner block. Let's say the first corner was red, but that individual corner block will also have two other colors attached to it. Let's say it is the red/blue/white block. Your next corner has a 4 in 21 chance of being orange, green, or yellow, but only a 3 in 21 chance of being red, blue, or white. Let's say your next corner is blue, using the blue/red/yellow block. Now you've used 2 reds, 2 blues, 1 white, and 1 yellow. So for corner three you are down to 2 in 18 for red and blue, but twice as likely (4 in 18) for orange and green, with white and yellow being 3 in 18. You are no longer being random.

The same principle holds true for the four non-corner squares you are reading, albeit with different numbers since each side square is only attached to one other color.

Yep. I'll have to stop announcing releases during the night.  

This means 128/15 ~= 8.5 scramblings on average. I'll change it on my post.

It is surely not recommended, since the result isn't completely unpredictable, as you said the user knows what he's doin'. I did it only for fun and I discourage anyone from using it for anything above a million satoshis. The dice is, by far, the greatest option. On a future release I'll warn the user about that.

Thanks. I had totally forgotten it.

As long as you scramble the cube each time you submit a side, I don't get how that applies. Wouldn't that be true only if you mix it once and submitting the 6 sides as they were?

That is what I was referring to. There are only 4 red corners on a Rubik's cube, for example. If you use one of them on the first corner, then you have decreased the chances of the other three corners being red and therefore reduced the entropy of these squares.

If someone was to use the tool without a physical cube and just click on a bunch of squares to change their color, then that would likely be even worse, similar to how we tell people not to manually pick words to make a seed phrase, regardless of how "random" they think they are being.

There's a 2/3 chance of 2 bits of entropy and a 1/3 chance of 1 bit of entropy, meaning an average of 1.666... bits of entropy per square. 9*1.666 = 15 bits.

Having said that, I still wouldn't recommend this method for the reasons I discussed above. Scrambling the cube manually is not going to produce the same kind of entropy as rolling a dice or flipping a coin since you are consciously deciding every move to make as well as which face to read from. Further, each square you enter decreases the entropy of all subsequent squares you enter until you scramble the cube again.

It's a cool idea to play around with, but you shouldn't use this to generate a serious wallet.

For the same reason you can't have 3 bits on each result of a six-side dice. The dice can only return you 6 different values, while 3 bits have 9 different combinations. Same happens for the rubik's cube.

(If I confused anyone, once you submit your cube's result, you mix it again. I just chose the same result to put into my entropy because of the GIF size)

---

Also forgot to write, future changes:

• Deriving addresses for altcoins and testnet.
• Option for electrum seed instead of BIP39.
• Maybe deck. Not sure how well can this work in practice. Do you have any other random related items on your mind to work on?

Major update:

Added rubik's cube mixing option and custom number of derived addresses.


As you can see blue, white, yellow and red gives us 2 bits while orange and green only one. So the worst case scenario (for time) would be having only green and orange blocks which would give a total of 9 bits for each side of the cube. On the greatest scenario, having no greens and oranges will return 18 bits.

So if I'm not mistaken every side will return 18 - (1/3)*18 = 12 bits 15 bits (9*1.666) which means 8.5 scramblings on average.

Release (binaries): CoinFlippedSeed-v0.3.zip (1.18MB)
SHA-1: 4DA93F3D72A9EB65282650E15D4E3C288A28FD71

---

Yes, but as you can imagine, it doesn't differ from the mouse movement way at all. It doesn't provide anything to the users, besides that cool way to derive their addresses. It is actually worst than the mouse movement, because it takes much longer than that. Anyway, I don't think that it belongs on this software, I think that it'd be better to keep it simple (and fully unpredictable).

Nonetheless, it'd be interesting to implement it in the future, since no one hasn't done it yet. *cough-cough*

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.

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.

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.

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.

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.

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.

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.

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.

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...


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....

Yes, this is surely faster.

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?

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

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

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.

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:


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)

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.

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.

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.

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)}:


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?

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.

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.

Great work!

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.