Proof of History: A Clock for Blockchain

A high-level explanation of Solana’s core innovation

Solana is the most performant permissionless blockchain in the world. On current iterations of the Solana Testnet, a network of 200 physically distinct nodes supports a sustained throughput of more than 50,000 transactions per second when running with GPUs. Achieving as such requires the implementation of several optimizations and new technologies, and the result is a breakthrough in network capacity that signals a new phase in blockchain development.

There are 8 key innovations that make the Solana network possible:

• Proof of History (POH) — a clock before consensus;
• Tower BFT — a PoH-optimized version of PBFT;
• Turbine — a block propagation protocol;
• Gulf Stream — Mempool-less transaction forwarding protocol;
• Sealevel — Parallel smart contracts run-time;
• Pipelining — a Transaction Processing Unit for validation optimization
• Cloudbreak — Horizontally-Scaled Accounts Database; and
• Replicators — Distributed ledger store

One of the most difficult problems in distributed systems is agreement on time. In fact, some argue that Bitcoin’s Proof of Work algorithm’s most essential feature is functioning as a decentralized clock for the system. At Solana, we believe Proof of History provides this solution and we’ve built a blockchain based on it.

Decentralized networks have solved this problem with trusted, centralized timing solutions. For example, Google’s Spanner uses synchronized atomic clocks between its data centers. Google’s engineers synchronize these clocks to a very high precision and constantly maintain them.

This problem is even harder in adversarial systems like blockchain. Nodes in the network can’t trust an external source of time or any timestamp that appears in a message. Hashgraph for example, solves this problem with a “median” timestamp. Each message that is seen by the network is signed and timestamped by a supermajority of the network. The median timestamp for the message is what Hashgraph calls “fair” ordering. Each message has to travel to the supermajority of the nodes in the system, then after the message collects enough signatures, the entire set needs to be propagated to the entire network. As you can imagine, this is really slow.

What if you could simply trust the timestamp that is encoded into the message? An enormous wealth of distributed systems optimizations would suddenly be at your disposal. E.g.

“Synchronized clocks are interesting because they can be used to improve the performance of distributed algorithms. They make it possible to replace communication with local computation.”

— Liskov, B. Practical uses of synchronized clocks in distributed systems

In our case this means a high throughput, high performance blockchain

Proof of History

What if instead of trusting the timestamp you could prove that the message occured sometime before and after an event? 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. With Proof of History, you can create a historical record that proves that an event has occurred at a specific moment in time.

The Proof of History is a high frequency Verifiable Delay Function. A Verifiable Delay Function requires a specific number of sequential steps to evaluate, yet produces a unique output that can be efficiently and publicly verified.

Our specific implementation uses a sequential pre-image resistant hash that runs over itself continuously with the previous output used as the next input. Periodically the count and the current output are recorded.

For a SHA256 hash function, this process is impossible to parallelize without a brute force attack using 2¹²⁸ cores.

We can then be certain that real time has passed between each counter as it was generated, and that the recorded order each counter is the same as it was in real time.

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.

Verification

While the recorded sequence can only be generated on a single CPU core, the output can be verified in parallel.

Each recorded slice can be verified from start to finish on separate cores in 1/(number of cores) time it took to generate. So a modern day GPU with 4000 cores can verify a second in 0.25 milliseconds.

ASICS

Isn’t every CPU different, and some much faster then others? How do you actually trust that “time” as it’s generated by our SHA256 loop is accurate?

This topic deserves its own article, but long story short is that we don’t much care if some CPUs are faster then others, and if an ASIC can be faster then the CPUs available to the network. The most important thing is that there is a finite bound on how much faster an ASIC can get.

We are using SHA256, and thanks to Bitcoin there has been significant research in making this cryptographic hash function fast. This function is impossible to speed up by using a larger die area, like a Look Up Table, or unrolling it without impact to clock speed. Both Intel and AMD are releasing consumer chips that can do a full round of SHA256 in 1.75 cycles.

Because of this, we have pretty good certainty that a custom ASIC will not be 100x faster, let alone 1000x, and most likey will be within 30% of what is available to the network. We can construct protocols that exploit this bound and only allow an attacker a very limited, easily detected and shortlived oportunity for a denial of service attack. More on that in the next article!

Code

If you like rust and cuda, and want to build the worlds fastest blockchain please reach out to us [email protected]

Solana’s implementation of Proof of History, alongside innovations like Tower BFT, Proof of Replication, and Gulf Stream combine to create the most performant blockchain in the world. Solana’s testnet is live today. You can see it at https://testnet.solana.com. For cost purposes, we are only running a handful of nodes. However, we have spun it up on many instances to over 200 physically distinct nodes (not on shared hardware) across 23 data centers on AWS, GCE, and Azure for benchmarking.

The runtime is functioning today, and developers can deploy code on the testnow now. Developers can build smart contracts in C today, and we are aggressively working on the Rust toolchain. Rust will be the flagship language for Solana smart contract development. The Rust toolchain is publicly available as part of the Solana Javascript SDK, and we are further iterating on the Software Development Kit.

Solana will soon launch a public beta incentivizing validators to run nodes via Tour de SOL — analogous to Cosmos’s Game of Stakes — that challenges the public at large to test the limits of the Solana network while earning tokens for doing so.