Mathematical Shortcuts To Hashing

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