Pollard's kangaroo ECDLP solver

[bitcurve]

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

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]

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]

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]

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]

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.

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]

Hello ther

Gratz to the solver of Puzzle # 130   

I don't know if it was solved using Kangaroo 

[Iekusari]

Hi all. I'm using the kangaroo version from https://github.com/iceland2k14/Kangrand I also have a list of 34.5 thousand public keys with account balance. Could you tell me the optimal settings for a PC with only a CPU and for a PC with a GPU? Just one address will be enough for me and I will post the rest on this forum.

[RetiredCoder]

Hi all. I'm using the kangaroo version from https://github.com/iceland2k14/Kangrand I also have a list of 34.5 thousand public keys with account balance. Could you tell me the optimal settings for a PC with only a CPU and for a PC with a GPU? Just one address will be enough for me and I will post the rest on this forum.

Some people still think that they can just run some software on their computer and gain access to someone’s balance.
For some reason, they also think they’re the first ones to come up with this idea.

[Iekusari]

Hi all. I'm using the kangaroo version from https://github.com/iceland2k14/Kangrand I also have a list of 34.5 thousand public keys with account balance. Could you tell me the optimal settings for a PC with only a CPU and for a PC with a GPU? Just one address will be enough for me and I will post the rest on this forum.

Some people still think that they can just run some software on their computer and gain access to someone’s balance.
For some reason, they also think they’re the first ones to come up with this idea.

These are the next riddles from Satoshi. public keys are known, but the range is unknown. Each address contains 50 bitcoins. why does he ask them? and apparently the kangaroo method is precisely aimed at such a search. someone else guesses the puzzles.

[RetiredCoder]

These are the next riddles from Satoshi. public keys are known, but the range is unknown. Each address contains 50 bitcoins. why does he ask them? and apparently the kangaroo method is precisely aimed at such a search.

Yeah, kangaroo is perfect to crack 256bit range, good luck!

[Iekusari]

These are the next riddles from Satoshi. public keys are known, but the range is unknown. Each address contains 50 bitcoins. why does he ask them? and apparently the kangaroo method is precisely aimed at such a search.

Yeah, kangaroo is perfect to crack 256bit range, good luck!

all addresses to these public keys start with 1, which means that they are in the range of 160 bits. That's what I read on the forum.

[RetiredCoder]

These are the next riddles from Satoshi. public keys are known, but the range is unknown. Each address contains 50 bitcoins. why does he ask them? and apparently the kangaroo method is precisely aimed at such a search.

Yeah, kangaroo is perfect to crack 256bit range, good luck!

all addresses to these public keys start with 1, which means that they are in the range of 160 bits. That's what I read on the forum.

Excellent! 

[Cricktor]

all addresses to these public keys start with 1, which means that they are in the range of 160 bits. That's what I read on the forum.

Okay, if you believe so...

The early coinbase transactions were P2PK type with private key very likely in the full range of 256 bits and unique relationship of public key. Why do you come up with the stupid idea of public addresses when you speak of Satoshi's 50BTC blocks or others from the very early days that haven't moved until now?

Why do you think you would've have the "right" to steal the coins if it were possible (hint: it isn't). What a deranged moral compass...

But go ahead, waste your time and energy with possible 2⁹⁶ public keys to match just one P2PKH public address. You're certainly the hero of 160bit-land who thankfully doesn't understand the very basics.

[garlonicon]

You're certainly the hero of 160bit-land who thankfully doesn't understand the very basics.

Imagine how surprised some people will be, if they will waste a lot of time, to find a collision, and find out, that for example instead of spending 50 BTC from some early block, they will only get 0.00006433 BTC from P2PKH.

[Iekusari]

You're certainly the hero of 160bit-land who thankfully doesn't understand the very basics.

Imagine how surprised some people will be, if they will waste a lot of time, to find a collision, and find out, that for example instead of spending 50 BTC from some early block, they will only get 0.00006433 BTC from P2PKH.

Someone took out one of the addresses in 05/2024. all 50 btc.

You're certainly the hero of 160bit-land who thankfully doesn't understand the very basics.

maybe you can tell me where to read so that I don’t ask stupid questions and waste your and my time

[Cricktor]

Imagine how surprised some people will be, if they will waste a lot of time, to find a collision, ...

Don't want to sound arrogant but I guess they would've earned that "experience" for starting on false premisses. There's more than only public addresses...

Someone took out one of the addresses in 05/2024. all 50 btc.

Which block's coinbase was it? Name the details! And what exactly does it prove when some early coins move now in 2024?

maybe you can tell me where to read so that I don’t ask stupid questions and waste your and my time

Work thoroughly through relevant pages of beginners and technical sections of https://learnmeabitcoin.com and/or read through Mastering Bitcoin by Antonopoulos. There are certainly some more good sources.

To spend one of the early P2PK (paid to a public key) coinbase coins, you need the exact private key that gives you the exact public key. And a specific private key has only one unique public key.

The security of a P2PKH public address is different because you only need to find one of 2⁹⁶ private keys giving you a public key that hashes to a RIPEMD160 hash collision of the public address, IIRC.


For a start you could also stop violating rule #32 of Unofficial list of (official) Bitcointalk.org rules, guidelines, FAQ as there's no need for you to post consecutive posts to quote from different replies. In the Topic Summary below the post entry box the thread's recent posts all have an Insert Quote link with which you can insert multiple quotes in one reply of yours.

You can also always edit your reply if it's still the last reply in a thread when you want to add something and your intention is not to bump a thread after at least 24h time. No need to inflate your post count annoyingly and by breaking set rules.

[bitsminer19]

So I have a question, now let's say I got a low entropy private key (60 and 70 bits range) for one of the 32 puzzle transactions, once I issue a transaction, the public key will get known and bots are already there to solve the private key using this tool.

How can I prevent someone else trying to RBF? Should I only make sure the fee is high for the transaction to get verified right away? They can still make the fee higher and higher right?

[cyberzzz]

So I have a question, now let's say I got a low entropy private key (60 and 70 bits range) for one of the 32 puzzle transactions, once I issue a transaction, the public key will get known and bots are already there to solve the private key using this tool.

How can I prevent someone else trying to RBF? Should I only make sure the fee is high for the transaction to get verified right away? They can still make the fee higher and higher right?

Dont send or  use any legacy address if you solve the puzzle , because we know the code for -address to pub- is publicly available everywhere instead use, starts with bc1q, or with 3

[bitsminer19]

So I have a question, now let's say I got a low entropy private key (60 and 70 bits range) for one of the 32 puzzle transactions, once I issue a transaction, the public key will get known and bots are already there to solve the private key using this tool.

How can I prevent someone else trying to RBF? Should I only make sure the fee is high for the transaction to get verified right away? They can still make the fee higher and higher right?

Dont send or  use any legacy address if you solve the puzzle , because we know the code for -address to pub- is publicly available everywhere instead use, starts with bc1q, or with 3

For sure I would spend to a bc1 address but that isn't my question.

For a short period of time, while my spend transaction from the original P2PKH address get verified, the transaction will have to show the public key for that address. I know that using the ECDLP Solver, I can find the private key in a matter of minutes if not seconds when the entropy is low (say 70 bits).

Anyone who is monitoring these transaction can also find the private key once the transaction is announced, and they can replace my transaction by fee into their own address instead of mine. How can I handle this? I believe this is what happened to the 66 bits private key address. The one who found the private key never got to spend the funds themselves.

[Cricktor]

It doesn't matter to what address type you try to spend your low entropy coins. RBF makes the transaction replaceable once someone else can compute the low entropy private key from knowing the exposed public key while your transaction is still in public mempools.

It also doesn't matter if you use a high fee rate as long as someone else could raise the fee rate in the replacing transaction, too. And you usually can't predict when the next block will be mined to confirm your transaction. It's not too rare that we see 30+ minutes between two blocks. So you can be quite unlucky if you try to be smart and submit your transaction after ~10min from the last block and the next block needs another 20, 30 or even more than 40min to be mined.

Your only chance is a service like slipstream.mara.com which keeps a transaction sent to it non-public and thus hidden from prying eyes of stealer-bots. We of course have to assume that slipstream.mara.com doesn't take advantage on its own behind the scenes, but that would ruin their reputation and could harm Mara pool to some extend.