Bitcoin Forum

As the Bitcoin mining power increases, the target for the SHA-256 hash value becomes smaller and thereby more difficult to reach. This maintains the average time for new blocks at 10 minutes.

A possible flaw could potentially be discovered when the target becomes smaller. For a hash function to work as intended it needs to behave like a random oracle.

"In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted." -- http://en.wikipedia.org/wiki/Random_oracle

Evidently, SHA-256 has behaved pretty much like a random oracle so far for Bitcoin, but what if for lower target values this property starts to degrade? A worst-case scenario would be that for a certain target value, a new block becomes impossible to mine. The Bitcoin mining today depends on the SHA-256 values being distributed randomly. If for some target value the randomness is reduced too much then the worst-case scenario becomes a possibility.

It's a bad situation, but fortunately SHA-256 has held up well this far so it's less than likely to happen. Of course, that doesn't answer your question as to what if it DID happen. I'd imagine it'd probably end in a hard-fork that involved changing to a new algorithm. It'd be a huge disruption and put a lot of ASIC miners out of business but probably wouldn't be the absolute end of Bitcoin.

And then, of course, it becomes a question of whether or not the new algorithm is any more random than SHA-256.

I don't believe it would happen but if it does happen we have no choice but hardfork.

To make sure existing ASIC will still work, we can change the requirement from


to



Let say due to defect in SHA256 it is impossible to find a block if more than 160 leading 0-bits are required. With the new scheme, the target will become 80 leading 0-bits while the probability of success remains 1/2^160

(Currently, the lowest hash found is 80 leading 0-bits: https://bitcointalk.org/index.php?topic=29675.msg8131780#msg8131780)

Actually, I don't think it would become a real problem.

Let's assume that it is impossible to have more than 100 leading 0-bits in an SHA-256 hash. When the target becomes 97 leading 0-bits, 1/8 of the eligible hashes are actually impossible. Therefore, the actual difficulty will become 1.14x of the apparent difficulty. 1.33x for 98 bits, 2x for 99 bits, 3.41x for 99.5 bits, 5.33x for 99.7bits, 14.93x for 99.9bits, etc. This will seriously hinder the growth of the apparent difficulty and we may never hit the boundary of 100 bits (unless someone with massive hashing power suddenly push it over the boundary).

Are you kidding? SHA256 was made by the NSA. They would never promote a faulty standard, right? ...right?

A random oracle is just an ideal theoretical model. In reality SHA-256 will only at best be an approximation of a random oracle if the claim in the following quote is correct:

"... This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function.

It has actually been shown (by Canetti, Goldreich and Halevi) that random oracles cannot exist "in all generality" in the following sense: it is possible to build pathological signature and asymmetric encryption schemes, which are secure when they internally use a random oracle, but which are insecure whenever an actual computable function is used instead of the mythical gnome-in-the-box.

Summary: proofs in the random oracle model are fine, but are never complete enough to cover a practical implementation: we know that any function we will use in lieu of the random oracle will not be a random oracle; so security relies on the fervent hope that the parts where the actual function is not a random oracle do not impact security. This justifies a bit of mistrust. Still, a proof in the random oracle model is much better than no proof at all." -- http://crypto.stackexchange.com/questions/879/what-is-the-random-oracle-model-and-why-is-it-controversial

Hey! I came to think about an idea of how to measure SHA-256's random oracle behavior so far. By taking the statistics for the Bitcoin hash rates over time compared with the target difficulty. If SHA-256 is a good random oracle then those two metrics should remain proportional over time. And if there are deviations (when averaged over longer periods) then that indicates that SHA-256 is a less good random oracle.

Of course, even if it turns out that the Bitcoin statistics so far shows good random oracle behavior there can still be deviations later on when the target is reduced and the difficulty increased. Unless it can be mathematically proved that the behavior will remain consistent over time. That could be tricky to prove if there are very complex nonlinearities in the distribution of SHA-256 hash values.

I've run SHA-256 a few billion times. It looks good, as in, uniform distribution of whatever inputs I gave it. Check out your favorite bitcoin casino, they do a few million SHA-256 every day.

Perhaps I am missing something, but didn't you just demonstrate why it might NOT be a problem? The actual difficulty would rise above the apparent difficulty, but the apparent difficulty would never rise to the point where a valid hash would be impossible, thus allowing the network to continue functioning.

If someone with massive hashing power could push it over the boundary, then blocks would stop until the next difficulty adjustment after which mining blocks would resume. Am I right?

Sorry, I meant " I don't think it would become a real problem."

However, if someone with massive hashing power could push it over the boundary, then blocks would stop, and stop forever. The next difficulty adjustment will happen after 2160 blocks are found, which will never happen.

Remember: difficulty adjustment happens every 2160 blocks, not every 2 weeks

That's true, but (Correct me if I'm wrong) it's nothing that couldn't be fixed by a fork. In fact, a fork would be even easier since the "original" branch of the network would be at a standstill. Granted, the fork would have to include some measure of preventing that same situation from happening again and that may not be feasible.

That's under this assumption of yours:


I don't see any basis for the assumption? Why might there be a certain threshold?

Just a pure academic discussion based on OP's idea

I found what looks like something that could be poor random oracle behavior of SHA-256:

http://s2.postimg.org/y6wbrkcqh/bitcoin_difficulty_transactions.png

Transaction times: https://blockchain.info/charts/avg-confirmation-time?timespan=2year&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address=

Difficulty: https://blockchain.info/charts/difficulty?timespan=2year&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address=

One problem is that blockchain.info is not always very reliable.  I've seen transactions unconfirmed on blockchain.info that are quickly confirmed on other block explorer sites.  Just search the tech support section for examples.

Another problem with that is that transaction confirmation times depend on when they saw the transaction vs.  when they saw it confirm.  Thus it could be influenced by network problems, latency etc. 

My stats is rusty, but you probably want a db of all block hashes and then analyse the conditional distribution and check for uniformness of distribution given the target at the time of each block.

A simple example might be to check the % of hashes that are lower than 50% of the target.  This should be 50%.  You could do this check over different periods to see if something is changing as well.

It is transaction confirmation time, not block time. The transaction volume burst during last bubble so it takes longer to confirm a transaction

It's true that there is an increase in number of transactions around that time but the increase in confirmation time happens a bit before (November 2013) the increase in transaction volume: https://blockchain.info/charts/n-transactions?timespan=2year&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address=

Notice here the green line that shows that the increase in confirmation times happened before the increase in transaction volume:

http://s21.postimg.org/vug4gwdbr/bitcoin_transaction_comparison.png

Not sure why you are looking at transaction confirmation times?

But the blockinfo graph shows an average of about 10 minutes. So isn't that really the block time?

There are lots of properties by which one can evaluate a hash function, but the most important are preimage resistance (if I give you a hash, can you find an input with that hash value?), second preimage resistance (if I give you a message, can you find another that hashes to the same value?) and collision resistance (can you find two messages with the same hash?). Of those, the third appears to be much harder to meet than the first two, based on historical results against hash functions.

I have a quote about that in post #6: "... This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function."

this is a quote from a recent cryptography paper authored by Christina Garman, Matthew Green, Ian Miers, and Aviel D. Rubin

I think it is pretty much inevitable that all of the cryptographic techniques used by bitcoin will need an upgrade at some point in the future.
I don't know when though. :)

Notice that the x-axis on the charts does NOT line up... ::)

Yes, I see that now. Strange that they would use different x-axis scales for the same 2 year period.  ???

Ok, then a more correct measurement is needed.

Your comparison does not make sense anyways - transactions suddenly taking longer to verify just means that blocks are getting relatively full or that people are trying to be cheap with their fees. It does not indicate problems with mining itself.

Are you sure? Looks like quite a big jump in transaction confirmation times.

Here are the transaction confirmation time and volume graphs with corrected x-axis scales:
 
http://s29.postimg.org/l3cvkkzvr/bitcoin_time_volume.png

I don't know how correct the graphs are. A more thorough measurement is probably needed to know for sure.

This metric has nothing to do with SHA256's viability as PoW algorithm.


You did not explain so far why spikes in transaction confirmation times should indicate anything else than an unsuccessful spamming attack, block getting full, users not paying fees or miners charging higher fees. Apparently you think this is the time between blocks? No, it isn't and you have already been told so.

The idea that poor random oracle behavior is a cause of the sudden increase in transaction confirmation times is a hypothesis. The hypothesis must be tested by measuring more carefully the actual historical data, and the test should be able to be replicated. Or other hypotheses, such as you mentioned, would be better to check first.

But how do you know that the metric hasn't anything to do with SHA-256 properties? At this point it seems that we have only a number of hypotheses. Sweeping the anomaly under the rug is an irresponsible way of dealing with it.

It may very well be that the increase has already been explained. It would be surprising if the whole Bitcoin community and all the experts have just ignored it and that a non-expert like myself has to point it out.

Yes, I believe that the graph shows the average time for blocks. The values are around 10 minutes. What is the difference between one confirmation and one block time?

"The classic bitcoin client will show a transaction as "n/unconfirmed" until the transaction is 6 blocks deep." -- https://en.bitcoin.it/wiki/Confirmation

A confirmation being 6 blocks deep. That's around 1 hour, not 10 minutes.

The graph shows the average time for a transaction to be included in a block. It does not show the time between blocks.

Imagine a currency where only 10 transactions fit in a block and blocks get generated every 10 minutes - if there are now suddenly 30 transactions showing up, it takes 30 minutes (15 minutes on average: 10*10 + 10*20 + 10*30 minutes of waiting divided by 30 transactions) until all of them have been processed, even though blocks were always on time.

Yes, there are many transactions within one block of course. I don't know the exact technical details about Bitcoin. It was just that I noticed, whoa, that's a big increase in the graph. To figure out the exact causes is a bit over my head so I only provided my hypothesis about random oracle behavior.

You are confusing your own topic.  Tx confirmation times have nothing to do with the thread you started. You need to look at distribution of hashes not the tx conf times.   

I wrote about hash rates in post #7, but then I found the graph showing an increase in confirmation times and thought it could be related. Now I'm unsure about it because I don't know all the technical details. For example the Bitcoin nonce is only 32 bits so it's more complicated than just changing the nonce in a single block to reach the target value.

I read that Average Transaction Confirmation Time is "The Average time take for transactions to be accepted into a block."

Miners can put transactions in a queue so that's not exactly the block time. My mistake.

I found another graph showing numbers of bitcoins in circulation: https://blockchain.info/charts/total-bitcoins?timespan=2year&showDataPoints=false&daysAverageString=1&show_header=true&scale=0&address=

For the two-year period the amount of bitcoins mined follows a smooth linear line. That could indicate that SHA-256 is a good random oracle.

There is a bend in the beginning of the graph, and that's because of a change in mining reward I assume (November 2012).