编程辅导 SHA-256 hash of the block’s header be less than (65535 << 208)/dif f iculty

Bitcoin and The Age of Bespoke Silicon
of California, San Diego
Recently, the Bitcoin cryptocurrency has been an interna- tional sensation. This paper tells the story of Bitcoin hard- ware: how a group of early-adopters self-organized and fi- nanced the creation of an entire new industry, leading to the development of machines, including ASICs, that had or- ders of magnitude better performance than what Dell, Intel, NVidia, AMD or Xilinx could provide.
We examine this story for clues as to how we can foster greater innovation in the semiconductor industry and enable this phenomenon to occur more broadly for more application areas, spawning a new age of hardware innovation tailored to emerging application domains—an Age of Bespoke Silicon.

Copyright By PowCoder代写 加微信 powcoder

Categories and Subject Descriptors B.7.1 [Integrated Cir- cuits]: Types and Design Styles
General Terms Design, Performance, Economics Keywords Dark Silicon, Bitcoin, Specialization
1. INTRODUCTION
Bitcoin, since its Jan 2009 deployment, has experienced ex- plosive, exponential growth. As of the writing of this paper, there are 11.5 million Bitcoins (BTC, or B) in circulation, and the USD/BTC exchange rate is $104, which means that the market capitalization of Bitcoin is just shy of $1.2 billion USD. Notably the Winklevoss twins, of The Social Network fame, have purchased $11 million worth of BTC, and have submitted a proposal to the SEC to create an Exchange- Traded Fund (ETF) to allow broader access to investors.
With such rapid growth, Bitcoin is the most successful dig- ital currency, exceeding the next most successful open digi- tal currency, Litecoin, by an order of magnitude. Underpin- ning Bitcoin’s success is a series of technological innovations, spanning from algorithms, to distributed software, and also into hardware. Amazingly, none of this success has been un- derwritten by a corporate or government entity, but rather emerged through a grass-roots collaboration of enthusiasts.
In this paper, we will introduce the algorithms and soft- ware that underpin the Bitcoin system, discuss the turbulent history of Bitcoin so far, and then delve into the fascinat- ing hardware ecosystem that has emerged—from GPUs, to custom FPGA systems to custom ASICs.
The latest round of hardware—dedicated ASICs—have been financed, developed, and deployed by Bitcoin users, which is perhaps an unprecedented event in recent history. One ques- tion is whether this model can scale to other application areas
To appear in the International Conference on Compilers, Ar- chitecture and Synthesis for Embedded Systems (CASES), September 2013.
and usher in a new era of bespoke silicon—that is, customized silicon that has been developed in small volumes—that lever- ages specialization to outperform high-volume general-purpose SoCs built by major billion-dollar companies.
2. THE BITCOIN CRYPTOCURRENCY
We overview the bitcoin system below: how it is used, pricing and difficulty trends, and how it is mined.
2.1 How Bitcoin Works: User Perspective
The first step is to create a Bitcoin account. Bitcoin ad- dresses can be created locally on your computer using open- source software, free of charge. The software outputs both a public key and a private key. No interaction with the outside world is necessary. The private key must be kept secret in order to protect the account, and is needed whenever you plan on sending money from the account. If the private key is lost, then the funds are also irrevocably lost. The public key, on the other hand, may be freely distributed to those people who might possibly want to make a payment to your account. To transfer funds to you, they will enter in their own account’s private key, and your public key, and a small user-specified transaction fee (typically .0005 B, but as low as a single Satoshi1 or even zero).
The Bitcoin system maintains a global, distributed crypto- graphic ledger of transactions, called the block chain, which is maintained through a consensus algorithm running across a large number of computers distributed across the world. These computers perform a computationally intense func- tion called mining, which integrates the transaction into the block chain. The transaction to debit from the sender’s ac- count and credit to your account is aggregated with other pending transactions together into a block by one of these machines and posted to the head of the block chain. A block also contains a hash of the previous head block of the block chain, creating a total order on all blocks in the block chain.
Upon receiving notice of the block being posted to the network, other nodes will verify that the transaction is in order—for instance, not improperly creating or destroying bitcoin, or over-spending from an account—and then use the new block as the head block for blocks that they are trying to post to the block chain. Each such additional block that is posted to the chain is referred to as a confirmation. If, by chance, two machines simultaneously append a block to the same link on the block chain, the fork will be resolved by picking the branch that has the longest chain of successors— essentially preferring the path that is followed by the major- ity of mining nodes. As new blocks are posted to the block chain, about every ten minutes, the transaction gets expo- nentially less likely to be reversed. Up until now, most BTC services are satisfied with six confirmations, but bitcoin cre- ation (see the next section) requires 100 confirmations.
2.2 Bitcoin Mining: Miner’s Perspective
1The atomic unit of Bitcoin, equivalent to .00000001 BTC.

Bitcoin mining is the heart of the distributed consensus algorithm that enforces the consistency of BTC transactions. Bitcoin miners span a wide spectrum of personalities:
1. High school and college students making use of cheap elec- tricity and/or hardware from their parents or universities;
2. Gamers who subsidize their game machines by running
GPU bitcoin mining codes on them when not in use;
3. Extreme hobbyists that buy multiple machines (“mining rigs”) until they max out the cooling capacity of their
basements (and/or the tolerance of their spouses);
4. Hackers deploying botnets robbing computation from net-
works of zombie machines;
5. Online collaboratives that raised funding to purchase min-
ing hardware and share in profits, and
6. Companies that raised funding from Bitcoin enthusiasts
via an IPO on a BTC-denominated non-SEC-regulated online stock exchange, and are designing ASIC hardware to mine BTC and distribute dividends.
What incentivizes bitcoin miners to perform the mining operation that is integral to transaction verification? The answer is that for each block they add to the block chain, the miner receives two rewards:
• First, they are given a block reward, which started out at 50 BTC and is halved every 210,000 blocks, about every four years. As of the writing of this article, we are on block 251,660; which means that the block reward is 25 BTC. Due to this halving, the total number of BTC will never exceed 21 million; 54.8% of BTC has already been issued, and 99% of all BTC will be issued by 2032.
• Second, they reap all of the transaction fees that are at- tached to the transactions in the block. The miner has the option of excluding or including transactions in the block, so the transaction fee creates an incentive for the miner to ex- pend the additional bandwidth, storage or compute required for that transaction. Requests with low transaction fees can take a long time (a day or more) to be added to a block.
Currently transaction fees average around a quarter of a bitcoin per block, while the block reward is 25 BTC. Over time, the block reward will drop, and BTC transaction vol- ume will increase, so we can expect that transaction fees will become increasingly the incentive for miners.
After bitcoin are earned, the user has the option of either selling them on an exchange like Mt. Gox (whether in USD, Euro or other currency; Bitcoin is truly international), or simply retaining them, hoping that they will appreciate.
Since a new block is supposed to be generated at around every ten minutes, how is this enforced? The answer is that in addition to aggregating the transactions into a block, the miners must find a nonce value that makes a double SHA-256 hash of the block’s header be less than (65535 << 208)/dif f iculty. Since SHA-256 has been designed to be non-invertable, the primary approach is to use brute force. If the difficulty value is twice as large, then it takes twice as many brute-force tries to find the corresponding nonce. The difficulty is scaled every 2016 blocks, using the world’s collective hashrate, the network hashrate, in the preceding period, to target an average block creation time of ten min- utes. In practice, the time between generated blocks oc- curs somewhat randomly, with some blocks being generated within a few seconds of each others, and other consecutive blocks taking over an hour. Thus, in the typical situation where mining capacity is increasing on the network (i.e. more machines are being put in place to mine), groups of 2016 blocks will be mined more quickly than the targeted two week period, and the difficulty will be adjusted upwards, but always trailing the ever-growing rate. Each machine, or rig, that is in place to mine will get a correspondingly smaller fraction of the current 24*6*25 = 3600 BTC bounty that is available per day. At some point, enough rigs have been added, and the difficulty increased, that the energy and maintenance cost of mining equals the value of BTC earned. At this point, the network enters steady state. Since the USD/BTC exchange fluctu- ates, mining profitability has also fluctuated—during dips, less energy efficient rigs are taken off-line, and the difficulty lowers, and the opposite when USD/BTC rises. 2.3 Bitcoin’s “In Plain View” Anonymity Since all Bitcoin transactions must be posted to the block chain, the Bitcoin system is inherently public because the block chain is public2. Bitcoin does not explicitly require personal identifying in- formation to perform transactions, which makes it highly use- ful for performing irreversible transactions with third-parties that you may not want to share physical address information with. However, the public record of the transactions can po- tentially allow identities to be de-anonymized by determined parties, even if users follow the practice of using a different address for every sum of money that is received. For instance, dispensing with BTC that you receive will often require that you payout sums of money to several dif- ferent parties. By receiving a transfer from that address, you are now able to identify other addresses that also do business with the same entity. Moreover, many entities publish their addresses so that they may use the blockchain in order to enhance trust—for instance showing that a set of payments have indeed been paid out to stakeholders as promised. Once an address is identified with an organization, gov- ernment entities can subpoena the records of a given public owner of an address to discover the corresponding real-life information about the user who owns a particular address. Improvements in anonymity are attainable through “dark pools”—services that perform transactions among accounts internally and only post the net differences to the block chain. 2.4 A Brief History Bitcoin resulted from a refinement of ideas in prior digital cryptocurrencies, and first came to light when a user identi- fying themselves as posted a paper on Nov 1, 2008 outlining the cryptocurrency system. On Jan 3, 2009, the system went live, and use grew slowly, then exponentially. Notably, one person paid for a pizza with 10,000 BTC (now worth over $1 million USD). Nakamato maintained the soft- ware base, communicating with others online, but by April 2011 had transferred responsibility for the code base and dis- appeared. Even today, Nakamoto’s identity is still a mystery, and the subject of rampant speculation. BTC Pricing Trends. Figure 1 shows the exchange rate of BTC to USD over time. Starting in 2010, the value of BTC really started to take off, rising from 5 cents in July 2010 to $105 in August 2013, a difference of 2100×. In that time, there were two bubbles, one in June 2011, peaking at $31.50 and one in April 2013, peaking at $266. Large drops in BTC value tend to follow periods of intense media attention that direct large numbers of people to speculate on BTC. Occa- sionally, there are also scares—based on rumors of weakness in the protocols or electronic-breakins in the institutions that 2E.g., the complete transaction history for address 1JVQw1siukrxGFTZykXFDtcf6SExJVuTVE is visible at https://blockchain.info/address/ 1JVQw1siukrxGFTZykXFDtcf6SExJVuTVE. $200 100 50 50,000,000 20,000,000 10,000,000 5,000,000 2,000,000 1,000,000 500,000 200,000 100,000 50,000 20,000 10,000 5,000 2,000 1,000 500 200 100 50 Difficulty USD/BTC Exchange rate (in USD) Difficulty J FMAMJ J ASONDJ FMAMJ J ASONDJ FMAMJ J ASONDJ FMAMJ J AS ’10 ’11 ’12 ’13 J FMAMJ J ASONDJ FMAMJ J ASONDJ FMAMJ J ASONDJ FMAMJ J AS ’10 ’11 ’12 ’13 Figure 2: BTC Mining Difficulty has increased by 50 M ×. Data from http://blockchain.info. Lines indicate the introduction dates of new technologies. GPUs and Pool overlapped. users to get incremental payouts every day as opposed to a large, 50 or 25 BTC payout every several months—by this time, mining a block was equivalent to several months of computation for a single high-end consumer GPU, and the amount of time could vary widely. One of the key innovations was figuring out how to make sure that the end-machines ac- tually did the work that they claimed to have done; and also to make sure they did not “run off” with the winning nonce. Unfortunately, pools concentrate the distributed na- ture of bitcoin, resulting in potential integrity threats to the majority-based confirmation process. Shortly afterwards, the first open-source FPGA miner code was released in June 2011. And then—the first ASIC miner came out in Jan 2013, and other efforts rapidly followed after- wards. Figure 2 shows the debut dates of these technologies. Advances in Performance and Energy-Efficiency. High- end, overclocked six-core CPUs like Core i7 990x eventu- ally reached 33 megahash (MH)/s when using SIMD ex- tensions. NVidia high-end consumer-grade GPUs like the GTX570 reached 155 MH/s rates, while $450 AMD GPUs like the 7970 performed even better, reaching 675 MH/s3. The next evolutionary step were FPGA-based miners, which emerged in June 2011. Open-source versions used four cost- effective Xilinx parts ($ per LUT), Spartan 150s, falling short of the $/MH/s of AMD GPUs, but on a 60 Watt power bud- get instead of 200 W. A commercial company, Butterfly Labs (BFL), began to market and sell a range of FPGA miners. FPGAs would have supplanted GPUs due to energy costs; however, ASICs came out, providing orders of magnitude cost reduction, driving up network hash rates, and inexorably driving GPU and then FPGA profits negative. Figure 1: BTC to USD Exchange Rate ($ per BTC) on the Mt Gox exchange. Since July 2010, the value of a BTC has increased two thousand-fold. Data from http://bitcoincharts.com. facilitate BTC/fiat currency conversion—that cause a mas- sive rush to sell, overwhelming the BTC exchanges. One of the key aspects that makes BTC attractive to speculators is the upper limit of 21 million bitcoin that will ever exist. If BTC were to replace gold as a value store, then the 1.5 tril- lion USD equivalent currently in world-wide gold reserves, when allocated to bitcoin, would make a single bitcoin worth $71,000—significantly above its current value. BTC Difficulty Trends. Figure 2 shows the trend of diffi- culty over time. The difficulty started as 1.0, and has scaled up to 50 million. This is notable because the initial difficulty corresponded to 4-8 general-purpose cores running the nonce- search algorithm, trying out ∼7M double-SHA hashes per second, and now the collective hashing rate of the network is 50 million times that, trying out over 350 TeraHash/sec! Two factors increase difficulty. First, due to the rising USD/BTC rate, mining can cover the expense of more rigs. Second, continual improvements have been made in both the software and hardware for bitcoin mining. Dips in BTC diffi- culty can be noted to line up with bubble bursts in the BTC price; in these cases, the value of the BTC did not justify the costs of running some of the more inefficient miners in pool, and their operators pulled them off-line. Timeline of Innovations in Mining Hardware and Soft- ware. Innovation has been amazingly fast. The first publicly available CUDA miner was released in Sept 2010, with the first OpenCL miner following in Oct 2010. Shortly after- wards, in Nov 2010, a new innovation was released—pooled mining—where groups of computers could work together and split up the nonce-space. Participants were rewarded accord- ing to the fraction of the explored nonce space they con- tributed before the correct nonce was found. These mining pools, which rapidly scaled to thousands of members, allowed See https://en.bitcoin.it/wiki/Mining_hardware_ comparison for a host of statistics. An important question that Bitcoin miners need to con- sider is whether the investment of USD in a new piece of hardware will pay off, versus simply buying the BTC on an exchange. Many custom BTC mining rigs (or shares in com- panies that maintain them on your behalf) are denominated in BTC4, so it’s embarrassing to buy such a rig and never recoup the original BTC cost in its mining profits, especially since maintaining the rigs requires round-the-clock monitor- ing and considerable energy bills. A simple solution is to evaluate the return of the mining operation in terms of BTC. With Bitcoin’s exponential increase in hashing difficulty, a rig’s ability to generate BTC drops exponentially over time. At the average of 1.199× growth of difficulty rating per 14- day period (see Figure 2), more than 66% of a rig’s lifetime BTC earnings comes in the first quarter, 22% will come in Q2, 7% in Q3, and 4% in Q4–Q∞. The lifetime earnings in BTC top out at ∼84× the initial daily earnings. Practically speaking, you will unplug the rig in two cases: first, when the daily earnings in USD is less than the cost of the energy bill, and second, when you need to clear space for your newly purchased set of much faster hashing hardware which has begun its rapid depreciation cycle. The rig’s value is the sum of these exponentially declining expected payments, minus operating costs, plus a final pay- ment, which is the salvage value of reselling the hardware at the end of its life cycle. From this, we can compute the ROI, with P=price, X=exchange rate, ME=maintenance and en- ergy costs, and DRi initial daily revenue5: bitcoin mining. First, you must decide which of several com- peting efforts for a new technology (whether ASIC or FPGA) is most likely to deliver first. Then, within that effort, you need to get yourself early on the wait list relative to other customers. Otherwise, although you picked the right tech- nology, the difficulty of the mining pool will have already ramped to meet the new technology, and you will lose the most valuable, early profits of the technology. For example, a Bitcoin software developer who was selected to receive the first available Avalon ASIC rig cost spent 108 BTC, earning over 15 BTC on its first day of operation in Feb 2013, while in August 2013, there are back-ordered rigs of the same type even though the rig only pulls in 0.9 BTC per day. Using the formula above, we can see 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com