Part 1: PoT without block injection
Consider a scenario where we have two timekeepers (who generate PoT outputs for each and every time slot): one honest and one malicious. They have the same hardware (which is sometimes referred to as the static hardware assumption). For simplicity, consider the case that c tends to infinity (i.e., no block injection). Then, if we have a delay bound \Delta, every farmer can obtain a correct PoT output within 2 \Delta when this output was generated.
To make it more concrete, suppose that both timekeepers generate a PoT output at time t. Then, this PoT output will arrive at the other timekeeper as well as all the farmers by t + \Delta. If the malicious timekeeper generated an incorrect output at time t, then the honest timekeeper will detect this error by t + \Delta and generate a fraud proof, which will reach all the farmers by t + 2 \Delta. This allows farmers to detect incorrect PoT and accept correct PoT. Therefore, if both timekeepers generate a PoT output for time slot t + 2 \Delta at time t, then all the farmers can obtain the correct PoT for slot t + 2\Delta on time. Clearly, some farms may obtain the correct PoT in advance.
But, what if the delay bound \Delta is violated? Then, some farmers may not obtain the correct PoT on time. In the worst case, all the farmers obtain incorrect PoT for a long time. Hence, we need a fall-back mechanism. Imagine that all the farmers use an incorrect PoT output due to an unexpected network delay larger than \Delta. Eventually, the honest timekeeper will generate a fraud proof, which will arrive at all the farmers. This fraud proof will trigger a fall-back event, making all the existing blocks generated after the incorrect PoT invalid. Say, this incorrect PoT is for time slot t’. Then, all the farmers have to delete all invalid blocks and quickly catch up from time t’ to the current time.
Part 2: PoT with block injection
Again, we consider a scenario with two timekeepers. Now, c is finite. That is, the sequence of PoT outputs depends on the underlying branch of the block tree. Specifically, the randomness of B_c (such as block hash) will be injected into the seed for time slot t_c + T (where B_c is generated at t_c). This complicates the design and analysis. Our strategy is to keep the case with block injection as close as possible to the case without block injection.
Timekeepers: They evaluate and maintain a PoT tree based on the underlying block tree. To reduce resource usage, each timekeeper only keeps k active PoT branches based on its local top-k longest chains. Timekeepers evaluate their PoT trees unless there is a heavier chain beyond their current tree (which switches them to the verification mode). Since verification is much faster than evaluation, timekeepers are still OK as long as the number of heavier chains to be verified is relatively small.
Claim: Under the bounded delay model, a farmer can obtain a correct PoT output within 2 \Delta when this output was generated as long as the following conditions are true
- The honest timekeeper is not overloaded (say, by valid or invalid heavier chains)
- The farmer’s local longest chain is one of the top-k longest chains observed by the honest timekeeper
Farmers: They maintain a PoT tree based on the outputs and fraud proofs from the timekeepers. Once a farmer receives a new block that extends its longest chain, it will check whether the associated PoT outputs in the block header are available in its PoT tree. If yes, it is an easy case. If no, it waits for a challenge period 2 \Delta during which it can do probabilistic verification.
Claim: Under the bounded delay model, a farmer can obtain a fraud proof for a new block with incorrect PoT within 2 \Delta as long as the following conditions are true
- The new block extends one of the top-k longest chains observed by the honest timekeeper
- The honest timekeeper is not overloaded
Two main issues still remain. First, what if the delay bound \Delta is violated? Second, what if the honest timekeeper is overloaded? We will discuss these two issues in Part 3.
Part 3: Discussing two issues
Two error events may happen if the delay bound is violated or the honest timekeeper is overloaded.
Error event 1: The farmers cannot obtain correct PoT outputs on time.
For this event, once the farmers receive the fraud proof later on, they will use the fall-back mechanism, making all the existing blocks generated along the incorrect PoT chain invalid and then catching up as discussed in Part 1.
Error event 2: The farmers accept a block with incorrect PoT.
For this event, the farmers will eventually reject this invalid block (due to incorrect PoT) as well as other blocks affected by this PoT.
To sum up, everything seems to be good if the delay bound is never violated and the honest timekeeper is never overloaded. However, it is inexpensive to create heavier chains with incorrect PoT as we discussed here about one month ago. This family of attacks can be mitigated by introducing a challenge period with probabilistic verification as well as an efficient fall-back mechanism.