Knot Recognition as a Proof of Work

Question

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?

Answer 1

If there is an Arthur-Merlin protocol for knottedness similar to the [GMW85] and [GS86] 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] proposed an Arthur-Merlin protocol for knottedness, but unfortunately there was an error and they withdrew their claim.

[Kup11] 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 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.