-
-
Published
Linked with GitHub
# Solana without Proof of History
## Solana's proof of history
Proof of history is a mechanism that measure elapsed time in Solana. The function computed is similar to a VDF: It is a sha256 hash chain. While it is not efficiently verifiable (the verification takes the same resources as the computation, but it's parallelizable), for practical purposes we can consider it like a VDF: It takes an input, computes a deterministic output based on it, and anyone can verify that this output is correct. Further, it seems unlikely that hash chains can be parallelized in a meaningful way, so it takes a certain amount of "wall clock time" to compute the function.
Like many PoS chains Solana has a deterministic block proposer schedule. Whenever a proposer creates a block, they have to include a "PoH" proof that the 400ms block delay has elapsed. Sometimes block proposers don't show up, meaning the next proposer in the schedule has to create a block and "skip" over the missed slot; in that case they would have to provide an 800ms PoH; more generally, to skip $k$ slots, an $400\mathrm{ms} \cdot (k+1)$ PoH has to be computed.
In practice, this has the effect that blocks are spaced by 400ms. Concretely, if block proposer $n$ shows up on time, proposer $n+1$ cannot create a concurrent block (that skips slot $n$) without computing a PoH at twice the speed.
## How other chains solve this
The common solution is to assign a fixed time to slots. So in Solana's case, if slot $n$ is at 12 noon, then $n+1$ can only be proposed at 12:00:00.40.
This is enforced by application of the fork choice rule: No block that is ahead of its time will be considered for the fork choice rule, and thus, for voting. (In Solana's terms, where there is no fork choice rule, this simply would simply mean that nodes would not consider block $n+1$ for voting until 12:00:00.40).
The challenge with this algorithm is that it only works if clocks are well synchronized. In practice, NTP does a good job at synchronizing clocks within 10ms or so. But under adversarial conditions, it is indeed harder to keep this synchronization. This is Solana's main argument why simple synchronized clocks are not enough, and the Proof-of-History construction is necessary. I think this is a valid argument; while I believe that time sync protocols can be hardened, that in itself is also a difficult task.
## An alternative that uses the chain itself to synchronize clocks
Here I make another suggestion for this which I believe has the same properties as the Proof of History construction, without employing a delay computation. The background is that we don't actually need to fix an absolute time for blocks. We can instead use the last consensus block's time as a reference.
Here is how it works. Let's say the last block in consensus is at height $n$ and was proposed at time $t$; in consensus means that voting on this block is complete and has confirmed the block. Note that $t$ is not the time that consensus is achieved, but the time at which the block was first received by the node. Each node may have a slightly different idea of $t$.
From there, we fix the times for the slots $n+k$ as $t+400\mathrm{ms} \cdot k$. This means that a proposal for slot $n+k$ will not be considered for any vote until time $t+400\mathrm{ms} \cdot k$; before that time, if we receive a proposal for slot $n+k$, we will simply store it for later and not vote on it yet.
The concrete implication is that the leader for slot $n+1$ has at least 400ms to make their proposal; Assuming that their block will propagate as well as the block of slot $n+2$, it will beat that block as long as it is sent before time $t+800\mathrm{ms}$. This is the same property that PoH would be enforcing between the blocks.