Closed gcolvin closed 2 years ago
Please not again
Have you no shame?
I do not understand what is intended. Supplemental PoW (to Ethash) is already possible in terms of Turing-complete scripts, though it needs a high transaction fee (as intended). Any transaction cannot be added without executing the script attached.
I think I'm speaking for many. Please just stop - the EIP was rejected by the community.
I call on the core devs, in the next all core devs meeting, to officially table this EIP and rescind its accepted state. It's so......obvious at this point that this should go the way of the dodo bird.
@gspoosi There is no governance mechanism by which the community can accept or reject this other than what the clients choose to implement and the miners choose to run. As a core dev I care about the security of the network, not people's opinions.
@tjayrush The most recent core devs' position was to accept @apbendi's compromise - leave ProgPoW as it is - speced, tested, and ready to deploy - but not deploy it unless ASICs look to be an actual threat. The mere ability to deploy may well serve as an adequate deterrent. This issue exists just to maintain a working draft of the spec.
Not a few of us are convinced that ASICs pose a genuine threat to the security of the Ethereum network. We are not likely to drop our concerns absent arguments to the contrary. Such arguments remain welcome at the discussions-to link.
@gcolvin That is ok. The work is valuable for sure - but a "forced" introduction of the EIP would do more harm than good community-wise.
RavenCoin has switched to ProgPow (resp. KawPoW) and it seems to have drastically reduced (x10) the total hash power - seems to work as intended!
@gspoosi The introduction of this EIP is not being forced. It was introduced two years ago.
The deployment of an EIP cannot be forced. It takes a consensus of the core devs to get it into the clients and attempt to deploy it, it takes a consensus of the miners to get it actually deployed on a chain, and in the case of a chain split it takes a consensus of the exchanges to decide which chain is ETH.
Hi @gcolvin, can you assign me ?
There has been no activity on this issue for two months. It will be closed in a week if no further activity occurs. If you would like to move this EIP forward, please respond to any outstanding feedback or add a comment indicating that you have addressed all required feedback and are ready for a review.
This issue was closed due to inactivity. If you are still pursuing it, feel free to reopen it and respond to any feedback or request a review in a comment.
eip: 1057 title: ProgPoW, a Programmatic Proof-of-Work author: Greg Colvin greg@colvin.org, Andrea Lanfranchi (@AndreaLanfranchi), Michael Carter (@bitsbetrippin), IfDefElse ifdefelse@protonmail.com discussions-to: https://ethereum-magicians.org/t/eip-progpow-a-programmatic-proof-of-work/272 status: Accepted type: Standards Track category: Core created: 2018-05-02
Simple Summary
A new Proof-of-Work algorithm to replace Ethash that utilizes almost all parts of commodity GPUs.
We Do Not recommend that this Proposal be deployed at this time. Rather it is being offered in the spirit of Ben DiFrancesco's compromise which for our purposes we state simply as,
This leaves open the possibility and threat of future deployment.
Abstract
ProgPoW is a proof-of-work algorithm designed to close the efficiency gap available to specialized ASICs. It utilizes almost all parts of commodity hardware (GPUs), and comes pre-tuned for the most common hardware utilized in the Ethereum network.
This document presents an overview of the algorithm and examines what it means to be “ASIC-resistant.” Next, we compare existing PoW designs by analyzing how each algorithm executes in hardware. Finally, we present the detailed implementation by walking through the code.
Motivation
Ever since the first bitcoin mining ASIC was released, many new Proof of Work algorithms have been created with the intention of being “ASIC-resistant”. The goal of “ASIC-resistance” is to resist the centralization of PoW mining power such that these coins couldn’t be so easily manipulated by a few players.
Ethereum's approach is to incentivize a geographically-distributed community of miners with a low barrier to entry on commodity hardware. As stated in the Yellow Paper:
It is from these premises that Ethash was designed.
5 years of experience with the Ethereum blockchain have demonstrated the success of our approach. This success cannot be taken for granted.
ProgPow restores Ethash' ASIC-resistance by extending Etash with a GPU-specific approach to the second path.
ProgPoW Overview
The design goal of ProgPoW is to have the algorithm’s requirements match what is available on commodity GPUs: If the algorithm were to be implemented on a custom ASIC there should be little opportunity for efficiency gains compared to a commodity GPU.
The main elements of the algorithm are:
The random sequence changes every
PROGPOW_PERIOD
(about 2 to 12 minutes depending on the configured value). When mining source code is generated for the random sequence and compiled on the host CPU. The GPU will execute the compiled code where what math to perform and what mix state to use are already resolved.While a custom ASIC to implement this algorithm is still possible, the efficiency gains available are minimal. The majority of a commodity GPU is required to support the above elements. The only optimizations available are:
These would result in minimal, roughly 1.1-1.2x, efficiency gains. This is much less than the 2x for Ethash or 50x for Cryptonight.
Rationale for PoW on Commodity Hardware
With the growth of large mining pools, the control of hashing power has been delegated to the top few pools to provide a steadier economic return for small miners. While some have made the argument that large centralized pools defeats the purpose of “ASIC resistance,” it’s important to note that ASIC based coins are even more centralized for several reasons.
While the goal of “ASIC resistance” is valuable, the entire concept of “ASIC resistance” is a bit of a fallacy. CPUs and GPUs are themselves ASICs. Any algorithm that can run on a commodity ASIC (a CPU or GPU) by definition can have a customized ASIC created for it with slightly less functionality. Some algorithms are intentionally made to be “ASIC friendly” - where an ASIC implementation is drastically more efficient than the same algorithm running on general purpose hardware. The protection that this offers when the coin is unknown also makes it an attractive target for a dedicate mining ASIC company as soon as it becomes useful.
Therefore, ASIC resistance is: the efficiency difference of specialized hardware versus hardware that has a wider adoption and applicability. A smaller efficiency difference between custom vs general hardware mean higher resistance and a better algorithm. This efficiency difference is the proper metric to use when comparing the quality of PoW algorithms. Efficiency could mean absolute performance, performance per watt, or performance per dollar - they are all highly correlated. If a single entity creates and controls an ASIC that is drastically more efficient, they can gain 51% of the network hashrate and possibly stage an attack.
Review of Existing PoW Algorithms
SHA256
The SHA algorithm is a sequence of simple math operations - additions, logical ops, and rotates.
To process a single op on a CPU or GPU requires fetching and decoding an instruction, reading data from a register file, executing the instruction, and then writing the result back to a register file. This takes significant time and power.
A single op implemented in an ASIC takes a handful of transistors and wires. This means every individual op takes negligible power, area, or time. A hashing core is built by laying out the sequence of required ops.
The hashing core can execute the required sequence of ops in much less time, and using less power or area, than doing the same sequence on a CPU or GPU. A bitcoin ASIC consists of a number of identical hashing cores and some minimal off-chip communication.
Scrypt and NeoScrypt
Scrypt and NeoScrypt are similar to SHA in the arithmetic and bitwise operations used. Unfortunately, popular coins such as Litecoin only use a scratchpad size between 32kb and 128kb for their PoW mining algorithm. This scratch pad is small enough to trivially fit on an ASIC next to the math core. The implementation of the math core would be very similar to SHA, with similar efficiency gains.
X11 and X16R
X11 (and similar X##) require an ASIC that has 11 unique hashing cores pipelined in a fixed sequence. Each individual hashing core would have similar efficiency to an individual SHA core, so the overall design will have the same efficiency gains.
X16R requires the multiple hashing cores to interact through a simple sequencing state machine. Each individual core will have similar efficiency gains and the sequencing logic will take minimal power, area, or time.
The Baikal BK-X is an existing ASIC with multiple hashing cores and a programmable sequencer. It has been upgraded to enable new algorithms that sequence the hashes in different orders.
Equihash
The ~150mb of state is large but possible on an ASIC. The binning, sorting, and comparing of bit strings could be implemented on an ASIC at extremely high speed.
Cuckoo Cycle
The amount of state required on-chip is not clear as there are Time/Memory Tradeoff attacks. A specialized graph traversal core would have similar efficiency gains to a SHA compute core.
CryptoNight
Compared to Scrypt, CryptoNight does much less compute and requires a full 2mb of scratch pad (there is no known Time/Memory Tradeoff attack). The large scratch pad will dominate the ASIC implementation and limit the number of hashing cores, limiting the absolute performance of the ASIC. An ASIC will consist almost entirely of just on-die SRAM.
Ethash
Ethash requires external memory due to the large size of the DAG. However that is all that it requires - there is minimal compute that is done on the result loaded from memory. As a result a custom ASIC could remove most of the complexity, and power, of a GPU and be just a memory interface connected to a small compute engine.
Specification
The DAG is generated exactly as in Ethash. All the parameters (ephoch length, DAG size, etc) are unchanged. See the original Ethash spec for details on generating the DAG.
ProgPoW can be tuned using the following parameters. The proposed settings have been tuned for a range of existing, commodity GPUs:
PROGPOW_PERIOD
: Number of blocks before changing the random programPROGPOW_LANES
: The number of parallel lanes that coordinate to calculate a single hash instancePROGPOW_REGS
: The register file usage sizePROGPOW_DAG_LOADS
: Number of uint32 loads from the DAG per lanePROGPOW_CACHE_BYTES
: The size of the cachePROGPOW_CNT_DAG
: The number of DAG accesses, defined as the outer loop of the algorithm (64 is the same as ethash)PROGPOW_CNT_CACHE
: The number of cache accesses per loopPROGPOW_CNT_MATH
: The number of math operations per loopThe value of these parameters has been tweaked between version 0.9.2 (live on the gangnum testnet) and 0.9.3 (proposed for Ethereum adoption). See this medium post for details.
PROGPOW_PERIOD
50
10
PROGPOW_LANES
16
16
PROGPOW_REGS
32
32
PROGPOW_DAG_LOADS
4
4
PROGPOW_CACHE_BYTES
16x1024
16x1024
PROGPOW_CNT_DAG
64
64
PROGPOW_CNT_CACHE
12
11
PROGPOW_CNT_MATH
20
18
The random program changes every
PROGPOW_PERIOD
blocks to ensure the hardware executing the algorithm is fully programmable. If the program only changed every DAG epoch (roughly 5 days) certain miners could have time to develop hand-optimized versions of the random sequence, giving them an undue advantage.Sample code is written in C++, this should be kept in mind when evaluating the code in the specification.
All numerics are computed using unsigned 32 bit integers. Any overflows are trimmed off before proceeding to the next computation. Languages that use numerics not fixed to bit lengths (such as Python and JavaScript) or that only use signed integers (such as Java) will need to keep their languages' quirks in mind. The extensive use of 32 bit data values aligns with modern GPUs internal data architectures.
ProgPoW uses a 32-bit variant of FNV1a for merging data. The existing Ethash uses a similar variant of FNV1 for merging, but FNV1a provides better distribution properties.
Test vectors can be found in the test vectors file.
ProgPow uses KISS99 for random number generation. This is the simplest (fewest instruction) random generator that passes the TestU01 statistical test suite. A more complex random number generator like Mersenne Twister can be efficiently implemented on a specialized ASIC, providing an opportunity for efficiency gains.
Test vectors can be found in the test vectors file.
The
fill_mix
function populates an array ofint32
values used by each lane in the hash calculations.Test vectors can be found in the test vectors file.
Like Ethash Keccak is used to seed the sequence per-nonce and to produce the final result. The keccak-f800 variant is used as the 32-bit word size matches the native word size of modern GPUs. The implementation is a variant of SHAKE with width=800, bitrate=576, capacity=224, output=256, and no padding. The result of keccak is treated as a 256-bit big-endian number - that is result byte 0 is the MSB of the value.
As with Ethash the input and output of the keccak function are fixed and relatively small. This means only a single "absorb" and "squeeze" phase are required. For a pseudo-code imenentation of the
keccak_f800_round
function see theRound[b](A,RC)
function in the "Pseudo-code description of the permutations" section of the official Keccak specs.Test vectors can be found in the test vectors file.
The inner loop uses FNV and KISS99 to generate a random sequence from the
prog_seed
. This random sequence determines which mix state is accessed and what random math is performed.Since the
prog_seed
changes only once perPROGPOW_PERIOD
it is expected that while miningprogPowLoop
will be evaluated on the CPU to generate source code for that period's sequence. The source code will be compiled on the CPU before running on the GPU.Test vectors can be found in the test vectors file.
The math operations that merges values into the mix data are ones chosen to maintain entropy.
Test vectors can be found in the test vectors file.
The math operations chosen for the random math are ones that are easy to implement in CUDA and OpenCL, the two main programming languages for commodity GPUs. The mul_hi, min, clz, and popcount functions match the corresponding OpenCL functions. ROTL32 matches the OpenCL rotate function. ROTR32 is rotate right, which is equivalent to
rotate(i, 32-v)
.Test vectors can be found in the test vectors file.
The flow of the inner loop is:
(loop % LANES)
is chosen as the leader for that loop iterationmix[0]
value modulo the number of 256-byte DAG entries is is used to select where to read from the full DAGDAG_LOADS
sequential words, using(lane ^ loop) % LANES
as the starting offset within the entry.prog_seed
andloop
come from the outer loop, corresponding to the current program seed (which is block_number/PROGPOW_PERIOD) and the loop iteration number.mix
is the state array, initially filled byfill_mix
.dag
is the bytes of the Ethash DAG grouped into 32 bit unsigned ints in litte-endian format. On little-endian architectures this is just a normal int32 pointer to the existing DAG.DAG_BYTES
is set to the number of bytes in the current DAG, which is generated identically to the existing Ethash algorithm.Test vectors can be found in the test vectors file.
The flow of the overall algorithm is:
hash32_t
targetRationale
((T.B.D. Review audits))
ProgPoW utilizes almost all parts of a commodity GPU, excluding:
Making use of either of these would have significant portability issues between commodity hardware vendors, and across programming languages.
Since the GPU is almost fully utilized, there’s little opportunity for specialized ASICs to gain efficiency. Removing both the graphics pipeline and floating point math could provide up to 1.2x gains in efficiency, compared to the 2x gains possible in Ethash, and 50x gains possible for CryptoNight.
Backwards Compatibility
This algorithm is not backwards compatible with the existing Ethash, and will require a fork for adoption. Furthermore, the network hashrate will halve since twice as much memory is loaded per hash.
Test Cases
progpow 0.9.2
The algorithm run on block 30,000 produces the following digest and result:
Additional test vectors can be found in the test vectors file.
progpow 0.9.3
Machine-readable test vectors
Additional test vectors can be found in the test vectors file.
progpow 0.9.4
Machine-readable test vectors ((T.B.D.))
Implementation
We Do Not recommend that this Proposal be deployed at this time. Rather it is being offered in the spirit of Ben DiFrancesco's compromise which for our purposes we state simply as,
This leaves open the possibility and threat of future deployment. Some of the authors are engaged in work to track what devices are mining our network. These and other efforts can provide information relevant to possible deployment.
Clients
Exchanges
Pools
License and Copyright
The ProgPoW algorithm and this specification are a new work. Copyright and related rights are waived via CC0.
The reference ProgPoW mining implementation located at ProgPOW is a derivative of ethminer so retains the GPL license.