In this project, only the CPU is used for brute-forcing.
Use GCC to compile this project:
A brief introduction to Bitcoin Puzzle, also known as BTC32, all necessary references, and some nice statistical analysis can be found is this repository. The whole Bitcoin Puzzle is a set of 160 puzzles with increasing difficulty, some of them are already solved (using brute force), and others are not. You can use this project to brute-force the private keys from this puzzle. The easiest non-solved yet puzzle is # 64.
Key represents a Bitcoin private key which is a 256-bit number. In some cases, it also may represent just 256-bit numbers which are not valid Bitcoin private keys or even 512-bit numbers. In the project, it is stored as an array of four or eight unsigned long long i. e. 64-bit digits. To work with such data, multiprecision arithmetic is implemented.
A key can be constructed either from four 64-bit digits, or eight 64-bit digits (for some further algorithms it is sometimes necessary to consider 512-bit numbers).
There are some static constant fields such as ZERO, ONE, etc. for some important key constants.
The next principal methods for keys are implemented:
add, subtract for arithmetical 256-bit addition and subtraction with a carry/borrow flag; addExtended adds 512-bit keys; increment effectively add 1 to a keymultiply for arithmetical multiplication; multiplyByR2 for optimized multiplication by R2; multiplyLow for calculating only low part of the result; reduce does Montgomery reductiondivide for division (Knuth's D-Algorithm is used)operator+=, operator-=, operator*=, invert for modular addition, subtraction, multiplication, and inversion modulo P, respectively; invertGroup effectively inverts a group of keys as described heregcd performs the extended Euclidean algorithmPoint represents a Bitcoin public point which is a point on secp256k1 which is a. k. a. Bitcoin Curve. It consists of two 256-bit keys x and y. G is the generator point.
A point can be constructed either from two keys (x and y), or from a private key as the corresponding public point (the last operation is quite slow).
The next principal methods for points are implemented:
initialize is a static method to initialize gPowers and gMultiples which are some useful pre-computed pointsoperator+=, add, subtract for elliptic curve addition and subtraction (two last methods use the pre-computed inverse of the abscissas difference); addReduced and subtractReduced calculate y % 2 instead of y for the result pointdouble_ for elliptic curve point doubling i. e. adding a point with itselfcompress method compresses the point to pass the result to sha256 (it is not usual compression of a public point but an optimized one)sha256 and ripemd160 are hashes which are used for converting a public point into a Bitcoin address. Addresses in this project are not common addresses of Bitcoin like 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN but Base58Check-decoded ones like 3EE4133D991F52FDF6A25C9834E0745AC74248A4 (by the way, the address in previous examples is the address of the puzzle # 64). In the project, these hash-functions are highly optimized such that they break their specification rules; for example, SHA256 does not do packing and unpacking to optimize speed.
All the methods from Key, Point, and functions from sha256, and ripemd160 are tested in test. Some of them, which are directly used in brute-forcing keys, are speed-tested.
On Windows (64-bit) with Intel(R) Celeron(R) J4125 processor the total speed is about 2.2 million keys per second.
On Raspberry Pi 3B+ with a 64-bit operating system, the total speed is more than 1.2 million keys per second. There are approximate time consumptions for the principal operations using 1 thread on Raspberry Pi 3B+ with a 64-bit operating system:
| Operation | Time for 1 operation | Usages for 1 key | Time for 1 key | % of total time |
|---|---|---|---|---|
sha256 |
750 ns | 1.0000 | 750 ns | 23 % |
Key::invertGroup |
3 000 000 ns | 0.0002 | 730 ns | 23 % |
Point::subtractReduced |
1200 ns | 0.5000 | 600 ns | 19 % |
Point::addReduced |
1200 ns | 0.4998 | 600 ns | 19 % |
ripemd160 |
510 ns | 1.0000 | 510 ns | 16 % |
Point::compress |
15 ns | 1.0000 | 15 ns | 0 % |
Key::operator-= |
17 ns | 0.5002 | 9 ns | 0 % |
Key::increment |
8 ns | 1.0000 | 8 ns | 0 % |
Point::add |
1200 ns | 0.0002 | 0 ns | 0 % |
The compiled program needs two required arguments — the private key prefix and the address prefix. The default number of threads is 4. If you need to run 2^n threads, pass the third argument with the number n. For example, to check all the private keys with prefix 000000000000000000000000000000000000000000000000FC9602C002C75EAA and find those whose address (Base58Check-decoded one) starts with 3EE4133D, using 16 threads, run
bitcoin_brute_forcer 000000000000000000000000000000000000000000000000FC9602C 3EE4133D 4The program prints lines to console with different prefixes:
[I]: an informational message (for example, a progress message)[W]: a wallet with a partially coinciding address[E]: an error messageThere is an example of a wallet in the program's output:
[W] 000000000000000000000000000000000000000000000000FC9602C002C75EAA 3EE4133DB100C6DEE46F584A1D88BA1533EEEE5DIt contains a pair of a hexadecimal private key (000000000000000000000000000000000000000000000000FC9602C002C75EAA) and the corresponding Base58Check-decoded address (3EE4133DB100C6DEE46F584A1D88BA1533EEEE5D). The program does not check the exact coincidence with the sought decoded address; it checks only the 20%-coincidence i.e. the first 4 bytes which you pass as the second argument.
There is also finish point check. If the finish point for some thread is wrong (normally, it doesn't happen), then there will be an error message in the output.