Für viamontis haben wir ein einfaches Tool in JavaScript entwickelt, mit dessen Hilfe Auslosungen vorgenommen werden können.
Die Regeln sind einfach: Pro Euro Warenkorbwert erhält man ein Los. Unser Tool ist ähnlich einfach: Es liest die Bestellungen ein und befüllt damit eine lange Liste.
Beispiel: A hat für 1,50 Euro ein Produkt gekauft, B für 3 Euro und C für 2,99 Euro. A bekommt ein Los und landet ein Mal in der Liste, während B drei Mal eingetragen wird und C zwei Mal. Die generierte Liste sieht nun folgendermaßen aus: A, B, B, B, C, C.
Das Tool geht so alle Bestellungen durch und erstellt eine sehr lange Liste. Am Ende wird der/die Gewinnende ausgewürfelt. Dafür wird die JavaScript-Funktion Math.random() verwendet, die das Äquivalent zu einem Würfel darstellt. Bei unserem Beispiel hätte der Würfel sechs Seiten — bei 1 gewinnt A, bei 2, 3 und 4 B und bei 5 und 6 C.
Die Einträge der Liste können durch das Tool auch durcheinander gewürfelt werden, bevor die/der Gewinnende ausgewürfelt wird. Dadurch fühlt sich das Ergebnis noch zufälliger an (es hat aber keine echte Auswirkung auf die Gewinnchancen).
Die Verwendung von Math.random() sorgt dafür, dass jedes Los gleichberechtigt ist und der Nutzer des Tools auch keinen Einfluss auf das Ergebnis nehmen kann. Damit ist das Ergebnis fair und niemand wird benachteiligt.
Für alle, die es gerne ganz genau wissen wollen, tauchen wir jetzt tief in die Materie ein und finden heraus, wie diese JavaScript-Funktion im Detail funktioniert.
Der Zufall
In der Mathematik, genauer gesagt in der Wahrscheinlichkeitstheorie, ist ein Zufallsereignis das Resultat eines Zufallsexperiments. Zu einem solchen Experiment gibt es eine Menge von Ereignissen, denen jeweils eine bestimmte Wahrscheinlichkeit zugeordnet werden kann.
Nehmen wir den Wurf eines sechseitigen Würfels. Die Ergebnismenge ist {1, 2, 3, 4, 5, 6} und jedes Ereignis ist gleich wahrscheinlich mit einer Wahrscheinlichkeit von 1/6 (solange der Würfel nicht gezinkt ist).
Die Qualität eines solchen Zufallsexperiments ist von den folgenden Faktoren abhängig:
- Unvorhersagbarkeit. Es ist unmöglich vorherzusagen, welche Zahl beim nächsten Wurf gewürfelt wird.
- Unabhängigkeit. Das Ergebnis des nächsten Wurfes ist komplett unabhängig davon, welche Zahlen zuvor gewürfelt wurden.
- Unbefangeheit. Jedes Ergebnis ist gleich wahrscheinlich.
Wenn alle drei Kriterien gleichzeitig erfüllt sind, hat man es mit einem idealen Zufallsexperiment zu tun und das Ergebnis ist eine Folge von idealen Zufallszahlen.
Pseudo Zufallszahlengeneratoren (Pseudo Random Number Generator)
Wer das Thema Zufallszahlen bei Computern recherchiert, wird immer wieder auf das Wort „pseudo“ stoßen. Deshalb müssen wir uns zuerst die Frage stellen, was der Unterschied zwischen einem Zufallszahlengenerator und einem pseudo Zufallszahlengenerator ist.
Der Zufallszahlengenerator erzeugt, wie der Name schon sagt, ideal zufällige Zahlen. Wann immer man einem solchen Generator sagt „Gib mir eine Zahl“, kommt eine komplett zufällige Zahl heraus. Das Problem dabei ist, dass unsere normalen Computer so etwas nicht können. Sie sind deterministische Maschinen. Das bedeutet, dass ein Algorithmus mit exakt gleichen Eingabeparametern auch immer das exakt gleiche Ergebnis liefert.
Und genau von dieser Art sind die Zufallsalgorithmen, mit denen wir es zu tun haben. Da sie nicht echt-zufällig sind, nennen wir sie pseudo-zufällig. Pseudo Zufallsgeneratoren versuchen einen echten Zufallsgenerator möglichst exakt zu emulieren.
Wenn wir im folgenden von Zufallszahlen reden, meinen wir immer pseudo-Zufallszahlen.
Math.random()
ECMAScript (die formale Sprachdefinition, die JavaScript zugrunde liegt) definiert Math.random() folgendermaßen:
Returns a Number value with positive sign, greater than or equal to +0𝔽 but strictly less than 1𝔽, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-defined algorithm or strategy. This function takes no arguments.
Referenz: https://262.ecma-international.org/12.0/#sec-math.random
Die Funktion liefert uns also eine (pseudo-)zufällige, positive Zahl, die größer gleich 0 und kleiner 1 ist. Eines macht sofort stutzig: Wenn die Zahl immer zwischen 0 und 1 liegt, wie kann man dann z.B. eine zufällige Zahl zwischen 1 und 100 würfeln? Das ist zum Glück sehr simpel:
Math.floor((Math.random() * 100) + 1);
Zuerst wird Math.random() aufgerufen und das Ergebnis mit 100 multipliziert. Das Ergebnis ist eine Zahl, die im Intervall [0, 100) (0 liegt im Intervall, 100 nicht) liegt. Nachdem 1 aufaddiert wird, haben wir einen Ergebnisbereich von [1, 101). Zum Schluss sorgt Math.floor noch dafür, dass das Ergebnis zur nächsten ganzen Zahl abgerundet wird. Damit haben wir ein Intervall von [1, 100] und die Garantie, dass es sich um ganze Zahlen handelt.
Die Formel für beliebige Ergebnisintervalle [min, max] ist
Math.floor(Math.random() * (max - min + 1) ) + min;
Wir wissen jetzt, wie wir mit einem JavaScript-Befehl an eine (pseudo-)zufällige Zahl in einem gewählten Intervall kommen. Hier hört die Arbeit für einen Webentwickler auf.
Aber für diesen Blogbeitrag gucken wir uns natürlich ganz genau an, was unter der Haube wirklich passiert.
Grundlegende Funktionsweise von PRNGs
Mithilfe eines (oder mehrerer) Eingabeparameters (Seed) und eines Algorithmus wird eine neue Zahl erzeugt. Für den ersten Durchlauf muss ein Seed gewählt werden, während für alle weiteren Durchläufe in der Regel anhand der zuvor generierten Zufallszahl ein neuer Seed bestimmt wird. Dadurch wird eine Sequenz von Zahlen erzeugt, die echten Zufallszahlen möglichst nahe kommen soll.
Der Algorithmus
Die Generierung von Zufallszahlen ist ein wichtiges Thema in der Mathematik und in der Informatik. Dementsprechend gibt es viele Algorithmen und es kommen immer wieder neue hinzu.
Es gibt ein paar Schlüsselkriterien, die die Qualität von Zufallsgeneratoren bestimmen, u.a.:
- Periodenlänge. Da es im Digitalen nur endlich viele Zahlen gibt, und PRNGs in weiteren Durchläufen die zuvor generierte Zufallszahl als Seed verwenden, kommt man irgendwann zwangsläufig wieder beim ersten Startwert an. Dies soll natürlich möglichst spät geschehen.
- Keine Muster. Die generierten Zahlen sollten keinem simplen Muster folgen (z.B. dass ein Algorithmus am Anfang einer Sequenz kleinere Zahlen erzeugt als am Ende oder dass aufeinanderfolgende Zahlen sich ähneln).
- Gleichverteilung. Die Zahlen der Ergebnismenge sollten die gleiche Wahrscheinlichkeit haben.
- Ressourcenverbrauch. Ein Algorithmus soll möglichst effizient (in Sachen Laufzeit und Speicherverbrauch) sein.
Um die Qualität eines solchen Algorithmus zu beurteilen, muss man ihn gründlich testen. Eine bekannte Testsuite ist TestU01.
Der Einsatzzweck bestimmt die Auswahl des Algorithmus. Ressourcenverbrauch kann mal eine größere und mal eine kleinere Rolle spielen, bei kryptografischen Anwendungen ist eine hohe Qualität der Zufallszahlen essentiell.
Zufallszahlen im Chromebrowser
Xorshift128+
Xorshift Zufallsgeneratoren wurden das erste Mal von George Marsaglia beschrieben (PDF). Darauf basierend (und auf der Arbeit von Saito and Matsumoto) veröffentlichte Sebastiano Vigna seinen Xorshift128+-Algorithmus, welcher in modernen Browsern verwendet wird. Firefox, Safari und Chrome verwenden diesen Algorithmus mit leicht veränderten Parametern.
Hier ist die Implementierung in V8, der JavaScript-Engine des Chrome-Browsers
XorShift128(uint64_t state0, uint64_t state1) {
uint64_t s1 = state0;
uint64_t s0 = state1;
state0 = s0;
s1 ^= s1 << 23;
s1 ^= s1 >> 17;
s1 ^= s0;
s1 ^= s0 >> 26;
state1 = s1;
return state0+state1;
}
Wie man sieht, ist der Algorithmus sehr kurz und besteht nur aus XORs, Bitshifts und Zuweisungen. Das macht ihn sehr effizient.
Wer schon einmal Berührungspunkte mit C/C++ hatte, wird sofort sehen, was dort passiert. Für alle Anderen gehen wir den Code einmal durch.
Der Algorithmus erwartet zwei 64-Bit-Zahlen als Eingabeparameter (state0 und state1). In den ersten drei Zeilen werden nur Werte zugewiesen. s1 bekommt den Wert von state0, s0 den Wert von state1 und anschließend state0 den Wert von s0.
Jetzt beginnen die Bit-Operationen. Wir haben Bit-Shifts ( << 23 ) und XOR auf Bitebene (^=).
Was da genau passiert gucken wir uns an einem Beispiel an:
s1 sei eine 8 Bit-Zahl mit dem Wert 13 (in Binärcode 00001101)
s1 ^= s1 << 3
Zuerst wird um 3 Bits nach links geshiftet. Das bedeutet, dass alle 1en um drei Felder nach links rücken. Dadurch wird aus 00001101 -> 01101000 (104 als Dezimalzahl).
Jetzt wird ein XOR durchgeführt. XOR steht für „exklusives oder“, welches sprachlich dem „entweder … oder “ entspricht. Dabei werden zwei Zahlen Ziffernweise miteinander verglichen. Immer wenn genau eine der beiden Ziffern eine 1 ist, steht auch im Ergebnis eine 1.
00001101 (13)
01101000 (104)
--------
01100101 (101)
Die eine Zeile Code sorgt also dafür, dass aus unserer 13 eine 101 wird. Das gleiche Prinzip wird in den anderen Zeilen angewendet, nur dass nach rechts geshiftet wird.
Der Algorithmus bietet 128 Bit an Eingabe-States (2×64 Bit) und liefert 64 Bit lange Zufallszahlen.
Wie man dem Paper von Vigna entnehmen kann, hat der Generator eine maximale Periodenlänge von 2^128-1. Bei 128 Bit an Eingabeparametern ist es das bestmögliche Ergebnis. Zudem sind die 64 Bit an generierten Zahlen gleichverteilt.
Wie schon erwähnt gibt es zur Überprüfung von PRNGs u.a. die TestU01-Suite. Dort schneidet Xorshift128+ sehr gut, wenn auch nicht perfekt, ab (hier und hier). Das soll aber niemanden verunsichern: Der Algorithmus ist sehr gut und hat sich bewährt.
Aber wir sind noch nicht fertig. Als Eingabeparameter werden zwei 64-Bit-Zahlen erwartet. Und da wir gelernt haben, dass Algorithmen mit gleichen Eingabeparametern auch immer die gleiche Ausgabe erzeugen, ist davon das Ergenis abhängig.
Hier kann jeder selber austesten, was verschiedene Parameter für Auswirkungen haben. Ein Muster bedeutet, dass die erzeugte Sequenz an Zufallszahlen nicht besonders gut ist. Das ist z.B. der Fall, wenn als Parameter „1“ und „2“ ausgewählt werden. „2“ und „4“ dagegen erzeugen ein Rauschen ohne erkennbares Muster.
Aber die Muster bei manchen Parametern machen den Algorithmus nicht schlecht. Daraus folgt nur, dass auch die Eingabeparameter zufällig sein sollten. Zur Ermittlung zufälliger Startparameter ist eine sogenannte Entropiequelle nötig. Im Quellcode von V8 ist zu sehen, dass diese Quelle vom Betriebssystem abhängt.
An dieser Stelle wollen wir uns auch einmal kurz klar machen, über welche Größenordnungen wir reden.
Der Algorithmus hat 128 Bit an Eingabestates. Das sind 2^128 oder 340.282.366.920.938.463.463.374.607.431.768.211.456 mögliche Eingabeparameter.
Es werden 64 Bit große Zahlen generiert. Das sind 2^64 oder 18.446.744.073.709.551.616 mögliche Ergebnisse.
Die Zahlen, mit denen wir hier arbeiten, sind also enorm groß.
Entropiequelle unter Windows
Wenn Chrome unter Windows läuft, greift folgender Codeschnippsel zur Ermittlung der Entropiequelle:
errno_t result = rand_s(&first_half);
result = rand_s(&second_half);
SetSeed((static_cast(first_half) << 32) + second_half)
Es werden über die Funktion rand_s zwei 32-Bit-Zahlen geholt und zu einer 64-Bit-Zahl kombiniert. rand_s wird von Windows bereitgestellt und ist hier näher beschrieben. Da Windows nicht Open Source ist, können wir nicht nachgucken, wie rand_s eine Zahl ermittelt. Aber Microsoft schreibt in der Dokumentation, dass kryptografisch sichere Zahlen erzeugt werden. Das bedeutet, dass die Nutzer keine Möglichkeit haben, bestimmte Zahlen zu erzwingen.
Fertig sind wir aber immer noch nicht, da wir hier eine 64-Bit-Zahl erzeugen, aber Xorshift128+ zwei benötigt. Deshalb wird in einem letzten Schritt mit Hilfe des Murmurhash3-Algorithmus anhand der vorhandenen Zahl zwei neue generiert. Hier passiert nichts spannendes mehr, deshalb wird der Code nur der Vollständigkeit halber hier aufgeführt.
Der dazugehörige Code sieht folgendermaßen aus
void RandomNumberGenerator::SetSeed(int64_t seed) {
state0_ = MurmurHash3(bit_cast(seed));
state1_ = MurmurHash3(~state0_);
}
und hier noch der Code für Murmurhash3
uint64_t RandomNumberGenerator::MurmurHash3(uint64_t h) {
h ^= h >> 33;
h *= uint64_t{0xFF51AFD7ED558CCD};
h ^= h >> 33;
h *= uint64_t{0xC4CEB9FE1A85EC53};
h ^= h >> 33;
return h;
}
Damit sind wir am Ende angelangt. Wie wir gesehen haben, liegt der Generierung von Zufallszahlen durch Math.random() ein mehrstufiger Prozess zugrunde.
Gehen wir nun noch einmal zurück zu den Qualitätskriterien für Zufallsexperimente und betrachten sie in Hinblick auf die Verwendung von Math.random() im Auslosungstool:
- Das Ergebnis ist für den Nutzer nicht vorhersagbar, da er keine Informationen darüber bekommt, mit welchen Werten der Algorithmus rechnen wird.
- Die Ergebnisse sind voneinander unabhängig. Auch bei wiederholtem Aufrufen von Math.random() kann der Nutzer kein Muster ableiten.
- Jede Zahl im gewählten Ergebnis-Intervall ist gleich wahrscheinlich. Niemand hat einen Nachteil oder Vorteil, wenn er auf einem bestimmten Platz der Liste steht.
Alles in allem ist das Tool komplett fair. Die diskutierten Schwächen sind rein theoretischer Natur und haben für den hier gewählten Einsatzzweck keine Relevanz.
