Bitcoin Forum

"So i've been working on a method for calculating valid hashes without doing a lame bruteforce"
"If my method works, i'll be able to generate 50BTC every few seconds but i'll lower it a bit to avoid arousing suspicion"

Ummm, satoshi?

http://twitter.com/#!/garethnelson

garethnelson Gareth Nelson
@
@lemonzest2008 my new approach is going to take lots of fucking about with the maths before I write the actual miner itself
4 minutes ago

garethnelson Gareth Nelson
@
@lemonzest2008 the one on the AFF site is just a mod of a standard miner - there's source available at aspiesforfreedom.com/mining/src
4 minutes ago

garethnelson Gareth Nelson
@
@lemonzest2008 nowhere near complete yet, unless you mean the boring standard one on the AFF site
5 minutes ago


garethnelson Gareth Nelson
@
@lemonzest2008 the bitcoin client? run bitcoind, but note it's a bit slow at generating if that's what you're after
12 minutes ago

garethnelson Gareth Nelson
@
@ZauberExonar great - how's your digital circuit design? in particular, boolean expression simplification for FPGAs
14 minutes ago

garethnelson Gareth Nelson
@
@LozKaye who on earth asked for that?
14 minutes ago

garethnelson Gareth Nelson
If I generate one block a day, at current exchange rates that'd be $11200USD/month - anyone want to help out for a cut?
21 minutes ago

garethnelson Gareth Nelson
@
@FabinetPM you don't know? :O
22 minutes ago

garethnelson Gareth Nelson
I then don't even have to bruteforce - just pick any of the remaining branches at random, then "..." and then "profit" #bitcoin #win
24 minutes ago

garethnelson Gareth Nelson
I eliminate the branches that lead to bits outside of the nonce changing in the input, then i'm left with a fixed set of branches
25 minutes ago
»

garethnelson Gareth Nelson
For NOT gates for example, it's easy - if you want a 0 out, you put a 1 in - for an XOR there's 2 possible inputs that lead to a 1
26 minutes ago

garethnelson Gareth Nelson
Then I can calculate the fixed inputs for each gate that will satisfy the output such that it's got the right number of 0s
27 minutes ago

garethnelson Gareth Nelson
The output is a wildcard prefix and a bunch of 0s at fixed length - I run backwards from the wildcard bits up through the boolean network
27 minutes ago

garethnelson Gareth Nelson
Doing the maths, a circuit with about 6000 logic gates can do SHA256, and 2000 odd of them are OR gates with multiple possible inputs
29 minutes ago

garethnelson Gareth Nelson
If my method works, i'll be able to generate 50BTC every few seconds but i'll lower it a bit to avoid arousing suspicion #bitcoin
30 minutes ago

garethnelson Gareth Nelson
So i've been working on a method for calculating valid hashes without doing a lame bruteforce

If he succeeds, bitcoin compromization will be the least of our worries.  SHA256 has stood up to mathematical analysis for many years, not just from the bitcoin community but from the entire world.

bitcoinfail.  Oh well, I guess I'll just start playing Crysis 2 now.

^this. Good luck to the guy. Many have tried - and there's so much other security infrastructure that uses SHA256 that we Bitcoin is the least of our worries. Besides, bitcoin'd just move to some other hashing algorithm.

Looking at how he "thinks" his solution will work, He doesn't understand the concept of destructive operations.  Think of it this way: The simplest hash function is %2.  Basically, given any input, find the remainder after you divide by 2.  It simplifies things down to a keyspace of 1 bit, and obviously there's lots of collisions.  However, given that information, there's no way to go backwards to the original number.  If I say the "hash" is 1, it could be 1, 3, 5, 7, 9, etc.

SHA256 has the following destructive operations:
6x non-carrying addition
Shift right
I believe the combination of ANDs and XORs ends up being destructive.

That's just in one iteration, and there are 64 iterations per hash.

+1 on what Quantumplation said.

Ultimately, it looks like he's some young hotshot who thinks he understands everything, considers himself a "hacker", and thinks he can best the worlds top mathematicians because he's 2 years into an associates degree at a shitty college.  I am dissapoint.

For what it's worth I talked to one of the authors behind the current best result against SHA256. They didn't think a failure of SHA256 as it's used in Bitcoin was likely any time soon. The best results from academia produce a random bitstring as the pre-image and only work against a reduced strength version of the algorithm.

I thought he was designing a miner.  Why would he need a pre-image for that?  All he needs is a partial collision with zero.

Oh, wait, so is it safe to go back to mining?

Er... No... bitcoin is dead, but i'll buy all your bitcoins for $1 each.

We was lazy disscussed that approuch to breack down the BTC prices (to buy them cheap) on russian local, month ago, and come to conclusion, that there is always be some nerd with numbers in hand, that will destroy that idea, - therefore we refuse it.

proof - http://forum.bitcoin.org/index.php?topic=4128.0

The input is a block header, the contents of which are not flexible. Only the nonce is.

Ah, of course.

If I'm not mistaken, most effort has gone into "single" SHA256, and though the composition of SHA256 operations would seem harder to crack, one never knows.

Not that I think the Twitter guy is likely to succeed, but in general I see too little attention placed on the strength of Bitcoin's cryptography and too many explanations that fail to mention its theoretical vulnerability.  Or citations in support of its strength, for that matter.

http://en.wikipedia.org/wiki/SHA-2#Cryptanalysis_and_validation

SHA256 isn't JUST used in bitcoin.  It's used in SSL, in banks all over the world, wireless encryption, cellphone encryption, encryption/verification for thousands of open source projects, etc.  If you need a citation for it's strength, it's been used for 10 years in all these fields without any likely attack vector found.

I'm aware, thank you for spreading the word.

ROT-13 is harder to crack than ROT-13(ROT-13).  Has anyone proven the same is not true of SHA256?  I will be very surprised...

relatively little research has been done on the subproblem of sha256 compromise on which bitcoin's security depends. it is not the same problem as one-to-one collisions (i.e., an outright compromise of the function). in the general case, it cannot be determined whether finding a result that corresponds to a pattern that matches x out of 2^256 hashes is indeed no more than x times easier than forcing a one-to-one collision. there are reasons to think that in bitcoin's particular case, it is just about that easy and thus that bitcoin's use of sha256 in mining is secure - but to my knowledge that hasn't been proven.

update for john: for technical reasons, i'm less concerned about that feature of bitcoin's use of sha256. the problem isn't necessarily the same for cyphers as for hashes. as for the former, as potentially interesting background reading (though not necessarily relevant here), see the excellent classic article by maurer called something like 'the importance of being first' in the journal of cryptology.

ROT-13 is nondestructive.  Very different from SHA-256.

I had this idea about not removing brute-forcing but optimizing the algorithm since not all output bits are needed, so we backtrack and remove all superfluous calculations. But if its 64 rounds per hash and two hashes, I think the gain would be extremely small. And also maybe this optimization has already been done?

I would be surprised if there were no results showing how to mine faster.  The statement that the current algorithm is the fastest one of all possible is rather strong.

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.

BitRapture.

Yes, I asked Yu Sasaki specifically about the problem of finding a partial pre-image rather than a full pre-image. She didn't seem to think it would make things any easier. I don't think we can do better than this for now. If there's a weakness in (double) SHA256 that would make it easier to solve the problem Bitcoin uses I guess there will be an academic paper on it eventually.

Is it right that it won't be a problem if it becomes a thousand or a million times easier to solve? People will just switch to the better algo and difficulty will increase like when we moved to GPUs.

As soon as it can be done, and everybody knows it can be done, and everybody want to do that, some other people will also find a way to do that and if it becomes open source (just like the gpu miner) - everybody will be doing that and the network hash rate will just supercharge as it did when graphics card mining were introduce - and the system will balance itself around the new competition factor - even securing the system even more against an attacker not using such a hash algorithm (if it exists!!!  :D)

That's what I thought, so SHA256 needs to completely break to be a problem for Bitcoin?

Yeah, because hacking billions from banks and pretty much every website using SHA256 wasn't enough incentive, clearly it takes bitcoin to get SHA256 attacking investigated  ::)

i'm curious what you think you could do to most 'banks' with a compromise of sha-2. more readily mount a phishing attack by spoofing an ssl certificate? sneak into their datacenter, figure out how they handle internal integrity checks, and then spoof those checks after injecting your own data?

SHA256 allows an attacker to create a hash that corresponds to [your message w/padding] + [his own message] without having to know what [your message] was. This could be a serious vulnerability for some (incorrect) applications of SHA256. Double hashing prevents this attack.

Really?  I thought that was only on SHA1 or MD5...

Also for SHA256, see the algorithm:
https://secure.wikimedia.org/wikipedia/en/wiki/SHA-2#SHA-256_.28a_SHA-2_variant.29_pseudocode

a-h represent the hasher state, and they're all concatenated to form the hash. So someone with the hash can continue the hashing with his own data. One of the requirements for the recent NIST competition was AFAIK that this was not possible (hasher has hidden state).

In the case of bitcoin this is not a problem though. This doesn't simplify finding a hash value within a certain range.

Indeed, he wouldn't exactly be the first guy making a bold claim on the internet.

Well this is embarrassing...........

I didn't vanish ;)

Long story short is this: I looked at how much hardware this would take to precalculate the branches and found it'd be cheaper to just buy BTC or mine the old-fashioned way.

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.

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.

I can imagine it is possible to use known cryptoanalysis of sha-2 to write software which is 50-90% more efficient of what we have now, though I doubt it.

From the time I put into this thing, it's possible - definitely possible - but you're better off using traditional methods because of the resources needed either in pregeneration using my approach or in development time.

So, we have a guy claiming to revolutionize the whole thing

+

aspiesforfreedom

aspie...


=

Yeeeaahhh sure....  ::) should i link the aspie article on encyclopedia dramatica?

The more relevant tweets that were missed off from the first post:
http://twitter.com/#!/garethnelson/status/75236526593810432
http://twitter.com/#!/garethnelson/status/75236664062132224
http://twitter.com/#!/garethnelson/status/75236789480210432

As for Gabi's comments, well - i'm just going to ignore the nastiness as ED is known for having nothing nice to say on any subject.
Example - http://encyclopediadramatica.ch/Bitcoin

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

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.

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.

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.


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


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.

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.

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

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


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.

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)

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.

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





 

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.

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.


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

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

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

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.

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.  ;D

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.  ;D

So, that's why I would do it differently  ;D

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

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.

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

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


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