23
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

I think the way to do this is to create a table of mosaic knots with a set of restrictions to disallow shortcuts. So a knot table is a set of knots that have a given property. The property below is being a prime knot.

Rolfsen Knot table

Now lets see a knot table made up of mosaic knots: a knot mosaic is a type of representation of knots which use tiles instead of being strings in a three dimentional space. Knot Mosaic Table

Now lets formally define what a knot mosaic is:

Mosaic Tiles

From https://arxiv.org/pdf/1602.03733.pdf A knot mosaic is the representation of a knot on an n × n grid composed of 11 tiles here are them below.

This is my starting point in asking you for a mosaic knot table with a set of restrictions. What I want to ask you is to give me a table with the following properties

  1. It must have at least one element with a crossing number $C$
  2. It must have at least element with dimension of $N$ by $M$
  3. It must be ambient isotopic to the knot $K$ that we send
  4. It must have a set of operations $O$ of cardinality $O_n$ that show that it is ambient isotopic to the knot $K$
  5. All operations must be unique
  6. You must give me the coordinates $CR$ of the operation on the knot itself.
  7. It must be encoded as a knot mosaic.

So lets encode the trefoil in a machine readable format. We take each tile and assign them a number (01-11). Using the programming language racket it will look like this

(define trefoil (array #[#[00 02 01 00]
                         #[02 10 09 01]
                         #[03 09 04 06]
                         #[00 03 05 04]] : Integer))

Which corresponds to $3_1$ in the above table by Rolfesen. Now, lets see a trivial task. Once again using racket

(struct braidcoin ([source_knot : (Matrix Integer)]
                   [target_knot : (Matrix Integer)]
                   [crossing_number : (Refine [n : Integer] (> n 0))]
                   [dimention : (Refine [n : Integer] (> n 0))]
                   [timestamp : date])

This would give us the trivial task which would be the trivial table would have only the prime knot $3_1$. The source and target knots in the above structure would be the same. The crossing number would be three. The dimension would be four by four.

So, now that we have established what the output should be. Now how do we tackle the generation of the problem?

So we know that under ambient isotopy that you can get to another knot diagram given another knot diagram in a finite set of reidmeister moves. So lets generate two random links. The task then we define is given two random links I want you to show that they are either equivalent by enumerating every possible knot that can be expressed or show that they are not equivaent by giving me a set of states or paths to a known knot in a table.

A way where we can improve the speed of knowing that a knot is in the table or not is by constructing a hash table with indices as the Alexander polynominal. Each instance would have the Alexander Polynominal computed for it and if they share the same Alexander polynominal it would be appended as an element to that table .

I have part of a working program at the following gist: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b

$\endgroup$
  • 3
    $\begingroup$ Given two large, random links, they are unlikely to be equivalent. And they probably won't have the same Alexander polynomial, which will let you prove that they are not equivalent in polynomial time. So the task is easy most of the time. I suspect it's extremely unlikely that you'll generate a genuinely hard example by taking random links. $\endgroup$ – Peter Shor May 17 '18 at 13:48
  • $\begingroup$ @PeterShor yes I recognize that. I don’t think I articulated this well but I am also making an arbitrary amount of these tasks when I am generating it to increase the hardness. Even with that occurring would that not make it harder ? $\endgroup$ – Joshua Herman May 17 '18 at 13:56
  • $\begingroup$ @PeterShor Also the certificate is not just that both knots are not equivalent but I want a set of knot moves to the unknot or to a knot that you could compute that it isn't ambient isotopic (such as the trefoil). $\endgroup$ – Joshua Herman May 17 '18 at 15:56
  • 1
    $\begingroup$ For "a known knot in a table," do you plan on having an exponential-sized table? Because there are exponentially many knots of a given size. $\endgroup$ – Peter Shor May 17 '18 at 16:05
  • $\begingroup$ Yes and no. The size of each instance of using knothash is bound by the cardinality of the Operation number and also a valid instance of a knot or link encoded as a knot mosaic. I plan on using these parameters to limit the amount of valid solutions so that the hardness of the problem is also a parameter. $\endgroup$ – Joshua Herman May 17 '18 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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