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 )
- A função é randomizada, usando alguma sequência aleatória (pública) .r
- Resolvendo é tipicamente tão duro como resolver .C
- Se uma solução é encontrado em , em seguida, uma solução pode ser eficientemente calculada para o desafio original .Ψ ( C ) Ψ - 1 ( x ) C
- Conhecer uma solução para não ajuda a encontrar uma solução para . Ψ ( 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 )
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.
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
Respostas:
( 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
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 Ck≈log2T {0,1}k C C
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 ΨH x∈{0,1}∗ f(H(r,x)) C (r,x)
Vamos ver que isso satisfaz todas as suas condições.
fonte
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 ) ∈ DC k x (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) D H C Data(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)∈D H(k||x||Data(k,x))<C
Vamos agora investigar como o problema atende aos requisitos 1-4.Ψ(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) C C Ψ(C) (k,x)∈D CΨ(C)2nC C Ψ(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)∈D H(k||x||Data(k,x))<C Data(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)∈D H(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)∈D por 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)
O SLT oferece outras vantagens além das condições 1-4, desejáveis ou necessárias para um problema de prova de trabalho.
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
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 ProblemaC C C C A .
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 .A PC PC
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.PC PC
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).
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 )C C C C (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)∈D H(k||x||Data(k,x))≥C Ψ(C) Ψ(C)
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 λ PP e−λx λ P
fonte