The main chain

Our DAG is a special DAG. In normal use, people mostly link their new units to slightly less recent units, meaning that the DAG grows only in one direction. One can picture it as a thick cord with many interlaced wires inside. This property suggests that we could choose a single chain along child-parent links within the DAG, and then relate all units to this chain. All the units will either lie directly on this chain, which we’ll call the main chain, or be reachable from it by a relatively small number of hops along the edges of the graph. It’s like a highway with connecting side roads.

One way to build a main chain is to develop an algorithm that, given all parents of a unit, selects one of them as the “best parent”. The selection algorithm should be based only on knowledge available to the unit in question, i.e. on data contained in the unit itself and all its ancestors. Starting from any tip (a childless unit) of the DAG, we then travel backwards in history along the best parent links.

Figure 3

Traveling this way, we build a main chain and eventually arrive at the genesis unit. Note that the main chain built starting from a specific unit will never change as new units are added. This is because on each step we are traveling from child to parent, and an existing unit can never acquire new parents.

If we start from another tip, we’ll build another main chain. Of note here is that if those two main chains ever intersect while they go back in history, they will both go along the same path after the intersection point. In the worst case, the main chains will intersect only in genesis. Given that the process of unit production is not coordinated among users, however, one might expect to find a class of main chains that do converge not too far from the tips.

Figure 3. Main chains built from different childless units intersect and then go along the same path. Of the two double-spends, the one with the lower main chain index (5) wins, while the other (with CI=6) is deemed invalid. Once we have a main chain (MC), we can establish a total order between two conflicting nonserial units. Let’s first index the units that lie directly on the main chain.

The genesis unit has index 0, the next MC unit that is a child of genesis has index 1, and so on traveling forward along the MC we assign indexes to units that lie on the MC. For units that do not lie on the MC, we can find an MC index where this unit is first included (directly or indirectly). In such a way, we can assign an MC index (MCI) to every unit. Then, of the two nonserials, the one that has a lower MCI is considered to come earlier and deemed valid, while the other is invalid. If both nonserials happen to have the same MCI, there is tiebreaker rule that the unit with the lower hash value (as represented in base64 encoding) is valid.

Note that we keep all versions of the double-spend, including those that eventually lose. DagCoin [3] was the first published work that suggested storing all conflicting transactions and deciding which one to treat as valid.

The MC built from a specific unit tells us what this unit’s author thinks about the order of past events, i.e. his point of view about the history. The order then implies which nonserial unit to consider valid, as described above. Note that by choosing the best parent among all parents of a given unit, we are simultaneously making a choice among their MCs: the MC of the unit in question will be the MC of its best parent extended forward by one link. Recognizing that many (or even all) parent units might be created by an attacker, and remembering that the choice of best parent is essentially the choice among versions of history, we should require from our best parent selection algorithm that it favors histories that are “real” from the point of view of the child unit. We hence need to devise a “reality test” that our algorithm would run against all candidate MCs to select the one that scores best.