Ergo dan Mekanisme Konsensus Autolykos: Bagian I

Berikut adalah analisis teknis mendalam tentang mekanisme konsensus Ergo, Autolykos. Karena ini adalah topik yang panjang dan detail, kami akan menerbitkannya dalam segmen-segmen selama dua minggu ke depan. Untuk Bagian I, penulis mulai membahas pseudocode penambangan blok dan membimbing kita melalui pembuatan “list R.”

Bagian I

Autolykos, mekanisme konsensus Ergo, adalah salah satu dari sedikit teka-teki proof of work yang memory-hard asimetris yang masih tahan ASIC - sehingga memastikan bahwa blockchain tetap terdesentralisasi sebanyak mungkin. Autolykos didasarkan pada makalah Equihash[1] dan masalah ulang tahun. Untuk merangkum, penambang ditugaskan untuk menemukan k (=32) dari N elemen, sehingga hash dari jumlah elemen tersebut kurang dari target. Pseudocode berikut menjelaskan proses penambangan dan analisis ini akan membahas setiap baris secara mendetail karena sangat sedikit sumber daya online yang menjelaskan Autolykos secara keseluruhan.

Pseudocode Penambangan Blok Autolykos

Sebelum membahas prosedur penambangan blok, algoritma terlebih dahulu memerlukan grup siklik G yang sangat besar dengan urutan prima q dengan generator tetap g dan elemen identitas e. Grup prima ini digunakan untuk mengembalikan bilangan bulat dalam Z/qZ selama fungsi hashing berbasis Blake2b256.

Contoh grup siklik dengan generator z, elemen identitas 1, urutan 6[2]

Kami tidak akan fokus secara mendetail pada grup siklik karena hanya mencakup segmen kecil dari skema PoW. Sekarang, mari kita bahas penambangan Blok Autolykos baris demi baris.

Baris 1 – Input h dan m

PoW dimulai dengan dua input: tinggi blok h dan hash header blok yang akan datang m. Hash header blok adalah hash dari komponen header blok, seperti hash header blok sebelumnya, akar merkle, nonce, dll.

Baris 2 – Hitung list R

Pertama, penting untuk memperhatikan notasi H() di baris 2. Notasi ini memanggil fungsi hashing Algoritma 3. Algoritma 3 adalah fungsi hash yang berbasis Blake2b256 dan digunakan di seluruh Autolykos. Algoritma 3 menyatakan bahwa jika hash Blake dari input berada di bawah 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), maka hash.mod(q) dikembalikan. Jika tidak, Algoritma 3 mengulangi hingga mencapai hash numerik dalam rentang yang valid. Sebagai referensi, perhatikan bahwa q adalah urutan prima dari grup G, keluaran hash Blake2b256 adalah 256 bit, panjang 64 digit, dan Algoritma 3 akan selalu mengembalikan hash numerik dalam Z/qZ.

Fungsi Hash Berbasis Blake2b256

Di baris 2, fokusnya adalah pembuatan list R. List R berisi nilai r yang merupakan hash numerik 31-byte yang dibuat dari bilangan bulat dalam [0, N). Nilai r dihasilkan oleh takeright(31,H(j||h||M)). Variabelnya adalah sebagai berikut:

• j, bilangan bulat dalam [0, N)
• h, tinggi blok
• M, 8kb data konstan - padding untuk memperlambat perhitungan hash

Bagian takeRight(31,H(…)) berarti bahwa diberikan H(…), keluaran Blake2b256 32-byte, 31 byte di sebelah kanan (yaitu dalam little endian (sementara algoritma hash lainnya adalah bit endian)) dikembalikan. Dengan kata lain, byte yang paling signifikan, byte yang paling jauh ke kiri, dibuang. Akibatnya, setiap nilai r adalah 31 byte yang paling tidak signifikan yang berasal dari keluaran 32-byte H(j||h||M)). Sebagai contoh, jika j = 1, r1 = takeRight(31,H(1||h||M)).List R terdiri dari N elemen dan dapat dihasilkan untuk setiap blok dengan meningkatkan j sebanyak 1 N-1 kali. Karena H(…) mengembalikan hash.mod(q), kita dapat menyatakan bahwa list R terdiri dari r0, 1, 2, 3 … N-1 dan list R ⊂ Z/qZ. Seperti yang dinyatakan dalam whitepaper Autolykos v2[3], “N elemen berasal dari tinggi blok dan konstanta, tidak seperti Autolykos v1, sehingga penambang dapat menghitung ulang kandidat blok dengan mudah sekarang (hanya indeks yang bergantung pada mereka).” Dengan kata lain, j selalu dalam [0,N), N ditentukan oleh h, M selalu konstan, dan h berubah setiap blok, satu-satunya variabel yang perlu dihitung penambang untuk list R adalah h.

List R disimpan dalam RAM. Dalam Autolykos, N = 2²⁶ (67,108,864 bilangan bulat) digunakan dalam implementasi untuk setiap blok sebelum 614400. Oleh karena itu, kebutuhan memori untuk blok sebelum blok 614400 adalah (226 * 31 byte =) 2.08GB. N pertama kali meningkat pada blok 614400. Setelah blok 614400, setiap 51200 blok, N meningkat sebesar 5%. Dengan kata lain, kebutuhan memori penambang Ergo meningkat sebesar 5% setiap ~71 hari. Pada blok 4198400 nilai N menjadi konstan dan sama dengan 2,143,944,600[4]. Perhatikan bahwa 2 nilai terakhir yang terdaftar dalam tabel harus 2,143,944,600 dan bukan 2,147,387,550. Setelah blok 4198400, kebutuhan penyimpanan list R akan menjadi (31 byte * 2,143,944,600) = 66.46GB.

N elemen berdasarkan tinggi blok

N elemen, Ethash vs. Autolykos

Autolykos mirip dengan Ethash dalam arti bahwa tinggi blok menentukan N elemen yang disimpan dalam RAM. Dengan Autolykos, tinggi blok menentukan N hash numerik 31-byte yang disimpan. Dengan Ethash, tinggi blok menentukan N halaman DAG 128B yang disimpan. Anda mungkin bertanya-tanya, jika blok Ergo terjadi setiap 2 menit, bagaimana penambang Ergo dapat menghasilkan dataset lebih dari 2GB dengan cepat? Penambang Ethereum hanya memperbarui DAG setiap 100 jam karena memakan waktu lama… Bagi penambang Ergo, beban untuk menghitung list R adalah N instance dari Algoritma 3; ingat, setiap nilai r dihitung sebagai takeRight(31,H(j||h||M)). Namun, GPU dapat melakukan ini dengan sangat cepat, GPU umumnya memiliki multiprosesor 32-lebar atau 64-lebar yang berarti bahwa 32 atau 64 instance Algoritma 3 dapat dilakukan secara bersamaan tergantung pada GPU. Sebagai contoh, GPU 32-lebar seperti RTX570 dapat mengisi list R hanya dalam beberapa detik.

Untuk Bagian II, kami akan melanjutkan dari sini dan melanjutkan penjelasan tentang Autolykos v2. Ikuti saluran media sosial Ergo untuk pembaruan tentang Bagian II dari seri ini.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] Kredit untuk Wolf9466#9466 di Discord