Complex Blocks

Author: BitMEX Research

Source: https://www.bitmex.com/blog/attack-blocks

Abstract: In this article, we will discuss “hardened blocks”—blocks specifically designed to be difficult to verify. Such blocks are formed when someone harbors hostility towards Bitcoin and creates “hardened transactions” (transactions specifically designed to take nodes a long time to verify). This concept was first discussed in January 2013 when a hardened transaction approaching 1MB in size appeared, requiring approximately 3 minutes to verify on a typical computer. There are variations of this attack that could worsen the situation by several orders of magnitude, but these will not be discussed in detail here. The BIP-54 soft fork proposal included a fix: limiting the total number of CHECKSIG and CHECKMULTISIG opcodes that can be used on a transaction’s non-Segregated Witness input.

Overview

This is the fourth article in a series about potential Bitcoin vulnerabilities that can be fixed or mitigated under BIP-54.

1. Bitcoin's Duplicate Transactions - March 2025 ( Chinese Translation )
2. The Timewarp Attack - March 2025 ( Chinese translation )
3. 64 Byte Transactions - December 2025 ( Chinese Translation )

In this final article, we'll explore one of the most serious potential vulnerabilities: the possibility of malicious blocks appearing; it can cause a node to spend an extremely long time verifying them. This problem is often referred to as the "worst-case block verification problem."

Origins of the problem

In January 2013, Bitcoin security researcher Sergio Lerner posted on the Bitcointalk forum explaining that it was possible to construct a valid Bitcoin transaction that would take a node at least 3 minutes to verify. The method involved creating a transaction with many inputs (considering historical timelines, specifically the Segregated Witness script type). These inputs suffered from the so-called "SIGHASH operation quadratic inflation" problem.

Sergio explained that a Bitcoin transaction with a size close to 1MB can generate over 19GB of hashable data, requiring at least 3 minutes to verify on a typical computer. The 1MB block size limit limits the severity of this problem; without it, the attack could be far more severe. In Sergio's example, the transaction is invalid, but the attack is still considered fatal because it forces a node to spend a considerable amount of time determining whether a transaction is valid or invalid. Furthermore, spending 3 minutes verifying a single transaction is clearly a serious problem. We have listed some of the potential issues in the table below.

Negative consequences of complicated transactions

Block size war

The problem of complex blocks also appeared in the "Blocksize War" (which lasted from 2015 to 2017), as a reason not to increase the block size limit; at the very least, new limits had to be added to constrain the impact of this problem.

In December 2015, Bitcoin security researcher Jonas Nick gave a presentation on this very topic at the "Scaling II" conference in Hong Kong. He explained why the block size limit should not be increased unless a new resource usage limit is added to Bitcoin blocks to mitigate the impact of such attacks.

- Image source: https://youtu.be/vfIs_trEhao?si=oRu2x6CfWhFbxG2R&t=3692 -

In January 2016, a blog post appeared on the Bitcoin Core project website explaining the advantages of "SegWit." A key advantage of SegWit was that it fixed the bug of non-linear expansion in the SIGHASH operation. This is why SegWit appears to be a powerful solution to Bitcoin's scaling problem: it maintains a 1MB size limit for older (potentially problematic) transaction formats while increasing the block size for transaction formats that do not have this fatal flaw.

Essentially, doubling the size of a transaction doubles both the number of signature operations and the amount of data that needs to be hashed to verify each signature. This has already been observed in non-experimental environments: a normal single block can be verified in just 25 seconds, while a maliciously crafted transaction can take more than 3 minutes to verify.

— Segregated Witness Benefits ( Chinese translation )

In March 2021, we published a book about the block size war, which also discussed the worst-case block verification problem. We mentioned that such a block could take "several hours" to verify—a significant difference from the "3 minutes" figure popular between 2013 and 2016. This is because some Bitcoin security researchers suggested to us that they had found ways to maximize the exploitation of this attack, thus exacerbating the situation and requiring several hours for verification. However, on the other hand, perhaps our "several hours" figure is also somewhat unrealistic, unless you are using a fairly low-spec device (such as a Raspberry Pi).

The non-linear inflation of SIGHASH operations means that as the number of inputs to a transaction increases, the number of hash operations required to verify that transaction increases quadratically, not non-linearly. This inflation problem is an obstacle to increasing the block size limit because (after removing the limit) attackers can create transactions that take a very long time to verify, long enough to bring the entire network to a standstill. An attacker could even construct a block containing many such large transactions, requiring an average computer several hours to verify. Therefore, for many small-block advocates, fixing this problem is a prerequisite for increasing the block size limit. They ridicule large-block advocates for being complacent because they haven't noticed this weakness and for lacking adversarial thinking.

— The Block Size War

Arithmetic of Malicious Blocks

In this section, we will explain this attack in more detail. When attackers prepare difficult blocks, they need to consider three Bitcoin consensus constraints:

For computational purposes, we explain the most basic form of this attack, even simpler than Sergio's 2013 example—though certainly an oversimplification. The idea is that the attacker first constructs some initiating transactions, which can be assumed to be placed in a separate block to avoid occupying the 1MB space of the block that actually triggers the attack. In these initiating transactions, the attacker creates numerous outputs, each containing 200 OP_CHECKSIG opcodes. With these outputs, the attacker is ready to create the actual attack transaction. This attack transaction uses all these outputs as inputs, and (in our scenario) can reserve one output for itself. Each input contains one meaningful CHECKSIG and 200 meaningless CHECKSIGs (filling the 10KB available space for a single script). This utilizes all available space, thus maximizing the power of the attack.

Given such an attack transaction, we use the following very basic approximation formula to calculate the total amount of data we need to hash when verifying the attack transaction. Note that the formula below includes a squared term for the number of inputs to reflect the quadratic inflation bug in the SIGHASH operation: the more inputs, the more data needs to be hashed, and this is a quadratic relationship.

总共需要哈希的数据（KB） = 201 * N * (10KB + N)其中N 为交易输入的数量

Using the formula above, we plotted the following graph, which reflects how the amount of data that needs to be hashed depends on the number of inputs in the attacking transaction. The shape of this curve reveals a square function. The formula above is imprecise and does not accurately count the amount of data that needs to be hashed; its purpose is merely to demonstrate: to very roughly illustrate this inflation problem and the mathematical relationships involved.

Number of data items to be hashed vs. number of transaction inputs

The horizontal axis of this table stops at slightly more than 8,000 inputs because the transaction size is now close to 1MB, which is the maximum space a transaction could use before Segregated Witness. To verify this transaction, the node needs to hash more than 30GB of data. This is an attack transaction, and in our very basic (and potentially inaccurate) case, the worst-case scenario it could cause. Our understanding is that the amount of data that needs to be hashed (not the number of ECDSA signature verifications) is the key indicator of the danger of such complex transactions, so we only focus on this metric.

Each KB of hash takes 0.005 ms (milliseconds) – a figure Jonas Nick mentioned in a 2015 presentation on a 2014 laptop (using a dual-core 3GHz i7 CPU). The graph below illustrates how long these attacked transactions might take to verify. In the worst case, it takes over 150 seconds to verify a single transaction, or more than two and a half minutes. This is clearly a fatal flaw. In a recent report ( Chinese translation ), regarding node performance, our nodes typically verify 15 blocks per second. Therefore, these difficult blocks significantly slow down verification speed (compared to regular blocks), by approximately 2300 times.

Verify the time spent attacking the exchange vs. the number of inputs to the attacking exchange.

However, current devices are much faster than those from 2015, and inputs can be validated in parallel. Therefore, the validation timeline above may be somewhat conservative for today's devices.

(Translator's note: Not all nodes on the Bitcoin network use the latest equipment; some nodes may have computing power equivalent to a 2015 i7 dual-core CPU.)

BIP-54 Remedial Measures

The fix proposed in BIP-54 is relatively simple: add new consensus constraints to individual transactions to limit the number of the following factors:

1. CHECKSIG and CHECKMULTISIG opcodes in all non-isolated witness inputs
2. The public key of the script output in the preceding step

If the sum of the two items mentioned above in a transaction exceeds 2500, it will be considered an invalid transaction.

With these fixes, in the scenario described above, an attack transaction will only contain 12 inputs, a block will only require 24MB of hashable data, and verification will take only 0.1 seconds. The problem seems to be well solved, at least in our very basic case.

in conclusion

To reiterate, our calculations and examples are extremely basic and far too simplified. There are also clever techniques that can make attacks significantly more severe (by orders of magnitude). For instance, adding output using long scripts can further increase the amount of data that needs to be hashed. In these extreme cases, a difficult block could escalate into a crisis for the Bitcoin network, as verifying just one block could take over an hour, potentially causing a large number of nodes to go offline or never return.

Fortunately, this type of attack is extremely complex to execute. First, it requires sending non-standard transactions, likely only miners can initiate such attacks. Even using services that submit transactions directly to miners (such as Matathon's Slipstream), miners likely have built-in security logic and won't sit idly by for hours verifying the submitted transaction. Second, these worst-case scenarios involve multiple complex initiation transactions that occupy a significant amount of block space before the difficult blocks are produced. If the attacker isn't careful, someone observing the Bitcoin network could potentially detect these initiation transactions and alert users to an urgent soft fork, which might prevent the attack (or not). Therefore, from this perspective, this vulnerability is similar to a "time warp attack."

However, despite the complexity of the attack, we believe it is a very serious problem for Bitcoin that needs to be fixed. It is likely the most serious of the four issues that BIP-54 intended to address. We have ranked these four issues from most serious to least serious as follows:

1. Complex Blocks
2. Time Warp Attack
3. 64 Transactions
4. Overlapping transactions

(over)