Guy on twitter claims he is working on hash method without brute force.

[Gareth Nelson]

If you complain about how ED is written it probably isn't for you 

Some stuff on there is mildly amusing, sometimes even in a self-depreciating way, but generally it's just nasty for the sake of being nasty.

I'm only going to suggest that you know what you're talking about before opening your mouth on the Internet, or people who DO know what they're talking about will call you out.

Is that in reference to ED or the original subject of this thread?
I'll publically say it now - my approach to this is not feasible.

As for ED - each to their own I suppose.

[TiagoTiago]

If you really know what you're talking about you don't need to build it, you can describe the process in details and others can check if it makes sense.

[DeathAndTaxes]

People on this thread are forgetting something very important - in bitcoin, we map a block hash to a nonce. This MASSIVELY reduces the search space, otherwise miners would not be feasible at all. My (now abandoned) work was about further reducing the search space by removing binary branches (i.e each bit of the nonce splits it into a new branch) that will never result in a valid hash as output. Each time you do this you divide the time taken to mine a valid block by 2. That's the theory anyway.

No it doesn't.

The nonce + rest of header combined is the message.  There is no binary relationship between nonce and the output hash.  If there was then you just broke SHA-256, something the best cryptographic minds in the world haven't even gotten close to.

You can't simply say "all nonces that start with 0 are bad and ones with 1 are possible good.  So looking at 2nd digit, 1 is bad, and 0 is possibly good".

Even if you could the nonce is only 2^32.  There is a very small chance that ANY of the nonce values are valid.  If none of them are valid (and 99.99999999999999999999% of the none are) then you need to change the extra-nonce.  Once you do that then the nonce tree you constructed is no longer vald.

My (now abandoned) work was about further reducing the search space by removing binary branches (i.e each bit of the nonce splits it into a new branch) that will never result in a valid hash as output.

This line specifically shows a complete lack of understanding about how cryptographic hashes work.  Given an input (no matter how simple or complex) it is impossible to predict what the output of the hash will be when you change one bit.  There is no method to construct a binary tree by checking each bit and building a relationship between input and output.

 That is the entire point of cryptographic hashes.  If you could then not only would bitcoin & SHA-256 be completely broken but the entire concept of one-way hashes would be broken also.  

I mean lets apply this to other uses of hashing functions.  Take a website with password lists hashed using SHA-256.  I make an account with a known password and then steal the password list.  If I can using a known input (my password) and known output (my password hash) form a relationship between the sets of inputs (currently unknown passwords) and outputs (stolen password hashes) then I could instantly (or very fast using a binary tree) decrypt all the passwords. It would be the largest breakthrough (or breakdown) in cryptography in ... well ever.   We are talking about massive social upheaval, everything from bank passwords to nuclear launch codes at risk and likely would get you the Nobel Prize in mathematics (if the world survived).

When I started to get into the details and try to build the thing I discovered that although theoretically possible it'd take so much resources it's not worth it.

The post the theoretical proof.  If is is possible just not economical that is one thing but so far your posts & tweets have been a random jumble of crypto "buzz words" that mean nothing.  I am convinced using cryptoanalysis miners could be improved but your "theory" isn't even a theory it is pure nonsense.

[Forp]

This line specifically shows a complete lack of understanding about how cryptographic hashes work.  

This line specifically shows a complete lack of understanding about how human motivation works. 

That said, from a crypto point of view, I am also highly sceptical that the approach taken by the OP will work out. Hash functions are constructions whose many task is to make the suggested approach fail. To the contrary: I am happy to bet quite some BTC that this attempt will fail.

However, we are here (on this forum) to learn and to improve and generally move ahead with Bitcoin. So I am happy about every attack on Bitcoin, every suggestion on improval and every step to move ahead with our common interest. Phrases like "shows a complete lack of" or "is nonsense" isn't exactly what motivates people. And: So long as there are still so many ecosystem elements missing in Bitcoin, so long as there are still so many problems with the client, so long as we have no formal specification, an RFC, and and ... and so long as my favorite online shop does not accept Bitcoin - we still need more people in the field. Not everyone is a Satoshi and even he had a time of learning, trial and error.

Thank you for listening.

[Raize]

Relevant:
http://en.wikipedia.org/wiki/Preimage_attack

[bcforum]

For those of you keeping track, the following nonces are UBER SPECIAL:

Code:

04111a63
a7900e03
bb971f16

Can you guess why?

[dentldir]

For those of you keeping track, the following nonces are UBER SPECIAL:

Code:

04111a63
a7900e03
bb971f16

Can you guess why?

No need to guess.  They are nonces that have generated more than a single solved block.

Not sure that makes them uber special though.

[Forp]

No need to guess.  They are nonces that have generated more than a single solved block.

If I am not completely mistaken, the probability of having such nonces given the current length of the blockchain and the breadth of SHA-256 is...for all realistic purposes zero.

Well, not really. I forgot the target. And the difficulty adjustment over time. And that there was a very low difficulty at the beginning.

It would be interesting to know the probability of such a thing to happen. I assume this happened in very early blocks? Anyone having the block numbers at hand? (My own block explorer version does not yet support searching on nonces)

[DeathAndTaxes]

Nonce is 2^32 number.  The probability of any nonce being used twice is thus exactly 1 in 2^32 and doesn't change regardlesss of difficulty.

[Forp]

The probability of any nonce being used twice is thus exactly 1 in 2^32 and doesn't change regardlesss of difficulty.

Is this really so easy?

The nonce is a criterion for meeting the target. For a low difficulty we have a different target than for a high difficulty. If difficulty is sufficiently high, chances are high that there is NO nonce at all in the range of 1 to 2^32 which meets the target (for this case there are numerous mechanisms in the Bitcoin implementation which deal with nonce overrun and others which ensure that eventually a (different) block will be found). If difficulty is very low, chances are that in said range there are several nonces which meet the target.

On the other hand, difficulty currently is so high that we see nonce overrun extremely often, so we might as well understand mining as process which (after overruns and all kinds of stuff which we are not interested in currently) comes up with an arbitrary nonce value in 0 to 2^32-1. So we might as well model it like that. Looks like right now, with high difficulty, your assumption is a good model.

And, I think, my statistical guts feeling fell victim of the birthday paradox. If we assume, as in above paragraph, that finding a nonce is an equally distributed selection process in 32 bit space, then having identical nonces in 140.000 blocks is the same as having a hash collision with a 32 bit hash function and 140.000 attempts. According to  http://en.wikipedia.org/wiki/Birthday_attack with 110.000 attempts chances are 75% to have at least one collision in this situation. So, actually, it is quite reasonable at block 140.000 to have a small, one digit number of such blocks.

Doubt dissmissed. Happy again. 





 

[DeathAndTaxes]

Your right I forgot about effect of Birthday paradox.

One thing I would correct is nonce is ALWAYS a range of 2^32.  Even w/ difficulty of 1 the nonce range is 2^32 and each hash has an equal chance of hitting the target. 

Difficulty of 1 = odds of hash being below target are 1 in (2^32)(1).  On average there is 1 valid hash per 1 nonce ranges.
Difficulty of 1689334.4045971 = odds of hash being below target are 1 in (2^32)(1689334.4045971). On average there is 1 valid hash per 1689334.4045971 nonce ranges.

[bcforum]

During the era of CPU mining is wasn't unusual for miners to search only the lower part of the nonce range. since a full 2^32 search would take too much time. I haven't analyzed the data yet, but I suspect there are more low nonces than high ones.

Code:

$ cat nonce.lst  | grep "^0" | wc
  47080   94160  753333
$ cat nonce.lst  | grep "^1" | wc
  12470   24940  201587
$ cat nonce.lst  | grep "^2" | wc
   7442   14884  121209
$ cat nonce.lst  | grep "^3" | wc
   6314   12628  103299
$ cat nonce.lst  | grep "^4" | wc
   6106   12212   99962
$ cat nonce.lst  | grep "^5" | wc
   6127   12254  100398
$ cat nonce.lst  | grep "^6" | wc
   6086   12172   99695
$ cat nonce.lst  | grep "^7" | wc
   6077   12154   99477
$ cat nonce.lst  | grep "^8" | wc
   5895   11790   96551
$ cat nonce.lst  | grep "^9" | wc
   5908   11816   96690
$ cat nonce.lst  | grep "^a" | wc
   5833   11666   95570
$ cat nonce.lst  | grep "^b" | wc
   5899   11798   96666
$ cat nonce.lst  | grep "^c" | wc
   5994   11988   98234
$ cat nonce.lst  | grep "^d" | wc
   5898   11796   96569
$ cat nonce.lst  | grep "^e" | wc
   5872   11744   96231
$ cat nonce.lst  | grep "^f" | wc
   5815   11630   95291

For those of you that don't speak Unix, the above data shows I'm correct.

[sd]

During the era of CPU mining is wasn't unusual for miners to search only the lower part of the nonce range. since a full 2^32 search would take too much time. I haven't analyzed the data yet, but I suspect there are more low nonces than high ones.

Isn't that just another example of Benford's Law?

http://en.wikipedia.org/wiki/Benford%27s_law

[stillfire]

Seems to me that the most natural way to write a mining program is to start at nonce 0 and go up. If there were two passing nonces for a particularly easy target, one high and one low, you'd get the low one.

[Forp]

Seems to me that the most natural way to write a mining program is to start at nonce 0 and go up.

Your statement exactly is the reason I would not do this as you suggested. 

Maybe you know this multi-joke:

A guy plays lotto, the one where you have to guess 6 numbers out of 1 - 45. And every week he picks the numbers 1, 2, 3, 4, 5, 6. After a month the lotto vending guy tells him: "Why don't you pick different numbers. 1, 2, 3, 4, 5, 6 - this is such an odd combination. It is really very improbable that exactly this combination is selected. I have been selling lotto tickets now for years and years - and such a combination, I can tell you, will never be coming".

If you are a mathematician, this is the first moment of laughter. 

So, the player replies: "Well, I am a mathematician, and I can prove that 1, 2, 3, 4, 5, 6 is as probable as is 3, 19, 23, 34, 38, 41.

So, the guy continues playing, and, after several years, indeed the numbers 1, 2, 3, 4, 5, 6 are selected. The guy goes to the shop to pick up his money but is very disappointed when he learns that he has to share the prize with 500 other mathematicians who also played 1, 2, 3, 4, 5, 6.

In the multi-joke, this is the second moment of laughter. 

So, that's why I would do it differently 

Ok. Ok. My remark is not supposed to be taken dead seriously. 

[DeathAndTaxes]

Nice jokes (I did laugh) but there are no ties in bitcoin blocks.

Even though each miner (or pool) starts at nonce 0 they are using different headers thus won't have the same nonce produce a winning block.  I miner which started at last nonce and worked downward wouldn't have any advantage.

Still it does explain why lower nonces occur more frequently ... they are tested more often.   That effect was more pronounced in the early days when it only took a single pass or few passes though nonce range to find a valid hash.  Today it takes on average 1.5 million trips through the nonce range to find a target hash thus I would imagine if you drew a histogram of valid nonces it would be less distorted for recent (say last 10K or so) blocks.

[Forp]

Even though each miner (or pool) starts at nonce 0 they are using different headers thus won't have the same nonce produce a winning block.  I miner which started at last nonce and worked downward wouldn't have any advantage.

Yeah. That's why I added "do not take that dead serious" or so at the end of my post.

And, still, it remains an interesting exercise... Assuming all blocks were identical (which they are not) and assuming the system were strictly synchroneous: The guy with the fastest CPU would always make the block, if all would mine from 0 upwards. In this (admittedly fictious and for Bitcoin completely unrealistic) scenario, the joke would really make sense.

We cannot think of such aspects often enough, because it is the very detail which, when overlooked, could produce interesting  effects. For example, I was highly sceptical of the anonymity of bitcoin until I checked in the reference code, that the address where you get your change back, really is placed into position 1 or 2 at random... 

[DeathAndTaxes]

And, still, it remains an interesting exercise... Assuming all blocks were identical (which they are not) and assuming the system were strictly synchroneous: The guy with the fastest CPU would always make the block, if all would mine from 0 upwards. In this (admittedly fictious and for Bitcoin completely unrealistic) scenario, the joke would really make sense.

I think Satoshi actually used that exact scenario in his paper and also provided the solution (each miner/pool has a different coinbase transaction thus different hash of the block thus will need a difference nonce to find a hash below the target).

We cannot think of such aspects often enough, because it is the very detail which, when overlooked, could produce interesting  effects. For example, I was highly sceptical of the anonymity of bitcoin until I checked in the reference code, that the address where you get your change back, really is placed into position 1 or 2 at random... 

It is kinda amazing how many thing bitcoin got right "on the first try".  Maybe it was just luck.

[ctoon6]

It is kinda amazing how many thing bitcoin got right "on the first try".  Maybe it was just luck.

yep, and its amazing how there are still so many things that break the system. the biggest being the unsustainable blockchain size. aside from that its pretty good