WanderingPhilospher
Full Member
Offline
Activity: 1162
Merit: 237
Shooters Shoot...
|
|
June 11, 2020, 03:52:13 PM |
|
If any of you are working on #115 or #120 or # any above that, by yourself, you're just wasting power.
Jean Luc's knowledge, with Zielar's unlimited GPUs through his work...YOU can't compete. Especially if Jean Luc is making changes to increase chances of Zielar finding the puzzle.
You can't compete. Not with Kangaroo. You'll have to get creative and try random other options.
It's like everyone has GPU power but no one wants to link up and send DPs to common server, or get together and agree on a specific DP to share work files, etc.
I'd rather have 10% of 1.15 BTC versus 0%.
I'm still in the chase, but not strictly with Kangaroo. I offered up my work files, at DP 30 or 31. They are just sitting in file, no longer being used. I'm down to DP 12, with creative works.
We also get lots of troubles handling large workfiles (above 200GB) so I created a partitioned work file system (available on github) , an integrity workfile checker. Told you
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1162
Merit: 237
Shooters Shoot...
|
|
June 11, 2020, 03:55:35 PM |
|
How long are your GPUs working on #115? If #110 was solved for 2 days, so with the same speed and the same luck you need 2days * sqrt(2^5) = 2 days * 5.66 ~ 11.3 days for #115. So, yes, if you started on 1 June, the estimated completion date 11-12 June For #110 you was very close to sqrt(n) operations, but not the average 2*sqrt(n). That means that probably you should wait another 11-12 days to be close to the average and 50% probability to find the key. EDIT: I doubt you will find the #115 key tomorrow. Much more likely at the end of June, or mid July. But not tomorrow. We almost reached 50% probability yesterday (~8 days of run, ~2^33 DP, DP25) but unfortunately everything was shutdown due to a storm Fortunately the workfiles has been preserved but we have to restart clients and servers to recover from crash. As there was no kangaroo backup we will get a DP overhead by restarting the work. I don't know if Zielar restarted the GPUs, yesterday he was a bit nervous We also get lots of troubles handling large workfiles (above 200GB) so I created a partitioned work file system (available on github) , an integrity workfile checker. We manage to re-merge all worfiles in ~24H. The current release is tagged 1.10(unstable) but should work. Hope it will go better now... I've told you...build a comparer. No issues with overhead or large workfiles or 24 hour merging. I've built a homemade one and am able to run any DP without any RAM or merging issues. But I'm not a programmer and know a better one can be built.
|
|
|
|
Etar
|
|
June 11, 2020, 05:40:56 PM |
|
Anybody think about using bsgs algo but with DP? bsgs fast but have a problem due to memory usage. maybe using DP can solve this issues?
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1162
Merit: 237
Shooters Shoot...
|
|
June 11, 2020, 06:00:01 PM |
|
Anybody think about using bsgs algo but with DP? bsgs fast but have a problem due to memory usage. maybe using DP can solve this issues?
Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb. I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
|
June 11, 2020, 06:35:59 PM |
|
Anybody think about using bsgs algo but with DP? bsgs fast but have a problem due to memory usage. maybe using DP can solve this issues?
Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb. I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step. How do you use DPs with BSGS?
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1162
Merit: 237
Shooters Shoot...
|
|
June 11, 2020, 06:48:03 PM |
|
Anybody think about using bsgs algo but with DP? bsgs fast but have a problem due to memory usage. maybe using DP can solve this issues?
Extremely fast, it gets through a FFFFFFFFFFF range in 2 seconds total. Including step build time. Only uses 600Mb. I thought about how to implement it differently. Use DP or build the table on harddrive and when giants start stepping compare back to the saved table. After so long, save the giant file with previously created file, and continue with giant step. How do you use DPs with BSGS? I don't...Etar was pondering if it could be done. I just added some of the thoughts I have had because the speed is insane and it's a 100% solver.
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1162
Merit: 237
Shooters Shoot...
|
|
June 11, 2020, 07:06:48 PM |
|
What are your thoughts...
For this Kangaroo ECDLP solver, if RAM was not an issue, what is the optimal DP setting?
Would lower always be better? Small DP means you have to find more DPs.
Expected group operations remains the same no matter how you adjust the DP, right?
So what is the optimal DP setting if RAM is not an issue?
|
|
|
|
Etar
|
|
June 11, 2020, 07:46:32 PM Last edit: June 11, 2020, 08:29:19 PM by Etar |
|
-snip- How do you use DPs with BSGS?
First fill baby steps, but not each point put to table but only DP and distance when you reach last DP you will get final distance. Doubled distance it will be Giant steps. Before GS you need to find 2 DP (+/-) for known pubkey, compare with hashtable this DP if not success sub GS from pubkey and repeat.. In ex. i generate random pubkey b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82bbfbb9d25748a27 92fcac6ec1b892db592556534f1b6155a37804522d1ff2194 private key is 0xA0300879 in range 2^32 I set DPsize=8, and maxDP in table around 262144 when i fill baby steps i get 262346 DPs It is very small hashtable ofcourse it is just for test.. In this case i should make 20 giant steps to find key. Total add point op was 6981. DPSIZE :8 MASK :ff00000000000000000000000000000000000000000000000000000000000000 TOTAL DPs:262144 STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 FINDx :b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82 FINDy :bbfbb9d25748a2792fcac6ec1b892db592556534f1b6155a37804522d1ff2194 100.1% TOTAL DPs :262346 AVEDIST :256 TABLE SIZE :0000000000000000000000000000000000000000000000000000000004000001 SUB POINTx:930224dc7b052d55216cd197b65997a703e4864ed12ef2f65018a5c8d815dde7 SUB POINTy:392b293eb3eb8d6597f659938411eb241d9ebb59209eeddb308e09b7dd5bf9ea JUMP..20 +FIND!!!>>00000000000000000000000000000000000000000000000000000000A0300879 HASH DISTANCE:3147960 PRE DISTANCE:2684354600 DISTANCE:103 POINTx:b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82 POINTy:bbfbb9d25748a2792fcac6ec1b892db592556534f1b6155a37804522d1ff2194 op 6981
the same with 2^40 range DPSIZE :8 MASK :ff00000000000000000000000000000000000000000000000000000000000000 TOTAL DPs:1048576 STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 FINDx :d25841ae281aad4c516463fe69553b6f9526ef39692b7a5a483d30fee7a3bc22 FINDy :0ab386a9f0985ba4718c827250789cc5e7fc0852800521bb725e05dddc9a4bc2 100.0% TOTAL DPs :1048354 AVEDIST :256 TABLE SIZE :0000000000000000000000000000000000000000000000000000000010000001 SUB POINTx:2d0ea198923cdaf6c8e38f2f7595912a19efb1e78a6c0ce793863da8b4312e3c SUB POINTy:f61fb584f1753d923951f4af8b26d9e96b572283c3f12c15971f6699bc74362b JUMP..1315 +FIND!!!>>000000000000000000000000000000000000000000000000000000A4530846E5 HASH DISTANCE:217563888 PRE DISTANCE:705985251910 DISTANCE:113 POINTx:d25841ae281aad4c516463fe69553b6f9526ef39692b7a5a483d30fee7a3bc22 POINTy:0ab386a9f0985ba4718c827250789cc5e7fc0852800521bb725e05dddc9a4bc2 op 530970
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
|
June 11, 2020, 08:16:10 PM |
|
For this Kangaroo ECDLP solver, if RAM was not an issue, what is the optimal DP setting?
Would lower always be better? Small DP means you have to find more DPs.
Expected group operations remains the same no matter how you adjust the DP, right?
So what is the optimal DP setting if RAM is not an issue?
If the RAM was not a issue, it would be better to use a low DP, because high DP means long time between a collision and its detection, especially if you use many kangaroos in parallel. But not too low, with DP = 0 ** you would have the minimum number of steps, but the generation of the the start points is much slower than the generation of the other points of the path. Let's say that the cost of generating a start point is about x50 the cost of generating the next point with a single jump, with an average length of 10k points (about 2^13) you should have a good value. Then DP = 12 / 13 / 14, not more. ** A note: if you use equivalence classes with DP = 0, you need only sqrt(2).sqrt(N) steps, this is the expected group operations.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
|
June 11, 2020, 08:26:46 PM Last edit: June 11, 2020, 08:39:08 PM by arulbero |
|
-snip- How do you use DPs with BSGS?
First fill baby steps, but not each point put to table but only DP and distance when you reach last DP you will get final distance. Doubled distance it will be Giant steps. Before GS you need to find 2 DP (+/-) for known pubkey, compare with hashtable this DP if not success sub GS from pubkey and repeat.. But in this way you find the private key at 100%? EDIT: In ex. i generate random pubkey b305a37bdbf60a2ba47fc0d134b2ce3646ab7d1236d0e29c73dc27da311dba82bbfbb9d25748a27 92fcac6ec1b892db592556534f1b6155a37804522d1ff2194 private key is 0xA0300879 in range 2^32 I set DPsize=8, and maxDP in table around 262144 when i fill baby steps i get 262346 DPs It is very small hashtable ofcourse it is just for test.. In this case i should make 20 giant steps to find key. Total add point op was 6981.
With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.
|
|
|
|
Etar
|
|
June 11, 2020, 08:46:29 PM |
|
-snip- With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.
you can use what ever you want amount of DPs, but less amount of DP then more GS you need. here is 16k DPs DPSIZE :8 MASK :ff00000000000000000000000000000000000000000000000000000000000000 TOTAL DPs:16384 STARTx:79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 STARTy:483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 FINDx :225e0e43997fb77b83ef7e61a7be88d2851b09da3e36615c0a2d7e06f06b4517 FINDy :cb488adc7c5ba9f4bf0ccf48e0adc7bd2fb2b1488ed42c9cd14a5762be5017dd 101.1% TOTAL DPs :16567 AVEDIST :253 TABLE SIZE :00000000000000000000000000000000000000000000000000000000003fffff SUB POINTx:045685b52a932ee1f2638b9ea3b075f8be2ecd902e14bb7eb1ff0c24c22bbcc5 SUB POINTy:672f0bb37150ac5427d93df317fcb2b2798251581f4966f067f59291b1413b5c JUMP..142 HASH DISTANCE:3177180 PRE DISTANCE:1191182052 DISTANCE:159 POINTx:225e0e43997fb77b83ef7e61a7be88d2851b09da3e36615c0a2d7e06f06b4517 POINTy:cb488adc7c5ba9f4bf0ccf48e0adc7bd2fb2b1488ed42c9cd14a5762be5017dd +FIND!!!>>0000000000000000000000000000000000000000000000000000000046CF8369 op 57909
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
|
June 11, 2020, 09:10:52 PM |
|
-snip- With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.
you can use what ever you want amount of DPs, but less amount of DP then more GS you need. here is 16k DPs The goal is to use less RAM than classic BSGS. Let's say we want to find a key in 120 bit range. With the classic BSGS you need 2^60 BS (huge amount of RAM) and 2^60 GS. With BSGS + (DP = 10): 2^50 BABYSTEPS + on average 2^59 GIANTSTEPS * 2^10 = 2^69 steps. Then less RAM but more steps. With BSGS + (DP = 10): if you want to use more BABYSTEPS: 2^80 BABYSTEPS + on average 2^29 GIANTSTEPS * 2^10 = 2^80 steps + 2^39 GIANTSTEPS. The advantage is that you can precompute this 2^80 BABYSTEPS, but you don't have space to store them.
|
|
|
|
COBRAS
Member
Offline
Activity: 967
Merit: 22
|
|
June 11, 2020, 10:37:13 PM Last edit: June 11, 2020, 10:52:34 PM by COBRAS |
|
-snip- With the classic BSGS, for a range of 2^32 you need only 2^16 = 65536 baby steps, you use instead 262346 DPs, you use more RAM, not less.
you can use what ever you want amount of DPs, but less amount of DP then more GS you need. here is 16k DPs The goal is to use less RAM than classic BSGS. Let's say we want to find a key in 120 bit range. With the classic BSGS you need 2^60 BS (huge amount of RAM) and 2^60 GS. With BSGS + (DP = 10): 2^50 BABYSTEPS + on average 2^59 GIANTSTEPS * 2^10 = 2^69 steps. Then less RAM but more steps. With BSGS + (DP = 10): if you want to use more BABYSTEPS: 2^80 BABYSTEPS + on average 2^29 GIANTSTEPS * 2^10 = 2^80 steps + 2^39 GIANTSTEPS. The advantage is that you can precompute this 2^80 BABYSTEPS, but you don't have space to store them. Jean_Luc BSGS support only 2^32 max BABYSTEP
|
[
|
|
|
|
Etar
|
|
June 12, 2020, 12:18:28 PM |
|
Interesting thing this elliptic curve.. I didn’t think that there are even fractional points on the curve For ex. if 7/2=3.5 (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da) /2= (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
and if double this point it will be again 7 (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) + (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) = (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
|
|
|
|
brainless
Member
Offline
Activity: 318
Merit: 34
|
|
June 12, 2020, 12:24:32 PM |
|
Interesting thing this elliptic curve.. I didn’t think that there are even fractional points on the curve For ex. if 7/2=3.5 (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da) /2= (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
and if double this point it will be again 7 (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) + (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) = (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
3.5 would be in real figure 57896044618658097711785492504343953926418782139537452191302581570759080747172 hex: 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4 pubkey: 04592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b03172dd2e1d26c23 3337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d its common practice
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
brainless
Member
Offline
Activity: 318
Merit: 34
|
|
June 12, 2020, 12:28:54 PM |
|
Interesting thing this elliptic curve.. I didn’t think that there are even fractional points on the curve For ex. if 7/2=3.5 (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da) /2= (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d)
and if double this point it will be again 7 (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) + (592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b031,72dd2e1d26c233337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d) = (5cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc,6aebca40ba255960a3178d6d861a54dba813d0b813fde7b5a5082628087264da)
3.5 would be in real figure 57896044618658097711785492504343953926418782139537452191302581570759080747172 hex: 7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4 pubkey: 04592152c398d6c719636a03a6dad64246a5a6814aa62c156b0ce5332f6759b03172dd2e1d26c23 3337760c49122a1df67d0aa792b453f97bd29765c83b47ba01d its common practice both odd and even fractional points are exist, you only need to calc it, as i can do it
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
Etar
|
|
June 12, 2020, 12:34:11 PM Last edit: June 12, 2020, 12:49:10 PM by Etar |
|
-snip- both odd and even fractional points are exist, you only need to calc it, as i can do it Can you explain how you calculate 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A4 ? edit: solved (n+7)/2
|
|
|
|
mrxtraf
|
|
June 12, 2020, 12:40:01 PM |
|
Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001
|
|
|
|
brainless
Member
Offline
Activity: 318
Merit: 34
|
|
June 12, 2020, 12:41:56 PM |
|
Try calculate real for 0.1 or 0.001 or 0.0000000000000000000000001 for 0.1 a = 1/3 b = a/2 result = 0.1
|
13sXkWqtivcMtNGQpskD78iqsgVy9hcHLF
|
|
|
|