Title: What if SHA-256 is a poor random oracle? Post by: Anders on September 13, 2014, 02:06:23 PM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Quokka on September 13, 2014, 02:56:41 PM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: jl2012 on September 13, 2014, 02:59:44 PM 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 Code: HASH256(version|prev_block|merkle_root|timestamp|bits|nonce) < target to Code: HASH256(version|prev_block|merkle_root|timestamp|bits|nonce) < target 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) Title: Re: What if SHA-256 is a poor random oracle? Post by: jl2012 on September 13, 2014, 04:53:39 PM 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). Title: Re: What if SHA-256 is a poor random oracle? Post by: Willisius on September 14, 2014, 01:16:00 AM Are you kidding? SHA256 was made by the NSA. They would never promote a faulty standard, right? ...right?
Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 14, 2014, 03:14:23 AM 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 Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 14, 2014, 08:01:46 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Dabs on September 14, 2014, 01:00:53 PM 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.
Title: Re: What if SHA-256 is a poor random oracle? Post by: Razick on September 14, 2014, 04:25:00 PM Actually, I suspect that 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). 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? Title: Re: What if SHA-256 is a poor random oracle? Post by: jl2012 on September 14, 2014, 04:42:20 PM Actually, I suspect that 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). 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 Title: Re: What if SHA-256 is a poor random oracle? Post by: Quokka on September 14, 2014, 10:47:38 PM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: 🏰 TradeFortress 🏰 on September 15, 2014, 01:02:54 AM 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. That's under this assumption of yours: Quote Let say due to defect in SHA256 it is impossible to find a block if more than 160 leading 0-bits are required. I don't see any basis for the assumption? Why might there be a certain threshold? Title: Re: What if SHA-256 is a poor random oracle? Post by: jl2012 on September 15, 2014, 03:42:15 AM 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. That's under this assumption of yours: Quote Let say due to defect in SHA256 it is impossible to find a block if more than 160 leading 0-bits are required. 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 Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 18, 2014, 07:19:22 AM 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= Title: Re: What if SHA-256 is a poor random oracle? Post by: spin on September 18, 2014, 08:07:37 AM I found what looks like something that could be poor random oracle behavior of SHA-256: .... blockchain.info .... 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: jl2012 on September 18, 2014, 12:07:49 PM 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= It is transaction confirmation time, not block time. The transaction volume burst during last bubble so it takes longer to confirm a transaction Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 18, 2014, 01:37:09 PM 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= Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 18, 2014, 02:12:12 PM 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 Title: Re: What if SHA-256 is a poor random oracle? Post by: spin on September 18, 2014, 05:07:15 PM Not sure why you are looking at transaction confirmation times?
Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 18, 2014, 05:15:58 PM 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? Title: Re: What if SHA-256 is a poor random oracle? Post by: logictense on September 18, 2014, 09:01:18 PM 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= Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 18, 2014, 09:30:12 PM 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= 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." Title: Re: What if SHA-256 is a poor random oracle? Post by: Crowex on September 18, 2014, 10:32:26 PM Quote 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. :) Title: Re: What if SHA-256 is a poor random oracle? Post by: Sukrim on September 19, 2014, 09:16:58 AM 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... ::) Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 10:10:17 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Sukrim on September 19, 2014, 10:39:51 AM 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.
Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 11:03:17 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 11:05:51 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Sukrim on September 19, 2014, 11:17:43 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 12:38:36 PM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 12:47:59 PM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Sukrim on September 19, 2014, 01:08:25 PM 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?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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 19, 2014, 01:42:30 PM 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?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. Title: Re: What if SHA-256 is a poor random oracle? Post by: spin on September 19, 2014, 09:45:02 PM 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.
Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 20, 2014, 05:09:13 AM 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. Title: Re: What if SHA-256 is a poor random oracle? Post by: Anders on September 20, 2014, 06:05:57 AM 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). |