Is it possible to prove the age of a document? 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.
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.