Bitcoin puzzle transaction ~32 BTC prize to who solves it

[digaran]

Like you said, we do not know the target, only the range.
So let's say the target's key is 199,999

Alrighty then, to be exact, when it comes to slapping me suddenly the secure random generator gives us 199,999? And when we are working with 6 digits then as an example use 14, 15 etc, suddenly we go high as 2^130 and compare the numbers?
So why not scaling up all the values and use actual 2^130 range/keys? Though you forgot that I was asking if the stride idea could be tweaked to find a perfect stride or not.

Even if the key is e.g, 189776, we could still divide the end range and subtract from our target by different subranges, like 200,000 - 189776 = 10224, we could then try subtracting the result from endrange/4, er/6, er/8 etc.
Nvm that, I don't know anything about math, I'm not even working actively on 130, my target is much bigger.

Btw, Legends_Never_Die is my alter ego account, time for a paint job on trust wall.😉

[nomachine]

the secure random generator gives us 199,999

Try non-secure random generator

Code:

import random
puzzle = 18
lower_range_limit = 2 ** (puzzle - 1)
upper_range_limit = (2 ** puzzle) - 1
seed = b'\x97h6\xd9\x7f\xcbh\xc4'
random.seed(seed)
dec = random.randint(lower_range_limit, upper_range_limit)
print(f"{dec}, {seed}")

 

[WanderingPhilospher]

Like you said, we do not know the target, only the range.
So let's say the target's key is 199,999

Alrighty then, to be exact, when it comes to slapping me suddenly the secure random generator gives us 199,999? And when we are working with 6 digits then as an example use 14, 15 etc, suddenly we go high as 2^130 and compare the numbers?
So why not scaling up all the values and use actual 2^130 range/keys? Though you forgot that I was asking if the stride idea could be tweaked to find a perfect stride or not.

Even if the key is e.g, 189776, we could still divide the end range and subtract from our target by different subranges, like 200,000 - 189776 = 10224, we could then try subtracting the result from endrange/4, er/6, er/8 etc.
Nvm that, I don't know anything about math, I'm not even working actively on 130, my target is much bigger.

Btw, Legends_Never_Die is my alter ego account, time for a paint job on trust wall.😉

I know you are used to spitting out random things and some are like ooooohhhhh ahhhhhhhhh, but you seldom listen lol.

You could be working in a 50 bit range or a 256 bit range; and you can subtract, divide, multiply, etc. whatever you want to do, or you can use whatever stride you can some up with, 14, 87, 1234344564, 47398573854734834, etc., it won't work because again, you could go around the curve and you won't know where the key lies or where to start your stride function from.

There is truly only one way to take advantage of a stride function; and I stated that months ago. My problem was, I could not create a stride function inside of CUDA. Or else I would have found 130's key already lol.

[Kamoheapohea]

I know you are used to spitting out random things and some are like ooooohhhhh ahhhhhhhhh, but you seldom listen lol.

He is just having a good time. Writing everything that comes to his mind here and creating alt accounts etc for additional drama . Why not.

How many keys/s do you need for your approach to work?

[WanderingPhilospher]

I know you are used to spitting out random things and some are like ooooohhhhh ahhhhhhhhh, but you seldom listen lol.

He is just having a good time. Writing everything that comes to his mind here and creating alt accounts etc for additional drama . Why not.

How many keys/s do you need for your approach to work?

If we are talking speed, I have a program (a variation of BitCrack) that will get around 400 MKey/s (per GPU) but honestly, that is to slow. I would like to get around 1,200 MKey/s (per card, low end 30xx card) and multiple cards per instance.

[Kamoheapohea]

If we are talking speed, I have a program (a variation of BitCrack) that will get around 400 MKey/s (per GPU) but honestly, that is to slow. I would like to get around 1,200 MKey/s (per card, low end 30xx card) and multiple cards per instance.

Ok I can help you with coding if I think it works. I also modified BitCrack and solved some of the early puzzles with pubkey.

[nomachine]

My problem was, I could not create a stride function inside of CUDA. Or else I would have found 130's key already lol.

Is there a built-in "stride" function specifically in the CUDA kernel? Or maybe there is a workaround in a grid-stride loop? Or do we have to write a new kernel?

[lordfrs]

You could be working in a 50 bit range or a 256 bit range; and you can subtract, divide, multiply, etc. whatever you want to do, or you can use whatever stride you can some up with, 14, 87, 1234344564, 47398573854734834, etc., it won't work because again, you could go around the curve and you won't know where the key lies or where to start your stride function from.

There is truly only one way to take advantage of a stride function; and I stated that months ago. My problem was, I could not create a stride function inside of CUDA. Or else I would have found 130's key already lol.

If you write the exact step code you want, there will be friends who will try to help. If you draw the algorithm flow diagram they can help you

[rosengold]

You could be working in a 50 bit range or a 256 bit range; and you can subtract, divide, multiply, etc. whatever you want to do, or you can use whatever stride you can some up with, 14, 87, 1234344564, 47398573854734834, etc., it won't work because again, you could go around the curve and you won't know where the key lies or where to start your stride function from.

There is truly only one way to take advantage of a stride function; and I stated that months ago. My problem was, I could not create a stride function inside of CUDA. Or else I would have found 130's key already lol.

If you write the exact step code you want, there will be friends who will try to help. If you draw the algorithm flow diagram they can help you

I wrote my own brute-forcer that implements stride on CUDA. actually I'm running it 24/7 for #66.

glad to see that people are focusing on new algos and scripts, I feel that someone is closer to solution.

[mcdouglasx]

My problem was, I could not create a stride function inside of CUDA. Or else I would have found 130's key already lol.

Is there a built-in "stride" function specifically in the CUDA kernel? Or maybe there is a workaround in a grid-stride loop? Or do we have to write a new kernel?

If you mean by “stride” jumps of 2-2 like 2,4,6, or jumps of any other number, you simply have to modify G by the pub that corresponds to the number of jumps you want, this does not affect the speed of the scalar multiplication, BSGS, etc.

[nomachine]

If you mean by “stride” jumps of 2-2 like 2,4,6.........

Nope....
About CUDA Programming
https://www.math.wsu.edu/math/kcooper/CUDA/c09Shuffle.php
https://nanxiao.gitbooks.io/cuda-little-book/content/posts/grid-stride-loops.html


How do you imagine that he can achieve 1,200 MKey/s per card if he doesn't hack CUDA itself ?

[digaran]

Warning, random spits ahead, watch out!😉
So, as I was spitting out some random thoughts coming to my mind and having fun with myself for no apparent reason, what if we reduce the size of our curve down to for example 2^130, then we would change G to something like e.g,  0x1, 0x2 of course with a much much smaller prime (P), would that somehow help us to compute much faster if the size of our points is considerably small?
There is one small problem, how can we map secp256k1 points to a small size curve???

Stay tuned for more spits, I'm dry right now.🤣

[nomachine]

how can we map secp256k1 points to a small size curve???

You already got an answer to the same question here

https://bitcointalk.org/index.php?topic=5469636;wap

You still hope that someone will tell you precise method before they grab the prize for themselves ?  

[digaran]

how can we map secp256k1 points to a small size curve???

You already got an answer to the same question here

https://bitcointalk.org/index.php?topic=5469636;wap

You still hope that someone will tell you precise method before they grab the prize for themselves ?  

I think you got it backwards, I'm trying to level the playing field for everyone to have equal opportunity/ time.
I'm the one trying to find the precise algorithm.

Lets correct the sentences above:
We are trying to level the playing field, and
We are trying to find the precise algorithm to solve this puzzle.

As long as everybody thinks like the first version of wording above, no results will be achieved, only by team work this can have a result in much less time than going solo.

I suggest you to watch Jigsaw movies once again, the key to the *victims success was always working as a team.
In that topic, there is no mention of changing G to a smaller size G.
Let me spit explain what I'm hallucinating talking about :
Let's change p to this one :

Code:

0xcdf15ce5b341762d

Now what I'm having a problem to find, is to shrink down secp256k1's G to be the same size while acting as before, meaning if the size is changed, multiplying the new G by 10 should give me a point similar/distinguishable from secp256k1's 0xa public key. If that is even possible and how much more speed we could gain by having a smaller G?

*OMG, are we really like the victims of jigsaw puzzle? Lol.

[nomachine]

Why simplify the matter when it can be complicated. . And even more complicated... overcomplicated or
 so abstract that even the Satoshi doesn't know what we talking about.

Let's start from the the fact that all puzzles are created from 32 zeros in bytes
private_key_bytes = b'\x00' * 32
or

Code:

b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'

Puzzle 1 have 1 bytes on end that is not zero
Puzzle 10 have 2 bytes on end that is not zero
Puzzle 20 have 3 bytes on end that is not zero
Puzzle 40 have 5 bytes on end that is not zero
Puzzle 50 have 7 bytes on end that is not zero

Puzzle 66 have 9 bytes on end that is not zero

Even the random.randrange is unnecessary - you can directly spit bytes into zeros

random_bytes = os.urandom(9)
private_key_bytes = b'\x00' * 32
private_key_bytes = private_key_bytes[:-len(random_bytes)] + random_bytes
signing_key = ecdsa.SigningKey.from_string(private_key_bytes, curve=ecdsa.SECP256k1)
compressed_public_key = signing_key.get_verifying_key().to_string("compressed")

and so on....

p.s.
Testing how fast this is using only OpenSSL in C++

[dred28]

I wrote a small script that takes about 1min to solve puzzle 15, but takes forever to solve 130 I want to share it here in case someone can see what I mean to archive, or tell me where i'm going wrong.
this is supposed to reverse the bits (bits_num) used for double and add, or just double. But I'm stuck at getting an education guess of which one to pick. I tried calculating the slope but no success, have a look at 130 or try it with puzzle 15 which is very fast

UPDATE:
this script is meant to reverse double and add or just double with a known private key bit number (hence -> bits_num). With a recursion up to 2^bits_num (this this where i need help), and go all the way back until u get the "G-SPOT", generator point. If you get the g-point then you just have to compute the first digit, will be 0 or 1. At the moment it runs all possible bits until the "G-SPOT" is found then you have the pvt in binary. Rev means reverse here. so its my own implementation of reverse for double and add, sub function reveses the point addition, 'Subtract;

Code:

from bit import Key
import ecdsa
import binascii
from ecdsa.curves import SECP256k1
import threading

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

curve = ecdsa.SECP256k1.curve
results = []

def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2

    if P1 == P2:
        lam = (3 * x1 * x1) * pow(2 * y1, -1, p)
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p)

    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

def dbl(K):
    x,y = K
    P = ecdsa.ellipticcurve.Point(curve, x, y)
    k_dbl = 2 * P
    return (k_dbl.x(),k_dbl.y())

def mul(k,P):
    x,y = P
    point = ecdsa.ellipticcurve.Point(curve, x,y)
    r_p = point * k
    return (r_p.x(),r_p.y())

def revDbl(K,n):
    return mul((n+1)//2,K)

def sub(K,G,n):
    neg_G = (G[0], -G[1])
    sub_K = add(K,neg_G)

    return sub_K

def unCmp(pub):
    cmp_pub = binascii.unhexlify(pub)
    cmp_vk = ecdsa.VerifyingKey.from_string(cmp_pub, curve=ecdsa.SECP256k1)
    uncmp_pub = cmp_vk.to_string(encoding="uncompressed")
    uncmp_pub_hex = binascii.hexlify(uncmp_pub).decode('utf-8')
    uncmp_pub_hex = uncmp_pub_hex[2:]
    x = int(uncmp_pub_hex[:64],16)
    y = int(uncmp_pub_hex[64:],16)
    return (x,y)

def is_point_on_curve(point):
    x, y = point
    lhs = (y * y) % p
    rhs = (x * x * x + 7) % p
    return lhs == rhs

def runRev(K, bin_str, bits_num):
    hx = 0
    if len(bin_str) != 0:
        hx = hex(int(bin_str,2))

    print(len(bin_str), bin_str, hx, sep="\t")
    
    global results
    
    if len(results) > 0:
        return
    else:
        if len(bin_str) <= bits_num:
            # Rev DBL + ADD
            r_sub = sub(K,G,n)
            da_k = revDbl(r_sub,n)
            da_bin_str = "1" + bin_str
            if da_k == G:
                print("KEY FOUND", hx)
                results.append(da_bin_str)
                return
            elif is_point_on_curve(da_k):
                runRev(da_k, da_bin_str,bits_num)
            else:
                print("NOT ON CURVE")

            # Rev DBL
            d_k = revDbl(K,n)
            d_bin_str = "0"+bin_str
            if d_k == G:
                results.append(d_bin_str)
                return
            elif is_point_on_curve(d_k):
                runRev(d_k, d_bin_str,bits_num)
            else:
                print("NOT ON CURVE")
        else:
            return

def main():
    global results
    pub = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852"
    K = unCmp(pub)

    bits_num = 130
    bin_str = ''
    runRev(K, bin_str, bits_num)
    
    if len(results) > 0:
        print("KEY FOUND",results)

if __name__ == "__main__":
    main()

[digaran]

I wrote a small script that takes about 1min to solve puzzle 15, but takes forever to solve 130 I want to share it here in case someone can see what I mean to archive, or tell me where i'm going wrong.
this is supposed to reverse the bits (bits_num) used for double and add, or just double. But I'm stuck at getting an education guess of which one to pick. I tried calculating the slope but no success, have a look at 130 or try it with puzzle 15 which is very fast

Code:

from bit import Key
import ecdsa
import binascii
from ecdsa.curves import SECP256k1
import threading

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

curve = ecdsa.SECP256k1.curve
results = []

def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2

    if P1 == P2:
        lam = (3 * x1 * x1) * pow(2 * y1, -1, p)
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p)

    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

def dbl(K):
    x,y = K
    P = ecdsa.ellipticcurve.Point(curve, x, y)
    k_dbl = 2 * P
    return (k_dbl.x(),k_dbl.y())

def mul(k,P):
    x,y = P
    point = ecdsa.ellipticcurve.Point(curve, x,y)
    r_p = point * k
    return (r_p.x(),r_p.y())

def revDbl(K,n):
    return mul((n+1)//2,K)

def sub(K,G,n):
    neg_G = (G[0], -G[1])
    sub_K = add(K,neg_G)

    return sub_K

def unCmp(pub):
    cmp_pub = binascii.unhexlify(pub)
    cmp_vk = ecdsa.VerifyingKey.from_string(cmp_pub, curve=ecdsa.SECP256k1)
    uncmp_pub = cmp_vk.to_string(encoding="uncompressed")
    uncmp_pub_hex = binascii.hexlify(uncmp_pub).decode('utf-8')
    uncmp_pub_hex = uncmp_pub_hex[2:]
    x = int(uncmp_pub_hex[:64],16)
    y = int(uncmp_pub_hex[64:],16)
    return (x,y)

def is_point_on_curve(point):
    x, y = point
    lhs = (y * y) % p
    rhs = (x * x * x + 7) % p
    return lhs == rhs

def runRev(K, bin_str, bits_num):
    hx = 0
    if len(bin_str) != 0:
        hx = hex(int(bin_str,2))

    print(len(bin_str), bin_str, hx, sep="\t")
    
    global results
    
    if len(results) > 0:
        return
    else:
        if len(bin_str) <= bits_num:
            # Rev DBL + ADD
            r_sub = sub(K,G,n)
            da_k = revDbl(r_sub,n)
            da_bin_str = "1" + bin_str
            if da_k == G:
                print("KEY FOUND", hx)
                results.append(da_bin_str)
                return
            elif is_point_on_curve(da_k):
                runRev(da_k, da_bin_str,bits_num)
            else:
                print("NOT ON CURVE")

            # Rev DBL
            d_k = revDbl(K,n)
            d_bin_str = "0"+bin_str
            if d_k == G:
                results.append(d_bin_str)
                return
            elif is_point_on_curve(d_k):
                runRev(d_k, d_bin_str,bits_num)
            else:
                print("NOT ON CURVE")
        else:
            return

def main():
    global results
    pub = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852"
    K = unCmp(pub)

    bits_num = 130
    bin_str = ''
    runRev(K, bin_str, bits_num)
    
    if len(results) > 0:
        print("KEY FOUND",results)

if __name__ == "__main__":
    main()

Can you explain the logic? I am not familiar with bit_num and rev dbl. Solving puzzle 15 in 1 minute is extremely slow. By working with standard secp256k1 parameters you won't get anywhere, what you need to do is finding a method to convert secp256k1 points to new points with a much smaller size, then you can have 1000 times more speed.

Currently I can generate 1m keys in 20 seconds with my primitive and simple native implementation on an old android phone. So 26867 which is the decimal for #15, would take me half a second to solve.
Welcome!
Don't be shy, come on in, mi woods su woods.😉

[dred28]

I wrote a small script that takes about 1min to solve puzzle 15, but takes forever to solve 130 I want to share it here in case someone can see what I mean to archive, or tell me where i'm going wrong.
this is supposed to reverse the bits (bits_num) used for double and add, or just double. But I'm stuck at getting an education guess of which one to pick. I tried calculating the slope but no success, have a look at 130 or try it with puzzle 15 which is very fast

Code:

from bit import Key
import ecdsa
import binascii
from ecdsa.curves import SECP256k1
import threading

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

curve = ecdsa.SECP256k1.curve
results = []

def add(P1, P2):
    x1, y1 = P1
    x2, y2 = P2

    if P1 == P2:
        lam = (3 * x1 * x1) * pow(2 * y1, -1, p)
    else:
        lam = (y2 - y1) * pow(x2 - x1, -1, p)

    x3 = (lam * lam - x1 - x2) % p
    y3 = (lam * (x1 - x3) - y1) % p

    return (x3, y3)

def dbl(K):
    x,y = K
    P = ecdsa.ellipticcurve.Point(curve, x, y)
    k_dbl = 2 * P
    return (k_dbl.x(),k_dbl.y())

def mul(k,P):
    x,y = P
    point = ecdsa.ellipticcurve.Point(curve, x,y)
    r_p = point * k
    return (r_p.x(),r_p.y())

def revDbl(K,n):
    return mul((n+1)//2,K)

def sub(K,G,n):
    neg_G = (G[0], -G[1])
    sub_K = add(K,neg_G)

    return sub_K

def unCmp(pub):
    cmp_pub = binascii.unhexlify(pub)
    cmp_vk = ecdsa.VerifyingKey.from_string(cmp_pub, curve=ecdsa.SECP256k1)
    uncmp_pub = cmp_vk.to_string(encoding="uncompressed")
    uncmp_pub_hex = binascii.hexlify(uncmp_pub).decode('utf-8')
    uncmp_pub_hex = uncmp_pub_hex[2:]
    x = int(uncmp_pub_hex[:64],16)
    y = int(uncmp_pub_hex[64:],16)
    return (x,y)

def is_point_on_curve(point):
    x, y = point
    lhs = (y * y) % p
    rhs = (x * x * x + 7) % p
    return lhs == rhs

def runRev(K, bin_str, bits_num):
    hx = 0
    if len(bin_str) != 0:
        hx = hex(int(bin_str,2))

    print(len(bin_str), bin_str, hx, sep="\t")
    
    global results
    
    if len(results) > 0:
        return
    else:
        if len(bin_str) <= bits_num:
            # Rev DBL + ADD
            r_sub = sub(K,G,n)
            da_k = revDbl(r_sub,n)
            da_bin_str = "1" + bin_str
            if da_k == G:
                print("KEY FOUND", hx)
                results.append(da_bin_str)
                return
            elif is_point_on_curve(da_k):
                runRev(da_k, da_bin_str,bits_num)
            else:
                print("NOT ON CURVE")

            # Rev DBL
            d_k = revDbl(K,n)
            d_bin_str = "0"+bin_str
            if d_k == G:
                results.append(d_bin_str)
                return
            elif is_point_on_curve(d_k):
                runRev(d_k, d_bin_str,bits_num)
            else:
                print("NOT ON CURVE")
        else:
            return

def main():
    global results
    pub = "03633cbe3ec02b9401c5effa144c5b4d22f87940259634858fc7e59b1c09937852"
    K = unCmp(pub)

    bits_num = 130
    bin_str = ''
    runRev(K, bin_str, bits_num)
    
    if len(results) > 0:
        print("KEY FOUND",results)

if __name__ == "__main__":
    main()

Can you explain the logic? I am not familiar with bit_num and rev dbl. Solving puzzle 15 in 1 minute is extremely slow. By working with standard secp256k1 parameters you won't get anywhere, what you need to do is finding a method to convert secp256k1 points to new points with a much smaller size, then you can have 1000 times more speed.

Currently I can generate 1m keys in 20 seconds with my primitive and simple native implementation on an old android phone. So 26867 which is the decimal for #15, would take me half a second to solve.
Welcome!
Don't be shy, come on in, mi woods su woods.😉

I just added an update to explain my script since it has no commenting and strange variable names.

[albert0bsd]

I just added an update to explain my script since it has no commenting and strange variable names.

Hi, Welcome!! It is nice to see more developers in this posts.

You don't need to quote all the previous text just to reply a single line, just quote those parts that are interesting.

BTW as digaran said before puzzle 15 in 1 minute is very slow. But i remember when i start to code for this I also start with such low speed, so as a starting  point that is OK.

Any doubt just ask.

[dred28]

sorry about the quotes, I will be here more often to learn. I have a very slow machine with 2 cores. Even 15 is slow for me. My goal is to get a script that is fast for the slowest machine , just like how fast the derivation of double and add function for public key