Zero Knowledge Proof using hash chains - Is there a flaw in the algorithm? I came across this blog post http://blog.stratumn.com/zkp-hash-chains/ which provides a Protocol to prove in zero-knowledge that an integer (such as age or balance) is greater than a known threshold.

It is based on this paper: Verifiable Auctions for Online Ad Exchanges

The protocol is as follows:


A trusted central document authority that provides proof services. P has requested a secret S from this authority, for use in proving her age. The authority assigns a secret (256 bit) S to P. Let’s say P's (S) is:

0000000000000000000000000000000027ae41e4649b934ca495991b7852b855

The Authority then calculates a hash-chain one link greater than P's age:

EncryptedAge=HASH^{ActualAge+1} (S)

P also computes

Proof=HASH ^ {1+ActualAge−AgeToProve} (S)

P then sends to the other party: 


The Authority’s signed Proving Kit (which contains her EncryptedAge )
The Proof she calculated

The party that needs to verify P's age does:


Extracts P's EncryptedAge from the Authority’s message
Computes:

VerifiedAge=HASH ^ {AgeToProve} (Proof)

Compares VerifiedAge == EncryptedAge. If equal then age is higher than age to verify.



Here is the code in JavaScript to test above protocol: https://repl.it/repls/SmartOccasionalQueries

I think there is a flaw in the protocol, it occurs in this step:

Proof=HASH ^ {1+ActualAge−AgeToProve} (S)


When 1+ActualAge is equal to AgeToProve, then hash is not applied on S. 


It ends up sending the secret as Proof. S should have been maintained as secret.
It ends up computing that verified Age == encrypted age, where as it is not, example: https://repl.it/repls/OrderlyPalegreenScriptinglanguages


The below is example from the blog, with Age = 19, and AgeToProof = 20:
In fact, it gets even worse if 1+ActualAge is less than AgeToProve, since in that case P would have to find a preimage for the hash in step 3!

But (even without actually following any of your links) I would guess that there's an implicit  assumption that a legitimate P will not even attempt to run the protocol unless ActualAge ≥ AgeToProve, since proving that they're not quite old enough doesn't gain them anything anyway.

Of course, a malicious P could do whatever they want, including accidentally (or deliberately!) revealing the secret.  But in general, we don't really care if a malicious party will do something that only hurts themselves.



OK, let me extend my answer after reading the linked blog post and article.

First of all, note that the blog post and the article actually describe different protocols with different participants and goals.  Specifically, the protocol described in the blog post has three participants:


a prover P who wants to prove to the querier Q that their age $a$ (a non-negative integer number of years) meets or exceeds some minimum limit $q \ge 0$, without revealing how much older than the minimum limit they are;
a querier Q who wants to know whether P is at least $q$ years old; and
a government authority A that knows how old P is, is trusted by both P and Q, and can sign messages in such a way that Q can verify that they come from A, even if relayed by P.


In the protocol describe in the article, however, the authority A does not exist!  Instead, in that protocol, P simply picks an arbitrary (non-negative integer) number $x$ and sends to Q a commitment to that number, such that they can later both:


prove to Q that the number $x$ they picked is greater than or equal to some threshold $q \ge 0$, without revealing how much greater it is; and
optionally, to release the exact value of $x$ and prove that this is indeed the number that they earlier committed to.


The reason this distinction matters is because the protocol outlined in the blog post actually contains some vestigial features (specifically, the way the initial seed for the hash chain is selected) that aren't required for the scenario described in it, and which could be left out to simplify the protocol!  Those features are only needed if we want P to be able to also optionally prove their exact age to Q.



To illustrate how the protocol is supposed to work, let me first start by describing a simpler protocol for the three-party case.  Specifically, instead of all this messing around with hash chains, the authority A could simply issue the prover P with a bunch of separate signed "tickets", each stating that:


  Authority A hereby certifies that P is at least $x$ years old.


where $x$ ranges from zero to P's actual age $a$.  Then, to prove that they're at least $q$ years old, P simply needs to select the ticket with $x = q$ and reveal it.

The problem with this scheme is that it requires A to sign a separate ticker for every year of P's life, and for P to store all of them.  (Honestly, that might not be much of a problem in practice, since in real life $a$ rarely exceeds 100.  But it could be a problem if we, say, decided to count P's age in days or even seconds instead of years.)  It would be kind of nice if we could have a scheme where:


the authority A could send P a single ticket stating their actual age;
there was a way for P (or anybody else!) to decrement the age on the ticket, i.e. to take a valid ticket that says the P is at least $x$ years old, and obtain a valid ticket stating that P is at least $x-1$ years old;
there was no way for P or anybody else to reverse this operation, i.e. to increment the age on the ticket and have it still accepted as valid; and
the authority A could simply sign a single ticket stating that "P is at least 0 years old", knowing that anybody who applies the decrement operation to any other valid ticket (and only to a valid ticket!) for P's age enough times will eventually obtain the signed ticket and be able to verify the signature.


One way to achieve that is to include an arbitrary string of, say, 256 bits on each ticket, and have the decrement operation include hashing that string with SHA-256 and replacing it with the hash output.  That is, A could send P a ticket stating:


  Authority A hereby certifies that P is at least $a$ years old.  Hash: $s$.


and a signature for the ($a$ times decremented) ticket:


  Authority A hereby certifies that P is at least 0 years old.  Hash: $H^a(s)$.


where $s$ is a random 256-bit string and $H^a$ denotes SHA-256 iterated $a$ times.

When P wants to prove to Q that they are at least $q \le a$ years old, they can then apply the decrement operation $a-q$ times to the original ticket sent by A to generate a ticket stating:


  Authority A hereby certifies that P is at least $q$ years old.  Hash: $H^{a-q}(s)$.


and send it to Q along with the signature for the "at least 0 years old" ticket that they received from A.  And Q, in turn, can apply the same decrement operation $q$ more times to re-derive the "at least 0 years old" ticket, and then verify that it matched A's signature.

The reason this works is because SHA-256 is (believed to be) preimage resistant.  This means that, given a random string $s$, it's easy for anybody to calculate SHA-256($s$), but effectively impossible to find any string $r$ such that SHA-256($r$) = $s$.  Thus, given the original ticket stating that they are (at least) $a$ years old (with the random hash $s$), P can easily obtain a valid ticket for any age $q \le a$, but not for any age greater than $a$.



OK, but then why does the protocol described in the blog post (and in the VEX paper) have the authority A first choose a random "seed" string $r$, and then use $s$ = SHA-256($r$) as the hash on the first ticket sent to P?

Well, one reason why one might do that is to make sure that the hash on the first ticket really looks like a normal SHA-256 output.  Sure, a random 256 bit string should be indistinguishable from a random SHA-256 output anyway, but we all know that in reality, random number generators can have subtle bugs that are often hard to test for.  Hashing the initial random value gives a little extra assurance that nobody can find any way to distinguish the original ticket stating P's true age from any decremented derivatives of it.

But that doesn't mean that A would have to ever reveal their original random value $r$ to P.  And indeed, the protocol as described above works perfectly well without it.  So why, then, does the VEX paper (and the blog post based on it) seem to suggest revealing this $r$ to P?  And doesn't doing so let P lie about their age by one year?

I'll answer the second question first.  Knowing $r$ will not let P lie about their age, provided that:


the seed $r$ is deliberately chosen not to be a possible SHA-256 output, and
the querier Q always verifies that the hash on the ticket is a possible SHA-256 output before accepting it as a proof of age.


OK, but what good does revealing $r$ to P do?  Well, it allows P to also choose to reveal (and prove!) their exact age to Q by disclosing $r$.  Since, as noted above, $r$ must not look like a valid SHA-256 output, this means that Q can be sure that it's indeed the first value in the hash chain leading down to the "at least 0 year old" hash signed by A, and that therefore $s$ = SHA-256($r$) must be the hash corresponding to P's true age (at the time A generated the signature, anyway).

Basically, without this extra feature, P could always decide to lie about being younger than they actually are, and there would be no way for Q to detect that, at least not without extra infromation from A.

For the age checking protocol described in the blog post, this isn't really a particularly important feature.  After all, if P needed to be able to prove their exact age, they could just get A to sign a separate message stating it. 

However, for the verifiable auction protocol described in the original VEX paper it is essential, because in that protocol there is no central authority A, and the provers instead get to freely choose the value they want to commit to.  Without a way to reveal and verify the actual committed value at some point, the provers could just pick some huge value (say, one billion) at the start of the auction, and only later decide which "at least" queries they actually want to answer affirmatively.



Anyway, it turns out that, while the protocol as designed (and reasonably interpreted) is sound as far as I can tell, the JS implementations linked from the blog post and from your question are both buggy.

In fact, both of them have two bugs: one of that allows the prover to generate a bogus proof for a minimum age one year greater than their true age (revealing their secret seed in the process), and another bug that allows the verifier to accept it. 

The first bug is simply that the prover should never attempt to generate a proof for a minimum age that they don't actually meet.  A minimal fix to the code linked from the blog post would be to add the following like to the beginning of the challenge() function:

function challenge(age, age_to_prove) {
  if (age &lt; age_to_prove) return null;  // &lt;- ADD THIS LINE!
  Q = hashchain(S, Number(age)+1-Number(age_to_prove))
  document.getElementById("display_Q").innerHTML = Q
  return Q
}


A similar bug is also present in the prove() function in your code, and can be fixed the same way.

The second bug is that, even if the prover (deliberately or by mistake) tries to use their initial hash chain seed as a proof of age, the prover must not accept it.  The blog post does correctly note this in the "Soundness" section:


  The exception to this is for $AgeToProve=ActualAge+1$, in which case Paula could just send $S$. However, as the format of $S$ is publicly known, a watchful verifier would detect the fraud [...]


but the linked JS code doesn't actually include such a check.  As a result, the verifier in the demo will happily accept the seed $S$ as bogus proof of age (and, due to the first bug, the prover will in fact respond with the seed if asked for a proof of a minimum age greater than their true age).

The blog post also uses a rather unfortunate choice for the format of the initial secret seed: 128 zero bits followed by 128 random bits, for a total of 256 bits.  The reason this choice is bad is that it precisely matches the output bit length of SHA-256, making it theoretically possible (even if extremely unlikely) for a genuine SHA-256 output to match the format of the secret seeds.  Literally any other choice of seed length (including just leaving out the 128 zero bits) would've avoided this issue.

Anyway, sticking with the poorly chosen seed format, a basic fix for the verify() function would be to add something like the following check at the top of it:

if (Q.length != 64 || Q.substr(0,32) == '00000000000000000000000000000000') {
  // this does not look like an SHA-256 output; verification failed!
  return null;
}


Of course, if the format of the secret seed was changed so that it wasn't exactly 256 bits (= 64 hex digits) long, then the .substr() check could be removed.  And also, of course, if the protocol was simplified (at the cost of removing the option for exact age verification) so that the prover never learned the secret seed to begin with, then this check would not even be necessary.