Hare Protocol Implementation
This page will describe the design and implementation details of the hare protocol. It is mainly intended for programmers who want to use it as a reference implementation. It is suggested to have a good understanding of the Hare protocol. See the suggested reading below for a good starting point.
The Hare protocol is used to achieve consensus on a set of values. Most of the protocol's logic is done in algorithm.go. This implementation supports having more than one concurrent consensus process as you shall see later on when we describe the broker and the orchestrator. The role of the Hare protocol in the Spacemesh stack is to achieve a faster and more secure mesh validation by using the results of the Hare protocol as votes in the mined block. I.e. each block created by a miner will include explicit votes on a set of valid blocks as received from the Hare protocol.
We are using XDR3 for message serialization which optional values.
All messages are the tuple of a message and a signature.
Message struct {
Sig []byte
InnerMsg *innerMessage
}
An inner message is an actual message. The message can take different forms depending on the provided type (PreRound/Status/Proposal/Commit/Notify): (Status, instanceID, K, Ki, Values) (Proposal, instanceID, K, Ki, Values, SVP) (Commit, instanceID, K, Ki, Values) (Notify, instanceID, K, Ki, Values, Certificate)
innerMessage struct {
Type messageType
InstanceID instanceID
K int32 // the round counter
Ki int32
Values []types.BlockID // the set. optional for commit InnerMsg in a certificate
RoleProof []byte // role is implicit by InnerMsg type, this is the proof
Svp *aggregatedMessages // optional. only for proposal Messages
Cert *certificate // optional
}
aggregatedMessages struct {
Messages []*Message
}
Values are optimized out of commit messages in a certificate. The set of values can be recovered since it is the same set for all commit messages.
certificate struct {
Values []types.BlockID // the committed set S (same for all messages)
AggMsgs *aggregatedMessages
}
Since there may be multiple concurrent consensus processes, we use a broker to dispatch the incoming messages of the protocol to the matching consensus process instance. The broker supports registration and un-registration of instances. On an incoming Hare message, the broker will check message validity and report back to the p2p layer (see Reporting Validation to P2P). If validation succeeds, the broker will peek inside the message to check the instance id for which the message is intended. If there is no registered process for this instance id, it will be buffered and passed later (see Early Messages). Otherwise, the broker will pass the messages to the registered instance (through the corresponding channel).
The consensus process (CP) is the implementation of the Hare protocol's logic.
After the CP starts, the protocol follows the rounds logic.
Since each round has different messages and logic, we delegate some of that logic to trackers.
Each message type has its corresponding tracker which keeps track of the relevant state for the specific message type.
We have five trackers corresponding to five message types:
-
PreRoundTracker- for each value, tracks the number of unique pre-round messages that included that value. It can be queried to check if a set is provable by pre-round messages and to filter non-provable values from a given set. -
StatusTracker- tracks status messages. It can be asked to validate the current status messages, check if the SVP is ready, build an SVP for a proposal and retrieve the proposal set. -
ProposalTracker- Tracks proposal messages in order to keep track of the leading proposed set and detect conflicting proposals. -
CommitTracker- tracks commit messages so we can build the corresponding certificate if we have collected sufficient commits. -
NotifyTracker- track notification messages per set. It can be asked for the number of notifications we witnessed (for a specific set) and if we witnessed a specific certificate.
Note: all trackers assume that the messages they receive are syntactically valid.
The eligibility package provides the ability to manage roles, i.e., to decide if a participant (including the current node) is eligible to participate in a given round of some layer.
The Hare Beacon provides the value under consensus. The Hare Oracle manages the eligibility queries by validating the VRF message and checking that the participant passed the active threshold for this round.
Note: the "active" and "leader" roles are determined the same way: they only differ by the thresholds. We set the expected number of leaders to more than one since we want to lower the probability that the proposal round will end with no leaders (we trade communication for lower probability). In order to deal with more than one leader in a proposal round (which can happen even with 1 expected leader), we rank the leaders (all actives in the proposal round) and pick the lowest-ranked leader (see proposal tracker).
Message validation is separated into two parts, the MessageValidator and EligibilityValidator. The former is used in the CP while the latter is used in the broker. The Hare should report back to the p2p layer about the result of a message validation. Contextual validation in CP is more delicate as the result may change between nodes and hence is not taken into account in the report back to the p2p layer (see Reporting Validation to P2P). That is the reason for the separation of these two validators.
The message validator is used to validate messages in the CP. It exposes two main validation methods, one to validate syntax and the other to validate the context. This separation is beneficial since inner messages (for example, in a certificate or an SVP) wouldn't require contextual validation.
The eligibility validator is used to validate messages on the broker level. This validation is part of the report sent back to the p2p layer (see Reporting Validation to P2P). It exposes a Validate method that validates the role of the sender.
The orchestrator keeps track of all running CPs. It is also in charge of collecting the CP outputs and can be queried for the output matching a specific instance (with a limited buffer).
The P2P layer has a mechanism that requires gossip-based protocols to report back to it with the result of the message validation. This mechanism prevents honest nodes from propagating invalid messages over the gossip network. We decided to include in the report only the contextual (broker-wise, meaning we accept only messages close to the current layers we are handling) eligibility and signature validations as both are independent of time drifts and context.
Currently, syntax validation is not included in the report since it is not as important in terms of malicious behavior. Following that need, we divide the validation logic into two: 1. Syntax and contextual validation used in the CP. 2. Contextual, eligibility and signature validation used in the broker. This way, the broker can unburden the ConsensusProcess from the responsibility to report back to the P2P layer.
Notes:
- While referring to contextual validation in both the broker and the CP, the former refers to layer context while the latter refers to round/iteration context.
- We are using ED25519 with public key extraction. So message validation is more tricky - the messages do not include the public key, it is extracted from the message and then checked against the system if we already know this sender.
Due to time drift, messages may appear as too early for some nodes. We want to allow buffering of messages that are intended for round r+1 even if they have arrived on round r. This required adjustments in two parts:
-
Broker- if an early message is received before the correspondingConsensus Processhas registered, we will not have an instance to dispatch the messages to. We currently buffer all early messages and pass them to the instance when it registers. -
Consensus Process- after validating the syntax we usecontextual validationto decide whether we should process the message in this round (contextually valid), buffer the message for the next round (early message) or ignore the message otherwise (contextually invalid).
The FixedRolacle is an intermediate implementation of the eligibility oracle which is used only for testing purposes. A fixed size committee is free of probability and hence:
- We cannot get a significantly bigger/smaller committee, just the exact provided size. This is especially required for testing since the typical numbers used are much lower and hence introduces higher variance.
- We have better control over the number of active honest/dishonest nodes.
Unit tests use many mocks in order to achieve high coverage. For example, you can find mocks of the p2p, message validation, roles oracle, different trackers and consensus process. When writing unit tests we recommend you consider both your needs and the available mocks. Of course, you are encouraged to add new ones as needed.
- E2E tests use the p2p simulator. Examples can be found in
consensus_test.go. - Integration tests use the real p2p implementation in our system. Examples can be found in integration_test.go.
- A customizable p2p mock is used to create abnormal behavior in the P2P. Examples can be found in flows_test.go.
- cmd/hare is the app for running E2E tests of hare&p2p in a single app. We used it in our automation tests.
- A high level, contextual explanation of the Hare protocol
- Hare Protocol
- Hare Go-Docs