Topic: Pollard's kangaroo ECDLP solver - page 2. (Read 60517 times)

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.

Excellent! 

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.

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

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.

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.

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.

Hello ther

Gratz to the solver of Puzzle # 130   

I don't know if it was solved using Kangaroo 

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.


No one said we have a new kind of decentralized way of operating the pool, yet it is a pool.

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.

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.

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

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

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

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.

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

That is a rabbit hole... there is no academic proof that endomorphism can be used to speed up attacks on ECDLP in an interval. People are trying for 20-30 years to take advantage of it, no success so far by anyone. It is only useful if you're attacking the full-blown 256-bit private key range, anything under 254 bits is pointless to use endomorphism on. Again, 3x more work with 3x more collision chances = same work. Of course it always works, I made lots of tests of kangaroos jumping through endo equivalence classes, but guess what? It doesn't result in a faster collision, it just, again, means you have 3x more jumps and 3x more chances of collision = same runtime. It's all an illusion, it's a zero-sum gain.

This has nothing to do with what we talk about.


By endomorphism I mean the different solutions to y^2 = x^3 + 7 mod P. the chance of wrong collision in the range is close to zero. if you see difference X values in the solution, x1, x2, and x3, you see their difference is usually much larger than 2^129.


I don't expect anything from you. If you don't trust me, simply read the code, it's open source!


The information about the reward distribution is available at the webpage. your argument against pools is valid for any such pool, not specifically mine.

Do you know what "useless" means? If you are doing 3x more work and have 3x more chances of success, than a 2nd grade student can tell you the total work time is identical, even worse due to the overhead.

Or maybe I haven't understood what you mean by endomorphism. Maybe you meant the symmetry? But we have other issues there, and honestly, again, I don't have time to review your code since you have no common GIT ref to the original work, so it would just be a waste of time. And you don't seem to offer some actual "what's changed", so you're asking us to simply trust your changes, which may very well be bad thinking on your side. If it's symmetry - do you account for the fact that some kangaroo can arrive at the point at infinity? That they can suffer doublings? There are dozens of things that can go wrong.  And simply looking at your code, it just seems identical to JLP, no offense.


Yes, it's silly to think anyone can credit you based on pure faith. Again, why don't you have a common GIT code base with the original work, so we can actually discuss about your improvements that you think are worth it?


What is your intent? Anyone can patch JLP to fix the 125-bit limitation, but it IS STILL THE SAME CODE in all principle. How is one suppose to trust your "pool"? Who is in control of the final merged work files? Why would one use their GPU to mine DPs that are sent to a machine outside of their control? Who gets the prize? Where's the code that enables an user to be rewarded based on his contributions? Do you even have a strategy for them, or just ask us to pay kWh of electricity for your own final benefit?

1. If you would of been reading the readme file, you will see the credit to JLP
2. So you essentially confirm my assumption. You judge too fast - you didn't even read any of the code. good job!


This is just nonsense, it always works, regardless of the interval/range


Again, without even reading the readme file/any of the code, and yet you think you can come to "definitive conclusions" on it. THIS IS SILLY.

Next time better not to claim such things without seeing them first.

---

The performance are a few percentages better, for your information. It is not just "aesthetic code style" updates.

Mod note: Consecutive posts merged

So, in other words, you confirm as taking at least me as an idiot. Good job on that.

Do you think I will afford losing a few hours of my life to actually do diffs on "your" code against JLP base code? Without even having some common GIT ref commit? It's 99.99% the same code, same structure, same files, same strategies, same pitfalls. Aesthetic code style updates and cleanup / dead code removal are still the same freaking code in the end, what are you doing, a compiler's job? And to make the claim that you are dishonest only takes 10 seconds of my life, to reach a definitive conclusion.

Copy pasting a project, removing all references to the original author, and not even bothering to give credit, is called plagiarism.

You're like the kid from the school that has their homework done by others, changes a few words, and tries to claim it as his own work. Teachers are not stupid, you know?

Endomorphism does not work for low bit-ranges, it only works if you solve a bit range of 254 bits or higher. So that is useless to implement if solving for private keys below 254 bits.

You want to present original work? How about this: actually understand the problem, and start from a scratch blank folder. You will always reach to something different than what you've copy pasted, updated here and there, and claimed as original.

So what exactly is your intent?