PBFT Fair Transaction Ordering Extension

gistfile1.txt

1. When a batch arrives, add it to a queue and include a "skip count" and the
   queue size when it was added
2. When a block is committed, remove batches from the front of the queue until
   all batches in the block have been removed. If a batch is not in the block,
   increase its skip count and save it. Push all batches that were skipped back
   onto the front of the queue, preserving the original order.
3. While pushing batches back onto the queue, check that the batch isn't being
   intentionally skipped by the validator:

    a. Check if the skip_count (S) is greater than the size of the queue when
       it was added (q_add) divided by the average throughput (T_avg)

          S > (q_add / T_avg)

    b. T_avg = sum((batches / block) for last N blocks) / N

4. If a batch is being intentionally skipped, consider the leader faulty and
   start a view change.

Note: This doesn't prevent a bad leader from re-ordering batches, but does
require that it include them eventually, even on a busy network.