New consensus algorithm with timestamps draft proposal

Goal: Assuming that all forks are malicious or bad programming, the network should spend the least amount of resources resolving them and be the most efficient in validating non-fork transactions.

Model:

  • Partial synchrony: all messages are delivered within d, but d is unknown.
  • n nodes = f/3 + 1, f byzantine nodes.
  • Quorum: f x 2 + 1.
  • l is the local timestamp of a node.
  • t is the timestamp of a transaction.
  • v is the timestamp of a vote.
  • s is the maximum difference in synchronization with real time using NTP (or NTS, which protects against man in middle attacks).
  • p is the maximum processing time from receiving a message and sending a response.
  • Assumption: Honest nodes vote on the first transaction they see on a given election and don’t change their vote.

Consensus algorithm:

  • Node receives a transaction with timestamp t.
  • Checks if the timestamp of the transaction is valid with t - s <= l <= t + s + d.
  • Checks if the transaction is valid.
  • If both yes, checks if there is already an election created with the hash of the transaction.
    • If no:
      • Creates an election with expiration t + 3p + 3d + s, the upper bound of a valid vote plus p for the processing time.
      • Broadcasts the transaction and a vote on the transaction with timestamp v.
    • If yes, do nothing (we are in the presence of a fork and a previous conflicting transaction was already voted in previously).
  • Receives votes on the election (can be received before the transaction).
  • Checks if the votes are valid with:
    • t - s <= v <= t + s + p + d. The timestamp of the vote v needs to be valid relative to the timestamp of the transaction t.
    • t - s <= l <= t + 2p + 3d + s. The upper bound needs to be long enough so that a vote from a malicious node broadcasted by an honest node is valid, otherwise a malicious party could send a vote only to some nodes, that would achieve quorum, and the others don’t.
  • If valid, broadcasts the votes to the network.
  • If quorum is achieved by some transaction of the election before the election expires, confirm that transaction. Otherwise drop the election and all the transactions in it.

Note: Timing parameters can be arbitrarily large to be safe, since only the resolution of forks will be affected.

Advantages:

  • Allows for ordering of transactions, which simplifies bootstrapping and network upgrades.
  • Less communication complexity: O(n) vs O(n^2).
  • Less latency (1 message delay in the optimistic case, 2 message delays in the pessimistic case).
  • Compatibility with PoS/TaaC.
3 Likes