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!

How Universities Work

In one of my recent posts, I made passing mention of “increasing research productivity” at universities. This is a pretty vague concept, and touches upon a often misunderstood topic: How Universities Work. This post is likely to paint only a partial picture, but I’ve seen that it can sometimes be downright confusing to outsiders, so it bears writing up.

I’ll give a simple model of how university outputs (and funding) work in South Africa. It’s usually not too dissimilar in other countries. Take it with a pinch of salt: the model may be less accurate depending on whether you’re looking at an institutional, departmental, or individual academic’s perspective.

The currency of universities can be summarised by two quantities: full-time equivalent students (FEs), and publication units (PUs). These are a university’s “bottom line”. We need resources (including money) to produce these, and their production usually unlock further resources – with which further FEs and PUs can be produced.

Another pinch of salt: this is a very crude yardstick that is useful to measure university productivity in a quantitative way. The true measure of a university’s productivity, is the impact it has on its society: the quality of the graduates entering productive careers; the knowledge and expertise it imports into its home country; the knowledge and expertise it contributes to the world, and to society and industry as stakeholders.

The University as Educator: Full-Time Equivalent Students

One primary role of the university is to lead matriculants into becoming graduates. The quality of a country’s universities has a direct impact on the quality of its professional workforce, and the depth of its literature and artistic and journalistic discourse. In South Africa, government subsidy is received for each “FE” (full-time equivalent student) enrolled. “Full-time equivalent” means that a part-time student may count only 0.5 FE, or some other fraction depending on course credits. This places pressure on universities to push student enrollment. However, the university also earns subsidy for each FE “delivered”, which is the rather industrious term for leading a student to graduation. This places pressure on universities to minimise drop-out rates and term of study.

It’s clear to see that this system is open to abuse. Enrollment rates can easily be inflated by dropping entrance requirements. Graduation rates can be improved by lowering course standards. However, these short-term strategies may have the opposite effect in the longer term, as a university’s reputation suffers. Also, the success and reputation of a university as educator has a direct effect on the second metric: postgraduate research.

The University as Research Institution: Publication Units

The role of the research university is “a vital issue for development” for countries such as South Africa [1]. Currently, South Africa is deep inside the underdeveloped region of the knowledge divide, with only about 0.93% of GDP spent on R&D [2], and a very low higher education enrollment of approximately 16% [3]. As in many other countries, the South African government incentivises research productivity by providing financial “rewards” for outputs. Here, another crude but useful yardstick comes into play: the publication unit (PU). When a researcher publishes her work in an accredited, peer-reviewed journal, one PU is earned. Publication in conference proceedings receive 0.3 PUs. PUs are divided between collaborating authors, and proof of independent peer review must be demonstrated.

Again, the system can be abused. It’s possible to push up PUs by publishing many lower-quality papers in less reputable journals or conferences, where the standards of peer review or editorial oversight may not be as high. The reputational damage of playing the “numbers game” is less direct.

In other parts of university quality review (e.g. the rating and promotion of individual academics) not only publication numbers are considered, but also the focus and the impact of the research. Impact is typically measured by counting citations to publications. This review of individual researchers’ quality of publications serves to disincentivise the “numbers game” somewhat.

Dealing with Universities

An important point to note is that universities aren’t particularly interested in making money for money’s own sake – but healthy income is critical to growing FEs and PUs, and (more importantly) serving the mission of the university to have an impact on its society and the world.

This can sometimes be confusing to funders and collaborators. We donated 50 microscopes, worth half a million each, for research – why isn’t the university more thankful? Chances are that we are; budget for equipment is always tight. But does that donation translate into a measurable increase in enrollment or publication? We give 30 postgraduate bursaries each year, worth R100k each – this is a strong negotation chip. Well, the value of a bursary to a university is indirect; it rather presents an advantage to students, which may or may not improve enrollment rates (would a student have been able to fund her own studies? what other bursaries were available?). The value of R1 investment in terms of FEs and PUs is rarely clear-cut.

In the end, however, these metrics are just measurable proxies for a university’s true resources: quickened minds, knowledge and ideas. A good university should never mistake the metric for the goal.

Kazakhstan Visit, Issue 4

New Yorker cover: 23 July 2012On 23 July 2012, the New Yorker’s cover showed a scene which relects our fear of becoming disconnected through our connectedness: a family portrait on a beautiful seaside resort – with each individual deeply engrossed in a mobile device, seemingly oblivious of each other and their surroundings. We’re still grappling with the role and etiquette of mobile devices in our connected society, as Scott Adams parodies in this Dilbert cartoon.

The New Yorker cover plays on a common fear that ubiquitously connected mobile devices are, in fact, making us less social; that it can tear away at the fabric of our society if we let it go unchecked.

Of course, we can today connect with people that we never would have been able to reach before.

At the moment, I’m working in a country where I don’t speak either of the main languages (Russian and Kazakh). Very few of the people we’ve met can speak English. The students whom we lecture seem to understand enough English so that we get by with lots of diagrams, maths and some interpretation in between. Our meetings with faculty are interpreted, always with the aid of an undergraduate student who studied English.

Still, we quite often find ourselves without an interpreter, in a country that’s very foreign to us. The last time I had an experience like this, was when I visited Beijing and Wuhan in 2005. I was armed with a small phrasebook, I memorised some Mandarin vocabulary and useful sentences, and I could count up to 10. It was hopeless. My mobile phone, an old Ericsson clamshell, only helped me to phone home when I felt too lonely. I was completely disconnected from the people around me.

Google Translate screenshotForward to Karaganda, Kazakhstan: present day. Our guide, Murat, doesn’t speak more than ten words of English. It doesn’t matter. My smartphone has become our voices. We blurt out sentences at each other in our native languages, laugh at the other party’s incomprehension, then someone calls “translate!” and the phone is passed to him. The Google Translate app does the to and fro between English and Russian – sometimes perfectly accurate; sometimes a bizarre ramble.

Our phones have become deeply personal objects, and sharing and exchanging the device almost creates a sense of personal connection. In shops, restaurants and at the university, strangers smile when you try to communicate something using the phone, and playfully join in to type a response in Russian for translation. And we get our thoughts across.

It’s incredible to me that we are able to connect with people that, only a few years ago, would effectively have been deaf and mute to us. More than that: we’re connecting with people with very different languages, and hence very different backgrounds – exactly the type of people I feel is worth getting to know.

Perhaps mobile devices are tearing away at the fabric of society. But if the fabric of society is sewn together by languages and cultures that stitch us into our familiar prejudices, I say: tear away.

Kazakhstan Visit, Issue 3

Today was down to business with our hosts at the Karaganda State Technical University. Although we came prepared to give lectures, it turns out that the other main reason for our invitation was to explore collaboration opportunities. Most of the day was spent in meetings with professors, the dean and a quick talk with the vice-rector, trying to identify areas in which Stellenbosch (Engineering) and KSTU’s research interests overlap.

The Kazakhstan universities seem to find themselves in the same difficulty as South African universities had a decade or two ago: after a long period of relative isolation (but strong ties to local industry, and a strong engineering culture), the Bologna Process is placing increasing pressure on universities to produce research outputs. This is a very difficult transition to make for a university which focuses mostly on education and industry collaboration. However, Stellenbosch University (certainly E&E Engineering) found itself in a similar situation in the late nineties; it’s only over the past decade that we really started increasing our research productivity

So there seems to be an interesting common ground. I’m struck by many similarities in South Africa and Kazakhstan’s development over the past two decades, and am looking forward to see how things develop over the rest of the visit. I’ve also realised that South African universities have a piece of capital we shouldn’t underestimate: our command of English in a world where the language is the lingua franca of research.

Kazakhstan Visit, Issue 2

I surrendered my passport today.

Any seasoned traveller knows:

  1. Never let someone take your passport.
  2. Stay out of trouble, and never disobey local laws.

So if it turns out that local laws require you to surrender your passport to the police for the duration of your stay, that’s a bit of a conundrum. But the lady organising the exchange was very friendly and reassuring about this, so let’s hope for the best.

I find Kazakhstan a wonderfully friendly place, and the people are relaxed and pleasant. Some parts are super-modern, especially the capital, Astana – don’t these pictures look like something out of the future? But some things harken back to a soviet history that I find strangely appealing. How weird to be inside one of the “ystergordyn” states, with sturdy soviet-era apartment blocks, policemen with extravagantly sloped visored hats, and with a passport somewhere in police custody! There’s a registration card inside my passport that must be stamped by my host city’s officials. I’m not allowed to travel without permission to leave, and my card must be stamped at any next destination (at least that’s how I understand it).

My impression of the old juxtaposed with cutting-edge modernity shares more with South Africa than I expected. Our first visit to the University confirmed this – everything is modernised and renovated beautifully, but there’s a counterpoint of legacy technology, tradition, and a fair amount of future shock.

I’ll tell you more next time. Coenrad and I have grown embarassingly fond of their fatty horsemeat sausages, which is a popular national food. I have some ideas for improving boerewors when I come back (although I suspect some retailers may have beat me to it without telling us).

Anyway, if I get stuck here because I can’t get my passport back, I’m at least sure I’ll eat well…

http://www.flickr.com/search/?q=astana%20architecture

Kazakhstan Visit, Issue 1

My good colleague Prof Coenrad Fourie and I were recently invited for a short trip as visiting professors to the Karaganda State Technical University in Kazakhstan. This has already been a very unique experience, and I’ll try to do a few short posts over the next couple of weeks to journal some of this.

If, like me, you knew nothing of Kazakhstan: first some background. (And just to get it out of the way, no, the country does not feature in a movie that might be your only exposure to the word “Kazakhstan”. Different countries,  in fact.) Kazakhstan is the world’s ninth largest country, and is nestled in a southern alcove of the Russian border, with China to the east, and doing a pinky-shake with Mongolia (have a look). Most of the people are Kazakh, which means they largely stem from the Turkic hordes like the Huns. The ancient Silk Road which connected the Orient and the Occident of the old world, ran through Kazakhstan.

Travelling is part of my job (remind me to write about the reasons for this some time, will you?) but this particular trip was trickier than usual, because South Africans can’t easily obtain visas for Kazakhstan before travelling – there’s no Kazakhstan consulate in South Africa. Consulates in other countries told us that it would be illegal to try to obtain a visa by sending our passports by courier. So we had to travel to our destination without a visa, but with lots and lots of documentation, including a document from their Foreign Affairs ministry with a “visa support number” as reference, and a letter from our own embassy in Kazakhstan.

It’s a bit nerve-racking to travel 22 hours by plane without knowing whether you’ll be let into your destination country. It turned out that the final border entry (where we got our visas issued at Almaty airport) was much easier than getting onto planes at your departure points, where carriers check your documents before issuing a boarding pass. At Delhi airport, an official disappeared with our passports and supporting documents for more than an hour before letting us out of what seemed like a little passenger containment area.

Fortunately, we arrived in our destination country safe and sound. A visit to one of the modernest cities I’ve ever seen, a meal of horsemeat, a 3-hour roadtrip in the dead of night, Google’s babel fish and a mind-boggling tour of a post-soviet city later, we’re finally in Karaganda. But more about this in the next post!

Games development position

moonlight42, a web media development company based in Century Square, Cape Town, is looking for a developer to work on their MMORPG games currently in production and on the planning board.

Minimum experience:

  • Java programming

Recommended experience:

  • J2EE
  • Java Applications Servers (Glassfish in particular)
  • C#
  • JavaScript / jQuery

If you’re interested, you can contact them via their website.

Postgrad newsletter

Our postgraduate coordinater, Tanya Ficker, put together a bumper edition of the Faculty of Engineering’s regular newsletter — you can read it here. This is a great overview of our faculty’s research activities, plus some excellent articles on what some of our alumni are up to.

Evil code in good source

An interesting discussion on Slashdot recently caught my eye: There are allegations that the FBI planted backdoors into the encryption software used by the OpenBSD operating system. Although the lead developer doubts that such backdoors eventually ended up in OpenBSD, code review is still underway.

But hang on, OpenBSD is an open source operating system. Surely if there were back doors built into the encryption software, somebody would have noticed it by now? After all, OpenBSD has been in active open-source development for 15 years, and the claims are that the backdoors were added a decade ago. Furthermore, OpenBSD is highly reputed for its security and correctness of code.

Well, sometimes the best place to hide something is in plain sight. Although no such backdoor has been found yet, that doesn’t mean that it cannot be there. As a very insightful comment in the Slashdot discussion pointed out, hiding nasty stuff in innocuous-looking source code is a bit of a hobby to some, as can be seen in the yearly Underhanded C Contest.

Have a look, for example, at the 2007 winning entries, where the challenge was to “write a short, simple C program that encrypts/decrypts a file, given a password on the command line.” A small fraction of the time, the program should dramatically compromise the strength of the encryption, and make the ciphertext simple or trivial to crack. However, the source code itself must look absolutely innocent.

The winning entries are fascinating: they exploit subtle programming errors that are almost impossible to pick up, and are highly likely to pass more casual review.

Open source is a brilliant model for improving trust in software, because as Eric Raymond put it, “given enough eyeballs, all bugs are shallow” — and, by extension, sneakiness too. But it’s useful to be reminded that this trust should never be absolute.


Switch to our mobile site