Bitcoin Forum

Dear Bitcointalkers,

I apologize if this question has been dealt with, but I haven't found a good answer to it:

Why is it not a terrible idea to rely on a single hash function (i.e. SHA256)?

Supposing that SHA256 was broken, wouldn't the entire accumulated Proof-of-Work become irrelevant all at once? And thus, wouldn't the entire transaction history be at immediate risk of being replaced by a longer chain?

I am sure there must be a good reason, but why not use at least two hash functions? Say, using function 1 for even numbered blocks, and function 2 for odd numbered blocks. That way, if function 1 is broken, it can be switched out with a better one, and during this time the transaction history is still protected by the accumulated PoW of function 2. I can see a drawback with this scheme: specialized hardware for function 1 may be utilized only 50% of the time, likewise for function 2. Perhaps a scheme in which two chains are constructed in parallel, one chain per function, but 'braided' together (a new block referring to the latest block of each chain) could avoid this problem.

I can certainly see potential issues in either case, it would complicate the design, and KISS is a good principle in general. However, what of the fundamental danger? Am I missing something? (Probably).

Humbly,
LH

Hmm... Doesn't the danger remain?

Alright, so let's say we used SHA-256 for even blocks and Keccak-256 for odd blocks. Now let's assume SHA-256 is broken. Now all the even blocks can be generated at will, without (the same) work. The attacker can still use half of his computational power to reverse transactions. In fact, he can still cheat the entire bitcoin economy by solving blocks within seconds, censoring/emptying the block's content.

Edit: He can actually reverse transactions with much less hashrate than half of it. If he's broken SHA-256, he can create one block whose work equals thousands'.

The crux idea is about pre-image resistance of SHA256 but a bigger issue would be a collision resistance, which is weaker than the pre-image.

Any breaks in a pre-image resistance is incremental and slow over time it is simply too difficult and unrealistic to expect the entire algorithm to be broken overnight. In addition, because we require the inputs to be a specific format and also ensures that it is valid at the current state, it wouldn't be a stretch to think that the pre-image wouldn't necessarily result in a valid Bitcoin block.

Having alternate PoW schemes would provide no additional tangible security benefits while making it more complicated.

Yes true, there doesn't seem to be any possible immunity from someone using a break for adding blocks very profitably.

However, they could only add *new* transactions, and not rewrite the entire blockchain from genesis to suit their fancy.

Thank you, I will now spend a few days learning the concepts required to understand your response :)

Not until they substantially raise difficulty; which requires mining 2016 blocks in 1/2 week (4x faster than expected) for every quadrupling of difficulty. So a 1000-fold increase requires over 10,000 blocks.

Interesting question. When could also invert the question: why use multiple hashes ?

Anyway PascalCoin does use multiple hashes. It re-hashes the existing hashes, it also has something called random hash.

There are some obvious down sides to using multiple hash algorithms:

1. More code required, thus:

1.1 More possibility of code bugs.
1.2 Slower compile time.
1.3 More disk usage to store source files.
1.4 More places to hide malicious code.
1.5 Almost impossible to check every hash algorithm/code for a single programmer, lot's of work to-do.

Point 1.5 is pretty heavy weighing. Here a single hash algorithm and single code base has some adventages and at least can be verified to function/work correctly.

I worry that with PascalCoin and randomhash one comprise of one hash function might make the rest of the hashing weaker, though currently I have seen no evidence of this.

Ultimately the final hash is still sha256.

Other more practical reasons might be:

2. There were no alternatives ready/available at the time, maybe no access to code.
2.1 Or security of other hashes less well studied, less confidence in them.

Other problems also illustrated by RandomHash / multiple hashes of PascalCoin:

3. Slower verification. I believe this was solved somehow, not exactly sure how.

Adventages of having multiple hashes:

4. Can more easily switch to another hash, since code base already there, used and tested over time.

The hash function is probably not the main weakness of bitcoin.

The main weakness of bitcoin could be the ecliptic curve algorithm which is used/involved in the generation of private keys.

If there is a pattern in this generation process then that is bad news for bitcoin.

Even as much as 1 bit pattern in the "keys" could comprise it, though still difficult.

At 2, 3 or 4 bits of patterns in the keys it's game over for bitcoin.

So holders of bitcoins are literally a few bits away from bankruptcy.

What needs to happen is more analysis of ecliptic curve algorithm, especially with fourrier transform analysis algorithms and such to determine/detect if there are any patterns in the "signals" where keys can be thought as signals.

At least that is my take from all of 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.

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?

If Hashes are irreversible will there be any means of having a successful brute force certainly not. But lets assume we choose to use a double hash function may be SHA256 and SHA224 all we get is a more complicated hashing and  will consume more storage and retrieval space for effective data mapping.

But time, if it's ruled by one entity, can be faked. The Proof-of-Work timestamp cannot be cheated if there are other miners and you don't control most of the hash rate. For example, say you want to fake your block's timestamp, to benefit yourself from lowering difficulty, by setting it 10 hours ahead. Since the median time of the past 11 blocks isn't complied with it, your block is going to be rejected.

But, if you're the one who chooses the median time of the past 11 blocks, since you mine them, you can fake things out.

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.

So, to use two hash functions, you have to:

1) build some re-hashed chain
2) create a new block hash for each block of this re-hashed chain
3) create your commitment as some random hash
4) increment a nonce in your commitment to get it below your own target

Then, you are still in the same network, because the only difference is that you tweak your own r-value in a signature, when you send your own transaction every sometimes, so you include your commitment for no additional on-chain bytes. For other nodes, it is still random, and they have no idea, which node can use this re-hashed chain, and where are those commitments (and, more importantly, how to read them, because the basic r-value should be random, and then tweaked by your commitment).

To reveal your commitment, you have to:

1) reveal your block header, hashed by your own function
2) reveal a proof that it is attached, by replacing SHA-256 with your own function

That revealing can use the same format as in Taproot. Just replace SHA-256 with your own function and push your own block header as a commitment. Also, in the same way it is possible to run any merge-mined altcoin, just by having some nodes that will move bitcoins every sometimes and push the current state of your chain as commitments, and then reveal them in their own network to push things forward.

How would you increment a nonce to get it below the target?

Sice the hash is random, you now have the additional problem of finding some nonce that will hash into a valid target.

According to my understanding, it's like computing SHA256d(YourHash(x), nonce) but that might be completely wrong.

I just don't see how custom hashes can be masqueraded as a SHA256d hash that is within target, in a feasible amount of time.

Simple. You form a commitment as a block header of the rehashed chain. It contains all fields, including your own nonce, because the old nonce makes sense only in the old chain.

If you have two different hash functions, then you have two different difficulties. And the second one will be quite low, unless more people will adopt that two-hash scheme, then we could switch, and then miners will raise that second difficulty. There is no point in creating very low hashes if you are alone. But there is a point in doing some hashing, because if the first hash function will be fully broken, then you will have a valid Proof of Work for the second hash function that will protect you (and all people that will accept your soft-fork).

Let's explore all fields we have for each block header:

1) version: you can keep it the same as in the original chain
2) previous block hash: it could be "previous commitment hash", for example SHA-3(previousCommitment)
3) merkle root: exactly the same as in the original chain, but every SHA-256 could be replaced with SHA-3
4) time: the same as in the original chain
5) difficulty: completely new and separated value, valid only for rehashed chain, there will be two difficulties
6) nonce: new and sepatated, there will be two nonces

So, you take the original Genesis Block, you rehash everything, and you form a new Genesis Block. From that point, you rehash the whole chain, by applying that rehashing procedure for every single block, just by replacing SHA-256 with SHA-3 everywhere. In this way, everything will be hashed by some new hash function. All signatures, all transactions, all witnesses, just everything. And all you need is to keep that rehashed chain somewhere, maybe even optimized to not store the same things twice, and then you can just attach SHA-3 commitments, in the same way as you can attach SHA-256 commitments, you just replace one 256-bit number with another 256-bit number, it will work.

To sum up, you can do that as a no-fork, then you are safe. Or you can also propose it as a soft-fork, but then you need to reach consensus and convince the whole network for accepting that rules. But you should start with protecting yourself and forming some working proposal, because it is easier to change the rules where you have some complete code and some BIP for that. And if those changes will be rejected, then you can still protect yourself, just in case, if you are really worried about SHA-256. You can even enforce new rules automatically, if some coins from SHA-256 preimages or collisions will be moved, but I think getting some alert is better, because then you will be notified and decide, what to do next.

Just use both hashes on all blocks. That way if one of them is broken, you can still rely on the other one. Extend it to 3 hashes or however many hash types you want in order to give you the security level you require.

I fail to see how this sort of redundancy would be beneficial if at all. If somehow you can generate any valid SHA256 hash at will (highly impossible), then the attacker would be able to dominate and reduce the work done for each block in the SHA256 part. If there is a collision in any of the hash for any set of data, how does the client handle it? Does the client consider both as valid? If it uses the other hash as a check, then isn't it better to just shift to a new algorithm when the need arise?

IMO implementing additional strain on the current resource constraint that we have is unnecessary and wouldn't provide any benefits over the cost.

Got it.


I guess we could also merely add this "nested commitment" inside new and subsequent blocks. I don't see how a no-fork will be accomplished if we are overwriting the Genesis block and old blocks. A soft fork would be more practical but would probably get more hostility, so maybe we can set a reserved bit to indicate there is a nested commitment after this one, like what TCP packets do. And of course, we make sure we reserve some bits in the nested commitment as well.

Nothing is overwritten in the existing SHA-256 chain. You form a new chain by replacing SHA-256 with SHA-3, and then you only attach commitments to your rehashed chain to prove that it existed at a given point in time. And because SHA-3 is used to form a commitment, you can later take some old signature and prove that your rehashed chain was attached correctly.

So, if you have some old client, you will see different r-values in some signatures, but because they are random, you will see no difference, unless people that use such commitments will reveal them somewhere. To sum up:

no-fork: the rehashed chain is committed to the SHA-256 chain, nothing is enforced
soft-fork: that chain is committed and enforced (it could be always connected to the coinbase transaction, with no additional on-chain bytes)

If it would be a soft-fork, then it should be in the coinbase transaction, and it is possible to create some standard for attaching all commitments, always store them sorted, and if you have a sorted merkle tree, then you can prove that there is some commitment (you hash it, and find it in the tree) or there is no commitment (you explore the tree logarithmically and find two leaves with the most matching prefix bits, and there is a proof that nothing is between them, because you reach data, so you cannot go deeper in this tree). So, if you have unsorted binary tree, you need to check everything to make sure that something is or is not a part of that tree. But if it is always sorted, then each data has its own position, and you can find it logarithmically, based on the hash of that data.

Edit:
no-fork: the client does nothing, it can also send some kind of alert or stop working, it depends on the local configuration
soft-fork: the client will switch to the rehashed chain automatically and will enforce new rules in a soft-fork way

It will try to find some commitments, and if there are none, then it could consider both as valid or use first-seen-safe rule. It could be handled in the same way as handling different blocks on the same height equal to one, when you run your Bitcoin Core client locally and attach some ASIC to flood your node with a lot of blocks on the same height. You can also see how it is handled in regtest, where many miners will mine many blocks on the same height, instead of creating a very long chain of blocks.

It is better, but that would be a hard-fork. It is easier to convince the community to form a consensus over some soft-fork than over some hard-fork.

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.


a collission would mean all the hashes matched. not just "any" of them. we're talking about not relying on a single hash function. to me that seems reasonable. gives a bit of backup redundancy. but yeah there is a cost. and maybe an entirely new algo would be better but that's a way different topic.

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

No, because if you have two hashes, then you need to perform all SHA-256 hashing as today, and also add all SHA-3 (or whatever) hashing on top of that. So, of course the performance will always be slower than today. But if some user wants to use two hashes instead of one, then they definitely can put some overhead on their own nodes. In case of no-fork, it is safe, you can put 100 additional hash functions if you really want. In case of soft-fork, you need to reach consensus, so I think most users will disagree, and will stick with plain, old, SHA-256-only version.

For example, lets say you used 10 hashes. Each hash should only take about 1 minute to find - 10 minutes total. Whereas if you were using just one hash, it would need to take the entire 10 minutes to find it. Same amount of work either way.

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

Nope, probably won't be detectable.

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.

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.

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.

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

On a related note to this:


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.

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.

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.

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.

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.

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

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.

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.

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.

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

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.

maybe their approach was just less than optimal.

Not sure about that.

they would just need to use something more secure.

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.

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.
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.
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.
Proving P=NP would be sufficient to prove SHA256 is not a one-way function.

Nope. That is just not what ASICs do.

Then a concrete proof would be good, either that of a past algorithm that has been broken or any theoretical attacks.
You can't really do much once you prove P=NP.

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

Why would the latter not be possible? Assuming that I can mine essentially for free, I can just re-create a version of the full blockchain, keeping all transactions identical to the original, except for the destination address in some coinbase transactions (those which are attributed to Satoshi in the original chain). Not sure what would prevent me from doing this.


Ok, but breaking SHA-256 would not imply that one-way functions don't exist (and neither would breaking ten or a hundred different hash functions).

Anyway, it still seems to me that there is a lot (too much) riding on the fact that SHA-256 will not be broken, or if so, that it would be broken in a slow, and visible fashion. I am quite surprised by this, seeing as Bitcoin's main tenet is immutability guaranteed by PoW, which falls apart in case of a break. Admittedly I don't know anything about cryptography, but the single point of failure strikes me as strange.

Simply because you won't be able to generate hashes like these just like that. There has never ever been any attacks which allows users to find pre-image in this manner.

You can do that, but the community won't recognize your chain as valid. It is quite obvious which chain to follow.

As I've mentioned, the manner which the topic postulates SHA-256 to be broken seems to suggest a catastrophic failure of it and for which I'm inclined to believe that the only scenario that happens is when all the other algorithms are also broken. Speed ups in the PoW is counter-acted by difficulty increase, at best there would be a minor reduction in the complexity of pre-image but not financially sensible enough to exploit it.

I think there is a clear distinction between what should be classified as a point of failure, which in this case is how the algorithm can become insecure. I don't doubt that SHA-256 would eventually be broken, but what I do doubt is that it would be broken in this manner. The most likely scenario is that we would recognize its weakness decades in advance and when it finally becomes (remotely) feasible, then we would've long shifted from using SHA256 as the PoW algorithm.

Well, 90 years ago Kurt Gödel proved such absolute statements are false.

That said - and thanks to bitcoin - we would never know if one is capable to easy reverse hashes. If NSA and similar cannot do it yet, then they would never be able to. Anybody coming close to an answer would be very incentivized to keep it to himself, and never ever share.

We know today that reversing hashes is impossible and will always be. If you know that the hash is 4, and your hash function is mod10, then you can use 4, 14, 24, 34, 44, ..., and you will never know, which value was hashed. You could know that only in one case: if you would know some properties of the hashed data. So, if you know that some ASCII string is hashed, then it may be possible to prove that this particular 256-bit hash will only match "Hello World", because nothing else is matching ASCII values (or nothing else is in your "dictionary"), and you can try to prove that, based on context. But if something is totally random, for example some private key, some signature nonce, things like that, then you will never know, what was really hashed, and what was recovered as a second preimage.

I think the answer is quite simple: because using two or more hash functions can make the system more complex, and will not make it more secure at the same time, so it is not worth it. But as I described, you can do it yourself, if you really want. You can implement it, you can promote it, you can convince people to switch to things like that, but I think the consensus will be formed around single hash function, unless something serious will be broken (or will show some serious weakness). Also, to add something more to SHA-256, you have to know, how it can be attacked, because you don't want to add mod10 and other useless hash functions when they are not needed and can be as "broken" as SHA-256, so it may turn out that for example SHA-3 is even worse in case of some particular attack vector, that's why it should be attack-vector-based, and not randomly picked.

Although I'm not a mathematician but that's not what he proved. He proved that in any mathematical system there are some statements that are considered true but can not be proven. Not that everything that is true such as basic math could be false! That would be crazy talk.