Quote from: kTimesG on Today at 07:30:31 PM

Quote from: farou9 on Today at 05:07:57 PM

So what is the fastest method to lookup in the 2**30 ,or in another words what should we store them in to get the fastest lookup possible

You already have the answers. The fastest method is unfeasible, because not enough RAM exists in the Universe. The best you can get on this planet, in 2025, is to use a hash table, to get a logN lookup time.

You can speed that up moderately by binning the key prefixes into a sparse array. For 2**30 keys, the expectation (average) is to have a single entry for every possible combination of the first 30 bits of the key.

So build a 2**30 array with constant-size values, to be able to do a O(1) lookup in the first phase.

Since inevitably some items will have 2, 3, 4, or more suffixes, you need to use a pointer to the list of suffixes and their values. Assuming all the data was precomputed already, this can be kept in a compact bitmap.

Let's see how much data all of these would consume:

We have 2**30 prefixes array items, each using:
   - 30 bits for prefix
   - 30 bits for bitmap data pointer
   - number of items in bitmap (let's say this is a "max length" integer, 4 bits to allow up to 16 entries)
We have 2**30 suffixes, each having (256 - 30) bits.
We have 2**30 values to store (consecutive private keys, with a known base offset), each using 30 bits.

O(1) lookup array will need 64 * 2**30 bits = 8192 MB

For the bitmap data: a single entry in the compact bitmap requires 226 + 30 = 256 bits.
Total data size: 256 * 2**30 bits = 32 GB

Lookup algorithm (2-phases: O(1) for first phase, 16 steps worst case for second phase):

// Phase 1
prefix = publicKey >> 226. // reduce key to 30 bits
dataPtr = prefixes[prefix]
if dataPtr == 0 // key not found
   return
// Phase 2
for item in data[dataPtr]:
   if item.suffix != publicKeySuffix:
   continue // key does not match
   // key matches
   return item.value // return private key
// if we get here, no suffix matched, so key is not found

There, this ideally uses 40 GB for everything. Not far from my original estimates.

In practice, it's gonna use more memory since it's much much faster to work with aligned units, like bytes and 64-bit addresses. This example is just an abstraction of a best-effort "fast lookup" for what you asked.

Ok fast lookup is a lost cause then ,
So how does bsgs work ,doesn't it need to store sqrt of the space to make sqrt of space speed ,right?