Reconhecimento de nós como prova de trabalho

Atualmente, o bitcoin possui um sistema de prova de trabalho (PoW) usando SHA256. Outras funções de hash usam gráficos de uso do sistema de prova de trabalho, inversão parcial da função de hash.

É possível usar um problema de Decisão na Teoria do Nó, como o reconhecimento do Nó, e transformá-lo em uma prova de função de trabalho? Também alguém já fez isso antes? Além disso, quando tivermos essa função de Prova de trabalho, será mais útil do que o que está sendo computado atualmente?

Se houver um protocolo Arthur-Merlin para atar semelhante aos protocolos [GMW85] e [GS86] Arthur-Merlin para não isomorfismo de grafos, acredito que uma prova de trabalho com criptomoeda possa ser projetada, em que cada prova de trabalho mostra que dois nós provavelmente não são equivalentes / isotópicos.

Mais detalhadamente, como é bem conhecido no protocolo Graph Non Isomorphism de [GMW85], Peggy, o provador, deseja provar a Vicky o verificador de que dois gráficos (rígidos) e G 1 nos vértices V não são isomórficos. Vicky pode secretamente jogar uma moeda aleatório i ∈ { 0 , 1 } , juntamente com outras moedas para gerar uma permutação π ∈ S V , e pode apresentar-Peggy um novo gráfico π ( L i ) . Peggy deve deduzir i . Claramente, Peggy só pode fazer isso se os dois gráficos não forem isomórficos.$G_0$$G_1$$V$$i\in\{0,1\}$$\pi\in\ S_V$$\pi(G_i)$$i$

Da mesma forma, e mais relevante para os fins de uma prova de trabalho , conforme ensinado por [GS86] uma versão Arthur-Merlin do mesmo protocolo, inclui Arthur concordando com Merlin em , G 1 , dado como, por exemplo, matrizes de adjacência. Arthur escolhe aleatoriamente uma função de hash H : { 0 , 1 } ∗ → { 0 , 1 } k , juntamente com uma imagem y . Arthur fornece H e y para Merlin. Merlin deve encontrar um ( i , π $G_0$$G_1$$H:\{0,1\}^*\rightarrow\{0,1\}^k$$y$$H$$y$$(i,\pi)$tal que .$H(\pi(G_i))=y$

Ou seja, Merlin procura uma pré-imagem do hash , a pré-imagem sendo uma permutação de uma das duas matrizes de adjacência fornecidas. Desde que k seja escolhido corretamente, se os dois gráficos G 0 e G 1 não forem isomórficos, haverá uma chance maior de que uma pré-imagem seja encontrada, porque o número de matrizes de adjacência em G 0 ∪ G 1 pode ser duas vezes mais grande do que se G 0 ≅ G 1 .$H$$k$$G_0$$G_1$$G_0 \cup G_1$$G_0\cong G_1$

Para converter o protocolo [GS86] acima em uma prova de trabalho, identifique os mineradores como Merlin e outros nós como Arthur. Concorde com um hash , que, para todos os fins, pode ser o hash S H A 256 usado no Bitcoin. Da mesma forma, concorda que y sempre será 0 , similar à exigência Bitcoin que o hash começa com um certo número de líder 0 ‘s.$H$$\mathsf{SHA256}$$y$$0$$0$

• A rede concorda em provar que dois gráficos rígidos e G 1 não são isomórficos. Os gráficos podem ser dados por suas matrizes de adjacência$G_0$$G_1$

• Um mineiro usa o link de volta para o bloco anterior, junto com sua própria raiz de transações financeiras Merkle, chame-o de , junto com seu próprio nonce c , para gerar um número aleatório Z = H ( c − B $B$$c$$Z=H(c\Vert B)$

• O mineiro calcula escolher ( i , π $W= Z\:mod\: 2V!$$(i,\pi)$

• O mineiro confirma que - isto é, para confirmar que o π escolhido aleatoriamente não é uma prova de que os gráficos são isomórficos$\pi(G_i)\neq G_{1-i}$$\pi$

• Caso contrário, o mineiro calcula um hash $W=H(\pi(G_i))$

• Se começar com o número apropriado de 0 , o mineiro "vence" publicando ( c , B $W$$0$$(c,B)$

• Outros nodos podem verificar que para deduzir ( i , π ) , e pode verificar que W = H ( π ( L i ) ) inicia-se com a dificuldade apropriado de 0 ‘s$Z=H(c\Vert B)$$(i,\pi)$$W=H(\pi(G_i))$$0$

O protocolo acima não é perfeito, acho que algumas distorções precisam ser resolvidas. Por exemplo, não está claro como gerar dois gráficos aleatórios e G 1 que satisfazem boas propriedades de rigidez, por exemplo, nem está claro como ajustar a dificuldade além de testar gráficos com mais ou menos vértices. No entanto, acho que essas são provavelmente superáveis.$G_0$$G_1$

Mas, para um protocolo semelhante sobre o nó , substitua permutações aleatórias na matriz de adjacência de um dos dois gráficos e G 2 por algumas outras operações aleatórias em diagramas de nós ou diagramas de grade ... ou algo assim. Não acho que movimentos aleatórios de Reidemeister funcionem, porque o espaço se torna muito pesado e rápido demais.$G_1$$G_2$

[HTY05] propôs um protocolo Arthur-Merlin para atar nós, mas infelizmente houve um erro e eles retiraram sua alegação.

[Kup11] mostrou que, assumindo a hipótese de Riemann generalizada, knottedness está em , e menciona que este também coloca knottedness em Um M , mas eu vou ser honesto eu não sei como traduzir isso no quadro acima; o A M protocolo de [Kup11] Eu acho que envolve encontrar um raro nobre p modulo que um sistema de equações polinomiais é 0 . O prime p é raro em que H ( p ) = 0 , e o sistema de equações polinomiais corresponde a uma representação do grupo complemento do nó.$\mathsf{NP}$$\mathsf{AM}$$\mathsf{AM}$$p$$0$$p$$H(p)=0$

De notar, consulte esta resposta a uma pergunta semelhante em um site irmão, que também aborda a utilidade de tais provas de trabalho "úteis".

Referências:

[GMW85] Oded Goldreich, Silvio Micali e Avi Wigderson. Provas de que nada mais são do que sua validade, 1985.

[GS86] Shafi Goldwasser, Michael Sipser. Moedas Privadas versus Moedas Públicas em Interactive Proof Systems, 1986.

[HTY05] Masao Hara, Seiichi Tani e Makoto Yamamoto. UNKNOTTING está em , 2005.$\mathsf{AM} \cap \mathsf{coAM}$

Greg Kuperberg. O nó está em , módulo GRH, 2011.$\mathsf{NP}$

Eu acho que a maneira de fazer isso é criar uma tabela de nós de mosaico com um conjunto de restrições para proibir atalhos. Portanto, uma tabela de nós é um conjunto de nós que possuem uma determinada propriedade. A propriedade abaixo está sendo um nó primordial.

Agora vamos ver uma tabela de nós composta de nós de mosaico: um mosaico de nós é um tipo de representação de nós que usam azulejos em vez de serem cordas em um espaço tridimensional.

Agora vamos definir formalmente o que é um mosaico de nós:

De https://arxiv.org/pdf/1602.03733.pdf Um mosaico de nós é a representação de um nó em uma grade n × n composta de 11 peças aqui estão abaixo.

Este é o meu ponto de partida para solicitar uma tabela de nós em mosaico com um conjunto de restrições. O que eu quero perguntar é para me dar uma tabela com as seguintes propriedades

1. Ele deve ter pelo menos um elemento com um número de cruzamento $C$
2. Deve ter pelo menos elemento com dimensão por $N$$M$
3. Deve ser ambiente isotópico para o nó que enviamos$K$
4. $O$$O_n$$K$
5. Todas as operações devem ser únicas
6. $CR$
7. Deve ser codificado como um mosaico de nós.

Então, vamos codificar o trevo em um formato legível por máquina. Pegamos cada peça e atribuímos a eles um número (01-11). Usando a raquete da linguagem de programação, será parecido com este

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

$3_1$

(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])

$3_1$

Então, agora que estabelecemos qual deve ser o resultado. Agora, como lidamos com a geração do problema?

Portanto, sabemos que, sob isotopia do ambiente, você pode obter outro diagrama de nós, dado outro diagrama de nós em um conjunto finito de movimentos reidmeister. Então, vamos gerar dois links aleatórios. A tarefa que definimos recebe dois links aleatórios. Quero que você mostre que eles são equivalentes, enumerando todos os nós possíveis que podem ser expressos ou mostre que eles não são equivalentes, fornecendo-me um conjunto de estados ou caminhos para um nó conhecido em uma mesa.

Uma maneira de melhorar a velocidade de saber que um nó está na mesa ou não é construindo uma tabela de hash com índices como o polinômio de Alexander. Cada instância teria o Alexander Polynominal calculado para ele e se eles compartilharem o mesmo Alexander Polynominal, seria anexado como um elemento para essa tabela.

Tenho parte de um programa de trabalho na seguinte lista: https://gist.github.com/zitterbewegung/4152b322eef5ecccdcf3502e8220844b