Mathematical Shortcuts To Hashing

[bonker]

I mean, given the insane resources and vital energy of the worlds cryptowonks, there has to be buckets of shortcut techniques that will cut the hash time vastly..... Must be more worth investigating that banging out more brute-force hardware.

Who's with me? I'm an epic maths genius, only suitable qualified persons need apply

[Sergio_Demian_Lerner]

SAT solving - An alternative to brute force bitcoin mining

http://jheusser.github.io/2013/02/03/satcoin.html

Not good enough, but it may improve...

[Sukrim]

SAT solving would only help if the algorithm does have parts that can be neglected e.g. a 0 somewhere in the input can be mapped more or less easily to a 13 or 19 in the output. This would also mean that SHA256 is weaker than expected.
I would love to see more examples on this approach, my guess is that this is just variance.

Also the extreme case that would be the easiest to solve according to the theory would be a known hash (e.g. "00000000000000000000000000000000") and then one needs to find a nonce that creates this...

Also what makes SAT solving worse is the need for a time stamp in the header and even worse the reference to the previous block. As far as I understand SAT solving it will try lots of combinations until it finds a solution or has no more combinations left to try. Frequent changes in the input area are probably not helping as there might be actual progress with SAT mining compared to the pure guessing game of traditional brute force mining.

[RagnarDanneskjold]

Context triggered hashing (CTPH)/ fuzzy hashing, yes?

http://ssdeep.sourceforge.net/

(PDF) - http://dfrws.org/2006/proceedings/12-Kornblum.pdf

[Sukrim]

Skimming over the ssdeep page + paper sounds more like it is describing the rsync algorithm (http://rsync.samba.org/tech_report/), a similar one is used in bup as well...
Also depending on desired block size these file signatures could be even larger than the input files.

I tried to build such a system for fun using Adler32 and SHA256, it ran fairly slow (as it was totally unoptimized and just a few lines after all) but still fast enough to deduplicate files at ~10MB/s on a single core.

How is this applicable to Bitcoin? You might be able to compress the block chain a bit by finding duplicate data, but besides that...?

[RagnarDanneskjold]

Skimming over the ssdeep page + paper sounds more like it is describing the rsync algorithm (http://rsync.samba.org/tech_report/), a similar one is used in bup as well...
Also depending on desired block size these file signatures could be even larger than the input files.

I tried to build such a system for fun using Adler32 and SHA256, it ran fairly slow (as it was totally unoptimized and just a few lines after all) but still fast enough to deduplicate files at ~10MB/s on a single core.

How is this applicable to Bitcoin? You might be able to compress the block chain a bit by finding duplicate data, but besides that...?

I mention fuzzy hashing only as a broad conceptual reply to the post's question (linked to sdeep for basic illustration as is the most common implementation) - similar underlying function as DPLL/backtracking algorithms in SatCoin.

[piotr_n]

It's a double hash... if you discover an actual shortcut in it, you'd probably deserve a Nobel price, FWIW

[bluemeanie1]

SAT solving would only help if the algorithm does have parts that can be neglected e.g. a 0 somewhere in the input can be mapped more or less easily to a 13 or 19 in the output. This would also mean that SHA256 is weaker than expected.
I would love to see more examples on this approach, my guess is that this is just variance.

Also the extreme case that would be the easiest to solve according to the theory would be a known hash (e.g. "00000000000000000000000000000000") and then one needs to find a nonce that creates this...

Also what makes SAT solving worse is the need for a time stamp in the header and even worse the reference to the previous block. As far as I understand SAT solving it will try lots of combinations until it finds a solution or has no more combinations left to try. Frequent changes in the input area are probably not helping as there might be actual progress with SAT mining compared to the pure guessing game of traditional brute force mining.

hi Sukrim,

youre right!

sha256("1")=  6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b
sha256("2")=  d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35
sha256("3")=  4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce
sha256("4")=  4b227777d4dd1fc61c6f884f48641d02b4d121d3fd328cb08b5531fcacdabf8a
sha256("5")=  ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d
sha256("6")=  e7f6c011776e8db7cd330b54174fd76f7d0216b612387a5ffcfb81e6f0919683

anyone notice a pattern here?

if you did, you should publish a paper because so far no one has.  btw- people did find problems with SHA-0 and some others that's why they are no longer used.

SHA is supposed to be irreversible, as in there is nothing you can tell about the input from the output.

thus it is theoretically impossible to reduce the probability of finding a solution to a block.  Advanced techniques like Genetic Algorithms will not improve your chances.  We might one day make advances in Number Theory which can tell us something about about where to look for eg. solutions to Bitcoin blocks, but as of now we don't know(that is, the general public- the NSA et al. might have secret knowledge of number theory and many people have suggested so).

there are things that haunt us about number theory that tend to indicate there are things we don't know.  http://en.wikipedia.org/wiki/Ulam_spiral

[Sukrim]

Well, the input range for the second hash is limited to 256 bits... maybe this could present some weaknesses, but I doubt there would be many flaws that would be useful for bitcoin mining.

Rainbow tables and the likes are just going to be far too sparse to be able to be of any use and as you can see from the SAT experiments so far also automated algorithms seem to not find shortcuts easily.

[bluemeanie1]

There is no obvious way to shortcut the mining algorithm.  The right place to look is Cryptology journals.  Researchers are always looking to find holes in the standard algos such as SHA-256.  They have found holes in previous algorithms.  If someone found a problem with SHA-256, then 1) there would be an market signal in the ASIC miner field- suddenly this hardware would be using an inferior algorithm 2) probably some kind of effect in the price of BTC.  But who really knows?

[bluemeanie1]

oh and regarding Genetic Algorithms, as they have been proposed as a way to solve blocks(informally).  GAs are simply a search function that optimize the discovery of maxima in a hyperplane of unknown shape.  However if this hyperplane is non-differentiable(which SHA most certainly is, to say the least), then it cannot be used to evolve a useful function.  Thus GAs don't give you anything in this case.

[piotr_n]

you could think of some kind of rainbow tables, to be used inside the hashing algorithm, that would allow to speed up some steps of it, but its always a trade of 'is it worth it?'.
seems that it isn't. it seems just cheaper to make an asic that will do these ops for you, instead of building rainbow tables or whatever such complex and memory hungry around such a simple binary operations.
though, from the math point of view, keep trying - the nobel prize is waiting...
and if you do it, you will also be my hero

[piotr_n]

yeah, i figured it was a stupid idea while writing it :-)
but that is how i'd eventually imagine shortcuts in the hashing process;  as some kind of lookup table stuff.
though, if someone can do it through a math, hell I'd like ton see it

[bonker]

It's a double hash... if you discover an actual shortcut in it, you'd probably deserve a Nobel price, FWIW

I deserve a Nobel Prize anyway just for my general slick moves. Even so, I'm pretty certain that short cuts are out there, just cus some semi-autistic pencil-neck at the NSA balks doesn't mean it aint there for the finding. 

[coinedBit]

it's not just the NSA that's using these algos, and if you were to find a "short cut", there would be tons of money to be made, even without touching bitcoin

[scintill]

SHA-256 as a boolean function, see also the discussion here.

[Qwedcxza1]

pow?

[Sukrim]

pow?

Proof of Work, in Bitcoin context:
Find a nonce (number used once) that makes the output of SHA256(SHA256(block header + nonce)) smaller than a certain number (difficulty).

The question is if there is any way around simply trying nonce = 0, nonce = 1... and so on until you find a fitting one, or if there are shortcuts or strategies to find one quicker.
The OP seems to be trolling though and I love the fact that for once this is being ignored and turned into an actually nice and interesting thread!

Lookup tables and so on might be used in the second iteration, you could store SHA256 hashes of the first round and if they lead to a hash that is already known in th secod round, you don't need to calculate that one. I doubt though that there would be many benefits from that, as the number of hashes starting with 128 zeros (that's a VERY high difficulty!) is still 2^128... (that's a VERY high number of hashes to store). You'll waste far more energy doing the (in most - with most meaning all - cases unsuccessful) lookup before doing the calculation of the second hash anyways.

[Qwedcxza1]

But if somebody did find a quicker way of hashing and everybody started doing it then the difficulty would have to increase wouldn't it? So it would be pointless unless you kept it secret so you could mine faster than everybody else.
I think it would be interesting if the pow could be somehow be used to do something useful. I don't really know how though.

[coinedBit]

if you were to find a way to speed-up hashing beyond just structured/standard-cell ASICS, the dumbest thing to do would be sharing your knowledge, you would ideally run your own little hashing farm and turn it on/off on demand to print money and "surf & ride difficulty".