Proof of history
Proof of history is a component that achieves consensus within a system through creating rules for validators to validate transactions. Developed by Solana, proof of history uses time stamps in the approval process, further reducing the amount of energy needed to approve transactions.
Since the blockchain is decentralized, there isn't an internal source of time to tell time. Instead, the solution is to have validators keep track of the sequence of events like a timeline.
Proof of history is not entirely a consensus algorithm, instead it works together with one to make consensus more complete within the blockchain.
How it works?
Proof of History uses a recursive cryptographic function called Verifiable Delay Function (VDF) to generate timestamps for each block in the blockchain. This function is designed to be computationally intensive to prevent malicious actors manipulating timestamps. This consensus mechanism is designed to work alongside other mechanisms like proof of stake or proof of work etc.
Front-running is still possible in Solana or other blockchains that use proof of history, however it is greatly reduced due to leader rotation.
Just like getting stamps on a passport when travelling, you receive a stamp each time you cross into a new country. These sequence of stamps act as a timeline of your travels, just like how proof of history uses a stamping process to approve transactions based on their occurence.
Solana's implementation of proof of history uses a sequential pre-image resistant hash that runs over itself repeatedly with the previous output used as the next input. The count of this along with the current outputs are recorded periodically. Each Solana validator maintains its own clock by encoding the passage of time with the VDF, which is a simple SHA-256 hash.
Upper bound on Time
Data can be inserted into the sequence by appending the hash of the data to the previous generated state. The state, input data, and count are all published. Appending the input causes all future output to change unpredictably. It is still impossible to parallelize, and as long as hash function is pre-image and collision resistant, it is impossible to create an input that would generate a desired hash in the future, or create an alternative history with the same hashes. We can prove that time passed between any two append operations. We can prove that the data was created sometime before it was appended. Just like we know that the events published in the New York Times occurred before the newspaper was written.
Lower bound on Time
Inputs into Proof of History can have references back to Proof of History itself. The back reference could be inserted as part of a signed message with the users signature, so it cannot be modified without the users private key. This is just like taking a photograph with the New York Times newspaper in the background. Because this message contains 0xdeadc0de hash we know it was generated after count 510144806912 was created.
But since the message is also inserted back into Proof of History stream, it is as if you took a photo with the New York Times in the background, and the next day the New York Times published that photo. We know that the content of that photo existed before and after a specific day.
Transaction speed
Through having proof of history, transactions sent and transactions processed could be done in the same order with shorter blocktimes. This creates less complexity as transactions can be done much faster compared to other chains, with a comparison of Ethereum mainnet and Solana, Ethereum has a capacity of 13-15 transactions per second, while Solana offers up to 65,000 to 72,000 transactions per second[1].
The timestamps generated by the VDF provides a verifiable and immutable record of transaction orders into each block of the Blockchain, allowing for faster finality and cannot be undone.
However, despite being so fast, Solana did have 7 outages since it's founding from 2020.[2]
Censorship Resistance
Through proof of history, censorship is achieved through preventing validators from "censoring" other validators from submitting blocks, allowing validators to write blocks to the block chain during their leader slots.
The VDF (Verifiable Delay Function) is designed to be memory heavy to prevent attackers from manipulating timestamps. Altering timestamps would require recalculation of the sequential hash, which is resource intensive and easily detectable.
Limitations
Despite providing fast transaction speeds, Proof of history is limited by requiring a trusted time source to function. If this source is compromised, the integrity of the entire blockchain is at risk.
Proof of history also requires more computational resources than other consensus mechanisms since it involves generation and verification of large amounts of data to perform calculations of Verifiable Delay Functions.