Could code be changed quickly if vulnerability found?

[chaintest]

I am fairly certain that I have found a vulnerability in Bitcoin, just not yet sure yet how serious it is.

For now, though, let's just assume I'm clueless newbie or a crackpot, and I'm wrong.

In theory, though, if someone discovered such a vulnerability -- serious enough that without fairly quick action (and/or detection), the survival of Bitcoin could be potentially be jeopardized -- is there a plan in place to put in a fix?  Let's say, for example, a miner discovered a way to solve blocks in a minute or two at the current difficulty level, on a standard CPU.  By waiting until the difficulty was re-calculated, they could rack up some 50,000BTC before the difficulty changed again.  And that would cause the new difficulty to skyrocket, , and making it nearly impossible for anyone else to mine blocks (perhaps there are safeguards in place for that).  Or the person who discovers it is benevolent and tells the world, and the network hash rate goes berserk.  Or they are more nefarious and use it to double-spend, reverse transactions, whatever.  Or they quietly mine bitcoins at a rate slower than the biggest miners, not drawing attention to themselves.

If a fix could be identified quickly, could it be coded/tested/distributed in a reasonable amount of time?  What about the "chicken and egg" problem: if the details of the vulnerability are disclosed before the fix, someone could abuse it before the fix, but if the details are not disclosed before the fix, changes to Bitcoin could be made that would be unnecessary (and it would open up the door to people making wild claims).

I've read the "Dealing with SHA-256 Collisions" thread; Bitcoin has become much, much bigger since then, and the potential problems much harder to deal with.

FWIW, I'm confident that there is a problem -- I just haven't yet figured out if it is serious enough to be concerned about at this point.  But I thought it couldn't hurt to have a fresh "what if?" discussion.

[cr1776]

Enlighten us on the vulnerability.

[coinrevo]

See BIP50: https://github.com/bitcoin/bips/blob/master/bip-0050.mediawiki

Very interesting questions/speculations. However the scenario you described is not realistic. Why should progress of mining capability be so sudden? Reminds me of all the atttempts at proving P=NP and questions around quantum computing. If somebody discovers such a technique it will likely be discovered by others. Moore's law graph is very smooth.

An attack on bitcoin is very similar to what happened to the fiat system in 2008. I think such an event in the fiat world is quite likely (see N. Taleb's writings). I hope that at the least bitcoin is a backup system, because such events could be quite catastrophic.

There are many scenarios which are unlikely, which does not mean they are not going to happen. I speculated there could be an attack insurance, so that the values would be frozen before the attack and then distributed during the fix. Analogous to bankruptcy proceedings. But if the fix would have been anticipated it would have been there in the first place (as you said chicken egg problem).

Say the exchange value would drop to zero. The "attacker" (in your scenario he is just an honest miner) has lost his money as well. Instead he could mine. If nobody has ever heard of this technique he would accumulate a lot of hashing power. Such an event is possible, and one of the weakness of the algorithm. One would hope by that time there are solutions. In the end nobody says it can't happen. It just seems a lot of people are betting their money that it won't. The exchange rate is the present value over the lifetime of the coin. If every cryptographer on the planet has analysed bitcoin and not found a vulnerability, its unlikely random guy23 will find one.

[empoweoqwj]

I am fairly certain that I have found a vulnerability in Bitcoin, just not yet sure yet how serious it is.

For now, though, let's just assume I'm clueless newbie or a crackpot, and I'm wrong.

In theory, though, if someone discovered such a vulnerability -- serious enough that without fairly quick action (and/or detection), the survival of Bitcoin could be potentially be jeopardized -- is there a plan in place to put in a fix?  Let's say, for example, a miner discovered a way to solve blocks in a minute or two at the current difficulty level, on a standard CPU.  By waiting until the difficulty was re-calculated, they could rack up some 50,000BTC before the difficulty changed again.  And that would cause the new difficulty to skyrocket, , and making it nearly impossible for anyone else to mine blocks (perhaps there are safeguards in place for that).  Or the person who discovers it is benevolent and tells the world, and the network hash rate goes berserk.  Or they are more nefarious and use it to double-spend, reverse transactions, whatever.  Or they quietly mine bitcoins at a rate slower than the biggest miners, not drawing attention to themselves.

If a fix could be identified quickly, could it be coded/tested/distributed in a reasonable amount of time?  What about the "chicken and egg" problem: if the details of the vulnerability are disclosed before the fix, someone could abuse it before the fix, but if the details are not disclosed before the fix, changes to Bitcoin could be made that would be unnecessary (and it would open up the door to people making wild claims).

I've read the "Dealing with SHA-256 Collisions" thread; Bitcoin has become much, much bigger since then, and the potential problems much harder to deal with.

FWIW, I'm confident that there is a problem -- I just haven't yet figured out if it is serious enough to be concerned about at this point.  But I thought it couldn't hurt to have a fresh "what if?" discussion.

Sorry, but if you didn't even know that "code can be changed" (implies you have no idea how open source is structured) I highly doubt you have found a vulnerability in any of the bitcoin mining algorithms.

[chaintest]

Enlighten us.

That's the $50 million question.  If I enlighten here, depending on whether or not I am right and how severe the issue is, things could get chaotic.  And, I need a bit more time to try to figure out how severe it really is.

Say the exchange value would drop to zero. The "attacker" (in your scenario he is just an honest miner) has lost his money as well. Instead he could mine. If nobody has ever heard of this technique he would accumulate a lot of hashing power. Such an event is possible, and one of the weakness of the algorithm. ... If every cryptographer on the planet has analysed bitcoin and not found a vulnerability, its unlikely random guy23 will find one.

Ah, I should see if I can change my handle to "random guy23".  :)

For the time being, I am assuming I am just random guy23, and that I'm seeing things that aren't there.  But I want to be prepared, just in case.  The idea of striking it rich certainly is appealing, but doesn't seem ethical.

[chaintest]

Sorry, but if you didn't even know that "code can be changed" (implies you have no idea how open source is structured) I highly doubt you have found a vulnerability in any of the bitcoin mining algorithms.

I am reasonably familiar with how open source is structured.  And I'm not asking if I have found a vulnerability (I know what I have found, and that I need to do more work to determine if there truly is a vulnerability, and if so, how severe it is).

Each open source product is different; I'm asking about this specific one.  Essentially, could a change be made reasonably quickly, and if so, how to deal with the chicken-and-egg problem?

Either Bitcoin has one or more serious vulnerabilities, or it does not.  The problem is that there is no way to know for sure whether or not it does unless/until one is discovered.  So is it best to hide our heads in the sand and hope there is none, or be prepared?

[coinrevo]

The way you phrased certain things I would be prepared against it. Yeah, have your go at the worlds largest supercomputing network. Let me guess: you've programmed an Artificial General Intelligence and asked it how to break SHA256?

[cr1776]

If you look on here you will see many people coming in saying "I have found a flaw, but can't give you details" and it turns out that they didn't understand something, so everyone is very skeptical when someone comes in and won't give out any details.

PM someone with development experience on here with the details - in exacting detail showing where in the code their is a problem, in the math, or in the design.  If it is a vulnerability, you'll hear back quite quickly if you have actually provided enough details and if there is a problem.

The link above shows how quickly the code can be changed if needed, so the answer to the question is, YES.

[chaintest]

The way you phrased certain things I would be prepared against it. Yeah, have your go at the worlds largest supercomputing network. Let me guess: you've programmed an Artificial General Intelligence and asked it how to break SHA256?

As I have said several times, I'm not asking if I have discovered a vulnerability.  I'm asking a what-if question, stating what I have to help give a warning.  In other words, it may not end up being a hypothetical question.  You're welcome to let me know that it is very unlikely that I found something important (like the poor guy who picks up the lottery ticket that has the winning numbers, but doesn't realize that they have to be in the right order).  But since you are evading the questions, it sounds like your vote (and that of empoweoqwj) is that if I did discover a vulnerability, I should take advantage of it and retire, and give no regard as to whether Bitcoin or individuals using it are.  If that's the ultimate answer, I'm OK with that!

[chaintest]

If you look on here you will see many people coming in saying "I have found a flaw, but can't give you details" and it turns out that they didn't understand something, so everyone is very skeptical when someone comes in and won't give out any details.

PM someone with development experience on here with the details - in exacting detail showing where in the code their is a problem, in the math, or in the design.  If it is a vulnerability, you'll hear back quite quickly if you have actually provided enough details and if there is a problem.

The link above shows how quickly the code can be changed if needed, so the answer to the question is, YES.

I am aware that it will take proof to convince people of a flaw, and that I likely have not discovered a flaw worthy of people dealing with.

As for PM'ing -- therein lies the chicken and egg problem.  If there is a serious flaw, what prevents the person from taking advantage of it?  We're not talking about the cash register at the local burger joint being open in an unlocked building at night, we're talking about the safe deposit box at the bank being open in an unlocked building at night -- in a jurisdiction where the penalty for getting caught is that you had to give up what you took.

Let's say that I found that whatever the block header, a nonce of 0x12345678 would generate a hash well exceeding the current difficulty level (of course it isn't really that simple).  Wouldn't it be very tempting for the person I tell to take advantage of that?  Perhaps generate a block an hour for half a day, selling for fiat every hour, and walk off with $250K of cash?

Now perhaps the code could be changed quickly if someone took advantage and started created new blocks once a minute, hoping to raise a quick $40M.  It's decided to go back to the block before they started, and they have no bitcoins (except perhaps the few they were able to sell).  But what if the miner knew that was a possibility, and created a new block say every 4 hours, generating $100K a day.  How would that even be detected?

[toast]

People would notice blocks with "a hash well exceeding the current difficulty level".

Why don't you slowly give more and more information, until you've convinced people you know what you're talking about.
For example, first state the class of bug. Are you saying you found a way to generate hashes far exceeding the current difficulty level?

[chaintest]

People would notice blocks with "a hash well exceeding the current difficulty level".

"a hash well exceeding the current difficulty level" was used to show that the attack could continue.  If I said "a hash just below the current difficulty level," the response is that after a few adjustments to the difficulty, the attack would no longer work.  So let's assume it is near what other people would get.

Why don't you slowly give more and more information, until you've convinced people you know what you're talking about.
For example, first state the class of bug. Are you saying you found a way to generate hashes far exceeding the current difficulty level?

I first have to do testing of my results, which will likely take a few days.  If I still think I'm on to something, I'll see what seems safe to share.

[coinrevo]

If you were serious, you would've double checked before opening a thread. I really wonder how many would pass on that opportunity to print money.

[chaintest]

If you were serious, you would've double checked before opening a thread.

Remember, this was intended to be a hypothetical question.  Either there is or is not a serious flaw in Bitcoin; if there is, wouldn't it be better to discuss how to deal with it now rather than wait for something to happen?

I really wonder how many would pass on that opportunity to print money.

At first I thought if I were to find such a flaw, I could go ahead and mine what I wanted -- and get rich, with money created out of nothing, so nobody would get hurt.  But then I realized, of course, that doing so would have the effect of taking money away from miners who have spent good money on mining hardware.  And if I were to cash out, knowing that the value of BTCs could go down as a result of what I discovered, I would effectively be stealing from the people buying the bitcoins.

Interestingly, everyone seems to be steering me to quietly take advantage of any secrets I may discover (or to spill the beans, that could allow someone else to take advantage of it -- as you said, "I really wonder how many would pass on that opportunity to print money.").

[TierNolan]

At first I thought if I were to find such a flaw, I could go ahead and mine what I wanted -- and get rich, with money created out of nothing, so nobody would get hurt.  But then I realized, of course, that doing so would have the effect of taking money away from miners who have spent good money on mining hardware.  And if I were to cash out, knowing that the value of BTCs could go down as a result of what I discovered, I would effectively be stealing from the people buying the bitcoins.

I don't agree.  If you did find a way to quickly find a valid hash, then you are just as entitled to mine as any other miner.

ASIC manufacturers take business from GPU miners, but there is nothing unethical about that.

Miners (including those with large investments) have no entitlement to block rewards.

Using your knowledge to double spend, reverse transactions or DDOS the network would not be ethical.

In summary, stealing bitcoins is unethical, but the coinbase bitcoins don't belong to anyone other than the miner who solves the hash.

If you don't know if you scheme will work, you could try it out.  If it does involve transferring bitcoins that you don't own to yourself, you could test it on bitcoins that you actually own.

[BurtW]

Pick someone who may know a bit about what you are talking about.  Someone who has been around a while.  Someone you trust.  Then PM them.

Some of the smartest and well known are gmaxwell, DeathAndTaxes, Mike Hearn, theymos, or Gavin himself.  I suggest you run your idea by one or more of them.

(This list is just off the top of my head - did not mean to leave anyone out )

Pretty much anyone with over 2500 posts or 900 activity can probably tell you if you have found something or not.

But pick someone you trust.

[piotr_n]

For now, though, let's just assume I'm clueless newbie or a crackpot, and I'm wrong.

No offence man, but I'm betting my entire bitcoin stash on you being wrong.
So go ahead and say it loud what vulnerability you think you have discovered - don't be shy

But let's assume...
IMHO, if a really critical vulnerability is found, it would rather be in ECDSA, not in SHA256.
I mean, if someone finds a way to solve SHA256 like 10 times faster - this is already accounted for. The difficulty will adjust and it should go on just fine.
But if the signatures are found to be broken, the value of bitcoin will quite likely go down to zero within a single day.
People are saying that if you don't reuse addresses then it should not matter, but I think they are wrong, since being unable to reuse an address would totally break a core function of the currency.
So in such a case there would be no sense to fix it - we can just as well start a new block chain, a new crypto-currency.
And all the coin holders would loose, though the hashing power should still be reusable, so the new currency shall quickly build up a value.

[BurtW]

If something is found then a hard fork can carry all/most/some the current accounts forward on to the new fork (probably, depending on the flaw found).

I say either PM a "super" hero or spit it out right here and now.

[piotr_n]

Right, unless you mean a critical vulnerability in the software, not in the protocol.

Yeah - we've been there. More than once, I think.
A new software is then being released within hours, all the miners switch to it ASAP and the fixed branch catches up to overtake the broken one -  problem solved.
I mean, some people could have lost some money because of double spending, but it would not be a total disaster, just a disturbance.

[flatfly]

Pick someone who may know a bit about what you are talking about.  Someone who has been around a while.  Someone you trust.  Then PM them.

Some of the smartest and well known are gmaxwell, DeathAndTaxes, Mike Hearn, theymos, or Gavin himself.  I suggest you run your idea by one or more of them.

(This list is just off the top of my head - did not mean to leave anyone out )

Pretty much anyone with an activity of over 2500 can probably tell you if you have found something or not.

But pick someone you trust.

Erm... Not even god has 2500+ activity...   Highest is theymos with 1428.

[BurtW]

Pick someone who may know a bit about what you are talking about.  Someone who has been around a while.  Someone you trust.  Then PM them.

Some of the smartest and well known are gmaxwell, DeathAndTaxes, Mike Hearn, theymos, or Gavin himself.  I suggest you run your idea by one or more of them.

(This list is just off the top of my head - did not mean to leave anyone out )

Pretty much anyone with over 2500 posts or 900 activity can probably tell you if you have found something or not.

But pick someone you trust.

Erm... Not even god has 2500+ activity...   Highest is theymos with 1428.

Fixed my original post, I meant posts.  OOPS.

[chaintest]

Just an update for those following:

Indeed, it may be back to the drawing board.

I had first discovered something by looking at the first few blocks that were created.  Rather than tediously going through many variables on many blocks, I wrote code to do it automatically.  That code came up with what appeared to be a statistical anomaly that seemed to confirm my original finding.  Further testing today, however, makes it look like there was a flaw in my logic with the code I wrote.

However, the original anomaly I found is still there, and I need to do some testing with that to see if it is an issue or not.  Since I was only looking at the first few blocks, it could be completely irrelevant at this point.

[cr1776]

Just an update for those following:

Indeed, it may be back to the drawing board.

I had first discovered something by looking at the first few blocks that were created.  Rather than tediously going through many variables on many blocks, I wrote code to do it automatically.  That code came up with what appeared to be a statistical anomaly that seemed to confirm my original finding.  Further testing today, however, makes it look like there was a flaw in my logic with the code I wrote.

However, the original anomaly I found is still there, and I need to do some testing with that to see if it is an issue or not.  Since I was only looking at the first few blocks, it could be completely irrelevant at this point.

Did it have something to do with the probability distribution of the blocks mined by Satoshi which were the first few (among others) of the blocks created?

If so, take a look here:
https://bitcointalk.org/index.php?topic=286883.0

[empoweoqwj]

If you find a flaw, you can get the email addresses of the main bitcoin developers from bitcoin.org

But I don't think that will be necessary

[super3]

We have had plenty of problems in the past, and they have all been fixed rather quickly.
Even if we did have a problem we are talking about a $10B network here.

If something really really broke, I'm sure all the core devs, thousands of coders, and all the Bitcoin companies could get together and probably rewrite Bitcoin from scratch in 24 hours.

[chaintest]

Did it have something to do with the probability distribution of the blocks mined by Satoshi which were the first few (among others) of the blocks created?

Fortunately, I read about that before doing my work.  What we see now in the nonces is the high bits skewing slightly towards 0 (as is expected if you start at zero).

I got thrown off by a pattern that I was seeing, but the same pattern appears in (truly) random numbers as well.  It still doesn't explain my initial results, which I will be testing some more.

[chaintest]

We have had plenty of problems in the past, and they have all been fixed rather quickly.
Even if we did have a problem we are talking about a $10B network here.

If something really really broke, I'm sure all the core devs, thousands of coders, and all the Bitcoin companies could get together and probably rewrite Bitcoin from scratch in 24 hours.

This seems to be the general consensus -- let's sit back and relax, and wait for a problem to come; let's not think about it now.

Put more bluntly, if I am on to something, and chose to take advantage of it -- you might never know.  You'd be sitting back chatting away with people about the $10B network, as I'm slowly lowering the BTC value and siphoning out money.

Of course, your response may be that if it was limited to a flaw that allowed people to mint coins more quickly, it would be fair game.  But I haven't seen any consensus about whether or not such would be ethical (as opposed to double-spending, reversing transactions, etc., that most would agree would not be ethical).  I'm not aware of any contract, rules, etc. regarding Bitcoin -- it's just sort-of assumed that you are supposed to check every possible hash, and shortcuts never were considered.

[coinrevo]

it's just sort-of assumed that you are supposed to check every possible hash, and shortcuts never were considered.

You just don't understand the system. This is exactly what proof of work does. Proof of work can be calibrated such that it is an even game. There is no shortcut - that's basically the definition of proof of work. There is no clever solution, it's all brute force.

There is no possibility of the same class of attacks of traditional software. Traditional vulnerabilities are about getting root access, or changing some strings, so that execution follows a different execution path, or spoofing. All of these really don't apply to bitcoin, as the nodes are run simultaneously. Its a completely new category of system, such as operating systems, databases, viruses, the internet. Most of the normal concepts just don't apply, which is one reason so few people understand it. Bitcoin is a theoretical concept, an opensource project, a network and a currency.

The real question is how to solve the pool problem so that proof of work is forced to be distributed. Unfortunately this is a flaw that seems to be hard to fix.

[prezbo]

it's just sort-of assumed that you are supposed to check every possible hash, and shortcuts never were considered.

You just don't understand the system. This is exactly what proof of work does. Proof of work can be calibrated such that it is an even game. There is no shortcut - that's basically the definition of proof of work. There is no clever solution, it's all brute force.

There's always a possibility of a shortcut unless it's mathematically proven not to exist - which is very rare in the field of cryptology. Having said that, bitcoin is a self-adjusting system and even if such a vulnerability is found in sha256 (unless it's a complete break) it would just adjust itself and no harm would be done.

[BurtW]

Of course, your response may be that if it was limited to a flaw that allowed people to mint coins more quickly, it would be fair game.  But I haven't seen any consensus about whether or not such would be ethical (as opposed to double-spending, reversing transactions, etc., that most would agree would not be ethical).  I'm not aware of any contract, rules, etc. regarding Bitcoin -- it's just sort-of assumed that you are supposed to check every possible hash, and shortcuts never were considered.

All "shortcuts" of this type are totally fair, ethical and expected.  The contract, rules, etc. you are looking for is the Bitcoin protocol.

Back in the old days I had a GPU miner, 5 cards, about 2 GH/s.  I discovered that by doing certain tweeks to my hardware setup I could get 2.4 GH/s out of it.  Were these tweeks unfair?  No.  Anything you can do to get more hashes per second out of your hardware is fair game.  Also, people discovered slightly faster hashing algorithms on a pretty regular basis.  I would download these firmware updates to my system.  Still fair.  Anything you can do to make your hashing algorithm more efficient is fair game.  The mining game boils down to just one thing:  whoever can get the most hashes per joule out of their system (and therefore the most BTC per joule) wins.

It sounds like you think you have found a way to more quickly get to the hash of the proper difficulty.  If that is true then I do not see it as fundamentally different from tweeking the hardware parameters or hashing algorithm.  If by hashing using this new algorithm you get an advantage over the other miners then your hashes/joule will be higher than the rest of the network and you will make more BTC/joule than others.

The system hash rate will go up by the amount of hashing you add to the network, the network will adjust, you will make a boatload of BTC, that is how the system works.

You will be rewarded for being more clever than all the other miners.

Even if your can use half the energy per hash as anyone else what would it matter to Bitcoin?  Of course, you should and would be rewarded for figuring that out.

Now, if you think you can get many orders of magnitude more hashes per joule than the others and by doing so can eventually take over the entire mining network that might becomes a bit sticky.  But I have faith that just by seeing that it is possible to do others would quickly figure out what you are doing and begin hashing in the same way.

What amount of gain/advangate are you talking about here (assuming I am on the right track regarding your discovery)?  0.01%? 0.1%? 1%? 10%? 100%? more?

[BurtW]

Put more bluntly, if I am on to something, and chose to take advantage of it -- you might never know.  You'd be sitting back chatting away with people about the $10B network, as I'm slowly lowering the BTC value and siphoning out money.

This is interesting.  Please explain what you are on about here.  Assuming you are on to something and you end up mining a huge boatload of BTC how on earth does you having a huge boatload of BTC affect the value of BTC?  If you did not mine the BTC someone else would have, right?  There is no difference to me or the rest of the network who ends up mining the BTC, there is still the same number of BTC mined, still the same long term cap of about 21 million coins.  All you would be affecting would be the initial distribution of the mined BTC - to your favor and financial gain.

Again, more power to you!  Go for it!

[super3]

Put more bluntly, if I am on to something, and chose to take advantage of it -- you might never know.  You'd be sitting back chatting away with people about the $10B network, as I'm slowly lowering the BTC value and siphoning out money.

We usually just call that mining.

[smolen]

I am fairly certain that I have found a vulnerability in Bitcoin, just not yet sure yet how serious it is.
Let's say, for example, a miner discovered a way to solve blocks in a minute or two at the current difficulty level, on a standard CPU.

Have you read those threads?
SHA-256 as a boolean function
Potentially faster method for mining on the CPU

[TehoM]

ITT:
Things that are way over my head.
 

[empoweoqwj]

I am fairly certain that I have found a vulnerability in Bitcoin, just not yet sure yet how serious it is.
Let's say, for example, a miner discovered a way to solve blocks in a minute or two at the current difficulty level, on a standard CPU.

Have you read those threads?
SHA-256 as a boolean function
Potentially faster method for mining on the CPU

I'm pretty sure he hasn't

[chaintest]

I'm pretty sure he hasn't

What a brilliantly helpful post!  :)

What amount of gain/advangate are you talking about here (assuming I am on the right track regarding your discovery)?  0.01%? 0.1%? 1%? 10%? 100%? more?

I figure it is safe to go into some more details now.

I am still processing the data; I haven't figured out yet for certain if there is indeed an advantage to be gained, or what it would be.  My hunch is that I am on to something, but that it would not provide enough of an advantage at this point (and like typical hash vulnerabilities, would come a bit at a time, which would be advantageous to Bitcoin, as that would provide the least volatility).  My hunch is that current ASICs would not be able to take advantage of this, but that GPUs would -- so you would need a big advantage for it to be worthwhile.

My concern is that there may be ways to eliminate certain nonces without having to calculate the hash for them.  As a simple (but made up) example, if you knew that the last nibble of the nonce had to be a 0 in order to solve the block, you would only have to check every 16th nonce, cutting your work by over 90% (or multiplying your hash rate by about 10x).  If you knew that the last 2 nibbles had to be 00, your hashrate would increase about 250x (256x minus any calculations you have to perform).  Of course, these are simplistic and unrealistic examples.

As for where I believe the vulnerability lies, it boils down to the hash needed to solve to block, and the leading zero bits.  Right now, the latest successful hash (0000000000000000f7d7b35dbc3d750166fe3b9c45e24a25dbed93fb4a28bf2f) has 256 bits (as all do), with the first 64 bits set to 0.  That's 25% of the bits set to 0, in a row.  Because of that, the hash ends up with about 25% less 1's than average.  Between having less 1's than average, and the order of the 0's, I believe it is possible to predict (given the block header data) whether certain nonces could solve the block.

Adding to this is that we now have a great data source to assist:  over 250,000 80-byte blocks of data, along with their 32-byte "winning" hash.

A typical use of hashes involves using the hash to verify that data has not changed; in this case, an attacker would have to change data in a way that the hash would come out to one specific value (the hash of the original data).  However, with Bitcoin, the attacker (miner) needs to change the data in such a way that any that the hash matches one of massive amounts of potential hashes (somewhere in the order of a septendecillion acceptable hashes -- now there's a word I don't see every day!).  So you've got a much, much better chance of finding a way of altering the data to "win."

One other thing worth mentioning -- like most (I would guess) data, the header block is skewed towards zeroes (I.E. 80 bytes of random data would have 320 0 bits on average; this data normally has more).

In any case, I haven't come up with anything conclusive, and from a purely statistical view (e.g. based on the expected numbers of people who have tried and failed), it is unlikely that I will.  However, my gut still feels that there is something here.

The fix would be to prevent the leading zeroes required in the hash.  For example, requiring that they be set to the first X bits of the Merkle tree would likely do the trick.

[toast]

My concern is that there may be ways to eliminate certain nonces without having to calculate the hash for them.  As a simple (but made up) example, if you knew that the last nibble of the nonce had to be a 0 in order to solve the block, you would only have to check every 16th nonce, cutting your work by over 90% (or multiplying your hash rate by about 10x).  If you knew that the last 2 nibbles had to be 00, your hashrate would increase about 250x (256x minus any calculations you have to perform).  Of course, these are simplistic and unrealistic examples.

A typical use of hashes involves using the hash to verify that data has not changed; in this case, an attacker would have to change data in a way that the hash would come out to one specific value (the hash of the original data).  However, with Bitcoin, the attacker (miner) needs to change the data in such a way that any that the hash matches one of massive amounts of potential hashes (somewhere in the order of a septendecillion acceptable hashes -- now there's a word I don't see every day!).  So you've got a much, much better chance of finding a way of altering the data to "win."

Do you understand the concept of "cryptographic hash"?

The closest possible viable solution that sounds even remotely like what you're talking about is in the two links given by this guy:

I am fairly certain that I have found a vulnerability in Bitcoin, just not yet sure yet how serious it is.
Let's say, for example, a miner discovered a way to solve blocks in a minute or two at the current difficulty level, on a standard CPU.

Have you read those threads?
SHA-256 as a boolean function
Potentially faster method for mining on the CPU

Question, have you read those two threads, and do you understand how they relate to what you're talking about?

[smolen]

My concern is that there may be ways to eliminate certain nonces without having to calculate the hash for them.  As a simple (but made up) example, if you knew that the last nibble of the nonce had to be a 0 in order to solve the block, you would only have to check every 16th nonce, cutting your work by over 90% (or multiplying your hash rate by about 10x).  If you knew that the last 2 nibbles had to be 00, your hashrate would increase about 250x (256x minus any calculations you have to perform).  Of course, these are simplistic and unrealistic examples.

As for where I believe the vulnerability lies, it boils down to the hash needed to solve to block, and the leading zero bits.  Right now, the latest successful hash (0000000000000000f7d7b35dbc3d750166fe3b9c45e24a25dbed93fb4a28bf2f) has 256 bits (as all do), with the first 64 bits set to 0.  That's 25% of the bits set to 0, in a row.  Because of that, the hash ends up with about 25% less 1's than average.  Between having less 1's than average, and the order of the 0's, I believe it is possible to predict (given the block header data) whether certain nonces could solve the block.

I believe that double SHA-256 is and for a long time will be immune to such kind of attacks, but blake hash as used in Blakecoin may be vulnerable to 'statistical mining'.

[chaintest]

Do you understand the concept of "cryptographic hash"?

Yes.  One of the design features is that given a hash, it is extremely difficult to create data that would generate that hash.  But we have septendecillions of hashes to pick from, exponentially increasing our chances of getting one that works (either via brute force, or otherwise).

Question, have you read those two threads, and do you understand how they relate to what you're talking about?

AFACT (can tell), both of those threads refer to possible shortcuts to the SHA256 hashing algorithm (in other words, testing the same number of nonces, just doing so faster).

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

So:

Case #1 [normal]:  You go through 2^32 nonces, calculate the hash for each, ending if you get a successful hash.
Case #2 [those 2 threads]:  You go through 2^32 nonces, calculate the hash for each using a faster method, ending if you get a successful hash.
Case #3 [my post]:  You go through perhaps 2^24 nonces, calculate the hash for each using a faster method, ending if you get a successful hash.

#2 and #3 both have the potential to be faster than what is traditionally used, but go about doing so in very different ways.  Case #3 treats the SHA256 algorithm as a black box, not caring what the algorithm does.  Case #2 looks at how the SHA256 algorithm works and tries to find ways to duplicate it faster.

[smolen]

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

Yes, that makes sense. No, Satoshi already took care about it. Guess why single SHA-256 is not enough for Bitcoin?

[eatingthenight]

From what I have read so far I don't see how this can have an effect on the network. This may make it possible for GPU's to mine much faster but even a 10x increase does not make them anywhere close to profitable.   I assume they would also shortly implement this for asics as well although it would take a bit more work. Pretty even if this would actual work all that would happen is the old 5GH would now be 50GH but doing the exact same thing. The network difficulty would adjust accordingly and it would be like nothing ever happened assuming that you could actually statistically filter out nonces.

[chaintest]

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

Yes, that makes sense. No, Satoshi already took care about it. Guess why single SHA-256 is not enough for Bitcoin?

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Do a double hash of this poor hashing algorithm, and you aren't any better off than just hashing once.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.  So binary 10011 becomes 01100.  If you double *that* really poor hashing algorithm, the results are even worse:  you get the original data!

So a double-hash with SHA256 will *presumably* increase security, but has anyone gone through and tried to prove that it actually does?

From my perspective, I do not consider what hashing algorithm is used, or what variations there may be.  You could do SHA256(MD5(CRC32(SHA256()))), and I would approach it the same way.  Now if it can be mathematically proven that the variation of the algorithm (in this case, doing it twice) makes it much harder to crack, then it would not make sense for me to continue looking into this.  But without such proof, believing that the variation is definitely better is dangerous (as proven above, where doubling other algorithms can generate no improvement, or make it easier to crack).

[chaintest]

From what I have read so far I don't see how this can have an effect on the network. This may make it possible for GPU's to mine much faster but even a 10x increase does not make them anywhere close to profitable.   I assume they would also shortly implement this for asics as well although it would take a bit more work. Pretty even if this would actual work all that would happen is the old 5GH would now be 50GH but doing the exact same thing. The network difficulty would adjust accordingly and it would be like nothing ever happened assuming that you could actually statistically filter out nonces.

Exactly.  At a 10x increase that would require new ASICs (or using existing CPUs/GPUs), the existing network should be able to handle it (a slight increase in hashrate very quickly, but staggered a bit; followed by a much larger increase as new ASICs came online).  It would upset those that paid for ASICs, but that's one of the risks.

At a 100x increase or 1000x increase, however, the picture would change.  If that were to occur, the cost per GH/s for GPUs might become much, much lower than current ASICs.  Dust off all those old GPUs and get them working within a couple of weeks, and it could strain the network.  Add a 100x to 1000x increase to ASICs within months to a year, and it could spell trouble.

And there could be new bottlenecks that appear.  The nonce is only 32 bits; it takes just 4GH/s to go through those in one second, at which point a new block header needs to be created.  For a 400GH/s ASIC, that's a new block header every 1/100 second.  At 1,000x increase, you're dealing with a new block header every 1/100,000 second, which could introduce new bottlenecks (e.g. calculating the Merkle tree).  Of course, such bottlenecks would reduce the stress on the system, which would be good.

But would about a 1,000,000x increase?  That would be a game changer.  If that was discovered and exploited to its full potential immediately, you've got a problem:  you could hit a new difficulty level very quickly, which would slow down the person discovering this to generating new blocks every 10 minutes or so, and giving everyone else nearly no chance of solving a block.  If the super-miner quits when the difficulty changes (after having made $50M or so of BTC), it could be days or longer before a single new block is solved.  And then you're dealing with blocks too big to be accepted, requiring a patch to allow Bitcoin to survive.  And what about the difficulty?  You could lower it with a patch, but then if the super-miner comes back online, it jumps again.

So at 10x, little concern.  1,000,000x, potential disaster.

[toast]

Yes.  One of the design features is that given a hash, it is extremely difficult to create data that would generate that hash.

And furthermore, there is total information loss. Any distribution you know over outputs does not help you determine distribution over inputs. All you've said is, "if we know the distribution over outputs, we could maybe turn that into knowledge about distribution over inputs".  You are saying SHA256 is an ineffective cryptographic hashing function. The DoD will make you very rich if you can show that this is the case.

AFACT (can tell), both of those threads refer to possible shortcuts to the SHA256 hashing algorithm (in other words, testing the same number of nonces, just doing so faster).

Yes, the shortcut involves trying to use knowledge about distribution of outputs to solve the problem faster. That's why it's relevant. But they aren't using techniques that rely on statistical analysis that SHA256 was designed to resist.

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.

Neither of those are cryptographic hashing algorithms. Do you see why?

[toast]

Actually nevermind, don't let naysayers like me slow you down. Your turing award awaits.

PM me if you find something and I'll help you get rich.

[chaintest]

Let's say the hashing algorithm is this:  Add up all the data bytes, take the lowest 8 bits (0 through 255), and multiply by 256.  In this case, the hash is 16 bits, with the lower 8 bits always zero.

Worse, take a hashing algorithm that takes each bit of the data and xor's it with 1.

Neither of those are cryptographic hashing algorithms. Do you see why?

They are cryptographic hashing algorithms, just extremely poor ones, I stated, to get the point across.

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

[BurtW]

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

SHA 256, twice for good measure.

Advanced cryptographic hashing functions are designed so that if you change one single bit in the input a majority of the bits are changed in the output.  They are designed this way on purpose so that the attack you are proposing does not work.

[chaintest]

I encourage you to provide an example with a more advanced cryptographic hashing algorithm.

SHA 256

Sorry, that's "example with", not "example of."  Yes, SHA256 is infinitely more advanced than my simple examples, but SHA256 has not been proven to be equally or less secure when performed twice.  My examples were showing that performing hashing algorithms twice does not always increase security, in some cases providing equal or less security.

toast was saying that my examples were not good because they were not advanced cryptographic hashing algorithms, and I was encouraging him (or others) to provide an example with an advanced cryptographic hashing algorithm.  But in most cases, simplistic examples are better, as they are easier to understand, and get the point across with less work.

[smolen]

And furthermore, there is total information loss.

AFACT (can tell), both of those threads refer to possible shortcuts to the SHA256 hashing algorithm (in other words, testing the same number of nonces, just doing so faster).

Yes, the shortcut involves trying to use knowledge about distribution of outputs to solve the problem faster. That's why it's relevant. But they aren't using techniques that rely on statistical analysis that SHA256 was designed to resist.

The information is not lost momentarily, it's slow dissipates with each hash round, were it pass from down to top or in reverse. Those two threads describe two different approaches to morph the structure of hash function. I think that single SHA-256 is small enough to be vulnerable to statistical analysis after such liposuction, but (I'm pretty sure killerstorm gave exact numbers, cannot find it now) double SHA-256 is big enough to be safe.

[smolen]

SHA256 has not been proven to be equally or less secure when performed twice

Well, it's not a proof, but for sake of discussion... Let's imagine that I have a magic way to restore preimage from SHA-256 (or any other) hash. By applying this magic twice I can restore preimage of double hash. Were I in possession of magic method of reversing double hash, I could reverse single hash by reversing double one and then re-applying single hash if such preimage exists. So breaking single hash leads to breaking double one, but not vice verse.

[toast]

Well you're right in the sense that it is possible to prove that a hash is not cryptographic but so far not yet possible to prove that a hash is cryptographic (P vs NP and all). We rely on the crypto community to keep us up-to-date on potential attacks. If you're interested in pursuing this, great! Cryptanalysis is an exciting field. I found a paper that might be helpful as a starting point.

http://www.femto-second.com/papers/SHA256LimitedStatisticalAnalysis.pdf

Again, realize all you are saying is "I know double SHA256 is supposed to be a strong cryptographic hash and most prominent cryptographers seem to think so, but what if it's not?"

I suppose the next step is to run some statistical analysis!

[chaintest]

... If you're interested in pursuing this, great! Cryptanalysis is an exciting field. I found a paper that might be helpful as a starting point.

http://www.femto-second.com/papers/SHA256LimitedStatisticalAnalysis.pdf

Thanks for the link; glancing at it, it appears to be similar to what I am doing.  I'll need to read that one thoroughly.

Again, realize all you are saying is "I know double SHA256 is supposed to be a strong cryptographic hash and most prominent cryptographers seem to think so, but what if it's not?"

Remember, Bitcoin does something different than most.  It is possible for a cryptographic hash function to meet the criteria of a cryptographic hash function (going by the Wikipedia definition), while having vulnerabilities as used by Bitcoin.  Specifically, checking a single nonce to see if it is successful (has enough leading zeroes) has the same effect as testing septendecillions of variations to a message against its original hash.

So if using current computing power it would take 1,000,000 years to create an altered message with the same hash as the original, it could take less than a second to alter a message and get a hash that Bitcoin considers successful.  Such a hashing algorithm would like be considered highly secure for most purposes, just not Bitcoin.

In other words, all those prominent cryptographers think that SHA256 is very strong, but that does not mean that they think that it is strong as used by Bitcoin.

[empoweoqwj]

I'm talking about determining that a nonce has little chance of producing a successful hash, and therefore not needing to make the calculation at all.

Yes, that makes sense. No, Satoshi already took care about it. Guess why single SHA-256 is not enough for Bitcoin?

I wouldn't bother pointing out facts to him. He seems determined to carry on regardless ..... until he realizes he hasnt found a vulnerability

[gmaxwell]

Many people have spent large amounts of time looking at far more mining data than you have available. (e.g. hundreds of gigabytes of shares) and have not found anything terribly useful.

Because the distribution of input data is not believed to matter miners do all sorts of things which bias their inputs e.g. increment starting at zero or only sweep part of the nonce range, etc. which can serve to create apparent after the fact biases which aren't real and can be hard to sort out.

The fact early termination winnowing would be useful if available isn't lost on anyone— its an oft cited reason why $otherfunction wouldn't make a good POW. (E.g. you can rapidly tell trivial 3sat problems from potentially hard ones, so you grind the problem generator and then use a fast solver for trivial problems). Many (most?) miners make use of the fact that you can terminate sha256 a couple rounds early with the h==0 constraint.

If you've found something that lets you mine faster— congrats. I look forward to hearing about your major mining income or reading your paper.

Good luck.