Topic: Ultra-Lightweight Database with Public Keys (for puzzle btc) (Read 1546 times)

It's absurd to debate with you bro, you are very ignorant, you say wrong things as facts, and you are boring.
Coincidentally, since you are a Kangaroo believer, you don't doubt that it was with Kangaroo and you give it as an irrefutable fact. Just because someone said it, what science you have.


You are ignorant, there may be 1000 ways to deal with this, it's not like I strictly have to use a lot of memory, simple answer, Alberto did it that way because it was the best for his approach.

I'm sure that one day, someone will reveal that they unlocked puzzle 130 with a different version of bsgs or something else and you'll say it's a lie.

We can never split 40 bits in two parts, such that none of the parts is higher or equal than half. The part that is the "space", no matter if big or small, needs to first be filled (using the respective amount of operations). It does not matter how well it is optimized, stored, scanned, or queried, the first thing that is required is that it needs to be created.

This is the issue OP refuses to understand, this sqrt(n) bound. He basically provides an idea that makes a good algorithm tens to hundreds of times slower than it should be (the higher the range, the bigger the slowdown), at the expense of lower used space, and highly increased amount of work.

If its about precomputing and reuse, oh well, precomputing that reduces the number of computations after every run can already be applied to basically any other algorithm as well, with better results and with much lower need for storage.

And yes it was confirmed #120 was solved using kangaroos. No one on Earth can stop someone from building an ASIC kangaroo that runs millions of times faster than any CPU, but also no one on Earth will ever be able to do the same with BSGS (they would also need to pretty much change the basics of how a computer works as well, to use an insanely huge amount of memory that doesn't even exist). Only a flat-earther like the OP would refuse to understand this indeed.

In my previous example I split 2^40 = 2^20 * 2^20

but you can split the same interval in this way: 2^40 = 2^22 (space) * 2^18 (time)

In my idea you do more work at precomputing the keys, but you store fewer keys (2^22 / 2^2 = 2^20 keys stored if there is a certain property with probability 1/4)

then you need to generate only 2^18 *2 = 2^19 keys (time) to retrieve the private key.

In this way I got : 2^20 (space) x 2^19 (time) = 2^39  (the constant is lower than 2^40)

You have to do more work to generate the DB, but then you need to do fewer calculations.

In general you can reduce 2^40 constant by a factor = (probability of a certain property in the entire 2^40 interval) / (frequency of the same property in a small interval, the interval of the precomputed keys)  

I'm not searching to break #135 key, I'm trying to optimize the search in small intervals (just for fun, to understand better how it works).

Don't worry, I understand my maths, this post is just an idea, don't take Kangaroo as a religion bro.
I've made a lot of progress with a group of friends (secretly), are you sure it was with Kangaroo? Be careful when pursuing your beliefs.

So what limit is that? The fact that #120 was just solved using "crazy fast kangaroos" doesn't help your case very much, it just proves again that they indeed work, exactly according to the math you're so much dismissing as "false". Let me see some BSGS solving any 90+ bits puzzle please. Without months of "building a database", as if that should not be  taken into account at all as "work".

false, once the limit is exceeded, kangaroo has no advantage, so it is worth the time spent generating the db. if you would use mathematical references to validate your claims, that would be great.
this is a method of improving scalability.
but hey, keep wasting your time with kangaroo, 3emi sends you his best wishes.

By the time you're doubling up on the amount of work (time) just to halve the required space, you're already far behind a different approach, which uses the same amount of time (work), but a constant amount of required space...

The costs of really wanting to get a 100% guaranteed deterministic solution does not scale from a point on, unfortunately. But getting a cheap probabilistic method to scale, and never finding it to NOT work, but still insisting it doesn't work, is like pretending that humanity can advance to a Type 4 civilization by tomorrow (possible? sure! likely? not so much!). It's more likely that something like that will happen, rather that a probabilistic algorithm to not find a solution. A probabilistic method is not like some lottery or whatever people may try to get an analogue to; it is unimaginable to actually find a counter-example that beats all odds.

The only way to reduce this constant would be to find a property satisfied with differenties probabilities in 2 sets:

the set of the keys stored (Space)
the set of the keys generated (Time)

For example, if you have to work in a 2^40 interval,

usually you have to precompute 2^20 keys to store (space)
and 2^20 keys at run time (time)
then 2^20 * 2^20 = 2^40

Now image you find a interval of 2^20 keys where a certain property occurs with probability 1/4 while the same property occurs with probability 1/2 in the rest  of the space (example: points with coordinates X lower than 0.5 * 2^256)

i.e. a set where a certain property occurs less frequently than the expected value.

You can store 2^20/2^2 = 2^18 keys, only the keys that satisfy such a property,

and then you need to generate 2^20 keys * 2 = 2^21 keys (on average you need to generate 2 keys at each step, because only 1 of 2 satisfies the property).

So: 2^18 (space) x 2^21 (time) = 2^39

But you have to find such property.


A way would be to perform a statistical analyse of (1*G, 2*G, 3*G, ...., 2^20*G) set.

Generate all the points, sort them by the x  coordinates;

on average you should get:

 more or less 1% in 0 more or less 1% in 0.01 ....

you select  the range where the actual percentual is minimal; maybe is 0.5% or 0.7% , but below 1%.

This is the property needed to reduce the set of keys to store more than the required increase in the number of calculations.

I think that if an algorithm does not directly depend on computing power and has a cumulative improvement efficiency (improves over time) after a certain time it will end up being more efficient than the rest.

Basically you need to rewrite all the code for this... I did my own approach and it was slower than my current bsgs version.

The Ultra-Lightweight Database version of (mcdouglasx) may solve the speed on bsgs, but it need to pre-process a lot of points near of 2^50 points just to get the same speed of my current version of BSGS on github. (such  pre-process task may need some months alone).

So extending my answer to your question, you need to understand the algorithm  mcdouglasx and rewrite the code, there is NO an easy way to do that, once that you edit that code, you need to pre-process the points up to 2^50 or something like that just to get the same speed of current keyhunt.

@mcdouglasx i watnt to write my toughts onthis topic, because it caused debate and friction between you and other users. I want to order my ideas and write here down for all of you. I am going to do that later.

How to create a baby table file (bPfile.bin) using your method here?
https://github.com/iceland2k14/bsgs/tree/main/v2_gmp

Ok, Digaran, bye, end of topic, "You won"

OK, I admit it, I am digaran! I only have one problem: I can't prove it.

Fuck all the research papers and all the mathematicians that dedicated their lives to them, and of course, even all the very practical software that proves you're full of non-sense and negate what is in front of your eyes. You live in your own reality, the one that broke the square-root bound (congrats on that) and I'm really impressed about how everyone managed to put in practice your ultra-lightweight DB. Or not, because it can't work the way you think it can, no matter if von Neumann himself rises up from the dead and takes a stab at it, because of the square root bound (5th time I mention it, since you probably didn't even looked it up what it means). You're lost, buddy. Buy a GPU, try out JLP's kangaroo, does it work 50x faster than your CPU, while using less power? If yes, than you have smth to meditate on for a while. Go read the CUDA introduction, look at the nice drawings on the first page, understand what transistors are used for, or the difference between a generic CPU vs dedicated computing units. Only then we can have a serious talk. No amount of storage optimizations will ever decrease the number of actual operations needed to solve a problem. You are looking in the wrong place.

Your theory is biased by your own interests, so please stop spamming here. Your theories without test models are just that: theories based on what you believe.

Sometimes, what seems logical in theory doesn’t always work in practice. This can be due to many factors, such as unconsidered variables, implementation errors, or simply because reality is more complex than anticipated.

Let me tell you a story about the arrogance of thinking you know everything and how it can lead to self-humiliation. When Marilyn vos Savant published her solution to the Monty Hall problem in 1990, she received a lot of criticism, especially from mathematicians and statisticians. More than 1,000 people with doctorates wrote to the magazine where she published her response to tell her she was wrong. Over time, her solution was accepted and became a classic example of how intuition can fail in probabilistic problems.

In short, you are only hindering research with your supposed theoretical intuitions without real scientific basis in practice. Respect the community. Of your five messages, all contain fallacies that do not represent reality because you speak from misinformation. That’s why you were so disliked when you used the name @digaran. Self-analyze, bro. If you find this topic useless, just ignore it.

You might as well be right. I started this off-topic with is a constant, so obviously if you use a ton of "space" then you need less "time" to solve the same problem.

This is valid no matter what algorithm you use. So I got it now - you want to store lots and lots of keys, in less space, maybe so more keys fit is fast memory (RAM?).

The fallacy in your logic is however this one: you are thinking only in terms of a system that actually uses memory in a fast way, and comparing two algorithms on this same system. In this case, the one that trades off more memory for less time is BSGS. I wish you good luck with that.

However, if we start comparing BSGS vs Kangaroo on a system that trades off slow/no memory with a lot more computing power, then what you find is that BSGS does not even apply (since memory is either really really slow, or non-existent), and an algorithm that is based on computing power alone, will always outperform it, simply because the amount of extra computing far surpasses any level of storage you optimized for, on a system with a low amount of computing power.

You lack long-term vision, I assure you that BSGS with a sufficiently large database in the future, would double your current speed with Kangaroo, and to surpass it you would have to double your computing power, on the contrary BSGS would only have to store more keys, this is the interesting point of this research, which is not limited to how much computing power you have, and I'm not saying that Kangaroo is not efficient, I'm just saying that it depends on the net computing power, which is already beginning to be seen as a stone in the shoe.


Did you know that to measure the height of a pole, you don't need to climb it, you calculate it just by measuring the portion of the shadow, that's how it works, but you keep giving these silly examples that don't reflect the reality of this.

I don't need to care how it works, but you fail to understand my question: does it help find a ECDLP solution faster than the sqrt bound?

It has zero relevance that you can store lots and lots of keys, if at the end of the day it only works based on EC scalar multiplications. I hope you do realize that Kangaroo requires only a small fixed amount of multiplications, that is, simply the number of kangaroos for initial setup, and everything else is simple additions, which are hundreds/thousands of times faster than a point multiply? And it can solve a key, on average, in around 1.71 sqrt(N) operations (by operation, I mean addition, not multiplication)? Which is a lot less than what BSGS requires? It has zero squat relevance how well you optimize the storage, because the first thing that matters is how many EC operations are performed, not how many trillions of keys you can scan as visited or not. Because first, those trillion keys need to be computed one way or the other

It's like drawing on a sheet some mountains and saying - here's the world's mountains, but you actually need to climb them, not looking at a pretty picture. These are totally separate levels of magnitude we are talking about. But anyway, you answered my question. Which is a no. Case closed.

You show that you do not know how this DB works(That's why I call you ignorant). When we talk about false positives, I am referring to the basic context of the test script that was done this way on purpose so as not to have to create a massive DB to test it, so "IT IS NOT PROBABILISTIC" although it could be, it would be a decision of the end user.


If you give a monkey infinite time typing randomly, at some point it will discover all the existing keys.
So this is not about strength and birthday paradoxes, this is beyond what kangaroo can do today.

Do you see me writing in JLP's post talking about databases? No, because that would be off-topic. That's what you do. You come here just to spam because you don't understand how it works. Contrary to what you say, "1 MB that takes forever to process." The DB is no longer inefficient as storage. If you understood before commenting, you wouldn't be treated as ignorant.

Yes, that is exactly what I said. More than that, you yourself admit your so called DB as having some whatever % probability of false positives, but at the same time (!) you argue about deterministic vs probabilistic methods, I mean really, WTF? I won't even mention again the non-sense about probability decay or whatever you called that thing you believe is happening when the interval size grows.

Ignorance is when you make claims without actually having anything to back them up with. So - do you know of any key that can't be solved by Kangaroo, if I show you that ANY public key you give me in some interval, I can break in sub-sqrt time, which proves you wrong? Would you say that using some 10 GB of helper data that can solve any key is worse or better than having a 1 MB file that takes forever to process, and isn't even as deterministic as you claim? For Kangaroo, we can simply add a false collision to a secondary table, which by itself makes it much more as a guarantee of never missing a true positive collision, unlike your super-tiny ultra lightweight bitmap.

I know what I’m doing and I know my approach and my limits. I’m not interested in breaking ECC. I know you are digaran (“your actions and opinions are admirable and those of others are worthless,” that’s your pseudo-scientific motto), but that doesn’t matter to me. We live in a free world, and there are faster methods without revealing. I reserved one since the beginning of the year, as I already mentioned, because I only need a more powerful PC. I didn’t think my life was going to take so many turns, but so it is. Starting over until the day comes, I’m not in a hurry because money is only a necessity. I will only feel the gratitude of victory before revealing it, while I share ideas that in the future I think will be useful. I only answer you to leave you without arguments and run away with some of these nonsense that more than arguments are from immature personalities.

What is your argument in the last message? This is not how you win debates; you only portray yourself.

Here you show your ignorance, are you saying that the size of the db is irrelevant in the context of the post made exclusively for that? Lol.

Let's cut straight to the chase: did you break the square root bound of finding a key in an interval? I am talking about the ECDLP problem in an interval.

If you did, congrats, I wait for the paper.

If you didn't (which is most likely) then we are definitely not on the same page, so engaging further in a discussion is useless, just like with COBRAS, since you didn't understand what the issues are. Shrinking some exakeys in a 1 KB file is not relevant to the subject.

Is it the same to use Kangaroo with 4 cores as with 12 cores? No, right? Because it is an algorithm that depends on computing power, which is limited (technology does not advance so quickly and the difficulty of the puzzles grows exponentially). That is, your probability decreases exponentially with time and the difficulty of the puzzle. It is not as you think that Kangaroo works better in higher ranges. If that were the case, 256 bits would be in danger. The correct thing to say is: Kangaroo is not useful in small ranges, and similarly, my database is not useful if you store small ranges of keys, because with this database its success rate grows over time without needing additional effort. I think that in the future this, along with BSGS, will be the most used, due to the advantages already described. You can even store random, sequential patterns and merge them with other databases shared by other users. I know it will take time, but my vision is towards the future.

Of course it's not magic. But what do you mean by this: "as the search space expands, its success rate deteriorates"? I'd say it's the other way around: having more pseudo-entropy increases the chances of a collision, because you have better uniformity, so the probabilities are allowed to behave closer and closer to the predicted "success rate". So this "success rate" as you call it is actually worse for smaller ranges, due to lower entropy.

If you throw a coin in the air 1.000.000 times there's a 99.99% chance the number of heads is in a very specific tight interval. If you throw it just 100 times, that confidence interval is a lot worse. Kangaroo will work in the same way, larger interval = higher confidence a solution can be found, otherwise the Universe is broken.

Perhaps your DB has only a very specific use-case: brute-force, which, while guaranteed, you might never live enough for it to finish, even if you count billions of trillions of keys per second. In contrast, do you know of an example of a private key that Kangaroo cannot find? Because I never encountered one. It's like trying to pin-point to a single atom in the Universe and stating "hey, look, this one can never be found this way" and discarding the algorithm as problematic because of this singular exception. While all the other atoms are part of a single DP "tree" into which they all merge into, at some point.

The B-tree is not a competitor here; the additional processing has nothing to do with the search speed in the database, which is fast enough. This is a different issue. As for Kangaroo, its problem is that it is probabilistic, and as the search space expands, its success rate deteriorates. You know very well that adding DPS doesn’t work like magic.

I guess the lesson here is that is always a constant!

A B-Tree is already scalable, fast, and doesn't require 128x more work for a single query. THAT is your competition here, not some "fixed amount of processing". Kangaroo et all can run concurrently on an unlimited number of computing devices, and use the one and same central DB. Which may not even need to be large at all, only adding a few DPs every now and then. However, those special values represent trillions of EC operations EACH.

Faster = Larger
Slower = Smaller

It is what my intuition tells me, that we should have a massive DB, to be more efficient than other algorithms, if only brute force is used:

Because Light DB is not a problem in terms of resource consumption once created by its structure.

This script interprets what would happen approximately when your DB is 200,000 times higher;

Assuming the case that your spered is 1mk/s:


I see it, for this point, in theory, it would be from x2 to x6 more efficient using light dB.

I mean the change from 0101 .. to 111 .., with 14 in length or more, this did not make a significant increase in the number
of patterns found, so the change does not affect the final size of the DB.

The dilemma is how long does it require having such a large database?
Apparently you don't need 200,000 times more to match performance.

I did some test with my laptop with an processor (11th Gen Intel(R) Core(TM) i5-1145G7 @ 2.60GHz)

I query 134217728 random values to the bloom filter already created.

Those 134 Million queries take 5.316306 seconds = 3.960956633090973e-8 seconds per item, so it is 39 Nano seconds per item
or a speed of 25 Million queries per second (25,246,426 queries/s)

Also mention that those 134 Million items give me 30 collision on the bloom filter (Possible false positives) those need to be handled:
- Checking next patter value in out sample if this exists
- Or checking the current item againts your Ultra-Lightweight Database

I also did a test creating keys and creating the bit array (not string)

So in my test i create 4* 2^33 keys ( 8589934592 ) and also create the bit array in the same time it takes 7100 seconds, that is an speed of 4839399 keys per second, but this was using 4 threads, so speed per core is 1,209,849 keys/s (Again the time include creating a bit array of the parity of the X value).

To for this CPU it would take near 0.165 seconds create the 200 thousand keys and their respective bit array. (This time don't include search of patterns or queries to bloom or database)




My previous test database was a database of 17 * 2**33 keys (146028888064)
So 200K times that number is 29205777612800000 keys that is great than 2**54
and that is just to get the same speed, or Am I wrong?


I hope my previous test give and idea of the expected speeds of the code already optimized for your Database:


What do you mean with this? What is the criteria for those  additional patterns ?

Can you elaborate a lite more?

About the size of 15 bits it is 2^15 = 32768 that means that in average you are going to find one match each 32768 keys

for each new item you have a probability of 1/(2**15) that is your pattern

So what is the probability of not finding a match in 200K items

P(NOT finding the item) = 1 - P(Finding the item)

P(NOT finding the item) = (1 - 1/(2**15)) = (2**15 - 1)/2**15

P(NOT finding the item in 200K) = ((2**15 - 1)/2**15 ) **  200000 = 0.002234

That is a probability of 0.2% that means that 2 of each 1000 sets of 200K keys will not find any match

I verified it as you indicate with repeated patterns 111 and 000 of length 15 or more. and it stays slightly the same in terms of elements and distances so you are right it is a more efficient approach.

I don't choose a fixed pattern "111111111111111" or a fixed length of 15 to minimize the risk of false positives, nor do I choose a shorter length because the DB would grow, and if it is longer than 15 you would have to use more computing power for the cost of a lighter DB.

Apparently the best approach is 14 or more in length with repeated patterns of 111 and 000, as you suggest.
In a quick test of 10 million keys, only 2 patterns exceeded the distance of 130 thousand keys, and only 3 additional patterns were stored with respect to the original.
which could reduce these 200 thousand keys in the search to a smaller cycle.


Yes, you store all the ones you find throughout the size of the db.

Additional to the extra 128 keys per query I also need to check 65 items to the bloom filter

Original it was to be 64 items but since I already calculate 65 different sets of possible items, from the 128 bits window:

1 to 64 - Item 1
2 to 65 - Item 2
3 to 66 - Item 3
...
64 to 127 - Item 64
65 to 128 - Item 65

Also 1/64 = 0.015625 that is 1.5% more process in this part, so One item extra would be not much noticeable, because bloom filter checks are faster than generate the keys




Yes the database should be at least 200K times great than current database.
And yes my current database can't exceeded the RAM amount that is the big limiting
(A lot of people ask me to use some NVme disk directly for this database instead the RAM,
In this case to compensate the different speed between RAM against Disk the database need to be x1000 times great.
so if you are using 128 GB of RAM, the NVme must be some like 128 TB)
But that is one topic apart



Yes definitely it can be added to BSGS, any method that can query if a public key is between 1 and M keys can be used for BSGS.

Yes also we can add your database to a bloom-filter or any other kind like XOR, Fuse filters.


Let me test and measure it, usually those filters have some constant time to query if the item is inside or not.

So we can pack your items like - Pattern:distance:something-else  (This is preferably in byte formats than strings)



Question here... why we don't limited the search to some easy pattern to recognize like 0000000000000000 or 1111111111111111
To be more efficient those should be stored as bit and some of them may be easily to search from the CPU point of view you know (ANDs ORs and bitshifts)



I think that once that you chose some specific pattern you should store all the matches that exists in your DB no?
Because if we don't store some matches then we may have some missing gaps and hence missing keys (HITS)


That size of 130kb is because the length of the strings that you are storing?

I think that a data structure should use less space but that is something that can be optimized later

Yes, in 50,100, 150 I'm talking about thousands.

Focusing on your tests with your approach:

original bsgs 1,073,741,824 keys stored

new bsgs 146,028,888,064 keys stored

dividing 146,028,888,064 by 128 is 1,140,850,688.

I think you would have to be able to process more keys in the same time frame.
and that's why it becomes slower because of all the processes that involve the 128 additional processes.
to equal efficiency.

In this db 146,028,888,064 fit in less than 20mb

In my database with 120 million elements, the sequence rarely exceeds
200,000 keys between patterns. This suggests that 200,000 can be an average maximum value for key cycles and
the way patterns are packed allows saving large amounts of keys or their benchmarks, which is efficient in terms of storage
unlike methods with fixed computing power like Kangaroo, we can keep moving forward by adding more keys to the database
and gain a significant advantage in terms of scalability.

We can also create an additional mini database with subtractions and additions to your target and have each of those pubs calculate certain amounts of keys and patterns join to the main database.

Example:

pub-a -13636775

pub-b +1368754

if the pattern is found and you get pub-a, you add 13636775 and you get the target pk.

if the pattern is found and you get pub-b, you subtract 1368754 and you get the target pk.


then you could have multiple reference points along the range which improves
the search system.


logic tells me that to achieve a favorable average for this database you should
be able to store more than 200k times the number of keys(I'm not entirely sure) that your current
database can handle (which in terms of space with this db is possible because in this
database 200k times more is not a significant increase compared to your current db)

but on the other hand in theory, there would come a point where the cost of 200k keys
would be profitable because you would only have to exceed the limit of equivalence in effort.

Now the complex thing is, what is the limit of patterns to store? I know that with Python it is
approximately 130kb for 120 million keys in a little more than 3 thousand elements.

What algorithm can this be integrated into? In a filter, how many searches can you do
per second on average? Can it be part of bsgs?

I would have to investigate what would be the most efficient way, because it is linked to how big
the database is, so will your speed.

In the end this database is related to scalability, and I think the barrier of added effort can be broken and improvements can be seen.

Now I get your idea.


150 , 100 , 50.  Thousands, right?

Here is what I understand

Your Ultra-Lightweight Database is more like a reference for some Patterns and their offsets related to next pattern right?

So each time that we need to query if some Random Key X is in our database we need to calculate some 50K to 200K Keys next to our target and looking for those Patterns

If some Patterns match with out database (Pattern and offset against other patterns in our database), we can easily calculate the value of that X Key.

As far I see to get this database of distances and patterns small you are paying with more process to find those matches.


You need a point of comparation, also you need to calculate what is the point where your approach is better than exising methods.

For example, in the test that I send to you using my approach, bloom filter + BSGS the speed was near 16 Petakeys/s ( 15,904,076,907,774,986 keys/s) Using 8GB or RAM

But the current version of keyhunt did 26 Petakeys/s with 4GB of RAM, if I use 8 like the other Test it would do some 50 Petakeys/s

And my program is slow compared it against the kangaroo (kTimesG's version) for CPU than can solve keys under 80 bits in 1 minute.

So I think that we need to calculate how many keys do you  need to have in your database just to become competitive against the existing tools.

First thinks that you need to do is measure how many time a CPU or GPU can calculate the 200K keys sequentially and search for the patterns.
And then calculate how many keys need the database to reach some Exakey/s, Zettakeys/s o Yottakey/s.

One good think Good about your approach is that the database can grows on demand you only need to keep calculating keys and search the patterns once that you found one just append it to the DB.

To be honest I think that It would be difficult beat to kangaroo but with enough DB it may be possible.

Lets do some calculation:

(2**80) / 60 seconds = 20148763660243819578436

Suppose that you take 1 Second in determine if the pattern is in our database or not

That would mean that you need a database with at least 20148763660243819578436 elements

>>> 2**75  <=  20148763660243819578436
False
>>> 2**74  <=  20148763660243819578436
True


So its something between 2**75 and 2**74, well those are just rounded numbers real database maybe near 2^70 or something low
But one thing comes to my mind, we can't solve a 2^65 with  pure brute-force alone.

How you plan to build a database that rounds the 2^60 items to compete against kangaroo.

If we have enough computer power to build a 2^60 or 2^70 database we may have some chances to be able to try something against 135.

Well those are just round numbers that comes to my mind in this moment.

Well Yes I did it, in my previous example that was done. Since almost all the times those 128 items need to be calculated, I calculate all those keys and generate all the array of 64 items all of them of 64 bits, then I proceed to check them against the bloom filter.

---

Thank you for your example actually that is what i want to ask next, let me check and analyze it, to see what i can do.

Maybe it would be more efficient to create a sliding window type variable where for example you calculate from 1-64 keys, and from there on you only calculate one more key and the bits in the window move to 2-65 and so on consecutively for the duration of your sequence?



The patterns in this database are sequences of 010101… or 101010… of length 15 or more.

Suppose:


Process:

Initial target: pk = 1,000,000

Consecutive subtractions: 1 is subtracted consecutively 200,000 times.

Concatenation: These values ​​are concatenated using 1 bit per key, creating a string of 200,000 bits.


Example for Db:

First pattern:

Start position of pattern (Bi): 10 (bits to pattern)

Pattern found (Pp): 010101010101010 (15 bits)

Bits to end of pattern (Tb): 25



Bi: 10, Pp: 010101010101010, Tb: 25



Second pattern:


position of pattern (Bi): 150,000 - 25 = 149,975

Pattern found (Pp): 01010101010101010 (17 bits)

Bits to end of pattern (Tb): 150,017



Bi: 149,975, Pp: 01010101010101010, Tb: 150,017



Database storage:


if we use xor, we must store this "Bi: 10, Pp: 010101010101010" as an item in the filter, and when found return Tb value "25".


Search script:



Generating a random point: Example pk = 999,997



Creating a bit string: From the random point, the subtractions are generated just like in the database.


Pattern search:


First pattern:

Start position of pattern (Bi): 7

Pattern found (Pp): 010101010101010 (15 bits)


We do not include Tb here because it is not necessary in the search.
Although Tb is not necessary for comparison in db, it is used in the calculation of the private key, keep your calculation in the code.

Bi: 7, Pp: 010101010101010


Second pattern:


Start position of pattern (Bi): 149,975

Pattern found (Pp): 01010101010101010 (17 bits)


Bi: 149,975, Pp: 01010101010101010



Database search: The last pattern found is searched.


Bi: 149,975, Pp: 01010101010101010



Match found:


return Tb: 150,017



Key calculation:

random_point - total_bits + Tb_in_db

(999,997 - 150,014 + 150,017) = 1,000,000



Sometimes there can be false positives but you ignore them by creating the pub for the obtained pk and comparing it with the target.

Considerations to avoid false positives:

Search cycles: You should search for cycles of 250,000 keys to cover the entire database with a very low margin of error, but you can explore with fewer keys: 150 , 100 , 50.

Storage capacity: 12 billion keys can be stored in a little more than 300,000 elements in your database or XOR filter with an incredibly low weight.

Speed: example; If you do 4 cycles per second, you will have 12,000,000,000 * 4 / Ks. By increasing the database, you will have even more speed.

I am not masking any bits, Lets to put an example of what am I doing.

I have 2 files:
- Your database (1 bit per public key in DISK)
- The bloom filter (for fast query in RAM)


Lets to show some data

That is just the binary string representation but internally in the program I just use 64 bit integer variables without any output format.

So I group those 64 keys in a single variable and that is the value that I send to the bloom filter to Initialize and construct it, each of those items need near 29 bits inside of the bloom filter.
I don't have any problem building the bloom filter or querying it to check if some value exist or not.

The problem is that we are looking for some unknown public key and we don't know its original value, so we don't know if that keys is aligned properly to our sequence.

for example in the BSGS algorithm you need to do some subtractions to the target key and check each of those results against your database.
So since we cannot do an exhaustive search in our Ultra-Lightweight Database because it need a lot of time in databases of some Hundred of Gigabytes.

I opted to use the bloom filter for fast search.

Each time that I need to query in the bloom filter I need to generate a 64 bit keys based on the publickey for example lets to said that our publickey result is 2 (Privatekey 2)
In this case i need to group keys from 2 to 65, the 64 bit generated is 1110001011000000001101000101001111111111111110100111111011001011 (Less significant on the left) if I query this value against the bloom filter it is going to return false.

So i need to check the next sequences until one is found or until reach 64 keys more


I have a method to handle false positives HITs and a method to determine the value of the target key based on some binary search with multiple queries to the bloom filter.

In fact for each key that i need check in the  bloom filer i need to calculate the next 128 keys just to get the correct sequences and guaranty that at least one of those must be properly aligned to our bloom filter items.

As i mention before in other posts I've thinking and rethinking about different approach to handle this database, fast searches and collisions, this previous example is the best way that I reached.

So if you or anyone have a faster way to do it efficiently please show us

(Again I am using my custom way to handle the database because I don't understand how your way works, all the Pp, Bi, Tb stuff I don't get it)

Be careful with masking the bits; this shouldn’t happen because even if you perform 64 more calculations (I suppose), the final total should at least have double the speed in the worst-case scenario.

I don't get offended by that, i am not a snowflake. I just wonder why if this topic about solving puzzles is annoying for some users why they bother in create new accounts just to make those comments.

Anyway, I am implementing this new approach just to check what is the new speed.
I believe that a laptop with 8 of RAM may be able to solve any key under 75 bits in a few seconds or minutes.

---

OK guys, I already completed and tested a BSGS version with this database but the results are not good as expected (But this is a first approach), let me summarize the results, I tested this against puzzle 66 public key in my laptop ( 11th Gen Intel(R) Core(TM) i5-1145G7 @ 2.60GHz with 16 RAM Physically )

17 GB of this database can store (17 * 2^33) items, in this case 146,028,888,064 (146 Billion keys) those stored in a bloom filter only need ~8GB of RAM
This test solve the key in ~10 Minutes

But the regular version of keyhunt with only 4GB of RAM used and only 1,073,741,824 keys stored (1 Billion keys) in the bloom filter only need 6 Minutes to solve it in the same hardware.
So that means that keyhunt with 8GB of RAM used will solve that same publickey in 3 minutes.

I have some screenshots that i want to share with mcdouglasx, also i am sharing the first code with him.

Not all is lost I figure it how to change some calculations and maybe win some  x2 or x4 times more speed with this Ultra-Lightweight Database.

I said that not all is lost because regardless than the new approach need some x64 times more processor to prepare some data to be checked, the final speed is not x64 times less, but only x4 times less, so if I implement a new approach at least i think that the speed can be the same o a little faster.

There are other options apart from bloom filters, there are some XOR filters and some fuse filters, those are supposedly using less data than a bloom filter, this may allow to store more items in the same RAM and speed up BSGS in general.

So I still have hope in this database.

Regards!

This is the idea of one database... there is not one complete script yet..

But to be honest I don't know what are your intentions here, are you coming here to make fun of us?

Quete from another topic:

I have added 3 new files, aggregate custom xor filter to 8 bytes because this database does not need many elements
and I think that it is not so likely false collisions, in the same way the false positives would be ignored in the script when
comparing with the target, Use Blake2 that is an efficient and fast hash for this task and is slightly lighter than using the
PATT_DB.txt.

Blake3 would make a notable difference?

https://github.com/Mcdouglas-X/Private-Key-Search-and-Ultra-Lightweight-Database-with-Public-Keys

This script is only an idea with a basic implementation, although you can do it, it does not guarantee the right speed, wait for Alberto and its own implementation in Keyhunt, or if you have knowledge in programming implement it yourself in C.

Can this script be used in any puzzler that has the pubkey revealed or does it only work in a specific bit wallet?

i`m realy sad for that you not the one 
and i keep my eye on this topic "Ultra-Lightweight Database with Public Keys" and waiting for the new implementation

I truly believe that you are on the right track, managing more keys in BSGS keyhunt is, without a doubt, the path to important progress on this topic.

Great

Sadly no, I wan't that lucky person.

By the way guys please keep this in topic for "Ultra-Lightweight Database with Public Keys"

I am finishing my code for this database with my own approach  (64 keys grouped in a 64 bits integer and each 64bit integer stored in a bloom filter using only 29 bits per item), since BSGS Speed depends on the total items stored in the database first tests looks promising.

Since i am not implementing the same approach/code of mcdouglasx i thing that I am going to open a new Topic for this, but all the credits of the bit database (1 bit per public keys) goes to him. Also I am donating to him.

tell me that you who get the 130 puzzle "tell me "

Then we are on the "search way", we do work what not get result asap, but , maybe  something was finded, for ex , my result 2^30 for 12191606 operations  but, this is mach slover then BSGS, probably  you find something similar too..... have a good day.

Well, I do what I can with what I have at my disposal.

@albertobsd


how many pubkeys you archives



2^64 ? 2^64 is anoth for find 2^130 bit priv ?


i find answers you archive 2^43 pubkeys. this is not anith for get privkey, need brute  2^87 range. I thin you know this, yes ?

I am storing up to 1 TB of binary data: 8.7 trillions of keys: 8796093022208.

This amout of bits grouped and stored in a bloom filter may need only 480 GB.

But stored in a Xor filter it will use only near 256 GB so i am trying everything to compact it more and try to use better methods to the search of collisions and search of the offset of the keys.

I hope for good results! In the case of this specific database, I would create a custom XOR filter. Since I only need the total bits (Tb) value of each line in the database, I would configure XOR to return the necessary value according to the line found. However, since I don’t think this PC will ever handle a 10MB database, I haven’t given it much thought.

I am implementing this datababase ( 1 bit per publickey ) i am grouping those in a 64 bits item and storing those 64bit integers in a Bloom filter for fast search, those need 29 bits per each 64 keys i think this will give more speed to the BSGS algorithm.

If the speed is boosted by this method i am going to change the bloom filter for a XOR filter becuae i believe that it may need only 16 bits per each item of 64 bits ( This mean that each group of 64 publickeys can be stored in a 16 bits)

The idea behind this database 1 item per bit might be some dubious because you need to some extra process to perform a search in the database, for example in my case, before this approach you only need to do a single subtraction (public key subtraction) and the compate it to the database, but now you need to do the original subtraction and then with that keys you need to contruct a item to compare in your database (bloom filter / short filter/ list / whatever) so you need to calculate other set of keys in order to be able to compare against your current database this mean thay you need more process. And not only 64 times more process you need more items to compare because you don't know if your target public keys is aligned with your current groups of keys.

So i am testing this just to validate what speed i am going to have, I am working a the very low bit level with bit shift operations and I think that my current approach is the most efficient from the CPU point ot view. I am not using any string conversion so i think there should be a point where this database will be useful

It is a bit by pairs and odd public keys, that is, the patterns are pubkeys sequences, in the code this can be seen.

Bro, you talk about first bits of pubkeys in your patterns, or patterns in privkeys ?

The patterns I choose them like this to guarantee a balance between the weight of the DB and the search speed, but you can experiment with it. Whenever the same changes in both scripts are made, there will be no problems with PK calculations.

Here:pk = (Rand - total_bits + Tb_in_t)-len(pattern)
Then, a check is made, to avoid false positives.


I really publish my ideas at your most basic point, so it is better understood.

Have you considered using XOR filters?

Great,Im also try use bit patterns.

why only this patters

Bi: 13806, Pp: 010101010101010, Tb: 13821

Bi: 10889, Pp: 101010101010101, Tb: 24725

Bi: 10637, Pp: 101010101010101, Tb: 35377

Bi: 186843, Pp: 010101010101010, Tb: 222235

were is

011011011
1001001

 ?

bro, how you calc from so little examples of bits (only 4 patterns)  fool privkey range ?

thx

yes, A Bloom filter is a probabilistic data structure used to test whether an element is present in a set. However, it does not store the elements themselves, but instead uses a series of hash functions to determine the presence of an element. Because of this, it is not possible to extract specific data, such as numbers, directly from a Bloom filter.
That's why I say this is a database, you can access and reuse the data.

Are you sure it's a lightweight database? More like a Bloom filter, but secp256k1 is used instead of xxhash/murmurhash/etc.

https://github.com/Mcdouglas-X/Private-Key-Search-and-Ultra-Lightweight-Database-with-Public-Keys


This project implements a database designed to store interleaved bit patterns (010101...) of 15 bits or more in length.

These patterns (Pp) are stored along with the number of public keys between patterns (Bi) and the total

bits traversed to the end of each pattern (Tb).


requirements:

secp256k1

https://github.com/iceland2k14/secp256k1

Database Structure

The database stores data in the following format:


This format allows the representation of thousands of public keys to be stored in just a few lines, making the database lightweight and easy to manage.

With my previous implementation 120 million keys fit into a 14 MB file and now the same keys are represented in a 165 KB file. Therefore, the file has been reduced by approximately 98.82%.


Search Functionality

To find matches, the search script processes between 10,000 and 250,000 public keys per cycle (low_m). You can configure this value at your discretion;
100,000 is recommended, as it is the average number of keys between patterns.

For example, if there are 50,000 public keys between pattern A and pattern B, starting at an intermediate point between both patterns will easily lead you
to the next pattern, and the script will calculate your private key.


Performance

The speed of the search depends on the size of your database. For instance, if you have a database of 100 million keys and your computer processes 1 million
keys per second, you would be processing around 1 billion keys per second.

Implementation Notes

This project is an implementation of an idea and is not optimized for speed or efficiency. You can create your own implementation in C.

You can reduce the minimum pattern length in database, which in turn could reduce low_m, resulting in faster search cycles and a larger database cost.

I have left the test database on github, if you just want to test the script.

At the moment, I don't have the computational resources to integrate into the world of GPUs and CPUs in C  .