Block Chain Technologies (AD-604 (B)) - Unit 3 Short Notes

How unit 3 is examined

This unit covers permissioned blockchains and the consensus protocols they use (state machine replication, Paxos, RAFT, Byzantine fault tolerance); no topic has been asked recently, so learn each definition and its key numbers.

Permissioned Block chain: Permissioned model and use cases, Design issues, Execute contracts

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. A permissioned blockchain is a ledger where only known, authorised participants may join, read, write or validate transactions, and every member has an identity issued by a membership authority. <mark>Permissioned blockchains trade open participation for identity, privacy and speed.</mark>

Key points.

1. Members are identified and approved, so trust is partial and consensus can be cheap, using voting instead of mining.
2. Use cases include trade finance, supply chain tracking, KYC, interbank settlement and healthcare records shared by a consortium.
3. Design issues are membership and identity management, data privacy between competitors, throughput and latency, the choice of consensus protocol, and governance of who may change the rules.
4. Smart contracts (chaincode) run only on authorised nodes; the result is agreed by the endorsing or validating nodes before it is committed to the ledger.
5. Because the participants are known, a misbehaving member can be identified and removed, which a public chain cannot do.

State machine replication and consensus models for a closed environment

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. State machine replication (SMR) keeps identical deterministic copies of a service on several nodes, applying the same commands in the same order, so that all replicas reach the same state even if some nodes fail. <mark>Agreement on the order of transactions is what makes all replicas end in the same state.</mark>

Key points.

1. A blockchain is a replicated state machine: the ledger is the state and each block is a batch of commands applied in agreed order.
2. A closed environment has a known, fixed set of nodes, so agreement is reached by voting among them and not by proof of work.
3. Crash fault tolerant (CFT) models such as Paxos and RAFT survive nodes that stop; Byzantine fault tolerant (BFT) models survive nodes that lie or act maliciously.
4. Determinism is essential: the same input in the same order must always give the same output on every replica.
5. A consensus protocol must give safety (no two replicas decide differently) and liveness (the system eventually decides).

Paxos and RAFT Consensus

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. Paxos and RAFT are crash-fault-tolerant protocols in which a majority of nodes agrees on a single value or on the order of a replicated log. <mark>With N nodes, they tolerate up to f crashes when N is at least 2f+1.</mark>

Key points.

1. Paxos has three roles: proposers suggest a value, acceptors vote, and learners learn the chosen value.
2. Paxos runs in two phases: prepare/promise, where a proposer asks acceptors to promise to ignore lower-numbered proposals, and accept/accepted, where the value is sent; it is chosen once a majority accepts.
3. RAFT is designed to be easier to understand: it elects one leader per term, and only the leader accepts client commands and replicates log entries to followers.
4. RAFT nodes are in one of three states, follower, candidate or leader; a follower that hears no heartbeat before its random election timeout becomes a candidate and asks for votes, and a majority of votes makes it leader.
5. A log entry is committed when a majority of nodes has stored it, so a minority of crashed nodes cannot stop progress.

Example: N = 5 nodes, majority = 3, so f = 2 crashes are tolerated.
N >= 2f + 1  ->  5 >= 5

Diagram. RAFT states.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-01" viewBox="0 0 424 166" width="424" height="166" role="img" aria-label="RAFT states. F follower, C candidate, L leader"><style>#dsfig-u3-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-01 .t{fill:#16181D;font-weight:500}#dsfig-u3-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-01 .dot{fill:#16181D}#dsfig-u3-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-01 .ah{fill:#454C5A}#dsfig-u3-01 .ah.hi{fill:#2340B8}#dsfig-u3-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-01 .e{stroke:#B1B7C3}html.dark #dsfig-u3-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-01 .t{fill:#E6E8ED}html.dark #dsfig-u3-01 .t.inv{fill:#0F1115}html.dark #dsfig-u3-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-01 .dot{fill:#E6E8ED}html.dark #dsfig-u3-01 .ann{fill:#8FA3FF}html.dark #dsfig-u3-01 .lbl{fill:#858D9C}html.dark #dsfig-u3-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-01 .ah{fill:#B1B7C3}html.dark #dsfig-u3-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M58.8,123.3 Q140.3,111.6 197.1,54.8" marker-end="url(#ah3)"/><path class="e" d="M229,48.5 L365.2,116.6" marker-end="url(#ah3)"/><path class="e" d="M193.2,42.7 Q111.7,54.4 54.9,111.2" marker-end="url(#ah3)"/><path class="e" d="M365,126 L61,126" marker-end="url(#ah3)"/><g class="wl"><rect x="103.4" y="91.3" width="61.5" height="18" rx="9"/><text class="t" x="134.1" y="100.3" dy=".35em" text-anchor="middle">timeout</text></g><g class="wl"><rect x="263.7" y="74" width="68.7" height="18" rx="9"/><text class="t" x="298" y="83" dy=".35em" text-anchor="middle">majority</text></g><g class="wl"><rect x="73.2" y="56.7" width="89.4" height="18" rx="9"/><text class="t" x="117.9" y="65.7" dy=".35em" text-anchor="middle">higher-term</text></g><g class="wl"><rect x="167.3" y="117" width="89.4" height="18" rx="9"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">higher-term</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">F</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">L</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">RAFT states. F follower, C candidate, L leader</figcaption></figure>

Byzantine general problem, Byzantine fault tolerant system, Lamport-Shostak-Pease BFT Algorithm

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. The Byzantine generals problem asks how loyal generals, who communicate only by messengers, can agree on a common plan (attack or retreat) when some generals are traitors who send conflicting messages. ==A system with f Byzantine nodes needs at least N = 3f+1 nodes to reach agreement.==

Key points.

1. A Byzantine fault is any arbitrary or malicious behaviour, such as sending different values to different nodes, which is worse than a simple crash.
2. A Byzantine fault tolerant system must satisfy two conditions: all loyal generals decide on the same plan, and if the commander is loyal, every loyal general follows the commander's order.
3. The Lamport-Shostak-Pease algorithm uses oral (unsigned) messages: with m traitors it needs at least 3m+1 generals and m+1 rounds of message exchange.
4. In the algorithm, the commander sends his value to all lieutenants; each lieutenant then relays what he received to the others, recursively for m rounds, and finally takes the majority of the values received.
5. With only 3 generals and 1 traitor agreement is impossible, because a loyal lieutenant cannot tell whether the commander or the other lieutenant is lying.

Example: m = 1 traitor needs N = 3(1) + 1 = 4 generals and 2 rounds.
Round 1: commander C sends "attack" to L1, L2, L3.
Round 2: each lieutenant relays what he heard; traitor L3 lies.
L1 sees (attack, attack, retreat) -> majority = attack. L2 does the same.

Diagram. Four generals, one traitor.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u3-02" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="C commander, L1 to L3 lieutenants, L3 traitor"><style>#dsfig-u3-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u3-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u3-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u3-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u3-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u3-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u3-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u3-02 .t{fill:#16181D;font-weight:500}#dsfig-u3-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u3-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u3-02 .dot{fill:#16181D}#dsfig-u3-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u3-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u3-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u3-02 .ah{fill:#454C5A}#dsfig-u3-02 .ah.hi{fill:#2340B8}#dsfig-u3-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u3-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u3-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u3-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u3-02 .e{stroke:#B1B7C3}html.dark #dsfig-u3-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u3-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u3-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u3-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u3-02 .t{fill:#E6E8ED}html.dark #dsfig-u3-02 .t.inv{fill:#0F1115}html.dark #dsfig-u3-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u3-02 .dot{fill:#E6E8ED}html.dark #dsfig-u3-02 .ann{fill:#8FA3FF}html.dark #dsfig-u3-02 .lbl{fill:#858D9C}html.dark #dsfig-u3-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u3-02 .ah{fill:#B1B7C3}html.dark #dsfig-u3-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u3-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u3-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u3-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M198.6,53.4 L54.8,197.2" marker-end="url(#ah4)"/><path class="e" d="M212,59 L212,191" marker-end="url(#ah4)"/><path class="e" d="M225.4,53.4 L369.2,197.2" marker-end="url(#ah4)"/><path class="e" d="M61,212 L191,212" marker-end="url(#ah4)" marker-start="url(#ah4)"/><path class="e" d="M233,212 L363,212" marker-end="url(#ah4)" marker-start="url(#ah4)"/><path class="e" d="M61,212 L363,212" marker-end="url(#ah4)" marker-start="url(#ah4)"/><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">L1</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">L2</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">L3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">C commander, L1 to L3 lieutenants, L3 traitor</figcaption></figure>

BFT over Asynchronous systems

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. An asynchronous system has no bound on message delay or processing time, so a slow node cannot be told apart from a failed one. <mark>The FLP result proves that no deterministic protocol can guarantee consensus in an asynchronous system if even one node may fail.</mark>

Key points.

1. The internet behaves asynchronously, so a BFT protocol for it cannot rely on timing assumptions for safety.
2. Practical BFT (PBFT) keeps safety always, and guarantees liveness only when the network is eventually synchronous, which avoids the FLP impossibility in practice.
3. PBFT needs N = 3f+1 replicas; a primary orders the requests, and the phases are pre-prepare, prepare and commit, each needing agreement from 2f+1 replicas.
4. If the primary is faulty or too slow, the replicas run a view change and elect a new primary.
5. Randomised protocols such as HoneyBadgerBFT avoid the FLP limit by using randomness and give liveness even without synchrony.

Last-minute revision

• Permissioned chain: known, authorised members; no mining needed.
• Public chain uses PoW or PoS; permissioned chain uses voting.
• SMR: same deterministic commands in the same order give the same state.
• Consensus needs safety (agree) and liveness (eventually decide).
• Crash fault tolerance (Paxos, RAFT): N ≥ 2f+1, majority quorum.
• Byzantine fault tolerance: N ≥ 3f+1.
• Lamport-Shostak-Pease oral messages: 3m+1 generals, m+1 rounds.
• RAFT: follower, candidate, leader; a term has one leader.
• Paxos roles: proposer, acceptor, learner; phases prepare and accept.
• FLP: no deterministic consensus in an asynchronous system with one fault.
• PBFT phases: pre-prepare, prepare, commit; view change replaces a bad primary.

Memory hooks

• Crash needs a majority (2f+1); traitors need two thirds (3f+1).
• RAFT = Raise a leader, Append, Follow.
• Paxos = Prepare, Promise, Accept.
• FLP: in async you cannot tell slow from dead, so no guarantee.
• PBFT = Pre-prepare, Prepare, Commit: three P/C steps.

Coverage checklist

• Permissioned Block chain: Permissioned model and use cases, Design issues for Permissioned block chains, Execute contracts — no past questions.
• State machine replication, Overview of Consensus models for permissioned block chain- Distributed consensus in closed environment — no past questions.
• Paxos, RAFT Consensus — no past questions.
• Byzantine general problem, Byzantine fault tolerant system, Lamport-Shostak-Pease BFT Algorithm — no past questions.
• BFT over Asynchronous systems — no past questions.