What computational problems would be good proof-of-work problems for cryptocurrency mining?

Question

What computational mathematics problems that could be used as proof-of-work problems for cryptocurrencies? To make this question easier to answer, I want proof-of-work systems that work in cryptocurrencies that contain many different kinds of proof-of-work problems (the use of many different kinds of proof-of-work problems is more secure than the use of only one type of proof-of-work problem) instead of proof-of-work systems that work in cryptocurrencies with only one kind of proof-of-work problem.

Background

To make things simple, cryptocurrency mining requires one to solve computational problems as a proof-of-work. For example, in Bitcoin, the miners must find data whose SHA-256 hash begins with many zeroes. Unfortunately, solutions to the proof-of-work problem for most cryptocurrencies have no intrinsic value in themselves, and these problems use up great amounts of resources and people have even made malware to solve these proof-of-work problems.

Mathematicians have a limited amount of computational resources and cryptocurrency mining could potentially supply mathematicians with a nearly unlimited amount of computational power. For example, cryptocurrency miners receive an equivalent of millions of dollars in revenue per day and they spend much computational power solving the problems required to mine these cryptocurrencies.

Requirements

Most computational mathematics problems are unsuitable as proof-of-work problems for cryptocurrencies. Here are some requirements and things we would like in such a problem.

1. $\textbf{Verifiable but intractible:}$ The problem must be difficult to solve but easy to verify. Many NP-complete problems will satisfy this requirement.

2. $\textbf{Tunability:}$ The difficulty of the problems must be fine-tunable. There should be a system in place that, given a positive real number $t$, automatically and efficiently selects a problem that can be solved on average in $t$ seconds without actually solving the problem. Optimization problems can easily be made to satisfy this requirement since with an optimization problem one can simply choose the best solution every 5 minutes or so (optimization problems may not be the best for cryptocurrencies though).

3. $\textbf{Intrinsic value:}$ The solution to the problems must have some intrinsic value. These solutions and not just the process of obtaining the solutions should be of a scientific, mathematical or practical interest.

4. $\textbf{Efficient automatic generation:}$ The problems must be automatically generated since cryptocurrencies in-general have no central authorities.

5. $\textbf{Solution tied to block and solver:}$ For example, in Bitcoin the information being hashed includes the person solving the problem along with other information. This way someone cannot steal someone else's solution.

The following traits are necessary only if there is one or a couple kinds of proof-of-work problem per cryptocurrency or there is no process to automatically remove broken proof-of-work problems.

i. $\textbf{Endless problems:}$ There must be a limitless amount of problems to solve so that a new problem could generated every few minutes.

ii. $\textbf{Unbreakability:}$ The class of problems should be “unbreakable”. The security of cryptocurrencies depends on the fact that no party should have a secret algorithm that quickly solves the problems and that no body is likely to develop such a secret algorithm in the future.

iii. $\textbf{Progress freeness:}$ Each individual problem must be “progress-free” in the following sense. If Alice works on the problem from noon and Alice has not found a solution by 12:30, then at 12:30 Alice will have no advantage over another participant who begins working on the problem at 12:30. In other words, the amount of time it takes to solve the given problem follows an exponential distribution.

iv. $\textbf{Pre-computation resistance:}$(observed by Loreno Heer in the comments) The proof-of-work problem should be “pre-computation resistant”. One way to obtain this desired property is to make the proof-of-work problem dependent on random data such as current transactions. One could also make future problems depend on previous solutions.

Other comments

I am slightly more interested in mathematical problems which have or may have future practical applications instead of problems which are only of a purely mathematical interest. In a best case scenario, I would like to see problems which may have cryptographic applications.

This question differs from this previous question since the previous question did not ask for problems which are specifically suitable as proof-of-work problems for cryptocurrency mining (and the answers given are not suitable as proof-of-work problems for cryptocurrency mining either).

Answer 1

Have you considered unknotting knots?

The problem would be finding a sequence of Reidemeister moves for a random link graph that reduces it to the unknot. In some cases, no such sequence would exist, but most random graphs are known to be unknotted under certain knotting algorithms: http://iopscience.iop.org/article/10.1088/1751-8113/49/40/405001/meta

Unknotting itself is in NP, as discussed here: Is there a polynomial-time algorithm for untangling the unknot?

Unknotting has many real-life applications. Furthermore, given a potential sequence of Reidemeister moves that might unknot the knot, it is quite easy to verify that it produces the unknot.

There may be some problems with this (maybe a secret fast algorithm in the works?), but if so, I'm sure someone else will comment.

Answer 2

Calculating the permanent of a small matrix is a computationally challenging problem, as discussed here, here, and here. See also the Wikipedia article.

Given an $n \times n$ matrix $A$, a naïve calculation of $\text{perm}(A)$ using the definition may require $|S_n|=n!$ multiplications. One of the best known algorithms is Ryser’s formula [Rys63], based on the inclusion-exclusion principle, requiring $O(2^n n^2)$ arithmetic operations.

Indeed, even deterministically verifying the statement $$k=\text{perm}(A)$$ may not be in $\text P$, that is, may not be polynomial in $n$. If such a language were in $\text P$, some very unlikely statements of computational complexity would follow.

However, as shown in [LFKN90] and refined by Babai, there exists an interactive proof that enables a prover $P$ to convince a polynomial-time bounded verifier $V$ of the above, with $O(n)$ steps of interaction, if the verifier were able to publicly toss a number of random coins. The [LFKN90] protocol involves the prover announcing coefficients of polynomials $f(x)$ corresponding to permanents of “minors” of the given graph. The random coin tosses are used to generate an element $x_i$ of $\mathbb{F_p}$ for some prime $p>n^4$; the verifier may verify statements such as $f(x_i)=k_i$.

To apply [LKFN90] to a cryptocurrency, the “miner” would be equated with the prover $P$, and other nodes would be equated with verifiers $V$.

[Mic94] taught how to remove the interaction in the random oracle model by applying the Fiat-Shamir heuristic to the proof, generating random coin-tosses in a non-interactive way. A cryptocurrency already has a large number of coins that are agreed to be random – namely, the merkle root of previous blocks.

As a proof-of-work based on calculating the permanent, the following protocol may be a starting point:

1. For block $b$, say $O(1)$ random $0-1$ matrices are added to a common pool. The matrices may be randomly generated based on hashes of previous blocks
2. Miners compete to find a permanent for $d$ matrices in the pool, where $d$ is some difficulty target
3. Once found, a miner follows [Mic94] to announce her proof, salting hashes of previous blocks with the coefficients of the [LFKN90] protocol to generate the random coin tosses used in the protocol

Calculating permanents of random matrices may have some intrinsic value in block-designs, matchings in bipartite graphs, symmetric tensors, etc. Furthermore, creating protocols for public verification of computation is, to me, an exciting area of research – the example given in the literature is verifying scientific computations done “in the cloud.”

As an aside, as taught in [Kil92] converting a (very long) proof string $\pi$ into a (succinct) commitment may be done by building a merkle-tree of the proof string, and committing to, i.e. publicly announcing, the root of the merkle-tree. Verification of a particular bit $\pi_i$ involves “following the path” from leaf-to-root. Importantly for a cryptocurrency, we shouldn’t burden the prover too much, and following [Kil92] to problems in $\text{NEXP}$ requires the miner to maintain the very long transcript $\pi$ in memory. Work since the late '90's has significantly reduced the burden on the prover, and I sense that there's a feeling that a true succinct non-interactive argument of knowledge may be just around the corner.

---

References

[LFKN90] C. Lund, L. Fortnow, H. Karloff, and N. Nissan. Algebraic methods for interactive proofs. 1990.

[Mic94] S. Micali. Computationally sound proofs. 1994.

[Kil92] J. Killian. A note on efficient zero-knowledge proofs and arguments. 1992.

[Rys63] J. H. Ryser. Combinatorial Mathematics. 1963.

Answer 3

Finding cycles in graphs is a standard graph theory problem that lends itself well to proof-of-work. See my Cuckoo Cycle project page at https://github.com/tromp/cuckoo which has tons of details, as well as bounties for improving the currently best implementations.

Of course, the specific pseudo-random graphs generated in Cuckoo Cycle have no practical use whatsoever...

Answer 4

I find this to be an excellent suggestion, though not sure all requirements can be satisfied. More specifically, 3 and 5 - if we randomly generate instances, then why would they have any intrinsic value? Would factoring large integers have any intrinsic value?

One example that I can think of is chess endgames. There is a growing database of which positions involving a few pieces are wins/draws. The problem is that the proof might be hard to verify, though probably not impossible to have a proof format that can be checked quite fast.

Also, if the bitcoin budget is in the millions, I think it would be nice to have a central board that would select every once in a while an important computational problem for whose solution there is a bounty of many bitcoins. At least I don't see anything wrong with this version of the proposal.

Answer 5

Here is a recent paper, which has been received positively in the cryptocurrency community. I will expand on this paper here.

While conventional hash functions do not allow one to construct very useful proof-of-work problems, if one replaces the hash function for the proof-of-work with a randomizing function specifically designed to be computed by reversible circuits, then the proof-of-work problem has practical use besides simply securing the blockchain. This proof-of-work problem will prompt the development of super-efficient reversible computers. Furthermore, these new proof-of-work problems will satisfy all of the requirements that one will want in a proof-of-work problem for cryptocurrencies that I have listed in the question.

What is reversible computing?

A bijective gate (such as the NOT, Toffoli, and Fredkin gates) is also called a reversible gate (and by definition every bijective gate must have the same number of input bits as output bits). A circuit is said to be reversible if all of its logic gates are reversible. As combinatorial circuits model ordinary computation, the reversible circuits model reversible computation. Any computation that can be efficiently carried out by an ordinary computer can also be reasonably efficiently computed using a reversible computer. For example, PSPACE=REVSPACE where REVSPACE refers to the problems which can be solved on a reversible computer with a polynomial amount of space.

Why reversible computing?

Landauer's principle states that erasing a bit always costs $k\cdot T\cdot\ln(2)$ energy where $k$ is the Boltzmann constant and $T$ is the temperature. Since $k=1.38064852\cdot 10^{-23}\cdot m^{2}\cdot kg\cdot s^{-2}\cdot K^{-1}$, we conclude that at $300 K$, erasing a bit costs $2.8 × 10^{−21}$ joules.

While conventional computing always costs energy since with conventional computing, one always has to erase information, there is most likely no lower limit to the efficiency of reversible computation since reversible computing does not erase any information. Since reversible computers will be more efficient than ordinary computers, reversible computers will not generate as much heat as ordinary computers, so reversible computers will be able to operate at much higher speeds than ordinary computers.

While a reversible computer should in theory be much more efficient than an irreversible computer, there are currently no reversible computers out in the market today which are more efficient than their irreversible counterparts.

If the proof-of-work problems for cryptocurrencies require one to solve problems designed for super efficient reversible computers, then corporations will have a great incentive to produce reversible integrated circuits which can quickly solve these problems without using so much energy.

A preliminary description of the proof-of-work problem

We shall now select a proof-of-work problem which should be carried out by a reversible computer just as easily as it is carried out by a classical computer. I therefore want the randomizing function to be computable on a reversible circuit without any ancilla.

For this proof-of-work problem, suppose that $f:\{0,1\}^{324}\rightarrow\{0,1\}^{324}$ is a function computed by a circuit which consists solely of reversible gates and where the circuit does not contain any garbage or ancilla bits.

Suppose that $\mathbf{k}$ is the hash of the block header and $\alpha$ is an adjustable 324 bit number. Then the proof-of-work problem for the current block shall be to find some 68 bit string $\mathbf{x}$ such that $f(\mathbf{k}\#\mathbf{x})\leq\alpha$ where $\#$ denotes the concatenation operation.

Answer 6

Discussion of the prospect of a cryptocurrency based on cellular automata prompted me to start developing the Catagolue project in the summer of 2014. The proof-of-work system was deliberately chosen to enable a cryptocurrency to be built upon it:

Given a string $S$, find some string $T$ such that the $16 \times 16$ pseudorandom pattern $f(S+T)$ yields interesting objects when run to stabilisation in Conway's Game of Life.

To make it intractable to reverse-engineer, the function $f$ is defined by taking the SHA-256 hash of the string to give a sequence of 256 bits, which are written in the obvious order in a $16 \times 16$ box to produce a pseudorandom Life pattern. 'Interesting' has not been formally defined, but any sensible definition (e.g. 'a sufficiently rare pattern of period $\geq 5$') will work for these purposes.

Since its conception, just over $9 \times 10^{12}$ initial conditions have been simulated, producing slightly more than $2 \times 10^{14}$ separate objects of 117 000 distinct types. An estimated $10^6$ CPU-hours have been committed to the project without any cryptocurrency or other financial reward being attached (and over a third of these were by contributors other than me). One of the more interesting objects to appear spontaneously was this one.

This proof-of-work satisfies points 1, 4, and 5. Point 2 is also satisfiable: in order to set the difficulty of the problem, modify the criterion of 'interesting' to exclude a given proportion of randomly-chosen soups. Choosing that threshold is straightforward by examining the empirical object frequency tables on Catagolue itself.

Arguably, it also satisfies point 3: whilst the problem is not of general mathematical interest, it is still sufficiently interesting to the 100 or so people who have contributed CPU time to the distributed search without any extrinsic reward.

Answer 7

I don't see how you will have a problem which is progress free but still in NP(requirement 7); or any kind of problem that is suitable for your purpose for that matter. To see why this seems unlikely lets consider the solution space for your problem as I start and when I have progressed in an arbitrary algorithm that searches the solution space. when I start the entire solution space given by your problem formulation is unexplored, However as soon as I start searching I know the best value and what solutions I have investigated before. This reduces the solution space. If I don't do this I run the risk of repeating solutions to no avail. therefore I suspect there is no optimal time non -stochastic algorithm which does not change the solution space in the sense that it records its own progress. Therefore I suspect there is no problem for which a solution can be found for sure that has the desired property. This in combination with the requirement that the problem should be scalable(so there is no guarantee that only large problems will be used) makes it hard to have any real solutions to this problem

If your drop this requirement, travelling salesman problems for random regions might be interesting since This could help transport companies alot while offering a huge potential number of problems that are highly customizable. However use would be somewhat limited since it would be quite random what TSPs would be solved. However It would be quite nice to have a database in which you enter some cities and a maximum distance and get a route between them that is shorter than that distance. you could for example use the 3000 largest cities on earth and compute random TSPs with those.

Another possibility is approximations of the Navier stokes equations for typical requirements. But this is somewhat outside my field

Not being able to coordinate which problems are solved when is a major problem for the usefullness, so all problems that have these kind of properties should be problems which are in general very useful. I think TSP problems with a pool of the 3000 largest cities in the world would have this property, but still alot of computations would be useless. minimum k-cut problems for computer design could also be useful as long as you can find a sub set of these problems that have a high chance of being useful, which I think is possible, but I know too little abnout chip design to find it myself. same thing for SAT problems.

I am not sure how to guarantee property 8, so I have not included that in my analysis.

edited for (hopefully) more relevance

A useful problem for cryptography could be SAT since boolean statisfiability can be easily re-written into most cryptography problems. However, the problem is still that there is no central authority to generate the problem and so finding a relevant SAT problem is much harder than it appears. One idea maybe is to not have one authority but instead some huge database of useful SAT instances where one is randomly pulled from. If the randomizer is apt precomputation is impossible.

Answer 8

Let me have another go, because I really love this question. Essentially it's like a SETI@home project - without going into details, let's just consider the theoretical model that some signals arrive from a source that is sufficiently random and then we have to do some computation on it to get some data. (If you prefer groundhogs to E.T., the weather forecast also has this property.) Then whoever computes the data first, will get a coin.

The main issue I see with similar models is that they don't satisfy property 1 (verifiability). I thought this could be solved through some court, but as pointed out by Joseph in the comments to the first version of this answer, this would lead to problems. So instead, we should pick a problem that can be verified. Unfortunately, I don't know much about what SETI was doing with the data, but probably there was something that they were looking for (and now I don't mean aliens, but some signals). So we could say that every 10 minutes there's a data that comes from space, the first person to find a signal wins a coin, but the data might contain no signal, in which case nobody is rewarded - I don't see an issue with this happening sometimes.

Answer 9

Has anyone considered improving a best lower bound on $\Omega_U$ by finding small programs $p_i$ that halt, where $\Omega_U$ is a Chaitin halting probability of a universal prefix-free Turing machine $U$?

That is, $$\Omega_U=\sum_{p\:halts}2^{-|p|}$$

For block $B_i$, miners $j$ announce a set $P_{ij}\subset P_U$ of programs $p_{ijk}\in P_{ij}$. Miners may be rewarded $\sum 2^{-|p_{ijk}|}$ coins when the network validates the halting. Accordingly, proof-of-work for smaller programs may be more rewarding than for larger programs, as they provide a greater lower bound on $\Omega_U$, and may have more evidence of proof-of-work.

The chain may include an ever-increasing sequence of convergents to $\Omega_U$.

A cousin to this idea involves finding proofs in Peano Arithmetic of small statements of number theory.

---

A little more formally, consider a prefix-free Turing machine $U$ that takes, as inputs, (prefix-free) binary strings $p$ and produces, as outputs, proofs $\pi$. If the program $p$ halts, then $|\pi|$ is bounded.

Let $P_U$ be the set of all prefix-free strings accepted by $U$, let $P\subset P_U$ be the set of all programs that halt. There is a function $P\rightarrow\mathbb{N}$ given by $|p|$, and another function $P\rightarrow\mathbb{N}$ given by $|\pi|$.

Let $B_i$ be the $i^{th}$ block in a blockchain $B$. The block $B_i$ includes (hashes of) recent financial transactions (a ledger), a hash of block $B_{i-1}$ to point back to (keeping the chain), a set $P_i\subset P$ of recently mined new programs that halt, and a hash of the proofs $\pi_{ik} $ for each $p_{ik}\in P_i$. We require $P_i\cap\bigcup_{l=0}^{i-1} P_l=\emptyset$; that is, we only accept new programs that had not yet been known to halt.

For block $i$, a miner $j$ may possess a set $P_{ij}$ of programs $p_{ijk}\in P_{ij}$, along with proof strings $\pi_{ijk}$. That is, the miner has possession of $(p_{ijk},\pi_{ijk})$.

Tunability: Every ten minutes or so, miner $j$ announce the subset $P_{ij}$ of programs, the total proof-of-work $\Gamma_{ij}=\sum|\pi_{ijk}|$, along with a hash of recent financial transactions that are to be confirmed. The clock can be set to be ten minutes, or otherwise the first miner $j$ that has a proof-of-work $\Gamma_{ij}>d$, where $d$ is some difficulty set to be an average of about ten minutes, may announce their proof. If the miner is the “winner” by having the largest sum $\sum 2^{-|p_{ijk}|}$ in ten minutes, or the earliest announcement of a $\sum|\pi_{ijk}|>d$, then the proof-of-work for block $B_i$ will be defined to be $\Gamma_i:=\Gamma_{ij}$.

Intractability: If $\Gamma_i>\sum_{r=2}^s\Gamma_{i-r}$ for some $s$, then the miner has done more work than at least the last $s$ blocks combined; accordingly, the miner may be suspected of having worked on a fraudulent chain of transactions. Other nodes may validate or quarantine the last $s$ blocks that the miner $j$ claims to be adding to, to make sure the blockchain contains valid transactions for the previous $s$ or so blocks.

For example, for block $i$ for a given $n$, let the “busiest beaver” function $bb(n,i)$ from $\mathbb{N}\times\mathbb{N}$ to $\bigcup P_i$ be the program $p_{bb}$ such that $|\pi_{bb}|$ is maximal. Finding a new $p_{bb}$ may lead to a significant requirement of cross-validation by other nodes to make sure it does not include fraudulent transactions. If $p_{bb}$ is announced as part of a fraudulent chain, it may not be accepted by the network. Honesty may be enforced because announcements require the total proof-of-work $\Gamma_{ij}$ to be stated. If $\Gamma_{ij}$ is large, then that may draw suspicion onto miner $j$. If the announced $P_{ij}$ includes a hash back of the already-validated chain most recent chain, then it may be easier to verify the hashes of the chains, so if one discovers a $p_{bb}$ for some size $n=|p_{bb}|$ through honest behavior, then one is rewarded at least $2^{-n}$ coins faster.

Choice of problems: Because programs must be newly found to halt, i.e. $p_{ijk}\not\in\cup_{l=0}^{i-1}P_l$, then one may choose to work on whatever smaller program is within one’s capability. Indeed, even CPU’s may sell their work to pools that include ASIC’s. CPU’s may find the “trivial many” larger programs that halt quickly, while ASIC’s hunt for the “vital few” smaller programs that take significant time to halt.

Validation: Proofs may be “validated” with a probabilistically checkable proof, if the network can agree on a way to generate a sequence $a$ of $q$ random coin flips, where $a_i\in\{0,1\}$. Although I am not sure, I think the PCP theorem suggests that the total number of coin flips $q$ needed to validate that all programs $p_{ijk}$ halt only grows polylogarithmically with $\sum|\pi_{ijk}|$. The coins may be generated based on previous and/or future hashes (such as SHA hashes) of transactions. A fraudulent prover may come up with many dummy small transactions to have the random coin flips $a_i$ come up her way, but that may be as difficult as cracking the SHA hash.

Progress Freeness: If $|p|$ is large enough, it is unlikely that two miners are working on the same program, as the total number of programs grows exponentially with $|p|$. For very large $|p|$, ASIC’s may not be motivated to hunt for halting. For smaller $|p|$, there may be a race amongst ASIC’s to find, for example, a $p_{bb}$. For medium-sized $|p|$, if an ASIC miner $j$ did not find a program that halts this time, then she may still find that a program that she has been continually running halts at a later time, thus her time spent previously may not be wasted. This is dissimilar to, say, finding nonce’s on SHA256.

Endless Problems: Because there are an endless number of programs whose halting status is unknown, there are an endless number of programs to choose from. However, the total number of MathCoins that may be mined is bounded above by $1/2$, as $\Omega_U$ is normal in base $2$ and one is only awarded $2^{-|p|}$ coins.

Intrinsic Value: An intrinsic value of bounds on $\Omega_U$ may be low (see comments); however, some of this may be translated to “cousin” problems of finding proofs of small statements in Peano Arithmetic, or any other incomplete theory. (“Truly remarkable proofs” may still not fit into the margins.)

Unbreakability Because the halting problem is, in general, undecidable, no party can have a secret algorithm that quickly solves problems. Having access to a program that generates only a finite number of bits to $\Omega_U$, hence even “secret programs” have small value. I think this is the strength to the proposal, to be "provably" unbreakable in this regard. Any incomplete theory is similar in this regard: Peano Arithmetic proofs, minimal Kolmogorov complexity as suggested in the comments, word problems in group theory, determining whether two finite simplicial complexes are homeomorphic, etc.

Answer 10

In 1996 Pascal Koiran showed that, assuming the Generalized Riemmann Hypothesis, Hilbert's Nullstellensatz is in $\mathsf{AM}$ over the complex numbers $\mathbb{C}$. That is, given a system $S$ of polynomial equations: $$f_1[x_1, x_2, \cdots x_n]= f_2[x_1, x_2, \cdots x_n]= \cdots f_m[x_1, x_2, \cdots x_n]=0$$ a powerful Merlin can convince a polynomial Arthur that $S$ is satisfiable over $\mathbb{C}$.

Koiran achieved this by showing that, assuming GRH, there is a $z$ of order $O(\text{exp}(mn))$ such that there are enough primes $p\le z$ with $S$ satisfiable modulo $p$ iff $S$ is satisfiable over $\mathbb{C}$. Similarly, Koiran showed that if $S$ is not satisfiable over $\mathbb{C}$, there are no more than half as many primes $p'$ such that $S$ is satisfiable modulo $p'$.

Koiran's Arthur-Merlin protocol involves:

• Arthur picking a random hash function $H$, along with a random number $y\le z$, and providing $H$ and $y$ to Merlin,

• Merlin finding a prime $t$ such that $H(x)=y$, along with a solution $(a_1, a_2, \cdots , a_n)\in (\mathbb{Z}/t\mathbb{Z})^n$, and

• Arthur verifying $H(t)=y$ and $(a_1, a_2, \cdots , a_n)\in (\mathbb{Z}/t\mathbb{Z})^n$ satisfies $S$.

This may lend itself to a proof-of-work to solve nullstellensatz problems that partially invert a hash, similar to the bitcoin proof-of-work.

If we identify Merlin as the miner and $t$ as the nonce, we may set $y$ to be fixed as a run of consecutive $0$'s in a hash, similar to bitcoin. Any good cryptographic hash, such as the $\mathsf{sha256}$ hash used in bitcoin, may suffice, as long as the number of consecutive $0$'s is correct.

Given a system of polynomial equations $S$ and a payload $B$, where the payload includes the Merkle-root of financial transactions, miner ID's, the previous hashes, and other ways to tie the solution to the block and solver, a proof-of-work might include:

• Miners calculating a first hash $H(B)$.

• Miners competing to find a prime $t$ close to the number represented by the first couple of bits of the first hash $H(B)$ such that $S$ is satisfiable modulo $t$, along with the satisfying witness $(a_1, a_2, \cdots a_n)$. The proof-of-work also requires a second hash $H(t)$ begins with the target difficulty $\sim mn\:0's$.

• Once found, miners announcing on the P2P network the payload $B$, along with the primes $t$ and the witness $(a_1, a_2, \cdots a_n)$.

• A hash of the present solution may be used to encode a system of polynomial equations $S_{next}$ to be solved for the next block, or the next system of polynomials may be decided through some other means.

If $S$ is not actually solvable, then another problem could be worked on if after a while no prime is found.

Answer 11

Just to point out this is already implemented in primecoin.

Primecoin network searches for special prime number chains known as Cunningham chains and bi-twin chains. The distribution of these prime chains are not well-understood currently as even for its simplest case twin primes their infinite existence is not proven.

Answer 12

It is shown in http://eprint.iacr.org/2017/203.pdf that you can convert many nice problems to challenges, and in https://cstheory.stackexchange.com/a/39902/419 that any problem can be converted into a challenge having certain nice properties.

Answer 13

Community Wiki just to spitball some ideas

---

Around July 2018, the hash rate of Bitcoin - the number of hashes per second - has been hovering around $45$ million Terahashes/$s$. Further, the order of the $3\times 3\times 3$ Rubiks Cube group is, famously, $43,252,003,274,489,856,000$. Thus, in a sense, as of now the entire Bitcoin mining network effectively does about as many hashes per second as the number of permutations of the Rubik's cube.

One unsolved problem related to Rubik's cubes asks for the mixing time $\tau$ under standard Singmaster moves - e.g., the number of random $\langle U,D,L,R,F,B\rangle$ twists - under the quarter turn or half turn metric. A rough guess is that after about $40$ or so half-turn moves, starting from the initial (solved) position, each one of the $|G|=43,252,003,274,489,856,000$ positions is equally likely. A cryptocurrency could probably be set to establish this, at least with high probability.

For example,

• Miners would convert their Merkle-root plus nonce pair into a word $g$ of Rubik's Cube moves, of $40$ moves, through some standard and agreed-upon encoding (e.g. $U=00,L=11$...)
• Miners apply their $g$ to a solved cube to generate a new permutation (Rubik's cube position)
• Miners cryptographically hash this permutation, salted with the previous block's hash
• The first miner to find and announce a word that hashes to less than or equal to $m/|G|$ (for some moving difficulty target $m\ge 1$) gets the coinbase

As $m$ gets closer to $1$, if $\tau$ is much greater than $40$ it will be harder and harder for miners to find a word $g$ which will be able to be hashed onto the low value, because they will only be exploring a strict subset of the Cayley graph.