Prueba de trabajo CAPTCHA: Control de la varianza de los algoritmos

Un Proof-of-Work CAPTCHA (PoW CAPTCHA) es una herramienta de prevención de bots que solicita al dispositivo del usuario que resuelva un pequeño rompecabezas computacional en segundo plano. En lugar de obligar a los usuarios a hacer clic en semáforos o descifrar texto distorsionado, el navegador realiza la tarea automáticamente.

El resultado suele ser una experiencia más fluida: ningún desafío visual, ningún seguimiento innecesario y, por lo general, solo una corta espera de unos segundos. Para los bots, sin embargo, el costo se acumula. Cada solicitud requiere tiempo y energía del dispositivo, lo que encarece el abuso a gran escala.

Pero los algoritmos estándar de prueba de trabajo tienen un problema: no miden el progreso. Resolver el acertijo es como jugar a la lotería una y otra vez hasta que ganas. Perder muchas veces no hace que el próximo intento tenga más probabilidades de tener éxito.

Esa aleatoriedad plantea un reto fundamental para los CAPTCHA. Si la prueba de trabajo no se utiliza correctamente, el reto del CAPTCHA se convierte en una lotería. Un usuario podría acertar al primer intento, completándolo en un segundo, mientras que otro usuario legítimo podría necesitar muchos intentos y tener que esperar diez segundos. Para los sitios web y las aplicaciones web que necesitan bloquear a los bots sin frustrar a los usuarios reales, ese tipo de variabilidad es inaceptable.

Por eso hemos creado Friendly Captcha, una herramienta fácil de usar, código abierto captcha basado en la prueba de trabajo. Friendly Captcha resuelve el problema de la variabilidad mediante un sistema de prueba de trabajo más sofisticado: en lugar de basarse en un único rompecabezas complejo, similar a una lotería, divide el trabajo en múltiples rompecabezas criptográficos más pequeños. Esto hace que los tiempos de resolución sean más predecibles, suaviza los valores atípicos debidos a la mala suerte y permite que el widget muestre el progreso en lugar de dejar a los usuarios esperando a ciegas.

El desafío de prueba de trabajo de Friendly Captcha no solo encarece los ataques, sino que también hace que los tiempos de resolución sean predecibles y justos. Creemos que un buen CAPTCHA debería requerir aproximadamente la misma cantidad de recursos computacionales por parte de dispositivos comparables, sin bloquear nunca a los usuarios reales.

Nuestra prueba de trabajo

La idea detrás de PoW es que el puzzle (también llamado desafío) debe ser barato de verificar, pero caro de calcular.

Un PoW que fuera "haz hash de esta cadena 1 millón de veces" sería caro de calcular, pero igual de caro de verificar. En cambio, la mayoría de los algoritmos PoW hacen que el usuario busque una aguja en un pajar: generamos un cadena rompecabezas py pedir al usuario que encuentre un nonce q tal que el hash de p y q concatenada cumple algunos criterios poco comunes. Si utilizamos una buena función hash, cualquier cadena de entrada tiene las mismas probabilidades de cumplir este criterio que otra.

Recuerda que cualquier byte o cadena puede interpretarse como un número. Tomamos los 4 primeros bytes del hash y los interpretamos como un número entero de 32 bits. Si ese número está por debajo de algún umbral T (que podríamos llamar el inverso de la dificultad) entonces es una solución válida. Cualquier entrada hash tiene la misma probabilidad de cumplir ese criterio, por lo que para encontrar la solución el usuario sólo tendría que probar diferentes valores para el nonce q hasta encontrar una solución ganadora. No es muy diferente de jugar mucho a la lotería.

Verificación en pseudocódigo

puzzleString = "mi-cadena-puzzle"
threshold = 1000 // Cuanto más bajo, más difícil es el puzzle
nonce = "3456356782345" // Este es el valor que el solucionador cambia para intentar encontrar una solución válida

hash_resultado = hash(puzzleString + nonce)
value = toUint32(resultado_hash[0:4])

si valor < umbral {
    print "¡Válido!"
} else {
    print "Solución no válida :("
}

¿Cuántos intentos hacen falta?

Si tus probabilidades de ganar la lotería son de una entre un millón, después de un millón de intentos tus probabilidades de ganar al menos una vez son de alrededor de 63,2% (1 - (1/un_millón)^un_millón o 1 - binom.pmf(1, un_millón, 1/un_millón)). He aquí un gráfico de densidad:

La mayoría de la gente necesita alrededor de un millón de intentos, pero algunos usuarios tienen muy mala suerte y necesitan 3 millones de intentos (~5% de hecho) ¡o incluso más! En otras palabras: hay una gran variación en el número de intentos necesarios. Esto es problemático para un PoW CAPTCHA: el usuario abandonará la espera si tarda 5 veces más de lo esperado. No les importa cuál sea la media matemática, sólo quieren registrarse en su sitio web.

Para una experiencia de usuario decente, el usuario también merece algún tipo de indicador de progreso. Basta con mostrar "resolviendo el captcha" durante 10 segundos sin ninguna indicación de hará que el usuario se dé por vencido y piense que el sitio web está roto. Si en cambio hay una barra de progreso que aumenta con el tiempo es mucho más tolerable.

El problema es que no hay progreso, nadie sabe cuándo encontrará el nonce que cree un hash que satisfaga los criterios. Afortunadamente, existe una solución sencilla tanto para el problema del progreso como para el de la varianza: pedimos a los usuarios que encuentren más de un nonce.

Problemas múltiples y más fáciles

En lugar de hacer que el usuario encuentre el nonce de 1 entre un millón, podemos hacer que encuentre 10 nonces para un problema de 1 entre 100k. El número esperado de intentos sigue siendo el mismo, ¡pero ahora podemos mostrar una barra de progreso al usuario!

No sólo resolvemos el problema de progreso, sino que también disminuimos la varianza de cuántos intentos fueron necesarios en total. A medida que aumentamos el número de nonces que pedimos, la varianza disminuye. Vamos a graficar eso:

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

un_millón = 1000000

n_intentos = np.arange(0, 5*un_millón, 1000)

fracción_todavía_resolviendo_1m = [binom.cdf(1, n, 1/un_millón) for n in n_intentos]
fracción_aún_solucion_500k = [binom.cdf(2, n, 2/un_millón) para n en n_intentos].
fracción_aún_solucion_200k = [binom.cdf(5, n, 5/un_millón) para n en n_intentos].
fracción_aún_solucion_100k = [binom.cdf(10, n, 10/un_millón) para n en n_intentos].
fracción_aún_solucion_50k = [binom.cdf(20, n, 20/un_millón) para n en n_intentos].

plt.figure(figsize=(12, 6))
plt.plot(n_intentos, fraction_still_solving_1m, label="1 premio de lotería, 1/1M")
plt.plot(n_intentos, fracción_sigue_resolviendo_500k, label="2 premios de lotería, 1/500K")
plt.plot(n_intentos, fraccion_sigue_resolviendo_200k, label="5 premios de lotería, 1/200K")
plt.plot(n_intentos, fraccion_sigue_resolviendo_100k, label="10 premios de lotería, 1/100K")
plt.plot(n_intentos, fracción_aún_solucion_50k, label="20 premios de lotería, 1/50K")
plt.legend()
plt.ylabel("Fracción que aún no ha terminado")
plt.xlabel("Cantidad de intentos")
plt.show()

Observando este gráfico podemos ver que si hacemos que la gente juegue a una sola lotería, ¡alrededor de 1 de cada 10 personas tardará más de 4 veces más que la media! Eso es inaceptable para un CAPTCHA, pero a medida que aumentamos la cantidad de victorias requeridas para una lotería más simple disminuimos la varianza considerablemente. En forma de tabla, cuántas personas no habrán terminado aún después de N intentos:

También podemos representar gráficamente la función de masa de probabilidad (abajo), que muestra claramente la varianza: el número esperado de intentos es aproximadamente el mismo, pero la varianza es mucho menor.

Los inconvenientes de exigir más soluciones

La primera es la necesidad de enviar más soluciones, lo que requiere un poco más de ancho de banda. En Friendly Captcha cada solución es un valor de 8 bytes transmitido como base64, por lo que pasar de 10 a 20 soluciones requeriría unos 106 caracteres adicionales (10*8*(4/3)).

En segundo lugar, simplemente hay más soluciones que verificar, pero dado que la verificación es barata, esto no importa.

Conclusión

Las pruebas de trabajo no suelen tener noción de progreso. Cualquier intento tiene la misma probabilidad que el siguiente de encontrar la solución. Al requerir múltiples soluciones de prueba de trabajo podemos disminuir la varianza, así como proporcionar una noción de progreso, ambas características son requisitos para un CAPTCHA basado en la prueba de trabajo.

¿Quiere ver la prueba de funcionamiento CAPTCHA en acción? Pruebe la demostración aquí. La biblioteca CAPTCHA de código abierto y el código del widget se encuentran en aquí.

FAQ