Topic: PY21 - A simple BIP39 mnemonic generator in PYTHON (Read 498 times)

No problem.

Nice.

Looks correct to me...

One trick I've picked up over the years is to do hash-based cumulative output testing. In this case, how that looks is to run your code many times in a loop on a deterministic sequence of random bits and then add each generated mnemonic to a running hash. Here's a test harness that I used to calculate the hash from running your code against a million deterministic inputs:


Its output was:


If I run my own BIP39 code through that same process, then I get the same result, so I'm pretty confident that if mnemonic-correctness issues do remain, then they remain in both of our implementations.

Sometimes time flies and you forget important things, like responding to a fellow developer.




Thanks for the great explanation. I have carefully revisited the post you 've written and I am confident I have realised exactly the bugs you 've mentioned.

Now, having corrected the issues, I kindly ask to review them below, so I can then safely update OP.

You are right, I have updated it to the BIP39 standard.

Just wondering; can someone explains why this
is bad...if it is...And why the code given by the others members are better (if they are).

Thanks:)

For the "24 words" (not OP's code), that's because its checksum generator doesn't follow BIP39 standard which should be the first 8 (entropy/32) bits of the entropy's SHA256 hash.
Reference: https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki#generating-the-mnemonic

Changing the checksum generator to something like this should fix it:

For the "12 words" (also not OP's code), aside from the checksum, it's using a 256-bit entropy instead of the standard 128-bit of a 12 word mnemonic.
Just adjust the code above to match the correct sizes:
And set the correct entropy size:
Those are just "band-aid" solution BTW since the whole code is specifically written to work with those BIP39-incompatible code.

Still, it looks as if given an entropy, the mnemonic generated doesn't match the one provided by Ian Coleman on his website...

Ok:)

It’s true, now the three of them combine.

Interesting code.
You assume you have a better entropy source when you randomly choose one from three random
entropy source. But is it really the case?

Moreover, i don't get:
if you don't store the result of the function.
Do you mean:


Cheers

Since this is a topic about entropy I made some interesting integrations, I modified the script by adding a random secp256k1 point, random passphrase, random entropy salted methods, using random hashes to avoid predictive patterns and random concatenation of their order.
As long as the entropy percentage is closer to 50%, it means better entropy "in theory".
What do you think?


updated to the BIP39 standard

24 words

12 words

Hello,

Thanks for the experimentation. Although it may not be a huge improvement,
i think it might be more natural to replace:


with

Cheers

Yup, in the context of your script, slicing a length-128 string from a larger string of random 1s and 0s would work (that is, it would correct the bias, because the high-order bit would then have a 50/50 chance of being either 1 or 0).

But, the way that you posed that option as an alternative to zfill makes me think you don't fully understand the source of this bias. I hope you don't find the following explanation tiresome, I just know that if it were me in your shoes, I'd really appreciate someone taking pains to help me understand the potential hole in my thinking:

Let's imagine a toy version of this problem where you're trying to generate just 4 (rather than 128) bits of entropy with a coin. Let's not go down the rabbit hole of coin fairness, entropy extraction, and tossing technique. (I have a sometimes-sophomoric, or, as my wife would say, "bloody stupid" sense of humor, especially when I'm in a good mood, so "tossing technique" just gave me the giggles. Don't toss while flipping coins, yeah?)

There are only 16 possible ways for 4 coin-tosses-in-a-row to end up, so let's put them all in a table (ignore the last 4 columns for now):

Outcome	Pattern	Binary	Decimal	f1($pcv)	f2($pcv)	f3($pcv)	f4($pcv)
#1	HHHH	1111	15	"0b1111"	"1111"	"1111"	"HHHH"
#2	HHHT	1110	14	"0b1110"	"1110"	"1110"	"HHHT"
#3	HHTH	1101	13	"0b1101"	"1101"	"1101"	"HHTH"
#4	HHTT	1100	12	"0b1100"	"1100"	"1100"	"HHTT"
#5	HTHH	1011	11	"0b1011"	"1011"	"1011"	"HTHH"
#6	HTHT	1010	10	"0b1010"	"1010"	"1010"	"HTHT"
#7	HTTH	1001	9	"0b1001"	"1001"	"1001"	"HTTH"
#8	HTTT	1000	8	"0b1000"	"1000"	"1000"	"HTTT"
#9	THHH	0111	7	"0b111"	"111"	"0111"	"THHH"
#10	THHT	0110	6	"0b110"	"110"	"0110"	"THHT"
#11	THTH	0101	5	"0b101"	"101"	"0101"	"THTH"
#12	THTT	0100	4	"0b100"	"100"	"0100"	"THTT"
#13	TTHH	0011	3	"0b11"	"11"	"0011"	"TTHH"
#14	TTHT	0010	2	"0b10"	"10"	"0010"	"TTHT"
#15	TTTH	0001	1	"0b1"	"1"	"0001"	"TTTH"
#16	TTTT	0000	0	"0b0"	"0"	"0000"	"TTTT"

The first four columns are: 1. the possibility/outcome # (1 through 16, so, every possible outcome accounted for), 2. the heads-or-tails pattern corresponding to each outcome (H = heads, T = tails), 3. the same heads-or-tails pattern but in base-2 (1 = heads, 0 = tails), and 4. the heads-or-tails pattern converted from base-2 into base-10.

The last four columns involve the imaginary variable $pcv (previous column's value) and the following definitions:


Now, the first thing to think about when looking at that table is if there are any "bad" or "low entropy" outcomes in it? The answer to that is no: as long as each outcome is equally probable, then any given outcome is just as "entropic" as any other outcome. HTTH is just as good as TTTT, savvy? That means that, tempting though it is, it's a mistake to use the string length of the values in the f2($pcv) column to decide whether or not you "have enough entropy" (to be clear, it's a mistake to base that decision on anything about a single outcome). If you discard outcomes whenever len(f2($pcv)) != 4, then you're only ensuring that the pattern will always begin with a heads instead of a tails (check the table to confirm that).

The second thing to think about when looking at that table is if the final patterns in the f4($pcv) column ever disagree with the source patterns in column 2? They don't. So, you can rest assured that the zfill(128) that was present in your original script was correct (that is, it was only restoring 0s that, in some sense, were there from the start, and were "lost" during an int to str conversion). You can/should pat yourself on the back for getting it right the first time.

There are at least two other bugs in your script though (beyond the bias bug, which we'll call Bug #1):

Bug #2

You need a zfill(32) before passing the hexadecimal representation of your entropy into bytes.fromhex (otherwise, you'll occasionally pass it an odd number of nibbles, which will cause it to raise a ValueError).

Bug #3

You need a zfill(256) at the end of the line that calculates your sha256_bin variable (otherwise, your checksum, and therefore the last word of your mnemonic, will be wrong 50% of the time).

For an example, try manually setting your entropy to cc399b43e82bfbc07f2fe3fd1f13ed41.

Your script will spit out the following mnemonic: slow smoke special space sausage then witness wise wonder weasel win lobster

Ian's script (and mine) will spit out this instead: slow smoke special space sausage then witness wise wonder weasel win lion

The reason your wonder weasel only managed to win a lobster instead of a lion, is because you're miscalculating the checksum bits as 1001 instead of 0001.

(I'm going to be too busy to respond for a while. I'll take a peek at this thread again in a few weeks' time.)

If you generate more rounds of entropy then the amount that you end up with will be the average of the entropy of all the rounds. in other words: (E(Loop1) + E(Loop2) + ...) / N. Unless you select the bits from a specific place in the total amount in which case the calculation becomes slightly different but still follows through.

It doesn't make much of a difference, and if the reason you are doing this is to cover for a potential insecurity in the random number generator, it will not work well. OpenSSL's RNG is much better for that purpose.

Thanks PowerGlove, I find your answer very helpful.
I will check it in detail later today and I will comment, if I find anything important.
As you said, this is the approach that I like to follow. I code in order to understand something better.

Do you think it would be better if I generated more bits of entropy and then keeping 128 of them? Instead of zfill or repeating the process if bits are less than 128.

You've introduced a small bias by doing that...

This is a pattern that I see pretty often: an attempt to make things "more secure" that ends up backfiring.

Think of it like this: by predicating that loop on the entropy being exactly 128 bits long, you've removed the possibility of your program ever generating a 128-bit value with the high-order bit set to 0. That means, in hexadecimal terms, your entropy will always start with an 8, 9, A, B, C, D, E, or F (0 through 7 are no longer possible). In BIP39 terms, the first word of your mnemonic will always start with one of the letters L through Z (no matter how many times you run your script, you'll never generate a mnemonic that starts with an A-word, for example).

I think that what you were doing before with the zfill was better. (But, if you change it back, you should be aware that that will reveal a different bug that's hiding in your code: bytes.fromhex always expects a string with an even number of nibbles. That is, bytes.fromhex('abcd') will return b'\xab\xcd', but bytes.fromhex('abc') won't return b'\x0a\xbc', as you might expect, instead, it will raise a ValueError. So, there's a ~6% chance that your script will fail on any given invocation. Try it yourself, run the original version of your script again and again in a terminal and you'll encounter that problem eventually and get a traceback that'll point to the offending line.)

Please don't feel discouraged. It's cool that you're learning Bitcoin by programming little bits and pieces of it yourself, and then sharing your code: that's a really effective way to learn in my experience, so keep it up, dude.

I don't know about you, but I really appreciate seeing other people's takes on problems that I've recently solved myself, especially if they involve techniques that I may not be familiar with. So, here's my take on a 12-word BIP39 mnemonic generator in Python:


And here's the same script but generalized to produce either 12, 15, 18, 21, or 24-word mnemonics:

Hello, I just updated the OP with this:


so now, if the entropy is less than 128, it repeats the process until it is 128 bits long.

Thanks for the feedback.

It would be a small improvement to remove zfill, since it doesn't do much other than padding with zeros for which it isn't needed when there is a SHA256 hashing after. That probably should be removed eitherways, if the entropy is lower than required, then they should be able to run the entropy generation again. In a similar vein, a sanity check on the entropy before the SHA256 hashing would improve the security as well.

Edit: I stand corrected on the point about regeneration of entropy; should not be strictly enforced at 128.

As the title suggests, I developed an easy to use script that generates a BIP39 mnemonic.

I implemented it for fun. I don't plan to use it for real money.

The script:

How to run:
1. Create a file on your machine (example mnemonic_gen.py).
2. Copy - paste the code from above.
3. Create a file on your machine, called bip39_wordlist.txt and copy-paste the wordlist into the file.
4. Make sure to have both files in the same directory.
5. Just run python mnemonic_gen.py

Sample output:

Extra notes:
1. The script uses secrets module to generate entropy. It is essentially a CSPRNG and is the recommended approach to generate pseudo-random numbers in Python. Internally, it makes use of os.urandom as well.
2. For best security, use it offline, by just running the script on an airgapped device.
3. This is not a complete wallet. You must import the seed phrase on an offline wallet that you like, in order to convert the BIP39 phrase into a seed and produce the corresponding xpriv and xpub.
4. This method is only recommended if you don't trust the entropy source of your device and you want to use CSPRNG on an airgapped computer though python libraries.
5. It is similar to Ian Coleman's BIP39 implementation, in a sense that they both must be executed offline. The difference lies in the libraries that are used, as Ian's implementation uses javascript, whereas the script above uses python libraries.