WanderingPhilospher
Full Member
Offline
Activity: 1092
Merit: 223
Shooters Shoot...
|
|
July 24, 2020, 10:26:11 PM |
|
Thanks. So the idea is that the tame herd is a series of numbers that are increasing in a constant way and the wild herd is variables that are "randomly" moving forward...when a collision occurs, how does that determine the public key? This is not exact, but will give you an example. The tame herd starts at random points, let's say at the middle of the range, then they make jumps. When they land on a dp, it's recorded. The wild herd starts at random points and they make jumps, but they normally start in a range behind the tame herd. If they land on a dp, it's recorded. We have to solve P = k.G, P is the public key, we know that k lies in the range [k1,k2], G is the SecpK1 generator point. (Tame,Wild) = Collision k = k1 + Tame.dist - Wild.dist
|
|
|
|
iamfreshfish
Newbie
Offline
Activity: 8
Merit: 0
|
|
July 26, 2020, 05:02:51 AM |
|
Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this So I got it to run. 1080ti on Windows Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt Starts off at 200Mkeys/s and then continuously drops Also why does this algo seem to only work for bit ranges that are multiples of 5?
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1092
Merit: 223
Shooters Shoot...
|
|
July 26, 2020, 05:10:59 AM |
|
Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this So I got it to run. 1080ti on Windows Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt Starts off at 200Mkeys/s and then continuously drops Also why does this algo seem to only work for bit ranges that are multiples of 5? Glad you finally got it to work. Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you. The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s. I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple".
|
|
|
|
Marynarz
Jr. Member
Offline
Activity: 40
Merit: 2
|
|
July 26, 2020, 09:56:34 AM |
|
Hi all Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase. The idea of replaying walk is good, I do like this in my BTCCollider. Here is an output on 30 trials. The final private key is not reconstructed here, you need to add (mod n) start range + N/2 Kangaroo v1.3 Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000 Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF Keys :1000 Number of CPU thread: 2 Range width: 2^40 Jump Avg distance: 2^20.00 Number of kangaroos: 2^11.00 Suggested DP: 8 Expected operations: 2^21.15 Expected RAM: 6.5MB DP size: 5 [0xF800000000000000] SolveKeyCPU Thread 0: 1024 kangaroos SolveKeyCPU Thread 1: 1024 kangaroos
Key# 0 S3Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1 Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632 [ 0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)
Kangaroo.exe -t 0 -d 11 -m 3.0 -gpu -g 80,256,80,256 -gpuId 0,1 -o found.txt in.txt Kangaroo v2.1 Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000 Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF Keys :293566 Number of CPU thread: 0 Range width: 2^40 Jump Avg distance: 2^19.97 Number of kangaroos: 2^22.32 Suggested DP: 0 Expected operations: 2^25.49 Expected RAM: 12.9MB DP size: 11 [0xFFE0000000000000] GPU: GPU #0 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used) SolveKeyGPU Thread GPU#0: creating kangaroos... GPU: GPU #1 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used) SolveKeyGPU Thread GPU#1: creating kangaroos... SolveKeyGPU Thread GPU#1: 2^21.32 kangaroos [12.9s] SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [12.9s] [185.39 MK/s][GPU 185.39 MK/s][Count 2^28.49][Dead 204][02s (Avg 00s)][6.4/21.9M B] Key# 0 [XX]Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CF E36A1 Aborted ! Jean_Luc, would you please explain to me why Kangaroo v2.1 has a problem finding this key?
|
|
|
|
Wouimbly
Newbie
Offline
Activity: 8
Merit: 0
|
|
July 26, 2020, 03:46:05 PM |
|
Hi! Just wonder what is the impact of searching multiple pubkey at once ? Does the key are search one by one or all at once ?
|
|
|
|
iamfreshfish
Newbie
Offline
Activity: 8
Merit: 0
|
|
July 26, 2020, 06:05:03 PM |
|
Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this So I got it to run. 1080ti on Windows Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt Starts off at 200Mkeys/s and then continuously drops Also why does this algo seem to only work for bit ranges that are multiples of 5? Glad you finally got it to work. Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you. The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s. I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple". Yeah it was weird but I was running out of space...was gobbling up RAM and I'm assuming pagefile as well but when I moved the app to a separate drive it is now running at 500Mkeys/s As for the "every 5th" I now understand that this algo requires the public key and the other BTC puzzle programs just brute force all the private key options in a range
|
|
|
|
WanderingPhilospher
Full Member
Offline
Activity: 1092
Merit: 223
Shooters Shoot...
|
|
July 26, 2020, 07:49:25 PM |
|
Hi! Just wonder what is the impact of searching multiple pubkey at once ? Does the key are search one by one or all at once ?
If you have more than one pubkey in your input file, the program searches one by one. If you don't use the -m option, the program could search for the first pubkey forever.
|
|
|
|
PawGo
Legendary
Offline
Activity: 952
Merit: 1369
|
|
July 31, 2020, 09:14:00 PM |
|
Hello, Regarding https://bitcointalk.org/index.php?topic=5265788.0, 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,
|
|
|
|
j2002ba2
|
|
August 01, 2020, 05:00:59 AM |
|
Hello, Regarding https://bitcointalk.org/index.php?topic=5265788.0, 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 a i by 's': a i/s = a 0/s + i.
|
|
|
|
paniker
Newbie
Offline
Activity: 49
Merit: 0
|
|
August 01, 2020, 08:31:17 AM |
|
Hi all,
So no one knows a pubkey to 64?
|
|
|
|
bigvito19
|
|
August 01, 2020, 09: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.
|
|
|
|
vimp666
Jr. Member
Offline
Activity: 37
Merit: 1
|
|
August 01, 2020, 12:03:00 PM |
|
Hi all,
So no one knows a pubkey to 64?
Address 64 has no outgoing transactions.Therefore, the public key is unknown.
|
|
|
|
PawGo
Legendary
Offline
Activity: 952
Merit: 1369
|
|
August 01, 2020, 01:22:28 PM Last edit: August 01, 2020, 03:18:31 PM by PawGo |
|
[EDITED]
I must rethink it ;-)
|
|
|
|
paniker
Newbie
Offline
Activity: 49
Merit: 0
|
|
August 01, 2020, 03:58:13 PM |
|
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 ?
|
|
|
|
COBRAS
Member
Offline
Activity: 892
Merit: 22
|
|
August 01, 2020, 09:23:08 PM |
|
@Jean_Luc, implement please Pollard's RHO code to bitcoin Maybe you can make a Pollard RHO like Pollard Kangaro without memory cost This is a link to sources: Code Sources ready to go - CUDA demonstration using Pollard's Rho - https://github.com/dghost/factor-cudahttps://github.com/dghostBSGS 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 P ollard'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.
|
[
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4200
Merit: 8442
|
|
August 04, 2020, 06:30:57 PM |
|
I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdfThere 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.
|
|
|
|
Jean_Luc (OP)
|
|
August 05, 2020, 10: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.pdfThere 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.
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4200
Merit: 8442
|
|
August 05, 2020, 02:07:11 PM |
|
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.
|
|
|
|
vimp666
Jr. Member
Offline
Activity: 37
Merit: 1
|
|
August 06, 2020, 04:04:04 PM |
|
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.
|
|
|
|
bigvito19
|
|
August 07, 2020, 01:06:15 PM Last edit: August 07, 2020, 04:28:16 PM by bigvito19 |
|
So this is what you all really wanted to use Kangaroo vs RHO
|
|
|
|
|