Author:
(1) Egor Zuev (zyev.egor@gmail.com) Author: Author: (1) Egor Zuev (zyev.egor@gmail.com) Table of Links Abstract and 1. Introduction Abstract and 1. Introduction System model


Initial node state


Append process
4.1 Local append
4.2 Append from another node
4.3 Record validation
4.4 State consistency


Replication process


Proof of correctness


M-of-N connections


Extensions and optimizations System model System model System model Initial node state Initial node state Initial node state Append process
4.1 Local append
4.2 Append from another node
4.3 Record validation
4.4 State consistency Append process 4.1 Local append 4.1 Local append 4.2 Append from another node 4.2 Append from another node 4.3 Record validation 4.3 Record validation 4.4 State consistency 4.4 State consistency Replication process Replication process Replication process Proof of correctness Proof of correctness Proof of correctness M-of-N connections M-of-N connections M-of-N connections Extensions and optimizations Extensions and optimizations Extensions and optimizations References 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. safety and liveness 3. Initial node state Before the boot phase, each node should have the following properties (or settings): Property

Description

Data type

Example



Private key

generated with secp256k1 standard

String

“edca08af903bbd7afd356bb2d6fdf54901fad8770c734416456d382012b0608b”



Public key

generated with secp256k1 standard (from private key)

String

“02b68e80e752f13906179688171d6a0345a6c6edd20b52f24ea489275668fa1eac”



Min gossip interval

Minimum gossip interval (ms)

Number

150



Max gossip interval

maximum gossip interval (ms)

Number

300



Proof expiration

How long the proof is valid (ms)

Number

300



Nodes

An array of nodes (peers) addresses (should include network address + public key of the peer)

[string]

[ “tcp://127.0.0.1:2000/ 036032cc7790000ac98fc2dbc200c486b073e74e8e4ff5fba15beb01c153f4c458” ] Property

Description

Data type

Example



Private key

generated with secp256k1 standard

String

“edca08af903bbd7afd356bb2d6fdf54901fad8770c734416456d382012b0608b”



Public key

generated with secp256k1 standard (from private key)

String

“02b68e80e752f13906179688171d6a0345a6c6edd20b52f24ea489275668fa1eac”



Min gossip interval

Minimum gossip interval (ms)

Number

150



Max gossip interval

maximum gossip interval (ms)

Number

300



Proof expiration

How long the proof is valid (ms)

Number

300



Nodes

An array of nodes (peers) addresses (should include network address + public key of the peer)

[string]

[ “tcp://127.0.0.1:2000/ 036032cc7790000ac98fc2dbc200c486b073e74e8e4ff5fba15beb01c153f4c458” ] Property

Description

Data type

Example Property Property Description Description Data type Data type Example Example Private key

generated with secp256k1 standard

String

“edca08af903bbd7afd356bb2d6fdf54901fad8770c734416456d382012b0608b” Private key Private key generated with secp256k1 standard generated with secp256k1 standard String String “edca08af903bbd7afd356bb2d6fdf54901fad8770c734416456d382012b0608b” “edca08af903bbd7afd356bb2d6fdf54901fad8770c734416456d382012b0608b” Public key

generated with secp256k1 standard (from private key)

String

“02b68e80e752f13906179688171d6a0345a6c6edd20b52f24ea489275668fa1eac” Public key Public key generated with secp256k1 standard (from private key) generated with secp256k1 standard (from private key) String String “02b68e80e752f13906179688171d6a0345a6c6edd20b52f24ea489275668fa1eac” “02b68e80e752f13906179688171d6a0345a6c6edd20b52f24ea489275668fa1eac” Min gossip interval

Minimum gossip interval (ms)

Number

150 Min gossip interval Min gossip interval Minimum gossip interval (ms) Minimum gossip interval (ms) Number Number 150 150 Max gossip interval

maximum gossip interval (ms)

Number

300 Max gossip interval Max gossip interval maximum gossip interval (ms) maximum gossip interval (ms) Number Number 300 300 Proof expiration

How long the proof is valid (ms)

Number

300 Proof expiration Proof expiration How long the proof is valid (ms) How long the proof is valid (ms) Number Number 300 300 Nodes

An array of nodes (peers) addresses (should include network address + public key of the peer)

[string]

[ “tcp://127.0.0.1:2000/ 036032cc7790000ac98fc2dbc200c486b073e74e8e4ff5fba15beb01c153f4c458” ] Nodes Nodes An array of nodes (peers) addresses (should include network address + public key of the peer) An array of nodes (peers) addresses (should include network address + public key of the peer) [string] [string] [ “tcp://127.0.0.1:2000/ 036032cc7790000ac98fc2dbc200c486b073e74e8e4ff5fba15beb01c153f4c458” ] [ “tcp://127.0.0.1:2000/ 036032cc7790000ac98fc2dbc200c486b073e74e8e4ff5fba15beb01c153f4c458” ] Consensus parameters After the boot phase, the gossip protocol starts and local API (for appending new records) becomes available. This paper is available on arxiv under CC0 1.0 UNIVERSAL license. This paper is available on arxiv under CC0 1.0 UNIVERSAL license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Public

Multisig, Hashes, and the Math Behind Trustless Record Keeping

SCL: A Secure Concurrency Layer For Paranoid Stateful Lambdas: Optimizations

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

A Beginner’s Guide to the Authenticated Byzantine Gossip Protocol

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

15 Common Types of Unethical Behavior Found in Open-Source Projects

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

15 Common Types of Unethical Behavior Found in Open-Source Projects

7 Consensus Mechanisms Developers Must Know to BUIDL for Web3

BFT Consensus: Will Your Car Full of Passengers Turn Right, Left, or Fly Over a Cliff?

Consensus Protocol in Blockchain

ConsensusPedia: An Encyclopedia of 30+ Consensus Algorithms

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps