Topic: Mathematical Shortcuts To Hashing - page 2. (Read 4554 times)

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. 

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

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

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.

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?

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.

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

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

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.

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

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

http://ssdeep.sourceforge.net/

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

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.

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

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