Colloquium: Bitcoin, the Protocol

On Thursday, 20 February 2014, I’ll be presenting a colloquium at the Computer Science Division, entitled Bitcoin, the Protocol. The colloquium is scheduled for 13:00-14:00 in A521 in the General Engineering Building at Stellenbosch University.

Abstract

After four years of quiet growth and development, the Bitcoin cryptocurrency leaped into prominence during 2013. Much of the current discourse around Bitcoin focuses on its viability as currency and its valuation. However, to appreciate its potential as the “Internet of ownership transfer”, a deeper understanding of its technical underpinnings is needed.

In this colloquium, Prof G-J van Rooyen gives a technological primer on the nuts and bolts of the cryptocurrency. The talk will demonstrate how the cunning use of hashes makes it possible to transfer ownership in such a way that cheating (double-spending) is impossible in a correctly functioning network. This is shown to be the most successful solution to the long-standing Byzantine Generals Problem, and a breakthrough in distributed information management.

The talk will also show how the Bitcoin peer-to-peer network forms the first widespread use of triple-entry accounting, and consider the applications of such technology. We will briefly dip into the scripting language built into the protocol: “DUP HASH160 EQUALVERIFY CHECKSIG” turns the Bitcoin protocol into Bitcoin the currency. More advanced scripts can make arbitrarily complex contracts and interactions possible.

Unusual for a colloquium, the talk will include a 0.00925 BTC lucky draw. Come prepared.

Understanding cryptocurrency “confirmation time”

Bitcoin transactions take about 10 minutes to confirm. That makes it pretty useless for point-of-sale services. Litecoin has improved on this by bringing the confirmation time to below 3 minutes, but cryptocurrencies are still dead in the water when competing with the fast transaction processing time of credit cards and EFTs.

The above quote paraphrases a common sentiment about an aspect of cryptocurrencies that can be confusing, namely the time that it takes, on average, to mine a new block of transactions. Many cryptocurrency clients use the first mined block as a reasonable guarantee that the transaction was not fraudulent, and may only allow a user to spend the received money once this first “confirmation” is received.

Does this mean that Bitcoin transactions are doomed to slow transfers of money, and that it cannot be used in retail? Not at all. Cryptocurrencies and traditional banking systems approach transactions with completely opposite approaches in how anonymity and trust are managed. However, cryptocurrencies can operate right across the spectrum of trust, from completely untrusted anonymous transfers (Bitcoin’s basic approach) to fast transfers that make use of established trust — not unlike banks and credit cards.

Transactions are instantaneous

Firstly, let’s get one point completely, unequivocally straight:

When a payer makes an honest transaction in an active cryptocurrency network, the recipient receives the funds immediately.

There is no delay (except the usual network latency, up to maybe a few seconds). If the payer was honest, and the receiver knows this, the payment just happens. If you tell your friend his share of the restaurant bill is 0.02 BTC, and he sends it to you, you’ll know about it immediately, and you don’t have to wait 40 minutes or pester him further.¬† You can only ever spend your own cryptocurrency; there’s no way to trick the network into allowing you to spend someone else’s money. If you don’t have the right key to sign the transaction, your recipient will immediately be able to verify this, and all nodes in the network will reject the transaction as junk.

This is hardly different from faxing a proof-of-payment slip to a landlord, or writing out a cheque to settle a utility bill (there are parts of the world where people still do this!). The recipient trusts that you didn’t forge the slip or the cheque, and even if you did: they know who you are, and the penalties for fraud are harsh.

Well, actually it is different. In a cryptocurrency scheme, the recipient can look at the transaction you generated, and verify that you actually had the funds available to pay him — that’s the magic of the public blockchain. Also, the signature on the transaction is a cryptographically secure proof that you have the right to spend that balance (this is much, much more secure than a signature on a credit card slip, or a PIN tapped into a chip-and-pin terminal).

For these transactions, “mining”, “blocks” and “confirmations” are irrelevant. You received a bona fide payment from someone whose identity is known to you, you can check the signature and the balance yourself, and you don’t need anyone’s help to confirm that this is a valid transaction. If the signature doesn’t match, or the balance isn’t available, you can immediately take the matter up with the payer.

Anonymous transactions

The big difference comes in when a completely anonymous, untrusted payer wishes to pay a recipient.

In traditional payment systems, this scenario is hardly supported at all, except with cash or in-kind transactions. Anonymous payments (such as cash) are fine for smaller transactions (such as buying a sandwich), but are problematic for larger transactions where fraud and counterfeiting become significant problems.

What is amazing about cryptocurrencies is that completely anonymous, untrusted payers can participate from the get go: there’s no long trust-building process of opening accounts and verifying identities. If a payer has an address with a positive balance, the payment can be made — there is just one caveat: the recipient cannot be sure that the anonymous stranger won’t attempt a “double spending attack”, by which the recipient has a chance of eventually receiving nothing, despite an initial valid transaction.

Double-spending

A double-spending attack is outright, prosecutable fraud, but is never a sure bet for the villain. To perform a double-spending attack, the villain must send a transaction to an unsuspecting merchant, and abscond with the goods as soon as the merchant is happy that the payment has cleared. In the mean time, the villain creates a new transaction spending the same funds into an account under his own control, in the hope that the merchant never receives the funds, but that he himself does. Again, the villain can only ever attempt to double-spend her own money, You can’t steal someone’s Bitcoin with this type of attack, just try to spend your own money twice.

A double-spending attack like this has no guarantee of success, even when the merchant doesn’t wait to see if a double-spend was attempted. It nominally has a 50% chance of succeeding, although there are some tricks that a fraudster can attempt to increase her odds a little (usually at financial cost to herself). Worse, there’s no way of hiding it — although the one transaction never ends up in the “longest chain” (the official ledger of valid transactions), the transaction still gets sent to the merchant, and to peers who will try to mine it, and can be used as evidence against the fraudster. The two conflicting transactions signed by her are non-repudiable: double-spends don’t happen by accident. So a fraudster must rely on utter anonymity for the con to succeed.

In the real world, such anonymity is rare. The simplest way to accept instantaneous cryptocurrency payments is to require a positive proof of real-world identity from the payer, so that you can follow up if the payment “bounces” ten minutes later.

The more crypto-libertarian approach is to keep things nice and anonymous, but to wait until the transaction is “confirmed”.

There are confirmations, and confirmations

Now, some disambiguation is needed here. When a merchant with a credit card terminal says the transaction is “confirmed”, the confirmation means that the merchant can safely part with the goods, and be confident that the credit card company will pay over the money in a day or two. The confirmation pretty much means “It’s fine, you can hand over the customer’s latt√©. We promise to pay you the money later (trust us!), and, because we know the customer, we’ll follow up with her so that she pays back the money she now owes us.”

This is by no stretch of the imagination an instantaneous transaction. It’s a fast confirmation that the merchant will receive his money, made possible by the merchant’s trust in the credit card company, and the company’s trust in the customer’s ability to settle her account. Let’s call this a “confirmation of funds available”.

When cryptocurrency applications talk about a transaction being “confirmed” it means something different. The merchant receives the money immediately anyway, but does not know whether a double-spend is going to be attempted. As soon as the transaction takes place, cryptocurrency miners across the world start bundling the transaction into “blocks” with other transactions, and verify that all transactions are legit. This in itself is not very difficult, but Nakamoto’s key insight was that, if you artificially make it hard to “sign off” on a block, and most of the miners are honest (e.g. rejecting double-spends) it becomes impossible for rogue miners to game the system. Let’s call a transaction bundled into a block a “confirmation of funds received”.

This is true because the honest miners are building a long chain of valid transactions that flow into each other, and even if a rogue miner were to slip in a fake block, the honest miners will always be faster at creating a chain of valid transactions, and the network only accepts the “longest chain” as the valid public ledger. For Bitcoin, new blocks are closed off every 10 minutes, on average.

For a merchant, this means that after a wait of no more than 10 minutes, he should have his first “confirmation” that the customer didn’t attempt a double-spend. That’s still not a 100% guarantee — if there is a serious attempt to post fraudulent transactions onto the network, rogue miners may be able to generate two or more blocks and retain the longest chain for a short while, before the honest miners inevitably overtake the attempt at fraud, and the longest chain only contains valid transactions again.

For completely anonymous transactions, a cryptocurrency client may wait until a new transaction is a number of blocks deep into the blockchain before trusting the received funds. The older the block that it’s in, the smaller the chance that it’s just part of a transient tail of fraudulent blocks. For example, the classic Bitcoin client will wait until the new transaction lies six blocks deep before it marks the transaction as “confirmed” — this is called “six confirmations”, and takes approximately an hour.

Calculating risk

It turns out that you can precisely calculate an attacker’s probability of successfully pulling off a double-spend, based on how long the merchant is willing to wait (the number of confirmations), and how much of the mining network the fraudster controls. For example, if the fraudster controls 10% of all the Bitcoin mining power in the world, and the merchant is willing to wait for 8 confirmations, the probability of a successful double-spend is about 1 in 10,000 (see Rosenfeld, M., “Analysis of hashrate-based double spending“).

The mathematics behind this is well-understood, and merchants performing high-value sales in a highly adversarial environment can calculate exactly how many confirmations are needed to make the probability of a double-spend arbitrarily low. If you’re selling an airplane to an anonymous buyer, you might want to wait an hour or two until the payment “clears”.

For casual transactions, 6 confirmations may be complete overkill. For example, after 2 confirmations, a fraudster would need to control more than 10% of the world’s mining power to have a 10% chance for the double-spend to succeed. Multiply this with the probability of actually running into such a customer, and this concern may well make the risk negligible for your hot-dog stand.

Again, this is only a concern when money is accepted from a completely anonymous person, where there is no recourse if the transaction “bounces” in 10 minutes time.

Building trust

An alternative to waiting for blockchain confirmations, is to establish some form of trust between the customer and the merchant. There are many ways to do this, and some very interesting possibilities — I believe that trust management will be an important role of financial institutions in future.

For example, the credit card transaction “works” because the merchant trusts the credit card company to pay him in a few days time, and the credit card company has an established relationship with the customer. The credit card company becomes a proxy for trust between the merchant and the customer.

This is quite simple to replicate using cryptocurrencies. The customer registers with a trusted intermediary, and lists some or all of her cryptocurrency addresses with the intermediary. For example, the intermediary may know the customer personally, and be able to prosecute fraud. Alternatively, the intermediary may preserve anonymity, but charge an insurance premium to offset the risks of fraud. In either case, the intermediary maintains these lists of “green adresses” which are good for the money they hold.

If the merchant trusts the intermediary, and a customer wishes to pay for goods using an account on the list of green addresses, the merchant immediately knows the transaction will clear.

The roles of such intermediaries are likely to become quite important in real-life cryptocommerce. These are also the entities that can manage chargebacks, warranties, insurance against hacking, etc., and I believe financial institutions should carefully look at the business models around such roles.

Conclusion

This has grown into a rather long post, but I hope it helps to illustrate the difference between “confirmation of funds available” used by vendors with fiat currencies, and “confirmation of funds received” in the context of cryptocurrencies. I also hope that it helps to dispel the myth that merchants must necessarily wait for a number of confirmations before a transaction can take place.

UPDATE 2014-01-15 12:12
Updated the text to also clarify that an adversary can only ever try to double-spend her own money — it is impossible to spend someone else’s currency without access to that person’s secret keys. Thanks for the suggestion, @simondlr!


Switch to our mobile site