22
votes
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, ...
15
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
14
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
13
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
11
votes
Accepted
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
9
votes
What problem would you base your mathcoin on?
Apologies if this answer is nitpicky and diverges slightly from the questions intent, but this particular soft question appears to warrant a soft answer.
Implicit in your term "mathcoin" are ...
Community wiki
9
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
7
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
7
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
6
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 $...
5
votes
Which hard mathematical problems do you have to solve to earn bitcoins ?
Another way to earn bitcoin is not to mine them, but to have them wired to you from other bitcoin accounts. The transactions are signed using ECDSA. So if you solve the discrete logarithm problem in ...
3
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
3
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
2
votes
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
1
vote
What computational problems would be good proof-of-work problems for cryptocurrency mining?
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 ...
Community wiki
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
bitcoins × 6cryptography × 4
soft-question × 1
sequences-and-series × 1
computational-complexity × 1
knot-theory × 1
gm.general-mathematics × 1
teaching × 1
experimental-mathematics × 1
quantum-computation × 1