Why rely on a single hash function?

[garlonicon]

If the whole network will switch? Yes, could be. But then it could be 3 minutes for the first hash and 7 minutes for the second, it can be distributed in many ways, it doesn't have to be equal on both sides. But if only one individual or a small group will switch, then it will take the same resources to validate SHA-256, and they will also need more resources to verify SHA-3 and to mine SHA-3, just because they want. They will never get any new bitcoins for doing that, they could only get some altcoins if their consensus will be based on accepting commitments from Bitcoin to push their chain forward.

Edit: it also seems to be possible to be rewarded in the Lightning Network for adding SHA-3 commitments. So yes, they could get some bitcoins for their work, but it would require adding some new rules inside some LN nodes to handle all of that (and it should be optional, to not mess up with existing LN functions).

[ranochigo]

I see your point. But the assumption is that if sha256 or any of the other hashes being used was broken then everyone would be able to reduce the work done for each block. Thus everyone would still be on a level playing field. OTOH, if just one attacker was breaking sha256 and no one else was then yeah, i see the problem. but wouldn't that be detectable and maybe a feature in the code could then disable the compromised hash function.

Nope, probably won't be detectable.

well, i think the overall amount of work would remain the same. just the difficulty target on each individual hash might be adjusted.

It won't be. The validation on each node is a O(N) problem where you'll just double the work on each node because you have each node validating two hashes on one. The validation effort of the entire network is a O(N^2) problem (CMIIW) because each of the nodes must now do two validations instead of one. There are tons of constraints involved with any changes made to the network and any radical changes have to consider the needs of the network and the possible resource requirements in the long term.

In this case, there isn't any tangible benefits because as mentioned, there is no such thing as a catastrophic failure in cryptography (or at least it isn't common at all in the realm of cryptography). It simply doesn't make sense for us to have to consider something like this when we have far more pressing issues to address first.

[garlonicon]

Nope, probably won't be detectable.

It is somewhat detectable. Somewhat, because there are challenges for SHA-256 collisions. Also, it is possible to create a challenge for SHA-256 preimage (challenges for HASH160 are called burn addresses). But yes, if all attackers are silent, then there is no chance to detect that.

The validation effort of the entire network is a O(N^2) problem (CMIIW) because each of the nodes must now do two validations instead of one.

True. You can see that on some altcoins that changed SHA-256 to something else, especially CPU-mineable coins that changed it everywhere, so not only mining is CPU-efficient, but merkle root and signature checking is also a bottleneck. Then, validating the whole CPU-mineable chain could be as hard as mining some blocks.

[larry_vw_1955]

It is somewhat detectable. Somewhat, because there are challenges for SHA-256 collisions. Also, it is possible to create a challenge for SHA-256 preimage (challenges for HASH160 are called burn addresses). But yes, if all attackers are silent, then there is no chance to detect that.

but if the same miner kept winning blocks you would know something was wrong.

[NotATether]

On a related note to this:

First of all it depends on what "broken" means. For example we call SHA1 broken and you can't reverse it or find a collision if you can't control the message, also it is still used in git for integrity of commits without any problem.

Although SHA1 pre-images are limmited to certain patterns imposed by the method of attack, enough pre-images migh be found in it that one day, a state actor (or someone stealing tools from a state actor) can forge SHA-1 messages with reasonable accuracy, and generally we cannot predict when this will happen due to the secrecy of these acts. [We usually find out when a zero-day for multiple software is discovered related to this instead]. That's why "unsafe" is the nominal definition for broken as far as cryptography is concerned.

[pooya87]

On a related note to this:

First of all it depends on what "broken" means. For example we call SHA1 broken and you can't reverse it or find a collision if you can't control the message, also it is still used in git for integrity of commits without any problem.

Although SHA1 pre-images are limmited to certain patterns imposed by the method of attack, enough pre-images migh be found in it that one day, a state actor (or someone stealing tools from a state actor) can forge SHA-1 messages with reasonable accuracy, and generally we cannot predict when this will happen due to the secrecy of these acts. [We usually find out when a zero-day for multiple software is discovered related to this instead]. That's why "unsafe" is the nominal definition for broken as far as cryptography is concerned.

The risks of different attacks on all cryptography algorithms are always present but we usually have a pretty good idea about cost of different attacks and the estimation is in the ballpark specially for solid old algorithms such as SHA256. This is why SHA1 was removed from a lot of places where it was used a long time before the successful attack was demonstrated by Google.

[ranochigo]

but if the same miner kept winning blocks you would know something was wrong.

No way of knowing which miners mined which blocks. The only reason you know certain pools are mining blocks is because they explicitly state it in their coinbase. Otherwise, you actually cannot tell them apart and any analysis can be defeated relatively easily (randomized nonce, timestamps, coinbase, etc).

Also defeating (not weaken) SHA256 or any cryptography like that is quite valuable, certainly not valuable enough to use on Bitcoin.

Although SHA1 pre-images are limmited to certain patterns imposed by the method of attack, enough pre-images migh be found in it that one day, a state actor (or someone stealing tools from a state actor) can forge SHA-1 messages with reasonable accuracy, and generally we cannot predict when this will happen due to the secrecy of these acts. [We usually find out when a zero-day for multiple software is discovered related to this instead]. That's why "unsafe" is the nominal definition for broken as far as cryptography is concerned.

IIRC SHA1 was considered insecure 2 decades ago or thereabout. The attacks were only somewhat practical fairly recently and even so they incurred quite a high cost and time.

[larry_vw_1955]

No way of knowing which miners mined which blocks. The only reason you know certain pools are mining blocks is because they explicitly state it in their coinbase. Otherwise, you actually cannot tell them apart and any analysis can be defeated relatively easily (randomized nonce, timestamps, coinbase, etc).

interblock times would go down if it had been broken. such that they always beat everyone else to the punch. so that's how you can detect it.

[ranochigo]

interblock times would go down if it had been broken. such that they always beat everyone else to the punch. so that's how you can detect it.

There's no difference between this and newer/more ASICs coming online. You can argue that someone might start mining all of the blocks but even that is unlikely because any breakthrough takes years to progress and SHA256 wouldn't possibly be broken overnight.

[NotATether]

interblock times would go down if it had been broken. such that they always beat everyone else to the punch. so that's how you can detect it.

But would the cost be economical for mining farms to consider? After all, they aready have the headache of maximizing profits out of the thin margins of hashpower vs. difficulty. It is unlikely theyhave much cash wiggle-room to rent several hundreds of CPUs (the attacks cannot be carried out on ASICs) for a computation which may not hit a block in time. And if there was any such warning that this is what they were doing (we'd hear roumors and leaks from the news), then the community would act quickly and deploy a BIP + soft-fork with another algorithm instead.

[larry_vw_1955]

interblock times would go down if it had been broken. such that they always beat everyone else to the punch. so that's how you can detect it.

But would the cost be economical for mining farms to consider? After all, they aready have the headache of maximizing profits out of the thin margins of hashpower vs. difficulty. It is unlikely theyhave much cash wiggle-room to rent several hundreds of CPUs (the attacks cannot be carried out on ASICs) for a computation which may not hit a block in time. And if there was any such warning that this is what they were doing (we'd hear roumors and leaks from the news), then the community would act quickly and deploy a BIP + soft-fork with another algorithm instead.

not sure what you're addressing. i was saying it sha256 got cracked, then that would obselete mining hardware from cpus to gpus to asics, everything.

[ranochigo]

not sure what you're addressing. i was saying it sha256 got cracked, then that would obselete mining hardware from cpus to gpus to asics, everything.

Actually NotATether brought up quite an interesting point that I actually didn't consider.

Any reduction in the complexity of SHA256 either requires a very specific set of hardware or just your regular GPU clusters which allows you to parallelize your calculations. ASICs are unfortunately too specific for this. Pre-image attacks are actually not very common still, I know MD2 was cracked but that required an enormous amount of memory and huge computational resources. You must realize that the complexity reduction of those are not significant enough, MD2 being 2^73[1] with varying memory requirements. In fact, SHA hasn't even been cracked yet, to any extent within the realm of feasibility.

There is no such thing as producing a valid block hash with little computations, that is not within our reach for the near future. If that happens, you can be sure that cryptography is dead.


[1] https://eprint.iacr.org/2008/089.pdf

[laminar_hash]

First of all it depends on what "broken" means. For example we call SHA1 broken and you can't reverse it or find a collision if you can't control the message, also it is still used in git for integrity of commits without any problem.

Secondly, I'd say if something is "broken" it has to be replaced instead of creating a band-aid where it still is used alongside something else. Adding the secondary hash requires a hard fork so why not just replace it?

Good point, I did not define "broken" with any degree of precision. In this context I would call SHA-256 broken if someone is able to find valid block hashes with a much decreased amount of work compared to brute force. If I understand correctly from my Wikipedia readings, breaking pre-image resistance would entail the ability to create a block for any desired hash value, whereas what I refer to is a weaker condition, i.e. finding a block whose hash value is small enough.

Concerning the point of replacing vs. creating a band-aid. I am thinking of scenarios in which it is not apparent that someone has managed to "break" the algo, until it is revealed in a catastrophic fashion when a longer chain is published as an adversarial attack on the Bitcoin network (resulting in sudden destruction of trust and collapse of price), at which point it may be too late to operate a replacement.

[laminar_hash]

As my friend always said: "we can do everything, the question is: should we?". And here you have the same situation: if you really want to add some hash function, then of course you can. You always can protect things by more restrictive rules, and make it a soft-fork or no-fork. You can start with no-fork, so your node will keep everything and will warn you that you have a block where SHA-256 is broken.

Technically, all you need is re-hashing everything with your hash function, and then add commitments for that. You can even hide your commitments in r-values of your signatures, then they still will be hashed by SHA-256, and you can always un-wrap them later, and then easily show that you have some additional Proof of Work protection that can be deployed immediately. Because it will give you no coins, there will be no problem with "mining without other people", as you will only hash some old blocks.

Thanks! Most of your post is going straight over my head, so I will invest in self-study to try and understand it. But from what I gather in your no-fork proposal, you are saying that I could be (privately) building a parallel chain with alternative hash function, and accumulating some Proof-of-Work in that, which could be used as a bootstrap if a sudden break of SHA-256 appeared, correct? If so, I guess that is an interesting point to consider, although it would basically mean that this work would go unrewarded by the network, and hence likely the accumulated PoW could only be very small, and would not last long vs. an adversary who had the means to break SHA-256.

[laminar_hash]

Also defeating (not weaken) SHA256 or any cryptography like that is quite valuable, certainly not valuable enough to use on Bitcoin.

1. Would it be useful in other contexts to be able to find "small enough" hashes?
2. Perhaps there are other very valuable uses, but Bitcoin does have half a trillion market cap. You could for example place a gigantic leveraged short on BTCUSD just before publishing your proof that SHA-256 is broken. Or you could rebuild the chain unchanged except for reassigning the Satoshi wallet to yourself.

[laminar_hash]

There is no such thing as producing a valid block hash with little computations, that is not within our reach for the near future. If that happens, you can be sure that cryptography is dead.

Why would all of cryptography be dead if this was possible for a specific hash function?

[larry_vw_1955]

Any reduction in the complexity of SHA256 either requires a very specific set of hardware or just your regular GPU clusters which allows you to parallelize your calculations.

i think you might be assuming sha256 is a one-way function. it might not be. and thus there could be an easy way to reverse it that no one ever though of yet.

ASICs are unfortunately too specific for this. Pre-image attacks are actually not very common still, I know MD2 was cracked but that required an enormous amount of memory and huge computational resources.

maybe their approach was just less than optimal.

There is no such thing as producing a valid block hash with little computations...

Not sure about that.

If that happens, you can be sure that cryptography is dead.

they would just need to use something more secure.

[pooya87]

i think you might be assuming sha256 is a one-way function. it might not be. and thus there could be an easy way to reverse it that no one ever though of yet.

It is and it will always be impossible to reverse hashes until the end of time, this is even true for non-cryptographic hash functions like MurmurHash. That's for a very simple reason: math.

To put simply if I told you I had a two digit number and I added its digits to get 10 you will not be able to figure out what that number was until the end of time. You can guess other numbers that give the same result like 10 or 46 or 55,... (ie. find collision) but you will never be able to "reverse" the operation to know what number I really used.

Now imagine if the result (10) wasn't so small and was 256 bit instead and I wasn't just doing x+y and was doing a lot more operations to get the final result. That's what happens in a hash function. Due to chaotic and irreversible nature of each operation it is never going to be possible to reverse it.

[ranochigo]

1. Would it be useful in other contexts to be able to find "small enough" hashes?

Most of the applications of cryptography in real life requires the property of it having to have a certain degree of pre-image resistance. If that were to be broken, the hash is no longer a one way function, to which it becomes useless for certain real-life applications. Even before that, we have the collision resistance being broken, which already means that the hash function wouldn't be very useful for sensitive operations.

2. Perhaps there are other very valuable uses, but Bitcoin does have half a trillion market cap. You could for example place a gigantic leveraged short on BTCUSD just before publishing your proof that SHA-256 is broken. Or you could rebuild the chain unchanged except for reassigning the Satoshi wallet to yourself.

The latter is not possible. As for the former, if you were to approach NSA or related organizations directly, you would probably have a guaranteed payout rather than to attack the chain and risk being labelled a criminal and getting yourself investigated. You'd probably have much better things to do if you could discover a feasible way to generate collisions anyways (at low costs of course).

Anyways, current resistance is still sufficiently high and that is expected for the near future.

Why would all of cryptography be dead if this was possible for a specific hash function?

Because historically well studied algorithms has never been broken with very little computational power/efforts. If you were to prove that one-way function don't exist, ie. P=NP, then any other cryptography functions would also be dead.

i think you might be assuming sha256 is a one-way function. it might not be. and thus there could be an easy way to reverse it that no one ever though of yet.

Proving P=NP would be sufficient to prove SHA256 is not a one-way function.

maybe their approach was just less than optimal.

Nope. That is just not what ASICs do.

Not sure about that.

Then a concrete proof would be good, either that of a past algorithm that has been broken or any theoretical attacks.

they would just need to use something more secure.

You can't really do much once you prove P=NP.

[tromp]

It is and it will always be impossible to reverse hashes until the end of time, this is even true for non-cryptographic hash functions like MurmurHash. That's for a very simple reason: math.

We are all eagerly awaiting your math proof of P != NP...