expected consensus timing rules

timing.md

Timing

And here begins one of the more annoying parts of implementing a distributed BFT consensus system. Everything relies on timing. And everyone around here loves things that rely on timing, right?

A blockchain is essentially a big expensive clock, where with each tick, a new block is produced. Proof of Work or Proof of SpaceTime by itself doesnt give us consensus. They just give us a clock. Traditional non-BFT systems also use clocks, but they can get away with less expensive clocks (like, wall clocks). The way we achieve consensus is by correctly following the clock, and using it to determine when each person is allowed to submit a state change and having a state transition selection heuristic (such as heaviest chain).

With PoST, our clock will ideally be very consistent. PoSTs are designed to take a relatively fixed amount of wall clock time, where PoW takes a Poisson distribution of time centered around some expected interval (10 minutes for bitcoin, 12 seconds for ethereum).

Each tick of that consistent clock will (probably) result in some number of nodes finding a winning ticket, crafting a block, and sending that out to the network. Clocks are sequential, meaning that one tick of a clock cannot start until the last one is complete. For us, that means that our 'clock tick' must reference the previous clock tick. Our PoST cannot start until we know the last clock tick. And since expected consensus defined each of those clock ticks to be potentially multiple PoSTs, we need to handle things appropriately. After checking if we are the winner of the current round (whether or not we win) we need to wait around for some time period to see if we get any other blocks from other peers, let's call this length of time D. We don't want to start on the next round too early, otherwise we may miss someone elses block, and we don't want to wait too long, otherwise the clock may start to drift. As a result of all this, the period of time that we sit waiting to hear about other blocks needs to be at the same time that every other miner in the world is also waiting to hear about other blocks, so that they all decide to start the next clock tick at the same moment, and finish that clock tick all around the same time.

This implies a few things about what our behaviour should be:

• Define a grace period time g. Where, If we receive a valid block for epoch T that results in a better tipset than we have already started mining on, and it is more than D+g past the end (as we observe it) of epoch T, we ignore it. However, if the new block is received between D and D+g, we halt our current mining process and restart on top of the new tipset.
• If we are working on a proof for epoch T+1, and we receive a block for epoch T+1 from another miner, we should begin the waiting period for blocks for T+2, and after D elapses, abandon our current work and start working on our proof for T+2. If we happen to complete our work during that waiting period, we should still broadcast our block, and attempt to mine on top of it (hoping that the block is received and validated by other miners before the D+g time window elapses).

Without the restriction of not including blocks received after D+g, a malcious miner could delay propogating their blocks until midway through the PoST generation process, causing all other miners to restart, and delaying the block time. Using this, an attacker with sufficient power could gain an advantage by stall all other miners long enough to mine a heavier chain including null blocks (attack needs thought)

______________________________________________________________________
|   D    | g |                 PoST     delay                         |
-----------------------------------------------------------------------
^- Epoch ^   ^                       ^
   Start |   |                       |
         |- Start mining here, but restart if you see a better tipset
             |                       |
             |- Don't restart mining on better tipset here
                                     |
                                     |
   If you get a better tipset here - |
   restart your epoch timer (but don't abandon mining until D has elapsed in case you
   complete your work in time to be included too). 
             

Selection of parameters:

• D should be enough to account for network-wide block propogation, but not more than that. Skewing D high gives miners willing to jump the gun a slight (but arguably not usable) advantage. D is really just here to avoid wasted work, as technically you could just start mining, and restart on every new better tipset until D+g.
• g should be selected such that D+g is the upper acceptable bound of reasonable network delays in block propogation.

Strategies for mining:

Strategy 1: Mine-at-every-block strategy:

• strategy:
  • on a new tipset:
    • c = ExtractChallenge(tipSet)
    • start p = PoStProve(c)
      • if win(p): post proof on chain
      • stop mining
• pro:
  • we get a fresh challenge at every proof
  • all the proof clocks re-align (a faster PostProve, will still have to wait for the new challenge from the chain))
• cons:
  • last-minute-miner: a malicious prover can delay doing the posts at each block, until the block before the proving period ends. In one block time, they would run all the proofs in parallel on multiple CPUs.
    • possible fix: For this to be secure the sealing time must be longer than proving period (impractical)
    • possible fix: This is not a rational behavior, since the malicious miner will not be able to win block reward (rational fix, but not security fix)

Strategy 2: Mine-at-every-block-but-chain-previous-proofs

• strategy:
  • on a new tipset:
    • c = ExtractChallenge(tipSet, lastP)
    • start lastP = PoStProve(c)
      • if win(lastP): post proof on chain
      • stop mining
• pro:
  • no last-minute-miner attack
• cons:
  • miner can grind challenge for the next post
  • ..?
• note: we shouldn't use incrementally verifiable computation, but we should prove all the post in batch when we want to post them.

Strategy 3: Keep-on-mining-on-failure

• strategy:
  • on miner starting proving period (this starts after a new clock reset for proofs):
    • c = ExtractChallenge(tipSet where your last challenge was posted (lookback tbd))
    • start proof = PoStProve(c, 1 blocktime)
      • if win(lastP): post proof on chain
      • continue mining PoStProveContinue(c, 1 blocktime) (this doesnt restart, but continues from the same cycle)

Strategy 4: Two-processes-mining (already discussed here)

• strategy:
  • Process 1 (periodic proofs): on miner starting proving period (this starts after a new clock reset for proofs):
    • c = ExtractChallenge(tipSet where your last challenge was posted (lookback tbd))
    • start proof = PoStProve(c, proving period blocktime (or interval required for posting proofs))
      • when done, post proof on chain
  • Process 2 (mining reward proofs): use strategy 1
• pro:
  • we separate the two proofs, one is for proving winning block, one for proving storage
  • we avoid the last-minute-miner since they have to run the first proof

Note to future readers: This was written when we were still thinking that we could use PoSts as the delay between blocks.