Generator Angka Acak Tanpa Bias

Dari mana angka-angkanya berasal

Pengundian memakai crypto.getRandomValues, generator acak browser yang aman secara kriptografis, yang diberi seed dari entropi yang dikumpulkan sistem operasi dan dirancang agar mengamati output-nya tidak memberi informasi berguna apa pun tentang angka berikutnya.

Alternatif yang paling jelas, Math.random, adalah hal yang berbeda. Ini generator pseudo-acak yang cepat - biasanya xorshift128+ - yang dibuat untuk kecepatan, diberi seed dari sesuatu seperti keadaan jam, dan state internalnya cukup kecil sehingga beberapa output saja bisa cukup untuk memulihkannya dan menebak sisanya. Spesifikasi ECMAScript secara tegas menyatakan bahwa fungsi ini tidak boleh dipakai untuk keperluan kriptografis.

Untuk memilih pemenang undian, perbedaannya jarang berpengaruh. Tetap dipakai di sini karena tidak ada biayanya, dan karena generator yang hanya kadang-kadang bisa dipercaya lebih sulit dinalar daripada yang selalu bisa dipercaya.

Bias modulo

Cara sederhana memasukkan nilai acak ke dalam rentang adalah mengambil sisa bagi dengan ukuran rentang, dan cara ini diam-diam salah setiap kali rentang itu tidak membagi habis rentang generator.

Ambil satu byte acak, 0 sampai 255, lalu minta angka dari 1 sampai 10. Ada 256 kemungkinan byte dan 10 kemungkinan jawaban, dan 256 bukan kelipatan 10. Enam dari sepuluh jawaban mendapat 26 byte dan empat sisanya mendapat 25, sehingga enam jawaban pertama muncul sekitar empat persen lebih sering daripada sisanya. Dengan rentang 1 sampai 100 kemiringannya lebih besar; dengan 1 sampai 200 lebih besar lagi.

Solusinya adalah rejection sampling: hitung berapa banyak nilai di bagian atas rentang generator yang menyebabkan ketidakseimbangan, buang setiap undian yang jatuh di sana, lalu coba lagi. Di sini, artinya nilai di atas kelipatan tepat terbesar dari rentang dibuang, bukan dilipat masuk. Kadang perlu satu undian tambahan, tetapi setiap angka di rentang itu memiliki peluang yang persis sama. Rutin yang sama dipakai oleh generator kata sandi dan UUID di situs ini.

Mengundi tanpa pengulangan

Mode tanpa pengulangan melakukan sampling tanpa pengembalian, yang Anda perlukan untuk nomor lotre, undian hadiah, dan memilih sebagian daftar secara acak. Begitu sebuah nilai terpilih, nilai itu dikeluarkan dari kumpulan, sehingga tidak ada angka yang muncul dua kali dalam satu hasil.

Ini mengharuskan rentang berisi setidaknya sebanyak angka yang Anda minta - enam angka unik tidak bisa diambil dari rentang berisi empat - dan alat ini akan memberi tahu hal itu alih-alih berputar tanpa henti. Perlu dicatat bahwa yang dibatasi adalah himpunannya, bukan urutannya: angka-angka tetap diambil dalam urutan acak, sehingga hasilnya adalah acakan dari himpunan bagian yang acak, bukan sampel yang terurut. Pengurutan tersedia terpisah jika Anda ingin hasilnya berurutan.

Yang bukan kegunaannya

Alat ini bagus untuk undian, dadu, data uji, menentukan tugas mana yang dikerjakan lebih dulu, dan ratusan keputusan kecil lain yang biasa diserahkan pada keberuntungan.

Ini bukan alat untuk membuat kunci, kata sandi, atau token, bukan karena keacakannya kurang, tetapi karena semua itu memerlukan panjang dan alfabet tertentu - gunakan generator kata sandi untuk itu. Alat ini juga tidak cocok untuk undian publik yang hasilnya harus dipercaya peserta: angka yang muncul di sebuah halaman tidak membuktikan apa pun bagi orang yang tidak melihatnya muncul, dan undian yang bisa diverifikasi memerlukan seed yang dipublikasikan dan komitmen yang dibuat sebelum undian, yang merupakan desain yang sama sekali berbeda.

Pseudoacak, kriptografis, dan benar-benar acak

Generator pseudoacak adalah fungsi deterministik: dengan keadaan awal yang sama, ia menghasilkan urutan yang sama selamanya. Itu keunggulan untuk simulasi, yang memang menuntut hasil bisa diulang, tetapi menjadi kelemahan di tempat yang mungkin ada orang mencoba menebak nilai berikutnya. Math.random di JavaScript umumnya xorshift128+, cepat tetapi dengan state internal kecil yang bisa direkonstruksi hanya dari segelintir keluaran.

Generator yang aman secara kriptografis dirancang supaya sebanyak apa pun keluaran yang diamati tidak memberi informasi berguna tentang sisanya. Benihnya berasal dari entropi yang dikumpulkan sistem operasi - jitter waktu, pola interupsi, instruksi perangkat keras seperti RDRAND - dan diperbarui secara berkala. crypto.getRandomValues di peramban dan /dev/urandom di Unix adalah antarmuka yang biasa dipakai, dan keduanya cukup cepat sehingga keamanannya praktis didapat cuma-cuma.

Keacakan sejati, yang berasal dari sumber fisik seperti derau termal atau peluruhan radioaktif, tersedia dalam modul perangkat keras dan layanan seperti random.org. Untuk hampir semua keperluan hal itu tidak diperlukan: generator kriptografis dengan benih yang baik tidak bisa dibedakan darinya oleh uji apa pun yang bisa dijalankan orang.

Mengacak daftar tanpa membuatnya berat sebelah

Cara mengacak yang paling terpikirkan - mengurutkan dengan pembanding acak - itu keliru, dan kelirunya tidak kelihatan kalau hanya diperiksa sekilas. Pengurutan berbasis perbandingan mengandaikan urutan yang konsisten, jadi pembanding acak menghasilkan distribusi yang sangat condong ke sebagian permutasi, dan hasilnya berbeda-beda antarimplementasi pengurutan. Kelihatannya teracak, padahal tidak.

Algoritme yang benar adalah Fisher-Yates: telusuri daftar dari belakang, lalu untuk setiap posisi pilih indeks acak antara nol dan posisi itu, termasuk posisi itu sendiri, kemudian tukar keduanya. Setiap permutasi punya peluang yang sama dan waktunya linear. Hampir semua pustaka standar bahasa pemrograman sudah menyediakan implementasi yang benar; kalaupun tidak ada, perulangannya cuma empat baris.

Memilih sebagian isi daftar adalah operasi yang sama, hanya dihentikan lebih awal: acak k posisi pertama lalu ambil bagian itu. Menarik indeks acak sambil membuang yang kembar juga berhasil, tetapi kinerjanya memburuk tajam saat k mendekati panjang daftar, dan justru di titik itulah implementasi dadakan mulai berputar cukup lama sampai terasa.

Seperti apa sebenarnya deretan acak itu

Manusia buruk dalam menilai keacakan, dan kesalahannya selalu ke satu arah: data acak yang sungguhan mengandung jauh lebih banyak gerombolan daripada yang bisa diterima naluri kita. Dari seratus lemparan koin, munculnya enam atau tujuh sisi gambar berturut-turut itu wajar, bukan mencurigakan; justru deretan yang sama sekali tidak punya rentetan panjang yang kemungkinan besar dikarang.

Inilah sebabnya fitur acak pada layanan streaming musik biasanya sama sekali tidak acak. Pengacakan yang sebenarnya cukup sering memutar penyanyi yang sama tiga kali berturut-turut sampai pengguna melaporkannya sebagai kerusakan, jadi algoritmenya sengaja menyebarkan para penyanyi: lebih tidak acak, tetapi lebih dekat dengan yang orang maksud ketika menyebut acak.

Ada dua naluri terkait yang layak ditahan: kekeliruan penjudi, yang mengira suatu hasil sudah waktunya keluar setelah rentetan hasil sebaliknya, dan efek ulang tahun, yang membuat kebetulan jauh lebih mungkin daripada dugaan - dengan dua puluh tiga orang, peluang ada dua orang yang berulang tahun di hari yang sama sudah lima puluh persen. Keduanya berasal dari salah taksir yang sama tentang betapa menggerombolnya keacakan.

Ketika Anda ingin angka yang sama setiap kali

Simulasi, konten yang dibangkitkan secara prosedural, dan pekerjaan statistik sama-sama butuh hasil yang bisa diulang: benih yang sama menghasilkan urutan yang sama, sehingga sebuah hasil bisa diperiksa ulang dan sebuah bug bisa dimunculkan kembali. Generator kriptografis justru alat yang salah di sini, karena benihnya tidak bisa ditentukan dengan sengaja.

Pendekatan yang lazim adalah memakai generator pseudoacak yang ringkas dan teruji - PCG, xoshiro, atau Mersenne Twister pada kode lama - dengan benih yang ditetapkan secara eksplisit dan dicatat. Dalam pengujian, mencetak benih saat pengujian gagal mengubah kegagalan yang muncul sesekali menjadi kegagalan yang bisa diulang, dan itulah beda antara bug yang akhirnya diperbaiki dan pengujian yang akhirnya dimatikan orang.

Pisahkan kedua generator itu dan jangan sekali-kali biarkan yang berbenih bocor ke kode yang menyangkut keamanan. Pola yang bikin celaka adalah satu fungsi bantu yang dipakai untuk mengacak data uji sekaligus untuk membuat token; sejak saat itu, urutan yang deterministik ikut menjaga sesuatu yang seharusnya tidak dijaganya.

Membuat undian yang diterima orang sebagai adil

Keadilan punya dua sisi: mekanismenya dan buktinya. Mekanisme di sini sudah benar - sumber kriptografis disertai penolakan nilai di luar rentang, sehingga setiap nilai dalam rentang punya peluang yang sama. Buktinya justru yang tidak bisa disediakan sebuah halaman web, karena angka yang muncul di layar tidak membuktikan apa pun bagi orang yang tidak ikut menyaksikan.

Kalau undian menyangkut uang atau kewajiban, cara baku adalah commit-and-reveal: umumkan hash dari daftar peserta dan hash benihnya sebelum pendaftaran ditutup, jalankan undian setelahnya dengan metode yang terbuka, lalu umumkan benihnya agar siapa pun bisa menghitung ulang hasilnya. Cara ini mengubah kepercayaan kepada penyelenggara menjadi hitungan yang bisa diperiksa siapa saja.

Untuk urusan sehari-hari - siapa yang presentasi duluan, tugas mana yang dikerjakan lebih dulu, siapa yang dapat tiket terakhir - semua itu tidak diperlukan. Keadilan yang relevan di situ adalah semua orang di ruangan melihat hasil yang sama muncul pada saat yang sama, dan karena itulah undian yang terlihat bersama-sama lebih baik daripada angka yang dibacakan seseorang dari layarnya sendiri.