Ergo dan Mekanisme Konsensus Autolykos: Bagian II

Minggu lalu, kami memperkenalkan eksplorasi mendalam tentang mekanisme konsensus Autolykos Ergo. Dengan artikel ini, kami menyelesaikan bagian kedua dari diskusi tersebut dan menyelami rincian lebih lanjut. Sebelum membaca dokumen ini, disarankan agar pembaca melihat Bagian I.

Sebagai pengingat, berikut adalah pseudocode penambangan blok dan fungsi hash.

Pseudocode Penambangan Blok Autolykos

Fungsi Hash Berbasis Blake2b256

Lines 3, 4 – mulai loop while dan menebak

Setelah menghitung list R, penambang membuat tebakan nonce dan memasuki loop untuk menguji apakah nonce pada akhirnya menghasilkan output yang di bawah nilai target yang diberikan.

Lines 5, 6 – seed untuk menghasilkan indeks

Line 5, i = takeRight(8, H(m||nonce)) mod N, menghasilkan integer dalam [0,N). Algoritma 3 digunakan tetapi dengan m dan nonce sebagai input. Setelah hash H(m||nonce) dikembalikan, 8 byte paling signifikan disimpan dan kemudian diteruskan melalui mod N. Sebagai catatan, nilai integer tertinggi yang mungkin dengan 8 byte adalah 2⁶⁴ – 1, dan dengan asumsi N = 2²⁶, hash 8-byte mod N akan menghasilkan beberapa digit pertama menjadi nol. Jumlah nol dalam i berkurang seiring pertumbuhan N.

Line 6 menghasilkan e, sebuah seed untuk menghasilkan indeks. Algoritma 3 dipanggil dengan input i (dihasilkan di line 5), h, dan M. Kemudian, byte paling signifikan dari hash numerik dibuang, dan 31 byte yang tersisa disimpan sebagai nilai e. Juga harus dicatat bahwa nilai e dapat diambil dari list R alih-alih dihitung karena e adalah nilai r.

Line 7 – generator indeks

Indeks elemen J dibuat menggunakan Algoritma 6 dengan input e, m, dan nonce. Fungsi genIndexes adalah pseudorandom satu arah yang mengembalikan daftar k (=32) angka dalam [0,N).

fungsi genIndexes

Ada beberapa langkah tambahan yang tidak ditunjukkan dalam pseudocode seperti byteswap. Pembuatan dan penerapan genIndexes dapat dijelaskan melalui contoh berikut:

GenIndexes(e||m||nonce)...

hash = Blake2b256(e||m||nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (yaitu, byteswap dan menggabungkan 4 byte dengan mengulangi 4 byte pertama) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

Kode python berikut menunjukkan proses pemotongan hash yang diperluas, mengembalikan indeks k. Dalam contoh ini kami mengasumsikan h < 614,400, sehingga N = 2²⁶ (67,108,864).

Pemotongan dan mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

Inti dari pemotongan adalah bahwa pemotongan mengembalikan k indeks yang merupakan nilai pseudorandom yang berasal dari seed, yaitu, e, m, dan nonce.

return [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Indeks ini dapat diterjemahkan menjadi nilai dalam basis 10 karena merujuk pada angka dalam [0, N). Misalnya, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314, dan seterusnya. Penambang menggunakan indeks ini untuk mengambil nilai k r.

Fungsi genIndexes mencegah optimasi karena sangat sulit, pada dasarnya tidak mungkin, untuk menemukan seed sehingga genIndexes(seed) mengembalikan indeks yang diinginkan.

Line 8 – jumlah elemen r yang diberikan k

Menggunakan indeks yang dihasilkan di line 7, penambang mengambil nilai k (=32) r yang sesuai dari list R dan menjumlahkan nilai-nilai ini. Ini mungkin terdengar membingungkan tetapi mari kita uraikan.

Melanjutkan contoh di atas, penambang menyimpan indeks berikut:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},
…
{31 | 8,830,952}

Diberikan indeks di atas, penambang mengambil nilai r berikut dari list R yang disimpan dalam memori.

{0 | 46,131,392} → dropMsb(H(46,131,392||h||M))
{1 | 65,585,313} → dropMsb(H(65,585,313||h||M))
{2 | 12,624,314} → dropMsb(H(12,624,314||h||M))
{3 | 10,599,011} → dropMsb(H(10,599,011||h||M))
…
{31 | 8,830,952} → dropMsb(H(8,830,952||h||M))

Perhatikan bahwa Takeright(31) yang dioperasikan pada hash 32-byte juga dapat ditulis sebagai dropMsb – buang byte paling signifikan.

Karena penambang sudah menyimpan list R di RAM, penambang tidak perlu menghitung k (= 32) fungsi Blake2b256 dan sebaliknya mencari nilai-nilai tersebut. Ini adalah fitur kunci dari ketahanan ASIC. Sebuah ASIC dengan memori terbatas perlu menghitung 32 iterasi Blake2b256 untuk mendapatkan nilai yang bisa dicari di memori, dan mengambil dari memori memakan waktu jauh lebih sedikit. Belum lagi, ASIC dengan memori terbatas akan memerlukan 32 instance Blake2b256 secara fisik di die untuk mencapai satu hash per siklus, yang akan memerlukan lebih banyak area dan biaya yang lebih tinggi. Sangat mudah untuk membuktikan bahwa menyimpan list R di memori sangat berharga. Anggaplah berikut ini, GPU memiliki tingkat hash G = 100MH/s, _N = 2²⁶, k = 32, interval blok t = 120 detik, dan elemen dicari setiap 4 hash. Saya suka mengasumsikan bahwa elemen dicari setiap 4 hash karena, untuk setiap tebakan nonce, beberapa elemen seperti i, J, dan H(f) memerlukan Algoritma 3, yaitu instance hash blake2b. Kami dapat memperkirakan bahwa setiap nilai r akan digunakan, rata-rata, (G * k * t)/(N*4) = 1430.51 kali.

Setelah 32 nilai r dicari, nilai-nilai tersebut dijumlahkan.

Line 9, 10, 11, 12 – periksa apakah hash dari jumlah di bawah target

Jumlah dari 32 nilai r di-hash menggunakan Algoritma 3, dan jika output di bawah target b, PoW berhasil, m dan nonce dikembalikan ke node jaringan, dan penambang diberi imbalan dalam ERG. Jika hash jumlah di atas target, Lines 4 – 11 diulang dengan nonce baru.

Jika Anda telah sampai sejauh ini, selamat! Setelah membaca semua informasi ini, Anda seharusnya memiliki pemahaman yang baik tentang Autolykos v2! Jika Anda ingin melihat demonstrasi visual dari Autolykos, silakan lihat grafik di akhir dokumen ini. Jika Anda ingin penjelasan video, Anda dapat menemukannya di sini.

Ketahanan ASIC

Kami tahu dari Ethereum bahwa algoritma ‘memory hard’ dapat ditaklukkan dengan mengintegrasikan memori pada ASIC. Ergo berbeda tetapi mari kita tinjau terlebih dahulu mengapa ASIC dengan memori terbatas tidak kompetitif dan mengapa penambang perlu menyimpan list R. Line 8 dari penambangan blok Autolykos menghalangi mesin dengan memori terbatas. Jika penambang ASIC tidak menyimpan list R, mereka memerlukan banyak inti untuk menghasilkan hash numerik 31-byte secara langsung. 32 nilai r tidak dapat dihitung secara efisien menggunakan loop inti tunggal karena output hanya akan dihasilkan setiap siklus hash ke-32. Diberikan J, untuk menghitung satu nonce per siklus hash, setidaknya 32 instance Blake2b256 yang menjalankan dropMsb(H(j||h||M)) diperlukan. Seperti yang kami sebutkan di atas, ini secara signifikan meningkatkan ukuran die dan biaya. Jelas bahwa menyimpan list R sangat berharga karena memiliki 32, atau bahkan 16, inti sangat mahal. Lebih tepatnya, membaca memori lebih cepat daripada menghitung instance Blake setiap kali nonce diuji.

Mari kita lihat apakah ASIC dengan memori yang cukup kompetitif karena itu lebih relevan untuk diskusi. Membandingkan Ethash dan Autolykos, perbedaannya adalah Ethash melibatkan N elemen saat hashing nonce dan header mencampur 64 kali, sedangkan Autolykos melibatkan N elemen saat mengambil 32 nilai r berdasarkan indeks yang dihasilkan. Untuk setiap nonce yang diuji, Autolykos menjalankan sekitar 4 instance Blake2b256 dan 32 pengambilan memori sementara Ethash menjalankan sekitar 65 instance mirip SHA-3 dan 64 pengambilan memori. Belum lagi, k saat ini diatur pada 32 tetapi nilai ini dapat ditingkatkan untuk mengambil lebih banyak nilai r jika diperlukan. ASIC yang menjalankan Ethash memiliki banyak ruang untuk meningkatkan kecepatan hashing SHA3 karena 65 hash diselesaikan per nonce yang diuji dibandingkan dengan sekitar 4 di Autolykos. Rasio pengambilan memori terhadap instance hash jauh lebih besar di Autolykos. Untuk alasan ini, Autolykos lebih memory hard daripada Ethash karena bandwidth memori memainkan peran yang jauh lebih besar dibandingkan kecepatan hashing.

Satu area di mana optimasi Autolykos dapat dilakukan adalah pengisian list R. Pengisian list R memerlukan N instance dari fungsi Blake2b256. N besar dan hanya semakin besar, jadi itu banyak hashing. Sebuah ASIC dapat mengoptimalkan kecepatan Blake2b256, memberikan lebih banyak waktu untuk penambangan blok karena list R diisi lebih cepat. Meskipun ini dapat dilakukan, pengisian list R memerlukan siklus melalui [0, N) dan GPU dengan multiprosesor 32-lebar sudah dapat mengisi list R dengan sangat cepat (dalam hitungan detik). Seseorang memerlukan ASIC dengan banyak inti Blake untuk menjadi jauh lebih cepat – sekali lagi, sangat mahal, dan mungkin tidak berharga karena bottleneck dapat menjadi bandwidth write memori (yaitu, menulis list R ke RAM daripada kecepatan hashing).

Area terakhir yang dapat dioptimalkan untuk Autolykos adalah kecepatan baca/tulis memori. Penambang ASIC Ethash memiliki kecepatan baca yang sedikit lebih cepat dibandingkan GPU karena memori di-clock lebih tinggi tanpa efek throttling GPU. Namun, perbedaan ini cukup tidak signifikan dan diharapkan menjadi semakin tidak signifikan seiring kemajuan GPU. Ini karena perangkat keras memori itu sendiri sama: DRAM. Seseorang mungkin bertanya-tanya apakah perangkat keras memori yang lebih cepat dapat digunakan di mana kecepatan baca dan tulis memori jauh lebih cepat… SRAM, misalnya, bisa menjadi langkah selanjutnya yang dapat dibayangkan dalam memecahkan algoritma memory hard, namun, SRAM bukanlah solusi yang layak hanya karena densitasnya yang lebih rendah.

SRAM di FPGA[2]

Foto di atas adalah FPGA dengan 8 chip memori di depan, dan ada 8 lagi di belakang. Total memori SRAM hanya 576MB. Memasang SRAM yang cukup di die tidak akan berhasil karena SRAM perlu ditempatkan lebih jauh dari inti karena tidak cukup padat untuk muat dalam satu lapisan di sekitar inti. Ini dapat mengakibatkan keterlambatan baca/tulis karena listrik perlu menempuh jarak yang lebih jauh meskipun perangkat keras itu sendiri lebih cepat. Selain itu, untuk menambang Ergo, kebutuhan memori meningkat seiring dengan meningkatnya N sehingga memasang SRAM yang cukup tidak layak seiring waktu. Oleh karena itu, ASIC SRAM tidak layak untuk dieksplorasi bahkan jika seseorang memiliki cukup uang untuk dibelanjakan pada SRAM itu sendiri.

Blake2b256

Satu perbedaan besar antara algoritma seperti Autolykos dan yang lainnya adalah penggunaan Blake2b256. Ini bukan kebetulan. Blake sangat bergantung pada operasi penjumlahan untuk pencampuran hash daripada operasi XOR. Operasi seperti XOR dapat dilakukan bit demi bit sedangkan penjumlahan memerlukan bit carry. Oleh karena itu, Blake memerlukan lebih banyak daya dan area inti dibandingkan algoritma SHA, tetapi tetap aman dan bahkan lebih cepat. Seperti yang disebutkan di situs web Blake2, “BLAKE2 cepat dalam perangkat lunak karena memanfaatkan fitur CPU modern, yaitu paralelisme tingkat instruksi, ekstensi set instruksi SIMD, dan beberapa inti.”[3] Oleh karena itu, meskipun ASIC dapat menghasilkan instance Blake lebih cepat, sifat bawaan dari fungsi tersebut membatasi optimasi dengan memerlukan penjumlahan dan melibatkan fitur yang ditemukan di CPU serta GPU.

Kecepatan Blake2b relatif terhadap fungsi hash lainnya

Kesimpulan

Autolykos adalah inovasi hebat yang merupakan respons yang diperlukan untuk melawan munculnya mesin ASIC yang dioptimalkan untuk PoW. Kami berharap seri 2 bagian ini telah membantu Anda memahami Autolykos pada tingkat yang lebih teknis dan mengapa ia lebih memory hard daripada Ethash. Saat Ethereum bertransisi ke jaringan PoS, akan ada komunitas besar penambang yang mencari tempat untuk mengarahkan daya hashrate mereka, dan Ergo harus menjadi pemain signifikan dalam menarik para penambang tersebut.

Jika Anda menikmati artikel ini, penulis mengundang Anda untuk memeriksa lebih banyak konten melalui akun Twitter mereka, @TheMiningApple.

[1] Kredit untuk Wolf9466#9466 di Discord
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).