Prova di lavoro CAPTCHA: Controllo della varianza degli algoritmi

Gli algoritmi PoW (Proof of work) in genere non hanno una nozione di progresso, ma sono più simili a giocare alla lotteria milioni di volte finché non si vince. Perdere un milione di volte non influenza le possibilità di vincere la prossima.

Abbiamo creato un facile da usare, captcha open source basato sulla prova di lavoro. È importante che questo captcha richieda all'incirca la stessa quantità di calcoli per ogni utente, e ancora più importante è che non ci siano anomalie.

Nell'esempio della lotteria non ci sono garanzie, un utente potrebbe vincere al primo tentativo e un altro potrebbe aver bisogno di molti tentativi. Prima di addentrarci nei dettagli e nella soluzione semplice, esploriamo le proprietà di una buona prova di lavoro.

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