Proof of Work (POW)

Proof of Work

Existing Blockchain technology is working on the core concept of 'Proof Of Work' (POW). A proof-of-work (PoW) is a protocol that is difficult to compute but easy to verify. It can be verified in far less time than it took to compute in first place. The process involves scanning for a value that when hashed, (such as with SHA-256), the hash begins with a number of zero bits. The average work required is exponential in the number of zero bits required and can be verified by executing a single hash. In simple words, Proof of work is an expensive computation done by all miners to compete to find a number that, when added to the block of transactions, causes this block to hash to a code with certain rare properties. Finding such a rare number is hard (based on the cryptographic features of the hash function used in this process), but verifying its validity when it's found is relatively easy. One can take the challenge, the proof string and hash them together and check if the hash begins with a number of zero bits. This requires to apply the hash function just once and verify the output indeed has requisite numbers of 0's in front. If so, then the proof of work is considered valid under the application of that cryptographic hash function. Every block in the participating network should contain such rare number.

Fig: Steps followed in Proof of Work

Mining

Mining is a process of generating proof of work. Mining is needed to be performed in order to facilitate transactions on the blockchain and to ensure that the computation done behind creation of each block in the blockchain is correct. This process is named mining because it is similar to the process of real mining (digging), except in this case for a new cryptocurrency and it is CPU time and electricity that is expended. The process involves extensive computation. If they're generated too fast, the computation difficulty increases. It is expensive as well because it requires costly hardware and lot of electricity consumption. Fun fact : It is estimated that the entire bitcoin network will use as much electricity as Ireland.

Blockchain protocol rewards the miner who first successfully solves proof of work algorithm with transaction fee and a preset amount of newly issued crypto currency for every block . In case of Ethereum, reward is 5.02447 ETH per block and Bitcoin mining block reward is 12.5 BTC per block (at present). Block reward adds an incentive for nodes (miners) to support the network, and provided a way to initially distribute coins into circulation, since there is no central authority to issue them.

Applications of Proof of Work

• Prevent 'Denial of Service' (DOS) Attack: The idea here is that the requester of a particular service would have to solve a very specific computational problem , a proof of work puzzle, before being allowed to use a service. The computational effort exerted is effectively a way to strangle the requester. The responder can, in turn, easily check if the requester carried out the requisite work and only if that work was carried out will the responder respond to that request for service.

• Determine spam email: The idea here is that POW can be tied to a particular email message. For a sender who is sending out a small number of messages are considered legitimate. It is somehow blocking but not so unreasonable. Now, for a spammer, who might be sending out a lot of messages, may be hundreds of thousands messages might find it expensive to repeatedly expand so many CPU cucles for each message and each senders to whom that message is being sent.

• In blockchain and Cryptocurrency : They uses POW schemes to create new blocks and generate new cryptocurrency.

Proof of Work in Bitcoin

Satoshi Nakamoto (the inventor of blockchain) in his article 'Bitcoin: A Peer-to-Peer Electronic Cash System' explained that proof- of-work system is needed to implement a distributed timestamp server on a peer-to-peer basis.

In Bitcoin, proof of work is implemented by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Every transaction has to have a unique incrementing nonce. The first transaction has to have nonce = 1, second nonce = 2, third nonce = 3 and so forth. The reason this is done so is to prevent replay attacks. Once the CPU effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work to change the block would include redoing all the blocks after it.

Fig: Diagram taken from 'Bitcoin: A Peer-to-Peer Electronic Cash System' by Satoshi Nakamoto

POW enabling trustless consensus

The proof-of-work also solves the problem of determining representation in majority decision making, which is essentially one-CPU-one-vote. If the majority were based on one-IP-address-one-vote, it could be subverted by anyone able to allocate many IPs. The majority decision is represented by the longest chain, which has the greatest proof-of-work effort invested in it.

If a majority of CPU power is controlled by honest nodes, the honest chain will grow the fastest and outpace any competing chains. Nodes always consider the longest chain to be the correct one and will keep working on extending it. If an attacker is able to assemble more CPU power than all the honest nodes, he can either defraud people by stealing back his payments, or using it to generate new coins. To perform the attack, he would have to modify a past block. It means he has to redo the proof-of-work of the block and all blocks after it and then catch up with and surpass the work of the honest nodes, which is definitely not an easy task. Even if, he assembles more CPU power than all the honest nodes, it does not allow the system to undergo arbitrary changes, such as creating value out of thin air or taking money that never belonged to the attacker. Honest nodes on the network are not going to accept an invalid transaction as payment, and will never accept a block containing them. An attacker can only try to change one of his own transactions to take back money he recently spent.

Proof-of-work protocol is needed for an electronic transaction system to prevent double-spending. It will record a public history of transactions that quickly becomes computationally impractical for an attacker to change if honest nodes control a majority of CPU power. Any node can leave and rejoin the network at will after accepting the proof-of-work chain as proof of what happened while they were gone. They vote with their CPU power, expressing their acceptance of valid blocks by working on extending them and rejecting invalid blocks by refusing to work on them. Any needed rules and incentives can be enforced with this consensus mechanism. POW is only useful when trustless consensus is required, otherwise it is an expensive and misuse of resources.

51% Attack

A 51% attack is when a miner, or more likely a mining pool, controls 51% of the network’s computational power. With that ability, they could invalidate valid transactions and double spend funds. They’d achieve this through creating and confirming their own fraudulent blocks, and do it so quickly, the rest of the mining community creating genuine blocks would have their legitimate work invalidated.

That’s where Proof of Stake (PoS) could really help. Even if someone owned 51% of a digital currency, it would not be in their interest to attack something in which they have a majority share. Also, it’s very unlikely that anyone would be interested in buying up 51% of a currency, due to it being prohibitively expensive. According to game theory, those with a larger stake in a cryptocurrency should want to maintain a secure network. Any attack would only serve to destabilize the digital currency, diminishing the value of their stake.

Proof of Work in Ethereum

In existing proof of work (PoW) algorithm like in Bitcoin, a small group of hardware companies or mining operations acquire a disproportionately large amount of power to impact or manipulate the network. Usage of ASICs, specialised chips specifically designed to outperform standardized computer hardware by many orders of magnitude in hashing performance is being used to solve the computation and mint more coins. Bitcoin’s mining system has always been heavily centralized, because Bitcoin miners are just grabbing block headers from places like GHASH.io and just mining on them without even thinking about their mining.

In Ethereum, the team decided to use mining algorithm that helps fight against mining centralization. Originally, they considered memory hard ideas like Dagger. The process of having decentralized mining is followed to make it more difficult to create ASIC’s chips for it. As it turns out, Dagger is great mathematically, but it is not all-that great when miners have GPU’s with shared memory. So, further they moved to different Proof of stake ideas, but it is yet to be implemented.

At present, Proof of Work in Ethereum is based on executing random transactions on random data from the block chain. The concept involves, in order to be a miner, one has to store the entire block chain and has to have a functioning Ethereum scripting engine. Basically, from this kind of system, a lot of centralisation is removed.

Ethash

The Ethereum network currently uses a planned proof of work (PoW) based consensus algorithm called Ethash. Other factors that promote mining centralization, such as handling of orphaned blocks, are tackled separately within the Ethereum protocol. Ethash is a specifically designed CPU friendly and "ASIC-resistant" PoW algorithm in Ethereum. It is going to be harder to make ASIC’s, but probably not impossible. The Ethereum team hopes to reduce economic incentives for mining centralization in Ethereum, at least until a secure PoS (Casper) algorithm can be designed and deployed.

The way that Ethash aims to provide a PoW algorithm for which commodity hardware is already highly optimized is by emphasizing a property called memory hardness. Memory hardness essentially means that your performance is limited by how fast your computer can move data around in memory rather than by how fast it can perform calculating operations. Consumer graphics cards compete very strongly in this area, which means that a potential ASIC designer can't easily do better: if they had a new idea for improving memory bandwidth it would be more profitable to sell that idea to a graphics card company than to design a mining ASIC for it.

Combining cryptographic signatures, merkle tree, and P2P networks into a viable distributed consensus system, to create cryptocurrency is a wonderful application of proof of work designed and implemented (in Bitcoin) by Satoshi Nakamoto .