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

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

5. Replication process

The algorithm uses Gossip-like approach for replication and works as follows:

1. 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.

2. 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

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

4. 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

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

6. 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)

7. 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

1. The general formula for obtaining partial signature is: 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ

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

3. The correctness: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ 𝐺 => 𝑝𝑟𝑖𝑣𝑎𝑡𝑒𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ => 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 ∗ ℎ𝑎𝑠ℎ

6.2 multi signature

1. The general formula for building multisig is: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖

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

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

4. 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.