Blockchain Architecture Design & Use Cases

Blockchain Architecture Design & Use-Cases

Multiple concepts included in Blockchain are,

• Distributed Systems
• Security & Privacy
• Cryptography
• Economics

1. Blockchain Introduction

1. Basics

What is a Blockchain?

A decentralized computation and information sharing platform that enables multiple authoritative domains, who do not trust each other, to cooperate, coordinate and collaborate in a rational decision making process

Broadly it is a Decentralized Database.

Disadvantages of Traditional systems

• Difficult to simultaneous access by more than one party
• Centralized environment, so it works as a single point of failure
• Not scalable
• Not robust to failure

Centralized v/s Decentralized v/s Distributed

Centralized Architecture aspects,

• Complete reliance on single point, which is not safe.
• Single coordinator

Decentralized Architecture aspects,

• More than one coordinators: Multiple points of coordination. To each coordinator only a subset of nodes are connected
• On failure of a single or multiple coordinator, individual nodes can connect to other available coordinators to perform the operation; until network become disconnected

Distributed Architecture aspects,

• Everyone coordinate with each other & collectively execute the task.

Blockchain - The internet database to support decentralization, with a strong consistency support.

Every individual node maintains a local copy of global data-sheet

The system tasks are,

• All individual copies are consistent with each other.

i.e. local copy that every node has are identical 

& these copies are always updated based on global information

• If one node wants to add some information to blockchain, then that will get updated to all the copy of the blockchain that every node process

Local information in Blockchain is called as Public Ledger - Any new transaction is validated against the old transactions from public ledger

Blockchains work like a public ledger, with numerous aspects as,

• Protocol for commitment : every valid transaction are committed & included in blockchain. Validity checking mechanism will validate transaction & discard invalid transaction.
• Consensus : It is important aspect. This mechanism ensures that all local copies with individuals are consistent i.e. identical & most updated.
• Security : Whenever a node broadcasts updated information, other nodes should be able to verify that it is tamper proof.
• Privacy & Authenticity : It is required as blockchain transactions belongs to various clients and copy of blockchain is available with every party.

Definition

A Blockchain is "an open, distributed ledger that can record transactions between two parties efficiently and in a verificable and permanent way”

Keywords

Open - information kept is accessible to all parties

Distributes or Decentralized - no single party control. copy of public ledger to every party, who are communicating with each other.

Efficient - fast & scalable with number client request as well as with number of participants in network

Verificable - everyone can check the validity of information

Permanent - the information is persistent i.e. tamper proof. To update information, new transaction need to add but old transaction can’t be changed or deleted

2. History

How private Alice can be identified?

every 10 mins mining is successful? means miners receive new bitcoins?

Transaction verification from block 1?

any tamper verification for current block after mining?

Blockchain is a data structure which is build over concept of hash function.

Cryptographically Secured Hash functions

Examples - MD5, SHA256

Hash function H(x) - Map any sized data to a fixed size. x is called message and H(x) is called message digest

Cryptographically secured - Hash functions are one way function. Given a x, it is possible to compute H(x). But given a H(x), no deterministic algorithm can compute x. For two different x1 & x2, H(x1) & H(x2) should be different. Only if x1 = x2, then H(x1) = H(x2).

Avalanche Effect property of Cryptographically Secured Hash functions

A small change in the data or message, results in a significant change in the output or message digest.

Cryptographically Secured Chain of Blocks 

First used for Time-stamp a digital document

Multiple blocks of data, in which each new block is connected by hash value of previous or last block in chain.

So this chain makes all blocks as tamper proof.

This is earlier version of Blockchain to secure digital documents.

Merkle Tree also known as Hash Tree

Every leaf node is labelled with hash of a data block

Every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes

A change in any leaf node document, leads to change in all subsequent parent nodes hash values, including Root Hash value.

Use of Markle Tree is to secure number of documents. E.g. Peer to peer networks, Bitcoin implementation

Bird-eye view of Cryptocurrency

Completely decentralized no central party for ordering or recording or 

controlling anything

Peer-to-peer system of software that runs at all parties machine, 

which are connected to each other & share information among themselves

Permissionless no identity required. anyone can participate in any 

role

Blockchain is backbone of Cryptocurrency architecture. Blockchain size grows exponentially as more transactions are performed.

Each transaction is nothing but hash value of transaction information. All transactions are connected with each other through Hash Chain. Generally multiple transactions make a single block.

Copy of blockchain is available to every individual party. New transaction get included in existing blockchain at each party.

Transaction Life Cycle in Cryptocurrency

1. A party makes a transaction, then digitally sign related information using own private key and broadcast it over the network to rest all nodes.
2. Other nodes validates the transaction based on the existing Blockchain and propagate to special nodes i.e. miners
3. Miners include transaction to next block of blockchain to be mined.
1. [Miners can also check the validity of transaction]
2. They collect all transactions from clients since last 10 mins, 
3. construct new block, and 
4. apply mining mechanism to connect new block to existing blockchain through cryptographic hash function.
5. Updated copy of blockchain is propagated in network
4. Update transaction to the 2nd party involved in it.

1. Blockchain 2.0 and Smart Contracts

Utilized much further than financial transactions, to avoid intermediates (the middleman)

Smart contracts can be realized using a public ledger, so Blockchain also can be pioneering technology to realize smart contracts

Crowdfunding - Contracts in a Centralized Platform

• Both parties (the product team and the supporters) need to trust the crowdfunding platform
• The crowdfunding platform, the middleman, takes significant charge to manage the entire process and risk involved

Smart Contracts for Crowdfunding Platform

• The contract is written in a code which is available to all the stakeholders – the supporters and the product team. Code will content all agreements.
• Contract will be put in Blockchain, so that everyone will be able to view the contract, but no one will be able to tamper it

Advantages of Smart Contracts

1. Immutable: No party will be able to change the contract once it is fixed and written to the public ledger (the Blockchain with immutable blocks)
2. Distributed: All the steps of the contract can be validated by every participating party – no one can claim later that the contract was not validated. The information is open – everyone can check and validate

3. Architectural Principles and Design

more time to find nonce value, then what in 10 mins?

Are not chance of no nonce value, for expecting number of zeros?

Challenge & block with nonce, both required?

LinkedIn blog

The Block - Securing Data Cryptographically

• A block is a container data structure that contains a series of transactions (multiple information).

For example, in Bitcoin: A block may contain more than 500 transactions on average, the average size of a block is around 1 MB (an upper bound proposed by Satoshi Nakamoto in 2010). Presently (as of March 2018) a block may grow up to 8 MB or sometimes higher. Larger blocks can help in processing large number of transactions in one go.

• All information in block is digitally signed and encrypted transactions verified by the peers. Ensures that participants can only view information on the ledger that they are authorized to see.
• Structure of a block has 2 components: 

For example, Bitcoin blocks & transaction are shown at https://blockchain.info/

Hash function: Hk = Hash(Hk-1 || Tx || Nonce)

1. Block Header - Metadata about a block

1. Previous block hash (Hk-1)

Every block inherits from the previous block – previous block’s hash used to create the new block’s hash – make the blockchain tamper proof (If someone trying to tamper a block, then all subsequent blocks also needs to be changed).

This is used to connect the blocks in chain

2. Mining statistics used to construct the block

Task of miner is to find Nonce values, such that to ensure difficult on generated hash value (Hk)

1. Timestamp - when mining has been done
2. Nonce
3. Difficulty - Finding nonce to meet the criteria of complexity of algorithm (i.e. certain number of zeros at the prefix of hash value, Hk). For example, in bitcoin level of complexity needs to find nonce such that 20 number of zeros in the prefix of Hk.

Difficulty of mining algorithm determines the toughness of tampering by an attacker with a block in blockchain

3. Merkle Tree Root

The transactions are organized in a Merkle Tree structure. The root of the Merkle tree is a verification of all the transactions. (Any change in a transaction will change root hash. This will also change hash of all subsequent blocks as they are linked to each. This is the beauty of blockchain, which makes it tamper proof data structure)

Change a Transaction → Change in Merkle Root → Change in current block Hash → Change in Next block hash

2. Data - List of Transactions (Tx) 

Transactions are organized as a Merkle Tree, which used to construct the block hash.

• Hashes in a Block header

1. Hash of current block (using Double SHA256 hash algorithm) - It is block identifier
2. Previous Block hash
3. Merkle Root - Has all transactions

Blockchain Replicas

• As there are multiple peers interconnected in network, every peer in a Blockchain network maintains a local copy of the Blockchain. 
• Requirements

• All the replicas need to be updated with the last mined block
• All the replicas need to be consistent – the copies of the Blockchain at different peers need to be exactly similar

• The Notion of Distributed Consensus

• Ensure that different nodes in the network see the same data at nearly the same point of time. All nodes in the network need to agree or consent on a regular basis, that the data stored by them is the same. 
• No single point of failure – the data is decentralized. If one node fails, data is available at other nodes. So the system can provide service even in the presence of failures, until unless network is disconnected
• The basic philosophy is based on message passing – inform your current state to others so that everyone can match or validate their current state with others in the network. So one can see if own current state is updated/recent or not, and matches with other peers.
• However, Traditional Consensus Algorithm requires that the participants in the consensus algorithm knows each other. To know with which node to validate the data
• Blockchain architecture involve a Permission-less Model, 

arbitrarily large network, and

no participant in the network really knew all other participants

the permission-less network (an open network), that one doesn’t need  to record identity while participating in the consensus system 

So a Challenge-Response based system work good in blockchain architecture – the network would pose a challenge to participant, and each node in the network would attempt to solve the challenge

The Bitcoin uses Proof of Work (PoW) algorithm – ensures consensus over a permission-less setting based on challenge-response

The Digital Money is the Economics Behind Blockchain Consensus, which

Ensures operational efficiency 

More levels of controlling monetary policy 

The computational effort expended by the nodes in achieving consensus would be paid for by cryptocurrency generated and managed by the network

The Technologies behind Blockchain

• The Data Structure – Distributed Ledger

Forms backbone of Blockchain

• Cryptography and Digital Signatures – Ensure security and tamper-proof architecture 
• The Consensus over a Permission-less Environment

Based on Challenge-Response scenarios to ensure correctness of data at individual peers without revealing identity

• The Economy of the Revenue Model – Encourages participants to join in the mining procedure

4. Conceptualization and Application

Orphan block creator also gets rewards?

Who will crete block once all rewards are over?

Are there any chances that longest chain has less number of transactions that short chain?

Security : The system is tamper-proof – it is “extremely hard” to make a change in the blockchain. Tampering the system becomes harder as the chain grows. 

Privacy : The transactions are pseudo-anonymous. Transactions are sent to public key addresses,i.e. cryptographically generated addresses, computed by peer application (the wallet applications in Bitcoin). Thus a certain level of privacy is achieved, not complete privacy as transaction is visible.

• Peer application listens for transactions addressed to an address (i.e. account),
• Encrypts the transactions by the public key of the target address
• Only the target node can decrypt the transaction and accept it 
• However, the actual transaction amount is open to all for validation

Blockchain as a Tree

Multiple users are simultaneously try to mine a block (i.e. simultaneously trying to solve mathematically challenging problem based on Challenge-Response architecture & try to find a block)

One of the longest chains is (randomly) accepted chain from Blockchain as a Tree. New block is mined, then it get added to that longest chain.

Orphaned Blocks - The blocks which are not part of the longest chain, but part of the Fork Chains. Others chains (forks) gets invalidated over time and ignored.

There are 2 models of Blockchain network

1. Permission-less (an open environment) - suitable for open control-free financial applications like cryptocurrency 
2. Permissioned (a close environment) - suitable for business applications like smart contract 

1. Blockchain 2.0 = Permissioned (Private) Model

• It is used beyond cryptocurrency
• Technologies used in Permission-less Model can be applied to closed or Permissioned Network settings too : Notions of consensus, Security, and Distributed replicated ledgers
• Such enterprise use-cases only involve a few 10 or 100 known participants
• Example applications : Asset Movements and Tracking in Financial marketplaces (Banks), Provenance Tracking in Supply chain (Manufacturer-Shipper-Distributor-Retailer), Distributed Web

Hyperledger Fabric

• A permissioned blockchain framework
• Provides an enterprise-grade foundation for transactional applications
• A shared ledger that supports smart contracts – ensures security and integrity of recorded transactions
• Unlike Bitcoin and Ethereum, Hyperledger Fabric supports strong privacy and confidential transactions
• Supports the notion of channels, a “subnet” of peers within the network that wants to share information confidentially. Gives restricted visibility - important for business applications
• Doesn't have notion of mining, rather it uses the notion of distributed consensus under a closed environment
• In Fabric Network Architecture, Blockchain users take membership from Certificate Authority to enrolled before participation. This makes environment closed.

5. Basic Crypto Primitives - 1

Basic cryptographic primitives behind the blockchain technology are,

1. Cryptographically Secured Hash Function
2. Hash Pointer and Data Structures
3. Digital Signature

1. Cryptographically Secured Hash Function

• Hash function used to connect the “blocks” in a blockchain in a tamper-proof way
• It takes any string as an input, The message M. Then it produces a fixed size output (256 bits in Blockchain), The message digest H(M).
• They are efficiently computable functions, doesn't need significant amounts of resources 
• Required properties of Hash Function,
• Collision-Free : If two messages are different, then there digest should also differ. If M1 ≠ M2, then H(M1) ≠ H(M2)
• Hiding : Should hide the original message behind the message digest (Reference avalanche effect). It should be one way function, i.e. it should be difficult to identify M from given a H(M)
• Puzzle-friendly : Given X and Y, it should be efficient to find k such that 𝑌=𝐻(𝑋||𝑘) [used to solve the mining puzzle in Bitcoin PoW]

Collision free

• One-way function, i.e. For a given 𝑥 it is easy to find 𝐻(𝑥). However, for a given 𝐻(𝑥), no deterministic algorithm can find 𝑥
• It is difficult to find 𝑥 and 𝑦, such that 𝑥≠𝑦; however 𝐻(𝑥)=𝐻(𝑦). NOTE: It is difficult to find, but collision is not impossible
• Finding a collision may take significant long time.

If a hash function produces 𝑁 bits of output, an attacker can compute only 2^(𝑁/2) hash operations on a random input to find two matching outputs with probability > 0.98.

For example, for a 256 bit hash function, the attacker needs to compute 2^128 hash operations. If every hash computation takes 1 Millisecond, then it takes 〖~10〗^28 years.

• If 𝐻(𝑥)=𝐻(𝑦), it can be assumed 𝑥=𝑦
• To check if two messages 𝑥 and 𝑦 are the same, it just need to remember just the hash value rather than the entire message. This is efficient because the size of the digest is significantly less than the size of the original messages.

Information Hiding

• For a given 𝐻(𝑥), it is “computationally difficult” to find 𝑥
• The difficulty depends on the size of the message digests 
• Hiding helps to commit a value and then check it later.

Puzzle-friendly

It that random searching is the best strategy to solve the above puzzle of finding k such that  𝑌=𝐻(𝑋||𝑘) for given X & Y.

SHA256 Algorithm : Message M to Message digest H(M)

1. Preprocessing
1. Pad the message to make message size as a multiple of 512
1. If the length of the message M is 𝑙; and 𝑙 𝑚𝑜𝑑 512≠0
1. Append the bit “1” at the end of the message
2. Append 𝑘 zero bits, where 𝑘 is the smallest non-negative solution to the equation 𝑙+1+𝑘≡448 𝑚𝑜𝑑 512
3. Append the 64-bit block which is equal to the number 𝑙 written in binary

The total length gets divisible by 512

2. Parse the message into 𝑵 512-bit blocks 𝑴𝟏, 𝑴𝟐,…, 𝑴𝑵
3. Every 512 bit block is further divided into 32 bit sub-blocks 𝑴_𝟎𝒊, 𝑴_𝟏𝒊,…, 𝑴_𝟏𝟓𝒊
2. Start with a fix initial hash value 𝐻0
3. Sequentially compute 𝐻𝑖=𝐻(𝑖−1)+𝐶_(𝑀𝑖) * 𝐻(𝑖−1)

Where, 𝐶 is the SHA-256 Compression Function (involves bit shifting & bit appending operations) and

+ means mod 2^32 addition

𝐻(𝑁) is the hash of 𝑀.

2. Hash Pointer and Data Structure

• A Cryptographic Hash Pointer is a pointer to a location where :
• some information is stored and 
• Hash of the information is stored 
• The Hash Pointer is used to, 
• Retrieve the information and 
• Check that the information has not been modified (by computing the message digest and then matching the digest with the stored hash value)

Hashchain

A Hash value points to previous data block

This architecture is used in blockchain

This detect tempering from Hash Pointer

Merkle Tree

Organization of Hash Pointers in a Tree

Change in any one leaf node, gets reflected to entire root path. So it is tamper proof.

3. Digital Signature

A Digital Code, which can be included with an electronically transmitted document to verify,

• The content of document authenticated
• Identify the sender
• Prevent non-repudiation - Used to validate the origin of a transaction

Sender can’t deny about own activities/transactions

No one else can claim the sender's transaction as own

Only signing authority can sign a document, but others can verify the signature

Signature is associated with the particular document, so it can’t be transferred to another document

For example, Bitcoin uses Elliptic Curve Digital Signature Algorithm (ECDSA)

2 types of cryptography algorithms

• Private key cryptography or Symmetric (key) cryptography 
• sender and receiver uses same key
• key known by only sender & receiver
• Public key cryptography or Asymmetric (key) cryptography 
• sender and receiver uses different key
• one key is private/secrete known by only sender, while other key is public known by others. Also algorithm is known by everyone.
• Generally encrypt the message using Receiver’s public key, while 

Receiver decrypt the message using own private key.

Public key Encryption Enc() = Plain to Cipher

Private key Decryption Dec() = Cipher to Plain

So anyone can encrypt the data, but only the intended receiver can decrypt it.

• In Blockchain, based on design any Public Key Encryption algorithm can be used.
• RSA Algorithm is basic example of Public Key Encryption. It is Fundamental Public Key Algo proposed. It has 4 phases as Key generation, Key distribution, Encryption, Decryption.
• RSA Encryption with public key (e, n)

Cipher text c = m^e (mod n)

RSA Decryption with private key (d, n)

Plain message m = c ^d (mod n)

Properties of cryptographic key in Public Key Cryptography

• Key should be generated truly randomly to prevent it from being guessed
• Key should be of sufficient length more the length, more difficult to guess
• Key should contain sufficient entropy all bits in key should be equally random

Digital Signature using Public Key Cryptography

1. Sender Sign the message using own Private key. (Send Plain message plus Encrypted message as own signature.)
2. Everyone verify the signature using the sender's Public key. (Decrypt Encrypted message with the sender's public key and compare it with sent message to verify authenticity.)

So for x bit long plain message, encryption will provide x bit long cipher text i.e. digital signature.

Signature size (encrypted message used as signature) can be reduced by sending encrypted message digest (i.e. Hash of encrypted message), rather than using encrypted message itself. Hash the message, Sign hash using the private key.

Thus combining Cryptographic hash & Digital signature, can help to reduce the size of signature.

2. Bitcoin basics

“Bitcoin is a decentralized digital currency enables instant payments to anyone, anywhere in the world (Cross Country Payment System)” – en.bitcoin.it

Objectives

     - No central authority

     - Use of peer-to-peer technology

2 operations

     - Transaction Management i.e. transfer of coins from one user to another

     - Money Issuance i.r. regulate the monetary base

Bitcoin Coins

Creation of coins

• Coins are generated during mining (each time a user discovers a new block)
• Controller supply: Must be limited for the currency to have value. Any maliciously generated currency needs to be rejected by the network.
• Rate of creation is adjusted after every 2016 blocks to aims for a constant 2 weeks adjustment period. The number of coins generated per block is set to decrease geometrically, with a 50% reduction for every 210,000 blocks, or approximately 4 years. This reduces, with time, the amount of coins generated per block. Miners will get less reward as time progresses
• So there may not be mining fee, but increase the transaction fee
• Theoretical limit for total bitcoins: Slightly less than 21 million

Sending Payments

• Each person has one or more addresses each with an associated pair of public and private keys (may hold in the bitcoin wallet)
• Uses public key cryptography to make and verify digital signatures, to ensure that one user doesn’t send other user’s coins by creating transaction 

#) Steps when Alice wants to send coins to Bob

1. Bob sends his address to Alice
2. Alice adds Bob’s address and the amount of coins to transfer in a “transaction” message
3. Alice signs the transaction with own private key, and announces own public key for signature verification
4. Alice broadcasts the transaction on the Bitcoin network for all to see
5. Anyone can validate the transaction with Alice’s public key

QQQ) How ‘Same bitcoin’ is identified for Double spending problem. Is double spending possible with long time gap?

QQQ) Anyone can find bitcoin address using public key

Double Spending problem = Same coin is used for more than one transactions. Validation by other peers in network prevents this.

Bitcoin Address

• Provides anonymity
• The bitcoin address is used for any transaction, not the user name or identity
• Bitcoin network is permission-less, one does not need to setup any “account”, or required any e-mail address, user name or password to login to the wallet
• The public and the private keys do not need to be registered, the wallet can generate them for the users
• Bitcoin address is mathematically corresponds to a public key based on ECDSA (the digital signature algorithm used in bitcoin) with RIPEMD 160 bits Hash and few more operations
• Each person can have many such addresses, each with its own balance. So it is difficult to know the amount each person owns.

Bitcoin Script

• a programming language to validate bitcoin transactions
• A list of instructions recorded with each transaction
• Describes how the next person can gain access to the coins, if that person wants to spend them
• It uses FORTH programming language
• simple, compact, stacked based computer programming language
• Not Turing Complete: no loops, no need of halting for infinite loop
• originally designed by Charles Moore
• a procedural programming language without type checking
• Use a stack for recursive subroutine execution
• and processed left to write
• Uses reverse Polish notation (RPN) or postfix notation
• Determine that a transaction input correctly claims a transaction output. A transaction is characterized by two parameters. Alice sends some coins: the output (out) of the transaction ,and Bob receives some coins: the input (in) of the transaction

#) Details steps w.r.t Bitcoin Script, when Alice wants to send coins to Bob

• Instead of signature & public key of Alice, bitcoin indeed transfers scripts scriptSig & scriptPubKey respectively; with transaction details (sender Alice, Receiver Bob, Amount bitcoin)
• Bob can spend the coins only if both the scripts, combined input followed by output, return true after execution.

Transaction Input =>    scriptSig = <signatureSender> <pubKeySender>

Transaction Output => scriptPubKey 

= OP_DUP  OP_HASH160 <pubKeySenderHash> OP_EQUALVERIFY   OP_CHECKSIG

Sender Public key is used to verify if transaction owner is Sender itself. As Public key in input script when hashed yields the Sender Address embedded in output script.

Signature in input script is used to verify ownership of Sender Public Key in input script, which is verified from output script. As Signature is generated from corresponding Sender Private Key.

Bitcoin P2P Network

• An ad-hoc network with random topology, Bitcoin protocol runs on TCP port 8333
• All nodes (users) in the bitcoin network are treated equally
• New nodes can join any time.
• Non-responding nodes are removed after 3 hours
• Nodes in network has virtual link or overlay link or P2P link
• Seed Nodes provide initial information to new joining node. During installation of bitcoin applet list of seed node address exist in it.

#) Joining in Bitcoin network

1. Message to a seed node to give the peer addresses list
2. Select certain random number of nodes and create peering relationship by joining the overlay network
3. Get most recent blockchain from peer nodes and update local copy of blockchain, and accept the copy of the blockchain which has been transferred by most number of peers (when different copies of blockchain received from neighbours due to decentralized architecture)
4. Consider longest chain from selection blockchain
5. Any information (broadcast new transaction or new mined block) can be sent in this network

#) Transaction Flooding in Bitcoin network

1. Once a transaction is initiated, then it is broadcasted to peers
2. Active/Online peers validate the transaction by executing the scripts
3. Receiving peer is mentioned as coin receiver, then only that peer accept the transaction and include mentioned bitcoins in wallet
4. After validation of transaction, the receiving peers again flood/broadcast the transaction in the network. This way every transaction is propagated in network and everyone active/online in network able to see all transaction. So miner also receive all transaction and construct the block based on those transactions.
5. During flooding of a transaction, if a node has already seen the transaction then it drops it referring list of it’s past seen transaction and it doesn’t rebroadcast the transaction. Thus avoid network from getting clogged with flooding of messages & limits the amount of unnecessary flooding.

#) Transaction & Script verification steps

1. Transactions are validated against conflict & against double spending
2. After script verification, Check if script matches with a pre-given set of whitelist scripts - avoid unusual scripts, avoid infinite loops

#) Steps to add or relay a new block

1. Verification of Block that it contains the correct hash based on the existing blockchain (nonce, previous hash & merkle root)
2. To check if all transactions inside the block are valid - By checking the scripts and By validating with existing blockchain
3. The block should be included in the current longest chain. Forks should not be relayed.

Bitcoin Distributed Consensus

Distributed Consensus is a procedure to reach a common agreement in a distributed or decentralized multi-agent platform (distributed computing). Important for a message passing system.

This provides reliability and fault tolerance in a distributed system, by ensuring correct operations in the presence of faulty individuals.

Single decision maker → Consensus NOT required

Multiple decision makers, collectively way they need to come to a decision → Consensus Required

Consensus can be difficult in scenarios of malicious individual.

If there is no failure, it is easy and trivial to reach in a consensus- By broadcasting choices to all and then By applying a choice of function (e.g. maximum of all values)

However achieving consensus can be non-trivial in distributed environment, as it need to deal with the following 3 types of failures, 

1. Crash Fault: A node suddenly crashes or becomes unavailable in the middle of a communication and can’t receive any message from that node. This is software failure.
2. Network or Partitioned Faults: This may occur due to network link failure and results to partition in network. So nodes in one partition becomes unavailable to nodes in another partition. This is a hardware failure.
3. Byzantine Faults: A node starts behaving maliciously. It is neither software nor hardware fault. Unlike other faults, effect of this fault is unpredicted. So it is more difficult fault to handle in distributed network. 

#) Required properties of Consensus Protocol

1. Termination: Every correct individual decides some value at the end of the consensus protocol.
2. Validity: If all the individuals proposes the same value, then all correct individuals decide on that value
3. Integrity: Every correct individual decides at most one value, and the decided value must be proposed by some individuals. It ensures that consensus value should not deviate from proposed values by individual in network.
4. Agreement: Every correct individual must agree on the same value (of termination). It is the most important property of consensus.

#) Types of message passing system during consensus

1. Synchronous Message Passing System: The message must be received within a predefined time interval. It provides strong guarantee on message transmission delay. So it gives simplification in designing the protocol. Examples: Paxos, Raft , Byzantine fault tolerance (BFT)
2. Asynchronous Message Passing System: There is no upper bound on the message transmission delay or the message reception time. No timing constraint, message can be delayed for an arbitrary period of time. Designing such protocol is much difficult. Impossibility Result: In a purely asynchronous distributed system, the consensus problem is impossible (with a deterministic solution) to solve if in the presence of a single crash failure. Randomized or probabilistic algorithms may exist.

Traditional Distributed consensus protocols are based on Message passing requires a closed environment – everyone needs to know the identity of others

Shared memory is another traditional distributed consensus protocol, where a common memory place is available to read and write the shared variables that everyone can access. But it is not suitable for Internet grade computing.

#) Correctness properties for Distributed Consensus Protocol

1. Safety: Correct individuals must not agree on an incorrect value
2. Liveliness (or Liveness): Every correct value must be accepted eventually

#) Reasons for requirement of Consensus in Bitcoin Network

• A node does not know all the peers in the network – this is an open network
• Some nodes can also initiate malicious transactions

Per transaction consensus (validate every individual transaction) is inefficient, as protocol needs to be run for every individual transaction.

Block based consensus (run algorithm on block of transactions) is much more efficient. This forms the Blockchain, with efficient implementation of consensus.

Different miners form different new block can result to a problem of consensus.

Consensus Objective = to decide which particular block to add in existing blockchain out of proposed blocks by different miners.

#) Challenges:

• Multiple miners in bitcoin network. The miners don’t know each other.
• Individual miners can propose new block based on transaction info one has. So it is not necessary that every miner will propose same block
• A miner can include almost many transactions in new block, provided it doesn't exceed certain threshold

#) Proof of Work (PoW)

It is an economic measure requiring some work from requester (usually processing time by a computer).

Probability of mining a block depends on the work done by the miner.

The miners need to give proof that they have done some work, before proposing a new block

The attackers will be discouraged to propose a new block, or make a change in the existing blocks

Asymmetry property of PoW ,

• The work must be moderately hard, but feasible for the requester
• The work must be easy check or validate for the provider

So requester will be get discouraged to forge the work, as they have to spend a significant amount of time to complete the work.

• Bitcoin PoW is based on Hashcash PoW.

Source code of HashCash available at http://www.hashcash.org/, which can be used to try with different numbers of zero bit targets and to observe the time to compute the hashcash. Sha1sum (on Linux) can be used to compute SHA-1 checksum of obtained hashcash.

• Difficulty of the system is to find Nounce (N=?) such that,

BlockHash = Hash(PrevHash:MarkleRoot:Nonce)

Thus PoW system ensures consensus by utilizing Challenge-based system, with challenge to find a Nonce so that BlackHash will have minimum of x number of zeros at prefix.

• Most implementations of Bitcoin PoW use double SHA256 hash function

• The miners collect the transactions for approximately 10 minutes (default setup) and starts mining the PoW.
• During that time, miners exclude transaction obtained from last block (new block), and create a new set of transactions to create new block & start PoW to find hash value
• The probability of getting a PoW is low. So it is difficult to predict the miner with ability to generate the block. Therefore no miner will be able to control the bitcoin network single handedly.
• Difficult of PoW makes blockchain tampering difficult with current hardware.

Work included in PoW help to solve attacks ,

• Double spending

Every transaction can be validated against the existing blockchain to control double spending. Existing transactions are irreversible (computationally impractical to modify).

• Sybil Attacks = Attacker may attempt to fill the network with the clients under its control and get monopoly over network. So that those clients can Refuse to relay valid blocks or Relay only attacked blocks (which can lead to double spending too)

Diversifying the connections to reduce sybil attacks, i.e. allowing outbound connection to one IP per /16 (a.b.0.0) IP address

• Denial of Service (DoS) Attacks = Attacker may send a lot of data to a node, making that node unable to process normal coin transactions.

Certain measures Bitcoin network take to solve DoS attack over PoW system are,

- No forwarding of orphaned blocks

- No forwarding of double-spend transactions

- No forwarding of same block or transactions

- Disconnect a peer that sends too many messages

- Restrict the block size to 1 MB

- Limit the size of each script up to 10000 bytes

#) Shortcomings / Problems of PoW

• Mining Pool are engaging in fraudulent actions
• Monopoly problem = miners with more resources can have more probability to complete the work, as PoW depends on the computing resources

So others will get less rewards over time; Users will be discouraged to join as miner. And then Few miners with huge computing resources will only get control over network.

• Hude power consumption by computing resources to perform PoW with time efficiency.

To attempt these problems other basic consensus mechanisms are proposed, like

• Proof of Stake (PoS)
• Proof of Burn (PoB)
• Proof of Elapsed Time (PoET)

Once PoW gets settle down & miners with certain coins from that. Then gradually can move to other mechanism

General transition from PoW, to ensure wide distribution of coins.

#) Proof of Stake (PoS)

• Amount of coins that the miner holds – Miner holding 1% of the coins can mine 1% of the PoS blocks.
• It handle Monopoly and Power Consumption, as it expect wide distribution of coins.
• With such restrictions increased protection is provided, as attacker need more coins to for executing attacks & that will be expensive. And with the majority of coins, an attack will have more effect on the attacker itself.
• Variants of “stake”

Randomization in combination of the stake (used in Nxt and BlackCoin). Randomization function decides the next miner to mine a block.

Coin-age = Number of coins multiplied by the number of days the coins have been held (used in Peercoin). Holding of coins for certain duration will prevent the attacker with more coins collected somehow.

#) Proof of Burn (PoB)

• Miners need to show proof that they have burned / spend some coins (burning coins= sending coins to a verifiably un-spendable address)
• PoB works by burning PoW mined cryptocurrencies, once PoW system get saturated.
• PoB need to spend digital cryptocurrencies resources (i.e. PoW mined cryptocurrencies), but no external resources are used other than that. So it is as expensive just like PoW (which needs investment in physical resources like computation device, time & power).
• It is efficient in power consumption as it requires burning (i.e. spending) digital currency, not physical resources.

#) Proof of Elapsed Time (PoET)

• Makes randomization among the miners, by making network to wait for a random amount of time & then first participant to finish becomes the leader for the new block
• To verify if a proposer has really waited for a random amount of time, it utilizes special CPU instruction set – Intel Software Guard Extension (SGX) . It is based on trusted execution platform, which is hardware platform to write Trusted code in private way. Trusted code is private to rest of application. So it is completely hardware control, not software control. This gives guarantee from hardware for random waiting time, not software level to attack.

#) PoW v/s PoS v/s PoB

• PoW → Do some work to mine a new block

PoS  → Acquire sufficient stake to mine a new block

PoB  → Burn some wealth to mine a new block

• PoW → Consumes physical resources, like CPU power and time

PoS  → Consumes no external resource, but participate in transactions

PoB  → Consumes virtual or digital resources, like the coins

• PoW         → Power hungry

PoS, PoB → Power efficient

• PoW, PoS, PoB → Primarily for permissionless environment

PoET              → for both permission & permissionless (with special hardware) environment

References:

#) “Analysis of hashrate-based double-spending, by Meni Rosenfeld”

https://bitcoil.co.il/Doublespend.pdf

#) “The proposal of PoS” with interesting ideas

https://bitcointalk.org/index.php?topic=27787.0

#) “The Peercoin protocol” uses PoB

https://peercoin.net/assets/paper/peercoin-paper.pdf

#) “Hyperledger Sawtooth” https://www.hyperledger.org/projects/sawtooth

The Miners

#) Sequence of tasks

1. Validate transactions
2. Construct a new block
3. Use hash power to vote on consensus
4. Commit transactions with a new block
5. Add new block to existing blockchain
6. Store and broadcast the blockchain to the peers (to propagate entire blockchain in network)

#) Steps for Mining coins

1. Join the network
1. Listen for transactions
2. Validate the proposed transactions receiving from clients
2. Listen for new blocks
1. Validate the new blocks
2. Re-broadcast a new block when it is proposed

3. Collect transactions for a predefined time
1. Construct a new block with collected transactions, excluding already included transactions (in latest block)

4. Mining = Find a nonce (with predefined zeros) to make the new block valid

5. Broadcast the new block to peers – everybody accepts it if it is a part of the main chain

6. Earn the reward for participating in the mining procedure

#) Mining Difficulty

= Measurement of difficulty to find a hash below  given target (of preceding zeros)

• It a global block difficulty in Bitcoin network or a pool-specific share difficulty for Mining pools.
• The difficulty is readjusted for every 2016 blocks.

Desired mining rate is one block each 10 minutes. So within 2 weeks approx 2016 blocks are generated.

The change in difficulty (decrease or increase) is in proportion to the amount of time over (difficulty was too hard)) or under (difficulty was too simple) two weeks the previous 2016 blocks took to find. (en.bitcoin.it)

current_difficulty = previous_difficulty * (2 weeks in milliseconds) / (milliseconds to mine last 2016 blocks)

• Hash can be any number between 0 and 2^256-1
• The offset for difficulty 1 is 0xffff * 2^208. For the offset for difficulty D is 0xffff * 2^208/D
• The expected number of hashes to find a block with difficulty D is (D * 2^256) / (0xffff * 2^208)

“Current difficulty” https://blockexplorer.com/api/status?q=getDifficulty

#) Mining Pool

= Contains hundreds or thousands of miners through special protocols

Set of miners coming together collectively to mine blocks. It is pooling of resources by the miners. Collectively generate new block & share the rewards among themselves.

They Share the processing power over a network to mine a new block, and Split the reward proportionally to the amount of work they contributed

Advantages ,

• Small miners can participate
• Predictable mining. Large number of miners participating leads to high probability of finding new block in blockchain by pool

Disadvantages ,

• Leads to centralization. Same miners (mining pools) relay multiple blocks, which is the notion of monopoly
• Discourages miners for running complete mining procedure. If Miner generate near optimal hash, then also get some amount of share. So Miners may not participate further.

Mining Pool Methods ,

1. Pay per Share (PPS)

Instant guaranteed payout to a miner at joining. So Miners get almost equal payment, risk is at the pool operator considering uncertainty of finding block. Miners are paid from the pool's existing balance, share of a miner is 𝑅=𝐵 × 𝑝

2. Proportional

Miners earn share once the pool finds a block (end of mining round)

𝑅=𝐵×𝑛𝑁, where 𝑛 is the amount of his own share, and 𝑁 is the amount of all shares in the round

3. Pay per Last N Share (PPLNS)

Similar to proportional, but Miner’s reward is calculated on the basis of N last shares. So Miners get more profit for a short round.

, where

𝐵: Block reward minus pool fee

𝑝: Probability of finding a block in a share attempt (𝑝=1/𝐷), 𝐷 is the block difficulty

1. Summary of Permissionless or Open model of Blockchain 

• Any user can join the network and participate in transactions. For example, Bitcoin is developed on this principle. Blockchain is fundamental building block of Bitcoin.
• The blockchain provides the backbone of the permissionless digital currency : Provides a decentralized architecture and Tamper-proof through hash-chain
• Miners ensures the consensus in the system

3. Permissioned Model

• It is an initiative from industrists. Mainly known as Blockchain 2.0
• It is based on Closed environment

Set of nodes which knows each other, but may not trust each other. (so Security and consensus are still required).

Nodes can’t join to network anytime. Before joining network, nodes need to validate themselves through authentication or pre-authorization mechanism. Users are authenticated prior.

• Run blockchain among known and identified participants
• Particularly interesting for business applications – execute contracts among a closed set of participants. For example, Smart Contracts, Provenance tracking of assets

Smart Contracts = “A self executing contract in which the terms of the agreement between the buyer and the seller is directly written into the lines of code”. 

Like scripts in Permissionless Blockchain Model, Detailed script using General Purpose Programming Language (for example, golang) can be used in Permissioned Blockchain Model to execute complex contracts.

#) Design Limitations

• Sequential Execution

Consensus order & execute transactions in sequential order. This gives a bound on the effective throughput.

Throughput = number of transaction committed per second or per unit time

So throughput is inversely proportional to commitment latency. Increase in difficulty (i.e. complexity) of challenge, will make drop in the effective throughput.

It also lead to a possible attack on the smart contract platform with malicious contract. Attacker can introduce a contract which will take long time to execute. That will launch Denial of Service (DoS) attack.

• Non-deterministic Execution

Some programming languages may produce different execution order in different run. Due to that the system may lead to inconsistent states (many fork in the blockchain).

Execution should always needs to be deterministic. Domain specific language (DSL) can be used to avoid such problems (for example, Ethereum )

• Execution on all nodes

Generally, execute smart contracts at all nodes, and propagate the state to others, to reach consensus

Consensus = Execute the contracts, Based on the inputs it reach to certain states. Propagate state to all nodes, Verify that the states match to ensure same state is propagated

So it needs sufficient number of trusted nodes to validate the execution of contracts. In case of more malicious nodes than trusted node, then they may get control over the entire environment. PoW can be used to avoid this problem, but even that may lead to starvation problem with a contract taking long time.

State synchronization across all nodes can help to solve this problem (one node execute the contract and then propagate the state further).

To avoid problem of faulty node (executing contact which is faulty), State Machine Replication can be used.

State Machine Replication

It involves execution of contract at a subset of nodes (rather than single node), and ensure that the same state is propagated to all the nodes in the network.

It is a powerful tool to ensure consensus in permissioned blockchain environment.

Steps in Distributed State Machine Replication

1. Place copies of the state machine on multiple independent servers. (Each server to have a copy of the entire state machine.
2. Servers receive client requests, as an input to the state machine.

Request goes to different servers, so if execution of state in each server will lead to different state on those servers.

3. So propagate the inputs to all the servers (instead of sending state by executing requests)
4. Order the inputs based on some ordering algorithm (may be associated timestamp with request can be used for ordering)
5. Execute the inputs based on the order decided, individually at each server.

So all server reaching the same state.

6. Sync the state machines across the servers, to avoid any failure.
7. If output state is produced, then server inform the clients/users about the output

#) Problems in this process, which require consensus algorithm in system ,

1. Need to maintain ordering service
2. On presence of failure, all servers need to be on the same state.

#) Reason to use state machine replication based consensus over permissioned blockchains

1. The network is closed, the nodes know each other, so state replication is possible among the known nodes/peers
2. Avoid the overhead of mining. No need to spend anything (like power, time to solve challenge, coins/digital cryptocurrency) other than message passing.
3. Some machines can be faulty or behave maliciously, so consensus is still required.

Distributed Consensus based on State Machine Replication System

#) Some Use-Cases

• Flight control system: E.g. Boeing 777 and 787
• Fund transferring system: Bitcoin and cryptocurrencies
• Leader election/Mutual Exclusion
• Party venue decision (either CCD or SubWay)

#) Each process can be in one of the 3 states

1. Undecided state: proposed value v from set of feasible values D
2. Communication state: exchange values among themselves
3. Decided state: After applying Consensus, set a decision variable d

#) Requirement of a Consensus Algorithm (are same as that in Permissionless Model)

1. Termination: Eventually each correct process sets its decision variable and Terminates after decision variable
2. Agreement: Every process should reach to common agreement. The decision value of all correct processes is the same.
3. Integrity: If the correct processes all proposed the same value, then any correct process in the decided state has chosen that value

#) Algorithms for Distributed Consensus based on State Machine Replication System

support Crash or Network Faults

1. PAXOS
2. RAFT

support Byzantine Faults (including Crash or Network Failures)

3. Byzantine fault tolerance (BFT)
4. Practical Byzantine Fault Tolerance (PBFT)

1. PAXOS

• First Consensus Algorithm (proposed by L. Lamport in 1989)
• Objective is to choose a single value under crash or network fault
• Uses majority voting principle, in synchronous environment.
• Types of nodes

Proposer: Propose values that should be chosen by the Consensus algorithm

Acceptor: Form the consensus and accept values Either accept or reject proposed the values

Learner: Learn which value was chosen by each acceptor (Everyone is learner in network, which learn the majority decision)

• System process are,

Making a proposal

1. Proposer Process: Initiate a ‘proposal number’ and send to Acceptor process (number good enough to get accepted). ‘Proposal number’ form a timeline, biggest number considered up-to-date.
2. Acceptor’s Decision Making: Each acceptor compares received proposal number with the current known values for all proposer’s prepare message. Accordingly accept or reject it.
3. Acceptor’s Message: Then Acceptor prepare the response message with ‘acceptance + proposal number + already accepted value’.

Accepting a value: 

1. Proposer’s Decision Making:Proposer receive a response from majority of Acceptors before proceeding
2. Accept Message:Proposer send accept message to all Acceptors. Message includes ‘proposer number + single value proposed’
3. Notifying Learner: Each Acceptor after accepting value from Proposer, informs the Learner about majority voted value. So everyone learns about majority voting value.

Handling Failures:

1. Single Proposer system is very simple. Proposer always have proposal with biggest number. So no proposal is rejected (considering that majority of Acceptors are non-faulty).

2. Acceptor fails during prepare phase: No issues, as other acceptor can hear the proposal and vote
3. Acceptor fails during accept phase: No issues, as other acceptor can vote for the proposal
4. More than N/2 - 1 acceptors fail: No proposer get a reply. So No values can be accepted (i.e. No Consensus)
5. Proposer fails during prepare phase: It means no one is proposing any value. Acceptors wait for some time, and then someone else become the Proposer (some Acceptor becomes the Proposer and propose new value)
6. Proposer fails during accept phase: Acceptors have already agreed upon whether to choose or not to choose the proposal based on the shared majority votes. From that it can be find if proposal is accepted or not.
7. Dueling Proposers:It is to due or tie case, where a Proposer sends new proposal value based on the other Proposer’s value. To avoid such cases, need to block the Proposers with lower id.

• Single selection is simple view of PAXOS. While in real system, there can be a sequence of selection, which is known as Multi PAXOS system. In that system, sequence of choices are made by applying repeated PAXOS protocol.

This is a little complicated, as all PAXOS messages need to be exchanges among each other repeatedly. That increases the complexity of PAXOS protocol in real system.

2. RAFT = Leader election mechanism

• RAFT is designed as an easy alternate of PAXOS, as PAXOS is not very relevant to Blockchain commitment protocol.
• It is widely used for Consensus mechanism.
• It is a generic way to distribute a state machine among a set of servers; and Ensures that every server agrees upon the same series of state transitions.

Basic idea is simple ,

• The nodes collectively selects a Leader; others become Followers. (With a Leader in the system achieving consensus becomes much easier, as can avoid having multiple Proposers proposing something altogether)
• Distributed environment elect a leader based on PAXOS algorithm. So there would be single Proposer i.e. Leader and all Acceptors will become Followers of Leader. Follower may either follow Leader or not.
• The Leader is responsible for state transition log replication across the Followers (i.e. all further transaction will be committed by elected Leader)
• Once Leader is elected, there can’t be multiple proposals and system becomes simple.

Operations in RAFT ,

1. (re)electing a leader
2. committing multiple values to the transaction log
3. dealing with replicas failing : Failure of up to (N/2 - 1) nodes does not affect the system, as system rely on Majority Voting Principle and majority of Followers are non-faulty & can send vote.

3. Byzantine fault tolerance (BFT) = Lamport-Shostak-Pease Algorithm 

PAXOS & RAFT assumes that Faulty node (malicious node) will not send any vote (i.e. from Non-Faulty node always receive correct vote).

But Byzantine Faulty node, may selectively send vote to some of nodes. If Leader behaves in Byzantine way (i.e. not sending same proposal to all Followers or Peers), PAXOS & PAFT can’t recover from it.

So PAXOS & RAFT can’t tolerate,

1. Crash fault nodes more than (N/2 - 1), as depends on Majority Voting
2. Byzantine Node (Leader)

BFT Model depends on ,

• N number of process (or nodes) with at most f faulty, where N = 2f+1)
• Receiver always knows the identity of the sender, i.e. Closed Model for Permissioned Blockchain Environment
• Fully connected
• Reliable communication medium
• Synchronous system, i.e. message will be received in predefined time interval

NOTE: In fully asynchronous system, even if a single node is faulty; then achieving consensus in predefined time interval is not possible

4. Practical Byzantine Fault Tolerance (PBFT)

Real system are not always synchronous, and may behave asynchronous way with no guarantee of message receipt within certain timeout duration. PBFT can be used in asynchronous environment under consideration of Impossibility Theorem.

Impossibility Theorem : It states that in pure asynchronous environment, it is impossible to reach consensus in the presence of at least a single faulty node.

PBFT is Practical because ,

• Ensures safety over an asynchronous network in presence of faulty node (but not liveness over pure asynchronous network due to Impossibility Principle!)

[To ensure liveness, there exist Weak Asynchronous assumption]

• support Byzantine Failure
• Low overhead

Real Applications examples are : Tendermint Core, IBM's Openchain, ErisDB, Hyperledger

PBFT supports,

• Asynchronous distributed system - delay in transmitting message(s), can receive out of order message(s)
• Byzantine failure handling in system - arbitrary node behavior
• Privacy over the system - ensure tamper-proof message(s) with hashing technique and authentication technique through digital signature 

PBFT system model is,

• A state machine is replicated across different nodes
• 3𝑓+1 replicas are there, where 𝑓 = the number of faulty replicas
• The replicas move through a succession of configurations, known as views.

One replica in a view is primary (like Leader) and others are backups (like Peers) [view = primary + backups]

[In a view, a node may change to primary replica; and so previous primary replica will then become backup]

Views are changed when a primary is detected as faulty

• Every view is identified by a unique integer number 𝑣 .
• Only the messages from the current views are accepted, in asynchronous network

Pre-prepare and prepare ensure that non-faulty replicas guarantee on a total order for the requests within a view (all requests are processed by Backup in order of sequence number)

View Change Protocol in PBFT

• It is used to enter in new (or next) view by changing the Primary 
• View-change protocol allows the system to make progress when primary fails and thus provides liveness (only in Weak Asynchronous with consideration of timeout by Backups for request to multicast by Primary to Backup)
• When the Primary fails, Backups will not receive any message (such as PRE_PREPARE or COMMIT) from the Primary.

Same may occur due to faulty Primary.

Then non-faulty replicas (Backups) detect the fault and together start View Change operation

View Changes are triggered by timeouts (for initiated request received by Secondary), to prevent Backups from waiting indefinitely for requests to execute.

• The view change operation takes care of
• Synchronization of checkpoints across the replicas (due to the asynchronous nature of system)
• Ensuring that all the replicas are ready to start at the new view 𝑣+1
• 
  

View Change Operations in PBFT,

• Backup starts a timer (to check timeout) when it receives a request, and the timer is not already running,

The timer is stopped when the request is executed

Restarts when some new request comes

• If the timer expires at view 𝑣 before request execution, then Backup starts a View Change to move the system to view 𝑣+1
• Backups Multicasts a <VIEW_CHANGE , 𝑣+1, 𝑛, 𝒞, 𝒫, 𝑖>,𝜎_𝑖 message to all replicas

𝑠 last stable checkpoint known to 𝑖

𝑛 the sequence number of 𝑠

𝒞 a set of 2𝑓+1 valid checkpoint messages proving the correctness of 𝑠 [ This ensures Safety property ]

𝒫 a set containing a set 𝒫𝑚 for each request 𝑚 that prepared at 𝑖 with a sequence number prior to 𝑛

Each set 𝒫𝑚 contains a valid pre-prepare message and 2𝑓 matchings [Old view messages]

• On timer expiry, a backup stops accepting messages except
• Checkpoint
• View-change
• New-View
• The new view is initiated after receiving 2𝑓 View Change messages

Properties ensured by PBFT

1. Safety

The algorithm provides safety if all non-faulty replicas agree on the current sequence numbers of requests that commit locally

2. Liveliness

To provide liveness, replicas move to a new view if they are unable to execute a request

• A replica waits for 2𝑓+1 view change messages and then starts a timer to initiate a new view (avoid starting a view change too soon)
• If a replica receives a set of 𝑓+1 valid view change messages for views greater than its current view, it sends view change message (prevents starting the next View Change too late i.e. to prevent delaying View Change)
• Faulty replicas are unable to impede progress by forcing frequent View Changes through periodic trigger 

[Reference: "Practical Byzantine fault tolerance" , Castro - Miguel and Barbara Liskov , OSDI. Vol. 99. 1999.]