Bitcoin Forum

Recently I started working on a new project called The FinderOuter¹ and whenever I implement an algorithm, I go around comparing it with others to see how others have tackled it compared to my approach. Unfortunately in this case I could only find 2 solution (1 (https://bitcointalk.org/index.php?topic=1624496.msg16334516#msg16334516) & 2 (https://github.com/ishristov/bitcoin-private-key-fixer)) and both are simple loops, not exactly the best approach.

So if you know of any code that could recover something like the following, please post it here:
Example is from bitcoin wiki (https://en.bitcoin.it/wiki/Wallet_import_format)

Alternatively if you have done this in the past and have any benchmark (the time it took to find the correct key) please post your time here for comparison.

Sneak peek of what I'm building in pure c# (1.25 million/sec is with core i3 CPU):
https://i.imgur.com/NA88t7h.jpg


1. Name is inspired by the TV show called Futurama (https://theinfosphere.org/The_Finder_Outer)

Have you considered using "random" combinations of missing characters as opposed to simply looping through the character sets sequentially?

I believe this would be much like the approach that "VanityGen" takes, where it just randomly generates a key and tests to see if it matches your desired prefix... You could randomly generate the missing characters and test if it results in a valid key etc.

I'm sure that there is all sorts of mathematical theory that is waaaayyyyy above anything I've ever been inclined to study that would predict which method is the more efficient.

Just using random combinations would most probably be less efficient.

He would need to store the characters which were already tested to not test the same one twice or even more often.
And if he does that, i doubt he would gain anything compared to simply iterating through the whole charset.

Yeah, but Maths can "surprise" you sometimes...

For instance, imagine trying to bruteforce a 4 digit combination of "9361"... going sequentially through all digits from 0-9... you're going to test 9362 iterations before you find the right one. Now imagine what the odds are of randomly generating 9361 if generating these combinations randomly... 0.1^4 right?

Now... what happens if the 4 digit combination was "0101"? You're only going to need 102 iterations... but the odds of randomly finding it are still 0.1^4...

So what are the odds of sequentially searching is faster than random? ??? Apparently, statisically, it makes no difference... (https://security.stackexchange.com/questions/44567/brute-force-in-order-or-random)

I suspect the more efficient method is dependent on a number of factors like the "randomness" of the combination you're looking for, the total size of the search space and how much time is required to generate and/or test each combination? But like I said... this is getting into some serious probability theory etc that confuses me these days :P

Usually when randomness is involved in an algorithm, the first step is random not the subsequent ones, and there is a relationship between these steps. There is also a chance of failure in such algorithms which means you have to go back to first step and choose another random first step. Example: Pollard's kangaroo algorithm, you "hop" around based on the first random entry point.
I am not familiar with how Vanitygen works but most probably the only reason for choosing a random key for its starting point is because the final result must be random and if it starts from anything not-random, the result could be reproduced and that makes the whole thing useless. Besides, that code is looking for collision in a very small space which is not more than a couple of bytes depending on the number of characters you chose so you have many possible results. But here we are looking for a single needle in a haystack.

What you said, could work if and only if there were some rules for going from key1 (the random key) to key2 apart from iteration (+=1) which means the only way of implementing something like this is to randomize the entry point and do the same thing from there. Anything other than that (eg. choosing a random combination each step) has the potential of increasing the chance of not finding the result ever since you'd be shooting in the dark.

Hint: the trick in optimization of something like this is going through all cases but not-repeating things you have already done. A simple loop over 656 mil+ would have taken about 20 minutes.

I don't see any suprise here. In both cases, you have to do 5000 checks on a large data set if each value will be generated only once. But you cannot force the generator to generate only unique values, so, additional overheads arise, associated either with the storage of already tested combinations, or with the re-verification of already tested ones. With a random number generator you will need to do 10000 generations on average.
Therefore, in this case, the best method is iteration.

I'm not sure when I'll be able to release the application itself, right now I'm looking into parallel programming and it is proving to be harder than I thought.
If you are interested in seeing the algorithm and have any feedback on it or any idea about parallelizing it you can check it out here: https://gist.github.com/Coding-Enthusiast/1a88a9c04a987b624bf33dee6765a635 (extra checks and report generator methods are removed)
The only thing missing is the code is the case when checksum is unknown (generate more than one result) and the code for Sha256 class which is pretty basic permutation function used in SHA algorithms without any intrinsics (ie. it is highly optimized but it has room to be optimized more).