Monday, September 15, 2014

The math behind why Bitcoin fees are understated

Quite often the biggest reason given that Bitcoin will be adopted by the masses is that it has very low transaction costs. This is simply untrue for most transactions that occur in everyday life. The reality right now is that the transaction costs of Bitcoin are commonly understated. Although there may be plenty of other reasons to use Bitcoin, low transactions costs isn't one of them. This may explain why you haven't cut up and thrown away your credit cards already.

Currently, the Bitcoin transaction mining fees can be anywhere from 5 to 15 cents regardless of the dollar value of the transaction. So it's is just as expensive to transfer $2 or $20 million. These are the only costs that are commonly referenced when claims are made that Bitcoin is cheap. Unfortunately, an implicit assumption made is that you are paid by your employer in Bitcoins, and whoever you pay for any products and services in Bitcoin will keep their money in Bitcoin.

Let's look at why Bitcoin isn't cheap by looking at the steps needed to buy a cup of coffee at a coffee shop using Bitcoin -

  1. Customer transfers dollars to a Bitcoin Exchange or broker to convert Bitcoin to dollars
  2. Customer buys Bitcoin at the exchange
  3. Customer transfers Bitcoin to his/her smartphone wallet at least once
  4. Customer purchases a coffee with Bitcoin from merchant
  5. Bitcoin is converted immediately to dollars by the merchant (to avoid currency fluctuations) 
  6. Coffee is delivered to customer
Now let us first look at all the fees related to this transaction -
  1. Wire-transfer or ACH fee to a Bitcoin Exchange for transferring dollars
  2. Bid-Ask spread costs when converting dollars to Bitcoin
  3. Exchange Fees incurred by the customer for buying Bitcoin
  4. Mining Fee for transferring the Bitcoin to the merchant
  5. Bid-Ask spread costs when the coffee shop converts Bitcoin to dollars
  6. Exchange Fees incurred by coffee shop for selling Bitcoin
  7. Any additional Wire-transfer/ACH fees to transfer dollars to the coffee shop's bank account.
This problem is further complicated by additional international wire transfer fees (which can be around $50 per transaction) if you don't have a lot of money in your bank to negotiate lower fees. The biggest Bitcoin Exchanges are abroad and that's where you can typically get the cheapest rates (i.e. smallest Bid-Ask spread and lowest Exchange Fees). 

Let's do a sample transaction using optimistic real world numbers and an American Bitcoin marketmaker, I am going to use because they are the largest Bitcoin seller in the US and because I can ignore wire transfer costs since they are an American company. Let's see how much money is paid in fees if I start off with $100 .

As of this writing, sells 1 Bitcoin (BTC) for $626.41 and buys for $612.60.  That means the Bid-Ask spread equals $626.41 less $612.60, or $13.81.  The buyer pays $6.905 in Bid-Ask spread/Exchange Fees and thus pays a total amount of $626.41 and receives 1 BTC and the seller pays $6.905 in Bid-Ask spread/Exchange Fees and receives $612.60 for selling 1 BTC. [Note: rolls in Exchange Fees with the Bid-Ask spread.]

Converting the Bid-Ask spread/Exchange Fees of $13.81 to a percentage would give us a Bid-Ask spread/Exchange Fee rate of about 2.2%. So if I purchase Bitcoin with $100, after the Bid-Ask spread/ Exchange Fees, we are left with $97.80. There should be, at a minimum one mining fee, so let's subtract $0.10, which takes our money down to $97.70. This means that combined the customer and the coffee shop pay about 2.3% in fees for this transaction.

Now 2.3% isn't terribly expensive, but it isn't "cheap" either. If you are doing transactions that are of a much smaller value, the mining fee has a greater impact thereby raising this number significantly. The number is approximately in line with what most credit cards charge. Although by using a credit card, the buyer gets insurance that any lost or stolen charges aren't the buyers responsibility. Most importantly, the seller is the one incurring all the credit card fees! It's not rational for the buyer to incur Bid-Ask spread and mining charges if instead the buyer can make the seller incur these charges by using a credit card.

I completely acknowledge that the math can change drastically in unusual circumstances. For example, if you are visiting a foreign country, you will need to pay foreign exchange fees to make purchases with a credit card or cash. In such cases, Bitcoin suddenly becomes the cheapest option to do business. 

Although, for most of the transactions done in a day, 2.3% in fees is not cheap. As a result, for Bitcoin to gain widespread adoption, the retailers will need to offer a discount for customers paying with Bitcoin, similar to how some retailers now offer a cash discount. This is currently not a common practice and it will probably take time for retailers to realize the other benefits of Bitcoin which warrant such a discount. Until such time, these fees may keep Bitcoin from gaining widespread traction at most retailers, and will continue exist as a currency of choice for its anonymous quality and other benefits.

Monday, July 14, 2014

AES vs Brute Force assisted with Moore's law

AES-256 has a few known attacks that are more efficient than an exhaustive search (brute force) due to weakness in AES-256 key schedule algorithm. As a result, Bruce Schneier, the Michael Jordan of cryptographers, has recommended that new applications use AES-128 instead of AES-256.

In practicality, an encryption algorithm's useful life is a lot shorter than its theoretical life due to the development of new mathematical attacks and computational speed doubling roughly every other year. In fact, DES was the standard symmetric encryption algorithm in the 90's before Moore's law made DES obsolete in 1998 when a $250,000 computer cracked a DES cipher in 56 hours.

I wanted to understand how theoretical advances in computational power based on Moore's law would impact the time needed to crack AES-128. Surprisingly, I had some difficulty locating literature on the subject.

I found an EE Times article which computed the amount of time needed to crack AES-128 using the world's fastest supercomputer. In short, their conclusion was that it would take 1.02E18 (about 1 billion billion) years to crack AES-128 if the only option was to use exhaustive search using the world's fastest supercomputer. They computed this number(1.02E18) by dividing the possible number of keys by combinations checks per year. Assumptions used were that the fastest supercomputer currently is 10.51 X 10^15 flops, and it takes 1000 flops to check each key.

Equation 1: Shows it will take 1.02 X 10^18 years to break AES-128 if we use the world's fastest computer today to attempt an exhaustive search of all keys  

The number 31536000 in equation 1 is the number of seconds in a year. Note, upgrading the supercomputer to account for advances in technology over time was not accounted for in their calculations.

Figure 1: It takes One Billion Billion(1.02x10^15) years to crack AES-128?

What I did was modify some of the formulas above used by the EE Times article to account for Moore's law.

Here are some of the basic number assumptions I started out with:
  1. World's fastest Supercomputer in 2014 - 33.86 PFlops (33E10^15 flops)
  2. Moore's Law Speed - Processing power doubles every 2 years 
  3. Numbers of flops needed to test each key combination -1000
Let's leave aside the discussion of Moore's law sustainability for the remainder of this post. I'll leave that discussion to professional physicists. Additionally, if you disagree with any of my assumptions, change them in the spreadsheet I used to do my calculations and try your own assumptions!

Here are the results for AES-128:

Year Years needed to crack
2025 5000 Trillion Years
2050 850 Billion years
2075 148 Million years
2100 25,618 years
2114 200 years
2129 1 year
Table 1: Shows how long an exhaustive search will take to crack AES-128 if we only used the fastest supercomputer of the day (and not upgrade it each year).

The second row in Table 1 should be read as the following, if we used the fastest supercomputer that would be available in the year 2050 to exhaustive search for keys, it would still take 850 billion years to crack AES-128. The last row of Table 1 shows that we would need to time travel to the year 2129 to use their fastest supercomputer available so that we could crack AES-128 via exhaustive search in about one year. Although the year 2129 is still 115 years away, 115 years is still significantly smaller than 1 billion billion years which is commonly quoted as the amount of time needed to crack AES-128. With that said, 115 years is practically good enough for nearly all applications.

In addition to the assumptions listed above, I've made some other hidden assumptions which are probably untrue. Here are a few:

  1. Amount of money spent to buy the world's fastest supercomputer will be the same each year (accounting for inflation). This is likely to underestimate the computational power of the future.
  2. The world's fastest computer today is actually listed correctly on Wikipedia. I suspect the NSA or another government body has a faster supercomputer or crypto cracker elsewhere.
  3. Moore's law will be sustainable for centuries to come.
  4. ASICS are not being used (really bad assumption, just ask Bitcoin miners).
  5. I've ignored all discussion and math of Quantum computers and recent/expected advances in distributed computers (Botnets). 
So what does the chart look like for AES-256:

Year Years needed to crack
2050 2.93E50 years
2100 8.72E42 years
2200 7.74E27
2300 6.8 Trillion years
2350 204,942 years
2385 1 year
Table 2: Shows how long an exhaustive search will take to crack AES-256 if we only used the fastest supercomputer of the day(and not upgrade it each year).

In reading Table 2, this means that by the year 2385, AES-256 will become computationally insecure for exhaustive search. Given that Bruce Schneier has recommended that new applications use AES-128, this probably means that a professional cryptographer like Bruce suspects that AES-256 keys can be retrieved faster than an exhaustive search of AES-128.

Under various assumptions, AES-128 will be computationally insecure around the year 2129 against brute force attacks. This is really not a problem today for nearly all applications given the distance we need to cover by the year 2129. The majority of computing power gains needed to break AES will occur only a few years prior to the year of break. To put things in perspective, the fastest supercomputer today has roughly 3x10^-18 of the computing power it will have by the year 2129.

With that said, if some of the assumptions prove to be totally false, the years needed to crack could potentially reduce significantly.

Fair Disclosure:

In fair disclosure, I am not a mathematician or a professional cryptographer. If you find something wrong with my math in this article, please let me know in the comments below! And don't forget to check out the spreadsheet if you want to test out your own assumptions.

Shikhir Singh currently works at BlackBerry where he works as a mobile developer. He has previously worked at Lockheed Martin, and Sun Microsystems. You can follow Shikhir on twitter at @shikhirsingh