Introduction Of ISAAC Consensus Protocol for BOSNet

Written by BlockchainOS DEV Team
March 30 2018

Preamble

In anticipation of our release of our ISAAC Consensus Protocol, we will release 2 parts to explain ISAAC.

This first part will explain the basic concept of ISAAC consensus protocol and will introduce the source code of ISAAC and also the examples and testing cases in several network environments. The second part, to be released at a later date, will show the various good and bad cases in a more complicated network environment.

Introduction

We, the Developers of BlockchainOS are developing BOSNet, our blockchain network, in a serious and modest manner.

 Nowadays a lot of blockchain platforms are trying to address and improve blockchain concerns such as performance and scalability. Renown platforms such as Bitcoin and Ethereum are also in the process of attacking these problems. Various teams have presented many protocols in the attempt to solve these issues, but there has yet to be a silver bullet.


We acknowledge that the understanding and the implementation of a ‘good’ blockchain network is yet to be complete, so we are researching and proving various kinds of existing technologies and protocols to optimise our blockchain.

We are creating our own consensus protocol which will form the fundamental foundation of BOSNet – Needless to say, the technology behind a cryptocurrency is dependent on its underlying technology – we believe the consensus protocol defines the cryptocurrency’s identity.

ISAAC consensus protocol is our team’s latest achievement of the implementation of BOSNet, and we will explain further how ISAAC works in various environments

BOSCoin and ISAAC

Last year in 2017, BlockchainOS announced BOScoin [1], a new economic environment based on our own blockchain network, BOSNet. The ISAAC consensus protocol is the fundamental component of BOSNet. ISAAC is the first implementation of ‘mFBA (modified FBA)’ which emphasizes and enhances the openness of FBA. We believe that mFBA will enhance the openness of our blockchain network to the extremities.

ISAAC comes from the abbreviation of the 4 states of our consensus process, Init’ (Initial), ‘Sign’, ‘Accept’, ‘All-Confirm’, and is also the first name of the renown Isaac Newton. Through the ISAAC consensus protocol, data will be safely and efficiently stored in the blockchain.

Why we invent ISAAC?

ISAAC is the implementation of mFBA, and as the name says, mFBA is derived from FBA with openness. When we started to envision how to create BOSNet, we believed that FBA would be the most suitable consensus protocol when comparing other protocols and the SCP (Stellar Consensus Protocol) [2], real world implementation of FBA, would be fundamental concept for our consensus protocol.

We have conducted a full interrogation of FBA and the SCP, and discovered that SCP is better than other comparable consensus protocols, but to support some of BOScoin’s features and environment, especially openness, it has some limitations.

The pros and cons of FBA and SCP

Essentially, FBA can be described by the following:

  • a network consisting of quorums, and each quorum is a group of nodes.
  • the consensus process is achieved via the quorums, and the collective agreement of the quorums is used as the final decision of the entire network despite byzantine failure [3].

This will make FBA different to other Byzantine Agreement consensus protocols such as PAXOS. These properties of FBA makes the consensus process simpler, faster, and more efficient but along with this also brings 3 major limitations: openness, performance and failure of safety.

Openness

The basic concept of SCP is that if an agreement is possible within a small group of nodes, we call it quorum, then the entire network can achieve ultimate agreement. Under these assumptions, a validator node has it’s own quorum set, which is the base unit of consensus. Only the validating node per account can participate in the consensus process. A new node attempting to join the network can declare itself as a validator and compose their own quorum set. However if other validators do not accept the new node into their quorum set, the decision of the new node will not be received by the other validators – since each node only cares about the validators in it’s own quorum set, the new node’s decision is not considered by the other validators during the consensus process. The SCP states that anybody can operate as a node and can join the Stellar network, which characterizes the network to be open. But this is only half correct. Although joining the network is open to anyone, however to join the network and participate in the consensus process as a validator is limited. Their consensus result has barriers and are not transmitted to the wider network. To join as a validator, the existing validators must approve and accept the new node[4].

 

Failure of safety: Double Spending Problem

In reality, nodes and it’s quorums can be located far away in terms of network latency. This matter prevents the message to be broadcasted to the entire network simultaneously. Safety [2] can fail at this point. Let us assume that an evil user has 100 BOS and the user attempts to send 100 BOS to 2 people at the same time. In an ideal environment where network latency is zero, only one payment will succeed and the other will be rejected. The confirmed payment will be recorded in the blockchain forever. However in reality where there is network latency, double spending could potentially occur and bring the network down. Consider the following environment:

  • The 2 quorums, Q(a) and Q(b) are located far away from each other (keep in mind network latency)
  • Each quorum can reach consensus approving the transaction within their own validator network, which are independent to the other quorums’ validators.

 

Under the above environment, if the payment message is sent to each quorum, Q(a) and Q(b), at the same time, Q(a) and Q(b) can reach agreements independent of each other. From perspective of the entire network, these are two contradictory transactions, Tx X and Tx Y,and are both confirmed and stored in the blockchain, resulting in a blockchain fork.

The Stellar Development Foundation acknowledged this problem that sacrificing safety over liveness and fault tolerance could potentially lead to double spending and ledger forks [11]. As a temporary fix, they decided to momentarily run a single validating node until they fixed the consensus algorithm, resulting in a fully centralized network in terms of deciding whether a transaction is valid or not.

The long term solution, SCP devised two interesting strategies: the nominating protocol and the conflict resolving process. When a new message is received, every node in the network tries to broadcast it to the entire network through a nomination protocol. Several seconds later, each validator assumes that the message is completely broadcasted throughout the network, which then the voting process is commenced.

The nomination protocol helps by creating time for the message to be broadcasted to all of the nodes within the network, however this is not enough to ensure complete safety. When a node notices conflict in it’s blockchain, the node will retrieve the block history data from other nodes, compare the data, and recover the conflict.

ISAAC specializes in,


  • ISAAC is based on mFBA, the modified version of FBA. Expecting that similar issues which may arise within FBA can also affect our ISAAC protocol, we aim to overcome these issues through our finalized mFBA consensus algorithm.
  • Openness of the network can be achieved by a necessary qualification process for a new node joining the network
  • Performance and safety can both be addressed by tight and well rooted integration between the nodes (i.e. quorum intersection [2])

Specification of ISAAC

BOSNet Specification: Blockchain & Consensus.

Consensus State

Each ballot will be processed and validated through 4 states. INIT -> SIGN -> ACCEPT -> ALL – CONFIRM 

 

 

INIT

This is the base state when a message is received. In this state, the validator will verify that all the validators in the same quorum has recieved the message.
When the validator receives a new message, it will create a ballot, this ballot will have an INIT state and it will be broadcasted to the other validators within the quorum.
The broadcasted ballot will be received by other validators and if the number of received votes are over a specific threshold, it is escalated to the SIGN state.

 

SIGN

The SIGN state validates the received ballot. The result of this validation will be included in the ballot and it will be broadcasted to the network.
The collected ballots will be counted and if it is in consensus and over a specific threshold, it will be escalated to the ACCEPT state.

 

ACCEPT

The ACCEPT state checks whether each validator should store the ballot in their blockchain. Even if the validator’s decision is different from the whole quorum’s decision, the validator follows the quorum’s decision as long as it is above the threshold.
If verified, it will proceed to the ALL-CONFIRM state.

 

ALL-CONFIRM

At this state the consensus process is complete for this ballot and will be stored on the blockchain.

Properties of a consensus protocol [10]

Safety

A set of nodes enjoy safety if no two of them ever externalize different values for the same slot.
All outputs produced have the same value (agreement), and – The output value equals one of the nodes’ inputs (validity)

 

Liveness

A node enjoys liveness if it can externalize new values without the participation of any faulty nodes. Eventually non-faulty nodes output a value.

 

Fault Tolerance

The number of faulty nodes in which the network can recover and still satisfy safety and liveness.

 

FLP Theorem

No deterministic consensus protocol can guarantee all three of safety, liveness, and fault tolerance in an asynchronous system [8].

 

Which one is most important, Safety, Liveness, Fault Tolerance?

In a distributed computational environment, the presence of faulty nodes are unavoidable due to network latency and malicious attacks – hence, to ensure a certain degree of fault tolerance is highly prioritized. In addition, preventing forks via double spending is also of high importance, hence safety of the network is also equally required. An ultimate Fault Tolerant environment needs to satisfy safety and liveliness, however as, from the FLP Theorem, this is not theoretically achievable, and we inevitably need to prioritize one aspect over the other. If we are to satisfy safety of the network, this prevents blockchain forks and eliminating any potential chance of a double spend. However liveliness is not ensured, so the rate of failure of transactions increases.

There are various ways to satisfy safety. Setting the threshold of each node to a higher level will ensure the validation of a universal agreement of transaction, hence securing safety. In the view of the network topology, ensuring as many quorum intersections as possible could also ensure the safety of the network.

Conversely, if we focus on Liveness, the potential of failure when a client requests transactions is decreased. The output of transactions will be externalized no matter what. However the potential of a fork increases and a double spending might occur. To address liveliness, we need to lower the consensus threshold of the nodes, or regarding network topology, we need to assign nodes to a specific quorum.

In blockchain, preventing a double spend takes priority over preventing transaction failures. Hence BOSNet’s priority is to ensure safety and fault tolerance. As per the aforementioned process, this will require increasing the validator’s threshold to an appropriate level, and structuring the network to have many nodes being commons. i.e. intersecting two or more quorums.

Case Study

 

Premise

  • All nodes are validators
  • Consensus (agreement between validators) handles multiple messages in an asynchronous way
  • Each validator validates the message and the associated ballot
  • The quorum set is pre-assigned
  • The validation result is YES or NO; YES means the message is valid.
  • Each validator keeps a list of non-faulty nodes 

 

General Forms Of Quorum

 

 

Test cases for safety and liveness depending on number of faulty nodes

Test cases that satisfy safety and liveness to the theoretical maximum limit of faulty nodes.
We assume the following ‘flower form’ of quorums:

 

  • Nodes = 8
  • Commons = 4
  • threshold = 60%

 

If the number of faulty nodes is 0, 1 ( n0 ), or 2 ( n0, n1 ), the network ensures both safety and liveness. Even if there are two faulty nodes, more than 60% of the validators in all quorums are able to respond, thus able to reach consensus. 

Each case is implemented in https://github.com/bosnet/isaac-consensus-protocol.
They can be executed by the following command line scripts:

None Faulty Nodes: flower-form.yml

Running

Verifying In Logs

Result(Success)

With One Faulty Node: flower-form-f1.yml

Running

Verifying In Logs

Result(Success)

With Two Faulty Nodes: flower-form-f2.yml

Running

Verifying In Logs

Result(Success)

With Three Faulty Nodes: flower-form-f3.yml

Running

Verifying In Logs

Result(Fail)

 

Future Work

We are constantly testing and verifying the ISAAC consensus protocol, and using it we aim to handle various kinds of data in our blockchain including: 

 

Terminology

Ballot

A unit and data format which BOSNet network nodes ACCEPT. Based on the ballot, BOSNet validators will vote and achieve consensus among each other.


Commons

The common validator(s) between two quorums. If validator V(a) belongs to both Q(a) and Q(b), then V(a) is the commons for Q(a) and Q(b)


Consensus

Consensus is the process to make universal agreement for data.


Extras

Validators that do not belong to the commons. If validator V(a) belongs to Q(a), but does not belong to Q(b), then V(a) is an extra for Q(a).


FBA

Federated Byzantine Agreement (FBA) is a consensus model. In FBA, each node decides on members of their own quorum, and entire quorums result from decisions by individual nodes. FBAS (Federated Byzantine Agreement System) is the achievement of agreement through federated voting.


Message

Data that are stored in the ledger. It contains message_id and data which should be verified by BOSNet participating nodes.


mFBA

Abbreviation of modified Federated Byzantine Agreement. BOSNet’s consensus protocol ISAAC is a construction of mFBA. It anticipates better openness for new nodes to join the BOSNet network.


Node

Node is the basic player in the network. There are several types of nodes: validators, observers, etc.


Faulty Node

Nodes that make any type of malfunction in the BOSNet Network. (eg. unable to make consensus in quorum, send wrong messages to other nodes, BOSNet network connection lag, etc)


Quorum

A group of nodes which are able to reach consensus among each other


Quorum intersection

The sharing of nodes between any two quorums. From the node’s point of view, when a node links 2 or more quorums together, it is considered a quorum intersection. In FBA, isolated quorums that do not satisfy quorum intersection cannot guarantee the safety of the network.


SCP

SCP is the Stellar Consensus Protocol developed by the Stellar Development Foundation. It is a construction of FBA.


Threshold

The percentage of nodes inside a quorum that must be exceeded to confirm a certain message or ballot.


Validator

A validating node participates in the consensus process. It validates incoming messages and makes agreements therefore helping the network reach universal consensus.


Voting

The process of validators within a quorum agreeing on the approval / disapproval of the broadcasted message.


References

1. BlockchainOS. The BOSCoin Platform White Paper: https://boscoin.io/wp-content/themes/boscoin//src/pdf/BOScoinWhitePaper.pdf

2. David Maziéres and Stellar Foundation. Stellar Consensus Protocol, A Federated Model For Internet-Level Of Consensus, 2016: https://www.stellar.org/papers/stellar-consensus-protocol.pdf

3. Miguel Correia, Giuliana Santos Veronese, Nuno Ferreira Neves and Paulo Verissimo. Byzantine Consensus in Asynchronous Message-Passing Systems: a Survey: http://www.gsd.inesc-id.pt/~mpc/pubs/survey-ba-journal-formated.pdf

4. Stellar Foundation. Validator list page of stellar.org: https://github.com/stellar/docs/blob/master/validators.md

5. Rafael Pass, Lior Seeman, and abhi shelat. Analysis of the Blockchain Protocol in Asynchronous Networks. 2016

6. David Maziéres. The Stellar Consensus Protocol, draft-mazieres-dinrg-scp-00. 2018: https://tools.ietf.org/id/draft-mazieres-dinrg-scp-00.txt

7. Jeremy Rubin. Federated Systems. 2015: https://www.stellar.org/papers/stellar-consensus-protocol.pdf

8. Michael J. Finscher, Nancy A. Lynch and Michael S. Peterson. Impossibility of Distributed Consensus with One Faulty Process. 1982:https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

9. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. 1982: http://lamport.azurewebsites.net/pubs/byz.pdf

10. M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. Laboratory for Computer Science, MIT, 1999. http://pmg.csail.mit.edu/papers/osdi99.pdf

11. Joyce Kim. Safety, Liveness and fault tolerance – the consensus choices. https://www.stellar.org/blog/safety_liveness_and_fault_tolerance_consensus_choice/

12. Leslie Lamport. Paxos made simple.http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

 

Go to ISAAC Part 2