== Bitcoin challenge transaction: ~1000 BTC total bounty to solvers! ==UPDATED==

[dextronomous]

hi there etar,

Here is python scrypt that devide 2^129 bit range by 2^20 with random position:

Code:

import random
import math

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )    
    """
    inv1 = 1
    inv2 = 0
    n=1
    while p != 1 and p!=0:        
        quotient = x // p        
        inv1, inv2 = inv2, inv1 - inv2 * quotient
        x, p = p, x % p        
        n = n+1
    
    return inv2

def dblpt(pt, p):
    """
    Calculate pt+pt = 2*pt
    """
    if pt is None:
        return None
    (x,y)= pt
    if y==0:
        return None 
    
    slope= 3*pow(x,2,p)*pow(2*y,p-2,p)  
    xsum= pow(slope,2,p)-2*x     
    ysum= slope*(x-xsum)-y 
    
    return (xsum%p, ysum%p)

def addpt(p1,p2, p):
    """
    Calculate p1+p2
    """
    if p1 is None or p2 is None:
        return None
    (x1,y1)= p1
    (x2,y2)= p2
    if x1==x2:
        return dblpt(p1, p)        
        
    # calculate (y1-y2)/(x1-x2)  modulus p    
    slope=(y1-y2)*pow(x1-x2,p-2,p)
    xsum= pow(slope,2,p)-(x1+x2)  
    ysum= slope*(x1-xsum)-y1 
    
    return (xsum%p, ysum%p)

def ptmul(pt,a, p):
    """
    Calculate pt*a
    """
    scale= pt    
    acc=None
    while a:        
        if a&1:
            if acc is None:
                acc= scale                 
            else:     
                acc= addpt(acc,scale, p)             
        scale= dblpt(scale, p)
        a >>= 1
        
    return acc

def ptdiv(pt,a,p,n):  
    """
    Calculate pt/a
    """   
    divpt=inverse(a, n)%n 
    
    return ptmul(pt, divpt, p)


def getuncompressedpub(compressed_key):
    """
    returns uncompressed public key
    """
    y_parity = int(compressed_key[:2]) - 2    
    x = int(compressed_key[2:], 16)
    a = (pow(x, 3, p) + 7) % p
    y = pow(a, (p+1)//4, p)    
    if y % 2 != y_parity:
        y = -y % p   
        
    return (x,y)

def compresspub(uncompressed_key):
    """
    returns compressed public key
    """
    (x,y)=uncompressed_key
    y_parity = y&1 
    head='02'
    if y_parity ==1:
        head='03'    
    compressed_key = head+'{:064x}'.format(x) 
    
    return compressed_key


#secp256k1 constants
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
g= (Gx,Gy)


rangePower=129
rb=2**rangePower
re=2**(rangePower+1)-1
print ("Bit range 2^",math.log2(re-rb))
print ("Begin > 0x%x"%rb,">DEC ",rb)
print ("End   > 0x%x"%re,">DEC ",re)

#MANUAL

compressed_key='03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852'
point=getuncompressedpub(compressed_key)
divisor = pow(2,20)
print("")

rbdiv = rb//divisor
rediv = re//divisor
print ("Div Begin > 0x%x"%rbdiv,">DEC ",rbdiv)
print ("Div End   > 0x%x"%rediv,">DEC ",rediv)
print ("Div Bit range 2^",math.log2(rediv-rbdiv))
newpub=ptdiv(point,divisor,p,n)
(partGx,partGy)=ptdiv(g,divisor,p,n)
idx=random.randrange(0,divisor-1)
#Randomly generate position in range 0..divisor-1
print("pos > 0x%x"%idx)
if idx<divisor:
    if idx==0:
        (searchpubx,searchpuby)=newpub
        (fracX, fracY)=(partGx,partGy)
    else:   
        (fracX, fracY)=ptmul((partGx,partGy),idx,p)        
        (searchpubx,searchpuby) = addpt(newpub,(fracX,p-fracY), p)
        (fracX, fracY) = addpt((fracX, fracY),(partGx,partGy), p)   
    print("searchpub > ",compresspub((searchpubx,searchpuby)))
else:
    print("idx>=divisor")

[/quote]

so if the private key found with this divisor = pow(2,20) can i adjust higher 2/30 ? how to get the private of 130
in console if the next pubkey found belonging to pubkey below. thanks man.>

Div Bit range 2^ 109.0
pos > 0xc3273
searchpub > 023

[1714622800]

1714622800

[1714622800]

1714622800

[1714622800]

1714622800

[1714622800]

1714622800

[1714622800]

1714622800

[Etar]

-snip-
so if the private key found with this divisor = pow(2,20) can i adjust higher 2/30 ? how to get the private of 130
in console if the next pubkey found belonging to pubkey below. thanks man.>

Div Bit range 2^ 109.0
pos > 0xc3273
searchpub > 023

When you find the key in the kangaroo, you need to multiply it by the divisor and add the position
For ex, your position 0xc3273, divisor = 2^20 =  0x100000
searchpub > 02c5b7be6babe3224acd1f87c02c387f9c4701e7ede2d511f93ca4733191b904bb
When kangaroo find the key you need:
PrivatKey = KangarooKey * Divisor + position
PrivatKey = KangarooKey * 0x100000 + 0xc3273

If we want to search for a key, as I described above, then we need to search for it according to certain rules. And not so that someone divides by 2 ^ 30, and someone by 2 ^ 20. As well as the division must be performed according to the rules from the script, and not according to some others.
In order to get success, we need to cover 2 ^ 20 positions, if we do not have enough resources, then we should not even start.

But I don't see a lot of people interested yet. Most likely everything will remain as it was and will try to look for the key in the entire range.

[GR Sasa]

@Etar, I'm interested. I recommend using ecctools for dividing the range. Anyways if we don't unite as you said, the miners will get the third key and we won't get anything

[Etar]

@Etar, I'm interested. I recommend using ecctools for dividing the range. Anyways if we don't unite as you said, the miners will get the third key and we won't get anything

The first problem is that we need thousands of hunters, not just you and me.
The second problem is that kangaroo is a probabilistic algorithm.
It is good when you know for sure that the public key you are looking for lies in the given range.
But in our case, only one public key will be in the range, so you need to set the -m parameter.
At the same time, it must be set to at least 2. And then this is not a guarantee that the desired key is not in the range.
For good in this case, need to search using BSGS. However, searching for a key using BSGS in the range of 109 bits is too resource-intensive, many times more resource-intensive than kangaroo.
So maybe someone can offer an alternative solution to this problem.

[bestie1549]

The real question here is why is nobody solving for the keys without the pubkeys e.g puzzle 66
We understand that the pubkeys puzzles would soon be fully solved but the focus here is solving the keys without the pubkeys because giving an example, if puzzle 64 was last solved on this day "2022-09-10" and up until now its almost one year now since the lask key without a pubkey was solved but just about 4 to 5 months since the last key with a pubkey was solved then I assume that puzzle 99 for example might take forever fot solve.
What is the best method to apply to solving for the keys without the pubkeys because puzzle 66 shoud have been solved by now.

[bestie1549]

and for the solvers of puzzle 120 and 125 we kindly plead that you publish the private keys of these puzzles respectfully. It is only fair to give us the keys for us to better understand the puzzle. Thank you. We don't need to know who you are if you solely choose to stay anonymous then that is fine. you could just create a random account and post the keys then you can go ahead to delete the account.

[digaran]

The real question here is why is nobody solving for the keys without the pubkeys e.g puzzle 66
We understand that the pubkeys puzzles would soon be fully solved but the focus here is solving the keys without the pubkeys because giving an example, if puzzle 64 was last solved on this day "2022-09-10" and up until now its almost one year now since the lask key without a pubkey was solved but just about 4 to 5 months since the last key with a pubkey was solved then I assume that puzzle 99 for example might take forever fot solve.
What is the best method to apply to solving for the keys without the pubkeys because puzzle 66 shoud have been solved by now.

Is that really the real question though? It has easy answers, with public key you can solve thousands of times faster, without public key, you either go directly to brute force all the keys in the range, or you'd go breaking 2 hash functions just to reach the public key, so it is more wise to skip all the drama and stick with the easy way.

I'd say up to puzzle 79 is solvable in a few years given the price going up to make it worth the effort, however even puzzle #159 can be cracked  with special ASICs as long as the prize is more than the cost, I suspect that we will never see more than #79 solved in our life time and this puzzle will remain a legacy among other achievements of Satoshi for the future generations!

[WanderingPhilospher]

We can use fraction-kangaroo or just a python script that will divide #130 puzzles into 2^20 pieces.
Each hunter will look at least for 1 key in the range of 109 bits.

What if we divide the pubkey by x amount. we will say divide #130 pubkey by 10; that gives us 1,024 pubkeys and reduces the range to 2^120/2^119.
I will run tames and then we just need 1,024 people (or less if multiple people run multiple pubkeys) to run wilds. I will post tame points (text files with all tame points) and then all who run wild points just need to verify if they have a match. If there is a match, we can share/split the reward. This way 2 people will share prize and people can run as many pubkeys as they want to.
We can decide on the best number to divide by, if interested.

Example tame points:

Code:

72eaff741b31e674e823570ea0000000
0ef943b6b900c758c17bd6f0c0000000
f8536da415411e4bb2c0177600000000
0bc01c4051c4b9d2b80c5d6900000000
e14aec9c4a01765c809410a5c0000000
c9bc2740735b478ee9cd841d80000000
31b580628f072553f30f5167c0000000
dac9c736237cd07117b71490a0000000
321f92692348055814d4eb5d00000000
eade44fe5ae49ffbfa972e5180000000
ad54552d665c1baaba46068d20000000
aab1759d8241aba0015fa611c0000000
e5ab9e9fd481a789f178b93a40000000
7e92ee441d924c83faee5d6800000000
2e8512535a029c1b5a841a3de0000000
8dcadd24e8f2990df80c961420000000
9d14e08ed9c558904c26892620000000
d93fda5a52d6112e7b9de460a0000000
405607ddd7a740b1f2903be2a0000000
ab6ebbdb77d55b14053f5a5900000000
17000a072245075a9ed2d66600000000
b8d81acdc5431b721dd5cb6140000000
3e825233033301486048390960000000
fc3b3117a291d34b4a865050a0000000
d315708ef56dfef75d2d640120000000
056bbb63a91be97200c435af60000000
94addc9dc093f8e54c86ab0600000000
eaa896be8970e3bdb8e0d1e2e0000000
c3f7c22c2b06460ce977a8cce0000000
45f68f5450fc5a8dfa6a7d9880000000
8b25ed6f78450eb98b86bd4420000000
6fc311534d7a988a92adf36c40000000
e223581788f08cf6f7e9e1de20000000
e0bf51daee64355694adeae480000000
a4ff4aaa40b238d16b2b3110c0000000
fc10fad238d54db43be74eb680000000
740959dd6375f90af1c10a8c40000000
3ef027cc12a6160697e2c453a0000000
df9de9947e9bc75dba0b6c22c0000000
d32d019d02b333e60d05b95140000000

And all anyone has to do is check their wild points against the above; if match, winner winner.

[GR Sasa]

I'm interested in this. I have 10 GPUs ready for your commandment!

[rosengold]

Congratulations to the solver of #125

12.5 BTC this was the greatest prize found by far on this puzzle. US $377.000 as today rates  

Please share the keys to update info about puzzle

EDIT: These guys don't need money, the same team solved puzzle #120 and the money of both remains untouched at 3Emiwzxme7Mrj4d89uqohXNncnRM15YESs

 

[WanderingPhilospher]

I'm interested in this. I have 10 GPUs ready for your commandment!

Let's see if anyone else is interested.

The easiest path would be to divide by 5 to put it back in the range of 2^124 since I have quite a few tame points already built up. That would mean only 32 pubkeys. But I'll wait to see if anyone has more/better suggestions.

[ripemdhash]

@WanderingPhilospher

Maybe this would be better.

Could you share the knowledge which onlive service for rent are best with a lot of GPU. and how to install Kangaroo on it.

It will be better if few people which has not GPUS will attach according the rules and instruction.

If someone give good instruction as step by step how to rent and how to setup the service -> a lot of people will join us.

[WanderingPhilospher]

@WanderingPhilospher

Maybe this would be better.

Could you share the knowledge which onlive service for rent are best with a lot of GPU. and how to install Kangaroo on it.

It will be better if few people which has not GPUS will attach according the rules and instruction.

If someone give good instruction as step by step how to rent and how to setup the service -> a lot of people will join us.

Vast.ai seems to be the best priced with ease of setup.
If enough people want to join they can; or maybe "donate" some $ so others can run/rent kangaroo instances on vast.
I would show how to set it up with video or instructions with pics, if there is enough interest.

[ripemdhash]

I'm intrested in it.

I will join.

[sssergy2705]

We can use fraction-kangaroo or just a python script that will divide #130 puzzles into 2^20 pieces.
Each hunter will look at least for 1 key in the range of 109 bits.

What if we divide the pubkey by x amount. we will say divide #130 pubkey by 10; that gives us 1,024 pubkeys and reduces the range to 2^120/2^119.
I will run tames and then we just need 1,024 people (or less if multiple people run multiple pubkeys) to run wilds. I will post tame points (text files with all tame points) and then all who run wild points just need to verify if they have a match. If there is a match, we can share/split the reward. This way 2 people will share prize and people can run as many pubkeys as they want to.
We can decide on the best number to divide by, if interested.

Example tame points:

Code:

72eaff741b31e674e823570ea0000000
0ef943b6b900c758c17bd6f0c0000000
f8536da415411e4bb2c0177600000000
0bc01c4051c4b9d2b80c5d6900000000
e14aec9c4a01765c809410a5c0000000
c9bc2740735b478ee9cd841d80000000
31b580628f072553f30f5167c0000000
dac9c736237cd07117b71490a0000000
321f92692348055814d4eb5d00000000
eade44fe5ae49ffbfa972e5180000000
ad54552d665c1baaba46068d20000000
aab1759d8241aba0015fa611c0000000
e5ab9e9fd481a789f178b93a40000000
7e92ee441d924c83faee5d6800000000
2e8512535a029c1b5a841a3de0000000
8dcadd24e8f2990df80c961420000000
9d14e08ed9c558904c26892620000000
d93fda5a52d6112e7b9de460a0000000
405607ddd7a740b1f2903be2a0000000
ab6ebbdb77d55b14053f5a5900000000
17000a072245075a9ed2d66600000000
b8d81acdc5431b721dd5cb6140000000
3e825233033301486048390960000000
fc3b3117a291d34b4a865050a0000000
d315708ef56dfef75d2d640120000000
056bbb63a91be97200c435af60000000
94addc9dc093f8e54c86ab0600000000
eaa896be8970e3bdb8e0d1e2e0000000
c3f7c22c2b06460ce977a8cce0000000
45f68f5450fc5a8dfa6a7d9880000000
8b25ed6f78450eb98b86bd4420000000
6fc311534d7a988a92adf36c40000000
e223581788f08cf6f7e9e1de20000000
e0bf51daee64355694adeae480000000
a4ff4aaa40b238d16b2b3110c0000000
fc10fad238d54db43be74eb680000000
740959dd6375f90af1c10a8c40000000
3ef027cc12a6160697e2c453a0000000
df9de9947e9bc75dba0b6c22c0000000
d32d019d02b333e60d05b95140000000

And all anyone has to do is check their wild points against the above; if match, winner winner.

Can you suggest how this happens. How can I view working files, how to separate wild and tame kangaroos?

[Etar]

Let's think before do something. We need to find puzzle #130 before the rivals.
Suppose they have 512 GPUs like 3090 (what they have 256 is exactly clear) in average they need ~306 days to solve #130.
If we reduce to range 2^119 bit and rent GPU we need 16 GPUs 3090 to solve 119 bit range in 306 day for every public key.
Price for 4x3090 $0.7/h or $67.2/d * 306 = $20563 Someone willing to shell out 20K for the theoretical possibility of winning?
Don`t forget that we should search 1024 public keys. So we need 1024 participants with at least 16 GPUs 3090 cards everyone.

Using tame and wild kangaroos separately is a good idea. Because we only need to generate tame kangaroos once.
Another point is that to launch only wild kangaroos, we needed tame kangaroos in an amount of at least x2-3 from the expected.
And the supply of tame kangaroos must cover the number of wild kangaroos for the worst case.
For 119bit expected op = 2^60.55 with DP size 27(~470Gb) need at least 2^33.55 Tame Dps to run only wild kangaroos.
I'm not criticizing, but just arguing whether it's worth starting at all without having the resources.
In fact, there are not many hunters here, especially those who have several dozen video cards of the RTX 3090 level.
Just reasoning.

[bestie1549]

Let's think before do something. We need to find puzzle #130 before the rivals.
Suppose they have 512 GPUs like 3090 (what they have 256 is exactly clear) in average they need ~306 days to solve #130.
If we reduce to range 2^119 bit and rent GPU we need 16 GPUs 3090 to solve 119 bit range in 306 day for every public key.
Price for 4x3090 $0.7/h or $67.2/d * 306 = $20563 Someone willing to shell out 20K for the theoretical possibility of winning?
Don`t forget that we should search 1024 public keys. So we need 1024 participants with at least 16 GPUs 3090 cards everyone.

Using tame and wild kangaroos separately is a good idea. Because we only need to generate tame kangaroos once.
Another point is that to launch only wild kangaroos, we needed tame kangaroos in an amount of at least x2-3 from the expected.
And the supply of tame kangaroos must cover the number of wild kangaroos for the worst case.
For 119bit expected op = 2^60.55 with DP size 27(~470Gb) need at least 2^33.55 Tame Dps to run only wild kangaroos.
I'm not criticizing, but just arguing whether it's worth starting at all without having the resources.
In fact, there are not many hunters here, especially those who have several dozen video cards of the RTX 3090 level.
Just reasoning.

well what if there are some of us willing to take that chance and all we have to do is join forces together. where do we start from and how do we start and most importantly how do we join forces so we don't make mistakes and communication cannot be only on this platform in case we need to share some funds.

I will volunteer 190 GPUs minimum of A40 and I have a few numbers of 3090 too about 50 pcs of 3090 and 50 pcs of 4090 there are 45 A40s and 45 A5000s. I need the next instructions on what to do

[WanderingPhilospher]

Let's think before do something. We need to find puzzle #130 before the rivals.
Suppose they have 512 GPUs like 3090 (what they have 256 is exactly clear) in average they need ~306 days to solve #130.
If we reduce to range 2^119 bit and rent GPU we need 16 GPUs 3090 to solve 119 bit range in 306 day for every public key.
Price for 4x3090 $0.7/h or $67.2/d * 306 = $20563 Someone willing to shell out 20K for the theoretical possibility of winning?
Don`t forget that we should search 1024 public keys. So we need 1024 participants with at least 16 GPUs 3090 cards everyone.

Using tame and wild kangaroos separately is a good idea. Because we only need to generate tame kangaroos once.
Another point is that to launch only wild kangaroos, we needed tame kangaroos in an amount of at least x2-3 from the expected.
And the supply of tame kangaroos must cover the number of wild kangaroos for the worst case.
For 119bit expected op = 2^60.55 with DP size 27(~470Gb) need at least 2^33.55 Tame Dps to run only wild kangaroos.
I'm not criticizing, but just arguing whether it's worth starting at all without having the resources.
In fact, there are not many hunters here, especially those who have several dozen video cards of the RTX 3090 level.
Just reasoning.

I agree. Needs reasoning. Many people say they will do x y and z but then quickly fall off. I may just run tames in the 2^129 and if people want to run wilds, they can, and compare to my tames list. Or chop it down to 124 bit range (since I have many tame DPs already) and then people can run 1-32 pubs and try to find a match.

Or maybe breaking it up into 32, 128, 256, etc ranges would be better?! I’m on the fence.

[WanderingPhilospher]

  I will volunteer 190 GPUs minimum of A40 and I have a few numbers of 3090 too about 50 pcs of 3090 and 50 pcs of 4090 there are 45 A40s and 45 A5000s. I need the next instructions on what to do

If you have that many and can run them for the long haul, then we may need to just run #130 in its original range. I could run tames and you and others run wilds.

Agree about posting elsewhere (not just this place) I have discord and telegram set up.

If we/others can agree on a plan, I’ll put things into motion.

[bestie1549]

  I will volunteer 190 GPUs minimum of A40 and I have a few numbers of 3090 too about 50 pcs of 3090 and 50 pcs of 4090 there are 45 A40s and 45 A5000s. I need the next instructions on what to do

If you have that many and can run them for the long haul, then we may need to just run #130 in its original range. I could run tames and you and others run wilds.

Agree about posting elsewhere (not just this place) I have discord and telegram set up.

If we/others can agree on a plan, I’ll put things into motion.

Agreed. Let's create the force. Let's join forces. No going back