Etar
|
|
June 18, 2020, 06:35:37 PM |
|
-snip- Etar if i am not wrong you have 49 bit 1000 pubkeys you shift dp file to 54 bit and you have this info " Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 " if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange 76 bit = 75557863725914323419135 54 bit = 18014398509481983 distance = 4194303 for 1000 pub key and for 1 pubkey = 419.4303 and for 32*g = 134217.72 in short you used tooo much time as compare to equal 76 bit work hope u understand
2^37.93 for ALL pubkeys for 1 pubkeys average op is 2^27.98And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit. In 54bit i solve 1000pubkeys. And work file will the same for each pubkeys i didn`t append DP to file while solving range 54bit.
|
|
|
|
brainless
Member
Offline
Activity: 329
Merit: 34
|
|
June 18, 2020, 06:39:10 PM |
|
-snip- Etar if i am not wrong you have 49 bit 1000 pubkeys you shift dp file to 54 bit and you have this info " Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 " if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange 76 bit = 75557863725914323419135 54 bit = 18014398509481983 distance = 4194303 for 1000 pub key and for 1 pubkey = 419.4303 and for 32*g = 134217.72 in short you used tooo much time as compare to equal 76 bit work hope u understand
2^37.93 for ALL pubkeys for 1 pubkeys average op is 2^27.98And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit. In 54bit i solve 1000pubkeys run any random pubkey for 76 bit, and see you need these 2^37.93 for finish
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
arulbero
Legendary
Offline
Activity: 1917
Merit: 2074
|
|
June 18, 2020, 06:41:51 PM |
|
The best time complexity with the birthday paradox and kangaroo having a starting position uniformly distributed in [0..N] is obtained when drawing alternatively one tame and one wild. When using DP0, you get ~2.sqrt(N). When using DPx, it is like drawing alternatively 2^x TAME and then 2^x WILD, you have then a DP overhead. I managed to get the formula for parallel version which is: ~2.CubicRoot( N (k.theta + sqrt(N)) ) where theta=2^dpbit and k the number of kangaroo-2 running in parallel. For theta=1 (DP0) and k=0 (or when k.theta << sqrt(N)) we well get ~2.sqrt(N), when k.theta >> sqrt(N), the time complexity tend to ~2.CubicRoot(k.N.theta). So it is important to choose a DP such as k.theta << sqrt(N).
Great work! The number of kangaroos running in parallel transforms DP (that means less RAM) in a overhead. For the #120, if you and Zielar use 2^30 kangaroos, you need to use a DP < 28. The problem is: how fast is a single kangaroo? You can't 'concentrate' the speed of several kangaroo in more speed for one. And it takes a lot for a single kangaroo to walk through a path of length = 2^28. If you reduce k, you reduce the speed, then you have to reduce theta (DP). How many kangaroos run in parallel on a single V100 ? At wich speed?
|
|
|
|
COBRAS
Member
Offline
Activity: 983
Merit: 23
|
|
June 18, 2020, 06:44:07 PM |
|
@JeanLuc make please option for save all dead kangaroo to .txt file in readable format ? This is needed information for understand mistake with ranges and -d param.
@JeanLuc and make please counting +/- dead kangaroo: [Dead 10] -> [Dead total: 10 ["+" 8, "-" 2 ]]
BR.
@JeanLucBuddy, will you reliase this ? BR
|
[
|
|
|
Etar
|
|
June 18, 2020, 06:44:49 PM |
|
-snip- run any random pubkey for 76 bit, and see you need these 2^37.93 for finish
Range 2^ 54.0 Expected OP 2^ 28.054231864896956 Range 2^ 76.0 Expected OP 2^ 39.05419477968964
|
|
|
|
brainless
Member
Offline
Activity: 329
Merit: 34
|
|
June 18, 2020, 06:45:25 PM |
|
-snip- Etar if i am not wrong you have 49 bit 1000 pubkeys you shift dp file to 54 bit and you have this info " Expected operations 2^28.06, Total op was 261530636052 = 2^37.93 " if i am not wrong you total op 2^38 work = to search 1 pubkey in 2^76 bitrange 76 bit = 75557863725914323419135 54 bit = 18014398509481983 distance = 4194303 for 1000 pub key and for 1 pubkey = 419.4303 and for 32*g = 134217.72 in short you used tooo much time as compare to equal 76 bit work hope u understand
2^37.93 for ALL pubkeys for 1 pubkeys average op is 2^27.98And i didn`t have 1000pubkeys in 49bit range. I solve 1 keys and convert work file to range 54bit. In 54bit i solve 1000pubkeys run any random pubkey for 76 bit, and see you need these 2^37.93 for finish for you 1000 pubkeys in 54 bit range total time for check ?
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
Etar
|
|
June 18, 2020, 06:52:52 PM |
|
-snip- for you 1000 pubkeys in 54 bit range total time for check ?
i don`t know how many time was spent for test but calc say that need average time 2^ 3.8s for 1 Pub with 20Mop/s on CPU
|
|
|
|
brainless
Member
Offline
Activity: 329
Merit: 34
|
|
June 18, 2020, 07:05:21 PM |
|
-snip- for you 1000 pubkeys in 54 bit range total time for check ?
i don`t know how many time was spent for test but calc say that need average time 2^ 3.8s for 1 Pub with 20Mop/s on CPU in short i can say for check 1000 keys from 54 bit, your actual work close to 74/75/76 bit range and it should be 54 bit total keys x 1000, and get your bit range for real work should be, btw you all are working in opposite direction, you are trying to change resource like dp, G etc, and in my view most fast way is reverse corresponding pubkey, leave all dp files of 115 as its, and just try my 80 pubkeys for 115 bit already generated dp file, and it will save 80% work and time instead to shift dp/G into 120 bit Etar i will give you experiment in other downbit range, in PM mode, then u will come to know whats difrence
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
Etar
|
|
June 18, 2020, 07:11:35 PM |
|
-snip- Etar i will give you experiment in other downbit range, in PM mode, then u will come to know whats difrence
ok
|
|
|
|
Etar
|
|
June 18, 2020, 09:20:39 PM |
|
Also i done test 1000 pubs with the same range but with normal soving without tricks. here result: Total OP: 273125509453.87 = 2^37.99 Average OP: 28.04
|
|
|
|
arulbero
Legendary
Offline
Activity: 1917
Merit: 2074
|
|
June 18, 2020, 10:23:26 PM |
|
Also i done test 1000 pubs with the same range but with normal soving without tricks. here result: Total OP: 273125509453.87 = 2^37.99 Average OP: 28.04
Unfortunately the difference is very small. -------------------------------------------------------------------------------------------------------- I read this article: https://medium.com/@johncantrell97/how-i-checked-over-1-trillion-mnemonics-in-30-hours-to-win-a-bitcoin-635fe051a752this is the puzzle https://twitter.com/alistairmilne/status/1266037520715915267I think that zielar could have won that prize easily too. About this part of the arcticle: In a GPU you have four main types of memory available to you (Global, Constant, Local, and Private). Global memory is shared across all GPU cores and is very slow to access, you want to minimize its use as much as possible. Constant and Private memory are extremely fast but limited in space. I believe most devices only support 64kB of constant memory. Local memory is shared by a “group” of workers and its speed is somewhere between Global and Constant.
My goal was to fit everything I needed into the 64kB of constant memory and never need to read from global or local memory to maximize the speed of the program. This proved to be a bit tricky because the standard precomputed secp256k1 multiplication table took up exactly 64kB by itself.
@JeanLuc How much constant memory do you use for the multiplication and for the addition? 32 jumps are 16kB for x and y-coordinate + 8 kB for their private keys (32 * 256bit = 8kB) + what else?
|
|
|
|
Jean_Luc (OP)
|
|
June 19, 2020, 02:14:46 AM |
|
@JeanLuc How much constant memory do you use for the multiplication and for the addition? 32 jumps are 16kB for x and y-coordinate + 8 kB for their private keys (32 * 256bit = 8kB) + what else?
I use the following setting to prefer L1 cache as shared mem is not used. cudaDeviceSetCacheConfig(cudaFuncCachePreferL1); In constant mem: __device__ __constant__ uint64_t _0[] = { 0ULL,0ULL,0ULL,0ULL,0ULL }; __device__ __constant__ uint64_t _1[] = { 1ULL,0ULL,0ULL,0ULL,0ULL }; __device__ __constant__ uint64_t _P[] = { 0xFFFFFFFEFFFFFC2F,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0ULL }; __device__ __constant__ uint64_t MM64 = 0xD838091DD2253531; // 64bits lsb negative inverse of P (mod 2^64) __device__ __constant__ uint64_t _O[] = { 0xBFD25E8CD0364141ULL,0xBAAEDCE6AF48A03BULL,0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL __device__ __constant__ uint64_t jD[NB_JUMP][4]; __device__ __constant__ uint64_t jPx[NB_JUMP][4]; __device__ __constant__ uint64_t jPy[NB_JUMP][4];
I will definitely reduce jD to 128 bits in the next release, the less constant mem usage is better, there is 64Kb available but for L1 cache the lowest is the best. In that case best choice for solving keys is using CPU Yes, this is true for small range (as written in the README). Great work!
Thanks For the #120, if you and Zielar use 2^30 kangaroos, you need to use a DP < 28.
Yes, we didn't launch the run yet, we will make our choice in the days to come. Small DP also increase needed mem. If you reduce k, you reduce the speed, then you have to reduce theta (DP).
Right. How many kangaroos run in parallel on a single V100 ? At wich speed?
~2^20 for the last 2 runs, we will see for #120.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1917
Merit: 2074
|
|
June 19, 2020, 06:40:55 AM |
|
@JeanLuc How much constant memory do you use for the multiplication and for the addition? 32 jumps are 16kB for x and y-coordinate + 8 kB for their private keys (32 * 256bit = 8kB) + what else?
I use the following setting to prefer L1 cache as shared mem is not used. cudaDeviceSetCacheConfig(cudaFuncCachePreferL1); In constant mem: __device__ __constant__ uint64_t _0[] = { 0ULL,0ULL,0ULL,0ULL,0ULL }; __device__ __constant__ uint64_t _1[] = { 1ULL,0ULL,0ULL,0ULL,0ULL }; __device__ __constant__ uint64_t _P[] = { 0xFFFFFFFEFFFFFC2F,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0ULL }; __device__ __constant__ uint64_t MM64 = 0xD838091DD2253531; // 64bits lsb negative inverse of P (mod 2^64) __device__ __constant__ uint64_t _O[] = { 0xBFD25E8CD0364141ULL,0xBAAEDCE6AF48A03BULL,0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL __device__ __constant__ uint64_t jD[NB_JUMP][4]; __device__ __constant__ uint64_t jPx[NB_JUMP][4]; __device__ __constant__ uint64_t jPy[NB_JUMP][4];
I will definitely reduce jD to 128 bits in the next release, the less constant mem usage is better, there is 64Kb available but for L1 cache the lowest is the best. 128 bit * 32 = 4kB saved, good. If you accept to break the compatibility with the #115 search, you can save another 1kB picking as jumps points with the first 32 bits of the x-coordinate = 0; you have many of them in the file of the old DPs.
|
|
|
|
zielar
|
|
June 19, 2020, 12:18:45 PM |
|
Also i done test 1000 pubs with the same range but with normal soving without tricks. here result: Total OP: 273125509453.87 = 2^37.99 Average OP: 28.04
Unfortunately the difference is very small. -------------------------------------------------------------------------------------------------------- I read this article: https://medium.com/@johncantrell97/how-i-checked-over-1-trillion-mnemonics-in-30-hours-to-win-a-bitcoin-635fe051a752this is the puzzle https://twitter.com/alistairmilne/status/1266037520715915267I think that zielar could have won that prize easily too. About this part of the arcticle: In a GPU you have four main types of memory available to you (Global, Constant, Local, and Private). Global memory is shared across all GPU cores and is very slow to access, you want to minimize its use as much as possible. Constant and Private memory are extremely fast but limited in space. I believe most devices only support 64kB of constant memory. Local memory is shared by a “group” of workers and its speed is somewhere between Global and Constant.
My goal was to fit everything I needed into the 64kB of constant memory and never need to read from global or local memory to maximize the speed of the program. This proved to be a bit tricky because the standard precomputed secp256k1 multiplication table took up exactly 64kB by itself.
@JeanLuc How much constant memory do you use for the multiplication and for the addition? 32 jumps are 16kB for x and y-coordinate + 8 kB for their private keys (32 * 256bit = 8kB) + what else? It is solved from 18.06
|
If you want - you can send me a donation to my BTC wallet address 31hgbukdkehcuxcedchkdbsrygegyefbvd
|
|
|
COBRAS
Member
Offline
Activity: 983
Merit: 23
|
|
June 19, 2020, 12:23:08 PM |
|
Also i done test 1000 pubs with the same range but with normal soving without tricks. here result: Total OP: 273125509453.87 = 2^37.99 Average OP: 28.04
Unfortunately the difference is very small. -------------------------------------------------------------------------------------------------------- I read this article: https://medium.com/@johncantrell97/how-i-checked-over-1-trillion-mnemonics-in-30-hours-to-win-a-bitcoin-635fe051a752this is the puzzle https://twitter.com/alistairmilne/status/1266037520715915267I think that zielar could have won that prize easily too. About this part of the arcticle: In a GPU you have four main types of memory available to you (Global, Constant, Local, and Private). Global memory is shared across all GPU cores and is very slow to access, you want to minimize its use as much as possible. Constant and Private memory are extremely fast but limited in space. I believe most devices only support 64kB of constant memory. Local memory is shared by a “group” of workers and its speed is somewhere between Global and Constant.
My goal was to fit everything I needed into the 64kB of constant memory and never need to read from global or local memory to maximize the speed of the program. This proved to be a bit tricky because the standard precomputed secp256k1 multiplication table took up exactly 64kB by itself.
@JeanLuc How much constant memory do you use for the multiplication and for the addition? 32 jumps are 16kB for x and y-coordinate + 8 kB for their private keys (32 * 256bit = 8kB) + what else? It is solved from 18.06 Good day. What was the length of the privkey Bro ?
|
[
|
|
|
Etar
|
|
June 19, 2020, 06:32:16 PM |
|
I tried to search keys in the same range as the working file. Everything is much faster: I solve 1 key at 54bit range and only tamed wild DPs. After that i fulfilled test with 1000pubkeys and got a not bad result. Expected op 2^28.06 for one key in average i got 2^27.20 for one key. This value variable dependency how many DPs you gain in workfile. here is workingfile info: DP bits : 8 Start : 40000000000000 Stop : 7FFFFFFFFFFFFF DP Count : 658682 2^19.329 HT Max : 12 [@ 009F12] HT Min : 0 [@ 000015] HT Avg : 2.51 HT SDev : 1.58
But why it didn`t work when we move DPs to range*32 with arulbero method ? P.S interesting thing that 2^27.20 it it is exactly 2^28.06 - (tameDPs+wildDPs/2)*(2^DP)
|
|
|
|
arulbero
Legendary
Offline
Activity: 1917
Merit: 2074
|
|
June 19, 2020, 06:36:49 PM |
|
But why it didn`t work when we move DPs to range*32 with arulbero method ?
Because each patch can reach only 1/32 of the points.
|
|
|
|
COBRAS
Member
Offline
Activity: 983
Merit: 23
|
|
June 19, 2020, 09:26:40 PM Last edit: June 19, 2020, 10:22:15 PM by COBRAS |
|
Sorry me for offtop. Can someone share me compiled Ubuntu 16. CUDA 10 version of Kangaroo ? Very needed. Try compile latest from GitHub but get trebles. in PM if someone can this doing.
make gpu=1 ccap=20 all cd obj && mkdir -p SECPK1 g++ -DWITHGPU -m64 -mssse3 -Wno-unused-result -Wno-write-strings -O2 -I. -I/usr/local/cuda-10.0/include -o obj/SECPK1/IntGroup.o -c SECPK1/IntGroup.cpp SECPK1/IntGroup.cpp: In constructor 'IntGroup::IntGroup(int)': [b]SECPK1/IntGroup.cpp:24:42: error: 'malloc' was not declared in this scope[/b] subp = (Int *)malloc(size * sizeof(Int)); ^ SECPK1/IntGroup.cpp: In destructor 'IntGroup::~IntGroup()': [b]SECPK1/IntGroup.cpp:28:12: error: 'free' was not declared in this scope[/b] free(subp); ^ Makefile:80: recipe for target 'obj/SECPK1/IntGroup.o' failed make: *** [obj/SECPK1/IntGroup.o] Error 1
??
|
[
|
|
|
brainless
Member
Offline
Activity: 329
Merit: 34
|
|
June 20, 2020, 03:36:50 AM |
|
Sorry me for offtop. Can someone share me compiled Ubuntu 16. CUDA 10 version of Kangaroo ? Very needed. Try compile latest from GitHub but get trebles. in PM if someone can this doing.
make gpu=1 ccap=20 all cd obj && mkdir -p SECPK1 g++ -DWITHGPU -m64 -mssse3 -Wno-unused-result -Wno-write-strings -O2 -I. -I/usr/local/cuda-10.0/include -o obj/SECPK1/IntGroup.o -c SECPK1/IntGroup.cpp SECPK1/IntGroup.cpp: In constructor 'IntGroup::IntGroup(int)': [b]SECPK1/IntGroup.cpp:24:42: error: 'malloc' was not declared in this scope[/b] subp = (Int *)malloc(size * sizeof(Int)); ^ SECPK1/IntGroup.cpp: In destructor 'IntGroup::~IntGroup()': [b]SECPK1/IntGroup.cpp:28:12: error: 'free' was not declared in this scope[/b] free(subp); ^ Makefile:80: recipe for target 'obj/SECPK1/IntGroup.o' failed make: *** [obj/SECPK1/IntGroup.o] Error 1
?? Your gpu model ?
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
|
|