What is the most efficient way to prove that a person computed $r$ rounds of some cryptographic hash function (ex. SHA256) on an input? Specifically, I'm trying to optimize (1) the running time of the verifier and (2) the size of the proof (in that order).

The trivial solution seems to be to show all $r$ hashes, where $v_i = hash(v_{i-1}), \space \forall i \leq r$, but this seems very space inefficient.

  • 3
    $\begingroup$ Welcome to Crypto.SE! There are a variety of possible techniques. To help me narrow down which will be most relevant to your particular situation: How large is $r$ in your setting? Are you OK with probabilistic answers (where there's a tiny chance the verifier is fooled)? What measure of efficiency do you care about most? The size of the proof? The running time of the verifier? The running time of the prover? Are you OK with an interactive protocol or does it need to be non-interactive? $\endgroup$
    – D.W.
    Jul 3 '17 at 1:09
  • 2
    $\begingroup$ To deterministically verify that r hashes indeed lead to the given value, the verifier has to compute all r hashes no matter what you do. So if you're looking for deterministic proofs, the most "efficient" is only to send the first and last values. For probabilistic proofs like D.W. suggests, you could e.g. send all intermediate values, and the verifier can randomly select a bunch of the steps to verify, to convince himself the result is correct. $\endgroup$
    – TMM
    Jul 3 '17 at 1:19
  • $\begingroup$ Thanks for great answers! I was looking to minimize (1) the running time for the verifier and (2) the size of the proof (in that order). r can be any natural number (but will usually be in the range [10^6,10^7]). Running time of prover is not an issue. Protocol can be interactive, but I'm really looking for a non-interactive solution (I think I know how to build the interactive verification game). $\endgroup$
    – user74433
    Jul 3 '17 at 9:52
  • $\begingroup$ If you only veify some of steps the chance of detecting forgery is small. I precompute a long chain of hashes unrelated to the input, then I calculate a small number of hashes much smaller then r on the input and switch over to my precomputed chain. Only 1 step is bad. Chances of detection are small. $\endgroup$
    – Meir Maor
    Jul 3 '17 at 15:13
  • $\begingroup$ Are you concerned to prove A) that $\text{hash}^r$ has been computed, as in the title; or B) that $r$ hashes have been computed? A) does not seem to allow cheap verification, while with some leeway B) does. $\endgroup$
    – fgrieu
    Jul 4 '17 at 10:00

Though a formal proof eludes me at the moment. I believe I can make a compelling argument this can't be done.

If what you want is for a prover to supply the output and some extra evidence. And the verifier should be able to convince himself with high probability it is correct with effort orders of magnitude less then computing the hash himself.

Even if the prover provides the full chain, a forger will be able to swap just a singls hash and compute any additional stuff on the forged chain. Other then checking the single forged hash( 1 in r) there is no way for the verifier to catch this. If the verifier checks even half of the steps at random that still gives the forger a 50% chance of succeeding(going undetected). You presumbly want the verifier to check only a handfull of hashes but that would give the forgery excellent chances of going undetected.

In order to get high confidence the verifier would have to do almost all the work of computing the r hashes himself.

  • $\begingroup$ Hi, thanks for your answer. Could you please make it a bit more readable ? :) Also the 50% chances of succeeding seems rather vague. Please provide a mathematical explanation for it. :/ $\endgroup$
    – Biv
    Jul 4 '17 at 8:00
  • $\begingroup$ When I say 50% I mean forgery has a 50% chance of going undetected. $\endgroup$
    – Meir Maor
    Jul 4 '17 at 8:23
  • $\begingroup$ 50% chances is huge. That is a risk that no one wants to take, which is why I would like to understand where that number come from. $\endgroup$
    – Biv
    Jul 4 '17 at 8:23
  • $\begingroup$ That was the point. It's just an example. If the veifier checks p% of the hashes he has a chance of p% to detect a single hash forgery. So 50% ia just an example. Even if the verifier will do half the work (which is way too much work) he will still only get 50% confidence. Hence my initial claim it can't be done. $\endgroup$
    – Meir Maor
    Jul 4 '17 at 8:28

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.