A Beginner’s Guide to the Authenticated Byzantine Gossip Protocol

Table of Links

Abstract and 1. Introduction

2. System model

3. Initial node state

4. Append process

   4.1 Local append

   4.2 Append from another node

   4.3 Record validation

   4.4 State consistency

5. Replication process

6. Proof of correctness

7. M-of-N connections

8. Extensions and optimizations

References

Abstract

ABGP refers to Authenticated Byzantine Gossip Protocol. The ABGP is a partial-synchronous, weak consistent, BFT based consensus algorithm. The algorithm implements the gossip protocol, but with BFT features inside (like multisig record approval). The algorithm has been developed as an alternative to classic private ledger solutions, like Hyperledger.

1. Introduction

ABGP is a partial-synchronous, weak consistent BFT algorithm. The algorithm implies that all nodes in network are known. To make sure, that there is no malicious node connected to network, ABGP use authentication approach. This means, that all proposed state mutations should be signed by nodes who propose it, or accept (until the final mutli-signature will be built). The replication between nodes happens by standard gossip protocol in one step: one node request for new changes from another, and another node sends back either new changes, or an empty array, if there are no new changes. On new record replication, the acceptor node, validate this record’s signature, in order to make sure that it has been signed by known nodes. The algorithm offers both liveness and safety for at most 𝑁 = 2𝑓 + 1 with quorum of 𝑄 = 𝑓 + 1, where N – the number of nodes in cluster and 𝑓 – is the number of faulty nodes in case of N-to-N connections. However, in case of M-of-N connections, the quorum may be much smaller.

2. System model

The system model represents a partially synchronous system, where nodes are connected by the network. We assume that the network may duplicate, fail to deliver, or deliver with delays messages. We also assume, that every node may become failed. By failed we mean malicious behavior, or just out-of-order.

The system is partially synchronous, which means that we expect delays / duplicates / message lost in the system. The communication between node is bi-directional, which means, if node A sends message to node B, then node B should send message to node A as a reply (like an HTTP request).

The system requires to be aware of all other nodes in the system. It means, that each node should have a bootstrapped list of all other nodes in the network. This bootstrap list should include address of node (which is optional in case of M-of-N connections) and public keys of all other nodes.

The algorithm uses ECC cryptography for signing purpose. Once enough nodes sign the hash of the record, the last node, which signed the hash – creates a multisignature. This is a part of “authentication mechanism”.

The term “authentication” means, that all mutation actions in algorithm should be signed and validated by its members (i.e. nodes). While “sign” action – means signing the record, the validation – means signature / multisignature validation.

The replication process inherits the gossip protocol properties: node choose randomly another peer in network and ask recent updates.

The algorithm guarantees safety and liveness as long as 𝑁 ≥ 2𝑓 + 1 for N-of-N connections. The safety property means that all healthy nodes agree on the certain change, sign it and apply to the state. The liveness means that even if 𝑓 nodes fail, the network will still be operatable.

3. Initial node state

Before the boot phase, each node should have the following properties (or settings):

Consensus parameters

After the boot phase, the gossip protocol starts and local API (for appending new records) becomes available.