|
O(sqrt(n)) in time means that you need to perform sqrt(n) group operations (addition here) in the worst case.
If you have n=2^64 (like the above problem), you need to perform sqrt(n) = 2^32 EC additions but to achieve this you also need to store in memory 2^32 "baby steps" and perform 2^32 additions to fill the memory. In total, 2*sqrt(n) group operation (worst case). If you have less memory, of course, you will have to perform more operations, O(sqrt(n)) is the best time/memory tradeoff for this method.
I don't know your code but to solve the 16 keys given by odolvlobo, yon can fill only once the memory and then process the 16 keys.
|
|
|
|
|
@etar
The BSGS algotrithm has a complexity in time and in memory.
You can have time in O(sqrt(n)) and memory in O(sqrt(n)). n is the search space size.
But you can also have time in O(1) and memory in O(n)
If you have n memory available and memory already filled, it makes no sense to give a key rate.
|
|
|
|
This is well know since the beginning of elliptic curve usage in crypto. But we count the number of group operation really performed (not the size of the range divided by time). For instance in my BTCollider which use the DP method (also in O(sqrt(n))), I get 27.9 Mips (GeForce GTX 1050 Ti) for 80bit collision search. That means that I really compute 27.9M group operation and hash per second. It solves 80bit collision in 14h30 (in average). Note that in that case, it have to compute an EC mult for each group operation. https://github.com/JeanLucPons/BTCCollider |
|
|
|
Yesterday, I read in detail about the giant baby steps algorithm.
I had heard about him before, but did not delve into the gist of it.
This algorithm is very similar to the one I use.
So you have use this algorithm which is in O(sqrt(n)) for both memory and time where n is the size of the range. Starting with an offset does not prevent to use this algorithm. That means that the key rate (or group operation) you announced is wrong. Do not waste time in solving the above problem, solving it will just prove that you have correctly implemented this known algorithm. |
|
|
|
Etar, you are funny person.
Yes, you just overestimate the rate. It is known that due to pollard kanagaroo method it is possible to perform less bruteforce operations. And roughly it is square root from the total length.
You just count the operations which are not actually performed. You use the method which is good due to birthday paradox. However, due to this methond you just need less operations.
So, your actual speed is not 2.2Ph/s but the square root from this amount, i.e. approx. 47 Mh/s in total.
This is what we try to explain since the beginning of this post. |
|
|
|
1Ph/s speed is roughly 2^66 per 24 hours. There is a bitcoin address with 0.64BTC and 64bit private key. You need 2^63 operations to bruteforce it. If you have real speed 2^66 per 24 hours, so you can perform 2^63 operations juts for 24/(2^3)=3 hours. So, welcome to prove your speed: just take 0.64BTC from this address: https://www.blockchain.com/btc/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQNThe private key for this address is in the range: 0x8000000000000000 - 0xffffffffffffffff (64bit key, i.e. with 192 leading zeros) Funny challenge  but the public key is not exposed there ? If no, you need to hash... |
|
|
|
|
@Etar
Your tests does not prove anything.
If you want to prove your key rate, follow the test given by gmaxwell.
If you manage to get 275313 GKey/s , you should be able to find a public key (and its corresponding private key) with a X starting with ~60 zero bits in 1 hour, (~64 bits in 1 day)
And to be sure that you didn't make any precomputation we should choice a random starting key.
|
|
|
|
|
You will just prove that you are able to solve ECDLP for a subset of priv key of a size near 2^62 in one hour.
But we have no proof of the algorithm used which can be in O(2^31).
Why you don't want to post your code ?
|
|
|
|
You can make private in range
from
0x0000000000000000000000000000000000000000000000000000000000000001
to
0x00000000000000000000000000000000000000000000000031f5c4ed27680000
than make public key(64bytes) from this private key and show me this public key.
You specify this range to prove your speed which is a 62bits range (not 64bits you're right). If you want to prove your speed, post your code. Solving ECDLP on sepck1 for a reduced priv key range does not prove the speed you announce. The speed of a method depend first on the complexity of the used algorithm not only on the speed of the hardware. |
|
|
|
Hello, Even if you solve ECDLP for a 64bits key, that does not prove the speed you announce. You can use variant of the DP method on a reduced subset of private keys and get a complexity of O(2^32). I wrote a GPU program that looks for partial collision on addresses (not the same process but the method is similar) It founds 64bits collision in few minutes on a GTX 1050 Ti. So post the code and we will see. https://github.com/JeanLucPons/BTCCollider |
|
|
|
OMG, I changed the grid size as you suggested now I am getting 51 GK/s, amazing ...
Great:) Is there any chance to use regex with gpu?
You can only use wildcard characters ? and *: C:\C++\VanitySearch\x64\Release>VanitySearchCUDA8.exe -stop -gpu 1AB*C?D VanitySearch v1.15 Search: 1AB*C?D [Compressed] Start Fri Apr 3 08:57:58 2020 Base Key: 181D206E917CAA73BBD771F81508B51E6EAD5B63A4ACFE7C0EB334436372AEE9 Number of CPU thread: 3 GPU: GPU #0 GeForce GTX 645 (3x192 cores) Grid(24x128) PubAddress: 1 ABsAWqsewBsiTAFzUuABocgEAP8JP9 C7 DPriv (WIF): p2pkh:L3uif98QLuVLNb71SgTrhKt61SjKXdJk1czxNb4j8ekRhpHYcmMj Priv (HEX): 0xC79B2930ABC2F63E601320D0412AC8BAF4E39933AF67FBC445AEEC73DC981FFA |
|
|
|
|
Try to play with gridsize, ex: -g 640,256,640,256,....
On the benchmark by DaveF, for a Tesla V100-SXM2-16GB we have 1.815 GK/s per board.
You have 40GK/s , so 2.5 GK/s per board, not so bad...
|
|
|
|
|
So good ccap is 70 for your hardware.
Did you get the same error message with ccap 70 ?
Could you try with cuda 10.0 ?
|
|
|
|
|
Hi,
Yes there is an issue with Cuda 10.2 (both on Linux and Windows), it works fine with 10.0.
I didn't try it by myself but some users already reported this issue.
Edit: May be it is a different problem there, when you compiled what ccap did you use ?
Could you try to execute VanitySearch -l ?
|
|
|
|
Wait, I just found out that the 50-100 consecutive results of the output files are the same address, need further testing.
@Jean_Luc What do you think is the issue?
Hi, Did you find the issue ? I didn't test your script yet. |
|
|
|
|
If you starts like this:
VanitySearch.exe 1BTC
At each startup, the base key is choosen randomly.
VanitySearch.exe -s "My Seed" 1BTC
In this case,it will compute the same thing each time, the base key is computed from the seed.
|
|
|
|
Clear output memory 4 bytes
It clears only the global counter (used by each GPU threads), the rest of the memory is written by the GPU each time it founds a match. Except for the 4 first bytes, there is no need to copy or reset anything. |
|
|
|
|
Hi,
cudaMemset(outputPrefix,0,4); reset the prefix counter which is a 32bits variable, there's no need to reset anything else.
This variable is used in:
pos = atomicAdd(out, 1);
where out is a pointer (uint32_t *) to outputPrefix.
|
|
|
|
|
Show Posts
