3

Suppose, for example, I want to write an Ethereum contract that pays 1 ETH for whoever gives me the right answer to sha256^1000000000("good boy"). That amount of computation would be much higher than Ethereum's gas limit, so, I need a way to prove sha256^1000000000("good boy") = Y without needing that much computing power on the verifier's side.

How can that be done?

(That is an weaker version of my earlier question, that didn't get good answers. Hopefully this problem is simpler?)

migrated from crypto.stackexchange.com Dec 9 '17 at 16:04

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • 2
    You can’t verify an iterated hash faster. You could pre calculate the result offline and store the hash of the expected result (sha256(“str”)^.1000001). We could maybe recommend a better method if you tell us the actual problem you want to solve. If this is some proof of work scenario use a asymmetric method like for example the PoW which is used by bitcoin (give me a nonce which together with my challenge generates a hash which is smaller than a defined difficulty) – eckes Dec 9 '17 at 15:18
  • @eckes Not much different from what I answered, is it? – e-sushi Dec 9 '17 at 15:27
  • @e-sushi yes, however in order to publically store an verifier (contracts are executable) you need to use a result after the expected iterations (larger exponent) Not before. Otherwise they could start from there. – eckes Dec 9 '17 at 15:30
  • @eckes Erm, what? That public verification result you assume might be an Ethereum thing – which would be off-topic here and more something for Ethereum.SE. Since we’re at Crypto.SE I assumed the verifier doesn’t store the SHA-256 (verification) result “in the open”. This was neither described in the question, nor asked. So, I logically assumed verifier keeps the verification result secret until a calculating sender indeed sends the correct, matching hash result. What you describe introduces a different security problem, completely unrelated to hashing a string millions or billions of times. – e-sushi Dec 9 '17 at 16:01
  • The op asks for an Ethereum contract to do it. And those are public. – eckes Dec 9 '17 at 16:03
1

That will be near to impossible to shortcut due to the simple reason that SHA-256 is cryptographically secure hash and doesn’t offer a way to do this without doing the actual computations.

Also, there are no known weaknesses in SHA-256 that would allow us to handle this. If there were, SHA-256 would be broken and definitely not cryptographically secure anymore.

The only solution would be having pre-knowledge of a verified part of the calculation; for example $\text{SHA256}^{987654321} = X$ so you have $X$ as a starting point that doesn’t expect a truckload of calculations to get your $Y$ that will take longer than we both live.

Yet, even if someone already calculated millions of SHA-256 rounds on the string “good boy” you’ld still have to verify somehow that that pre-computation is indeed correct and not flawed… which ends up being the same problem that you’ld probably have to recalculate things completely.

Thinking about it for a sec – your scenario comes close to a computational complexity which could be compared to the complexity that secures some cryptocurrency blockchains like Bitcoin which use different, but alike time- and resource-consuming calculations in their “Proof Of Work”.

Therefore, my suggestion would be to simply lower the complexity from your $$\text{SHA256("good boy")}^{1000000000}$$ to something more usable and achievable $$\text{SHA256("good boy")}^{1000000}$$

A verifier that can't perform that much computations will still chew a day or two on that, but you can lower or raise the bar according to your specific needs.

One thing should be clear: Using a cryptographically secure hash, you can’t verify quicker than calculating this completely; just like the calculating sender will have to completely calculate the result you later want to verify. More computational resources will logically result in quicker calculation… which might or might not be a problem when your verifier doesn’t have the same computational resources as the other party. This is something you need to remember and watch out for, depending on how and/or where you want to use/implement your idea.

  • How is that true? The question is not about computing this function fast, but verifying that the computation was performed correctly, in smaller time than required for evaluating it. And we know that it is feasible, with cryptographic methods, to generate proofs that a very long computation leads to some result, so that verifying the proof takes far less time than performing the computation. That's called delegation of computation, and a SNARGs would perfectly do the trick - we even have implementations available. – Geoffroy Couteau Dec 9 '17 at 18:23
  • @GeoffroyCouteau LOL, really? Ok, I’m open to be corrected. Simply then tell me the SHA-256 result of sha256^1000000000("good boy") so you can verify and prove it’s not what I claim: 2e115facdd6e12fdb2938b6a0d6662efa2cd92dac6a3c5c94c8784c52a1dd0b5 (which is exactly the problem OP is asking about ever since he dropped the question at Crypto.SE). If you’re able to verify and prove my hash result is not correct, I’ll gladly delete my answer. For your convenience, this offer stands for as long as I live. Good luck! ;) – e-sushi Dec 10 '17 at 8:29
  • @GeoffroyCouteau See, I agree that there are other solutions to the problem, but the question specifically asked about verifying a billion SHA-256 calculations on a string. So, my answer limits itself to talking about exactly that. One of the reasons I moved the Q&A over here is that it became clear the asker needs something different than his/her SHA-256 idea. As you’ll notice, your comment and answer avoid to talk about SHA-256 all together and bluntly point to another solution, while failing to explain why “verifying a billion SHA-256 rounds” as described is not feasible in such scenarios. – e-sushi Dec 10 '17 at 8:53
  • I'm open to correction also, and I might have misunderstood OP's question :) I interpreted the following sentence: "I need a way to prove sha256^1000000000("good boy") = Y without needing that much computing power on the verifier's side" as the following question: the prover, who computes the iterated hash, needs a way to produce an accompanying proof that he did it correctly, so that the proof can be verified faster than computing the hash entirely. In my understanding of the scenario, it becomes feasible, because the prover is willing to help the verifier in the process. – Geoffroy Couteau Dec 10 '17 at 10:39
  • 1
    But of course, if the prover simply gives you the result and tell you to verify it, without anything more, you cannot do much better than doing the entire calculation. Verifying a billion sha256 calculation on a string (or, indeed, any other type of well defined heavy calculation) in small amount of time is perfectly feasible if the prover is willing to help, he can even do so non-interactively by producing a short accompanying proof, but it's indeed infeasible without his help. – Geoffroy Couteau Dec 10 '17 at 10:48
0

See my answer to your other question at Cryptography.SE: the simplest solution would be to use a smart contract that performs the verification algorithm of a SNARG system for the statement you want. The verification time can be made essentially independent of the size of the computation, and several implementations of SNARGs are available. The main issue here is for the prover, who would not only need to solve the riddle, but also to generate a proof that he solved it, which can take quite some time - but you're trying to make it hard for him to solve it anyway, so it's probably not an issue.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.