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 4. Append process 4.1 Local append The append process looks like that: Each new record should have key, value and version fields


On append, the algorithm should create hash of record: ℎ𝑎𝑠ℎ = 𝑠ℎ𝑎256(𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒, 𝑣𝑒𝑟𝑠𝑖𝑜𝑛). This hash brings uniqueness to the record


Then algorithm should create partial signature as follow: partialSignature = (privateKey ∗ hash)𝑚𝑜𝑑 𝑁, where 𝑁 is curve parameter.


Then algorithm add timestamp and timestamp index to the record. The timestamp – is a timestamp when record is created. The timestamp index is used when concurrency is possible, and two or more records can be created at the same time. In case this happens, all records with the same time have their own index (like 0, 1, 2).


Then this record, alongside with hash and signature can be stored locally (for instance in database)


This record is called intermediate Each new record should have key, value and version fields Each new record should have key, value and version fields On append, the algorithm should create hash of record: ℎ𝑎𝑠ℎ = 𝑠ℎ𝑎256(𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒, 𝑣𝑒𝑟𝑠𝑖𝑜𝑛). This hash brings uniqueness to the record On append, the algorithm should create hash of record: ℎ𝑎𝑠ℎ = 𝑠ℎ𝑎256(𝑘𝑒𝑦, 𝑣𝑎𝑙𝑢𝑒, 𝑣𝑒𝑟𝑠𝑖𝑜𝑛). This hash brings uniqueness to the record Then algorithm should create partial signature as follow: partialSignature = (privateKey ∗ hash)𝑚𝑜𝑑 𝑁, where 𝑁 is curve parameter. Then algorithm should create partial signature as follow: partialSignature = (privateKey ∗ hash)𝑚𝑜𝑑 𝑁, where 𝑁 is curve parameter. Then algorithm add timestamp and timestamp index to the record. The timestamp – is a timestamp when record is created. The timestamp index is used when concurrency is possible, and two or more records can be created at the same time. In case this happens, all records with the same time have their own index (like 0, 1, 2). Then algorithm add timestamp and timestamp index to the record. The timestamp – is a timestamp when record is created. The timestamp index is used when concurrency is possible, and two or more records can be created at the same time. In case this happens, all records with the same time have their own index (like 0, 1, 2). Then this record, alongside with hash and signature can be stored locally (for instance in database) Then this record, alongside with hash and signature can be stored locally (for instance in database) This record is called intermediate This record is called intermediate 4.2 Append from another node When one node receives new records from another (for instance node A obtained records from node B) during replication process, the append rules vary: The algorithm should validate the record


Then algorithm should check, do this node already has this record (it can be done by finding the record by hash).
2.1)If record exist then:2.1.1) In case received record is multisig and local record is intermediate – then algorithm should replace local intermediate record with received multisig and update the root.2.1.2) In case local and received records are multisig, then the highest multisig is chosen (the algorithm compares 2 signatures by value) and stored in local record.2.1.3) In case local record is multisig and received one is intermediate – then algorithm ignore this record (i.e. doesn’t apply) 2.1.4) In case local and received records are intermediate – then algorithm just take signatures from received record (which are not present on local record) and append them to local record.2.2)if record doesn’t exist:2.2.1) then algorithm should sign the hash of the received record (like was in local append described above), add it to this record and store

Then the algorithm should check if there are enough signatures for multisig (this number is defined by quorum size).
3.1) if yes then:3.1.1) algorithm build multisig: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖𝑚𝑜𝑑 𝑁3.1.2) algorithm build shared public key: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ3.1.3) algorithm replace intermediate signatures with multisig and sharedPublicKey3.1.4) algorithm save the record and update the root. The algorithm should validate the record The algorithm should validate the record Then algorithm should check, do this node already has this record (it can be done by finding the record by hash).
2.1)If record exist then:2.1.1) In case received record is multisig and local record is intermediate – then algorithm should replace local intermediate record with received multisig and update the root.2.1.2) In case local and received records are multisig, then the highest multisig is chosen (the algorithm compares 2 signatures by value) and stored in local record.2.1.3) In case local record is multisig and received one is intermediate – then algorithm ignore this record (i.e. doesn’t apply) 2.1.4) In case local and received records are intermediate – then algorithm just take signatures from received record (which are not present on local record) and append them to local record.2.2)if record doesn’t exist:2.2.1) then algorithm should sign the hash of the received record (like was in local append described above), add it to this record and store Then algorithm should check, do this node already has this record (it can be done by finding the record by hash). 2.1)If record exist then: 2.1.1) In case received record is multisig and local record is intermediate – then algorithm should replace local intermediate record with received multisig and update the root. 2.1.2) In case local and received records are multisig, then the highest multisig is chosen (the algorithm compares 2 signatures by value) and stored in local record. 2.1.3) In case local record is multisig and received one is intermediate – then algorithm ignore this record (i.e. doesn’t apply) 2.1.4) In case local and received records are intermediate – then algorithm just take signatures from received record (which are not present on local record) and append them to local record. 2.2)if record doesn’t exist: 2.2.1) then algorithm should sign the hash of the received record (like was in local append described above), add it to this record and store Then the algorithm should check if there are enough signatures for multisig (this number is defined by quorum size).
3.1) if yes then:3.1.1) algorithm build multisig: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖𝑚𝑜𝑑 𝑁3.1.2) algorithm build shared public key: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ3.1.3) algorithm replace intermediate signatures with multisig and sharedPublicKey3.1.4) algorithm save the record and update the root. Then the algorithm should check if there are enough signatures for multisig (this number is defined by quorum size). 3.1) if yes then: 3.1.1) algorithm build multisig: 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 = ∑ 𝑝𝑎𝑟𝑡𝑖𝑎𝑙𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 𝑖𝑚𝑜𝑑 𝑁 3.1.2) algorithm build shared public key: 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 = ∑ 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ 3.1.3) algorithm replace intermediate signatures with multisig and sharedPublicKey 3.1.4) algorithm save the record and update the root. 4.3 Record validation The validation process works as follows: First signatures are validated: in case of intermediate signatures First signatures are validated: in case of intermediate signatures 1.1) If signatures are intermediate, then for each intermediate signature the algorithm validate that: 𝑝𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦𝑖 ∗ ℎ𝑎𝑠ℎ = 𝑠𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺, where G – is a curve parameter (SECP256K1) 1.2)If signature is multisig, then 1.2.1) sharedPublicKey is reconstructed from involved public keys in signature process (the public keys with signatures are stored in record) and compared against received sharedPublicKey. If it’s not equal – then validation is not passed 1.2.2) then multisignature is validated as: 𝑚𝑢𝑙𝑡𝑖𝑆𝑖𝑔𝑛𝑎𝑡𝑢𝑟𝑒 ∗ 𝐺 = 𝑠ℎ𝑎𝑟𝑒𝑑𝑃𝑢𝑏𝑙𝑖𝑐𝐾𝑒𝑦 4.4 State consistency To make sure, that all nodes have the same sets of records, the root has been introduced. The root is represented as sum of hashes of confirmed records (records with multisig): 𝑟𝑜𝑜𝑡 = ∑ ℎ𝑎𝑠ℎ 𝑖 𝑚𝑜𝑑 𝑛, where 𝑛 is a curve parameter. The following formula allows to build the root without order, so technically the append order of hashes doesn’t make any sense in this case. Also, keep in mind, as algorithm has eventual consistency (without rollback option) – we can’t guarantee any ordering. Also, to make root update quick, the algorithm stores the root on record level: On multisig record insert, the algorithm updates the root by addition of previous root to record’s hash: 𝑟𝑜𝑜𝑡 = (𝑟𝑜𝑜𝑡𝑝𝑟𝑒𝑣 + ℎ𝑎𝑠ℎ) 𝑚𝑜𝑑 𝑛


Then this root hash is appended to the record (I call it stateHash)


During next append of another new record, there is no need to recalculate the hash root of all records, but we sort confirmed (multisig) records in DESC order by timestamp and timestamp index, and take stateHash from the first record (which is the most recent one) On multisig record insert, the algorithm updates the root by addition of previous root to record’s hash: 𝑟𝑜𝑜𝑡 = (𝑟𝑜𝑜𝑡𝑝𝑟𝑒𝑣 + ℎ𝑎𝑠ℎ) 𝑚𝑜𝑑 𝑛 On multisig record insert, the algorithm updates the root by addition of previous root to record’s hash: 𝑟𝑜𝑜𝑡 = (𝑟𝑜𝑜𝑡𝑝𝑟𝑒𝑣 + ℎ𝑎𝑠ℎ) 𝑚𝑜𝑑 𝑛 Then this root hash is appended to the record (I call it stateHash) Then this root hash is appended to the record (I call it stateHash) During next append of another new record, there is no need to recalculate the hash root of all records, but we sort confirmed (multisig) records in DESC order by timestamp and timestamp index, and take stateHash from the first record (which is the most recent one) During next append of another new record, there is no need to recalculate the hash root of all records, but we sort confirmed (multisig) records in DESC order by timestamp and timestamp index, and take stateHash from the first record (which is the most recent one) This approach is also useful for traceability and validation purpose, as all state can be replayed up to any point of history and calculated hash root can be compared with stateHash. 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

A Beginner’s Guide to the Authenticated Byzantine Gossip Protocol

EScholar Technologies

Too Long; Didn't Read

Download free Tech Leaders Productivity Report!

Multisig, Hashes, and the Math Behind Trustless Record Keeping

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