Time is money
Agreeing upon the time is imperative for networks of all kind. Professor Paul Eggert at UCLA is editor of the Internet Assigned Numbers Authority (IANA), an institution that keeps a database of timezones and used by millions of software programs. Similarly, a trusted central authority like Google’s Spanner uses synchronized atomic clocks. Atomic clocks are precise enough to demonstrate time dilation between two clocks stacked on top of each other. In a decentralized network, there is no IANA and no centralized clock, so how do participants agree on the accuracy of time presented by adversaries? The answer lies in Proof-of-History.
Proof of History (PoH) is a consensus mechanism introduced as a part of the Solana blockchain protocol, designed to achieve high throughput, low latency, and secure consensus among network nodes. Anatoly Yakovenko, in his 2017 whitepaper detailing PoH, describes it as one of eight key innovations that make Solana what it is. In any blockchain network, achieving consensus is crucial for maintaining the integrity and immutability of the distributed state machine.
Proof of History is a challenging concept, let’s try to break it down.
Proof of History
Proof of History introduces a novel approach to consensus that leverages cryptographic techniques to establish a verifiable and immutable record of time within the blockchain. At its core, PoH is a mechanism for generating a historical record of events in a linear and trustless manner. It provides a reliable timestamping mechanism that can be used to order transactions and synchronize the state of the network across all participants.
When you take a photograph with the cover of New York Times, you are creating a proof that your photograph was taken after that newspaper was published, or you have some way to influence what New York Times publishes.
—Anatoly Yakovenko (2017)
In a nutshell, the idea is that an input hash starts the clock, with a sequence of SHA256 hash functions that use the previous output as input. This is easily verifiable looking backwards, but ensures that a time has passed between each function call. Along with a counter, we create an upper and lower bound on time, making it easy to verify chronological order.
Suppose we want to verify a timestamp of 12:00:01. If we can be sure that the transaction came after 12:00:00 and before 12:00:02, we can be sure that the timestamp of 12:00:01 is accurate because time is monotonically going forward and the problem becomes an application of intermediate value theorem.
The process of recording these steps must be done in a single core to ensure time has passed between each function call, while verification can be done in parallel with a speedup that is proportional to the number of cores available to the verifier. The parallelization of verification enables faster synchronization and trust of timestamps within the adversarial network.
Upper and Lower Bounds
Appending data into previous states causes every state thereafter to change unpredictably. This means that you wouldn’t be able to claim that data was created after it exists in the state. As a corollary, you cannot claim that the data was created before the appending operation as an upper bound for both events because all future states are altered. Data must exist before it changed everything in front of it in time.
If you use a previous hash as an input to a user signed transaction, and imbed the signature into the next state, it is proof that the next state came after the previous hash. This means that if I used a hash from a previous state, that previous state becomes the lower bound for the current state because the input that exists in the current state is a time-delayed derivative of information from that previous hash. Data must exist after it was created.
With these upper and lower bounds, we can verify order of information and timestamps. This is very useful and does not necessarily need to have atomic clock level precision to offer massive speed improvements in the blockchain. As Toly states, “a modern day GPU with 4000 cores can verify a second in 0.25 milliseconds.” On precision, the fact that modern CPUs and ASICs have reached similar optimizations, we can be roughly confident that bound estimates do not have orders of magnitude improvements that will change the correctness of this algorithm.
Advantages of Proof of History:
Scalability: PoH enables Solana to achieve high throughput and low latency by providing a reliable mechanism for ordering transactions. This scalability is essential for supporting a wide range of decentralized applications and use cases. As nodes in the Solana network are able to trust incoming timestamps through parallelized verification, transactions are processed much faster.
Security: The cryptographic nature of PoH ensures the integrity and immutability of the historical record. This ensures the security of the network against malicious actors who may attempt to incorrectly order transactions and disrupt the integrity of the network.
Decentralization: By providing a fair and transparent mechanism for leader selection and block production, PoH promotes decentralization within the Solana network. Validators are incentivized to act honestly, knowing that the integrity of the network relies on the accuracy of timestamps. Each validator can easily verify incoming timestamps while remaining adversarial.
Efficiency: PoH reduces the computational overhead associated with achieving consensus by providing a deterministic and efficient mechanism for timestamping. This efficiency allows Solana to process a large number of transactions quickly and cost-effectively.
Conclusion:
Proof of History is a groundbreaking consensus mechanism that addresses key challenges faced by traditional blockchain networks. By providing a verifiable and immutable record of time, PoH enables Solana to achieve high throughput, low latency, security, and decentralization. This innovative approach to consensus has the potential to unlock new possibilities for decentralized applications and pave the way for the mainstream adoption of blockchain technology.
As long as humans have not unlocked time travel in the future, Proof of History is an exceptional solution to the synchronization of clocks in a trust-less, adversarial network.
Resources
https://solana.com/news/proof-of-history
https://medium.com/solana-labs/proof-of-history-a-clock-for-blockchain-cf47a61a9274