Boa noite, amigos!
Demorou mas chegamos. No versículo anterior vimos a parte 3. No de hoje a parte final da tradução de ‘Bitcoin: A Peer-to-Peer Eletronic Cash System‘.
11. Cálculos
Consideramos o cenário de um atacante tentando gerar uma cadeia alternativa mais rápido que a cadeia honesta. Mesmo se isto for realizado, ele não joga o sistema à mudanças arbitrárias, como criar valor do nada ou tirar dinheiro que nunca pertenceu ao atacante. Os nodos não aceitarão uma transação inválida como pagamento, e os nodos honestos não irão aceitar um bloco que a contenha. Um atacante só pode tentar alterar uma de suas próprias transações para recuperar o dinheiro que gastou recentemente.
A corrida entre a cadeia honesta e a cadeia de um atacante pode ser caracterizada como uma caminhada aleatória binomial. O evento de sucesso é a cadeia honesta sendo estendida em um bloco, aumentando sua liderança em +1, e o evento falho é a cadeia do atacante sendo estendida em um bloco, reduzindo a lacuna em -1.
A probabilidade de um atacante se recuperar de um dado déficit é análoga ao problema da ruína do jogador. Suponha que um jogador com crédito ilimitado comece com um déficit e jogue potencialmente um número infinito de tentativas para tentar chegar ao ponto de equilíbrio. Podemos calcular a probabilidade de que ele chegue ao ponto de equilíbrio, ou que um invasor alcance a cadeia honesta, da seguinte maneira [8]:
p = probabilidade de um nodo honesto encontrar o próximo bloco
q = probabilidade de um atacante encontrar o próximo bloco
qz= probabilidade de que o atacante alcance de z blocos atrás
Dada nossa suposição de que p>q, a probabilidade cai exponencialmente à medida que aumenta o número de blocos que o invasor precisa alcançar. Com as probabilidades contra ele, se ele não der um golpe de sorte para a frente logo no início, suas chances tornam-se cada vez menores à medida que ele fica para trás.
Agora consideramos quanto tempo o destinatário de uma nova transação precisa esperar antes de ter certeza suficiente de que o remetente não pode alterar a transação. Presumimos que o remetente seja um atacante que deseja fazer o destinatário acreditar que o pagou por um tempo e, em seguida, mudar o pagamento para ele mesmo depois de algum tempo. O receptor será alertado quando isso acontecer, mas o remetente espera que seja tarde demais.
O receptor gera um novo par de chaves e fornece a chave pública ao remetente pouco antes de assinar. Isso evita que o remetente prepare uma cadeia de blocos com antecedência, trabalhando nela continuamente até que tenha a sorte de avançar o suficiente e, então, executar a transação naquele momento. Assim que a transação é enviada, o remetente desonesto começa a trabalhar em segredo em uma cadeia paralela contendo uma versão alternativa de sua transação.
O destinatário espera até que a transação seja adicionada a um bloco e os z blocos que tenham sido vinculados a ela. Ele não sabe a quantidade exata de progresso que o atacante fez, mas assumindo que os blocos honestos levaram o tempo médio esperado por bloco, o progresso potencial do atacante será uma distribuição de Poisson com valor esperado:
Para obter a probabilidade de o atacante ainda conseguir alcançar agora, multiplicamos a densidade de Poisson para cada quantidade de progresso que ele poderia ter feito pela probabilidade de alcançar a partir daquele ponto:
Reorganizando para evitar somar a cauda infinita da distribuição …
Convertendo para linguagem C …
#include
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 – q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k <= z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i <= k; i++)
poisson *= lambda / i;
sum -= poisson * (1 – pow(q / p, z – k));
}
return sum;
}
Executando alguns resultados, podemos ver a probabilidade cair exponencialmente com z.
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
Resolvendo para P inferior a 0,1% …
P < 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
12. Conclusão
Propusemos um sistema para transações eletrônicas sem depender de confiança. Começamos com a estrutura usual de moedas feitas de assinaturas digitais, que fornece um forte controle de propriedade, mas é incompleta sem uma forma de evitar gastos duplos. Para resolver isso, propusemos uma rede ponto a ponto usando prova de trabalho para registrar um histórico público de transações que rapidamente se torna computacionalmente impraticável para um atacante alterar se nodos honestos controlarem a maioria do poder da CPU. A rede é robusta em sua simplicidade não estruturada. Os nodos funcionam todos de uma vez com pouca coordenação. Eles não precisam ser identificados, uma vez que as mensagens não são roteadas para nenhum local específico e precisam ser entregues apenas na base do melhor esforço. Os nodos podem sair e se juntar à rede à vontade, aceitando a cadeia de prova de trabalho como prova do que aconteceu enquanto eles estavam fora. Eles votam com seu poder de CPU, expressando sua aceitação de blocos válidos trabalhando para estendê-los e rejeitando blocos inválidos recusando-se a trabalhar neles. Quaisquer regras e incentivos necessários podem ser aplicados com este mecanismo de consenso.
[8] W. Feller, “An introduction to probability theory and its applications,” 1957.
Terminada a tradução do Whitepaper do Bitcoin, uma das obras mais F#D@$ de todo criptoeste, e sem dúvidas a mais importante.
