Qualquer desafio computacional pode ser transformado em prova de trabalho?

20

A aparentemente sem sentido da mineração de criptomoedas levantou a questão de alternativas úteis, veja estas perguntas em Bitcoin , CST , MO . Gostaria de saber se existe um algoritmo que possa converter praticamente qualquer desafio computacional (cuja solução pode ser verificada com eficiência) em outro desses desafios (que é usado para a prova de trabalho) tal que Ψ ( C )CΨ(C)

  1. A função é randomizada, usando alguma sequência aleatória (pública) .rΨr
  2. Resolvendo é tipicamente tão duro como resolver .CΨ(C)C
  3. Se uma solução é encontrado em , em seguida, uma solução pode ser eficientemente calculada para o desafio original .Ψ ( C ) Ψ - 1 ( x ) CxΨ(C)Ψ1(x)C
  4. Conhecer uma solução para não ajuda a encontrar uma solução para . Ψ ( C )CΨ(C)

4 '(atualização). Como apontado por Noah em um comentário, a condição anterior deve ser reforçada para exigir que o pré-processamento também não ofereça nenhuma vantagem na resolução de . Ψ ( C )CΨ(C)

Esta última condição é necessária para que ninguém pode ser colocado em uma posição vantajosa apenas porque sabem que uma solução de . Usando esse método, as pessoas podem enviar problemas computacionais que desejam resolver e uma autoridade central pode escolher algo que valha a pena resolver (como encontrar alienígenas versus quebrar senhas). Observe que não parece ser um problema se o problema levar até uma semana para ser resolvido (acho que esses alienígenas não podem ser tão bons em se esconder;), pois isso pode resultar em uma recompensa maior por uma solução. De qualquer forma, esses tópicos não estão relacionados à solução do meu problema teórico, mas é claro que fico feliz em discuti-los nos comentários / no fórum.C

Uma solução possível seria a seguinte: mapeia em , isto é, para resolver e algum outro desafio computacionalmente difícil. Um problema é que o conhecimento de uma solução para facilita a resolução de (o quanto mais fácil depende da dificuldade do ). Outra questão é que tornou-se mais difícil do que .C ( C , H A S H R ) C C Ψ ( C ) H O S H r Ψ ( C ) CΨC(C,HASHr)CCΨ(C)HASHrΨ(C)C

domotorp
fonte
3
Talvez isso possa ser relevante: eprint.iacr.org/2017/203.pdf
Andreas Björklund
3
Qual é a diferença entre um "desafio computacional" e um "desafio de prova de trabalho"?
Ou Meir
2
Certamente, mas a própria definição de provas de trabalho geralmente requer vários desafios, pois a propriedade principal que as define é a não-amortizabilidade. Esta é a razão pela qual trabalhos como eprint.iacr.org/2017/203.pdf foram realizados - você precisa de garantias de não amortizabilidade para quase todas as aplicações de PoWs, especialmente criptomoedas. De qualquer forma, você está procurando uma solução publicamente verificável ou seria suficiente uma solução privada verificável? Você quer um esquema praticamente eficiente ou está de acordo com uma solução teórica?
Geoffroy Couteau
5
@domotorp, por que você acha que eprint.iacr.org/2017/203.pdf não é relevante para sua pergunta?
Alon Rosen
5
Embora não ofereça uma redução de qualquer problema de pior caso em P, o artigo fornece PoW útil com base em um amplo conjunto de problemas. Especificamente, qualquer problema redutível a Vetores ortogonais (OV), incluindo todos os problemas de gráfico que são estáveis ​​na lógica de primeira ordem. Também se aplica ao problema k-OV (conjecturado para exigir aproximadamente n ^ k tempo), bem como a outros problemas do mundo da complexidade refinada. Portanto, embora talvez não seja tão geral quanto você esperaria, os resultados ainda são bastante gerais. E para os problemas mencionados acima, as propriedades 1 a 4 são realmente satisfeitas.
Alon Rosen

Respostas:

8

( Nota : Andreas Björklund sugeriu uma solução nos comentários que acredito ser melhor do que a descrita abaixo. Consulte http://eprint.iacr.org/2017/203 , de Ball, Rosen, Sabin e Vasudevan. Em resumo, eles fornecem provas de trabalho baseadas em problemas como vetores ortogonais cuja dureza é bem compreendida e para os quais muitos problemas (por exemplo, k-SAT) podem ser reduzidos de forma relativamente eficiente.Sua instância de PoW é tão difícil quanto um vetor ortogonal na pior das hipóteses, mesmo que a instância de entrada seja fácil, para evitar uma grande desvantagem da solução descrita abaixo.CΨ(C)C

A solução descrita abaixo pode se beneficiar de sua simplicidade - pode ser descrita para um não especialista -, mas me parece ser muito menos interessante teoricamente.)

Uma solução é possível se alguém assumir que "o algoritmo mais rápido para é fundamentalmente randomizado" (e se modelarmos uma função hash criptográfica como um oráculo aleatório). Uma maneira de formalizar isso é dizer queC

  1. CTFNPFP (caso contrário, acho que não é realmente um desafio válido);
  2. o algoritmo aleatório mais rápido para é executado no tempo esperado em uma instância típica; e TCT
  3. existe uma função eficientemente computável de até o domínio de soluções para por modo que sempre exista um com uma solução para .{ 0 , 1 } k C k log 2 T s { 0 , 1 } k f ( s ) Cf{0,1}kCklog2Ts{0,1}kf(s)C

Observe que a suposição de que implica que a pesquisa de força bruta de é essencialmente o algoritmo ideal para . Portanto, essa é uma suposição bastante forte. Por outro lado, se não satisfaz essas propriedades, é difícil para mim imaginar satisfazer suas condições (2) e (4).{ 0 , 1 } k C Cklog2T{0,1}kCC

Então, dada a função hash , que como um oráculo aleatório, definimos da seguinte forma, onde para alguns é a entrada aleatória para . O objetivo é gerar forma que seja uma solução para . Em outras palavras, deve usar hash para "boas moedas aleatórias" para o algoritmo acima.Ψ H ( C ; r ) r { 0 , 1 } k Ψ H x { 0 , 1 } f ( H ( r , x ) ) C ( r , x )H:{0,1}{0,1}kΨH(C;r)r{0,1}kΨHx{0,1}f(H(r,x))C(r,x)

Vamos ver que isso satisfaz todas as suas condições.

  1. "A função é randomizada, usando alguma sequência aleatória (pública) ." Verifica!rΨr
  2. "Resolver normalmente é tão difícil quanto resolver ." Observe que o algoritmo aleatório simples para é executado no tempo esperado no máximo mais sobrecarga polinomial, e pela suposição é essencialmente o tempo de execução do algoritmo ideal para .C Ψ H ( C , r ) 2 k 2 kT CΨ(C)CΨH(C,r)2k2kTC
  3. "Se uma solução for encontrada para , então uma solução poderá ser calculada com eficiência para o desafio original ." Isso pode ser feito computando , que é uma solução para por suposição.Ψ ( C ) Ψ - 1 ( x ) C f ( H ( r , x ) ) CxΨ(C)Ψ1(x)Cf(H(r,x))C
  4. "Conhecer uma solução para não ajuda a encontrar uma solução para ." Por definição, resolver requer encontrar tal que seja uma solução para . Como modelamos como um oráculo aleatório, podemos limitar o tempo de execução esperado de qualquer algoritmo que resolva esse problema pela complexidade esperada ideal do problema de consulta no qual é fornecido por uma caixa preta e somos solicitados a encontrar um solução para o mesmo problema. E, novamente porque é um oráculo aleatório, a complexidade esperada da consulta é apenas o inverso da fração de elementos Ψ ( C ) Ψ H ( C ; r ) x f ( H ( R , x ) ) C H H H x { 0 , 1 } k C T 2 k 2 - k» k r { 0 , 1 } H C r CCΨ(C)ΨH(C;r)xf(H(r,x))CHHHx{0,1}k que são soluções (até um fator constante). Por suposição, o tempo ideal de execução esperado de qualquer algoritmo para é , o que implica que essa fração não pode ser muito maior que . Como e são escolhidos uniformemente aleatoriamente, isso é verdade mesmo com o pré-processamento que pode depender de e (mas não ) e, em particular, é verdade mesmo se conhecermos uma solução para com antecedência.CT2k2kkr{0,1}HCrC
Noah Stephens-Davidowitz
fonte
Esta é uma solução muito boa. O único lugar em que vejo uma possibilidade de melhora é a condição (2). Para muitos problemas em , existem algoritmos em time para alguns . Seria bom se algo assim pudesse ser preservado, mas não tenho certeza se isso pode ser feito. Certamente, seu método já é superior aos usados ​​atualmente para criptomoedas! c n c < 2NPcnc<2
Domotorp 2/01
De fato, talvez nem mesmo muita coisa precise ser alterada na blockchain. Apenas a comunidade pode concordar que em algum momento um precisa ser anexado à blockchain cujo hash resolve qualquer problema prático. De fato, talvez o blockchain padrão possa continuar, e isso poderia ser apenas um desafio independente e individual. Possivelmente no mercado, uma instância desse tipo valerá mais do que moedas tradicionais, assim como Rogue One é melhor que sw7 ou sw8. x
Domotorp #
Estou feliz por ter gostado :). Eu só quero esclarecer que, enquanto minhas condições em implicam que "a pesquisa de força bruta em algum espaço de pesquisa é essencialmente ideal", elas não implicam que a pesquisa de força bruta no espaço de pesquisa original é essencialmente ideal. Por exemplo, para o SAT, isso não é o mesmo que exigir que o algoritmo mais rápido seja executado em tempo. 2 nC2n
Noah Stephens-Davidowitz
No caso de composição - por exemplo, o problema computacional admite uma definição de problema na qual o problema computacional pode ser composto por problemas menores, cuja solução é mais fácil, e existe uma solução que não é baseada na composição, a não-amortizabilidade seria responsável por isso. ?
User3483902
Eu acho que outro problema com esta solução é o que você apontou em um comentário para minha pergunta, a saber, que se alguém puder pré-processar maneira eficiente, poderá obter uma vantagem séria. Eu acho que essa é uma questão bastante delicada. Imagine que eu envie um problema cuja solução (em um formato padrão) possa ser verificada em tempo, mas eu tenho um método secreto para verificá-lo em time. Isso me dá uma grande vantagem para resolver . n Cn Ψ(C)nΨ(C)
Domotorp #
1

A seguinte técnica simples, que chamo de solução de loteria (SLT), pode ser usada em conjunto com outras técnicas (como ter vários problemas de prisioneiros de guerra, a técnica mencionada na resposta de Noah Stephens-Davidowitz, etc.) para ajudar a transformar desafios computacionais em provas viáveis. problemas de trabalho. O SLT ajuda a melhorar os problemas com problemas de mineração de criptomoeda que não sejam as condições 1-4.

Suponha que seja um desafio computacional da forma "encontre um hash adequado junto com uma string tal que ". k x ( k , x ) DCkx(k,x)D

Configuração do problema : Suponha que seja um conjunto, seja uma função hash criptográfica e seja uma constante. Suponha, além disso, que é uma informação que é fácil de obter depois que se determina que mas que não pode ser obtido de outra maneira.D H C Dados ( k , x ) ( k , x ) DΨ(C)DHCData(k,x)(k,x)D

Problema objetivo: Encontre um par tal que seja um hash adequado e onde e onde .( k , x ) k ( k , x ) D H ( k | | x | | Dados ( k , x ) ) < CΨ(C)(k,x)k(k,x)DH(k||x||Data(k,x))<C

Vamos agora investigar como o problema atende aos requisitos 1-4.Ψ(C)

  1. Temos que assumir que já está randomizado para que o SLT satisfaça essa propriedade.C

2-3. normalmente se tornará mais difícil que e isso é uma coisa boa. A dificuldade de um problema de prova de trabalho precisa ser ajustada, mas o problema original pode ou não ter um nível de dificuldade ajustável (lembre-se de que a dificuldade na mineração de Bitcoin é ajustada a cada duas semanas) . A dificuldade do problema é igual à dificuldade de encontrar algum adequado multiplicado por . Portanto, como a constante é finamente ajustável, a dificuldade de também é finamente ajustável.C C Ψ ( C ) ( k , x ) D 2 nΨ(C)CCΨ(C)(k,x)D CΨ(C)2nCCΨ(C)

Mesmo que o problema seja mais difícil do que o problema original , quase todo o trabalho para resolver o problema será gasto em simplesmente encontrar um par com vez de calcular hashes (não se pode calcular se ou não até um calculou e não se pode calcular menos que se verifique esse ).C Ψ ( C ) ( k , x ) ( k , x ) D H ( k | | x | | Dados ( k , x ) ) < C Dados ( k , x ) Dados ( k , x ) Dados ( k , x ) DΨ(C)CΨ(C)(k,x)(k,x)DH(k||x||Data(k,x))<CData(k,x)Data(k,x)Data(k,x)D

Obviamente, o fato de que é mais difícil que apresenta algumas novas preocupações. Para um problema útil, é mais provável que alguém queira armazenar os pares que em algum banco de dados. No entanto, para receber a recompensa em bloco, o mineiro deve revelar apenas um par que e vez de todos os pares independentemente de ou não. Uma solução possível para esse problema é que os mineiros simplesmente revelem todos os pares ondeC ( k , x ) ( k , x ) D ( k , x ) ( k , x ) D H ( k | | x | | Dados ( k , x ) ) < C ( k , x ) D H ( k | | x | |Ψ(C)C(k,x)(k,x)D(k,x)(k,x)DH(k||x||Data(k,x))<C(k,x)D( k , x ) ( k , x ) D ( k , x ) D ( k , x ) D Ψ ( C ) CH(k||x||Data(k,x))<C(k,x)(k,x)Dpor cortesia. Os mineiros também terá a capacidade de rejeitar cadeias se os mineiros não colocaram seu quinhão de pares . Talvez, deva-se contar o número de pares para o cálculo de quem tem a cadeia válida mais longa também. Se a maioria dos mineradores postar suas soluções, o processo de resolução de produzirá tantas soluções quanto o processo de resolução de .(k,x)D(k,x)DΨ(C)C

No cenário em que os mineiros publicam todos os pares , satisfazem o espírito das condições 2-3.Ψ ( C )(k,x)DΨ(C)

  1. 4Ψ(C) pode ou não atender à condição dependendo do problema específico.4

Other Advantages of this technique:

O SLT oferece outras vantagens além das condições 1-4, desejáveis ​​ou necessárias para um problema de prova de trabalho.

  1. Melhorando o equilíbrio segurança / eficiência: O SLT ajudará no caso de poder ser muito fácil de resolver ou muito difícil de verificar. Em geral, é muito mais difícil de resolver do que , mas é tão fácil de verificar quanto .CΨ(C)CΨ(C)C

  2. Remoção de um problema quebrado / inseguro: O SLT pode ser usado para remover algoritmos problemas de POW ruins em uma criptomoeda com um problema de POW de backup e vários problemas de POW. Suponha que uma entidade encontre um algoritmo muito rápido para resolver o problema . Então, esse problema não é mais um problema de prova de trabalho adequado e deve ser removido da criptomoeda. A criptomoeda deve, portanto, ter um algoritmo que remove da criptomoeda sempre que alguém postou um algoritmo que resolve o problema muito rapidamente, mas que nunca remove o problema . Aqui está um resumo desse algoritmo de remoção de problemas sendo usado para remover um problema que chamaremos de ProblemaCCCCA .

uma. Alice paga uma taxa alta (a taxa cobrirá os custos que os mineradores incorrem para verificar o algoritmo) e depois publica o algoritmo que chamaremos de Algoritmo K que quebra o Problema no blockchain. Se o algoritmo K depende de uma grande quantidade de dados pré-calculados , Alice publica a raiz Merkle desse dados pré-computados .APCPC

b. Instâncias aleatórias do Problema A são produzidas pelo Blockchain. Alice então publica as partes dos dados pré-computados necessárias para que o Algoritmo K funcione corretamente junto com sua ramificação Merkle, a fim de provar que os dados realmente vieram do . Se o algoritmo de Alice for alimentado rapidamente com o dados pré-calculados , o problema será removido e Alice receberá uma recompensa por postar o algoritmo que remove o problema da blockchain.PCPC

Este procedimento de remoção de problemas é computacionalmente caro para os mineradores e validadores. No entanto, o SLT remove a maior parte da dificuldade computacional dessa técnica, para que possa ser usada se necessário em uma criptomoeda (instâncias em que essa técnica é usada provavelmente serão bastante raras).

  1. Os pools de mineração são mais viáveis: em criptomoedas, muitas vezes é muito difícil ganhar a recompensa em bloco. Como as recompensas em bloco são muito difíceis de ganhar, os mineradores geralmente exploram os chamados " pools de mineração", nos quais combinam seus recursos na solução de um problema e compartilham a recompensa em blocos proporcionalmente à quantidade de "quase acidentes" encontrados. . Um possível problema para é que pode ser difícil produzir uma noção qualitativa do que constitui uma “quase perda” para o problema e o algoritmo para encontrar uma quase perda pode ser diferente do algoritmo para resolver . Como os mineiros de piscinas procuram quase acidentes, eles podem não ser muito eficientes na soluçãoC C C Ψ ( C ) ( k , x ) ( k , x ) D H ( k | | x | | Dados ( k , x ) ) C Ψ ( C ) Ψ ( C )CCCC (e, portanto, poucas pessoas participarão de pools de mineração). No entanto, para , existe uma noção clara de near miss, a saber, near near é um par que mas em que , e o algoritmo para encontrar quase erros para será o mesmo que o algoritmo para encontrar soluções para .Ψ(C)(k,x)(k,x)DH(k||x||Data(k,x))CΨ(C)Ψ(C)

  2. Transparência no progresso: Um problema de prova de trabalho é considerado livre de progresso se o tempo que leva para uma entidade ou grupo de entidades encontrar o próximo bloco na blockchain segue a distribuição exponencial onde a constante é diretamente proporcional à quantidade de poder computacional que entidade está usando para resolver o problema . A falta de progresso é necessária para problemas de mineração de criptomoedas, para que os mineradores recebam uma recompensa em bloco proporcionalmente ao seu poder de mineração para obter descentralização. O SLT certamente ajuda os problemas de mineração a obter progresso sem frestas.e - λ x λ PPeλxλP

Joseph Van Name
fonte