REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and other

[ranochigo]

Here you go.

https://block.d.evco.in/tx/e61339a40aa4e90e983fe0d64cf09eed5fa1e6eac227b6761f06ac7af1929baf

Not sure how to redeem myself. But there's the same pubkey as BTC Block 0.

The block of that coin merely sends the block rewards to the same address as Bitcoin's genesis block. It doesn't matter if they have the key pair or not and it is not a collision either.

It's based on Bitcoin and thus the addresses are the same.

[1715590433]

1715590433

[1715590433]

1715590433

[1715590433]

1715590433

[1715590433]

1715590433

[1715590433]

1715590433

[1715590433]

1715590433

[BlackHatCoiner]

Isn't this whole thing pointless?

If you find a hash collision, and spend the bitcoin, it is potentially everyone's bitcoin for a while, because you've revealed the pre-image. In fact, nobody but the mining pool owners can actually claim the reward. Even they have a pressure on who's going to mine it first. In fact, with the computational power one pool might have, it is trivial to reorg the chain by 1 block, just to steal that reward from another mining pool.

[garlonicon]

Isn't this whole thing pointless?

No, because the point is to reward someone for finding a collision. In centralized solutions, you can claim that you solved for example some mathematical problem, but then it has to be verified by mathematicians, and they can give you some reward or not, they can always disagree, even if you are technically right. Here, it is pretty clear: if you unlock the script, then you can claim the reward, no matter what, and no centralized entity can decide that "you shouldn't get it, because I don't like you, or because I don't like your solution, even if it is correct, because I had something else in mind, didn't expect that, whatever". See: Vertical Castling in Chess.

If you find a hash collision, and spend the bitcoin, it is potentially everyone's bitcoin for a while, because you've revealed the pre-image.

For the old address types, it is definitely not "everyone's bitcoin for a while", just because of standardness rules. But for P2WSH and P2TR, yes, it is.

In fact, nobody but the mining pool owners can actually claim the reward.

Still, the reward will always be paid if the solution will be revealed. But yes, it can be improved by wrapping that over some other kind of proofs. For example, elliptic curves provide enough functionalities to handle 256-bit numbers directly, so something with OP_CHECKSIG could be done here, not to require the solution to be some valid key, but instead to force doing computations on public keys, without revealing private keys. And the same for the famous puzzle: it can be improved by creating some kind of range proof, to prove that the private key has for example only 64 bits, without revealing it.

Even they have a pressure on who's going to mine it first.

You can say the same about every mined block. We currently have 6.25 BTC plus fees, and the pressure is the same for that reward. If you have 6.50 BTC in the first block and 6.30 BTC for the second block, then you can still pick transactions with the highest fees, and for example get 6.51 BTC in reorged block (it depends on details like transaction sizes).

In fact, with the computational power one pool might have, it is trivial to reorg the chain by 1 block, just to steal that reward from another mining pool.

You can say the same when the basic block reward will drop to zero. Miners will then decide if they want to honestly build the chain on top of the latest block, or maybe reorg it, and get the highest fees from both blocks. And that situation is not really that different than a situation where someone sends 50 BTC in fees, then that spike belongs to the miners, and then miners are also incentivized to reorg the chain, and to fight for that reward. And that's why "coinbase coverage" is important: if the coinbase reward is 7 BTC, then if you want to send 700 BTC, you need 700/7=100 blocks to be absolutely sure that dishonest miners will definitely give up (the probability is worse, but I think most people will stick with simple maths, instead of using formulas from the whitepaper to calculate Poisson distribution correctly).

[BlackHatCoiner]

No, because the point is to reward someone for finding a collision.

The point is to reward the person who found the collision. Not just someone, because someone else found a collision.

For the old address types, it is definitely not "everyone's bitcoin for a while", just because of standardness rules.

What do you mean? Isn't it standard to replace-by-fee a transaction that spends that puzzle-output? Or just double-spend it in another manner, before it gets confirmed.

For example, elliptic curves provide enough functionalities to handle 256-bit numbers directly, so something with OP_CHECKSIG could be done here, not to require the solution to be some valid key, but instead to force doing computations on public keys, without revealing private keys.

There's no private key here neither. Just a pre-image and its hash. A fairer way to setup such puzzle is to find two values that lead to the same hash, one of which is a public key that is provably owned by the solver.

Here's the locking script that does it:

Code:

OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_2DUP OP_SHA256 OP_SWAP OP_SHA256 OP_EQUALVERIFY OP_DROP OP_CHECKSIG

With input (unlocking script):

Code:

<sig> <pubKey> <x>

Once executed, it'll look like this, assuming signature is valid and SHA256(pubKey) = SHA256(x):

Code:

<sig> <pubKey> <x>
OP_2DUP: <sig> <pubKey> <x> <pubKey> <x>
OP_EQUAL: <sig> <pubKey> <x> 0
OP_NOT: <sig> <pubKey> <x> 1
OP_VERIFY: <sig> <pubKey> <x>
OP_2DUP: <sig> <pubKey> <x> <pubKey> <x>
OP_SHA256: <sig> <pubKey> <x> <pubKey> <SHA256(x)>
OP_SWAP: <sig> <pubKey> <x> <SHA256(x)> <pubKey>
OP_SHA256: <sig> <pubKey> <x> <SHA256(x)> <SHA256(pubKey)>
OP_EQUALVERIFY: <sig> <pubKey> <x>
OP_DROP: <sig> <pubKey>
OP_CHECKSIG: 1

That way, the solver can spend the output, knowing that there's nobody who can double-spend it. The only disadvantage is that it limits you try with a public key and not with any two possible messages.

[garlonicon]

The point is to reward the person who found the collision. Not just someone, because someone else found a collision.

There are some things to distinguish here:
1) If we want to reward the winner, and not reveal the solution, then the proof should be wrapped, for example by operating on public keys, to reach some equation, which will correspond to the situation, where the same algorithm will be performed directly on the private keys.
2) If we want to reward the winner, and also reveal the solution, then it should be two-step: first, the reward should be allocated to the winner, and then that reward should be claimed after getting enough confirmations, and that claim should require revealing the solution.
3) It is hard to make sure who really found the solution. Even in that case of SHA-1, I don't think that reward was taken by the authors of the research. Changing that requires wrapping the solution, and that requires some tricks like homomorphic encryption or zero knowledge proofs.

What do you mean?

If you have P2WSH or P2TR, then you can spend some custom script. If you have P2SH, then standardness rules apply. Your script under P2SH has to be standard if used as a raw script. If it is not, then by default your transaction will be rejected as non-standard. So it is not "everyone's bitcoin for a while", but only "all miners' bitcoin for a while".

The only disadvantage is that it limits you try with a public key and not with any two possible messages.

This significantly slows down the whole process. I guess even if SHA-1 collisions are publicly known, it is much harder to do the same for public keys, and I guess today there are still no such collisions known. For now, even 64-bit public key is still available, so it is very hard limitation. You can also look at some collisions and their sizes to see that the structure of the messages is very specific, even limiting it by requiring any 512-bit value would be a very hard limitation, because it would limit the attack to a single block of SHA-1.

[NotATether]

The addresses are not at risk of being swiped by internet surfers as long as the researcher claims the rewards from the script before disclosing the collision - since the act of spending from one of these addresses also happens to be a practical collision demonstration as well.

So I don't see the big fuss about any of this.

[digaran]

Hi inactive devs, 🤨 are you an MCU fan? Then you should know the term "what if?". I don't care if my suggestion is stupid or not because I can't tell if it is, that's why I'm posting it here.

Regarding collisions, "what if" we could create our own fake EC, base58, hash160, using imaginary and rigged numbers and then generate our own collisions, like a billion private key matching an address. We could then apply the rules and standards of the real EC to our fake EC to see how our rigged collisions spread out through the curve, we wouldn't be able to map them directly to the real private keys of our real EC, but we could see how our fake numbers react and behave when introduced to the curve.

That should give us some starting points on how to look for collisions in our real EC, right?

Stay tuned for more earth shattering discoveries.🤭
Thank you for reading my half baked proposal.

[garlonicon]

That should give us some starting points on how to look for collisions in our real EC, right?

No, because those things are more complex than that, and your changes would not propagate in the way you want. For example, you can take the first 32 bits of SHA-256, and try to find preimages with all zeroes. In practice, every Bitcoin header is a matching preimage for such "fake hash function". But it won't push you any further, you will get a random matching value (called nonce), that will be useless in the real hash function, because it will be still only partial preimage, and won't give you any hints for full preimage.

It is like trying to break RSA by using low numbers, and thinking that if you can factorize a small number like 323 into two primes, 17 and 19, then you can do the same on bigger numbers. You cannot, because you need a better algorithm, and your simplified solution will not give you any hints.

Even worse, some inefficient algorithms will give you some answers in a reasonable time, so you won't improve them if you stay on lower numbers. For example, if you will use some fake EC y^2=x^3+7, with p=67 and n=79, then to find an inverse of a number, you don't even need to use Extended Euclidean algorithm, because for such low numbers, bruteforcing every combination will work. So, you won't encounter some problems on smaller numbers, that you will encounter on bigger ones.

Another example is trying to use less bits in a hash function. If you have SHA-1, you have IV equal to "0x67452301,0xefcdab89,0x98badcfe,0x10325476,0xc3d2e1f0", and you have k-values equal to "0x5a827999,0x6ed9eba1,0x8f1bbcdc,0xca62c1d6". There are three types of left rotations, equal to "1,5,30". You can switch from 32-bit values into 8-bit values, and produce 40-bit hashes, instead of 160-bit hashes. You can use IV equal to "0x67,0xef,0x98,0x10,0xc3", k-values equal to "0x5a,0x6e,0x8f,0xca", and left rotations, equal to "1,5,6". Then, you can produce a message, where w-values will be also 8-bit. After that, you can find some 128-bit chunk with many leading zeroes:

Code:

00 2e 35 3c
f9 80 00 00
00 00 00 00
00 00 00 28

It has "0000000093" hash, so it has eight leading nibbles, that means at least 32 leading zero bits. So far so good, but then, the question is, how to use that in real SHA-1, and produce an equivalent, so a hash with 128 leading zero bits? As I said, you will have only a random message, it won't help you in that case. And even if you check 2^40 combinations to find a full 40-bit preimage in this fake hash, it won't help you to get closer to the real 160-bit preimage, because even if many SHA-1 properties are preserved, the avalanche effect will make a complete mess, and a single different computation in the middle, will alter the whole result.

[digaran]

Can someone please explain what happens if there is a collision? How can someone exploit it? How can we stop the exploit? Is it safe to publish such collisions like what the OP is asking?  Btw, why bitcoin's SHA256 is different, is it because it hashes bytes?
Since this is technical I don't know where else to ask.

[pooya87]

Can someone please explain what happens if there is a collision? How can someone exploit it?

I can only think of weird ways of abusing the scripts but they all involve you stealing your own coins which make no sense. That is because in a collision you have to create two different messages that produce the same hash, the hash that would be used in a pay to script script meaning you are creating the output script yourself.

How can we stop the exploit?

By changing the hash algorithms that are used, for example by switching to version 3 of SHA.

Is it safe to publish such collisions like what the OP is asking?

If you publish the collision, anybody would be able to spend the reward of these puzzles. That's about it.

Btw, why bitcoin's SHA256 is different, is it because it hashes bytes?

The only difference is the size and the algorithm, otherwise all hash functions deal with bytes although the algorithm is defined to work with octet strings, they are all implement to deal with full octets (ie. the algorithm is defined to let you compute the hash of a 1 bit input but implementations don't let you and it has to be padded to 8 bits).

[digaran]

Btw, why bitcoin's SHA256 is different, is it because it hashes bytes?

The only difference is the size and the algorithm, otherwise all hash functions deal with bytes although the algorithm is defined to work with octet strings, they are all implement to deal with full octets (ie. the algorithm is defined to let you compute the hash of a 1 bit input but implementations don't let you and it has to be padded to 8 bits).

Is there any tool that I could use offline to experiment on BTC's SHA-256 and both 160 hash functions on windows? (Lol). I tried different online services and all of their output differed from bitcoin's. That's why I asked.
@long inactive OP, at the time of creating the reward transactions, you spent around 0.5BTC as a reward for something that challenging and at the time price of 0.5 bitcoin was less than 100$, was this a mockery of some sort or you guys were serious?

[garlonicon]

I can only think of weird ways of abusing the scripts but they all involve you stealing your own coins which make no sense.

It is also about spending funds from multisig addresses. And in case of LN or other networks, where public keys are known, it is possible to prepare the right script upfront, because you usually know the public key upfront.

If you publish the collision, anybody would be able to spend the reward of these puzzles.

Not anyone, but only miners, because those scripts are non-standard. It would work for anyone if those puzzles would use P2WSH or P2TR instead of P2SH.

the algorithm is defined to let you compute the hash of a 1 bit input but implementations don't let you and it has to be padded to 8 bits

It depends which implementations: https://sha256algorithm.com/

Code:

SHA-256("")=e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA-256(singleZeroBit)=bd4f9e98beb68c6ead3243b1b4c7fed75fa4feaab1f84795cbd8a98676a2a375
SHA-256(singleOneBit)=b9debf7d52f36e6468a54817c1fa071166c3a63d384850e1575b42f702dc5aa1

[vjudeu]

Is there any tool that I could use offline to experiment on BTC's SHA-256 and both 160 hash functions on windows?

The easiest way is to write that tool in any programming language. Because some tools that are available, can give you the final hash, but won't let you see internal state of hash functions. And writing that is not hard: optimizing and making it fast enough for mining is hard, but if you are interested only in mathematical aspects of hash functions, then you can execute it round-by-round, and you don't need any optimizations, at least not at the beginning. Also, brute-forcing is not the way to go, so you are going to write some code anyway, if you want to get any of those coins.

Usually to understand hash functions, you don't need to go beyond a single block. That means, for SHA-256, you don't need longer messages than 512 bits if you want to try some simple attacks. The same for SHA-1, and for many other Merkle–Damgård hash functions. Also, if you will have some short implementation of SHA-1, then you can easily change how it works, and see how those changes can propagate.

Some example of C++ implementation for SHA-1, with displaying internal status, round-by-round:

Code:

#include <cstdint>
#include <iostream>
#include <sstream>
#include <string>

std::string toString32(std::uint32_t value)
{
    std::ostringstream out;
    out.width(8);
    out.fill('0');
    out<<std::hex<<value;
    return out.str();
}

std::uint32_t rotateLeft(std::uint32_t value,std::size_t n)
{
    return (value<<(n%32))|(value>>(32-(n%32)));
}

std::uint32_t f1(std::uint32_t b,std::uint32_t c,std::uint32_t d)
{
    return (b&c)|((~b)&d);
}

std::uint32_t f2(std::uint32_t b,std::uint32_t c,std::uint32_t d)
{
    return b^c^d;
}

std::uint32_t f3(std::uint32_t b,std::uint32_t c,std::uint32_t d)
{
    return (b&c)|(b&d)|(c&d);
}

void printRound(std::size_t i,std::uint32_t a,std::uint32_t b,std::uint32_t c,std::uint32_t d,std::uint32_t e,
                std::uint32_t f,std::uint32_t k,std::uint32_t w)
{
    std::cout<<i<<'\t'<<toString32(a)<<' '<<toString32(b)<<' '<<toString32(c)<<' '<<toString32(d)<<' '<<toString32(e);
    if(i<80)
    {
        std::cout<<" | "<<toString32(f)<<' '<<toString32(k)<<' '<<toString32(w);
    }
    std::cout<<'\n';
}

#define PRINT_ROUND(i) printRound((i),a[i],b[i],c[i],d[i],e[i],f[i],k[i],w[i])

int main()
{
    std::uint32_t a[82],b[82],c[82],d[82],e[82];
    a[0]=0x67452301;
    b[0]=0xefcdab89;
    c[0]=0x98badcfe;
    d[0]=0x10325476;
    e[0]=0xc3d2e1f0;
    std::uint32_t w[82]=
    {
        0x80000000,0x00000000,0x00000000,0x00000000,
        0x00000000,0x00000000,0x00000000,0x00000000,
        0x00000000,0x00000000,0x00000000,0x00000000,
        0x00000000,0x00000000,0x00000000,0x00000000
    };
    for(std::size_t i=16;i<80;++i)
    {
        w[i]=rotateLeft(w[i-3]^w[i-8]^w[i-14]^w[i-16],1);
    }
    std::uint32_t f[82],k[82];
    std::cout<<"i       a[i]     b[i]     c[i]     d[i]     e[i]       f[i]     k[i]     w[i]    \n";
    std::cout<<"---------------------------------------------------------------------------------\n";
    for(std::size_t i=0;i<20;++i)
    {
        f[i]=f1(b[i],c[i],d[i]);
        k[i]=0x5a827999;
        PRINT_ROUND(i);
        a[i+1]=rotateLeft(a[i],5)+f[i]+e[i]+k[i]+w[i];
        b[i+1]=a[i];
        c[i+1]=rotateLeft(b[i],30);
        d[i+1]=c[i];
        e[i+1]=d[i];
    }
    for(std::size_t i=20;i<40;++i)
    {
        f[i]=f2(b[i],c[i],d[i]);
        k[i]=0x6ed9eba1;
        PRINT_ROUND(i);
        a[i+1]=rotateLeft(a[i],5)+f[i]+e[i]+k[i]+w[i];
        b[i+1]=a[i];
        c[i+1]=rotateLeft(b[i],30);
        d[i+1]=c[i];
        e[i+1]=d[i];
    }
    for(std::size_t i=40;i<60;++i)
    {
        f[i]=f3(b[i],c[i],d[i]);
        k[i]=0x8f1bbcdc;
        PRINT_ROUND(i);
        a[i+1]=rotateLeft(a[i],5)+f[i]+e[i]+k[i]+w[i];
        b[i+1]=a[i];
        c[i+1]=rotateLeft(b[i],30);
        d[i+1]=c[i];
        e[i+1]=d[i];
    }
    for(std::size_t i=60;i<80;++i)
    {
        f[i]=f2(b[i],c[i],d[i]);
        k[i]=0xca62c1d6;
        PRINT_ROUND(i);
        a[i+1]=rotateLeft(a[i],5)+f[i]+e[i]+k[i]+w[i];
        b[i+1]=a[i];
        c[i+1]=rotateLeft(b[i],30);
        d[i+1]=c[i];
        e[i+1]=d[i];
    }
    PRINT_ROUND(80);
    a[81]=a[80]+a[0];
    b[81]=b[80]+b[0];
    c[81]=c[80]+c[0];
    d[81]=d[80]+d[0];
    e[81]=e[80]+e[0];
    PRINT_ROUND(81);
}

And then, you can see exactly, step-by-step, how SHA-1 of the empty message is changed into its hash:

Code:

i       a[i]     b[i]     c[i]     d[i]     e[i]       f[i]     k[i]     w[i]    
---------------------------------------------------------------------------------
0	67452301 efcdab89 98badcfe 10325476 c3d2e1f0 | 98badcfe 5a827999 80000000
1	1fb498b3 67452301 7bf36ae2 98badcfe 10325476 | fbfbfefe 5a827999 00000000
2	5d43e370 1fb498b3 59d148c0 7bf36ae2 98badcfe | 79d36ac0 5a827999 00000000
3	158d2f62 5d43e370 c7ed262c 59d148c0 7bf36ae2 | 45d12aa0 5a827999 00000000
4	cdecfb5d 158d2f62 1750f8dc c7ed262c 59d148c0 | d760284c 5a827999 00000000
5	4953565e cdecfb5d 85634bd8 1750f8dc c7ed262c | 97704bd8 5a827999 00000000
6	e44ab766 4953565e 737b3ed7 85634bd8 1750f8dc | c5731fd6 5a827999 00000000
7	c09d7f27 e44ab766 9254d597 737b3ed7 85634bd8 | 93719d97 5a827999 00000000
8	87074800 c09d7f27 b912add9 9254d597 737b3ed7 | 9250ad91 5a827999 00000000
9	41376611 87074800 f0275fc9 b912add9 9254d597 | b817edd9 5a827999 00000000
10	cbdbff31 41376611 21c1d200 f0275fc9 b912add9 | b1015bc8 5a827999 00000000
11	40166973 cbdbff31 504dd984 21c1d200 f0275fc9 | 6049d900 5a827999 00000000
12	adc0e0ca 40166973 72f6ffcc 504dd984 21c1d200 | 505ff9c4 5a827999 00000000
13	84c05eb2 adc0e0ca d0059a5c 72f6ffcc 504dd984 | d2369f4c 5a827999 00000000
14	1512c8b9 84c05eb2 ab703832 d0059a5c 72f6ffcc | d045987e 5a827999 00000000
15	40182905 1512c8b9 a13017ac ab703832 d0059a5c | ab7030aa 5a827999 00000000
16	d8fd6547 40182905 4544b22e a13017ac ab703832 | e12036ac 5a827999 00000001
17	06bf9173 d8fd6547 50060a41 4544b22e a13017ac | 55049269 5a827999 00000000
18	28a9520e 06bf9173 f63f5951 50060a41 4544b22e | 563f1b51 5a827999 00000000
19	0b3088dd 28a9520e c1afe45c f63f5951 50060a41 | d6bf495d 5a827999 00000002
20	e758e8da 0b3088dd 8a2a5483 c1afe45c f63f5951 | 40b53802 6ed9eba1 00000000
21	90eb9850 e758e8da 42cc2237 8a2a5483 c1afe45c | 2fbe9e6e 6ed9eba1 00000000
22	7dbb787d 90eb9850 b9d63a36 42cc2237 8a2a5483 | 6bf18051 6ed9eba1 00000004
23	1c64d028 7dbb787d 243ae614 b9d63a36 42cc2237 | e057a45f 6ed9eba1 00000000
24	1e97b73a 1c64d028 5f6ede1f 243ae614 b9d63a36 | 6730e823 6ed9eba1 00000002
25	62d7f53f 1e97b73a 0719340a 5f6ede1f 243ae614 | 46e05d2f 6ed9eba1 00000008
26	34f3d6d8 62d7f53f 87a5edce 0719340a 5f6ede1f | e26b2cfb 6ed9eba1 00000000
27	4f2ed1c1 34f3d6d8 d8b5fd4f 87a5edce 0719340a | 6be3c659 6ed9eba1 00000000
28	c7b11e2d 4f2ed1c1 0d3cf5b6 d8b5fd4f 87a5edce | 9aa7d938 6ed9eba1 00000010
29	874b786f c7b11e2d 53cbb470 0d3cf5b6 d8b5fd4f | 99465feb 6ed9eba1 00000000
30	ca4556cb 874b786f 71ec478b 53cbb470 0d3cf5b6 | a56c8b94 6ed9eba1 0000000a
31	6a2e466e ca4556cb e1d2de1b 71ec478b 53cbb470 | 5a7bcf5b 6ed9eba1 00000020
32	62ea3d59 6a2e466e f29155b2 e1d2de1b 71ec478b | 796dcdc7 6ed9eba1 00000006
33	b77bac25 62ea3d59 9a8b919b f29155b2 e1d2de1b | 0af0f970 6ed9eba1 00000000
34	4b1347e2 b77bac25 58ba8f56 9a8b919b f29155b2 | 754ab2e8 6ed9eba1 00000040
35	391ef0c4 4b1347e2 6ddeeb09 58ba8f56 9a8b919b | 7e7723bd 6ed9eba1 00000008
36	abbab988 391ef0c4 92c4d1f8 6ddeeb09 58ba8f56 | c604ca35 6ed9eba1 00000028
37	04f07669 abbab988 0e47bc31 92c4d1f8 6ddeeb09 | 3739d441 6ed9eba1 00000080
38	b201788b 04f07669 2aeeae62 0e47bc31 92c4d1f8 | 2059643a 6ed9eba1 00000008
39	62273351 b201788b 413c1d9a 2aeeae62 0e47bc31 | d9d3cb73 6ed9eba1 00000000
40	9bdbdd71 62273351 ec805e22 413c1d9a 2aeeae62 | 60241f12 8f1bbcdc 00000108
41	95aa398b 9bdbdd71 5889ccd4 ec805e22 413c1d9a | d889dc70 8f1bbcdc 00000000
42	5e28e858 95aa398b 66f6f75c 5889ccd4 ec805e22 | 54aafddc 8f1bbcdc 000000a0
43	95642485 5e28e858 e56a8e62 66f6f75c 5889ccd4 | 666aee58 8f1bbcdc 00000200
44	fa950aba 95642485 178a3a16 e56a8e62 66f6f75c | 956a2e06 8f1bbcdc 00000064
45	de1e3a01 fa950aba 65590921 178a3a16 e56a8e62 | 77990a32 8f1bbcdc 00000000
46	afe695ab de1e3a01 bea542ae 65590921 178a3a16 | fe1d0a21 8f1bbcdc 00000408
47	a195ba90 afe695ab 77878e80 bea542ae 65590921 | bfa786aa 8f1bbcdc 00000088
48	e6d39f43 a195ba90 ebf9a56a 77878e80 bea542ae | e395ae80 8f1bbcdc 0000029c
49	0bca9922 e6d39f43 28656ea4 ebf9a56a 77878e80 | eaf1af62 8f1bbcdc 00000800
50	6ae826ff 0bca9922 f9b4e7d0 28656ea4 ebf9a56a | 29e4efa0 8f1bbcdc 00000080
51	01ff3253 6ae826ff 82f2a648 f9b4e7d0 28656ea4 | eaf0a6d8 8f1bbcdc 00000028
52	e2581ce0 01ff3253 daba09bf 82f2a648 f9b4e7d0 | 82fa225b 8f1bbcdc 00001088
53	56ce73ab e2581ce0 c07fcc94 daba09bf 82f2a648 | c27a0cb4 8f1bbcdc 00000000
54	ae56e542 56ce73ab 38960738 c07fcc94 daba09bf | 50de47b8 8f1bbcdc 00000a40
55	8590c0e8 ae56e542 d5b39cea 38960738 c07fcc94 | bc96856a 8f1bbcdc 00002000
56	be4a4bea 8590c0e8 ab95b950 d5b39cea 38960738 | 859198e8 8f1bbcdc 00000668
57	168ce0bb be4a4bea 2164303a ab95b950 d5b39cea | ab44397a 8f1bbcdc 00000080
58	e1afab22 168ce0bb af9292fa 2164303a ab95b950 | 2784b0ba 8f1bbcdc 00004088
59	982bcbca e1afab22 c5a3382e af9292fa 2164303a | e5a3ba2a 8f1bbcdc 00000880
60	9b9d2913 982bcbca b86beac8 c5a3382e af9292fa | e5e3192c ca62c1d6 000028c8
61	d37db937 9b9d2913 a60af2f2 b86beac8 c5a3382e | 85fc3129 ca62c1d6 00008000
62	85b9d227 d37db937 e6e74a44 a60af2f2 b86beac8 | 93900181 ca62c1d6 000008a8
63	cd98fbb7 85b9d227 f4df6e4d e6e74a44 a60af2f2 | 9781f62e ca62c1d6 00000080
64	bb0f226f cd98fbb7 e16e7489 f4df6e4d e6e74a44 | d829e173 ca62c1d6 000108e8
65	eb59446c bb0f226f f3663eed e16e7489 f4df6e4d | a907680b ca62c1d6 00000000
66	d37225cb eb59446c eec3c89b f3663eed e16e7489 | f6fcb21a ca62c1d6 0000a000
67	111341f3 d37225cb 3ad6511b eec3c89b f3663eed | 0767bc4b ca62c1d6 00020080
68	e79afbf0 111341f3 f4dc8972 3ad6511b eec3c89b | df19999a ca62c1d6 00006400
69	8ba00627 e79afbf0 c444d07c f4dc8972 3ad6511b | d702a2fe ca62c1d6 00000000
70	503c7ae0 8ba00627 39e6befc c444d07c f4dc8972 | 760268a7 ca62c1d6 00040800
71	3cd517f9 503c7ae0 e2e80189 39e6befc c444d07c | 8b32c595 ca62c1d6 00008800
72	b47ddf0e 3cd517f9 140f1eb8 e2e80189 39e6befc | ca3208c8 ca62c1d6 00029c10
73	5e3a0780 b47ddf0e 4f3545fe 140f1eb8 e2e80189 | ef478448 ca62c1d6 00080000
74	63db37b2 5e3a0780 ad1f77c3 4f3545fe 140f1eb8 | bc1035bd ca62c1d6 00008080
75	15e98d17 63db37b2 178e81e0 ad1f77c3 4f3545fe | d94ac191 ca62c1d6 00002820
76	b0149467 15e98d17 98f6cdec 178e81e0 ad1f77c3 | 9a91c11b ca62c1d6 001088c0
77	14b7106a b0149467 c57a6345 98f6cdec 178e81e0 | ed983ace ca62c1d6 00000000
78	666b8bc6 14b7106a ec052519 c57a6345 98f6cdec | 3dc85636 ca62c1d6 000a40c0
79	6e9d9f84 666b8bc6 852dc41a ec052519 c57a6345 | 0f436ac5 ca62c1d6 00200080
80	72f480ed 6e9d9f84 999ae2f1 852dc41a ec052519
81	da39a3ee 5e6b4b0d 3255bfef 95601890 afd80709

Then, you can compare it with other tools, and check that SHA-1("")=da39a3ee5e6b4b0d3255bfef95601890afd80709, that means all computations are correct.

Edit:

I tried different online services and all of their output differed from bitcoin's. That's why I asked.

I guess you used text mode, while Bitcoin uses binary mode. For example, if you have "12345678" as some message to be hashed, then your message probably was in this form:

Code:

31323334 35363738 80000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000040

But what you should use, was that form:

Code:

12345678 80000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000020

And then, you can compare those hashes:

Code:

SHA-1("12345678")=7c222fb2927d828af22f592134e8932480637c0d
SHA-1(0x12345678)=9bce73d0c8b9eca4f24154f3bd3b8aa473b1c3a9

Another thing is endianness. For example, maybe you used 0x78563412, while you should use 0x12345678.

To move things forward, I can give you the Genesis Block hash as an example of how things should be computed:

Code:

SHA-256(0100000000000000000000000000000000000000000000000000000000000000000000003ba3edfd7a7b12b27ac72c3e67768f617fc81bc3888a51323a9fb8aa4b1e5e4a29ab5f49ffff001d1dac2b7c)=af42031e805ff493a07341e2f74ff58149d22ab9ba19f61343e2c86c71c5d66d
SHA-256(af42031e805ff493a07341e2f74ff58149d22ab9ba19f61343e2c86c71c5d66d)=6fe28c0ab6f1b372c1a6a246ae63f74f931e8365e15a089c68d6190000000000

And then, you can notice that the result of SHA-256 is reversed. The reason is that little-endian is used in many places, for example in hashes. And that's why you have to change endianness many times, and process hashes byte-by-byte, and put them in reversed order. The same is true for many other fields, for example you can see 0x01000000 as version, that means 0x00000001, because of endianness.

Edit: Also, I made some introduction to hash functions in another topic, it can be useful if you want to try some basic attacks: https://bitcointalk.org/index.php?topic=5402178.0

[pooya87]

Not anyone, but only miners, because those scripts are non-standard. It would work for anyone if those puzzles would use P2WSH or P2TR instead of P2SH.

My understanding is that the redeem script is not subjected to the usual standard rules that would reject the scripts in OP which is why I said "anyone". Although I'm not 100% sure but according to the code it seems like the only "standard" check on redeem scripts is their max sigop count and nothing else:
https://github.com/bitcoin/bitcoin/blob/2a0c05defd32c37f083fa2cc890e03aecc451555/src/policy/policy.cpp#L201-L203

[seoincorporation]

Can someone please explain what happens if there is a collision?

If there is a collision that means someone could have 2 different private keys for the same address.

How can someone exploit it?

With brute force, let's say your target is X RIPEMD160, and you test the hex private keys one by one, then you could find any address searching in 10% of all the total private keys.

How can we stop the exploit?

We can't, but to exploit this is just theoretical, doing it in real life with our current hardware would take too many years, I don't even worth the try.

Is it safe to publish such collisions like what the OP is asking?

Yes, it's safe, maybe 1 address gets compromised, but it will prove the collisions are real because we know they are real but no one has got one yet.

[garlonicon]

My understanding is that the redeem script is not subjected to the usual standard rules that would reject the scripts in OP which is why I said "anyone".

It can be checked on regtest. First, generate some blocks:

Code:

dumpprivkey bcrt1qz5szl8r5ysxmcrfdggt84r83ewr9hy9k2qnmex
cVQHivxE1ZSJvX1xZxNRSzUY9j7ZUtFTQWPXbHEcZN1NkWPczSQe
generatetoaddress 101 bcrt1qz5szl8r5ysxmcrfdggt84r83ewr9hy9k2qnmex

Then, use that address with OP_ABS: 3QsT6Sast6ghfsjZ9VJj9u8jkM2qTfDgHV. Convert to regtest:

Code:

decodescript a914fe441065b6532231de2fac563152205ec4f59c7487
{
  "asm": "OP_HASH160 fe441065b6532231de2fac563152205ec4f59c74 OP_EQUAL",
  "desc": "addr(2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw)#3xnzta3l",
  "address": "2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw",
  "type": "scripthash"
}
decodescript 6e879169907c9087
{
  "asm": "OP_2DUP OP_EQUAL OP_NOT OP_VERIFY OP_ABS OP_SWAP OP_ABS OP_EQUAL",
  "desc": "raw(6e879169907c9087)#yaqxx9nt",
  "type": "nonstandard",
  "p2sh": "2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw",
  "segwit": {
    "asm": "0 414fcb4322bbf4f5b89e94b0749b8504f61937ce8ed3cdee78a70f685420c822",
    "desc": "addr(bcrt1qg98uksezh060twy7jjc8fxu9qnmpjd7w3mfummnc5u8ks4pqeq3q6asxr9)#7zg82sfu",
    "hex": "0020414fcb4322bbf4f5b89e94b0749b8504f61937ce8ed3cdee78a70f685420c822",
    "address": "bcrt1qg98uksezh060twy7jjc8fxu9qnmpjd7w3mfummnc5u8ks4pqeq3q6asxr9",
    "type": "witness_v0_scripthash",
    "p2sh-segwit": "2N6LJuD5PY3woKAZAN2qgpwwbC7wpfaJDWV"
  }
}

Send to that regtest address: 2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw

Code:

decoderawtransaction 02000000000101c2c2f6a1760cad50e51f91dd112a0c3f1423e53d0b32106f922741e82368d35f0000000000fdffffff0191f1052a0100000017a914fe441065b6532231de2fac563152205ec4f59c748702473044022022b4fce5367029c66e1bfbe1615e584e393c516430966a22ad83eb415600190d02205ebb08eeee83e525af76f9a860c923af724bd6f00fabac390b44b0ec20d1bccd01210243b3106e0e478bbffa9561afc0caad73525ea1f09a763ff1b9b9e50fe591b9fdf4000000
{
  "txid": "cee6e8dd048868cb0a74855efeaecaeead3295a2ad8151818b9e62c4950550eb",
  "hash": "c23550c07178b00e28615e0c3bca518c87104c67993569117942ecc37a5c2143",
  "version": 2,
  "size": 192,
  "vsize": 111,
  "weight": 441,
  "locktime": 244,
  "vin": [
    {
      "txid": "5fd36823e84127926f10320b3de523143f0c2a11dd911fe550ad0c76a1f6c2c2",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "txinwitness": [
        "3044022022b4fce5367029c66e1bfbe1615e584e393c516430966a22ad83eb415600190d02205ebb08eeee83e525af76f9a860c923af724bd6f00fabac390b44b0ec20d1bccd01",
        "0243b3106e0e478bbffa9561afc0caad73525ea1f09a763ff1b9b9e50fe591b9fd"
      ],
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 49.99999889,
      "n": 0,
      "scriptPubKey": {
        "asm": "OP_HASH160 fe441065b6532231de2fac563152205ec4f59c74 OP_EQUAL",
        "desc": "addr(2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw)#3xnzta3l",
        "hex": "a914fe441065b6532231de2fac563152205ec4f59c7487",
        "address": "2NGRfABWuVZC3sfN6pcvbmr7zxhF1BTYSAw",
        "type": "scripthash"
      }
    }
  ]
}

Then, we can try spending those coins, in the same way as it was demonstrated on mainnet. First, we prepare our transaction, sending it back to a new address:

Code:

dumpprivkey bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67
cT5k4GH315YFRKiy2VGxG8DVFcXAh9wF7nPZnanMjbsgEd9PypWn
createrawtransaction "[{\"txid\":\"cee6e8dd048868cb0a74855efeaecaeead3295a2ad8151818b9e62c4950550eb\",\"vout\":0}]" "[{\"bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67\":49.99999000}]" 0 true
0200000001eb500595c4629e8b815181ada29532adeecaaefe5e85740acb688804dde8e6ce0000000000fdffffff0118ee052a01000000160014917e9cf02ca3cc88e09b79c0903b3449b06ccc8300000000
decoderawtransaction 0200000001eb500595c4629e8b815181ada29532adeecaaefe5e85740acb688804dde8e6ce0000000000fdffffff0118ee052a01000000160014917e9cf02ca3cc88e09b79c0903b3449b06ccc8300000000
{
  "txid": "18c65cd8c233106ab9156c4589e65b20fdcbcb3d8cda4c2f87e1b73fdf7ac55d",
  "hash": "18c65cd8c233106ab9156c4589e65b20fdcbcb3d8cda4c2f87e1b73fdf7ac55d",
  "version": 2,
  "size": 82,
  "vsize": 82,
  "weight": 328,
  "locktime": 0,
  "vin": [
    {
      "txid": "cee6e8dd048868cb0a74855efeaecaeead3295a2ad8151818b9e62c4950550eb",
      "vout": 0,
      "scriptSig": {
        "asm": "",
        "hex": ""
      },
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 49.99999000,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 917e9cf02ca3cc88e09b79c0903b3449b06ccc83",
        "desc": "addr(bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67)#q8c9z43p",
        "hex": "0014917e9cf02ca3cc88e09b79c0903b3449b06ccc83",
        "address": "bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67",
        "type": "witness_v0_keyhash"
      }
    }
  ]
}

Our spending script would be "OP_1NEGATE OP_1", so "4f51" should do the trick:

Code:

decoderawtransaction 0200000001eb500595c4629e8b815181ada29532adeecaaefe5e85740acb688804dde8e6ce000000000b4f51086e879169907c9087fdffffff0118ee052a01000000160014917e9cf02ca3cc88e09b79c0903b3449b06ccc8300000000
{
  "txid": "726c8e7426506f697e82e897d97c04eb0aae9f55f98dad3dee5c14912af54740",
  "hash": "726c8e7426506f697e82e897d97c04eb0aae9f55f98dad3dee5c14912af54740",
  "version": 2,
  "size": 93,
  "vsize": 93,
  "weight": 372,
  "locktime": 0,
  "vin": [
    {
      "txid": "cee6e8dd048868cb0a74855efeaecaeead3295a2ad8151818b9e62c4950550eb",
      "vout": 0,
      "scriptSig": {
        "asm": "-1 1 6e879169907c9087",
        "hex": "4f51086e879169907c9087"
      },
      "sequence": 4294967293
    }
  ],
  "vout": [
    {
      "value": 49.99999000,
      "n": 0,
      "scriptPubKey": {
        "asm": "0 917e9cf02ca3cc88e09b79c0903b3449b06ccc83",
        "desc": "addr(bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67)#q8c9z43p",
        "hex": "0014917e9cf02ca3cc88e09b79c0903b3449b06ccc83",
        "address": "bcrt1qj9lfeupv50xg3cym08qfqwe5fxcxenyr2a5h67",
        "type": "witness_v0_keyhash"
      }
    }
  ]
}

And then, we can try to send this transaction:

Code:

sendrawtransaction 0200000001eb500595c4629e8b815181ada29532adeecaaefe5e85740acb688804dde8e6ce000000000b4f51086e879169907c9087fdffffff0118ee052a01000000160014917e9cf02ca3cc88e09b79c0903b3449b06ccc8300000000
726c8e7426506f697e82e897d97c04eb0aae9f55f98dad3dee5c14912af54740

Then, we can try to get it confirmed:

Code:

dumpprivkey bcrt1qv7kur5h9h3q74sz5p53q9uytktzzvrhym4qnm3
cNZeS6Mddi2wk7zcvxbEEhqd4oKwjEmSfs7qWdvSh6iRdHteJM7W
generatetoaddress 6 bcrt1qv7kur5h9h3q74sz5p53q9uytktzzvrhym4qnm3

Surprisingly, it was confirmed on regtest. I didn't expect that, last time I checked P2SH addresses, there was a strict requirement that the underlying script has to be standard. I wonder, in which version that was changed, because I remember times, where I had problems with non-standard scripts under P2SH in the past.

[pooya87]

Surprisingly, it was confirmed on regtest. I didn't expect that, last time I checked P2SH addresses, there was a strict requirement that the underlying script has to be standard. I wonder, in which version that was changed, because I remember times, where I had problems with non-standard scripts under P2SH in the past.

It depends on the standard rule, there are other checks taking place in other places (not everything is checked in policy.cpp). For example the interpreter.cpp also performs certain checks on the scriptsig before it reaches the redeemscript and it could be rejecting the tx as non-standard there.

[digaran]

I'm back with more questions 🤭.
In regards to private key collision, are we talking about 2^96 different private keys, 2^96 different public keys which only result in a single RIPEMD-160 ( Address )?

Would that mean 2^96 bitcoin public keys hash to the same SHA-256 hash value? I guess there are indeed 2^96 different public keys that their SHA-256 collides, because we can't mathematically derive 2 different addresses from 1 hash.
However there is also an option to directly use RIPEMD-160 on your public key and get 2 different addresses, but the blockchain doesn't know how to verify your ownership of the new address unless you tell the nodes/ miners to do RIP-160 directly and skip the SHA-256.
Now with the idea explained above, it opens up a window of collision attack on hash-160 and SHA-256 algos. In such a way where if you perform RIP-160 on your pub you would get an address e.g. ( 1digaranXXXXXXXXXXXXXXXXXXXsomething) then knowing the private/public keys of that address is equal to knowing that the SHA-256 hash of the pub key of that address collides with your original public key on RIPEMD-160 algo.

If I'm wrong, good for all, but if I'm right then this should be taken care of because if I could get this right, others might have already figured it out.

[ymgve2]

Your post is very confusing so I'm not even sure what you're saying, and I think you're confused about how addresses are generated. The private key is made into a serialized public key (compressed or uncompressed), THEN it is sent through SHA-256 and THEN the result of that is sent through RIPEMD160. You can't pick, both hash algorithms are done in sequence. You never apply RIPEMD160 to the public key directly.

And here's the math:

There exists approx 2^256 different private keys, which result in 2^256 different uncompressed public keys, but also 2^256 different compressed public keys, for a total of 2^257 different public keys.

To get an address, first the public key is hashed with SHA-256. Due to the reduction from 2^257 to 2^256, each SHA-256 hash will have on average a collision with 1 other public key. Some might collide with 2 other keys, some will collide with none.

Then that SHA-256 hash is hashed with RIPEMD160. This is a reduction from 2^256 to 2^160, meaning that on average each SHA-256 hash will collide with 2^96 other addresses (because 256-160=96).

[digaran]

Well, you say we can't do RIPEMD-160 directly on public keys, well I have done it and have got valid addresses, FYI, all the "theories" about the possible collisions are inaccurate, almost all of the Y coordinates could be used as X coordinates for other addresses, and vice versa.

I just gave you an attack vector, which has nothing to do with bitcoin, it just happens that bitcoin has put itself in the middle of 2 hash collisions ( rather who ever designed them did ).