Proof of History — Is It a Verifiable Delay Function?

When Victor Shoup writes a paper, I read it. One of his most recent research outputs is [5]:

Proof of History — Is It a Verifiable Delay Function?

When Victor Shoup writes a paper, I read it. One of his most recent research outputs is [5][here]:

It is more of a note than a paper, and aims to provide a critique of proof of history. For this, Victor references the Solana paper and which outlines the usage of proof of history to improve on proof of state. He quotes the Solana paper with [here]:

PoH [proof of history] is used to encode trustless passage of time into a ledger — an append only data structure. When used alongside a consensus algorithm such as Proof of Work (PoW) or Proof of Stake (PoS), PoH can reduce messaging overhead in a Byzantine Fault Tolerant replicated state machine, resulting inn [sic] sub-second finality times

With proof of history, a prover (P) with a starting value of s_0 will aim to create a sequence of values from s_1 to s_N:

This is a hash chain, and only by knowing the previous hash will we be able to compute the next valid hash. If we know the starting value (s_0), we can produce a valid hash chain. With proof-of-history, we generate a value of k, and then compute the hashes of:

For example, if k=5, then the prover will compute s_5, s_10, s_15, and so on, up to s_qk. The prover will not be able to run this in parallel, and must undertake all the iterations up to qk. The Verifier (V) knows s_0, then receives these values, and uses this algorithm to verify the hashes:

In this, case V can parallelise the operation for each of the received values of s, and with k=5, will only need to run five rounds of hash for each of the paralised checks. Overall, for V, there can be q parallel operations, and each has k hash operations, but P will have to compute k.q hashes in sequence. It is thus time-consuming for P to produce the correct hash sequence, but fairly easy for V to check it. For example, if k=100, and q=5000, P has 500,000 hash sequences, while V runs 5,000 parallel operations of 100 hashes for each parallel operation. P thus has a proof of time that it has taken to compute the hashes, and where the time taken will relate to the time taken for each hash operation, and the speed of the hardware.

Verifiable Delay Function (VDF)

Let’s say I want you to do some work, and you show me the result. But, I don’t want to actually do the work, but still, check it. With this, we can use a difficult mathematical calculation that must be done in a certain way, and where there are no shortcuts. One way is to compute:

and where we need to compute g times g time g … for 2^T times. There is no shortcut to parallel processing. We then need to find a way for Peggy (the prover) to prove her work, and Victor (the verifier) to check the work in a simple way.

and where we need to compute g times g time g … for 2^T times. There is no shortcut with parallel processing. We then need to find a way for Peggy (the prover) to prove her work, and Victor (the verifier) to check the work in a simple way.

For this, we can use a Verifiable Delay Function (VDF) where we can prove that a given amount of work has been done by Peggy. Victor can then send Peggy a proof value, and for her to compute a result which verifies the work has been done, without Victor needing to do the work.

VDFs were first proposed by Dan Bohen et al [4], but it was Pietrzak [1] and Wesolowski [2] who then proposed the repeated squaring function to define the workload. In this article, we will implement the Wesolowski method:

In this case, Victor would like Peggy to do is defined by a time value (T), a base (x) and a random prime number (N):

This work can only be done in a sequential way, and where Peggy cannot implement a parallel processing method to reduce the time to compute. So how does Victor prove that Peggy has done the work, without actually computing the value of y. For this, Victor sends a challenge value of L. Peggy then computes:

This is much faster than computing the actual work that Peggy has done. The value of val then gives a quotient (q) and a remainder (r). Peggy then computes:

Peggy then sends y (the work value) and π. Victor computes:

and checks that the following is the same as the value of y that Peggy sent:

If the values are the same, Victor has proven that Peggy has computed the right value — and undertaken the work — without Victor having to compute the value that Peggy computed. Victor does know that the answer is correct, though.

The coding is [here]:

import sys
import hashlib
import libnum
# import hashlib
def do_work(x,T,N):
  for i in range(1,T):
    po=pow(2,T,N)
  return(pow(x,po,N))x=3
T=8
bits=24
L=18if (len(sys.argv)>1):
	x=int(sys.argv[1])if (len(sys.argv)>2):
	T=int(sys.argv[2])if (len(sys.argv)>3):
	bits=int(sys.argv[3])if (len(sys.argv)>4):
	L=int(sys.argv[4])if (T>100): T=100
if (x>100): x=100N=libnum.generate_prime(bits)
x=3print (f"x={x}, T={T}, N={N}")print (f"Challenge. L={L}")y=do_work(x,T,N)
q=pow(2,T,N)//L
r=pow(2,T,N)%L
print (f"q={q}")
print (f"r={r}")pi=pow(x,q,N)print (f"\nProver computes y={y}")
print (f"Prover send pi={pi} and y={y}")r=pow(2,T,L)
ynew=(pow(pi,L,N)*pow(x,r,N))%N
print (f"\nVerifier computes r={r}")
print (f"Verifier computes y={ynew}")if (y==ynew):
  print("\nProver has done the work")

And here is a sample run [here]:

x=3, T=10, N=254965212704684994675822688735349549753
Challenge. L=116
q=8
r=96Prover computes y=32458177501682064707796249637766588138
Prover send pi=6561 and y=32458177501682064707796249637766588138Verifier computes r=96
Verifier computes y=32458177501682064707796249637766588138Prover has done the work

In many areas of blockchain we need to prove that entity can perform work for us, and for this to require a given amount of computation. A VDF is a perfect way for this to happen, but for the verifier to not have to do the actual work. In this way, we have a Proof-of-Work method, and which can be used to prove that nodes are willing to invest their workload in creating a reliable consensus. IOTA is one infrastructure that is implementing VDF for their infrastructure [here][3]:

Victor’s Critique of Proof of History

Victor outlines from [here] that a leader node in a consensus network produces a proof of history that integers a sequence of transactions. This is then transmitted to validators to prove the proof. At times, P signs the proof of history, and then each V adds their signature to represent one vote on its likely validity. Each V has a stake in the system and the weighting of their votes to weighted by the size of their stake. On a majority vote of Vs, the sequence of transactions will be considered as finalised. If P becomes unresponsive, the Vs elect a new leader. When a V is not voting correctly, the system implements slashing (confiscation of stake).

Victor critiques this methodology by outlining that it lacks details on the actual operation of the protocol, and lacks the assessment of communication overhead, latency, theoughput and computational complexity.

He then outlines a quote for the Solana clock:

Today’s blockchain-based networks have a clock problem . . . POH [proof of history] is a solution to the clock problem . . .

Whereas other blockchains require validators to talk to one another in order to agree that time has passed, each Solana validator maintains its own clock by encoding the passage of time in a simple SHA-256, sequential-hashing verifiable delay function (VDF).

In this we see that the delay function is controlled by a SHA-256 hash operation, rather than the square function used in [1,2].

Conclusions

In the end, Victor is critical of the proof-of-history method proposed by Solana, especially since the complexity of the consensus mechanism could increase the computational requirements, and that it has little effect on improvements to the communication complexity. But the most significant statement is:

Proof of history is not really a veriﬁable delay function (VDF), as proof-of-history veriﬁcation is computationally expensive, unlike veriﬁcation in a true VDF.

And, so, proof of history is possibly not actually a VDF.

Reference

[1] Pietrzak, K. (2018). Simple verifiable delay functions. In 10th innovations in theoretical computer science conference (itcs 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[2] Wesolowski, B. (2019, May). Efficient verifiable delay functions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques (pp. 379–407). Springer, Cham.

[3] Attias, V., Vigneri, L., & Dimitrov, V. (2020). Implementation study of two verifiable delay functions. Cryptology ePrint Archive.

[4] Boneh, D., Bonneau, J., Bünz, B., & Fisch, B. (2018, August). Verifiable delay functions. In Annual international cryptology conference (pp. 757–788). Springer, Cham.

[5] Shoup, V. (2022). Proof of history: what is it good for? [here].