A POW problem that can incentivize the energy efficient CNOT computer.

So in my previous posts, I have talked about a cryptocurrency POW which I call R5 which will incentivize the construction of the reversible computer. The POW R5 however does not incentivize the early stages of reversible computation when it is difficult to construct energy efficient implementations of reversible gates. My solution to this problem is to develop a new cryptocurrency POW problem which I shall temporarily call Slimeland (I will think of a better name in the future, I promise).

Incentivizing CNOT circuits instead of full-blown reversible circuits

So recall that the CNOT gate is the logic gate $(x,y)\mapsto(x,x\oplus y)$. Since the CNOT gate is a linear transformation, the CNOT gate is not universal for reversible computation. The goal of Slimeland is to incentivize the construction of a circuit composed mainly of CNOT gates. There are several reasons why a CNOT gate circuit should be easier to construct than a full-blown reversible circuit including the following:

  1. The CNOT gate is not universal for reversible computation.
  2. The CNOT gate acts on only two bits while universal reversible gates must act on at least 3 bits.
  3. The CNOT gate is linear.

It is therefore safe to assume that the research and development costs for developing an energy efficient reversible circuit composed almost exclusively of CNOT gates will be far less than that of developing a reversible circuit composed mainly of universal gates. Therefore, if one can construct a cryptocurrency POW problem that will incentivize the development of the energy reversible circuit composed mainly of CNOT gates, then energy efficient circuits that efficiently compute the CNOT gate will be developed very soon in order to quickly receive a return on investment.

Problem description

Suppose that $f$ is a suitable function. Suppose that $m,n$ are natural numbers and $D$ is an adjustable real number. Then he objective of the POW problem Slimeland is to find a $m$ bit hash $k$ along with an $n$ bit string $x$ so that $f(k||x)<2^{m+n}/D$. The function $f$ should be composed mostly of CNOT gates. However, since the CNOT gate is linear, the function $f$ cannot be composed exclusively of CNOT gates.

  1. The most efficient circuit for computing the function $f$ should consist solely of reversible gates without resorting to any ancilla or garbage bits.
  2. The circuit for the function $f$ should have a very high ratio of CNOT gates to non-linear gates in order to incentivize the construction of energy circuits composed mainly of CNOT gates.
  3. The circuit for the function $f$ needs to have enough non-linear gates to be cryptographically secure.
  4. The function $f$ should be as efficiently verifiable as possible.

Properties 2-4 are at odds with each other, so it is a challenge to construct a function $f$ that satisfies these conditions.

The internal testing technique

So the internal testing technique is method that I have come up with that can ensure that a cryptocurrency remains secure even if the cryptographic security of its POW problem is questionable.

Suppose that a cryptocurrency has Problem A as its POW problem. Suppose furthermore that Problem A has an adjustable level of security (the level security of symmetric cryptosystems can be adjusted simply by adding more rounds). Then a cryptocurrency applying the internal testing technique for Problem A will have two POW problems which we shall denote by Problem $A_{test}$ and Problem $A_{secure}$. Suppose that $N$ is an adjustable natural number. Then $A_{test}$ will have security level $N$ while $A_{secure}$ will have security level $3N$. Problem $A_{test}$ will also be weakened in other ways. While the security level for $A_{test}$ is decreased, the difficulty of $A_{test}$ will be increased (for example to 1000 times the difficulty of $A_{secure}$) so that it is not feasible for a miner to solve Problem $A_{test}$ using a brute force attack, and a miner must therefore solve $A_{test}$ by partially breaking its security. If $A_{test}$ is solved too often (for example, if $A_{test}$ is solved for more than one percent of all blocks), then the underlying cryptocurrency will automatically increment the number $N$ by one. As a security measure, the blocks for which $A_{test}$ is solved cannot be too close together.

Using the internal testing technique, the security of the underlying cryptocurrency POW problem will automatically be adjusted in case of any advancement in cryptanalytic techniques. By using the internal testing technique, Slimeland can remain secure even though the circuit used that solves Slimeland is mostly composed of the linear CNOT gates.

Leave a Reply

Your email address will not be published. Required fields are marked *

− one = nine