3
$\begingroup$

Suppose that I have a document and I want to build a proof, for the year of 2020, that this document existed in 2017. I could, for one, use a public blockchain - that is the only method I know for accomplishing this. Is there, though, a more compact and self contained method to achieve the same?

Solution sketch

I pick an inherently sequential hashing algorithm and build an ASIC for it that operates at provably near the thermodynamics limits. I keep "hashing" that document continuously, non-stop, until 2020. Then, at 2020, I publish the resulting HASH^N(document) value. Someone with an equally powerful ASIC will be able to verify my document indeed existed in 2017. The only issue is that it will take him another 3 years to do so. Moreover, if I want to prove that in 2030, a verifier would need 13 years and so on.

$\endgroup$
  • $\begingroup$ Why can't you provide a proof now ? (e.g. using proofofexistence.com ) $\endgroup$ – Ruggero Feb 9 '17 at 17:27
  • $\begingroup$ What is your threat model? What kinds of capabilities does the attacker have? I'm assuming trusted 3rd party is out of the question too. $\endgroup$ – mikeazo Feb 9 '17 at 17:27
  • 1
    $\begingroup$ If you know who should be able to verify this: Give him an commitment on your document now, and only do the unveil at that point in the future. The buzzword "blockchain" might actually not give you what you look for: There is no guarantee that the assumptions, which are essential for the blockchain, are still valid in 2020. And even then, it might not be valid any more in 2030, and someone could erase your proof then. The "permanenet" is quite limited when describing blockchains as "permanent write-only storage". $\endgroup$ – tylo Feb 9 '17 at 17:38
  • $\begingroup$ @tylo Even in the worst case, including the document hash in the block chain ensures distribution to many recipients, not too different from including it in a printed news paper that's widely read. $\endgroup$ – CodesInChaos Feb 9 '17 at 18:04
  • 2
    $\begingroup$ Possibly relevant Q/A from sec.se $\endgroup$ – Ella Rose Feb 9 '17 at 18:37
2
$\begingroup$

This exact issue was handled in great details in this article that you might want to check. In particular, this article explains in detail how their construction can be applied to timestamp documents. Basically, it shows how the methodology you describe can be made efficient for the verifier. The intuition is that rather to hash a chain, the prover will hash the nodes of a graph with some particular structure (a depth-robust graph, to name it). Because of this structure, the following efficient verification procedure can be used:

  • The prover hashes the entire graph
  • The prover computes and sends a Merkle commitment of the entire hash graph (this allows to commit to an arbitrary bit string and open the bits at a given position succinctly, i.e. in time logarithmic in the size of the string)
  • The verifier queries random nodes of the graph; the prover open these nodes and their parents
  • The verifier checks that the openings are correct and that each opened node was correctly hashed from its parents.

Because of the structure of the graph, repeating the last two steps a polylogarithmic number of times is sufficient to ensure that the prover correctly hashed a long chain in the graph; if the hash function is inherently sequential, this proves that he invested some long computation time.

Several alternatives to the above method are possible. To list a few:

  • Proceed exactly as you explained, and add a succinct zero knowledge argument that proves that you did the correct computations. Such a succinct argument can be constructed e.g. using probabilistically checkable proofs in the random oracle model, or from various kinds of knowledge-of-xponent assumption.
  • Use the following nice idea from this article: some designated verifier generates the secret key for an RSA scheme, and sends the public modulus $n$. "Hashing" is simply done by squaring mod $n$ - i.e., the $t$-time function is $f:x \mapsto x^{2^t} \bmod n$. This is expected to be impossible to speed up without the secret key. However, with the secret key, verification is very fast: the verifier simply computes $t' = 2^t \bmod \phi(n)$ and then $x^{t'} \bmod n$, in total time logarithmic in $n$, and checks that he got the same result.
|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Unfortunately anybody knowing the secret key in the last suggestion can fake the proof. So far we don't have a way to generate an appropriate semi-prime without producing the factors in the process. (Even the elaborate key generation ceremony zcash pulled off trusts the generating parties not to collude. $\endgroup$ – CodesInChaos Feb 10 '17 at 8:24
  • $\begingroup$ Yes, it requires to assume that the designated verifier will not collude with the prover. This is clearly less satisfying, but perhaps more practical than the other alternatives I mentioned. $\endgroup$ – Geoffroy Couteau Feb 10 '17 at 10:16
  • $\begingroup$ Both answers are very great so I'm deadlocked and can't pick one... thanks for the knowledge. $\endgroup$ – MaiaVictor Feb 10 '17 at 22:28
1
$\begingroup$

Your "sequential expensive function" approach can be refined in two ways:

  1. Regularly save a checkpoint. Then the verifier can run parallel computations between each checkpoint. So if they have 100 computers they can cut down the time from from 3 years to 11 days.

  2. Use a reversible function that's cheaper to compute in one direction and expensive in the other.

    Squaring modulo a prime (vs square root) or elliptic curve point doubling (vs halving) are two candidates, but I didn't evaluate how much faster the cheap direction is for these. You need to alternate these with some unstructured disturbance (e.g. a blockcipher like permutation) to prevent the attacker from simplifying this repeated function.

The big problem with this approach is ensuring that your ASIC is really the fastest way to compute the function.

|improve this answer|||||
$\endgroup$

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.