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.


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.

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.

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.

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.

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

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


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.

What a brilliantly helpful post!  :)


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.

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.

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.

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.

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?


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

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


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.

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?

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!

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?

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.


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.

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.

Hello everyone.

I started looking into Bitcoin a couple days ago after talking with someone about it.  I cannot remember why he mentioned it.  I had heard about it over the years, looked into a bit a year or so ago, but never even installed the software.  I figured I would look into it to see if it was worth having mining software running on my computer (hah! I'm a bit late for that!).

Now, I'm going through with the eyes of a developer, as if I were going to right a Bitcoin software.  I've started with the genesis block, calculating the hash for it, and in general seeing how everything works.

I'm working on a post for tomorrow, but thought a brief intro would be in order first.