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

Os algoritmos de prova de trabalho (PoW) geralmente não têm noção de progresso, em vez disso, são mais como jogar na lotaria milhões de vezes até ganhar. Perder um milhão de vezes não influencia as suas hipóteses de ganhar a próxima.

Criámos um fácil de utilizar, captcha de fonte aberta baseado numa prova de trabalho. É importante que este captcha leve aproximadamente a mesma quantidade de computação para ser completado por qualquer utilizador, e ainda mais importante que não existam valores anómalos.

No exemplo da lotaria não há garantias, um utilizador pode ganhar na primeira tentativa e outro pode precisar de muitas tentativas. Antes de nos debruçarmos sobre as especificidades e a solução simples, vamos explorar as propriedades de um bom problema de prova de trabalho.

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