Tromp's idea, I think, was something like this. (Or it may be I'm inventing something different under the delusion this was his idea, but anyhow.)
From an n-bit string x, you apply some cryptographic bijective function F1 to reach another y=F1(x). Or, you could instead have used F2, or F3.
This defines a directed graph with 2^n vertices and each outvalence=3. Now, to prove you've done work, you say "starting from the n-bit string 0101101...1, apply functions 1,3,2,3,3,2,2,2,1,...,2 in succession, to return to start point." Where the whole sentence is O(n) characters long. Anybody can verify or deny the truth of your sentence very quickly. But it is not easy to find true sentences of this nature. Further, if the start point is chosen by somebody else (not you) then you will have even more difficulty finding true sentences of this nature.