Texto traduzido por Michelle Mafra
Por: Satoshi Nakamoto
Lista de Endereços de Criptografia
Bitcoin P2P e-cash papel
13-11-2008 22:56:55 UTC - E-mail original - Visualizar no tópico
James A. Donald escreveu:
Não é suficiente que todos saibam o X. Também precisamos que todos sabem que todos sabem o X e que todos sabem que todos sabem que todos sabem o X - o que, como no problema dos generais bizantinos, é o clássico problema difícil de processamento de dados distribuído .
A cadeia de prova-de-trabalho é uma solução para o problema dos generais bizantinos. Vou tentar reformulá-lo nesse contexto.
Vários generais bizantinos têm um computador e querem atacar o wi-fi do rei brutalmente forçando a senha, o que eles descobriram ter um certo número de caracteres. Depois que estimulam a rede a gerar um pacote, eles devem quebrar a senha dentro de um tempo limitado para invadir e apagar os logs, caso contrário, eles serão descobertos e terão problemas. Eles só têm energia suficiente na CPU para quebrá-lo rápido o suficiente se a maioria deles atacar ao mesmo tempo.
Eles não se importam particularmente quando o ataque será, apenas que todos concordem. Foi decidido que quem quiser anunciar um horário, e o horário que for ouvido primeiro será o horário oficial do ataque. O problema é que a rede não é instantânea e, se dois generais anunciam tempos de ataque diferentes quase ao mesmo tempo, alguns podem ouvir um primeiro e outros ouvirem o outro primeiro.
Eles usam uma cadeia de prova-de-trabalho para resolver o problema. Depois que cada general recebe o tempo de ataque que ouve primeiro, ele define seu computador para resolver um problema extremamente difícil de prova de trabalho que inclui o tempo de ataque em seu hash. A prova de trabalho é tão difícil que é esperado que demore 10 minutos, todos trabalhando ao mesmo tempo, antes que um deles encontre uma solução. Depois que um dos generais encontra uma prova de trabalho, ele a transmite à rede, e todos mudam seu cálculo atual de prova de trabalho para incluir essa prova de trabalho no hash em que estão trabalhando. Se alguém estava trabalhando em um horário de ataque diferente, ele muda para este, porque sua cadeia de provas de trabalho agora é mais longa.
Após duas horas, um tempo de ataque deve ser calculado por uma cadeia de 12 provas de trabalho. Todo general, apenas verificando a dificuldade da cadeia de prova de trabalho, pode estimar quanto de energia paralela da CPU por hora foi gasto nela e ver que deve ter exigido que a maioria dos computadores produzisse essa prova de prova. Trabalhar no tempo previsto. Todos eles deveriam ter visto, porque a prova de trabalho é a prova de que eles trabalharam nela. Se a energia da CPU exibida pela cadeia de prova de trabalho for suficiente para decifrar a senha, eles poderão atacar com segurança no horário acordado.
A cadeia de provas de trabalho é como são resolvidos todos os problemas de sincronização, banco de dados distribuído e visão global que você perguntou.
Cryptography Mailing List
Bitcoin P2P e-cash paper
James A. Donald wrote:
It is not sufficient that everyone knows X. We also need everyone to know that everyone knows X, and that everyone knows that everyone knows that everyone knows X - which, as in the Byzantine Generals problem, is the classic hard problem of distributed data processing.
The proof-of-work chain is a solution to the Byzantine Generals' Problem. I'll try to rephrase it in that context.
A number of Byzantine Generals each have a computer and want to attack the King's wi-fi by brute forcing the password, which they've learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.
They don't particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels like it will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.
They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work is so difficult, it's expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they're working on. If anyone was working on a different attack time, they switch to this one, because its proof-of-work chain is now longer.
After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have required the majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proof-of-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.
The proof-of-work chain is how all the synchronisation, distributed database and global view problems you've asked about are solved.
Comments