Proof-of-Work CAPTCHA: Kontrolle der Algorithmus-Varianz

Ein Proof-of-Work-CAPTCHA (PoW-CAPTCHA) ist ein Tool zur Abwehr von Bots, bei dem das Gerät des Nutzers im Hintergrund ein kleines Rechenrätsel lösen muss. Anstatt den Nutzer dazu aufzufordern, auf Ampeln zu klicken oder verzerrten Text zu entziffern, erledigt der Browser diese Aufgabe automatisch.

Das Ergebnis ist oft ein besseres Nutzererlebnis: Es gibt keine visuelle Herausforderung, kein unnötiges Tracking und die Wartezeit beträgt in der Regel nur wenige Sekunden. Für Bots summieren sich die Kosten jedoch. Jede Anfrage erfordert Zeit und Energie des Geräts, wodurch groß angelegter Missbrauch verteuert wird.

Standard-Proof-of-Work-Algorithmen haben jedoch ein Problem: Sie messen den Fortschritt nicht. Das Lösen des Rätsels gleicht einem wiederholten Lottospiel, bis man gewinnt. Die vielen Niederlagen erhöhen nicht die Wahrscheinlichkeit, dass der nächste Versuch erfolgreich ist.

Diese Zufälligkeit stellt eine entscheidende Herausforderung für CAPTCHAs dar. Wenn Proof-of-Work nicht richtig eingesetzt wird, wird die CAPTCHA-Herausforderung zu einer Lotterie. So kann es passieren, dass ein Nutzer beim ersten Versuch gewinnt und in einer Sekunde fertig ist. Gleichzeitig benötigt ein anderer legitimer Nutzer viele Versuche und muss zehn Sekunden warten. Für Websites und Webanwendungen, die Bots stoppen müssen, ohne echte Menschen zu frustrieren, ist eine solche Varianz inakzeptabel.

Deshalb haben wir Friendly Captcha entwickelt: ein benutzerfreundliches Open-Source Captcha, das auf Proof-of-Work basiert. Friendly Captcha löst das Problem der Schwankungen mit einem ausgefeilteren Proof-of-Work-System. Anstatt sich auf ein einziges schwieriges, lotterieähnliches Rätsel zu verlassen, teilt Friendly Captcha die Arbeit in mehrere kleinere kryptografische Rätsel auf. Dadurch werden die Löszeiten vorhersehbarer, unglückliche Ausreißer werden ausgeglichen und das Widget kann den Fortschritt anzeigen, anstatt die Nutzer blind warten zu lassen.

Die Proof-of-Work-Herausforderung von Friendly Captcha ist nicht nur aufwendig für Angreifer. Sie sorgt auch für vorhersehbare und faire Löszeiten. Wir sind der Meinung, dass ein gutes CAPTCHA auf vergleichbaren Geräten etwa den gleichen Rechenaufwand erfordern sollte, ohne echte Menschen zu behindern.

Unser Proof-of-Work-Setup

Die Idee hinter PoW ist, dass das Rätsel (auch als Herausforderung) muss billig zu verifizieren, aber teuer zu berechnen sein.

Ein PoW, der “diese Zeichenkette 1 Million Mal hashen” würde, wäre teuer in der Berechnung, aber ebenso teuer in der Verifizierung. Stattdessen lassen die meisten PoW-Algorithmen den Benutzer nach einer Nadel im Heuhaufen suchen: Wir generieren eine Rätselkette pund bitten Sie den Benutzer, eine nonce q so dass der Hash von p und q konkateniert wird, einige seltene Kriterien erfüllt. Wenn wir eine gute Hash-Funktion verwenden, ist es genauso wahrscheinlich, dass eine beliebige Eingabezeichenkette dieses Kriterium erfüllt wie eine andere.

Denken Sie daran, dass jedes Byte oder jeder String als Zahl interpretiert werden kann. Wir nehmen die ersten 4 Bytes des Hashes und interpretieren sie als 32-Bit-Ganzzahl. Wenn diese Zahl unter einem bestimmten Schwellenwert T liegt (den Sie als den Kehrwert der Schwierigkeit bezeichnen könnten), handelt es sich um eine gültige Lösung. Jede Hash-Eingabe erfüllt dieses Kriterium mit gleicher Wahrscheinlichkeit. Um die Lösung zu finden, würde der Benutzer also einfach verschiedene Werte für die Nonce ausprobieren q bis sie eine gewinnbringende Lösung finden. Das ist nicht viel anders als ein Lotteriespiel!

Verifizierung in Pseudocode

puzzleString = "mein-puzzle-string"
threshold = 1000 // Je niedriger, desto schwieriger ist das Rätsel
nonce = "3456356782345" // Dies ist der Wert, den der Löser ändert, um eine gültige Lösung zu finden

hash_result = hash(puzzleString + nonce)
Wert = toUint32(hash_result[0:4])

wenn Wert < Schwellenwert {
    print "Gültig!"
} else {
    print "Ungültige Lösung :("
}

Wie viele Versuche sind nötig?

Wenn Ihre Chancen, im Lotto zu gewinnen, eins zu einer Million stehen, beträgt Ihre Chance, nach einer Million Versuchen mindestens einmal zu gewinnen, etwa 63,2% (1 - (1/one_million)^one_million oder 1 - binom.pmf(1, one_million, 1/one_million)). Hier ist ein Dichteplot:

Die meisten Menschen benötigen etwa eine Million Versuche, aber einige Benutzer haben wirklich Pech und benötigen stattdessen 3 Millionen Versuche (~5% in der Tat) oder sogar mehr! Mit anderen Worten: Es gibt eine große Varianz bei der Anzahl der benötigten Versuche. Das ist problematisch für ein PoW CAPTCHA: Der Benutzer wird das Warten aufgeben, wenn es 5 Mal länger dauert als erwartet. Es ist ihm egal, was der mathematische Durchschnitt ist, er möchte sich einfach nur auf Ihrer Website anmelden.

Für ein angemessenes Benutzererlebnis verdient der Benutzer auch eine Art Fortschrittsanzeige. Einfach nur anzeigen “das Captcha lösen” Wenn Sie 10 Sekunden lang keine Anzeige sehen, wird der Benutzer aufgeben und denken, die Website sei defekt. Wenn es stattdessen einen Fortschrittsbalken gibt, der mit der Zeit ansteigt, ist das viel erträglicher.

Das Problem ist, dass es keinen Fortschritt gibt. Niemand weiß, wann er die Nonce finden wird, die einen Hash erzeugt, der die Kriterien erfüllt. Glücklicherweise gibt es eine einfache Lösung sowohl für das Problem des Fortschritts als auch der Varianz: Wir bitten die Benutzer, mehr als eine Nonce zu finden.

Mehrere, einfachere Probleme

Anstatt den Benutzer dazu zu bringen, die 1:1 Million Nonce zu finden, können wir ihn 10 Nonces für ein 1:100k Problem finden lassen. Die erwartete Anzahl von Versuchen ist immer noch die gleiche, aber jetzt können wir dem Benutzer einen Fortschrittsbalken zeigen!

Wir lösen nicht nur das Fortschrittsproblem, sondern verringern auch die Varianz, wie viele Versuche insgesamt erforderlich waren. Wenn wir die Anzahl der Nonces erhöhen, die wir abfragen, nimmt die Varianz ab. Lassen Sie uns das grafisch darstellen:

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

eine_million = 1000000

n_versuche = np.arange(0, 5*eine_million, 1000)

fraction_still_solving_1m = [binom.cdf(1, n, 1/one_million) for n in n_attempts]
fraction_still_solving_500k = [binom.cdf(2, n, 2/one_million) for n in n_attempts]
fraction_still_solving_200k = [binom.cdf(5, n, 5/one_million) for n in n_attempts]
fraction_still_solving_100k = [binom.cdf(10, n, 10/one_million) for n in n_attempts]
fraction_still_solving_50k = [binom.cdf(20, n, 20/one_million) for n in n_attempts]

plt.figure(figsize=(12, 6))
plt.plot(n_attempts, fraction_still_solving_1m, label="1 Lottogewinn, 1/1M")
plt.plot(n_attempts, fraction_still_solving_500k, label="2 Lottogewinne, 1/500K")
plt.plot(n_attempts, fraction_still_solving_200k, label="5 Lottogewinne, 1/200K")
plt.plot(n_attempts, fraction_still_solving_100k, label="10 Lottogewinne, 1/100K")
plt.plot(n_attempts, fraction_still_solving_50k, label="20 Lottogewinne, 1/50K")
plt.legend()
plt.ylabel("Anteil derer, die noch nicht fertig sind")
plt.xlabel("Anzahl der Versuche")
plt.show()

Wenn wir uns diese Grafik ansehen, sehen wir, dass etwa 1 von 10 Personen mehr als viermal so lange braucht wie der Durchschnitt, wenn wir sie eine einzige Lotterie spielen lassen! Das ist für ein CAPTCHA inakzeptabel, aber wenn wir die Anzahl der erforderlichen Gewinne für eine einfachere Lotterie erhöhen, verringert sich die Varianz erheblich. In Tabellenform, wie viele Personen nach N Versuchen noch nicht fertig sind:

Wir können auch die Wahrscheinlichkeitsmassenfunktion (unten) aufzeichnen, die die Varianz ebenfalls deutlich zeigt. Die erwartete Anzahl der Versuche ist ungefähr gleich, aber die Varianz ist viel geringer.

Die Nachteile der Forderung nach mehr Lösungen

Es gibt einige Nachteile, wenn mehr Lösungen benötigt werden. Der erste ist die Notwendigkeit, mehr Lösungen zu übermitteln, was ein wenig mehr Bandbreite erfordert. Bei Friendly Captcha ist jede Lösung ein 8-Byte-Wert, der als base64 übertragen wird. Wenn Sie also von 10 auf 20 Lösungen erhöhen, benötigen Sie etwa 106 zusätzliche Zeichen (10*8*(4/3)).

Zweitens gibt es einfach mehr Lösungen zu verifizieren, aber da die Verifizierung billig ist, spielt das keine Rolle.

Fazit

Bei Proof-of-Work gibt es in der Regel keine Vorstellung von Fortschritt. Jeder Versuch ist genauso wahrscheinlich wie der nächste, die Lösung zu finden. Indem wir mehrere Lösungen für den Proof-of-Work verlangen, können wir die Varianz verringern und eine Vorstellung vom Fortschritt vermitteln. Beides sind Voraussetzungen für ein CAPTCHA, das auf Proof-of-Work basiert.

Möchten Sie das Proof of Work CAPTCHA in Aktion sehen? Probieren Sie die Demo hier. Die Open-Source-CAPTCHA-Bibliothek und den Widget-Code finden Sie hier.

FAQ