What computational problems would be good proof-of-work problems for cryptocurrency mining?
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.
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:
- 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
- Miners compete to find a permanent for $d$ matrices in the pool, where $d$ is some difficulty target
- 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.
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...