Proof of Time: How Google’s TrueTime Can Be Used in the Blockchain

Achieving strong consistency in a decentralized and distributed system is a difficult task. In a distributed database structure, there would have to be a way to deterministically order transactions with different timestamps coming in from servers all over the world. It’s instructive to see how Google solved this problem through its use of TrueTime, and to ask if a blockchains could use the same paradigm as a method to order transactions on its ledger.

How Google Uses Time to Achieve Consistency

Google Spanner is a relational database technology that leverages extremely accurate time readings to achieve database consistency. In Google Spanner, database tables are partitioned into splits to load-balance and avoid hotspots. Spanner then further places the splits into three isolated zones. The Paxos consensus protocol is used to keep all zones in sync. If there’s a write to the database, the Paxos leader assigns a timestamp to the write transaction using TrueTime and informs the replica splits about the database update. Once a majority of the zones acknowledge the transaction, Paxos consensus takes over and the replicas apply the changes to the database at that particular timestamp.

Google Spanner is able to achieve strong data consistency in various access situations using a distributed and highly accurate time keeping mechanism. Specifically, it’s able to keep an external consistency using a variety of clocks:

• GPS.
• Atomic clocks.
• Google’s fiber network.

Using TrueTime Functions for Ordering Timestamps

Google’s various highly-accurate timekeeping techniques allows it to create TrueTime, which is actually a bounded time window of uncertainty. TrueTime is given as an interval, [earliest, latest], which varies between 1 ms to 7 ms in length. The TrueTime API can be queried to pinpoint when a transaction actually occured for a given reported timestamp t:

• TT.earliest(t) = the earliest the timestamped data point could’ve occurred.
• TT.latest(t) = the latest the timestamped data point could’ve occurred.
• TT.now(t) = TTinterval: [earliest, latest].
• TT.after(t) = true if t has definitely passed.
• TT.before(t) = true if t has definitely not arrived yet.

TrueTime guarantees that if a transaction commits before another one starts, then the first timestamp will be guaranteed to be smaller than the second one. TrueTime deals with the uncertainty inherent with physical clocks by narrowing down the possible time interval to an extremely small range of 1 ms — 7 ms. It’s consistency strategy is simple: whenever a timestamp is being committed, the system waits a maximum of 7 ms before the next transaction gets committed. Since all transactions must adhere to this wait time, the ordering is consistent and this slight time jitter of 1 ms — 7 ms becomes an acceptable level of error to achieve data consistency.

Using the TrueTime Concept for Blockchain Consensus

The question of how to order transactions on a blockchain with reference to time can be posed as follows: if event T1 happens before event T2, then timestamp t1 should be before timestampe t2. By translating some of Google TrueTime concepts over to the world of crypto, we can begin to see the beginnings of how Proof of Time can be achieved on the blockchain.

1. Google must use many time servers across a wide geographic range to ensure redundancy. Likewise, a network of mining nodes could proliferate and achieve the same distributed redundancy effect for a blockchain as long as they have sufficient incentive to do so. As long as the blockchain gives miners enough motivation in the form of mining rewards, miners should proliferate on the network and provide this service as a byproduct of them seeking to earn mining profits.
2. Google Spanner uses atomic clocks as well as GPS to achieve TrueTime. Although atomic clocks are out of reach for most mining machines, GPS plug-in modules are available for machines like Raspberry Pi for less than $50. The local quartz clock inside every mining machine is synced via GPS clock frequently throughout the day to keep clock jitter inaccuracies to a minimum.
3. Google is confident enough in its Spanner database tech to use it in some of its most demanding applications, from Gmail to its main money product, Google Adwords. These apps flood their databases with transactions that need to be correctly ordered. The algorithm is such that Spanner will wait for the TrueTime interval to pass before releasing any locks and writing the next result to the target database.

A blockchain can use the TrueTime concept of an error interval but it’s limited by one thing which Google can take for granted: Google owns their fiber network that runs PTP protocol to time-sync their servers. Being a centralized entity means they can optimize their infrastructure to keep their server ping times down. Decentralized miners on the blockchain do not have this luxury, so we’ll have to deal with the possibility that although the mining nodes’ clocks are gps-accurate, their sends may be delayed due to non-optimized network routes between nodes.

The blockchain must ensure that their TrueTime concept is useful across different network topologies where miner reports might be delayed. One method to achieve a consistent ordering of transactions is to use two stages in the same state machine replication:

• A waiting room state machine stage can be implemented to deal with variance of distributed nodes reporting transaction timestamps. This area will be a conflict-free replicated data type (CRDT) with the main objective of achieving consensus among replicas in the ordering of transactions.
• The real ledger stage which, once the order of transactions have been confirmed in the waiting room, chooses the earliest confirmed transaction from the waiting room stage.

The waiting room captures incoming transactions into a mutable section where late coming transactions can be re-ordered according to their timestamps. Transactions will spend a set amount of time in the mutable area before entering an immutable area. In the immutable area, any late coming transactions are not added for any particular delegator — replica chains unless it has been added to one or more particular delegator’s or replica’s immutable area already. In Google Spanner parlance, delegator — replica chains correlate to Spanner’s zones, and replicas are referred to as splits in Google Spanner. The immutable area acts as a CRDT where records can only be added. In practice, this means any syncing from other delegator’s replicas that add new transactions must be added to other delegator’s replicas. No new transactions are added from their own nodes; instead, they use the sync function between replicas to ensure that the immutable section reaches consensus.

This syncing between replicas is eventually able to reach consensus without choosing a leader which is different from Google Spanner’s use of a Paxos leader to achieve consensus among splits. Instead, as long as each node is trustable, we can use time itself as a leader.

What Benefits Would Proof of Time Have Over PoW or PoS?

One of the major bottlenecks of current blockchains is transaction speed. Ethereum, a blockchain that’s transitioning from PoW to PoS, can only perform 15 transactions / second without resorting to layer-2 sharding. Proof of Time (PoT) allows for a unique consensus mechanism that maximizes scalability while still maintaining data consistency. Using PoT allows a blockchain to use replica nodes without worrying about them getting their transactions mixed up as transaction order becomes a function of time. Because each node has its own accurate clock, they don’t have to wait on other nodes before sending their transactions.