Prova de trabalho

Em criptografia, o protocolo prova de trabalho ou PoW (do inglês, Proof-of-work) é um protocolo utilizado para a prevenção de ataques cibernéticos como DDOS e spam. Ele surgiu como uma tentativa de reduzir os efeitos desses ataques utilizando de funções hash. Para um usuário realizar alguma ação, ele deve ser capaz de provar que realizou alguma tarefa, essa prova é a garantia de que o usuário gastou tempo para gerar uma resposta que satisfaça algum requisito do avaliador. Para esse sistema funcionar, tal prova deve ser trabalhosa de ser criada, mas facilmente verificada pelo avaliador.

Seu uso inicial foi em correspondência eletrônica,^[1] mas foi eventualmente aplicado em criptomoedas como o Bitcoin para verificar transações, garantir consenso na blockchain e minerar moedas.

História

A ideia apareceu pela primeira vez em 1993 em um artigo publicado por Cynthia Dwork e Moni Naor como um mecanismo para combater emails de spam.^[1] No artigo em si não utilizou da palavra prova de trabalho, mas já continha o conceito de forçar o usuário à provar que realizou alguma tarefa para conseguir utilizar do serviço, com o intuito de desmotivar uso inútil.

O conceito de Proof of Work (PoW) tem suas raízes em pesquisas iniciais sobre o combate ao spam e à prevenção de ataques de negação de serviço. Uma das primeiras implementações de PoW foi o Hashcash, criado pelo criptógrafo britânico Adam Back em 1997. O Hashcash foi projetado como um mecanismo anti-spam que exigia que os remetentes de e-mails realizassem uma pequena tarefa computacional, provando efetivamente que eles despenderam recursos (na forma de tempo de CPU) antes de enviar um e-mail. Essa tarefa era trivial para usuários legítimos, mas imporia um custo significativo para spammers que tentassem enviar mensagens em massa.^[2]

O sistema do Hashcash baseava-se no conceito de encontrar um valor de hash que atendesse a certos critérios, uma tarefa que exigia esforço computacional e, assim, servia como uma "prova de trabalho". A ideia era que, ao tornar computacionalmente caro enviar grandes volumes de e-mails, o spam seria reduzido.^[3]

O termo em si só foi a ser utilizado novamente em 1999, em um artigo publicado por Markus Jakobsson e Ari Juels,^[4] que formalizou a ideia do protocolo Prova de Trabalho. Desde então, foram desenvolvidos vários métodos de prova usando tal sistema, incluindo o Hashcash proposto por Adam Back em 1997.

Esse artigo também deu uma base para o que mais tarde seria a ideia de provas de trabalhos reusáveis, proposta por Hal Finney.^[5] O sistema Finny usou PoW Hashcash para cunhar novos tokens.^[6] No entanto, o sistema comprometeu a decentralização para o bem de simplicidade contando com servidor centralizado para se proteger contra o problema de gasto duplo dos fundos.^[7] Essa ideia foi mais tarde utilizada por Satoshi Nakamoto na criação do Bitcoin, a primeira criptomoeda descentralizada.^[8]

Conceito

A ideia principal do protocolo POW é reduzir spam e outros ataques cibernéticos, e para isso se utiliza de um sistema onde o usuário deve provar que gastou um certo tempo para encontrar alguma resposta que satisfaça algum requisito que o verificador pedir. A tarefa de encontrar tal resposta deve ser difícil e trabalhosa para o protocolo funcionar, mas não impossível. A verificação dessa prova por outro lado deve ser muito mais rápida e fácil de ser realizada.

Podemos usar uma visão superficial do PoW em Bitcoin para exemplificar o processo: Uma nova transação é pedida para ser feita. Para isso, ela deve passar pela verificação da função SHA-256. Para um usuário gerar uma prova para adicionar ao pedido, ele deve garantir que o próximo bloco tem de ter todos os n primeiros numeros do resultado do hash o numero zero. Para gerar isso, ele adiciona um nonce criptográfico ao final do bloco, um nonce pode ser qualquer valor numérico. O nonce influência o resultado do hashing. O usuário testa nonce por nonce até encontrar um que leve ao resultado com n primeiros números sendo zero. Isso pode levar a milhares de tentativas antes de achar um nonce resposta. Para todos os outros usuários verificarem a validade desse próximo bloco, eles só precisam verificar se ele tem os primeiros n dígitos zero.

Para usuários regulares, o esforço de se gerar uma prova é mínimo, uma vez que ele não deseja realizar um grande volume de pedidos, mas usuários maliciosos que tem o intuito de sobrecarregar o sistema serão restritos pelo tempo necessário para gerar essas provas de trabalho, e não conseguirão causar nenhum dano. Além disso, caso necessário, uma função pode ser ajustada para ser mais rápida ou mais lenta de se gerar uma prova de trabalho válida, de acordo com o que o recipiente deseje.

Existem dois modos de se aplicar esse protocolo. Numa implementação de simples verificação, o usuário já possui consigo informações sobre a tarefa a realizar e só precisa computar o resultado e enviar ao avaliador. O avaliador só precisa verificar se o resultado se encaixa nos parâmetros antes de realizar o pedido. Esse modelo é o que foi proposto inicialmente para e-mails.

Outra implementação é baseada no recipiente enviar as tarefas ao usuário. O usuário realiza um pedido ao recipiente e ele, já sabendo das possíveis respostas, retorna alguma tarefa que o usuário deve realizar. Resolvido a tarefa, o resultado é enviado pelo usuário ao recipiente, e se o resultado for alguma das respostas que o recipiente sabia, ele aceita. O maior interesse de usar esse modo é a adaptabilidade do sistema, caso necessário ele pode aumentar ou diminuir a dificuldade da criação da prova, aumentando ou diminuindo o tempo necessário para o usuário gerar a prova, o que é útil para mineração em criptomoedas.

Prova de trabalho reusável

Prova de trabalho reusável foi originalmente publicado por Hal Finney em 2004. RPOW (do inglês, Reusable Proofs of Work) foi criado como um protótipo para moedas digitais, mas não tinha o propósito de se tornar nada mais que um protótipo.^[9] O desenvolvimento dele foi essencial para a criação de criptomoedas.

Nick Szabo em 2002, sugeriu que a criação de dinheiro digital seria possível e que tal dinheiro seria reconhecível como uma moeda valida conquanto fosse provado que tal valor fosse difícil de criar, e isso seria possível de ser feito definindo provas de trabalhos como valor monetário. Algumas ideias iniciais de implementar isso foi o b-money de Wei Dai e o Bit Gold do próprio Nick Szabo.

Em 2008, Satoshi Nakamoto publicou um artigo que utilizava do RPOW para criar uma moeda usando uma rede peer-to-peer, que foi chamada de Bitcoin. Desde então, vários altcoins baseados no Bitcoin foram desenvolvidos com suas próprias versões de provas.

Funcionamento

Quando um usuário realiza certa tarefa e recebe a prova de trabalho dela, ele gera um token, que contém a prova, a dificuldade da prova realizada e a assinatura do usuário que gerou o token. Esse token é uma confirmação que o usuário tem consigo um certo valor de trabalho realizado, que pode ser utilizado como uma moeda.

Normalmente, PoW não podem ser reutilizados por que um usuário poderia utilizar ele para multiplas vezes, conhecido como o problema de gasto duplo. Mas RPOW podem ser transferidos de pessoa em pessoa, e cada vez que eles são repassados, eles geram um novo RPOW que podem, novamente, ser repassados. De fato, não são o mesmo token sendo reutilizado, mas a cada transação, novos tokens idênticos são gerados enquanto os anteriores são destruídos, de forma que garanta que esses tokens realmente sejam difíceis de gerar e que eles possuem um valor real. ^[10] Qualquer pessoa pode ver o código da implementação RPOW para garantir que é impossível de se gerar moedas sem se utilizar de POW, dando confiabilidade à moeda.

Esse uso foi sugerido também para e-mails, de forma que usuários genuínos, quando mandando e retornando e-mails entre si, poderiam utilizar a prova anterior sem precisar criar uma nova. Isso beneficiaria os usuários genuínos enquanto não haveria diferença para usuários maliciosos, e assim, poderia se aumentar o custo de gerar uma prova para desmotivar ainda mais ataques cibernéticos.

Na implementação de Hal Finney o RPOW era suscetível a ataques do tipo Gasto Duplo. O RPOW era protegido pelas chaves privadas guardadas no hardware TPM e dos fabricantes que guardavam as chaves privadas, e caso um Hacker obtivesse essas chaves, a segurança desse sistema estaria ameaçada.

No Bitcoin, utiliza de RPOW para resolver o problema de atualizações assíncronas em uma rede peer-to-peer e para gerar moedas que podem ser comercializadas. Esse modelo permite que os usuários troquem moedas entre si sem precisar de nenhum intermediário, e que essas transações sejam sempre confiáveis em um banco de dados descentralizado que é o Blockchain. Isso resolve o problema de Duplo Gasto que a implementação de Hal possuía.

Implementações

Enquanto o uso original de POW foi em e-mails, o POW e RPOW são partes essenciais de critpomoedas. O Bitcoin utiliza de uma Prova de Trabalho chamada de Hashcash.^[11] Litecoin e Dogecoin utilizam do algoritmo scrypt.^[12] Bytecoin, Monero e MonetaVerde utilizam do algoritmo CryptoNight.

Além de criptomoedas, sistemas de mensagens como BitMessage, um protocolo de mensagens encriptadas anônimo centralizado, utiliza de POW.^[13]

Hashcash

O Hashcash é uma das implementações de prova de trabalho. Nos headers do hashcash, que também contém o e-mail alvo e a data da operação, existem o valor de zeros que devem ser contidos no hash além de um string de caracteres aleatórios e um contador binário.

O usuário inicialmente cria esse header e inicializa o processo com um numero aleatório adicionado ao header, depois de passar por uma função hash do 160-bit do tipo SHA-1, se o resultado possuir os primeiros 20 bits como zero, então essa hash é aceitável e ele à envia ao sistema, caso contrário, ele tenta outros numeros até conseguir um que se encaixe nisso. De maneira aleatória, um usuário teria de tentar pelo menos 2^20 valores diferentes para encontrar um que se encaixe nos requisitos.

O sistema, recebendo o header enviado, roda ele sobre a função hash SHA-1, se algum dos primeiros 20 bits forem diferente de zero, ele ignora a mensagem. Além disso, ele realiza checagens na data e no e-mail alvo, de forma a saber se a ação foi feita a pelo menos dois dias ou se o e-mail alvo estava na lista de e-mails válidos. O sistema então guarda o que foi enviado de forma a garantir que essa hash não seja utilizada novamente para outro header hash, se tentarem validar usando um hash já no sistema, ele rejeitará.

^[14][15]

scrypt

A implementação da prova de trabalho utilizando scrypt têm interesse em reduzir a influência de mineração por ASIC. Ele incorpora o algoritmo SHA-256 que é utilizado pelo bitcoin, mas os cálculos dela são muito mais serializados, assim priorizando uma RAM grande mais que um poder de processamento alto Assim scrypt é um algoritmo dependente de espaço computacional ao invés de poder computacional. Devido à isso, não existe uma competição acirrada com mineradores que possuem equipamentos especializados para mineração e não promove uma corrida de hardware especializado. Além disso, scrypt é mais rápido em aceitar novas transações comparado ao Hashcash.^[16]

CryptoNight

O protocolo de prova de trabalho do CryptoNight tem o nome de ‘Prova de Trabalho igualitário’. Essa implementação têm como foco garantir que usuários que possuem CPUs padrão e que não têm acesso a hardware especializado possuam a mesma relevância quanto usuários especializados. Ele faz isso utilizando de instruções que já estão contidas em CPU para realizar sua prova de trabalho, o que é muito trabalhoso para ser implementado em um hardware especializado. Essa implementação usa um algorítimo associado à espaço de memória para gerar a prova de trabalho. A ideia é utilizar do tempo de acesso a aleatório à memória lenta e tem enfase na dependência de latência. Todo bloco é dependente dos blocos anteriores, ao contrario do scrypt.^[17]

Outras

Além dessas implementações, existem diferentes funções de hashing utilizada em outras provas de trabalho, como o X11, Groestel, Keccak, Myriad, HEFTY1, Quark, SHA-3, scrypt-n, scrypt-jane, Ethash, Cuckoo, Momentum, Dagger, Kimoto’s Gravity Well e SHA-512.

ASIC

ASICs são hardwares de usos específicos que podem ser projetados para realizar um certo algoritmo com o minimo de tempo possível. Em relação à provas de trabalho, principalmente lidando com mineração em Bitcoin, existem ASIC especializados em realizar funções hash de forma extremamente rápida, o que reduz a efetividade da prova de trabalho em diminuir o numero de pedidos. Para evitar isso, algumas variantes de prova de trabalho e algoritmos buscam ser capaz de manter o tempo necessário para gerar as provas mesmo quando se utiliza hardware especializados, esses são chamados de ASIC-resistentes. Existem argumentos contra o desenvolvimento de sistemas resistentes a ASIC, argumentando que não é possível ser completamente resistente a ASIC e que o desenvolvimento só iria forçar desenvolvedores ASIC à desenvolver novo hardware para resolver o sistema resistente, forçando os desenvolvedores de sistemas à criar um novo sistema, e assim por diante.^[18]

Em criptomoedas, o aumento do numero de pedidos realizados pode levar à um grupo ter um maior numero de verificação, reduzindo a descentralização do sistema. Essa centralização pode levar a um grupo malicioso à manipular quais transações vão ser aceitas no blockchain e quais serão rejeitadas. Além disso, o monopólio de grandes empresas com tais equipamentos desmotiva usuários com menos poder computacional de tentar minerar, uma vez que não terá um grande retorno por bloco minerado, o que piora o problema de centralização.

Lista de funções de prova de trabalho

Lista de algumas das funções mais conhecidas de prova de trabalho:

• Módulo de raiz quadrada inteira de um primo grande
• Assinatura de Ong – Schnorr – Shamir quebrada por Pollard
• Inversão de hash parcial
• Sequências de hash
• Quebra-cabeças
• Enigma baseado em Diffie-Hellman
• Moderado
• Hokkaido
• Mbound
• Ciclo de cuco

Outros tipos de provas

Enquanto prova de trabalho tenta limitar o uso por tempo de gerar uma resposta para provar que realizou algum trabalho, novas tecnologias foram desenvolvidas para usos mais específicos ou que tem como objetivo restringir utilizando outro recurso.

• Prova de participação, utilizada pelo Peercoin, é uma dessas variantes que tenta utilizar menos energia do que PoW.
• O TorCoin utiliza da ideia de Prova de Largura de Banda ^[19].
• Prova de espaço é uma variante que ao invés de dar importância a tempo computacional, da importância a capacidade de armazenamento do computador. ^[20].
• Prova de Propriedade tenta garantir que certos dados estavam com certo usuário no momento quando a prova foi criada.^[21]
• Prova de queima, onde um usuário deve provar que ‘queimou’ um certo valor de criptomoedas para usar os serviços.
• Prova de atividade, uma combinação de prova de trabalho com prova de participação.^[22]

• Prova de capacidade, outro algoritmo baseado em espaço de memória que você deve provar que guardou um certo espaço de data chamado de ‘plots’, que será a prova.
• Prova de pesquisa, um modelo hibrido PoW e PoS que utiliza os calculos que iriam ser utilizados para gerar hashes para resolver funções do tipo BOINC^[23].

Ver também

• Função hash criptográfica
• SHA-2

Referências

1. Dwork, Cynthia; Naor, Moni. Pricing via Processing or Combating Junk Mail (PDF) (Tese). Consultado em 27 de Junho de 2016
2. «Modeling and Practice for Trustworthy and Secure Systems». www.mdpi.com (em inglês). Consultado em 16 de agosto de 2024
3. Back, Adam. Hashcash - A Denial of Service Counter-Measure (PDF) (Tese). Consultado em 27 de Junho de 2016
4. Juels, Ari; Jakobsson, Markus. Proofs of Work and Bread Pudding Protocols (Tese). Consultado em 27 de Junho de 2016
5. Finney, Hal. Reusable Proofs of Work (Tese). Consultado em 27 de Junho de 2016
6. «What is proof-of-authority consensus algorithm?». kucoin.com. Consultado em 21 de abril de 2022
7. «The genesis files: how Hal Finney's quest for digital cash led to RPOW (and more)». bitcoinmagazine.com. Consultado em 21 de abril de 2022
8. Satoshi, Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System (PDF) (Tese). Consultado em 27 de Junho de 2016
9. Finney, Hal. RPOW – Reusable Proofs of Work (Tese). Consultado em 8 de Julho de 2016
10. «Hal Finney's Email». Consultado em 8 de Julho de 2016
11. «Hashcash - Bitcoin Wiki». webcache.googleusercontent.com. Consultado em 4 de julho de 2016
12. «Block hashing algorithm - Litecoin Wiki». litecoin.info. Consultado em 4 de julho de 2016. Arquivado do original em 10 de agosto de 2017
13. «Proof of work - Bitmessage Wiki». bitmessage.org. Consultado em 4 de julho de 2016
14. Satoshi, Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System (Tese). Consultado em 27 de Junho de 2016
15. https://en.bitcoin.it/wiki/Hashcash Hashcash no bitcoin, acessado usando o Google cache
16. «What is the Difference Between Litecoin and Bitcoin?» (em inglês). Consultado em 4 de julho de 2016
17. «CryptoNote Technology». cryptonote.org. Consultado em 4 de julho de 2016
18. https://download.wpsoftware.net/bitcoin/asic-faq.pdf ASICs and Decentralization FAQ
19. http://cryptome.org/2013/09/tor-lira.pdf LIRA: Lightweight Incentivized Routing for Anonymity
20. https://eprint.iacr.org/2013/796.pdf Proofs of Space
21. https://en.bitcoin.it/wiki/Proof_of_Ownership+&cd=1&hl=pt-BR&ct=clnk&gl=br Proof of Ownership
22. https://eprint.iacr.org/2014/452.pdf Proof of Activity: Extending Bitcoin’s Proof of Work via Proof of Stake
23. http://wiki.gridcoin.us/Proof-of-Research Proof-of-Research