PointsBuilder a speedy CPU range points generator

Hey everyone! I created a C library and a demo app that shows how libsecp256k1 can be utilized for super fast batch addition and scanning through a specified range from start to end. The resulting affine points can be streamed and processed with callbacks, or you can just use it as a basic tool to test your CPU's performance. How does it work? - Provide a range start, size, and how many threads you want to use. The rest is just magic! You only need two EC point multiplications. For instance, if you want to generate all the first 1 billion points starting from a scalar k (using only 64 bits for this demo) and do it with 64 threads, you’ll only need those two initial point multiplications! The code calculates a constant array of points, incrementing by G. Batch addition is then done directly using the secp256k1 arithmetic. My batch addition implementation is really optimized it’s not the typical algorithm that you might have seen around. The purpose of this demo is to show that it runs incredibly FAST based on my tests, it’s at least twice as fast as various other options you might come across, especially those seen in most VanitySearch projects and similar ones. Also, the demo supports saving the X coordinates to a database, but that’s not the main goal of the code. You can do basic benchmarks without actually specifying a database for storing results (because saving them is way slower than calculating them in RAM). Just an important note I forgot to include in the GitHub README:

nomachine will miss fishing for a few hours/days breaking this code down

And results on extremely week Ryzen 7 5800H: root@DESKTOP-BD9V01U:/mnt/e/vm/Cyclone/secp256k1# ./bench_step510 Threads : 16 Keys/s  : 42.63 M Scalar  : 00000000000000000000000000000000000000000000000000000000061772d0 PubKey  : 03c6ab40b70a67ff7b8b6fc7dcaebef25433dfe741ba193baabc822eea01e9a53c I’m a little bit faster:) Ryzen 5800H slower than your i9 - 45%-50% And by the way, did you try to use RELIC? I think that it will be faster than libsecp256k1. And also I have a secp library with point add speed -300Mkey/s on 7945HX CPU

I'm not sure I understand what you mean, or what your code does, or how does it relate to what is being discussed. The point of this library is to actually generate ALL the affine points in a given interval. I'm not seeing exactly what yours does though.

Thanks for the code ! Only got the chance to read it quickly on phone for now. Is there anything other than batch inverse and +- from a central point ? I think I have a version of my OpenCL code somewhere which does something similar, I’ll run benchmarks on my 7950X to see how it compares.

You're welcome. Yes, the inversion tree is non-serial, which allows SIMD compiler optimizations, to have the field multiplications computed in parallel (as in, the low-level arithmetic can be vectorized), which makes it faster to build and decompose the tree into the inverses. Other than these, it's basically just a CPU emulation of how a CUDA grid behaves: set some starting points, and advance the middle points after each launch. During each launch, each thread / pivot does a bunch of batched additions and stores results. At the end of the batch, the last point for which the inverse is computed, is the jump point for the pivot's next position. This makes the code 2x shorter in length. This uses the least possible amount of ECC field operations. Jacobian code shown above cannot possibly be faster, it would require conversion back to affine, which is slower even if also optimized (I have a version that does optimized Jacobian-based range covering too, but it was around 4 times slower because of all the extra field operations).

Thanks for the code ! I'll try to give you some ideas that maybe can help you improve it further. I was looking at void batch_addition. I attach below your logic, it is not the code of course, I just took the comments to explain better: I think you could save some operation by precomputing neg(x1) out of the loop and at each iteration calculating A=(-x1-x2) since you use this value for both P+Q and P-Q. I'll try to show you, I hope you can understand it: This way, you should be able to save batch_size additions and 3*batch_size-1 negations. I know it's not a lot in the end, but it should still be a bit more efficient. When I implemented this in my CUDA kernel, I did notice a slight speedup. Maybe it won't make any real difference in practice, but as soon as I have more time, I'll try to implement it in your code

You're totally correct - perfect observation. The const points should simply have a negated X. And yeah, this speeds up things in CUDA as well. Sometime very small things like this can bring a few percent of extra speed. I also forgot to use -march=native to actually benefit from CPU native instructions. Will fix today.

Nah. I'm already stuck in other scripts.

What is the main purpose of the code. How does it store the X points exactly ?

Fast points generation of a full range. You can see how the affine X coordinate is saved in db.c - what is unclear? The X bytes get stored into an index (little-endian bytes), and the key offset (from 0) as an integer value. This is what you wanted, no? If you want it saved another way, just adapt the code, and support the inevitable slowdowns.

So they are all stored in 1 file ? And how do I run it ,i can deal with c++ and py but c I have no idea how that works

Compile it and run it according to the README maybe. You can do what you want with the database afterwards, as long as you interpret the values as offsets to the base key of the range. The code seems stable, looks like the only cases where results are wrong if you give it a range start that equals 512 (or N - 1534). I'll add some checks for these two edge cases. So you're good if you want to dump keys from 1 to 1.000.000.000 But you have to disable the check in main.c to do that, for now. As for your first question: yes it dumps data into a database. I have a feeling you want something that can dump 1 billion points to disk instantly. However this code streams keys in non-sequential order, because of how the ranges are scanned in parallel. I'm not aware of anything faster than an actual database if you really want the X values indexed in order to be able to later query it to get the scalar. The only thing that's faster is to not use a database and work in RAM.

I made this mod to a separate branch to get rid of the ops you mentioned: - store - x1 - x2 - pre-compute negated x2 The speed fluctuates so often between runs, that it's hard to tell a difference.

But the question is what is structure of the database if its 1 file there is no advantage for lookup . So they are stored randomly. Well that much ram is expensive.

Oh well, if a searchable X-coordinate indexed structure such as the B*-tree of an SQLite 1-file only database table having the X bytes as a primary key (and no rowid indexing overhead) has "no advantage for lookup", I don't really know what does. Maybe dumping into tens of thousands of text files and doing linear searches. That sounds ideal! You're free to do what you want with the generated points though. Storing them all to disk is not exactly optimal, no matter how you do it. That's why maybe you should not do it at all, unless you want a 10.000x slowdown in general when planning to actually use the points without having all of them loaded in RAM.

how much ram do we need to store 2^30 points ,and what gpu or gpus do we need to maintain the speed of operations and lookup to be instant , like if our gpu can make 10^9 scalars ops per second how can maintain that speed and their lookup

There is no known algorithm that can lookup a non-linear key, in a dictionary structure, in instant (O(1)) time. A tree data structure retrieves keys and data in log(numKeys) steps (for example, 30 steps on average / worst-case, to find a value in a binary tree with 2**30 keys, depending on the type of the data structure). B-Trees (used by SQLite) can do it even faster, since a node can have hundreds of direct children. This is why you're most likely better off with storing such a DB on disk, and letting the DBMS take care of what's cached in RAM. Ofcourse, a bloom filter can take care of fast filtering such a lookup before it's needed. The only way to know how much RAM is needed is to compute and store the table, because you can't know in advance the total entropy of all those keys, so it may require more or less space, depending on the clustering density of the key indexing (same prefix bytes = less used memory), and the data structure used for the lookup. Anyway, for 2**30 256-bit keys, each storing a 64-bit integer, you'd need around 40 - 50 GB at the minimum. Running a lookup tree on a GPU spells trouble. Even if doable, the memory latency will kill any sort of performance. GPUs are compute devices, while lookups are a memory-intensive operation.

ok let say we have 60gb ram , and we computed the 2**30 x points in the ram will the lookup be instant (O(1)) ? i have this algorithm that can solve puzzle 58 in (1/3)sqrt of the steps needed for bsgs to solve it but we need to the 2**30 DB , the algorithm is little bit nonsense but it worked but if we cant lookup up in instant o1 its not practical

It won't be instant, because the keys are dispersed in range 1 to 2**256, so, as I already mentioned, this requires a dictionary data structure (map, tree, hash table, database are such examples). The only way to have a O(1) lookup is, by basic principles, to know exactly the location that needs to be read. Since you have 2**30 keys, and each key is 256 bits, a truly O(1) lookup requires 2**256 * (sizeOfAssociatedValue) bytes, in order to do a direct O(1) lookup of any 256-bit key. You will have 2**30 locations that have an associated value, and (2**256 - 2**30) locations that are wasting space for nothing. But it is O(1) in complexity. That's why other data structures like trees / maps / hash tables / storage databases are optimal: they are the perfect balance between minimizing storage and minimizing complexity down from O(n) to O(logN). O(1) is only practical if there is enough spare memory to keep all possible keys. There are only around 2**70 bytes in all storage devices ever manufactured on Earth, so do you get the picture now?