Proof of Work — Ethereum
By Palludallu on ALTCOIN MAGAZINE
Ethereum is a blockchain-based open technology platform that enables individuals to develop and launch decentralized applications (also known as dapps). This is made possible due to the smart contract functionality that the Ethereum platform possesses. Today, miners play an important role in making sure ethereum works.
Ethereum Tokens:
Ethereum’s tokens are created through the process of mining at a rate of 5 ether per mined block. Mining is one innovation that makes decentralized record-keeping possible. Although ethereum is looking into other methods of coming to consensus about the validity of transactions, mining currently holds the platform together.
Proof of Work:
✔ The Ethereum blockchain is maintained by a distributed network of nodes, and in order for a node to add a block to the blockchain, it must undergo Ethereum’s proof of work mining process.
✔ Miners hash variations of the input data by including a nonce. The nonce is an arbitrary number that varies the input data such that the correct output that allows the miner to add a new block to the blockchain can be found.
✔ The ethereum algorithm, Etash, is the hashing algorithm that is used in this proof of work algorithm.
✔ Every 12–15 seconds, a miner finds a block. If the miner slows down or moves faster than the time limit, the algorithm readjusts the difficulty of the problem so that the miners spring back to roughly the 12-second solution time.
How does mining work in ethereum?
✔ For each block of transactions, miners use computers to repeatedly and very quickly guess answers to a puzzle until one of them wins.
Mining uses the puzzle-solving method:
How do miners earn?
✔ A block reward of 3 ether.
✔ All of the gas that was consumed when executing all of the transactions within the block.
✔ An additional reward for including uncles as part of the block. Miners that include uncles in a block receive 2.625 ether
DAG in Ethereum Blockchain?
✔ Dagger Hashimoto is the mining algorithm for ethereum.
✔ Dagger Hashimoto aims to simultaneously satisfy two goals:
- ASIC-resistance: the benefit of creating specialized hardware for the algorithm should be as small as possible.
- 2. Light Client verifiability: a block should be relatively efficiently verifiable by a light client.
Dagger algorithm:
✔ Dagger algorithm works by creating a directed acyclic graph (the technical term for a tree where each node is allowed to have multiple parents) with ten levels including the root and a total of 225–1 values.
✔ In levels 1 through 8, the value of each node depends on three nodes in the level above it, and the number of nodes in each level is eight times larger than in the previous.
✔ In level 9, the value of each node depends on 16 of its parents, and the level is only twice as large as the previous; the purpose of this is to make the natural time-memory tradeoff attack be artificially costly to implement at the first level, so that it would not be a viable strategy to implement any time-memory tradeoff optimizations at all.
✔ Finally, the algorithm uses the underlying data, combined with a nonce, to pseudorandomly select eight bottom-level nodes in the graph, and computes the hash of all of these nodes put together.
✔ If the miner finds a nonce such that this resulting hash is below 2256 divided by the difficulty parameter, the result is a valid proof of work. Pseudocode for Dagger algorithm :
✔ Let D be the underlying data, N be the nonce and || be the string concatenation operator (ie. ‘foo’ || ‘bar’ == ‘foobar’).
Hashimoto algorithm:
✔ Uses cryptographic hash function not as a proof of work itself, but rather as a generator of pointers to a shared data set allows for an I/O bound of work. ✔ Difficult to optimize via ASIC design and difficult to outsource nodes without a full data set.
✔ Derived from three operations: hash, shift, and modulo.
Pseudocode for Hashimoto algorithm:
✔ We define the following functions: 1. Nonce: 64bits. A new nonce is created for each attempt. 2. get_txid(T): return the txid (a hash of a transaction) of transaction number T from block B. 3.block_height: the current height of the block chain, which increases at each new block.
✔ The target is then compared with final_output, and smaller values are accepted as proofs.
✔ The initial hash output is used to independently and uniformly select 64 transactions from the blockchain. At each of the 64 steps, the hash_outputA is shifted right by one bit, to obtain a new number,shifted_A.
✔ A block is chosen by computing shifted_A modulo the total number of blocks, and transaction chosen by computing shifted_A modulo the number of transactions within that block.
✔ These txids are also shifted by the same amount as the shifted_A which selected them. Once the 64 txids have been retrieved, they all XORed together and used as the input for the final hash function, along with the original nonce.
✔ The original nonce shifted up into the most significant bits, is needed in the final XOR function because very small sets of transactions may not contain enough permutations of txids to satisfy the proof of work inequality.
✔ In fact, this algorithm only becomes I/O bound as the blockchain expands in size. In the extreme case of a blockchain with only 1 block and 1 transaction, the entire 64 iteration process can be omitted, and the nonce for final_output can be rapidly iterated as the txids will always be the same.
Ethash algorithm:
Proof of work algorithm that ethereum implements :
✔ The Ethash algorithm relies on a pseudorandom dataset, initialized by the current blockchain length. This is called a DAG and is regenerated every 30,000 blocks (or every 5 days) and the DAG will continue to grow in size as the blockchain grows.
✔ The fixed output that is produced during the hashing process, in order for a node to add a block to the Ethereum blockchain, must be a value that is below a certain threshold. Ethash ASIC-resistance :
✔ Proof of working mining on the Ethereum algorithm, Ethash, requires retrieving pieces of random data from the DAG, hashing randomly selected transactions from any block on the blockchain, and then returning the result from the hashing process.
✔ Thus, in order for an individual to mine on Ethereum, they will have to store the entire DAG for the purposes of being able to fetch data and compute selected transactions.
✔ The result of the Ethereum mining structure is that a miner spends more time reading the DAG, as opposed to executing computations that are fetched from it. This is an intentional design architecture that is aimed at making mining on Ethereum ASIC (application-specific integrated circuit) resistant.
✔ The requirement of having to hold a large amount of memory during the mining process means that entities such as mining farms gain little benefit from loading terabytes of memory into their mining devices.
✔ Large-scale miners receive little benefit from doing this because smaller miners can similarly also purchase terabytes of memory, as the energy cost of memory taken on by a large-scale miner and a smaller miner is comparable. What is memory hard? 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.
✔ Every mixing operation requires a 128 byte read from the DAG. Hashing a single nonce requires 64 mixes, resulting in (128 Bytes x 64) = 8 KB of memory read.
✔ Since fetching the DAG pages from memory is much slower than the mixing computation, we’ll see almost no performance improvement from speeding up the mixing computation.
✔ The best way to speed up the ethash hashing algorithm is to speed up the 128 byte DAG page fetches from memory. Thus, we consider the ethash algorithm to be memory hard or memory bound. The primary reason for constructing a new proof of work function instead of using an existing one was to attack the problem of mining centralization, where a small group of hardware companies or mining operations acquire a disproportionately large amount of power to impact or manipulate the network.
✔ The Preprocessed Header — derived from the latest block and the Current Nonce — the current guess, are combined using a SHA3-like algorithm to create our initial 128-byte mix, called Mix 0.
✔ The Mix is used to compute which 128-byte page from the DAG to retrieve, represented by the Get DAG Page block.
✔ The Mix is combined with the retrieved DAG page. This is done using an ethereum-specific mixing function to generate the next mix, called Mix 1.
✔ Steps 2 & 3 are repeated 64 times, finally yielding Mix 64.
✔ Mix 64 is post-processed, yielding a shorter, 32 byte Mix Digest.
✔ Mix Digest is compared against the predefined 32-byte Target Threshold.
✔ If Mix Digest is less than or equal to Target Threshold, then the Current Nonce is considered successful and will be broadcast to the ethereum network
✔ Otherwise, Current Nonce is considered invalid, and the algorithm is rerun with a different nonce (either by incrementing the current nonce or picking a new one at random).
