A protocol proposal

In this proposal, I try to summarize everything that we have discussed into one protocol. Luigi and I have been working on the rate control mechanism, and this is the first place where we have made our ideas public.

Description

  • We choose one of the mana proposals. All the proposals would work here.
  • DRAND for the random number generator
    • We choose a “council” of high mana holders.
    • The random number is revealed after some subset of the council releases their fragments.
    • When a random number is revealed, a new round begins.
    • Rounds numbers are now a decentralized clock. Timestamps will be measured in terms of this clock
    • Rounds will be divided into Epochs (eg 1000 rounds=1 epoch).
      • A different committee will be chosen for each Epoch.
      • The committee for Epoch i will be selected during Epoch i-1 based on the mana of a canonically chosen transaction issued in Epoch i-2.
  • Timestamps*
    • Every transaction will include a timestamp measured in (possibly fractional) units of the random number clock
    • Every transaction will also include a number called the gap, which is a time which will also be measured in (possibly fraction) termis of the random number clock. (See the rate control bullet)
    • Two transactions issued by the same node collide if their intervals (time stamp, timestamp +gap) intersect.
      • Colliding transactions are strictly forbidden.
  • We will vote using FPC.
    • Opinions are a pair (b,l) where b is a Boolean value and l is the level of knowledge.
    • When voting, we take the opinion on the following questions:
      • Is the time stamp valid?
      • Are there any collisions, using the FCoB (See Overleaf: Fast consensus of Barcelona(a.k.a. FC Barcelona) decision rule (wait time c for collision)?
      • Do I think that the transaction propagated through the network (this is based on the gap score in the rate control section)?
    • The total opinion is initially the “least” opinion on each of the above questions.
    • FPC will be applied to all transactions. (However only level 1 and level 2 knowledge transactions will cause FPC to do anything.)
    • After FPC terminates on a transaction, the total opinion is set (b,3) where b is the output value
  • Rate control: we will use a timestamp based rate control algorithm
    • Nodes process transactions in order of their time stamp. Proof of collisions are given priority
    • Transactions with total opinion (0,2) or (0,3) are not gossiped.
    • Nodes give each transaction a gap score. Transactions with good gap scores are prioritized. The gap score is determined by:
      • Size of gap (bigger gap=better)
      • Amount of mana (more mana=smaller gap)
      • Current network traffic
      • Reputation: attempts to spam the network will lower the gap score.
    • Nodes will set their gaps using an AIMD style algorithm,
      • A node can only shrink the gaps in consecutive transactions incrementally. This can and will be enforced.
      • If a node detects that their transaction has not been propagated through the network (via FPC voting), they will dramatically increase their gap.
  • TSA: we will use Luigi’s algorithm.
    • Tips will be chosen to maximize the past cone.
    • A transaction will only be a candidate for TSA if every transaction in its history has total opinion either (1,2) or (1,3).
  • Ledger state computation: The timestamps will be sued to totally order the tangle, then apply the conflict white flag approach.

Pros

  • This is built off of a rate control algorithm.
  • Most of the components are well understood.

Cons

  • FPC might not work by itself. Maybe we could incorporate CA into it instead, but we don’t know if this possible yet or if CA works.
  • Nodes have to vote on transactions that they have not seen. It is not clear what are the implications of this. Does this open a spam attack vector? With what level of knowledge should a node participate in FPC if it has not seen the transaction?

Open Questions

  • The rate control algorithm needs to be refined. Specifically, we need to clearly outline how transactions set their gaps using the AIMD style algorithm. It is also not clear what the attack vectors are.
  • Congestion detection is also something that we should focus more. Trivially, each node will have knowledge of the current network traffic, because they receive the gossiped txs (if the node drops txs, network is congested). Is this enough? Do we need an additional mechanism to detect whether my own txs have already been received by the other nodes?
  • The termination condition in Luigi’s TSA algorithm needs further study.
  • How will the transactions that mana is computed from be chosen? (This becomes easier with milestones)
  • For the TSA, it may make sense to include one of the distributed milestone proposals given by Sergei and myself.
  • If we are able to find another Binary Voting Protocol with a passive voting option, then the FPC can be replaced with this. Moreover, if this protocol does not use a DRNG, we can remove this portion of the algorithm and also use normal cocks.
  • The DRNG puts the entire clock of the system in the hands of a small council. We do not know the implications of this.
  • We still do not know how nodes which are entering the network should come on line. Similarly, we do not know how to protect it against long range attacks. I would offer the following suggestion: include the issuing node ID and its signature into the actual transaction structure. In this case, the timestamp on a transaction could effectively verified after enough of the mana has approved it. However, this opens the door essentially to “on tangle voting” and has not been studied.

I think we’ll be able to answer this question only after seeing it in action.

Thank you for not mentioning the A-word explicitly :slight_smile:
(But, seriously, it is shit.)

just to prove that I read it with attention :smiley:

We may have a backup council, or use external public randomness (like the NIST RNG), or even use 1/2 if no other RN is available. Frankly, I don’t see it as a big problem.

To enter the network, you need to use some trusted place anyway, no (like, to get the node software, you won’t go to some random coolhackerzz.io site)?

Also, at least initially, having high-mana nodes cast their votes as data transaction could help, imo.

A-word? Do you mean Avalanche? First, I realize that Avalanche will not function, and second, it is not a BVP.

I was actually referring to CA (or some version of it with a passive option).

We will see. I was hoping to get some in put from Bob and his team, since they are experts in this sort of thing.

I dont see this as a big problem either, but it is a point that we must acknowledge. I can see our critics on twitter homing in on this point

True, but to be honest its just something we have not discussed, and I think its a potential attack vector. We dont want the coordinator to just be replaced with some sort of boot strapping coordinator.

My remark was meant to be general: I don’t see how would you enter any network without some degree of trust w.r.t. the entry point.
(An why would you even want to join something that you don’t trust in any sense?..)