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 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

  • 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

  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?

--

--

teaproject.org

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store