Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 81. (Read 59389 times)

jr. member
Activity: 40
Merit: 2
August 11, 2020, 04:01:43 AM
Ah...this google translator Tongue over 6 million dead kangaroo appeared while solving the problem with DP13, I solved the problem using the -t 4 processor if it matters.


PS. I didn't modify the code.
sr. member
Activity: 462
Merit: 701
August 11, 2020, 03:54:13 AM
It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.

The problem occurred in v2.1

What do you mean by "adding 6 million kangaroos dead" ?
Did you modify the code ?
jr. member
Activity: 40
Merit: 2
August 11, 2020, 03:42:28 AM
Could someone explain to me why this happened?

This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ?


It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.

The problem occurred in v2.1
sr. member
Activity: 462
Merit: 701
August 11, 2020, 01:32:01 AM
Could someone explain to me why this happened?

This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ?

Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?

The expected number of operation is the average number of group operations needed to solve the key (including the DP overhead). It correspond to ~50% probability.
If you use -m 3 and if the search is aborted, you are sure at ~99.7% that the key is not in the given range.
jr. member
Activity: 40
Merit: 2
August 10, 2020, 02:39:44 PM
Could someone explain to me why this happened?

Code:
 Unexpected wrong collision, reset kangaroo !
Found: Td 26B501C33D35DA
Found: Wd 26B501C33D35DA

 Unexpected wrong collision, reset kangaroo !
Found: Td 631129815BBDF2
Found: Wd 631129815BBDF2

 Unexpected wrong collision, reset kangaroo !
Found: Td 62F22824B6E91
Found: Wd 62F22824B6E91

 Unexpected wrong collision, reset kangaroo !
Found: Td 508A6055322AF9
Found: Wd 508A6055322AF9

 Unexpected wrong collision, reset kangaroo !
Found: Td 2D3A2764183555
Found: Wd 2D3A2764183555

 Unexpected wrong collision, reset kangaroo !
Found: Td 66A2632596D7A6
Found: Wd 66A2632596D7A6

legendary
Activity: 952
Merit: 1385
August 10, 2020, 10:47:37 AM
Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?
sr. member
Activity: 462
Merit: 701
August 10, 2020, 05:37:17 AM
Hi,

I published a new release 2.2:
https://github.com/JeanLucPons/Kangaroo/releases/tag/2.2

Slight performance increase:
    ModInv performance increase (Thanks to Peter Dettman)
    GPU kernel performance increase

Thanks to gmaxwell for pointing me out this interesting PR of bitcoin core Smiley

full member
Activity: 706
Merit: 111
August 07, 2020, 08:06:15 AM

So this is what you all really wanted to use Kangaroo vs RHO


jr. member
Activity: 37
Merit: 1
August 06, 2020, 11:04:04 AM
Hi all,

So no one knows a pubkey to 64?
Address 64 has no outgoing transactions.Therefore, the public key is unknown.


so everybody seraching higher known addresses ?
Pollard's method can only search for those addresses where the public key is known. So the answer to your question is Yes.
staff
Activity: 4284
Merit: 8808
August 05, 2020, 09:07:11 AM
Thanks for the reading. I didn't read it yet.
I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance.
The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things.

Right.

This is specific to disk stored distinguished points stored for tame entries used to generically accelerate many different executions.

The idea is that sometimes distinguished points are closely spaced on a walk, and sometimes far apart. Given a constant amount of storage you would prefer to store widely spaced distinguished points over closely spaced ones.  You can't know the actual spacing, since you don't know what the walk looked like before your start-- but you could track how far you walked and store that.
sr. member
Activity: 462
Merit: 701
August 05, 2020, 05:37:45 AM
I won't implement a rho method for secp256k1. It is not feasible to reach a solution using this method.

I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdf

There are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting.

Thanks for the reading. I didn't read it yet.
I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance.
The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things.
staff
Activity: 4284
Merit: 8808
August 04, 2020, 01:30:57 PM
I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdf

There are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting.
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
August 01, 2020, 04:23:08 PM
@Jean_Luc, implement please Pollard's RHO code to bitcoin Huh

Maybe you can make a Pollard RHO like Pollard Kangaro without memory cost Huh



This is a link to sources:



Code Sources ready to go Smiley - CUDA demonstration using Pollard's Rho  - https://github.com/dghost/factor-cuda

https://github.com/dghost

BSGS and Pollard's rho both cost O(n−−√) operations where n is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc. However, BSGS also has O(n−−√) memory cost, so the area*time cost—which is a proxy for euro or joule cost—is O(n) even if we unrealistically assume O(1) random access to memory. In contrast, Pollard's rho costs O(n−−√) time on a machine of constant space and thus O(n−−√) area*time. Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost. There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains O(n−−√)
.
If you knew the secret scalar were in a restricted range [a,b]
, you could use Pollard's kangaroo, which costs O(b−a−−−−√) time on a machine of constant size. The kangaroo method too can be parallelized without increasing overall cost. If, say, b−a≈2100 for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible. But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.

newbie
Activity: 49
Merit: 0
August 01, 2020, 10:58:13 AM
Hi all,

So no one knows a pubkey to 64?
Address 64 has no outgoing transactions.Therefore, the public key is unknown.


so everybody seraching higher known addresses ?
legendary
Activity: 952
Merit: 1385
August 01, 2020, 08:22:28 AM
[EDITED]

I must rethink it ;-)
jr. member
Activity: 37
Merit: 1
August 01, 2020, 07:03:00 AM
Hi all,

So no one knows a pubkey to 64?
Address 64 has no outgoing transactions.Therefore, the public key is unknown.
full member
Activity: 706
Merit: 111
August 01, 2020, 04:45:57 AM
Hi all,

So no one knows a pubkey to 64?


If pubkey to 64 was exposed it would have been solved already.
newbie
Activity: 49
Merit: 0
August 01, 2020, 03:31:17 AM
Hi all,

So no one knows a pubkey to 64?
full member
Activity: 206
Merit: 447
August 01, 2020, 12:00:59 AM
Hello,

Regarding https://bitcointalksearch.org/topic/solving-wif-in-a-hybrid-mode-5265788, would it be possible to modify kangaroos to work on sparse range?
I would like to launch search on range [a0, ..., ai, ..., aN], where ai = a0+(i*s), with stride 's'.
As I understand now program 'scales down' range to 0->aN', with a corresponding changes on pubkey, right?

Regards,

For continuous range you could divide ai by 's': ai/s = a0/s + i.
legendary
Activity: 952
Merit: 1385
July 31, 2020, 04:14:00 PM
Hello,

Regarding https://bitcointalksearch.org/topic/solving-wif-in-a-hybrid-mode-5265788, would it be possible to modify kangaroos to work on sparse range?
I would like to launch search on range [a0, ..., ai, ..., aN], where ai = a0+(i*s), with stride 's'.
As I understand now program 'scales down' range to 0->aN', with a corresponding changes on pubkey, right?

Regards,
Pages:
Jump to: