70
$\begingroup$

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

$\endgroup$
  • 6
    $\begingroup$ What is the justification for "NP-complete problems or other brute force search problems will satisfy these requirements?" You don't have to believe or prove P=NP to find a significantly better way to solve an NP-complete class of problems. It might be, for example, that despite being NP-complete, over $99.9\%$ of the instances of a problem are easy. It might be that there is an obvious brute-force solution but there is also a much faster but still super-polynomial algorithm. $\endgroup$ – Douglas Zare May 15 '17 at 12:31
  • 4
    $\begingroup$ verret. The search space which one can go over in 30 minutes is typically a very small portion of the total search space, so knowing that a solution does not exist in a very small portion of the total search space does not give anyone a significant advantage. $\endgroup$ – Joseph Van Name May 16 '17 at 5:49
  • 10
    $\begingroup$ I notice this question has an open bounty. Will it be paid in Bitcoin? $\endgroup$ – Neal May 17 '17 at 19:01
  • 11
    $\begingroup$ @JosephVanName I'm confused by your interpretation of MO's reaction to this question as "hostility". With 55 upvotes, I estimate that this is in the top .5% of all questions in the site - the fact that it attracted several detailed, constructive, and enthusiastic answers is another very positive sign. Your own answer has been downvoted a couple of times, but there is a difference between critical feedback and hostile / unprofessional behavior, and I see no evidence of the latter. $\endgroup$ – Paul Siegel Aug 1 '17 at 12:01
  • 9
    $\begingroup$ @JosephVanName I did not claim that anyone provided constructive feedback to your answer, though the first comment appears at least to be thoughtful and relevant (whether or not it is correct). Constructive feedback is not a requirement for downvoting, and there are plenty of legitimate reasons for downvoting other than the mathematical content of an answer. For instance, providing a link with no explanation does not make for a particularly good answer; I didn't downvote in this case, but I can see why a reasonable person might. $\endgroup$ – Paul Siegel Aug 1 '17 at 12:29

13 Answers 13

22
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ Peter Shor and coauthors have discussed this question in the paper "Quantum money from knots." Proceedings 3rd Innovations in Theoretical Computer Science Conference, ACM, 2012. See the responses to the MO question, Applications of knot theory. In particular, see Peter's comments posted there. $\endgroup$ – Joseph O'Rourke May 17 '17 at 14:11
  • 3
    $\begingroup$ I am a bit concerned about the tunability of the difficulty this problem. Is there an easy way to tell how difficult it is to untie a knot without actually or attempting to untie? One way to solve this tunability problem is to make this similar to an optimization problem. For example, if multiple participants untie the knot or link in 10 minutes, then the participant who uses the least number of Reidemeister moves to untie the knot wins. If nobody unties the knot, then the participant with the equivalent knot with the fewest number of crossings wins. $\endgroup$ – Joseph Van Name May 17 '17 at 17:48
  • $\begingroup$ @JosephVanName You can do a bunch of small notes. For example, Bitcoin uses hashes, and it increases the number of hashes miners do over time. $\endgroup$ – PyRulez Jun 9 '17 at 0:10
  • 2
    $\begingroup$ What are these many real-life applications of unknotting? Do they overlap with the unknotting problems that would be a suitable proof-of-work? $\endgroup$ – Douglas Zare Jul 31 '17 at 4:24
  • 1
    $\begingroup$ This seems to be already discussed in cstheory.stackexchange.com/questions/32292/… $\endgroup$ – domotorp Dec 28 '17 at 20:23
15
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ @JosephVanName, you can vote it down if you'd like, and you explained why. But I'm sorry if I didn't make it clear that the Fiat-Shamir heuristic was intended to remove interaction; a miner would publish the entire transcript of what an interactive proof would be. This transcript may be large, but is still $O(\text{poly} n)$. I really like this question, I've learned a lot on my own by researching the topic. I think eprint.iacr.org/2017/203.pdf comes close to addressing many of your requirements, and they propose the Fiat-Shamir heuristic to remove interaction. $\endgroup$ – Mark S Jul 31 '17 at 21:08
  • 2
    $\begingroup$ I now withhold my voting on this answer for the time being. My opinion was premature. Sorry. $\endgroup$ – Joseph Van Name Jul 31 '17 at 21:29
13
+750
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Quoting Yoav: "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." $\endgroup$ – domotorp Jun 4 '17 at 19:00
  • 1
    $\begingroup$ I believe the requirement to be contradictory. One cannot hope for intrinsic value in solutions to randomly generated proof-of-work problems; only for value in the development of most efficient methods for solving them. $\endgroup$ – John Tromp Jun 5 '17 at 1:14
  • $\begingroup$ Well, that's exactly what I wrote in my first answer as well... Then in my second answer I've tried to overcome this difficulty. $\endgroup$ – domotorp Jun 5 '17 at 3:53
  • 6
    $\begingroup$ I don't think intrinsic value contradicts random generation. Randomly generate a sequence for a protein, then see if the most efficient configurations fit some receptors (or more concretely, you can imagine that afterward, the result can be translated as $0.05\%$ likely to cure cancer, $97.3\%$ likely to kill the patient). It may be of interest to search a very large space for proteins which have desirable properties. You can imagine that the problem is to compute properties of random algebraic curves. The collected data would show the distributions of genera or other statistics. $\endgroup$ – Douglas Zare Jul 3 '17 at 21:25
12
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suppose factorization can be used to further test the strength of the RSA cryptosystem. However, since the numbers to factor need to be generated automatically in a decentralized manner, one will not be able to prepare the factors of the numbers in advance. I suppose that this may be a solution to this issue. Natural numbers $x_{1},...,x_{r}$ are randomly generated using data from the previous blockchain. The winner is the entity who computes the most difficult factorization of some $x_{i}$ in the allotted amount of time. $\endgroup$ – Joseph Van Name May 23 '17 at 2:45
  • 2
    $\begingroup$ Cryptocurrencies are supposed to be decentralized entitites. Therefore, one should not constantly change the proof-of-work problems for the cryptocurrency. All of the proof-of-work problems should therefore be set in stone before the cryptocurrency is launched. If there is a change to the proof-of-work problem, then such a change should be done very seldomly. $\endgroup$ – Joseph Van Name May 23 '17 at 2:59
  • $\begingroup$ However, I am optimistic that many of the current cryptocurrencies can chance to useful proof-of-work problems simply because cryptocurrencies are still very new and have not yet stood the test of time, and therefore there will need to be some adjustments. Furthermore, new cryptocurrencies are being launched all the time, so perhaps a new cryptocurrency could use many proof-of-work problems instead of one. $\endgroup$ – Joseph Van Name May 23 '17 at 3:14
  • $\begingroup$ @Joseph Regarding factoring, I think there are many solutions to the problem that some numbers are easier to factor. I would personally recommend to award less money for solutions that are found fast. (So theoretically, if you find a solution and suspect that no one else will find one, then it's better to announce it later, but why would you suspect that? There should also be a cap on the award.) $\endgroup$ – domotorp May 23 '17 at 3:20
  • $\begingroup$ Yes. There are many solutions. Another way to determine the most difficult factorization would be for the miners to announce the hash of the concatenation of the solution with other data when they find it. If multiple entities find what happens to be the same solution, then the solution would be automatically disqualified since it is easy. $\endgroup$ – Joseph Van Name May 23 '17 at 3:30
10
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ First, you wrote, "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." (emphasis added). Second, logical reversibility is not, contrary to popular perception, a prerequisite for thermodynamic reversibility. A logically irreversible operation can be performed in a thermodynamically reversible way (see doi.org/10.1016/j.shpsb.2004.11.006 and arxiv.org/abs/1508.05319). $\endgroup$ – Yoav Kallus Jun 1 '17 at 17:58
  • 10
    $\begingroup$ Well, you think that chess endgames are silly. We all have our unpopular opinions. $\endgroup$ – Yoav Kallus Jun 2 '17 at 0:56
  • 5
    $\begingroup$ Don't worry. If I thought so I would have. $\endgroup$ – Yoav Kallus Jul 31 '17 at 1:51
  • 2
    $\begingroup$ Why the delete vote? $\endgroup$ – Joseph Van Name Oct 18 '17 at 21:48
  • 3
    $\begingroup$ Cryptocurrencies can also reward the development of the quantum computer; if you make a good quantum computer, then you will be allowed to take all abandoned bitcoins and all bitcoins from people who have not updated to a quantum safe digital signature algorithm yet. $\endgroup$ – Joseph Van Name Dec 5 '17 at 15:20
9
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How do we know a majority of the time is spent calculating the cellular automaton instead of computing hashes? One way to guarantee that a majority of the time is spent computing the cellular automaton is for the problem to be modified to "Given a string S, find strings T, along with a $16\times 16$-grid of bits U where at most 8 bits are 1 such that $f(S+T)\oplus U$ produces interesting life patterns." This way, a miner can use the same hash $f(S+T)$ over and over again while changing $U$ after every attempted solution. $\endgroup$ – Joseph Van Name Sep 22 '17 at 22:06
  • 1
    $\begingroup$ In practice, SHA-256 hashes are much cheaper to compute than running the cellular automaton (on a fast x86-64 machine, it takes about 1 microsecond to produce the hash, and 400 microseconds on average to run the cellular automaton and classify the results). $\endgroup$ – Adam P. Goucher Sep 22 '17 at 23:07
  • $\begingroup$ ok. So for now a CA will be easier to compute than SHA-256, but when CA ASICs come along, will SHA-256 still be much faster than the ASICs? $\endgroup$ – Joseph Van Name Sep 22 '17 at 23:14
  • 1
    $\begingroup$ Computing cellular automata is a very useful POW problem. After all, Bitcoin mining machines get really bored of computing SHA256 hashes all the time, and these Bitcoin mining machines therefore need more entertaining problems. I care about the Bitcoin mining machines and I do not want them to get bored of solving SHA256 hashes all the time. $\endgroup$ – Joseph Van Name Dec 11 '17 at 0:09
  • 2
    $\begingroup$ @JosephVanName If you know how to make computers able to distinguish between boring and entertaining, why spend time on problems as boring as cryptocurrency POW? $\endgroup$ – მამუკა ჯიბლაძე Dec 13 '17 at 5:44
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The Block being mined plus the nonce calculated generates (through some prefixed algorithm which generates a n gate boolean cct) a satisfiable cct. The nonce alongwith the cct input together constitute the answer. $\endgroup$ – ARi Aug 13 '17 at 17:29
7
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "similar to some court system"-and how will this be done in a completely decentralized and automated manner in such a way that the community can easily verify if the calculations are correct and always be in agreement? For whether predictions, which thermometers will be used? How will one select thermometers in an automated manner that guarantees consensus? Decentralization is the most important aspect of cryptocurrencies, and the purpose of using a proof-of-work problem in the first place is to achieve decentralization. $\endgroup$ – Joseph Van Name May 25 '17 at 22:56
  • $\begingroup$ @Joseph I'm no expert in bitcoin, but what happens there if someone claims to have found a nonce but the hash doesn't start with 0's? The difference is that verification is easier, but theoretically a gang of miners could form a syndicate and claim it's correct. Who has the final say? This question seems quite relevant as recently fact denying became quite popular at all levels. $\endgroup$ – domotorp May 26 '17 at 4:16
  • $\begingroup$ Mhm, I suppose that simply anyone can reject to accept a bitcoin whose hash is not valid, so you're right that the situation is quite different. I'll modify my answer. $\endgroup$ – domotorp May 26 '17 at 8:29
  • $\begingroup$ Even if one were to somehow make weather forecasting as a proof-of-work problem for cryptocurrencies (by having miners submit weather data to achieve decentralization). Keep in mind that there is already a market for weather prediction, so this proof-of-work problem will be just another subsidy for accurate weather prediction and hence no new markets will be created. $\endgroup$ – Joseph Van Name Jun 6 '17 at 13:39
6
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ The exact value of $\Omega$ is highly dependent on how it is encoded via a universal machine, just like the Halting Problem. (In computability theory, we [or at least I] have a habit of calling any left c.e. Martin-Löf random $\Omega$.) While I think Chaitin has a strong opinion that his encoding of $\Omega$ is the canonical one, I don't think that opinion is shared by many in the field. $\endgroup$ – Jason Rute May 19 '17 at 20:06
  • 2
    $\begingroup$ While this proof-of-work problem may have "intrinsic value" to a few theoretical mathematicians, I doubt that the cryptocurrency community will embrace this proof-of-work problem since I do not see any practical real-world applications coming from this problem. $\endgroup$ – Joseph Van Name May 20 '17 at 4:22
  • 1
    $\begingroup$ Universal inductive inference and compression are applications. $\endgroup$ – user76284 May 21 '17 at 19:40
  • 1
    $\begingroup$ Is this supposed to include a method for validating mathematical proofs? Suppose I prove that some program halts within $2^{2^{2^{100}}}$ steps. This is not that uncommon. How is this supposed to be verified? How do you address the fact that it is easy to determine whether a program halts for the vast majority of programs, but uncomputably hard on a few? $\endgroup$ – Douglas Zare Jul 3 '17 at 17:45
  • 2
    $\begingroup$ I don't understand what you mean by a proof on the lower bound of the length of the proof. That sounds much worse. What do you mean? And how do you address the issue that the vast majority of programs might halt quickly or quickly enter an obvious loop, while a tiny percentage are why the problem is unsolvable? $\endgroup$ – Douglas Zare Jul 3 '17 at 21:09
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.