Reconhecimento de nós como prova de trabalho

23

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?

Joshua Herman
fonte
8
Você pode estar interessado nesta questão relacionada no bitcoin SE: Existe uma maneira de configurar sistemas de prova de trabalho sem fazer um trabalho inútil?
Artem Kaznatcheev
@ArtemKaznatcheev Obrigado mal olhar para isso.
Joshua Herman

Respostas:

7

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.G0G1Vi{0,1}π SVπ(Gi)Eu

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 , π )G0 0G1H:{0 0,1}{0 0,1}kyHy(Eu,π)tal que .H(π(GEu))=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 0G 1 pode ser duas vezes mais grande do que se G 0G 1 .HkG0 0G1G0 0G1G0 0G1

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.HSHUMA256y0 00 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ênciaG0 0G1

  • 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 )BcZ=H(cB)

  • O mineiro calcula escolher ( i , π )W=Zmod2V!(i,π)

  • O mineiro confirma que - isto é, para confirmar que o π escolhido aleatoriamente não é uma prova de que os gráficos são isomórficosπ(Gi)G1iπ

  • Caso contrário, o mineiro calcula um hash W=H(π(Gi))

  • Se começar com o número apropriado de 0 , o mineiro "vence" publicando ( c , B )W0(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 ‘sZ=H(cB)(i,π)W=H(π(Gi))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.G0G1

Mas, para um protocolo semelhante sobre o , 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.G1G2

[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ó.NPAMAMp0pH(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.AMcoAM

Greg Kuperberg. O nó está em , módulo GRH, 2011.NP

Mark S
fonte
1
E os movimentos aleatórios de Markov? mathworld.wolfram.com/MarkovMoves.html
Joshua Herman
Além disso, você pode considerar os nós como gráficos assinados com quatro valências. Então você só tem que impor essa restrição G1 e G2
Joshua Herman
Aqui está uma redução de uma coloração de quandle em uma instância SAT. arxiv.org/pdf/1505.06595.pdf
Joshua Herman
sim, determina se você tem uma passagem acima ou abaixo. Veja en.wikipedia.org/wiki/Medial_graph
Joshua Herman
Isso ajudaria a testar a ridicidade? Parece que você só precisa construir um gráfico de Laman que seja fácil em 2D (e nós são gráficos planares). www3.cs.stonybrook.edu/~jgao/CSE590-fall05/notes/lecture3.pdf
Joshua Herman
1

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.

Mesa de nó de Rolfsen

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. Tabela do mosaico do nó

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

Azulejo mosaico

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 MNM
  3. Deve ser ambiente isotópico para o nó que enviamosK
  4. OOnK
  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))

31

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

31

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

Joshua Herman
fonte
3
Dado dois grandes links aleatórios, é improvável que sejam equivalentes. E eles provavelmente não terão o mesmo polinômio Alexander, o que permitirá provar que eles não são equivalentes no tempo polinomial. Portanto, a tarefa é fácil na maioria das vezes. Suspeito que seja extremamente improvável que você gere um exemplo genuinamente difícil usando links aleatórios.
quer
@ PeterShor sim, eu reconheço isso. Eu não acho que articulei isso muito bem, mas também estou fazendo uma quantidade arbitrária dessas tarefas ao gerá-las para aumentar a dureza. Mesmo com isso ocorrendo, isso não tornaria as coisas mais difíceis?
Joshua Herman
@PeterShor Além disso, o certificado não é apenas que ambos os nós não são equivalentes, mas eu quero que um conjunto de nós se mova para o nó ou para um nó que você possa calcular que não seja isotópico do ambiente (como o trevo).
Joshua Herman
1
Para "um nó conhecido em uma tabela", você planeja ter uma tabela de tamanho exponencial? Porque existem exponencialmente muitos nós de um determinado tamanho.
Peter Shor
Sim e não. O tamanho de cada instância do uso do knothash é limitado pela cardinalidade do número da Operação e também por uma instância válida de um nó ou link codificado como um mosaico do nó. Planejo usar esses parâmetros para limitar a quantidade de soluções válidas, de modo que a dureza do problema também seja um parâmetro.
Joshua Herman