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

Los algoritmos de prueba de trabajo (PoW) no suelen tener noción de progreso, sino que son más parecidos a jugar a la lotería millones de veces hasta ganar. Perder un millón de veces no influye en tus posibilidades de ganar la siguiente.

Hemos creado un fácil de usar, código abierto captcha basado en pruebas de trabajo. Es importante que este captcha requiera aproximadamente la misma cantidad de cálculos para que cualquier usuario lo complete, y aún más importante que no haya valores atípicos.

En el ejemplo de la lotería no hay garantías, un usuario puede ganar en el primer intento y otro puede necesitar muchos intentos. Antes de sumergirnos en los detalles y en la solución sencilla, vamos a explorar las propiedades de un buen problema de prueba de trabajo.

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