Bitcoin Forum
November 06, 2024, 11:17:08 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 ... 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 [144]
  Print  
Author Topic: Pollard's kangaroo ECDLP solver  (Read 58550 times)
kTimesG
Member
**
Offline Offline

Activity: 253
Merit: 39


View Profile
September 20, 2024, 03:40:22 PM
Last edit: September 20, 2024, 03:54:04 PM by kTimesG
 #2861

How exactly is it three times more work? I think you misunderstand what I am saying

y**2 = x**3 + 7

So you have x1 x2 x3, right? If you want to take advantage of endo, then you collide on an invariant of ±y, right? Like y**2 or min(y, p - y) or maybe by parity (if (y & 1) then y = p - y) which is the fastest way.

Now what? You hope to find the same y of an endo class when jumping through the same interval? Well, your chances to hit an Y of another endo class is astronomically low, since they belong to other keys spread through the 256-bit key space, not necessarily your interval.

130-bit range has 2**129 Y values.
Each Y value has 2 (4) more endos for some other keys each somewhere in the 256-bit space.

Chances to hit some other Y than your own class in the 130-bit space is 6*2**129/2**256 more or less.
So you have something like 1 in 2**127 chances to ever find two Y of different endo classes in the same 2**130 key interval. It just becomes pointless extra computation.

Now, since it takes somewhere like 2**65 operations to solve bit 130, then a basic conclusion is:

You'd have to solve around 2**62 130-bit puzzles before you ever get an collision on an Y between two different endo classes, on average..

Smarter way: make sure you jump through the other 2 endomorphic key intervals (so, 3 jump tables, adjust points as multiples of lambda). This way, you do 3x more work, but at least the chances of collision on Y are much more likely to occur, and the walks are all different, so even more chances to hit a collision.

So, first way is rather pointless (the chance to hit an endo Y is basically less than the chance to solve the puzzle itself), and the second one has no gains.
bitcurve
Newbie
*
Offline Offline

Activity: 28
Merit: 6


View Profile
September 20, 2024, 03:49:18 PM
 #2862

How exactly is it three times more work? I think you misunderstand what I am saying

y**2 = x**3 + 7

So you have x1 x2 x3, right? If you want to take advantage of endo, then you collide on an invariant of ±y, right? Like y**2 or min(y, p - y) or maybe by parity (if (y & 1) then y = p - y) which is the fastest way.

Now what? You hope to find the same y of an endo class when jumping through the same interval? Well, your chances to hit an Y of another endo class is astronomically low, since they belong to other keys spread through the 256-bit key space, not necessarily your interval.

130-bit range has 2**129 Y values.
Each Y value has 2 (4) more endos for some other keys each somewhere in the 256-bit space.

Chances to hit some other Y than your own class in the 130-bit space is 6*2**129/2**256 more or less.
So you have something like 1 in 2**127 chances to ever find two Y of different endo classes in the same 2**130 key interval. It just becomes pointless extra computation.

Smarter way: make sure you jump through the other 2 endomorphic key intervals (so, 3 jump tables, adjust points as multiples of lambda). This way, you do 3x more work, but at least the chances of collision on Y are much more likely to occur, and the walks are all different, so even more chances to hit a collision.

So, first way is rather pointless (the chance to hit an endo Y is basically less than the chance to solve the puzzle itself), and the second one has no gains.

This is not what I'm doing. it's not even related... what I'm doing is when we try to compare two points, instead of comparing their x and y values, we just compare the Y values

Quote
Well, your chances to hit an Y of another endo class is astronomically low, since they belong to other keys spread through the 256-bit key space, not necessarily your interval.
So I see you understand why the chance of wrong collision is near zero, astronomically low as you said.
kTimesG
Member
**
Offline Offline

Activity: 253
Merit: 39


View Profile
September 20, 2024, 05:07:37 PM
 #2863

So I see you understand why the chance of wrong collision is near zero, astronomically low as you said.

You got it wrong. It was about the chance of a real collision. But whatever.
bitcurve
Newbie
*
Offline Offline

Activity: 28
Merit: 6


View Profile
September 20, 2024, 05:31:40 PM
 #2864

So I see you understand why the chance of wrong collision is near zero, astronomically low as you said.

You got it wrong. It was about the chance of a real collision. But whatever.

The chance to get two keys that share the same Y value in a distance of less than 2^129 in the interval is very low. with the same complexity as what you described before, I did get it right.
Hence in order to check if two points are equal it is practically waste of cycles to check both x and y values for equality.

Check this out on JLP's code:
https://github.com/JeanLucPons/Kangaroo/blob/master/SECPK1/Point.cpp#L75

If done properly, we only need to compare the y values.
kTimesG
Member
**
Offline Offline

Activity: 253
Merit: 39


View Profile
September 21, 2024, 10:40:54 AM
 #2865

A proper pool effort that doesn't start with a 0% trust level will never send the full DP information to the pool operator.

Distributed work is not the same thing as a pool, it's a means of accelerating solving for a sole owner.

A trustworthy project would need to be able to guarantee to workers that they won't get screwed off, so full transparency is a must. One of those guarantees is full access to the server current state, such that any participant can vouch that the key wasn't yet found.

But this also means that the server itself is not corrupted (like hiding relevant data from workers once the key is found). But in order to do that, all DPs must be made public. However once they are public, then the pool itself becomes useless since someone can steal the DPs and use them outside of the pool.

How about this? Workers send the DPs, but without the distance. Server (or anyone) detects the collision, but is unable to compute the solution, since none of the required distances is known. They were found by two separate workers, each knowing half of the required information. So in order to solve, you need 3 parties:

- solver (holding the DP collision key)
- worker who found a DP of kangaroo type A
- worker who found same DP but of kangaroo type B

Build some strong information exchange scheme around these three such that none of them gets in the possession of the private key. A solution would be a 4th party trusted by all 3, running some software that, once the 3 parties each provide their own secret information (DP key, distance A, distance B), signs a BTC transaction which is agreed in advance by all of them.

How to do that? Use a decryption scheme such that the secret data each holds can only be decrypted if it was encrypted using a hash of the agreed transaction. There still remains the chance that the 4th party can steal the key once it's decrypted (or refuse to sign and broadcast the TX), so we still have a weak link. A solution would be that the software that decrypts and signs only runs when all the parties have access to it at the same time, so they can be sure that it will indeed sign and send the TX when they provide their encrypted part of the data.

See, there's a whole lot more to implement this, than simply adding a few % of speed to JLP with a bunch of micro-optimisations and calling it a pool.
bitcurve
Newbie
*
Offline Offline

Activity: 28
Merit: 6


View Profile
September 21, 2024, 03:43:32 PM
 #2866

A proper pool effort that doesn't start with a 0% trust level will never send the full DP information to the pool operator.

Distributed work is not the same thing as a pool, it's a means of accelerating solving for a sole owner.

A trustworthy project would need to be able to guarantee to workers that they won't get screwed off, so full transparency is a must. One of those guarantees is full access to the server current state, such that any participant can vouch that the key wasn't yet found.

But this also means that the server itself is not corrupted (like hiding relevant data from workers once the key is found). But in order to do that, all DPs must be made public. However once they are public, then the pool itself becomes useless since someone can steal the DPs and use them outside of the pool.

How about this? Workers send the DPs, but without the distance. Server (or anyone) detects the collision, but is unable to compute the solution, since none of the required distances is known. They were found by two separate workers, each knowing half of the required information. So in order to solve, you need 3 parties:

- solver (holding the DP collision key)
- worker who found a DP of kangaroo type A
- worker who found same DP but of kangaroo type B

Build some strong information exchange scheme around these three such that none of them gets in the possession of the private key. A solution would be a 4th party trusted by all 3, running some software that, once the 3 parties each provide their own secret information (DP key, distance A, distance B), signs a BTC transaction which is agreed in advance by all of them.

How to do that? Use a decryption scheme such that the secret data each holds can only be decrypted if it was encrypted using a hash of the agreed transaction. There still remains the chance that the 4th party can steal the key once it's decrypted (or refuse to sign and broadcast the TX), so we still have a weak link. A solution would be that the software that decrypts and signs only runs when all the parties have access to it at the same time, so they can be sure that it will indeed sign and send the TX when they provide their encrypted part of the data.

See, there's a whole lot more to implement this, than simply adding a few % of speed to JLP with a bunch of micro-optimisations and calling it a pool.

Nice ideas, but considering the time it'll take to implement this, it is a lose-lose situation. Better off with less members yet start the pool sooner.

Quote
See, there's a whole lot more to implement this, than simply adding a few % of speed to JLP with a bunch of micro-optimisations and calling it a pool.

No one said we have a new kind of decentralized way of operating the pool, yet it is a pool.
JDScreesh
Jr. Member
*
Offline Offline

Activity: 47
Merit: 13


View Profile
September 23, 2024, 07:53:08 AM
 #2867

Hello ther Smiley

Gratz to the solver of Puzzle # 130   Wink

I don't know if it was solved using Kangaroo  Huh Shocked
Pages: « 1 ... 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 [144]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!