BLOCK PROPAGATION

• BLOCK PROPAGATION

3.
1          What is It About?

Blocks in cryptocurrency protocols are used to establish common state.
 They form the input the consensus protocol strives to reach agreement on.
 Blocks order transactions,
 thus the state of the network can be constructed by following the ordering of transactions included in blocks in the consensus chain.
 Transactions once included in a block deep in the consensus chain are considered confirmed.
 Therefore,
 block propagation is an issue of utmost importance to the consensus process.
 How fast miners learn about new blocks,
 and how quickly blocks can be created and validated are crucial for the efficiency of a cryptocurrency.
 

A block consists of a header and a set of transactions.
 These transactions can be relayed by the sender together with the block,
 but this wastes bandwidth if they are already stored in the mempool of the receiver.
 

Blocks are typically re-propagated to all connected peers as soon as basic validity of the announcement has been established (e.
g.
,
 after the proof of work check).
 In Bitcoin,
 propagation uses the NewBlock and NewBlockHashes messages.
 The NewBlock message includes the full block and is sent to a small fraction of connected peers (usually the square root of the total number of peers).
 All other peers are sent a NewBlockHashes message containing just the hash of the new block.
 Those peers may request the full block later if they fail to receive it from anyone within reasonable time.
 

Blocks can be relayed with a compressed encoding.
 Efficient propagation of blocks is critical to achieving consensus,
 reducing storage bloat,
 overcoming network firewall bottlenecks,
 and allowing scaling to a large number of processed transactions per second (Q1).
 Delayed blocks can lead to forks [24]: Based on measurements of the rate of information propagation in the network,
 the propagation delay in the network can be the primary cause for blockchain forks.
 Blockchain forks should be avoided as they are symptomatic for inconsistencies among the replicas in the network.
 As a mitigation strategy,
 the authors propose pipelining the block’s delivery,
 i.
e.
,
 starting to transmit blocks before they have been fully validated.
 

One of the reasons for such delays is churn.
 Imtiaz et al.
 [54] report that almost all (97%) Bitcoin nodes are connected intermittently only,
 which results in significant numbers of unsuccessful exchanges,
 roughly twice the figure for continuously connected nodes.
 In particular,
 they demonstrate experimentally that this churn leads to a 135% average increase in block propagation time (i.
e.
,
 336.
57 ms vs.
 142.
62 ms),
 and can lead to as high as an 800-fold increase in the worst case measured.
 

Permissioned blockchain networks based on Byzantine Fault Tolerance (BFT) consensus algorithms are also highly affected by the propagation time.
 Nguyen et al.
 [83] demonstrate how a network delay leads to a 30 times larger offset in the consensus layer in Hyperledger.
 

Often,
 miners collaborate in mining pools to share the risks and rewards of finding blocks ( Q2,
Q3).
 To this end,
 a dedicated server is connected to a node that acts as a gateway to a cryptocurrency network.
 This node gathers newly transmitted transactions and newly built blocks to construct a new block template.
 The template header is then sent via a mining pool server to the miners,
 which attempt to complete it to a valid block.
 In the simplest approach for Bitcoin,
 the miners try different values for the nonce field in the header.
 If the resulting hash has enough leading zeros for the current difficulty level,
 i.
e.
,
 when the block is completed,
 then it is sent back to the server,
 which then uses the gateway node to publish the newly formed block to the network and distributes the reward among the miners of the pool corresponding to their contributions.
 In 2017,
 Bitcoin derived at least 95% of its mining power from 10 mining pools; in the Ethereum network,
 6 pools are responsible for 80% of the mining power [66].
 

3.
2          State-of-the-Art

Networking-induced bounds on throughput and latency for the protocols in Bitcoin are studied in Reference [22].
 By considering the effective throughput of the network,
 i.
e.
,
 the percentage of nodes that receive a block within one block interval period,
 they conclude that the block size should not exceed the block interval divided by the effective throughput.
 From simulating the P2P network and measuring the time that the blocks reach the nodes,
 they infer that for 10min or shorter intervals the block size should be below 4 MB,
 as they found the block propagation time to grow roughly linearly with the block size until around 80 KiB blocksize,
 above which the throughput dominates (around 55 Kbps or 26 transactions per second to reach 90% of all nodes within one block interval).
 To improve the system’s latency,
 the block interval can be shortened,
 yet the block size must be adapted in alignment with the above bound.
 To be able to scale beyond these limits,
 the authors compile a list of technical design approaches,
 capturing consensus and storage components in addition to networking.
 Many of them have been active research topics,
 e.
g.
,
 set reconciliation protocols,
 relay networks,
 incentivation and overlay topologies,
 they are discussed in more detail below.
 

Compressedblockencoding.
 Many proposals to minimize the bandwidth consumption for block propagation exist.
 One such proposal for Bitcoin addresses the inefficiency of broadcasting blocks with all the transactions included.
 By the time a new block is created,
 it is very likely that most peers have these same transactions stored in their mempool.
 As such,
 relaying new blocks causes inbound bandwidth spikes for receiving nodes and potentially large outbound bandwidth spikes for nodes that receive blocks before their peers,
 since they will flood the network with the new,
 raw block data.
 

Xtreme Thinblocks (XThin) [106],
 deployed in Bitcoin Unlimited (BU) clients uses Bloom filter encoding the transaction IDs in nodes’ mempool,
 thus only missing transactions must be exchanged.
 In an alternative,
 the Compact Blocks protocol [1],
 deployed in the Bitcoin Core,
 Bitcoin ABC,
 and Bitcoin Unlimited clients,
 the block’s transaction IDs are announced shortened to 6-bytes.
 If the receiver has missing transactions,
 then it requests them separately.
 Thus,
 if the receiver is missing many transactions,
 then Compact Blocks have an extra roundtrip time compared to Xthin,
 which may cost more if enough transactions are missing.
 Graphene [85] combines the use of a Bloom Filter with Invertible Bloom Lookup Tables (IBLTs) [47].
 The main concept of Graphene’s approach consists in shrinking the size of the sender’s Bloom filter by increasing its false positive rate,
 and correcting any false positives at the receiver with an IBLT.
 The summed size of the two structures is smaller than using either alone.
 In practice,
 this technique performs significantly better than Compact Blocks for all but the smallest number of transactions,
 and it performs better asymptotically than any approach relying on Bloom-filters only.
 In comparison to XThin,
 Graphene uses significantly lower bandwidth both when the receiver is and is not missing transactions.
 However,
 Graphene may use an additional roundtrip time to repair missing transactions.
 The protocols described above rely on a single peer to send the complete data of a block,
 opposed to using multiple peers to transmit partial data.
 Velocity [21] is an approach that exploits the fact that typically several peers already have (parts of the) data in a block.
 To this end,
 it applies Fountain codes,
 which provide a mechanism by which information can be encoded such that the resulting segments can be probabilistically re-assembled into the original data when the number of the received segments exceeds a threshold.
 

Upon receiving a message advertising the knowledge of one or more objects,
 a receiver requests any unknown blocks using a request message to all its neighboring peers.
 Peers that have information on the requested block(s) respond with repeated responses,
 each encoding one symbol.
 The receiver collects these symbols and reconstructs the corresponding blocks when it has received a sufficient number of symbols.
 If the reconstruction succeeds,
 then it notifies its peers to stop symbol transmission.
 Note that this approach can be used for node bootstrapping in addition to speeding up synchronization.
 

Stratum Mining Protocol.
 Stratum [55,
 88] is the de-facto standard mining communication protocol used by blockchain-based cryptocurrency systems.
 It enables miners to reliably and efficiently fetch jobs from mining pool servers.
 

Stratum was initially a proposal for an open source client-server overlay protocol to support lightweight clients.
 The Stratum mining protocol extends this proposal to a networking protocol for pooled mining services on the Bitcoin network and many other blockchain protocols.
 The protocol establishes client-server connections using TCP sockets between mining clients and a pool operator or server to distribute new work defined through a blockchain’s proof of work protocol.
 

Recabarren et al.
 [92] exploit Stratum’s lack of encryption to develop passive and active attacks on Bitcoin’s mining protocol,
 with important implications on the privacy,
 security and even safety of mining equipment owners.
 Active attacks can hijack shares submitted by miners,
 and their associated payouts,
 by modifying TCP packet surreptitiously without causing disconnections and session resets.
 To mitigate such attacks,
 the authors propose Bedrock,
 a Stratum extension that protects the privacy and security of mining participants with mining cookies.
 Each miner shares a secret with the pool and includes in its puzzle computations,
 preventing attackers from hijacking the solutions.
 

Another attack on mining is introduced in Reference [75],
 assuming miners are ration.
 An attacker presents only headers,
 i.
e.
,
 a proof that the attacker mined blocks,
 without the block itself.
 From the miner’s perspective,
 this reduces the probability to mine a successful block and thus might make it non-profitable,
 in expectation after considering mining costs (e.
g.
,
 electricity and wear).
 Weak blocks.
 To speed up block propagation even further,
 one approach is to let miners broadcast blocks they are working on before they have finished the corresponding proof of work.
 More precisely,
 so called weak or near blocks whose proof of work is insufficient for the target difficulty,
 can be disseminated early.
 As a consequence,
 when the block is fully mined the corresponding payload has been received and validated by most nodes already and only the headers need to be broadcast and processed [3].
 

Traditionally,
 the weak blocks are discarded in Bitcoin,
 wasting their proof of work entirely.
 Ideally,
 the chain is solified with any and all sufficient proofs of work.
 Weak blocks by definition have shorter interarrival times and could thus be used by miners to both receive strong confirmation signals for weak transactions (transactions in weak blocks) as well as anticipate forks sooner (since mining variance is reduced in weak blocks,
 conflicting blocks appear sooner).
 Many updates to Nakamoto Consensus have been proposed that utilize similar ideas,
 yet no protocol change to utilize weak blocks has made its way into the Bitcoin Core source code.
 Some,
 such as BitcoinNG [36],
 exploit weak blocks to store and propagate transactions.
 The key blocks serve to elect a new leader,
 granting that miner the right to extend the chain with weak blocks.
 The protocol splits rewards between miners of previous leader elections to incentivize against malicious behavior such as selfish mining or hidden block extension attacks.
 Another similar proposal termed Flux [116] augments the existing Bitcoin protocol with weak blocks such that chains of weak blocks or sub-chains contribute to a chain’s proof of work.
 Using the heaviest chain rule as its consensus rule,
 it can provide faster transaction confirmation times by ensuring that key blocks that link to sub-chains contain transactions included in the sub-chain’s weak or sub-blocks.
 This can work in practice without the buy-in from all miners as well.
 One can imagine that if a certain number of miners opts in for broadcasting weak blocks,
 key blocks (which would also serve as legacy Bitcoin blocks) could ensure that the dominant chain contains some sub-chains of weak blocks.
 

Relay Networks.
 In parallel to the public P2P protocol,
 separate relay networks have been designed to increase network efficiency for miners.
 The first such system for Bitcoin,
 called Bitcoin relay network [78],
 achieves this by disseminating blocks without full block verification and retransmitting known transactions.
 It consists of a few nodes (supported by donations) scattered around the globe,
 all of which peer with each other.
 Another approach,
 Falcon [10],
 relies on cutthrough routing for faster block propagation in addition to minimal validation and a handoptimized topology.
 More recently,
 FIBRE [14] has been initiated to provide a similar service by combining cut-through routing with compact blocks and forward error correction over UDP (the normal Bitcoin protcol uses TCP) for registered users.
 Both Falcon and FIBRE can greatly reduce block propagation times and block orphan rates in the Bitcoin network,
 as shown in Reference [84].
 However,
 it is important to note that neither was designed,
 nor is suitable,
 to scale Bitcoin.
 Bitcoin cannot rely solely on these relay networks to achieve higher throughput,
 since the use of a relay network to scale,
 places the control over which transactions are included in the blockchain,
 and which miners may participate,
 in the hands of its operator.
 For example,
 the relay network operator may choose (or be coerced) to propagate blocks only from one group of miners,
 and reject all others,
 or to propagate blocks only to one group of miners,
 and not to others.
 Worse still,
 it might reject all blocks that contain transactions involving a specific address,
 effectively banning its owner from using it.
 

State Synchronization.
 For new nodes to be able to contribute to the P2P network quickly,
 Ethereum provides a state synchronization protocol.
 The first message sent by two Ethereum peers after the handshake describes their status containing information on the node’s protocol version,
 network ID (multiple Ethereum networks exist),
 the hash of the genesis block,
 the best known block hash and the currently used difficulty.
 Only connections to nodes operating on the same network ID and genesis block are maintained.
 Based on their best block hashes the nodes will then synchronize their available information.
 

In Ethereum two validation mechanisms can be distinguished: (1) block header validation and (2) blockchain state validation.
 Block header validation,
 ensures that a block’s parent block hash,
 block number,
 timestamp,
 difficulty,
 gas limit,
 and valid proof of work hash are correct.
 In contrast,
 blockchain state validation consists of sequentially executing all transactions and thus requires significantly more computation and time.
 To reduce the time for new nodes to synchronize and validate the entire blockchain,
 the fast sync mode has been introduced.
 Instead of running blockchain state validation on all blocks since genesis (as necessary in Bitcoin),
 header validation is run until a pivot point block close to the most recent head of the blockchain is chosen (using messages to obtain meta information including gas consumption,
 transaction logs,
 and status code).
 At the pivot point,
 a fast sync node downloads a global state database at that block.
 From the pivot point onward,
 the node performs full blockchain validation.
 

Incentives for Block Propagation.
 For cryptocurrencies to function properly,
 blocks need to be propagated promptly upon their creation to all other users in the network.
 This is crucial both to the liveness and to the security of these protocols.
 To this end,
 there is a need to examine that miners are incentivized to follow block propagation rules,
 and not to vary from them (Q4).
 Selfish mining attacks [37,
 97] aim to increase the relative fraction of blocks mined by an attacker through timing the release of blocks created by an attacker.
 The strategies differ based on how long the attacker waits before publishing blocks from a secret chain.
 These attacks show that there are cases in which miners can profit by not propagating blocks as soon as they are created.
 

Another case in which miners can profit by deviating from vanilla block propagation is SPV mining.
 In a similar vein,
 the “SPV (simplified payment verification) mining” concept can decrease the block propagation latency,
 by avoiding the full verification of blocks and instead relaying them partly unchecked.
 Originally,
 the approach has been developed to expedite mining: To build on top of the previous block and extend the chain,
 miners need the hash of the previous block.
 However,
 they do not need the full block with all the transaction data to start mining.
 It is in fact sufficient to only have the hash of the previous block header to mine a valid block.
 The incentive for SPV mining is a rush to mine blocks as fast as possible to increase profits.
 Waiting to download the full block and validate all of the transaction results in idle time,
 which can lead to lost profits.
 Therefore miners may be tempted to find the next block before they have even had time to download and verify the previous block.
 This way,
 miners avoid putting any transactions in the block (apart from the coinbase transaction that rewards the miner),
 since they cannot know which transactions were in the previous block.
 Including transactions could result in double-spending (which would deem the block invalid).
 SPV mining is one of the reasons that empty blocks appear on the blockchain [110].
 Moreover,
 SPV mining increases the probability of an invalid block being used to extend the chain and mine the next block linking to an invalid block (since the transactions are not validated by the following block,
 or even multiple blocks).
 This in turn results in the network being less reliable for payments as double-spends are more likely.
 In fact SPV mining has already caused a split in the network in the past: In 2015 there was a change implemented in the Bitcoin protocol (regarding enforcing BIP66 strict DER signatures) that was supposed to go into action after 95% of the network updated their software.
 The way in which this was implemented is the following: Once 950 of the last 1,
000 blocks were version 3 (v3) blocks,
 all upgraded miners would reject version 2 (v2) blocks.
 On 4 July 2015,
 shortly after the threshold was reached,
 a small miner (part of the non-upgraded 5%) mined an invalid block.
 Unfortunately,
 it turned out that roughly half the network hash rate was mining without fully validating blocks,
 and built new blocks on top of that invalid block,
 causing a split.
 

SPV mining is also an issue in Ethereum,
 and in 2018 it was discovered that F2Pool (one of the largest mining pools at the time) was engaged in SPV mining,
 which resulted in a disproportionate number of empty blocks.
^[1]

Another similar strand of attack is Spy mining among competing mining pools.
 Spy mining occurs when attackers join the pools of others to obtain hints about new blocks appearing on the network.
 When a spy detects such information via the changed headers sent to it in the Stratum protocol,
 it can notify its other pool to avoid wasted work.
 Thanks to SPV,
 the miners can start mining a new block without seeing the old block’s content.
 

3.
3           Open Questions

Latency and throughput of cryptocurrencies depend on the efficiency of block propagation.
 Therefore,
 mechanisms and incentives to spread newly minted blocks as quickly as possible while minimizing bandwidth waste are crucial.
 At the same time,
 the system design must not forego safety and the protocols in place must ensure that blocks contain valid transactions despite the hunt for speed.
 

Open Question 1.
 How does one accelerate block propagation? Enables scaling to higher transaction rates and lower latency.
 Several approaches to optimize the exchange of information in blocks between two nodes as well the dissemination in the network have been presented.
 Yet,
 

both dimensions provide opportunities for empirical studies of the status quo and subsequently to devise new approaches to overcome this barrier to faster transaction rates.
 

Open Question 2.
 How does one design efficient networks for mining pools? Pools that communicate information efficiently are better at mining,
 i.
e.
,
 they have an advantage in mining over their competitors.
 Within a pool one could consider a more permissioned model with a more structured overlay topology for speed,
 balancing the possible velocity gains with the risk of new attacks.
 

Open Question 3.
 Should mining pools be allowed? Do the benefits of mining pools outweigh the security risk they introduce from a centralization aspect? If not,
 then can they be prevented? Can pools be monitored for malicious behavior? How does one design a mechanism that incentivizes honest pool behavior?

Open Question 4.
 How does one incentivize mining blocks with many valid transactions? This will drive up transaction rates.
 SPV mining poses risks,
 thus designing a system preventing this behavior,
 e.
g.
,
 with economic incentives is still open.
 

---

[1] https://medium.
com/@ASvanevik/why-all-these-empty-Ethereum-blocks-666acbbf002.