An idea for increasing speed

[ghost]

Hi albertobsd!
There is an idea how to speed up the search for a given range in Keyhunt.
I had a hypothesis
Example: time ./keyhunt -m bsgs -t 6 -f tests/in.txt -r 49dccfd96dc5df56487436f5a1b18c4f5d340000000000000000000000000000:49dccfd96dc5df56487436f5a1b18c4f5d34ffffffffffffffffffffffffffff
In a sequential search, you will often find 4,5,6,7,8 ... of the same characters in succession.
I studied almost all private keys on which there were coins, none of which has 4 or more symbols in succession. There are exceptions when you manually create an address from a private key.

As in the English language, not words in which 4 identical letters go in succession.

An example of identical symbols:
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5aaaaa000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000077770000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e00000ffffff00000
If we assume that here the last a is equal to the month of the search
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5aaa**[a]**a000000000000
Then it turns out this month wasted.
If you remove all the same symbols, the speed will increase symmetrically.
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5eeee0000000000000 all keys after eeee are invalid.
(eeee0000000000000->eeeefffffffffffff)
Other examples:
FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFE BAAE DCE6 AF48 A03B BFD2 5E8C D036 4141 all keys after FFFF are invalid.
7777 FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF all keys after 7777 are invalid.
1234 1111 FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF all keys after 1111 are invalid.

1234 5111 1FFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF FFFF all keys after 1111 are invalid.
What I suggest:
Search the private keys variable for identical symbols and replace them with +1.
Example: 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5aaaaa000000000000 change aaa to aab total search speed × 2.
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5aaaba000000000001
I know that an additional search for identical characters (prefixes) may reduce the speed by ~ 5-10%
The total travel time will be less by -30-50%.
I tried to implement this in LostCoins there is multithreading, GPU, I didn't have enough C++ knowledge.

You can output the range 1- ffffffff to a file and see how many times 3,4,5,6,7... characters were dropped in a row.
If you increase the range, the same ones will drop out symmetrically more often + intermediate ones. BitCoinCore randomizes private keys, there are almost no identical symbols in a row in random.

As far as I understand, the keyhunt algorithm creates bloom filters from hexadecimal data hashes for a private key. If we remove all incorrect values from the filter in which there are 4 or more identical symbols.
First, the filter will weigh less memory.
Secondly, the speed will increase.

Thank you for reading, I tried to write clearly.

It is interesting to hear your opinion

[sssergy]

#115

[ghost]

Because of these identical 0-F characters, I prefer random search.

There are two options for how this can be done:

1. Scalar multiplication of vectors is difficult to implement, only masters can do it.

2. When creating a bloom filter, skip (not write to memory) all hashes with 4 or more identical symbols.

We will wait for an answer.

[albertobsd]

I have some work for this is not implemented yet, im testing it

2. When creating a bloom filter, skip (not write to memory) all hashes with 4 or more identical symbols.

The correct bloom filter creation is critical for the correct work of the BSGS algorimth i CAN'T skip any element in the bloom filter, the bloom filter will remain intact, for more information see https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/

As you said Direct scalar multiplication is in average 128 times slower than Point addition.

my idea for this approach with BSGS is the next: lets to suppose that BSGS can test some 48 bits in one single cycle the range is 120bits example:

800000000000000000000000000000
XXXXXXXXXXXXXXXXXXYYYYYYYYYYYY

So the YY.. is the part that BSGS scan at good speed and the XX... part is the only part that can be accelerated or skipping values until match with some restriction.

Im using some deterministic approach for this only using values that match with some percentage of bits in 1 , so if you only want test values between [ 35%, %60 ] with bits in 1 instead of have 800000000000000000000000000000 as base range we are going to have 80010201020107f7ff000000000000 where the las zeros are going to be checked with BSGS from 000000000000 to ffffffffffff

Some list of the values to be use as BASE RANGE for BSGS is the next:

New range: 80010201020107f7ff000000000000
New range: 80010201020107fbff000000000000
New range: 80010201020107fdff000000000000
New range: 80010201020107feff000000000000
New range: 80010201020107ff7f000000000000
New range: 80010201020107ffbf000000000000
New range: 80010201020107ffdf000000000000
New range: 80010201020107ffef000000000000
New range: 8001020102010bf7ff000000000000
New range: 8001020102010bfbff000000000000

They may look some biased but is because the set of restrictions:

• Average bits in 1 between 35%, %60
• No two same byte value together example 80 01 01, the 01 is together to another 01 01, this value is omitted.
• No three same nibbles value together example 80001234, there are three 0 next to other 0 so that kind of values are omitted.

Yes those values can be selected at request, the good thing is that you can set the minimum and maximum average values of bits in 1 so if you don't found anything with [ 35%, %60 ] you can change it to [ 60%, %75 ] or any other value that you want and no one value is going to be repeated un less you selected values like [50% , 60%] or something else overlapped range.

What you thing guys about this approach ?

Regards!

[ghost]

I have no knowledge of C++ and English, just a little logic.

i CAN'T skip any element in the bloom filter

If you cannot remove the excess from the filter, you can do something similar at the output, skip and not transform further.
Example:
S = start private key + out from bloom filter

string str[16] = "000, 111, 222, 333, 444, 555, 666, 777, 888, 999, aaa, bbb, ccc, ddd, eee, fff";
S.find (str, pos = 1)
if (pos == 1) {
string zero = "quick skiped..";
}else{
    Continuation of the transformation of the private key into the same, public key...
   for... while...
}

Primitively, it will skip 100 times faster than converting unnecessary values with the same characters to public.

XXXXXXXXXXXXXXXXXXYYYYYYYYYYYY

I agree xxx is more important to skip. Since x can be equal to the week (month, year) of the empty search
Initially, I thought to make a replacement, but this is not logical, it is better to skip

[ghost]

I don't understand the dotted algorithm.
Why make a big bloom filter?
For example, instead of a 64-bit filter, 256 GB
You can make 4 x 100 MB each with 16 bits 0000-FFFF and multiply them together. Will the speed be slow?

[ghost]

For puzzles
New range: 80010201020107ffbf000000000000
For skip...
800100100100100100000000000000
8001001001001001a0000000000000
8001001001001001e0000000000000
8001001001001002a0000000000000
8001001001001002f0000000000000

[albertobsd]

Why make a big bloom filter?

Because is the way that the BSGS algorithm works, there is no other way, i've thinking in that for more than one year and there is no other way, if you know some other way please let me know.

Please READ: https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/ if you don't know English please use some web page to translate it to your language.

You can make 4 x 100 MB each with 16 bits 0000-FFFF and multiply them together. Will the speed be slow?

No, BSGS doesn't work in that way you need to have all the b Points in the Cache (Bloomfilter)

[ghost]

Thanks for the clarification, it is difficult to read the formulas for elliptic curves, I will study a little.

There is an idea to use video card memory instead of RAM.
For example, the 3090 has 24GB DDR6 of very fast memory, as well as very high bandwidth. It would be used :)))
I read that you don’t want to do what you don’t want to use. Let's hope that the programmer kanhavishva will show interest and implement bgbs on the GPU. I am learning from its sources.
Thank you and all the masters for your hard work and the fastest program.

[albertobsd]

I read that you don’t want to do what you don’t want to use.

I don't code for GPU because I don't have GPU, so why I going to code something if i will never use it? Also i need access a GPU to test the code for GPU.... I don't have a desktop computer, I only have one old laptop from 5 years ago, i can't put a GPU there.

[ghost]

Let's hope fortune smiles at you or a donate has arrived for a new pc.
So far, only thanks if I find a puzzle from me 3090 :)

[ghost]

Speed ​​question:
BGBS vs Rotor-Cuda
Let's take max BGBS rate
PC 1 Public key 256GB Speed ~ 1 Ekeys/s (1,000,000,000,000,000,000 private keys/s)
Servers 10TB Speed ~10 Zkeys/s
(10,000,000,000,000,000,000,000 private keys/s)

Take a Rotor-Cuda search at (ripmd160) GPU.
There are 30,000,000 addresses in the database.
GPU Speed ​​(RTX 3090 1000Mk/s) ~ 1,000,000,000 private keys/s
1 address (ripmd160) has ~79228162514264337593543950336 private keys.
30,000,000 addresses = 2376844875427930127806318510080000000 private keys.
Theoretically this equals a base with that many addresses.

We calculate the speed:
2376844875427930127806318510080000000 * 1,000,000,000 =
2,376,844,875,427,930,127,806 Ykeys/s
(2,376,844,875,427,930,127,806,318,510,080,000,000,000,000,000 private keys/s)

If you take the base of all coins (302,000,000 addresses) all.bin, the speed will be even higher ...

BGBS is only good for finding one puzzle 32-160 bit. This is the fastest solution to date.

If you are looking for a 160-bit puzzle, then it is better to do it with the address base. Since theoretically in 160 bits there can be all privat keys from all addresses from the base.

It would be cool if the BGBS algorithm searched the address base (ripmd160) with a speed exceeding the GPU.

Do you think I counted correctly?

I would like to hear your opinion on this.

[albertobsd]

Hi, yes rmd hashes has more probability to be found that is true.
Somo of your calculations are wrong.

It would be cool if the BGBS algorithm searched the address base (ripmd160) with a speed exceeding the GPU.

Yes, but it is not possible we cannot do any math operarion with rmd hashes.

[ghost]

It's clear about BGBS.
I agree on the account of more chances to find.
When searching by addresses (rimpd160), the address base hypothetically increases, which makes it more likely to find.
I am tormented by another question
1 address (ripmd160) has ~ 79228162514264337593543950336 private keys
If you find another private key, it will have a different public key.
If the blockchain already has a public key and the one found does not match.
Does the system not authorize?
If the blockchain does not have a public key (address no out transactions), I suppose there will be no problems.
I suppose you do not know the answer, you must first find another private key and check it not in theory but in practice

[albertobsd]

It is called P2PKH ( Pay to Public Key Hash) if the hash match it will works, doesn't matter if the publickey doesn't match