blockchainkit.network

blockchainkit.network hub · History · Examples · API reference

Peer-to-peer networks: topologies, logical time, dissemination, overlays, and block relay.

Peer graphs, logical clocks, gossip and reliable broadcast, replication under partitions, Kademlia and its attacks, block relay, forks, and transaction privacy.

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

Types and results

Event records and result containers for blockchainkit.network.

class blockchainkit.network.core.base.Delivery(time, sender, recipient, payload)

Bases: object

First receipt of a byte payload at a peer at integer simulation time.

Parameters:

• time (int)

• sender (str)

• recipient (str)

• payload (bytes)

time: int

sender: str

recipient: str

payload: bytes

class blockchainkit.network.core.base.RumorRun(informed, n)

Bases: object

How a rumor spread, round by synchronous round.

Variables:

• informed (tuple of int) – informed[r] peers knew the rumor after round r; informed[0] is 1, the source.

• n (int) – Number of peers.

Parameters:

• informed (tuple[int, ...])

• n (int)

informed: tuple[int, ...]

n: int

property rounds: int

Rounds played until the run stopped.

property complete: bool

True if every peer heard the rumor.

class blockchainkit.network.core.base.BroadcastResult(delivered, agreement, totality, messages)

Bases: object

Outcome of a Byzantine reliable-broadcast run.

Variables:

• delivered (dict) – Each correct process’s delivered value, or None if it delivered nothing.

• agreement (bool) – No two correct processes delivered different values.

• totality (bool) – Either every correct process delivered or none did.

• messages (int) – Messages sent by correct processes.

Parameters:

• delivered (dict[int, str | None])

• agreement (bool)

• totality (bool)

• messages (int)

delivered: dict[int, str | None]

agreement: bool

totality: bool

messages: int

class blockchainkit.network.core.base.Operation(kind, replica, value, ok)

Bases: object

One client request to a replicated register and its outcome.

Variables:

• kind (str) – "read" or "write".

• replica (int) – The replica the client contacted.

• value (str or None) – The value written, or the value read; None if the request failed.

• ok (bool) – False if the replica refused the request to stay consistent.

Parameters:

• kind (str)

• replica (int)

• value (str | None)

• ok (bool)

kind: str

replica: int

value: str | None

ok: bool

class blockchainkit.network.core.base.LookupResult(path)

Bases: object

Route of a Kademlia lookup.

Variables:

path (tuple of int) – Node identifiers visited, from the source to the node that answered.

Parameters:

path (tuple[int, ...])

path: tuple[int, ...]

property hops: int

Number of messages forwarded, one fewer than the nodes on the path.

property found: int

The node that answered, the closest to the target that the route reached.

class blockchainkit.network.core.base.RelayCost(messages, bytes, completion)

Bases: object

Traffic and time to relay one block from one source to every reachable peer.

Variables:

• messages (int) – Messages of any kind sent.

• bytes (int) – Total bytes sent.

• completion (int) – Time until the last peer has the block, in one-way link latencies.

Parameters:

• messages (int)

• bytes (int)

• completion (int)

messages: int

bytes: int

completion: int

class blockchainkit.network.core.base.CompactBlockResult(full_bytes, compact_bytes, missing, round_trips)

Bases: object

Bytes needed to relay one block in full and as a compact block (BIP 152).

Variables:

• full_bytes (int) – Header plus every transaction.

• compact_bytes (int) – Header, nonce, short IDs, and the transactions the receiver lacked.

• missing (int) – Transactions the receiver had to request: absent from its mempool, or ambiguous because their short ID collided.

• round_trips (int) – 1 if the mempool covered the block, 2 if a request was needed.

Parameters:

• full_bytes (int)

• compact_bytes (int)

• missing (int)

• round_trips (int)

full_bytes: int

compact_bytes: int

missing: int

round_trips: int

Constructions and protocols

Deterministic discrete-event gossip; no sockets, wall clock, or background threads.

class blockchainkit.network.systems.gossip.SimulatedNetwork(peers, *, seed=0, on_receive=None)

Bases: object

An undirected peer graph with seeded link delays and duplicate suppression.

Parameters:

• peers (collections.abc.Iterable of str) – Unique nonempty peer names. Initially no links exist.

• seed (int) – Private PRNG seed; construction does not modify global randomness.

• on_receive (collections.abc.Callable, optional) – Callback for each first delivery, including the originating peer. Return False to reject that payload at that peer and stop forwarding. Returning None or True accepts it. Rejections remain seen.

Notes

Disconnecting a link drops its in-flight messages. Reconnecting does not automatically synchronize old data: call broadcast again. Latency is sampled at send time, inclusive of both endpoints, and is at least one tick.

classmethod from_graph(graph, *, latency=(1, 1), seed=0, on_receive=None)

Build a network whose peers "0", "1", … are linked like graph.

>>> from blockchainkit.network import SimulatedNetwork, ring_lattice
>>> SimulatedNetwork.from_graph(ring_lattice(8, 2))
SimulatedNetwork(peers=8, links=8, time=0, pending=0)

Parameters:

• graph (Graph)

• latency (tuple[int, int])

• seed (int)

• on_receive (Callable[[Delivery], bool | None] | None)

Return type:

SimulatedNetwork

property time: int

Current simulated tick.

property deliveries: tuple[Delivery, ...]

Immutable snapshot of accepted first deliveries.

property messages_sent: int

Messages handed to links so far, including duplicates that receivers discard.

property pending: int

Number of queued events, including events invalidated by disconnection.

connect(left, right, *, latency=(1, 1))

Create or replace a link with inclusive integer latency bounds.

Parameters:

• left (str)

• right (str)

• latency (tuple[int, int])

Return type:

None

disconnect(left, right)

Remove a link, invalidating all in-flight events sent on that link.

Parameters:

• left (str)

• right (str)

Return type:

None

broadcast(sender, payload)

Originate or retransmit bytes to neighbors; receivers suppress duplicates.

Parameters:

• sender (str)

• payload (bytes)

Return type:

None

run(*, until=None, max_events=100000)

Process queued events up to a time/event bound; return events processed.

With until set, the clock advances to that tick if the event budget was not exhausted. Events after until remain queued for a later run.

Parameters:

• until (int | None)

• max_events (int)

Return type:

int

Peer graphs: random (Erdős–Rényi 1959), small-world (Watts–Strogatz 1998), and scale-free (Barabási–Albert 1999).

Who is connected to whom decides how fast news spreads, how many links an attacker must cut, and how much a single peer can see. These generators build the three classic families so experiments can compare them on equal terms.

class blockchainkit.network.systems.topology.Graph(n, edges)

Bases: object

An immutable undirected simple graph on the nodes 0, 1, ..., n - 1.

Parameters:

• n (int) – Number of nodes, at least 1.

• edges (collections.abc.Iterable of tuple of int) – Unordered pairs of distinct nodes; duplicates are merged.

Examples

>>> from blockchainkit.network import Graph
>>> path = Graph(3, [(0, 1), (1, 2)])
>>> path.distances(0)
(0, 1, 2)
>>> path.is_connected()
True

property n: int

Number of nodes.

property edges: tuple[tuple[int, int], ...]

Every edge once, as (smaller, larger), in sorted order.

neighbors(node)

Sorted neighbors of node.

Parameters:

node (int)

Return type:

tuple[int, …]

degrees()

Number of neighbors of every node, indexed by node.

Return type:

tuple[int, …]

distances(source)

Hop counts from source by breadth-first search; None if unreachable.

Parameters:

source (int)

Return type:

tuple[int | None, …]

components()

Connected components, largest first (ties by smallest node).

Return type:

tuple[frozenset[int], …]

is_connected()

True if every node can reach every other node.

Return type:

bool

average_path_length()

Mean hop count over all ordered pairs of distinct, mutually reachable nodes.

This is the L of Watts and Strogatz. A graph with no such pair (a single node, or no edges) has length 0.

Return type:

float

clustering()

Average local clustering coefficient: the C of Watts and Strogatz.

A node’s coefficient is the fraction of pairs of its neighbors that are themselves linked (“my friends know each other”). Nodes with fewer than two neighbors contribute 0.

Return type:

float

blockchainkit.network.systems.topology.complete_graph(n)

Every pair of the n nodes linked: the setting of classic rumor-spreading results.

>>> from blockchainkit.network import complete_graph
>>> len(complete_graph(5).edges)
10

Parameters:

n (int)

Return type:

Graph

blockchainkit.network.systems.topology.erdos_renyi(n, p, *, seed=0)

Random graph G(n, p): each of the n(n-1)/2 possible links exists with probability p.

Erdős and Rényi showed that connectivity appears abruptly: for large n, G(n, p) is almost surely disconnected when p < (1 - e) ln n / n and almost surely connected when p > (1 + e) ln n / n.

>>> from blockchainkit.network import erdos_renyi
>>> erdos_renyi(30, 1.0).is_connected()
True

Parameters:

• n (int)

• p (float)

• seed (int)

Return type:

Graph

blockchainkit.network.systems.topology.ring_lattice(n, k)

Ring where each node links to its k nearest nodes, k / 2 on each side.

>>> from blockchainkit.network import ring_lattice
>>> ring_lattice(6, 2).neighbors(0)
(1, 5)

Parameters:

• n (int)

• k (int)

Return type:

Graph

blockchainkit.network.systems.topology.watts_strogatz(n, k, beta, *, seed=0)

Small-world graph: rewire each ring-lattice edge with probability beta.

Following Watts and Strogatz, each edge (u, u + j) of ring_lattice() keeps its endpoint u and, with probability beta, moves its other end to a uniformly random node, avoiding self-loops and duplicate links. A few shortcuts (small beta) shrink the average path length almost to that of a random graph while the clustering stays close to the lattice’s.

>>> from blockchainkit.network import watts_strogatz
>>> len(watts_strogatz(20, 4, 0.3, seed=1).edges)
40

Parameters:

• n (int)

• k (int)

• beta (float)

• seed (int)

Return type:

Graph

blockchainkit.network.systems.topology.barabasi_albert(n, m, *, seed=0)

Scale-free graph by preferential attachment.

Start from m + 1 fully linked nodes. Each new node links to m distinct existing nodes, chosen with probability proportional to their current degree (“the rich get richer”). The degree distribution approaches the power law P(k) ~ k^-3: a few hubs, many small nodes.

>>> from blockchainkit.network import barabasi_albert
>>> g = barabasi_albert(50, 2, seed=3)
>>> len(g.edges) == 3 + 2 * (50 - 3)
True

Parameters:

• n (int)

• m (int)

• seed (int)

Return type:

Graph

Logical clocks: Lamport timestamps (1978) and vector clocks (Fidge, Mattern 1988).

Peers have no shared clock, so “which happened first?” has no physical answer. Lamport defined happened before from the messages themselves: an event precedes later events at the same process, a send precedes its receive, and the relation is transitive. Two events related neither way are concurrent.

A history is a sequence of processes, each a sequence of events. An event is a pair (kind, label): ("local", name), ("send", message) or ("receive", message). Each message label is sent once and received at most once.

blockchainkit.network.systems.clocks.Event

(kind, label) with kind "local", "send" or "receive".

alias of tuple[str, str]

blockchainkit.network.systems.clocks.lamport_timestamps(processes)

Assign Lamport clock values to every event.

Each process keeps a counter. It increments the counter before each event, attaches it to every message it sends, and on receipt jumps to max(own, received) + 1. The result satisfies the clock condition: if a happened before b, then C(a) < C(b). The converse does not hold.

Returns:

result[p][i] is the timestamp of event i at process p.

Return type:

tuple of tuple of int

Parameters:

processes (Sequence[Sequence[tuple[str, str]]])

Examples

>>> from blockchainkit.network import lamport_timestamps
>>> lamport_timestamps([[("send", "m")], [("local", "x"), ("local", "y"), ("receive", "m")]])
((1,), (1, 2, 3))

blockchainkit.network.systems.clocks.vector_timestamps(processes)

Assign vector clock values to every event.

Each process p keeps one counter per process. It increments entry p before each event and, on receipt, first takes the entrywise maximum with the vector carried by the message. Entry q of an event’s vector counts the events at q that happened before or at it, so vectors characterize causality exactly: see happened_before().

Examples

>>> from blockchainkit.network import vector_timestamps
>>> vector_timestamps([[("send", "m")], [("local", "x"), ("receive", "m")]])
(((1, 0),), ((0, 1), (1, 2)))

Parameters:

processes (Sequence[Sequence[tuple[str, str]]])

Return type:

tuple[tuple[tuple[int, …], …], …]

blockchainkit.network.systems.clocks.happened_before(a, b)

True if the event stamped a happened before the event stamped b.

For vector timestamps, a -> b exactly when a <= b entrywise and a != b.

>>> from blockchainkit.network import happened_before
>>> happened_before((1, 0), (1, 2)), happened_before((1, 0), (0, 1))
(True, False)

Parameters:

• a (Sequence[int])

• b (Sequence[int])

Return type:

bool

blockchainkit.network.systems.clocks.concurrent(a, b)

True if neither vector-stamped event happened before the other (and they differ).

>>> from blockchainkit.network import concurrent
>>> concurrent((1, 0), (0, 1))
True

Parameters:

• a (Sequence[int])

• b (Sequence[int])

Return type:

bool

Epidemic dissemination: push, pull and push-pull rumor spreading.

Each round, every peer calls one neighbor chosen uniformly at random. In push, informed callers tell the callee; in pull, uninformed callers ask the callee and learn the rumor if it knows it; push-pull does both. Demers et al. (1987) compared these for replicated databases. On the complete graph, push alone informs everyone in about log2 n + ln n rounds (Frieze and Grimmett 1985, Pittel 1987).

blockchainkit.network.systems.epidemics.MODES = ('push', 'pull', 'push-pull')

The supported exchange modes.

Type:

tuple of str

blockchainkit.network.systems.epidemics.pittel_rounds(n)

Rounds push gossip needs on the complete graph: log2 n + ln n, up to O(1).

The log2 n term is the doubling phase, while few peers know the rumor; the ln n term is the coupon-collector tail, while the last uninformed peers wait to be called.

>>> from blockchainkit.network import pittel_rounds
>>> round(pittel_rounds(1024), 2)
16.93

Parameters:

n (int)

Return type:

float

blockchainkit.network.systems.epidemics.spread_rumor(network, *, mode='push', source=0, seed=0, max_rounds=10000)

Simulate synchronous random-call rumor spreading.

Parameters:

• network (blockchainkit.network.systems.topology.Graph or int) – The peer graph, or an integer n for the complete graph on n peers (simulated without building its n(n-1)/2 edges).

• mode ({"push", "pull", "push-pull"}) – Who learns from each call; see the module docstring.

• source (int) – The peer that knows the rumor at round 0.

• seed (int) – Seed for the random calls.

• max_rounds (int) – Stop after this many rounds even if peers remain uninformed.

Returns:

Informed counts per round. The run also stops once every peer that the source can reach is informed.

Return type:

blockchainkit.network.core.base.RumorRun

Examples

>>> from blockchainkit.network import spread_rumor
>>> run = spread_rumor(1000, seed=1)
>>> run.complete, run.informed[:4]
(True, (1, 2, 4, 8))

Byzantine reliable broadcast (Bracha 1987).

A sender wants every correct process to deliver the same value, even if the sender lies by telling different processes different things. Bracha’s protocol adds two all-to-all phases on top of the sender’s message:

1. Echo. On the sender’s value, a process tells everyone “I got v”.

2. Ready. On ceil((n + t + 1) / 2) echoes of v, or t + 1 readies of v (amplification), a process tells everyone “ready for v”, once.

3. Deliver. On 2t + 1 readies of v, a process delivers v.

Any two echo quorums overlap in a correct process, which echoes only once, so correct processes never become ready for different values. Amplification makes delivery all-or-nothing. Both arguments need n > 3t.

blockchainkit.network.systems.broadcast.SENDER = 0

The broadcasting process.

Type:

int

blockchainkit.network.systems.broadcast.reliable_broadcast(n, faulty, proposals, *, tolerance=None)

Run Bracha’s broadcast in synchronous rounds from process 0.

Parameters:

• n (int) – Number of processes, at least 2.

• faulty (collections.abc.Iterable of int) – Byzantine processes. A faulty sender sends proposals[r] to each process r. Faulty processes collude with that split: to each correct process r they echo and ready proposals[r], the strongest support they can give to a disagreement.

• proposals (collections.abc.Sequence of str) – One value per process; entries at faulty processes are ignored. If the sender is correct, all correct entries must equal proposals[0].

• tolerance (int, optional) – The t used in the thresholds; defaults to (n - 1) // 3, the most the protocol can tolerate. Running with more faulty processes than tolerance shows the bound is needed.

Return type:

blockchainkit.network.core.base.BroadcastResult

Examples

>>> from blockchainkit.network import reliable_broadcast
>>> result = reliable_broadcast(4, {0}, ["a", "a", "b", "b"])
>>> result.agreement, result.totality, sorted(set(result.delivered.values()))
(True, True, ['b'])

The CAP trade-off (Brewer 2000; Gilbert and Lynch 2002) on a replicated register.

A register is copied on several replicas. When the network partitions them, a replica that cannot reach the others must choose: answer from what it knows (stay available, risking stale reads and lost writes) or refuse (stay consistent). Gilbert and Lynch proved no system can guarantee both during a partition. A blockchain makes the same choice: Bitcoin keeps producing blocks on both sides of a split and reconciles later.

blockchainkit.network.systems.replication.MODES = ('consistent', 'available')

The two policies a replica can follow during a partition.

Type:

tuple of str

class blockchainkit.network.systems.replication.ReplicatedRegister(replicas, *, mode='consistent', initial='')

Bases: object

A string register replicated on replicas nodes that can be partitioned.

Parameters:

• replicas (int) – Number of replicas, at least 1; they are numbered from 0.

• mode ({"consistent", "available"}) – "consistent": a request succeeds only if the contacted replica reaches a strict majority, and it then writes to or reads from every reachable replica. Any two majorities overlap, so a read sees the latest successful write. "available": every request succeeds using the replicas the contacted one can reach.

• initial (str) – The value every replica starts with.

Notes

Every value carries a version (counter, replica); a write’s counter is one more than the highest it can see. heal() reconnects all replicas and keeps the highest version (last writer wins), so in available mode a write made on the losing side of a partition is lost.

Examples

>>> from blockchainkit.network import ReplicatedRegister
>>> register = ReplicatedRegister(3, mode="consistent")
>>> register.partition([0], [1, 2])
>>> register.write(0, "x").ok, register.write(1, "y").ok
(False, True)

property history: tuple[Operation, ...]

Every request so far, in order.

values()

The value each replica currently holds, indexed by replica.

Return type:

tuple[str, …]

partition(*groups)

Split the replicas into groups that can talk only within themselves.

The groups must cover every replica exactly once.

Parameters:

groups (Iterable[int])

Return type:

None

heal()

Reconnect every replica and converge on the highest version.

Return type:

None

write(replica, value)

Ask replica to store value; return the recorded operation.

Parameters:

• replica (int)

• value (str)

Return type:

Operation

read(replica)

Ask replica for the value; return the recorded operation.

Parameters:

replica (int)

Return type:

Operation

Kademlia routing by XOR distance (Maymounkov and Mazières 2002).

Every node has a bits-bit identifier, and the distance between two identifiers is their bitwise XOR read as an integer. A node sorts the nodes it knows into k-buckets: bucket i holds up to k nodes whose distance lies in [2**i, 2**(i+1)), the nodes whose identifier first differs from its own at bit i. Knowing a few nodes at every scale lets a lookup halve the remaining distance at each hop, so it takes about log2 n hops among n nodes.

blockchainkit.network.systems.kademlia.xor_distance(a, b)

Kademlia’s distance: a XOR b. It is symmetric and zero only for a == b.

>>> from blockchainkit.network import xor_distance
>>> xor_distance(0b1010, 0b0110)
12

Parameters:

• a (int)

• b (int)

Return type:

int

blockchainkit.network.systems.kademlia.node_id(key, bits)

Derive a bits-bit identifier from a public key: the top bits of its SHA-256.

Assigning identifiers by hash means a node cannot simply pick a position in the identifier space; it has to search for keys. See the Sybil experiment.

>>> from blockchainkit.network import node_id
>>> node_id(b"alice", 8) < 2**8
True

Parameters:

• key (bytes)

• bits (int)

Return type:

int

class blockchainkit.network.systems.kademlia.KademliaNetwork(ids, *, bits, k=8, seed=0)

Bases: object

Nodes with idealized k-bucket routing tables.

Parameters:

• ids (collections.abc.Iterable of int) – Distinct node identifiers in [0, 2**bits).

• bits (int) – Identifier length.

• k (int) – Bucket capacity. Each bucket is filled with up to k nodes drawn uniformly from all nodes at that distance scale.

• seed (int) – Seed for filling the buckets.

Notes

Real Kademlia nodes fill their buckets gradually from the traffic they see and prefer long-lived contacts. Here every table is filled at once from global knowledge, which isolates the routing geometry.

Examples

>>> from blockchainkit.network import KademliaNetwork
>>> net = KademliaNetwork([0b000, 0b011, 0b100, 0b110], bits=3, k=1)
>>> net.lookup(0b000, 0b111).path
(0, 6)

property ids: tuple[int, ...]

Node identifiers in increasing order.

buckets(node)

The k-buckets of node; bucket i holds contacts at distance [2**i, 2**(i+1)).

Parameters:

node (int)

Return type:

tuple[tuple[int, …], …]

closest(target, count)

The count nodes closest to target by XOR distance (global truth).

In Kademlia these nodes store the value with key target.

Parameters:

• target (int)

• count (int)

Return type:

tuple[int, …]

lookup(source, target)

Route greedily from source toward target.

At each hop the current node forwards to the contact in its buckets closest to target, while that is closer than itself. If the current node differs at bit i from the true closest node, its bucket i is nonempty and every contact there is closer to the target, so the route always ends at the closest node.

Parameters:

• source (int)

• target (int)

Return type:

LookupResult

Eclipse attacks on peer selection (Heilman, Kendler, Zohar and Goldberg 2015).

A node picks its outbound connections at random from a table of addresses it has heard of. An attacker who fills that table with its own addresses can make every connection land on an attacker: the node is eclipsed, and sees only the blocks and transactions the attacker chooses to show it.

Bitcoin’s defense, strengthened after the 2015 paper, is bucketing: an address goes to a bucket determined by a secret hash of its network group (its /16 IP prefix), and each group can reach only a few buckets. An attacker with many addresses but few groups can then fill only a small part of the table, however many addresses it sends.

blockchainkit.network.systems.addresses.eclipse_probability(attacker_fraction, outbound)

Chance that all outbound connections land on attackers: f ** outbound.

Each connection is modeled as an independent draw from a table in which a fraction f of the entries belong to the attacker.

>>> from blockchainkit.network import eclipse_probability
>>> eclipse_probability(0.5, 8)
0.00390625

Parameters:

• attacker_fraction (float)

• outbound (int)

Return type:

float

class blockchainkit.network.systems.addresses.AddressManager(*, buckets=64, bucket_size=16, buckets_per_group=None, seed=0)

Bases: object

A node’s table of known peer addresses, with optional group bucketing.

Parameters:

• buckets (int) – Number of buckets.

• bucket_size (int) – Capacity of each bucket. Adding to a full bucket evicts a random entry, so a flood of new addresses pushes old ones out.

• buckets_per_group (int, optional) – If given, each network group can place addresses in only this many buckets (Bitcoin’s defense). If omitted, an address may land in any bucket.

• seed (int) – Seeds both the node’s secret bucketing key and its random choices.

Examples

>>> from blockchainkit.network import AddressManager
>>> table = AddressManager(buckets=4, bucket_size=2, seed=1)
>>> table.add("10.0.0.1", "10.0")
>>> table.addresses
('10.0.0.1',)

bucket_of(address, group)

The bucket an address is stored in, derived from the node’s secret key.

Parameters:

• address (str)

• group (str)

Return type:

int

add(address, group)

Store an address heard from the network, evicting a random entry if needed.

Parameters:

• address (str)

• group (str)

Return type:

None

property addresses: tuple[str, ...]

Every stored address, bucket by bucket.

select(count)

Choose count distinct addresses: each time a random nonempty bucket, then an entry.

Picking a bucket first, as Bitcoin does, means an attacker confined to a few buckets is picked rarely even if those buckets are full.

Parameters:

count (int)

Return type:

tuple[str, …]

Block relay: flooding, inv/getdata announcements (Bitcoin 2009), compact blocks (BIP 152, 2016).

Flooding sends the full block over every link. Bitcoin’s original protocol instead announces the block’s hash with an inv message and sends the block only to peers that ask with getdata, so each peer downloads it once, at the price of a round trip per hop. Compact blocks go further: most transactions are already in the receiver’s mempool, so the sender lists short transaction IDs and the receiver rebuilds the block locally.

blockchainkit.network.systems.relay.HEADER_SIZE = 80

Bytes in a block header.

Type:

int

blockchainkit.network.systems.relay.ANNOUNCE_SIZE = 61

Bytes in an inv or getdata for one item: a 24-byte message header, a one-byte count, and a 36-byte inventory vector.

Type:

int

blockchainkit.network.systems.relay.MODES = ('flood', 'announce')

The relay strategies compared by relay_cost().

Type:

tuple of str

blockchainkit.network.systems.relay.relay_cost(graph, *, size, mode='flood', source=0)

Count the traffic to relay a size-byte block from source to its component.

Every peer, on first receiving the block, passes it on to each neighbor except the one it came from, so 2E - (n - 1) messages cross the links of a connected graph with E edges and n peers.

• "flood": each such message carries the whole block, and the block reaches a peer at distance d after d link latencies.

• "announce": each such message is an inv; a peer that lacks the block answers its first inv with a getdata and receives the block. Every peer downloads the block once, but each hop costs three latencies.

Examples

>>> from blockchainkit.network import complete_graph, relay_cost
>>> relay_cost(complete_graph(10), size=1_000_000).bytes
81000000

Parameters:

• graph (Graph)

• size (int)

• mode (str)

• source (int)

Return type:

RelayCost

blockchainkit.network.systems.relay.short_id(transaction, nonce, size=6)

A size-byte transaction ID salted by the block’s nonce.

Salting with a per-block nonce stops an attacker from crafting transactions whose short IDs collide in every block. BIP 152 uses SipHash keyed by the header and nonce; this teaching version uses SHA-256.

>>> from blockchainkit.network import short_id
>>> len(short_id(b"tx", nonce=7))
6

Parameters:

• transaction (bytes)

• nonce (int)

• size (int)

Return type:

bytes

blockchainkit.network.systems.relay.compact_block_relay(block, mempool, *, nonce=0, short_id_size=6)

Compare sending block in full with sending it as a compact block.

The compact form costs the header, an 8-byte nonce, and one short ID per transaction. The receiver matches short IDs against its mempool. A transaction with no match, or with an ambiguous or wrong match, must be requested in a second round trip: a request of ANNOUNCE_SIZE bytes plus 2 bytes per index, then the transactions themselves.

Examples

>>> from blockchainkit.network import compact_block_relay
>>> block = [bytes([i]) * 250 for i in range(100)]
>>> result = compact_block_relay(block, block[:90])
>>> result.missing, result.round_trips, result.full_bytes
(10, 2, 25080)

Parameters:

• block (Sequence[bytes])

• mempool (Iterable[bytes])

• nonce (int)

• short_id_size (int)

Return type:

CompactBlockResult

Propagation delay and forks (Decker and Wattenhofer 2013).

A block takes time to reach the other miners. Until it arrives, they keep mining on the old tip, and if one of them finds a block in that window the chain forks. Block discovery is a Poisson process, so with propagation delay tau and mean block interval T the chance that a block is followed by a competitor within tau is 1 - exp(-tau / T). Shorter intervals or slower relay mean more forks, wasted work, and an easier time for attackers.

blockchainkit.network.systems.propagation.fork_rate(delay, interval)

Probability that a competing block appears before a block has propagated.

Parameters:

• delay (float) – Time for a block to reach the other miners.

• interval (float) – Mean time between blocks, in the same unit.

Return type:

float

Examples

>>> from blockchainkit.network import fork_rate
>>> round(fork_rate(12.6, 600), 4)
0.0208

blockchainkit.network.systems.propagation.simulate_fork_rate(delay, interval, *, blocks=10000, seed=0)

Measure the fork rate on a simulated chain of Poisson block discoveries.

Draws exponential gaps with mean interval between successive blocks and counts the blocks whose successor was found less than delay later, when its miner could not yet have seen them.

>>> from blockchainkit.network import simulate_fork_rate
>>> simulate_fork_rate(0.0, 600, blocks=100)
0.0

Parameters:

• delay (float)

• interval (float)

• blocks (int)

• seed (int)

Return type:

float

Transaction-origin privacy: diffusion versus Dandelion (Bojja Venkatakrishnan, Fanti and Viswanath 2017).

When a peer broadcasts its transaction, it is usually the first to send it. Spy peers that connect widely record who first sent them each transaction and guess that peer is the origin: the first-spy estimator. Dandelion first passes the transaction along a random path (the stem), each hop continuing with probability q, and only then diffuses it. The spies then see the end of the stem, far from the origin.

blockchainkit.network.systems.privacy.MODES = ('diffusion', 'dandelion')

The broadcast strategies compared by first_spy_precision().

Type:

tuple of str

blockchainkit.network.systems.privacy.first_spy_precision(graph, spies, *, mode='diffusion', trials=200, stem_probability=0.9, seed=0)

Fraction of broadcasts whose origin the first-spy estimator identifies.

Each trial picks an honest origin uniformly at random.

• "diffusion": the origin sends to all neighbors, and each peer forwards on first receipt, with independent Exp(1) delay per message.

• "dandelion": the transaction first walks to a random neighbor; after each hop it continues the stem with probability stem_probability and otherwise diffuses from where it is. A spy on the stem guesses the peer that handed it the transaction.

The original Dandelion routes stems over a dedicated line-shaped anonymity graph; here the stem is a random walk on graph itself.

Examples

>>> from blockchainkit.network import complete_graph, first_spy_precision
>>> first_spy_precision(complete_graph(2), {1}, trials=10)
1.0

Parameters:

• graph (Graph)

• spies (Iterable[int])

• mode (str)

• trials (int)

• stem_probability (float)

• seed (int)

Return type:

float

Plotting

Plotting helpers for blockchainkit.network: graphs, space-time diagrams, and spreading.

blockchainkit.network.visualizers.plots.plot_gossip_timeline(deliveries, *, payload=None, ax=None)

Show when each peer first accepted a payload, earliest at the top.

Parameters:

• deliveries (collections.abc.Sequence of blockchainkit.network.core.base.Delivery) – Usually SimulatedNetwork.deliveries.

• payload (bytes, optional) – Payload to plot; required when deliveries contain several payloads.

• ax (matplotlib.axes.Axes, optional) – Axes to draw on; a new figure is created if omitted.

Return type:

matplotlib.axes.Axes

blockchainkit.network.visualizers.plots.plot_graph(graph, *, highlight=(), ax=None)

Draw a peer graph with its nodes on a circle.

A circle shows the structure of ring lattices and small worlds directly: lattice links hug the rim and rewired shortcuts cut across it.

Parameters:

• graph (blockchainkit.network.systems.topology.Graph) – The graph to draw.

• highlight (collections.abc.Iterable of int) – Nodes to draw in a contrasting color, such as spies or hubs.

• ax (matplotlib.axes.Axes, optional) – Axes to draw on; a new figure is created if omitted.

Return type:

matplotlib.axes.Axes

blockchainkit.network.visualizers.plots.plot_rumor_spread(runs, *, ax=None)

Plot the fraction of peers still uninformed after each round, on a log scale.

On a log scale, push’s slow final phase shows as a straight line (the residue shrinks by a constant factor per round), while pull’s accelerating fall shows the residue squaring each round.

Parameters:

• runs (collections.abc.Mapping of str to blockchainkit.network.core.base.RumorRun) – Runs to compare, keyed by their legend label.

• ax (matplotlib.axes.Axes, optional) – Axes to draw on; a new figure is created if omitted.

Return type:

matplotlib.axes.Axes

blockchainkit.network.visualizers.plots.plot_space_time(processes, *, ax=None)

Draw Lamport’s space-time diagram, labeling each event with its Lamport clock.

Each process is a horizontal line, time runs left to right, and each message is an arrow from its send to its receive. An event is placed at its Lamport timestamp, so every arrow points forward in time.

Parameters:

• processes (collections.abc.Sequence of collections.abc.Sequence of Event) – A history as accepted by lamport_timestamps().

• ax (matplotlib.axes.Axes, optional) – Axes to draw on; a new figure is created if omitted.

Return type:

matplotlib.axes.Axes