SMR | Tendermint ( Partial Synchronous)| PERMISSIONLESS SETTINGS AROUND A CONSENSUS PROTOCOL

Before reading blog, you can go through this blog for introduction and knowing more around byzantine general problem and how it all started -https://weufoundation.medium.com/consensus-design-around-byzantine-problem-ce75696cd89c .

This blog will take you through these questions are SMR, TENDERMINT AND PERMISSIONLESS SETTINGS

IN THE LAST BLOG WE HD DISCUSSED AROUND BB AND BA (with pki and without pki). Today, in this blog we talked about State Machine Replication (most of the blockchain uses SMR protocol)

Let's start with SMR.

STATE MACHINE REPLICATION

A technique where each node maintains a copy of a state machine, and they need to execute the same sequence of commands on their state machines in order to keep them consistent. For example, a bank system may use SMR to ensure that all the branches have the same balance for each account.

Let's take a poker game example with Alice, Bob, Carol and Dave.

One possible creative example around state machine replication technique in blockchain is a story about a group of friends who want to play a game of poker online. Here is how it goes:

Alice, Bob, Carol, and Dave are four friends who love to play poker. They decide to use a blockchain-based platform to play a game of poker online, without trusting any third-party service. They each download a poker app that implements state machine replication (SMR) to ensure that the game is fair and consistent, even if some of them are dishonest or offline.

The app works as follows:

• The app creates a set of four nodes, one for each player, and assigns them unique identifiers and public keys. Each node represents a state machine that can process inputs (such as bets, cards, and actions) and produce outputs (such as messages, transactions, and outcomes).
• The app also creates a smart contract that defines the rules of the game, such as the initial pot, the betting rounds, the card dealing, and the winning conditions. The smart contract is a deterministic function that takes the current state and input of the game and produces the next state and output of the game.
• The app uses a consensus protocol to coordinate the nodes and ensure that they agree on the same state and output of the game at each step. The consensus protocol works by having each node propose a block that contains one or more inputs from the players, and having the other nodes validate and accept the block if it follows the smart contract. The protocol also handles forks, conflicts, and failures by using a reputation system that rewards honest nodes and penalizes dishonest nodes.
• The app uses cryptography to secure the communication and transactions between the nodes. The app uses digital signatures to verify the identity and authenticity of the inputs from the players and uses encryption to hide the cards from other players until they are revealed.

The game starts as follows:

• Alice creates a new game on the app and invites Bob, Carol, and Dave to join. She sets the initial pot to 100 tokens and the minimum bet to 10 tokens. She also sets a timeout of 10 seconds for each player to make their move.
• Bob, Carol, and Dave accept the invitation and join the game. They each deposit 100 tokens from their wallets to the smart contract. The app generates a random seed and uses it to shuffle and deal two cards to each player. The app also creates a genesis block that contains the initial state and output of the game and broadcasts it to all nodes.
• Alice is the first player to act. She decides to raise by 20 tokens. She sends her input (raise 20) to her node, which creates a new block that contains her input and signs it with her private key. Her node then broadcasts the block to the other nodes.
• Bob, Carol, and Dave receive Alice’s block and validate it by checking her signature and applying her input to the smart contract. They see that Alice has raised by 20 tokens and that the new state and output of the game are updated accordingly. They accept Alice’s block and append it to their local chains.
• Bob is the next player to act. He decides to fold. He sends his input (fold) to his node, which creates a new block that contains his input and signs it with his private key. His node then broadcasts the block to the other nodes.
• Alice, Carol, and Dave receive Bob’s block and validate it by checking his signature and applying his input to the smart contract. They see that Bob has folded and that the new state and output of the game are updated accordingly. They accept Bob’s block and append it to their local chains.

The game continues in this manner until one of the following conditions is met:

• One player wins all the tokens in the pot by having the best hand or by making all other players fold.
• All players agree to end the game by sending a special input (end) to their nodes.
• A timeout or a failure occurs on one or more nodes.

In any case, the app uses the final state and output of the game to determine the outcome and distribute the tokens accordingly. The app also updates the reputation scores of each node based on their behaviour during the game.

A bit around how they are different.

State Machine Replication (SMR) is a method for implementing a fault-tolerant service by replicating servers and coordinating client interactions with server replicas. SMR is significantly more challenging than Byzantine Agreement because it involves parties agreeing on not just a single value, but a sequence of values or operations. This means that in SMR, the participants (clients) and requests can change over time, and the protocol needs to handle these changes to ensure consistency across all replicas.

BA or BB focuses on achieving consensus on a single value among processors in the presence of faults, SMR deals with maintaining consistency across replicated servers in a changing environment with varying clients and requests.

THE SETUP

A client is an entity that interacts with the service by sending requests and receiving responses. A client can be a human user, an application, or another service that runs on top of the consensus protocol.

THE REQUIREMENTS

Consistency and liveness are two important properties of distributed systems. Consistency means that the system behaves in a predictable and correct way, and liveness means that the system makes progress and responds to requests.

The requirement setting with consistency and liveness depends on the specific goals and needs of the system. For example, some systems may require strong consistency, which means that all nodes see the same data at the same time, but this may sacrifice availability or partition tolerance. Other systems may prefer eventual consistency, which means that nodes may see different versions of data for a while, but they will eventually converge to the same state, but this may compromise correctness or safety.

Some examples of consistency models in distributed systems are:

• Strong consistency: Reads always return the most recent write, and writes are visible to all nodes immediately.
• Sequential consistency: Reads and writes appear to happen in some sequential order, and operations of each node appear in this order as specified by its program.
• Causal consistency: Reads and writes that are causally related (i.e., one depends on another) appear to happen in the same order for all nodes.
• Eventual consistency: Reads and writes may return different values for a while, but they will eventually converge to the same value.

Some examples of liveness properties in distributed systems are:

• Availability: Every request receives a response from a non-failing node.
• Progress: Every non-failing node eventually executes its operations.
• Termination: Every operation eventually completes.
• Fairness: Every node has a fair chance to execute its operations.

BUT HERE WE ARE GOING TO DISCUSS AROUND SMR

• Consistency means that all nodes in the network agree on the same state of the blockchain, which is a sequence of blocks that contain transactions. Consistency ensures the validity and integrity of the data.
• Liveness means that the network can process new transactions and add new blocks to the blockchain. Liveness ensures the availability and responsiveness of the service.

• The confirmed set of a processor as the set of transactions that have been signed by a majority of non-faulty processors. A transaction is signed by a processor when it receives a message from the client that contains the transaction and a digital signature.
• The protocol satisfies the SMR properties under the assumption that at least one non-faulty processor receives a signed transaction from each client. The proof is based on showing that the confirmed sets of non-faulty processors are always consistent (they contain the same transactions) and progressive (they grow over time).
• It allows lazy clients to participate in the system without sending messages to all processors. A lazy client is a client that only sends transactions to a subset of processors, instead of broadcasting them to everyone. Though even bitcoin allows this property where the clients can go out of the consensus participation and come back and take part in consensus with f+1 conf. from distinct processors, even if the transactions are confirmed by non-faulty processors. Because the dishonest guy can act malicious in the network but if i carry f+1 confirmations we really don't have to care about even the client went offline.

A consequence for lazy client condition is SMR cannot be solved if f ≥ n/2.

The Dolev-Strong protocol is a consensus protocol that solves the state machine replication problem under the synchronous model assumption. . The synchronous model assumption is the assumption that the communication network has reliable message delivery and bounded message delays.

The Dolev-Strong protocol works as follows: There is a designated sender node that has a private input, and a set of receiver nodes that need to agree on the sender’s input. The sender node broadcasts its input along with a digital signature to all other nodes. Each node that receives a message from the sender or another node forwards it to all other nodes, unless it has already forwarded a message with the same content. Each node maintains a set of messages that it has received, and decides on the output based on the following rules:

- If there are more than f messages with the same content and valid signatures from different nodes, where f is the maximum number of faulty nodes, then output that content.
- If there are more than f messages with different contents and valid signatures from different nodes, then output ⊥ (meaning no agreement).
- If neither of the above conditions holds after N rounds, where N is the total number of nodes, then output ⊥.

The Dolev-Strong protocol guarantees that all honest nodes will output the same value, and that value will be equal to the sender’s input if the sender is honest. This means that the protocol satisfies the properties of agreement and validity, which are the desired properties of a consensus protocol. The protocol is also very fault-tolerant, as it can tolerate up to N-1 faulty nodes out of N total nodes.

So it proves that using Dolev- Strong protocol it is quite simple to implement SMR.

LETS SOLVE A BIT AROUND BYZANTINE BROADCAST USING THE SAME SOLUTION AS SMR

PARTIALLY SYNCHRONOUS SETTINGS

Partial synchronous settings are a way of modeling the communication network of a distributed system. They are based on the idea that the network is usually reliable and fast, but sometimes it can experience delays or failures due to unpredictable events.

As they have to maintain the consistency of the network when network conditions will not be good, but as soon as network conditions becomes good liveness comes in place because when network conditions are not good, they were not receiving any messages, so liveness was not maintained.

So how we are going to implement it? Well here is the solution-

There are two parameters that describe the network behavior: a known finite time range ⊿ and an unknown event called GST (global stabilization time). Before GST, the network can behave arbitrarily, meaning that messages can be lost, delayed, reordered, or duplicated.

Get WEU FOUNDATION’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

After GST, the network becomes synchronous, meaning that messages are delivered within ⊿ time units. However, the nodes in the system do not know when GST occurs or if it has occurred at all.

In this case, processors also don't know the upper bound delta, so protocols can function for any finite bound without knowing its value.

The thing is to figure for which n and f model the protocol works out.

• The unknown Δ model and the GST model. These models are equivalent, meaning that they capture the same network behavior and assumptions. Here we discuss also that how to convert a protocol that works under one model to work under the other model.
• The unknown Δ model is a partial synchronous setting where Δ is unknown to the nodes. This means that the nodes do not know how long it takes for a message to be delivered after GST. The unknown Δ model is useful for designing protocols that do not depend on timing assumptions.
• The GST model is a partial synchronous setting where Δ is known to the nodes. This means that the nodes know how long it takes for a message to be delivered after GST. The GST model is useful for analysing protocols that use timing assumptions.

How to convert a protocol that works under the unknown Δ model to work under the GST model.

• The idea is to give each node the ability to turn Δ into 1 by increasing the intervals between the times at which they execute their instructions. For example, if a node executes an instruction at time t under the unknown Δ model, it will execute it at time 2t under the GST model with Δ = 1. This way, even if GST is larger than Δ (which means that messages are delivered faster than expected), the nodes will still execute their instructions in sync with each other.

How to convert a protocol that works under the GST model to work under the unknown Δ model.

• The idea is to use an algorithm called Clock Synchronization, which allows each node to estimate an upper bound on Δ based on their local clocks and message timestamps. This way, even if Δ is unknown to the nodes (which means that messages are delivered slower than expected), they can still use timing assumptions based on their estimates.

The main thing in BB is like if the broadcaster is faulty, which is f≥1 it not possible and even we have a working protocol it is not possible, due to the contradiction we discussed.

BA and SMR in partially synchronous settings

As we can observe, in the three processors system in the partial synchronous setting is not possible if f≥ n/3.

Well, if we can solve SMR in the partially synchronous setting we can solve BA too with that. So, we are directly ging to talk around SMR here -

BA and SMR in partially synchronous settings with PKI

A.K.A Solving TENDERMINT

An incompatible block in Tendermint is a block that violates the consensus protocol rules, such as having an invalid signature, a wrong hash, or a conflicting previous block. An incompatible block can cause a fork, which is a situation where different validators have different views of the blockchain history. A fork can only happen if at least 1/3 of the validators are faulty or malicious and sign conflicting blocks. Tendermint uses a two-stage voting mechanism to prevent forks and ensure safety and liveness of the protocol.

• Tendermint consists of two main components: a consensus algorithm and an application interface. The consensus algorithm is responsible for coordinating the nodes and reaching agreement on the transactions. The application interface is responsible for validating and executing the transactions and updating the state.
• The consensus algorithm is based on a variant of Practical Byzantine Fault Tolerance (PBFT), which is a classical protocol that can tolerate up to one-third of faulty nodes. The algorithm uses a leader-based approach, where one node is selected as the proposer for each round, and proposes a block of transactions to be committed. The other nodes are called validators, and they vote on the proposed block using a two-phase voting mechanism.
• The application interface is based on the ABCI (Application Blockchain Interface), which is a generic interface that allows any application to run on top of Tendermint. The ABCI defines three types of messages that are exchanged between the consensus algorithm and the application: CheckTx, DeliverTx, and Commit. CheckTx is used to check the validity and priority of a transaction before proposing it. DeliverTx is used to execute a transaction and update the state after it is committed. Commit is used to compute and return a cryptographic hash of the state after each block.
• Tendermint has several advantages over other consensus protocols, such as high performance, simplicity, and flexibility. Tendermint can achieve high performance because it only requires two rounds of communication to commit a block, and it can handle thousands of transactions per second. Tendermint is simple because it only relies on a few assumptions and parameters, and it has a clear separation of concerns between consensus and application logic. Tendermint is flexible because it can support any application that can be modeled as a state machine, and it can be easily integrated with other protocols and platforms.

It's going to simple in terms where if someone is providing the block, and if he doesn't know the predecessor chain rather than we are going to see block they are going to see the predecessor chain. And after that they are going to consider the block.

Quorum certificates are a way of proving that a majority of nodes have voted for a certain value or block in a round of the consensus algorithm. The consensus algorithm is based on a variant of Practical Byzantine Fault Tolerance (PBFT), which is a classical protocol that can tolerate up to one-third of faulty nodes. The algorithm uses a leader-based approach, where one node is selected as the proposer for each round and proposes a block of transactions to be committed.

By this way, it doesn't work though, but if we include two rounds of communication and f+1 proof this is going to work out.

Two stages of voting.

What happens if we consider two stages of voting on the block instead? If they see a QC on the block B produced in stage 1 (say) of round r, proposers then produce a stage 2 vote, and it is a QC in stage 2 that means confirmation.

Does this work? The problem with the previous protocol was that a block might be confirmed, but non-faulty processes might not see the relevant QC.

So, if we have two stages of voting, if we consider blocks confirmed when they see a Stage 2 QC but already have processors ‘lock’ on a block when they see a Stage 1 QC, then we’ll satisfy consistency.

Summary so far:

Have two stages of voting in each round.

Have processors lock on a block when they see a Stage 1 QC.

Release the lock when they see an incompatible block with a higher QC.

Consider a block confirmed when it gets a Stage 2 QC.

…then we’ll satisfy consistency. It’ll also be easy to prove liveness.

Its going to be the same , with just release in the round 1 , if the processors see that there are more QC locked

A QC block is considered to be valid and can be extended by the leader of the round. The protocol consists of three steps:

• Time t = 3rA: The leader of the round extends the highest QC block they have and broadcasts it to other nodes. They also set a timer for Δ time units.
• Time t + Δ: The leader checks whether they have received a higher QC block from another node. If so, they abandon their own block and extend the higher one. They broadcast the new block and reset the timer for another Δ time units.
• Time t + 2Δ: If the leader’s block receives enough votes from other nodes to form a Stage 2 QC, the block is confirmed and added to the chain. Otherwise, the leader waits for another Δ time units and repeats the process.

Casper FFG ( Ethereum)

Casper FFG is a consensus protocol for the realization of proof-of-stake (PoS) on Ethereum. It is based on the idea of a finality gadget, which is a mechanism that can finalize blocks on top of an existing proof-of-work (PoW) chain. Casper FFG uses a hybrid PoW/PoS model, where PoW is used for block proposal and PoS is used for block finalization. Casper FFG aims to achieve the following goals:

• Security: Casper FFG ensures that finalized blocks are secure and irreversible, even in the presence of network delays or malicious nodes. It also introduces a slashing mechanism that penalizes nodes for violating the protocol rules or trying to revert finalized blocks.
• Scalability: Casper FFG reduces the need for PoW, which consumes a lot of energy and resources. It also enables faster confirmation times and higher throughput, as finalized blocks do not need to wait for more PoW confirmations.
• Decentralization: Casper FFG allows anyone to participate in the consensus process by staking Ether, the native currency of Ethereum. It also reduces the risk of centralization by making PoW less dominant and rewarding honest nodes for their contributions.

Casper FFG works as follows:

• The underlying PoW chain produces blocks at regular intervals, called epochs. Each epoch consists of 50 blocks, and the first block of each epoch is called a checkpoint. Checkpoints are the only blocks that can be finalized by Casper FFG.
• The nodes that participate in Casper FFG are called validators. Validators have to deposit a minimum amount of Ether into a smart contract, called the validator deposit contract, to join the validator set. Validators can also withdraw their deposits after a certain period of time, called the withdrawal period.
• Validators take turns to propose checkpoints and vote on them. The proposer of a checkpoint is chosen randomly by a function that depends on the epoch number and the validator IDs. The proposer broadcasts their proposed checkpoint to other validators, along with a reference to the previous checkpoint they have seen.
• Validators vote on checkpoints by sending messages that contain their ID, the hash of the checkpoint, the epoch number, and their signature. Validators can vote on multiple checkpoints in different epochs, but they have to follow some rules to avoid conflicting votes. These rules are called the slashing conditions, and they prevent validators from voting on two different checkpoints in the same epoch or voting on a checkpoint that does not reference their previous vote.
• A checkpoint is considered justified if it receives votes from at least two-thirds of the validators in terms of stake. A checkpoint is considered finalized if it is justified and its direct ancestor is also justified. A finalized checkpoint cannot be reverted by any means, and it confirms all its ancestors as well.
• Validators receive rewards for proposing and voting on checkpoints, and they lose their deposits if they violate the slashing conditions or go offline for too long. The rewards and penalties are calculated by a formula that depends on various factors, such as the total stake, the number of validators, and the finality delay.

Casper FFG is an overlay that abstracts the block proposing mechanism and is only responsible for consensus. The block proposing mechanism is implemented by the underlying chain, and the block proposal from the underlying chain is called checkpoints. Casper FFG is inspired by PBFT, a classical Byzantine fault tolerant consensus protocol, but it adds some new features and simplifies some rules. Casper FFG also has some similarities with Tendermint, another PoS-based consensus protocol.

LET'S SUMMARISE EVERYTHING WITH BA , BB AND SMR ( synchronous and partially synchronous with PKI and without PKI)

A BRIEF AROUND BITCOIN (A PERMISSIONLESS CONSENSUS)

• Probabilistic: Bitcoin does not guarantee that all nodes will agree on the same state at all times, but it makes it very unlikely that they will disagree for long. This is because PoW makes it hard for an attacker to create a longer chain than the honest nodes, unless they have more than 50% of the computing power in the network. The probability of disagreement decreases exponentially as more blocks are added to the chain, making it more secure and stable.
• Works in the synchronous setting: Bitcoin assumes that the network is synchronous, meaning that there is a known upper bound on the message delay between nodes. This assumption is necessary for PoW to work, as it ensures that nodes can synchronize their clocks and agree on the difficulty of the puzzle. If the network is asynchronous, PoW might not be able to prevent forks or double-spending attacks.

• Lazy client’ condition: Bitcoin also assumes that there is a ‘lazy client’ condition, meaning that there is at least one honest node that does not participate in PoW but only validates and follows the longest chain. This node acts as a passive observer and can detect any inconsistency or fraud in the system. If there is no lazy client, an attacker might be able to fool all active nodes into accepting a fake chain.

I hope it helps you to understand how to solve the consensus problem in STATE MACHINE REPLICATION (with PKI AND WITHOUT PKI).

We discussed how tendermint works and a bit of around permissionless protocol like bitcoin too.

I hope you enjoyed reading this blog and learned something new about consensus protocols for distributed systems. Consensus protocols are fascinating and important topics that have many applications and implications for the future of computing and society. If you liked this blog, please share it with your friends and colleagues who might be interested in learning more about SMR, BA and BB. You can also leave a comment below with your feedback or questions. Thank you for reading! 😊

Written by — Fardeen khan. Thanks to — Andrew Lewis-Pye for providing valuable lectures out there .

Connect with me here — ( https://x.com/thelastknown_?t=RfAJjWStYGwI6y4GCrOfGA&s=09 )