lightweight database, for brute force using publickeys-32Mk =3.81MB(secp256k1)

[WanderingPhilospher]

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 range

1 key each 2^20 (1 million)

time to generate the DB: 0.060 s
size of DB: 32kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^36 range

1 key each 2^20 (1 million)

time to generate the DB: 0.5 s
size of DB: 512kB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^40 range

1 key each 2^20 (1 million)

time to generate the DB: 7.3 s
size of DB: 8 MB

max time to find the private key : less than 2 seconds.
-------------------------------------------------------------------------------
2^44 interval

1 key each 2^20 (1 million)

time to generate the DB: 2 m
size of DB: 129 MB

max time to find the private key : less than 4 seconds.
-------------------------------------------------------------------------------
2^44 range

1 key each 2^24 (16 millions)

time to generate the DB: 7.3 s
size of DB: 8 MB

max 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)

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?

[arulbero]

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.

[COBRAS]

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.

publick you scrypts pls ?

[WanderingPhilospher]

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.

[arulbero]

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.

[sssergy2705]

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 key is better than 64bits for 2^32/2^20 = 2^12 keys.

Less size, less search time, 100% keys found.

The first version of the script worked, the second does not find matches.
There may be an error in the code.

[arulbero]

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?

[sssergy2705]

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.

[arulbero]

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

[WanderingPhilospher]

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.

[arulbero]

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?

[WanderingPhilospher]

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).

[arulbero]

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.

[WanderingPhilospher]

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.

Imagine running Kangaroo with DP 0 and space wasn’t an issue.

[arulbero]

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.

[WanderingPhilospher]

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.

[arulbero]

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?

[ecdsa123]

@WanderingPhilospher:


I think is the time to publish your modification script for creating database and for seeking in database.

I think -> to better optimised you need use mmap library

in 2 GB files I have up to 2 seconds for "finding the str"

[WanderingPhilospher]

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?
No, not necessarily. I have other ideas how to check for collisions that doesn't require a check every step; but it would work.

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?

During creation of Dbs;
pubkey - create
pubkey - some random number - create
pubkey - some random number again - create
..........
pubkey - some random number again - create

While each create is evenly spaced, we have several creations (could be hundreds or thousands, it's unlimited)

I am trying to think of ways to lessen the space trade off of traditional kangaroo, that's all. I'm sure you have ideas.

[WanderingPhilospher]

@WanderingPhilospher:


I think is the time to publish your modification script for creating database and for seeking in database.

I think -> to better optimised you need use mmap library

in 2 GB files I have up to 2 seconds for "finding the str"

Mine is only different from the OPs in that I don't use the BitArray, I stick to bytes.
Tradeoff, my DB is 4 times as large, but search is faster.

mmap increases search time?

With a 2GB DB file, I could find a key in less than a second (in the smaller ranges we've been discussing here)
I have a Db that is 488MB that contains 1,000,000,000 keys; that means I can check an entire 2^29.89 range in less than a second.
So at 2GB (roughly) 4 times that speed, so a 2^31.89 range checked in less than a second.