Who Has Your Back in Crypto?

Hacking Distributed
 
Who Has Your Back in Crypto?

Image/photo

I came across a Twitter poll on which entities have their interests and priorities most closely aligned with Bitcoin users. The results, if they are to be believed, indicate an enormous misunderstanding, or else they betray the result of a successful disinformation campaign. To wit, more than 60% of the respondants believe that the devs have users' interests at heart. Only 23% trust businesses, and a mere 15% say the miners.

This is completely wrong.

In general, open-source (OSS) developers, especially second generation developers who were not present at the inception of the project, have skewed interests that are at odds with those of the users. Depending on your investment thesis, either the miners or businesses have their economic interest best aligned with users. Let's discuss why.

It is incredibly common and ordinary for second generation developers to add gratuitous complexity and bloat to a project. There are two reasons that compel them to do this.

Wanna Be Famous
Image/photo

One reason is to simply leave their unique mark. How else would anyone know that the developers are any good if there isn't a unique new vision? What new line do the developers get to put on their resumes, or which files do they point to in github on subsequent job interviews? "Added Schnorr signatures" sounds far more impressive than "I responded to bug reports and refactored a 5000-line main.cpp file" no matter how useless and cumbersome Schnorr signatures may be to use in practice, and how badly a refactoring was needed [1].

This means that projects often evolve by incorporating vanity features, typically by force of pure ego. Your typical primadonna dev will want to add a dessert table to the banquet; good luck getting them to slice the bread. Especially when there is turnover in a team, the next generation often change the project aesthetic.

A well-known example and ongoing fail-mobile is the systemd project, where a Linux developer named Poettering is trying to import into Linux all of Windows' problems. Like PulseAudio before it, systemd cites legitimate areas where Linux needs improving, but then breaks away from the underlying Unix aesthetic in every possible way. Poettering and his team can't be satisfied with incremental fixes that preserve the original vision -- it is essential that they redo things in their completely unique way, which totally isn't a bug, except I couldn't hear you when we had PulseAudio and I can't parse my logs now, can't install an update without rebooting my machine like a Windows pleb, and sometimes can't start up my system and it's totally not a bug.

Wanna Be Rich
Image/photo

The second reason is to make themselves indispensable, by increasing the complexity of the OSS project. Many open source developers are uncredentialed, young people with few other accomplishments and job prospects, looking to break into a lucrative industry. A complex code base immediately makes them an expert because they know all its warts and they know where all the skeletons are buried in the code. That's because they put them there. This immediately guarantees a consulting stream. You want to add a tweak? Well, you can't, you need to hire someone who understands the mess.

The best example for this is Asterisk [2]. An OSS project so complex, no one can do anything other than what's explicitly in the tutorials, and even then, it requires magic incantations and blood sacrifice. For those who do not know, Asterisk is a system for building phone management systems. You would think that audio management would involve the composition of nice, modular units, with uniform interfaces and clean configuration files. You'd be wrong. When I last looked, there were no abstractions in Asterisk. Things just barely worked for the few use cases, and only if you did everything the way you were prescribed. If you went off script, everything would break down. "If you do A, then B, then X, then S, you'll get the effect you want, because X relies on B's setup and leaves the state ..." you get the point. The people who have mastered this completely useless tangle of constraints ensure a steady income stream and enjoy a standing within their own community of people who do not know better of being an "expert." It's like being an expert at naming things, it sounds like a discipline, almost like science, but it's all just a bunch of does-not-matter in the end.

It is the rare person who can create something, stand behind it, put in the grueling hours to respond to bugs and errors, and then see others get rich off of it, without any trace of wanting to participate in the action. So if the codebase does not provide a direct way of compensating the developers, rest assured that the developers will find a way.

Consequences
These motivations are short-sighted and self-limiting. They drive away new devs from entering the space and strangle the project. The behaviors above are rewarded in the short-term, but spell the convalescence phase for a project.

What About Cryptocurrencies?
Image/photo

So who has your best interests at heart when it comes to cryptocurrencies? Is it the miners, the businesses, or the developers?

If you hold coins, your interests are aligned with those who hold massive amounts of coins. That's not developers. It's most definitely not second-generation developers who were not there on day one when coins were cheap.

If you believe the currency will gain value by expanding community, you are aligned with those who desparately want the economy to expand. That's also not developers.

Miners hold massive amounts of coins. Businesses want a bigger economy, more users and fast coin turnover.

In contrast, developers have complex games they play. Sure, they want the coin value to grow, but not drastically more than your cousin Joe that you somehow convinced to go into your favorite coin with you. If they weren't there for the pre-mine, they wouldn't even have that many coins. While we all hate pre-mined coins, they do provide the right incentives for the long-term success of the coin.

Another way to analyze the situation is to look at the potential losses to be incurred by the different entities. A miner has 100s of millions of dollars' worth of hardware they have committed to the future success of the currency. A typical startup will have a few to tens of millions at risk. Collectively, VCs have poured more than a billion into the cryptocurrency space and they want to see it expand tenfold for returns.

In contrast, a typical second-generation dev has invested just their own time, which may possibly have been partially subsidized by a firm, and collected an average number of coins [3]. It's often unclear that they would have had better prospects elsewhere. They rage-quit and wal away from projects all the time. The worst that can happen to many devs, whose visions are flawed and whose bets turn out to completely tank a project, is to have switch IRC channels, clone a different but similar git repository, and muzzle their toxicity as they integrate themselves into a different social hierarchy.

Takeaway
Image/photo

When evaluating statements from miners, businesses and developers, cast your lot accordingly. No one likes corporations; many large and monopolistic ones tend to eke out profits at the expense of their users. Miners, well, they tend to be predominantly Chinese these days due to abundance of excess hydro power over there, so, if someone is the sieg-heilin', statue-lovin', hitler-would-have-been-alright-if-he-had-obtained-marching-permits type [4], it's clear what one would think. And developers have the benefit of actually having a face, and for some, a 7x24 social media presence. And the thing about troll-backed deceptive narratives is that it sounds all so good, and so popular -- all those likes and upvotes from those nameless trolls in those censored forums must indicate something, right?

Yet the underlying forces are precisely the opposite of how things might seem on a naive, superficial examination.

Of course, in an ideal world, people would evaluate proposals from a scientific perspective, instead of casting their lot with a particular tribe. And the ecosystem would not have distinct roles where people with different roles have goals in opposition to others. Whoever can invent that coin, whoever can build a community based on reasoned, civil, scientific discussion, is sure to make a killing.
    [1]    Bitcoin's main.cpp file used to be 5000 lines long, and quixotically, remained so for many years. Schnorr signatures are nice, there is nothing wrong with them, and we all need them as much as we need a second prehensile tail. "Wait, we don't even have a first one," you might say. That would be the point.
    [2]    I was an avid Asterisk user for multiple years, thanks to a high pain tolerance that allows me to also work on cryptocurrencies. While it was fun to automatically screen telemarketers, to redirect calls to my nearest phone, and to play hold musac for people who called the house, the underlying software was nothing but just bloat, with no attention paid to clean interfaces and repurposable components.
    [3]    On average, people are average. One could claim that developers would more consistently buy in, comparable to more fervent currency fans, but one could also claim that they would want to diversify their risk as well. From my own personal observation, many crypto investors have personal wealth that far exceeds early developers.
    [4]    He did, in fact, have a permit.
To Sink Frontrunners, Send in the Submarines

Hacking Distributed
 last edited: Sun, 27 Aug 2017 22:01:00 -0700  
To Sink Frontrunners, Send in the Submarines

The problem: Frontrunning
Miner frontrunning is a fundamental problem in blockchain-based markets in which miners reorder, censor, and/or insert their own transactions to directly profit from markets running on blockchain economic mechanisms. Miner frontrunning takes advantage of the responsibility of miners in a blockchain system to order transactionsin an attack described in great detail by Martin Swende in ablog post, which we highly recommend for background on this important issue.

Frontrunning is not strictly theoretical: in practice, frontrunning-like tactics have been observedduring large ICO releases, with increasingly sophisticated attacks anticipated as the financial incentivesfor gaming high-profile contracts increase and attract more sophisticated attackers.

As described in a previous article on frontrunning, "any scheme that a) provides full information to miners b) doesn't include nondeterminism and c) is vulnerable to ordering dependencies is gameable."

In this article, we will examine a potential mitigating strategy for frontrunning through the lens of a fair sealed/closed bid auction mechanism that resists miner frontrunning. This strategy can be used for fair markets, fairICOs, fair ENS-style auctions, and much more.

We stumbled upon this problem during the creation of our upcoming billion-dollar ICO token launch, HaxorBux (HXR).

Our mitigating strategy is an idea that we call a submarine send.Submarine sends aim at a strong confidentiality property. Rather than just concealing transaction amounts—which isn’t sufficient to prevent frontrunning, as we’ll show—submarine sends conceal the very existence of a transaction. Of course, a permanently concealed transaction isn’t very useful. Submarine sends thus also permit a transaction to be surfaced by the sender at any desired time in the future—thus the term “submarine”.

Image/photo
Submarines: They can’t frontrun you if they can’t find you

We have published a proof-of-concept implementation on github(still lacking some features like the Merkle-Patricia verification described later in this post). We encourage contributions and comments in the issues section there!

Why it’s hard to prevent frontrunning
A folklore method for concealing transaction values—used for everything from randomness generation to (non-blockchain) sealed-bid auctions—is called commit / reveal. The idea is simple. In a first protocol phase, every user Ui submits a cryptographic commitment Ui = commit(vali) to the value vali representing her input to the protocol, e.g., her bid in an auction. After all inputs have been gathered, in a second phase, every player reveals vali by decommitting Ui. During the first, commitment phase, no user can see any other user’s bid / value vali and thus front-run the second phase.

This is all well and good, but vali is a value, not actual money. So what if a user wins a sealed-bid auction conducted this way. How do we ensure that she actually pays the amount val that she bid?

In a decentralized system, where users may be untrustworthy, val is a more or less worthless IOU. The only way to ensure payment is for all users actually to commit $val, i.e., commit the money represented in their bid. In Ethereum, though, there is no (simple [1]) way to conceal the amount of Ether in an ordinary send. So when P sends $val as a commitment, she reveals her bid amount. That brings us back to square one. [2]

Suppose instead of Ethereum, we were using a hypothetical system that actually concealed transaction amounts and even the sender identity (but not whether a contract receives a transaction). Call it ZEthereum. Then, of course, we’d solve the problem. Front running isn’t possible in an auction if you don’t know your competitors’ transaction amounts. Right?

Unfortunately, even concealed transaction amounts don’t do the trick, as a simple example shows.

Example 1 (Transaction Existence): Tweedledum is bidding on a rare military helmet in an auction administered through a ZEthereum smart contract. He knows that there is only one other possible bidder, his brother Tweedledee, who loves the helmet, but has at most $1000 available to bid for it. If Tweedledum learns of the existence of a second bid, his strategy is clear: He should bid $1000.01. Otherwise, he can win with a bid of $0.01, far below the real value of the helmet. Even though bid amounts are concealed, Tweedledum can game the auction by learning whether or not a bid exists.

Image/photo
Tweedledee cheated of helmet by Tweedledum’s frontrunning

While this example is contrived, there are real systems in which the existence and also the timing of bids can leak information. For instance, in an ICO, it’s easy to imagine even naive algorithms estimating interest in a token and altering their bid based on contract buy-in statistics.

Send in the submarines
Our solution, a submarine send, is a poor-man’s solution to the problem of concealing transaction amounts and existence for a target smart contract "Contract". It doesn’t conceal transaction amounts as strongly as our hypothetical ZEthereum would, and it doesn’t definitively hide the existence of transactions. But it provides what we believe to be good enough guarantees in many cases.

The key idea is to conceal sends to Contract among other, unrelated and indistinguishable transactions.

A submarine send embeds a real transaction among a collection of cover transactions, thus achieving a form ofk-anonymity. Put another way, the submarine transaction sits in an anonymity set consisting of k cover transactions. While not as strong as notions such as differential privacy or full concealment based on cryptographic hardness assumptions, k-anonymity has proven useful in many practical settings. And some low-cost enhancements can strengthen our scheme’s properties.

The basic format of a submarine send is simple: It is a send of $val from an addrP, where P is the player interacting with Contract, to a fresh address addrX. The trick is to structure address addrX such that it has two properties: (1) addrX looks random in the view of potential adversaries and (2) $val is committed to SC in a manner that can be proven cryptographically.

Let’s illustrate with an example, showing how a system that is vulnerable to frontrunning can be rendered more secure by use of submarine sends.

Example 2 (Ash ICO): Suppose that smart contract AshContract implements sales of a new type of token called an Ash. Purchasers burn Ether to obtain tokens at a market-driven Ether-to-Ash exchange rate.

It’s easy to see that AshContract is vulnerable to frontrunning. A large buy transaction will substantially raise the market price of Ash. Thus a miner that observes such a transaction Trans can profit by squeezing in her own buy transaction before Trans and selling afterward. We can remedy this problem by enhancing AshContract as follows:

Example 2 (Ash ICO) continued: In a commit phase, a player P with address addrP makes a submarine send via transaction Trans as follows. P sends $val to address addrX for public key X, where X = H(addrP, SCN, TKEY), where SCN is a contract-specific identifier, TKEY is a transaction-specific key / witness (e.g., a randomly selected 256-bit value), and H is Ethereum-SHA-3.

In a reveal phase, to prove that she has burned $val, P sends TKEY to AshContract. AshContract then: (1) Verifies TKEY is a fresh key; (2) Computes X = H(addrP, SCN, TKEY) and addrX; and (3) Checks addrX.balance == $val. Upon successful verification, AshContract awards Ash tokens to P.

Observe that during the commit phase, X and addrX are computed from an as-yet unrevealed key (namely TKEY). Thus the transaction Trans is indistinguishable from an ordinary send to a fresh address. [3] Assuming that many other such ordinary sends happen during the bidding period, an adversary cannot identify Trans as a purchase of Ash.

During the reveal phase, P proves to AshContract that she burned $val to purchase Ash. [4] Given the way public key X is computed, it is infeasible to compute a corresponding valid private key. Thus money sent to addrX is unrecoverable, i.e., burned.

Of course, there are cases in which we don’t want to burn the committed currency. As we now show, it is possible to implement submarine sends in which $val is recoverable by AshContract after the reveal phase.

Image/photo
The two phases of a submarine send

Submarine sends via EIP-86
It is possible to implement cheap and simple submarine sends in which $val can be recovered. For this purpose, we rely on a new feature introduced inEIP-86. EIP-86 was scheduled to go live in the upcoming Metropolis hard-fork, but unfortunately its deployment has been postponed for now. We detail a temporary, more expensive option for implementing submarine sends in the blog appendix.

The crucial change in EIP-86 is the introduction of a new CREATE2 opcode to the Ethereum Virtual Machine. Like the already existing CREATE opcode, the new opcode will also create new smart contracts on the blockchain. However, unlike CREATE, CREATE2 will compute the address of the newly created smart contract C as H(addrCreator, salt, codeC), where addrCreator is the address of the contract’s creator, salt is a 256-bit salt value chosen by the creator, and codeC is the EVM byte code of C’s initcode.

To construct submarine sends, we combine this new way of computing contract addresses with a very simple smart contract which we call Forwarder. Forwarder performs one function: Upon receiving a message-call, it checks whether the message-call was sent by Contract. If so, Forwarder sends its entire Ether balance to Contract. Otherwise, Forwarder does nothing. Here is a simple implementation of Forwarder written in Solidity:

contract Forwarder {

address constant addrContract = 0x123;

function () {
if (msg.sender == addrContract)
addrContract.send(this.balance);
}

}

To save gas, we can also implement Forwarder directly in EVM bytecode, reducing the size of the Forwarder contract by ~ 75%.

Let’s put the pieces together and examine how the commit and reveal phases work.
  • Commit: To commit, P computes the address A := H(Contract’s address || Data || initcode(Forwarder)), where Data contains any additional required information about P’s bid as well as a fresh nonce. The bidder P the sends $val to A. At this point in time, A is a fresh address which has never been observed on the network.
  • Reveal: Upon P’s revelation of Data, Contract verifies the freshness of the nonce contained in Data, computes A as described above and checks that A.balance == $val. Contract then instantiates Forwarder at address A using the CREATE2 opcode. Next, Contract message-calls into this Forwarder contract which in turn promptly transfers $val to Contract.
While EIP-86 offers the best vehicle for implementation of submarine sends, as noted above, it is nonetheless possible to implement them in Ethereum today. For details, see the blog appendix (“Submarine sends, today”.)

The astute reader might notice that an important step is still missing in the above scheme: Contract does not check that the transaction that sent $val to A actually happened during the commit phase! This is crucial, as otherwise we face a frontrunning issue again: Upon seeing a reveal of a submarine send, a miner could compute A, observe A.balance, and include his own commit and reveal transactions after the commitment phase has already ended.

So how should we go about verifying the timeliness of the transaction to A? The conceptually simplest solution is to verify this off-chain, e.g. using Etherscan, but that sort of defeats the purpose of smart contracts, right?

A more technically involved solution would be for P to reveal, in addition to Data, a proof that a transaction of $val to A was made during the commit phase. This proof can then be verified by Contract. The proof would include a block number, all the transaction’s attributes (transaction index, nonce, to, gasprice, value, etc), aMerkle-Patricia Proof of inclusion in the transaction trie, as well as a block header, and convince Contract that (1) that block was mined during the commit phase; and (2) that the relevant transaction is included in that block. However, generating and verifying such a proof for every submarine send is cumbersome and expensive.

The solution we propose follows an alternative “optimistic” approach: Instead of having every bidder prove to Contract that they followed the protocol correctly, we will allow parties to prove to Contract that some bidder cheated. As the cheating party will forfeit its bid as a result, this solution should incentivize correct behavior of the bidding parties. Bidders still reveal all transaction attributes and the corresponding block header to Contract but they do not include a proof (this is the expensive part after all). After the reveal phase is over, Contract enters a short verification phase in which parties may submit proofs that some other party’s reveal is incorrect. Analogously to the above proof of correct behavior, a proof of cheat consists in showing that the transaction attributes and block header revealed by a bidder are incorrect: i.e., that the given block is not in the blockchain, or that it does not contain the purported transaction. [5] If the proof verifies, Contract would collect the bid from the Forwarder contract, and send it to the loyal watchdog as reward. As verifying other bidders’ reveals off-chain is very simple, honest bidders have a strong incentive to check for and report a cheating party that outbid them (as long as honest bids are larger than the gas cost of proving wrongdoing).

We believe this solution offers a good compromise: Although Contract still has to implement the rather tedious procedure of verifying the (non-) inclusion of a transaction in Ethereum’s blockchain, this procedure should only ever be called if a party actually reveals an incorrect bid. In such a case, the misbehaving party’s bid is forfeited and used to offload the gas costs of the party that revealed the wrongdoing.

Exactly what constitutes a cover transaction?
If we were to make a submarine send today, how hard would it be for a frontrunning miner to detect it? The answer to this question crucially depends on the size of the anonymity set we are trying to hide our submarine in. As a reminder, this anonymity set comprises other “normal” transactions in the Ethereum network that look the same as a submarine send.

Suppose our commit window spans blocks Bstart to Bend. During that window, a frontrunner will be looking for transactions to some address A that satisfy the following properties:
  • Address A had never been observed in the network prior to this commit window.
  • Address A is not involved in any other transactions (internal or external) during the commit window. [6]
  • The transaction to address A carries a nonzero amount of ether.
Such addresses A, which we refer to as “fresh addresses”, are candidates for being the destination of a submarine send and thus make up our anonymity set. Note that it is irrelevant whether these fresh addresses are involved in further transactions after the end of the commit window (i.e., in blocks after Bend). Indeed, although this could reveal that some addresses were actually not used as part of a submarine send (thus effectively reducing the anonymity set), at that point in time the danger of a frontrun is moot as the commit phase has passed.

The choice of the commit window (the number of blocks from Bstart to Bend) should thus be primarily governed by the size of the anonymity set one might expect over that period.

Empirical analysis: Anonymity-set size
We performed a simple experiment to determine the effective size of the anonymity set for submarine sends. We selected a commit window of roughly 30 minutes between blocks 4007900 and 4008000. In that period, we recorded 7109 transactions (excluding internal transactions), of which 661 satisfy the above properties and thus make up an anonymity set for submarine sends.

As an example, consider this addresswhich received 5 ETH in block 4007963 and has not been involved in any other transaction since. [7]

The graph below shows how the size of the anonymity set grows throughout the commit phase.

Image/photo
Size of anonymity set over time

If we consider a larger commit window of a little over two hours, between blocks 4007600 and 4008000, we find that the anonymity set for submarine sends consists of 1534 “fresh” addresses.

Transaction shaping
Of course, a frontrunning miner might try to use information other than the freshness of the destination address to de-anonymize a submarine send. In particular, perhaps the miner knows that the transaction she wants to frontrun will contain a certain amount of Ether. In that case, it is important that the submarine send “blends in” with other transactions of similar value. Thus effective cover transactions must also contain transaction amounts that are statistically similar to that in the submarine send.

Fortunately, we found that the transactions that make the anonymity set span a diverse range of Ether amounts, with the majority of values between 0.01 and 100 ETH, and an average transaction value of about 6 ETH. Below we show the distribution of Ether values for the transactions to fresh addresses between blocks 4007900 and 4008000.

Image/photo
Transaction value histogram, blocks 4007900 to 4008000

Furthermore, there are a few ways to perform what we call transaction shaping in order to help prevent transaction amounts from revealing submarine sends:
  • Refunds: Contracts can refund full or partial submarine send amounts, providing limited further cover similar to the ENS amount hiding mechanism.
  • Flexible send amounts: In some cases, a sender has some flexibility in the amount of money she transmits in a submarine send. Refunds create such flexibility, but it can exist in other settings. For example, users may be willing to randomly vary their purchase amounts in AshContract to help conceal their transactions.
  • Fragmentation: Senders can split submarine send initial deposits into multiple transactions (potentially from a range of addresses), providing further noise for heuristics attempting to detect these sends. Of course, given the lack of transaction-graph confidentiality in Ethereum, there is a risk that multiple transactions can be traced to the same user. This risk can be mitigated by means of mixing.
  • Synthetic cover traffic: Senders can create their own cover traffic at minimal cost by sending money to fresh addresses they control.
Conclusion
Frontrunning and related problems are pervasive problems, with no good available remedies in Ethereum. Submarine sends, while imperfect, offer a powerful and practical solution. Fortunately, there is already a fairly high volume of low-to-medium-value cover transactions in Ethereum today, and we can expect it to grow as the system evolves. Ourproof-of-conceptworks on the Ethereum network today, though it costs more gas than our ideal scheme. For submarine sends to be truly practical, all we await is the adoption of EIP-86.

Appendix
Submarine sends, today
If you don’t want to wait until EIP-86 is adopted, we have good news for you. It is already possible to use Submarine Sends in Ethereum, although it is more complex and costly than in the future EIP-86-Ethereum. To rid ourselves of the dependency on EIP-86, we need another way to construct fresh addresses that are later inhabited by a contract. Since we cannot use CREATE2, we will have to make do with CREATE.

Whenever a contract is created with CREATE, its address is computed as H(addrCreator, nonceCreator), where addrCreator is the address of the contract’s creator and nonceCreator counts how many contracts have been created by the contract’s creator. [8] Hence, the creator has some control over nonceCreator: to increment nonceCreator by one, the creator only has to spawn a new contract. Of course, incrementing nonceCreator until it encodes the output of a cryptographic hash function (say 80 bits [9]) is completely out of the question. But we can encode this value in a series of nonces, making the scheme somewhat practical.

As in the EIP-86 example, we also need a Forwarder contract. However, Forwarder isn’t quite as simple as in the EIP-86 example; beyond forwarding funds to Contract, it now also must be able to clone itself, i.e. to CREATE a new instance of itself.

Once again, we have a commit and a reveal phase:
  • Commit: P computes a commitment H’(Data), where Data contains the required information about P’s bid and a fresh nonce. P splits H’(Data) into k distinct 2-bit chunks [10] H’(Data)[1], H’(Data)[2], ..., H’(Data)[k]. The value of each two-bit chunk is interpreted as an integer in [1..4]. P then computes the address A := H(H(... H(Contract's address || H’(Data)[1]) ... || H’(Data)[k-1]) || H’(Data)[k]) and sends $val to A. As before, A is a fresh address which has never been observed on the network.
  • Reveal: Upon P’s revelation of Data, Contract verifies the freshness of the nonce contained in Data, computes A as described above, and checks that A.balance == $val. Contract then orchestrates a chain of contract creations by repeatedly calling clone() on various Forwarder instances until a Forwarder instance appears at address A: For each H’(D)[i] (1 ≤ i ≤ k), Contract calls the clone() function of the Forwarder instance at address H(... H(Contract's address || H’(Data)[1]) ... || H’(Data)[i-1]) at least H’(Data)[i] times. At the end of this process, a Forwarder instance will have been instantiated at address A and Contract then withdraws $val from that instance.
We have created a prototype implementation using 80 bits for H’(Data) in which creating a series of contracts and withdrawing the funds costs ~5 million gas. [11] We believe that optimising this implementation would bring the gas cost down by roughly 50%. At a currently feasible gas price of 4 gigawei this corresponds to 0.02 ETH or 3.65 USD.

Block stuffing attacks
Of course, our scheme has some limitations. Attacks still exist where an adversary can spam a large volume of high-fee transactions in an attempt to stop players from either committing or revealing, especially late in these periods. The longer the period, the more costly this becomes to the adversary. One mitigation strategy is to make the period long enough that the cost required to fill blocks exceeds the value estimated to be at stake.

Unfortunately, an inherent tradeoff between latency and fairness may always exist in systems aiming to provide fairness guarantees by tackling frontrunning, as smaller periods of hiding information from miners leave users more vulnerable toreorganizations and consider the input of fewer miners.

    [1]    https://blog.ethereum.org/2017/01/19/update-integrating-zcash-ethereum/
    [2]    
There are other approaches to addressing front-running that don’t involve concealment of transaction amounts:

(A) Players could commit small, uniformly priced deposits that they forfeit if they fail to pay. But they may still not be incentivized to pay in full.

(B) Players can break up their bids across multiple transactions and reveal their belonging to the same bid in the reveal phase. But a lack of transaction-graph confidentiality means that even bids from multiple addresses might be tied to the same user. We propose this approach as an added layer of security for submarine sends, but its limitations need to be made clear.

    [3]    Indeed, in the Random Oracle Model, the ability to identify Trans as a submarine send would imply the ability to perform signature forgery.
    [4]    This example glosses over the details of how party P convinces Contract that the burn of $val actually occurred during the commit phase and not after. We’ll come back to this important issue in the next section.
    [5]    As the Transaction Trie is sorted, showing that a transaction is not in it simply reduces to showing that either there is no transaction with the given index in the trie or that the transaction at the given transaction index has different attributes than the ones given during the reveal.
    [6]    If the address only receives transactions, it could technically still be a candidate for a submarine send as we could always split up a submarine send into multiple transactions to the same destination address.
    [7]    At the time of writing, the most recent block number is 4036411.
    [8]    This isn’t the whole story: If the creator is a contract, nonceCreator counts how many contracts have been created by the creator. Otherwise, nonceCreator counts how many transactions have been initiated by the creator. Furthermore, the inputs to the hash function are rlp-encoded before hashing.
    [9]    Since we don’t require our hash function to be resistant to collision attacks, we don’t have to worry about the birthday paradox and can get away with using a shorter hash. 80 bits should still provide ample defense against pre-image attacks, especially in light of the fact that an attacker only has a rather short amount of time in which finding a pre-image benefits her.
    [10]    Somewhat surprisingly, a theoretical analysis reveals that out of all fixed-width chunking schemes, 2-bit chunking is the cheapest on average. For example, using 2-bit chunks is 20% more efficient than using 1-bit chunks.
    [11]    Since this comes close to the block gas limit, we split the withdrawal process into multiple transactions. Note that it’s relatively cheap to compute A; the high gas cost is caused by the creation of the hundreds of contracts needed for withdrawing funds from A.
The Cost of Decentralization in 0x and EtherDelta

Hacking Distributed
 
The Cost of Decentralization in 0x and EtherDelta

This Tuesday, a decentralized exchange platform called 0x will be holding a $24 million token sale. In the midst of an ICO frenzy that has funneled $1.3 billion into fledgling projects, the 0x sale seems like a drop in the bucket. 0x, though, is at the forefront of a wave of decentralized exchange projects that also includes EtherDelta, BitShares, KyberNetwork, and Omega One.

So what are decentralized exchanges, and why does the world need them?

A centralized cryptocurrency exchange is administered by an entity that represents a single point of failure. Users deposit their funds directly with the exchange, and the exchange assumes responsibility for matching buy and sell orders, which it can do in real time. Many exchanges support the purchase and sale of cryptocurrencies, fiat currencies, and cryptocurrency tokens. Examples of centralized exchanges include Coinbase, Kraken, and ShapeShift—as well as MtGox and Bitfinex. These last two were famously compromised, resulting in the loss of roughly 650,000 BTC and 120,000 BTC respectively, hundreds of millions of dollars at the time. (ShapeShift too was hacked, but a mere $200k or so worth of funds were stolen.)

Therein lies the rub. Centralized exchanges have the serious drawback that they require users to trust the exchange with their money. A fraudulent or compromised exchange can result in theft of users’ funds. There are also other drawbacks to centralized exchanges, such as the vulnerability of the users to frontrunning by the exchange administrator, as we discuss below.

Decentralized exchanges were created specifically to address centralized exchanges’ vulnerability to theft of user funds. In a decentralized exchange, users retain a degree of control of their own funds. They do not send money directly to a wallet that is controlled by a single entity. Instead, trading orders, and thus the release of user funds, are authorized directly by users via digital signatures. In principle, therefore, user funds cannot be stolen.

“In principle” is the operative phrase here. As we show, the ability to sign off on transactions does not equate with real control. Enabling users to control their own funds seems a good thing, but it has the side effect of abandoning the real-time nature of centralized exchanges in favor of slow, on-chain trading, That in turn exposes users of decentralized exchanges to new risks of monetary loss. Consistent with 0x’s apparent design philosophy of community empowerment, there is further dimension of decentralization in 0x’s governance scheme, which permits token holders to upgrade 0x contracts. This feature unfortunately creates a systemic risk such that users’ funds could again be potentially exposed to theft, resulting in some degree of the worst of both worlds.

Any complex new system is likely to suffer from design flaws. Decentralized exchanges have some definite advantages over their centralized counterparts, but also some distinct drawbacks. The design landscape is complex and it is essential to evaluate the merits of individual systems and the risks they pose to users of being cheated or exploited. Some of the flaws of 0x are inherent to decentralized exchanges, while others aren’t, as we now explain.

0x closely resembles EtherDelta, an existing exchange. We therefore compare 0x with EtherDelta to better understand the design choices and likely risks in 0x exchanges.

In this blog post, we present a brief overview of the general design behind today’s decentralized exchanges. Then we discuss three categories of decentralized-exchange design flaws:
  • General flaws affecting all decentralized exchanges, at least within the design space currently explored by the community.
  • 0x-specific flaws introduced by particulars of the 0x architecture.
  • EtherDelta-specific flaws that are minor and don’t affect 0x, but teach us something about the challenges of correctly implementing exchanges.
Finally, we describe experiments we have performed in EtherDelta. These experiments highlights that the risks we describe are real and already emerging in a decentralized exchange with fairly low volume. We conclude with a brief discussion of the decentralized-exchange design space as a whole.

Decentralized exchanges: Brief overview
To support real-time trades, decentralized exchanges such as EtherDelta and 0x adopt essentially the same architecture for public (“broadcast”) orders. Users send their orders to off-chain matching services (called “Relayers” in 0x), which post them in off-chain order books. Such posting takes place in real time—much faster than if orders were posted on a decentralized blockchain.

Any user (called a “Maker” in 0x) can publish any buy or sell request (that this user signs) on the order book of the off-chain service. An order is accompanied by an exact price, i.e., limit orders aren’t supported.

EtherDelta and 0x both attempt to minimize trust in the off-chain matching service by not giving it the power to perform automatic matching of the buy and sell orders. Instead, any other user (called a “Taker” in 0x) trades against a posted order by adding a counterorder and digitally signing and sending the complete transaction, i.e., pair of orders, directly to the blockchain. The transaction is sent to a smart contract that executes the transaction, transferring assets between the buyer and seller (Maker and Taker in 0x). The lifecycle of a transaction is shown below in Figure 1.

EtherDelta and 0x both adopt this general design, but differ in two key ways. 0x allows anyone to stand up an exchange (“Relayer” in 0x), while EtherDelta has a unique one. Additionally, 0x, unlike EtherDelta, has a system of tokens used to pay transaction fees and for system governance.

Image/photo
Lifecycle of a transaction, using 0x terminology. (1) The Maker sends a digitally signed broadcast order (e.g., “Sell 100 TOK for 1 ETH”) to the Relayer, who (2) Posts the order to the Order book. The Taker finds the order in the order book and digitally signs it, with a counterorder (“Buy 100 TOK for 1 ETH”) to the DEX (“Decentralized EXchange”) smart contract.

General flaws in decentralized exchanges
The general design just described introduces several basic vulnerabilities:

Exposure to arbitrage: The lack of automatic matching permits in-market arbitrage, whereby stale orders are filled to the disadvantage of users unable to quickly cancel their orders in response to market fluctuations. For example, the arbitrageur can execute against a standing pair of orders (sell 1 TOK at 1 ETH and buy 1 TOK at 2 ETH) to make an immediate profit of 1 ETH. Since the only way for users to invalidate their signed orders (that they published on the off-chain service) is by sending an on-chain cancellation transaction that is explicitly processed by the exchange contract, the arbitrageur may pay a high gas fee to miners and win the race against the cancellation transaction. Therefore, users who wish to increase the probability of a successful cancellation may need to attach an excessively high fee that depends on the value of the trade, which makes the exchange platform unattractive to honest users. We show below that this problem isn’t theoretical, but already arises in practice.

Vulnerability to miner frontrunning: Order cancellations are a common feature of decentralized exchanges (after all, an exchange with no cancellation ability may not be useful in a volatile market), and their on-chain nature renders these cancellations particularly vulnerable to miner frontrunning; the miner of the next block will always have the option to execute cancelled orders with themselves as the counterparty, potentially profiting from such an order. To add injury to insult, the miner even collects gas costs from a user’s failed cancellation. This issue was noted in the Consensys 0x report, and is recognized as a limitation of on-chain cancellations in the community.

Exposure to exchange abuses: Since the off-chain matching service doesn’t perform automatic matching, it is supposed to publish all users’ orders as quickly as possible, resulting in principle in fully transparent behavior. In actual fact, though, the exchange can suppress orders, mounting a denial-of-service attack against users in order to corner a market or censor particular users’ transactions. Worse yet, it can front-run orders. Specifically, it can engage in the same kind of in-market “sandwich” arbitrage described above, especially when high-value trades are requested. The problem is that signed orders flow to the off-chain server first. The server can thus match the trade data with pseudonymous users that it controls. Both suppression and front-running by an exchange are extremely hard to detect.

0x-specific flaws
Decentralized governance: In just two days, 0x will launch the Initial Coin Offering (ICO) of their ZRX token. The token will serve two functions: First, it will allow market participants to pay a Relayer’s fees for listing orders. Second, the token will be used for "decentralized governance" over the evolution of the protocol and the DEX contract holding market participants' assets.

Why a dedicated token should be used for Relayer fees is unclear—after all one could simply pay Relayers in ETH instead. The use of a token for decentralized governance is a more interesting use case.

Unfortunately, the 0x whitepaper does not provide any detailed information on how this governance process will work. Neither does the code in 0x's github repository. Since the governance process appears to be the only good reason for creating the ZRX token, this is all the more disappointing.

The 0x whitepaper does, however, state that non-disruptive protocol updates (i.e. changing the protocol and underlying smart contracts without requiring opt-in of individual users) are an explicit design goal of the governance scheme. This immediately raises questions about the security properties of the governance process. If, for instance, 0x were to use a simple majority voting scheme to approve updates to the DEX (which holds all user assets), an attacker could perform a 51% attack where she buys more than half of all ZRX tokens and then votes to replace the DEX with a malicious contract sending all assets to the herself. Designing a secure, decentralized governance process will be difficult and involve a multitude of delicate tradeoffs. Once again, decentralization is no panacea and carries a price in terms of complexity and possibly weakened security!

Side deals: 0x's design allows for two kinds of orders, broadcast orders and point-to-point orders. Broadcast orders make use of a Relayer, who broadcasts the Maker's order to any listening Takers who can choose to fill the order by sending a signed message to the DEX. (Figure 1 shows the lifecycle of a broadcast order.) Relayers can charge fees as a reward for their broadcasting services: When an order is filled, the DEX will transfer any fees from the Taker and Maker's accounts to the Relayer's account.

In contrast, point-to-point orders do not make use of Relayers and thus avoid Relayer fees. As their name suggests, point-to-point orders allow two market participants to trade directly with each other by sending signed messages to the DEX.

This leads to a scheme that allows Makers and Takers to evade Relayer fees:
  • The Maker M posts an order O on a Relayer service.
  • A Taker T listening to the Relayer learns of the order and decides she wants to fill it. She contacts the Taker off-chain [1] with a point-to-point order O' corresponding to O: If O offers to sell 1 TOK for 1 ETH, O' will offer M to buy 1 TOK for 1 ETH from T.
  • Once M receives the order, she sends a single Ethereum transaction to the blockchain. This transaction calls the DEX twice, first cancelling O and then immediately filling O'. Note that thanks to the atomicity of Ethereum transactions, M carries no risk of both O and O' being filled.
Since cancellations are free and O is never filled, the Relayer will not earn any fees. Systematic exploitation of this flaw could lead to a tragedy of the commons, where individual market participants would make it uneconomical to run a Relayer by always evading fees, thereby destroying the "common good" of Relayers.

Side deals are less of a problem in EtherDelta because EtherDelta doesn’t support point-to-point orders and the fees for broadcast orders are hardcoded in the smart contract. However, 0x’s approach is not without advantages: Having a single DEX hold the assets for all point-to-point and broadcast orders and allowing multiple Relayers will likely lead to a more liquid market; furthermore, competition among Relayers may lower the fees that user pay. This tradeoff cannot be easily overcome: EtherDelta could in principle support multiple Relayers by using a separate contract for each of them, but this approach would not allow the liquidity in the order books of the Relayers to be shared.

Maker griefing: Maker griefing is an attack recognized in audits of 0x whereby an order maker moves tokens that are supposed to be involved in an order, causing it to fail in the final on-chain processing stages responsible for moving the funds. If such a failure occurs, the on-chain taker must pay gas fees to attempt execution of an order that never completes or provides any benefit to the taker, an inefficient use of taker time and money.

Repeating this attack on a large scale could potentially waste Taker gas, making Takers incur high order fees, costs, and delays in addition to the transparent Taker fees charged by the exchange. A cartel could place both legitimate and illegitimate orders, sharing information with each other out of band about which orders were legitimate. This would force outsiders to incur penalties, a potentially profitable strategy for a sufficiently powerful cartel. The recommended tooling mitigations do not entirely solve the issue, as they rely on checks of blockchain state, which could potentially change immediately before or even during the release of a new block. The potential for miner involvement as Makers in permissionless distributed markets or miner collusion with these cartels further amplifies these attacks, as miners could both collect the profit from Takers burning gas in griefing attacks and trigger the attacks in previously unseen transactions inserted in blocks before order fulfillment. Such a miner attack would allow no possibility of detection for the recommended tool-based mitigations.

The technological and economic barriers to these attacks or the formation of potential cartels mean these strategies may not surface until decentralized exchanges achieve substantial volume (and thus allow for substantial profit), dangerously providing a false sense of security and a false confidence in on-chain market architectures.

Similarity to EtherDelta: As described in the design of both exchanges, EtherDelta and 0x share a number of similarities. As EtherDelta is a full system that is currently operational and includes a number of in-production smart contracts, it is unclear where a potentially large ICO raise could be allocated beyond the development of equivalent technologies and distributed governance. The 0x roadmap provides some hints of potential strategies for differentiation, and we hope to see the development of advance and novel R&D improvements accompany the deployment of proposed EtherDelta-like infrastructure.

EtherDelta-specific flaws
Slow cancellation: Despite its processing of cancellations with low observed latency after a cancellation order is mined on-chain, the requirement of waiting until the next mined block (or later with potentially full blocks) imposes a significant barrier to real-time exchange, potentially locking up user funds and enabling profitable miner arbitrage on larger orders through frontrunning.

Slow order processing: During the posting of our test orders on EtherDelta in the experiments we conduct below, we observed a substantial delay required to place orders in the systems. This operation is not contingent on any on-chain transaction processing, and it is not clear to us why the system is imposing such a delay.

High gas costs for competing transactions: Due to the high latency of EtherDelta’s order book, some Takers may be blind to each others’ orders. This can cause a race condition where multiple Takers compete to fulfill a single order, leading to order failure with some delay and gas costs incurred by all but the winning Takers. This could potentially become problematic on attractive orders as the system increases in size, specifically with the possibility of miner participation and frontrunning.

Experiments with EtherDelta
We experimentally verified some of the flaws listed above. First, we evaluated the total theoretical arbitrage opportunity of 10 major ERC-20 Token/ETH exchanges (BQX, CDT, CVC, EOS, PAY, PLR, PPT, VERI, XRL exchange with ETH) on EtherDelta over a period of 24 hours (from 2017-8-11 00:30:00 UTC to 2017-8-12 00:30:00 UTC). Our experiments show that—assuming perfect execution, the current EtherDelta transaction fee of 0.3% of total volume, and a gas price of 20 Gwei—an arbitrageur could have gained 14.71785 ETH in the above period. At current exchange rates ($303.9 / ETH), this corresponds to $4,472.75 / day or $1.6+ million / year. Specifically, we observed 45 arbitrage opportunities during our period of study, with an average arbitrage opportunity of 0.32 ETH. Compared with centralized exchanges, EtherDelta has relatively small volume today. Were its volume to grow substantially without technical changes, arbitrage opportunities would presumably grow to be quite substantial.

Many of these arbitrage opportunities resulted from clear user error, i.e., obvious mispricing of orders. Even without such error, however, we identified approximately 6.7 ETH in arbitrage opportunities over the 24-hour period of study, corresponding to about $2,036.

Having confirmed that arbitrage opportunities exist in practice, we demonstrated experimentally that they are exploitable in practice. We designed a simple trading bot that would monitor EtherDelta's order books for arbitrage opportunities and send orders exploiting them to the blockchain. Our preliminary numbers suggest that out of 12 orders sent, 7 (or 58.3%) succeeded. The cause of failed arbitrage attempts was a failure to post our order fast enough, i.e., someone else hit the order or the maker cancelled the order before our order executed. (We did not seek to exploit all 45 observed arbitrage opportunities because this would have required roughly 80 ETH worth of tokens, which is more than we poor academic researchers possess.)

Assuming that the success rate we observed is representative, we can approximately estimate the expected net daily profit available to arbitrageurs according to the following formula:
Expected profit = (Net profit per transaction * Probability of success - Gas per transaction * (1 - Probability of success)) * Total number of opportunities

Our experiments during the period of study suggest the estimate:
Expected profit = 0.32 ETH * 58.3% * 45 - 0.004 ETH * (1 - 58.3%) * 45= 8.32 ETH

Or about ~$2500 per day. While this is not enormous, particularly if competition arises among arbitrageurs, an increase in popularity and therefore volume on decentralized exchanges would of course result in far larger potential profits.

The decentralized-exchange design space
There is a large design space for decentralized exchanges beyond the EtherDelta/0x variety. For example, an alternative is to allow the off-chain matching service to perform automatic matching, and even require each trade to include a signature by the off-chain service. To avoid loss of funds in the case that the off-chain service disappears, users would still be able to withdraw their assets without approval of the off-chain service, but only via a slow process. This design eliminates two of the major problems that we described above: The arbitrageur won’t be able to race against users who have already cancelled their orders, and miners won’t be able to front-run users. Unfortunately, the off-chain matching service will have the same kind of power to perform in-market arbitrage as centralized exchanges. Unlike centralized exchanges, though, it won’t have the power to steal users’ deposits.

Another reason to avoid automatic matching by the off-chain service, however, is that it reduces the complexity of the code of the exchange contract. Automatic matching support would naturally support functionality such as limit orders that don’t exist in EtherDelta / 0x. (Given the simplicity of the code base for which 0x are raising $24 million, code supporting automatic matching would presumably be worth several hundred million or so...)

Conclusion
Centralized exchanges have serious drawbacks, perhaps most notably exposure of users’ funds to theft. But the wave of creation of decentralized exchanges that place users’ funds in their control does not fully protect users’ funds, and introduces new problems. It is tempting to dismiss the problems we’ve observed in EtherDelta as trivial, but we believe they will grow as decentralized exchanges do. What we’re seeing today is just a harbinger of problems to come should decentralized exchanges sweep over the cryptocurrency landscape. But since the problems that we’ve identified are exacerbated when higher value trades take place, we conjecture that such problems will ultimately limit the popularity of decentralized exchanges.

This all is not to say that decentralized exchanges do not have a place or cannot fill a valuable market niche. We are also not claiming the superiority of centralized exchanges; notably, centralized exchanges can steal all user funds, the strongest form of unfairness. Nonetheless, it is important to remain aware of the tradeoffs made to achieve this decentralization and their potential negative effects on users of a certain exchange architecture. Someday, someone may devise a decentralized exchange architecture that doesn’t suffer from any of the limitations we’ve enumerated. This challenge remains an open problem.

As a final note, we observe that 0x and EtherDelta provide only a trading platform for tokens that circulate on a single blockchain. They don’t support trading BTC for LTC and so on. As our discussion illustrates, achieving even this modest goal with adequate performance and security is a herculean task for decentralized exchanges. Support for cross-chain trading requires far more complex architectures, see for example KyberNetwork and Omega One. Decentralized exchanges that enable cross-chain trading are likely to exhibit all the problems discussed in this blog post, and more.

    [1]    We are deliberately vague about the mechanism of off-chain communication since it isn't relevant to the scheme. A simple example would be the use of email using a simple directory-like smart contract to associate Ethereum addresses with their owner’s email addresses.
Disclosure
In the interest of transparency, we would like to note that one of the authors of this blog post, Phil Daian, is an advisor to Swap, a P2P trading protocol that is an alternative to decentralized exchanges. Swap is not immune to many of the issues identified in this blog post, given that an Indexer, the Swap mechanism for counterparty discovery, could play a role much like that of a Relayer plus Order Book. (The Swap whitepaper provides insufficient information for detailed analysis.)
Bitcoin's Impending Accounting Disaster

Hacking Distributed
 
Bitcoin's Impending Accounting Disaster

Image/photo
Some idiot is making it rain Bitcoin Cash, and it's not good.

Once again, there's a brewing accounting disaster and ensuing drama to follow in Bitcoin land. This next one has the potential to outdo past accounting disasters, and because the topic is politically charged, can lead to all kinds of upheaval in its aftermath. It's also instructive to examine from a techie perspective, for it sheds light into the kinds of financial scams that people run.

At the center of this debacle is a new currency called "Bitcoin Cash." Bitcoin Cash is a new coin that is derived from Bitcoin in two ways: the code is very similar, except it has the capacity to clear more transactions per second, and it shares the same financial history. That is, if you own a Bitcoin (BTC), come August 1st, you'll also own a Bitcoin Cash (BCC).

This distribution technique is similar to how the new Brazilian real was distributed to the masses, or how stock shares are distributed in the case of a spin off. If you hold a share of Google, you end up holding both a Google and an Alphabet share after the split.

It turns out that at least one, possibly more, cryptocurrency exchange gets this accounting wrong. This creates the opportunity to make money out of the thin air. At the same time, it also creates the possibility for exchanges to go bankrupt.

The Rules
Here is the distilled version of how the popular exchange Bitfinex plans to account for the BCC coin distribution:
The token distribution methodology will be:
  • All BTC wallet balances will receive BCC
  • Margin longs and margin shorts will not receive BCC
  • Margin shorts and margin longs will not pay BCC
  • BTC Lenders will receive BCC

This is a good time to check up on your ability to detect scam opporunities. Do you immediately see how you can abuse these rules to make money?

If you need a hint, it's worth pointing out that this distribution method is in direct opposition to Bitfinex's own guidelines on how coin distributions ought to work.

Ok, those of you who can see the scam and have loose morals have probably stopped reading at this point and are busy positioning themselves for their own little scam. Let's now go over how the trick works for the rest of us normal people.

The Scam
The problem has to do with how positive BTC balances are unconditionally rewarded with BCC, while negative balances are not accounted for properly.

In particular, imagine our favorite player Alice. Suppose that she has 1 BTC, and she deposits it at Bitfinex.

Stuart (the Scammer) reads the rules above, and creates an account on Bitfinex. He then margin-shorts 1 BTC. That is, he borrows Alice's 1 BTC, and sells it. He now owes 1 BTC to Alice.

Stuart then, in a funny trade, buys his own margin-short with cash. He now owns 1 BTC, and owes 1 BTC to Alice. His position is market neutral and he carries no risk. Alice also owns 1 BTC.

Then the split happens. Bitfinex decides to credit both Stuart and Alice with 1 BCC, each! That is, Bitfinex erroneously creates a liability of 2 BCC. Meanwhile, they only actually own 1 BCC.

Bitfinex immediately becomes a fractional reserve, and simultaneously inflates the BCC supply.

Takeaways
This goes counter to all kinds of established accounting principles, including Bitfinex's own guidelines for how to account for coin splits.

It is a terrible outcome for BCC. BCC price will be lower than its natural level as a result of this fraudulent accounting practice.

Of course, the BCC that Bitfinex creates out of the thin air like this is not real BCC. The BCC price at Bitfinex should not be comparable to BCC price elsewhere. But of course, the market will not know how to compare or price in the bankruptcy risk. As a result, this will depress the actual BCC's price. It is, in effect, blowing through BCC's 21M cap by manufacturing fake BCC.

It is also terrible for Bitfinex, in that they can lose money and even go bankrupt, because they are creating more liabilities for themselves than assets. But Bitfinex are old pros at running a bankrupt exchange. They previously lost $60M, socialized the losses across their user base, issued tokens for the loss, then bought their own tokens back for pennies on the dollar, thus appearing to come out of bankruptcy. Their Tether contracts ended up growing in "assets" at a time when their banking operations were interrupted, leading many to conclude that Tethers were unbacked and untethered securities despite their marketing and name. The next exchange on the Fed's radar for flaunting laws, accounting practices and plain old ethical behavior, after BTC-E, ought to be Bitfinex.

The Scam is Underway
Are people actually taking advantage of this loophole? You bet!

As one trader puts it Short 1 btc. Buy 1 btc. Get 1 bcc free :).

The short interest at Bitfinex is at historical highs. And yet it's not due to negative sentiment -- these are neutralized short positions, where the same person is both shorting and going long, just to game the system. As a result, the Bitcoin price is unaffected even while huge short positions are being developed just to game the broken accounting.

The real losers at the end of this will be all of us, regular cryptocurrency enthusiasts. The SEC, in its landmark decision where it rejected the notion of a Bitcoin-backed ETF, cited specifically the unprofessional way in which most Bitcoin exchanges are run. The end result of all these small games is that, yes, some people make a few coins in the short run, but the cryptocurrency cause is set back, and the reputational damage punishes everyone for years to come.
  • Many thanks to two accounts dedicated to ferreting out bizarre behaviors in the crypto space, Cukefinex Auditor and BitCrypto'ed, for pointing out the Bitfinex shenanigans. They are beacons of sanity and you should follow them.
An In-Depth Look at the Parity Multisig Bug

Hacking Distributed
 
An In-Depth Look at the Parity Multisig Bug

Image/photo
Multiple signatures are better than one.

This year’s IC3-Ethereum bootcamp brought together the Ethereum Foundation’s top developers, IC3 students and faculty, and dozens of others from industry and academia. We worked together over the course of a week on ten exciting, intensive development projects, and ended with a bang on the last day. The Ethereum wallet rescue group (with a little help from a couple of IC3ers) scrambled to respond when 153,037 Ether (worth $30+ million) was stolen from three large Ethereum multisig wallet contracts.

The MultisigExploit-Hacker (MEH), as he, she, or they are known, exploited a vulnerability in the Parity 1.5 client’s multisig wallet contract. A fairly straightforward attack allowed the hacker to take ownership of a victim’s wallet with a single transaction. The attacker could then drain the victim’s funds, as happened in these three transactions once the wallets were compromised. The victims were three ICO projects: Edgeless Casino, Swarm City, and æternity.

In the following we will give an in-depth technical explanation of the hack, describe the white-hat response, and draw some lessons about how such breaches might be prevented in the future.

How the attack worked
There are many reports that the vulnerability was due to the simple omission of an “internal” modifier that made it possible for anyone anywhere to take ownership of an existing wallet due to Solidity’s “default-public” policy. While it is true that the addition of the right modifiers would have prevented the attack, the attack is a little more clever than this would suggest.

The vulnerable MultiSig wallet was split into two contracts to reduce the size of each wallet and save gas: A library contract called “WalletLibrary” and an actual “Wallet” contract consuming the library. Here is a toy version of WalletLibrary:

// called by constructor
function initWallet(address _owner) {
owner = _owner;
// … more setup ...
}

function changeOwner(address _new_owner) external {
if (msg.sender == owner) {
owner = _new_owner;
}
}

function () payable {
// ... receive money, log events, ...
}

function withdraw(uint amount) external returns (bool success) {
if (msg.sender == owner) {
return owner.send(amount);
} else {
return false;
}
}
}

WalletLibrary looks pretty boring: Beyond some initialization code that will be called in the constructor of Wallet, WalletLibrary provides the basic functionality you would expect from a wallet: Anybody can deposit money into the wallet, but only the owner can withdraw her funds or change the owner of the wallet.

Here’s an example, simplified contract that could be using this WalletLibrary:

function Wallet(address _owner) {
// replace the following line with “_walletLibrary = new WalletLibrary();”
// if you want to try to exploit this contract in Remix.
_walletLibrary = ; _walletLibrary.delegatecall(bytes4(sha3("initWallet(address)")), _owner); } function withdraw(uint amount) returns (bool success) { return _walletLibrary.delegatecall(bytes4(sha3("withdraw(uint)")), amount); } // fallback function gets called if no other function matches call function () payable { _walletLibrary.delegatecall(msg.data); } }

This time, the code looks more complex. Notice the use of delegatecall throughout the contract. delegatecall is designed to enable the use of shared libraries, saving precious storage space on the blockchain otherwise wasted in duplicating widely used, standard code.

delegatecall works by executing the program code of a contract in the environment (and with the storage) of its calling client contract. This means that the library code will run, but will directly modify the data of the client calling the library. It essentially is as if the code of the library had been pasted into the client issuing the delegatecall. Any storage writes inside the delegatecall will be made to the storage of the client, not the storage of the library. delegatecall allows a client contract to delegate the responsibility of handling a call to another contract.

At the EVM level, a contract is just a single program that takes a variable-length binary blob of data as input and produces a variable-length binary blob of data as its output. A transaction in EVM provides an address and some data. If the address holds code, this data is used in a “jump table” like structure in the beginning of the contract’s code, with some of the data (the “function selector”) indexing jumps to different parts of contract code using the standard encodings described in the Ethereum Contract ABI specification. Above, the function selector for calling a function called initWallet that takes an address as its argument is the mysterious looking bytes4(sha3("initWallet(address)")).

Now that we understand delegatecall and how function selectors work, we can read and understand the Wallet contract. To begin with, we have a simple constructor that delegates the initialization of the contract’s state to WalletLibrary. This is followed by a withdraw function which -- once again -- delegates its task to WalletLibrary.

Finally, we want our wallet to be able to receive funds. This is commonly handled with a Solidity construct called a fallback function. A fallback function is a default function that a contract is able to call to respond to data that doesn’t match any function in the lookup table. Since we might want all sorts of logic to be triggered upon the receipt of funds (e.g. logging events), we again delegate this to WalletLibrary and pass along any data we might have received with the call. This data forwarding also exposes WalletLibrary’s changeOwner function, making it possible to change the Wallet’s owner.

Wallet is now completely vulnerable. Can you spot the vulnerability?

You might have noticed that the initializeWallet function of WalletLibrary changes the owner of the Wallet. Whoever owns the Wallet can then withdraw whatever funds are contained in the contract. But as you can see, initializeWallet is only executed in the constructor of Wallet (which can only run once, when Wallet is created), and Wallet doesn’t itself have an initializeWallet function. Any calls sending this function selector to Wallet in a transactions’ data won’t match.

So, the attacker cannot call Wallet.initializeWallet(attacker) to change the owner of the wallet and we are safe after all‽

As it turns out, the implementation of the fallback function means that we are not. As we already saw, a fallback function is a default function that a contract is able to call to respond to data that doesn’t match any function in the lookup table. The intent is to allow contracts to respond to receipt of funds and/or unexpected data patterns; in our wallet, it both enables funds receipt and allows for functions to be called in the wallet library that are not explicitly specified in the wallet.

One use of such a “generic forward” feature could be upgradeability, with the pattern perhaps even recommended as a security precaution for the event that the need for additional functions not anticipated at release time became known: By allowing the wallet’s owner to change the address of the library contract, one could keep the wallet with its funds at the same address while changing the underlying implementation. In the Parity contract, it is likely that forwarding data was only done to save gas costs, as the contract is not upgradeable and all forwards could have been made explicit at compile time. Instead, this implicit default forwarding was used over explicit forwarding to expose certain functions like revoke.

So, when an attacker calls Wallet.initializeWallet(attacker), Wallet’s fallback function is triggered (Wallet doesn’t implement an initializeWallet function), and the jump table lookup fails. Wallet’s fallback function then delegatecalls WalletLibrary, forwarding all call data in the process. This call data consists of the function selector for the initializeWallet(address) function and the attacker’s address. When WalletLibrary receives the call data, it finds that its initializeWallet function matches the function selector and runs initializeWallet(attacker) in the context of Wallet, setting Wallet’s owner variable to attacker. BOOM! The attacker is now the wallet’s owner and can withdraw any funds at her leisure.

In reality, the initializeWallet function was more complicated and took more parameters, but the principle of the attack is exactly the one described above. You can see one of the initializeWallet calls of the attacker; the attacker then immediately withdrew the funds, earning her 26,793 ETH (or ~6.1 million USD). Not bad for two function calls and 60 cents in gas cost!

If initializeWallet had been marked as internal, there would have been no corresponding entry in the jump table, making it impossible to call initializeWallet from outside the contract. If initializeWallet had checked for double initialization, there would also have been no problem. Adding to the confusion is the fact that certain functions that are supposed to be callable from outside the contract are marked as external; one could easily wrongly assume that all functions not marked as external aren’t visible from the outside. In the Parity’s patch to the vulnerable contract, a modifier was added to a helper function of the vulnerable wallet initialization process to throw an exception if the attacked initialization function was re-called.

The response
A white-hat recovery team (MEH-WH) developers identified and drained all remaining vulnerable wallets into this wallet. They recovered a total of $78 million worth of tokens (half the value being BAT and ICONOMI) plus 377,105+ ETH (around $72 million). The funds will be returned to their owners as noted on r/ethereum:
If you hold a multisig contract that was drained, please be patient. [The MEH-WH] will be creating another multisig for you that has the same settings as your old multisig but with the vulnerability removed and will return your funds to you there.

This is all well and good for the recovered funds, but the stolen funds are in all likelihood unrecoverable. The Ethereum community cannot, for instance, easily execute a hard fork as they did in the case of The DAO. The DAO had a built-in 34-day delay, during which the stolen funds were locked into the contract and subject to recovery. The MEH only needs to identify compliant exchanges to cash out or convert to ZEC to retain the stolen funds with full anonymity. The MEH has already cashed out small amounts, as in this roughly 50 ETH transaction at Changelly.

Unless the hacker trips up, the community will have to resign itself to the loss of the money---more than in any U.S. bank robbery -- and an enduring mystery over the identity of the thief / thieves. In case you’re wondering, none of our ten bootcamp projects involved stealing ETH from multisig wallets. :)

Lessons
Looking at the history of the vulnerable contract in Parity’s github repository, we find that the contract was first added as a complete blob of code on December 16 of last year in commit 63137b. The contract was edited extensively once, on March 7 in commit 4d08e7b and then wasn’t touched until the attack occurred. Since the contract was originally added as one big blob, it was likely copied from somewhere else, making its provenance in development unclear. Note that the first version of the contract already contained the vulnerable code.

It is hard to believe that such an large (and valuable!) vulnerability could have gone undiscovered for such a long time. However, in light of the contract’s length and complexity and the complex interactions between Solidity’s fallback functions, its default-public visibility of functions, delegatecalls, and call data forwarding, that enable the attack, this seems less surprising. At least one other multisig contract had an analogous bug that stemmed from the lack of a function modifier.

We believe that there are multiple levels on which lessons should be drawn from this attack:

First of all, we recommend that Solidity adopt a default-private level of visibility for contract functions. This change would have likely prevented this exploit and others like it. This may be an opportunity to batch a number of other safe usability related changes, much needed additional types, and solutions to common gripes into Solidity. It's also an opportune time to think about versioning at the source language level, to be able to easily introduce new features into the language without having to worry about backwards compatibility.

In a more general sense, we believe that this attack was the result of security’s oldest enemy, complexity: It seems likely that the missing “internal” function modifier would have been discovered by the developers if Wallet had just been a single contract instead of delegatecalling out to WalletLibrary. Even without this modifier, Wallet would not have been vulnerable as long as Wallet’s fallback function wouldn’t have unconditionally forwarded any calldata to WalletLibrary, exposing unexpected functions able to modify the data in Wallet.

Interestingly, this specific attack may not have been caught by testing as implemented by most developers, since the vulnerability wasn’t caused by incorrect behaviour of a function, but rather by the unexpected exposure of a function (that behaved correctly) to the public. Nevertheless, we do, of course, strongly recommend that smart contract authors thoroughly test their contracts, and a test policy that included testing for function visibility on every function would have exposed the issue.

The creation of a rigorously followed best practices guide for testing and smart contract review that requires that visibility assumptions be made explicit and tested is thus, we believe, one of the strong lessons from this attack. Today, it is not uncommon to see large contracts deployed with only a handful of unit tests, with little to no reasoning about interaction between contracts, and with unit tests that do not even accomplish full statement or decision coverage. Beyond these glaring omissions of basic software quality techniques standard in the space, it remains apparent that there is still work to be done in understanding best practices for high level tooling and language design for smart contracts.

The Parity project has released a post-mortem giving a high level overview of the attack and discussing the steps Parity will take in the future to ensure that such an attack will not happen again. Many of their conclusions agree with the ones we made here.

Acknowledgements
We would like to thank Everett Hildenbrandt of the KEVM project for his feedback and helpful suggestions on explaining the attack.
Parity's Wallet Bug is not Alone

Hacking Distributed
 
Parity's Wallet Bug is not Alone

A bug was found in Ethereum's Parity Multisig Wallet yesterday, wherein anyone could take ownership of any multisig wallet and usurp the funds. And it looks like someone did just that, emptying out around $30M from three multisig addresses affecting three ICOs. The root cause of the bug was a missing "internal" identifier, where a function that should only have been called internally got exposed to everyone.

This is not the first instance of such a bug. The point of this blog post is to underscore some takeaways that might make sure that it's the last. I'll do this by describing a bug I found and fixed in BitGo's multisig wallet last year, and making the case for a general fix.

The Backstory
Image/photo
I took time away from this to look at BitGo code. I was younger and dumber.

I was sitting on the beach at the summer house (which I had bought with my proceeds from the DAO hack [1]) when I got a message from Benedict Chan and Ben Davenport at BitGo. They wanted me to take a look at their multisig wallet. I don't normally do code reviews -- they are hard work, carry too much reputational risk, and with some probability, people will misrepresent my limited involvement as some kind of endorsement of their entire business proposition. Further, they didn't offer any compensation and IC3 had no relationship with BitGo. But I liked BitGo at the time, mostly because they employed great people like Ben Chan and Jameson Lopp. Plus it was a lazy summer afternoon, I was sitting by the Med, with the crickets doing their thing, and the wind wasn't up yet to kiteboard. So I decided to spend about 15 minutes to look, through the glare on my laptop screen, at their code.

This is a good time to look through their code yourself and see if you can spot any vulnerabilities. It should be a little easier given the context. Here it is.

If you're feeling adventurous, see if you can spot the second attack. There isn't just one, but two related and distinct vulnerabilities.

In case you are feeling lost, like I initially felt, here's some orientation. This code is different from the usual multisig pattern one would build on Ethereum. BitGo evidently decided to replicate their Bitcoin workflow in Ethereum, so they pass around an object from one party to another, building the multisig transaction off-chain. In contrast, the natural approach in Ethereum would have been to keep track of the number of signatories inside the contract. It took me several minutes to figure out this design decision. Around minute 12, I spotted the bug.

Do you see the problem?

Spoilers follow.

The big issue is that any idiot on the internet can call tryInsertSequenceId() with any value they like. And a natural thing to call it with is, of course, a bunch of numbers close to MAXINT. After that, the multisig wallet is stuck. It will not be able to issue any further transactions. Any funds in the contract will be stuck forever. Well, either forever, or until BitGo is able to lobby King Vitalik [2] and get him to agree to a hard fork. Needless to say, that's in jest; I've recently read one too many rants by Bitcoiners who are upset that Ethereum is gaining dominance. The truth is, Vitalik couldn't pull off a hard fork even if he wanted to. BitGo would have to convince the entire Ethereum community to swap the state of their contract to re-mobilize their funds. Chances of that happening are somewhere between an ice-skating vacation in hell, Bitcoin Core adopting something invented by someone who does not go to extra lengths to appease their fragile egos, and Craig Wright actually signing something with the genesis key -- squarely in the "not going to happen" category.

The bug would have been averted by marking tryInsertSequenceId() as private.

Not at all ironically, the bug in the BitGo multisig contract is due exactly to the same root cause as in the Parity multisig smart contract.

A Second Vulnerability in the BitGo Contract
Image/photo
Safe defaults lead to less time on the laptop, more time on the water.

There is a second vulnerability in this contract. As I wrote to BitGo
I'm also worried that someone (eg equivalent of a hacked Bitfinex) could manipulate the infrastructure around this wallet contract so as to make the other party (BitGo) skip over most the sequence id space and sign 10 legitimate transactions with really large seqids, then be unable to sign any more transactions.

This is an attack on the BitGo API via a compromised client. Even if the private or internal modifier had been present, the contract would have been open to this kind of attack. These kinds of API design issues are fairly tricky to spot. It's one thing to verify the correctness of a contract against a formal spec, another thing to verify it against an implicitly assumed but not actually enunciated spec, and a different thing altogether to see if the spec is safe given the operating conditions.

I'm fairly paranoid, so I would have hardened the API by ensuring that the smart contract does not allow one to advance through the identifier space non-sequentially. That is, I'd rule out skipping around. Counting one by one all the way up to 2^256 would not constitute a feasible attack -- that DoS attempt would be preceded by the heat death of the universe. That would prohibit exhaustion of sequence ids by misbehaving clients.

Takeaways
Image/photo
Every big contract is simultaneously a bug bounty and a lambo.

I personally had a good run finding critical bugs, but this portends a dangerous trend. Specifically, with my co-authors Dino Mark and Vlad Zamfir, I found 9 bugs in the DAO, one of which was used by the DAO hacker. But I found-yet-incorrectly-dismissed the otherbug that the DAO hacker used. We seem to be living through a phase particularly rich in critical bugs.

There are some depressing takeaways here. Two separate multisig wallet contracts, which have been scrutinized heavily, were vulnerable to the same kind of bug. This reifies the finding from the 1970's that N-version programming tends to suffer from bugs in the same critical points. Even if one spends the effort to implement N independent versions of the same functionality, they might fail at the same time or around the same breaking points. True independence of failures is difficult to achieve.

Worse, many eyeballs don't make code safe. Just about every ICO, trust and company used the Parity multisig wallet, and that code was considered well-tested. One could perhaps try to make the case that Parity is a volunteer-run, open source project, that professional software houses have their act together better. But that'd contradict the fact that BitGo got bit by the same exact bug. So, clearly, the problem here is systemic and needs a systemic solution. As the database community painstakingly discovered, most programmers cannot handle power: they need sane defaults and mechanisms that fail safe when the programmer is negligent.

And there is also a positive lesson for language design. These kinds of bugs would be greatly reduced if the default policy in Solidity were "default-private." Almost every other language uses default-private, forcing a smart contract programmer to take extra steps to expose a procedure to outsiders. The tradeoff in Solidity is, frankly, wrong. Default-public is too error prone.

I'd urge the Solidity project to change this behavior. Make fields and functions in a contract bedefault-private. Such a change does not affect already-deployed smart contracts, does not require a fork, and can even be made optional with the addition of a compiler flag. It's relatively trivial to affect compared to the impossibility of recovering lost funds.
The BitGo After-Story
Image/photo
Can one blame Romus or Romulus for their upbringing?

Some of you may be wondering how BitGo handled this episode.

I notified BitGo of this issue and theypromptly fixed their code. They had apparently removed the "private" modifier to facilitate unit testing.

This brings up yet another takeaway -- there ought to be some way of dropping private modifiers during testing, and only during testing. Mutating one's code to perform testing is not good practice.

BitGo did not believe that the second issue would be a problem in practice, as they thought that the surrounding client code would not issue non-consecutive sequence numbers. It's their call and their own risk assessment. Recall that I wasn't getting paid for any of this and had no skin in the game, so there was no point in contesting their assessment. I'm told that BitGo ultimately did not launch a product based on Ethereum.

I wrote a nice and friendly email to BitGo:
Great to hear that that was useful. Much better to catch potential issues now, than to try to deal with the fallout from a multi-million contract that is stuck. I don't know if BitGo has a Technical Advisory Board, but if it does, I'd consider it. That'd create an open channel for interactions like this. Otherwise, the chances of catching me on vacation with cycles to spare are, regrettably, fairly low.

I never heard a word from BitGo for the next 4-5 months or so. I chalked that up to most early CTOs in the crypto space having been abandoned by their families at a young age and been raised by wolves. I was surprised, however, when Ben Davenport publicly adopted a rabid small block stance and supported the small troll squad known as Dragon's Den. When I emailed him about the impact of unprofessional conduct on the whole space, he sent me the following lovely message:
I understand you are currently on sabbatical from Cornell. Are your fellow faculty members aware of the attention that's being drawn to the Cornell CS department due to your public statements? Hope your activity during your sabbatical year doesn't influence your tenure committee too much.

You all, who realize that I received tenure many years prior, can imagine the bemused look on my face at the implied, yet toothless, threat on my employment. Tenure is intended precisely to stem these kinds of threats on academic freedom.

In the last two months, I had the pleasure of meeting Mike Belshe, CEO of BitGo, in person, who apologized and thanked me for this episode, almost a year after the fact. Belshe is a grown-up and they continue to employ excellent engineers. Regardless, I've decided to have absolutely nothing to do with BitGo in a professional capacity, and, coupled with the Bitfinex hack for which I consider BitGo partly responsible, I've decided to steer clear of their products.

--

    [1]    Just kidding.
    [2]    Also just kidding.
Atomically Trading with Roger: Gambling on the success of a hardfork

Hacking Distributed
 
Atomically Trading with Roger: Gambling on the success of a hardfork

Overview
We have designed a new protocol for Bitcoin and Ethereum that lets users bet on the outcome of a hardfork. Prior to the hardfork, two parties can deposit coins and commit to a wager; after the hard fork occurs, the coins are swapped on both forks. Our protocol is inspired by Loaded's challenge to Roger to swap 60k coins in the event of a Bitcoin Unlimited hardfork.

Our story begins
Satoshi Nakamoto's 1MB block size limit was activated on 12th September 2010 as an anti denial of service mechanism. Four months later, Satoshi Nakamoto left the community without removing the block size limit. His departure has led to the block size debate.

Over the years several projects have attempted and failed to adjust this block limit as changing Bitcoin's consensus rules appears to require significant support from miners, developers, exchanges, and validators.

Bitcoin Unlimited (BU) is one such proposal to adjust the block limit by a hardfork. Currently around 54% of mining power is signaling support for it. BU includes a new consensus rule called emergent consensus that allows miners to govern the block size amongst themselves.

As with any hard fork, the danger is that the blockchain could split in two upon activating the new consensus rule. One fork would follow the 1MB consensus rules; the other fork would follow the new emergent consensus rules.

Loaded's challenge to Roger
It is worth highlighting that members of the Bitcoin community perceive that a blockchain split is highly probable if BU is successful. In fact, this perception has led to Loaded (a wealthy member of the Bitcoin community) challenging Roger Ver (a vocal advocate of Bitcoin Unlimited) to put his money where his mouth is and to swap at least 60k coins (i.e. a 1:1 trade) if the blockchain does indeed split into two distinct forks.

The best part of this story is that Roger responded within two days to signal his willingness to pursue the bet.
It goes without saying that the Bitcoin community is highly excited at the prospect of the bet. Some of the notable posts and articles surrounding the bet:Of course before we can be excited about the bet... a single question remains:

What is the best technical approach for Loaded and Roger to pursue this bet?

Loaded stated that he would prefer if the trade could be performed as an atomic swap.

Anyone familiar with atomic swap protocols in Bitcoin will instinctively think of Tier Nolan's protocol after reading Loaded's post. In fact, I (Patrick McCorry) responded to Ethan Heilman on twitter to suggest that Loaded and Roger use TierNolan's protocol.

Ethan Heilman identified that the TierNolan protocol is not suitable for the bet since Roger and Loaded cannot use TierNolan to commit to the trade prior to the activation of Bitcoin Unlimited's hardfork. However Ethan's second reply about using replay protection to build a new atomic trade protocol led to an eureka moment.

Facilitating the Gamble
Together we developed a new atomic trade protocol to allow Loaded and Roger to deposit coins prior to the hard fork's activation and perform the atomic swap after the blockchain splits. In fact, we propose a protocol for both Bitcoin and Ethereum.

Bitcoin Atomic Trade Protocol
A key design decision for the Bitcoin atomic trade protocol was to ensure it was compatible with Bitcoin as deployed today (i.e. in the absence of a fix for transaction malleability). The protocol has three stages:

Deposit coins. Both Roger and Loaded deposit coins into a single funding transaction.

Off-chain Setup. First, Roger signs a cancellation transaction to Loaded that allows him to cancel the atomic trade if the off-chain setup is not complete.

Next, Roger signs a trade transaction and sends it to Loaded. This transaction allows Loaded to claim both deposits in the non-Bitcoin Unlimited blockchain (i.e. old consensus rules) if Roger reveals the secret A of H(A).

Then, Loaded signs a trade transaction and sends it to Roger. It is worth mentioning that this trade transaction has replay protection to ensure it can only be accepted into Bitcoin Unlimited's blockchain. This transaction allows Roger to claim both deposits if he reveals the secret A of H(A).

Once both trade transactions are exchanged, Roger is required to sign two forfeit transactions and send them to Loaded. The purpose of the forfeit transactions is to lock Roger into the trade such that if he does not reveal the secret A, then Loaded can claim all coins in both blockchains when the trade expires.

Assuming the above steps are complete and Loaded has not canceled the trade, then Roger can broadcast a commit transaction that locks both parties into the trade (i.e. blocking Loaded's cancellation transaction).

Atomic Trade. Roger can broadcast his trade transaction into the Bitcoin Unlimited blockchain once the hardfork occurs. This also requires Roger to reveal the secret A in order to claim both deposits.

Assuming the blockchain does indeed split into two forks, then Loaded can use the secret A to also broadcast his trade transaction in the non-Bitcoin Unlimited blockchain.

Of course, if Roger decides to abort and not claim his coins, then the trade expires and Loaded can claim all coins in both blockchains.

The key insight of this protocol (and bitcoin contracts in general) is that it is difficult to achieve fair exchange in the absence of a transaction malleability fix. In the appendix of our paper we include a second atomic trade protocol for Bitcoin that assumes transaction malleability has been fixed. Not surprisingly the second protocol's design is vastly simpler and is similar to how a payment channel is established, i.e. both trade transactions are signed off-chain before signing and broadcasting the funding transaction.

Ethereum Atomic Trade Protocol
As mentioned, we also designed a smart contract for Ethereum called 'Trade' to perform an atomic trade in the event of a hardfork. An interesting insight of this protocol is that a hardfork oracle can be realised to allow other contracts to detect whether it is in fork-1 (i.e. old consensus rules) or fork-2 (i.e. new consensus rules).

The protocol is straightforward:
  • Both parties audit the the Trade and Hardfork Oracle contracts.
  • Both parties deposit their coins into the Trade contract to lock their deposits until the hardfork activates.
  • Each party withdraws both deposits from the contract in their respective fork after the hardfork's activation.
Of course, the Trade contract communicates with the Hardfork Oracle contract to identify which blockchain it is in before authorising any withdrawal.

Fin
It is exciting that both Loaded and Roger may potentially swap their coins in the event that Bitcoin Unlimited is successful. Of course, our protocol is applicable not just to Bitcoin Unlimited, but any hardfork that includes replay protection. We hope the community have fun reading the paper and if anyone is willing to develop the protocol for use in any future hardfork then please let us know!

p.s. It is also worth mentioning that this paper is great example that using twitter is not always a waste of time... :)

Acknowledgements We want to thank Amy Castor for her constructive comments on an early draft of the blog post.
Twitter, Reddit and 4chan: The Web's Fake News Centipede

Hacking Distributed
 
Twitter, Reddit and 4chan: The Web's Fake News Centipede

The New York Times recently published an example of how information that appeared on a “fringe” community, such as a parody website, managed to creep into mainstream web communities like Facebook and Fox News. Figure 1 depicts how the fake information flowed between the communities involved in this particular example, thus forming a sort of _centipede_ of web communities. This example highlights how fringe communities can influence mainstream web communities by manipulating and spreading unconfirmed information. Before our study, this phenomenon had not been rigorously investigated, and there was no thorough measurement and analysis on how information flows between online communities.

Image/photo
Figure 1: An example of a Web Centipede as presented by The New York Times.

Nevertheless, anecdotal evidence and the aforementioned example suggests that mainstream web communities, such as Facebook and Twitter, as well as “fringe” web communities, such as 4chan and Reddit, are part of the Web centipede of information diffusion. In our technical report, we systematically study Twitter, Reddit, and 4chan with respect to the influence they have on each other, aiming to understand their impact on the greater information ecosystem. More specifically, we study the temporal dynamics of URLs from 99 mainstream and alternative news domains as they appear in these three communities.

The three platforms are quite different, and worthy of a brief explanation:
  • Twitter. It is a mainstream micro-blogging, directed social network where users can share 140-character tweets to their followers.
  • Reddit. It is a social news aggregator where users can post URLs to content along with a title. Users can upvote/downvote the post. The aggregate of the votes determine the ranking of the post, thus determining the popularity and reachability of the content to the users of the platform. The platform is organized into sub-communities called subreddits. Users can create subreddits, each with their own topic and moderation policy. In our paper, we focus on 6 specific subreddits that substantially contribute to the dissemination of alternative and mainstream news: The_Donald (for Donald Trump supporters), politics, news, worldnews, AskReddit and conspiracy.
  • 4chan. It is an imageboard kind of discussion forum: users create a new thread by making a post with a single image attached, and perhaps some text, in one of several boards (69 as of May 2017) for different topics of interest. Users on 4chan are anonymous and boards are monitored by “janitors“ that ensure conversation remains on-topic. However, janitors are generally not concerned about the language used, hence 4chan is often quite a hostile place. Furthermore, there are several examples that highlight 4chan's impact on the Web and the community. For example, a hoax that originated from 4chan about the death of Ethereum's founder resulted in loses of $4 billion in Ethereum's market value. In this work, we looked at the Politically Incorrect board (/pol/), which focuses on discussion of world news and politics.
Below, we briefly describe some of our findings from temporal dynamics and influence estimation analyses.

Temporal Dynamics
Given the set of unique URLs across all platforms and the time they first pop up, we analyze their appearance in one, two, or three platforms, and the order in which this happens. For each URL, we find the first occurrence on each platform and build corresponding “sequences.” E.g., if a URL first appears on Reddit and subsequently on 4chan, the sequence is Reddit→4chan (R→4). These sequences allow us to study and visualize the information ecosystem by utilizing graph modelling and analysis techniques. Specifically, we create two directed graphs, one for each type of news, where the vertices represent alternative or mainstream domains, as well as the three platforms, and the edges represent the set of sequences that consider only the first-hop of the platforms. For example, if a breitbart.com URL appears first on Twitter and later on Reddit, we add an edge from breitbart.com to Twitter, and from Twitter to Reddit. We also add weights on these edges based on the number of such unique URLs. By examining the paths, we can discern the domains whose URLs tend to appear first on each of the platforms. Below we show the graphs built for alternative and mainstream domains.
Image/photoImage/photo
Comparing the outgoing edges’ thickness, we see that breitbart.com URLs appear first in Reddit more often than on Twitter, and more frequently than they do on 4chan. However, for other popular alternative domains, such as infowars.com, rt.com, and sputniknews.com, URLs appear first on Twitter more often than Reddit and 4chan. Also, 4chan is rarely the platform where a URL first shows up. For the mainstream news domains, we note that URLs from nytimes.com and cnn.com tend to appear first more often on Reddit than Twitter and 4chan. On the other hand, URLs from other domains like bbc.com and theguardian.com tend to appear first more often on Twitter than Reddit. As is the case with the alternative domains graph, there is no domain where 4chan dominates in terms of first URL appearance.

Influence Estimation
To estimate how the individual platforms influence the media shared on other platforms we use a statistical model known as Hawkes processes. This method enables us to say with confidence that a particular event (i.e., posting of a URL) is caused by a previously occurring event. For example, we can be confident that an event that happened on 4chan’s /pol/ board (i.e., a URL is posted in a 4chan thread) resulted on an event on Twitter (i.e., the same URL is posted on Twitter), thus denoting influence from 4chan to Twitter. This is particularly useful for modelling the influence of the three platforms, since they are not independent; each one is influenced by the others as well as the greater Web (more details about the Hawkes methodology can be found in the manuscript). For instance, there are someexamples of crazy conspiracy theories that originate from “fringe” communities and have an impact on other web communities, sometimes even ending up being reported by both mainstream and alternative news users.

In our experiments we measure the influence of the 6 selected subreddits from Reddit (The_Donald, politics, worldnews, AskReddit, conspiracy, news), /pol/ board from 4chan and the Twitter platform. Figure 2 shows the estimated total impact of the three platforms on each other, for both mainstream URLs (M) and alternative URLs (A). Twitter contributes heavily to both types of events on the other platforms, and is in fact the most influential single source for most of the other communities. After Twitter, The_Donald and /pol/ also have a strong influence on the alternative URLs that get posted on other communities. The_Donald has a stronger effect for alternative URLs on all communities except Twitter. Yet it still has the largest alternative influence on Twitter, causing an estimated 2.72% of alternative URLs tweeted. Interestingly, we observe that The_Donald causes 8% of /pol/’s alternative URLs, while /pol/’s influence on The_Donald is less, at 5.7%. For the mainstream URLs the strength of influence is reversed. Specifically, /pol/’s influence on The_Donald is 8.61%, whereas The_Donald’s influence on /pol/ is 6.13%. In the following figure we report the percentage of influence for each combination of communities.

Image/photo
Figure 2: Estimation of influence between the platforms for alternative and mainstream URLs.

Conclusion
This work is a first attempt at characterizing the dissemination of mainstream and alternative news across multiple social media platforms, and to estimate a quantifiable influence between them. To achieve this, we analyze thousands of URLs obtained from millions of posts in Reddit, Twitter and 4chan. Ultimately, we find that fringe communities have a surprisingly large affect on well-known platforms. That said, there is certainly more to learn. In the future, we aim to include other information modalities in our analysis, namely textual and image characteristics, to further assess the influence between communities.
Bancor Is Flawed

Hacking Distributed
 
Bancor Is Flawed

Bancor just did their Initial Coin Offering (ICO) last week and raised a record $144M within a few hours. They now hold the record for the biggest crowd-funding, ever, in the history of mankind.

We don't want to dwell too much on what this illustrates about the current ICO craze. It's a fact that raising that much cash through a standard VC process would require a credible team, multiple rounds of funding, with much due diligence and milestones along the way. None of that happened here -- Bancor went from appearing on the scene 5 months ago to raising 9-digits cash with no demonstration that their scheme actually works.

In this post, we want to quickly make the case that their approach is flawed. To recap, they propose a scheme to provide liquidity for digital assets, using a smart contract. In essence, they propose a public algorithm by which they can always propose a bid/ask price for other people's coins. Now, a flawed approach doesn't mean that what they have is exploitable the way The DAO was, though we detail some immediate problems with the code below. What we mean is that the contract, as implemented, is far from meeting its purported narrative, even if no one takes advantage of the exploit.

The quick takeaway is that Bancor can be gamed by miners, and, even if the miners are naive or benevolent, will always trail the real market. It provides no efficiency guarantee during this discovery process, and will likely waste its reserves on market price discovery. You should think twice before you layer a coin on top of Bancor.

Let's do a quick walk through the red flags we encountered as we read the code and documentation for Bancor tokens, known as BNT.

Issues with Bancor Fundamentals
  • Bancor uses lots of mumbo jumbo terminology.
Bancor addresses the "double coincidence of wants" problem in economics through an "asynchronous price discovery" mechanism that blah blah blah buzzwords blah and more buzzwords. Half of these buzzwords aren't even real. "Asynchronous price discovery" is a franken-word they made up. It borrows asynchronous from distributed systems and "price discovery" from economics. The crowds eat this stuff up, but in reality, it's just a giant red flag -- there's no content here.

Let's move on, for it's possible to have a good idea underneath fluffy marketing.
  • The core problem they want to address, "Double Coincidence of Wants" is not a real problem.
"Double coincidence of wants" is a real problem in economics today in the sense that the "itsy bitsy spider" problem is a real problem in zoology -- that is, it's something one might learn in grade school, and it's completely irrelevant in the real world.

To be fair, you might indeed come to the market with two rabbits one day and I might come to the market with two chickens on the same day. I might also have an aversion to rabbit meat and a family history of mal de caribou. We would then be unable to conduct a trade.

In reality, this never happens, because...
  • One can always use ether as a medium of exchange.
There already exists a common currency through which we can trade. It's called ether, and we can use it no matter which token pairs we want to trade, because those very tokens are, by definition, implemented on top of Ethereum and were purchased with ether in the first place. Using BNT tokens is like stepping into a kid's swimming pool, placed in an ocean.

The entire point of the underlying currency, ether, is to serve as the medium of exchange for the diverse assets built on top. Sure, we can always layer BNT on top, and use BNT underneath the new Bancor-based tokens, but there would be little point in doing so besides creating a money flow for the people behind Bancor. For every coin they design that uses Bancor, we can design a more efficient version that doesn't use Bancor.

In short, the BNT tokens are for show. They are not necessary.
  • Bancor is essentially a central bank strategy for automatically setting a dynamic peg for new coins.
Behind the hype, Bancor comes down to a very simple idea: it's a smart contract that automatically provides a buy and sell price for a new coin. This is known as a market maker.

Let's suppose that you decide to create your own coin called X. You hype up the X ICO, sell $100M of X, and decide to back it with $10M of BNT. This is your reserve.

What Bancor proposes to do is to create a market for your coins by automatically buying and selling them for prices that would preserve the ratio of your reserve to the total supply. That is, depending on how much reserve the contract has outstanding, it will automatically offer a price for the X tokens. If the reserves are, say, $12M BNT, then it will offer to buy back X coins for higher prices, to bring the reserve fraction back in line to the usual level. If the reserves are low, it will offer lower prices. So you can always buy or sell into the contract, even if there is no one else to buy or sell to.
  • That's it. That's the whole idea.
It's only 40 lines of code.

Now, there is nothing wrong with raising $3.5M per line of code, if indeed there is a certain technical advantage that those lines of code possess.
  • Everything Bancor can do for you on chain, you can do by yourself off chain.
You yourself could easily have held that $10M in reserve, and you could have intervened in the market at your leisure. If you wanted to, you could follow the exact same algorithm as Bancor and achieve the exact same results. There is no value to be had from using Bancor.

Let us repeat that: in terms of controlling the price of the X token, there is absolutely nothing to be gained by using the fixed Bancor strategy. Whatever equilibrium price Bancor would achieve for you through its on chain management, you could have achieved while managing the reserve yourself, off chain.

To be fair, a Bancor proponent would say, "but you are committing provable reserves to your currency." To which the answer is, "there are many other ways of proving your reserves, none of which tie you down to a dirt simple and flawed strategy for life."
  • It is much better to manage the reserves manually than to commit to the Bancor strategy.
If you held the reserves yourself and issued buy and sell orders, like everyone else, you could not only follow the Bancor strategy to the letter if you liked, but you could use any other strategy that you preferred. You'd have the benefit of the immense neural network that you carry behind your eyes, and the freedom to switch strategies at any time.
  • The Bancor strategy sets prices independent of the market.
The prices that Bancor offers for tokens have nothing to do with the actual market equilibrium. Bancor will always trail the market, and in doing so, will bleed its reserves. A simple thought experiment suffices to illustrate the problem.

Suppose that market panic sets around X. Unfounded news about your system overtake social media. Let's suppose that people got convinced that your CEO has absconded to a remote island with no extradition treaty, that your CFO has been embezzling money, and your CTO was buying drugs from the darknet markets and shipping them to his work address to make a Scarface-like mound of white powder on his desk.

Worse, let's suppose that you know these allegations to be false. They were spread by a troll army wielded by a company with no products, whose business plan is to block everyone's coin stream.

What's your best strategy if you were in control of your $10M in reserves and were manually setting prices?

We don't know about you, but we'd hold the reserves tight and assuage the market. Maybe hold a press conference with the CEO, have the CFO show the books to an auditor, and present a sober and somber CTO describe how he was just making ginger bread houses with powdered confectionary for a fundraiser when he happened to sneeze. At the end of such a painful episode, we'd have battle scars, but also $10M in the bank.

If you used Bancor, your Bancor smart contract would have no knowledge of what is happening out there in the real world. It wouldn't know the market movements, it wouldn't know where the coin ought to be, and it would follow its blind strategy of offering bid/ask prices. That strategy involves making a market through thick and thin, without any information about reality. In fact, that reality is determined purely by external markets, and the contract will, unstrategically, use its reserves to discover and match what the markets demand of it at that instant.

In this case, Bancor would offer ever decreasing prices for X coins during a bank run, until it has no reserves left. You'd watch the market panic take hold and eat away your reserves. Recall that people are convinced that the true value of X is 0 in this scenario, and the Bancor formula is guaranteed to offer a price above that. So your entire reserve would be gone.
  • The Bancor strategy fails to capitalize on excess value
Now, a Bancor proponent would say "ok that was bad, but you're not giving us the full story. After your press release, people would start buying your coins, and the contract would rebuild its reserves."

Ok, let me illustrate what happens on the upside, and make the case that what they are saying is correct, but also incredibly inefficient. It's like saying "hey, your nerves do grow back after spinal injury." Yes, they do. Not so clear that you'll walk again.

Let's imagine that on the day of your big press conference, with the CEO, clean books, sober CTO and a new head of HR, your engineering team announces a new deterministic, asynchronous consensus protocol that takes a constant number of rounds [1], and a perpetual motion machine [2]. The crowds now love you. They go from dumping your shares at any price to fighting each other tooth and nail to buy your shares. In the time between ethereum blocks, a single X is worth infinity dollars on third-party exchanges. You could now literally sell just a single coin and retire forever.

But instead, you're using the Bancor strategy. The smart contract doesn't know that these changes are taking place. What it will do is offer to sell that first X for dirt cheap. It will fail to capitalize, on your behalf, on the difference between infinity and its sad, algorithmically determined low price. It just doesn't know. That extra money will get burned as miners' fees, as people try to outbid each other to own this token at the huge discount offered by the oblivious Bancor platform.

Essentially, we showed what happens when the true market price follows a step function between two extremes. The prices offered by the Bancor market making 40-liner will not follow this step function in tandem -- it is necessarily inefficient. That inefficiency is wasteful and gameable.
  • The algorithmic dampening provided by Bancor isn't desirable for already liquid assets whose value is unstable.
The previous two scenarios explored two extremes. But, to be fair, the following argument could be made in the steady-state case: "if your coins are locked up in this market maker, you lose the ability to insider-trade on the knowledge that most of the rumors about the CTO and CFO are false. However, this is simply a more general tradeoff between flexibility on one side and reliability on the other side -- although you deny yourself the flexibility to make extra profits on private knowledge, your users gain the comfort of knowing that there exists this market maker which will dampen price movements, and that it will not go anywhere."

This is true, the reserves do dampen price movements. If the price is going to be doing some ups and downs around a single mean value, Bancor can help facilitate trades by acting as a market maker.

But the situation is pretty bad when the price is leaving one level for another. If it's going down, then Bancor will bleed its reserves to keep the price close to the higher point that the price used to be at. And if it's going up, Bancor will sell coins at a price lower than the equilibrium point of the market, and therefore slow down the up movement.
  • The Bancor strategy will not do anything to find or maintain the true equilibrium value of an asset.
The preceding cases already illustrated the fundamental problem: Bancor is designed solely to maintain a reserve fraction. It has nothing to do with finding or maintaining the true value of an asset. It doesn't know, yet it'll blindly offer buy and sell bids. It'll use its reserves to discover what prices it ought to set.
  • Bancor thus acts like a dynamically adjusted currency peg.
Currency pegs have been tried again and again: ask any Argentinian for details. Any time you have a central bank trying to use its reserves to buoy up a peg, you have the opportunity for gaming. You'll recall that George Soros masterfully ran the reserves of the Bank of England down, simply by knowing their strategy. In this case, everything is happening on a public blockchain, using a fixed algorithm, with full visibility, while the true price is being set elsewhere through informed buy and sell orders.
  • Bancor presents an arbitrage opportunity. It does not lead the market towards equilibrium, it trails the market, always and by definition.
The mismatch between the Bancor price and the true market price is the cost that Bancor pays to have its smart contract be informed of the true value of the asset.

It is not the case that Bancor is helping the market perform price discovery. Quite the opposite: it's Bancor that is discovering the price, by virtue of offering buy and sell bids that are at odds with the value of the asset on the open market. It relies on arbitrageurs to bridge the gap and bring Bancor up to speed on what is happening. It pays a price out of its reserves for this function.

As such, Bancor will always trail the true value in the open market, and act as a buffer or a dampener. Bancor uses its reserve to be informed of the delta between the price it offers and the price out in the open.
  • Bancor does not "eliminate labor" in price discovery.
Despite Bancor's claims that they eliminate labor in price discovery, their current contract does nothing of the sort. It simply shifts the market maker labor onto arbitrageurs. It is now the arbitrageurs' job to notify the Bancor contract of the true price of an asset, and get paid a programmatic reward to do so.
  • There is no indication that the Bancor strategy is an optimal, or even good, use of reserves to discover the price.
The previous point was that Bancor uses its reserves to figure out where the market is, and sets a price accordingly. This isn't inherently bad, but it's neither what's in the advertised materials, nor is there any indication that the formula they used is the best use of reserves.

Why not, for instance, a market making strategy that approaches the target price using a different formula? Or uses AI techniques? Or uses past history of price action? The depth of the order book? The possibilities, for the strategy that a central bank would follow to manage its reserves, are endless. Bancor picked just the simplest possible option. The space of options remains unenunciated and uncharacterized, and there is no indication why this approach is superior to others in the Bancor materials.
  • Bancor is a net negative in markets with substantial liquidity.
Bancor-style automatic trading should be suspended when the external markets are already liquid. Throwing a dampener at a liquid market, one whose motions are preordained and predictable by all, is not the best use of those reserves.

The sensible way to design Bancor is to place some limits on how much of its reserves it will use in any time period, to avoid the problems we identified. There are currently no provisions for this. Doing this well requires importing some facts about liquidity from the external world into Bancor, perhaps with the aid of oracles such as virtual notary, town crier, oraclize and augur. But at a minimum, some limits on how much of its reserves the contract will spend in any given time period seem called for.
  • Bancor claims to provide liquidity, but does not.
Liquidity is the ability to buy or sell potentially large amounts without moving the price substantially. The Bancor contract does not guarantee this property, despite claiming that it does. Prices can move arbitrarily, and the price slippage is dependent on the amount bought or sold. This is a simple consequence of the fact that Bancor has no risk model and has no smarts. It's simply a market trailing dampener.
The preceding discussion examined the fundamental Bancor value proposition, in the abstract. Let's now examine its instantiation in Ethereum.

Front Running
  • Bancor is open to front-running.
Bancor's current implementation is open to a simple front-running attack. A miner, upon seeing that someone is submitting an order to buy from Bancor, would squeeze his own buy order ahead of the user's. He would thus always get a rate from the Bancor market maker that is better than what the user gets. Every time.

Bancor has a "minReturn" concept, akin to a limit order, that ensures that if the order goes below a certain level of profitability, the user can cancel it.

But the miners know exactly what limits the users set. Ethereum transactions aren't private. So a miner can squeeze in just the right order ahead of the user.

On the way down, front-running works the same way, with the miners squeezing sell orders ahead of the user, and thus pocketing the price difference.

And it's possible for miners to automate this process with a simple software kit. Further, even non-miners can take advantage of this behavior, by paying higher fees to appear before the Bancor transaction in the block.
  • Bancor's suggested fix to front-running is broken.
In a Twitter exchange, Bancor engineers mentioned that they are planning changes where they would charge the same fixed price to all transactions in the same block.

What they mentioned isn't currently implementable on Ethereum, at least not in a straight-forward fashion. Transactions within a block execute completely independently. If there are two transactions T1 and T2 in a single block, T1's execution occurs in isolation, without knowing about T2's presence in the same block. So it's not possible to charge T1 and T2 the same price, because T1 has no idea that T2 will execute in the future.

There are schemes we can imagine, where T1 and T2 are placed on the block first, and then a later "execute" transaction is placed on a subsequent block that looks backwards and gives the same price to T1 and T2. This gets around the limitation in the previous paragraph but it's really ugly and kludgy, not to mention more expensive to execute and open to new attacks of its own.

In general, any scheme that a) provides full information to miners b) doesn't include any nondeterminism and c) is vulnerable to ordering dependencies is gameable. Bancor and all their proposed modifications, including order floors and per-block prices, still satisfy all three.
Bad Math, Rounding and Lack of Testing
  • Bancor reimplemented math.
Bancor ended up reimplementing their own functions for arithmetic. That is, their own add, subtract, multiply, and exponentiation.

As an aside, this is sad to see for two reasons. First, finance applications should not have to worry about overflow errors. Ethereum should provide base types that make sure these kinds of reimplementations are never necessary in application code.

Second, no reimplementation of basic math routines should look the way Bancor's code looks. It's a mishmash of special numbers baked into the code. There is a certain style to writing code that is correct by construction. The code has to be crafted such that, not only is it correct, but it is easy to prove correct upon inspection. Bancor code is nothing like that, and baking magic numbers into the code is something for which we penalize first year undergraduates.
  • Bancor did not test their own math.
The sum total number of dedicated tests for these math functions is 6. Multiplication is tested solely by multiplying 2957 by 1740.

The coverage of the exponentiation function is abysmal. There are 0 directed tests that cover this critical function. There are other tests that take a quick path through exponentiation, but there are more than 30 different cases, and 30 different magic numbers embedded in the code. The existing, indirect, checks cover only a handful.
  • Arithmetic errors can be fatal.
Special magic constants litter Bancor code. So much so that we found it difficult to test this code for correctness ourselves. There is an art to writing correct, clean code, and Bancor exhibits none of it. An error in any one of the constants would be catastrophic.

And even simple rounding errors can be problematic in this game. A rounding error can enable an attacker to buy-then-sell a token to Bancor, and make a fraction of a cent in the process. If they can earn such a small quantity above transaction fees, then they'd do exactly that all day long to drain funds.

A final corner case to check for is what happens when the reserves are down to zero. The code needs to be able to recover from that scenario. The current code has special case handling for selling the entire supply. This seems strange for the continuous, path-independent Bancor formula.
Integration and Scale
  • Bancor does not support the notion of supply caps for Bancor-based tokens.
If the tokens that are based on Bancor are not actually securities, but serve as access tokens for a system, then they will typically correspond to some right to service. In many, though admittedly not all, scenarios, the system can only deliver a finite amount of service, so the designers will want to set a supply cap on their tokens. Yet Bancor's smart contract will create tokens out of the thin air in response to demand.
  • Bancor does not scale.
Bancor generates continuous on-chain tx volume for arbitrage on tokens that nobody cares about by definition. If they did care, those tokens would have liquidity and not need Bancor. It requires continuous on-chain activity for what is currently primarily off-chain economic action.
Users Overpay
  • Bancor shortchanges its users.
Since the Bancor contract cannot issue fractional tokens, it simply takes your money and gives you a number of tokens rounded (see rounding above) to an integer. Since you don't know when exactly your transaction will execute when you submit your bid, you have to pay both transaction fees to the miner to mine your transaction, and throw in an extra dollop of cash or coins to Bancor such that the contract can execute your trade without running under. If you guess wrong, you'll end up, say, getting 0.99998 coins, which conveniently rounds down to 0.

This will undoubtedly cause a lot of frustrated messages from users, who might feel that they submitted an honest bid, and got something short of their expectations.

Bancor whitepaper claims that you can predict what you will get back, but that's patently false: in the presence of concurent users submitting transactions, you cannot predict at all. Any extra amount you overpay is usurped by the Bancor contract.
Potential Reentrancy Issues
  • Bancor code is "difficult to prove correct."
That's code for "it's a mess."

Well-written code looks like a work of art. It doesn't matter if it's C or Go or Ruby or Prolog; in fact, it looks especially like a work of art if it's well-written C code. But it does matter if it's Javascript, because well-written Javascript code is like the mythical Yeti: often discussed, with snippets of evidence for its existence, but no one has seen it in its full, corporeal form.

The Bancor code has a distinct Javascript quality to it. This has been the hallmark of badly written smart contracts: they have messy code paths, don't follow best practices, and happen to work by the skin of their teeth. The code works on a good day with the wind on its back. But when it comes to corner cases, things get awfully complex. In the course I teach, when I point out such situations to students, they go into a diatribe that goes "well, you see, the problem can't arise because for it to happen, A has to happen first, but A is guarded by B, and C ensures that B cannot happen." This is a temporal logic proof, over a certain code path. It's complex, fragile in the face of code evolution, and totally unacceptable in professional code development. We want flat, simple invariants, maintained by following best practices. Without regard for the correctness of the student's code, we grade such cases a 2 out of 10. They ought to know better, and they're 20 year olds with two years of programming experience. Bancor definitely has to know better, given The DAO experience.

So, in what follows, we will point out violations of best practices as problems. We did not have time to look into whether they are exploitable, because it's tedious to do so and it's immaterial. There ought to be no violations of best practices in a good contract.
  • Bancor code has a reentrancy problem in the sell() function.
There is what appears to be a reentrancy problem (recall that an exploitable reentrancy bug affected The DAO) in BancorChanger. Now, not every reentrancy bug is exploitable, and not every reentrancy bug gives rise to a The DAO like disaster. But nevertheless, there ought to be no state changes after a funds transfer, and there it is, right there on line 389 of the current (undeployed) code.

We cannot tell yet if this is exploitable, but it is disconcerting. There is no reason to perform a state change on something critical, such as virtualBalance, after the funds have been transferred.
  • Bancor code has a different reentrancy problem in the change() function.
There is a similar reentrancy problem in change(). When going from one token to another (recall the "double coincidence of wants!", perhaps it is referring to the double concidence of two different h4x0rs over the funds in Bancor), it performs, first, a buy() followed by a sell(). But buy() and sell() are both functions that call out of the Bancor contract. So it's possible to get into a messy situation if the token transfers during the buy() or sell() operation call back into the Bancor contract.

Again, we cannot tell yet if it is exploitable, but it should be avoided. All transfers should happen after all the state changes.
  • Bancor code assumes that ERC20 tokens based on Bancor are cooperative.
The code assumes that the tokens layered on top of Bancor are cooperative. But ERC20 tokens can contain malicious code. It is difficult or impossible for Bancor engineers to vet the token code that is layered on top, and even if they do, it may be possible to change the ERC20 token contract after deployment.
Verdict
The Bancor code falls short of the narrative used to sell the code. Blindly making markets using a strategy that has no proof or reasoning for why it's good is a flawed idea. Additional problems, such as front-running, potential reentrancy issues, poor code quality, lack of testing and the general unnecessity of inventing a new currency, give us pause.

Keep in mind that there are lots of flawed ideas in the world. Not every flawed idea is catastrophic -- we've done many things that definitely were not proven good ideas, and survived to be writing these words. Perhaps miners will be altruistic and avoid front-running, perhaps all the magic numbers are correct even though they are untested, perhaps there are no rounding errors that matter.

But we know for sure that the Bancor approach is not the best use of one's currency. Someone armed with additional information not on the blockchain can certainly make markets in a better informed fashion. Since Bancor is possible to simulate off chain, committing to it on chain provides little to no additional value, except limit one's future moves.

Overall, it seems that the current Bancor approach is fundamentally inefficient and will bleed reserves. Assuming that there are no immediately exploitable issues in the code, and assuming that miners play nice and avoid front-running, we expect that we will see Bancor-based coins discover the limitations of the Bancor approach.

To end on a positive note, the optimistic way to look at the Bancor episode is that it's the first, flawed step in an interesting direction. It will surely be followed by more sophisticated approaches that have a better chance of living up to the hype. People are beginning to look for ways to codify Janet Yellen and place her on the blockchain. True, she need have no fear of losing her job right now. But sooner or later, we will have actualy smart contracts that provide strong guarantees as they manage a currency.
Footnotes
    [1]    This is impossible.
    [2]    This is also impossible.

Acknowledgments
We are grateful to Vitalik Buterin for his insightful feedback on earlier drafts of this document. Note that our technical analysis does not constitute investment advice. Crypto prices rarely follow rational rules, historically, some of the flawed systems that we have highlighted in this blog have done well, partly due to the increased attention they have received. Caveat emptor.

Recent Developments
  • Bancor delays token activation and their switch to trading BNT on their own platform.
  • The latest, hastily applied, patches to the Bancor code seem to revolve around rounding errors and precision loss.
  • This post discusses the rounding problem, mentioned above. It also mentions a social attack stemming from people not understanding how fractional reserves and the Bancor formula work.
Announcing The Town Crier Service

Hacking Distributed
 
Announcing The Town Crier Service

We are delighted to announce the (alpha) public launch of Town Crier (TC) on the Ethereum public blockchain. TC acts as a secure data pipeline between smart contracts and websites, or what’s commonly called an oracle.

Image/photo
The TC logo: A handbell + ‘T’ + ‘C’

TC isn’t a mere oracle, though. Thanks to its use of a powerful new form of trusted hardware (Intel SGX), it provides unprecedented data integrity. Equally importantly, TC enables general, flexible, and practical smart-contract execution with strong data privacy.

If you’d like to plunge into technical details and play with TC right off the bat, you’ll find all you need atwww.town-crier.org. You can use TC’s Ethereum smart contract front end. We’ve also partnered with SmartContract so you can experiment with coin-price queries through their easy-to- use interface.

You can also read our published technical paper here. For those wanting a gentler introduction, though, read on...

Why do we need oracles?
Smart contracts confined to on-chain data are like sportscars on local roads. They’re purring with latent power, but can’t do anything really interesting.

To unleash their potential, smart contracts need access to the wide open vistas of data available off-chain, i.e., in the real world. A financial smart contract needs access to equity, commodity, currency, or derivative prices. An insurance smart contact must be aware of triggering events such as bad weather, flight delays, etc. A smart contract allowing consumers to sell online games to one another must confirm that a seller successfully transferred game ownership to a buyer.

Image/photo
Latent power waiting to be unchained...

Today, though, smart contracts can’t obtain such data in ahighly trustworthy way. And they can’t achieve data privacy. These deficiencies are starving smart contract ecosystems of the data they need to achieve their full promise.

We’d even argue that this problem of data starvation was one cause of the DAO debacle. The DAO attracted $150+ million because lack of data meant a lack of good smart contracts for people to invest in.

What’s the problem?
Let’s take flight insurance as a running example. It’s been widely explored by the community and you can find an implementation on the TC website.

Suppose Alice buys a flight insurance policy from a smart contract MolassesFlights that pays $100 should her flight, WA123, be delayed or cancelled. Clearly, MolassesFlights needs to learn the status of Alice’s flight. How can it do this? Smart contracts (and blockchains) can’t query websites, as they don’t have internet connections. And even if they did, there’s a more basic problem. Suppose that the creators of MolassesFlights and its users all trust flightaware.com. In order to determine the status of a particular flight, someone (say, Carol, a MolassesFlight operator) must query flightaware.com with Alice’s flight information (Q = “WA123”) and obtain a response (e.g., R = “Flight WA123 delayed”). The problem is that there’s no way for Carol to pass along R such that someone else knows that R, as relayed by Carol, is correct and free from tampering.

This lack of transferability holds even if Carol obtained Rover HTTPS, the protocol used for secure (authenticated and encrypted) web connections. Carol learns that R is authentic because she logged into a website authenticated by a valid certificate. But HTTPS doesn’t enable her to convince another party that flightaware.com sent R. (HTTPS doesn’t support data signing.) As a result, there’s no trustworthy way to feed R to a smart contract.

There’s another problem as well. For Alice to buy flight insurance, she must specify her flight to MolassesFlight. If she sends it in the clear on the blockchain, she reveals her itinerary on the blockchain, and thus to the entire world -- an unacceptable breach of privacy.

Enter TC.

TC in a nutshell
Image/photo
Ah, the jet age…

TC’s core code runs in a secure enclave, an environment protected in hardware by a new Intel technology called SGX (Software Guard eXtensions). When TC queries a website over HTTPS and obtains a response R, other parties can confirm that R is authentic because the hardware (CPU) itself prevents any modification of TC or its state. SGX also enables TC to handle confidential data privatelywithin the enclave.

Specifically, SGX provides three key properties:
  • Integrity: An application running in an enclave is protected against tampering by any other process, including the operating system.
  • Confidentiality: The state of an application running in an enclave is opaque to any other process, including the operating system. (See our paper for some important caveats.)
  • Attestation: The platform can generate an attestation, a digitally signed proof that a given application (identified by a hash of its build) is running in an enclave.
Using Property 3 (Attestation), a user can verify that a valid TC application instance is running in an SGX enclave. SGX attestations can bind a public key PK to an application instance such that the corresponding private key SK is known only to the application.

Provided that a user trusts the TC implementation (whose source code we publish), therefore, she can trust that data TC has signed using SK are valid. The same goes for a smart contract, of course. Given PK, it can verify the correctness of data emitted by TC.

Once a user has established trust in a TC instance, Properties 1 and 2 come into play. Property 1 (Integrity) prevents anyone from tampering with the execution of TC and thus ensures that TC transmits only data validly obtained from target websites. In our flight insurance example, this property ensures that flight data will be exactly as reported by flightware.com. Property 2 (Confidentiality) enables TC to handle private data. In the same example, Alice can encrypt her flight information (Q = “WA123”) under TC’s public key. TC send query Q to flightaware.com over HTTPS. Consequently, Alice’s flight will not be disclosed on the blockchain or to TC’s operators.

In general, you can think of SGX as running an application in a black box or simulating its execution by a trusted third party. Even the owner of the machine on which the application is running can’t break its integrity or confidentiality.

The figure below shows the basic flow of data between a user smart contract (User Contract), the TC smart contact front end (TC Contract), and the TC Server. Here, prog denotes core TC code, params is the set of parameters in a query, and data is the website response (R in our above example). See our paper for details.

We provide more details on the under-the- hood workings of TC in our blog appendix.

From Alpha to Omega: TC today and tomorrow
TC today is an “alpha” system. It’s fully functional, and supports several different query types:
  • Flight data,
  • Stock tickers,
  • UPS tracking,
  • Coin market prices, and
  • Weather data.
Flight data queries are encrypted as described above. Other queries are in the clear.

Image/photo
Basic blockchain-to- server data flow in TC

As you can see, the current set of query types and functionality are fairly limited. Thus our current “alpha” label. We’ve got a lot more in the works, though, including:
  • Custom queries: We’re planning to allow users to define their own query types. In this way, users will be able in effect to create their own oracles. (This is possible today in SmartContract, with whom we’ve partnered in our alpha launch.)
  • Account-scraping: One of the most powerful opportunities enabled by TC stems from its ability to handle confidential data. Our Steam exchange query, which is under development, exemplifies this opportunity. This query will ingest a pair of user identities A and B, a user credential belonging to A (and 2FA passcode, if necessary), and a game identifier. TC will respond by indicating whether A transferred ownership of the game to B. To do this, TC logs into user A’s account. Thanks to the use of SGX, all of this can be done without exposing A’s credentials to anyone, including TC operators. This is just the tip of the iceberg. The ability to handle data confidentially is a stepping stone to full-blown versions of off-chain confidential smart-contract execution.
  • Data-source and TC-server redundancy: If a data source goes bad, e.g., a source of flight information is incorrect, TC will blindly and faithfully relay incorrect data. An extension of TC, however, can combine data from multiple sources to reduce the risk of error at the source. For example, TC can fetch stock ticker data from five different websites and take the majority value. Another problem is that if TC goes down, a relying user contact will fail to receive timely data. We plan to address this problem through deployment of redundant servers, an approach that can also minimize the (improbable but not inconceivable) risk of an enclave getting physically compromised.
We look forward to your comments and thoughts about how TC can evolve and best serve the Ethereum and broader smart contract communities.

The fine print
TC is patent-pending. We expect to commercialize versions of TC for other blockchains, particularly permissioned ones. It’s also possible that we will charge for special query types and/or bulk queries in Ethereum later down the road.

The current Ethereum public blockchain TC functionality, however, is free, and we plan to keep it that way. Users only need to pay the gas costs for a query. We intend to enlarge our free service substantially. As academics and smart contract enthusiasts, we’re interested above all in helping smart contracts achieve their full potential and seeing the grand experiment called Ethereum flourish and empower users in ways yet to be imagined.

More to Come
TC is just one of many other systems coming from IC3. Several near the end of the pipeline and worth looking out for are Teechain, a secure layer-2 payment system, HoneyBadger, a highly robust asynchronous BFT system, Snow White, a new, highly efficient consensus protocol, and Solidus, a confidentiality-preserving on-chain settlement system.

Thanks!
Town Crier was created by students and faculty in IC3 (meaning that the students did the real work, of course). Yan Ji, Oscar Zagarra, and Fan Zhang created our alpha service, with generous help from Lorenz Breidenbach and Phil Daian.

We want to thank Intel for their close collaboration, particularly Mic Bowman and Kelly Olsen for their support and advice, Sergey Nazarov at SmartContract for supporting our alpha launch, and the Ethereum Foundation, especially Vitalik Buterin, Alex Van de Sande, and Vlad Zamfir, for their input on TC during early development.

Appendix: A peek under the covers
While our general approach is conceptually simple, realizing TC using SGX requires some finesse.

To begin with, enclaves don’t have network stacks, so they must rely on the operating system (OS) for network functionality. Running outside the TC enclave is a Relay that handles TC’s network connections.

The whole point of running in an enclave, though, is to avoid trusting the operating system. How can we build a trustworthy application coiled in the embrace of a potentially hostile operating system?

As mentioned above, TC communicates with HTTPS-enabled websites, and thus uses TLS. To prevent OS tampering with TC connections to websites, we’ve partitioned a TLS implementation (mbedTLS) such that the handshake and record layer portions reside in the enclave, while the TCP layer resides outside the enclave. In this way, the code inside the enclave has a secure channel to the website. In effect, we treat the OS itself as a network adversary—exactly what TLS is meant to protect against by design.

As we’ve noted, TC has a smart contract front end, which we simply call the TC Contract. We therefore also have the problem of securing communication between this front end and TC code in the enclave. How do we prevent the OS from corrupting blockchain data?

The simplest solution would be to run a client (e.g., Geth) inside the enclave. But this would bloat what’s called the trusted computing base (TCB), the code that users need to trust in order to trust TC. The basic TC code, plus Geth, plus any wrapper around Geth would be a lot of lines of code.

We solve this problem in a counterintuitive way. TC doesn’t actually verify incoming data from the blockchain. It hopes that the Relay (and OS) are passing it valid queries from the TC Contract, but it accepts and processes bogus queries. The trick in our implementation is that TC signs queries along with responses. This way, the TC Contract, which records the queries it handles, can weed out invalid queries. And happily any corruption of queries is visible on the blockchain, providing incontrovertible evidence of corruption. The schematic below shows how these various pieces fit together for queries to a hypothetical service https://www.lots-o-data.com.

Elements in green are those trusted by a User Contract querying TC. Note that there’s no need to trust the Relay, i.e., it sits outside the trusted computing base.

Image/photo
Basic TC architecture

Other oracle designs
There are alternative ways to create oracles, and it’s beneficial for the community to be able to draw on multiple sources of data.

One approach to oracle design, exemplified by Gnosis and Augur, leverages prediction markets. These systems create a financial incentive for a community to express truthful evaluations of queries, and thus data that may be consumed by smart contracts. This approach has some nice features. For example, it permits queries to be expressed in the form of natural language, something that TC can’t easily support (at least, not without some pretty sophisticated NLP).

Prediction markets don’t scale to large numbers of queries, however, as the cost per query in human brainpower and capital commitments is high. Nonetheless, this approach does serve a particular niche very well.

Oraclize is another option. It uses a clever protocol that leverages TLSnotary to create attestations (and has some pending work on other options, e.g., Android-based software attestation). Oraclize has been an important catalyst within the Ethereum community, as it has helped address the data-starvation problem. Its assertions of authenticity, however, are ultimately weaker than those obtainable through use of a hardware root of trust. Most importantly, without trusted hardware, it’s not possible to offer true data confidentiality. Even encrypted queries must be decrypted by and are therefore exposed to the oracle and/or a supporting service. Thanks to its simple and elegant security model, SGX enables TC to skirt these problems.
Levels of Enlightenment for Researchers

Hacking Distributed
 
Levels of Enlightenment for Researchers

Having gone through graduate school, and having watched hundreds of others do the same, I have come to realize that there is a common progression. I have observed three distinct stages, or levels of enlightenment, that individuals proceed through when faced with an intellectual challenge.

I want to chronicle this seemingly universal process, partly to seek feedback from those of you with deeper insights than mine, partly to provide reassurance to young graduate students, partly to help people who are entering my field, but mostly to serve as a framework for how to evaluate communities and improve discourse. For any community will consist of various individuals, scattered throughout this continuum between the various stages of enlightenment. And it's useful to be able to categorize and guide appropriately.

One caveat: I am not claiming to speak from a position of authority on this topic. All of this is "meta" and outside my area of expertise. I can claim to have reached Level 3 only in a limited number of narrow fields, and I'm constantly trying to explore new fields myself. So for all I know, maybe there are 16 stages of enlightenment and I've only seen 3! But I do think it's useful to discuss how people respond to intellectual challenges, what this means for those around them, and perhaps how we can all engage in better discussions.

Level 0: The Newcomer
Image/photo

Almost all newcomers to an area are greeted by a barrage of ideas developed by people who came before them. Even if an area seems "brand new," say, computing in the 40s, it buds off of existing fields, like electrical engineering or math, and entails the use of techniques drawn from both. Mastering these techniques is often a difficult process, for the road ahead seems windy and the end is not clear.

For one, learning a new area requires adopting the terminology and frameworks used within that area, some of which might be confusing and even off-putting. For instance, what we call "slow start" in networking refers to exponential growth, one of the fastest possible ramp up functions possible. Every new system to master comes with idiosyncratic complexitiesthat reflect its history. The bigger the gap is between how a clever person would design something from scratch versus how it is right now due to its history, the more offputting and inaccessible it is.

And the ties between the disparate lines of work aren't crystal clear. There are few people, for instance, who can relate how the work on failure detectors, in distributed systems, is related to consensus protocols. The relationship between a new consensus protocol and others that came before it may not be clear, even to the authors of the work themselves.

And there is seemingly a ton of material to master. This is especially true when one is learning on their own and there isn't someone to guide them through the enormous data bank of published work. And it can be confusing, if not incredibly unproductive, because there is often a giant gap between what is said publicly and what is known among the experts. For instance, there are some well-publicized results that are known by experts to be misguided or misleading, such as the CAP Theorem. A simple reading path will often guide one into the underbush, where even the trees, let alone the forests, are not visible. Self-study in such areas will lead one into ratholes.

Level 0 Reaction: Overwhelmed
Image/photo

The standard reaction most people have at this stage is to feel overwhelmed. If you talk to graduate students in their first two years, they universally feel like they have far too much reading to do.

There are some common pitfalls at this stage.

Lack of integration is probably the biggest problem that people encounter as they try to make sense of the various papers they are reading. Instead of fitting the new material into a cohesive whole, they learn and memorize results. Instead of applying uniform standards and criteria to different ideas, they evaluate each idea separately, within its own framework. For instance, it is quite common for people who have done some but not enough reading in databases to use the acronyms ACID and CAP, without realizing that the C in these acronyms is completely different. Or, for another instance, for people who hold day jobs building distributed systems to claim that Paxos is a Byzantine Fault Tolerance algorithm (yes, there are Byzantine Paxos variants, but no, Paxos does not handle Byzantine failures).

Lack of time is an issue that plagues the part-timers. In most areas of study, it is impossible to perform the necessary synthesis in one's mind except by reading a large number of papers in a relatively short span of time (say, 4-8 papers per week for 10 weeks). The mental cache needs to contain the material to be cross-connected, and that can't happen at a rate of 1 paper per week.

Finally, lack of breadth is a common problem. You might say "hey, wait a minute, in this age of ADHD, you're telling me that it's lack of breadth, and not lack of focus, that is a problem?" Indeed, in my experience, focus isn't critical in the early stages. There is so much to learn that it doesn't matter if you attack left or right or center -- as long as you do the reading voraciously, you will master it (and if you're not doing the reading, we go into the "lack of time" category above). The problem cases I've seen are invariably people who are so focused on one topic that they try to go deep and skip the foundation-building that comes from reading a broad base of papers.

Most people never proceed past Level 0. It is possible to always remain behind the reading, just with a slightly expanding vocabulary and a constantly foggy understanding. Being in a structered degree program helps yank one out of this zone, but is not a guarantee.

Level 1: The Half-Expert
Image/photo

As people gain more expertise in an area, the Level 0 feeling of "inferiority in front of the collective works of mankind," gives way to its opposite. They have now mastered a sub-piece of human knowledge. They speak the lingo. And most importantly, they have acquired the ability to critique it. They now possesses destructive powers.

Specifically, people at this level can read a paper and either figure out its critical weaknesses, or they have built a catalog of quick critiques they have memorized. For instance, every time someone says proof of stake, a half expert will cite the "nothing at stake" problem, to knowing nods from other Level 1s and 0s. Or someone will introduce a new database and a Level 1 will ask if a database is "CP or AP." These cringeworthy discussions are signaling mechanisms that Level 1s have adopted to distinguish themselves from Level 0s.

Most Level 1s are incredibly good at identifying problems with past work. In fact, they can't help but do this; they've been trained to become weakness-finding-machines. This skill is a critical enabler for what they need to do at the next level up. But leveling up is hard.

So they see it as their hard-earned privilege and, now, birthright to attack every idea that came before them, as well as every new idea that they encounter. Snark and negativity flows with copious abandon from half-experts.

Level 1 Reaction: Dismissal and Destruction
Image/photo

And as we know from the Lord of the Rings and the entire "power-corrupts" canon, it's hard not to wield destructive powers. This is where we begin to see damaging behaviors. No work is good enough. Everything that has ever come before is crap. The greats on whose shoulders they rise clearly didn't know anything about the demands of today's systems.

There are three behavioral patterns that are common among half-experts.

First is sheer laziness. When asked to critique an idea, Level 1s will simply google related words, parse what they see (for they can now do this properly, as they are not Level 0s), and deliver a non-original critique that, in essence, was provided to them by someone else. Some might hang out on IRC channels to pick up others' ideas and regurgitate them. Many Level 1s have their pet issues that they feel defines them. For instance, some might harbor a special love or special hatred for certain techniques (e.g. certain algorithms, approaches and so forth), ready to go into a canned rant every time these are mentioned.

Second, they exhibit an obsession with their own ideas. At this stage, ideas are rare and hard to come by for the Level 1. Typically, their solutions are complex, under-thought and under-justified. It is quite common to see solutions that are essentially kitchen sinks that "solve" multiple problems at the same time. Achieving novelty with a simple and elegant solution is hard: you really have to invent something new. Creating something novel by gluing together disparate components is almost trivial. For instance, in a world where the only rain protection consists of hats, inventing an umbrella would be the next best invention, but requires intellectual prowess that a Level 1 simply lacks. It's much easier to invent a novel hat, incorporating a propeller, a wide brim, and a feather on top. Because no one has done that before, it's automatically novel. Crucially, its weaknesses cannot be readily discovered by other lazy Level 1s by simple googling. Too wet? It has a wide brim. Too hot? Propeller fixes that. What's the weird feather for and why didn't you design something simpler? Ah, but you see, the wide brimmed hats for sale never anticipated the needs of my particular hat usage, and you're a dummy if you don't see why the feather is absolutely essential.

Finally, in my experience, Level 1s have few ideas, but what few ideas they have, they repeat over and over again. People say that when you have a hammer, everything looks like a nail. I don't know if that's universally true, but what I have seen is that, to a blacksmith's apprentice who worked so hard to forge that first hammer, everyone else's hammers look totally inferior.

Level 1 half-experts often develop narratives to justify their destructive behavior. One narrative is that whatever they are working on is too important, too exceptional, too precious. This is wrong, of course, unless they are working on nuclear launch systems, but then again, Level 1's are never allowed to work on nuclear launch systems. I've met people who worked on (non-nuclear) launch systems, as well as many people who worked on systems that actually serve about a billion people. None of these experts had 1/100th the hubris of a half-expert. Another narrative, commonly used by Level 1s in industry, is to justify destructive behavior by citing their business concerns. Somehow, especially in the US, bad businesspeople firmly believe that "all is fair in business" or "it's just business," as if those words could ever provide an adequate basis for destructive behavior.

Of course, any given community will have some Level 1 members in transition. In unhealthy or immature communities, where there are large groups of people at Level 0, these people might even be revered. After all, they have a better understanding of issues than Level 0 muggles who haven't even done the required reading. And they might seem to have an insightful comment or two every now and then. And if they can't produce an insightful comment themselves, they can always acquire and resell someone else's ideas.

Quite a few people get stuck at Level 1 and never proceed beyond. Interestingly, such people are quite rare in PhD programs: the number of people who dropped out of our PhD program because they were stuck in Level 1 is incredibly small. What is much more common is the self-taught student who managed to reach Level 1 on his or her own, but is unable to make further progress. They often form or join a tribe of like-minded people, for much needed validation and for protection against criticism from people who know better. And they frequently make much of the noise. People at higher levels are actually busy with productive activities, while the Level 1 typically spends more time jockeying for social recognition instead of technical competence.

Level 2
There is no characterizable Level 2. Between Level 1 and the ultimate Level 3 lies some chaotic times, different for every individual, marked by much hard work.

Level 3: Nirvana
Image/photo

At some point in the process of trying to master, and then advance, a new area, something magical happens. The researcher realizes that, indeed, all past work has weaknesses, and that this is normal, for it is quite difficult to achieve perfection. Their destructiveness gives way to a positive attitude that can extract valuable contributions from other people's work. They realize that we are all in this together. They become able to function in a cohesive environment of like-minded peers. And their productivity skyrockets.

Those of you who are familiar with successful software houses (like Google on the large company end of the spectrum, and Chain on the startup side, and everything in between) will immediately recognize that these are the qualities that most happy science and tech communities encourage. Hacker News, for all its many faults, works very hard to avoid snark in an effort to keep out Level 1 discourse, and it succeeds somewhat. Academia, of course, is all about principled behavior, from design to critique.

I'm not going to say anything about the value of reaching Level 3, or whether it makes a community more healthy. The causality could run the other way -- instead of happy communities being a result of people who have reached Level 3, it could be that happy communities allow people reach the final stage of enlightenment.

And are there communities that are devoid of Level 3s, yet able to function? Undoubtedly so.

But in my experience, the most stable and productive environments tend to have a large number of people who have reached this final stage. Such people are able to provide and receive criticism without making it personal. They can see the value in half-baked ideas and foster them, instead of shooting them down on sight. New people fearlessly join such groups because they know that their ideas will get fair consideration.

I don't want to paint too rosy or idealistic a picture. We know that even academia, which tries very hard to foster a Level 3 environment, has personal rivalries and petty infighting. But the discourse, at least in the communities I have been a part of, is almost always civil, the problem cases are confined, and there exist common values to help steer the group out of ruts of negativity.

Overall, the bottom line is that this is the exact progression I have seen hundreds of times in graduate programs at several different schools. Those who reach Level 3 seem to be far more productive. Of course, it's certainly possible to be productive without fully going through the stages -- my own institution has awarded PhD degrees to people who never progressed beyond Level 1. But somehow, there seems to be a strong correlation between the Level 3 mindset and the ability to advance human knowledge.

Addendum
Perhaps it's worth talking about the nebulous Level 2, the all too critical transition between Level 1s and Level 3s. I'd like to hear from the readers on what they think enables people to cross over the chasm. Is it a hard challenge? Mentorship? Recognition? Something else? If so, how do we help more researchers achieve higher levels of enlightenment?
Hijacking Bitcoin: Routing Attacks on Cryptocurrencies

Hacking Distributed
 
Hijacking Bitcoin: Routing Attacks on Cryptocurrencies

At a high-level, Bitcoin is a randomly-established peer-to-peer network composed of thousands of nodes and tens of thousands of connections which rely on flooding to propagate transactions. As an attacker, being able to prevent the spread of information in such a network seems unrealistic, if not impossible.

Yet, this apparently sensible observation does not take into account that the Internet routing infrastructure (i.e., the set of protocols that govern how Internet traffic flows) is notoriously insecure and can easily be manipulated by attackers to intercept Bitcoin traffic. It also does not consider that large Internet Service Providers (ISPs), such as the ones sitting in the core of the Internet, might be naturally crossed by a large fraction of Bitcoin traffic already. Since Bitcoin messages are exchanged in clear text and without integrity checks, any (malicious) third-party on the forwarding path can eavesdrop, drop, modify, inject, or delay Bitcoin messages. The question is then: Is Bitcoin vulnerable to such routing attacks?

In our recent paper Hijacking Bitcoin: Routing Attacks on Cryptocurrencies to appear at the IEEE Symposium on Security and Privacy, we shed light on these aspects by studying the security of Bitcoin from an Internet routing perspective and quantify the potential disruptive effects of network attackers. Among others, we show that:
  • Bitcoin is surprisingly centralized from an Internet routing perspective: 20% of the Bitcoin nodes are hosted in less than 100 IP prefixes. To put this in perspective, there are close to 600,000 IP prefixes advertised in the Internet today. At the same time, few well-established ISPs (e.g. Hurricane Electric) naturally see a large fraction of the Bitcoin traffic. Together, these two characteristics make large-scale routing attacks surprisingly practical.
Image/photo
Only 13 ASes host 30% of the entire network, while 50 ASes host 50% of the Bitcoin network.
  • Because of its centralization, partitioning the Bitcoin network and isolate 50% of its mining power only requires a small routing attack, one which is orders of magnitude smaller than the attacks routinely seen in the Internet today. Any malicious ISP with access to the Internet routing infrastructure can perform this attack which starts to be effective after only few minutes (according to our own measurements on the live network).
  • Any ISP transiting Bitcoin traffic can delay the propagation of mined blocks (for up to 20 minutes), in a stealth way, even if she sees one direction of the traffic.
  • Bitcoin traffic is impacted by routing attacks today. We found many examples of actual routing attacks that ended up diverting Bitcoin traffic.
  • While multi-homing and end-to-end encryption (BIP 151) reduce the risks of network attacks, they do not prevent them. Our results show that even heavily multi-homed mining pools are vulnerable to routing attacks. Further, end-to-end encryption do not prevent an attacker from dropping Bitcoin connections.
In this post, we take a closer look at these issues. We start by describing the two possible network attacks which we consider, namely partitioning and delay attacks, along with their potential impact on Bitcoin. We then discuss some short and long-term countermeasures that would increase Bitcoin's robustness against network attackers. More details on our work can be found on our website.

Partitioning attacks
With partitioning attacks, an attacker aims at splitting the Bitcoin network into (at least) two disjoint components such that no information (e.g. transaction) can be exchanged between them. To partition the network into two components, a network attacker intercepts all the traffic destined to all the Bitcoin nodes contained within one of the component and drops any connection to the other component. To intercept traffic, a network attacker relies on vulnerabilities in the Border Gateway Protocol (BGP), the only Internet routing protocol used today, which does not validate the origin of routing announcements. These attacks, commonly referred to as BGP hijacks, involve getting a router to falsely announce that it has a better route to some IP prefix. By hijacking all the IP prefixes pertaining to the nodes in one component, the attacker can effectively intercept all the traffic exchanged between the two components. Once on path, the attacker can sever all these connections effectively disconnecting the two components. An animation of the attacks can be found on our website.

Image/photo
Illustration of how an AS-level adversary (AS8) can intercept Bitcoin traffic by hijacking prefixes to isolate the set of nodes P = (A, B, C, D, E).

The extreme centralization of Bitcoin from an Internet viewpoint makes partition attacks particularly effective as few IP prefixes need to be hijacked. Indeed, our measurements show that 50% of Bitcoin mining power is hosted in only 39 prefixes (i.e., in 0.007% of all Internet prefixes). This allows an attacker to isolate ~50% of the mining power by hijacking only these 39 prefixes. Much larger BGP hijacks (involving orders of magnitude more IP prefixes) are routinely seen in the Internet today.

While intercepting Bitcoin traffic using BGP hijacking is effective, any un-intercepted Bitcoin connection bridging the two components would quickly render the partition ineffective. Due to factors such as multi-homing, some nodes cannot be prevented from exchanging information, forming some kind of persistent connections. The presence of such connections makes partitioning attacks more challenging for the attacker, but not impossible. In our paper, we elaborate on how an attacker can provably identify and mitigate these persistent rogue connections by reducing the size of the partition she is trying to achieve.

By partitioning the network, the attacker forces the creation of two parallel blockchains. After the attack, all the blocks mined by the side with the shorter chain will be discarded together with all included transactions and the corresponding miners’ revenues. Moreover, discarded transactions will be irrecoverably canceled if there exist other transactions in the prevailing branch of the chain which spent the exact same Bitcoins (conflicting transactions).

Delay attacks
Bitcoin nodes are designed to request blocks from only a single peer to avoid overtaxing the network with excessive block transmissions. The block is requested again (from another peer) only if the request is not answered after 20 minutes. This design decision, coupled with the fact that Bitcoin traffic is unencrypted, allows for a powerful attack in which anyone intercepting Bitcoin traffic can delay block propagation on the corresponding connections. To do so, the attacker performs simple modification to the content of the Bitcoin messages she intercepts. As Bitcoin messages are not protected against tampering, neither the receiver nor the sender have any indication that the message has been modified, allowing the attacker to stay under the radar. The actual impact of such an attack depends on the victim and ranges from double spending (for merchant nodes) to wasted computation power (for miners). An animation of the attack can be found here.

Image/photo
Illustration of how an AS-level adversary (AS8) which naturally intercepts a part of the victim's traffic (node C) can delay the delivery of a block to it for 20 minutes.

Like for partition attacks, the centralization of Bitcoin nodes in few networks and prefixes, combined with the centralization of mining power in few pools, make delay attacks practical. We found that three ISPs together see 60% of all Bitcoin traffic. If malicious, these ISPs could therefore effectively and invisibly keep many bitcoin nodes uninformed. Unlike partitioning attacks though, we also found that even these powerful attackers could not disrupt the entire cryptocurrency. So, even though many nodes would be slowed down, Bitcoin, as a whole, would still function.

We verified the practicality of a delay attack by performing one against our own nodes. We found that a network attacker that intercepts only half of a victim’s connections can keep it uninformed for 64% of its uptime. We also found that the vast majority of the Bitcoin nodes (70%) are vulnerable to such an attack today.

How can we prevent network attacks?
Fortunately, there are both short- and long-term countermeasures against network attacks. First, peer selections could be made routing-aware. Bitcoin nodes could, for example, aim at maximizing the diversity of the Internet paths seen by their connections to minimize the risk that an attacker can intercept all of them. Moreover, nodes could monitor the behavior of their connections to detect events like abrupt disconnections from multiple peers or unusual delays in block delivery. These events could serve as an early indicator of a routing attack and could, for instance, trigger the establishment of extra randomly-selected connections. Finally, solutions like end-to-end encryption would also help (especially against delay attacks). Yet, encryption alone would not be sufficient to protect against partitioning attacks as an attacker can still drop encrypted Bitcoin connections.

Summary
The purpose of our research is to raise the awareness of the Bitcoin community on the need to prevent routing attacks from disrupting the cryptocurrency. While we have no evidence that large-scale routing attacks against Bitcoin have already been performed in the wild, we believe few key characteristics make these attacks practical and potentially highly disruptive. These characteristics include: the high centralization of Bitcoin (from a mining and routing perspective), the lack of authentication and integrity checks, and some design choices pertaining, for instance, to how a node requests a block. We are currently in the process of implementing some of the countermeasures highlighted above. Clearly, we wouldn’t mind some help in doing so!
Revealing the hidden links in the Monero blockchain

Hacking Distributed
 
Revealing the hidden links in the Monero blockchain

If you follow the world of cryptocurrencies, you probably know that Monero is a privacy-centric cryptocurrency that has surged in the market since late 2016. My coauthors and I, from Princeton and UIUC, have just released some research showing that its privacy claims, particularly for transactions made prior to February 2017, are significantly overstated. Based on the invective response our research has generated, the Monero community would much prefer you focus only on their newest offering, while ignoring the unfulfilled promises from their recent past.

For a bit of background: Just like in Bitcoin, each Monero transaction has some inputs and some outputs. Each input is a link to the output of a previous transaction, forming a graph.

In Bitcoin, these linkages are transparent and explicit. Every block explorer website (like blockchain.info) lets you follow the graph, clicking the links to move from one transaction to the next. These linkages have also been the basis for graph analysis, clustering, and deanonymization analysis.

Image/photo
A typical users' mental model of Monero transactions is informed by this illustration.

In Monero, however, the links between transactions are obscured. Each transaction input can contain decoy links called “mixins.” Every transaction input has multiple incoming links, and every output has multiple outgoing links; in principle, no one can tell which is the real one among the mixins. You may have formed a mental model based on the popular illustration shown to the right.

Furthermore, if you visit any Monero block explorer website, you'll see the transaction graph is presented as a dead end. You can't tell where each input comes from, and you can't tell where each output goes. Just as an example, have a look at how typical block explorers render this transaction from May 2016, ChainRadarand MoneroBlocks

This transaction has 5 inputs and 5 outputs. Each input has 6 mixins (7 links in total, including the real one), indicating a high level of privacy is desired. The outputs are dead ends, and you can't tell which of the 7 links is the real one. After all, Monero is the "opaque blockchain".

In our research paper, "An Empirical Analysis of Linkability in the Monero Blockchain," we show that in fact for most of Monero's blockchain history, the mixins haven't done much good. Most transactions made prior to February 2017 actually are linkable. Here's the problem. In the past, most coins were spent by 0-mixin transactions (those that opt-out of privacy altogether) were commonplace. Including these coins as decoys doesn't do any good, because it's already obvious where they've actually been spent. However, the Monero wallet does not take this into account. The result is that we are able to identify the correct links for the majority (62%) of 1+ mixin Monero transactions made from 2014 through 2016. The Monero blockchain has provided little more privacy than Bitcoin.

To illustrate the problem and make its impact crystal clear, alongside our paper we've launched a block explorer, called MoneroLink, that reveals the hidden linkages in Monero transactions. If you visit the MoneroLink page for the transaction mentioned above, you'll see we are able to identify the correct incoming link for 3 of the 5 inputs, and we're able to identify the correct outgoing link for 2 of the 5 outputs, despite the large number of mixins.

Image/photo
The MoneroLink block explorer reveals the hidden linkages among Monero transactions (from 2014 through 2016).

We readily note that for transaction made since March 2016, the rate at which we can link transactions has steadily decreased, although the correct link can still be guessed with higher probability than you would hope. In this post I'm eliding almost all the technical details, but a more detailed analysis can be found in our technical paper.

Is this a surprise?
Image/photo

If the existence of a link-revealing Monero block explorer comes as a surprise to you, then you're not alone. This is the first block explorer of its kind. To date, there has been no indication that the Monero blockchain is vulnerable to such wide analysis. And it clearly contradicts the privacy claims in Monero's marketing and popular media.

However, the reaction to our work from Monero developers and discussion community on /r/monero has been to say we have known this all along.
“This is not news. Anyone who has done any basic reading on Monero has known this for a long time”(tweet)

What “basic reading” refers to here is a pair of reports, MRL-0001 and MRL-0004, from 2014 and 2015 respectively, which introduce the main vulnerability that our explorer relies on (as well as even more sophisticated concerns outside our scope), explaining that they could plausibly lead to “a critical loss in untraceability across the whole network if parameters are poorly chosen and if an attacker owns a sufficient percentage of the network.” [Emphasis mine.]

Neither of the MRL reports conveys that this is an actual problem affecting actual transactions. Instead, the papers are abstract, describing mathematical models of marbles in urns and hypothetical attack scenarios involving Simpsons characters. Most importantly, no prior report has made any empirical analysis based on actual blockchain data.

The contribution of our work is to show that 1) the parameters have been poorly chosen, 2) there doesn't need to be any attacker, the problem manifests all on its own, and 3) we confirm that indeed the result has been a critical loss in untraceability.

On the soothing quality of the MRL reports
Image/photo

I'd like to call attention to a particular pattern of discussion, in which MRL reports have been used (unintentionally) to quell further investigation. At various points in Monero's history, several forum posters have stepped right up to the threshold of this revelation, but have been gently steered away from proceeding further, using the MRL reports to end the discussion.

Case 1: In December 2015. A redditor asks “Educate me: Zero mixins forgo all the privacy advantages of Monero, right? But do they damage or interfere significantly with other transactions?”

Redditor VedadoAnonimato responds:
“I'm not even sure whether the mixin selection algorithm rejects outputs that have previously been spent in no mixin transactions. If the selection algorithm can't reject these, then the situation is dire, since currently the majority of Monero transactions have no mixin." (permalink)

Monero developer smooth_xmr confirms VedadoAnonimato's concerns, but then refers to the MRL report to convince readers that the problem is already dealt with.
"The math in MRL-0001 shows that those outputs will eventually become irrelevant though... we plan to blacklist those from any future mixins which will immediately solve the problem” (permalink)

The authoritative “math in MRL-0001” is the final word, effectively ending the discussion. Incidentally, the proposed change to “immediately solve the problem” was never implemented (the measures actually implemented have had a gradual effect instead). Regardless, even if it were implemented, “solve the problem” here means that future transactions will enjoy better privacy. This doesn't do a bit of good for anyone who relied on the privacy of prior transactions!

Case 2: In the following thread, a user asks, “Is Monero Really Anonymous?” and posts a link to an essay speculating on a form of linkability.
“This has been discussed at length. … [MRL-0001] explains the known issues related to tracing transactions, how well monero already does at them, and where it needs to do better.” (permalink)

Further down thread, “There's nothing to discuss that hasn't already been extensively documented in those linked whitepapers.”

Case 3: Here's another example showing how the MRL reports have been interpreted:
“Peters comment is MRL-0001 which got fixed with MRL-0004 - a totally theoretic attack anyway :-) (bitcointalk)

Our research clearly shows that this attack is not theoretical, but absolutely affects actual transactions. It has taken empirical blockchain analysis to show this.

In fact, VedadoAnonimato (again in late 2015) even highlighted the need for this missing empirical approach:
"It would be interesting to know if somebody has actually gone through the data and checked how many transactions can be partially or totally traced through the problems pointed out there." (permalink)

The thread, of course, ends immediately on that cliff hanger. The blockchain data has always been there for anyone to take a look at, but it's only now that we've done the work.

The truth hurts, but time heals
Image/photo

The Monero cryptocurrency and community will undoubtedly survive this revelation. The best response now would be to acknowledge that this result comes as a surprise and no one knew just how many prior transactions were vulnerable to linkability analysis. Even if some folks have had a suspicion deep down that this might be the case, no one has particularly wanted to look into the data and see the unpleasant truth.

If the Monero developer community instead rallies around the “This research is not new!” narrative, then that bodes poorly for them. It means that the community's leadership has knowingly allowed users to be misled about the privacy of prior transactions. The right thing to do would have been to issue an advisory that communicates the problem very clearly:
WARNING: Monero users who made transactions in 2014-2016 expecting unlinkability should be warned that their transactions are most likely linkable after all.

This is exactly the message that the MoneroLink block explorer conveys. It's better late than never!

The MRL reports have served as a form of dog-whistle communication. The reports are written (unintentionally, but perhaps subconsciously) in densely coded language that avoids alarming users. Developers have been working in earnest to improve future versions of the software, but have not sought to empirically quantify the existing problem or to clearly warn users about the privacy implications. Real users today can easily be impacted by a loss in privacy of yesterday's transactions.

I'll wrap up with a final quote from smooth_xmr:
"Most transactions in 2014 and 2015 (and even most of 2016) were mining and trading. There were precious few ways to use it for anything else. There was a crypto kingdom game at some point, and a dice site, that's about it." (permalink)

This is plausible, and hopefully it's true, since it would mean the potential harm caused by this vulnerability is limited. However, even if only a small number of users relied on Monero for privacy in 2016 and earlier, then their privacy matters, and this warning is intended for them.

Addendum 1. More responses from the Monero community
As anticipated, this release stirred up a flurry of shitposting and character attacks, on reddit and on twitter, from a loud minority of grumpy folks. I'm resisting the urge to curate the worst of these for a cheap vindictive pleasure. Most of the rest are editorial quibbles about how we present our results.

Instead I'd like to thank Monero core dev smooth_xmr for an excellent discussion thread with technical feedback. We take your criticism seriously and will incorporate it in updates to our paper. I also want to thank SamsungGalaxyPlayer and KaroshiNakamoto for insightful (but still very critical) posts, including a great thread calling for a more rational and level-headed public response to a research release like this.

Addendum 2. Isn't this a paid hit piece for Zcash?
Disclaimer, disclaimer. I've been involved with Zcash for years (as well as for several other cryptocurrency projects, like Tezos, Ethereum), as a consultant and recently as a founder of its community-supporting Foundation. This is transparently and appropriately disclosed on the front page of our technical report. It's also clear to see from my website, twitter profile @socrates1024, and is duly reported to my employer, the University of Illinois. My research is not funded by Zcash, and the other coauthors have nothing to do with Zcash at all.

Many of the initial reactions to our research predictably focused on questioning our motives as a way of drawing attention away from the substance of our report. By all means, be skeptical of our findings, and ideally reproduce them independently.

Addendum 3. On the timing of our release coinciding with the Monero hard fork upgrade
Whoops. We dropped our paper within a few hours of a planned hard fork flag day. Maybe no one will believe me, but this timing was entirely coincidental, and I was not aware that Monero was going to upgrade then. This is totally my fault, because in hindsight there were plenty of places I could have read about this. (I've been reading lots of monero reddit threads recently while preparing our article, but only by keyword search, not by reading the front page.)

In particular, Monero has established the admirable policy of scheduling hard fork upgrades regularly, on April 15 or on three other predictable days of the year, and has committed to this policy for over a year.

I can see how this timing looks like hostility. If I were paying more attention and noticed, I absolutely would have waited until after the hard fork to release news that that would likely distract the developers and broader community. Originally we hoped to release this work two weeks ago, but I got distracted by the Financial Cryptography conference and didn't finish the website until now. I'm relieved this hard fork upgrade went fine, as have all of Monero's hard fork upgrades to date.
A Thinking Person's Guide to the Latest Bitcoin Drama

Hacking Distributed
 
A Thinking Person's Guide to the Latest Bitcoin Drama

The war for control over Bitcoin's future took a bizarre turn yesterday when Greg Maxwell, a developer with Bitcoin Core project and CTO of Blockstream, announced that a certain chip contained the ASICBOOST optimization, and suggested an immediate activation of Segwit in response.

Here's my quick response to this turn of events:
  • So far, there's absolutely no independently confirmed evidence of ASICBOOST actually being used on any chip.
  • If ASICBOOST was actually used, we'd see ample evidence on the blockchain. This evidence would be in the form of transactions that are picked according to an algorithm that shuffles the transactions to create a sought collision, instead of sorting them by fee-per-byte.
  • I do not have the time to perform a thorough study, but I manually examined a randomly picked block mined by Antfarm a few days ago. As you can also examine for yourself, the transactions are ordered essentially by fee-per-byte, which is not what we would see if they were shuffled to create collisions.
You can stop reading here. If #1, #2 and #3 are false, then there's absolutely nothing but baseless accusations flying around. Someone needs to do a thorough study to instantiate the claims.

On the offchance that Antpool is actively utilizing ASICBOOST, there's still quite a lot to be said about the claims:
  • Building more efficient mining chips is what miners are supposed to do, as it secures the blockchain. Framing an optimization as an attack is disingenuous. Going from 28nm to 16nm was not an attack on the network. Better mining algorithms have never been considered an attack.
  • There are countless patents involved in the manufacture of ASICS, spanning layout, doping, lithography, all the way to packaging. Layout alone can confer advantages that far exceed the paltry 30% possible with ASICBOOST. The Bitcoin community believes it understands hashing algorithms, but that's no reason to ignore patents related ASIC manufacture in general. If a case is to be made against patents, then it needs to be made properly, across all patents related to ASIC manufacture.
  • Taking action to block this is similar to the government taking measures to block Elon Musk's more efficient electric cars. Specifically prosecuting a chosen miner, in the current political climate, would send a terrible message of absolute centralization in the hands of one particular developer group, and it would severely damage Bitcoin mining and the coin's security.
  • Segwit is being offered as a solution to ASICBOOST. Yet Segwit has at best a tenuous connection as a response to ASICBOOST mining. There are countless other, non-controversial solutions that can disable ASICBOOST, should one choose (wrongly) to do so.
  • The fact that Segwit is being offered as an inevitable and only solution to ASICBOOST suggests something about the true motivations behind this reputational attack.
  • There is a history of reputational attacks against people who have spoken up against Segwit. This is toxic and not healthy for the space.
  • Some people have asserted that ASICBOOST forms a conflict of interest (CoI) that explains why Jihan opposes Segwit. This is based on the false premise that everyone would adopt Segwit if it weren't for a CoI. There are many other publicly discussed reasons to oppose Segwit, based on technical and philosophical grounds.
  • If commercial "conflicts of interest" are a showstopper that should cause a company to abdicate its voice in the ecosystem, then practically every significant company would have to have no say in Bitcoin's evolution. Every other company is trying to influence the coin to evolve according to their own vision, while taking steps to maximize its role within that vision. We call this "capitalism." If we suddenly instituted draconian measures to cut companies out due to CoIs, one of the first companies with CoIs would be Blockstream.
  • Overall, the community seems to be at a point of rapture. As we all move forward, let's make sure that we take every step for good, substantiated reasons backed by science. Reality is too important to let it be swayed by arguments to emotion and by the noise generated by troll armies, on either side.
Let's do our due diligence first, and dispassionately find a coherent strategy that represents the best path forward for all.
BitFury's Smallest-First Mining Is Bad For Bitcoin

Hacking Distributed
 
BitFury's Smallest-First Mining Is Bad For Bitcoin

Image/photo
He shot a lot of cucumbers when most normal people shoot one deer.

Bitcoin's mempool has reached unprecedented levels recently. We had about $1B stuck in transactions waiting to be confirmed, and the number of waiting transactions broke an all time record at 70,000. Amidst all this, we had BitFury come in and mine a number of blocks using a non-standard "smallest transactions first" strategy. I want to quickly explain why this is actually bad for Bitcoin.

If all the miners did this, it would lead to lower throughput overall, a less predictable network and a net initial increase in fees followed by everyone paying only the lowest possible fee, destroying the fee market and the ability to tell apart useful transactions from spam.

Quixotically, BitFury got praise for what they did, which either shows that most people are innumerate or that they can only look ahead 0-ply where actions have no consequences -- they live in the here and now, like goldfish, with nary a care, and follow the good book when it comes to making decisions, as opposed to thinking through what actions lead to what outcomes. That's why they get excited when they hear "it's time for game theory." Well, it's pretty much never time for game theory. But it is time to think critically about the effect of a miner picking transactions in a different order.

This kind of deviation creates terrible incentives, the chief among which is (1) to break large transactions up into small pieces, and (2) to attach the most minimal fee or no fee at all. In turn, this makes the inputs into the system, the transactions, take up precious additional space and actually increases the overall demand for blockspace.

And breaking up the correspondance between fees/byte versus confirmation time wreaks havoc on wallets' ability to predict wait times, and thus their ability to attach meaningful fees. It completely kills the "fee market" that we all heard so much about.

There have been only two arguments in favor of mining smallest transactions first:
  • "We have a transaction backlog. There are lots of transactions. Let's clear out as many of the transactions as possible."
  • "The same strategy is proven and working even in the Apple Store in queue. They ask you and if you have a simple question, they will give you priority, decreasing the queue length." This quote was provided to me by Alex Petrov of BitFury over Twitter DM.
Let's see why these two arguments fall apart under scrutiny. I didn't have much time to write this blog post, so its coverage will jump between these two arguments chaotically, which is quite fitting given the topic.

Smallest First vs. Most Needy First
The shift in BitFury's behavior comes down to a switch from "largest fees per byte first" strategy to "smallest first".

This switch makes sense only if what you care about are superficial metrics, and then, only if you have a tiny time horizon and are not concerned with the big picture.

Scheduling Theory and Bitcoin
The core of the second argument is based on a simple result from scheduling theory, which says that shortest-job-first is the optimal strategy if what you care about is to minimize completion time, that is, time from submission of a transaction to its appearance in a block.

The reasoning for this is simple: assume there are transactions A, B and C. Suppose A is 1MB large while B and C are 500KB each. Mining A first, then B and C together yields a collective wait time of 1 (for A) + 2 (for B) + 2 (for C) = 5 block-times for 3 users, or 5/3 blocks per transaction submitter. Mining B and C first, followed by A, yields a collective wait time of 1 (for B) + 1 (for C) + 2 (for A) = 4 block-times for 3 users, or 4/3. The latter is clearly shorter than the former. If we apply this logic iteratively, we'll find that it makes the most sense for the miners to prioritize small transactions first, and mine transactions in sorted order, from smallest to largest.

So Alex's logic seems, superficially, to make sense: if we are given an inflexible collection of transactions in a batch at the beginning of time, if the users submitting them are honest and not trying to game the system, and our goal is solely to minimize user wait time in a world where every transaction has a user waiting for it to clear and all users are equally important, then picking the small transactions first is a good strategy. That's why you see people at well-run airports, banks, and customs lines pulling people who need little time to service out of the line to expedite their case. Anyone with a valid passport and simple itinerary knows the pain of getting stuck behind that guy who is missing paperwork, was born on the Marshall Islands just as it was changing hands -- he is going to take a while, and more people would feel better if he stood aside and let the line clear up. This is also why, at the Apple Store, they ask you if your transaction is short and easy, and pull you out: they don't want you to get stuck behind the problem person who has a complicated transaction involving 2 returns, 3 gift cards under slightly different names, and the involvement of an Apple Genius. Shortest-Job-First is a provably optimal strategy, for serving a static batch of inflexible, unchanging requests.

But the logic fails because the premise is not correct. Smallest-first is a terrible, short-sighted strategy when applied to Bitcoin.

Bitcoin transactions are flexible. A large transaction can easily be turned into multiple small transactions, that, together, take up more space than the original transaction. Mining small transactions first provides an incentive to wallets to break up their transactions into such smaller pieces. But many small transactions that accomplish the same task as a single big transaction actually consume more space than the single big transaction. So, in aggregate, they reduce the system's economic throughput. They are a wasteful way to use our precious block space.

Bitcoin transactions are also not equally important. The main metric we have for telling apart the important transactions from worthless spam is the fee they carry: important transactions carry more in fees. Processing the transactions that are unimportant first will reduce the wait time for transactions whose users do not mind waiting, while making the people with time-limited transactions suffer longer. It's a strategy purely for optics, aiming to lower numbers of waiting transactions, not maximize the actual good that the system is doing or serve the people who have signaled their need for service.

Finally, Bitcoin users want predictability. Those people in favor of a fee market especially require predictability: if the market is being cleared in a haphazard, random order, then the wallets will have no feedback on whether their fees are high, low, or just right. Chaos isn't a good strategy when you want to develop a feedback loop.

Fundamental Problem
Overall, smallest first is a fundamentally bad idea because it breaks the connection with the fee paid and the resources consumed. Recall that the block space is the limited resource here, and the fees paid are our way of gating that access, of measuring who needs it most. Hence, the default metric to sort transactions by is satoshis per byte -- this ensures that the transactions that do the most economic good get prioritized first.

Switching to small-transactions-first enables BitFury to post this tweet and collect kudos from the community for entirely the wrong reasons.

First, the system should not be processing low importance transactions over more important ones. Maximizing economic good requires going after the most economically useful transactions first, and our only proxy for "economically most useful" is to sort by largest-fees-per-byte-first.

Second, one miner sweeping up the smallest, lower-fee transactions doesn't really do any good for the system. Someone still has to mine the larger transactions. Those outstanding large transactions still need to be cleared. A temporary, short term increase in the transaction rate for one miner doesn't achieve anything in the longer term. It's like a teenager cleaning up her desk and sorting her socks, really quickly -- it's a nice but ultimately pointless gesture, her tasks aren't done until the entire room is cleaned up, and the sum total of tasks still takes the same amount of time. She left the hard work to others.

Third, this policy provides an incentive to wallets to break up their transactions, to issue many smaller transactions in lieu of a single large one. That would lead to more wasted space overall, and a net decrease in throughput. A miner that did this in a predictable fashion would be damaging to the network.

Fourth, prioritizing small transactions can mislead or confuse the fee estimators built into wallets. I don't have the time to examine the various fee estimators today, but I believe the default fee estimator has built into it the assumption that miners will maximize their profits and perform largest-fees-per-byte-first, and uses the fee distribution in the mempool to pick its own fees. In this case, seeing high fee transactions sit around and not get mined will cause the users to actually bid even higher fees, actually leading to an added expense for users until the wallets adapt. Now, this is not the only way to estimate the fees (in fact, it is notoriously difficult to estimate the fees) . There may be fee estimators out there that instead base their decisions on the fees found in mined blocks. In that case, they will issue transactions with low fees, which will lead to stuck transactions and a bad user experience.

Finally, once the wallets adapt to smallest-first mining, their best strategy will be to attach the lowest possible fee to every transaction. The mempool then becomes a Hail Mary zone, where people toss their transactions cut up into small little chunks, and hope that the miners will sweep through their precious transfers just by sheer happenstance. The fee market will collapse, and we can no longer have a rational market, because the miners will not be behaving rationally, putting up the space in the blocks up for auction. Imagine a web search service, where you pay solely the fees to place your ads, and the ads are included based on chance. This is not a winning strategy for anyone. Just ask Yahoo.

I'm Doing Work In An Irrational Order to Reduce My Workload
Alex Petrov of BitFury has also expressed concern that, when transactions sit around in the mempool and expire, they get resubmitted, causing the miners to have to re-validate them. This is tantamount to saying that, because you are overloaded by your boss asking you to do the same N things over and over again, you'll do them in an irrational order. Once again, Alex may be pointing to something that might need fixing, but the fix is almost certainly not smallest-first. Adding more resources, parallelizing validation, maintaining a 1 bit validation cache even when transactions are evicted, etc are all effective techniques for avoiding repeated work.

Are There Better Ways To Reduce The Mempool?
One simple way to reduce the mempool backlog is to make the blocks larger, either through a blocksize increase or through the more complex Segwit patch. That will reduce fees, to boot, in return for increasing the space, bandwidth and CPU consumption of Bitcoin. Given how cheap and plentiful storage and CPU are, and how much bandwidth increased just last year alone, adopting some kind of a blocksize increase is the thing to do.

Thanks, but no thanks
Overall, smallest-first is, at best, a strange strategy. It most certainly does not accomplish what we all need: more useful economic activity recorded quickly on the blockchain.

Luckily, it's also a losing strategy: at the moment, a miner mining smallest-first will earn around 5% lower in BTC terms than what it would have been had they gone for mining largest-fees-per-byte-first. Let's hope that this dampens their behavior and counteracts the damage they inflict on Bitcoin through increased delays on important transactions, perverse incentives, worse utilization of the blockchain space and potentially increased fees.

Aviv Zohar said it best when he quipped "[smallest-first] will raise the revenue of other miners and eventually push irrational ones out of the market."
BitFury's Smallest-First Mining Is Bad For Bitcoin

Hacking Distributed
 
BitFury's Smallest-First Mining Is Bad For Bitcoin

Image/photo
He shot a lot of cucumbers when most normal people shoot one deer.

Bitcoin's mempool has reached unprecedented levels recently. We had about $1B stuck in transactions waiting to be confirmed, and the number of waiting transactions broke an all time record at 70,000. Amidst all this, we had BitFury come in and mine a number of blocks using a non-standard "smallest transactions first" strategy. I want to quickly explain why this is actually bad for Bitcoin.

If all the miners did this, it would lead to lower throughput overall, a less predictable network and a net initial increase in fees followed by everyone paying only the lowest possible fee, destroying the fee market and the ability to tell apart useful transactions from spam.

Quixotically, BitFury got praise for what they did, which either shows that most people are innumerate or that they can't look ahead -- actions have no consequences, they live in the here and now, like goldfish, with nary a care. That's why they get excited when they hear "it's time for game theory." Well, it's pretty much never time for game theory. But it is time to think critically about the effect of a miner picking transactions in a different order.

This kind of deviation creates terrible incentives, the chief among which is (1) to break large transactions up into small pieces, and (2) to attach the most minimal fee or no fee at all. In turn, this makes the inputs into the system, the transactions, take up precious additional space and actually increases the overall demand for blockspace.

And breaking up the correspondance between fees/byte versus confirmation time wreaks havoc on wallets' ability to predict wait times, and thus their ability to attach meaningful fees. It completely kills the "fee market" that we all heard so much about.

There have been only two arguments in favor of mining smallest transactions first:
  • "We have a transaction backlog. There are lots of transactions. Let's clear out as many of the transactions as possible."
  • "The same strategy is proven and working even in the queue at the Apple Store. They ask you and if you have a simple question, they will give you priority, decreasing the queue length." This quote was provided to me by Alex Petrov of BitFury over Twitter DM.
Let's see why these two arguments fall apart under scrutiny. I didn't have much time to write this blog post, so its coverage will jump between these two arguments chaotically, which is quite fitting given the topic.

Smallest First vs. Most Needy First
The shift in BitFury's behavior comes down to a switch from "largest fees per byte first" strategy to "smallest first".

This switch makes sense only if what you care about are superficial metrics, and then, only if you have a tiny time horizon and are not concerned with the big picture.

Scheduling Theory and Bitcoin
The core of the second argument is based on a simple result from scheduling theory, which says that shortest-job-first is the optimal strategy if what you care about is to minimize completion time, that is, time from submission of a transaction to its appearance in a block.

The reasoning for this is simple: assume there are transactions A, B and C. Suppose A is 1MB large while B and C are 500KB each. Mining A first, then B and C together yields a collective wait time of 1 (for A) + 2 (for B) + 2 (for C) = 5 block-times for 3 users, or 5/3 blocks per transaction submitter. Mining B and C first, followed by A, yields a collective wait time of 1 (for B) + 1 (for C) + 2 (for A) = 4 block-times for 3 users, or 4/3. The latter is clearly shorter than the former. If we apply this logic iteratively, we'll find that it makes the most sense for the miners to prioritize small transactions first, and mine transactions in sorted order, from smallest to largest.

So Alex's logic seems, superficially, to make sense: if we are given a fixed set of transactions in a batch at the beginning of time, if the users submitting them are honest and not trying to game the system, and our goal is solely to minimize user wait time in a world where every transaction has a user waiting for it to clear and all users are equally important, then picking the small transactions first is a good strategy. That's why you see people at well-run airports, banks, and customs lines pull the people who need little time to service out of the line, and serve first. Anyone with a valid passport and simple itinerary knows the pain of getting stuck behind that guy who is missing paperwork, was born on the Marshall Islands just as it was changing hands, whose parents are Liberland natives -- he is going to take a while, and more people would feel better if he stood aside and let the line clear up. This is also why, at the Apple Store, they ask you if your transaction is short and easy, and expedite you if it is: they don't want you to get stuck behind the problem person who has a complicated transaction involving 2 returns, 3 gift cards under slightly different names, and the involvement of an Apple Genius. Shortest-Job-First is a provably optimal strategy, for serving a static batch of inflexible, unchanging requests.

But the logic fails because the premise is not correct. Smallest-first is a terrible, short-sighted strategy when applied to Bitcoin.

Bitcoin transactions are flexible. A large transaction can easily be turned into multiple small transactions, that, together, take up more space than the original transaction. Mining small transactions first provides an incentive to wallets to break up their transactions into such smaller pieces. But many small transactions that accomplish the same task as a single big transaction actually consume more space than the single big transaction. So, in aggregate, they reduce the system's economic throughput. They are a wasteful way to use our precious block space.

Bitcoin transactions are also not equally important. The main metric we have for telling apart the important transactions from worthless spam is the fee they carry: important transactions carry more in fees. Processing the transactions that are unimportant first will reduce the wait time for transactions whose users do not mind waiting, while making the people with time-limited transactions suffer longer. It's a strategy purely for optics, aiming to lower numbers of waiting transactions, not maximize the actual good that the system is doing or serve the people who have signaled their need for service.

Finally, Bitcoin users want predictability. Those people in favor of a fee market especially require predictability: if the market is being cleared in a haphazard, random order, then the wallets will have no feedback on whether their fees are high, low, or just right. Chaos isn't a good strategy when you want to develop a feedback loop.

Fundamental Problem
Overall, smallest first is a fundamentally bad idea because it breaks the connection with the fee paid and the resources consumed. Recall that the block space is the limited resource here, and the fees paid are our way of gating that access, of measuring who needs it most. Hence, the default metric to sort transactions by is satoshis per byte -- this ensures that the transactions that do the most economic good get prioritized first.

Switching to small-transactions-first enables BitFury to post this tweet and collect kudos from the community for entirely the wrong reasons.

First, the system should not be processing low importance transactions over more important ones. Maximizing economic good requires going after the most economically useful transactions first, and our only proxy for "economically most useful" is to sort by largest-fees-per-byte-first.

Second, one miner sweeping up the smallest, lower-fee transactions doesn't really do any good for the system. Someone still has to mine the larger transactions. Those outstanding large transactions still need to be cleared. A temporary, short term increase in the transaction rate for one miner doesn't achieve anything in the longer term. It's like a teenager cleaning up her desk and sorting her socks, really quickly -- it's a nice but ultimately pointless gesture, her tasks aren't done until the entire room is cleaned up, and the sum total of tasks still takes the same amount of time. She left the hard work to others.

Third, this policy provides an incentive to wallets to break up their transactions, to issue many smaller transactions in lieu of a single large one. That would lead to more wasted space overall, and a net decrease in throughput. A miner that did this in a predictable fashion would be damaging to the network.

Fourth, prioritizing small transactions can mislead or confuse the fee estimators built into wallets. I don't have the time to examine the various fee estimators today, but I believe the default fee estimator has built into it the assumption that miners will maximize their profits and perform largest-fees-per-byte-first, and uses the fee distribution in the mempool to pick its own fees. In this case, seeing high fee transactions sit around and not get mined will cause the users to actually bid even higher fees, actually leading to an added expense for users until the wallets adapt. Now, this is not the only way to estimate the fees (in fact, it is notoriously difficult to estimate the fees) . There may be fee estimators out there that instead base their decisions on the fees found in mined blocks. In that case, they will issue transactions with low fees, which will lead to stuck transactions and a bad user experience.

Finally, once the wallets adapt to smallest-first mining, their best strategy will be to attach the lowest possible fee to every transaction. The mempool then becomes a Hail Mary zone, where people toss their transactions cut up into small little chunks, and hope that the miners will sweep through their precious transfers just by sheer happenstance. The fee market will collapse, and we can no longer have a rational market, because the miners will not be behaving rationally, putting up the space in the blocks up for auction. Imagine a web search service, where you pay solely a fixed fee to place your ads, and the ads are included based on chance. This is not a winning strategy for anyone. Just ask Yahoo.

I'm Doing Work In An Irrational Order to Reduce My Workload
Alex Petrov of BitFury has also expressed concern that, when transactions sit around in the mempool and expire, they get resubmitted, causing the miners to have to re-validate them. This is tantamount to saying that, because you are overloaded by your boss asking you to do the same N things over and over again, you'll do them in an irrational order. Once again, Alex may be pointing to something that might need fixing, but the fix is almost certainly not smallest-first. Adding more resources, parallelizing validation, maintaining a 1 bit validation cache even when transactions are evicted, etc are all effective techniques for avoiding repeated work.

Are There Better Ways To Reduce The Mempool?
One simple way to reduce the mempool backlog is to make the blocks larger, either through a blocksize increase or through the more complex Segwit patch. That will reduce fees, to boot, in return for increasing the space, bandwidth and CPU consumption of Bitcoin. Given how cheap and plentiful storage and CPU are, and how much bandwidth increased just last year alone, adopting some kind of a blocksize increase is the thing to do.

Thanks, but no thanks
Overall, smallest-first is, at best, a strange strategy. It most certainly does not accomplish what we all need: more useful economic activity recorded quickly on the blockchain.

Luckily, it's also a losing strategy: at the moment, a miner mining smallest-first will earn around 5% lower in BTC terms than what it would have been had they gone for mining largest-fees-per-byte-first. Let's hope that this dampens their behavior and counteracts the damage they inflict on Bitcoin through increased delays on important transactions, perverse incentives, worse utilization of the blockchain space and potentially increased fees.

Aviv Zohar said it best when he quipped "[smallest-first] will raise the revenue of other miners and eventually push irrational ones out of the market."
The Greening of Blockchains

Hacking Distributed
 
The Greening of Blockchains

Image/photo

The glorious view from our windows at Cornell Tech takes in 432 Park Avenue, the tallest residential building in the world. This tower is a monument to many things. Above all, for a student of Financial systems, it epitomizes ways to store wealth with breathtaking waste. (Fittingly, it was inspired by a wastepaper basket, shown to the right.) Buildings like it are sprouting up around NYC as investment vehicles for the ultra-wealthy, and their owners don’t actually live much in them. 432 Park and its ilk are essentially hollow vaults.

Something similar can be said for Bitcoin. As a concept and technological inspiration, Bitcoin is a marvelous thing. And unquestionably like 432 Park, it does see legitimate and valuable uses (and some shady ones). As a currency, though, Bitcoin serves in no small degree as a wasteful and ecologically damaging way for people to park their money.

There are a number of ways to substantiate this claim. One is in terms of its electricity consumption. Estimates vary, but it is likely that the Bitcoin network consumes roughly as much electricity as a nuclear reactor, about 1/3 of the entire electricity consumption of the entire country of Ireland. (See our back-of-the-envelope calculations in the blog notes.) To view this in another light, a recent IC3 paper estimated the cost-per-confirmed transaction at as much as $6.20 in capital costs and electricity. (Transaction rates have been rising, and today the figure is substantially lower, but still high.) That’s $6.20 in resources per transaction to move money between accounts in the same system.

Bitcoin proponents argue that this is simply the cost of decentralization. A credit-card network doesn’t provide the pseudonymity, freedom from government interference, portability, and other features of Bitcoin, so it isn’t comparable. This is true. But it isn’t a law of nature that a system like Bitcoin should be so resource-intensive. Researchers at IC3 believe that the many benefits of Bitcoin can be had without the waste. In a few papers released over the past month or so, we’ve outlined three different approaches to the development of greener alternatives:
  • PieceWork is a tweak to standard cryptocurrency PoWs that enables recycling of mining effort.
  • Resource-Efficient Mining (REM) repurposes innately useful workloads for mining effort. It relies on use of a trusted hardware technology called Intel SGX.
  • Snow White is the Proof-of-Stake system with rigorous security guarantees.
PieceWork: Recycling PoWs
Image/photo

If we can't reduce waste at the source, why not recycle? That's the premise of the first, and simplest idea, called PieceWork. Piecework involves a slight modification to the standard Proof-of-Work (PoW) construction, decomposing it into two layers. One layer produces small PoWs called puzzlets that play a critical role in the mining process and can also, as we shall show, serve useful non-mining purposes.

Consider a standard cryptocurrency, abstracting away into a single value X the details of what gets hashed into a PoW (transactions, the previous block, etc.). A miner’s task then is is simply to search for an input (“nonce”) n∈N for which

H(X, n) ≤ Z,

where Z is a threshold representing the difficulty of the PoW.

To decompose a PoW into two layers, we instead construct it as follows:

H(X, n) = Fout (X, Fin (X, n; rin ), rout ),

where rin = H0(r) and rout = H1(r) for distinct hash functions H0, H1 and a secret value r. (These two values are a technical requirement to prevent what are called block withholdingattacks. See the blog notes.)

A valid solution is a value n such that

Fin (∙, n, ∙) < Zin and Fout (∙, n, ∙) < Zout.

To solve this puzzle or PoW, a miner must first find an n such that Fin (∙, n, ∙) < Zin. This inner-puzzle is what we call a puzzlet. To solve the whole PoW, a miner must find a puzzlet solution. The puzzlet solution must additionally satisfy Fout (… n…) < Zout, meaning that a miner must in general come up with many puzzlet solutions to solve the PoW as a whole. By setting Zin + Zout = Z, one obtains a PoW with the same difficulty as that in (1).

What’s the benefit of this two-layered structure? A puzzlet, i.e., the task of finding a solution n to Fin (∙, n ,∙) < Zin, can be outsourced by a miner or mining pool operator to a worker, and put to any of several non-cryptocurrency goals. DoS prevention for TLS is one example. TLS requires computationally intensive crypto operations from a server to set up connections. Thus it’s a natural target for DoS attacks, prompting the idea of requiring clients to solve PoWs if a server comes under attack, an idea now floated in an IETF proposal. These PoWs used for DoS mitigation can themselves be puzzlets. The effect is that the server becomes a mining pool operator, and its clients become workers. And a DoS attacker effectively showers the victim HTTPS server with cryptocurrency. (Of course, a server can also dispense puzzlets and make money even when it’s not under attack…) Other examples of puzzlet uses are spam prevention (the original PoW goal proposed by Dwork and Naor), MicroMint, and Tor relay payments.

In summary,PieceWork requires only a small modification to standard cryptocurrency PoWs. It turns them into dual-use computational problems and recycle wasted mining effort. How much recycling it can feasibly accomplish is an open research question. PieceWork benefits from a number of previous, related ideas.Our short paper on it can be found here.PieceWork will be presented in April at BITCOIN 2017.

Resource-Efficient Mining (REM): Using Innately Useful Work as Mining Effort
Image/photo

A very different approach to minimizing waste is embraced in our second project, a system called REM. Rather than relying on hash-based PoWs, it makes use of an entirely different type of PoW, in which the W, i.e., the work, is useful. We call this concept Proof of Useful Work (PoUW).

Of course, traditional PoWs have several useful properties, prime among them the ease with which solutions can be verified. Most workloads don’t have this property. To enable verification of work on arbitrary useful workloads, REM relies on a new technology: Intel SGX.

Intel’s new SGX (Software Guard eXtensions) trusted execution environment technology. In a nutshell, SGX enables the execution of an application in a hardware-protected environment, called an enclave, that is isolated from the operating system and other applications. It thus protects the application against tampering by even the owner of the machine on which it’s running. SGX also enables generation of an attestation that proves to a remote party that a particular application was running in an enclave. SGX is already supported in many recent-model Intel CPUs.

As a good way to see how SGX can facilitate mining, it’s worth discussing an elegant mining scheme proposed by Intel called PoET (Proof of Elapsed Time). The idea behind PoET is simple. If miners use SGX, then they can be forced to use only a sanctioned piece of mining software that simulates PoWs. Standard PoWs have solution times that are exponentially distributed. A PoET client can thus sample a solution time from an exponential distribution, simply sit idle until this time elapses, and then wake up with a block in hand. The first client to awake gets to publish its block. An SGX attestation proves to others in the system that the client idled as it should have.

PoET has several nice features. Foremost among them is the fact that (at first glance) it’s virtually energy-waste-free. Clients idle instead of hashing. Block solution times can be tuned to mimic those of a standard mining regime, like Bitcoin or Ethereum mining. Thus PoET can effectively be plugged into such schemes. It is also relatively egalitarian in that it achieves precisely one vote per CPU. PoET, though, has two technical challenges. We call these the broken chips and stale chips problems.

First, the broken chips problem. SGX security isimperfect and, as with any trusted hardware, it’s to be expected that a well-resourced adversary can break it. Thus, it’s to be expected that some SGX CPUs will be broken. In the basic PoET scheme, a broken chip has devastating effect, as it enables a miner to simulate a zero mining times and win every consensus round, i.e., publish all blocks. Intel has proposed a statistical testing regime to detect breaks, but details aren’t published and formal foundations are needed for a good analysis.

REM faces the same challenge. In REM, we have developed a rigorous statistical testing regime with formal foundations and shown analytically and empirically that it is highly effective: It can strictly limit the gains of adversaries that have broken chips while minimizing incorrect rejection of blocks from honest miners.

The stale chips problem is more subtle. Our economic analysis shows that in many practical settings in PoET and related systems, it will be advantageous for a miner to buy old (“stale”) SGX CPUs and cobble them together into “farms” that mine cheaply. Such farms reinstate a fraction of the waste that PoET is trying to avoid to begin with. This is where REM’s Proof of Useful Work (PoUW) approach comes into play. In a nutshell, with PoUW, miners run whatever workloads they consider to be useful---protein-folding computations and ML classification algorithms are a couple of examples considered in our work. Miners can prove that they did work on these problems using SGX. The probability of a miner mining a block is proportional to the amount of work she does. Thus, REM turns otherwise useful work into mining effort. Making PoUW work is technically challenging. It requires that workloads be themselves compiled and instrumented using SGX to prove correctness, an innovation of independent interest introduced in REM.

The biggest objection lodged against SGX-based mining is the fact that it places Intel in charge, undermining the decentralization at the heart of permissionless ledgers. Of course, Intel is already a trust anchor. But we’d view this another way, and characterize REM and PoET as partially decentralized. You canread about REM here, in a paper under submission.

Snow White: Proof of Stake with Rigorous Security Guarantees
Image/photo

Our final approach to reducing cryptocurrency waste is one both proposed and studied by many projects in the cryptocurrency community since the inception of Bitcoin. This idea is called proof of stake, and revolves around the basic premise that rather than mining simulating a lottery where your chance of finding a block is proportional to computing power, mining simulates a lottery where your chance of finding a block is proportional to the number of coins (or “stake”) you have in the system.

A key roadblock to the adoption and deployment of proof of stake systems involves questions around the security guarantees that they provide. This continues to be an ongoing source of controversy and debate in the community, with sources like the Bitcoin Wiki claiming that “Proof of Stake alone is considered to an unworkable consensus mechanism” and efforts like Ethereum’s Casper projectstudying questions of how to design a maximally useful and relevant proof of stake protocol for the next generation of cryptocurrencies.

Despite its potential shortfalls, we believe proof of stake represents a critical new development and direction in both the blockchain and distributed consensus fields. With this in mind, we set out to applyprevious work by Rafael Pass (an IC3 member) and others, in which a model for analyzing and proving consistency, chain growth, and restrictions on adversarial chain impact for proof of work blockchains was developed.

To more accurately model the nature of blockchain distributed consensus, and the implication of network delays, we propose a new model for consensus called the sleepy model. This model more accurately mimics the operation and naturally captures the design of permissionless blockchains. In the sleepy model, a user (node or miner) can leave or join the protocol at will. This is modeled by (non-crashed) users in the protocol being given the ability to “sleep”, or go offline and rejoin the network at some unspecified later date with unmodified original state. The key question then becomes how can we design a useful consensus protocol in the sleepy model, when at least half of all online nodes (or stake) is honestly following the protocol?

The guarantees of consistency and availability are rigorously defined in this new model, more accurately capturing the guarantees users expect from blockchain protocols. The analogues of proof-of-work style guarantees like chain growth (availability) and chain quality (integrity) are also discussed. We believe this new class of consensus protocols in the “sleepy” model represents one of the fundamental contributions of blockchains to the distributed consensus space. Neither the asynchronous, partially synchronous, or synchronous models, in either a permissioned or permissionless setting, prove sufficient to model or reason about these new consensus protocols or the probabilistic and often economic guarantees they provide.

To that end, we are working on two protocols proven in the Sleepy model:Sleepy and Snow White.

Sleepy is a simple protocol intended to achieve the guarantees of chain quality, chain growth, and consistency/agreement with 51% of online nodes being honest. This protocol is intended for deployment in apermissioned context, and assumes stake assigned or instantiated by some trusted source. This makes Sleepy ideal for bankchains or other permissioned deployments, in which the set of stakeholders is known a priori but the blockchain guarantees of robust, auditable distributed consensus remain desirable. Every second, every member of the committee is eligible to “mine” a new block in the system, which involves a standard block mining solution with a public source of entropy as the nonce. Standard difficulty adjustments retarget the block interval to a desired target, as in Bitcoin and Ethereum today. The challenges of choosing an appropriate, ungameable mining function and source of entropy are tackled in the work, and proof is given that no committee member can manipulate the protocol to their advantage.

Snow White, on the other hand, is an extension of Sleepy intended to provide the same rigorous blockchain-derived guarantees in apermissionless setting, such as in the deployment of a public cryptocurrency. Obviously, this is substantially more difficult: choosing appropriate committee members for the block lottery, as well as ensuring that no coalition of these committee members (of bounded size) can game the protocol for more than a negligible advantage, are highly nontrivial. The resulting protocol is actually quite simple: each step, a committee mines as in Sleepy, with a shared source of entropy h0. With sufficiently many bits of entropy in h0 and an appropriately selected committee weighted on stake, it is possible to prove the desired result of chain quality, growth, and consistency in the Sleepy model. Choosing both the committee and h0 such that no adversary or non-majority coalition of adversaries gain substantial advantage by deviating from the protocol is the key to the construction and concrete parameters of the protocol, which are discussed further in our full publication.

Sleepy and Snow White represent the first rigorously justified and proven blockchain consensus protocols in both the permissioned and permissionless proof of stake space. It is our belief that the rigorous proofs of security are valuable as both theoretical efforts and to guide protocol development and deployment. Both the proof and concrete parameterization of these protocols are highly non obvious, and while heuristic protocols designed elsewhere in the community (with only informal justification) may operate in a similar manner to Sleepy, there is no guarantee that subtle network-level, timing, committee / stake poisoning, and other attacks are not present in these protocols. In our work, we assume an optimal adversary with ability to delay network messages up to some arbitrary time, a very strong notion of attacker that makes our protocols the most rigorous conceived in the space thusfar.

You can read about the papers in prepublication manuscripts we have uploaded for release on ePrint: Snow White,Sleepy. Further conference or journal publications with implementation details of these systems, full proofs, simulation results, and experimental comparisons to existing cryptocurrencies are currently in development. We hope to share more exciting news about these new protocols soon.

[It is worth noting that our willingness to assume that the majority of online coins are honestly following the protocol is an assumption that `has been challenged `_ by the Ethereum foundation. We do not necessarily agree with these criticisms or model; we believe that the ε-Nash equilibrium achievable in *Snow White is sufficient for the design of a robust, decentralized coin. Nonetheless, we believe developing and proving protocols secure in this context is valuable: both as the most natural model for private blockchain deployments, and to illuminate common pitfalls in proof of stake protocol design that may lead to attacks in naive protocols. We look forward to a full specification of Ethereum’s Casper, and to comparing both its assumptions and attack surface with that of Snow White.

Notes
Back-of-the-envelope Bitcoin electricity consumption calculation
There are many estimates of the electricity consumption of the Bitcoin network, but we don’t find them convincing. For example, this widely cited onederives an upper bound of 10 GW (in 2014!). As we’ll see from a simple calculation below, that would imply that miners were losing huge amounts of money. So here’s our crack at a crude estimate.

Using the technique in this paper, to obtain a lower bound on electricity consumption, let’s take the Antminer S9 to represent the state of the art in mining rigs. It consumes 0.098 W/GH. The current mining rate of the Bitcoin network is about 3,330,000 TH/s. Thus, were all miners using Antminer S9s, the electricity consumption of the network would be about 326 MW. (Of course, many miners are probably using less efficient rigs, so this is a loose lower bound.)

To obtain an upper bound on electricity consumption, assume that miners are rational, i.e., won’t mine if it causes them to lose money. At the current price of about $1000 / BTC, given a 12.5 BTC mining reward and block production rate of about 6 blocks per hour, the global mining reward per hour is about $72,500. A common, extremely cheap form of electricity used by miners is Chinese hydroelectric power; the very low end of the levelized cost of such electricityis $0.02 / kWh. Thus rational miners will consume no more than 3.625 GW of electricity. (Of course, this estimate disregards the capital costs of mining, and is therefore probably a quite loose upper bound.)

Taking the log-average of these two bounds yields an estimate of 1.075 GW, about the output of a single unit in a nuclear power station. Ireland’s average electricity consumption is about 3.25 GW (as derived from this 2013 figure).

Again, this is a crude estimate, but we believe it’s probably within a factor of 2 of the real one.

Why use rin and rout in PieceWork?
It is possible to outsource mining with the standard cryptocurrency PoW H(X,n) ≤ Z, simply by declaring a puzzlet to be the problem of finding an n such that H(X,n) ≤ Z_{easy}, for some Z_{easy} > Z. In other words, a worker can be asked to find a solution to a PoW easier than the target. But with some probability, a solution to H(X,n) ≤ Z_{easy} will also be a solution to H(X,n) ≤ Z, i.e., will solve the outsourcing miner’s PoW.

The problem with this approach is that a malicious worker can mount ablock withholding attack. If it happens to find a solution to H(X,n) ≤ Z, it can simply not submit it. Or it can demand a bribe from the outsourcer. Use of rin and routconceals from a worker whether or not a puzzlet solution is also a solution to the global PoW, preventing such attacks.
The Greening of Blockchains

Hacking Distributed
 
The Greening of Blockchains

Image/photo

The glorious view from our windows at Cornell Tech takes in 432 Park Avenue, the tallest residential building in the world. This tower is a monument to many things. Above all, for a student of Financial systems, it epitomizes ways to store wealth with breathtaking waste. (Fittingly, it was inspired by a wastepaper basket, shown to the right.) Buildings like it are sprouting up around NYC as investment vehicles for the ultra-wealthy, and their owners don’t actually live much in them. 432 Park and its ilk are essentially hollow vaults.

Something similar can be said for Bitcoin. As a concept and technological inspiration, Bitcoin is a marvelous thing. And unquestionably like 432 Park, it does see legitimate and valuable uses (and some shady ones). As a currency, though, Bitcoin serves in no small degree as a wasteful and ecologically damaging way for people to park their money.

There are a number of ways to substantiate this claim. One is in terms of its electricity consumption. Estimates vary, but it is likely that the Bitcoin network consumes roughly as much electricity as a nuclear reactor, about 1/3 of the entire electricity consumption of the entire country of Ireland. (See our back-of-the-envelope calculations in the blog notes.) To view this in another light, a recent IC3 paper estimated the cost-per-confirmed transaction at as much as $6.20 in capital costs and electricity. (Transaction rates have been rising, and today the figure is substantially lower, but still high.) That’s $6.20 in resources per transaction to move money between accounts in the same system.

Bitcoin proponents argue that this is simply the cost of decentralization. A credit-card network doesn’t provide the pseudonymity, freedom from government interference, portability, and other features of Bitcoin, so it isn’t comparable. This is true. But it isn’t a law of nature that a system like Bitcoin should be so resource-intensive. Researchers at IC3 believe that the many benefits of Bitcoin can be had without the waste. In a few papers released over the past month or so, we’ve outlined three different approaches to the development of greener alternatives:
  • PieceWork is a tweak to standard cryptocurrency PoWs that enables recycling of mining effort.
  • Resource-Efficient Mining (REM) repurposes innately useful workloads for mining effort. It relies on use of a trusted hardware technology called Intel SGX.
  • Snow White is the Proof-of-Stake system with rigorous security guarantees.
PieceWork: Recycling PoWs
Image/photo

If we can't reduce waste at the source, why not recycle? That's the premise of the first, and simplest idea, called PieceWork. Piecework involves a slight modification to the standard Proof-of-Work (PoW) construction, decomposing it into two layers. One layer produces small PoWs called puzzlets that play a critical role in the mining process and can also, as we shall show, serve useful non-mining purposes.

Consider a standard cryptocurrency, abstracting away into a single value X the details of what gets hashed into a PoW (transactions, the previous block, etc.). A miner’s task then is is simply to search for an input (“nonce”) n∈N for which

H(X, n) ≤ Z,

where Z is a threshold representing the difficulty of the PoW.

To decompose a PoW into two layers, we instead construct it as follows:

H(X, n) = Fout (X, Fin (X, n; rin ), rout ),

where rin = H0(r) and rout = H1(r) for distinct hash functions H0, H1 and a secret value r. (These two values are a technical requirement to prevent what are called block withholdingattacks. See the blog notes.)

A valid solution is a value n such that

Fin (∙, n, ∙) < Zin and Fout (∙, n, ∙) < Zout.

To solve this puzzle or PoW, a miner must first find an n such that Fin (∙, n, ∙) < Zin. This inner-puzzle is what we call a puzzlet. To solve the whole PoW, a miner must find a puzzlet solution. The puzzlet solution must additionally satisfy Fout (… n…) < Zout, meaning that a miner must in general come up with many puzzlet solutions to solve the PoW as a whole. By setting Zin + Zout = Z, one obtains a PoW with the same difficulty as that in (1).

What’s the benefit of this two-layered structure? A puzzlet, i.e., the task of finding a solution n to Fin (∙, n ,∙) < Zin, can be outsourced by a miner or mining pool operator to a worker, and put to any of several non-cryptocurrency goals. DoS prevention for TLS is one example. TLS requires computationally intensive crypto operations from a server to set up connections. Thus it’s a natural target for DoS attacks, prompting the idea of requiring clients to solve PoWs if a server comes under attack, an idea now floated in an IETF proposal. These PoWs used for DoS mitigation can themselves be puzzlets. The effect is that the server becomes a mining pool operator, and its clients become workers. And a DoS attacker effectively showers the victim HTTPS server with cryptocurrency. (Of course, a server can also dispense puzzlets and make money even when it’s not under attack…) Other examples of puzzlet uses are spam prevention (the original PoW goal proposed by Dwork and Naor), MicroMint, and Tor relay payments.

In summary,PieceWork requires only a small modification to standard cryptocurrency PoWs. It turns them into dual-use computational problems and recycle wasted mining effort. How much recycling it can feasibly accomplish is an open research question. PieceWork benefits from a number of previous, related ideas.Our short paper on it can be found here.PieceWork will be presented in April at BITCOIN 2017.

Resource-Efficient Mining (REM): Using Innately Useful Work as Mining Effort
Image/photo

A very different approach to minimizing waste is embraced in our second project, a system called REM. Rather than relying on hash-based PoWs, it makes use of an entirely different type of PoW, in which the W, i.e., the work, is useful. We call this concept Proof of Useful Work (PoUW).

Of course, traditional PoWs have several useful properties, prime among them the ease with which solutions can be verified. Most workloads don’t have this property. To enable verification of work on arbitrary useful workloads, REM relies on a new technology: Intel SGX.

Intel’s new SGX (Software Guard eXtensions) trusted execution environment technology. In a nutshell, SGX enables the execution of an application in a hardware-protected environment, called an enclave, that is isolated from the operating system and other applications. It thus protects the application against tampering by even the owner of the machine on which it’s running. SGX also enables generation of an attestation that proves to a remote party that a particular application was running in an enclave. SGX is already supported in many recent-model Intel CPUs.

As a good way to see how SGX can facilitate mining, it’s worth discussing an elegant mining scheme proposed by Intel called PoET (Proof of Elapsed Time). The idea behind PoET is simple. If miners use SGX, then they can be forced to use only a sanctioned piece of mining software that simulates PoWs. Standard PoWs have solution times that are exponentially distributed. A PoET client can thus sample a solution time from an exponential distribution, simply sit idle until this time elapses, and then wake up with a block in hand. The first client to awake gets to publish its block. An SGX attestation proves to others in the system that the client idled as it should have.

PoET has several nice features. Foremost among them is the fact that (at first glance) it’s virtually energy-waste-free. Clients idle instead of hashing. Block solution times can be tuned to mimic those of a standard mining regime, like Bitcoin or Ethereum mining. Thus PoET can effectively be plugged into such schemes. It is also relatively egalitarian in that it achieves precisely one vote per CPU. PoET, though, has two technical challenges. We call these the broken chips and stale chips problems.

First, the broken chips problem. SGX security isimperfect and, as with any trusted hardware, it’s to be expected that a well-resourced adversary can break it. Thus, it’s to be expected that some SGX CPUs will be broken. In the basic PoET scheme, a broken chip has devastating effect, as it enables a miner to simulate a zero mining times and win every consensus round, i.e., publish all blocks. Intel has proposed a statistical testing regime to detect breaks, but details aren’t published and formal foundations are needed for a good analysis.

REM faces the same challenge. In REM, we have developed a rigorous statistical testing regime with formal foundations and shown analytically and empirically that it is highly effective: It can strictly limit the gains of adversaries that have broken chips while minimizing incorrect rejection of blocks from honest miners.

The stale chips problem is more subtle. Our economic analysis shows that in many practical settings in PoET and related systems, it will be advantageous for a miner to buy old (“stale”) SGX CPUs and cobble them together into “farms” that mine cheaply. Such farms reinstate a fraction of the waste that PoET is trying to avoid to begin with. This is where REM’s Proof of Useful Work (PoUW) approach comes into play. In a nutshell, with PoUW, miners run whatever workloads they consider to be useful---protein-folding computations and ML classification algorithms are a couple of examples considered in our work. Miners can prove that they did work on these problems using SGX. The probability of a miner mining a block is proportional to the amount of work she does. Thus, REM turns otherwise useful work into mining effort. Making PoUW work is technically challenging. It requires that workloads be themselves compiled and instrumented using SGX to prove correctness, an innovation of independent interest introduced in REM.

The biggest objection lodged against SGX-based mining is the fact that it places Intel in charge, undermining the decentralization at the heart of permissionless ledgers. Of course, Intel is already a trust anchor. But we’d view this another way, and characterize REM and PoET as partially decentralized. You canread about REM here, in a paper under submission.

Snow White: Proof of Stake with Rigorous Security Guarantees
Image/photo

Our final approach to reducing cryptocurrency waste is one both proposed and studied by many projects in the cryptocurrency community since the inception of Bitcoin. This idea is called proof of stake, and revolves around the basic premise that rather than mining simulating a lottery where your chance of finding a block is proportional to computing power, mining simulates a lottery where your chance of finding a block is proportional to the number of coins (or “stake”) you have in the system.

A key roadblock to the adoption and deployment of proof of stake systems involves questions around the security guarantees that they provide. This continues to be an ongoing source of controversy and debate in the community, with sources like the Bitcoin Wiki claiming that “Proof of Stake alone is considered to an unworkable consensus mechanism” and efforts like Ethereum’s Casper projectstudying questions of how to design a maximally useful and relevant proof of stake protocol for the next generation of cryptocurrencies.

Despite its potential shortfalls, we believe proof of stake represents a critical new development and direction in both the blockchain and distributed consensus fields. With this in mind, we set out to applyprevious work by Rafael Pass (an IC3 member) and others, in which a model for analyzing and proving consistency, chain growth, and restrictions on adversarial chain impact for proof of work blockchains was developed.

To more accurately model the nature of blockchain distributed consensus, and the implication of network delays, we propose a new model for consensus called the sleepy model. This model more accurately mimics the operation and naturally captures the design of permissionless blockchains. In the sleepy model, a user (node or miner) can leave or join the protocol at will. This is modeled by (non-crashed) users in the protocol being given the ability to “sleep”, or go offline and rejoin the network at some unspecified later date with unmodified original state. The key question then becomes how can we design a useful consensus protocol in the sleepy model, when at least half of all online nodes (or stake) is honestly following the protocol?

The guarantees of consistency and availability are rigorously defined in this new model, more accurately capturing the guarantees users expect from blockchain protocols. The analogues of proof-of-work style guarantees like chain growth (availability) and chain quality (integrity) are also discussed. We believe this new class of consensus protocols in the “sleepy” model represents one of the fundamental contributions of blockchains to the distributed consensus space. Neither the asynchronous, partially synchronous, or synchronous models, in either a permissioned or permissionless setting, prove sufficient to model or reason about these new consensus protocols or the probabilistic and often economic guarantees they provide.

To that end, we are working on two protocols proven in the Sleepy model:Sleepy and Snow White.

Sleepy is a simple protocol intended to achieve the guarantees of chain quality, chain growth, and consistency/agreement with 51% of online nodes being honest. This protocol is intended for deployment in apermissioned context, and assumes stake assigned or instantiated by some trusted source. This makes Sleepy ideal for bankchains or other permissioned deployments, in which the set of stakeholders is known a priori but the blockchain guarantees of robust, auditable distributed consensus remain desirable. Every second, every member of the committee is eligible to “mine” a new block in the system, which involves a standard block mining solution with a public source of entropy as the nonce. Standard difficulty adjustments retarget the block interval to a desired target, as in Bitcoin and Ethereum today. The challenges of choosing an appropriate, ungameable mining function and source of entropy are tackled in the work, and proof is given that no committee member can manipulate the protocol to their advantage.

Snow White, on the other hand, is an extension of Sleepy intended to provide the same rigorous blockchain-derived guarantees in apermissionless setting, such as in the deployment of a public cryptocurrency. Obviously, this is substantially more difficult: choosing appropriate committee members for the block lottery, as well as ensuring that no coalition of these committee members (of bounded size) can game the protocol for more than a negligible advantage, are highly nontrivial. The resulting protocol is actually quite simple: each step, a committee mines as in Sleepy, with a shared source of entropy h0. With sufficiently many bits of entropy in h0 and an appropriately selected committee weighted on stake, it is possible to prove the desired result of chain quality, growth, and consistency in the Sleepy model. Choosing both the committee and h0 such that no adversary or non-majority coalition of adversaries gain substantial advantage by deviating from the protocol is the key to the construction and concrete parameters of the protocol, which are discussed further in our full publication.

Sleepy and Snow White represent the first rigorously justified and proven blockchain consensus protocols in both the permissioned and permissionless proof of stake space. It is our belief that the rigorous proofs of security are valuable as both theoretical efforts and to guide protocol development and deployment. Both the proof and concrete parameterization of these protocols are highly non obvious, and while heuristic protocols designed elsewhere in the community (with only informal justification) may operate in a similar manner to Sleepy, there is no guarantee that subtle network-level, timing, committee / stake poisoning, and other attacks are not present in these protocols. In our work, we assume an optimal adversary with ability to delay network messages up to some arbitrary time, a very strong notion of attacker that makes our protocols the most rigorous conceived in the space thusfar.

You can read about the papers in prepublication manuscripts we have uploaded for release on ePrint: Snow White,Sleepy. Further conference or journal publications with implementation details of these systems, full proofs, simulation results, and experimental comparisons to existing cryptocurrencies are currently in development. We hope to share more exciting news about these new protocols soon.

[It is worth noting that our willingness to assume that the majority of online coins are honestly following the protocol is an assumption that `has been challenged `_ by the Ethereum foundation. We do not necessarily agree with these criticisms or model; we believe that the ε-Nash equilibrium achievable in *Snow White is sufficient for the design of a robust, decentralized coin. Nonetheless, we believe developing and proving protocols secure in this context is valuable: both as the most natural model for private blockchain deployments, and to illuminate common pitfalls in proof of stake protocol design that may lead to attacks in naive protocols. We look forward to a full specification of Ethereum’s Casper, and to comparing both its assumptions and attack surface with that of Snow White.

Notes
Back-of-the-envelope Bitcoin electricity consumption calculation
There are many estimates of the electricity consumption of the Bitcoin network, but we don’t find them convincing. For example, this widely cited onederives an upper bound of 10 GW (in 2014!). As we’ll see from a simple calculation below, that would imply that miners were losing huge amounts of money. So here’s our crack at a crude estimate.

Using the technique in this paper, to obtain a lower bound on electricity consumption, let’s take the Antminer S9 to represent the state of the art in mining rigs. It consumes 0.098 W/GH. The current mining rate of the Bitcoin network is about 3,330,000 TH/s. Thus, were all miners using Antminer S9s, the electricity consumption of the network would be about 326 MW. (Of course, many miners are probably using less efficient rigs, so this is a loose lower bound.)

To obtain an upper bound on electricity consumption, assume that miners are rational, i.e., won’t mine if it causes them to lose money. At the current price of about $1000 / BTC, given a 12.5 BTC mining reward and block production rate of about 6 blocks per hour, the global mining reward per hour is about $72,500. A common, extremely cheap form of electricity used by miners is Chinese hydroelectric power; the very low end of the levelized cost of such electricityis $0.02 / kWh. Thus rational miners will consume no more than 3.625 GW of electricity. (Of course, this estimate disregards the capital costs of mining, and is therefore probably a quite loose upper bound.)

Taking the log-average of these two bounds yields an estimate of 1.075 GW, about the output of a single unit in a nuclear power station. Ireland’s average electricity consumption is about 3.25 GW (as derived from this 2013 figure).

Again, this is a crude estimate, but we believe it’s probably within a factor of 2 of the real one.

Why use rin and rout in PieceWork?
It is possible to outsource mining with the standard cryptocurrency PoW H(X,n) ≤ Z, simply by declaring a puzzlet to be the problem of finding an n such that H(X,n) ≤ Z_{easy}, for some Z_{easy} > Z. In other words, a worker can be asked to find a solution to a PoW easier than the target. But with some probability, a solution to H(X,n) ≤ Z_{easy} will also be a solution to H(X,n) ≤ Z, i.e., will solve the outsourcing miner’s PoW.

The problem with this approach is that a malicious worker can mount ablock withholding attack. If it happens to find a solution to H(X,n) ≤ Z, it can simply not submit it. Or it can demand a bribe from the outsourcer. Use of rin and routconceals from a worker whether or not a puzzlet solution is also a solution to the global PoW, preventing such attacks.
State of the Bitcoin Network

Hacking Distributed
 
State of the Bitcoin Network

Image/photo
Distribution of 5743 full nodes obtained from bitnodes.21.co/ (Jan 9th, 2017)

The Bitcoin network is similar to a living organism. It continuously undergoes rapid changes in terms of distribution, size, and quality of its components. Its evolution impacts the security and the performance of the whole system.

Image/photo
The current measurement infrastructure is built on 17 nodes

We have been observing the ongoing evolution of the Bitcoin network with a measurement tool that actively collects data from the actual network. Our measurement tool consists of long-running processes executing on a globally distributed infrastructure that spans 5 continents. We have been continuously collecting data regarding the provisioned bandwidth of peers, peer-to-peer latency, and protocol-level network traffic for Bitcoin nodes connected over IPv4, IPv6, and Tor nodes.

We have been using this tool to populate the data for the Miniature World system, whose goal is to replicate the entire Bitcoin network at 1:1 scale in the basement of our department in order to evaluate protocols.

In this post, we want to highlight some of the interesting discoveries from our last batch of measurements in the process of characterizing the Bitcoin network.

Provisioned Bandwidth
Image/photo
Provisioned bandwidth is estimated using the maximum epoch bandwidth

Provisioned bandwidth is a lower bound on the estimated transmission bandwidth of a Bitcoin node. It typically corresponds to the limits imposed by its last-mile connection to the Internet. Provisioned bandwidth forms the bottleneck for a bitcoin peer to receive/transmit blocks, transactions, and corresponding metadata. Higher provisioned bandwidth lets miners propagate/collect blocks to/from the network faster. Our tool measures provisioned bandwidth by requesting a large number of blocks from each peer, dividing the time into epochs and, for each epoch, measuring the bandwidth either until all requested data is received or a predefined timeout is reached. The maximum observed bandwidth in any epoch is the provisioned bandwidth we plot in this section and the next.

The figure shows the provisioned bandwidth measurements for IPv4 peers. Peaks around 10 and 100 Mbit/s regions represent typical bandwidth capacities of a home user, and a typical Amazon EC2 Bitcoin instance. Overall, most nodes seem to be connected at speeds over 5 Mbit/sec. Only about 10% of the nodes have a capacity under 5 Mbit/s and the median is over 50 Mbit/s. The long tailed distribution shows that there exist some nodes with considerably high bandwidth capacities, around 300Mbit/s.

Evolution of Provisioned Bandwidth
Image/photo
Evolution of provisioned bandwidth (IPv4 nodes)

Perhaps our most interesting discovery is that the Bitcoin network has improved tremendously in terms of its provisioned bandwidth.

The measurements show that Bitcoin nodes, which used to be connected to the network at a median speed of 33 Mbit/s in 2016 (See our related paper) are now connected at a median speed of 56 Mbit/s. In other words, the provisioned bandwidth of a typical full node is now 1.7X of what it was in 2016. The network overall is 70% faster compared to last year.

Of course, every measurement study in the real world is subject to experimental limitations and even expected errors. Our study might yield incorrect provisioned bandwidths if (1) the bottleneck on the path lies on the side of the measurement apparatus, and not the measured nodes (i.e. not in the access network a.k.a. "the last mile," or on a link close to the measured node that other nodes contacting the same node would also have to traverse), (2) other traffic near the measurement apparatus interferes with the measurements to make #1 true during a measurement, or (3) if the measured nodes shape traffic in a way that is specific to the measurement apparatus (e.g. throttle it). We have taken great pains to ensure that #1 and #2 errors are minimized. #3 is unlikely given what we know about the predominant client software and nodes' operational procedures. And conditions are sufficiently similar between last year's measurements and this year's such that measurement errors, to the extent they exist, would tend to cancel each other out. In short, we believe there is a genuine speedup in the entire network.

The provisioned bandwidth of a node plays a critical role in determining system parameters, such as the maximum block size. The increase in provisioned bandwidth suggests that, for people who were happy with the level of decentralization that Bitcoin exhibited last year, blocks can now be made 1.7X larger without impacting their centralization concerns, assuming that these measurements capture the state of the network.

That last assumption is subject to the caveat that our study examined the entire network, whereas centralization concerns impact the miners. One could push forward the argument that the network conditions between miners are not reflected by the conditions between regular nodes, that the miners evolved differently from the rest of the network over the last year. We look forward to seeing such arguments made scientifically and with quantitative data, as well as seeing other measurement studies that repeat our measurements and bring new raw data into the maximum block size debate.

Finally, do keep in mind that provisioned bandwidth is not the only metric that affects the maximum block size debate. We encourage the community to discuss these findings in a spirit of scientific inquiry, which starts by accepting objective measurements as what they are.

P2P Latency
Image/photo

The network latency between peers impacts the block and transaction propagation times. To estimate the P2P latency, the measurement tool relies on latency measurements from multiple beacons. First, for each pair of peers, it measures the latency to peers from a single vantage point. Using triangle inequality, it estimates upper and lower bounds for the latency between peers. Then it repeats this process from other vantage points to obtain a set of bounds for each such measurement. Finally, the measurement tool determines a range for the estimated latency between each peer by picking the maximum from lower bounds and the minimum from the upper bounds.

The figure shows the estimated mid-range latency of virtual links between IPv4 peers. The results indicate that the median latency of peers is around 110 ms.

Stale Peers
Image/photo
Distribution of stale peers as of Jan 2017

We define a peer as stale if its height is more than 1% behind the height of the best blockchain. Compared to a fresh peer, a stale peer is likely to experience a heavier network traffic due to the potential bootstrapping process. The measurement tool extracts the height field from the version messages to identify such peers in the Bitcoin network. It collects version messages from each peer during the protocol handshake.

Our results indicate that about 2.6% of IPv4 nodes and 1% of IPv6 nodes are stale. All Tor nodes were fresh, which might indicate that at the time of these measurements, no recent Tor node has joined the network.

A stale rate of 2.6% is unexpectedly high. One hypothesis is that these nodes are forever behind the main chain because they are unable to catch up due to their bandwidths being too limited relative to the block size. We evaluated this hypothesis by examining the provisined bandwidths of these nodes. Of the 92 stale IPv4 nodes, 71 responded to our provisioned bandwidth measurement. Their bandwidths were mean 124 Mbits/s, 10th percentile at 7.6 Mbits/s, median at 110 Mbits/s, and 90th percentile at 310 Mbits/s. These statistics are higher than the general population across the board, showing that this hypothesis is false. These nodes do not have slow connections, and their staleness is not due to an inability to catch up due to bandwidth limitations.

We performed a followup study where we examined the level of staleness of the stale nodes. Of the 92 stale IPv4 nodes, 74 responded to this followup. Of these 74, 62 have the same height as before -- i.e. they do not try to catch up. We suspect that a software error is keeping these nodes from making forward progress.

Distribution of Mining Power
To identify the varying power of miners in the Bitcoin network, we examined the weekly distribution of mining power in a one-year period. Mining power estimation is based on the ratio of blocks generated by miners. In Bitcoin, miners voluntarily provide the identity information as part of each block they mine.

Image/photo
The trendline passes through the median of each batch.

For each week of 2016, we calculated the corresponding mining power of peers. We assigned index 1 to the largest weekly mining power, index 2 to the second one, and so on. Figure shows the top 20 weekly mining power distribution. Each batch of bars represents the collection of weekly mining power ratios. Note that miners not necesarily preserve their index throughout different weeks. The results show that the weekly mining power of a single miner has never exceeded the 30% of the overall mining power in 2016. Morever, in the second half of the year, the highest mining power has consistently been under the 20% range.

The details of our measurements are now available in slides, and there is a corresponding video presentation on Miniature World talk at BPASE '17.
State of the Bitcoin Network

Hacking Distributed
 
State of the Bitcoin Network

Image/photo
Distribution of 5743 full nodes obtained from bitnodes.21.co/ (Jan 9th, 2017)

The Bitcoin network is similar to a living organism. It continuously undergoes rapid changes in terms of distribution, size, and quality of its components. Its evolution impacts the security and the performance of the whole system.

Image/photo
The current measurement infrastructure is built on 17 nodes

We have been observing the ongoing evolution of the Bitcoin network with a measurement tool that actively collects data from the actual network. Our measurement tool consists of long-running processes running on an infrastructure that is globally distributed across 5 continents. We have been continuously collecting data regarding the provisioned bandwidth of peers, peer-to-peer latency, protocol-level network traffic, and the impact of time on the collected measurements for Bitcoin nodes connected over IPv4, IPv6, and Tor nodes.

We have been using this tool to populate the data for the Miniature World system, whose goal is to replicate the entire Bitcoin network at 1:1 scale in the basement of our department in order to evaluate protocols.

In this post, we want to highlight some of the interesting discoveries from our last batch of measurements in the process of characterizing the Bitcoin network.

Provisioned Bandwidth
Image/photo
Provisioned bandwidth is estimated using the maximum epoch bandwidth

Provisioned bandwidth is the measured bottleneck network bandwidth of a bitcoin node. It typically corresponds to the limits imposed by its last-mile connection to the Internet. Provisioned bandwidth forms the bottleneck for a bitcoin peer to receive/transmit blocks, transactions, and corresponding metadata. Higher provisioned bandwidth lets miners propagate/collect blocks to/from the network faster. Our tool measures provisioned bandwidth by requesting a large number of blocks from each peer, dividing the time into epochs and, for each epoch, measuring the bandwidth either until all requested data is received or a predefined timeout is reached. The maximum observed bandwidth in any epoch is the provisioned bandwidth we plot in this section and the next.

The figure shows the provisioned bandwidth measurements for IPv4 peers. Peaks around 10 and 100 Mbit/s regions represent typical bandwidth capacities of a home user, and a typical Amazon EC2 Bitcoin instance. Overall, most nodes seem to be connected at speeds over 5 Mbit/sec. Only about 10% of the nodes have a capacity under 5 Mbit/s and the median is over 50 Mbit/s. The long tailed distribution shows that there exist some nodes with considerably high bandwidth capacities, around 300Mbit/s.

Evolution of Provisioned Bandwidth
Image/photo
Evolution of provisioned bandwidth (IPv4 nodes)

Perhaps our most interesting discovery is that the Bitcoin network has improved tremendously in terms of its provisioned bandwidth.

The measurements show that Bitcoin nodes, which used to be connected to the network at a median speed of 33 Mbit/s in 2016 (See our related paper) are now connected at a median speed of 56 Mbit/s. In other words, the provisioned bandwidth of a typical full node is now 1.7X of what it was in 2016. The network overall is 70% faster compared to last year.

Of course, every measurement study in the real world is subject to experimental limitations and even expected errors. Our study might yield incorrect provisioned bandwidths if (1) the bottleneck on the path lies on the side of the measurement apparatus, and not the measured nodes (i.e. not in the access network a.k.a. "the last mile," or on a link close to the measured node that other nodes contacting the same node would also have to traverse), (2) other traffic near the measurement apparatus interferes with the measurements to make #1 true during a measurement, or (3) if the measured nodes shape traffic in a way is specific to the measurement apparatus (e.g. throttle it). We have taken great pains to ensure that #1 and #2 errors are minimized. #3 is unlikely given what we know about the predominant clients and their operational procedures. And conditions are sufficiently similar between last year's measurements and this year's, such that any measurement errors would either tend to cancel each other out. In short, we believe there is a genuine speedup in the entire network.

The provisioned bandwidth of a node plays a critical role in determining system parameters, such as the maximum block size. The increase in provisioned bandwidth suggests that, for people who were happy with the level of decentralization that Bitcoin exhibited last year, blocks can now be made 1.7X larger without impacting their centralization concerns, assuming that these measurements capture the state of the network.

That last assumption is subject to the caveat that our study examined the entire network, whereas centralization concerns impact the miners. One could push forward the argument that the network conditions between miners are not reflected by the conditions between regular nodes, that the miners evolved differently from the rest of the network over the last year. We look forward to seeing such arguments made scientifically and with quantitative data, as well as seeing other measurement studies that repeat our measurements and bring new raw data into the maximum block size debate.

Finally, do keep in mind that provisioned bandwidth is not the only metric that affects the maximum block size debate. We encourage the community to discuss these findings in a spirit of scientific inquiry, which starts by accepting objective measurements as what they are.

P2P Latency
Image/photo

The network latency between peers impacts the block and transaction propagation times. To estimate the P2P latency, the measurement tool relies on latency measurements from multiple beacons. First, for each pair of peers, it measures the latency to peers from a single vantage point. Using triangle inequality, it estimates upper and lower bounds for the latency between peers. Then it repeats this process from other vantage points to obtain a set of bounds for each such measurement. Finally, the measurement tool determines a range for the estimated latency between each peer by picking the maximum from lower bounds and the minimum from the upper bounds.

The figure shows the estimated mid-range latency of virtual links between IPv4 peers. The results indicate that the median latency of peers is around 110 ms.

Stale Peers
Image/photo
Distribution of stale peers as of Jan 2017

We define a peer as stale if its height is more than 1% behind the height of the best blockchain. Compared to a fresh peer, a stale peer is likely to experience a heavier network traffic due to the potential bootstrapping process. The measurement tool extracts the height field from the version messages to identify such peers in the Bitcoin network. It collects version messages from each peer during the protocol handshake.

Our results indicate that about 2.6% of IPv4 nodes and 1% of IPv6 nodes are stale. All Tor nodes were fresh, which might indicate that at the time of these measurements, no recent Tor node has joined the network.

A stale rate of 2.6% is unexpectedly high. One hypothesis is that these nodes are forever behind the main chain because they are unable to catch up due to their bandwidths being too limited relative to the block size. We evaluated this hypothesis by examining the provisined bandwidths of these nodes. Of the 92 stale IPv4 nodes, 71 responded to our provisioned bandwidth measurement. Their bandwidths were mean 124 Mbits/s, 10th percentile at 7.6 Mbits/s, median at 110 Mbits/s, and 90th percentile at 310 Mbits/s. These statistics are higher than the general population across the board. These nodes do not have slow connections, and their staleness is not due to an inability to catch up due to bandwidth limitations.

We performed a followup study where we examined the level of staleness of the stale nodes. Of the 92 stale IPv4 nodes, 74 responded to this followup. Of these 74, 62 have the same height as before -- i.e. they do not try to catch up. We suspect that a software error is keeping these nodes from making forward progress.

Distribution of Mining Power
To identify the varying power of miners in the Bitcoin network, we examined the weekly distribution of mining power in a one-year period. Mining power estimation is based on the ratio of blocks generated by miners. In Bitcoin, miners voluntarily provide the identity information as part of each block they mine.

Image/photo
The trendline passes through the median of each batch.

For each week of 2016, we calculated the corresponding mining power of peers. We assigned index 1 to the largest weekly mining power, index 2 to the second one, and so on. Figure shows the top 20 weekly mining power distribution. Each batch of bars represents the collection of weekly mining power ratios. Note that miners not necesarily preserve their index throughout different weeks. The results show that the weekly mining power of a single miner has never exceeded the 30% of the overall mining power in 2016. Morever, in the second half of the year, the highest mining power has consistently been under the 20% range.

The details of our measurements are now available in slides, and there is a corresponding video presentation on Miniature World talk at BPASE '17.