Topic: Why rely on a single hash function? - page 2. (Read 607 times)

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.

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

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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?

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.

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.