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 ¶
const ( BVAL msgVoteType = iota AUX )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ABA ¶ added in v1.0.3
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.