Topic: REWARD offered for hash collisions for SHA1, SHA256, RIPEMD160 and other - page 3. (Read 40742 times)

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:
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.

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.

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.

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.

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".

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.

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

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.

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:

With input (unlocking script):

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

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.

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.

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.

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.

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).

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).

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.

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.

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.

Bruce sure knows his stuff.

thats something we could see it coming, thats why it was developed sha256 and some other algos, like will be created many more algos to replace sha256, it will be interesting to see what would  btc core developers do on those coming scenarios

http://www.coindesk.com/who-broke-the-sha1-algorithm-and-what-does-it-mean-for-bitcoin/

SHA1 is like MD5 

No Panic guys 

SHA1 has also been deemed quite vulnerable to collision attacks which is why all browsers will be removing support for certificates signed with SHA1 by January 2017. SHA256 however, is currently much more resistant to collision attacks as it is able to generate a longer hash which is harder to break.

https://en.bitcoin.it/wiki/Weaknesses#Breaking_the_cryptography

If a SHA256 collision happens what is the worst scenario? I think I would have a hearth attack or something.

How would the Core team proceed in order to make the switch to a safe algo? Would it be an absolute fuckfest or it is a smooth process? Because I presume we wouldn't have a lot of time to waste being exposed with SHA256 through the transition.

Could anti Core trolls or just bitcoin attackers in general try to delay the switch or somehow block it?

I hope those things are properly planned in the unfortunate even that happens otherwise im not going to be able to sleep ever again.

Not all cases are morally clear cut. What if someone disagrees with how someone else acquired the coins in the first place?

A more interesting example of how "stealing" becomes fuzzy is LN payment channels. What if I close a channel with an earlier stage to my advantage, and I succeed because my peer for some reason fails to monitor the blockchain?

Am I stealing? Not really. My gains  would be the result of an explicit and well known  clause of our contract. Would you consider this morally wrong?

I think we should value the programmatic rules of contracts and as such not judge these types of theft in the same way as we would do with theft in the "real" world.

You may not recognize or agree with a or any legal distinction between stealing someone's BTC and claiming a BTC reward as was done here in this thread or is being done in the puzzle transaction.

But there is a huge moral distinction between the two:  stealing someone's BTC is wrong, claiming a BTC reward is not wrong.

Just because you can do something does not make it morally right.

That is an interesting distinction as this implies that the blockchain should recognize some form of legal or moral ownership defined outside of the blockchain.

An alternative view more in line with the decentralized nature of bitcoin, is that "ownership" is simply defined as being able to produce a valid input script for an output script.

As such, someone being able to find the private key of an early public key by whatever means, must be considered the "owner". It doesn't matter if the keys are found on an (owned) usb-stick or by trial and error,

sha256 for now can sleep peacefully, i dont know for how long, every day hardaware processing capabilities increase, and the news about china's quantum computer may affect all this

Yeah that's funny it happened the same day but I don't see how this could be related

And hopefully we won't see an SHA256 collision in our lifetime but you never know, it may have a major flaw discovered in the following years

Here the team founds an algorithm 100000 times faster than bruteforcing

Is it a coincidence that this happened right when bitcoin was shattering throught the ATH?

Anyway, as far as I know we are safe for years with SHA256, or satoshi said so some years ago, he said we wouldnt see a SHA256 collision in our lifetime.