PoW-based Distributed Milestones

One option for the removal of the milestone issuing coordinator is to allow any participant to issue a milestone. In order for this to be done, there must be a process that limits the global rate in which milestones are issued. One such process can be based on Proof of Work. Below is a description of how such a process could be defined.

Most challenges regarding distributed milestones are related to the fact that in a distributed milestones issuance process, there are bound to be independent milestones. These do not exist when a single entity creates all milestones, and issues every milestone “on top” of the previous one. This mandates an expansion of the concept of “THE last milestone”, in a way that is analogous to the whitepaper’s definition of a tip:

Definition: A milestone that is not referenced by another milestone, will be called a tipstone. When discussed in reference to a milestone P, only the past cone of P is taken into account. (Milestone Q is a tipstone in regards to milestone P, if the past cone of P does not include any milestone that references Q).

Lemma: Two tipstones are independent of each other. (If they are not independent, than one is approved by the other, and therefore not a tipstone).

The task of the Coordinator

While the task of the coordinator is usually summed up as “to issue milestones”, there is actually more to it, even before considering a distributed milestone issuance. The Coordinator’s milestones:

  1. Conflict avoidance: Do not include conflicts in their past cones.
  2. Milestone volume: Add transactions to consensus in a certain capped rate.
  3. Milestones rate: Are issued on average every x minutes.

While points 1 and 3 are clear from the definition of the coordinator, point 2 is implicit in the coordinator’s behaviour. A malicious coordinator could create transactions and milestones at a rate that would prevent nodes with limited bandwidth from participating in the network.

A Valid Milestone

The three tasks above should be translated to a clear definition of what a valid distributed milestone is. In general lines:

  1. A distributed milestone must not include conflicts in its past cone. (alternatively, it can include conflicts if there is a deterministic rule on which is ignored).
  2. Given a distributed milestone, the sum volume of all transactions that are referenced by it, and are not referenced by other milestones in its past cone, should not be greater than a set constant value. (This rule becomes strictly stronger (too strong) when a milestone has in its past cone two tipstones).
  3. The hash of a distributed milestone must be lower than some difficulty threshold which is periodically adjusted to maintain a constant rate of milestones.

Points 1 and 2 can be formally defined and implemented. For a more rigorous definition of point 3, the difficulty adjustment process must be well defined.

Difficulty Adjustment

On the surface, it looks like difficulty adjustment can be done in the same way it is done in the Bitcoin network. (See https://en.bitcoin.it/wiki/Difficulty, https://en.bitcoin.it/wiki/Target, and https://en.bitcoin.it/wiki/Block_timestamp). However, the nature of the tangle enables a milestone to approve two tipstones (this can be seen as the merging of a fork, as long as the new milestone is valid as defined above). While this is technically valid and possibly even beneficial, it raises the (existing) issue of incentives. If there is no incentive to do so, each milestone will only approve one tipstone, reducing the tangle to some type of blockchain. This will be explored in the open questions section below.

Consensus Rule

The possible existence of multiple tipstones, and the possible orphanage of some, mandates a consensus rule that dictates which current tipstone represents the most updated consensus. While this can be simply defined as “the tipstone with the most PoW in its past cone”, one must keep the question in mind when exploring the incentive system of issuing PoW-based milestones, and of tip selection for regular transactions in such a system.

(It is important to justify the distinction of milestones and transactions as different object types - A milestone is not equivalent to a set of transactions with the same PoW, as it has a much higher ratio of PoW/volume. A milestone is a small-volume object that justifies the bandwidth allocation of all transactions in its past cone. While one might know of those transactions ahead of time, one can also wait for the issuance of a milestone, and then allocate bandwidth only for the transactions required for solidification).

Incentive System

The first question is - what incentive would get someone go through the trouble of issuing milestones? The next question would be, given that incentive, how would that participant go about doing that? The first question has at least three possible components:

  1. To include transactions they care about in the consensus
  2. To get transaction fees
  3. To get a milestone reward

Point 3 would require a change to the monetary cap of the token, and should therefore require a change that is out of scope for this text.

Point 2 nullifies point 1, so the two should therefore be explored independently.

Point 2 raises some complex questions:

  • How will transaction fees be managed for a transaction that is approved by two independent (but eventually merged) tipstones?
  • What kinds of selfish mining would emerge on a tangle?

To answer those questions, a fuller model of fee-based-distributed-milestones should be formulated and explored. (see open questions below).

Assuming that point 1 would not be reduced to point 2 by the emergence of an external fee market, it would require milestones to be easy enough to issue. This means that the PoW required per milestone would be relatively small, lowering the PoW/volume ratio of milestones, which in turn reduces TPS. Some additional mathematical analysis is required here, but this is likely equivalent or reducible to a solution in which there is no distinction between milestones and transactions, but with a much higher PoW requirements. (This relates to the objective layer discussion).

Open questions:

  • How would a care-based-distributed-milestones (point 1) solution behave? Can low PoW requirements per milestone coexist with a degree of milestone rarity that ensures that low-bandwidth actors could still participate? (In other words: If each actor wants to issue transactions -> each actor wants to issue a milestone -> milestones are equivalent to transactions and are therefore meaningless as separate objects).
  • How could a fee-based-distributed-milestones solution look? How would that affect incentives and mining?

A very fundamental problem that I see with the PoW-based milestones/checkpoints is the following: how to prevent an attacker (equipped with a lot of hash power) from placing a checkpoint into a “bad” location (e.g., not confirming a lot of new transactions)?

If the answer is “because the honest hashrate will be higher”, then we’re back to hashraces/Chinese minerzz problem (essentially the reason why we have moved away from the WP approach).