NextPOW

Proof of work that creates useful ASICs

Changing the BCH proof-of-work entails complex tradeoffs far beyond the scope of this work. The NextPOW algorithm is deployed in this experimental chain to prevent ASIC use, rather than as a serious candidate for deployment to Bitcoin Cash. However, if BCH chooses to change the proof-of-work, these ideas should be considered.

Rationale

Background

Every algorithm can be implemented on an ASIC – a CPU, GPU, or RAM is itself an ASIC! “ASIC” is just a general term for any custom chip, however for the rest of this article we will use the term “ASIC” to mean a chip or set of chips that have been specifically designed to mine a cryptocurrency, and “COTS” (commercial off the shelf) to refer to commodity hardware programmed for mining.

Some algorithms are more “amenable” to the creation of an ASIC. This concept can be more formally defined as the ratio of the ASIC performance/watt verses COTS performance/watt. This ratio needs to justify the expense and risk of developing and fabricating ASICs.

Since all POW algorithms are inherently parallelizable because they search via random checking for a solution across a large space, once an algorithm is instantiated in hardware, it can be easily replicated up to chip capacity. Therefore, intuitively, the algorithm that is takes less on-chip real-estate, the fewest chips, and less developer effort is more ASIC friendly.

Existing Algorithms

The Bitcoin double SHA256 algorithm is very ASIC friendly. Its a “1 page of code” iterative algorithm that takes very little memory and employs simple logic operations.

Some efforts have been made to make algorithms more ASIC resistant. Particular strategies are to increase the required on-chip real-estate, require multi-chip solutions (different process technologies mean that you can’t efficiently put “RAM” on “CPU” ASICs, for example), and make development complex.

Ethereum’s “memory-hard” algorithm uses a lot of RAM because commodity RAM is state-of-the-art – if a better RAM was built, it would be sold as RAM, not as a mining ASIC. However, a board design that closely couples efficient processors with low latency RAM in a tight physical space can outperform general purpose computers.

It has been proposed to design an algorithm where the Intel processor is the most efficient ASIC design. Essentially, such an algorithm would use most or all of the Intel’s CISC instruction set to ensure that any separately designed ASIC would also need to essentially include all the elements of a general purpose computer to implement it. This strategy both increases the development complexity and the on-chip real-estate of the algorithm.

These efforts attempt to discourage the development of ASICs, but the profit potential remains hard to overcome. Additionally, these efforts assume that ASICs are “bad”, but this idea is debatable. ASICs represent a large financial commitment to a network, and that commitment implies stewardship. They also prevent general purpose CPUs from being used. The world’s CPUs can be seen as a huge amount of capacity that can be used to attack the blockchain, and then return to their prior use without any financial loss.

NextPOW Inverts the reasoning

NextPOW questions the fundamental assumption that ASICs are “bad” and instead asks “what if we use the profit potential to encourage the development of ASICs that we want?”

In particular, let’s force any ASIC developer to solve the problem of signature validation and UTXO lookup. These are the two most time consuming tasks in transaction and block validation (although an ASIC that provides a highly parallelized bitcoin script executing CPU would be perfect). A fast hardware solution to these two problems would remove all node performance and scalability concerns, making the blockchain limited solely by network capacity.

Algorithm

Quickly deployed algorithm

NextPOW currently only includes Schnorr signature generation as a proof-of-concept. Since the main complexity in signature generation and validation is elliptic curve multiplication, this is pretty good.

• Given the block’s hash (double sha256 of the block header): hash
• Calculate h1, the sha256(hash)
• Use hash as a private key (POW fails if it is invalid)
• Sign h1 resulting in sig
• powhash = sha256(sig)
• If powhash <= target, return true, else false (normal POW ‘target’ comparison)

Possible new algorithm

But it would be better to force the ASIC designer to implement as close to signature verification as possible to make the additional cost of exposing signature verification as low as possible.

Let’s review Schnorr signature verification:

• Given:
  32-byte message m, public key point P, signature: (32-byte r, scalar s)

1. Signature is invalid if s >= n or r >= p.
2. Compute scalar e = Hash(r || compressed§ || m) mod n.
3. Compute point R = s * G - e * P.
4. Reject if R is infinity or R.y is not a quadratic residue.
5. Signature is valid if the serialization of R.x equals r.

This algorithm can be transformed into a POW puzzle as follows:

32-byte block hash m, public key point P = PubKey(sha256(m)), scalar s = sha256(sha256(m)), scalar r = sha256(s)

1. Invalid POW if s >= n or r >= p.
2. Compute scalar e = sha256(r || compressed§ || m) mod n.
3. Compute point R = s * G - e * P.
4. Invalid POW if R is infinity or R.y is not a quadratic residue.
5. Return sha256(R.x, R.y)