Remove kickout messages in TxFlow


#1

Informal TxFlow spec describes kickout messages:

Second , if by the time the Leader of epoch X+1 is ready to publish their representative message they have not seen yet the representative message for X yet, they post a special kind of a message on the DAG calling other validators to promise not to endorse X (or any other representative message with smaller epoch that is not approved by representative message of epoch X+1) should it appear in the future. We call such a message a kickout message. If another validator posts a message that approves a kickout message for block X, but doesn’t endorse the representative message for epoch X itself, no future message from such validator will be considered to be an endorsement for epoch X, even if such message approves the representative message for epoch X. If a validator posts a message that for the first time approves a kickout message for block X, but also approves the block X itself, it is still considered to be an endorsement of X.

Instead of using kickout messages & collecting endorsments, we can leverage the DAG itself to figure out if some epoch will be skipped.

Example:
Epoch 2 leader is malicious and has not posted the “epoch increase” message. If Epoch 3 leader observed 2/3n + 1 messages from other verifiers in epoch 2, leader posts a message. Now this message will be received by:

  • By verifier that still hasn’t seen epoch 2 leader’s message. Then they just post their message approving the epoch 3 leaders message
  • By verifier who has seen epoch 2 leader message. Naturally, they will approve both and gossip that.

Then logic for verifiers to consider when to finalize an epoch and form is block consists of:

  • If they see epoch T leader message that points at 2/3n+1 epoch T - 1 messages, they just start optimistically executing transactions.
  • If they don’t see epoch T leader message and see epoch T + 1 leader message then they wait either until they observe that message from T + 1 to collect 2/3n + 1 distinct verifier approvals (and use all messages it approves as epoch=T) or observing leader T message, whichever happens first.

Meaning, even if leader T + 1 leaves right after posting their message and T doesn’t show up, there will still be a block published because 2/3n + 1 will agree on that T + 1 message. In this case the next leader to post “epoch increase” is leader of T + 2.


An informal spec of TxFlow
#2

If they don’t see epoch T leader message and see epoch T + 1 leader message then they wait either until they observe that message from T + 1 to collect 2/3n + 1 distinct verifier approvals (and use all messages it approves as epoch=T) or observing leader T message, whichever happens first.

This is not a sufficient condition for a validator to assume the consensus was reached. Consider the following scenario:

  • T+1 is posted
  • T+1 accumulates 2/3-1 signatures
  • T is posted, and T+1 accumulates remaining signatures to have 2/3 +1
  • One validator observes T, and T+1 with 2/3+1 signatures, another validator observes T+1 with 2/3+1 signatures but not T.

Two validators reached two conflicting conclusions, and both think that their decision is what the consensus is reached upon.


#3

I have a concern which is probably a more specific issue of the more general issue outlined by Alex. The issue is that two verifiers will endup with two different sets of transactions: one set for verifier that observes leader T message, and another that observes that message from T+1 collects 2/3+ approvals.