Skip to content

NexaPOW

Proof of work that creates useful ASICs

Rationale

Background

Every algorithm can be implemented on an ASIC -- a CPU, GPU, or RAM is itself an ASIC! An Application-Specific Integrated Circuit or "ASIC" is just a general term for any custom chip designed for a particular use rather than intended for general purpose use, 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 paralleliseable 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.

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

Genesis Algorithm

NexaPOW 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. In this description the || operation denoted byte string concatenation.

  • Start with the block's candidateHash (this is the hash of the header of the block not including the nonce).
  • Calculate miningHash which is the double_sha256(candidateHash || nonce)
  • Calculate h1, the sha256(miningHash)
  • Use miningHash 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)

Proposal

Nexa will hard fork to a new Proof-of-Work with the following properties.

BlindedPOW

See BlindedPOW.

Both Generator and General ECC multiplication

POW should incorporate both of these operations. It currently incorporates generator multiplication only as part of signing.

UTXO Lookup

Deployment of a UTXO commitment system that allows succinct existence proofs (typically 32*log(number of UTXOs) bytes) into the block header will enable a POW algorithm to require lookups into this database.

Given some input entropy, for example E = Hash256(nonce, header_hash),

A proposed puzzle is to find the D = Hash256(E, nearest idem in utxo set to E, contents of that utxo). By including as a prefix of this hashed data, the miner cannot pre-calculate D for every element in the UTXO set. It must access a real UTXO set.

Proof-of-work validation will require the UTXO data and existence proof to be provided to validating headers-only (e.g. SPV) clients. However, this data can be discarded by these clients once the header's POW is validated.

As an additional discouragement to attacks that eschew UTXO lookup, this operation should be executed first (and additional operations should use data produced by this one as input).

Elliptic Curve Multiplication

As in the algorithm launched at genesis, the POW will contain at least on ECC multiplication, preferably contained within a signature validation.

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)

  • Signature is invalid if s >= n or r >= p.

  • Compute scalar e = Hash(r || compressed(P) || m) mod n.
  • Compute point R = s * G - e * P.
  • Reject if R is infinity or R.y is not a quadratic residue.
  • 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(P) || 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)