Could code be changed quickly if vulnerability found?

[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?