# Enigmas não terceirizáveis

Em criptografia, um enigma não terceirizável (do inglês non-outsourceable puzzle) é um tipo de prova de trabalho criada para desencorajar a concentração da capacidade de mineração nas mãos de poucas mining pools, situação que vai de encontro com um dos objetivos originais do Bitcoin, que é a descentralização.

## Contexto

Uma mining pool é uma abordagem de mineração na qual diversos mineradores contribuem para a geração de um novo bloco, e então compartilham a recompensa entre si, de acordo com o processamento computacional que cada minerador contribuiu. Uma "share" é concedida aos membros que apresentarem uma prova do trabalho que o seu minerador resolveu.
Mining pools são atrativas para mineradores por conta da dificuldade de se conseguir minerar um bloco utilizando hardware mais lento - uma característica que só piora com o tempo, dado que, em Bitcoin, a dificuldade de se minerar um novo bloco aumenta a cada 2016 blocos. Um minerador que faz parte de uma organização dessas essencialmente troca uma baixa possibilidade de ter grandes lucros (gerando o novo bloco sozinho) por uma fração da recompensa, porém com maior regularidade. Hosted mining, uma alternativa às mining pools, vai um passo além: o usuário não precisa nem ter hardware próprio, ele só aluga o hardware fornecido pela companhia de hosting.
No entanto, mesmo trazendo benefícios aos mineradores individualmente, essa abordagem leva à concentração do poder de mineração nas mãos de um pequeno número de entidades (que controlam as mining pools). Tal consolidação de poder contradiz o princípio da descentralização, que é um dos conceitos libertários principais do Bitcoin. Um dos principais temores da comunidade é o chamado ataque de 51%, no qual uma única entidade que contribui para a maior parte do hashrate de mineração (a unidade de poder de processamento na plataforma Bitcoin) teria total controle da rede e poderia manipular a blockchain como bem quisesse.

## Propostas

O maior culpado por essa centralização de poder seria o mecanismo atual de recompensa do Bitcoin (prova de trabalho), que não apresenta nenhum tipo de incentivo para que os mineradores trabalhem sozinhos. Pelo contrário, ele serviria para reforçar o cenário atual: membros de uma pool inerentemente não confiam uns nos outros, o que leva à necessidade de cada membro submeter ao administrador da pool provas criptográficas de que se está trabalhando para o bem da pool. Esse tipo de política só é possível porque uma prova de trabalho produzida por um membro pode ser usada (e demandada) pelo administrador da pool livremente.

### Withholding

Uma solução simples para o problema da concentração do poder de mineração, mas que não traz nenhum tipo de benefício econômico para o minerador é chamada Withholding. Nela, o minerador encontra uma solução enquanto trabalha como um participante de uma mining pool, mas não publica o novo bloco para o administrador da pool. Com isso, a mining pool deixa de receber a recompensa pelo bloco - o que diminui o seu rendimento - e o minerador ainda continua recebendo sua recompensa pelos blocos encontrados pelos demais membros da pool. Ele se prejudica economicamente, visto que não consegue gastar a recompensa pelo bloco encontrado (se esse bloco fosse publicado para o administrador, o minerador receberia pelo menos uma parte da recompensa, proporcional à quantidade de trabalho), mas também consegue prejudicar a pool.

### Nonoutsourceable Scratch-Off Puzzle

A solução técnica chamada Nonoutsourceable Scratch-Off Puzzle propõe a criação de enigmas não terceirizáveis: provas de trabalho cujo objetivo é evitar a centralização do poder de mineração, e que garantem que se o administrador de uma mining pool pode terceirizar o trabalho para um minerador, esse minerador pode, por sua vez, roubar a recompensa sem produzir nenhuma evidência que poderia identificá-lo. Tal possibilidade, por sua vez, diminuiria o incentivo para se terceirizar a mineração, visto que o administrador pode ter sua recompensa roubada pelo minerador, sem nenhuma maneira de provar a participação do mesmo na fraude.
A solução proposta pretende alcançar seu objetivo por meio de duas técnicas:
* O enigma é gerado de tal maneira que, se um minerador faz grande parte do trabalho de mineração, ele possui uma parte grande o suficiente de uma "chave privada" que ele pode usar no futuro para associar a recompensa à sua própria chave pública, efetivamente roubando a recompensa do administrador da pool.
* Oferece-se uma alternativa de zero-conhecimento para que o minerador possa gastar a recompensa roubada de uma maneira que não revele nenhum tipo de informação, inclusive informação que poderia ser utilizada para comprometer o minerador.
Primeiramente cria-se um enigma não terceirizável fraco, que só garante a propriedade 1, mas não a propriedade 2. Depois, a partir de uma transformação de zero-conhecimento, um enigma não terceirizável forte é compilado a partir do enigma não terceirizável fraco.
A necessidade de se transformar um enigma não terceirizável fraco em uma versão mais forte vem da incapacidade do minerador que roubou a recompensa de efetivamente gastá-la sem repercussões negativas. Sem a proteção adicional da abordagem de zero-conhecimento - uma técnica na qual um usuário pode gastar unidades de uma criptomoeda sem que os demais participantes da transação conheçam sua identidade -, o minerador poderia enfrentar um processo legal, e sua reputação perante as demais mining pools certamente estaria comprometida.
O nome scratch-off vem da comparação comum feita entre a mineração de bitcoins e a compra de bilhetes de uma loteria: um minerador gasta uma unidade de esforço pra descobrir se ele tem um bilhete premiado.

### Two-Phase Proof-of-Work

Outra implementação de enigmas não terceirizáveis proposta é chamada Two-Phase Proof-of-Work, e tem como principais objetivos - além de desencorajar a criação de grandes mining pools - uma transição fácil a partir dos enigmas atuais e a manutenção do investimento atual em infra-estrutura de mineração. Nessa abordagem, temos dois enigmas ao invés de um, sendo que:
* O hash duplo do cabeçalho é menor que uma parâmetro de dificuldade $X$.
* O cabeçalho é então assinado usando a chave privada da transação coinbase, e o hash dessa assinatura é menor que um parâmetro de dificuldade $Y$.
O primeiro enigma é exatamente igual ao enigma criptográfico atual. Os computadores que fazem a mineração atualmente são otimizados para calcular esse tipo de enigma, o que permite reutilizar a infra-estrutura atual sem maiores problemas. O valor do parâmetro $X$ é geralmente menor do que o valor da dificuldade atual da rede Bitcoin.
Já no segundo enigma, toma-se a solução do primeiro enigma, e é pedido que os mineradores assinem essa solução com a chave privada do endereço de pagamento. Pede-se também que os mineradores verifiquem se o hash desse resultado é menor que o parâmetro de dificuldade $Y$.
Por conta do parâmetro $X$ ser menor do que a dificuldade atual da rede, os mineradores podem produzir um número maior de soluções parciais, e usar um equipamento secundário para fazer o cálculo do segundo enigma, até chegar a uma solução completa. Com um $Y$ suficiente pequeno (maior dificuldade), o administrador da pool não vai conseguir receber todas as soluções parciais e testá-las uma a uma, dado que as operações para resolver o segundo enigma são tão caras quanto as operações para resolver o primeiro enigma. Dessa maneira, o administrador também vai ter que terceirizar a resolução do segundo enigma para os mesmos mineradores - já que os mesmos possuem as chaves privadas. Os mineradores que chegarem a uma soluçaõ poderão, então, manter a recompensa para si mesmos.

## Críticas

Críticas comuns a esse tipo de enigma incluem:
* Pode ser mais fácil encontrar um participante desonesto de uma mining pool do que os defensores dos enigmas não tercerizáveis levam a crer. Isso é particularmente verdadeiro em versões mais fracas dos enigmas, nas quais um minerador pode ser detectado ao tentar gastar a recompensa roubada, devido à falta de anonimato: nesse cenário, o administrador da mining pool e os mineradores podem concordar em usar um certo prefixo do espaço de valores de nonce como uma marca d'água. O administrador da mining pool só aceitaria soluções com a marca d'água, e se o minerador que roubou a solução tentasse gastá-la, a marca d'água seria facilmente detectável.
* Contratos inteligentes não seriam mais viáveis com a solução Nonoutsourceable Scratch-Off Puzzle, por conta do uso da opção de pagamento de zero-conhecimento.
* As soluções usam conceitos criptográficos mais complexos, que podem levar a erros durante a implementação.
* Usar esse tipo de enigma também afetaria mining pools públicas, como a P2Pool, que não estariam contribuindo para o problema da concentração do poder de mineração, por conta do seu aspecto distribuído. Um contra-argumento comum à essa crítica é que essa mining pool específica representa somente 2% do poder de mineração de bitcoins.
* Se a qualquer momento mais de 51% dos mineradores decidirem impedir os demais usuários de minerar bitcoins sozinhos (sem ser parte de uma mining pool), eles só precisam ignorar os blocos criados por tais mineradores, e só aceitar blocos com uma determinada identificação da pool à qual o minerador pertence. Em Julho de 2014, a mining pool GHash.IO efetivamente ultrapassou o limiar de 51% do poder de mineração de bitcoins, levando a comunidade a discutir soluções para essa possível ameaça. Desde então a mining pool GHash.IO se comprometeu a limitar sua participação no poder de mineração a 39.99%. Essa ocorrência, no entanto, provê embasamento à crítica aos enigmais não terceirizáveis no que diz respeito à ataques de 51%.

## Utilização

Permacoin é uma criptomoeda alternativa que visa aproveitar os recursos computacionais dos mineradores - normalmente desperdiçados durante o processo de mineração de bitcoins, dada a natureza das provas de trabalho convencionais - para replicar bases de conhecimento importantes, como bibliotecas virtuais.
Dado que a descentralização geográfica (tanto do processamento durante a mineração quanto do armazenamento dos dados sendo replicados) é de grande importância para o Permacoin, se os mineradores pudessem facilmente terceirizar o processamento e armazenamento dos dados para provedores de nuvem, o objetivo dessa criptomoeda estaria comprometido, visto que os dados estariam novamente nas mãos de poucas companhias, em um número limitado de lugares.
Para resolver esse problema em potencial, Permacoin utiliza uma versão fraca de um enigma não terceirizável. Para se desencorajar a terceirização do processamento por parte dos mineradores, associa-se a chave privada do minerador à solução do enigma, de forma que se o minerador desejar terceirizar o processamento do enigma, ele precisará compartilhar sua chave privada com o provedor de nuvem - caso contrário, não será capaz de receber o prêmio pela solução. Para se desencorajar a terceirização do armazenamento dos dados, durante o processo de resolução do enigma é necessário realizar diversas consultas aos dados, em posições aleatórias (a aleatoriedade é providenciada pelo uso de um oráculo). Se o processamento do minerador é feito localmente e o armazenamento é providenciado pelo provedor de nuvem, a demora causada pelos diversos acessos vai significar uma diminuição drástica das chances do minerador encontrar uma solução a tempo de ser recompensado.