tag:blogger.com,1999:blog-22350257210739335122024-03-14T00:14:59.932-07:00BitCoin SourceUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-2235025721073933512.post-25809873704604610852012-10-27T16:34:00.000-07:002012-10-27T16:34:01.319-07:00Proof of work<br />
<h2>
Copied from <a href="http://bitcoinmedia.com/proof-of-work-exposed/">bitcoinmedia.com/proof-of-work-exposed</a></h2>
<h1 style="background-color: white; color: #222222; font-family: Georgia, Times, serif; font-size: 36px; font-weight: normal; line-height: 38px; margin: 5px 0px 0px; padding: 0px;">
<br /></h1>
<h1 style="background-color: white; color: #222222; font-family: Georgia, Times, serif; font-size: 36px; font-weight: normal; line-height: 38px; margin: 5px 0px 0px; padding: 0px;">
Proof of work exposed</h1>
<div class="meta" style="background-color: white; color: #444444; font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 11px;">
<div class="date" style="color: #888888; font-style: italic; margin-bottom: 5px;">
January 24, 2012</div>
By <a href="http://bitcoinmedia.com/author/genjix/" style="color: #205b87; outline: none; text-decoration: none;" title="Posts by Amir Taaki (genjix)">Amir Taaki (genjix)</a></div>
<div class="entry" style="background-color: white; color: #444444; font-size: 14px; line-height: 18px;">
Underpinning bitcoin is its proof of work algorithm. It is a computational problem which when solved <em>proves</em> you expended <em>work</em> to solve. In bitcoin’s context, work refers to electricity and proof to the ‘target check’.<br />
<strong>Hashing</strong><br />
The actual algorithm involves a hash function.<br />
An algorithm is a list of instructions for solving a problem. An abstract flow-chart of a computer program is an algorithm.<br />
<a href="http://bitcoinmedia.com/proof-of-work-exposed/euclid_flowchart_1/" rel="attachment wp-att-679" style="color: #cc0000; outline: none; text-decoration: none;"><img alt="" class="alignnone size-medium wp-image-679" height="300" src="http://bitcoinmedia.com/uploads/2012/01/Euclid_flowchart_1-133x300.png" style="border: 0px; height: auto; margin: 5px 0px; max-width: 555px;" title="Euclid_flowchart_1" width="133" /></a><br />
Algorithms can be put inside black boxes called functions. Things (input) go into a function, magic happens inside, and things (output) come out.<br />
<a href="http://bitcoinmedia.com/proof-of-work-exposed/function_machine/" rel="attachment wp-att-682" style="color: #cc0000; outline: none; text-decoration: none;"><img alt="" class="alignnone size-full wp-image-682" height="152" src="http://bitcoinmedia.com/uploads/2012/01/Function_machine.png" style="border: 0px; height: auto; margin: 5px 0px; max-width: 555px;" title="Function_machine" width="159" /></a><br />
When programmers talk of algorithms, they mean a set of instructions or a procedure which they are interested in its inner workings. When speaking of a function, a programmer is referring more to what it does rather than how it works. So in this article, when we refer to the proof of work algorithm we are examining how it works. For the hash function which is used by the proof of work, we are less interested how it works and more what are its effects.<br />
A hash function takes a single input and gives a single output that is not easily recognised from the input. Good hash functions (there are many variants from MD5 to SHA) should hardly never generate collisions- that is when two different inputs produce the same output.<br />
<a href="http://bitcoinmedia.com/proof-of-work-exposed/hash-table/" rel="attachment wp-att-685" style="color: #cc0000; outline: none; text-decoration: none;"><img alt="" class="alignnone size-full wp-image-685" height="230" src="http://bitcoinmedia.com/uploads/2012/01/hash-table.png" style="border: 0px; height: auto; margin: 5px 0px; max-width: 555px;" title="hash-table" width="300" /></a><br />
In practice, this means that hash functions generate hashes that have many digits.<br />
<code>$ python<br />>>> import hashlib<br />>>> hashlib.sha256("hello").hexdigest()<br />'2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824'</code><br />
We put <code>hello</code> into the SHA256 hash function, and its algorithm computed the hash value which the function spat out;<code>2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824</code>.<br />
Another property of a good hash function is small changes in input lead to large changes in output. This makes it difficult (practically impossible) to reverse a hash function. Bad hash functions can be reversed with enough computation power. The output hash may not have enough digits and the total search space is too small. Or there are too many collisions in the hash function.<br />
<iframe allowfullscreen="" frameborder="0" height="315" src="http://www.youtube.com/embed/e285rZKJk6k" width="420"></iframe><br /><em>Small changes in the starting conditions lead to large hard to guess changes in output.</em><br />
A security measure that all websites should employ is to not store your password on their server but a hash of the password. When you login, the website hashes your password and checks whether it matches their hash. This makes it impossible for an attacker who compromises the website to learn of the user’s passwords.<br />
When MtGox had their database leaked online, that they were compromised in the first place was also confounded by their poor choice of a hashing algorithm. It was trivial to run through every possible combination of digits, recreate the hash and check for matches in the list to find user’s passwords. A good hashing algorithm makes this <a href="http://en.wikipedia.org/wiki/Brute-force_attack" style="color: #cc0000; outline: none; text-decoration: none;">kind of attack</a> infeasible.<br />
<strong>Proof of work</strong><br />
The bitcoin proof of work algorithm is simple:<br />
<ol>
<li>Hash a block</li>
<li>Calculate the current target from the difficulty</li>
<li>Is the block hash value less than the current target?</li>
</ol>
A bitcoin miner is constantly hashing a block to see if it passes the above check. If not then it slightly modifies the block and tries again. It keeps doing this until it finds a block that passes. A valid block has been found, and the miner will broadcast this block to the network.<br />
The difficulty is set by the network. Around every 2 weeks, the network reconvenes and decides on a new difficulty. If it was too easy to make blocks, then the difficulty rises. If too hard, then difficulty falls.<br />
This is why bitcoin blocks all start with zeros. The block hashes are numbers. Block 163701 has a hash value in <a href="http://en.wikipedia.org/wiki/Hexadecimal" style="color: #cc0000; outline: none; text-decoration: none;">hexadecimal</a> representation of:<br />
<code>00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018</code><br />
In decimal this is:<br />
<code>15072061652479515824586354748403488046119941424972330391289880</code><br />
Looking at <a href="http://blockexplorer.com/block/00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018" style="color: #cc0000; outline: none; text-decoration: none;">block 163701</a>, note the field labelled “Bits”.<br />
<code>Difficulty: 1307728.360604 ("Bits": 1a0cd43f)</code><br />
To transform a bits value into a target we use the formula:<br />
<code>t = b<sub>2</sub> · 2<sup>8(b<sub>1</sub> - 3)</sup></code><br />
<code>b<sub>1</sub></code> is the first <a href="http://en.wikipedia.org/wiki/Byte" style="color: #cc0000; outline: none; text-decoration: none;">byte</a> of our “bits” value or 0x1a in hexadecimal (26 in decimal). <code>b<sub>2</sub></code> is the rest of the value or 0x0cd43f (840767).<br />
<code>t = 0x0cd43f · 2<sup>8(0x1a - 3)</sup></code><br />
<code>>>> 0x0cd43f * 2**(8*(0x1a - 3))<br />20615546854515052444405957679617344022137222968655050411343872L<br />>>> "%x"%(0x0cd43f * 2**(8*(0x1a - 3)))<br />'cd43f0000000000000000000000000000000000000000000000'</code><br />
The maximum possible target is a constant defined by <code>0x1d00ffff</code>.<br />
<code>>>> "%x"%(0x00ffff * 2**(8*(0x1d - 3)))<br />'ffff0000000000000000000000000000000000000000000000000000'</code><br />
To find the difficulty we use:<br />
difficulty = maximum possible target / currently agreed on target<br />
Taking from our example:<br />
<code>>>> 0xffff0000000000000000000000000000000000000000000000000000 / float(0xcd43f0000000000000000000000000000000000000000000000)<br />1307728.3606040676</code><br />
Which is the same difficulty we noted earlier on block explorer. We know the current target, and we have the block hash. If the block is valid and passes the proof of work test then that block hash will be a smaller number than the current target.<br />
<code>0x00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018 < 0xcd43f0000000000000000000000000000000000000000000000</code><br />
<code></code><code>True</code><br />
A miner’s task is to make a block and keep modifying that block so that it produces a different hash, until that hash passes the above test. Noting our <a href="http://blockexplorer.com/block/00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018" style="color: #cc0000; outline: none; text-decoration: none;">example block</a>, there is a field called “Nonce”.<br />
<code>Nonce: 2528486661</code><br />
To modify the blocks, miners usually keep adding one to the nonce and rehash the block. Although they can equally set it to random values or modify the block in other ways such as re-arranging the transactions contained in the block. And if the nonce reaches its maximum value, then miners will perform some trickery on their first transaction and continue on (trickery is increment coinbase nonce or <code>IncrementExtraNonce(...)</code>).<br />
Creating a block is not easy. It takes computational processor cycles. Ergo it takes electricity. Ergo it costs money. Creating a block usually has miniscule profit or even negative expected value. As more people mine and create blocks, the network drives up the difficulty squeezing out all the profit.<br />
Once a miner finds a valid block that passes the proof of work test, it is sent out to the network. Other participants in the network pick up the block, verify that it passes the test, accept it into their own blockchain and relay it on.</div>
Unknownnoreply@blogger.com2tag:blogger.com,1999:blog-2235025721073933512.post-58266127834350596462012-10-18T13:46:00.002-07:002012-10-18T13:46:54.990-07:00stale blockAt any second, a block may be "solved." This means that everyone else
in the world working on that block must stop, and restart their work.
Continuing to work after that point is known as working on a "stale
block" because it is old data, and old transactions.Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-2235025721073933512.post-79100239667936050822012-10-18T13:02:00.002-07:002012-10-18T13:02:36.780-07:00Generating Bitcoins<br />
<div id="inner">
<div id="content-sidebar-wrap">
<div class="hfeed" id="content">
<div class="post-464 post type-post status-publish format-standard hentry category-computer-science category-internet tag-bitcoin tag-bitcoin-mining">
<h1 class="entry-title">
Bitcoin Mining</h1>
<div class="entry-content">
Bitcoin is a digital currency. If you have a minute, check out this video:<br />
<span class="embed-youtube" style="display: block; text-align: center;"><iframe class="youtube-player" frameborder="0" height="458" src="http://www.youtube.com/embed/Um63OQz3bjo?version=3&rel=1&fs=1&showsearch=0&showinfo=1&iv_load_policy=1&wmode=transparent" type="text/html" width="760"></iframe></span><br />
Did that mean anything to you? The important things are:<br />
<ul>
<li>Bitcoins are being exchanged for goods, and</li>
<li>people are exchanging dollars (and other currency) for Bitcoins.</li>
</ul>
<h2>
Generating Bitcoins</h2>
One key to the Bitcoin currency is the limited and predictable rate
at which coins are added to the system (see 0:33-0:43 in the video).
This control is achieved by tying the generation of one block (50 units)
of Bitcoins to the solving of a computationally difficult problem:
solve the problem, get a block of Bitcoins. The distributed Bitcoin
network adjusts the difficulty of this problem after every 2016 blocks
of Bitcoins are generated. The difficulty is adjusted so that on
average, 6 blocks of Bitcoins (300 units) are generated every hour by
users around the world. The incentive to devoting your computer’s power
and time to solving the difficult computational problem is that the user
whose computer solves the problem gets awarded that block of 50
Bitcoins.<br />
For more detail about the computational problem, read the Bitcoin <a href="http://www.bitcoin.org/bitcoin.pdf">white paper</a>.
It’s generally equivalent to finding a number that hashes (using
SHA-256) to a value that is less than a particular 256-bit target.
Adjusting that target value is how the distributed Bitcoin network
adjusts the difficulty of block generation. Moving the target lower
makes for a more difficult computational problem: it will take more
random tries to find a value whose hash is less than the target.<br />
One more detail. Every 210,000 blocks, the Bitcoin reward per block
is cut in half. Right now, the payout is 50 Bitcoins per block. Sometime
soon, the payout will halve to 25 Bitcoins per block.<br />
<h2>
Bitcoin mining</h2>
So, people are paying dollars for Bitcoins, and you can use your
computer for a chance of being awarded Bitcoins. Can you make money off
of this? Right now, I think the answer is yes, but it depends on your
situation and how you approach the problem.<br />
Remember that the computational problem is basically finding a number
whose SHA-256 hash is less than the current target value. You need a
machine that can do this operation very quickly, and repeatedly. Right
now (May 24, 2011), the difficulty level is set such that it will take
on average 1,048,471,150,000,000 hash attempts before finding one that
wins you a block (50 units) of Bitcoins (that’s over 1 quadrillion
attempts… I had to look that up). Your CPU power will be able to do
around 2-10 million hashes per second. That means, if conditions stayed
exactly as they are now, it would take your CPU about 3-10 years to win a
Bitcoin block. <strong>People are not using CPUs to mine for Bitcoins.</strong><br />
The only way you will have any hope at being awarded a block of Bitcoins is to <strong>use the computing power of a GPU</strong>
(graphics processing unit). Originally used for manipulating computer
graphics, today, GPUs are being used for general parallel processing
tasks. It happens that the hashing required for Bitcoin generation is a
perfect fit for a GPU. Top-of-the-line ATI GPUs can do 270-360 million
hashes per second (compare that to the 2-10 million per second that a
CPU can do). Still, that takes about 33-45 days to win a Bitcoin block
and the difficulty could be increased during that time period. (Note:
Nvidia GPUs are not as well suited to this problem, giving only up to
140 million hashes per second.)<br />
A popular alternative to mining individually is to <strong>join a Bitcoin mining pool</strong>.
A mining pool is a group that has collectively agreed to work on
Bitcoin generation to increase the probability of being awarded a block
of 50 Bitcoins. An example is here: <a href="http://mining.bitcoin.cz/stats/">http://mining.bitcoin.cz/stats/</a>.
As of May 24, 2011, this pool has about 4300 worker machines (including
mine). This results in a combined 430 billion hashes per second. This
pool is awarded a block every 40 minutes on average. The block of 50
Bitcoins is distributed between the 4300 workers according to how much
work each of them did during the search. My machine, doing 270 million
hashes per second, gets about 0.02-0.04 Bitcoins from each block that is
awarded. Pooled mining allows you to bring in Bitcoins slowly over
time, rather than waiting for weeks for an individual return of 50
Bitcoins.<br />
<h2>
Is it worth it?</h2>
There are a lot of assumptions that go into answering this question.
How much does power cost where you live? How many Bitcoins can you gain
per day? What will people pay for Bitcoins when you’re ready to sell
them?<br />
<strong>Power</strong><br />
If you live in Canada, you’re in luck. Canada has the cheapest power in
the world. In British Columbia, Canada, the rate is $0.0627/kWh. A 500W
machine will draw 360 kWh in one month, or $22.57. In the US, you could
be paying anywhere from $0.09-0.20/kWh. Power in some European countries
is as high as $0.30/kWh.<br />
<strong>Generation rate</strong><br />
I’ll assume that you have or will buy a top-of-the-line card. So, let’s
use the low end of that range: 270 Mh/s (megahashes/second). As
mentioned before, at the current difficulty level, this gives a 50
Bitcoin block every 45 days. If you’re doing pooled mining, the
amortized rate should work out to about the same (around 1.1 Bitcoins
per day) To work this out for different difficulty levels or your own
hardware, check this out: <a href="https://en.bitcoin.it/wiki/Generation_Calculator">https://en.bitcoin.it/wiki/Generation_Calculator </a><br />
<strong>How much will people pay?</strong><br />
This is the most uncertain of all the assumptions. <a href="http://bitcoincharts.com/markets/">http://bitcoincharts.com/markets/</a>
gives current data on Bitcoin prices in USD, GBP, and EUR. The prices
have averaged around 6.5-7 USD per Bitcoin, but that is a very recent
spike. Over the past 30 days, the average is 4.80 USD per Bitcoin.<br />
<div class="wp-caption aligncenter" style="width: 510px;">
<a href="http://bitcoincharts.com/charts/mtgoxUSD#rg60zvztgSzm1g10zm2g25"><img alt="A chart showing the Bitcoin market over the past few months." src="http://bitcoincharts.com/charts/chart.png?width=906&m=mtgoxUSD&k=&r=60&i=&c=0&s=&e=&Prev=&Next=&v=1&cv=0&ps=0&l=0&p=0&t=S&b=&a1=&m1=10&a2=&m2=25&x=0&i1=&i2=&i3=&i4=&SubmitButton=Draw&" title="Bitcoin Market" width="500px" /></a><div class="wp-caption-text">
Volume
(in USD) on the left axis. USD per BTC on the right axis. Bars show
volume, box and whiskers show daily values, 25-75 percentiles, and
high/low.</div>
</div>
<br />
From these assumptions, one should be able to net about
$90-$100/month if you live in Canada. This will decrease as the
difficulty increases, but that’s a good starting point. Even if you have
to buy new hardware for this, good graphics cards hold resale value
that you can reclaim once you’re done with your mining.<br />
One interesting point about profitability… as prices rise to make
Bitcoin mining profitable, more people will join the mining population,
driving up the difficulty and production costs, reducing the
profitability. On average, Bitcoin mining should not be profitable.
Access to cheap power makes the difference. You’ll be on the winning
side of average.</div>
</div>
</div>
</div>
</div>
Unknownnoreply@blogger.com4tag:blogger.com,1999:blog-2235025721073933512.post-54757200476967092312012-10-18T11:22:00.000-07:002012-10-18T11:22:21.759-07:00Mining With GPUs<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-xe05TjV89Tc/UIBHua-DarI/AAAAAAAAASw/RMXgEVt8N4g/s1600/bitcoingpu.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="http://3.bp.blogspot.com/-xe05TjV89Tc/UIBHua-DarI/AAAAAAAAASw/RMXgEVt8N4g/s320/bitcoingpu.jpg" width="320" /></a></div>
Archived 07-15-12
Mining With GPUs - The Bitter End?<br />
<br />
Though the recent rally in the exchange rates has caused mining profitability to rise to the highest level seen since February, many mining operators are planning for the future and liquidating their inefficient rigs, as shown in this post’s photo.<br />
<br />
In less than six months, block 210,000 will be reached and with that event the block reward will drop by half, to the level of just 25 BTC. Thus instead of 7,200 BTC targeted for issuance per-day, only 3,600 BTC per-day will go to those mining.<br />
<br />
Because it can’t be known what the exchange rate and mining difficulty level will be at that point in time, mining operators are preparing by either switching over to more efficient mining equipment or are liquidating operations outright — oftentimes due to the higher capital requirements needed to acquire the modern forms of mining hardware (FPGA and ASIC).<br />
<br />
But one mining operator’s pain is another’s gain. Those operating where electric rates are a fraction of their competitor’s rates are still able to compete while mining with GPUs due to the comparatively lower cost of GPU hardware. Lower cost, maybe, but they still aren’t cheap. Even though the GPUs from this post’s photo are offered for sale as being used previously for mining (presumably for many months) they still have a relatively high market value compared to the price when they are purchased brand new. The HD 6950s in this instance, are offered at only a 25% discount versus the current price from NewEgg.<br />
<br />
The seller, in this instance, is not leaving mining but instead “restructuring” his mining operation to use far less power to be compatible with the operation’s new solar power source. “I’m in a position to buy enough solar panels at an amazing price that I’ll never need to buy electricity again” writes forum member AmpEater.
So while there likely won’t be less GPU mining occurring in total, there will be a rotation of hashing equipment. GPUs are being decommissioned where power is expensive and those same cards remain a valued commodity to those with access to power that is relatively cheap.<br />
<br />
If the exchange rate continues to rise faster than the difficulty does, even with the block reward drop these mining operators using GPUs yet might come to find their strategy paying off handsomely.<br />
<br />Unknownnoreply@blogger.com0