Prova de Trabalho CAPTCHA: Controlo da variância do algoritmo

O Proof-of-Work CAPTCHA (PoW CAPTCHA) é uma ferramenta de prevenção de bots que solicita ao dispositivo do utilizador que resolva um pequeno quebra-cabeças computacional em segundo plano. Em vez de obrigar as pessoas a clicar em semáforos ou a decifrar texto distorcido, o navegador realiza essa tarefa automaticamente.

O resultado é muitas vezes uma experiência mais fluida: sem desafios visuais, rastreamento desnecessário e, geralmente, apenas uma curta espera de alguns segundos. Para os bots, no entanto, o custo acumula-se. Cada pedido requer tempo e energia do dispositivo, o que torna o abuso em larga escala mais dispendioso.

Mas os algoritmos padrão de prova de trabalho têm um problema: não medem o progresso. Resolver o puzzle é como jogar na lotaria vezes sem conta até ganhar. Perder muitas vezes não torna a tentativa seguinte mais provável de ter sucesso.

Essa aleatoriedade representa um desafio crucial para os CAPTCHA. Se a prova de trabalho não for utilizada corretamente, o desafio do CAPTCHA transforma-se numa lotaria. Um utilizador pode acertar à primeira tentativa, concluindo-o num segundo, enquanto outro utilizador legítimo pode precisar de várias tentativas, tendo de esperar dez segundos. Para sites e aplicações web que precisam de bloquear bots sem frustrar os utilizadores reais, esse tipo de variação é inaceitável.

É por isso que criámos o Friendly Captcha, um sistema intuitivo, captcha de fonte aberta baseado na prova de trabalho. O Friendly Captcha resolve o problema da variabilidade com um sistema de prova de trabalho mais sofisticado: em vez de depender de um único enigma complexo, semelhante a um sorteio, divide o trabalho em vários enigmas criptográficos mais pequenos. Isto torna os tempos de resolução mais previsíveis, atenua os picos de azar e permite que o widget mostre o progresso, em vez de deixar os utilizadores à espera sem saber o que se passa.

O desafio de prova de trabalho do Friendly Captcha não se limita a tornar os ataques dispendiosos. Também torna os tempos de resolução previsíveis e justos. Acreditamos que um bom CAPTCHA deve exigir aproximadamente a mesma quantidade de computação por parte de dispositivos comparáveis, sem nunca bloquear utilizadores reais.

A nossa configuração de prova de trabalho

A ideia subjacente ao PoW é que o puzzle (também designado por desafio) deve ser barato de verificar, mas caro de calcular.

Um PoW que fosse "fazer o hash desta cadeia 1 milhão de vezes" seria caro de calcular, mas igualmente caro de verificar. Em vez disso, a maioria dos algoritmos PoW faz com que o utilizador procure uma agulha num palheiro: geramos um cadeia de puzzles pe pedir ao utilizador que encontre um nonce q de tal forma que o hash de p e q concatenadas satisfazem alguns critérios raros. Se utilizarmos uma boa função de hash, qualquer string de entrada tem a mesma probabilidade de satisfazer este critério que outra.

Lembre-se que qualquer byte ou string pode ser interpretado como um número. Pegamos nos primeiros 4 bytes do hash e interpretamo-los como um número inteiro de 32 bits. Se esse número for inferior a um certo limiar T (a que se pode chamar o inverso da dificuldade), então é uma solução válida. Qualquer entrada de hash tem a mesma probabilidade de satisfazer esse critério, pelo que, para encontrar a solução, o utilizador só teria de experimentar valores diferentes para o nonce q até encontrarem uma solução vencedora. Não é muito diferente de jogar muitas vezes na lotaria!

Verificação em pseudocódigo

puzzleString = "my-puzzle-string"
threshold = 1000 // Quanto mais baixo, mais difícil é o puzzle
nonce = "3456356782345" // Este é o valor que o solucionador muda para tentar encontrar uma solução válida

hash_result = hash(puzzleString + nonce)
valor = toUint32(hash_result[0:4])

se valor < limiar {
    print "Válido!"
} else {
    imprima "Solução inválida :("
}

Quantas tentativas são necessárias?

Se a probabilidade de ganhar na lotaria é de uma em um milhão, após um milhão de tentativas a probabilidade de ganhar pelo menos uma vez é de cerca de 63,2% (1 - (1/um_milhão)^um_milhão ou 1 - binom.pmf(1, um_milhão, 1/um_milhão)). Aqui está um gráfico de densidade:

A maioria das pessoas faz cerca de um milhão de tentativas, mas alguns utilizadores têm muito azar e precisam de 3 milhões de tentativas (~5% na realidade) ou até mais! Por outras palavras: existe uma grande variação no número de tentativas necessárias. Isto é problemático para um PoW CAPTCHA: o utilizador desistirá de esperar se demorar 5 vezes mais do que o esperado. O utilizador não quer saber qual é a média matemática, apenas quer inscrever-se no seu sítio Web.

Para uma experiência de utilização decente, o utilizador também merece algum tipo de indicador de progresso. Mostrar apenas "resolver o captcha" durante 10 segundos, sem qualquer indicação de que está a funcionar, fará com que o utilizador desista e pense que o sítio Web está avariado. Se, em vez disso, houver uma barra de progresso que aumenta com o tempo, é muito mais tolerável.

O problema é que não há progresso, ninguém sabe quando vai encontrar o nonce que cria um hash que satisfaz os critérios. Felizmente, existe uma solução simples para o problema do progresso e da variância: pedimos aos utilizadores que encontrem mais do que um nonce.

Problemas múltiplos e mais fáceis

Em vez de obrigar o utilizador a encontrar o nonce de 1 em um milhão, podemos obrigá-lo a encontrar 10 nonces para um problema de 1 em 100k. O número esperado de tentativas continua a ser o mesmo, mas agora podemos mostrar uma barra de progresso ao utilizador!

Não só resolvemos o problema do progresso, como também diminuímos a variância de quantas tentativas foram necessárias no total. À medida que aumentamos o número de nonces que pedimos, a variância diminui. Vamos desenhar isso:

import matplotlib.pyplot as plt
import numpy as np
from scipy.stats import binom

um_milhão = 1000000

n_tentativas = np.arange(0, 5*um_milhão, 1000)

fracção_ainda_em_solução_1m = [binom.cdf(1, n, 1/um_milhão) for n in n_tentativas]
fracção_still_solving_500k = [binom.cdf(2, n, 2/um_milhão) for n in n_tentativas]
fracção_sem_solução_200k = [binom.cdf(5, n, 5/um_milhão) for n in n_tentativas]
fracção_sem_solução_100k = [binom.cdf(10, n, 10/um_milhão) for n in n_tentativas]
fracção_ainda_solucionar_50k = [binom.cdf(20, n, 20/um_milhão) for n in n_tentativas]

plt.figure(figsize=(12, 6))
plt.plot(n_tentativas, fracção_sem_solução_1m, label="1 prémio de lotaria, 1/1M")
plt.plot(n_tentativas, fracção_ainda_solucionar_500k, label="2 prémios de lotaria, 1/500K")
plt.plot(n_tentativas, fracção_ainda_solucionar_200k, etiqueta="5 prémios de lotaria, 1/200K")
plt.plot(n_tentativas, fracção_ainda_solucionar_100k, etiqueta="10 prémios de lotaria, 1/100K")
plt.plot(n_tentativas, fracção_sem_solução_50k, etiqueta="20 prémios de lotaria, 1/50K")
plt.legend()
plt.ylabel("Fração que ainda não terminou")
plt.xlabel("Quantidade de tentativas")
plt.show()

Olhando para este gráfico, podemos ver que, se pedirmos às pessoas que joguem numa única lotaria, cerca de 1 em cada 10 pessoas demorará mais de 4 vezes mais tempo do que a média! Isto é inaceitável para um CAPTCHA, mas à medida que aumentamos o número de prémios necessários para uma lotaria mais simples, diminuímos consideravelmente a variância. Em forma de tabela, quantas pessoas ainda não teriam terminado após N tentativas:

Também podemos traçar a função de massa de probabilidade (abaixo), que mostra claramente a variância: o número esperado de tentativas é aproximadamente o mesmo, mas a variância é muito menor.

As desvantagens de exigir mais soluções

Há algumas desvantagens em exigir mais soluções: a primeira é a necessidade de apresentar mais soluções, o que exige um pouco mais de largura de banda. No Friendly Captcha, cada solução é um valor de 8 bytes transmitido em base64, pelo que passar de 10 para 20 soluções exigiria cerca de 106 caracteres adicionais (10*8*(4/3)).

Em segundo lugar, há simplesmente mais soluções para verificar, mas dado que a verificação é barata, isso não tem importância.

Conclusão

A prova de trabalho geralmente não tem qualquer noção de progresso. Qualquer tentativa tem a mesma probabilidade que a seguinte de encontrar a solução. Ao exigir múltiplas soluções de prova de trabalho, podemos diminuir a variância, bem como fornecer uma noção de progresso, ambas as caraterísticas são requisitos para um CAPTCHA baseado em prova de trabalho.

Quer ver a prova de trabalho CAPTCHA em ação? Experimente a demonstração aqui. A biblioteca de código aberto CAPTCHA e o código do widget encontram-se aqui.

FAQ