Pollard's kangaroo ECDLP solver - page 105.

COBRAS

member

Activity: 873

Merit: 22

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

Quote from: arulbero on June 11, 2020, 04:10:52 PM

Quote from: Etar on June 11, 2020, 03:46:29 PM

Quote from: arulbero on June 11, 2020, 03:26:46 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.

Jean_Luc BSGS support only 2^32 max BABYSTEP

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: Etar on June 11, 2020, 03:46:29 PM

Quote from: arulbero on June 11, 2020, 03:26:46 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.

Etar

sr. member

Activity: 617

Merit: 312

Quote from: arulbero on June 11, 2020, 03:26:46 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

Code:

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

Activity: 1932

Merit: 2077

Quote from: Etar on June 11, 2020, 02:46:32 PM

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

But in this way you find the private key at 100%?

EDIT:

Quote from: Etar on June 11, 2020, 02:46:32 PM

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.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: WanderingPhilospher on June 11, 2020, 02:06:48 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.

Etar

sr. member

Activity: 617

Merit: 312

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

Merit: 237

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: 1162

Merit: 237

Shooters Shoot...

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

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

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

Merit: 2077

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

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

Merit: 237

Shooters Shoot...

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

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: 1162

Merit: 237

Shooters Shoot...

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

Quote from: MrFreeDragon on June 10, 2020, 03: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: 1162

Merit: 237

Shooters Shoot...

Quote from: WanderingPhilospher on June 10, 2020, 03: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, 03: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: 205

Merit: 1

Quote from: Konstanting2 on June 11, 2020, 04: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: 873

Merit: 22

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

Quote from: Konstanting2 on June 11, 2020, 04: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: 873

Merit: 22

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

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

Quote from: MrFreeDragon on June 10, 2020, 03: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: 1162

Merit: 237

Shooters Shoot...

Quote from: MrFreeDragon on June 10, 2020, 03: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: 1162

Merit: 237

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.

Topic: Pollard's kangaroo ECDLP solver - page 105. (Read 58630 times)