O problema de gasto duplo e os generais bizantinos

Curiosidade

1. Se um arquivo digital pode ser copiado perfeitamente e instantaneamente, o que impede que seja usado duas vezes?
2. Como um grupo de estranhos sem identidade em comum pode concordar sobre uma única história sem um líder para arbitrar disputas?
3. O que torna um voto em uma rede aberta mais valioso do que a palavra de outra pessoa?

Explorar

1. Um token digital é meramente um arquivo. Diferentemente do dinheiro físico, ele pode ser duplicado bit a bit sem custo algum e sem perda de qualidade. Se Alice enviar dez unidades para Bob, ela mantém o arquivo original e pode enviar essas mesmas dez unidades para Charlie simultaneamente. Até 2008, todo sistema digital de dinheiro funcional dependia de um emissor confiável: os sistemas online verificavam cada pagamento de forma centralizada, enquanto os sistemas offline só conseguiam identificar quem fazia gastos duplicados após o fato.
2. O DigiCash de David Chaum exigia que cada beneficiário depositasse moedas no banco, o qual verificava cada número de série em relação à sua lista de moedas já utilizadas. As Provas Reutilizáveis de Trabalho de Hal Finney dependiam de um único servidor que executava código de fonte aberta em hardware seguro para rastrear os tokens já usados. O b-money de Wei Dai propunha servidores responsáveis por registrar os depósitos, e esses servidores poderiam ser multados em caso de fraude, mas nunca foi desenvolvido. Cada um desses projetos tinha como ponto central uma parte confiável ou um grupo conhecido.
3. Em 1982, Leslie Lamport, Robert Shostak e Marshall Pease formalizaram o Problema dos Generais Bizantinos em ACM Transactions on Programming Languages and Systems. Os generais que cercam uma cidade precisam concordar se devem atacar ou recuar, mas alguns deles são traidores que enviam mensagens conflitantes; os próprios mensageiros são confiáveis. Com mensagens não assinadas, um consenso só é possível se menos de um terço dos generais for traidor (n ≥ 3f+1); com um terço ou mais, nenhum protocolo pode garantir isso.
4. Protocolos clássicos tolerantes a falhas, como o PBFT, exigem um conjunto fixo e conhecido de participantes. Isso funciona para os livros-razão internos dos bancos, mas falha em redes abertas onde qualquer pessoa pode se juntar. John Douceur identificou o ataque Sybil em 2002: um adversário pode gerar identidades falsas ilimitadas para diluir votos honestos ou controlar os quóruns. Em uma rede peer-to-peer aberta, a identidade é barata e infinita, portanto qualquer esquema que conte identidades pode ser dominado por um único agente.
5. O whitepaper de Satoshi Nakamoto abordou isso diretamente. Seu resumo apresenta o bitcoin como uma solução para o problema do gasto duplo sem a necessidade de um terceiro confiável. Em vez de depender da identidade ou da confiança institucional, o sistema vincula cada bloco a uma prova cumulativa de trabalho (PoW). Os votos são ponderados pelo poder computacional, que não pode ser multiplicado inventando identidades; um atacante precisa superar em capacidade de cálculo toda a rede honesta para reescrever a história.
6. O resultado é a finalização probabilística. Uma transação não é permanentemente final no sentido matemático, mas torna-se cada vez mais segura à medida que cada novo bloco estende a cadeia. Enquanto um atacante controlar menos da metade do poder de hashing, a chance de reversão diminui exponencialmente a cada confirmação. Esse trade-off aceita a possibilidade teórica de reversão para obter imutabilidade prática sem controle centralizado. Abra um explorador de blocos e observe como o trabalho acumulado cresce com a altura de cada bloco; esse custo acumulado é o que ancora o livro-razão à realidade física.

Fatos-chave

Exercício nove, seis, três, um

Verificação de fatos

Datas, números e afirmações verificados com as fontes publicadas listadas abaixo.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)