all credit to mcdouglasx. this is their idea. i just tested it and found ways to make it run faster in python.
their thread:
https://bitcointalk.org/index.php?topic=5475626their github:
https://github.com/Mcdouglas-X/lightweight-database-for-Bitcoin-public-keys-bruteforcewhat mcdouglasx built
you can store public keys as 1 bit each instead of 256 bits. a public key y coordinate is either even or odd. even = 0, odd = 1. one bit tells you something real about that key. 64 bits together form a pattern unique enough to identify any key in a database of billions.
32 million keys fit in 3.81 MB. 4 billion keys fit in 512 MB. this works because you are not storing the keys themselves. you are storing a 1-bit fingerprint of each key.
to create the database you start with your target public key. you subtract 1 repeatedly to make a chain of keys going backwards from the target. for each key you check if the y coordinate is even or odd and write a 0 or 1. the bits get packed into bytes and written to a file.
to search you pick a random private key in your range, generate its public key, do 64 subtractions from it, extract 64 parity bits, pack them into 8 bytes, and check if those 8 bytes appear anywhere in the database file. if they do, the position where they were found tells you exactly how far you are from the target. you add that offset to your random starting key and you have the private key.
arulbero and WanderingPhilospher tested this in the thread. it finds keys. with a 64-bit collision margin the false positive rate is near zero.
where the original python code is slow
mcdouglasx used a module called bitstring (BitArray) to pack bits to bytes. that module does the work in pure python character by character. it is the bottleneck.
the original search loads the entire database file into RAM with file.read() then scans it with python's bytes.find(). on large files this eats memory and the scan is slow.
the parity check converts each point to hex then to int then to string then checks the last character. most of those steps are unnecessary.
three simple fixes, all pure python, no new dependencies
fix 1: pack bits directly with bytearray
skip the BitArray module entirely. access the point data directly. each uncompressed point from ice.point_loop_subtraction is 65 bytes. byte 64 is the last byte of the y coordinate. the lowest bit of that byte IS the parity. check it with a single bitwise AND. pack bits into a bytearray as you go.
buf = bytearray((num_keys + 7) //
for t in range(num_keys):
byte_val = res[t * 65 + 64]
if byte_val & 1:
buf[t >> 3] |= (1 << (7 - (t & 7)))
f.write(bytes(buf))
this is about 10 times faster than BitArray. no string conversions. no external module. just stdlib bytes.
fix 2: search with mmap instead of file.read()
mmap maps the database file directly into memory without copying it. mmap.find() calls libc memmem which runs at memory bandwidth speed. no python overhead per byte.
import mmap
with open('database.bin', 'rb') as f:
with mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ) as mm:
pos = mm.find(candidate_bytes)
if pos >= 0:
return pos
the database can be 16 GB. mmap handles it. no RAM usage beyond what the OS caches. search time under 0.1 seconds even for large files.
fix 3: extract parity from the raw byte
skip hex conversion, int conversion, string conversion, and endswith checks. the parity bit is literally bit 0 of the last byte of the uncompressed point. one bitwise AND gives you the answer.
byte_val = res[t * 65 + 64]
bit = byte_val & 1
that is it. two CPU cycles. the original was about 200 cycles.
how to skip keys you do not need to store
if you know something about where the target key lives you can store fewer keys and cover more range. this is optional. it depends on what structural patterns you believe exist in the puzzles.
if you store only even y keys you step by 2 instead of 1. your database covers double the range for the same size. if you store only keys where the private key leaves a certain remainder mod 5 you step by 5. if you store only keys where the private key equals a known value mod 323 you step by 323.
each filter multiplies your effective range. use the ones you can prove. skip the rest. the database format does not care what step size you use. it works the same whether you step by 1 or 1000000.
how to not lose work if your computer crashes
building a large database can take hours. power cuts or crashes should not mean starting over. five simple rules make the process safe.
1. save your progress to a .tmp file. flush it. rename it over the real checkpoint file. if the write is interrupted the real file is untouched.
2. write a progress line to a log file every N keys. include how many keys written and how far through the total you are. flush it to disk. if the log stops you know where it died.
3. if an error happens save checkpoint first then log the error. you always know the last good state.
4. catch ctrl-c. save checkpoint on the first press. kill on the second press.
5. never write results directly. write to .tmp then flush then rename. a partial result file is worse than no file.
all of this uses only python standard library. open, write, flush, os.fsync, os.replace. no dependencies. about 50 lines of reusable code.
summary
mcdouglasx's idea stores 32 million keys in 3.81 MB and finds any one of them in under a second on one CPU core in python. with the three fixes above it runs about 10 times faster at database creation and uses near zero RAM for search regardless of database size.
the database is not a puzzle solver. it is a verification tool. if your analysis narrows the search to a few million candidate keys this database checks all of them in minutes on a laptop.
credit: mcdouglasx for the 1-bit database. arulbero for the BSGS analysis and search scripts. WanderingPhilospher for weeks of testing and finding bugs. the bitcointalk puzzle thread for keeping the discussion alive since 2015.
the code for all of this is available in mcdouglasx's github repo linked above. the fixes described here are standard python optimizations. anyone can test them. nothing here requires special hardware or paid software.
Good luck, racing you to the solution
all changes here. welcome to test.
