On Soft Fork Security

This post is a publication of an old draft I had on the Ethereum soft fork and its security.  I chose not to publish the article at the time, but am releasing it now for public viewing.

Lots of fun with soft forks in the last few months, starting with the discovery of a potential DoS vulnerability in the proposed Ethereum DAO wars fork, followed by an analysis that suggests that Ethereum is inherently safer than Bitcoin against miner censorship on soft forks.  Even Ethereum’s founder Vitalik Buterin was quoted as reflecting on the results by saying “In my opinion, outside of the scope of this one narrow incident, the difficulty of implementing soft forks is a good thing; it means that a small mining oligopoly cannot engage in censorship (a property that Bitcoin does not have!) and that the only way to practically interfere with the protocol operation is a hard fork, and hard forks are, in my opinion, more democratic as the entire community and not just a few miners must participate”.

This blog post will cover my thoughts on just what this difficulty property that Bitcoin supposedly does not have entails, and how we can quantify it for general blockchains and blockchain applications.  I’ll lean on my reading of previous forks, and attack vectors previously discovered by the cryptocurrency community in their applications.  In the original series of posts that started this debate, HackingDistributed also notes that “… miners can still exclude transactions based on features that are easy to statically analyze: e.g. format, syntactic features, source addresses, etc.”  Part of this post will be spent determining whether only such transactions can be censored, and we will also address both why and how such transactions can be censored.  We will only cover soft forks.

This post contains only hypotheses meant for potential consideration in future discussions.  There is nothing that has been rigorously validated within, and as such the post represents my personal opinion alone.  We will focus specifically on a class of attacks on soft forks at the network and mempool level, where an attacker generates transactions valid under old rules and invalid under new rules and attempts to leverage these transactions to attack either new or old nodes.  Such attacks are similar to the attack on the Ethereum soft-fork previously described, and involve exhausting the mempool of nodes (and potentially overwhelming the relay network with transactions).

Other fork-specific attacks are possible and must be excluded through manual audit, but this class of attack is particularly devastating because it represents a general purpose DoS vector, a network partitioning vector, and in all cases is completely free to an attacker (as it relies on transactions that will never be mined).

Soft Fork Security Metrics

Soft forks inherently work by tightening validation rules on blocks and/or transactions, invalidating nonconforming data that may be generated by and valid to old versions of the software.  Because much of the current discussion surrounds soft forks that modify transaction rules, we’ll focus on those; they’re both more relevant and interesting than soft forks that only restrict block format.

It is my personal opinion that the general security of soft forks against denial of service attacks such as the one presented against the proposed Ethereum fork can be broken down by asking two questions:

  1. Is the increased computation involved in checks on transactions or blocks bounded and cheap, or expensive and unbounded?
  2. To what extent will old nodes relay newly nonconforming transactions? (in this analysis, we conflate relaying with mempool acceptance, which is how most of these systems work in practice)

In the following sections, I’ll justify the following broad and cursory breakdown:

Old Nodes Relay/Accept Unbounded Old Nodes Relay/Accept Limited
Cheap, Bounded Check  Old Nodes Vulnerable to DoS  Safest Soft Fork
Expensive or Unbounded Check  Old, New Nodes Vulnerable to DoS  New Nodes (less) Vulnerable to DoS

For each box, we’ll analyze the general attack possible against any fork with these conditions met, providing examples when possible.  If a fork is claimed to be safe, we will provide an intuitive argument for why a mempool or network exhaustion attack is not possible.  To make the case for safety, we’ll look at soft forks which are resilient against such attacks.

Finally, to lighten the read a bit, we’ll consider a few different types of soft forks which could result in miner oligopoly-imposed censorship on the Ethereum network, providing some counterarguments to the claim that Ethereum is inherently resistant to bad soft forks.

Some Notation

If you’re the type of person who benefits from a rigorous and well-defined notation, we will introduce some.  Otherwise feel free to skip to the next section for a less technical but equally substantive read.

In a soft fork, let T be the set of valid transactions from the view of an old node.  Let T’ be the set of valid transactions from the view of a new node.  A soft fork thus changes the validation rules for transactions such that T’ ‎⊊ T‎ (T’ must be a proper subset of T, otherwise the fork is not a fork).

For some t ∈ T, we then define two functions: V(t) defines whether a t is targeted for exclusion by the soft fork (defined as t ∈ T \ T';), and R(t) checks whether old nodes would propagate t to their peers.

The interesting question then becomes whether we can design a fork whereby T \ T (newly restricted transactions) constitutes meaningful censorship in Ethereum, and what the consequences of designing such a fork poorly could be to the network.

So we can rewrite our above table as:

| t . V(t) ^ R(t) | is 0 or small constant | t . V(t) ^ R(t) | is large
V(t) cheaply computable  Old Nodes Vulnerable to DoS  Safest Soft Fork
V(t) not cheaply computable  Old, New Nodes Vulnerable to DoS  New Nodes (less) Vulnerable to DoS

 

Cheap Checks, Easy Relays

In this case, transactions which are nonconforming under the new rules can be cheaply categorized, but are relayed unbounded by old nodes unaware of the soft fork rules.

Old nodes vulnerable: Such conditions open old nodes up to a simple attack: an attacker mines many seemingly attractive transactions to old nodes, who accept and relay the transactions among themselves (“easy relays”).  These transactions fill the mempool of the old nodes, and exhaust the capacity of these nodes to process relay transactions in a full denial of service attack.  If a “denial of service” score is assigned to such bad transactions (as in Bitcoin, where nodes can be depeered for relaying invalid transactions), old nodes may be disconnected from new nodes through such an attack, potentially partitioning the network.  Old nodes also waste non-free work processing these transactions, which have no chance of inclusion in blocks and linger in the mempool for extended time periods.

New nodes immune: New nodes derive an immunity against attacks in this model because checks are cheap.  New nodes may be vulnerable to a DoS amplification vector, as honest old nodes relay invalid transactions to new nodes, wasting processing power before they are discarded.  However, the “cheap checks” ensures that old nodes are still able to process legitimate transactions and thus are not completely denied service.  Requiring some number of peers to be running the soft fork turns this safety guarantee from probabilistic (as there is a high probability of new node peering and thus no DoS) to guaranteed.

Even Bitcoin opens itself to attacks under forks of this nature; if a fork blocks a particular destination in the output of transactions, for example, the check is cheap, but old nodes will be vulnerable to attack by an attacker flooding their mempool with tons of invalid but seemingly high priority transactions.  Such an attack could partition the network and deny service to all old nodes, and could also be used as an amplification vector for a network-based DoS on new nodes, which will waste processing power completing gratuitous and unnecessary (albeit cheap) checks.

So even Bitcoin maintains some level of resistance to any forks which modify transactions the current network will relay, as every such fork enables a corresponding network attack.

Expensive Checks, Easy Relays

In this catastrophic scenario, stronger variants of the attacks above are made possible by computationally expensive checks.

Old nodes vulnerable: As in the previous attack, old nodes can easily have their mempool and relay capacities exhausted by invalid transactions.  The expensive checks do not affect old nodes, who do not perform such checks.  The vulnerability of these nodes is identical to the case where checks are cheap.

New nodes vulnerable: Unlike in the previous attack, the amplification vector for denial of service on new nodes is far more severe in this scenario.  New nodes are forced to process and reject large numbers of seemingly legitimate transactions relayed by old nodes, discarding them only after wasting substantial resources at no cost to the attacker.  New nodes cannot depeer or stop processing transactions from old nodes, as an attacker could leverage this for a permanent network partition through a stream of invalid transactions, potentially even leading to consensus inconsistencies.  An additional amplification vector is provided even to fork-enabled nodes that peer only with other new nodes, as an attacker can submit large numbers of transactions which require expensive checks, an amplification vector that grows proportionally to the cost of the checks.  New nodes are thus vulnerable to substantial resource exhaustion attacks in such a model.

It is this case into which the proposed DAO soft fork fell: checks were expensive, as they often required running the full program involved in a transaction to check for DAO calls.  Relay was unbounded, as old nodes considered these transactions fully valid.  A major attack naturally resulted.

Cheap Checks, Hard Relays

This type of fork is claimed to be the safest, primarily because they are not in general vulnerable to any attacks we described.

Old nodes immune: Old nodes are immune from mempool and relay exhaustion attacks by the hard relays of nonconforming transactions; these transactions are limited in their propagation across the network, and limited in their capacity to enter old nodes’ mempools, limiting the potential amplification of denial of service attacks.

New nodes immune: New nodes are similarly immune to denial of service attacks, with cheap checks making nonconforming transactions easily discarded, and hard relays requiring few such transactions to be processed by new nodes.  No mempool space is wasted by new nodes, as in all of these scenarios.

Bitcoin’s SegWit fork is an example of such a fork – invalid SegWit transactions fail isStandard on older nodes, meaning they are not relayed across the network and cannot be used to launch a mempool DoS attack on older nodes.   The relatively cheap checks (the most difficult part of which is relatively fast and generally bounded ECDSA verification) mean that manually spamming a new node with invalid transactions would likely not be more effective than any other form of network-based DoS.

Such forks in general prevent old nodes from needing to waste processing and relaying time on transactions that will never be mined, and prevent new nodes from having to perform unbounded and expensive checks before ascertaining whether a transaction is valid, potentially working to validate a transaction that pays no fees.

Expensive Checks, Hard Relays

An interesting question is whether hard relays alone are sufficient for a safe soft fork.  In general, the answer seems to be “somewhat”, though expensive checks combined with hard relays do open new nodes to some denial of service amplification.

New nodes vulnerable to amplification: Because new nodes perform expensive checks before discarding transactions, an amplification vector occurs whereby new nodes are flooded with nonconforming transactions, incurring expensive verification penalties for transactions that pay no fees. The potency of this amplification vector depends on just how expensive these checks are in practice.

Old nodes immune: Old nodes do not run the expensive checks or relay transactions, so the penalty they incur is in the form of a mempool exhaustion attack bounded by their acceptance of bad transactions, which is limited.  Service continues on old nodes, relatively unaffected.

As far as I know, no fork in this category has been proposed in practice.

Cheapening Ethereum Checks

One of the natural “immunities” of Ethereum to soft forks (and thus natural vulnerabilities to attack) comes in the form of its generally expensive checks.  These checks exclude the safest type of soft fork, which requires its invalid transaction checks to be cheap.  A natural question is thus is it possible to cheapen Ethereum checks?

The answer is obviously yes.  Some types of checks, even on Ethereum, are inherently cheap: the address that initiated a transaction, the size of a transaction, the conformance of the transaction script to some template, and more all open up potentially safe soft forks on the Ethereum platform.  Checks can further be cheapened through analysis techniques like static analysis; scripts can easily be checked for a wide variety of properties with no false positives, banning op-codes, banning calls to certain contracts, banning certain types of storage modifications, and more.

Any property can be checked similarly by static analysis with some false positive rate. Let’s take the DAO soft fork: static analysis can simply analyze the call graph of a given contract call and check whether a DAO address is called.  For some transactions, this check may be prohibitively expensive to complete with no false positives.  In this case, the algorithm simply returns true.  The checks are therefore cheap and bounded.  The false positives may affect some users with complex transactions, though it’s almost certain that you can design an algorithm that allows all but the most obfuscated of transactions.

By accepting false positives to bound analysis costs, one sidesteps the issues mentioned in the articles linked earlier with static analysis (“But many static analyses are costly, and these costs all inherently pose a DoS vector to fight against censorship.”).

By cheapening checks, it is possible to create an Ethereum soft fork that falls under “cheap checks / easy relays”.  While this still leaves old nodes vulnerable to potential DoS, Ethereum does impose some limits on relay / mempool acceptance (like limiting the number of per-address transactions in the mempool) that may allow such a soft fork to be implemented safely.  In the case where relays remain easy, new nodes are still safe from attacks, and only old nodes are potentially vulnerable to DoS (a strictly nicer result than a hard fork, in which old nodes are pemanently DoS’d with regards to the new chain).

Soft Fork Censorship on Ethereum!

So how can we design an Ethereum fork that miners can use to censor transactions?  Well, the easiest way is to find something with some sort of network-wide relay limit, and that’s bounded and cheap to check a transaction for.  How about just banning an address from moving their coins?  By default, the geth mempool holds 64 transactions from an address (imposing bounded relays on old nodes), so censoring a particular address would likely have a negligible impact on the network.  New nodes could also entirely invalidate these transactions, rendering only old nodes vulnerable to a very weakly amplified partial denial of service.  The cheapness of these checks places the fork in the safest bounded relay / cheap checks category.

What about a fork that does the same thing as the proposed DAO soft fork?  Well, there are two ways to make it safer: cheapen the checks, or bound the relays.  The former case can be accomplished as described above, through static analysis; simply come up with a bounded check for DAO contract calls, as mentioned previously.  For every CALL opcode, use a model that doesn’t actually run the program to reconstruct the input data (simple in most cases).  If a transaction takes too long to verify, just discard it as invalid and perform the full verification when it ends up in a block, orphaning the whole block if it does end up being invalid.

Can we go even further and limit the propagation of such bad transactions across old nodes, imposing hard relays and saving old nodes from having their mempools attacked and their service denied?  One way would be by just locking up and refusing to mine the movement of any coins associated with an attempted DAO transaction, for some time period.  Old nodes only keep a limited number of transactions associated with each address in their mempool, and by requiring an attacker to freeze capital (potentially indefinitely) the requirements for performing a successful DoS are increased.

And my BTC!

Two interesting properties that Bitcoin has that make soft forks easier, and thus make Bitcoin potentially more vulnerable to miner censorship through safe soft forks, include the wide disparity between standard (relayed/accepted to mempool) and valid (able to be mined) transactions and the inherent bounds on any possible checks.

Soft forks that make non-standard transactions more restrictive (and standard to new nodes) inherently fall in the “hard relays” category (as old nodes will not relay these or accept them to mempool).  Also, because the scripting language is restrictive and has a limited number of acceptable templates, any check is inherently bounded by the maximum transaction size.  This stands in contrast to Ethereum, where a small transaction could produce an expensive check.

This standardness mechanism was explicitly intended by Satoshi Nakamoto to allow for soft forks and future extensions to Bitcoin transactions.  Forks that modify standard transactions, on the other hand, fall in the “easy relays” category (as old nodes will relay standard transactions), and are thus more difficult to make safe.  Interestingly enough, this implies that even Bitcoin carries some resistance to certain classes of forks.  The most harmful fork is also possible in Bitcoin, however, if a new template is introduced where checking for conformance becomes expensive.

What about UASF?

Another hot topic in the Bitcoin community today is the user activated soft fork.  In this model, nodes essentially activate a softfork under predetermined conditions without considering hashpower support.

I find myself agreeing emphatically with luke-jr (which for the record, on questions of technical tradeoffs is very rare):

Without at least a majority hashrate validating blocks, it is possible just a single invalid block could split the chain such that the majority continue building a most-work on that invalid block. This failure to validate a softfork is similar in some respects to a hardfork, but with one critical difference: the default behaviour of old nodes will be to follow the chain with the most-work that was valid under the pre-softfork rules. This actually *inverts* the benefit of the softfork over a hardfork, and makes a softfork deployed in such a manner de facto behave as if it had been a hardfork, IF someone ever mines a single malicious block.

Essentially, a UASF is a “worst of both worlds” scenario between hard and soft forks.  It has the worst of hard forks: if activated with under majority hashpower, trust in miners to honestly follow the protocol is absolute.  Otherwise, old nodes and new nodes are vulnerable to a complete chain split, and it is unclear whether the chain the majority hashpower (old chain) or “node fork” (new chain) supports will remain valuable.  This is a scenario even worse than a hardfork, as the majority hashpower (with no signaling mechanism to mitigate these risks) is likely to be on the “unupgraded chain”.  The risks to SPV and light clients are the same as during a hardfork, as are the risks to and undue influence of web wallets, which get to choose which soft fork to enforce for their users.

But why the worst of soft forks?  Well, only changes that could be proposed as BIP9 soft forks anyway would be supported by such a scheme.  You get all the restrictions of soft forks (excluding a large class of potential protocol upgrades which result in breaking changes), with the risk of an extra contentious hardfork if hashpower adoption never materializes.

Any attempts to rectify these problems must include some sort of hashpower signaling, at which point you have essentially reduced to BIP9 with a lower activation threshold.  Note that this also implies that UASF is no less vulnerable to miner coercion/manipulation than BIP9 forks (modulo the threshold).  A majority of hashpower can still enforce either activation (by design) or nonactivation (by censoring conforming blocks) of UASF for political reasons.  It is likely a far smaller proportion than the required majority threshold could have such influence in a divisive political climate.

Thinking about UASFs in Bitcoin in the context of our above analysis: unbounded relays are disallowed, as UASF defines a “well formed” soft fork as one not modifying standard transactions.  From this perspective it is safe.  But what about the cost of computation?  It is possible that a soft fork with expensive computation could be proposed via UASF, and this actually opens a new and unexpected attack vector!

Imagine a scenario in which I propose an unpopular soft fork, with high hidden computation costs.  Only a small fraction of nodes adopt it, after which it is abandoned by the network.  To these nodes, the soft fork may have “activated”.  I can then cheaply DoS these nodes with transactions that do not conform to the soft fork rules.  Though these transactions are valid, these unupgraded nodes will discard them as invalid, wasting computational resources on transactions that the attacker never pays fees for.  In the event of 0 hashpower support, a mempool poisoning attack with conforming transactions is also possible, as miners will not accept such transactions into mempool (nor will most nodes relay them).  Unless the targets are also mining, the attacker won’t pay fees for such nonstandard transactions.

So, any node operator adopting (or opposing) any form of UASF must remain extremely vigilant as to its activation, must prepare for the risk of a chain split, must stay informed of hashpower forking choice, and must be prepared to abandon the relevant change in the case of lack of adoption (to prevent denial of service).  This is at least as strong as the precautions that need to be taken for a hard fork, and when the additional restrictions that come with the activation mechanism are accounted for, there seems to be little case for the use of UASF over either BIP9 or a contentious hard fork.

What about fees?

One of the interesting characteristics of the proposed DoS on the Ethereum soft fork was that it pays no fees.  This raises the question of whether “Do discarded transactions pay fees?” is a relevant metric for evaluating soft fork security.  The answer: perhaps.

The case against is that none of the attacks we describe in this post pay fees.  They all rely on transactions that will never be mined, and are not considered valid by nodes on the new fork.  Because soft forks intrinsically make validation rules more restrictive, attacking that difference with a transaction considered invalid by new nodes is the natural attack model, and most attacks will not pay fees.

The case for is that it is possible to mitigate some attacks by designing a cryptocurrency in which previously-valid but newly-invalid transactions pay fees.  A simple case of this would be a soft fork permanently blacklisting coin movement for any coins that publish a bad transaction, with a new transaction type to include this “proof of bad transaction” in a block (and thus trigger the ban on all nodes enabled with the soft fork).  While this strategy may punish old nodes for not upgrading, it still falls firmly in the soft fork paradigm.

No fork, no problem

Perhaps a more interesting form of censorship that is even weaker than a soft fork is a miner tweaking their priority rules, say to mine transactions from a given address set first in any blocks.  That address would then have a natural frontrunner’s advantage in any system that considers transaction ordering or is time sensitive, like an e-ponzi scheme or a financial matching engine with a naive prioritization scheme.  Even a small percentage of hashpower implementing these rules could result in a statistically significant (and even financially profitable!) advantage for an adversary.

Conversely, miners could simply discard transactions of an address they wanted to censor without discarding blocks that contain them.  If a significant network majority implemented such an attack, that address would find themselves deprioritized to the point of potentially leaving the network.  Such an attack would be an ideal way of implementing AML/KYC-style regulations: if miners were held legally liable for mining noncompliant transactions but not mining on top of noncompliant chains, it would be still possible to degrade service substantially for some users with no fork.

So, a mining oligopoly can simply introduce censorship even with limited hashpower, even without a fork, and at low to no cost to themselves (in Ethereum, Bitcoin, and any mining-based cryptocurrency).  Similar attacks on proof of stake protocols can proceed with stakers (alone or in staker oligopolies/cartels), even if the number of coins held by these stakers is limited.  These attacks would be fully compliant with both new and old rules, and thus would be unable to be detected or punished programatically (for example in a PoS scheme involving staker deposits).

Conclusions

Despite claims to the contrary, it is thus not my opinion that Ethereum is inherently more secure to censorship against a minority of miners than Bitcoin, even with regard to soft forks.  Ethereum benefits from several incidentally convenient properties (transactions being inherently more expensive to analyze, and old nodes being inherently more permissive in their mempool acceptance/relaying) that may make properly implementing and deploying a hard fork censoring a particular target difficult, and may be categorized as censorship resistance.

All of these difficulties, however, have workarounds that would likely succeed in practice, especially if they were in market demand and users kept valuing the resulting chain.  The only defense against censorship by an oligopoly of miners on any blockchain is vigilance and network rejection through hard forks, and pro-censorship soft forks remain in the cards for the future of Ethereum.

In a sense this discussion is primarily philosophical- no cryptocurrency is inherently immune to censorship by a majority of miners on the chosen PoW (or PoS) algorithm, who can simply attack any non-censored chain users choose to value with a 51% attack.  However, a sustained 51% attack on a currency would likely permanently and completely destroy its value (and thus miners’ capital investment), whereas an unpopular soft fork may remain survivable, making this class of attacks attractive to censors who have some incentive to maintain currency value, through capital investments or otherwise.

On the other hand, users of cryptocurrencies have clear recourses against any censorship attempts – their own hard forks (especially implementing a PoW change), and the ability to access and modify the entirety of the client source make it unlikely that a network with detectable miner-imposed censorship would ever get used, and impossible that a censored network will ever completely eradicate uncensored networks.

These aspects make all open source blockchain-based cryptocurrencies inherently resistant to, and even immune to censorship on a much deeper level than could ever be addressed by any soft fork.

As for our criteria?  May it prove valuable in future soft fork design and analysis.

As always, I am happy to accept any challenges to the above claims or mental models; leave them in the comments below!

Sincerest thanks to Ari Juels and Vlad Zamfir for feedback on earlier drafts of this post!

Leave a Reply