Wednesday 7 December 2016

A BitCoin backgrounder written by a guy who knows nothing about Bitcoin...

There is a saying that those who can, do, and those who can't, teach.  In this particular area, I'm definitely not an expert.  But even so, I thought I might jot down things I've learned about BitCoin from people who do seem to know their stuff.  Ask one of them if you have a hard question.

  • So first of all, BitCoin is intended as a kind of anonymous currency: money, used to buy things, but managed in a way that completely hides the identity of the two (or more) parties to each transaction.  At the end of the day, of course, you may prefer actual currency.  So the basic model is that you get BitCoins by exchanging actual money (or other goods) for BitCoins, and this is also how you cash out.  BitCoin is one of many digital currencies these days, but is probably the most widely used.
  • The anonymity aspect is very important to the BitCoin community.  Banks don't like this because they have a legal obligation to know their customers and to be able to explain who they received money from, and who it was transferred to.  Thus part of the BitCoin ecosystem is a new kind of banking model, independent of classic banking.
  • For the purist, BitCoin is not actually considered to be a currency, at least not yet:  BitCoins are classified as commodities by the federal tax authorities in the US.  Theoretically, you are supposed to declare how much you paid for your BitCoins, and how much you sold them for, and pay capital gains tax on the difference, and then for products with BitCoin pricing, there is a way to declare and pay taxes on barter transactions.  I don’t know how many of the people who transact using Bitcoins actually do this.
  • The protocol was invented by Satoshi Nakamura, seemingly an assumed name (it turns out that there is a real Satoshi Nakamura, but he doesn’t seem likely to be the inventor and perhaps is better seen as a victim of identity theft, in this context).   In fact there is a long history of mathematicians banding together and writing things under assumed names (Bourbaki, for example).  Given its relatively sophisticated choice of cryptographic system (elliptic curve cryptography, fundamental to BitCoin, produces large keys and is fairly slow, hence is not widely used in today’s cryptographic systems.  However, it was a great choice for BitCoin, which needed a way to construct a computationally hard puzzle, and also needs immunity to scenarios in which a future quantum computing breakthrough could render RSA ineffective.  But this level of knowledge is typical of students who do well in a modern cryptography course.  In fact, the image of students doing this makes some sense: the actual BitCoin manifesto (the origin document for this whole field) is poorly written, making it unlikely that the authors were academic scholars.  There would be a very easy way to prove that you were one of the original inventors, if so inclined: you could simply reveal that you hold one of the original BitCoins, by spending it: the inventors generated several billion dollars worth of BitCoins early in the blockchain.  But there may be reasons that they wouldn’t wish to spend those.  First, having it become known that you were one of the wealthiest people in the world through your holdings of BitCoin could make you and your family a target for criminals.   Further, the whole point of the original manifesto is political: it puts the protocol forward as a tool for breaking down the capitalist establishment.  A person deeply committed to this view would very likely have destroyed the original BitCoins.  Having done so, it would actually become very difficult to prove that one had created the system.  Further, given this philosophy, “coming out” to claim the associated fame would be a betrayal of principle.

A bit more technical:

  • A BitCoin is actually an entry in a shared ledger, called the BitCoin blockchain.  These days we consider the BitCoin blockchain to be one instance of a more general technology – blockchains, in this sense, are an enabler for other things too.
  • Everything in BitCoin is anonymous.  A coin is just a randomly generated unique identifier.  The endpoints that transact BitCoins are themselves identified by random unique ids (so don’t misplace your digital identity, because this system lacks an id recovery tool). You can create new ids as needed, and can have many ids, and can discard ones you no longer plan to use.
  • In some sense, an endpoint id identifies a component running the BitCoin protocol, and the BitCoin ids represent the form of data that these protocols talk about.  There is no ledger that connects your real-world identity to your endpoint ids, and possession of the BitCoin id is already proof that you “own” that coin. 
  • A BitCoin can only been spent once.  Each transaction generates new coins, even if the transaction didn’t fragment one coin into multiple subcoins or combine multiple coin fragments into a larger coin (each coin has an id, but also has a value, which is denominated in fractions of the official BitCoin currency.  1 BitCoin was worth $733 the day I wrote this Blog posting, about double the value from a year ago.  In fact, BitCoin values have been fairly volatile: it peaked at $1000 in 2014, about 2 years ago, yet was almost devoid of value if you look back to 2013 or earlier, and dipped to $250 early in 2016.

The particular Bitcoin implementation has some interesting properties:

  • It assumes a network layer that uses a form of anonymous gossip to rapidly propagate messages: any machine using the BitCoin software is supposed to be more or less current in the sense of having the same broadcast messages as all the other machines, within a delay of a few minutes (so: not microseconds, but not years either).
  • The participants are assumed to be Byzantine: they will violate the protocol properties if it is in their own self-interest to do so, and this could mean lying in arbitrary ways.
  • BitCoin depends upon public key cryptography: it uses double SHA256 for mining/block creation; and a protocol called Elliptic Curve Digital Signatures (ECDSA) for private/pub keys and signatures.   ECDSA is slow, but quite strong compared to other popular methods, like RSA.
  • The BitCoin protocol uses a form of consensus to fully replicate the Blockchain: each new broadcast proposes an extension to the Blockchain, which needs to countersign the prior end of the Blockchain and then reports some BitcCin transactions, and is signed with a form of cryptographic seal that actually solves a computationally hard puzzle (specifically, the block includes a nonce value that must be set so that the hash of the block has a given number of leading zeros in it.   The BitCoin ledger comes with a dynamic rule for deciding how many zeros are required: once every 2016 blocks, the rule is recomputed.  This value is actually picked so that blocks will be created approximately once every 10 minutes.  You can estimate the total hashing performance of the entire BitCoin network from the rate: as of the end of 2016, the network was computing approximately 2 billion billion hashes per second (the computers in the network are mostly equipped with special hardware – your desktop wouldn’t be able to compute hashes quickly enough to ever manage to publish a new block before some other hardware-accelerated system would beat it to the punch).
  • By publishing an extension to the blockchain, a computer earns money in the form of fractional BitCoins (specifically, a tax on the transactions in the block, plus a reward for finding the hash).  The reward is gradually diminishing, but the belief is that the tax is enough of an incentive to keep the network running even when the reward goes to zero.
  • There can definitely be races in which two or more Blockchain extensions get proposed simultaneously.  The rule is that any participant will adopt the longest valid Blockchain it knows about, even if this means rolling back from what it previously thought was the suffix of the Blockchain (e.g. some machine X might initially believe that A is the last block, but then learn about an extension B, C and since that extension is longer, it would accept the extension even though this causes X to throw A away).
  • Experience shows that rollbacks are pretty rare.  In fact the longer that BitCoin has been running, the less frequent the rollbacks have become and the shorter the average rollback.  Just the same, if your friend sells you a pack of chewing gum for a fraction of a BitCoin, don’t be upset if she waits until a few minutes have passed (until your transaction has been published, and then a few more blocks have been published that extend the chain beyond the one with your transaction in it) before handing over the pack of gum.
  • Various factors limit the number of transactions per block in BitCoin.  As of late 2016 the average block contained about 2000 transactions, up from 500 two years earlier.  But this means that the entire global BitCoin network is actually logging just 288,000 transactions per day.  That number gives a glimpse into the limitations of the model.

And it isn’t necessarily perfect:

  • The transaction rate is basically limited and is way too low for genuine global use of BitCoin in any kind of serious way.
  • My colleagues Ittay Eyal and Gun Sirer showed that BitCoin is actually unfair, in the sense that a cartel of miners can earn more than its fair share of the BitCoin rewards, even though the official BitCoin protocol precludes cartel-like behavior (to cheat, the cartel uses a modified broadcast protocol and only shares its updates within the cartel members, reporting a few blocks at a time to the outside world rather than publishing each block as it is minted).  In effect, the cartel cheats by splitting the work of mining (which is not unusual), but also as soon as some member finds an extension, reorienting the cartel to mine the extension.  Meanwhile, non-cartel members are wasting time mining the original chain.  By the time the cartel publishes its extension (maybe 3 blocks all released at once), the rest of the world has wasted time and only ended up with perhaps 2 blocks worth of extension, which then get rolled back.  So the cartel gets rewarded for keeping its discoveries secret.   There result is basically a kind of game theory analysis of the standard protocol and illustrates the sense in which the protocol really isn’t flawless.
  • As it turns out, Eyal and Sirer also have a protocol to fix the problem (called BitCoin NG), and it has some additional benefits too, notably that it allows more than one extension to the Blockchain at a time and by doing that, gets rid of the limitation on how many transactions can be logged per hour.  But nobody knows whether it will gain wide acceptance.

2 comments:

  1. Hi Ken, I am enjoying reading your blog. We met in 2003 when you helped us (GAO) with a cybersecurity "technology assessment" I'm glad you posted a note on LinkedIn about your blog -- I'm learning a lot from the articles.

    Best regards, -Naba

    P.S. here's that report http://www.gao.gov/assets/160/157541.pdf where we mention you :-)

    ReplyDelete
  2. Wow, I had forgotten the GAO study. Yes, that was really interesting. Are you still at the GAO? The topic is one that should be revisited on a regular frequency… these days, I especially worry about the cyber exposure of the US national power grid, just because our most serious adversaries have demonstrated cyber-disruption capabilities, and the power grid is increasingly cyber-dependent. But the cross-cutting dependencies are very troubling too: hit one of these and everything else freezes up. Several of my blog entries have touched on this issue in one way or another.

    ReplyDelete

This blog is inactive as of early in 2020. Comments have been disabled, and will be rejected as spam.

Note: only a member of this blog may post a comment.