IntersectMBO / IntersectMBO/ouroboros-consensus
Anticipate slot leaders forging invalid blocks
- Dominant language
- Haskell
- Stars
- 67
- Forks
- 43
- Avg merge
- 5d 13h
- Merged PRs (30d)
- 43
Description
The `determineForkLength` function
https://github.com/input-output-hk/ouroboros-network/blob/489f8e3bf174bb2d15561fc1a06cdab9c966aef8/ouroboros-consensus/test-consensus/Test/Dynamic/Util/Expectations.hs#L99-L103
computes the acceptable upper bound on fork length at the end of each test run, i.e. how many blocks a final chain can have on it beyond the common prefix shared by all final chains. This is used to check final chains in `Test.Dynamic.General.prop_general` and so in all consensus tests:
```
-- | Consensus protocol to use
data Ouroboros.Consensus.Protocol.Protocol blk where
-- | Run BFT against the mock ledger
ProtocolMockBFT :: ... -> Protocol (SimpleBftBlock SimpleMockCrypto BftMockCrypto)
-- | Run Praos against the mock ledger
ProtocolMockPraos :: ... -> Protocol (SimplePraosBlock SimpleMockCrypto PraosMockCrypto)
-- | Run Praos against the mock ledger but with an explicit leader schedule
ProtocolLeaderSchedule :: ... -> Protocol (SimplePraosRuleBlock SimpleMockCrypto)
-- | Run PBFT against the mock ledger
ProtocolMockPBFT :: ... -> Protocol (SimplePBftBlock SimpleMockCrypto PBftMockCrypto)
-- | Run PBFT against the real ledger
ProtocolRealPBFT :: ... -> Protocol (ByronBlockOrEBB ByronConfig)
```
This Issue concerns the `LeaderSchedule` argument to `determineForkLength`. That function currently assumes that a node leading a slot will forge a block and add it to its chain and then every connected node will via ChainSync/BlockFetch also receive and switch its chain to that block. This assumption holds for `ProtocolMockBFT` and `ProtocolMockPraos`, but the forging of invalid blocks can violate it for `ProtocolLeaderSchedule`, `ProtocolMockPBFT`, nor `ProtocolRealPBFT`.
* In the `ProtocolMockBFT` test, block validity is unrelated to the (round-robin) leader schedule.
* In the `ProtocolMockPraos` test, the argument to `determineForkLength` is the leader schedule observed _a posteriori_ by inspecting the blocks in the final chains. That leader schedule is therefore incomplete, excluding those leaders whose blocks didn't reach the final chains. In particular, nodes that forged an invalid block in a slot will not be reported as leading that slot.
* In the `ProtocolLeaderSchedule` test, I'm not sure if the `PraosInsufficientStake` poses the same kind of risk as does `PBftExceededSignThreshold`, explained below.
* For `ProtocolMockPBFT` and `ProtocolRealPBFT`, the block forged by a slot leader may be invalid. For example, if one node joins the network much earlier than the rest, it will eventually create blocks invalid according to `PBftExceededSignThreshold`. The `determineForkLength` function currently does not anticipate that.
Failing to anticipate `PBftExceededSignThreshold` and similar could lead `determineForkLength` to artificially inflate the upper bound, which makes our tests unnecessarily lax. It could also go the other way, making them incorrectly strict: the only time `determineForkLength` lowers its work-in-progress upper bound is when a slot has a single leader; that resets the bound to `0`, since it should put the network in consensus. But if that sole leader actually forged an invalid block, the network would not return to consensus, possibly causing the test to fail.
In spite of the above explanation, I haven't seen `prop_general` fail due to block invalidity. This Issue can be completed in two possible ways:
* Find a repro that fails this way, (ideally) re-tune generators to find similar, and refine `determineForkLength` accordingly.
* Determine and explain here why `prop_general` is not failing due to an incorrectly low upper bound, and possibly do something to avoid inflating the upper bound.
Contributor guide
Research direction
Start with determineForkLength in ouroboros-consensus/test-consensus/Test/Dynamic/Util/Expectations.hs and trace how Test.Dynamic.General.prop_general uses its bound. Investigate invalid blocks under the listed protocol variants and seek a prop_general reproduction involving PBftExceededSignThreshold or similar forging failures. Done means either a reproducible, retuned test with a corrected bound or a documented explanation of why the bound cannot become incorrectly low, with any needed safeguard.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- haskell
- Domain
- blockchain, distributed-systems
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100