Bitzuma

Bitcoin from Scratch: Consensus

By Rich Apodaca | Updated

Timestamps enable an auditor to record and communicate a specific transaction sequence. However, a given auditor will occasionally observe a different transaction sequence than its peers. To record a uniform transaction order, the auditors much reach consensus.

This post is part of the extended series Bitcoin from Scratch.

Consensus is a state of agreement among the members of a group. Auditors need to reach consensus about the order of transactions to fulfill their mission of protecting users against double spending. This requires a mechanism to resolve differences in timestamp ordering.

A strictly linear timestamp chain interferes with consensus by limiting auditors to recording only one version of history. Adhering to a single, inflexible sequence precludes the negotiation needed to reach consensus. If instead auditors recorded multiple transaction sequences, they could compare them to resolve differences. This feature can easily be added by allowing multiple timestamps to claim the same parent. In effect, the linear timestamp chain would be replaced with a branching tree.

Imagine that two auditors, Vanna and Victor, simultaneously processed different audit requests (using timestamps C and B, respectively). Vanna receives Victor’s relayed timestamp B, and Victor receives Vanna’s relayed timestamp C. Although neither timestamp can be appended to the end of the timestamp chain, they can be inserted as siblings of timestamp A. In doing so, each auditor creates the same tree.

SVG Image
Branching the Chain. Vanna and Victor relay timestamps at the same time (left). Each auditor receives a relayed timestamp that can’t be appended to the end of the chain (center). However, the relayed timestamps can be inserted as siblings claiming the same parent A (right).

The branch point at timestamp A demarcates two versions of the audit history. This divergence must be resolved eventually to eliminate the risk of double spending. In other words, Vanna and Victor need a way to decide which of the two branches, A-B or A-C, represents the universally valid transaction history. Back and forth communication adds time and complexity to the process, and so should be avoided. Ideally, resolution would occur spontaneously.

Fortunately, the issue can be decided without sending or receiving additional messages. The auditors need only follow two simple rules:

  1. Append newly-received, valid timestamps to the longest branch. If two or more branches of equal length exist, build on the one that was seen first.
  2. If appending a timestamp makes one branch longer than the other, re-process the transactions in the shorter branch and add any missing timestamps to the longer branch.

To continue with the previous example, imagine that Vanna verifies a new transaction (D). Her next job is to pick the branch in her ledger that will be extended. Branch A-B and branch A-C are equally long. Recalling that she saw branch A-C first (because she created it), Vanna appends timestamp D to timestamp C (Rule 1). Vanna relays timestamp D to Victor, then re-processes transaction B (Rule 2).

SVG Image
Growing a Branch. Vanna adds Transaction D to her branched chain, moving Transaction B to her queue for reprocessing (left). She then relays the new Timestamp D to Victor (right).

Victor receives Vanna’s timestamp D, and appends it to branch A-C. Having grown a longer branch, Victor re-processes transaction B (Rule 2). At this point, both Vanna and Victor have equivalent ledgers and one transaction that needs to be re-processed (B). They are in complete agreement about the ordering of transactions.

SVG Image
Updating a Branch. Victor adds Timestamp D to his branched chain, moving transaction B to his queue for re-processing (bottom left). Both auditors now have identical branched chains and queues (bottom right).

The situation becomes more complicated if auditors relay timestamps at the same time. Imagine that Vanna and Victor start with equivalent, but branched timestamp trees. Each auditor receives a new, unique audit request at exactly the same time. The requests are processed and timestamped, then relayed simultaneously. Neither auditor is aware of the timestamp in transit from the other auditor.

SVG Image
Slow Timestamp Relay. Auditors with branched chains receive a new audit request simultaneously (left). Each auditor relays a different timestamp to the other at the same time (right).

Vanna and Victor receive their respective inbound timestamps, and update their ledgers accordingly. However, this merely results in extending both branches by one timestamp. Rather than solving the problem, Vanna and Victor made it worse. The tie can only be resolved if one auditor relays timestamps at a faster rate than the other. In other words, the auditors are stuck in a race condition.

SVG Image
Race Condition. Vanna and Victor simultaneously accept relayed timestamps (left). However, doing so leaves both timestamp trees in a branched state (right).

A race condition prevents consensus even when only two auditors are involved. Adding more auditors just compounds the problem by increasing the number of in-flight timestamps. Furthermore, increasing the rate of audit requests by users results in ever longer branches, again undermining the auditor’s core mission of protecting users from double spending fraud.

Auditors can sometimes arrive a common transaction sequence using only a timestamp tree and two simple rules. However, consensus breaks down as audit request volume and the number of auditors increases.