mostefaoui

Documentation

Overview

Copyright 2020 IOTA Stiftung SPDX-License-Identifier: Apache-2.0

Here we implement the Asynchronous Byzantine Binary Agreement by Mostefaoui et al., as described in the HBBFT paper:

> Miller, A., Xia, Y., Croman, K., Shi, E., and Song, D. (2016). The Honey Badger of > BFT Protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer > and Communications Security, CCS ’16, page 31–42, New York, NY, USA. > Association for Computing Machinery.

The original paper by Mostefaoui is:

> A. Mostefaoui, H. Moumen, and M. Raynal. Signature-free > asynchronous byzantine consensus with t< n/3 and o (n 2) > messages. In Proceedings of the 2014 ACM symposium on > Principles of distributed computing, pages 2–9. ACM, 2014.

The HBBFT paper presents the algorithm as follows:

> • upon receiving input b_input, set est_0 := b_input and proceed as > follows in consecutive epochs, with increasing labels r: > – multicast BVAL_r(est_r) > – bin_values_r := {} > – upon receiving BVAL_r(b) messages from f + 1 nodes, if > BVAL_r(b) has not been sent, multicast BVAL_r(b) > – upon receiving BVAL_r(b) messages from 2f + 1 nodes, > bin_values_r := bin_values_r ∪ {b} > – wait until bin_values_r != {}, then > ∗ multicast AUX_r(w) where w ∈ bin_values_r > ∗ wait until at least (N − f) AUX_r messages have been > received, such that the set of values carried by these > messages, vals are a subset of bin_values_r (note that > bin_values_r may continue to change as BVAL_r messages > are received, thus this condition may be triggered upon > arrival of either an AUX_r or a BVAL_r message) > ∗ s ← Coin_r.GetCoin() > ∗ if vals = {b}, then > · est_r+1 := b > · if (b = s%2) then output b > ∗ else est_r+1 := s%2 > • continue looping until both a value b is output in some round r, > and the value Coin_r' = b for some round r' > r.

Additionally we add the STOP messages to make this algorithm terminating. The STOP messages are discussed in the original paper by Mostefaoui.

This implementation is split to several parts to handle various rance conditions easier.

• varBinVals -- maintains the binValues variable and handles the BVAL messages.
• varAuxVals -- maintains the `vars` variable and handles the AUX messages.
• varDone -- tracks the termination condition for the algorithm.
• uponDecisionInputs -- a predicate waiting for the CC and AuxVals to be ready.

All these parts are independent of each-other and are wired-up in this file. With these parts defined, the overall algorithm can be rephrased as follows:

> • upon receiving input b_input, set est_0 := b_input and proceed as > follows in consecutive epochs, with increasing labels r: > - start the round r (for varBinVals, CC and others). > - on each varBinVals update pass it to varAuxVals. > - wait until varAuxVals != {} and s ← Coin_r.GetCoin() > ∗ if vals = {b}, then > · est_r+1 := b > · if (b = s%2) then output b > ∗ else est_r+1 := s%2 > • continue looping varDone is true.

Index

• Constants
• type ABA
  • func New(nodeIDs []gpa.NodeID, me gpa.NodeID, f int, ...) ABA
• type Output

Constants

const (
	BVAL msgVoteType = iota
	AUX
)

Types

type ABA

type ABA interface {
	AsGPA() gpa.GPA
}

Public API for this protocol.

func New

func New(nodeIDs []gpa.NodeID, me gpa.NodeID, f int, ccCreateFun func(round int) gpa.GPA, log *logger.Logger) ABA

Creates a single node for a consensus.

Here `ccCreateFun` is used as a factory function to create Common Coin instances for each round. This way this implementation is made independent of particular CC instance. The created CC is expected to take `nil` inputs and produce `*bool` outputs.

type Output

type Output struct {
	Value      bool
	Terminated bool
}

This structure is provided as an output of the algorithm. If the value is undecided, untyped nil is returned. The Terminate field indicates, if this algorithm can be dropped (no other peers need any messages from this node).