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 5. Replication process The algorithm uses Gossip-like approach for replication and works as follows: Gossiping happens in an infinite loop. On each loop (let’s call it round) node (let’s call it node A) choose randomly one peer (let’s call it node B) with which it should gossip.


Then node A sends message to node B. The message includes timestamp and timestamp index from which node A expects to get updates from node B. It’s like a pagination (i.e. give me all records, which timestamp is higher than <some timestamp>). Also keep in mind, that node A should store last requested timestamp and timestamp index for node B (in order not to request the same records again). If there wasn’t communication before, then node A sends timestamp = 0 and timestampIndex = 0


Node B prepare an array of records which satisfy the provided timestamp and timestampIndex from node A (i.e. filter 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝|| (𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 === 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 && 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥))


Node B sends records back to Node A as array of records with some limit (like no more than 10 records in one request, to prevent traffic flooding). The limit option can be set in algorithm parameters


Node A receive these records, sort them in ASC order, and apply them (the logic is described in “Append process / append from another node”)


After append, node A updates last requested timestamp and timestampIndex for node B to the timestamp and timestampIndex from the last record received from node B (sorted in ASC order)


Then protocol awaits for random amount of milliseconds taken from range (the minimum and maximum time is specified in consensus parameters, check section 2). Once timeout expires – the process starts over Gossiping happens in an infinite loop. On each loop (let’s call it round) node (let’s call it node A) choose randomly one peer (let’s call it node B) with which it should gossip. Gossiping happens in an infinite loop. On each loop (let’s call it round) node (let’s call it node A) choose randomly one peer (let’s call it node B) with which it should gossip. Then node A sends message to node B. The message includes timestamp and timestamp index from which node A expects to get updates from node B. It’s like a pagination (i.e. give me all records, which timestamp is higher than <some timestamp>). Also keep in mind, that node A should store last requested timestamp and timestamp index for node B (in order not to request the same records again). If there wasn’t communication before, then node A sends timestamp = 0 and timestampIndex = 0 Then node A sends message to node B. The message includes timestamp and timestamp index from which node A expects to get updates from node B. It’s like a pagination (i.e. give me all records, which timestamp is higher than <some timestamp>). Also keep in mind, that node A should store last requested timestamp and timestamp index for node B (in order not to request the same records again). If there wasn’t communication before, then node A sends timestamp = 0 and timestampIndex = 0 Node B prepare an array of records which satisfy the provided timestamp and timestampIndex from node A (i.e. filter 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝|| (𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 === 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 && 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥)) Node B prepare an array of records which satisfy the provided timestamp and timestampIndex from node A (i.e. filter 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝|| (𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 === 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝 && 𝑟𝑒𝑐𝑜𝑟𝑑𝐵.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥 > 𝑟𝑒𝑐𝑜𝑟𝑑𝐴.𝑡𝑖𝑚𝑒𝑠𝑡𝑎𝑚𝑝𝐼𝑛𝑑𝑒𝑥)) Node B sends records back to Node A as array of records with some limit (like no more than 10 records in one request, to prevent traffic flooding). The limit option can be set in algorithm parameters Node B sends records back to Node A as array of records with some limit (like no more than 10 records in one request, to prevent traffic flooding). The limit option can be set in algorithm parameters Node A receive these records, sort them in ASC order, and apply them (the logic is described in “Append process / append from another node”) Node A receive these records, sort them in ASC order, and apply them (the logic is described in “Append process / append from another node”) After append, node A updates last requested timestamp and timestampIndex for node B to the timestamp and timestampIndex from the last record received from node B (sorted in ASC order) After append, node A updates last requested timestamp and timestampIndex for node B to the timestamp and timestampIndex from the last record received from node B (sorted in ASC order) Then protocol awaits for random amount of milliseconds taken from range (the minimum and maximum time is specified in consensus parameters, check section 2). Once timeout expires – the process starts over Then protocol awaits for random amount of milliseconds taken from range (the minimum and maximum time is specified in consensus parameters, check section 2). Once timeout expires – the process starts over 6. Proof of correctness 6.1 Partial signature The general formula for obtaining partial signature is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ


The validation is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑟𝑢𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ


The correctness: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ 𝐺 => 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The general formula for obtaining partial signature is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The general formula for obtaining partial signature is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The validation is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑟𝑢𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The validation is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑟𝑢𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The correctness: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ 𝐺 => 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The correctness: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ 𝐺 => 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ 6.2 multi signature The general formula for building multisig is: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖


The general formula for building multi public key is: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ


The validation of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ


The correctness of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖 ∗ 𝐺 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The general formula for building multisig is: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖 The general formula for building multisig is: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖 The general formula for building multi public key is: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ The general formula for building multi public key is: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ The validation of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The validation of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The correctness of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖 ∗ 𝐺 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ The correctness of signature: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖 ∗ 𝐺 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ 7. M-of-N connections The following algorithm allows to build M-of-N connections network. This simply means, that there is no strict requirement, that all nodes should have connections between each other. This approach helps to define more efficient networking. However, keep in mind, that in order to guarantee consensus each node should have at least 𝑓 + 1 connections. Author:
(1) Egor Zuev (zyev.egor@gmail.com) Author: Author: (1) Egor Zuev (zyev.egor@gmail.com) 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.

Gossip Protocol Replication, Multi-Signatures, and M-of-N Consensus Explained

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

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

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

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

Could Block Proposals Be Fair and Efficient Without Proof of Work (PoW)?

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps