Shoup on Proof of History

For a long time I tried to understand what Proof-of-History brings to the table. What is it useful for? What problem does it solve?

At the beginning of may 2022, Victor Shoup, who is a renowned cryptographer and currently working at DFinity, took a deep dive into Proof of History. He wrote an opinion paper on the subject, which you can find here: Proof of history: what is it good for? He looked at the blog posts and the available documentation, but did not look at the source code. This is understandable from an academic point of view, because the theory should come before the practice.

Back to the Basics

At the beginning of the paper, Shoup makes a nice summary of what decentralized systems are about, namely Safety and Liveness, meaning you cannot cheat, and the protocol won’t stop. This is less difficult to achieve than what is needed for database systems: here you need in addition external consistency. This means that an external user should not be surprised by the way conflicts are resolved.

He also gets into the differences between the Proof of History (PoH) algorithm and the Verifiable Delay Functions (VDFs). Whereas a VDF has a high cost of setting up the proof, the verification is much easier. This is not the case for PoH, because the prover needs to do the same amount of work as the verifier.

The final point he recalls in the basics is the differentiation of permissioned versus unpermissioned systems. Permissioned systems have a central setup that lists all the nodes in the system, like distributed databases. Unpermissioned systems allow anybody to join with a node, and this was the most important feature added by Bitcoin. Finally the Proof of Stake mechanism can be interpreted as one or the other, even though Shoup prefers to put it with the permissioned algorithms. This is because the stake you put down does create a list of nodes that can participate in the consensus.

The need for a universal clock

In order to create this universal clock, Proof of History proposes to create a hash-chain on the prover:

h_(n+1) = sha256( h_n )

But then the prover only sends every qth hash value to the verifier. This reduces the amount of data to be sent over the network. Now the verifier can verify if these values correspond to a correct hash-chain by re-calculating the hashes. In this way, the prover showed that they did some amount of work, and thus some time passed.

Solana says that this universal clock can then be used to make the consensus faster. According to Shoup, this argumentation is flawed: most blockchains do not need a universal clock. And those who need one, do not spend a lot of complexity in setting it up. So Shoup concludes that the universal clock is not a big problem, and that optimizing it with PoH does not bring any advantage.

Conclusion

Of course we need to take into account Shoup’s affiliation with DFinity, a contender to Solana. As such it is not easy to dismiss some of the critiques. Probably the one Solana will attack the most is the fact that Shoup only relied on the whitepaper, the blog posts, and the articles, without going into the source code. But from an academic point of view the whitepaper should contain the most important parts. And you should not need external contributors to prove what you are doing.

Linus Gasser