Saturday, October 27, 2012

Proof of work

Copied from

Proof of work exposed

January 24, 2012
By Amir Taaki (genjix)
Underpinning bitcoin is its proof of work algorithm. It is a computational problem which when solved proves you expended work to solve. In bitcoin’s context, work refers to electricity and proof to the ‘target check’.
The actual algorithm involves a hash function.
An algorithm is a list of instructions for solving a problem. An abstract flow-chart of a computer program is an algorithm.

Algorithms can be put inside black boxes called functions. Things (input) go into a function, magic happens inside, and things (output) come out.

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.
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.

In practice, this means that hash functions generate hashes that have many digits.
$ python
>>> import hashlib
>>> hashlib.sha256("hello").hexdigest()

We put hello into the SHA256 hash function, and its algorithm computed the hash value which the function spat out;2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824.
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.

Small changes in the starting conditions lead to large hard to guess changes in output.
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.
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 kind of attack infeasible.
Proof of work
The bitcoin proof of work algorithm is simple:
  1. Hash a block
  2. Calculate the current target from the difficulty
  3. Is the block hash value less than the current target?
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.
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.
This is why bitcoin blocks all start with zeros. The block hashes are numbers. Block 163701 has a hash value in hexadecimal representation of:
In decimal this is:
Looking at block 163701, note the field labelled “Bits”.
Difficulty: 1307728.360604 ("Bits": 1a0cd43f)
To transform a bits value into a target we use the formula:
t = b2 · 28(b1 - 3)
b1 is the first byte of our “bits” value or 0x1a in hexadecimal (26 in decimal). b2 is the rest of the value or 0x0cd43f (840767).
t = 0x0cd43f · 28(0x1a - 3)
>>> 0x0cd43f * 2**(8*(0x1a - 3))
>>> "%x"%(0x0cd43f * 2**(8*(0x1a - 3)))

The maximum possible target is a constant defined by 0x1d00ffff.
>>> "%x"%(0x00ffff * 2**(8*(0x1d - 3)))

To find the difficulty we use:
difficulty = maximum possible target / currently agreed on target
Taking from our example:
>>> 0xffff0000000000000000000000000000000000000000000000000000 / float(0xcd43f0000000000000000000000000000000000000000000000)

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.
0x00000000000009611e31fd14c3c786bb792e17f9b95f65620491ac55ed4bc018 < 0xcd43f0000000000000000000000000000000000000000000000
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 example block, there is a field called “Nonce”.
Nonce: 2528486661
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 IncrementExtraNonce(...)).
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.
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.

Thursday, October 18, 2012

stale block

At 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.

Generating Bitcoins

Bitcoin Mining

Bitcoin is a digital currency. If you have a minute, check out this video:

Did that mean anything to you? The important things are:
  • Bitcoins are being exchanged for goods, and
  • people are exchanging dollars (and other currency) for Bitcoins.

Generating Bitcoins

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.
For more detail about the computational problem, read the Bitcoin white paper. 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.
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.

Bitcoin mining

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.
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. People are not using CPUs to mine for Bitcoins.
The only way you will have any hope at being awarded a block of Bitcoins is to use the computing power of a GPU (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.)
A popular alternative to mining individually is to join a Bitcoin mining pool. 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: 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.

Is it worth it?

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?
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.
Generation rate
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:
How much will people pay?
This is the most uncertain of all the assumptions. 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.
A chart showing the Bitcoin market over the past few months.
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.

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.
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.

Mining With GPUs

Archived 07-15-12 Mining With GPUs - The Bitter End?

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.

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.

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).

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.

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.

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.