blockchainkit.consensus#

blockchainkit.consensus hub · History · Examples · API reference

Consensus: agreement protocols, proof of work and stake, and the attacks they resist.

Proof-of-work search and its expected cost, catch-up probabilities, and stake-weighted proposer selection.

Every public name below is re-exported by the subpackage: import it as bk.consensus.<name>. The plotting helpers are the exception: import them explicitly from blockchainkit.consensus.visualizers, which loads Matplotlib.

Types and results#

Result containers for blockchainkit.consensus.

class blockchainkit.consensus.core.base.MiningResult(block, attempts)[source]#

Bases: object

A successful mined block and the number of hashes attempted.

Parameters:
block: Block#
attempts: int#
class blockchainkit.consensus.core.base.GeneralsResult(decisions, agreement, validity)[source]#

Bases: object

Outcome of an oral-messages run.

Variables:

  • decisions (dict) – Each loyal lieutenant’s decision.

  • agreement (bool) – All loyal lieutenants decided the same (condition IC1).

  • validity (bool) – If the commander is loyal, every loyal lieutenant followed its order (condition IC2); vacuously true for a traitorous commander.

Parameters:
decisions: dict[int, str]#
agreement: bool#
validity: bool#
class blockchainkit.consensus.core.base.ConsensusRun(decisions, rounds, decided)[source]#

Bases: object

Outcome of a randomized-consensus run: who decided what, after how many rounds.

Parameters:
decisions: dict[int, int]#
rounds: int#
decided: bool#
class blockchainkit.consensus.core.base.ViewChangeRun(view_starts, timeouts, decided_view, decision_time)[source]#

Bases: object

Views tried under partial synchrony, until the first one that made progress.

Parameters:
view_starts: tuple[int, ...]#
timeouts: tuple[int, ...]#
decided_view: int#
decision_time: int#
class blockchainkit.consensus.core.base.SquareRootResult(root, multiplications)[source]#

Bases: object

A modular square root and the multiplications spent computing it.

Parameters:

  • root (int)

  • multiplications (int)

root: int#
multiplications: int#
class blockchainkit.consensus.core.base.PBFTResult(prepared, commits)[source]#

Bases: object

Values each honest replica prepared and committed (None if it did not).

Parameters:
prepared: dict[int, str | None]#
commits: dict[int, str | None]#
class blockchainkit.consensus.core.base.DifficultyRun(block_times, targets)[source]#

Bases: object

Simulated block intervals and the target in force for each block.

Parameters:
block_times: tuple[float, ...]#
targets: tuple[int, ...]#
class blockchainkit.consensus.core.base.SelfishMiningResult(selfish_blocks, honest_blocks, revenue)[source]#

Bases: object

Blocks each side contributed to the final chain, and the pool’s share.

Parameters:

  • selfish_blocks (int)

  • honest_blocks (int)

  • revenue (float)

selfish_blocks: int#
honest_blocks: int#
revenue: float#
class blockchainkit.consensus.core.base.Offense(validator, kind, first, second)[source]#

Bases: object

Two votes by one validator that violate a Casper slashing condition.

Parameters:
validator: str#
kind: str#
first: tuple[int, int, bytes]#
second: tuple[int, int, bytes]#

Constructions and protocols#

The Byzantine generals problem and the oral-messages algorithm (1982).

Lamport, Shostak and Pease asked how loyal generals can agree on a plan when some generals, possibly including the commander, are traitors who send different messages to different recipients. Their algorithm OM(m) has every lieutenant relay what it heard, recursively, and take a majority. It succeeds whenever there are more than three times as many generals as traitors: n > 3m. With three generals and one traitor no algorithm can.

blockchainkit.consensus.systems.byzantine.oral_messages(generals, traitors, order, *, rounds, lie=<function _default_lie>)[source]#

Run OM(rounds) with general 0 as commander.

Parameters:

  • generals (int) – Total number of generals n, at least 3; general 0 commands.

  • traitors (set of int) – Traitorous generals; they send lie(sender, receiver, value) instead of the true value.

  • order (str) – The commander’s order, "attack" or "retreat".

  • rounds (int) – The recursion depth m: OM(m) tolerates m traitors when n > 3m.

  • lie (collections.abc.Callable) – The traitors’ strategy.

Returns:

Loyal lieutenants’ decisions and whether IC1 and IC2 hold.

Return type:

blockchainkit.consensus.core.base.GeneralsResult

Examples

>>> from blockchainkit.consensus import oral_messages
>>> oral_messages(4, {3}, "attack", rounds=1).decisions
{1: 'attack', 2: 'attack'}

Ben-Or’s randomized consensus (1983), and the FLP impossibility (1985) it sidesteps.

Fischer, Lynch and Paterson proved that no deterministic protocol can guarantee agreement in an asynchronous network if even one process may crash: an adversary scheduling message delivery can keep it undecided forever. Ben-Or’s protocol escapes by tossing coins. In each round processes exchange values, propose a strong majority if they see one, and adopt a proposal or flip a coin. Whatever the schedule, the coins eventually line up.

blockchainkit.consensus.systems.randomized.ben_or(initial, faults, *, coin=None, adversarial=True, seed=0, max_rounds=1000)[source]#

Run Ben-Or’s binary consensus for crash faults (n > 2f).

Each process waits for n - f messages per phase, the most it can wait for when f processes may have crashed; the scheduler chooses which.

Parameters:

  • initial (collections.abc.Sequence of int) – Each process’s input bit.

  • faults (int) – The number of crashes f the protocol is sized for.

  • coin (collections.abc.Callable, optional) – coin(process, round) -> 0 or 1. Defaults to a seeded fair coin. Pass a deterministic function to see the FLP adversary win.

  • adversarial (bool) – If True, the scheduler delivers the messages most likely to delay a decision; otherwise a random n - f subset.

  • seed (int) – Seed for the coin and the random scheduler.

  • max_rounds (int) – Give up after this many rounds.

Returns:

Decisions so far, rounds run, and whether every process decided.

Return type:

blockchainkit.consensus.core.base.ConsensusRun

Examples

>>> from blockchainkit.consensus import ben_or
>>> ben_or([1, 1, 1], faults=1).decisions
{0: 1, 1: 1, 2: 1}

Partial synchrony (Dwork, Lynch and Stockmeyer 1988): progress after an unknown GST.

Real networks are neither synchronous (known delay bound) nor fully asynchronous (FLP applies). Partial synchrony assumes a bound Delta holds after some unknown Global Stabilization Time (GST). Protocols stay safe always, and make progress once a leader’s view lasts long enough: doubling the timeout each view guarantees that eventually it exceeds Delta.

blockchainkit.consensus.systems.synchrony.view_changes(gst, delta, base_timeout, *, growth=2, max_views=64)[source]#

Simulate leader views with growing timeouts until one makes progress.

Before GST the adversary delays the leader’s message past every timeout; from GST on it arrives after delta ticks. View v lasts base_timeout * growth**v and succeeds when it starts at or after GST and its timeout is at least delta.

Raises:

TimeoutError – No view succeeded within max_views (for example, timeouts that never grow past delta).

Parameters:
Return type:

ViewChangeRun

Examples

>>> from blockchainkit.consensus import view_changes
>>> view_changes(gst=10, delta=5, base_timeout=1).decided_view
4

Pricing via processing (Dwork and Naor 1992): make each message cost computation.

To fight junk mail, Dwork and Naor proposed that a sender compute a pricing function, moderately hard to evaluate but easy to check, for each message. One of their examples is a square root modulo a prime: computing it takes an exponentiation, checking it takes one multiplication. Back’s Hashcash later used hash preimages for the same purpose, and Bitcoin’s proof of work descends from that.

blockchainkit.consensus.systems.pricing.modular_square_root(value, prime)[source]#

Compute a square root modulo a prime p = 3 (mod 4), counting multiplications.

For such primes, value**((p + 1) / 4) is a square root of any quadratic residue. Square-and-multiply needs about 1.5 log2 p multiplications; checking the answer needs one.

Raises:

ValueError – prime is not a prime congruent to 3 modulo 4, or value has no square root (it is not a quadratic residue).

Parameters:
Return type:

SquareRootResult

Examples

>>> from blockchainkit.consensus import modular_square_root
>>> result = modular_square_root(4, 7)
>>> result.root ** 2 % 7
4

Bounded proof-of-work experiments with explicit success probabilities.

blockchainkit.consensus.systems.pow.target(difficulty)[source]#

Return the inclusive target for a leading-zero-bit difficulty.

>>> from blockchainkit.consensus import target
>>> target(0) == 2**256 - 1
True
Parameters:

difficulty (int)

Return type:

int

blockchainkit.consensus.systems.pow.expected_trials(difficulty)[source]#

Return 2**difficulty, assuming independent uniform 256-bit hashes.

Parameters:

difficulty (int)

Return type:

int

blockchainkit.consensus.systems.pow.valid_pow(block)[source]#

Check that the block hash, interpreted big-endian, is at most its target.

Parameters:

block (Block)

Return type:

bool

blockchainkit.consensus.systems.pow.mine(block, *, max_attempts=100000)[source]#

Search sequential nonces starting at block.nonce, with a strict bound.

Raises:

  • TimeoutError – No solution was found within max_attempts (not evidence of no solution).

  • ValueError – The search would exceed the 64-bit nonce space.

Parameters:
Return type:

MiningResult

Practical Byzantine Fault Tolerance (Castro and Liskov 1999): the normal-case round.

With n = 3f + 1 replicas, any two quorums of 2f + 1 overlap in at least f + 1 replicas, so at least one honest replica is in both. A replica prepares a value after 2f matching prepare messages and commits it after 2f + 1 matching commits. Two honest replicas can then never commit different values in one view, even if the leader equivocates, as long as at most f replicas are faulty.

blockchainkit.consensus.systems.pbft.quorum_size(replicas)[source]#

Return 2f + 1 for the largest f with n >= 3f + 1.

>>> from blockchainkit.consensus import quorum_size
>>> quorum_size(4), quorum_size(7)
(3, 5)
Parameters:

replicas (int)

Return type:

int

blockchainkit.consensus.systems.pbft.pbft_round(replicas, faulty, value, *, equivocate=False, other='B')[source]#

Run one PBFT pre-prepare / prepare / commit exchange with leader 0.

Faulty replicas send prepare and commit messages for both values to everyone, the most confusing thing they can do. A faulty leader with equivocate=True pre-prepares value to the first half of the honest replicas and other to the rest.

Parameters:

  • replicas (int) – Number of replicas n, at least 4.

  • faulty (set of int) – Faulty replica numbers. The protocol is sized for f = (n - 1) // 3; pass more to see safety fail.

  • value (str) – The leader’s value, and the conflicting one an equivocating leader also sends.

  • other (str) – The leader’s value, and the conflicting one an equivocating leader also sends.

  • equivocate (bool)

Returns:

What each honest replica prepared and committed.

Return type:

blockchainkit.consensus.core.base.PBFTResult

Idealized models of an attacker catching up with the honest chain.

blockchainkit.consensus.systems.catch_up.eventual_catch_up(attacker_fraction, deficit)[source]#

Return eventual catch-up probability in an ideal infinite random walk.

For q<1/2 this is (q/(1-q))**deficit. This is NOT Nakamoto’s finite- confirmation Poisson model: there is no propagation delay or time bound.

>>> from blockchainkit.consensus import eventual_catch_up
>>> eventual_catch_up(0.25, 2)
0.1111111111111111
Parameters:

  • attacker_fraction (float)

  • deficit (int)

Return type:

float

blockchainkit.consensus.systems.catch_up.attacker_success_probability(attacker_fraction, confirmations)[source]#

Return Nakamoto’s probability that an attacker ever overtakes z confirmations.

While the honest chain gains z blocks, the attacker’s progress is approximately Poisson with mean lambda = z q / p. From each possible lead k, the attacker still needs to make up z - k blocks, which by eventual_catch_up() happens with probability (q/p)**(z-k) (whitepaper, section 11):

P = 1 - sum_{k=0}^{z} e^(-lambda) lambda^k / k! * (1 - (q/p)^(z-k)).

Examples

>>> from blockchainkit.consensus import attacker_success_probability
>>> round(attacker_success_probability(0.1, 5), 7)
0.0009137
Parameters:

  • attacker_fraction (float)

  • confirmations (int)

Return type:

float

Difficulty retargeting (Bitcoin 2009): hold the block interval steady as hashrate changes.

The whitepaper (section 4) says proof-of-work difficulty is set by a moving average targeting an average number of blocks per hour. Bitcoin’s first release recomputes the target every 2016 blocks, scaling it by the ratio of actual to expected time, clamped to a factor of four in either direction.

blockchainkit.consensus.systems.difficulty.retarget(target, actual_time, expected_time)[source]#

Return target * actual / expected, clamped to [target/4, 4*target].

A larger target is easier. Blocks that came too fast shrink it.

>>> from blockchainkit.consensus import retarget
>>> retarget(1000, actual_time=600, expected_time=1200)
500
Parameters:

  • target (int)

  • actual_time (int)

  • expected_time (int)

Return type:

int

blockchainkit.consensus.systems.difficulty.simulate_difficulty(hashrates, *, interval=600, window=2016, seed=0)[source]#

Simulate block discovery with exponential waiting times and periodic retargets.

With target T, a block needs about 2**48 / T hashes on average, so at hashrate h its waiting time is exponential with mean 2**48 / (T h).

Parameters:

  • hashrates (collections.abc.Sequence of float) – The network hashrate while each successive block is mined.

  • interval (int) – The target block time, in seconds.

  • window (int) – Blocks between retargets.

  • seed (int) – Seed for the waiting times.

Returns:

Each block’s waiting time and the target it was mined under.

Return type:

blockchainkit.consensus.core.base.DifficultyRun

Stake-weighted proposer sampling, not a complete PoS consensus protocol.

class blockchainkit.consensus.systems.pos.StakeSampler(stakes, *, seed=0)[source]#

Bases: object

Select proposers with exact integer weights and reproducible randomness.

Parameters:

  • stakes (collections.abc.Mapping) – Nonnegative weights with a positive total. Names are sorted so mapping insertion order does not alter results.

  • seed (int) – Simulation seed, not an unpredictable consensus randomness beacon.

Examples

>>> from blockchainkit.consensus import StakeSampler
>>> StakeSampler({"alice": 1, "bob": 0}, seed=7).sample(3)
('alice', 'alice', 'alice')
choose()[source]#

Select one validator with probability stake / total stake.

Return type:

str

sample(rounds)[source]#

Return proposers for a bounded number of rounds.

Parameters:

rounds (int)

Return type:

tuple[str, …]

GHOST fork choice (Sompolinsky and Zohar 2013): follow the heaviest subtree.

When blocks are frequent, many honest blocks end up off the longest chain, and that wasted work no longer protects it. GHOST (Greedy Heaviest Observed SubTree) walks from genesis and at each fork picks the child whose whole subtree carries the most work, counting the honest side branches too. Ethereum’s proof-of-work chain used a variant through uncle rewards.

blockchainkit.consensus.systems.fork_choice.subtree_work(chain, block_hash)[source]#

Return the expected work of a block and all its descendants.

Parameters:
Return type:

int

blockchainkit.consensus.systems.fork_choice.ghost_tip(chain)[source]#

Return the tip chosen by GHOST: descend into the heaviest subtree at every fork.

Ties go to the smaller hash, matching Blockchain.

Parameters:

chain (Blockchain)

Return type:

Block

Selfish mining (Eyal and Sirer 2014): majority is not enough.

A pool that withholds the blocks it finds, and publishes them only to overtake or tie the honest chain, wastes the honest miners’ work. Above a threshold hashrate its share of the chain exceeds its share of the hashrate, so honest miners gain by joining it. gamma is the fraction of honest miners who build on the pool’s block during a tie.

blockchainkit.consensus.systems.selfish.selfish_mining_revenue(alpha, gamma)[source]#

Return the selfish pool’s long-run share of blocks (Eyal and Sirer, eq. 8).

R = (alpha (1-alpha)**2 (4 alpha + gamma (1 - 2 alpha)) - alpha**3) / (1 - alpha (1 + (2 - alpha) alpha))

>>> from blockchainkit.consensus import selfish_mining_revenue
>>> round(selfish_mining_revenue(0.4, 0.0), 3)
0.484
Parameters:
Return type:

float

blockchainkit.consensus.systems.selfish.selfish_mining_threshold(gamma)[source]#

Return the hashrate above which selfish mining pays: (1 - gamma) / (3 - 2 gamma).

Parameters:

gamma (float)

Return type:

float

blockchainkit.consensus.systems.selfish.simulate_selfish_mining(alpha, gamma, *, blocks, seed=0)[source]#

Simulate the selfish-mining state machine (Eyal and Sirer, Algorithm 1).

Each event, the pool finds a block with probability alpha, otherwise the honest network does. The state is the pool’s private lead, plus a tie state after the pool publishes to match an honest block.

Parameters:
Return type:

SelfishMiningResult

The nothing-at-stake problem (Buterin 2014): voting on every fork is free.

A proof-of-work miner must split its hashrate between forks. A proof-of-stake validator can sign blocks on every fork at no cost, and collect the reward whichever fork wins. If everyone does, forks never resolve. The remedy, first proposed in Buterin’s Slasher, is a penalty: evidence of signing two conflicting blocks destroys the validator’s deposit.

blockchainkit.consensus.systems.stake_games.fork_voting_payoffs(fork_a_probability, reward, penalty)[source]#

Expected payoff of voting for fork A, fork B, or both.

Parameters:

  • fork_a_probability (float) – Chance that fork A becomes canonical.

  • reward (float) – Reward for having voted on the winning fork.

  • penalty (float) – Deposit destroyed when a validator is caught voting on both (slashing).

Returns:

Expected payoff of the strategies "A", "B" and "both".

Return type:

dict

Examples

>>> from blockchainkit.consensus import fork_voting_payoffs
>>> fork_voting_payoffs(0.5, 1.0, 0.0)
{'A': 0.5, 'B': 0.5, 'both': 1.0}

Cryptographic sortition (Algorand 2017): secret, stake-weighted committee selection.

Algorand picks each round’s committee by lottery. Every unit of stake is a ticket; a user hashes a round seed with their private key (in Algorand a verifiable random function, so others can check the result) and maps the hash to a number of selected tickets that is Binomial(stake, tau / W). Nobody, not even the user, knows who is on the committee before they speak, and splitting stake across accounts does not change the expected seats.

blockchainkit.consensus.systems.sortition.sortition(secret, stake, total_stake, expected, *, round_seed)[source]#

Return how many of a user’s stake units are selected this round.

The hash of secret || round_seed, read as a uniform number in [0, 1), is located in the cumulative Binomial(stake, expected / total_stake) distribution. Teaching simplification: a hash of the secret replaces the verifiable random function, so others cannot verify the draw.

Examples

>>> from blockchainkit.consensus import sortition
>>> sortition(b"my key", 0, 1000, 20, round_seed=b"r1")
0
Parameters:
Return type:

int

Casper the Friendly Finality Gadget (Buterin and Griffith 2017).

Validators with deposits vote for links between checkpoints, source -> target. A checkpoint becomes justified when two thirds of the stake vote for a link to it from a justified source, and its source becomes finalized when the target is the very next checkpoint. Two slashing conditions make conflicting finality cost at least a third of all stake: never cast two different votes for the same target height, and never cast a vote that surrounds another.

class blockchainkit.consensus.systems.finality.FinalityGadget(stakes)[source]#

Bases: object

Track Casper FFG votes, justification, finality, and slashable offenses.

Checkpoint 0 (genesis) starts justified and finalized.

Parameters:

stakes (collections.abc.Mapping) – Each validator’s deposit.

Examples

>>> from blockchainkit.consensus import FinalityGadget
>>> ffg = FinalityGadget({"a": 1, "b": 1, "c": 1})
>>> for v in "abc":
...     ffg.vote(v, source=0, target=1)
>>> sorted(ffg.justified)
[0, 1]
property justified: frozenset[int]#

Heights of justified checkpoints.

property finalized: frozenset[int]#

Heights of finalized checkpoints.

property slashable: tuple[Offense, ...]#

Every pair of votes that breaks a slashing condition, in detection order.

vote(validator, source, target, checkpoint=b'')[source]#

Record a vote for the link source -> target and update finality.

checkpoint distinguishes conflicting blocks at the same height.

Parameters:
Return type:

None

Plotting#

Plotting helpers for blockchainkit.consensus: mining effort and stake weighting.

blockchainkit.consensus.visualizers.plots.plot_mining_trials(difficulties, attempts, ax=None)[source]#

Compare measured hash attempts with the expected 2**difficulty.

Parameters:
Return type:

matplotlib.axes.Axes

blockchainkit.consensus.visualizers.plots.plot_stake_shares(stakes, proposers, ax=None)[source]#

Compare each validator’s stake fraction with its observed proposer fraction.

Parameters:
Return type:

matplotlib.axes.Axes