<p>If there is an <em>Arthur-Merlin</em> protocol for knottedness similar to the <a href="https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf" rel="noreferrer">[GMW85]</a> and <a href="http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/goldwasser-Sipser.pdf" rel="noreferrer">[GS86]</a> Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic.</p>

<p>In more detail, as is well known in the Graph Non Isomorphism protocol of [GMW85], Peggy the prover wishes to prove to Vicky the verifier that two (rigid) graphs $G_0$ and $G_1$ on $V$ vertices are not isomorphic.  Vicky may secretly toss a random coin $i\in\{0,1\}$, along with other coins to generate a permutation $\pi\in\ S_V$, and may present to Peggy a new graph $\pi(G_i)$.  Peggy must deduce $i$.  Clearly Peggy is only able to do this if the two graphs are not isomorphic.</p>

<p>Similarly, and more relevant for the purposes of a <em>proof-of-work</em>, as taught by [GS86] an <em>Arthur-Merlin</em> version of the same protocol includes Arthur agreeing with Merlin on $G_0$, $G_1$, given as for example adjacency matrices. Arthur randomly picks a hash function $H:\{0,1\}^*\rightarrow\{0,1\}^k$, along with an image $y$.  Arthur provides $H$ and $y$ to Merlin.  Merlin must find a $(i,\pi)$ such that $H(\pi(G_i))=y$.</p>

<p>That is, Merlin looks for a preimage of the hash $H$, the preimage being a permutation of one of the two given adjacency matrices.  As long as $k$ is chosen correctly, if the two graphs $G_0$ and $G_1$ are not isomorphic then there will be a higher chance that a preimage will be found, because the number of adjacency matrices in $G_0 \cup G_1$ may be twice as large than if $G_0\cong G_1$.</p>

<p>In order to convert the above [GS86] protocol to a proof-of-work, identify <em>miners</em> as Merlin, and identify <em>other nodes</em> as Arthur.  Agree on a hash $H$, which, for all purposes, may be the $\mathsf{SHA256}$ hash used in Bitcoin.  Similarly, agree that $y$ will always be $0$, similar to the Bitcoin requirement that the hash begins with a certain number of leading $0$’s. </p>

<ul>
<li><p>The network agrees to prove that two rigid graphs $G_0$ and $G_1$ are not isomorphic.  The graphs may be given by their adjacency matrices</p></li>
<li><p>A miner uses the link back to the previous block, along with her own Merkle root of financial transactions, call it $B$, along with her own nonce $c$, to generate a random number $Z=H(c\Vert B)$</p></li>
<li><p>The miner calculates $W= Z\:mod\: 2V!$ to pick $(i,\pi)$</p></li>
<li><p>The miner confirms that  $\pi(G_i)\neq G_{1-i}$ - that is, to confirm that the randomly chosen $\pi$ is not a proof that the graphs are isomorphic</p></li>
<li><p>If not, the miner calculates a hash $W=H(\pi(G_i))$</p></li>
<li><p>If $W$ begins with the appropriate number of $0$’s, then the miner “wins” by publishing $(c,B)$</p></li>
<li><p>Other nodes can verify that $Z=H(c\Vert B)$ to deduce $(i,\pi)$, and can verify that $W=H(\pi(G_i))$ begins with the appropriate difficulty of $0$’s</p></li>
</ul>

<p>The above protocol is not perfect, some kinks I think would need to be worked out.  For example, it's not clear how to generate two random graphs $G_0$ and $G_1$ that satisfy good properties of rigidity, for example, nor is it clear how to adjust the difficulty other than by testing for graphs with more or less vertices.  However, I think these are probably surmountable. </p>

<p>But for a similar protocol on <em>knottedness</em>, replace random permutations on the adjacency matrix of one of the two graphs $G_1$ and $G_2$ with some other random operations on knot diagrams or grid diagrams... or something.  I don’t think random Reidemeister moves work, because the space becomes too unwieldy too quickly.</p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.176.4721&amp;rep=rep1&amp;type=pdf" rel="noreferrer">[HTY05]</a> proposed an Arthur-Merlin protocol for knottedness, but unfortunately there was an error and they withdrew their claim. </p>

<p><a href="https://arxiv.org/abs/1112.0845" rel="noreferrer">[Kup11]</a> showed that, assuming the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$, and mentions that this also puts knottedness in $\mathsf{AM}$, but I’ll be honest I don’t know how to translate this into the above framework; the $\mathsf{AM}$ protocol of [Kup11] I think involves finding a rare prime $p$ modulo which a system of polynomial equations is $0$.  The prime $p$ is rare in that $H(p)=0$, and the system of polynomial equations corresponds to a representation of the knot complement group.</p>

<p>Of note, see <a href="https://mathoverflow.net/questions/269786/what-computational-problems-would-be-good-proof-of-work-problems-for-cryptocurre/270003#270003">this answer</a> to a similar question on a sister site, which also addresses the utility of such "useful" proofs-of-work.</p>

<hr>

<p><strong>References:</strong></p>

<p>[GMW85] Oded Goldreich, Silvio Micali, and Avi Wigderson.  Proofs that Yield Nothing but their Validity, 1985.</p>

<p>[GS86] Shafi Goldwasser, Michael Sipser.  Private Coins versus Public Coins in Interactive Proof Systems, 1986.</p>

<p>[HTY05]  Masao Hara, Seiichi Tani, and Makoto Yamamoto.  UNKNOTTING is in $\mathsf{AM} \cap \mathsf{coAM}$, 2005.</p>

<p>[Kup11] Greg Kuperberg.  Knottedness is in $\mathsf{NP}$, modulo GRH,  2011.</p>

CC BY-SA 3.0
2017-10-07T05:01:56.220Z
What about random Markov moves?
http://mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
CC BY-SA 4.0
2018-05-18T19:42:55.353Z
Note that this answer confuses AM with the Proof of Work portion of bitcoin so the answer can’t actually be performed.
Joshua Herman
CC BY-SA 3.0
2017-10-29T00:03:58.707Z
Also you can consider knots as graphs that are signed graphs that are four valence. So you just have to enforce that restriction on G1 and G2
Joshua Herman
CC BY-SA 3.0
2017-10-30T02:32:52.600Z
Here is a reduction of a quandle coloring to a SAT instance.  https://arxiv.org/pdf/1505.06595.pdf
Joshua Herman
CC BY-SA 3.0
2017-11-02T00:23:25.063Z
yes it determines if you have an over or under crossing. See https://en.wikipedia.org/wiki/Medial_graph
Joshua Herman
CC BY-SA 3.0
2017-11-05T16:52:50.743Z
Would this help for testing for ridigity ? Looks like you only have to construct a laman graph which is easy in 2D (and knots are planar graphs).
http://www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman
CC BY-SA 3.0
2017-11-05T17:01:54.517Z
To test for it you need to use a pebble graph.

https://en.wikipedia.org/wiki/Pebble_game
Joshua Herman
CC BY-SA 3.0
2017-11-06T02:40:50.037Z
The $B_2$ braid group has a homomorphism to the cyclic group.
https://groupprops.subwiki.org/wiki/Braid_group
Joshua Herman
CC BY-SA 3.0
2017-11-06T12:49:32.990Z
Also, the general case of computing graph automorphism is in NP there is a good enough way to compute the automorophism group.

https://en.wikipedia.org/wiki/Graph_automorphism

https://math.stackexchange.com/questions/340001/how-to-prove-a-graph-asymmetric#514514

http://users.cecs.anu.edu.au/~bdm/nauty/

https://en.wikipedia.org/wiki/Erdős–Rényi_model
Joshua Herman
CC BY-SA 3.0
2017-11-07T17:48:43.167Z
See nauty https://web.cs.dal.ca/~peter/software/pynauty/html/intro.html
Joshua Herman
CC BY-SA 3.0
2017-09-27T01:51:03.233Z
2017-11-05T16:25:23.777Z
2017-11-05T16:25:23.777Z
Mark S
<p>Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion. </p>

<p>Is it possible to use a Decision problem in Knot Theory such as Knot recognition and make it into a proof of work function? Also has anyone done this before? Also, when we have this Proof of Work function will it be more useful than what is being currently computed?</p>

CC BY-SA 3.0
2015-08-16T14:51:53.500Z
You might be interested in this related question over on the bitcoin SE: [Is there a way to set up proof-of-work systems without doing useless work?](http://bitcoin.stackexchange.com/q/331/46)
Artem Kaznatcheev
CC BY-SA 3.0
2015-08-16T15:19:02.003Z
@ArtemKaznatcheev Thanks ill look into that.
Joshua Herman
CC BY-SA 3.0
2015-10-06T23:28:51.287Z
see also [why hasnt there been encryption algorithm based on NP hard problems](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard) / [cs.se]
vzn
<cc.complexity-theory><reference-request><cr.crypto-security><algebraic-topology>
Knot Recognition as a Proof of Work
Joshua Herman
# Knot Recognition as a Proof of Work

(Asked by: username_0 on 2015-08-16)

Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion.

Is it possible to use a Decision problem in Knot Theory such as Knot recognition and make it into a proof of work function? Also has anyone done this before? Also, when we have this Proof of Work function will it be more useful than what is being currently computed?

**Tags:** cc.complexity-theory, reference-request, cr.crypto-security, algebraic-topology

> **Comments:**
> **username_1**: You might be interested in this related question over on the bitcoin SE: [Is there a way to set up proof-of-work systems without doing useless work?](http://bitcoin.stackexchange.com/q/331/46)  
> **username_0**: @ArtemKaznatcheev Thanks ill look into that.  
> **username_2**: see also [why hasnt there been encryption algorithm based on NP hard problems](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard) / [cs.se]  

---

## 1 answers

### Answer by username_3 on 2017-09-27. Score: 8

If there is an *Arthur-Merlin* protocol for knottedness similar to the [[GMW85]](https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf) and [[GS86]](http://crypto.cs.mcgill.ca/~crepeau/COMP647/2007/TOPIC01/goldwasser-Sipser.pdf) Arthur-Merlin protocols for Graph Non Isomorphism, then I believe such a cryptocurrency proof-of-work could be designed, wherein each proof-of-work shows that two knots are not likely to be equivalent/isotopic.

In more detail, as is well known in the Graph Non Isomorphism protocol of [GMW85], Peggy the prover wishes to prove to Vicky the verifier that two (rigid) graphs $G\_0$ and $G\_1$ on $V$ vertices are not isomorphic. Vicky may secretly toss a random coin $i\in\{0,1\}$, along with other coins to generate a permutation $\pi\in\ S\_V$, and may present to Peggy a new graph $\pi(G\_i)$. Peggy must deduce $i$. Clearly Peggy is only able to do this if the two graphs are not isomorphic.

Similarly, and more relevant for the purposes of a *proof-of-work*, as taught by [GS86] an *Arthur-Merlin* version of the same protocol includes Arthur agreeing with Merlin on $G\_0$, $G\_1$, given as for example adjacency matrices. Arthur randomly picks a hash function $H:\{0,1\}^\*\rightarrow\{0,1\}^k$, along with an image $y$. Arthur provides $H$ and $y$ to Merlin. Merlin must find a $(i,\pi)$ such that $H(\pi(G\_i))=y$.

That is, Merlin looks for a preimage of the hash $H$, the preimage being a permutation of one of the two given adjacency matrices. As long as $k$ is chosen correctly, if the two graphs $G\_0$ and $G\_1$ are not isomorphic then there will be a higher chance that a preimage will be found, because the number of adjacency matrices in $G\_0 \cup G\_1$ may be twice as large than if $G\_0\cong G\_1$.

In order to convert the above [GS86] protocol to a proof-of-work, identify *miners* as Merlin, and identify *other nodes* as Arthur. Agree on a hash $H$, which, for all purposes, may be the $\mathsf{SHA256}$ hash used in Bitcoin. Similarly, agree that $y$ will always be $0$, similar to the Bitcoin requirement that the hash begins with a certain number of leading $0$’s.

* The network agrees to prove that two rigid graphs $G\_0$ and $G\_1$ are not isomorphic. The graphs may be given by their adjacency matrices
* A miner uses the link back to the previous block, along with her own Merkle root of financial transactions, call it $B$, along with her own nonce $c$, to generate a random number $Z=H(c\Vert B)$
* The miner calculates $W= Z\:mod\: 2V!$ to pick $(i,\pi)$
* The miner confirms that $\pi(G\_i)\neq G\_{1-i}$ - that is, to confirm that the randomly chosen $\pi$ is not a proof that the graphs are isomorphic
* If not, the miner calculates a hash $W=H(\pi(G\_i))$
* If $W$ begins with the appropriate number of $0$’s, then the miner “wins” by publishing $(c,B)$
* Other nodes can verify that $Z=H(c\Vert B)$ to deduce $(i,\pi)$, and can verify that $W=H(\pi(G\_i))$ begins with the appropriate difficulty of $0$’s

The above protocol is not perfect, some kinks I think would need to be worked out. For example, it's not clear how to generate two random graphs $G\_0$ and $G\_1$ that satisfy good properties of rigidity, for example, nor is it clear how to adjust the difficulty other than by testing for graphs with more or less vertices. However, I think these are probably surmountable.

But for a similar protocol on *knottedness*, replace random permutations on the adjacency matrix of one of the two graphs $G\_1$ and $G\_2$ with some other random operations on knot diagrams or grid diagrams... or something. I don’t think random Reidemeister moves work, because the space becomes too unwieldy too quickly.

[[HTY05]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.176.4721&rep=rep1&type=pdf) proposed an Arthur-Merlin protocol for knottedness, but unfortunately there was an error and they withdrew their claim.

[[Kup11]](https://arxiv.org/abs/1112.0845) showed that, assuming the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$, and mentions that this also puts knottedness in $\mathsf{AM}$, but I’ll be honest I don’t know how to translate this into the above framework; the $\mathsf{AM}$ protocol of [Kup11] I think involves finding a rare prime $p$ modulo which a system of polynomial equations is $0$. The prime $p$ is rare in that $H(p)=0$, and the system of polynomial equations corresponds to a representation of the knot complement group.

Of note, see [this answer](https://mathoverflow.net/questions/269786/what-computational-problems-would-be-good-proof-of-work-problems-for-cryptocurre/270003#270003) to a similar question on a sister site, which also addresses the utility of such "useful" proofs-of-work.

---

**References:**

[GMW85] Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that Yield Nothing but their Validity, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems, 1986.

[HTY05] Masao Hara, Seiichi Tani, and Makoto Yamamoto. UNKNOTTING is in $\mathsf{AM} \cap \mathsf{coAM}$, 2005.

[Kup11] Greg Kuperberg. Knottedness is in $\mathsf{NP}$, modulo GRH, 2011.

> **Comments:**
> **username_0**: What about random Markov moves? http://mathworld.wolfram.com/MarkovMoves.html  
> **username_0**: Also you can consider knots as graphs that are signed graphs that are four valence. So you just have to enforce that restriction on G1 and G2  
> **username_0**: Here is a reduction of a quandle coloring to a SAT instance.  https://arxiv.org/pdf/1505.06595.pdf  
> **username_0**: yes it determines if you have an over or under crossing. See https://en.wikipedia.org/wiki/Medial_graph  
> **username_0**: Would this help for testing for ridigity ? Looks like you only have to construct a laman graph which is easy in 2D (and knots are planar graphs). http://www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf  
> **username_0**: To test for it you need to use a pebble graph.  https://en.wikipedia.org/wiki/Pebble_game  
> **username_0**: The $B_2$ braid group has a homomorphism to the cyclic group. https://groupprops.subwiki.org/wiki/Braid_group  
> **username_0**: Also, the general case of computing graph automorphism is in NP there is a good enough way to compute the automorophism group.  https://en.wikipedia.org/wiki/Graph_automorphism  https://math.stackexchange.com/questions/340001/how-to-prove-a-graph-asymmetric#514514  http://users.cecs.anu.edu.au/~bdm/nauty/  https://en.wikipedia.org/wiki/Erdős–Rényi_model  
> **username_0**: See nauty https://web.cs.dal.ca/~peter/software/pynauty/html/intro.html  
> **username_0**: Note that this answer confuses AM with the Proof of Work portion of bitcoin so the answer can’t actually be performed.  

---

