Probabilistic Consensus

Probabilistic finality

Simple Fundamental Explanation

Imagine 100 people in a massive stadium trying to agree on what color to paint the walls: Red or Blue. They cannot all talk at once.

Deterministic Consensus: A leader stands up, counts everyone’s vote one by one, declares the winner, and makes everyone sign a contract. If the leader has a heart attack halfway through, the whole process freezes, a new leader is elected, and they start over.
Probabilistic Consensus: Everyone whispers their favorite color to 5 random people near them. If you hear “Red” more than “Blue”, you change your mind to “Red”. In the next minute, everyone whispers again.

Eventually, the entire stadium will be whispering the exact same color. There is no leader. There is no official “contract”. But at a certain point, the probability of the crowd suddenly changing their mind back to the other color is zero.

Probabilistic Consensus algorithms allow a distributed network of computers to agree on a single state of truth without needing a perfect, synchronized, deterministic voting process.

Deep Dive: How It Works Under the Hood

Traditional consensus algorithms like Paxos or Raft are deterministic. They provide absolute guarantees of safety (they will never agree on two different things) under specific failure conditions (usually $< 50%$ of nodes failing). However, they require extensive communication overhead (often $O (N^{2})$ ) and strict leader election.

Probabilistic consensus sacrifices deterministic finality for massive scalability and partition tolerance.

The Nakamoto Consensus (Bitcoin)

The most famous probabilistic consensus is Proof-of-Work (Nakamoto Consensus) used in blockchains. When a new block is mined, the network doesn’t explicitly “vote” to accept it. Instead, miners simply start building the next block on top of it.

If two conflicting blocks are mined simultaneously, the chain forks.
The rule is: Always trust the longest chain.

Because mining requires massive computational power, the probability of an attacker secretly building a longer chain in the background drops exponentially with every new block added.

Avalanche Consensus

A newer approach is the Avalanche protocol. It uses a mechanism called Metastable Subsampling. A node wants to decide between transaction A or B.

It asks a small, random sample of $K$ peers what they prefer.
If a supermajority ( $> α$ ) says A, the node changes its preference to A.
It repeats this process over and over.

The system acts like a ball resting on the peak of a hill (a metastable state). A tiny gust of wind (random network noise) will push the ball slightly to one side. Once it starts rolling down one side, momentum (the feedback loop of nodes changing preferences) takes over, and the entire network rapidly crashes into a single, irreversible decision.

Visual Diagram: Avalanche Subsampling

Network of 1,000 nodes.
Node X is undecided between Red and Blue.

Round 1:
X asks 10 random nodes: [R, R, R, R, B, R, R, R, B, B]
7 Red, 3 Blue.
X tentatively adopts Red.

Round 2:
X asks 10 different random nodes: [R, R, R, R, R, R, R, B, R, R]
9 Red, 1 Blue.
X becomes more confident in Red.

Round N:
After getting a supermajority for Red 20 times in a row,
X permanently locks in Red. The probability that the rest
of the network locked in Blue is astronomically low.

Practical Example: Cryptocurrency Finality

In a deterministic system like a SQL database, when you commit a transaction, it is 100% final instantly.

In Bitcoin, when you transfer money, there is no “final” state. When your transaction is included in a block (1 confirmation), there is a tiny probability that the block could be overwritten by a longer chain (an orphan block).

After 2 blocks, the probability is lower.
After 6 blocks (usually ~1 hour), the probability of the transaction being reversed is considered statistically impossible, unless an attacker possesses $> 50%$ of the entire world’s computational power.

Exchanges wait for 6 confirmations because they rely on the mathematical certainty of the probabilistic curve. The transaction is never technically final, but practically, it is set in stone.

The Mathematics: Equations and In-Depth Analysis

1. Probability of a Reversal in Nakamoto Consensus

Assume an attacker has a proportion $q$ of the network’s hash power, and the honest nodes have $p$ (so $p + q = 1$ ). Assume the honest nodes have already mined $z$ blocks on top of your transaction.

What is the probability that the attacker can mine $z$ blocks faster than the honest network to rewrite history? This is modeled as a Gambler’s Ruin problem.

If $q \geq p$ , the attacker will eventually win (Probability = 1). If $q < p$ , the probability $P_{z}$ of the attacker catching up from $z$ blocks behind is:

P_{z} = 1 - k = 0 \sum z \frac{λ ^{k} e ^{- λ}}{k !} (1 - (q / p)^{z - k})

(Where $λ = z \frac{q}{p}$ is the expected number of blocks the attacker mines while the honest network mines $z$ blocks).

Satoshi Nakamoto provided a simpler approximation in the original whitepaper. For a 10% attacker ( $q = 0.1$ ):

$z = 0 \to P = 1.0$
$z = 1 \to P \approx 0.2$
$z = 5 \to P \approx 0.001$
$z = 10 \to P \approx 0.0000012$

The probability of reversal drops exponentially as $z$ increases.

2. Avalanche Metastability

In Avalanche, the network size is $N$ , the sample size is $k$ , and the supermajority threshold is $α$ . The state of the network can be defined by the number of nodes preferring Red ( $S_{r}$ ). The probability that a specific node switches to Red in a given round is a hypergeometric distribution (drawing $k$ nodes from $N$ , needing at least $α$ Reds).

Because $α > k /2$ , the transition function is non-linear. If $S_{r} = 50%$ , the system is unstable. But if $S_{r}$ drifts to $51%$ , the probability of a node sampling a majority of Reds is slightly higher than $51%$ . This creates a positive feedback loop. The math proves that the expected time to reach $100%$ agreement is $O (lo g N)$ , making it incredibly fast and scalable.

Lab

Compare Nakamoto probabilistic finality (P(reversal) vs confirmation depth) to an Avalanche-style commit threshold over consecutive supermajority polls — same README math, two notions of “done.”

Confirmations (z)6 blocks deep

Attacker hash power (q)10% attacker · 90% honest

Avalanche roundround 0

Network Red bias58% prefer Red

Nakamoto chain — gold = confirmed depth; dashed = genesis.

commit threshold 0.0100%

Avalanche subsampling — lock after 8 consecutive α=7 majorities (k=10).

Last poll: 5/10 Red → preference blue

With q = 10% and z = 6, is P(reversal) already below the exchange threshold (0.0100%)? (Avalanche streak: 0/8.)

z=6: P(final) = 99.98% · Avalanche round 0: streak 0/8 — Nakamoto threshold likely met.