What if SHA-256 is a poor random oracle?

[logictense]

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=

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.

[Anders]

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=

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

[Crowex]

at some point in the future, it seems likely SHA256 will be broken in a way that makes it utterly unsuitable for instantiating a random oracle, just as MD5 and MD2 have been broken.

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.

[Sukrim]

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

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

[Anders]

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

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.

[Sukrim]

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.

[Anders]

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.

[Anders]

Here are the transaction confirmation time and volume graphs with corrected x-axis scales:
 


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

[Sukrim]

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

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

*snip*

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.

[Anders]

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

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

*snip*

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.

[Anders]

Apparently you think this is the time between blocks? No, it isn't and you have already been told so.

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.

[Sukrim]

Apparently you think this is the time between blocks? No, it isn't and you have already been told so.

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

[Anders]

Apparently you think this is the time between blocks? No, it isn't and you have already been told so.

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

[spin]

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.   

[Anders]

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.

[Anders]

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