Pollard's kangaroo ECDLP solver - page 103.

Etar

sr. member

Activity: 616

Merit: 312

Quote from: arulbero on June 11, 2020, 02:35:59 PM

-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.

Code:

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

Code:

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

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

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?

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: arulbero on June 11, 2020, 02:35:59 PM

Quote from: WanderingPhilospher on June 11, 2020, 02:00:01 PM

Quote from: Etar on June 11, 2020, 01: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?

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.

arulbero

legendary

Activity: 1914

Merit: 2071

Quote from: WanderingPhilospher on June 11, 2020, 02:00:01 PM

Quote from: Etar on June 11, 2020, 01: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?

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

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: Etar on June 11, 2020, 01: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?

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.

Etar

sr. member

Activity: 616

Merit: 312

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

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: Jean_Luc on June 11, 2020, 11:44:33 AM

Quote from: MrFreeDragon on June 10, 2020, 04:25:13 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 Cheesy

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 Sad

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 Cheesy

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.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: WanderingPhilospher on June 10, 2020, 04:44:54 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.

Quote

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

Jean_Luc

sr. member

Activity: 462

Merit: 696

Quote from: MrFreeDragon on June 10, 2020, 04:25:13 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 Cheesy

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 Sad

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 Cheesy

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...

sssergy2705

copper member

Activity: 188

Merit: 0

Quote from: Konstanting2 on June 11, 2020, 05:37:20 AM

Thank you very much for the help. I was able to finally run the program. Community tell me how to open a 65save answer file? The file does not have an extension, I open notepad there are hieroglyphs, squares. I tried to open Bred3.0.3, I didn’t open it. Thank you very much in advance.

HxD Hex Editor, Winhex, Cygnus Hex Editor, etc

COBRAS

member

Activity: 814

Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Konstanting2 on June 11, 2020, 05:37:20 AM

Thank you very much for the help. I was able to finally run the program. Community tell me how to open a 65save answer file? The file does not have an extension, I open notepad there are hieroglyphs, squares. I tried to open Bred3.0.3, I didn’t open it. Thank you very much in advance.

Maybe totalcommander can help. TC file viewer support many codepages(ANSI,Unicode, etc...)

Konstanting2

newbie

Activity: 27

Merit: 0

Thank you very much for the help. I was able to finally run the program. Community tell me how to open a 65save answer file? The file does not have an extension, I open notepad there are hieroglyphs, squares. I tried to open Bred3.0.3, I didn’t open it. Thank you very much in advance.

COBRAS

member

Activity: 814

Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: WanderingPhilospher on June 10, 2020, 04:46:12 PM

Quote from: MrFreeDragon on June 10, 2020, 04:25:13 PM

Quote from: ?? on ??

Together with the author of this work, we plan to have solution # 115 tomorrow and set a new record :-)

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 Cheesy

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.

You never know, he may have been granted access to more GPUs through work. Or maybe the luck factor will play in to his favor.

In wikipedia wrighted - about max solved is 109 Bytes )))

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: MrFreeDragon on June 10, 2020, 04:25:13 PM

Quote from: ?? on ??

Together with the author of this work, we plan to have solution # 115 tomorrow and set a new record :-)

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 Cheesy

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.

You never know, he may have been granted access to more GPUs through work. Or maybe the luck factor will play in to his favor.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

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.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: ?? on ??

Together with the author of this work, we plan to have solution # 115 tomorrow and set a new record :-)

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 Cheesy

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.

PietCoin97

jr. member

Activity: 91

Merit: 3

the thing is i start with dp 24 after you found the 110 bit then i lost big file for dp 24

then i start with new one with dp 26 i run it for 6 days

this is my workfile

Loading: 115all
Version : 0
DP bits : 26
Start : 40000000000000000000000000000
Stop : 7FFFFFFFFFFFFFFFFFFFFFFFFFFFF
Key : 0248D313B0398D4923CDCA73B8CFA6532B91B96703902FC8B32FD438A3B7CD7F55
Count : 9743276691781672 2^53.113
Time : 68.7d
DP Size : 403.0/1183.5MB
DP Count : 13140929 2^23.648
HT Max : 89 [@ 021EC5]
HT Min : 22 [@ 00EAD0]
HT Avg : 50.13
HT SDev : 7.09
Kangaroos : 0 2^-inf

Kangaroo v1.8
Loading: 115all
Version : 0
DP bits : 24
Start : 40000000000000000000000000000
Stop : 7FFFFFFFFFFFFFFFFFFFFFFFFFFFF
Key : 0248D313B0398D4923CDCA73B8CFA6532B91B96703902FC8B32FD438A3B7CD7F55
Count : 11306564601638692 2^53.328
Time : 103.7d
DP Size : 655.4/1815.3MB
DP Count : 21411199 2^24.352
HT Max : 129 [@ 021EC5]
HT Min : 46 [@ 00BF14]
HT Avg : 81.68
HT SDev : 9.07
Kangaroos : 0 2^-inf

PietCoin97

jr. member

Activity: 91

Merit: 3

oww Zielar i run my engines so long now for 115 and you solve it tomorrow ? wht dp size you choose ?

i have dp 26 maybe i can share with you

Etar

sr. member

Activity: 616

Merit: 312

Seems like #115 pazzle it is the latest pazzle to solve with kangaroo.
Next #120 need 160 days with 100x2080ti. With the same power even at not the best algorithm Ethash for this card this huge power get 1.6BTC for 160 days, it is much more then expected reward for solving key.

PietCoin97

jr. member

Activity: 91

Merit: 3

someone have workfile for share with dp26 ?

Topic: Pollard's kangaroo ECDLP solver - page 103. (Read 55445 times)