|Yogesh Malhotra, PhD
Future of Finance Project (www.FutureOfFinance.org), Global Risk Management Network, LLC,
"Bitcoin price volatility implies huge market risk." - Economist Nouriel Roubini
757 Warren Road, Cornell Business and Technology Park, Ithaca, NY 14852-4892, U.S.A.
- Roubini launches stinging attack on bitcoin, CNBC, March 10, 2014.
December 04, 2013
This research report represents the first known attempt with specific technical focus on cryptographic ‘proof of work’ in the context of virtual crypto-currencies such as Bitcoin. The cryptography, encryption and cryptanalysis technical focus of the report is intentional and related to Bitcoin’s innovative capabilities, vulnerabilities and threats. Money is an interesting construct that continues to occupy the fancy of many ranging from economists to quantum physicists... The future of money becomes "entangled" with future of money laundering when focus is not on privacy and anonymity alone, but also lack of traceability... Situated somewhere along the trajectory between real money and quantum money, virtual crypto-currencies based upon ‘cryptographic proof’ represent a natural stage in the evolution of global finance... The future of money, whatever form it may take – virtual or quantum, will quite likely be "entangled" with the future evolution of ‘cryptographic proof of work.’ The feasibility and large-scale global implementation of Bitcoin as a crypto-currency has earned it admiration as a remarkable conceptual and technical achievement and an elegant solution. Its cryptographic solution enables creation and regulation of issue of crypto-currency, preventing its counterfeiting and double-spending, and securing its global transmission at minimal transaction cost while using little time. Central to all those interesting innovations is the cryptographic ‘proof of work’ supplanting trust in a third-party that is the central focus of the current study.
“The bitcoin protocol provides an elegant solution to the problem of creating a digital currency—i.e., how to regulate its issue, defeat counterfeiting and double-spending, and ensure that it can be conveyed safely—without relying on a single authority... It represents a remarkable conceptual and technical achievement, which may well be used by existing financial institutions (which could issue their own bitcoins) or even by governments themselves.”
-- The Federal Reserve Bank of Chicago, Chicago Fed Letter, December 2013, No. 317
Bitcoin Protocol: Model of ‘Cryptographic Proof’ Based
Global Crypto-Currency & Electronic Payments System
"For the importance of money essentially flows from its being a link between the present and the future."
-- The General Theory of Employment, Interest, and Money, John Maynard Keynes, 1935
"You can know the name of a bird in all the languages of the world, but when you're finished, you'll know absolutely nothing whatever about the bird... So let's look at the bird and see what it's doing -- that's what counts."
Money is an interesting construct that continues to occupy the fancy of many ranging from economists to quantum physicists. Virtual crypto-currencies enabled by global interconnectivity and ‘cryptographic proof of work’ represent a natural stage in the evolution of virtual global financial transactions and exchange. Bitcoin is one such crypto-currency that seems to be a ‘remarkable conceptual and technical achievement’ and ‘an elegant solution’ to creating a digital currency, regulating its issue, countering counterfeiting and double-spending, and ensuring secure transmission without relying on a single authority. Central to the interesting innovation is the cryptographic ‘proof of work’ that supplants trust in any third-party in enabling exchange of value. This research report is the first known attempt to specifically focus on cryptographic ‘proof of work’ in the context of Bitcoin and how it really works in enabling Bitcoin’s innovative capabilities. It also analyzes the mystery shrouding Bitcoin’s origin trying to examine if it is a cryptographic protocol, virtual currency, financial instrument, or something else. Central focus is on Bitcoin’s cryptographic proof based P2P electronic payment system with focus on Bitcoin addresses and public key cryptography, transactions and ECDSA-based digital signatures, time-stamping and organizations of transactions into blocks, and mining of cryptographic proof to create the transaction block chain and enable trust. Some perspective of the multi-billion dollar ‘Bitcoin economy’ is also provided in the context of analysis of Bitcoin mining and cryptographic proof computing power requirements. Potential weaknesses in Bitcoin’s security and encryption protocols and recently highlighted key security vulnerabilities and attacks including lack of perceived user identification anonymity are discussed.
-- "What is Science?" The Physics Teacher, 1969, Richard P. Feynman
Introduction: Virtual Currency: Beginning of the End of Real Money?
The IEEE Spectrum special report Future of Money heralding ‘The Beginning of The End of Cash’ chronicles growing trend of virtual currency transactions. It outlines growing use of centralized and decentralized digital cash such as Bitcoin. Beyond virtual currencies, it discusses how quantum computing developments will enable quantum money, i.e., real money which cannot be counterfeited. The future of money becomes "entangled" with future of money laundering when focus is not on privacy and anonymity alone, but also lack of traceability. For instance, the above report notes that: “Anarchists, drug dealers, prostitutes, politicians, dog walkers, and nannies all have reason to prefer cash. There’s a big, spinning world of under-the-table transactions, and what makes it go round is cash." Based on 20% improperly reported or unreported US income, US Treasury lost half-trillion dollars in 2008 alone. Bitcoin is of particular interest given “it is truly untraceable and therefore, like cash, cannot be recovered if lost or destroyed.” Bitcoin extensions such as Zerocoin by a Johns Hopkins computer scientist are further expected to emulate truly anonymous and untraceable money laundering pools.
Virtual Currency and the Emergence of Bitcoin Crypto-Currency
Bitcoin is called a crypto-currency as it relies on cryptography to generate the ‘currency’ and validate related transactions. The real pursuit of virtual currency began around early-1990s among individuals concerned about privacy, anonymity, and lack of traceability. Among them was a group of Silicon Valley friends who fancied liberating currency from governmental control. Around same time, a computer scientist named Nick Szabo was contemplating ‘bit gold’ as a digital coin given as reward for solving difficult-to-solve problems. His scheme of ‘miners’ of coins dedicating CPU-power to solve system-assigned cryptographic equations seems a likely precursor to later Bitcoin. Like Bitcoin, he also envisaged solving problems as cryptographic proof-of-work (PoW) that is approved by the network and becomes part of the next system-assigned challenge. 10-15 years later, the Bitcoin paper by unknown “Satoshi Nakamoto” contemplated creating similar ‘chain of data’ as a record of block chain of transactions.
Bitcoins: Virtual Currency, Financial Instrument, or ‘Something Else’?
US Senate Committee on Homeland Security and Governmental Affairs recently conducted a live hearing on virtual currencies with primary focus being on Bitcoin. In online archive of testimony statements is the original Bitcoin paper which is at the crux of the whole affair. Presented as the central piece of the testimony hearings, interestingly, it is authored by someone who evidently doesn’t even exist. First appearing online in November 2008 it was followed by the Bitcoin network in April 2009. Debate is on among worldwide governments about how to regulate Bitcoin: as currency or financial instrument as it defies most such comparisons given its notorious uses as well as price-volume behaviors. Germany recognized it as a ‘financial instrument’ unlike e-money or foreign currency. US Department of Homeland Security earlier closed US bank accounts of Mt. Gox, the world’s largest bitcoin exchange until a month ago. In US Senate hearing testimony, Fed Chairman Ben Bernanke observed that such virtual currency exchanges and related bank transactions must comply with Bank Secrecy Act (BSA) and Anti-Money Laundering (AML) requirements. He also reinforced Fed’s role in enforcement of section 311 of US Patriot Act against Bitcoin exchanges such as Liberty Reserve S.A. which pleaded guilty in a $6 billion money-laundering case.
Having earlier outlawed virtual currencies, China recently allowed popular participation in Bitcoin market while emphasizing that it does not recognize Bitcoin. With China now accounting for 62% of the global market volumes in Bitcoin, its move is attributed to the BTC price crossing the $1,000 mark for the first time and BTCChina is now the world’s largest Bitcoin exchange. Related concern is that Bitcoin can threaten US dollar’s status as world’s reserve currency with yuan-Bitcoin exchange rate now becoming a leading indicator of the dollar-Bitcoin rate. With $8 billion worth of US residential real estate purchased over last year, wealthy Chinese share of foreign US residential real estate has jumped 50%. Chinese now own between $450 billion to $700 billion in offshore assets, with most wealth transferred illegally such as by using BTC as legally each of them can’t transfer more than $50,000. Rising 7,600% over the year and on track to being world’s first trillion dollar non-fiat ‘currency’, BTC rose to $1,175.79 on Nov. 28, 2013, as shown in Figure 1. In response, most of Canada’s Big-6 banks froze or shut down the accounts of exchanges that convert BTC to cash for customers.
Figure1. Astronomical Rise of the BTC, data source: bitcoincharts.com
The pseudonymous Satoshi Nakamoto is characterized as the ‘inventor’ of Bitcoin. Various firms (Samsung, Toshiba, Nakamichi & Motorola as in SaToshi NakaMoto), and institutions such as the NSA (Nakamoto, SAtoshi) are identified among entities that may have ‘invented’ Bitcoin using the pseudonym. Some note similarity of pseudonym with Tatsuaki Okamoto, cited among references in the 1996 paper How to Make a Mint: The Cryptography of Anonymous Electronic Cash authored by National Security Agency’s Office of Information Security Research and Technology Cryptology Division. Twelve years before the Bitcoin paper, the NSA paper, based upon its review of electronic cash schemes, made notable observations. It noted that cryptography underlying those schemes seemed fine and delivered promised anonymity. It also observed however that those schemes seemed not as satisfactory from a law enforcement point of view: “In particular, the dangers of money laundering and counterfeiting are potentially far more serious than with paper cash. These problems exist in any electronic payment system, but they are made much worse by the presence of anonymity. Indeed, the widespread use of electronic cash would increase the vulnerability of the national financial system to Information Warfare attacks.”
Besides world’s largest multi-billion dollar money-laundering case, Bitcoin has been linked with multiple other criminal activities such as child pornography, bank hacking, and sale of prohibited drugs. On the day of US Senate Hearing, Forbes published about the online service Assassination Market for crowdfunding political assassinations of any government official by collecting anonymous BTC contributions. On other hand, Bitcoin cryptographic P2P digital system enables near instantaneous global payment transfers for minimal transaction fees making it appealing to consumers, speculators, and cybercriminals. Bitcoin identifies individual users by “addresses” that are ‘plausibly deniable’, i.e., a merchant receiving BTCs as payments may not deliver on promised services and yet the payments are not reversible. Extensions of Bitcoin such as Zerocoin are further expected to enable truly untraceable money laundering pools.
Some reports note the first creation of BTC on January 3, 2009 as ‘all bit and no coin’ based upon ‘thirty-one thousand lines of code and an announcement on the Internet’. Over two years, the mysterious pseudonymous inventor is said to have written hundreds of posts in flawless English inviting other developers to improve the code. In April, 2011 he is said to have been heard from last when he sent a note to one of them that he has moved on. First Bitcoin to U.S. dollar exchange transaction in history, 5,000 BTC for $5 on PayPal, is self-attributed by Finnish developer Martti Malmi. BTC at less than a penny initially rose above $29 by June 2011 falling to $5 by September 2011. It crossed $100 between April and May 2013 and $200 around October 21, 2013. In the week before the US Senate Hearing, it crossed $400 and shot past $900 on the day of Hearing before diving back to around $500. Based on a report that estimated Nakamoto’s million BTC holding at $100 million in first week of May, 2013, he may have cashed out as a billionaire on the day of Senate Hearing. Analysts are bewildered as the price volume action begs answers to questions such as: What other ‘currency’ or ‘financial instrument’, if any, demonstrates such price-volume behavior? What are the fundamentals, if any at all, that provide any realistic assessment of the true valuation of a BTC?
Bitcoin: A ‘Cryptographic Proof’ Based P2P Electronic Payment System
Bitcoin, a cryptographically secure decentralized peer-to-peer (P2P) electronic payment system enables transactions involving virtual currency in the form of digital tokens. Such digital tokens, Bitcoin coins (BTCs), are a type of crypto-currency whose implementation relies on cryptography to generate the tokens as well as validate related transactions. Bitcoin solves counterfeiting and double-spending problems without any centralized authority. It replaces trust in a third-party such as a bank with a cryptographic proof using a public digital ledger accessible to all network nodes in which all BTC balances and transactions are announced, agreed upon, and recorded. Transactions are time-stamped by hashing them into an ongoing chain of hash-based PoW forming a record that can’t be changed without redoing that chain. Anonymity is maintained through public-key cryptography by using P2P addresses without revealing user identity.
Bitcoin Addresses & Public Key Cryptography
Bitcoin coin (BTC) is essentially a hashed chain of digital signatures based upon asymmetric or public key cryptography. Each participating Bitcoin address in the P2P network is associated with a matching public key and private key wherein a message signed by private key can be verified by others using the matching public key. A Bitcoin address corresponds to the public key which is a string of 27-34 alphanumeric characters such as:
and occupies about 500 bytes. Users are encouraged to create a new address for every transaction to increase privacy for both sender and receiver. While this creates anonymity for both sender and receiver, however, given irreversibility of transactions, nonrepudiation may be compromised. Addresses can be created using Bitcoin clients or ‘wallets’. The sender uses his or her private key to assign payments to receiver’s public key oraddress. Characters within the address also serve as checksum to validate any typographical errors in typing the address. The private key is the secret key which is necessary to access BTCs assigned to the corresponding public key address. Private keys start with first character 1 or 3: 1 implies use of one key while 3 denotes multiple private keys for ‘unlocking’ a payment. Bitcoin addresses and associated private keys are stored in encrypted wallet data files typically backed up offline for security. If a wallet or a private key is lost, related BTCs are lost forever.
Bitcoin Transactions & Digital Signatures Based on ECDSA
Bitcoin’s operation is based upon elliptic curve cryptography: addresses are derived from elliptic-curve public keys and transactions authenticated using digital signatures. Elliptic Curve Digital Signature Algorithm or ECDSA is the cryptographic algorithm used by Bitcoin to ensure that funds are spent by rightful owners. The private key, a single unsigned 256 bit integer of 32 bytes, is essentially a randomly generated ‘secret’ number supposedly known only to the person that generated it. The range of valid private keys is governed by the secp256k1 ECDSA standard used by Bitcoin. The public key corresponds to a private key, but does not need to be kept secret.
Figure2. How Bitcoin Addresses Transfer Payments and Verify Signatures
A public key can be computed from a private key, but it is presumably computationally infeasible to do vice-versa. A public key can be used to authenticate or confirm the validity of the digital signature. As shown in Figure 2 above, address N transfers the payment to address M by digitally signing using its private key the mathematically generated hash H of prior transaction TN and public key of address M. Also, as shown, the digital signature of address N can be verified by using N’s public key without knowing its private key. The Bitcoin block chain contains all such transactions ever executed wherein each block contains the SHA-256 hash of the previous block.
The elliptic curve over a finite field Fp, with most popular choice being prime fields GF(p) where all arithmetic is performed modulo a prime p, is set of all pairs (x, y) ∈ Fp which fulfill E:
y2 ≡x3 + a.x + b mod p
together with an imaginary point of infinity O , where p > 3 is prime, and a, b ∈Fp. The cryptographic signatures used in Bitcoin are ECDSA signatures and use the curve secp256k1 defined over Fp where p = 2256– 232– 977 which has a 256-bit prime order. This choice deviates from NIST recommended FIPS 186-4 standard in that the curve coefficients are different from the NIST recommended standard to speed up scalar multiplication as well as Pollard’s rho algorithm for computing discrete logarithms.
Given ECDSA public-key K, Bitcoin address is generated using the cryptographic hash functions SHA-256 and RIPEMD-160:
HASH160 = RIPEMD-160(SHA-256(K)).
Bitcoin address is computed directly from the HASH160 value as illustrated below in Figure 3, where base58 is a binary-to-text encoding scheme:
Figure3. How Bitcoin Address is Computed Using ECDSA Algorithm
In summary, the electronic coin, BTC, a chain of ECDSA enabled hashed digital signatures, is transferred by the sender (payer) who appends to it a digitally signed hash of previous transaction and the public key of the receiver (payee). The receiver relies upon signatures to verify the chain of ownership and on P2P majority consensus about the single history of order in which publicly announced transactions are received.
However, Bitcoin ECDSA signatures may be susceptible to the following potential encryption related vulnerabilities and threats: (i) insufficient or poor randomness when the same public key is used for multiple Bitcoin transactions or the same key pair is used to protect different servers owned by the same entity; (ii) an invalid-curve attack in which an attacker obtains multiples with secret scalars of a point on the quadratic twist, e.g. via fault injection if the point doesn’t satisfy the correct curve equation (iii) implementation issues such as side-channel attacks, software bugs, design or implementation flaws; (iv) hardness assumptions about number theoretic problems such as integer factorization and discrete logarithms computation in finite fields or in groups of points on an elliptic curve not applying as assumed in specific contexts. Recent recommendations by RSA, about withholding use of Dual Elliptic Curve Deterministic Random Bit Generation (or Dual EC DRBG) and the influence of DRBG compromise on consuming applications such as DSA may also deserve attention.
Organizing Transactions into Blocks and Time Stamping Them
A BTC transaction is a signed section of data broadcast to the network and collected into blocks. It typically references prior transaction(s) and assigns specific number of bitcoins from it to one or more Bitcoin addresses. Transactions are recorded in the network in form of files called blocks. Structures of the blockheader and block are shown below.
Figure4. Structure of a Bitcoin Transaction Block
Figure5. Structure of a Bitcoin Transaction Blockheader
As seen in Figures 4 and 5, a block contains most recent transactions sent to the network not yet recorded in prior blocks. Each block includes in its block header a record of some or all recent transactions and a reference to the prior block. It also contains the ‘answer’ to a difficult-to-solve mathematical problem related to the verification of transactions for the block. This problem relates to finding factors of a very large integer: difficult to solve but thereafter easy to verify by other nodes once factors are found.
The chain of ownership is created by using a timestamp server that creates and widely publishes hash of a block of items to be time-stamped with each timestamp including previous timestamps in its hash value. To prevent double-spending, i.e., ensuring that the BTC payer didn’t sign an earlier transaction for same BTC or already spent the BTC, a timestamp server is used to maintain a single chronological history in which each transaction was received. This process ensures that at the time of the transaction, the payee knows that majority of nodes agree to having received the current transaction as the first received. Subsequent transactions for the same BTC don’t need to be recorded as they are rejected in the verification process. As the only way to confirm absence of a transaction is to maintain a record of all transactions, as seen in Figure 6, each timestamp includes the previous timestamp in its hash starting from first transaction.
Figure6. Each Timestamp Includes Previous Timestamp in its Hash Forming a Chain
The block chain makes double-spending very difficult as each block is preceded by prior block in chronological order as well as is based upon its hash value. To prevent double-spending, i.e., spending of the same BTC twice, public keys and signatures are published as part of publicly available and auditable block chain. To make it infeasible to falsify the block-chain, PoW is used to make addition of each block very costly.
Mining Cryptographic Proof of Work to Create Transaction Block Chain
Transactions are bundled into blocks by network nodes functioning as miners. Mining is the process of attempting to generate validation hashes, i.e., competing to be the first to find and broadcast the correct hash based upon large integer factorization that ‘solves’ the current block. A block chain is a transaction database shared by all nodes in the network and contains every executed transaction. Every block in the chain contains a hash of previous block thus creating a block chain from the first block to the current block. A block chain may be searched or navigated by using a block chain browser.
BTCs acquire perceived value based upon PoW in terms of computational power invested for solving the cryptographic challenge of prime factorization of large numbers related to verification of BTC transactions. BitCoin uses SHA-256 hash algorithm to produce verifiably large random numbers requiring predictable amount of CPU power to factorize. Generating a SHA-256 hash with value less than the current target, a 256-bit large number that all Bitcoin clients share, solves a block which ‘mines’ new coins that the responsible miner receives as incentive for solving the problem.
The P2P distributed timestamp server is implemented using PoW by incrementing a nonce in the block until its hash results in required zero bits beginning the hash. As depicted in Figure 7, to create different cryptographic hash values from the same input string, mining computers calculate cryptographic hash values based on combination of hash value of all prior Bitcoin transactions, the new transaction block, and a nonce.
Figure7. Mining Cryptographic Proof of Work to Create Transaction Block Chain
The nonce in a bitcoin block is a 32-bit (4-byte) field, its value is set so that the hash of the block will contain a run of zeros. According to NIST SP800-90A, nonce is a time-varying value that has at most a negligible chance of repeating, for example, a random value that is generated anew for each use, a timestamp, a sequence number, or some combination of these. (DRBG uses a DRBG mechanism and a source of entropy input, and may, depending on implementation of DRBG mechanism, include a nonce source.)
Any change to block data such as changing nonce results in totally different new block hash value. It is infeasible to predict which initial data set will create the right hash with the required number of leading zeros. Hence, miners need to generate many hashes with different nonces until they can find one that works. Iterative computation requires time and resources; hence presentation of the block with correct nonce value constitutes the PoW. Double-spending same BTC would require not only re-computing and replacing the transaction where it was spent but also all subsequent blocks in the chain. This characteristic underlies the use of the longest block chain as the most reliable and trusted PoW by all nodes as well as apparent infeasibility of re-computing the same block chain to falsify it such as in order to reverse a transaction. Hence the longest block chain verified and included in most recent hashed output of the public ledger accessible to all P2P nodes serves both as the purveyor of ‘cryptographic trust’ as well as the deterrent of reversibility of transactions.
SHA-256, a member of the SHA-2 algorithms designed by the NSA and extensively used in Bitcoin protocols, is based on the following cryptographic hash function, majority function, and circular (modular) rotations and shifts.
SHA 256 is known to be potentially vulnerable to collisions besides pre-image attacks, non-linear reduced round attacks, and higher-order differential attacks. Similarly, RIPEMD-160 is potentially susceptible to differential attacks, pre-image attacks and collision attacks. As SHA-2 shares same structure and mathematical operations as already “broken” SHA-1 and MD5, this is a cause for concern. To replace SHA-2 in case of a cryptanalysis attack that weakens it, SHA-3 is the new cryptographic hash algorithm selected by NIST. SHA-3 has fundamentally different structures and uses quite different mathematical operations as compared with SHA-2. Additional concerns relate to current publicly known classical computers capable of 54.9-petaflops and quantumcomputers in use for heavy-duty benchmarking by Google, NASA and others which may have additional implications about potential vulnerabilities.
Summary: How Bitcoin P2P Electronic Payment System Works
The Bitcoin P2P network protocol thus works in an approximately step-by-step fashion as envisioned by its original pseudonymous inventor in the historic proposal.
- New transactions are broadcast to all nodes.
- Transactions into a block by each node...
- …Which then works on finding a difficult proof-of-work for its block.
- When a proof-of-work is found, the node broadcasts the block to all other nodes.
- Nodes accept the block and its transactions only if valid and not double spent.
- Nodes accept the block by starting creating next block in the chain while using hash of accepted block as previous hash.
Mining & Cryptographic Proof Computing Power Requirements
After about every 10 minutes, miners bundle payment transactions into blocks which are subsequently included in the shared ledger i.e. longest block chain of balances and transactions. In the Bitcoin protocol, new BTCs are generated as incentives to reward miners for verifying transactions and creating cryptographic proof that replaces trust in a third party such as a bank in case of real cash exchange. Prior discussion on the ‘Proof of Work’ and hashed block chains focused on the technical details of the cryptography and security encryption protocols. Related computational resource requirements and the actual process of increasingly specialized mining given exponentially growing difficulty and exponentially decreasing [potential] of reward seem equally interesting.
The computationally challenging problem that miners solve is focused on factorization of large primes and is associated with verification of transactions discussed above. Assuming new transaction block NB is to be added to existing block chain BC, then miners need to find nonce N which will result in the hash F(BC, NB, N) that starts with the required number of zeros as well as is smaller than the current target T specified by the system at that time. As well recognized in cryptanalysis research about prime factorization of large numbers, while finding such factors is computationally complex, verifying their product is not difficult. Also, lower the value of T, the more computationally challenging is the factorization problem. Rate of increase in the computational complexity grows exponentially so that mining of new coins decreases exponentially getting halved in every subsequent year so that there will be only a total of 21 million BTCs by 2040. Given exponentially increasing complexity, miners have already advanced beyond specialized hardware such as specialized Bitcoin mining ASICs clocking billions of hashes per second to pooled resources such as botnets.
Exponential computational difficulty can be checked using a Bitcoin mining profitability calculator which lists current difficulty level at: 707,408,283 and current incentive at 25 BTC per block. Difficulty is defined here as a measure of how difficult it is to find a new block compared to the easiest it can ever be. It is adjusted every 2016 blocks based on the time it took to find previous 2016 blocks. At the desired rate of one block each 10 minutes, 2016 blocks would take exactly two weeks to find regardless of the exploding number of participants in the P2P network that make the ‘game’ even more challenging. Even after doing all the hard work, there is no guarantee that you have made any progress: “There's no such thing as progressing 1% towards the solution as at every point, the probability is same. After working on it for 24 hours, your chances of solving it are equal to what your chances were at the start or at any moment. Believing otherwise is what's known as the gambler's fallacy.” For those venturesome to go solo BTC mining with an average desktop, a rough estimate of ‘Net Profit of -1464.60 USD’ is available at the time of writing from blockchained.com as shown in Figure 8.
Figure8. BTC Mining Has Become a Deep Pocketed 'Pooled Player' Game
As mentioned, mining has advanced way beyond CPUs (central processing units) to GPUs (graphics processing units) to more flexible FPGAs (field-programmable gate arrays) to bespoke ASICs (application-specific integrated circuits). Mining groups now pool processing power using server farms with arrays of racks of ASIC cards dedicated to mining. For any new block created by hashing old transaction block, the first transaction originally created 50 BTC reward for the block creator. Algorithmically, the reward is set at 50 BTC from 2009 to 2012, 25 BTC from 2012 until late 2016, and so forth so that there will never be more than 21 million BTCs. Once BTC mining is exhausted, transaction fees paid to miners are expected to constitute the difference between a [higher] input and [smaller] output of BTCs. With latest specialized hardware, mining has reached a point where only those with access to free or cheap electric power can afford to continue and even they will produce a relatively marginal return on investment.
Increasing computational complexity of mining is also evident in the following charts for network hashing (Figure 9) and Bitcoin daily growth (Figure 10) rates from http://bitcoin.sipa.be/. More nodes, or specifically, more CPU power, involved in mining makes it all the more harder to generate SHA-256 hashes which need to be generated by brute force of computing power.
Figure9(a). Exponentially Growing Bitcoin Total Network Hashing Rate
Figure9(b). Exponentially Growing Bitcoin Total Computation Speed
Figure10. Bitcoin Daily Growth Rate
With many online websites and services dedicated to tracking BTC markets and transactions, a quick snapshot of the ‘BTC Economy’ from one such site bitcoinwatch.com is shown in Figure 11. Some interesting numbers from those statistics include: current total 12,061,150 BTCs with market cap 12,248,339,048 USD, 8.29 blocks generated per hour, and network hashrate of 66840.80 PetaFLOPS. Also, it is clear that BTCChina is the predominant BTC exchange leader after overtaking lead from Mt. Gox.
Figure11. The 'Bitcoin Economy' Overview Snapshot
Cryptographic Proof as Substitute for Trust in Third Party
When a miner finds a suitable block hash, he couples it with a nonce and broadcasts it to the network. Resulting hash is combined with previous completed block hash along with the BTCs being exchanged thus forming the block chain. The block chain represents the ‘trust’ of each transaction because each new transaction block is generated based on the unique hash of the previous block of all prior transactions. The entire history of every transaction can be traced back through the longest chain that is ‘trusted’ by all P2P nodes which keep extending it further. Because the network trusts the longest continuous block chain and a suitable SHA-256 hash may take 10 minutes or so to generate, an attack would require more computational power than all honest nodes combined. To pre-empt such possibility, a block is not considered final until it is 6 links deep which may take up to an hour. The distributed timestamp server generates proof of chronological order of transactions and the system is supposed to be secure unless a group of attacker nodes can collectively control more CPU power than honest nodes.
Known and Potential Attacks and Vulnerabilities of Bitcoin
Pros and cons of Bitcoin as well as potential weaknesses in its security and encryption protocols were discussed above; other potential vulnerabilities are summarized below. Most probably, the pseudonymous Bitcoin inventor didn’t envision today’s global BTC mining computational arms-race with armies of botnets using global captive computers, software vendors using malware to steal customers’ CPU power for mining BTCs, or clearly illegal service using ransom-ware forcing law enforcement officers into making BTC payments via their openly public customer service Web site.
Bitcoin is known for its [pseudo-]anonymity of user identification as it uses randomly generated public keys for Bitcoin addresses; however, it is not truly anonymous. As noted in the US Senate Hearing testimony of the Criminal Division: “Criminals are drawn to services that allow users to conduct financial transactions while remaining largely anonymous… [However,] To be clear, virtual currency is not necessarily synonymous with anonymity.” Public key addresses are self-identified by users for receiving payments or when they need to convert BTCs to other currencies including real money when user identity is linked with related public key address. Furthermore, different public keys that are input in a specific transaction or a sequence of transactions can be related to the specific users and the private keys used for sending payments need to be known to the transmitting exchanges. Also, change addresses used for returning residual ‘change’ from Bitcoin transactions can be linked to respective input addresses as well as input users. Private transactions between parties of same exchange are privy to the exchange which may be able to bypass such identification by not using the strict Bitcoin protocol of transparency of each transaction. The ‘default’ Bitcoin protocol doesn’t provide true anonymity which may require protection from both forward attacks and reverse attacks. Forward attacks involve getting something that identifies a user using coins received with methods that should remain secret. Reverse attacks involve getting something that should remain secret by using coins that can identify a user.
Several additional ‘weaknesses’ representing vulnerability of Bitcoin coins and transactions are identified next. Wallet files are vulnerable to theft and need to be encrypted and backed off-line. Old backup wallet files and contents can be retrieved with existing backup facilities. Coin’s history can be traced to link user identities to the pseudo-anonymous addresses. Unlike Bitcoin addresses, if a payment is sent to IP address, man-in-the-middle attack is feasible given IP addresses can be spoofed. Unless node-to-node encryption is used, packet sniffing can reveal the sent transactions. Distributed denial of service (DDoS) attacks pose potential threats just like with any other networked cryptographic service. However, deep-pocketed DDoS attacks using ‘remarkable 100 G/bits per second in bandwidth’ and million-dollar hacking heists are becoming increasingly common. Timejacking attacks can be done by announcing inaccurate timestamps when connecting to a node where an attacker can deceive it into accepting an alternate block chain by altering the node's network time counter. Results may range between increased chances of double-spending, drained computational resources, and slower transaction rates. Potential causes for concern for miners also include: more efficient mining gear only raises the network ‘difficulty’ without reducing energy use and cheaper energy linearly increases mining energy use. Similar concerns apply to other cryptographic proof of work currencies such as Litecoin as well.
Besides vulnerabilities of encryption protocols to available quantum computers, classical computers capable of 54.9-petaflops may pose major ‘>50%’ threat to Bitcoin. The specific attack results from anyone in the network acquiring more than 50% computing power being able to exclude, modify, and self-reverse transactions and prevent some or all ‘mining’ of valid blocks. Even with less than 50% power such attacks are feasible: e.g. someone with 40% of network computing power can overcome a 6-deep confirmed transaction with a 50% success rate. Nevertheless, it is exponentially difficult to change historical blocks going back in time and it isn’t possible to change blocks created before the last checkpoint. Even though a profit-seeking attacker potentially may gain from following the protocol or launching other attacks, however, “if the above attack is successfully executed, it will be difficult or impossible to "untangle" the mess created -- any changes the attacker makes might become permanent.” Given individual mining pools have controlled 25% to 33% of mining power, a Cornell study, argues that >50% attack is feasible even though developers seem not as concerned.
Double spending attacks to which the Bitcoin protocol is vulnerable include Race attack, Finney attack, Vector76 attack, Brute force attack, and >50% attack. The research study Two Bitcoins at the Price of One found that the Bitcoin protocol is highly susceptible to Race attacks. Such attacks involve successfully sending one transaction to a merchant while sending different transaction spending same coins that were first sent to eventually make it into the block chain. The Finney attack is another fraudulent attack requiring the miner’s participation once a block has been mined with a conflicting transaction not yet announced to the network. While a miner verifying the block that contains money sent by someone to oneself, the sender may find the block and send the money to someone else. The sender receives his money while the legitimate transaction is rejected as the same money can’t be double spent. Vector76 attack is a combination of the above two attacks such that a transaction that even has one confirmation can still be double-spent. In a Brute force attack, the attacker submits to the merchant or network a transaction which pays the merchant, while privately mining a blockchain fork in which a double-spending transaction is included instead. In >50% attack discussed earlier, the attacker simply perseveres with private fork generating blocks faster than the rest of the network until he controls the longest branch superseding those of the honest network.
Future of Bitcoin and Other Crypto-Currencies
In his letter of September 06, 2013, the Chairman of the US Federal Reserve, quoting a 1995 US House of Representatives hearing, noted that: “while [virtual currency] innovations may pose risks related to law enforcement and supervisory matters, there are also areas in which they may hold long-term promise, particularly if the innovations promote a faster, more secure and more efficient payment system.” In many ways, despite their notorious widespread use in illegal activities the current popular appeal of crypto-currencies such as Bitcoin seems to stem from the innovations that the Fed Chairman and the Chicago Fed mentioned in their respective documents. In his letter, the Fed Chairman underscored the need for regulatory compliance on part of public and private players in electronic cash and related banking and finance industries. On the other hand, there is the search for true anonymity and privacy on part of some academics and practitioners besides users of such crypto-currencies as discussed. The future of cryptography, cryptanalysis, and crypto-currencies is anticipated to evolve based upon reconciliation of expectations, needs, and wants of diverse stakeholders.
A snapshot of the current contenders for that future of crypto-currencies is displayed in this concluding discussion. Currently, there are 30 to 40 virtual currencies listed. Figure 12 lists a comparison of top-30 showing 20-fold lead of Bitcoin over Litecoin.
Figure12. How the Current Crop of Virtual Currencies Stack Up
Such virtual currencies are also known as alt-coins for alternative crypto-currencies. alt-coins based upon SHA-256, the hashing algorithm for Bitcoin, include NMC: Namecoin, PPC: PPCoin (Peercoin), DVC: Devcoin, TRC: Terracoin, BTE: Bytecoin, IXC: Ixcoin, I0C: I0coin, FRC: Freicoin, and BLC: Blakecoin. In contrast, alt-coins such as Litecoin using scrypt, a password-based key derivation function that cannot be mined using ASICs, include besides LTC: Litecoin, NVC: Novacoin, FTC: FeatherCoin, MNC: MinCoin, BBQ: BBQcoin, TAG: Tagcoin, MEG: Memorycoin, and BTCs/BTC2: Bitcoin Scrypt. Like Bitcoins, most of these virtual currencies are mined similarly by using cryptographic proof of work concepts. Given central role in making the crypto-currencies possible, ‘cryptographic proof of work’ is anticipated to have a longer shelf-life than any of the above currencies. The future of money, whatever form it may take – virtual or quantum, will quite likely be "entangled" with the future evolution of ‘cryptographic proof of work.’ Hence, the focus of this report has been on most central concept underlying the current trajectory of e-evolution of money and global payments.
This research report represents the first known attempt with specific technical focus on cryptographic ‘proof of work’ in the context of virtual crypto-currencies such as Bitcoin. The cryptography, encryption and cryptanalysis technical focus of the report is intentional and related to Bitcoin’s innovative capabilities, vulnerabilities and threats. Situated somewhere along the trajectory between real money and quantum money, virtual crypto-currencies based upon ‘cryptographic proof’ represent a natural stage in the evolution of global finance. The feasibility and large-scale global implementation of Bitcoin as a crypto-currency has earned it admiration as a remarkable conceptual and technical achievement and an elegant solution. Its cryptographic solution enables creation and regulation of issue of crypto-currency, preventing its counterfeiting and double-spending, and securing its global transmission at minimal transaction cost while using little time. Central to all those interesting innovations is the cryptographic ‘proof of work’ supplanting trust in a third-party that is the central focus of the current study.
- Ben S. Bernanke. Letter to the U.S. Senate Committee on Homeland Security & Governmental Affairs. Board of Governors of the Federal Reserve System. September 6, 2013.
- Joppe W. Bos, J. Alex Halderman, Nadia Heninger, Jonathan Moore, Michael Naehrig, and Eric Wustrow. Elliptic Curve Cryptography in Practice. Microsoft Research. November 2013.
- H. Dobbertin, A. Bosselaers, and B. Preneel, 'RIPEMD-160, A Strengthened Version of RIPEMD, Fast Software Encryption, LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, pp. 71-82.
- Economist. Technology Quarterly. Bitcoin under pressure. Q4 2013. Nov 30th 2013.
- Ittay Eyal and Emin Gun Sirer. Majority is not Enough: Bitcoin Mining is Vulnerable. Computer Science > Cryptography and Security, Cornell University Library. November 15, 2013.
- Federal Financial Institutions Examination Council. Bank Secrecy Act / Anti-Money Laundering Examination Manual. 2010.
- Timothy A Hall. The FIPS 186-3 Digital Signature Algorithm Validation System (DSA2VS). National Institute of Standards and Technology. Updated: September 5, 2013.
- Danny Yuxing Huang, Hitesh Dharmdasani, Sarah Meiklejohn, Kirill Levchenko, Alex C. Snoeren, Stefan Savage, Nicholas Weaver, Chris Grier, and Damon McCoy. Poster: Botcoin - Bitcoin-Mining by Botnets. IEEE Security. Spring 2013.
- Nicola Jones. Google and NASA Snap Up Quantum Computer D-Wave Two. Scientific American. May 17, 2013.
- Ghassan O. Karame, Elli Androulaki and Srdjan Capkun. Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin. IACR Cryptology ePrint Archive. 2012.
- Laurie Law, Susan Sabett, and Jerry Solinas. How To Make A Mint: The Cryptography Of Anonymous Electronic Cash. National Security Agency Office of Information Security Research and Technology, Cryptology Division. National Security Agency. 18 June 1996.
- Yogesh Malhotra. Quantum Computing, Quantum Cryptography, Shannon's Entropy and Next Generation Encryption & Decryption. Global Risk Management Network, LLC, 2013.
- Yogesh Malhotra. Cryptology Beyond Shannon's Information Theory: Preparing for When the 'Enemy Knows the System'. Global Risk Management Network, LLC, 2013.
- Yogesh Malhotra. Number Field Sieve Cryptanalysis Algorithms for Most Efficient Prime Factorization on Composites. Global Risk Management Network, LLC, 2013.
- Sarah Meiklejohn, Marjori Pomarole, Grant Jordan, Kirill Levchenko, Damon McCoy, Geoffrey M. Voelker, and Stefan Savage. A Fistful of Bitcoins: Characterizing Payments Among Men with No Names, Proceedings of the ACM Internet Measurement Conference, Barcelona, Spain, October 2013.
- Florian Mendel, Tomislav Nad, Stefan Scherz, and Martin Schläffer. Differential Attacks on Reduced RIPEMD-160, Lecture Notes in Computer Science Volume 7483, 2012, pp. 23-39.
- Florian Mendel, Thomas Peyrin, Martin Schläffer, Lei Wang, and Shuang Wu. Improved Cryptanalysis of Reduced RIPEMD-160, Lecture Notes in Computer Science Volume 8270, 2013, pp 484-503.
- Satoshi Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. November, 2008.
- Peter W. Shor, Edward Farhi, David Gosset, Avinatan Hassidim, and Andrew Lutomirski. Quantum Money. MIT. January 19, 2012.
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. January 31, 2011.
- NIST. FIPS Pub 180-4: Federal Information Processing Standards Publication Secure Hash Standard (SHS). Information Technology Laboratory, National Institute of Standards and Technology. March 2012.
- NIST. NIST Special Publication 800-90A: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. January 2012.
- NIST. Supplemental ITL Bulletin For September 2013: NIST Opens Draft Special Publication 800-90A, Recommendation For Random Number Generation Using Deterministic Random Bit Generators, For Review And Comment. September 2013.
- B. Preneel, A. Bosselaers, and H. Dobbertin. The cryptographic hash function RIPEMD-160. CryptoBytes, Vol. 3, No. 2, 1997, pp. 9-14.
- Somitra K. Sanadhya and Palash Sarkar. Non-linear Reduced Round Attacks against SHA-2 Hash Family. ACISP '08 Proceedings of the 13th Australasian conference on Information Security and Privacy, 2008, pp. 254 - 266.
- Yu Sasaki, Lei Wang, and Kazumaro Aoki. Preimage Attacks on 41-Step SHA-256 and 46-Step SHA-512. IACR Cryptology ePrint Archive. 2009.
- William Stallings. Inside SHA-3. IEEE Potentials, November/December 2013, pp. 26-31.
- U.S. Senate Committee on Homeland Security & Governmental Affairs. Beyond Silk Road: Potential Risks, Threats, and Promises of Virtual Currencies. November 18, 2013.
- http://Bitcoinexaminer.org/who-is-satoshi-nakamoto/, http://Bitcointalk.org/index.php?topic=235342.0.
- CPU: central processing unit, GPU: graphics processing unit, FPGA: field-programmable gate array, ASIC: application-specific integrated circuit