Prova di lavoro CAPTCHA: Controllo della varianza degli algoritmi

Proof-of-Work CAPTCHA (PoW CAPTCHA) è uno strumento di prevenzione dei bot che richiede al dispositivo dell'utente di risolvere un piccolo rompicapo computazionale in background. Anziché chiedere agli utenti di cliccare su semafori o decifrare testi distorti, il browser esegue l'operazione automaticamente.

Il risultato è spesso un'esperienza più fluida: nessuna sfida visiva, nessun tracciamento non necessario e solitamente solo una breve attesa di pochi secondi. Per i bot, tuttavia, il costo si accumula. Ogni richiesta richiede tempo ed energia del dispositivo, il che rende più costosi gli abusi su larga scala.

Ma gli algoritmi standard di proof-of-work hanno un problema: non misurano il progresso. Risolvere il puzzle è come giocare alla lotteria più e più volte finché non si vince. Perdere molte volte non rende il tentativo successivo più probabile di successo.

Tale casualità rappresenta una sfida cruciale per i CAPTCHA. Se la prova di lavoro (proof-of-work) non viene utilizzata correttamente, la sfida CAPTCHA si trasforma in una lotteria. Un utente potrebbe vincere al primo tentativo, completandola in un secondo, mentre un altro utente legittimo potrebbe aver bisogno di molti tentativi, con un'attesa di dieci secondi. Per i siti web e le applicazioni web che devono bloccare i bot senza creare frustrazione agli utenti reali, questo tipo di variazione è inaccettabile.

Ecco perché abbiamo creato Friendly Captcha, un sistema intuitivo, captcha open source basato sul proof-of-work. Friendly Captcha risolve il problema della varianza grazie a un sistema proof-of-work più sofisticato: invece di affidarsi a un unico rompicapo complesso, simile a una lotteria, suddivide il lavoro in più rompicapo crittografici più piccoli. Ciò rende i tempi di risoluzione più prevedibili, attenua i valori anomali dovuti alla sfortuna e permette al widget di mostrare lo stato di avanzamento, invece di lasciare gli utenti in un'attesa alla cieca.

La sfida proof-of-work di Friendly Captcha non si limita a rendere costosi gli attacchi, ma garantisce anche che i tempi di risoluzione siano prevedibili ed equi. Riteniamo che un buon CAPTCHA debba richiedere all’incirca lo stesso carico di calcolo da parte di dispositivi comparabili, senza mai ostacolare gli utenti reali.

La nostra configurazione di proof-of-work

L'idea alla base del PoW è che il rompicapo (chiamato anche sfida) deve essere economico da verificare, ma costoso da calcolare.

Un PoW del tipo "hash questa stringa 1 milione di volte" sarebbe costoso da calcolare, ma altrettanto costoso da verificare. Invece la maggior parte degli algoritmi PoW fa sì che l'utente cerchi un ago in un pagliaio: generiamo un stringa di puzzle pe chiedere all'utente di trovare un nonce q tale che l'hash di p e q concatenate soddisfano alcuni rari criteri. Se utilizziamo una buona funzione hash, qualsiasi stringa in ingresso ha la stessa probabilità di soddisfare questo criterio di un'altra.

Ricordate che qualsiasi byte o stringa può essere interpretato come un numero. Prendiamo i primi 4 byte dell'hash e li interpretiamo come un numero intero a 32 bit. Se questo numero è inferiore a una certa soglia T (che si potrebbe chiamare l'inverso della difficoltà), allora è una soluzione valida. Qualsiasi hash inserito ha la stessa probabilità di soddisfare questo criterio, quindi per trovare la soluzione l'utente dovrebbe semplicemente provare diversi valori per il nonce q finché non trovano una soluzione vincente. Non è poi così diverso dal giocare spesso alla lotteria!

Verifica in pseudocodice

stringa-puzzle = "mia-stringa-puzzle"
soglia = 1000 // Più bassa è, più difficile è il puzzle
nonce = "3456356782345" // Questo è il valore che il risolutore cambia per cercare di trovare una soluzione valida

hash_risultato = hash(puzzleString + nonce)
valore = toUint32(hash_risultato[0:4])

se valore < soglia {
    print "Valido!"
} else {
    print "Soluzione non valida :("
}

Quanti tentativi sono necessari?

Se le probabilità di vincere alla lotteria sono una su un milione, dopo un milione di tentativi le probabilità di vincere almeno una volta sono circa 63,2% (1 - (1/un_milione)^un_milione o 1 - binom.pmf(1, un_milione, 1/un_milione)). Ecco un grafico della densità:

La maggior parte delle persone impiega circa un milione di tentativi, ma alcuni utenti saranno davvero sfortunati e avranno bisogno di 3 milioni di tentativi (~5% in realtà) o anche di più! In altre parole: c'è una grande varianza nel numero di tentativi necessari. Questo è problematico per un PoW CAPTCHA: l'utente rinuncerà all'attesa se impiega 5 volte più tempo del previsto. A loro non importa quale sia la media matematica, vogliono solo iscriversi al vostro sito web.

Per un'esperienza d'uso decente, l'utente merita anche una sorta di indicatore di progresso. Mostrare solo "risolvere il captcha" per 10 secondi senza alcuna indicazione di ciò, l'utente si arrenderà e penserà che il sito web sia rotto. Se invece c'è una barra di avanzamento che aumenta nel tempo è molto più tollerabile.

Il problema è che non c'è progresso, nessuno sa quando troverà il nonce che crea un hash che soddisfa i criteri. Fortunatamente, esiste una soluzione semplice sia al problema dell'avanzamento che a quello della varianza: chiediamo agli utenti di trovare più di un nonce.

Problemi multipli e più semplici

Invece di far trovare all'utente il nonce 1 su un milione, possiamo fargli trovare 10 nonce per un problema 1 su 100k. Il numero di tentativi previsti è sempre lo stesso, ma ora possiamo mostrare all'utente una barra di progresso!

Non solo si risolve il problema dell'avanzamento, ma si riduce anche la varianza del numero totale di tentativi necessari. Aumentando il numero di nonces richiesti, la varianza diminuisce. Tracciamo il grafico:

importare matplotlib.pyplot come plt
importare numpy come np
da scipy.stats importa binom

un_milione = 1000000

n_tentativi = np.arange(0, 5*un_milione, 1000)

frazione_ancora_risolutiva_1m = [binom.cdf(1, n, 1/one_milione) per n in n_tentativi]
fraction_still_solving_500k = [binom.cdf(2, n, 2/one_milione) per n in n_tentativi]
frazione_ancora_soluzione_200k = [binom.cdf(5, n, 5/un_milione) per n in n_tentativi]
frazione_ancora_soluzione_100k = [binom.cdf(10, n, 10/un_milione) per n in n_tentativi]
frazione_ancora_soluzione_50k = [binom.cdf(20, n, 20/un_milione) per n in n_tentativi]

plt.figure(figsize=(12, 6))
plt.plot(n_tentativi, fraction_still_solving_1m, label="1 vincita alla lotteria, 1/1M")
plt.plot(n_attempts, fraction_still_solving_500k, label="2 vincite alla lotteria, 1/500K")
plt.plot(n_attempts, fraction_still_solving_200k, label="5 vincite alla lotteria, 1/200K")
plt.plot(n_attempts, fraction_still_solving_100k, label="10 vincite alla lotteria, 1/100K")
plt.plot(n_attempts, fraction_still_solving_50k, label="20 vincite alla lotteria, 1/50K")
plt.legend()
plt.ylabel("Frazione che non ha ancora finito")
plt.xlabel("Quantità di tentativi")
plt.show()

Osservando questo grafico possiamo vedere che se facciamo giocare le persone a una singola lotteria, circa 1 persona su 10 impiegherà più di 4 volte più tempo della media! Questo è inaccettabile per una CAPTCHA, ma se aumentiamo la quantità di vincite richieste per una lotteria più semplice, diminuiamo notevolmente la varianza. In forma di tabella, quante persone non avrebbero ancora finito dopo N tentativi:

Possiamo anche tracciare la funzione di massa di probabilità (sotto) che mostra chiaramente anche la varianza: il numero di tentativi previsti è circa lo stesso, ma la varianza è molto più bassa.

Gli svantaggi di richiedere più soluzioni

La richiesta di un maggior numero di soluzioni presenta alcuni aspetti negativi: il primo è la necessità di inviare un maggior numero di soluzioni che richiedono una maggiore larghezza di banda. In Friendly Captcha ogni soluzione è un valore di 8 byte trasmesso in base64, quindi passare da 10 a 20 soluzioni richiederebbe circa 106 caratteri in più (10*8*(4/3)).

In secondo luogo, ci sono semplicemente più soluzioni da verificare, ma dato che la verifica è economica, questo non ha importanza.

Conclusione

La prova di lavoro di solito non ha alcuna nozione di progresso. Ogni tentativo ha la stessa probabilità del successivo di trovare la soluzione. Richiedendo più soluzioni di prova del lavoro, possiamo ridurre la varianza e fornire una nozione di progresso, entrambi requisiti per un CAPTCHA basato sulla prova del lavoro.

Volete vedere la prova di lavoro CAPTCHA in azione? Provate la demo qui. La libreria open source CAPTCHA e il codice del widget sono disponibili qui.

FAQ