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

[1714785990]

1714785990

[1714785990]

1714785990

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

[Sukrim]

Depends on how bullish you are on bitcoin...

Also, if you find a way to make mining significantly easier you can either play the poker game and try to get rich with BTC or by selling the SHA256 weakness to someone(TM) or you take the safe route and just publish it. If there is a significant weakness in SHA256 (and to be useful in mining, it needs to be quite significant) chances are that you're not the first one to find it and there are MUCH more valuable things at stake than a small ~1 billion USD cryptocurrency community of nerds and dreamers.

PoW being useful... I would say giving a strong incentive to do cryptoanalysis of SHA256 (or whatever other algorithm is used in the future or other bitcoin-style currencies) is already useful. There are few things in computation that I can think of that are truly "useful" besides being interesting. Would it be more "useful" if you need to attach a larger prime number than the previous block had to a block? Would it be "useful" to embed the current word distribution in all wikipedia editions? To predict what the NASDAQ or some other stock index will be in 10 minutes and whoever predicts closest by that time, gets the block retroactively (that one might even be useful after all )? To predict something else (weather data, forex data, sports events)? What the next nanosecond would look like if you set off a tactical nuke in environment X?
I just can't imagine things that don't rely on central sources and are truly useful, sorry. Mayme you can? Do you have some ideas on that topic?

[Qwedcxza1]

Well I was thinking of something along the lines of producing large prime numbers. They can be useful in cryptography. The problem is that proof of work needs a problem that takes a great deal of computational power to find a solution and very little to check the solution.
 If you are finding prime numbers then it takes a great deal of computational power to check whether it is prime. But you could turn it around into finding factors of a very large number to check whether it is prime.
 Once you have found the useful problem that needs a great deal of computational power to solve but little to check there is also the problem of whether it could be pre-mined and somebody could save up solutions and use them for a double spend so each new problem would have to be created from the last solution.
 I don't think there is any real reason why proof of work could be used on a separate problem to the blockchain as it does not necessarily have to be related. All we need is that it is in someone's best interest to use their solution to the problem to earn coins from mining rather than trying to double spend.

[Sukrim]

But you could turn it around into finding factors of a very large number to check whether it is prime.

Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...

I think "useful" would maybe work with predictions (e.g. the stock scenario) as it would also leave open the actual implementation up to the users. Still you would need to predict something that can be observed from everyone on the whole earth and that on the other hand is not under the control of an entity that might restrict access or manipulate the observation itself.

Other "useful" examples would be for instance SAT solving a huge set of clauses (that you could generate randomly) - to make it really hard though you would need to generate probably quite large sets after some time and then they become less and less useful again. Also you could utilize existing solutions to make tiny alterations and submit a new solution so you would need to guarantee that no other set of clauses was being used to even generate your intitial set in the first place.

[Qwedcxza1]

But you could turn it around into finding factors of a very large number to check whether it is prime.

Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...

A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor anybody can quickly check whether it actually is a factor.
 Then some formula using the previous number and the factor that has just been found is used to create the next big number to check.
 Of course there is the problem that if the number is actually prime we never find a factor. This isn't an answer just an idea of what sort of thing the pow problem might be.

 There is a lot of processing power out there working on hashing. What if a researcher wants to use this sort of distributed processing power for a useful research project? Everybody donates their processing power to the project and they are then entered into a lottery with the chances of winning related to how much processing power they donate. This lottery replaces the lottery of whether or not you come up with the right nonce.

[coinedBit]

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

Never say never, you can only accomplish the unthinkable if you consider it possible in the first place.
Among hundreds of scammers, there are some pretty clever people around here , and there are some pretty sophisticated ideas floating around, too.

However, people looking at speeding up btc-mining by discovering shortcuts (not necessarily in SHA256, but rather in the way it is used by bitcoin, and the way difficulty is modified in a p2p fashion), should have a pretty strong background in math, cryptology, computer science and engineering.

There are really only very few threads to be found here where you can find people discussing these things who obviously do have such a background, which is only really obvious to people with a similarly strong background. Some of the more interesting threads include:

https://bitcointalk.org/index.php?topic=55888.0
https://bitcointalk.org/index.php?topic=120473.0

Bottom line being, you need to know how to translate crypto-maths into code and vice versa, not just at the HLL level (C/C++, OpenCL or VHDL), but also at the instruction level,i.e. assembly/RTL instructions and parallel hardware, i.e. GPUs, FPGA and structured/standard cell ASICs. All these skills are hard to find in a single person.

Again, I am not saying that SHA256 can be realistically broken by a single person, but rather that you can indeed make certain assumptions about the way SHA256 is used by bitcoin for mining purposes, and for controling difficulty through mining output, by just requiring more bits to be 0 - which conceptually /could/ translate into less potential work for the miners, like mentioned earlier.

[bluemeanie1]

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

or if you had such secret knowledge you could run a spy agency...  hmm....

[bluemeanie1]

But you could turn it around into finding factors of a very large number to check whether it is prime.

Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...

A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor anybody can quickly check whether it actually is a factor.
 Then some formula using the previous number and the factor that has just been found is used to create the next big number to check.
 Of course there is the problem that if the number is actually prime we never find a factor. This isn't an answer just an idea of what sort of thing the pow problem might be.

 There is a lot of processing power out there working on hashing. What if a researcher wants to use this sort of distributed processing power for a useful research project? Everybody donates their processing power to the project and they are then entered into a lottery with the chances of winning related to how much processing power they donate. This lottery replaces the lottery of whether or not you come up with the right nonce.

how about this:

the currency is 'pre-mined' EXCEPT if you find a new prime number.  The miners only get transaction fees.

here is the twist:

so if you think you discovered a prime number, you create a special block which grants you eg. 80,000 USD worth of primecoin.

if someone discovers a factor to that prime, then you lose your block, your award, and anyone holding those coins also loses their balances(this would of course require extensive reordering of the BC- but it is effectively possible). This kind of tracing to a genesis transaction is done and proven with color coins.  What does this create?  it means that pseudoprimes would be a kind of currency, just not a very sound one.  If you chose to accept value from a dubious pseudoprime, you risk losing your money.  So this puts the onus on the person claiming the number, they might want to publish a reason why they think this number is prime.

it would have an interesting effect, for instance the pseudoprimes that are located along features in the Ulam Spiral would have higher market rates than those that didn't.  It would create an entire speculative market for prime computation.  Kurt Godel would be ecstatic.

In other words:  you believe integer X is prime.  You read a whitepaper that suggested so.  So you buy some coins that are FOUNDED in that prime.  If it is later proven to be prime, the market value goes up.  If I'm a Integer Factorization Miner, and I think I can find a factor in it- I take out a short position- mine the integer, find a factor, publish, and the price plummets and I go buy a steak dinner.

Has no one ever proposed this idea before?  Primes are really the only true COMMODITY in mathematics.  They are in limited supply but also unbounded.  They are useful.  They are hard to find.  This lives up more to the promise of bitcoin than bitcoin itself.

[bluemeanie1]

But you could turn it around into finding factors of a very large number to check whether it is prime.

Couldn't you just lie about this? Imagine "15" is such a huge number: I just claim that the only factors I could find for 15 are 1 and 15, thus making it prime. This still requires you to try to find other factors to debunk my claim...

A large number is proposed and everybody keeps dividing it by various primes until somebody gets lucky and finds a factor. It takes a lot of computational power to keep dividing but when you have found a factor anybody can quickly check whether it actually is a factor.

these problems lie at the basis of the RSA function itself: http://en.wikipedia.org/wiki/RSA_%28algorithm%29#Integer_factorization_and_RSA_problem

[David Rabahy]

I'm sure I'm missing something here (timestamp and previous block come to mind) but would it be possible to create a burst of transactions yourself -- enough to populate an entire block -- carefully designed to make the calculation of the hash quicker than accumulating transactions from the broadcast stream?

[Qwedcxza1]

carefully designed to make the calculation of the hash quicker than accumulating transactions from the broadcast stream?

The idea of the hash is that sha256(x)->y is a one way function that gives out pretty random results
So if you know y you can't work out x
If you know x you can work out y but it will be a random result
So carefully designing your own x won't help you predict y so you have to use brute force until you come up with the y you are looking for or start experimenting with some of the SAT techniques

[bluemeanie1]

Careful how you use the term random there, its not a very accurate usage.

[Sukrim]

I'm sure I'm missing something here (timestamp and previous block come to mind) but would it be possible to create a burst of transactions yourself -- enough to populate an entire block -- carefully designed to make the calculation of the hash quicker than accumulating transactions from the broadcast stream?

By adding transactions, you can change the merkle root part of the blocks, yes. There is so far no known way though to find out how to "design" this input to make the output more favorable for BTC mining, so currently only the nonce is generally changed when mining for some time. Merkle root and timestamp also change over time of course, but while iterating over 1 nonce range (from 0 to 2^32) usually the remaining header is kept or assumed constant to make it also easier for miners so they don't have to constantly check for changes after every single nonce.

SAT solvers are also just fancy brute forcing mechanisms, though they have the advantage that they can be able to ignore certain paths on their own if they are not useful or redundant.

[bluemeanie1]

I'm sure I'm missing something here (timestamp and previous block come to mind) but would it be possible to create a burst of transactions yourself -- enough to populate an entire block -- carefully designed to make the calculation of the hash quicker than accumulating transactions from the broadcast stream?

By adding transactions, you can change the merkle root part of the blocks, yes. There is so far no known way though to find out how to "design" this input to make the output more favorable for BTC mining, so currently only the nonce is generally changed when mining for some time.

this would certainly violate the irreversibility principle behind SHA-256.

[RandyFolds]

Enormous trollfail, bonkers.


So, when are you gonna take me up on this trip to the bone zone?