ADR 030: Consensus Refactor

Context

One of the biggest challenges this project faces is to proof that the implementations of the specifications are correct, much like we strive to formaly verify our alogrithms and protocols we should work towards high confidence about the correctness of our program code. One of those is the core of Tendermint - Consensus - which currently resides in the consensus package. Over time there has been high friction making changes to the package due to the algorithm being scattered in a side-effectful container (the current ConsensusState). In order to test the algorithm a large object-graph needs to be set up and even than the non-deterministic parts of the container makes will prevent high certainty. Where ideally we have a 1-to-1 representation of the spec, ready and easy to test for domain experts.

Addresses:

Decision

To remedy these issues we plan a gradual, non-invasive refactoring of the consensus package. Starting of by isolating the consensus alogrithm into a pure function and a finite state machine to address the most pressuring issue of lack of confidence. Doing so while leaving the rest of the package in tact and have follow-up optional changes to improve the sepration of concerns.

Implementation changes

The core of Consensus can be modelled as a function with clear defined inputs:

  • State - data container for current round, height, etc.
  • Event- significant events in the network

producing clear outputs;

  • State - updated input
  • Message - signal what actions to perform
  1. type Event int
  3. const (
  4.     EventUnknown Event = iota
  5.     EventProposal
  6.     Majority23PrevotesBlock
  7.     Majority23PrecommitBlock
  8.     Majority23PrevotesAny
  9.     Majority23PrecommitAny
  10.     TimeoutNewRound
  11.     TimeoutPropose
  12.     TimeoutPrevotes
  13.     TimeoutPrecommit
  14. )
  16. type Message int
  18. const (
  19.     MeesageUnknown Message = iota
  20.     MessageProposal
  21.     MessageVotes
  22.     MessageDecision
  23. )
  25. type State struct {
  26.     height      uint64
  27.     round       uint64
  28.     step        uint64
  29.     lockedValue interface{} // TODO: Define proper type.
  30.     lockedRound interface{} // TODO: Define proper type.
  31.     validValue  interface{} // TODO: Define proper type.
  32.     validRound  interface{} // TODO: Define proper type.
  33.     // From the original notes: valid(v)
  34.     valid       interface{} // TODO: Define proper type.
  35.     // From the original notes: proposer(h, r)
  36.     proposer    interface{} // TODO: Define proper type.
  37. }
  39. func Consensus(Event, State) (State, Message) {
  40.     // Consolidate implementation.
  41. }

Tracking of relevant information to feed Event into the function and act on the output is left to the ConsensusExecutor (formerly ConsensusState).

Benefits for testing surfacing nicely as testing for a sequence of events against algorithm could be as simple as the following example:

  1. func TestConsensusXXX(t *testing.T) {
  2.     type expected struct {
  3.         message Message
  4.         state   State
  5.     }
  7.     // Setup order of events, initial state and expectation.
  8.     var (
  9.         events = []struct {
  10.             event Event
  11.             want  expected
  12.         }{
  13.         // ...
  14.         }
  15.         state = State{
  16.         // ...
  17.         }
  18.     )
  20.     for _, e := range events {
  21.         sate, msg = Consensus(e.event, state)
  23.         // Test message expectation.
  24.         if msg != e.want.message {
  25.             t.Fatalf("have %v, want %v", msg, e.want.message)
  26.         }
  28.         // Test state expectation.
  29.         if !reflect.DeepEqual(state, e.want.state) {
  30.             t.Fatalf("have %v, want %v", state, e.want.state)
  31.         }
  32.     }
  33. }

Consensus Executor

Consensus Core

  1. type Event interface{}
  3. type EventNewHeight struct {
  4.     Height           int64
  5.     ValidatorId      int
  6. }
  8. type EventNewRound HeightAndRound
  10. type EventProposal struct {
  11.     Height           int64
  12.     Round            int
  13.     Timestamp        Time
  14.     BlockID          BlockID
  15.     POLRound         int
  16.     Sender           int   
  17. }
  19. type Majority23PrevotesBlock struct {
  20.     Height           int64
  21.     Round            int
  22.     BlockID          BlockID
  23. }
  25. type Majority23PrecommitBlock struct {
  26.     Height           int64
  27.     Round            int
  28.     BlockID          BlockID
  29. }
  31. type HeightAndRound struct {
  32.     Height           int64
  33.     Round            int
  34. }
  36. type Majority23PrevotesAny HeightAndRound
  37. type Majority23PrecommitAny HeightAndRound
  38. type TimeoutPropose HeightAndRound
  39. type TimeoutPrevotes HeightAndRound
  40. type TimeoutPrecommit HeightAndRound
  43. type Message interface{}
  45. type MessageProposal struct {
  46.     Height           int64
  47.     Round            int
  48.     BlockID          BlockID
  49.     POLRound         int
  50. }
  52. type VoteType int
  54. const (
  55.     VoteTypeUnknown VoteType = iota
  56.     Prevote
  57.     Precommit
  58. )
  61. type MessageVote struct {
  62.     Height           int64
  63.     Round            int
  64.     BlockID          BlockID
  65.     Type             VoteType
  66. }
  69. type MessageDecision struct {
  70.     Height           int64
  71.     Round            int
  72.     BlockID          BlockID
  73. }
  75. type TriggerTimeout struct {
  76.     Height           int64
  77.     Round            int
  78.     Duration         Duration
  79. }
  82. type RoundStep int
  84. const (
  85.     RoundStepUnknown RoundStep = iota
  86.     RoundStepPropose       
  87.     RoundStepPrevote
  88.     RoundStepPrecommit
  89.     RoundStepCommit
  90. )
  92. type State struct {
  93.     Height           int64
  94.     Round            int
  95.     Step             RoundStep
  96.     LockedValue      BlockID
  97.     LockedRound      int
  98.     ValidValue       BlockID
  99.     ValidRound       int
  100.     ValidatorId      int
  101.     ValidatorSetSize int
  102. }
  104. func proposer(height int64, round int) int {}
  105. func getValue() BlockID {}
  107. func Consensus(event Event, state State) (State, Message, TriggerTimeout) {
  108.     msg = nil
  109.     timeout = nil
  110.     switch event := event.(type) {
  111.         case EventNewHeight:
  112.             if event.Height > state.Height {
  113.                 state.Height = event.Height
  114.                 state.Round = -1
  115.                 state.Step = RoundStepPropose
  116.                 state.LockedValue = nil
  117.                 state.LockedRound = -1
  118.                 state.ValidValue = nil
  119.                 state.ValidRound = -1
  120.                 state.ValidatorId = event.ValidatorId
  121.             } 
  122.             return state, msg, timeout
  124.         case EventNewRound:
  125.             if event.Height == state.Height and event.Round > state.Round {
  126.                state.Round = eventRound
  127.                state.Step = RoundStepPropose
  128.                if proposer(state.Height, state.Round) == state.ValidatorId {
  129.                    proposal = state.ValidValue
  130.                    if proposal == nil {
  131.                            proposal = getValue()
  132.                    }
  133.                    msg =  MessageProposal { state.Height, state.Round, proposal, state.ValidRound }
  134.                }
  135.                timeout = TriggerTimeout { state.Height, state.Round, timeoutPropose(state.Round) }
  136.             }
  137.             return state, msg, timeout
  139.         case EventProposal:
  140.             if event.Height == state.Height and event.Round == state.Round and 
  141.                event.Sender == proposal(state.Height, state.Round) and state.Step == RoundStepPropose { 
  142.                    if event.POLRound >= state.LockedRound or event.BlockID == state.BlockID or state.LockedRound == -1 {
  143.                        msg = MessageVote { state.Height, state.Round, event.BlockID, Prevote }
  144.                    }
  145.                    state.Step = RoundStepPrevote
  146.             }
  147.             return state, msg, timeout
  149.         case TimeoutPropose:
  150.             if event.Height == state.Height and event.Round == state.Round and state.Step == RoundStepPropose {
  151.                 msg = MessageVote { state.Height, state.Round, nil, Prevote }
  152.                 state.Step = RoundStepPrevote
  153.             }
  154.             return state, msg, timeout
  156.         case Majority23PrevotesBlock:
  157.             if event.Height == state.Height and event.Round == state.Round and state.Step >= RoundStepPrevote and event.Round > state.ValidRound {
  158.                 state.ValidRound = event.Round
  159.                 state.ValidValue = event.BlockID
  160.                 if state.Step == RoundStepPrevote {
  161.                     state.LockedRound = event.Round
  162.                     state.LockedValue = event.BlockID
  163.                     msg = MessageVote { state.Height, state.Round, event.BlockID, Precommit }
  164.                     state.Step = RoundStepPrecommit
  165.                 }
  166.             }
  167.             return state, msg, timeout
  169.         case Majority23PrevotesAny:
  170.             if event.Height == state.Height and event.Round == state.Round and state.Step == RoundStepPrevote {
  171.                 timeout = TriggerTimeout { state.Height, state.Round, timeoutPrevote(state.Round) }
  172.             }
  173.             return state, msg, timeout
  175.         case TimeoutPrevote:
  176.             if event.Height == state.Height and event.Round == state.Round and state.Step == RoundStepPrevote {
  177.                 msg = MessageVote { state.Height, state.Round, nil, Precommit }
  178.                 state.Step = RoundStepPrecommit
  179.             }
  180.             return state, msg, timeout
  182.         case Majority23PrecommitBlock:
  183.             if event.Height == state.Height {
  184.                 state.Step = RoundStepCommit
  185.                 state.LockedValue = event.BlockID
  186.             }
  187.             return state, msg, timeout
  189.         case Majority23PrecommitAny:
  190.             if event.Height == state.Height and event.Round == state.Round {
  191.                 timeout = TriggerTimeout { state.Height, state.Round, timeoutPrecommit(state.Round) }
  192.             }
  193.             return state, msg, timeout
  195.         case TimeoutPrecommit:
  196.             if event.Height == state.Height and event.Round == state.Round {
  197.                 state.Round = state.Round + 1
  198.             }
  199.             return state, msg, timeout
  200.     }
  201. }    
  203. func ConsensusExecutor() {
  204.     proposal = nil
  205.     votes = HeightVoteSet { Height: 1 }
  206.     state = State {
  207.         Height:       1
  208.         Round:        0          
  209.         Step:         RoundStepPropose
  210.         LockedValue:  nil
  211.         LockedRound:  -1
  212.         ValidValue:   nil
  213.         ValidRound:   -1
  214.     }
  216.     event = EventNewHeight {1, id}
  217.     state, msg, timeout = Consensus(event, state)
  219.     event = EventNewRound {state.Height, 0}
  220.     state, msg, timeout = Consensus(event, state)
  222.     if msg != nil {
  223.         send msg
  224.     }
  226.     if timeout != nil {
  227.         trigger timeout
  228.     }
  230.     for {
  231.         select {
  232.             case message := <- msgCh:
  233.                 switch msg := message.(type) {
  234.                     case MessageProposal:
  236.                     case MessageVote:    
  237.                         if msg.Height == state.Height {
  238.                             newVote = votes.AddVote(msg)
  239.                             if newVote {
  240.                                 switch msg.Type {
  241.                                     case Prevote:
  242.                                         prevotes = votes.Prevotes(msg.Round)
  243.                                         if prevotes.WeakCertificate() and msg.Round > state.Round {
  244.                                             event = EventNewRound { msg.Height, msg.Round }
  245.                                             state, msg, timeout = Consensus(event, state)
  246.                                             state = handleStateChange(state, msg, timeout)
  247.                                         }    
  249.                                         if blockID, ok = prevotes.TwoThirdsMajority(); ok and blockID != nil {
  250.                                             if msg.Round == state.Round and hasBlock(blockID) {
  251.                                                 event = Majority23PrevotesBlock { msg.Height, msg.Round, blockID }
  252.                                                 state, msg, timeout = Consensus(event, state)
  253.                                                 state = handleStateChange(state, msg, timeout)
  254.                                             } 
  255.                                             if proposal != nil and proposal.POLRound == msg.Round and hasBlock(blockID) {
  256.                                                 event = EventProposal {
  257.                                                         Height: state.Height
  258.                                                         Round:  state.Round
  259.                                                         BlockID: blockID
  260.                                                         POLRound: proposal.POLRound
  261.                                                         Sender: message.Sender
  262.                                                 }
  263.                                                 state, msg, timeout = Consensus(event, state)
  264.                                                 state = handleStateChange(state, msg, timeout)
  265.                                             }
  266.                                         }
  268.                                         if prevotes.HasTwoThirdsAny() and msg.Round == state.Round {
  269.                                             event = Majority23PrevotesAny { msg.Height, msg.Round, blockID }
  270.                                             state, msg, timeout = Consensus(event, state)
  271.                                             state = handleStateChange(state, msg, timeout)
  272.                                         }
  274.                                     case Precommit:    
  276.                                 }
  277.                             }
  278.                         }
  279.             case timeout := <- timeoutCh:
  281.             case block := <- blockCh:    
  283.         }
  284.     }
  285. }
  287. func handleStateChange(state, msg, timeout) State {
  288.     if state.Step == Commit {
  289.         state = ExecuteBlock(state.LockedValue)
  290.     }    
  291.     if msg != nil {
  292.         send msg
  293.     }    
  294.     if timeout != nil {
  295.         trigger timeout
  296.     }    
  297. }

Implementation roadmap

  • implement proposed implementation
  • replace currently scattered calls in ConsensusState with calls to the new Consensus function
  • rename ConsensusState to ConsensusExecutor to avoid confusion
  • propose design for improved separation and clear information flow between ConsensusExecutor and ConsensusReactor

Status

Draft.

Consequences

Positive

  • isolated implementation of the algorithm
  • improved testability - simpler to proof correctness
  • clearer separation of concerns - easier to reason

Negative

Neutral