As provas de trabalho podem ser verificadas probabilisticamente?

Estou espreitando por um tempo; Esta é minha primeira postagem aqui. Sinto muito se minha pergunta está mal formada ou mal formatada. Essa pergunta surgiu de algumas idéias de outra pergunta de um site irmão.

Questão

Devido à natureza de uma blockchain, um grande número de lançamentos de moedas publicamente aceitáveis pode ser gerado - ou seja, os hashes dos blocos anteriores podem ser acordados pela rede para serem sorteados aleatoriamente $\{0,1\}$ .

Por conseguinte, alguém tentou criar uma solução para o problema dos generais bizantinos para uma blockchain, em que uma prova de trabalho é um problema de decisão em $NEXP$ ou $PSPACE$ , e a prova é verificada probabilisticamente , usando hashes de blocos anteriores quando a moeda pública é lançada?

Motivação

Vi discussões on-line tentando melhorar a prova de trabalho de criptomoedas, por exemplo, encontrando testemunhas de $NP$ problemas

Um provador que encontra testemunha de um $NP$ O problema pode anunciar publicamente a testemunha para provar que ela fez o trabalho.

Se houvesse um conjunto estático comum de $NP$ problemas, digamos $TSPs$ de subconjuntos do $n$ maiores cidades da Terra, anunciando a testemunha para garantir bloqueio $i$ significa que qualquer pessoa pode pegar a mesma testemunha e anexar o trabalho a outra corrente, o que não protege a corrente.

Se a verificação fosse uma prova de conhecimento nulo, o mundo (além do provador) talvez nunca precise saber o que a testemunha realmente era.

No entanto, como observado por outros, como as criptomoedas são sistemas ponto a ponto sem confiança, tentar manter essa testemunha com zero conhecimento pode ser difícil em um sistema ponto a ponto sem confiança.

Por exemplo, se um provador encontrar uma solução para um dos $TSP$ problemas de um pool estático e anuncia uma $ZKP$ prova, ela ainda pode ser tentada a vender sua testemunha a um fraudador se o preço estiver correto. Esse fraudador pode anexar o trabalho a outra cadeia fraudulenta.

A testemunha de um $NP$ O problema pode não proteger uma blockchain, que é um dos propósitos de uma prova de trabalho.

Propostas semelhantes

Convertendo o espaço problemático de um pool estático de $NP$ problemas em um conjunto dinâmico de problemas podem ajudar, e vi uma proposta que, penso, gera dinamicamente problemas de isomorfismo de subgráficos como provas de trabalho. No entanto, tanto quanto posso dizer, a proposta acima verifica a testemunha deterministicamente.

Também vi tentativas de usar PCPs para verificar cálculos terceirizados, embora eu não ache que o trabalho terceirizado esteja conectado a uma blockchain de criptomoeda. Talvez esse trabalho chegue perto.

História

Em [GMR85] , os autores introduzem sistemas de prova interativos. Em [GS86] , os autores mostram um protocolo público de moedas para nonisomorphism de gráfico. Em [Sha91] , o autor prova $IP=PSPACE$ .

Em [BFL91] , os autores provam que $MIP=NEXP$ . Em [BFLS91] , os autores imaginaram estender essas idéias para transformar provas matemáticas formais em provas transparentes verificáveis em tempo polilogarítmico.

Em [AS92] , os autores caracterizaram os trabalhos acima como implicando que as afirmações matemáticas podem ser verificadas no tempo polilogarítmico apenas pela leitura $poly(logn)$ bits em uma prova de um teorema da aritmética Peano, com uma prova de tamanho $n$ (que eles reduziram a um número sublogarítmico de bits e reduziram-se contemporaneamente a $O(1)$ consultas no teorema do PCP consagrado).

EG, citando [AS92] , eles visualizam declarações:

{(T, 1^{n}) : T i s a t h e o r e m o f P e a n o a r i t h m e t i c w i t h a p r o o f o f s i z e \leq n}

$\{(T,1^n):T\:is\:a\:theorem\:of\:Peano\:arithmetic\:with\:a\:proof\:of\:size\:\leq n\}$

como idiomas em $NP$ , com testemunhas que podem ser verificadas probabilisticamente com um número sublogármico de bits.

Note que é indecidível encontrar uma relação fácil entre $|T|$ , o comprimento do teorema provou, com $|\pi|=n$ , o tamanho da prova. Declarações prováveis simples podem ter provas longas, ou declarações prováveis longas podem ter provas curtas.

Ou seja, pelo Teorema da Incompletude, $n$ cresce mais rápido do que qualquer função computável de $|T|$ . Assim, pode-se considerar uma versão limitada do acima, digamos $n=O(exp |T|)$ e encontre provas de tamanho exponencial para pequenos teoremas. Assim, declarações como:

{(T, 1^{n}) : T i s a t h e o r e m o f P e a n o a r i t h m e t i c w i t h a p r o o f o f s i z e O (e x p (| T |))}

$\{(T,1^n):T\:is\:a\:theorem\:of\:Peano\:arithmetic\:with\:a\:proof\:of\:size\:O(exp(|T|))\}$

pode ser visto como idiomas em $NEXP$ , com entradas de tamanho $|T|$ .

[AS92] afirma que "suspeitamos que esse resultado seja amplamente de interesse teórico (e não prático) " (grifo nosso ).

Em [Kil92], o autor descreve um provador que se compromete com uma prova probabilisticamente verificável de $\pi$ como raiz de uma árvore de Merkle e respondendo a perguntas públicas sobre $i$ da prova, revelando o caminho de $i$ à raiz Merkle comprometida publicamente.

Em [Nak08], a solução do autor para o problema dos generais bizantinos implica exigir provas de trabalho.

A prova de trabalho em [Nak08] envolve a inversão parcial de hashes criptográficos - por exemplo, dado um hash criptográfico $h(x)\in\{0,1\}^N,x\in\{0,1\}^*$ , um bloco $i\in\mathbb{N}$ e (raiz de Merkle) transações financeiras $B_i\in\{0,1\}^N$ , encontrando um nonce $n$ de tal modo que

h (n ‖ B_{i})

$h(n\Vert B_i)$ começa com um número

d

$d$ de liderar

0 s

$0s$ .

A prova de trabalho em [Nak08] tem algumas vantagens - protege as transações, contando com o hash SHA256 bem estabelecido ( $N=256$ ), etc. A dificuldade de encontrar um nonce cresce à medida que $O(2^{kd})$ para alguns $k$ . A prova de trabalho em [Nak08] é verificável imediatamente por todos os nós no tempo $O(d)$ , e a verificação é muito rápida.

Da mesma forma, pode haver desvantagens em inverter parcialmente o SHA256 - muita energia é gasta em um problema que é essencialmente um quebra-cabeça aleatório e um tanto artificial. Além disso, todos aqueles que tentam a prova de trabalho estão trabalhando no mesmo problema , enquanto haverá um "vencedor".

Exemplos

NEXP

Considere, para bloco $i$ , um provador comprometendo-se com uma raiz Merkle, como em [Kil92] , de uma prova $\pi$ de alguma afirmação $T$ da aritmética Peano em formato probabilisticamente verificável, como em [AS92] . Ela pode usar na prova os axiomas Peano e outras regras de inferência. Ela também pode usar outros teoremas provados em blocos anteriores como lemas para acelerar a prova de seu próprio teorema. O primeiro mineiro a anunciar provas de declarações onde $\sum2^{-|T|}>d$ por algum limiar de dificuldade $d$ "ganha" o bloco.

Ela então usa o hash do bloco $i-1$ como a moeda aleatória lançada usada pelo verificador em [Kil92] para consultar $O(1)$ pedaços de $\pi$ .

Como recompensa pela mineração, ela recebe um lucro de $\sum2^{-|T|}$ unidades monetárias. Por isso, ela é incentivada a encontrar provas de pequenos teoremas (pois eles valem mais).

Isso também mantém a quantidade total de moeda cunhada finita e delimitada abaixo por $1/2$ (Porque $1/2$ de todas as fórmulas bem formadas são verdadeiras e $1/2$ são falsas e nem todas podem ser provadas.)

Eu também acho que isso incentiva $|T|$ crescer apenas como $O(log\:i)$ , Onde $i$ é o número do bloco, porque os mineradores apenas olham para declarações menores.

Isso também mostra que um mineiro que comprova uma declaração $T$ também pode anunciar $\sim\sim T$ e $\sim\sim\sim\sim T$ , etc., e ainda assim ser recompensado $2^{-O(|T|)}$ unidades monetárias.

Eventualmente, o mundo pode descobrir que alguma pequena declaração da aritmética Peano é verdadeira, embora nenhuma pessoa ou mineiro possa ter acesso a toda a prova. Alguns mineiros podem ter provado lemas individuais, que são usados por outros para finalizar a prova. Esses outros mineiros talvez nunca precisem ter suas provas verificadas deterministicamente.

PSPACE

Como outro exemplo de prova de trabalho, considere adicionar um número de fórmula booleana quantificada gerada aleatoriamente ( $QBF$ ) a um "conjunto" de problemas em aberto. Digamos, no bloco de mineração $i$ , $O(1)$ $QBF$ problemas com uma média de $l=O(log\:i)$ literais são gerados e adicionados ao "pool".

Os problemas adicionados ao pool podem ser gerados aleatoriamente com base no hash dos blocos anteriores.

Os fornecedores (mineradores) competem para encontrar provas de que um ou mais dos problemas no “pool” são verdadeiros ou falsos. O primeiro provador a encontrar um número $d$ de declarações no "pool" obtém o lucro da mineração. Ao encontrar uma prova, um provador se envolve em uma prova interativa em moeda pública da verdade ou falsidade das declarações que eles provaram. Acho que eles podem se engajar na heurística Fiat-Shamir em sua prova anunciada.

Os fornecedores não são, necessariamente, obrigados a provar que os problemas gerados mais recentemente são verdadeiros ou falsos, apenas que alguns dos problemas no pool são verdadeiros ou falsos. Por exemplo, um problema adicionado $10$ ou $100$ blocos atrás ainda podem ser trabalhados e comprovados para este bloco.

Portanto, um problema que está "na piscina" há muito tempo se manifesta como um problema mais difícil, porque está "na piscina" por mais tempo.

Os provadores podem ser recompensados $2^{-l}$ unidades monetárias. Portanto, há um incentivo para encontrar QBFs verdadeiros com um número menor de literais. Isso também mantém a moeda total finita. Como alguns QBFs com um grande número de literais podem ser mais fáceis do que outros com um pequeno número de literais, pode ser mais fácil para os mineiros trabalhar em problemas recém-adicionados e mais fáceis com um número maior de literais do que em problemas mais antigos e mais difíceis com um número menor. de literais, embora o lucro possa ser menor.

Ao contrário da inversão do SHA, os provadores $P_1$ e $P_2$ não precisa estar trabalhando na mesma posição ao mesmo tempo. Quem encontrar uma prova primeiro, apenas a anuncia, contando com os bits aleatórios do hash do bloco anterior para verificar probabilisticamente. O perdedor deste bloco ainda pode continuar procurando sua prova e vencer na próxima rodada.

Porque $PSPACE$ podem ser considerados jogos entre $\exists$ e $\forall$ , a mineração pode ser considerada como solução de jogos. Eventualmente, o mundo pode descobrir que o xadrez (ou qualquer outro jogo) está resolvido. No entanto, nenhum provador tem acesso a toda a prova, porque ninguém poderá armazenar a prova inteira.

Referências

[AS92] S. Arora, S. Safra. Verificação probabilística de provas: uma nova caracterização de NP. ligação

[BFL91] L. Babai, L. Fortnow e C. Lund. O tempo exponencial não determinístico possui provas interativas de dois provadores. ligação

[BFLS91] L. Babai, L. Fornow, L. Levin e M. Szegedy. Verificando cálculos em tempo polilogarítmico. ligação

[GMR85] S. Goldwasser, S. Micali, C. Rackoff. A complexidade do conhecimento de provas interativas. ligação

[GS86] S. Goldwasser, M. Sipser. Moedas privadas vs. moedas públicas em sistemas de prova interativos. ligação

[Kil92] J. Killian. Uma observação sobre provas e argumentos eficientes de conhecimento zero. ligação

[Nak08] S. Nakomoto. Bitcoin: um sistema de caixa eletrônico ponto a ponto. ligação

[Sha92] IP = PSPACE ligação

complexity-theory np hash proof-of-work Mark S
fonte

Eu não entendo bem a parte da motivação (se a testemunha for muito grande, levará muito tempo para ser transferida para um destinatário não autorizado, também levará muito tempo para ser transferida para o legítimo destinatário, então parece que todo mundo perde ) Se você deseja uma prova intransferível, sugiro a leitura de provas interativas, provas de conhecimento zero e similares. Dito isso, não vejo por que probabilisticamente verificável versus deterministicamente verificável necessariamente ajudaria com o problema da transferibilidade, portanto isso me parece um problema XY .

Estou um pouco confuso com várias das observações aqui. Não sei ao certo como interpretar "tentar manter uma testemunha com zero conhecimento pode ser difícil" ou o que isso significa (se nada puder ser mantido em segredo, grande parte da criptografia é inútil). Eu suspeito que seu primeiro passo deve ser definir um problema específico que você está tentando resolver e identificar o modelo de ameaça (descubra se você tem um prego ou um parafuso, antes de comprar um martelo). Também não tenho muita certeza de como interpretar a referência a "lemas" no contexto de uma prova de trabalho, embora talvez seja apenas minha falta de imaginação.

Não tomei tempo para ler sua pergunta, mas você pode estar interessado neste artigo. delivery.acm.org/10.1145/3140000/3132757/...

jalex Stark