Why Permissionless Consensus Needs a Physical Global Clock
This note shares a few views on the role of Proof-of-X (PoX) in permissionless consensus. Among the three PoX schemes discussed here, PoW and PoH each construct a physical clock, used to space the blocks apart in time so that they appear less quickly. PoS cannot construct a clock, so a later section explains how Ethereum imports one from the outside. Permissionless consensus and the well-known blockchains discussed here share almost the same assumptions, so the rest of this note does not separate the two.
Distributed consensus builds a logical clock. The logical clock is the order in which events happen in a distributed system. It is also the order in which the nodes hold that events should be processed. Lamport showed that a meaningful clock in a distributed system is, in essence, this order. A physical clock is only one way to construct that order.
Lamport first assumed a closed system. Later the model assumed that nodes may be malicious, which is the Byzantine Generals Problem. FLP gives a more basic limit. In an asynchronous network, once a single process may fail, no deterministic protocol is correct. In other words, asking a protocol to terminate under asynchrony is the same as assuming that no node ever fails. The root of the proof is that a node cannot tell a slow node apart from a faulty one. After the FLP impossibility, work on the Byzantine Generals Problem split into two lines. One line assumes a partially synchronous network. The other line introduces randomness to force termination in protocols that could otherwise hang. Both lines later became known as Byzantine Fault Tolerant (BFT) protocols.
However, even though a partially synchronous network lets a node introduce its own local physical clock, it does not need to construct a global clock. Permissionless consensus does need a global physical clock to guide consensus. This need comes from a basic difference between the permissionless assumption and the assumption behind BFT protocols. The rest of this note explains that difference step by step.
Each permissionless consensus protocol constructs its global clock differently. Yet these clocks are essential for handling the problems that the permissionless assumption creates. The permissionless assumption means openness, and openness means the Sybil attack. This note explains how Bitcoin’s Proof of Work (PoW) and Solana’s early Proof of History (PoH) construct a physical clock. Besides constructing a physical clock, PoW also provides Sybil resistance along the way. PoS cannot construct a clock. It can only provide Sybil resistance. We then ask what Ethereum does on top of that.
Logical Clocks
In 1978 Lamport wrote “Time, Clocks, and the Ordering of Events in a Distributed System.” The paper set the intuition for the whole field. What matters in a distributed system is not physical time but the happened-before relation between events. Lamport proposed the logical clock to express order, with no need to synchronize physical clocks, which are not reliable. To construct such a clock for all nodes in a distributed setting, we must first solve the problem that FLP raised.
FLP (Fischer–Lynch–Paterson, 1985) says the following. In an asynchronous network, under a model that requires deterministic commit, no protocol is correct once a single process may fail. The reason is plain. You cannot tell whether a node is slow or dead. When a message is late, you can never decide whether the other side has crashed or the network has simply stalled.
There are two ways out of FLP.
Partial synchrony (DLS, 1988). The model assumes that the network eventually stabilizes and becomes synchronous. A node can then use its local physical clock to set timeouts, catch the moment the network enters synchrony, and drive the protocol forward. The physical clock enters consensus through this path.
Randomization (Ben-Or, 1983, and the later common coin). Coin tossing breaks the ability of the adversary in an asynchronous network to hold the protocol in a deadlock. No physical clock is needed to reach consensus under asynchrony. The coin breaks the adversary’s ability to keep the system forever bivalent, that is, undecided between two values. Termination then holds with probability one. The coin only provides a shared bit that the adversary cannot predict and cannot bias.
There are two definitions of partial synchrony, both from the DLS paper. In the first, there is an unknown but fixed delay bound $\Delta$. The bound always holds, but the protocol does not know its value. In the second, there is a known $\Delta$, but it holds only after some unknown time called the Global Stabilization Time (GST). Before GST the network is fully asynchronous. Later work engineered this idea by assuming that synchronous and asynchronous periods alternate again and again. A partially synchronous protocol introduces timeouts. In essence, the protocol bets that the network will eventually enter, or already sits in, that bounded phase, so that the protocol can keep liveness. In partially synchronous BFT, the physical clock is only a local and relative liveness tool. This tool has nothing to do with safety.
Local Clocks Cannot Solve Permissionless Consensus
Partially synchronous BFT, or permissioned consensus even if the term is not precise, needs only a local physical clock. From the viewpoint of State Machine Replication (SMR), the system receives a request, replicates it in the same order across all replicas, and reports back to the user through a reply interface. The typical method for this replication is the rotating leader. Each round begins by selecting a leader. The leader broadcasts a block that contains several requests. The other nodes vote. Once a node collects a quorum, it proceeds to the next round. When a node receives the messages, it resets its local physical clock. When the local clock times out, the node sends a timeout message. In the same way, after a node collects enough timeout messages, the protocol changes to the next leader.
The protocol runs in this message-driven way. Here is the key point. A quorum, meaning $n-f$ messages, must contain at least $n-2f$ messages from honest nodes. So forming a quorum is itself a synchronization mechanism. The protocol keeps its own beat through messages. A formed quorum means that $n-2f$ honest nodes agree on something, at least at the moment they sent their messages. For BFT this agreement is enough. The pacemaker, or a family of view-synchronization protocols, then supplies the liveness that the protocol needs.
However, this BFT message-driven approach cannot survive under the permissionless assumption. Andrew Lewis-Pye and Tim Roughgarden, in “Permissionless Consensus,” give a layered definition of the permissionless assumption. The definition covers almost every assumption used by real permissionless consensus protocols, and it grounds their design principles. Here we focus on the fully permissionless model, which matches Bitcoin’s assumption. A node does not know the identities of the other nodes in the system. It can only verify their signatures. It does not even know how many nodes there are in total, because anyone can join or leave at will, which is an open system. Any node inside the system can also forge identities, which is the Sybil attack.
Because of this, the common tricks of BFT protocols fail one by one. The rotating leader first needs a fixed list of nodes, given by a fixed-system assumption, and the permissionless assumption does not support such a list. The quorum intersection that guarantees safety relies on each node knowing how many nodes the system contains. The message-driven idea relies on the same knowledge, and an open system does not support it. If one wants to use a common coin, it requires secret sharing inside a system with a fixed and known number of nodes, which is also out of reach.
So the permissionless assumption does not support the message-driven mechanism that BFT uses, the one that counts messages and needs no global clock. Counting messages is exactly how BFT keeps its own beat, and now that beat is gone. To build permissionless consensus, we still want to select a leader at a suitable time and let it produce a block. The problem comes down to two questions. How is the leader selected? After one is selected, how long until the next leader produces a block? The first question is Sybil resistance. The second question can only be answered by a physical clock.
Proof of Work Provides Both a Physical Global Clock and Sybil Resistance
Satoshi Nakamoto wrote “A Peer-to-Peer Electronic Cash System.” Several people had proposed the idea of PoW before him, but using Nakamoto consensus as the fork-choice rule was Nakamoto’s contribution, and for this he gets the credit.
PoW does both of the above at once.
Sybil resistance. The permissionless assumption admits malicious nodes, and there is no BFT-style message-driven or view-change machinery to protect the protocol. You must prevent any node from sending messages at will, such as proposing a block. So PoW sets up a hash lottery. To produce a block, a node must first solve a puzzle that is hard to compute but that other nodes can verify in an instant. Your influence over block production is proportional to your hash power.
Leader selection with a (rough) fixed time interval. The same act of hashing computes both who the next leader is and how long until the next leader appears.
This leader selection carries one essential requirement. In a probabilistic sense, after one block is produced, the next block, and so the next leader, must not appear right away for some interval of time. Blocks must be spaced out in time. They cannot appear one right after another. To be more specific, PoW probabilistically pulls the average block interval far above the network propagation delay, and this spacing bears directly on the safety of Nakamoto consensus.
Nakamoto consensus has two rules.
The explicit fork-choice rule. This is the longest-chain rule. A miner extends whichever chain is heaviest.
The implicit commitment rule. This rule is hidden inside the fork-choice rule. The white paper only states, in vague terms, that a deeper block is harder to roll back. Later the Bitcoin Backbone Protocol formalized this idea as the common-prefix property.
Why does spacing the blocks relate to safety? Because spaced block production gives the nodes a window to synchronize with one another. A real system that wants to reach the optimal resilience defined in Nakamoto consensus must make all honest nodes converge to the same longest chain. Such convergence is of course ideal, but we should try hard to reach it. This point differs from BFT protocols. In BFT, the $n-f$ quorum only needs to guarantee that at least $n-2f$ honest nodes see the same thing, and that is enough. The optimal resilience that Nakamoto consensus asks for corresponds to all honest nodes being perfectly synchronized.
The reason for this correspondence is as follows. After one honest miner produces a block, it takes a propagation delay before the whole network learns of it. During that delay, other honest miners are still doing PoW on what each of them believes is the longest chain. So honest mining power forks against itself and wastes effort. Adversarial power, whether viewed from the model assumption or from a real system, can avoid forking against itself. As a result, worse synchronization, and faster block production, means weaker effective honest power. In other words, the block spacing is what holds down this self-forking. The larger the spacing, the more the honest nodes can converge to the same chain before the next block arrives. This problem has been studied widely, with asymptotic bounds under various assumptions and with numerical bounds.
So PoW lays down a sequence of ticks across the whole network. A leader proposes a block according to these ticks, and the blocks are then chained into an order by the previous-block hash. Once in a while two ticks are pressed almost at the same time, and the next tick vindicates one of them. Nakamoto called PoW a timestamp server.
There is more. In PoW, hash power is consumed over time at a bounded rate, the hash rate. So the act of Sybil resistance itself defines the passage of time. In Bitcoin, Sybil resistance and the global physical clock are guaranteed by one and the same mechanism.
Proof of Stake Provides Only Sybil Resistance and Must Import an External Clock
Ethereum is a different case. After the switch from PoW to PoS, that rough global physical clock no longer exists. Yet Ethereum introduces a stricter clock instead. PoW provides a tick clock that emerges by probability, while Ethereum uses NTP to make it stricter. Ethereum requires every node to synchronize with a global clock and to define timestamps by that clock. Any message whose node time differs from the global timestamp by more than a threshold is ignored. This section explains why Ethereum needs such a clock. The scheme and the strictness of the clock depend on Ethereum’s own design, but the reason for introducing the clock is similar to the Bitcoin case above.
Let us first see how Ethereum works today. A node must deposit, or stake, to gain the right to produce blocks. Ether is scarce, so Ethereum naturally uses PoS to provide Sybil resistance. Moreover, the act of staking gives an Ethereum node information about the other nodes, such as their number. For this reason, the paper “Permissionless Consensus” places Ethereum’s assumption in a category different from Bitcoin’s. Most notably, with the number of nodes known, Ethereum can even choose to use a BFT protocol directly as its consensus. But pure BFT places a high demand on nodes staying online, and it cannot scale.
A common way to make a BFT protocol scale is to use a sub-committee. As long as the sub-committee is random and unpredictable, the adversary is not strong enough to target it, and the small size of the committee can be used to reach excellent complexity. One key problem with a sub-committee is how the nodes outside it can still reliably learn about, and even partly take part in, the consensus process, while still keeping low complexity. Algorand defined and solved this problem.
Ethereum also uses the sub-committee idea. Yet Algorand’s assumptions differ a great deal from the real system that Ethereum faces. The clearest difference is that Ethereum does not require all honest nodes to stay online, while Algorand does. So Ethereum cannot use a pure BFT method for consensus. Instead they built a method that combines GHOST with a BFT protocol. Ethereum regards itself as the only entity that both achieves deterministic finality and successfully uses GHOST, a loose but effective mechanism.
To be more specific, because the nodes know the number of nodes in the network, Ethereum still lets all nodes vote to guarantee deterministic finality. To support a large number of nodes, Ethereum makes the interval between two full votes large, and calls such a span an epoch. It then divides each epoch into 32 slots. Each slot selects one node at random to produce a block. The target of the once-per-epoch vote can be thought of as something from the previous epoch, called a checkpoint, which we discuss below. A natural question is how the blocks between one slot and the next are linked. Ethereum uses GHOST and splits all nodes at random into 32 parts in each epoch, with each part responsible for the vote of one slot. To be more specific, each node’s single vote does two things at once. At the LMD-GHOST level, it votes for the head block that the node sees, so Ethereum designs the weight of the fork-choice rule to be defined by the number of votes, while the weight of each vote is defined by the stake of the voting node. At the FFG level, it votes for the checkpoint on the current epoch boundary, with the last justified checkpoint as the source.
The role of this mechanism is the following. When the network is not good, or when the slot has many malicious nodes, honest nodes disagree more about the head that LMD-GHOST selects, but block production does not stop. Ethereum does not rely on LMD-GHOST for safety either. Furthermore, the checkpoint is the block on each epoch boundary, that is, the first slot, and the votes accumulated within an epoch justify it and then finalize it. Because every block carries a unique previous hash, once this checkpoint is committed, the corresponding epoch and all blocks before it are committed along with it. Safety is the job of this layer.
Similar to Bitcoin, within each epoch the nodes must use LMD-GHOST to decide which block is the head of the blockchain, so it is necessary to keep most honest nodes in agreement about the head. To do this, one again needs a long enough physical clock, or a sequence of ticks, to space the blocks apart, and this is exactly why Ethereum uses NTP. Unlike Bitcoin, which generously sets the block interval to ten minutes, Ethereum sets the block interval to 12 seconds and leaves the first 4 seconds for block synchronization. Four seconds is enough, because Ethereum does not rely on GHOST for safety. Conversely, when the block interval is set too small, the chain that GHOST maintains may stay split and fail to converge. At that point even the checkpoint splits, no checkpoint can collect a quorum of votes, and the system falls into disorder and stalls.
In summary, this global clock does several things. It locates which slot we are in, and so who should vote now. It decides by timestamp whether we should move to the next slot. It gives LMD-GHOST a strongly synchronized point and tells the nodes when, at the 4-second mark, to count the GHOST weights, where the 4-second parameter exists to keep most honest nodes in agreement about the head. And it skips an absent proposer, by a timeout against the global clock.
Solana’s Proof of History and Proof of Stake
Solana has too many moving parts. First, it has PoS and Proof of History (PoH). PoS prevents the Sybil attack and does leader selection, while PoH does something similar to PoW providing a block interval. PoH builds a continuous chain of SHA-256 hashes, feeding the previous output in as the next input without stopping. Generation is serial, single-core, and not parallelizable. Verification can be parallel, but the total work is still not negligible. Because a single core can compute only a bounded number of hashes per second, computing $N$ hashes proves that at least a certain amount of real time has passed. Strictly speaking, PoH is a fake VDF. A true VDF must satisfy three properties: a serial computation delay, a unique output, and succinct verification. PoH satisfies the first two but not the third. Its verification is fast only because it is parallelizable. The total work is still large, and there is no succinct proof. Solana itself admits in GitHub issue #388 that the wording was imprecise, and some have noted that a SHA-256 hash chain is closer to a proof of sequential work than to a VDF.
These two parts, PoH and PoS, can on their own achieve an effect similar to Bitcoin consensus. Leader selection is weighted by stake, chosen at random in advance, and announced in advance. The leader on duty must compute a string of PoH inside its own block, starting from the previous block’s hash, which forces a leader selection with a time interval. If you try to cut corners, skip another node’s slot, and produce a block early, the PoH tick count will not line up, and a verifier rejects it the moment it checks. To reach consensus, one only needs to add one more module: let the fork-choice rule go by the stake weight of the node that produced the block. This choice is natural and much like Bitcoin, except that Bitcoin takes chain length as the object of the fork-choice rule, while Solana can take the proposer’s stake weight as the object.
Yet the result is bad. Solana then becomes almost no different from Bitcoin: it has no deterministic finality, and it still must keep block production fairly slow. Making the fork-choice rule go by stake weight is itself a poor choice. First, the same stake can propose several blocks. Second, a single proposer’s stake is a low-value signal, and placing the fork choice on a comparison of two proposers’ stakes is as poor as the fork-choice rule of Nakamoto consensus. Solana is even worse than Bitcoin here. Bitcoin can guarantee, in a probabilistic sense, that the chain will keep producing blocks, while Solana’s PoH can only prove to the network that this proposer truly waited this long and computed this much before sending this block. But what if this proposer goes offline and stops producing blocks? Does the next leader simply wait, or does it set a local timeout and skip the missing one? These problems are easy to solve in a system implementation: the next leader skips once its local timeout fires and computes the PoH of the skipped slots itself. But they are problems that the protocol does not face directly, and the real source of this liveness can only be a local timeout, not PoH itself.
To get deterministic finality, Solana also makes the fork-choice rule vote-based, with the weight of a vote again based on stake. A node in Solana also votes once after it sees a block. The difference from Ethereum is this. Ethereum only treats the votes cast within a slot as weights, while Solana goes one step further and directly counts the number of votes. When the count passes a quorum, it calls the block optimistically confirmed. This optimistic rule is one source of Solana’s fast commitment, but true finalization still needs 32 successor blocks. Later block production then follows down this quorum-confirmed fork with the heaviest vote count, while each block still uses only the previous hash to point to its direct parent.
Once the quorum is the fork-choice rule, there must be a rule for switching safely to another fork. Suppose a new block conflicts with a block that a quorum has already committed. In theory, the new block must also carry a quorum of existing votes before a switch to it is safe. Yet Solana sets this threshold at only 38 percent, that is, one third plus a buffer of about 4.66 percent. Beyond that, it allows a switch to the new block’s fork. The meaning is that rolling back an optimistically confirmed block requires at least about 4.66 percent of the stake to commit a slashable offense. Here Solana differs clearly from Ethereum. Solana thinks that having 4.66 percent of nodes equivocate is already a serious matter, and in a real environment it truly is, while Ethereum would consider such low resilience unworkable.
Solana often advertises high throughput, low latency, and low fees, so Solana is formidable, the highest-performing of the high-performance public chains. But the performance often does not come from the protocol. It comes from specific system design, parameters, and choices. For example, there are several reasons Solana is fast. One is that the network has few nodes, around a thousand today, and running distributed consensus on a small network is fast by nature. Another is that Solana uses many simplified rules and ignores the consequences they may bring. For example, it uses erasure coding to cut the cost of broadcast, but it does no fault tolerance. It claims that it needs no mempool and so need not broadcast transactions, but only because PoS-based leader selection can be predicted in advance, and as for censorship, it refuses to deal with it. It uses no adaptive fee mechanism, but instead keeps a low fee across all time ranges. Someone will surely ask how the fee stays low when transaction volume is large, and Solana does it with a large block limit, paying no attention to whether the network is flooded with blocks and transactions.
Yet these concerns, whether fault tolerance, censorship, or an oversized block limit, seem to arise rarely in a real system. Byzantine fault tolerance is the top priority of a blockchain, but the faults that occur in a real system often do not come from a protocol-level Byzantine replica. They come from real bad actors. To produce a contradictory block, you need at least a truly asynchronous network plus enough equivocation, and in the real world these two rarely happen together at scale. Censorship resistance is an important part of consensus, but as long as you pay enough, no one will really censor your transaction, and if you pay enough, you can even arrange the position of your own transaction. An oversized block limit weakens synchronization, but no one really checks whether the actual system resilience equals the resilience that the protocol defines.
There is no need to rely fully on protocol-level decentralization and resilience to govern faults and ensure safety. When Solana truly hits an error, it halts, and the administrators call out in the Discord mb-validators channel for everyone to restart at a certain slot. Such is the appeal of social consensus. Monero twice ran into a situation where a single mining pool held the majority, and in the end nothing happened either time. Solana’s approach, even if it is reasonable in a real system, sits rather far from rigorous science. Still, we really should think carefully about how much weight decentralization and resilience deserve in a real system.
Solana’s consensus design is rather vague, mainly in the relation between PoH and the quorum-based confirmation. Removing the quorum-based confirmation is fully workable, as in the Bitcoin-like design of PoH plus PoS above. That confirmation only exists for fast confirmation, and so for lower commit latency. Removing PoH and keeping only PoS plus the quorum does not work at all, because the quorum-based confirmation only implements simple voting and counting, and the nodes have no way to replace a faulty leader, whereas the earlier PoH plus local timeout can.
Back to Solana’s own design. Without the quorum-based confirmation, PoH would have to carry the heavy task, like PoW, of controlling the network-wide block rate and so ensuring safety. As it stands, however, PoH only needs to set the block rate to be exactly the rate at which a quorum of votes is collected. PoH’s core function no longer holds any autonomy, which raises a natural question: why not remove it outright?
So, Solana recently did rewrite its consensus. It removes PoH outright, switches to a local timeout, and uses a BFT protocol for consensus. It drops the pretense; the node count is small anyway, so BFT can run. At the level of the consensus itself, it wraps a two-round fast consensus around a three-round consensus. The two-round fast consensus has a resilience of $1/5$, so it takes the slow-path quorum of $60\%$ that matches $1/5$ and wraps it around the three-round consensus. It states that when actual fault is below 20 percent, the protocol takes the fast path, and that even with another 20 percent of crash fault, it can still take the slow path. There is nothing novel here.
BTC, ETH, and Solana Against the Permissionless Consensus Taxonomy
Under the layered assumptions of permissionless consensus by Lewis-Pye and Roughgarden, BTC, ETH, and Solana no longer belong to the same category of permissionless consensus.
BTC is fully permissionless. As long as you compute a hash, you have taken part in the system. Even if you do not find a solution, you still contribute hash rate. You need no registration of any kind, only the cost of computation, so this assumption is the weakest and the most open.
ETH and Solana are the more closed quasi-permissionless case. Their leader selection, and the consensus rules that follow, both assume implicitly that the system knows which nodes exist. They use PoS to register who is eligible to take part in proposing.
In other words, in PoW participation is anonymous and needs no registration. In PoS, to take part you must stake, and a stake is made through an on-chain transaction, so you are recorded into a known and enumerable stake set. Compared with BTC, ETH and SOL are more closed systems with more assumptions. There is also this. PoS bootstraps on the very chain it is meant to protect. The money you stake is sent to the chain as a transaction, and the fact that you become a validator already relies on the past security commitment of this chain. PoS also brings something that PoW never had to consider. A new node, or a node that has been offline for a long time, cannot rebuild security from genesis alone. It needs a recent and trusted checkpoint, while a Bitcoin node can rebuild the chain from genesis using hash power alone.
Summary
A physical clock stands for real time. It is not itself a logical order, only a means to achieve something. In partially synchronous BFT, it is merely a tool to judge whether the synchronous period has begun. In permissionless consensus it carries much more. It is beautiful in Bitcoin, which is hard to change and has stayed the same for more than a decade. It no longer exists in the newest Solana, and yet in Ethereum it is taken to an extreme. These differences reflect the different voices and forces inside the blockchain community. Understanding the large gaps among these three systems is worthwhile, especially for an emerging technology and system whose future direction is still unclear.