Blockchain systems rely on cryptographic primitives to ensure security, authenticity, and verifiability. These primitives are modeled as idealized functions with well-defined security properties.
A digital signature scheme is a tuple of probabilistic polynomial-time (PPT) algorithms: \[ \mathcal{S} = (\mathsf{KeyGen}, \mathsf{Sign}, \mathsf{Verify}) \] where: - \(\mathsf{KeyGen}(1^\lambda) \to (sk, pk)\): Generates a secret key \(sk\) and public key \(pk\) for security parameter \(\lambda\). - \(\mathsf{Sign}(sk, m) \to \sigma\): Produces a signature \(\sigma\) for message \(m\). - \(\mathsf{Verify}(pk, m, \sigma) \to \{0,1\}\): Returns \(1\) if \(\sigma\) is valid for \(m\) under \(pk\).
Security Property (EUF-CMA): An adversary, given access to a signing oracle, cannot produce a valid signature \(\sigma^*\) on a message \(m^*\) that was not previously signed, except with negligible probability.
Intuition: Signatures ensure that transactions and blocks are authored by legitimate participants. In blockchain systems, they prevent forgery and enable non-repudiation.
A cryptographic hash function is a function: \[ \mathcal{H}: \{0,1\}^* \to \{0,1\}^\lambda \] modeled as a random oracle (an idealized function that outputs uniformly random values for new inputs).
Security Properties: 1. Collision Resistance: It is computationally infeasible to find \(x \neq y\) such that \(\mathcal{H}(x) = \mathcal{H}(y)\). 2. Pre-image Resistance: Given \(y = \mathcal{H}(x)\), it is computationally infeasible to recover \(x\). 3. Second Pre-image Resistance: Given \(x\), it is computationally infeasible to find \(x' \neq x\) such that \(\mathcal{H}(x) = \mathcal{H}(x')\).
Intuition: Hash functions are used to: - Commit to data (e.g., Merkle roots for state commitments). - Link blocks in a chain (via block hashes). - Generate pseudorandom values (e.g., for leader election).
A VDF is a triple of algorithms: \[ \mathcal{VDF} = (\mathsf{Setup}, \mathsf{Eval}, \mathsf{Verify}) \] where: - \(\mathsf{Setup}(1^\lambda, \Delta) \to pp\): Generates public parameters \(pp\) for a delay parameter \(\Delta\). - \(\mathsf{Eval}(pp, x) \to (y, \pi)\): Computes output \(y\) and proof \(\pi\) after \(\Delta\) sequential steps. - \(\mathsf{Verify}(pp, x, y, \pi) \to \{0,1\}\): Verifies \(y\) in \(O(\log \Delta)\) time.
Intuition: VDFs introduce sequential computation that cannot be parallelized, ensuring that: - Block production requires real time (e.g., in Solana’s Proof-of-History). - Adversaries cannot speed up computation via parallelism.
This layer defines the logical state, the programs residing within it, and the generic “Events” that trigger state evolution.
The state space \(\Sigma\) is defined as a tuple comprising data storage and program logic: \[ \Sigma = (\mathcal{D}, \Omega) \] Where: - \(\mathcal{D}: \mathcal{A} \to \mathbb{N}\) is the Data Layer (e.g., mapping addresses to balances/UTXOs). - \(\Omega: \mathcal{A} \to \{0,1\}^*\) is the Program Space (Smart Contracts). \(\Omega(a)\) stores the immutable bytecode at address \(a\). - The genesis state \(\sigma_0 = (\mathcal{D}_0, \emptyset)\) initializes the data and contains no deployed programs.
An Event \(\epsilon\) is the atomic unit of state transition. It generalizes the concept of a transaction to include simple transfers, smart contract deployments, and contract executions. \[ \epsilon = (\mathsf{type}, \mathsf{payload}, \pi_{\mathsf{auth}}) \] Where: - \(\mathsf{type} \in \{ \mathsf{Transfer}, \mathsf{Deploy}, \mathsf{Invoke} \}\): Discriminator defining the event’s nature. - \(\mathsf{payload}\): The data payload, structure varies by type: - If \(\mathsf{type} = \mathsf{Transfer}\): Contains sender, recipient, value. - If \(\mathsf{type} = \mathsf{Deploy}\): Contains sender, init-code (bytecode to store). - If \(\mathsf{type} = \mathsf{Invoke}\): Contains sender, target address \(a\), function selector, and input arguments. - \(\pi_{\mathsf{auth}}\): Authentication proof (e.g., digital signature) authorizing the event.
Validity Predicate: \[ \mathcal{V}: \Sigma \times \mathcal{E} \to \{0,1\} \] \(\mathcal{V}(\sigma, \epsilon) = 1\) if the signature is valid and the sender has sufficient resources (gas/balance).
The state transition function \(\delta\) updates the state based on the event type. It is a partial function: \[ \delta: \Sigma \times \mathcal{E} \to \Sigma \cup \{\bot\} \] The transition logic is defined by cases on \(\mathsf{type}\):
Simple Transfer: \[ \delta(\sigma, \epsilon) = \sigma' \text{ where } \mathcal{D}' = \mathcal{D} \text{ updated with value transfer} \]
Smart Contract Deployment (\(\mathsf{Deploy}\)): \[ \delta(\sigma, \epsilon) = \sigma' \text{ where } \Omega'(a_{\mathsf{new}}) = \mathsf{init\_code} \] This event adds new logic to the state.
Smart Contract Execution (\(\mathsf{Invoke}\)): \[ \delta(\sigma, \epsilon) = \text{Execute}(\sigma, \Omega(a_{\mathsf{target}}), \mathsf{payload}) \] This loads the bytecode from \(\Omega\) at the target address and executes it. The execution may read/write \(\mathcal{D}\) and is bounded by a resource limit (Gas) \(\Gamma\): \[ \text{If } \Gamma_{\mathsf{consumed}} > \Gamma_{\mathsf{limit}} \implies \text{Revert}(\sigma) \]
Intuition: In traditional blockchains, transactions are simple database updates. In smart contract platforms, an Event triggers the execution of the Program stored in the state, allowing the state to mutate itself autonomously based on predefined logic.
A state commitment remains a succinct cryptographic binding to the entire state: \[ \mathcal{M}: \Sigma \to \{0,1\}^\lambda \] Note: For Ethereum, \(\mathcal{M}(\sigma)\) is the State Root, which commits to both the account balances (\(\mathcal{D}\)) and the contract storage/code (\(\Omega\)) via a Modified Merkle Patricia Trie.
This layer defines how time is measured in a decentralized system, where nodes may have differing local clocks.
An epoch is a discrete time interval during which a subset of validators is authorized to propose blocks. The sequence of epochs is totally ordered: \[ \varepsilon_0, \varepsilon_1, \varepsilon_2, \dots \] where: - Each epoch \(\varepsilon_i\) has duration \(\delta_i \in \mathbb{R}^+\). - \(\delta_i\) may be fixed (e.g., 12s in Ethereum) or adaptive (e.g., Bitcoin’s difficulty adjustment).
Intuition: Epochs provide a synchronization mechanism for validators, ensuring that: - Only one validator proposes a block per epoch (in leader-based protocols). - Validators agree on the order of blocks.
The temporal authority oracle \(\mathcal{O}\) determines which validator is authorized to propose a block in epoch \(i\): \[ \mathcal{O}: \mathbb{N} \times \mathcal{V} \times \Theta \times \Sigma \to \{0,1\} \] where: - \(\mathcal{V}\) is the set of validators. - \(\Theta\) represents temporal parameters (e.g., RANDAO seed, VRF output). - \(\Sigma\) is the current state (e.g., stake distribution).
Output: \[ \mathcal{O}(i, v, \theta_i, \sigma_i) = 1 \iff v \text{ is authorized to propose in epoch } i. \]
Examples: 1. Proof-of-Work (Bitcoin): - \(\mathcal{O}(i, v, \theta_i, \sigma_i) = 1\) if \(v\) finds a nonce \(n\) such that \(\mathcal{H}(B_{i-1} \| n) < D\), where \(D\) is the difficulty target. 2. Proof-of-Stake (Ethereum): - \(\mathcal{O}(i, v, \theta_i, \sigma_i) = 1\) if \(v\) is selected via RANDAO + VRF based on stake. 3. Proof-of-History (Solana): - \(\mathcal{O}(i, v, \theta_i, \sigma_i) = 1\) if \(v\) is the next validator in a VDF-generated sequence.
The epoch transition function \(\Psi\) dynamically adjusts the epoch duration based on network conditions: \[ \delta_{i+1} = \Psi(\sigma_i, \gamma_i, \delta_{\mathsf{base}}) \] where: - \(\sigma_i\) is the state at the end of epoch \(i\). - \(\gamma_i \in \Gamma\) represents network observations (e.g., block propagation time, congestion metrics). - \(\delta_{\mathsf{base}}\) is a baseline duration (e.g., 12s in Ethereum).
Examples: 1. Bitcoin: - \(\Psi\) adjusts \(\delta_{\mathsf{base}}\) every 2016 blocks to target a 10-minute block time. - \(\gamma_i\) includes the actual time taken to mine the last 2016 blocks. 2. Ethereum (Post-Merge): - \(\delta_{\mathsf{base}} = 12s\) (fixed). - \(\Psi\) does not adjust \(\delta_i\) (slot time is constant). 3. Solana: - \(\delta_i\) is adaptive based on network load. - \(\gamma_i\) includes metrics like transaction throughput and leader rotation speed.
This layer grounds the abstract “mempool” in the physical network, modeling how transactions and blocks propagate across nodes.
The overlay graph \(G_t = (N_t, E_t, \omega_t)\) is a time-varying directed weighted graph representing the P2P network at time \(t\): - Nodes \(N_t\): - \(\mathcal{V}_t\): Validators (consensus participants, e.g., miners or stakers). - \(\mathcal{C}_t\): Clients (transaction originators, full/light nodes). - \(\mathcal{R}_t\): Relay infrastructure (e.g., sentries, block builders, MEV relayers). - Edges \(E_t \subseteq N_t \times N_t\): - Persistent P2P connections (e.g., TCP links). - May be asymmetric (e.g., a validator may connect to a relay but not vice versa). - Latency Weight \(\omega_t: E_t \to \mathbb{R}^+\): - \(\omega_t(u,v)\) is the propagation delay for a message from \(u\) to \(v\). - Depends on: - Physical distance (geographic latency). - Bandwidth constraints. - Network congestion.
Intuition: The overlay graph captures the real-world constraints of blockchain networks: - Nodes are not fully connected (unlike idealized models). - Latency varies significantly (e.g., 10ms within a data center vs. 200ms intercontinental). - Adversaries can manipulate \(G_t\) (e.g., eclipse attacks).
The mempool is the set of pending Events. Each node \(u\) maintains: \[ \mathcal{M}_u(t) = \left\{ \epsilon \mid \epsilon \text{ received by } u \text{ before } t \right\} \setminus \left\{ \epsilon \mid \epsilon \in B_j \right\} \] where: - \(B_j\) is a confirmed block. - \(\mathcal{M}_u(t)\) is node-specific and may differ from \(\mathcal{M}_v(t)\) for \(u \neq v\).
Properties: 1. Non-global: Two nodes may have different mempools due to network latency or censorship. 2. Dynamic: Transactions are added when received and removed when included in a block. 3. Priority-based: Transactions may be ordered by fee, arrival time, or other heuristics.
Example (Ethereum): - \(\mathcal{M}_u(t)\) is a priority queue ordered by gas price. - Nodes may drop low-fee transactions if the mempool is full.
An event \(\epsilon\) originates at a source client \(s\) and propagates via the gossip protocol. The propagation time to a validator \(v \in \mathcal{V}_t\) is: \[ \Delta_{s,v}(t) = \min_{p \in \mathsf{Paths}_{G_t}(s,v)} \sum_{(u,w) \in p} \omega_t(u,w) \] where: - \(\mathsf{Paths}_{G_t}(s,v)\) is the set of all paths from \(s\) to \(v\) in \(G_t\). - \(\Delta_{s,v}(t)\) is the shortest-path latency from \(s\) to \(v\).
Intuition: - Events do not appear instantly in all mempools. - Validators closer to \(s\) (in network terms) see \(\epsilon\) earlier. - This creates latency arbitrage opportunities (see Definition 4.5).
The gossip protocol \(\mathcal{G}\) determines how transactions are forwarded: \[ \mathcal{G}: \mathcal{M}_u \times 2^{N_t} \to 2^{\mathcal{T}} \] where \(\mathcal{G}(\mathcal{M}_u, \mathsf{Neigh}(u))\) returns the set of transactions to send to neighbors \(\mathsf{Neigh}(u)\).
Variants: 1. Flooding (Naive Gossip): - \(\mathcal{G}(\mathcal{M}_u, \mathsf{Neigh}(u)) = \mathcal{M}_u \setminus \mathcal{M}_u^{\mathsf{sent}}\). - Simple but bandwidth-inefficient (redundant transmissions). 2. Diffusion (Erlay): - Uses Invertible Bloom Lookup Tables (IBLTs) to reconcile mempools with neighbors. - Reduces bandwidth by only sending differences. 3. Structured Gossip (e.g., Ethereum’s Gossipsub): - Nodes form a mesh and forward messages along the mesh. - More efficient but requires topology maintenance.
Intuition: Gossip protocols balance: - Bandwidth efficiency (minimize redundant transmissions). - Propagation speed (ensure fast inclusion). - Censorship resistance (prevent adversaries from blocking transactions).
When a validator \(v\) produces a block \(B_i\), it propagates the block via: \[ \mathcal{G}_B: B_i \times N_t \to \{\mathsf{ack}, \mathsf{nack}\}^{\mathsf{Neigh}(v)} \] where: - \(\mathcal{G}_B\) sends \(B_i\) to neighbors and waits for acknowledgments. - The block propagation diameter \(D_t\) is the worst-case time for \(B_i\) to reach all honest validators: \[ D_t = \max_{v,u \in \mathcal{V}_{\mathsf{honest}}} \Delta_{v,u}(t) \]
Intuition: - \(D_t\) is a critical parameter for consensus safety and liveness. - If \(D_t\) is too large, validators may propose conflicting blocks (forks). - Protocols like Compact Blocks (Bitcoin) or Weak Subjectivity (Ethereum) reduce \(D_t\) by sending only block headers first.
The adversary \(\mathcal{A}\) controls a subset of nodes \(N_{\mathsf{corr}} \subset N_t\) and can: 1. Delay Messages: - Add \(\delta_{\mathsf{adv}}\) to \(\omega_t\) on edges incident to \(N_{\mathsf{corr}}\). - Example: A malicious ISP throttling traffic to a validator. 2. Drop Messages: - Remove edges (selective censorship). - Example: A relay node refusing to forward transactions. 3. Eclipse Attacks: - Partition the graph such that all paths between honest validators pass through \(N_{\mathsf{corr}}\). - Example: An adversary controlling all peers of a victim validator.
Intuition: The adversary’s goal is to: - Break safety (create forks by delaying blocks). - Break liveness (censor transactions). - Extract MEV (exploit latency advantages).
A protocol has \((\epsilon, \delta)\)-Eclipse Resistance if for any honest validator \(v \in \mathcal{V}\): \[ \Pr[\mathcal{A} \text{ can eclipse } v] \leq \epsilon \] provided: 1. \(\deg_{G_t}(v) \geq \delta\) (sufficiently many peers). 2. Fewer than \(\frac{1}{3}\) of \(v\)’s neighbors are adversarial (for BFT protocols).
Intuition: Eclipse resistance ensures that: - Validators cannot be isolated by the adversary. - The network remains connected even under attack.
Example (Ethereum): - Validators are required to maintain \(\geq 50\) peers. - The adversary needs to control \(\geq 17\) of a validator’s peers to eclipse it (assuming \(\frac{1}{3}\) threshold).
This layer defines how validators agree on a single chain of blocks, despite network delays and adversarial behavior.
A block \(B_i\) is a tuple: \[ B_i = (H_{i-1}, \sigma_{\mathsf{root}}^{(i)}, \vec{\epsilon}_i, \pi_{\mathsf{consensus}}, \eta_i) \] where: - \(H_{i-1}\): Hash of the parent block. - \(\sigma_{\mathsf{root}}^{(i)}\): State commitment after applying the events. - \(\vec{\epsilon}_i \subseteq \mathcal{M}_v(t_i^{\mathsf{start}})\): An ordered sequence of Events (Transfers, Deploys, and Invocations) included by the proposer. - \(\pi_{\mathsf{consensus}}\): Proof of authority (PoW/PoS). - \(\eta_i\): Additional metadata (e.g., timestamp, gas limit).
Intuition: A block is a batch of Events. Validating a block requires re-executing the sequence \(\vec{\epsilon}_i\) starting from the previous state \(\sigma_{i-1}\) to verify that the resulting state matches the claimed \(\sigma_{\mathsf{root}}^{(i)}\).
The epoch duration \(\delta_i\) must satisfy: \[ \delta_i > D_t + \Delta_{\mathsf{process}}(\vec{\epsilon}_i) + \Delta_{\mathsf{verify}}(\vec{\epsilon}_i) \] Note: \(\Delta_{\mathsf{process}}\) and \(\Delta_{\mathsf{verify}}\) now depend on the computational complexity of the smart contracts invoked in \(\vec{\epsilon}_i\) (bounded by the block gas limit).
Intuition: This condition ensures that: - All honest validators observe \(B_{i-1}\) before proposing \(B_i\). - No validator proposes \(B_i\) before seeing all pending events.
Example (Ethereum): - \(\delta_i = 12s\) (fixed). - \(D_t \approx 2s\) (for well-connected validators). - \(\Delta_{\mathsf{process}}\) and \(\Delta_{\mathsf{verify}}\) scale with block gas usage.
A blockchain \(\mathcal{C}_n\) is a sequence of blocks. Validity requires that for every block \(B_i\): 1. Integrity: Parent hashes link correctly. 2. State Validity: \(\delta(\sigma_{i-1}, \vec{\epsilon}_i) = \sigma_i\) (The events transition the state correctly). 3. Temporal Authority: The proposer was authorized.
When the elected leader for slot \(s\) fails to produce a block within the slot duration \(\delta_i\) (e.g., node offline, network partition), the protocol must recover to preserve liveness. Define the current physical slot: \[ s_{\mathsf{phys}}(t) = \left\lfloor \frac{t - t_{\mathsf{genesis}}}{\delta_i} \right\rfloor \] When \(s_{\mathsf{phys}}(t) \geq |\mathcal{C}|\) (chain height), the leader for slot \(s_{\mathsf{phys}}(t)\) may produce the next block, even if \(s_{\mathsf{phys}}(t) > |\mathcal{C}|\) (missed slots). The block’s timestamp must fall within slot \(s_{\mathsf{phys}}(t)\)’s window. This ensures the chain progresses when nodes come and go.
Implementation (PoS2/TokenX): can_produce_block uses \(\max(|\mathcal{C}|, s_{\mathsf{phys}}(t))\) for leader election. Consensus derives slot from block timestamp when validating.
The fork choice rule \(\mathcal{F}\) selects the canonical chain from the set of observed chains \(\mathcal{G}\): \[ \mathcal{F}: \mathcal{G} \to \mathcal{C} \] where \(\mathcal{C}^* = \mathcal{F}(\mathcal{G})\) is the longest chain (in PoW) or the heaviest justified chain (in PoS).
Examples: 1. Nakamoto Consensus (Bitcoin): - \(\mathcal{F}(\mathcal{G})\) selects the chain with the most accumulated work: \[ \mathcal{C}^* = \arg\max_{\mathcal{C} \in \mathcal{G}} \sum_{B \in \mathcal{C}} \mathsf{Work}(B) \] - \(\mathsf{Work}(B) = \frac{2^{256}}{D}\) (where \(D\) is the difficulty target). 2. Gasper (Ethereum PoS): - \(\mathcal{F}(\mathcal{G})\) selects the chain with the highest justification score, where: - A block is justified if \(\geq \frac{2}{3}\) of validators attest to it. - A block is finalized if it is justified and its child is also justified. 3. Avalanche: - \(\mathcal{F}(\mathcal{G})\) uses repeated sub-sampling to converge on a chain.
Intuition: The fork choice rule must: - Be deterministic (all nodes agree on \(\mathcal{C}^*\)). - Be resilient to forks (prevent long-range attacks). - Incentivize honest behavior (e.g., following the longest chain).
A validator \(v\) with a low-latency view of the network can order Events within \(\vec{\epsilon}_i\) to maximize MEV: \[ \vec{\epsilon}_i^* = \arg\max_{\vec{\epsilon} \subset \mathcal{M}_v} \mathsf{MEV}(\vec{\epsilon}, \prec_v) \] Intuition: This accounts for the fact that the order of Events (especially \(\mathsf{Invoke}\) events) drastically affects the final state \(\sigma_i\).
Mitigations: 1. Fair Sequencing (e.g., Flashbots): - Transactions are ordered by a trusted relay rather than the proposer. 2. Time-Based Ordering (e.g., FSS): - Transactions are ordered by arrival time at a reference node. 3. Commit-Reveal Schemes: - Transactions are committed before being revealed to prevent front-running.
This layer defines the economic incentives that ensure validators behave honestly.
Each validator \(v\) commits an external resource \(\alpha_v \in \mathbb{R}^+\) to participate in consensus: - Proof-of-Work (Bitcoin): \(\alpha_v\) is hashrate (computational power). - Proof-of-Stake (Ethereum): \(\alpha_v\) is staked ETH. - Proof-of-Space (Chia): \(\alpha_v\) is allocated disk space.
Intuition: - \(\alpha_v\) determines \(v\)’s influence in consensus (e.g., probability of proposing a block). - The total resource commitment \(\sum_v \alpha_v\) defines the security budget of the protocol.
The slashing function \(\mathcal{S}\) imposes economic penalties for misbehavior: \[ \mathcal{S}: \mathcal{V} \times \Sigma \to \mathbb{R}^+ \] where \(\mathcal{S}(v, \sigma)\) is the amount slashed from \(v\) for provable misbehavior.
Examples: 1. Safety Violations: Signing conflicting blocks. 2. Availability Violations: Failing to propose blocks. 3. Invalid State Transitions: Proposing a block \(B_i\) where \(\delta(\sigma_{i-1}, \vec{\epsilon}_i) \neq \sigma_i\) (i.e., claiming an invalid state root).
(Concrete instantiations: Double-signing in Ethereum, invalid state transition in Cosmos, liveness faults in Tendermint.)
Intuition: Slashing ensures that: - Misbehavior is costly (deters attacks). - Honest validators are rewarded (via block rewards and fees).
A protocol is Network-Incentive Compatible if for all rational validators \(v\): \[ U_v(\Pi) \geq U_v(\Pi^*) + \mathsf{negl}(\lambda) \] where: - \(U_v(\Pi)\) is \(v\)’s utility under the honest protocol \(\Pi\). - \(U_v(\Pi^*)\) is \(v\)’s utility under a deviating strategy \(\Pi^*\) that includes network-level attacks (e.g., eclipse attacks, latency arbitrage).
Intuition: This requires that: - The cost of controlling high-centrality positions in \(G_t\) (e.g., running a relay node near an exchange) exceeds the MEV extracted from latency advantages. - Validators have no incentive to deviate from the protocol even when they can exploit network asymmetries.
Example (Ethereum): - Running a relay node near an exchange costs \(\approx \$10,000/\text{month}\). - The MEV extracted from front-running may be \(\approx \$5,000/\text{month}\). - Thus, the protocol is not network-incentive compatible in this case. - Solution: Use MEV-boost to auction block space, ensuring that MEV is distributed fairly.
These properties define the security and performance of the blockchain system.
For any two honest nodes \(u, v\) with chains \(\mathcal{C}_u, \mathcal{C}_v\) at times \(t_u, t_v > \mathsf{GST}\) (Global Stabilization Time): \[ \mathcal{C}_u \preccurlyeq \mathcal{C}_v \lor \mathcal{C}_v \preccurlyeq \mathcal{C}_u \] where \(\preccurlyeq\) denotes the prefix relation (i.e., one chain is a prefix of the other).
Intuition: - No conflicting finalized blocks: Honest nodes never disagree on the canonical chain. - Common prefix property: If two nodes see different chains, one is a prefix of the other.
Example (Bitcoin): - Safety is probabilistic: The probability of a fork decreases exponentially with the number of confirmations. - After 6 confirmations, the probability of a reorg is negligible.
For any valid transaction \(\tau\) submitted to at least one honest node \(s \in \mathcal{C}_t\) at time \(t\), and assuming \(\mathcal{A}\) does not control the min-cut between \(s\) and \(\mathcal{V}_{\mathsf{honest}}\): \[ \exists i: \tau \in B_i \in \mathcal{C}(t + T) \text{ where } T \leq \frac{D_t \cdot k}{1 - f} \] where: - \(k\) is the expected number of epochs for inclusion. - \(f\) is the adversarial stake fraction.
Intuition: - Transactions are eventually included in the blockchain. - The inclusion time \(T\) depends on: - Network latency (\(D_t\)). - Adversarial power (\(f\)). - Protocol parameters (\(k\)).
Example (Ethereum): - \(D_t \approx 2s\). - \(k \approx 2\) (transactions are usually included within 2 epochs). - \(f < \frac{1}{3}\). - Thus, \(T \approx 6s\) (in practice, often faster due to parallel block proposals).
A protocol is \((\epsilon, \Delta_{\mathsf{max}})\)-Censorship Resistant if for any transaction \(\tau\) with fee \(\geq f_{\mathsf{min}}\), the probability that \(\tau\) remains unconfirmed after time \(\Delta_{\mathsf{max}}\) is \(\leq \epsilon\), provided \(\mathcal{A}\) does not control a vertex cut separating the originator from \(\frac{2}{3}\) of \(\mathcal{V}\) by weight.
Intuition: - Transactions with sufficient fees are eventually included. - The adversary cannot permanently censor transactions unless they control a large fraction of the network.
Example (Ethereum): - \(\epsilon = 0.01\) (1% chance of censorship after \(\Delta_{\mathsf{max}}\)). - \(\Delta_{\mathsf{max}} = 120s\) (2 minutes). - \(f_{\mathsf{min}} = 1 \text{ gwei}\) (minimum fee to avoid censorship).
Mitigations for Censorship: 1. Inclusion Lists (Ethereum): - Proposers must include transactions from a predefined list. 2. Decentralized Relayers: - Transactions are submitted to multiple relayers to avoid single points of censorship. 3. Time-Based Inclusion: - Transactions are included after a fixed delay, regardless of fees.
These theorems formalize the interdependence between network topology, consensus, and security.
In a partially synchronous BFT system tolerating \(f < \frac{1}{3}\) Byzantine validators, if the underlying graph \(G_t\) has vertex connectivity \(\kappa(G_t) \leq 3f\), then \(\mathcal{A}\) can partition the network to create conflicting finalized blocks without violating local BFT assumptions, thus breaking Safety (Definition 6.1).
Proof Sketch: 1. If \(\kappa(G_t) \leq 3f\), the adversary can partition \(\mathcal{V}\) into three sets \(V_1, V_2, F\) where: - \(|F| \leq 3f\) (adversarial nodes). - \(F\) controls all paths between \(V_1\) and \(V_2\). 2. The adversary delivers \(B_i\) to \(V_1\) and \(B_i'\) to \(V_2\), where \(B_i\) and \(B_i'\) are conflicting blocks. 3. Each partition sees only one block and finalizes it locally. 4. When the partition heals, the network has two conflicting finalized blocks, violating safety.
Corollary 7.2: For BFT consensus, a necessary condition for safety is: \[ \kappa(G_t) > 3f \]
Intuition: - High connectivity is required to prevent partitions. - In practice, this means: - Validators must have many diverse peers (e.g., geographically distributed). - The network must be resilient to node failures.
Under the Network-Adjusted Stability Condition (Definition 4.2), if the gossip protocol \(\mathcal{G}\) has propagation complexity \(O(|N_t| \cdot \log |N_t|)\), then liveness (Definition 6.2) holds with \(T \in O(\delta_i \cdot \log |\mathcal{V}|)\).
Proof Sketch: 1. The gossip protocol ensures that a transaction \(\tau\) propagates to all honest validators in \(O(\log |\mathcal{V}|)\) rounds. 2. Each round takes \(O(D_t)\) time (block propagation diameter). 3. Thus, \(\tau\) is included in a block within \(O(\delta_i \cdot \log |\mathcal{V}|)\) time.
Intuition: - Efficient gossip ensures fast transaction propagation. - Liveness depends on: - The scalability of the gossip protocol. - The epoch duration \(\delta_i\).
| Parameter | Bitcoin (PoW) | Ethereum PoS | Solana | Avalanche |
|---|---|---|---|---|
| \(\mathcal{O}\) | \(\mathcal{H}(B) < D\) | RANDAO + VRF | PoH (VDF-sequence) | Sub-sampling |
| \(\Psi\) | 2016 blocks retarget | Fixed 12s | Adaptive (400ms target) | Async (no slots) |
| \(G_t\) | Random graph (8 conn) | Discv5 DHT + mesh | Turbine (tree) | Kademlia |
| \(\mathcal{G}\) | Erlay | Gossipsub 1.1 | Turbine (FEC) | Gossip |
| Safety | Probabilistic | \(\kappa > \frac{1}{3}|\mathcal{V}|\) | Leader rotation | Snowball finality |
| Censorship Resistance | Topology-agnostic | Relayer-dependent (MEV-boost) | Leader-dominant | Subnet-dependent |
The layers of a blockchain system are interdependent: 1. Layer 1 (State) defines the application logic and state transitions (\(\delta\)). 2. Layer 2 (Time) defines epochs (\(\varepsilon_i\)) and proposer selection (\(\mathcal{O}\)). 3. Layer 3 (Network) defines how events and blocks propagate (\(G_t, \mathcal{M}_u\)). 4. Layer 4 (Consensus) defines block structure (\(B_i\)) and fork choice (\(\mathcal{F}\)), constrained by network latency (\(D_t\)). 5. Layer 5 (Economics) defines incentives (\(\mathcal{S}\)), which must account for network-level attacks (e.g., latency arbitrage).
Key Insight: The Network Topology layer (Layer 3) is the physical constraint that binds the logical consensus (Layer 4) to real-world latency and geographic distribution. Ignoring network effects leads to security vulnerabilities (e.g., eclipse attacks, MEV extraction) or performance bottlenecks (e.g., slow block propagation).