Posets and Consensus

William Sanders ·

In any cryptocurrency, transactions are linked to one another using hashes. This unalterable relationship endows the set of transactions with a natural mathematical structure called a partial order. In this post, we discuss partial orders and how they are useful for IOTA.

The real numbers, ℝ, has a natural ordering denoted by ≤. As children, we learned that all numbers, x, y, z, and the relation ≤ satisfy the following conditions:  

  1. Reflexivity: x≤x
  2. Antisymmetry: x≤y and y≤x implies x=y
  3. Transitivity: x≤y and y≤z implies x≤z
  4. Totality: Either x≤y or y≤x

Relations of this sort are pervasive in mathematics and are thus named: a total order is any relation ≤ satisfying these properties. A set with a total order is called a totally ordered set.  

Moreover, every subset of ℝ is totally ordered, such as the natural numbers ℕ and the interval[0,1]. However, there are other more exotic examples of totally ordered sets. For instance a classroom X of children is totally ordered by height provided that no two children in X have identical height. Specifically, for children x and y in X, we may declare that x≤y if x is shorter than y. In fact various characteristics such as age, weight, or grades produce many different total orderings onX.  

However, not all orders are total. For instance in ℝ² let (a,b)≤(c,d) if a≤c and b≤d. Although this relation satisfies Conditions (1)-(3), ℝ² is not totally ordered since, for example, the elements(2,3)and(3,2)are incomparable, because a<c while b<d. This example motivates a different type of order.  

A partial order is a relation ≤ that satisfies all of the above conditions except Condition 4, and thus some elements can be in comparable. A poset(short for partially ordered set) is a set with a partial order. For instance ℝ² is a poset with the above relation.  

For another example, let X be the following set of movies: Star Wars Holiday Special, The Matrix, Shrek, and The Godfather. I say that x≤y if movie y better than movie x. The Star Wars Holiday Special is often considered one of the worst movies of all time, whereas The Godfather is considered one of the best. Thus, it is clear that:  

However, in my opinion, The Matrix and Shrek are incomparable. ThusXis a poset, but not a totally ordered set.

Recall that aDAG, or a directed acyclic graph, is a collection of vertices connected by arrows with no cycles, i.e. it has no nontrivial sequence of arrows  

x→x₁→x₂→ᐧᐧᐧ→xₙ→x

beginning and ending in the same place. In this section, we explain the close relationship between DAGs and posets.

First, we can partially order the vertex set of any DAG D. For vertices x, y in D, let x≤y if there is a path from x to y. Recall that a path from x to y is a sequence of arrows:  

x→x₁→x₂→ᐧᐧᐧ→xₙ→y

We leave it to the reader to check that the relation ≤ partially orders the vertices ofD. Note that x≤y and y≤x if and only if there is a cycle including x and y. Thus ≤ satisfies Condition (2) if and only ifDis acyclic.  

Conversely, for a posetX, we can define a DAG whose vertex set isX. For each element x in X, we draw an arrow to every y in X which covers x. An element y covers x if x<y but there exists no z in X such that x<z<y. For example, in the natural numbers,3covers2, but4does not.  

In the finite case, these operations are mutual inverses, yielding a one to one correspondence between finite DAGs and finite posets. Thus every finite DAG is essentially a finite poset, and vice versa, allowing us to freely confuse the concepts. For example, the set{1,2,3,4}can be represented as both a poset and a DAG:

1 →2→3→4

1≤2≤3≤4.

In the mathematics we say that finite DAGs and finite posets are equivalent categories.  

Recall that IOTA stores transactions in a DAGT called the tangle: an arrow x→y exists if and only if transaction x directly approves transaction y. Thus the tangleTis also a poset with x≤y whenever x indirectly approves y.  

The IOTA protocol gives priority to larger transactions: when x≤y, transaction y is more important than x. For instance, the genesis is both the largest or maximum element in T and also the most important of all transactions.  

However, we still have a problem: suppose x and y conflict, and x and y are incomparable, i.e. neither transaction approves the other. In this case, we need to decide which transaction is more important.  

IOTA solves this problem by using the confidence level to totally orderT: write x⪣y if the confidence level of y is larger than x. Indeed, under⪣any two transactions are comparable, and so ⪣ is indeed a total ordering. Moreover,⪣refines≤, that is x≤y (x approves y) implies that x⪣y.  

With the total ordering ⪣, every pair of transactions is comparable, and thus we can resolve any conflicts. For example, if transactions x and y spend the same money from the same account, then they conflict. Eventually either x⪣y or y⪣x. If y⪣x, then the protocol accepts x, the larger of the two transactions.  

We make one caveat: the relation⪣is only truly a total order if no two transactions have identical confidence level, since otherwise Condition (2) is violated. However, this is actually a fairly reasonable assumption since the probability of two transactions have exactly the same confidence level is quite low.

Partial orders also appear in traditional blockchains. In a blockchain, transactions are ordered by where they appear on the longest chain. However, since any transaction not on the main chain is ignored, they are placed in a negatively infinite position.

As seen with the IOTA protocol, partial orders encapsulate the consensus mechanisms in DLTs. If two transactions potentially conflict, then a DLT protocol needs to prioritize them in some fashion. However, priority is a partial order on the set of transactions. Thus all nodes in a DLT must reach consensus on the partial order of transactions.

This story is similar to the equivalence of classical consensus to atomic broadcast. A protocol in a distributed system achieves atomic broadcast if it establishes amongst the nodes an ordered log of messages. Computer scientists have shown that consensus and atomic broadcasts are equivalent problems. Establishing a partial order on transactions appears to be the DLT equivalent of atomic broadcast.

So how do posets help us? First, posets are rich and well-studied mathematical objects. Thus we have an opportunity to import language, algorithms, and theorems from the world of posets to the world of DLTs. Considering a problem from multiple perspectives often reveals innovated solutions.

Posets also help us understand how a specific DLT reaches consensus by analyzing how it orders transactions. This analysis can highlight security weaknesses: any place where the order can be changed is a point which can be attacked. For instance, in IOTA, confidence levels can be manipulated and in block chains, the longest chain can change.