Ethereum, Solidity and integer overflows: programming blockchains like 1970

Role of language design in exploit mitigation

On Wednesday a new vulnerability was disclosed in the implementation of some ERC20 tokens including BEC operating on the Ethereum blockchain. As far as impact goes, the flaw is about as critical as they come: unauthorized “gifting” of tokens out of thin air.  While this may have been the first time such a bug was observed being exploited in the wild on a blockchain, the type of vulnerability is far from novel: an integer overflow, rooted in the fact that most programming languages operate on numbers with limited range. Perform a calculation where the result falls outside that range and the result of that operation is no longer accurate, violating common-sense assumption. For example two very large numbers added together can produce a small number. Or two positive values multiplied may yield a negative product. This class of bugs are very well known in the realm of low-level languages such as C and C++. Combined with weak type-safety, lack of range checking and manual memory management, such flaws often provide a starting point for building a full remote-code execution exploit.

What is unusual is that the Ethereum virtual machine (EVM) design and the Solidity language made a series of bad decisions that resurrected a vulnerability class from low-level systems programming in the context of a wildly different environment intended for decentralized smart-contracts. To better demonstrate these unforced errors on the part of language & VM designers, it is instructive to compare how a low-level language such as C or x86 assembly handles overflows.

Getting by with finite integers

Suppose we are asked to sum two unsigned integers X and Y, and compare them to some other value Z. This is a common pattern in bounds checking, a defensive measure to prevent the application from reading/writing from memory outside the intended regions.

if (X + Y > Z) {
  // Limits exceeded, bail out
} else { 
  // Continue execution…
}

For extra color, let’s assume one of these values such as “X” can be controlled by an attacker, while Y and Z are constrained by the application itself. If arithmetic in C operated in the Platonic realm of natural numbers, the above code snippet would always run correctly. But these values are not represented by an idealized “integer” type that can take on any value. Instead they are limited to a fixed range, defined by the size of the integral type. This is dependent on the compilation model, which itself is tightly coupled to the hardware architecture code is being targeted at. For example, in the data-model LP64 common for Linux, the C type “unsigned int” has 32-bits while the larger type “unsigned long” can hold 64-bits. (Integral types can also be signed, further reducing the representable magnitude since roughly half the possible values are now allocated to negative numbers.) That “unsigned int” type can represent every number in the range 0 through 4294967295 inclusive. Equally important, it can not represent any value outside that range.

That poses a problem for doing math: it is possible to write expressions such as X + Y where both X and Y start out in the permitted range but the result falls outside. In other words, the operation overflows the result type. So what happens when a C program is asked to run a calculation resulting in overflow? Intuitively the options are:

1. Return the result in a different, larger integral type such as “long.” While appealing at first glance, this is not a feasible solution for two reasons. First we run out of integral types when the same trick has to be applied for “long” or even “long long,” which a recent addition. As long as the type system only has a finite number of built-in types, there will be one with the highest capacity where we run out of room. But more importantly, playing games with types will only result in converting the out-of-range problem into a type-cast problem. Typically programmers write expressions such as “sum = X + Y” where X, Y and sum all have the same type. Even if the result is magically upgraded into a wider type, it will still get shoe-horned into the original type downstream. Playing conversion games only delays the inevitable.
2. Treat it as a fatal error. In the same way division by zero results in halting the program— or more precisely, raising a signal/exception which, if unhandled will terminate the program— every overflow could result in triggering an error designed to immediately stop execution flow.
3. Undefined behavior. This is a favorite cop-out for language designers, effectively stating that the compiler is free to produce any value: the result can be 0, 42, the compiler authors’ year of birth or it may crash. All of them are valid outcomes if the behavior is deemed “undefined” according to the language specification.
4. Truncate the result in a well-defined manner and keep soldiering on.
   

It will come as no surprise to those familiar with the minimalist philosophy of C that the language opts for a combination of #3 and #4. (C++ carries on that tradition, for the most part deferring to C on the behavior of primitive types.) Overflow for unsigned types is perfectly legal and truncates the result. Specifically only the least-significant 32-bits of the result are taken. Meanwhile overflow on signed integral types is undefined. But pragmatically speaking, for most compilers and hardware architectures the result ends up being very similar to unsigned behavior: values are truncated to squeeze into the expected type. Looked another way, C programs are not working in the realm of natural numbers with their infinite possibilities. Instead they are doing modular arithmetic in a finite ring where values outside the range “wrap around” to an equivalent one modulo some power of 2.

One level below: x86/x64 hardware behavior

If this property of C looks arbitrary, going one more level down to look at how processors handle arithmetic at the hardware level may vindicate the designers. C is close to the metal, so to speak. Its constructs often map 1:1 into capabilities of an underlying hardware. Consider the common Intel x86 architecture. This architecture sports 32-bit registers and features instructions for operating on them. For example one can add the contents of register EAX to the value existing in register EBX:

add EBX, EAX

Since registers are also limited in the range of numbers they can express, executing this instruction poses the same dilemma: what happens if EAX and EBX hold values that added together would exceed the maximum integer representable in 32-bits? As with most hardware architectures, x86 adopts the convention of doing modular arithmetic: operations are implicitly performed modulo 2**32 (or some other appropriate power of two when working with 16-bit or 8-bit registers.) Nor is that a quirk limited to Intel: most hardware follows this pattern.

Defensive programming: hardware vs software

Given that context, it is hard to fault C for following the same model: it allows using efficient CPU instructions to perform arithmetic without having to double-check or adjust the results spit out by the processor. And while C is rarely accused of being a high-level language, many other languages that followed including those targeting virtual machines such as Java, have also taken the path of least resistance by going along with the hardware. Languages like Python and Scheme where integers have arbitrary precision by default are the exception, not the rule.

That said, there are some crucial differences in how arithmetic works at a low-level which are missing from the abstractions offered in high-level languages:

• Multiplication has special case behavior of using the “type expansion” idea. Specifically product of 32-bit integers are in fact written into the pair of registers EDX and EAX, to accommodate a full 64-bit product.
• CPU has a flags register that contains special flags updated based on the result of the last operations. This includes an overflow flag. Even more conveniently, the x86 instruction set contains conditional jumps based on whether that flag is set: JO, short for jump-on-overflow. That makes life easy for a programmer working in assembly language to detect and respond to overflow conditions with just 1 additional instruction— which for all intents and purposes is an unconditional jump, because the branch-predictor will correctly guess that an overflow will not happen in the common scenario.

By contrast checking for overflow in a language such as C or Java is far more kludgy because these low-level signals are missing. There is no facility provided by the language itself for dealing with overflows in an efficient manner. Options are:

• Perform an extra arithmetic operation first to check if overflow will happen. For example, we can subtract one operands from the maximum representable value and if that difference is larger than the second operand, addition is guaranteed to overflow.
• Sanity check the result after performing the operation, by comparing the result against one of the original operands. (Leveraging the observation that an overflow condition exists for unsigned addition if and only if the alleged sum is less than either one of the operands. Note that the rules are a lot more complex for signed arithmetic.)
  

Many libraries exist for doing arithmetic safely with such overflows checks included, but they trade-off safety for kludgy syntax and readability. Instead of writing a straightforward mathematical expression such as “result = X * Y + (Z * scale) + offset” one must replace each binary operator by a functional call, and potentially conditional checks for the overflow status of that particular subexpression. C++ with its support for operator overloading can at least overcome the syntactic problem, since one can design a replacement for every integer type along with  that performs overflow checking. However in the absence of direct compiler support or very diligent use of inline assembly, these user-defined substitutes will be very inefficient compared to native types.

Compiler features to the rescue?

Where the language falls short, compiler authors can sometimes step in. For example GCC has an option called trapv that will raise a trap when operations on signed integers overflow. This is an important distinction because C already considers such behavior to be undefined— crashing the program is just as valid as truncating the result modulo 2**32. But there is no corresponding option to treat overflow of unsigned integral types as a fatal condition: no “correct” compiler can do that because such overflow is perfect legal C and even explicitly relied on to implement functionality such as hash-functions and cryptographic algorithms. (A research paper from 2007 explores the idea of instrumenting existing binaries to fail on unsigned overflow, confronting exactly that problem of having to identify code that deliberately relies on truncation.)

Solving the problem for signed integers may sound good enough except for the fine-print in C conversion rules: in any operation involving a mixture of signed and unsigned operands, the signed input gets typecast to unsigned and arithmetic performed on unsigned values. In other words, introducing any unsigned value into a calculation voids the overflow check.

Solidity and Ethereum: the missing defense

EVM features large 256-bit words internally and has instructions to perform arithmetic operations on these values. Solidity in turns offers integral types up to 256-bits for programmers to use. But as the preceding discussion suggests, one can not “outrun” integer overflow vulnerabilities by adding bits to integer types any more than buffer overflows are fixed by adding more RAM. (Going from 32-bit →  64-bit architecture has expanded addressable memory to 256 terabytes but that did not spell the end of memory corruption bugs.) As long as resources are finite and attackers allowed to sneak inputs into an operation, it is possible to have an arithmetic overflow.

When it comes to defensive measures for avoiding overflow vulnerabilities, it turns out both platforms are worse than their ancient counterparts. In Solidity operations on integral types silently wrap-around by default in the event of an overflow. There is not even a compiler flag (at the time of writing) to treat overflow events as critical error— the equivalent of 10 year old “trapv” flag in GCC. At the processor level, EVM has no efficient mechanism for tracking overflow state or making decisions conditional on whether a recent computation resulted in overflow. There is nothing comparable to the x86 overflow flag and attendant condition branching instruction. Strictly speaking this is not required; a compiler can synthesize overflow checks with existing EVM instructions, patterned after the kludges used for C. But intrinsic EVM support could have made it that much easier.

For historic perspective, the x86 architecture dates back to the 1970s. So does C, designed as a low-level systems programming language with the explicit goal of closely mirroring the underlying hardware. (C++ arrived on the scene in the early 1980s, adding object-oriented paradigms while continuing to pay homage to the efficiency requirements of C.) Ethereum started four decades later with a completely different use-case: programming smart-contracts on a blockchain, which is an extremely inefficient system for computation and where correctness matters far more than shaving a few virtual cycles. Likewise, Solidity as a language for writing smart-contracts started from a clean slate. Unlike C++ it did not inherit the baggage of having to support existing C code with assumptions about how integer arithmetic words. It’s a tribute to the short-term memory of computer science that a modern programming language designed with the singular purpose of building applications on a blockchain platform— where bugs can result in significant monetary losses— still ended up perpetuating an ancient vulnerability class.

CP

 

 

Money for nothing: Bitcoin Cash & the economics of hard-forks (part II)

[continued from part I]

Obstacles to hash-rate equilibrium

There are important caveats to the preceding argument. First we made a simplifying assumption in equating “mining rewards” to coinbase rewards. That neglects additional earnings from transaction fees collected on every payment taking place in that block. For much of the history of Bitcoin, this would have been a reasonable assumption: coinbase rewards dominated fees. In fact this dynamic made possible the extremely low fees that inspired many an optimistic pundit to sound the death-knell of other payment systems that charge usuriously high transaction costs in comparison. Over time as blocks became increasingly congested with scaling solutions stuck in a political quagmire, fees have continued creeping up. At some point in early 2017 the network achieved a state of inversion: transaction fees exceeded coinbase rewards in their contribution to overall mining revenue. That dynamic will continue to be exacerbated as the reward decreases periodically through the “halving” events baked into the bitcoin monetary supply.

That said, the decision criteria for choosing a chain is the relative expected reward per block. Imagine one chain has massive congestion and very high fees (consumers racing to out-bid each other to get their transactions through) while another chain has plenty of spare capacity in its blocks, with correspondingly low fees. That second chain is less appealing to miners, all else being equal and may not merit switching even if it appears to be trading at a premium based on coinbase rewards alone. On the other hand, the congested chain is also much less appealing to users: why continue paying exorbitant fees if you can transact on the other other chain faster and at lower cost? (After all the raison d’etre of Bitcoin Cash is ostensible adoption of 2MB blocks that squeeze more payments into one block, with reduced fees expected to follow as natural side-effect as artificial scarcity is eliminated.) It is unclear to what extent lock-in effects exist for cryptocurrencies. But assuming that some users are free to defect, the second blockchain may appreciate in value over time relative to the first. As more people conclude they can reap greater benefits transacting on that chain, they will bid up the value of the currency (and incidentally, start filling up those blocks with more transactions.) From this perspective, a miner is sacrificing short-term revenue by accepting lower transaction fees in exchange for anticipated future increase in value of accumulated reserves, due to better economics/features offered by the forked chain.

Short-term instability

The second caveat is that the analysis focuses on steady state, after block times have adjusted. As pointed out in the hypothetical scenario of the 1% miner, the introduction of new hash power into a network that follows Bitcoin-type rules leads to temporarily increased profitability for all participants. While the system has mechanism to adjust mining difficulty in response to available capacity, those adjustments take effect slowly. They happen approximately once every 2 weeks in the case of Bitcoin, and use an unweighted average over that time. If the sudden influx of hash power took place in the middle of that window, the algorithm will under-correct: it averages out the hash power before and after the arrival of a new participant, instead of giving higher precedence to more recent history. It may take up to two adjustment periods to fully correct for the spike. The good news is introduction of hash power also hastens the arrival of  adjustment, which is measured in number of blocks. Sudden removal of hash power on the other hand leads to a destabilizing cycle: blocks take longer to mine and the adjustment period to correct that itself will take longer to arrive. Because that reduces the profitability of mining, it may inspire additional defections resulting in even longer block times in a vicious cycle.

Bitcoin Cash experienced a relatively mild version of that phenomenon after the hard-fork: because the minority chain split off with the full difficulty level of Bitcoin proper but only a small fraction of its hash rate, blocks were extremely slow to arrive at first. Granted BCH proponents had anticipated this problem and built an emergency adjustment feature into their protocol. But even that proved insufficiently responsive to correct for the deficit initially. Adding insult to injury, the mechanism over-corrected as miners began jumping into BCH mid-August to exploit the arbitrage opportunities. As a result difficulty and amount of hash-power began to experience wild fluctations two weeks after the hard-fork, with BCH exceeding BTC in hash-rate at one point. (So much for the simple rule “the chain with the majority hash-power is Bitcoin” proposed for anointing the winner after a contentious hard-fork.) To summarize: in the short-term there can be significant divergence from predicted equilibrium due to the relatively slow adoption of mining difficulty in comparison to how quickly network capacity can change due to sudden entry or departure of miners.

Animal spirits all the way?

One unresolved question remains: if market value of a cryptocurrency can drive rational miners to participate in supporting that blockchain, what gives rise to that valuation in the first place? Is there causality in the other direction where miner support (expressed in actual hash-rate, not press releases and blog posts) is sufficient to prop up market value? Consider the initial point where Bitcoin Cash split off from Bitcoin, and a coalition of miners accounting for 10% of total rate made a credible pledge to mine BCH regardless of market pricing. It could be that they have a grievance with BTC, they are being otherwise being compensated by participants with an axe to grind or they are simply irrational. Does that information allow investors to price BCH in relation to BCH?  Proportionality based on hash-rate does not make sense. Blockchains involve winner-takes-all dynamics and network effects. A compatible blockchain with 1% the hash-rate of Bitcoin does not have 1% of its security or censorship-resistance: since many existing Bitcoin mining pool have more power than that, any one of them could easily overpower the minority chain to execute 51% attacks.

Similarly a cryptocurrency with 1% of user-base of another one does not have 1% the utility: it would be the equivalent of an alternative social network that only 1% of your friends participate. From these perspectives, BCH started out with a major disadvantage. Very few wallets support it out of the gate; the chances of being able to pay a friend in BCH was much lower compared to BTC. Most exchanges announced they would not open up order-books for BCH; it will be more difficult to convert BCH into fiat or other cryptocurrencies. While merchants have made symbolic gestures of accepting Bitcoin to signal their “forward-thinking,” no one has put out press releases touting BCH acceptance. Given that one BCH was valued at hundreds of dollars in the immediate aftermath of the fork even before the dust settled, its current hash-rate can be explained as consequence of miner incentives. The more troubling question for future hard-forks is: given the long odds of competing against the main chain, how any splinter fork can achieve that market valuation in the first place.

CP

Money for nothing: Bitcoin Cash & the economics of hard-forks (part I)

Pricing a parallel universe

Over a month has passed since Bitcoin Cash has forked from the main Bitcoin chain. Short-lived anomalies observed in the aftermath of the split, such as very slow mining times due to widely miscalculated block difficulty, have mostly been resolved. While most exchanges have not opened order-books for BCH, sufficient liquidity exists and trading continues at non-zero prices. So much for the predictions of “experts” who projected a rapid decay to zero once the blockchain came up to speed, allowing people to move funds in any reasonable time frame. (Deja vu? Back in 2016 on the verge of the Ethereum hard-fork to bailout the DAO, so-called “experts” also predicted the minority chain Ethereum Classic would die out quickly.)

In fairness, the majority of Bitcoin proper trading does not hit the blockchain either, taking place on the internal ledgers of exchanges. That alone should have been a clue that mobility/velocity of fund movement can not be the deciding factor in determining market value of a cryptocurrency. But are there systemic ways of pricing a splinter faction such as Bitcoin Cash relative to its main chain?

BTC itself has significantly appreciated since August, going from below $3K to nearly crossing the $5K milestone before taking a hit in response to news from a crackdown in China. BCH has fluctuated significantly but continues to hold a valuation in the hundreds of dollars. In other words: the price of bitcoin after the fork plus that of bitcoin cash greatly exceeds that of bitcoin before the fork. Consider that every person who owned bitcoin before the fork still owns the same amount of bitcoin, plus a corresponding quantity of bitcoin cash.

On its face, the hard-fork has created value out of nothing.

Creating a new cryptocurrency out of thin air

Not to shabby for an initiative with modest beginnings as a strategic bluff to another threatened soft-fork. To recap: in response to the lukewarm reception by Bitcoin miners to the segregated witness feature, one of the factions in the never-ending scaling debate proposed a user-activated soft fork or UASF. This approach would effectively force the issue with miners, by disregarding blocks which do not include support for their favorite pet-feature. In response, an opposing faction threatened a user-activated hard-fork (UAHF) that would force miners to commit to a different criteria by disregarding chains that do not include support for their favorite pet-feature, namely 2MB blocks. UAHF was more deterrence than a coherent scaling plan: its proponents painstakingly pointed out the plan would only be invoked if segregated witness activation did not take place cleanly. Last minute developments appeared to render that unnecessary: segregated witness and large-blocks were merged into a Franken-design under the controversial “New York agreement.” Enough miners signaled for that version to reach its activation threshold. Crisis averted? Not quite: one die-hard group decided to run with the UAHF banner regardless of existing consensus, proceeding to create a new fork that supports 2MB blocks—Bitcoin Cash.

Before we go on to conclude that hard-forks are an unambiguous boon to the ecosystem and expect to have one every week, consider a few alternative explanations for the outcome:

• Speculative bubble in the broader cryptocurrency space, a point many commentators have raised warnings about. No one has accused cryptocurrency investors of being too cautious in this day and age of oversubscribed ICOs. Bitcoin Cash may have been perceived as the next gold-rush by aggressive investors looking for another asset class to get in on the ground floor.
• Creative conspiracy theories: secret cabals committing to a price floor for BCH in order to generate demand from exchanges or motivate miners to commit hash power. This could explain why BCH had a non-zero valuation but it can not account for why BTC itself started on a steady upwards trajectory.
• Here is a more charitable interpretation for investor psychology: the community breathing a collective sigh of relief after segregate witness activation proceeding relatively “cleanly” by some definition. While the UAHF hard-fork came out of left field, it had incorporated lessons from past times when the network played a game of chicken with hard-forks. There was no risk of the alternative chain collapsing back on the main-chain, thanks to the deliberate introduction of an incompatibility at the fork point. There was replay protection: transactions from the main chain could not be broadcast on the alternative chain. (That was a critical lesson the Ethereum community learned during its DAO debacle. Compatibility between chains resulted in problems managing funds independently: by default sending ETH also resulted in sending ETC because someone else could—and did, as a matter of fact— take the transaction from the original chain and replay it on the Classic chain.) According to this explanation, bitcoin prices were artificially depressed before the fork due to collective investor anxiety and successful completion of the fork simply erased those worries.

Hash-rate follows valuation

Beyond the particular motivations that support the current price structure, the relative value of Bitcoin Cash to Bitcoin makes for an interesting experiment in comparing predictions from economic theory with observed market behavior of the participants. That goes for miners too: while it is common to accuse investors of tulip-mania irrational exuberance, miners are supposed to be rational actors maximizing subject to well-understood economics of mining. While Bitcoin Cash transactions are deliberately incompatible to Bitcoin transactions, the proof-of-work function used to mine blocks is identical on both sides. That means the chain split presents each miner with a continuous decision point: mine BTC, mine BCH or perhaps some mixture of both by dedicating partial capacity.

The relative profitability of mining—defined as rewards to amount of hash-rate expended— for BTC/BCH has fluctuated wildly during the initial few weeks. As profitability of the BCH blockchain soared, more miners were tempted to jump ship. Eventually the pendulum swung too far and BCH had too much competition, a form of the Yogi Berra saying applies: it is too crowded, no one mines there anymore. But the graph shows an unmistakable trend of converging towards 100%, the point where both chains are equally profitable. This same behavior was observed in the aftermath of ETH/ETC split. The price ratio between the chains was approximately equal to their difficulty ratio.

Is there a relationships between hash-rate and price? It is straightforward to argue for causality in one direction when two chains have compatible proof-of-work function. That compatibility is critical because it allows repurposing mining power. Recall that the majority of commercial mining is done using highly specialized hardware that has been painstakingly optimized for a specific proof-of-work function. It can not be used to support mining on a different blockchain unless that blockchain also uses the same proof-of-work. So an Ethereum miner can not easily switch to Litecoin without significant capital expense in acquiring new hardware, but they can turn around on a dime to mine Ethereum Classic using the same fixed assets.

This interoperability creates an opportunity to arbitrage hash power between blockchains. Suppose BTC is trading at $4000 and a mining pool has 1% of the hash-rate. Neglecting transaction fees, this pool would expect to collect on average 1% of the block reward of 12.5 BTC which comes out to $500 in fiat equivalent. Now suppose that BCH has one-tenth the total hash rate of Bitcoin network being a minority chain, but is valued at one-eighth of bitcoin at $500. In other words BCH is trading at a premium compared to its hash rate. In that case our mining pool can improve its profitability by shifting all power to mine BCH. After switching sides, the miner now accounts for roughly ~9% of the newly expanded BCH network capacity. That means on average they can count on collecting 9% of the 12.5 BCH reward per block. Converted to USD that comes out to ~$563. In other words defecting to BCH when it was trading at a premium to its hash-rate has improved the bottom line. (In fact until difficulty adjustment takes place, their actual profitability will be even higher because the network is still operating under the assumption of its original capacity. Blocks will arrive faster, so the reward per unit time is even more lucrative— considering that primary operational expense for mining is power consumption, that is a more relevant metric.)

Yet the same calculus does not work for a different mining pool which starts out with 5% of total hash-rate. That pool is looking at an average $2500 per block in earnings while operating on the main chain. Switching over to BCH, they become the big fish in a small pond, now accounting for one-third of the total BCH rate— and in the process posing a risk to decentralization due to having achieved critical mass for selfish-mining. But their expected earnings in steady state actually drops to less than $1700 USD per block. What went wrong? Shifting that 5% of mining capacity to the greatly under-powered BCH network destroys the condition that gave rise to the arbitrage opportunity in the first place: with the infusion of new hash power, BCH is no longer trading at a premium compared to its hash rate. (Of course this does not mean larger mining pools can not take advantage of the opportunity: it just means they have to shift some fraction of their resources over to BCH instead of their full capacity.)

Bottom line here is that rational miner behavior gives rise to a dynamic where hash-rate is naturally allocated between compatible blockchains in response to market valuation of those currencies. Put succinctly: hash-rate follows valuation.

[continued]

CP

 

Chain-switching attacks and Bitcoin Cash: improving the odds

Incentives for withholding hash power

Can it make economical sense for a Bitcoin miner to strategically withdraw hash-power from the Bitcoin network? It is easy to imagine situations when a miner may choose to power down obsolete hardware that has become too inefficient, when the expected gain from operating those rigs does not justify the electricity costs. But could it make sense to power down perfectly competitive mining rigs suddenly and turn them back on at a different time in the future?

Suppose Bob has 20% of mining power and decides to completely quit mining at the end of the current adjustment period. Assuming that is the only change in the mining landscape—and this is a big leap of faith, considering that other participants may have spare capacity waiting on the sidelines— the result is that for the next adjustment period of 2016 blocks, the remaining miners will experience a slowdown. Difficulty level has not adjusted but only 80% of mining capacity remains, with the result that blocks will arrive 25% slower than average. The adjustment period will take correspondingly longer than the usual two weeks, after which point the difficulty is reduced to 80% of the original. Now if there were no other changes to overall mining capacity, the system would revert to its usual pace of producing blocks, since difficulty and hash-rate have once again achieved parity. But in comes Bob out-of-left field, powering up all of his mining rigs once again. Now difficulty parameter is too low by 20%, or equivalently the network runs a 25% surplus hash-rate over the last estimate. Blocks will arrive once every 8 minutes on average and this state of affairs will continue for a shorter-than-usual adjustment period of ~11 days. At that point difficulty could have adjusted back to observed hash-rate, except Bob is not done: once again he powers down his entire operation, leaving the network with an overestimate of difficulty. This results in a cycle of alternating periods where difficulty is overestimated and underestimated, with blocks arriving too fast or too slow. This is the scenario outlined in a SecureList/Kaspersky blog post, which goes on to argue that  miners have an incentive to game the system by strategically moving hash-power in and out in this fashion.

Economics of timing the (mining) market

Putting aside the question of whether other miners waiting on the sidelines would jump in to compensate if they saw difficulty levels fluctuate, let’s analyze this situation from the economic perspective of the individual miner (more likely, mining pool) we will call Bob. During the 17.5 days when his operation goes quiet, Bob collects no mining rewards at all. This is a lost opportunity cost. Mining has both fixed costs in the specialized rigs and data-center infrastructure, as well as marginal costs in electricity powering all that energy-hungry hardware.  The good news for Bob is that during the next period when he is back to business-as-usual, he still has 20% share of overall network capacity. He collects the exact same proportion of rewards as before. The only difference is that those rewards arrive faster: all of those blocks come in 11.2 days instead of 14. Accordingly his economic competitiveness measured in bitcoins earned per second has improved.

So far, so good. But how does that compare against the idle time? That turns out to be the main drawback. It may look like Bob is screwing over the competition by temporarily withdrawing: everyone else is left to mine at artificially high difficulty for longer than usual. But this is illusory: the remaining players are also collecting higher share of rewards than usual. (To take one example, if hash-rate was equally distributed between 5 mining pools, after one quits each of the remaining pools will see their share increase from 20% → 25%.) While the network is producing blocks 25% slower than usual—from the standpoint of miners, their block rewards are correspondingly arriving less frequently— all of the miners left in the game are also collecting 25% more reward when they successfully mine a block. Their economic productivity measured in bitcoins collected per second has not changed at all. That means profitability has not changed either: regardless of what they are paying for electricity, continuing to mine at the artificially higher difficulty produces the same gain/loss per unit of time as before. (Again, assuming everything else is held constant: while block rewards are fixed, mining fees are variable and could go either way. A congested blockchain with slower confirmation times could result in fewer people attempting to transact, putting downward pressure on fees. But conversely it could mean that there is ever more urgency to get mined into the next block, resulting in higher fees.)

Meanwhile Bob receives diddly-squat during the entire time his rigs sit idle. That represents a complete loss of productivity for an even longer period of time; recall that the next adjustment period of artificially high-difficulty lasts longer than 14 days as remaining miners are struggling to produce blocks. That extended stretch of 0 bitcoins per second more than counters any advantage sustained during the easy-mining period. Given only the Bitcoin blockchain, it is difficult to see how strategically timing entry and exit out of the mining operation could result in improved economics for the miner playing that game.

An alternative chain is the playground of idle miners

Unless of course, the miner can find something better to do with all of that idle hardware sitting around? Enter Bitcoin Cash. Given two blockchains with compatible proof-of-work functions (in the broadest sense, meaning that hardware designed to mine for one can be converted to mine for the other without significant loss of efficiency) a new strategy becomes available to miners: instead of idling their rigs, they can simply switch over to the other chain.

The effectiveness of that strategy depends on several variables. Perhaps the most obvious one is the relative profitability of mining the alt-coin compared to Bitcoin itself. In general there is no a priori rule that mining alt-coins must be equally profitable in terms of rewards to hash-rate invested. While cost of hash-rate is relatively predictable in hardware costs and electricity, the rewards are highly volatile given the sharp fluctuations in cryptocurrency markets. More importantly, given that other blockchains such as Ethereum employ a different proof-of-work function than Bitcoin, it is often not possible to simply redirect existing hardware to mine an entirely different blockchain.

Restricting our attention to chains with compatible proof-of-work functions, there is a market dynamic to keep their profitability at approximately the same level in steady state. If a significant disparity exists, miners can jump ship to mine on the other chain. That incentive applies even to miners ideologically committed to a particular currency. If a miner only cares about Bitcoin but sees an opportunity to earn the equivalent of 10% more USD on a different chain with sufficient liquidity. The rational choice is:

• Mine that alternative currency
• Immediately cash out to all rewards to USD or other fiat currency
• Use the proceeds to buy back bitcoin on the open market

Provided the discrepancy exceeds transaction costs of making those trades, that strategy still earns more bitcoin for the adaptable miner. In the case of Bitcoin and Bitcoin Cash, relative profitability has been fluctuating wildly, partly because BCH difficulty adjustments have been very slow to kick-in after the fork. But it is plausible that in steady state—assuming the forked chain, survives that is— profitability will remain in the same neighborhood, if not exactly equal.

The other wildcard is how difficulty adjustments work on the alternative chain. Recall that sudden introduction/departure of hash-power from the network has a transient effect on the overall profitability of that blockchain. This effect is short-lived as long as the difficulty level is adjusted to account for the total mining capacity expected. With some exceptions around edge-cases (such as the rapid, emergency adjustments to deal with the massive drop in the afterwork of the hard-fork) Bitcoin Cash has similar rules to Bitcoin around scheduling: the network aims for 10-minute intervals between blocks and adjusts difficulty after every 2016 blocks to hit that target. However these two chains will not necessarily agree on when each adjustment period starts or ends. Even in steady state, they are likely to appear as two out-of-phase waves with the same frequency rather than perfectly synchronized ones.

Luckily for hypothetical miner Bob engaged in a chain-switching attack, synchronization is not necessary. After withdrawing from mining capacity from BTC, the miner can simply switch to mining BCH starting at some arbitrary point in the middle of BCH adjustment period. (Note at the time of writing, overall BCH hash-rate is much lower compared to BTC. If we continue using the 20% figure as before, that amount of BTC capacity switching sides would completely dominate the minority chain, effectively constituting a 51% attack.) Until that period completes, the network is operating at increased pace, doling out rewards too fast because the presence of the new actor has not been factored into the difficulty calculation yet. Everyone, including Bob responsible for this temporary spike, is collecting BCH at a rate faster than what one would predict given their share of mining power. After the adjustment, target block-time is restored and expected reward per unit time also gets trimmed for everyone. But miner Bob is continuing to earn some reward, albeit in a different cryptocurrency. He can continue doing that until BTC chain readjusts its difficulty to create an environment where jumping back in is appealing again. This improves the economics of chain switching compared to simply idling all rigs for an adjustment period.

But counteracting that is another factor: the act of Bob completely withdrawing from BTC and redirecting all capacity at BCH has lowered the relative profitability of BCH. There is now more hash rate chasing the same amount of block rewards in BCH, while BTC is experiencing a competitive vacuum. (This assumes BCH and BTC prices have not magically moved in the opposite direction to correct for hash-rate. While hash-power naturally follows valuation by miners voting with their rigs, it is unclear what causal mechanism exists for market-price of a cryptocurrency traded on multiple exchanges to adjust to gain/loss of hash-power.) That may in turn create incentives for hash-power to naturally defect from BCH and switch back to BTC, compensating for the original drop.

To summarize, while it appears that each miner can cause network instability & fluctuation in block times by strategically exiting/reentering the market, that behavior is unlikely to be more profitable than the simpler strategy of always mining at the same rate 24/7. The introduction of a second compatible chain however does alter the dynamics, by compensating for lost income during the idle time. But even in that scenario,  it is unclear how other actors would respond because a natural equilibrium exists for the distribution of hash power between compatible chains, given rational miners with freedom to choose based on pricing.  More research is necessary to shed light on these competitive dynamics.

CP

 

Tabs, spaces and the straitjacket of coding conventions

(An attempt to account for StackOverflow survey results)

In June StackOverflow published one of the more surprising results from their developer survey: “Developers Who Use Spaces Make More Money Than Those Who Use Tabs.” This is a counterintuitive result, considering that the question of spaces and tabs has always been considered a matter of personal preference, with no impact on the actual quality of code written. So much that this debate made it into an episode of “Silicon Valley,” a show predicated on repackaging the follies of our technology sector for popular consumption. Yet here is a survey from highly-regarded website with a statistically significant number of respondents, suggesting that this superficial stylistic difference affects career prospects. It would be akin to learning that traders who wore suspenders generated 10% more profits than their colleagues wearing belts. What is going on here? After all, switching from tabs to spaces is trivial and can be automated with a text editor. Should engineers around the world embark on a global search-and-replace across every file to give themselves a raise?

To their credit, StackOverflow authors realize this claim sounds absurd on the surface and try to find alternative explanations that could account for the observed difference in terms of variables that . Going back to our previous parallel situation drawn from finance: if there was a convention that people trading commodities wear belts while those speculating in equities prefer suspends, that would account for the difference in observed returns. In effect the belt/suspenders question is not a casual factor; it is just a proxy for an underlying “hidden” variable which influences the outcome in reality. If we could perform a controlled experiment where fixed-income traders were all given a wardrobe make-over and switched to suspenders, they would sadly not turn into rainmakers for their employer.

Yet in the case of tabs vs spaces, that observed difference in salary persists after controlling for obvious variables such as choice of programming language and specific area of development such as web/mobile/embedded. Across every category, the difference is in the same direction: those using spaces earn more. More importantly the StackOverflow data is looking at median salary instead of averages. Compared to an average, that statistic is much less susceptible to being skewed by a handful of “space” fanatics in a particular niche (such as ICO development) with outsized numbers.

Here is an alternative explanation: for a large number of developers, the choice of tabs vs spaces is not a reflection of personal preference but dictated by the coding conventions of their project. Observed tabs/spaces difference would then follows naturally from intrinsic differences in compensation between organizations who adopt strict formatting guidelines (specifically, mandating spaces) and those who are relatively liberal about formatting.

Coding style guides are common in large organizations to maintain consistent standards across their coding base. These standards can cover everything from very high-level/substantial topics such as language features permitted to trivial ones such as the placement of braces and line-breaks. For example, here is the Google C++ guide which opines on everything from use of namespaces to the evils of virtual inheritance and operator overloading—verboten at Google. (In fact by disallowing most advanced C++ features, this style of coding effectively turns C++ development at Google into a glorified C-with-classes circa 1990s.) The goal of consistency is to make it as easy as possible for engineer Alice to dive into a new code-base and review/improve code written by engineer Bob. If Bob was allowed to use arcane language features or esoteric design patterns in his work, it would be a lot more difficult for Alice to come up to speed and contribute. A more cynical interpretation is that conventions make engineers interchangeable, helping the organization at the expense of individual employees and overall productivity.

Indentation falls into that second category of “cosmetic” changes that have no impact on the semantics of code: how far each nested block of code is offset from the enclosing block, and whether that layout effect is achieved by using a single tab character or some fixed number of spaces. (Granted there are languages such as Python where indentation does change the meaning of  what code does. But even in that case, it remains immaterial whether that information is conveyed using spaces or tabs.)

Now if Alice is employed by a large company that mandates spaces while Bob is working for a scrappy start-up with laissez faire approach to formatting, they may end up using different indentation style even if Alice started out with no preference either way. The difference in compensation could simply reflect the underlying difference in the type of organizations that adopt coding conventions, assuming such conventions are more likely to favor spaces over tabs— as in the case of C++/Java/Python at Google or C# at MSFT. In that case the higher earnings for the spaces camp could be an artifact of large, established employers relying on high cash compensation while small start-ups lean heavily on equity such as stock options to attract candidates.

There is an ambiguity here in the phrasing of the survey question: whether it is asking for preference or status quo. The question “spaces or tabs” can be interpreted two ways:

• Are you currently using spaces or tabs?
• If you had your druthers, would you prefer to use spaces or tabs?

The first question is influenced by choice of employer, and the apparent correlation to salary could then be explained away as an artifact of a handful of large, successful tech companies having settled on coding conventions with spaces. The second is strictly a matter of individual preference; it would indeed be a very surprising result if it turns out that developers who had an innate preference for using spaces, absent any organizational mandate, somehow proved to be better compensated. (Of course it is also possible that company-mandated coding conventions are over time embraced and internalized by individuals subject to abiding by those rules. Coders who start out without any preference may later come to decide that there is “one-true-way” of indentation, namely the one they have been using all along.)

CP

The optimal Ethereum heist: attacking the Parity wallet (part III)

[continued from part II]

To recap: there are several mysterious questions around how the attacker(s) who discovered a critical vulnerability in a popular Ethereum smart-contract went about exploiting that flaw to steal funds:

• Only exploited some of the vulnerable contracts, even though all targets are equally easy to locate
• Skipped contracts containing more funds in favor of going after lower-value targets with lower returns

At first, this does not seem consistent with an attacker driven by profit motivation. Armed with a 0-day exploit, the optimal strategy is systematically plundering the richest targets first— on the assumption that once people get wind of the vulnerability, they will race to defend their contracts, reducing the chances of successful exploitation.
But on second thoughts, the attacker may have been operating with another constraint in mind: potential PR backlash against the theft. Consider the three contracts that were targeted:

• SwarmCity: a self-described “decentralized commerce platform” which raised funds with a resale of its SWT tokens.
• Edgeless Casino: Online gambling website operating on the ethereum blockchain, which crowdfunded itself by issuing EDG tokens.
• æternity: a platform for “scalable smart contracts interfacing with real world data” according to its website. The development of this project was also funded by, you guessed it, an initial coin offering. [ https://www.coinstaker.com/initial-coin-offering/aeternity ]

Compare this to some examples of wallets that were left untouched in spite of having significant holdings:

• BAT: Basic Attention Token, affiliated with the Brave browser project. Brave aims to shift the dominant revenue model for websites away from advertising (which leads to a race to the bottom in privacy, with increasingly invasive data collection on all users) and towards voluntary contributions powered by micro-payments.
• ICONOMI: A meta-platform for managing other cryptocurrency assets
• cofound.it: This one has a buzzword salad of “distributed global platform that connects exceptional startups, experts and investors worldwide”

There are at least two theories on why this group was spared and the former unlucky group exploited, and both hinge on the same premise: the possibility of a hard-fork that would reverse all theft transactions.

Recall that this drama played out once before: the DAO contract had raised close to $150M in ether at the prevailing exchange rates when it was successfully attacked, with the perpetrator walking away with $80M of those funds collected from investors. Or more precisely, they would have walked away with that tidy sum were it not for the Ethereum Foundation stepping in with a deus ex machina. In an ironic echo of the 2008 crisis which partly inspired Satoshi’s development of Bitcoin— too-big-to-fail institutions on the verge of collapse bailed out by intervention-happy regulators eager to rescue the ecosystem at all costs— the Foundation engineered the blockchain version of historical revisionism, returning stolen funds back to the DAO. At least that was the objective, but it did not exactly result in a clean undo. While the majority of hash power went along with this act of deliberate tampering with the ledger, a splinter faction to continue running with the original version which became the altcoin Ethereum Classic.

That history raises an important question for any enterprising criminal contemplating large-scale mayhem on the Ethereum blockchain: what is the threshold for a hard-fork? At what point does the Foundation deem a particular address as too-big-to-fail? Is there a version of the Federal Reserve “systemically important financial institution” criteria that decides which ones merit a bail-out in case of security breaches? There are three plausible theories:

1. Value-at-risk. DAO breach resulted in the loss of $60M before the funds were returned with the bailout. The Parity attack netted ~$30M, suggesting the attacker stopped about half-way to that previous mark. But these numbers are deceptive because the price of Ether in USD has appreciated more than 10x since the DAO debacle. So measured in native currency, the current theft is dwarfed by the DAO.
2. Public perception of the affected entities. The Brave browser presumably enjoys grass-roots support, because it is an underdog battling commercial behemoths (MSFT IE/Edge & Google Chrome) on behalf of users in a bid to improve user privacy online. This is exactly the type of project everyone wants to cheer on to a successful launch. Edgeless Casino is a dodgy gambling site sitting in a murky area of regulation that no one will shed any tear over. Taking away money used to fund Brave development would likely result in a public outcry. Robbing the casino would merit a shrug or even inspire schadenfreude.
3. Old-school crony capitalism: only individuals with close connections to the Ethereum Foundation get bailed out. Unlike previous cases where public information about wallet owners can be used to make an informed assessment, this relationship is more difficult for an attacker to gauge ahead of time.

Either way, the attacker succeeded by this criteria. No one is seriously contemplating a hard-fork to reverse this particular theft. (In fairness, the DAO had a built-in safeguard to stop funds movement for several weeks after the theft. That feature greatly simplified the intervention: because the funds could not move around or taint other addresses, required blockchain edits to undo this action were limited to a few transactions. By comparison, the Parity wallet thief is free to move funds around. Correctly undoing the breach may involve reversing not only the original theft transactions but also every other transaction dependent on it in a ripple effect.

So it turns out that crime on the Ethereum blockchain does pay after all—but only when the perpetrator has the good sense to stop short of crossing the line that would trigger a hard-fork, even if that means deliberately following a seemingly “suboptimal” attack strategy. The optimal Ethereum theft is one that walks away with an amount just below the threshold of value/significance/popularity that would invite intervention by means of a hard-fork.

CP

 

 

The optimal Ethereum heist: attacking the Parity wallet (part II)

[continued from part I]

A suboptimal heist?

Looking at how the attacker exploited the vulnerability shows that it was far from being the most elegant operation. First notice the delays between the two calls made to each vulnerable contract. Here is another look at the pairs of calls made for exploiting three different vulnerable wallets:

Pairs of calls used to exploit the Parity multi-signature wallet vulnerability against three different contracts

In the first attack, there is a gap of 10 Ethereum blocks between the calls, corresponding to ~3 minutes based on current block frequency. For the second attack, the calls are separated by 7 blocks. For the final victim, they are only 2 blocks apart suggesting that the perpetrator improved their execution over time. Still these wide gaps suggest that at least the first two attacks were being crafted manually, likely using an interactive REPL such as the geth Javascript console that allows invoking arbitrary methods on any contract. In principle there is no reason to wait between calls: as long as a miner processes them in the correct order, they could even take place in the same block. Even if the perpetrator is proceeding cautiously, waiting to confirm that the first step has achieved the intended effect, there is no reason to wait more than one block before pulling the trigger on the second one. (Note that unlike Bitcoin, Ethereum network does not have a perennial backlog of transactions or arbitrary fee hikes—unless an ICO is going on. Block timestamp is a close proxy for actual attacker moves.) In other words the attacker did not bother with automating the exploit by writing a script to make the calls in quick succession. Each victim appears to have been exploited with a hand-crafted sequence of calls.

That brings up the second mystery: choice of targets. The first successful attack is followed by several hours of inactivity, two more attacks in quick succession and finally, complete silence. There is more activity from the attacker address in days following the heist; but those are all for distributing the stolen Ether into other addresses, likely in preparation for cashing out. There are no other instances of the pair of calls to a vulnerable contract. While it is conceivable this actor switched accounts to better cover its tracks, there are no other instances of theft reported besides the original attack and the white-hat response. Assuming the white-hat group is indeed a distinct actor and not simply another front for the attacker, the surprising conclusion is the perpetrator operated on a leisurely schedule and stopped after targeting just three vulnerable contracts.

The next mystery is that 12 hour pause between the first and second attacks. That initial salvo netted a respectable 26793 ETH in spoils—over $5M. But the perpetrator was clearly not content to rest on those laurels, as evidenced by the following two encores. Why wait that long? Zero-day exploits have “half-lives,” especially when their affects are noisy; and it is difficult to imagine a more noisy demonstration of an exploit than burglarizing large sums on a public blockchain. Once the first vulnerable contract is hit, the clock starts ticking for everyone else to rediscover that vulnerability independently. In general such rediscovery poses two problems for the offense. First, other crooks will get into the game, racing the original finder to exploit remaining vulnerable targets. Second, defenders will be alerted to the existence of a vulnerability. They can craft a patch that closes the window of exploitation for everyone.

Granted that second response only applies if it is possible to upgrade an application in place without losing its state. While this is true for applications running on desktop and mobile platforms (you can patch your web-browser or operating system with nothing more than a couple minutes lost rebooting) it is not true for all platforms. For instance smart-card architectures compliant with the Global Platform standard have no concept of “upgrading” an existing application— applets can only be deleted and reinstalled, with all associated data lost in the process. (And that is a security feature: it protects applications from malicious updates, even by the software publisher.) It turns out Ethereum contracts are far more similar to smart-card applets than they are to vanilla Windows apps: Ethereum has no concept of replacing the code behind a contract with new code. In fact such a capability would run counter to the ideal of immutable contracts. If the code governing a contract can be modified after the fact, it can not be counted on to behave according to predefined rules in perpetuity. But all is not lost for the defenders: in an echo of the proverb “if you can’t beat them, join them,” white-hats can co-opt the exploit, using it preemptively to rescue funds from vulnerable contracts. This is exactly what happened during the DAO attack and again with the Parity wallet in this case.

Bottom line: once the existence of a vulnerability becomes public knowledge, the odds of successful exploitation for any one actor declines down over time. (Paradoxically the chances that any given vulnerable target will be exploited goes up; there are many more threat actors armed with the required capabilities. But they are all competing against each other for the same pool of victims.) A rational attacker being aware of these dynamics would pic off as many targets as possible in the shortest time to preempt the competition. Instead there is a 12 hour self-imposed ceasefire after the first successful exploit and only two more thefts after that. Why?

It is certainly not the difficulty of locating vulnerable contracts that is holding up the attacker. They have the exact same code; they are only differentiated by arguments to the constructor specified at creation time. That means a standard blockchain explorer can help locate other contracts sharing the same code. For example Etherscan has a web interface to search for similar contracts to one specified by address:

Locating contracts with identical or very similar code to a given contract

Given a security flaw in a widely used smart-contract, locating all instances of that vulnerable contract is shooting fish in a barrel. So why stop with three? The white-hat group has allegedly rescued 375K+ ether, more than twice the ~150K ETH the perpetrator managed to purloin. That is a lot of money left on the table.

Even more puzzling, the wallets attacked did not even represent those with highest balances. Given the increasing probability of rediscovery over time, the optimal strategy is going after wallets with highest balances first. But among contracts rescued by the white-hat group are three with balances of 120K, 56K and 47K respectively, each one alone higher than the take from the first victim. Why pass on these more lucrative targets when the same level of effort redirected elsewhere—doing nothing beyond copy/pasting a different contract address into the exploit sequence—could have yielded higher returns?

By all indications, the execution of this attack looks sloppy:

• No automation for delivering the exploit
• Long pause between the first and second wave, giving defenders precious time to organize a counter-strike
• Worst of all, suboptimal choice of victims that fails to maximize profit given complete freedom to choose targets

Yet viewed in another light, that last one may have been a deliberate decision to optimize for a different criteria: the chances of actually getting away with the theft, walking away with the ill-gotten-gains.

CP

[continued]