Bitcoin Forum
October 23, 2017, 01:50:24 PM *
News: Latest stable version of Bitcoin Core: 0.15.0.1  [Torrent]. (New!)
 
   Home   Help Search Donate Login Register  
Pages: 1 2 3 [All]
  Print  
Author Topic: Guy on twitter claims he is working on hash method without brute force.  (Read 8457 times)
jimbobway
Legendary
*
Offline Offline

Activity: 1398



View Profile
May 30, 2011, 04:58:10 PM
 #1

"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
1508766624
Hero Member
*
Offline Offline

Posts: 1508766624

View Profile Personal Message (Offline)

Ignore
1508766624
Reply with quote  #2

1508766624
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1508766624
Hero Member
*
Offline Offline

Posts: 1508766624

View Profile Personal Message (Offline)

Ignore
1508766624
Reply with quote  #2

1508766624
Report to moderator
jimbobway
Legendary
*
Offline Offline

Activity: 1398



View Profile
May 30, 2011, 05:00:02 PM
 #2


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
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 05:01:49 PM
 #3

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.

proudhon
Legendary
*
Offline Offline

Activity: 1232



View Profile
May 30, 2011, 05:04:37 PM
 #4

bitcoinfail.  Oh well, I guess I'll just start playing Crysis 2 now.
eturnerx
Member
**
Offline Offline

Activity: 84


View Profile
May 30, 2011, 05:09:04 PM
 #5

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.
^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.
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 05:10:28 PM
 #6

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.

Insti
Sr. Member
****
Offline Offline

Activity: 294


Firstbits: 1duzy


View Profile
May 30, 2011, 05:14:23 PM
 #7

+1 on what Quantumplation said.
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 05:17:12 PM
 #8

Quote
Aspie, hacker, part-time CompSci+Psychology OU student, pirate party member, AI geek, Assassins Creed fanatic, pseudo-transhumanist

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.

Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
May 30, 2011, 05:26:47 PM
 #9

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.
John Tobey
Hero Member
*****
Offline Offline

Activity: 481



View Profile WWW
May 30, 2011, 05:31:04 PM
 #10

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.

Can a change to the best-chain criteria protect against 51% to 90+% attacks without a hard fork?
proudhon
Legendary
*
Offline Offline

Activity: 1232



View Profile
May 30, 2011, 05:44:51 PM
 #11

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.

Oh, wait, so is it safe to go back to mining?
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 05:49:24 PM
 #12

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.

Dobrodav
Full Member
***
Offline Offline

Activity: 182


CarTaxi: The 1st car towing platform on blockchain


View Profile
May 30, 2011, 05:53:31 PM
 #13

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

Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
May 30, 2011, 06:18:55 PM
 #14

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.

The input is a block header, the contents of which are not flexible. Only the nonce is.
John Tobey
Hero Member
*****
Offline Offline

Activity: 481



View Profile WWW
May 30, 2011, 06:28:52 PM
 #15

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.

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.

Can a change to the best-chain criteria protect against 51% to 90+% attacks without a hard fork?
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 06:34:41 PM
 #16


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.

John Tobey
Hero Member
*****
Offline Offline

Activity: 481



View Profile WWW
May 30, 2011, 06:54:23 PM
 #17

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.

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

Can a change to the best-chain criteria protect against 51% to 90+% attacks without a hard fork?
unk
Member
**
Offline Offline

Activity: 84


View Profile
May 30, 2011, 06:59:07 PM
 #18

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.
FooDSt4mP
Full Member
***
Offline Offline

Activity: 182


View Profile
May 30, 2011, 07:54:51 PM
 #19

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.

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


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

As we slide down the banister of life, this is just another splinter in our ass.
sandos
Full Member
***
Offline Offline

Activity: 122


View Profile
May 30, 2011, 07:59:23 PM
 #20

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?

[ CENTRA ] Multi-Blockchain Worldwide Debit Card & Insured Wallet
▞▬▬▬▞▬▬▬▞▬▬▬▞▬▬▬▞▬▬▬▞▬▬▬▚▬▬▬▚▬▬▬▚▬▬▬▚▬▬▬▚▬▬▬▚
FacebookSlackTwitterGithubMediumANN Thread
zby
Legendary
*
Offline Offline

Activity: 1557


View Profile
May 30, 2011, 08:07:33 PM
 #21

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.
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.
grue
Global Moderator
Legendary
*
Offline Offline

Activity: 2016



View Profile
May 30, 2011, 08:23:13 PM
 #22

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

It is pitch black. You are likely to be eaten by a grue.

Tired of annoying signature ads? Ad block for signatures
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 30, 2011, 08:26:01 PM
 #23

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

BitRapture.

Mike Hearn
Legendary
*
Offline Offline

Activity: 1526


View Profile
May 30, 2011, 08:35:03 PM
 #24

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.
FreeMoney
Legendary
*
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW
May 30, 2011, 08:37:28 PM
 #25

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.

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
cloud9
Member
**
Offline Offline

Activity: 70


View Profile
May 30, 2011, 08:42:24 PM
 #26

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!!!  Cheesy)

Disclaimer:  Postings of Cloud9 are only individual views of opinion and/or musings and/or hypothesisses.  On a non-authoritative, peer-to-peer public forum, you do not need permission from Cloud9 to derive your own conclusions or opinions, so please do.  Calculations and assumptions to be verified.
FreeMoney
Legendary
*
Offline Offline

Activity: 1246


Strength in numbers


View Profile WWW
May 30, 2011, 08:45:06 PM
 #27

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

Play Bitcoin Poker at sealswithclubs.eu. We're active and open to everyone.
gigitrix
Hero Member
*****
Offline Offline

Activity: 666


Bitcoins finest!!!


View Profile
May 31, 2011, 01:08:44 AM
 #28

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  Roll Eyes
unk
Member
**
Offline Offline

Activity: 84


View Profile
May 31, 2011, 01:52:43 AM
 #29

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?
bittrader
Jr. Member
*
Offline Offline

Activity: 42



View Profile
May 31, 2011, 11:39:01 PM
 #30

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.

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.
Quantumplation
Full Member
***
Offline Offline

Activity: 154



View Profile
May 31, 2011, 11:43:47 PM
 #31

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.

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

wumpus
Hero Member
*****
Offline Offline

Activity: 798

No Maps for These Territories


View Profile
June 01, 2011, 04:40:03 AM
 #32

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.

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.

this is going to turn out just like the may doomsday. once it flops, the guy is just going to vanish.
Indeed, he wouldn't exactly be the first guy making a bold claim on the internet.

Bitcoin Core developer [PGP] Warning: For most, coin loss is a larger risk than coin theft. A disk can die any time. Regularly back up your wallet through FileBackup Wallet to an external storage or the (encrypted!) cloud. Use a separate offline wallet for storing larger amounts.
Gareth Nelson
Hero Member
*****
Offline Offline

Activity: 722


View Profile
October 04, 2011, 07:36:42 PM
 #33

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

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

I didn't vanish Wink

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.
ElectricMucus
Legendary
*
Offline Offline

Activity: 1568


Drama Junkie


View Profile
October 04, 2011, 07:44:48 PM
 #34

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.

First they ignore you, then they laugh at you, then they keep laughing, then they start choking on their laughter, and then they go and catch their breath. Then they start laughing even more.
Gareth Nelson
Hero Member
*****
Offline Offline

Activity: 722


View Profile
October 04, 2011, 07:46:48 PM
 #35

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.
Gabi
Legendary
*
Offline Offline

Activity: 1050


View Profile
October 04, 2011, 07:58:34 PM
 #36

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

+

aspiesforfreedom

aspie...


=

Yeeeaahhh sure....  Roll Eyes should i link the aspie article on encyclopedia dramatica?
Gareth Nelson
Hero Member
*****
Offline Offline

Activity: 722


View Profile
October 04, 2011, 08:01:57 PM
 #37

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
ElectricMucus
Legendary
*
Offline Offline

Activity: 1568


Drama Junkie


View Profile
October 04, 2011, 08:25:01 PM
 #38

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

First they ignore you, then they laugh at you, then they keep laughing, then they start choking on their laughter, and then they go and catch their breath. Then they start laughing even more.
Gareth Nelson
Hero Member
*****
Offline Offline

Activity: 722


View Profile
October 04, 2011, 08:42:15 PM
 #39

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

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.
error
Hero Member
*****
Offline Offline

Activity: 574



View Profile
October 05, 2011, 12:26:41 PM
 #40

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

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.

15UFyv6kfWgq83Pp3yhXPr8rknv9m6581W
Gareth Nelson
Hero Member
*****
Offline Offline

Activity: 722


View Profile
October 06, 2011, 09:50:18 AM
 #41

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

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
Hero Member
*****
Offline Offline

Activity: 616


Firstbits.com/1fg4i                :Ƀ


View Profile
October 06, 2011, 11:30:06 AM
 #42

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.

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX Smiley

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
October 06, 2011, 12:40:58 PM
 #43

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.

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

Quote
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
Full Member
***
Offline Offline

Activity: 198


View Profile
October 06, 2011, 01:12:50 PM
 #44

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

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
Donator
Legendary
*
Offline Offline

Activity: 1408


View Profile
October 06, 2011, 09:40:04 PM
 #45

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

OrganofCorti's Neighbourhood Pool Watch - The most informative website on blockchain health
bcforum
Full Member
***
Offline Offline

Activity: 140


View Profile
October 07, 2011, 02:59:43 AM
 #46


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

Code:
04111a63
a7900e03
bb971f16

Can you guess why?

If you found this post useful, feel free to share the wealth: 1E35gTBmJzPNJ3v72DX4wu4YtvHTWqNRbM
dentldir
Sr. Member
****
Offline Offline

Activity: 324



View Profile
October 07, 2011, 08:54:37 PM
 #47


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.


1DentLdiRMv3dpmpmqWsQev8BUaty9vN3v
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
October 07, 2011, 09:28:05 PM
 #48

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
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
October 08, 2011, 12:10:06 AM
 #49

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
Full Member
***
Offline Offline

Activity: 198


View Profile
October 09, 2011, 11:24:59 AM
 #50

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





 
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
October 09, 2011, 03:53:46 PM
 #51

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
Full Member
***
Offline Offline

Activity: 140


View Profile
October 09, 2011, 07:05:50 PM
 #52


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.

If you found this post useful, feel free to share the wealth: 1E35gTBmJzPNJ3v72DX4wu4YtvHTWqNRbM
sd
Hero Member
*****
Offline Offline

Activity: 730



View Profile
October 10, 2011, 05:14:22 PM
 #53


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
Full Member
***
Offline Offline

Activity: 125


View Profile
October 10, 2011, 05:21:30 PM
 #54

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.

Lost your wallet password? Try Stillfire's Password Recovery Service.
Forp
Full Member
***
Offline Offline

Activity: 198


View Profile
October 10, 2011, 08:57:52 PM
 #55

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

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

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

So, that's why I would do it differently  Grin

Ok. Ok. My remark is not supposed to be taken dead seriously.  Cheesy
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
October 10, 2011, 09:10:40 PM
 #56

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
Full Member
***
Offline Offline

Activity: 198


View Profile
October 10, 2011, 09:31:31 PM
 #57

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  Roll Eyes 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...  Roll Eyes
DeathAndTaxes
Donator
Legendary
*
Offline Offline

Activity: 1218


Gerald Davis


View Profile
October 10, 2011, 10:07:22 PM
 #58

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

Quote
We cannot think of such aspects often enough, because it is the very detail which, when overlooked, could produce interesting  Roll Eyes 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...  Roll Eyes

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

Activity: 350



View Profile
October 10, 2011, 10:17:30 PM
 #59

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  Wink

Pages: 1 2 3 [All]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!