This is the public key: f5c03157f4a489ed71c0df0f37799431b3f432654a9bd6efdbb79ba767b62e81
I need to find this private key: 821480591424854
Private key found!!!
Collision!
258530638003543
604085cce892dbb8bf9e70959ef178bc78fb123caaa4e9b1f3521139542da57f For example, I got a collision, how to calculate the private key? The key 821480591424854 is in the range 2^49 - 2^50 Try with these parameters: start_key = 1
num_public_keys = 2**50
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 2**24
Did you use bits_to_store = 64? And the other parameters? |
|
|
|
You (not me) are comparing 2 different type of sets, but you can't apply the idea of this thread to the DP keys, because they are not equally spaced. Lol, ok. With Kangaroo, it does not matter if they are or are not equally spaced. However, if you think the keys stored in a Kangaroo DB must be NOT equally spaced, then that is also achievable with this script. You just mimic different starting keys, like Kangaroo does. To me, I have a DB full of DP 0 bits, wilds. Now I run only tames, and check for collisions. In my mind, it does not matter if the keys in the DB are equally spaced or not, but that is easily achieved by offsetting the target pubkey before running DB creation. Then: you have a DB full of DP 0 bits (no DP) wilds equally spaced when you run tames, you want to check for collisions every step using the idea of this thread? And if the wilds DP (DB bits > 0) are not equally spaced, how can you perform a check against the wild DB using 1 bit per key? |
|
|
|
But the distance between 2 keys must be the same, otherwise I don't understand how can you know if a key is in your database.
And the DP keys in DP database are not equally spaced.
I don’t understand. The keys in DB are/can be equally spaced. DP keys aren’t equally spaced because points with DPs are not equally spread. Ok, we agree on these facts. But you said:
For #115, DP size of 25, had 2^33.5 points; a file size of over 350GB.
I have a file with 2^36 keys stored, but at only 8GB. Do you see the difference?
You (not me) are comparing 2 different type of sets, but you can't apply the idea of this thread to the DP keys, because they are not equally spaced. |
|
|
|
Yes, if you are trying to reduce the size of a DP database, the task is different.
You want to know if a certain DP key is in DP database as fast as possible, right? Then you need a small size and fast search algorithm that works with a group of non consecutive keys.
Your 2^33.5 keys are spread in a 2^115 space, not in a 2^34 space. The task is very different. Who said my keys or this script's keys are limited to a 2^34 space? I can spread them out as little or as much as wanted. Example: I can generate 2^34 keys spread out every 1000000000 keys or I can mimic Kangaroo jumps; spread the keys out every (for #130) 130 / 2 + 1 = 66; so I could spread the keys out every 2^66 key. For the DB that has 2^36 keys stored in it, the search script generates 64 subs and checks entire DB in 1 second. I'm not concerned about speed when a DB has over 68 Billion keys in it. It's a lot faster than the merging of files to check for a collision (JLPs Kangaroo version). But the distance between 2 keys must be the same, otherwise I don't understand how can you know if a key is in your database. And the DP keys in DP database are not equally spaced. |
|
|
|
1 bit for 2^32 keys is better than 64bits for 2^32/2^20 = 2^12 keys.
Less size, less search time, 100% keys found.
To speed up the serch, I need to store more information per byte, more density of information/work per byte stored.
For example, If I generated all 2^44 keys and I stored only the keys with the first 20 bit = 0, I would get a database with the same size of a databse created with 1 key each 1 million.
But the search time would be faster, cause I would need to check only 1 key against the database instead of 1 million. I think you are looking at it from a small interval size. I am looking at it from a larger standpoint. For #115, DP size of 25, had 2^33.5 points; a file size of over 350GB. I have a file with 2^36 keys stored, but at only 8GB. Do you see the difference? We are looking at using a smaller DB size in different ways.If you ran a DP of 20 in a 2^44 range, you would wind up with roughly 2^24 keys stored. As far as finding DPs, I have the fastest script, not on the market lol. GPU script. I can find all DPs (of any size), in a 2^44 range in a little less than 16 minutes. Yes, if you are trying to reduce the size of a DP database, the task is different. You want to know if a certain DP key is in DP database as fast as possible, right? Then you need a small size and fast search algorithm that works with a group of non consecutive keys. Your 2^33.5 keys are spread in a 2^115 space, not in a 2^34 space. The task is very different. You don't need the private key, you need only to know if you have hit a DP already in database? |
|
|
|
The first version of the script worked, the second does not find matches.
There may be an error in the code.
On my PC, 100 keys found out of 100, ....  Did you set the same parameters in both scripts? About an hour and a half ago, I copied both scripts, created a database and launched the search script. I didn't change anything in the parameters. Ah, I uploaded a version of create_database that doesn't match with that version of the search_pk script Now it should work: To perform multiple search, for linux: time for i in {1..100}; do python3 search_pk_arulbero.py; done |
|
|
|
The first version of the script worked, the second does not find matches.
There may be an error in the code.
On my PC, 100 keys found out of 100, .... Did you set the same parameters in both scripts? |
|
|
|
4) my script finds the key every time? So far, yes. Ok, when I ran your original script, it was less than 20% of the time the key was found. Keep working on the database size. I know you will get it down! If you can get it down to 1 bit per key like the OPs, then you're onto something. His DB is unmatched so far. Less than 20%? Did you try with the last version? Maybe the first version was not correct, I fixed some stuff. I don't understand why: 1 bit for 2^32 keys is better than 64bits for 2^32/2^20 = 2^12 keys. Less size, less search time, 100% keys found. To speed up the serch, I need to store more information per byte, more density of information/work per byte stored. For example, If I generated all 2^44 keys and I stored only the keys with the first 20 bit = 0, I would get a database with the same size of a databse created with 1 key each 1 million. But the search time would be faster, cause I would need to check only 1 key against the database instead of 1 million. |
|
|
|
Impressive!
How did you manage to make your database smaller compared to your original script? And why does it go up in size with the same amount of keys? Edit: I read it wrong as if you were storing 1 Mil keys every time lol.
Also, does your search script find the key every time?
1) my original script (create_database) is not changed 2) not with the same amount of keys, range is not equal to number of keys number of keys stored = range / 2^20 in one case, and number_of_keys = range / 2^24 in other case 3) my script is basically BSGS: big steps -> database : 1*G, 1*G+2^20*G, 1*G+2*2^20*G, 1*G+3*2^20*G, ...., range*G small steps --> search: P=k*G, k*G-G, k*G-2*G, k*G-3*G, ...., k*G-2^20*G the only difference is: I'm triyng to reduce the size of database, storing only 64 bits for each key and other improvements. 4) my script finds the key every time? So far, yes. |
|
|
|
From start to finish. But it's not the speed, it's the size of the DB, only 121kb  Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time. My results: ------------------------------------------------------------------------------- I managed to get another improvement, using the symmetrie. Instead of generating a interval [1 -> 2^40], if we shift the interval to [-2^39,2^39] then the 'positive' part has the same x-coordinates of the 'negative' part, so I can store only half keys (and have the same information). Now these are my results: ------------------------------------------------------------------------------- 2^32 range1 key each 2^20 (1 million) time to generate the DB: 0.055 ssize of DB: 16kBmax time to find the private key : less than 2 seconds. ------------------------------------------------------------------------------- 2^36 range1 key each 2^20 (1 million) time to generate the DB: 0.26 ssize of DB: 256kBmax time to find the private key : less than 2 seconds. ------------------------------------------------------------------------------- 2^40 range1 key each 2^20 (1 million) time to generate the DB: 3.65 ssize of DB: 4 MBmax time to find the private key : 2 seconds. ------------------------------------------------------------------------------- 2^44 range1 key each 2^20 (1 million) time to generate the DB: 59 ssize of DB: 65 MBmax time to find the private key : 3 seconds. ------------------------------------------------------------------------------- 2^44 range1 key each 2^24 (16 millions) time to generate the DB: 3.65 ssize of DB: 4 MBmax time to find the private key : 31 seconds. ------------------------------------------------------------------------------- I didn't upload the script yet. Next step could be find a way to speed up the search, probably storing the keys in a different order. Could this script be faster than BSGS (Baby Step Giant Step)?
Or Are they similar to each other?
Faster than BSGS ? No. |
|
|
|
From start to finish. But it's not the speed, it's the size of the DB, only 121kb Well I mean the speed is good for a single core. DB creation and search for the key and find it in under 9 seconds, 100% of the time. My results: ------------------------------------------------------------------------------- 2^32 range1 key each 2^20 (1 million) time to generate the DB: 0.060 ssize of DB: 32kBmax time to find the private key : less than 2 seconds. ------------------------------------------------------------------------------- 2^36 range1 key each 2^20 (1 million) time to generate the DB: 0.5 ssize of DB: 512kBmax time to find the private key : less than 2 seconds. ------------------------------------------------------------------------------- 2^40 range1 key each 2^20 (1 million) time to generate the DB: 7.3 ssize of DB: 8 MBmax time to find the private key : less than 2 seconds. ------------------------------------------------------------------------------- 2^44 interval1 key each 2^20 (1 million) time to generate the DB: 2 msize of DB: 129 MBmax time to find the private key : less than 4 seconds. ------------------------------------------------------------------------------- 2^44 range1 key each 2^24 (16 millions) time to generate the DB: 7.3 ssize of DB: 8 MBmax time to find the private key : 30 seconds. ------------------------------------------------------------------------------- The problem with my implementation is that the time search goes up with the size of DB and with the number of the keys I skip in the database creation. The goal is to have a faster implementation for large intervals, not for small intervals I updated my search_key script. Now it is a little faster. Using a key in the 30 bit range: 3d94cd64
The result,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This is the public key: 0d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b
I need to find this private key: 0x3d94cd64
Private key found!!!
0x594cd64
a152cbd0f4fdb5caf73c1ef6469896a760461bb0d297075962b40b7f5e93d2fd
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0x5 94cd64 the last 6 are correct but the 5 of course is wrong, so produces the wrong public key.
Not sure why
I thought it might be a false positive, but ran through the whole database, but no other string was found.
Are you sure you have changed the parameters in both scripts (same parameters in both): create_database and seach_pk ? Anyway I updated the search_pk (it is in the same post) |
|
|
|
I wrote the both scripts:
create_database_arulbero.py
search_key_arulbero.py
Both scripts appear identical or is it me?  You're right, I copied twice the same file. Now there are 2 different scripts. |
|
|
|
You say 4GB but you aren't comparing apples to apples.
In your scenario of only saving every 128 keys out of 2^36 keys, your DB does not contain 2^36, but 2^36 / 2^7 = 2^29 keys.
If I spread out my keys to every 128 inside a 2^36 range and only store 2^29 keys, my DB size would be about 63MB. Big difference, huge.
If the goal is finding the private key of a public key that is in a interval for which you have precomputed the public key, AND at the same time the goal is to keep the size of the db as small as possible, why don't you reduce your db size to 63 MB then? |
|
|
|
I wrote the both scripts: create_database_arulbero.py
search_key_arulbero.pyparameters: private key interval: from 1 to 2^32keys stored: 2^32 / 2^7 = 2^25 (1 each 128) bits for each key = 64 size of database: 257 MBtime to create the database: 3 min 55 stime to find the private key of a single random public key in the db: 0.1 - 0.3 s
create_database_arulbero.py#!/usr/bin/env python3
# 2023/Dec/03, create_database_arulbero.py
import secp256k1 as ice
import sys
#############################################################################
# Set the number of public keys to generate
#############################################################################
start_key = 1
num_public_keys = 2**32 #(about 4 billions of keys)
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 2**20
rate_of_key_to_store = rate_of_key_to_generate
interval_to_generate = range(start_key, start_key + num_public_keys, rate_of_key_to_store)
interval_to_store = range(start_key,start_key + num_public_keys,rate_of_key_to_store)
binary_mode = 1
#############################################################################
if (binary_mode == 1):
f = open("public_keys_database.bin", "wb") #binary mode
########################################generation#############################################
public_keys=[]
public_keys_complete=list(map(ice.scalar_multiplication,interval_to_generate)) #generates the public keys complete
public_keys=list(map(lambda w: int(w[33-bytes_to_store:33].hex(),16),public_keys_complete)) #extract only the last bytes_to_store
########################################writing the db##########################################
for i in range(0,len(interval_to_store)):
f.write(public_keys[i].to_bytes(bytes_to_store,sys.byteorder)) #writes each key
f.close()
else:
f = open("public_keys_database.txt", "w")
#generation
public_keys=[]
for i in interval_to_generate:
P4 = ice.scalar_multiplication(i)
public_keys.append(P4[33-bytes_to_store:33].hex())
#writing the db
for i in range(0,len(interval_to_store)):
f.write(public_keys[i])
f.close()
# 2023/Dec/03, arulbero_search_key.py
import secp256k1 as ice
import random
import sys
#############################################################################
# Set the number of public keys to generate
#############################################################################
start_key = 1
num_public_keys = 2**32
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 2**20
rate_of_key_to_store = rate_of_key_to_generate
split_database = 256 #read only a fraction of the database to speedup the finding of the string
interval_to_generate = range(start_key,start_key + num_public_keys, rate_of_key_to_store)
interval_to_store = range(start_key,start_key + num_public_keys,rate_of_key_to_store)
binary_mode = 1
#########################################################################################
#pk = 0x3243 = 12867
#P = ice.scalar_multiplication(12867)
#P="0x6800b#b8a9dffe1709ceac95d7d06646188c2cb656c09cd2e717ec67487ce1be3"
#############generates random private key and public key#################################
pk= random.randint(start_key, start_key + num_public_keys)
#pk=start_key + num_public_keys-1
P = ice.scalar_multiplication(pk)
print()
print("This is the public key: " + P[1:33].hex())
print("I need to find this private key: "+str(pk))
###################subtraction of : P - 1G, P - 2G, ..., P - rate_of_key*G################
substract_pub = ice.scalar_multiplication(1)
complete_pub= ice.point_loop_subtraction(rate_of_key_to_generate, P, substract_pub)
partial_pub=[] #need only the last bytes_to_store
P2=int(P[33-bytes_to_store:33].hex(),16).to_bytes(bytes_to_store,sys.byteorder)
partial_pub.append(P2)
for i in range(1,rate_of_key_to_store+1):
partial_pub.append(int(complete_pub[(i-1)*65+33-bytes_to_store:(i-1)*65+33].hex(),16).to_bytes(bytes_to_store,sys.byteorder))
################search in database##########################################################
num_bytes = num_public_keys*bytes_to_store//rate_of_key_to_store
size = num_bytes//split_database
s_partial_pub = set(partial_pub)
with open("public_keys_database.bin", 'r+b') as f:
#s=f.read()
for k in range(0, num_bytes, num_bytes//split_database):
f.seek(0,1)
partial_db = f.read(num_bytes//split_database)
l_partial_db = [partial_db[i:i + bytes_to_store] for i in range(0, size, bytes_to_store)]
s_partial_db = set(l_partial_db)
a = list(s_partial_db & s_partial_pub)
if (len(a)>0):
n = partial_db.find(a[0])
if n > -1:
print()
print("Private key found!!!")
private_key = (n+k)//bytes_to_store*rate_of_key_to_generate + partial_pub.index(a[0])+1
if(pk == private_key):
print("It is correct!!!")
else:
print("Collision!")
print(private_key)
P3 = ice.scalar_multiplication(private_key)
pub_key=P3[1:33].hex()
print((pub_key)[:])
f.close()
sys.exit(0)
print("string not found")
|
|
|
|
and if database is larger and larger -> it creating then too many false positives.
Then simply you have to store more bits per key; if you want to have 0 collisions, store 256 bits for key. It works always. And if you want a smaller database, you can store 1 key each 1024 keys. |
|
|
|
What would be the false positives for the way you store keys? Mine is almost 0%. I've ran hundreds of tests now with zero false positives.
Also, why can't you store keys as a 0 or a 1? To make your DB even smaller?
My search script is like the OPs original but I added incremental.
In random, it lands on random point, does 64 comps, goes to next random point, 64 comps, etc.
Incremental is the same way except if you start at 0 and your stride/jump size is 2^20, then land on point 2^20, do 64 comps, jump to 2^20+2^20 point, do 64 comps, etc.
The script can also spread the keys out like you are saying. Save only every other 128 keys, the keys do not have to be sequential.
I store 64 bits for each key, you store 64 bits for 64 keys; in my database there are less strings of 64 bits to compare with, then I think my probability is almost zero too. For smaller databases (like 2^30 keys) I could use even less than 64 bits for keys (like 48 bits) without problems. If I implemented the "first x bits = 0" then the probability of collisions (at the same size of database) would be even lower (but it would take much longer to build the database). I'm curious to your false positives and any search script you would create.
Me too. |
|
|
|
Understood.
I have a database with 63,570,000,000 keys stored in it, with a size of only 7.7GB. This one was created using the BitArray function, but it has flaws when doing a search so I am not using it at the moment.
But when I run the search script, it uses the equivalent in RAM, roughly 7.7GB of RAM used during the search.
But I can make jumps the size of 63,570,000,000 (almost 2^36), do 64 computations, and know within a second if key is in that range or not. So every less than a second, it jumps 2^36 keys and checks for a match. But this is using python, could be much faster in C, C++, and a lot faster with GPU support.
Then, you can reduce the space and increase the costs of search computations. With my script a db of 2^36 keys utilizes about 4GB. In that case I store 1 key each 128. It takes about 1 hour. And 128 computations are very fast for the 'search part'. And searching 64 bit --> shift 64 bit --> next 64 bit --> shift 64 bit should be faster than 64 bit -> shift 1 bit -> 64 bit (If I understand your script) |
|
|
|
I store every key, 2^25 keys, represented with a “0” or a “1”.
Ok, then you are using the idea of this thread.
But how does this help you do a search for a key?
What search would you run with this script?
The OPs (and my modified script) basically stores “wilds” a known pubkey’s offset keys.
And the search script can land in any key space, do 64 key computations, and find the key of the key is in that range.
The idea is: if you know that a public key P is in your db, of course you need only 64 key computations. The same for my script. ( I didn't write a script "search" so far, I made only a script to build the database as small as possible). Your idea: store a bit of any key
My idea: store several bits of some keysThe general case is: 1) I have a public keys P. I don't know the private key, but I know it is in range [1 - 2^64] (example). But this range is too big, I cant store or build a such huge database. There are 2 main possibilities: a) I generate a database of 2^32 public keys [from 1*G to 2^32*G] (baby steps) and I store all of them, then I compute P1 = P - 2^32*G and verify if it is in my db, otherwise I compute P2 = P - 2*(2^32*G) and so on (giant steps). This is baby-giant steps algorithm, about 2^32 computation but a huge size database. b) I generate a database of 2^32 public keys [from 1*G to 2^32*G], but I store only 1 key each 64 (to save space). Then I compute P1 = P - 2^32G and I verify if it is in my db. Now I have to perform 64 subtraction from P1: P1 - G, P1 - 2G, P3 - G , .... P3 - 64*G because P1 could be in interval [1*G -> (2^32)*G] but not in my db (I don't store all the keys). These 64 subtraction are the price we have to pay to have a smaller database. to be sure that P1 is or is not in the interval [1->2^32]. If P1 or the other 64 keys are not in my db, I compute P2 = P - 2*(2^32*G) and so on. |
|
|
|
Can you give me a concrete example of how or what keys you would store (making the filesize smaller) and how you could use it in a search?
My example to you is:
If I generate 2^25 keys in the database, it's size will be 16MB.
2^25 keys -> 16MB means : you store 4 bits for each key? 2^25 * 4 bits = 2^27 bits = 2^24 bytes = 16MB. Or you store only some keys? |
|
|
|
This script generates a database of 32 million keys (3.9 MB) in 3.5 seconds, it stores only 1 key each 64 keys, and only 8 bytes for each key #!/usr/bin/env python3
# 2023/Dec/03, arulbero_pub_key.py
import secp256k1 as ice
#############################################################################
# Set the number of public keys to generate and other parameters
#############################################################################
start_key = 1
num_public_keys = 32000000
bits_to_store = 64
bytes_to_store = bits_to_store//8
rate_of_key_to_generate = 64
rate_of_key_to_store = rate_of_key_to_generate
interval_to_generate = range(start_key,num_public_keys+1, rate_of_key_to_store)
interval_to_store = range(start_key,num_public_keys+1,rate_of_key_to_store)
binary_mode = 1
#private_keys = list(interval_to_generate)
#############################################################################
if (binary_mode == 1):
f = open("public_keys_database.bin", "wb") #binary mode
###########generation#################
public_keys=[]
for i in interval_to_generate: #generate the other keys
P = ice.scalar_multiplication(i)
public_keys.append(P[33-bytes_to_store:33].hex())
###########writing the db###############
for i in range(0,len(interval_to_store)):
h = int(public_keys[i],16)
f.write(h.to_bytes(bytes_to_store,byteorder='big'))
f.close()
else:
f = open("public_keys_database.txt", "w")
###########generation#################
public_keys=[]
for i in interval_to_generate:
P = ice.scalar_multiplication(i)
public_keys.append(P[33-bytes_to_store:33].hex())
###########writing the db###############
for i in range(0,len(interval_to_store)):
h = public_keys[i]
f.write(h)
f.close()
If you want to read the data, switch to "binary_mode = 0". With 2^32 keys (4 billions), it takes about 4 minutes to generates a db of 257 MB (1 key each 128 keys, 64 bits for key). |
|
|
|
|
Show Posts
