Nevertheless, it is a Bitcoin-compliant transaction that can be replaced at any time as long as the original transaction has not been confirmed, isn't it ? 1. You commit your Script behind some address type. Which means, that people won't see for example "OP_RIPEMD160 <puzzleHash> OP_EQUALVERIFY <solverKey> OP_CHECKSIG" immediately, but they will see just some P2WSH hash, or some P2TR public key, nothing else. 2. Then, when you reveal the Script behind your address, it is too late to modify it, because it is already deeply confirmed. And then, nobody can create an identical Script with a different "<solverKey>" or replace solver's key. 3. If you spend coins from the Script mentioned above, then everyone can verify, that you know SHA-256 of the public key. Only the true solver will know that. Then, some huge mining pool can agree to deposit some coins, to learn the solution to the puzzle. 4. The solver will see, that coins are deposited to "OP_SHA256 <revealedHash> OP_EQUALVERIFY <solverKey> OP_CHECKSIG". Everyone will know the address, and the Script behind it, but only the solver will know the public key to the puzzle. 5. The solver can pass a transaction to the mining pool, claiming all coins from his address. Then, the pool can learn the public key, and sweep it with 100% transaction fee. Edit: In general, it seems to be resistant to some simple attacks: 1. If the solver is lying, he will be unable to produce a proper address, and spend it, while revealing SHA-256 of the public key, so nobody will give him any coins in the first place. 2. If someone is observing the chain, and trying to replicate "I have the key" signal with a different solver's key, then that person will be unable to do that before the solver, because the real solver's address will be deeply confirmed. If we count the earliest attempt as the legit one, then any future solvers will not get anything. 3. Rewarding the solver is not direct, it is more similar to HTLC: there are two conditions: the solver's public key (with signature), and the puzzle's public key (where the hash of it is revealed in the Script). Which means, that the solver cannot run away with coins, without revealing the public key to the puzzle. 4. It is compatible with full-RBF and other network rules: the puzzle can be sweeped with 100% fee, and if it will be done by some pool, then the transaction will start from a single confirmation. Reorging a single block is not that easy. However, if the risk of reorg is too high, then rewarded amounts can be adjusted if needed, and someone may agree to reveal the public key for 6 BTC, instead of 6.6 BTC. We will see. This is a great idea if it works. Someone would need to test this in the puzzle 66 range to see if it works...
|
|
|
Well, someone would take half? Or not ? ![Cry](https://bitcointalk.org/Smileys/default/cry.gif) I'm not sure if there will be enough left to drink beer. I don't know if it's worse to be a puzzle winner or a bot. Something else must be thought of; this cannot be done like this. It's not worth it to anyone.
|
|
|
Here is my log
INFO:root:Running scan... INFO:root:Running scan... INFO:root:Extracted Public Key: 2024-07-24 07:32 029a3a2ae3ad3858cf49421e6ff547598bb8da72c2bce50490067d9ce7b2e2dc90 INFO:root:Running command: echo '029a3a2ae3ad3858cf49421e6ff547598bb8da72c2bce50490067d9ce7b2e2dc90 20000000000000000:3ffffffffffffffff' | nc -v localhost 8080 INFO:root:Keyhunt stdout: 29c8156de964053a9 ERROR:root:Keyhunt stderr: Connection to localhost (127.0.0.1) 8080 port [tcp/http-alt] succeeded!
INFO:root:Private Key: 29c8156de964053a9 INFO:root:WIF Key: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZhN8faDbJc2NqwACiuJ Daemon not running; try 'electrum daemon -d' starting daemon (PID 552717)
INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00022 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 1 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00033 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 2 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00044 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 3 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00055 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 3 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00066 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 4 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00077 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 5 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00088 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 6 failed. ERROR:root:Max fee bump attempts reached for transaction bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386. Daemon stopped
So your bot doesn't check for the latest or highest trans fee, it just auto increments until it's the highest? Looks like it reached your set amount of attempts before overtaking the highest fee. Yes. Somewhere at 59.53 USD. I think this is all nonsense. If we were on a real puzzle 66, we would threw in the garbage 3 BTC in 5 minutes. That's bad.
|
|
|
Here is my log
INFO:root:Running scan... INFO:root:Running scan... INFO:root:Extracted Public Key: 029a3a2ae3ad3858cf49421e6ff547598bb8da72c2bce50490067d9ce7b2e2dc90 INFO:root:Running command: echo '029a3a2ae3ad3858cf49421e6ff547598bb8da72c2bce50490067d9ce7b2e2dc90 20000000000000000:3ffffffffffffffff' | nc -v localhost 8080 INFO:root:Keyhunt stdout: 29c8156de964053a9 ERROR:root:Keyhunt stderr: Connection to localhost (127.0.0.1) 8080 port [tcp/http-alt] succeeded!
INFO:root:Private Key: 29c8156de964053a9 INFO:root:WIF Key: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZhN8faDbJc2NqwACiuJ Daemon not running; try 'electrum daemon -d' starting daemon (PID 552717)
INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00022 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 1 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00033 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 2 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00044 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 3 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00055 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 3 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00066 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 4 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00077 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 5 failed. Trying again... INFO:root:Running bumpfee command: electrum bumpfee bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386 0.00088 --destination bc1qgtuf2hke00apm2sl6xxu0geeme7g7hnx6k3ydy WARNING:root:Fee bump attempt 6 failed. ERROR:root:Max fee bump attempts reached for transaction bc16e7ce388d936c93583d17c5e691a2677ee9eabbc0ae6d03841fc5e0f1a386. Daemon stopped
|
|
|
Miners prioritize transactions with higher fees over those they encounter first.
To address this, one solution is to operate a full node, deactivate full-RBF (Replace-by-Fee), and broadcast your transaction with a fee 20 times higher than the usual rate. This would provide a 20-second window before the transaction reaches another full-RBF node, increasing the chance that a miner might include it in a block by mistake. However, I doubt this will happen, as I believe miners will likely engage in this bot fee competition directly.
@nomachine: may I ask why you deleted your message ? Maybe it's a stupid idea that the puzzle winner has to make a kind of bot also for his transaction. . ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
Maybe it's mind game, all bot busy for find test , and newly bots maybe also block by ping many times, and in background they play real 66 bit puzzle transaction ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) A professional bot definitely does not use mempool.space or similar APIs. It uses its own node, so blocking is only for inexperienced bots that use third-party APIs. You actually need full-node distro. And mempool in local network .You should use a separate machine just for that, and another very powerful machine for the Bot and BSGS/Keyhunt. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) So, how many machines you have ? ![Undecided](https://bitcointalk.org/Smileys/default/undecided.gif) Five just in my room. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) What you talking about? I do it with just my Ryzen 9 3900x with VMs when needed. I have UmbrelOS with a node and mempool on a separate machine, which can be a NUC or any small PC (with 1TB drive for node). I don't want to waste RAM with VMs on a machine with a BSGS server. So, you host entire Bitcoin blocks—600 GB—locally? ![Roll Eyes](https://bitcointalk.org/Smileys/default/rolleyes.gif) Can you read? Yes, I just wrote that above. By running a node, you support the Bitcoin network. You can experiment with Bitcoin-related applications directly.....
|
|
|
Maybe it's mind game, all bot busy for find test , and newly bots maybe also block by ping many times, and in background they play real 66 bit puzzle transaction ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) A professional bot definitely does not use mempool.space or similar APIs. It uses its own node, so blocking is only for inexperienced bots that use third-party APIs. You actually need full-node distro. And mempool in local network .You should use a separate machine just for that, and another very powerful machine for the Bot and BSGS/Keyhunt. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) So, how many machines you have ? ![Undecided](https://bitcointalk.org/Smileys/default/undecided.gif) Five just in my room. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) What you talking about? I do it with just my Ryzen 9 3900x with VMs when needed. I have UmbrelOS with a node and mempool on a separate machine, which can be a NUC or any small PC (with 1TB drive for node). I don't want to waste RAM with VMs on a machine with a BSGS server.
|
|
|
Maybe it's mind game, all bot busy for find test , and newly bots maybe also block by ping many times, and in background they play real 66 bit puzzle transaction ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) A professional bot definitely does not use mempool.space or similar APIs. It uses its own node, so blocking is only for inexperienced bots that use third-party APIs. You actually need full-node distro. And mempool in local network .You should use a separate machine just for that, and another very powerful machine for the Bot and BSGS/Keyhunt. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) So, how many machines you have ? ![Undecided](https://bitcointalk.org/Smileys/default/undecided.gif) Five just in my room. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
Maybe it's mind game, all bot busy for find test , and newly bots maybe also block by ping many times, and in background they play real 66 bit puzzle transaction ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) A professional bot definitely does not use mempool.space or similar APIs. It uses its own node, so blocking is only for inexperienced bots that use third-party APIs. You actually need full-node distro. And mempool in local network .You should use a separate machine just for that, and another very powerful machine for the Bot and BSGS/Keyhunt. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
We could see a situation where multiple or thousands of bots continuously send replacement transactions, each one with progressively higher fees, trying to claim the coins for themselves. Since no bot is willing to give up the opportunity for another, this could result in a continuous increase in fees. In the end, almost all of the funds might be eaten up by transaction fees, with most of the money going to the miners. Is it possible that someone runs a bot waiting for 66bit having fees set to almost all balance just to piss everyone off ? You know the answer ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) It doesn't matter whether the first replacement transaction or 24 in a row is 6 BTC; the result will be the same in the end.
|
|
|
I have managed to get a "Bot" but it's not a bot i have still to manually give the private key because i didn't know how to extract public key once its in the mempool plus i didn't know how to run Keyhunt or kangaroo after getting public key, sooooo i guess i'll have to be awake lol, i'm so bad
I would be happy for any improvement or any opinions if the following script may work?
I would like to ask for a small script that extract public key once it's seen on the mempool. I couldn't do it myself sadly. Could anyone help?
Thank you!
nomachine posted his bot a couple pages back that includes getting public key, running keyhunt, and sweeping funds. Please note that this is not the definitive version. Everyone needs to test and retest to create the final version. However, it serves as an example of what it should look like. The bot PC should have nothing installed except the bot. Anything else can affect the response and screw up. A very good ping and a reliable connection to the mempool are crucial. one of the clues: This code only work for TX already confirmed
while True: logging.info("Running scan...") pubkey = get_exact_public_key_unconfirmed(address) or get_exact_public_key_confirmed(address) if pubkey: logging.info(f"Extracted Public Key: {pubkey}") save_public_key(pubkey)
# Uncomment to run Keyhunt (ensure you have the keyhunt tool and the correct parameters) run_keyhunt(pubkey) I have two functions. One is for unconfirmed and the other for confirmed separately ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
The important thing is to be successful without getting in front of the computer. I think you were on the computer for the first exam. Now we will see if the bot you created will perform transactions without your knowledge. The creator will do this work while everyone is asleep and at any time period. The result will be very different.
Yep. And sh** happens with "full" automated programs.
|
|
|
Ok, all of you BOT owners. Get ready for round 2 of RBF test.
I am a newb with ding certain things on the blockchain and what I am trying to do. I probably shouldn't be doing this, but sometimes, mistakes, are the best things to learn from.
I would like all to participate as they did in the last 66 bit bot test. But def at least the winner, albert0bsd. But I know the more, the better chances to test different strategies or programs/processes, so I would like to get all bot owners on board.
Same setup, key is in the 66 bit range.
Address:
166Bitrbfa16oR7DKKSzgdhU4MpVKE4cKb
It seemed like everyone has an auto bot...meaning all you are doing is putting in the address on some type of watch list, and once your program gets a hit for the address, the bots do their thing to find the key and alter the original transaction.
So if everyone who is going to participate, put in the above address into your bot ASAP. I would like to get a response back from at least albert0bsd that he is entered the address and is ready to proceed.
All I ask, if one of you are successful in diverting the coinage, you PM me and tell me how you did it. That's all. Just a request, not a requirement lol.
I'm not sure I will say the exact time I send funds out of the address, because that is more realistic to 66's transfer, no one is going to let us know they are about to sweep the coins...but that could change.
This may fail, may be successful. We all shall see.
Am I missing any information/anything else to put out there?
Ok, bot owners, let's get ready to rumble. Who is ready? Let's do it.
You are so right, no one tells you when to withdraw puzzle 66, they do the transaction suddenly. You can also notify Alberto and other people who own the bots and withdraw the money suddenly. You can also organize a bait and at the same time you can run a real transaction for 13zb1hQbWVsc2S7ZTZnP2G4undNNpdh5so. That would be fun. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
This may fail, may be successful. We all shall see.
Am I missing any information/anything else to put out there?
Ok, bot owners, let's get ready to rumble. Who is ready? Let's do it.
You don't need to do it. ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif) You skeered? LOL. Let's just try it. It's already set up. I will be banned by mempool.space due to DDoS attack LOL. SO, you have a botnet to send transactions ? ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Nope. But it's not a bad idea. The more IP addresses and computers involved the better.
|
|
|
This may fail, may be successful. We all shall see.
Am I missing any information/anything else to put out there?
Ok, bot owners, let's get ready to rumble. Who is ready? Let's do it.
You don't need to do it. ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif) You skeered? LOL. Let's just try it. It's already set up. I will be banned by mempool.space due to DDoS attack LOL.
|
|
|
This may fail, may be successful. We all shall see.
Am I missing any information/anything else to put out there?
Ok, bot owners, let's get ready to rumble. Who is ready? Let's do it.
You don't need to do it. ![Tongue](https://bitcointalk.org/Smileys/default/tongue.gif)
|
|
|
Are you sure about that?
Nah. There are too many numbers on the screen. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
You can use nomachine's Rust Kangaroo a few posts back, or write a Python script that does the job according to your requirements (e.g. "that actually works"). Too slow? Well, don't expect to find something that "actually works", is fast, and solves 130, sitting out there for you to snug up and inherit 13 BTC tomorrow.
Not in Rust. Pure C++ with GMP. Here is the latest version that goes 470K Hops per second. Theoretically, with 12 cores, it can achieve 5 million hops per second. The more cores you have, the better the result will be. However, it's not worth using this for a puzzle above 70bit. A GPU must be used instead.... Pure self-contained Python Kangaroo with no libraries required. 225K Hops per second. DO NOT USE THIS TO SEARCH FOR 130. It is just an educational, reference-only example. All the math uses Python integers. kangaroo.py import math, os, sys, time
class S: # Scalar field N = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
@staticmethod def add(a, b): return (a + b) % S.N
class F: # Curve field P = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
@staticmethod def add(a, b): return (a + b) % F.P
@staticmethod def mul(a, b): return (a * b) % F.P
@staticmethod def pow(b, e): return pow(b, e, F.P)
@staticmethod def sqrt(a): return F.pow(a, (F.P + 1) // 4)
@staticmethod def inv(a): if a == 0: return 0
r = 1 s = 0 low = a % F.P high = F.P
while low > 1: q = high // low nm = s - q * r nw = high - low * q high = low s = r low = nw r = nm
return r % F.P
class Point: # Affine point def __init__(self, x, y, parity=-1): self.x = x self.y = y if parity == -1 else Point.calc_y(x, parity)
@classmethod def uncompress(cls, s): parity, xh = int(s[:2], 16), s[2:] if parity not in [2, 3]: raise Exception("Expected parity 02 or 03") return Point(int(xh, 16), 0, parity % 2)
@staticmethod def calc_y(x, parity): y = F.sqrt(F.add(F.pow(x, 3), 7)) # y = sqrt(x**3 + 7) return y if parity == y % 2 else F.P - y
class JPoint: # Jacobian point def __init__(self, x, y, z): self.x = x self.y = y self.z = z
def affine(self): z = F.inv(self.z) z2 = F.mul(z, z) return Point(F.mul(self.x, z2), F.mul(self.y, F.mul(z, z2)))
def mul(self, n): if self.y == 0 or n == 0: return JPoint(0, 0, 1)
if n == 1: return self
if n < 0 or n >= S.N: return self.mul(n % S.N)
if (n % 2) == 0: return self.mul(n // 2).double()
return self.mul(n // 2).double().add(self)
def double(self): if self.y == 0: return JPoint(0, 0, 0)
y2 = F.mul(self.y, self.y) s = F.mul(4 * self.x, y2) M = F.mul(3 * self.x, self.x)
x = F.add(F.mul(M, M), - 2 * s) return JPoint(x, F.add(F.mul(M, s - x), -F.mul(8 * y2, y2)), F.mul(2 * self.y, self.z))
def add(self, q): if self.y == 0: return q if q.y == 0: return self
qz2 = F.mul(q.z, q.z) pz2 = F.mul(self.z, self.z) U1 = F.mul(self.x, qz2) U2 = F.mul(q.x, pz2) S1 = F.mul(self.y, F.mul(q.z, qz2)) S2 = F.mul(q.y, F.mul(self.z, pz2))
if U1 == U2: if S1 != S2: return JPoint(0, 0, 1) return self.double()
H = F.add(U2, -U1) R = F.add(S2, -S1) H2 = F.mul(H, H) H3 = F.mul(H, H2) U1H2 = F.mul(U1, H2) nx = F.add(F.mul(R, R), -F.add(H3, 2 * U1H2)) ny = F.add(F.mul(R, F.add(U1H2, -nx)), -F.mul(S1, H3)) nz = F.mul(H * self.z, q.z)
return JPoint(nx, ny, nz)
class Group: G = Point( 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 )
@staticmethod def add(p, q): m = F.mul(F.add(p.y, -q.y), F.inv(F.add(p.x, -q.x))) x = F.add(F.add(F.mul(m, m), -p.x), -q.x) return Point(x, F.add(F.mul(m, F.add(q.x, -x)), -q.y))
@classmethod def mul(cls, p, k): # [k]P point scalar multiplication return JPoint(p.x, p.y, 1).mul(k).affine()
@classmethod def batch_add(cls, ga, gb): n = len(ga) d = [0] * n p = [0] * n z = 1 for i in range(n): d[i] = F.add(ga[i].x, -gb[i].x) z = F.mul(z, d[i]) p[i] = z
t = F.inv(z)
for i in range(n - 1, -1, -1): if i > 0: xi = F.mul(t, p[i - 1]) t = F.mul(t, d[i]) else: xi = t
m = F.mul(F.add(ga[i].y, -gb[i].y), xi) ga[i].x = F.add(F.add(F.mul(m, m), -ga[i].x), -gb[i].x) ga[i].y = F.add(F.mul(m, F.add(gb[i].x, -ga[i].x)), -gb[i].y)
class TrueRandom: def __init__(self, max_value: int, num_bits: int, min_value: int = 0): self.upper_bound = max_value - min_value + 1 self.min = min_value self.num_bits = num_bits self.domain = 2 ** num_bits self.num_bytes = math.ceil(num_bits / 8) self.shift = 8 * self.num_bytes - num_bits
def get_next(self): random_bytes = os.urandom(self.num_bytes)
# trim to num_bits random_int = int.from_bytes(random_bytes, byteorder='big') >> self.shift
# normalize from domain range to target range sample = self.upper_bound * random_int // self.domain
return sample + self.min
def kangaroo_with_results(k1, k2, P, dp, herd_size): k_cand, counter, tbl_size = kangaroo(k1, k2, P, dp, herd_size=herd_size)
k = k_cand[0] if k1 <= k <= k2: P_check = Group.mul(Group.G, k) if P_check.x == P.x: print(f'Key: {hex(k)}\nGroup ops: {counter}')
return k_cand, counter, tbl_size
def create_kangaroo(kang_type, pos: int, herd_pts, herd_distances, k1, k2, P, rnd: TrueRandom, v): if kang_type == 0: # d = rnd.get_next() # [0, k2 - k1) d = (k2 - k1 + 1) + pos * v # b/2 + i*v # d = (k2 - k1 + 1) // 2 herd_distances[pos] = d herd_pts[pos] = Group.mul(Group.G, k1 + d) else: # d = rnd.get_next() - (k2 - k1 + 1) // 2 # [-(k2-k1)/2, (k2-k1)/2] d = (k2 - k1 + 1) // 2 + pos * v # b + i*v # d = 0 herd_distances[pos] = d herd_pts[pos] = Group.add(P, Group.mul(Group.G, d))
def check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd, respawn_dead=True, stop_at_dp=True): x = herd[pos].x
if x & dp_mask == 0: item = hashmap.get(x)
if item is not None: if item[0] == kang_type ^ 1: # collision d_wild, d_tame = (item[1], dist[pos]) if kang_type == 0 else (dist[pos], item[1]) return [S.add(k1 + d_tame, - d_wild)], 0 else: # print(f'Dead kangaroo at {pos}') if respawn_dead: # create_kangaroo(kang_type, pos, herd, dist, k1, k2, P, R) # move along with a small random value d = v_rnd.get_next() dist[pos] += d herd[pos] = Group.add(herd[pos], Group.mul(Group.G, d))
# this will recurse until a non-dead kangaroo is produced k, created = check_col(kang_type, hashmap, herd, dist, pos, k1, k2, P, dp_mask, R, v_rnd) return k, 1 + created else: hashmap[x] = (kang_type, dist[pos])
return 0, 0
def build_jump_distances(alpha, with_points=False): jump_points = [] jump_distances = []
# compute A (jump distances) such that average(A) is closest to expected alpha # Pollard says choosing A as powers of two feels like "needs more investigation" min_diff = 1 while True: jump_distance = 2 ** len(jump_distances) jump_distances.append(jump_distance) if with_points: jump_points.append(Group.mul(Group.G, jump_distance))
alpha_real = sum(jump_distances) / len(jump_distances) diff = abs(1 - alpha_real / alpha) if alpha_real >= alpha: if diff > min_diff: jump_distances.pop() break if diff < min_diff: min_diff = diff
return jump_distances, jump_points
def kangaroo(k1, k2, P, dp: int, herd_size: int = 128): b = k2 - k1 + 1 # size of search interval m = herd_size + herd_size # m/2 + m/2 # parallel case - minimize alpha for total number of jumps alpha = m * math.sqrt(b) / 4 # m * sqrt(b) / 4
jump_distances, jump_points = build_jump_distances(alpha, with_points=True) alpha_real = sum(jump_distances) / len(jump_distances)
n = len(jump_distances)
# adjust alpha to the actual average jump distance alpha_expected = alpha alpha = alpha_real
# expected total number of jumps for each trailing kangaroo (1 per processor) expected_trailing_jumps = 2 * math.sqrt(b) / m # 2 * sqrt(b) / m
# beta = 0.553 # serial case # ab_jumps = int(alpha * beta) # serial case # max_tame_distance = int(alpha * alpha * beta + b // 2)
# expected number of jumps done by a trailing kangaroo after it enters the [b, ...] region # this would equal the number of jumps done by a tame kangaroo that starts from b num_tame_jumps = 4 * alpha / (m * m) # 4 * alpha / (m**2) max_tame_distance = int(alpha * num_tame_jumps + b) # average jump size * num jumps + start # max_wild_distance = int(alpha * num_tame_jumps + b/2) # average jump size * num jumps + start # = (2*a/m)**2 = (sqrt(b) / 2)**2
# set v to the "partition" size for a processor, and not a power of two v = b // m - 1 # (b/2) / (m/2) # v = herd_size v_rnd = TrueRandom(v, 256)
hashmap = {} wilds: list = [None] * herd_size tames: list = [None] * herd_size w_dist = [0] * herd_size t_dist = [0] * herd_size counter = 0 done_ab_jumps = 0
expected_total_jumps = math.ceil((num_tame_jumps + expected_trailing_jumps) * herd_size) print( f'processors: {m}' f'\n num jump distances: {n}' f'\nmax jumps per tame kangaroo: {math.ceil(num_tame_jumps)}' f'\nmax jumps per wild kangaroo: {math.ceil(expected_trailing_jumps)}' f'\n expected total jumps: {expected_total_jumps} {math.log2(expected_total_jumps):.2f} bits' f'\n avg real jump distance: {round(alpha_real)} {math.log2(alpha_real):.2f} bits' f'\n avg expected jump distance: {round(alpha_expected)} {math.log2(alpha_expected):.2f} bits' f'\n expected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits' # f'\n expected max wild distance: {max_wild_distance} {math.log2(max_wild_distance):.2f} bits' )
R = TrueRandom(k2 - k1, 256, 0) dp_mask = (1 << dp) - 1
for idx in range(herd_size): create_kangaroo(0, idx, tames, t_dist, k1, k2, P, R, v) counter += 1
k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd) counter += born if k: return k, counter, len(hashmap)
create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R, v) counter += 1
k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd) counter += born if k: return k, counter, len(hashmap)
batch_jp: list = [None] * herd_size
start_time = time.time() last_p_time = 0 while True: if done_ab_jumps < num_tame_jumps: # jump tames for idx in range(herd_size): d = tames[idx].x % n # tames[idx] = Group.add(tames[idx], jump_points[d]) # un-batched addition batch_jp[idx] = jump_points[d] t_dist[idx] += jump_distances[d]
Group.batch_add(tames, batch_jp)
for idx in range(herd_size): counter += 1
k, born = check_col(0, hashmap, tames, t_dist, idx, k1, k2, P, dp_mask, R, v_rnd) counter += born if k: return k, counter, len(hashmap)
done_ab_jumps += 1 if done_ab_jumps >= num_tame_jumps: # new_max = max(t_dist) # avg_dist = sum(t_dist) / len(t_dist) # print( # f'Tames are done.' # f'\nExpected max tame distance: {max_tame_distance} {math.log2(max_tame_distance):.2f} bits' # f'\nAverage max tame distance: {avg_dist} {math.log2(avg_dist):.2f} bits' # f'\nActual max tame distance: {new_max} {math.log2(new_max):.2f} bits' # ) # max_tame_distance = max(max_tame_distance, new_max) # max_wild_distance = int(max_tame_distance + b / 2) # add initial tame - wild gap
# create new tames herd for idx in range(herd_size): d = b + idx * v + v_rnd.get_next() # b/2 + i*v + z
t_dist[idx] = d tames[idx] = Group.mul(Group.G, k1 + d) counter += 1
done_ab_jumps = 0
for idx in range(herd_size): d = wilds[idx].x % n # wilds[idx] = Group.add(wilds[idx], jump_points[d]) # unbatched addition batch_jp[idx] = jump_points[d] w_dist[idx] += jump_distances[d]
Group.batch_add(wilds, batch_jp)
for idx in range(herd_size): counter += 1
k, born = check_col(1, hashmap, wilds, w_dist, idx, k1, k2, P, dp_mask, R, v_rnd) counter += born if k: return k, counter, len(hashmap)
if w_dist[idx] > max_tame_distance: # create_kangaroo(1, idx, wilds, w_dist, k1, k2, P, R) z = v_rnd.get_next() d = b // 2 + idx * v + z # b + i*v + z
w_dist[idx] = d wilds[idx] = Group.add(P, Group.mul(Group.G, d))
counter += 1
total_time = time.time() - start_time if total_time - last_p_time > 3: last_p_time = total_time print(f'Ops: {counter} Table size: {len(hashmap)} Speed: {counter / total_time:.0f} ops/s')
def run_puzzle(idx: int, pub_key, dp: int = 0, herd_size: int = 128, benchmark=0): # puzzle #X has (X - 1) unknown bits k1 = 1 << (idx - 1) k2 = (k1 << 1) - 1
# subtract k1 to search in a [0, k2 - k1) interval k2 -= k1 k1 = 0
P = Point.uncompress(pub_key)
# subtract (k2 - k1)G from P to bring target point's k to [0, k2 - k1) interval P = Group.add(P, Group.mul(Group.G, -(k2 + 1)))
now = time.time() _, ops, hashmap_size = kangaroo_with_results(k1, k2, P, dp, herd_size) total_time = time.time() - now print(f'Ops: {ops} Stored: {hashmap_size}') print(f'Speed: {ops / total_time:.0f} ops/s')
if __name__ == '__main__': # r, p = int(sys.argv[1]), sys.argv[2] # run_puzzle(r, p, dp=0, herd_size=128)
# run_puzzle(32, '0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69', # herd_size=512)
run_puzzle(48, '0291bee5cf4b14c291c650732faa166040e4c18a14731f9a930c1e87d3ec12debb', dp=8, herd_size=1024)
Puzzle 48: processors: 2048 num jump distances: 38 max jumps per tame kangaroo: 6899 max jumps per wild kangaroo: 11586 expected total jumps: 18927375 24.17 bits avg real jump distance: 7233629130 32.75 bits avg expected jump distance: 6074001000 32.50 bits expected max tame distance: 190638869267657 47.44 bits ... Ops: 17607859 Table size: 68719 Speed: 225400 ops/s Key: 0x2de6d7ce3b9b Group ops: 18288933 Ops: 18288933 Stored: 71317 Speed: 222616 ops/s
I have almost the same script with Jacobian coordinates in C++ but using #include <boost/multiprecision/cpp_int.hpp> It's not a million per second, but it's very close. ![Grin](https://bitcointalk.org/Smileys/default/grin.gif)
|
|
|
Is there any way to have this running on macOS natively ? It would be awesome to try the new M processors with it.
I have tried to port your version but some libraries are missing for macOS thats a pity.
kangaroo.cpp #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <array> #include <set> #include <sstream>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& P0 = P[0]; const mpz_class& P1 = P[1]; const mpz_class& Q0 = Q[0]; const mpz_class& Q1 = Q[1]; mpz_class lmbda, num, denom, inv; if (P != Q) { num = Q1 - P1; denom = Q0 - P0; } else { if (P1 == 0) return Z; num = 3 * P0 * P0; denom = 2 * P1; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); lmbda = (num * inv) % p; mpz_class x = (lmbda * lmbda - P0 - Q0) % p; if (x < 0) x += p; mpz_class y = (lmbda * (P0 - x) - P1) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { mpz_class result; mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t()); if (result != 0) return false;
T.push_back(P); t.push_back(Pindex);
// Create a set of Points from T for fast lookup std::set<Point> T_set(T.begin(), T.end());
// Create a set of Points from W for quick existence check std::set<Point> W_set(W.begin(), W.end());
// Iterate through W and check if each element is in T for (const auto& match : W_set) { if (T_set.find(match) != T_set.end()) { auto it = find(T.begin(), T.end(), match); int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP);
// Measure time once and reuse it auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;
// Open file once, write all data, and close it static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl;
return true; } }
return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % system_profiler SPSoftwareDataType Software: System Software Overview: System Version: macOS 13.6.1 (22G313) Kernel Version: Darwin 22.6.0 Boot Volume: macOS Boot Mode: Normal User Name: nomachine (nomachine) Secure Virtual Memory: Enabled System Integrity Protection: Enabled Time since boot: 1 day, 14 hours, 11 minutes nomachine@iMac Desktop % nano kangaroo.cpp nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % ./kangaroo - KANGAROO: Tue Jul 23 08:50:41 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
- PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 63 sec
|
|
|
You can use nomachine's Rust Kangaroo a few posts back, or write a Python script that does the job according to your requirements (e.g. "that actually works"). Too slow? Well, don't expect to find something that "actually works", is fast, and solves 130, sitting out there for you to snug up and inherit 13 BTC tomorrow.
Not in Rust. Pure C++ with GMP. Here is the latest version that goes 470K Hops per second. #include <gmp.h> #include <gmpxx.h> #include <chrono> #include <ctime> #include <fstream> #include <iomanip> #include <iostream> #include <random> #include <vector> #include <array> #include <set> #include <sstream>
using namespace std;
typedef array<mpz_class, 2> Point;
const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16); const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16); const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16); const Point PG = {Gx, Gy}; const Point Z = {0, 0};
auto starttime = chrono::high_resolution_clock::now();
Point add(const Point& P, const Point& Q, const mpz_class& p = modulo) { if (P == Z) return Q; if (Q == Z) return P; const mpz_class& P0 = P[0]; const mpz_class& P1 = P[1]; const mpz_class& Q0 = Q[0]; const mpz_class& Q1 = Q[1]; mpz_class lmbda, num, denom, inv; if (P != Q) { num = Q1 - P1; denom = Q0 - P0; } else { if (P1 == 0) return Z; num = 3 * P0 * P0; denom = 2 * P1; } mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t()); lmbda = (num * inv) % p; mpz_class x = (lmbda * lmbda - P0 - Q0) % p; if (x < 0) x += p; mpz_class y = (lmbda * (P0 - x) - P1) % p; if (y < 0) y += p; return {x, y}; }
Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo) { Point R = Z; Point current = P; mpz_class k_copy = k; while (k_copy > 0) { if (k_copy % 2 == 1) { R = add(R, current, p); } current = add(current, current, p); k_copy >>= 1; } return R; }
mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo) { mpz_class X_cubed = (X * X * X) % p; mpz_class tmp = (X_cubed + mpz_class(7)) % p; mpz_class Y; mpz_class exp = (p + mpz_class(1)) / mpz_class(4); mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t()); if ((Y % 2) != y_parity) { Y = p - Y; } return Y; }
bool comparator(const Point& P, const mpz_class& Pindex, const mpz_class& DP_rarity, std::vector<Point>& T, std::vector<mpz_class>& t, const std::vector<Point>& W, const std::vector<mpz_class>& w) { mpz_class result; mpz_fdiv_r(result.get_mpz_t(), P[0].get_mpz_t(), DP_rarity.get_mpz_t()); if (result != 0) return false;
T.push_back(P); t.push_back(Pindex);
// Create a set of Points from T for fast lookup std::set<Point> T_set(T.begin(), T.end());
// Create a set of Points from W for quick existence check std::set<Point> W_set(W.begin(), W.end());
// Iterate through W and check if each element is in T for (const auto& match : W_set) { if (T_set.find(match) != T_set.end()) { auto it = find(T.begin(), T.end(), match); int index = distance(T.begin(), it); mpz_class tP = t[index]; mpz_class wP = w[distance(W.begin(), find(W.begin(), W.end(), match))]; mpz_class dec = abs(tP - wP);
// Measure time once and reuse it auto end = chrono::system_clock::now(); time_t end_time = chrono::system_clock::to_time_t(end); cout << "\n\033[01;33m[+]\033[32m PUZZLE SOLVED: \033[32m" << ctime(&end_time) << "\r"; cout << "\r\033[01;33m[+]\033[32m Private key (dec): \033[32m" << dec << "\033[0m" << endl;
// Open file once, write all data, and close it static std::ofstream file("KEYFOUNDKEYFOUND.txt", std::ios::app); file << "\n" << string(140, '-') << endl; file << "SOLVED " << ctime(&end_time); file << "Private Key (decimal): " << dec << endl; file << "Private Key (hex): " << dec.get_str(16) << endl; file << string(140, '-') << endl;
return true; } }
return false; }
vector<mpz_class> generate_powers_of_two(int hop_modulo) { vector<mpz_class> powers(hop_modulo); for (int pw = 0; pw < hop_modulo; ++pw) { powers[pw] = mpz_class(1) << pw; } return powers; }
string search(const vector<Point>& P, const Point& W0, const mpz_class& DP_rarity, int Nw, int Nt, int hop_modulo, const mpz_class& upper_range_limit, const mpz_class& lower_range_limit, const vector<mpz_class>& powers_of_two) { vector<Point> T(Nt, Z), W(Nw, Z); vector<mpz_class> t(Nt), w(Nw);
gmp_randclass rand(gmp_randinit_default);
for (int k = 0; k < Nt; ++k) { t[k] = lower_range_limit + rand.get_z_range(upper_range_limit - lower_range_limit); T[k] = mul(t[k]); }
for (int k = 0; k < Nw; ++k) { w[k] = rand.get_z_range(upper_range_limit - lower_range_limit); W[k] = add(W0, mul(w[k])); }
long long Hops = 0, Hops_old = 0; auto t0 = chrono::high_resolution_clock::now(); vector<mpz_class> memo(hop_modulo);
for (int pw = 0; pw < hop_modulo; ++pw) { memo[pw] = powers_of_two[pw]; }
bool solved = false; while (!solved) { for (int k = 0; k < (Nt + Nw); ++k) { ++Hops; if (k < Nt) { mpz_class pw = T[k][0] % hop_modulo; solved = comparator(T[k], t[k], DP_rarity, T, t, W, w); if (solved) break; t[k] += memo[pw.get_ui()]; T[k] = add(P[pw.get_ui()], T[k], modulo); } else { int n = k - Nw; mpz_class pw = W[n][0] % hop_modulo; solved = comparator(W[n], w[n], DP_rarity, W, w, T, t); if (solved) break; w[n] += memo[pw.get_ui()]; W[n] = add(P[pw.get_ui()], W[n], modulo); } }
auto t1 = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(t1 - t0).count(); if (elapsed_seconds > 1.0) { double hops_per_second = static_cast<double>(Hops - Hops_old) / elapsed_seconds; auto elapsed_time = chrono::duration_cast<chrono::seconds>(t1 - starttime); int hours = chrono::duration_cast<chrono::hours>(elapsed_time).count(); int minutes = chrono::duration_cast<chrono::minutes>(elapsed_time % chrono::hours(1)).count(); int seconds = (elapsed_time % chrono::minutes(1)).count(); stringstream elapsed_time_str; elapsed_time_str << setfill('0') << setw(2) << hours << ":" << setfill('0') << setw(2) << minutes << ":" << setfill('0') << setw(2) << seconds; double p_2 = log2(Hops); cout << "\r[+] [Hops: 2^" << fixed << setprecision(2) << p_2 << " <-> " << fixed << setprecision(0) << hops_per_second << " h/s] [" << elapsed_time_str.str() << "]" << flush; t0 = t1; Hops_old = Hops; } }
cout << "\r[+] Hops: " << Hops << endl; auto end = chrono::high_resolution_clock::now(); double elapsed_seconds = chrono::duration_cast<chrono::duration<double>>(end - starttime).count(); return "\r[+] Solution time: " + to_string(elapsed_seconds) + " sec"; }
int main() { int puzzle = 50; string compressed_public_key = "03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6"; int kangaroo_power = 6; mpz_class lower_range_limit = mpz_class(1) << (puzzle - 1); mpz_class upper_range_limit = (mpz_class(1) << puzzle) - 1;
mpz_class DP_rarity = mpz_class(1) << ((puzzle - 2 * kangaroo_power) / 2 - 2); int hop_modulo = ((puzzle - 1) / 2) + kangaroo_power;
int Nt = 1 << kangaroo_power; int Nw = 1 << kangaroo_power;
vector<mpz_class> powers_of_two = generate_powers_of_two(hop_modulo);
mpz_class X, Y; if (compressed_public_key.length() == 66) { X = mpz_class(compressed_public_key.substr(2), 16); Y = X2Y(X, stoi(compressed_public_key.substr(0, 2)) - 2); } else { cout << "[error] pubkey len(66/130) invalid!" << endl; return 1; }
Point W0 = {X, Y}; auto starttime = chrono::high_resolution_clock::now(); time_t currentTime = time(nullptr); cout << "\r\033[01;33m[+]\033[32m KANGAROO: \033[01;33m" << ctime(¤tTime) << "\033[0m" << "\r"; cout << "[+] [Puzzle]: " << puzzle << endl; cout << "[+] [Lower range limit]: " << lower_range_limit << endl; cout << "[+] [Upper range limit]: " << upper_range_limit << endl; cout << "[+] [EC Point Coordinate X]: " << X << endl; cout << "[+] [EC Point Coordinate Y]: " << Y << endl; mpz_class expected_hops = 2.2 * sqrt(mpz_class(1) << (puzzle - 1)); double log_expected_hops = log2(expected_hops.get_d()); cout << "[+] [Expected Hops: 2^" << fixed << setprecision(2) << log_expected_hops << " (" << expected_hops << ")]" << endl;
vector<Point> P = {PG}; P.reserve(256); for (int k = 0; k < 255; ++k) { P.push_back(add(P[k], P[k])); }
unsigned long seed = static_cast<unsigned long>(time(nullptr)); gmp_randclass rand(gmp_randinit_default); rand.seed(seed);
search(P, W0, DP_rarity, Nw, Nt, hop_modulo, upper_range_limit, lower_range_limit, powers_of_two);
cout << "\r[+] Average time to solve: " << chrono::duration_cast<chrono::seconds>(chrono::high_resolution_clock::now() - starttime).count() << " sec" << endl;
return 0; } g++ -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -fopenmp -lgmp -lgmpxx for MacOS clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % system_profiler SPSoftwareDataType Software: System Software Overview: System Version: macOS 13.6.1 (22G313) Kernel Version: Darwin 22.6.0 Boot Volume: macOS Boot Mode: Normal User Name: nomachine (nomachine) Secure Virtual Memory: Enabled System Integrity Protection: Enabled Time since boot: 1 day, 14 hours, 11 minutes nomachine@iMac Desktop % nano kangaroo.cpp nomachine@iMac Desktop % clang++ -std=c++11 -o kangaroo kangaroo.cpp -m64 -march=native -mtune=native -mssse3 -Wall -Wextra -ftree-vectorize -flto -O3 -funroll-loops -ffast-math -lgmp -lgmpxx nomachine@iMac Desktop % ./kangaroo - KANGAROO: Tue Jul 23 08:50:41 2024
- [Puzzle]: 50
- [Lower range limit]: 562949953421312
- [Upper range limit]: 1125899906842623
- [EC Point Coordinate X]: 110560903758971929709743161563183868968201998016819862389797221564458485814982
- [EC Point Coordinate Y]: 106403041512432555215316396882584033752066537554388330180776939978150437217531
- [Expected Hops: 2^25.50 (47453132)]
- [Hops: 2^24.82 <-> 469162 h/s] [00:01:03]
- PUZZLE SOLVED: Tue Jul 23 08:51:44 2024
- Private key (dec): 611140496167764
- Hops: 29560288
- Average time to solve: 63 sec
But it takes 6000 years to solve Puzzle 130 --> [Expected Hops: 2^65.50 (52175271301331128848)] ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) Theoretically, with 12 cores, it can achieve 5 million hops per second. The more cores you have, the better the result will be. However, it's not worth using this for a puzzle above 70bit. A GPU must be used instead....
|
|
|
|