Certification for Hare (WIP)

[sidsankhe]

Overview and Motivation

We propose adding a new role, that of a Hare Certifier, which publishes the results of the Hare algorithm when it terminates. This is advantageous for the following reasons:

• Parties that are not participating in the Hare can ignore all Hare messages, and can only care about the published output from the Hare Certifiers. Therefore, any node can know for sure if Hare terminated, and honest parties will not disagree on whether the Hare terminated successfully or not, if it aborts as a result of a timeout.
• The above "black-boxing" also helps with sync. Otherwise, you'd have to receive messages for the past hdist layers in order to determine how to vote.
• Future optimizations: might run the Hare on a separate network to optimize for bandwidth, and have the full gossip network only see the published output of the Hare certifier.

High-level Design

A committee for Certification will be chosen based on the VRF (with an input possibly being the layer number and a special character for Certification). This committee will not be updated per round, but will last for the entire duration of the Hare algorithm on that given layer. The committee will listen to the Hare conversation, recording notify messages on all sets of values that they see. Once this committee accumulates f+1 notify messages on a set, it will deem that the Hare has terminated, will create and sign this output set, and gossip it to the entire network. This is an accurate instance for Hare terminating, because it means that the rest of the network should also see f+1 notify messages on the same set, indicating that all honest parties would terminate.

Proposed Implementation

Augment the Hare code to:

• On kicking off the Hare protocol for a given layer, check whether the node is eligible to be a Hare Termination Certifier
• Store state for each incoming notify message in order to gauge Hare termination
• On f+1 notify messages, broadcast the signed output set (along with the SVP) as a special Hare message
• On receiving the special Hare message, all nodes should store it temporarily, until hdist layers have passed

Implementation Plan

• Write tests for the proposed behavior. Augment hare/algorithm_test.go and add test files for all the new files added.
• Implement Eligibility checks for Hare Termination Certifier using VRF.
• Implement state that gets updated on each subsequent notify message
• Implement output set sending and receiving

Questions

1. Should nodes in the active set listen for Hare termination messages? If they receive a Hare termination message with a valid signature, should they store it and terminate? Where should these messages be stored?
2. Should there be a way for the nodes to listen to the output of only the Hare termination messages?
3. What does a node need to do if it successfully listens to the output of the Hare certifier, i.e. gets a valid termination message. Does it need to do anything other than simply store this message?
4. What does contextual validity mean for the certification messages? Are all received certification messages contextually valid?

Stakeholders and Reviewers

TBD

[lrettig]

A committee for Certification will be chosen based on the VRF (with an input possibly being the layer number and a special character for Certification)

I propose that we use no "special character" - the VRF input for the certification is just the layer number (round ID).

[countvonzero]

implemented