Abstrak

Buku besar publik adalah rangkaian data yang tidak dapat diubah dan dapat dibaca dan ditambah oleh semua orang. Buku besar umum memiliki kegunaan yang tak terhitung banyaknya dan menarik. Mereka dapat mengamankan, di depan mata, segala jenis transaksi —seperti kepemilikan, penjualan, dan pembayaran—sesuai urutan terjadinya. Buku besar publik tidak hanya mengekang korupsi, namun juga memungkinkan penerapan yang sangat canggih —seperti cryptocurrency dan smart contracts. Mereka berdiri untuk merevolusi cara masyarakat demokratis beroperasi. Namun, seperti yang diterapkan saat ini, skalanya buruk dan tidak dapat mencapai potensinya. Algorand adalah cara yang benar-benar demokratis dan efisien untuk mengimplementasikan buku besar publik. Berbeda dengan sebelumnya implementasi berdasarkan bukti kerja, memerlukan jumlah komputasi yang dapat diabaikan, dan menghasilkan riwayat transaksi yang tidak akan “bercabang” dengan probabilitas yang sangat tinggi. Algorand didasarkan pada perjanjian Bizantium (yang baru dan super cepat) yang menyampaikan pesan. Agar lebih konkrit, kami akan mendeskripsikan Algorand hanya sebagai platform uang.

Perkenalan

Uang menjadi semakin virtual. Diperkirakan sekitar 80% dari Amerika Serikat dolar saat ini hanya ada sebagai entri buku besar [5]. Instrumen keuangan lainnya juga mengikuti langkah serupa. Di dunia yang ideal, di mana kita dapat mengandalkan entitas pusat yang dipercaya secara universal, yang kebal terhadap semua kemungkinan serangan dunia maya, uang dan transaksi keuangan lainnya hanya dapat dilakukan secara elektronik. Sayangnya, kita tidak hidup di dunia seperti itu. Oleh karena itu, cryptocurrency terdesentralisasi, seperti itu seperti Bitcoin [29], dan sistem “smart contract”, seperti Ethereum, telah diusulkan [4]. Di inti dari sistem ini adalah buku besar bersama yang mencatat urutan transaksi dengan andal, ∗Ini adalah versi makalah ArXiv yang lebih formal (dan asinkron) oleh penulis kedua [24], sebuah makalah sendiri berdasarkan Gorbunov dan Micali [18]. Teknologi Algorand adalah objek berikut ini permohonan paten: US62/117,138 US62/120,916 US62/142,318 US62/218,817 US62/314,601 PCT/US2016/018300 US62/326.865 62/331.654 US62/333.340 US62/343.369 US62/344.667 US62/346.775 US62/351.011 US62/653.482 US62/352.195 US62/363.970 US62/369.447 US62/378.753 US62/383.299 US62/394.091 US62/400.361 US62/403.403 US62/410,721 US62/416,959 US62/422,883 US62/455,444 US62/458,746 US62/459,652 US62/460,928 US62/465,931beragam seperti pembayaran dan kontrak, dengan cara yang tidak dapat diubah. Teknologi pilihan untuk menjamin ketahanan terhadap kerusakan tersebut adalah blockchain. Blockchain berada di balik aplikasi seperti cryptocurrency [29], aplikasi keuangan [4], dan Internet of Things [3]. Beberapa teknik untuk mengelola buku besar berbasis blockchain telah diusulkan: bukti kerja [29], bukti kepemilikan [2], toleransi kesalahan Bizantium praktis [8], atau kombinasi tertentu. Namun saat ini, pengelolaan buku besar menjadi tidak efisien. Misalnya, proof-of-work milik Bitcoin pendekatan (berdasarkan konsep asli [14]) memerlukan banyak perhitungan, boros dan skalanya buruk [1]. Selain itu, secara de facto ia memusatkan kekuasaan di tangan yang sangat sedikit. Oleh karena itu kami ingin mengajukan metode baru untuk mengimplementasikan buku besar publik yang menawarkan kenyamanan dan efisiensi sistem terpusat yang dijalankan oleh otoritas yang terpercaya dan tidak dapat diganggu gugat, tanpa inefisiensi dan kelemahan penerapan desentralisasi saat ini. Kami menyebutnya pendekatan kami Algorand, karena kami menggunakan keacakan algoritmik untuk memilih, berdasarkan buku besar yang dibuat sejauh ini, sekumpulan verifikator yang bertugas membangun blok transaksi valid berikutnya. Tentu saja, kami memastikan bahwa pilihan tersebut terbukti kebal dari manipulasi dan tidak dapat diprediksi hingga saat ini pada menit-menit terakhir, namun juga pada akhirnya menjadi jelas secara universal. Pendekatan Algorand cukup demokratis, dalam artian tidak secara prinsip maupun de facto menciptakan kelas pengguna yang berbeda (sebagai “penambang” dan “pengguna biasa” di Bitcoin). Dalam Algorand “semua kekuasaan ada pada himpunan semua pengguna”. Salah satu properti penting dari Algorand adalah riwayat transaksinya hanya dapat bercabang dengan jumlah yang sangat kecil probabilitas (misalnya, satu dalam satu triliun, atau bahkan 10−18). Algorand juga dapat mengatasi beberapa masalah hukum dan kekhawatiran politik. Pendekatan Algorand berlaku untuk blockchains dan, lebih umum, untuk metode pembangkitan apa pun rangkaian blok yang tahan terhadap kerusakan. Kami sebenarnya mengajukan metode baru—alternatif dari, dan lebih efisien daripada, blockchains— yang mungkin merupakan kepentingan independen. 1.1 Asumsi dan Masalah Teknis Bitcoin Bitcoin adalah sistem yang sangat cerdik dan telah menginspirasi banyak penelitian selanjutnya. Namun, itu juga bermasalah. Mari kita rangkum asumsi mendasar dan masalah teknisnya—yang mana sebenarnya dimiliki oleh semua mata uang kripto yang, seperti Bitcoin, didasarkan pada proof-of-work. Untuk ringkasan ini, perlu diingat bahwa, di Bitcoin, pengguna dapat memiliki beberapa kunci publik skema tanda tangan digital, uang dikaitkan dengan kunci publik, dan pembayaran adalah a tanda tangan digital yang mentransfer sejumlah uang dari satu kunci publik ke kunci publik lainnya. Intinya, Bitcoin mengatur semua pembayaran yang diproses dalam rantai blok, B1, B2, . . ., masing-masing terdiri atas kelipatan pembayaran, sehingga seluruh pembayaran B1, dilakukan dalam urutan apa pun, diikuti oleh pembayaran B2, dalam urutan apa pun, dll., merupakan rangkaian pembayaran yang sah. Setiap blok rata-rata dihasilkan setiap 10 menit. Urutan blok ini adalah sebuah rantai, karena disusun sedemikian rupa untuk memastikan bahwa setiap perubahan terjadi secara merata dalam satu blok, meresap ke semua blok berikutnya, sehingga lebih mudah untuk mengenali perubahan apa pun riwayat pembayaran. (Seperti yang akan kita lihat, hal ini dicapai dengan memasukkan kriptografi ke dalam setiap blok hash dari yang sebelumnya.) Struktur blok seperti itu disebut sebagai blockchain. Asumsi: Mayoritas Kekuatan Komputasi yang Jujur Bitcoin berasumsi bahwa tidak ada yang berbahaya entitas (atau koalisi entitas jahat yang terkoordinasi) mengendalikan sebagian besar komputasi daya yang dikhususkan untuk pembangkitan blok. Faktanya, entitas seperti itu dapat mengubah blockchain,dan dengan demikian menulis ulang riwayat pembayaran, sesuai keinginan. Secara khusus, dapat melakukan pembayaran \(\wp\), memperoleh manfaat yang telah dibayarkan, dan kemudian “menghapus” jejak apa pun dari \(\wp\). Masalah Teknis 1: Limbah Komputasi Pendekatan proof-of-work Bitcoin untuk memblokir pembangkitan membutuhkan jumlah komputasi yang luar biasa. Saat ini, hanya dengan beberapa ratus ribuan kunci publik dalam sistem, hanya dapat dikumpulkan oleh 500 superkomputer terkuat hanya 12,8% persen dari total daya komputasi yang dibutuhkan dari pemain Bitcoin. Ini jumlah komputasi akan meningkat pesat jika semakin banyak pengguna yang bergabung dalam sistem. Masalah Teknis 2: Konsentrasi Kekuasaan Saat ini, karena jumlahnya yang selangit diperlukan komputasi, pengguna, mencoba membuat blok baru menggunakan desktop biasa (apalagi a ponsel), diperkirakan akan kehilangan uang. Memang benar, untuk menghitung blok baru dengan komputer biasa, biaya yang diharapkan dari listrik yang diperlukan untuk menggerakkan komputasi melebihi imbalan yang diharapkan. Hanya menggunakan kumpulan komputer yang dibuat khusus (yang tidak melakukan apa pun selain “menambang blok baru”), satu mungkin berharap mendapat untung dengan menghasilkan blok-blok baru. Oleh karena itu, saat ini, secara de facto, ada dua kelas pengguna yang terpisah: pengguna biasa, yang hanya melakukan pembayaran, dan kumpulan penambangan khusus, yang hanya mencari blok baru. Oleh karena itu, tidak mengherankan bahwa, hingga saat ini, total daya komputasi per blok generasi terletak hanya dalam lima kelompok. Dalam kondisi seperti itu, asumsi mayoritas kekuatan komputasi yang jujur menjadi kurang kredibel. Masalah Teknis 3: Ambiguitas Di Bitcoin, blockchain belum tentu unik. Memang bagian terakhirnya sering kali bercabang: blockchain mungkin —katakanlah— B1, . . . , Bk, B′ k+1, B′ k+2, menurut satu pengguna, dan B1, . . . , Bk, B′′ k+1, B′′ k+2, B′′ k+3 menurut pengguna lain. Baru setelah beberapa blok ada telah ditambahkan ke dalam rantai, dapatkah seseorang yakin bahwa k + 3 blok pertama akan sama untuk semua pengguna. Oleh karena itu, seseorang tidak dapat langsung mengandalkan pembayaran yang terdapat di blok terakhir rantai. Akan lebih bijaksana untuk menunggu dan melihat apakah blok tersebut sudah cukup dalam blockchain dan dengan demikian cukup stabil. Secara terpisah, permasalahan penegakan hukum dan kebijakan moneter juga telah diangkat mengenai Bitcoin.1 1.2 Algorand, Singkatnya Pengaturan Algorand bekerja dalam lingkungan yang sangat sulit. Secara singkat, (a) Lingkungan Tanpa Izin dan Izin. Algorand bahkan bekerja secara efisien dan aman dalam lingkungan yang benar-benar tanpa izin, di mana banyak pengguna diizinkan untuk bergabung secara sewenang-wenang sistem kapan saja, tanpa pemeriksaan atau izin apa pun. Tentu saja, Algorand berhasil bahkan lebih baik di lingkungan yang berizin. 1Anonimitas (semu) yang ditawarkan oleh Bitcoin pembayaran dapat disalahgunakan untuk pencucian uang dan/atau pendanaan individu kriminal atau organisasi teroris. Uang kertas tradisional atau emas batangan, yang pada prinsipnya menawarkan kesempurnaan anonimitas, seharusnya menimbulkan tantangan yang sama, namun fisik mata uang ini secara signifikan memperlambat pergerakan uang transfer dana, sehingga memungkinkan adanya pemantauan pada tingkat tertentu oleh lembaga penegak hukum. Kemampuan untuk “mencetak uang” adalah salah satu kekuatan mendasar suatu negara-bangsa. Oleh karena itu, pada prinsipnya masif Penerapan mata uang yang mengambang secara independen dapat membatasi kekuatan ini. Namun saat ini, Bitcoin masih jauh dari harapan ancaman terhadap kebijakan moneter pemerintah, dan karena masalah skalabilitasnya, hal ini mungkin tidak akan pernah terjadi.(b) Lingkungan yang Sangat Bermusuhan. Algorand bertahan melawan Musuh yang sangat kuat, yang mampu (1) secara instan merusak pengguna mana pun yang dia inginkan, kapan pun dia mau, dengan ketentuan, dalam a lingkungan tanpa izin, 2/3 uang dalam sistem adalah milik pengguna yang jujur. (Dalam a lingkungan yang diizinkan, berapa pun uangnya, cukuplah 2/3 penggunanya jujur.) (2) mengontrol sepenuhnya dan mengoordinasikan dengan sempurna semua pengguna yang rusak; dan (3) menjadwalkan pengiriman semua pesan, dengan ketentuan bahwa setiap pesan dikirim oleh pengguna yang jujur menjangkau 95% pengguna jujur dalam waktu \(\lambda\)m, yang semata-mata bergantung pada ukuran m. Properti Utama Meskipun kehadiran musuh kita yang kuat, di Algorand • Jumlah perhitungan yang diperlukan minimal. Intinya, tidak peduli berapa banyak penggunanya hadir dalam sistem, masing-masing dari seribu lima ratus pengguna harus melakukan paling banyak beberapa detik komputasi. • Blok Baru Dibuat dalam waktu kurang dari 10 menit, dan secara de facto tidak akan pernah meninggalkan blockchain. Misalnya, dalam ekspektasi, waktu untuk menghasilkan blok pada perwujudan pertama lebih sedikit daripada Λ + 12.4\(\lambda\), di mana Λ adalah waktu yang diperlukan untuk menyebarkan sebuah blok, dalam gosip peer-to-peer mode, tidak peduli berapa pun ukuran blok yang dipilih, dan \(\lambda\) adalah waktu untuk menyebarkan 1.500 pesan 200Blong. (Karena dalam sistem yang benar-benar terdesentralisasi, Λ pada dasarnya adalah latensi intrinsik, dalam Algorand faktor pembatas dalam pembuatan blok adalah kecepatan jaringan.) Perwujudan kedua memiliki sebenarnya telah diuji secara eksperimental ( oleh ?), menunjukkan bahwa sebuah blok dihasilkan dalam waktu kurang dari 40 detik. Selain itu, blockchain Algorand hanya dapat bercabang dengan probabilitas yang dapat diabaikan (yaitu, kurang dari satu dalam satu triliun), sehingga pengguna dapat meneruskan pembayaran yang terdapat dalam blok baru segera setelahnya blok muncul. • Semua kekuasaan berada di tangan pengguna itu sendiri. Algorand adalah sistem terdistribusi yang sebenarnya. Khususnya, tidak ada entitas eksogen (seperti “penambang” di Bitcoin), yang dapat mengontrol transaksi mana diakui. Teknik Algorand. 1. Protokol Perjanjian Bizantium yang Baru dan Cepat. Algorand menghasilkan blok baru melalui protokol kriptografi, penyampaian pesan, perjanjian biner Bizantium (BA), BA⋆. Protokol BA⋆tidak hanya memenuhi beberapa properti tambahan (yang akan segera kita bahas), namun juga sangat cepat. Secara kasar, versi input binernya terdiri dari loop 3 langkah, di mana pemain i mengirimkan satu pesan mi ke semua pemain lainnya. Dieksekusi dalam jaringan yang lengkap dan sinkron, dengan lebih banyak lagi dari 2/3 pemain jujur, dengan probabilitas > 1/3, setelah setiap loop berakhirnya protokol persetujuan. (Kami menekankan bahwa protokol BA⋆memenuhi definisi asli perjanjian Bizantium dari Pease, Shostak, dan Lamport [31], tanpa melemah apa pun.) Algorand memanfaatkan protokol BA biner ini untuk mencapai kesepakatan, dalam komunikasi kami yang berbeda model, di setiap blok baru. Blok yang disepakati kemudian disertifikasi, melalui sejumlah yang ditentukan tanda tangan digital dari verifikator yang tepat, dan disebarkan melalui jaringan. 2. Penyortiran Kriptografi. Meskipun sangat cepat, protokol BA⋆ akan mendapatkan manfaat lebih jauh kecepatan saat dimainkan oleh jutaan pengguna. Oleh karena itu, Algorand memilih pemain BA⋆untuk menjadisubset yang jauh lebih kecil dari himpunan semua pengguna. Untuk menghindari jenis konsentrasi kekuasaan yang berbeda masalah, setiap blok baru Br akan dibangun dan disepakati, melalui pelaksanaan BA⋆ baru, oleh sekelompok verifikator terpilih yang terpisah, SV r. Pada prinsipnya, memilih set seperti itu mungkin sama sulitnya memilih Br secara langsung. Kami mengatasi potensi masalah ini dengan pendekatan yang kami sebut merangkul saran mendalam dari Maurice Herlihy, penyortiran kriptografi. Penyortiran adalah praktik memilih pejabat secara acak dari sejumlah besar individu yang memenuhi syarat [6]. (Penyortiran dilakukan selama berabad-abad: misalnya, oleh republik Athena, Florence, dan Venesia. Dalam peradilan modern sistem, pemilihan acak sering digunakan untuk memilih juri. Pengambilan sampel secara acak juga baru-baru ini dilakukan menganjurkan pemilu oleh David Chaum [9].) Dalam sistem desentralisasi tentunya memilih koin acak yang diperlukan untuk memilih secara acak anggota setiap set pemverifikasi SV r bermasalah. Oleh karena itu kami menggunakan kriptografi untuk memilih setiap kumpulan verifikasi, dari populasi semua pengguna, dengan cara yang dijamin otomatis (yaitu tidak memerlukan pertukaran pesan) dan acak. Intinya, kami menggunakan fungsi kriptografi untuk menentukan secara otomatis, dari blok sebelumnya Br−1, pengguna, pemimpin, bertugas mengusulkan blok baru Br, dan pemverifikasi himpunan SV r, di bertugas untuk mencapai kesepakatan mengenai blok yang diusulkan oleh pemimpin. Karena pengguna jahat dapat mempengaruhi komposisi Br−1 (misalnya, dengan memilih beberapa pembayarannya), kami secara khusus membuat dan menggunakannya masukan tambahan untuk membuktikan bahwa pemimpin untuk blok ke-r dan himpunan pemverifikasi SV r memang benar dipilih secara acak. 3. Jumlah (Benih) Qr. Kita menggunakan blok terakhir Br−1 di blockchain untuk melakukannya secara otomatis menentukan set verifikasi berikutnya dan pemimpin yang bertugas membangun blok baru Sdr. Tantangan dalam pendekatan ini adalah, dengan hanya memilih pembayaran yang sedikit berbeda di dalamnya putaran sebelumnya, Musuh kita yang kuat memperoleh kendali luar biasa atas pemimpin berikutnya. Bahkan jika dia hanya mengendalikan 1/1000 pemain/uang dalam sistem, dia dapat memastikan bahwa semua pemimpin demikian berbahaya. (Lihat Intuisi Bagian 4.1.) Tantangan ini penting bagi semua pendekatan proof-of-stake, dan, sepanjang pengetahuan kami, hingga kini masalah ini belum terselesaikan dengan memuaskan. Untuk menghadapi tantangan ini, kami sengaja membangun, dan terus memperbarui, secara terpisah dan hati-hati kuantitas yang ditentukan, Qr, yang terbukti, tidak hanya tidak dapat diprediksi, tetapi juga tidak dapat dipengaruhi, oleh kita Musuh yang kuat. Kita dapat menyebut Qr sebagai benih ke-r, karena dari Qr itulah Algorand memilih, melalui penyortiran kriptografi rahasia, semua pengguna yang akan memainkan peran khusus dalam pembuatannya blok ke-r. 4. Penyortiran Kritografi Rahasia dan Kredensial Rahasia. Secara acak dan jelas menggunakan blok terakhir saat ini, Br−1, untuk memilih himpunan verifikasi dan pemimpin yang bertanggung jawab membangun blok baru, Br, tidaklah cukup. Karena Br−1 harus diketahui sebelum menghasilkan Br, kuantitas terakhir yang tidak dapat dipengaruhi Qr−1 yang terkandung dalam Br−1 harus diketahui juga. Oleh karena itu, demikian adalah verifikator dan pemimpin yang bertugas menghitung blok Br. Jadi, Musuh kita yang kuat mungkin akan langsung merusak semuanya, sebelum mereka terlibat dalam diskusi apa pun tentang Br, untuk mendapatkan kontrol penuh atas blok yang mereka sertifikasi. Untuk mencegah masalah ini, para pemimpin (dan sebenarnya juga para pemeriksa) secara diam-diam mengetahui peran mereka, namun mereka bisa menghitung kredensial yang tepat, yang mampu membuktikan kepada semua orang bahwa memang memiliki peran tersebut. Kapan Ketika pengguna secara diam-diam menyadari bahwa dia adalah pemimpin untuk blok berikutnya, pertama-tama dia secara diam-diam merakit bloknya sendiri sendiri yang mengusulkan blok baru, dan kemudian menyebarkannya (sehingga dapat disertifikasi) bersama dengan blok miliknya kredensial. Dengan cara ini, Musuh akan segera menyadari siapa pemimpin selanjutnya blok tersebut, dan meskipun ia dapat langsung merusaknya, maka sudah terlambat bagi Musuh untuk melakukannya mempengaruhi pilihan blok baru. Memang benar, dia tidak bisa “memanggil kembali” pesan pemimpinnya lagidaripada pemerintah yang kuat dapat memasukkan kembali pesan yang disebarkan secara viral oleh WikiLeaks. Seperti yang akan kita lihat, kita tidak bisa menjamin keunikan pemimpin, dan semua orang juga tidak yakin siapa pemimpinnya adalah, termasuk pemimpinnya sendiri! Namun, pada Algorand, kemajuan pasti akan terjamin. 5. Penggantian Pemain. Setelah dia mengusulkan blok baru, pemimpinnya mungkin akan “mati” (atau mati). dirusak oleh Musuh), karena tugasnya telah selesai. Namun, bagi para verifikator di SV r, keadaannya tidak begitu baik sederhana. Memang, bertugas mengesahkan blok baru Br dengan tanda tangan yang cukup banyak, mereka harus terlebih dahulu menjalankan perjanjian Bizantium pada blok yang diusulkan oleh pemimpinnya. Masalahnya adalah, tidak peduli seberapa efisiennya, BA⋆membutuhkan banyak langkah dan kejujuran> 2/3 pemainnya. Hal ini menjadi masalah karena, demi alasan efisiensi, himpunan pemain BA⋆ terdiri dari himpunan kecil SV r dipilih secara acak di antara kumpulan semua pengguna. Jadi, Musuh kita kuat, meski tidak mampu merusak 1/3 dari seluruh pengguna, tentu dapat merusak seluruh anggota SV r! Untungnya kami akan membuktikan bahwa protokol BA⋆, yang dijalankan dengan menyebarkan pesan dengan cara peer-topeer, dapat digantikan oleh pemain. Persyaratan baru ini berarti protokolnya benar dan mencapai konsensus secara efisien bahkan jika setiap langkahnya dijalankan dengan cara yang benar-benar baru dan acak dan dipilih secara independen, sekelompok pemain. Jadi, dengan jutaan pengguna, masing-masing terdiri dari sekelompok kecil pemain terkait dengan langkah BA⋆kemungkinan besar memiliki perpotongan kosong dengan himpunan berikutnya. Selain itu, kumpulan pemain dengan langkah BA⋆ yang berbeda mungkin akan memiliki karakter yang sangat berbeda kardinalitas. Selain itu, anggota setiap set tidak mengetahui siapa pemain berikutnya jadilah, dan jangan diam-diam melewati keadaan internal apa pun. Properti pemain yang dapat diganti sebenarnya sangat penting untuk mengalahkan yang dinamis dan sangat kuat Musuh yang kami bayangkan. Kami percaya bahwa protokol pemain yang dapat diganti akan terbukti penting dalam banyak hal konteks dan aplikasi. Secara khusus, hal ini akan sangat penting untuk melaksanakan sub-protokol kecil dengan aman tertanam di dunia pemain yang lebih besar dengan musuh yang dinamis, yang bahkan mampu merusak sebagian kecil dari total pemain, tidak mengalami kesulitan untuk merusak semua pemain yang lebih kecil sub-protokol. Properti/Teknik Tambahan: Kejujuran Malas Pengguna yang jujur mengikuti resepnya instruksi, termasuk online dan menjalankan protokol. Karena, Algorand hanya memiliki sedikit saja kebutuhan komputasi dan komunikasi, online dan menjalankan protokol “di latar belakang” bukanlah pengorbanan besar. Tentu saja, ada beberapa “ketidakhadiran” di antara pemain jujur, seperti itu karena hilangnya konektivitas secara tiba-tiba atau perlunya reboot, secara otomatis ditoleransi (karena kami selalu dapat menganggap beberapa pemain tersebut sebagai pemain jahat untuk sementara waktu). Namun, mari kita tunjukkan, bahwa Algorand dapat dengan mudah diadaptasi agar berfungsi dalam model baru, di mana pengguna yang jujur sering kali offline. Model baru kami dapat diperkenalkan secara informal sebagai berikut. Kejujuran yang Malas. Secara kasar, pengguna i malas-tapi-jujur jika (1) dia mengikuti semua yang ditentukan instruksi, ketika dia diminta untuk berpartisipasi dalam protokol, dan (2) dia diminta untuk berpartisipasi ke protokol jarang sekali, dan dengan pemberitahuan terlebih dahulu. Dengan gagasan yang santai tentang kejujuran, kita mungkin bahkan lebih yakin bahwa orang-orang jujur juga demikian tersedia ketika kita membutuhkannya, dan Algorand menjamin bahwa, ketika hal ini terjadi, Sistem beroperasi dengan aman meskipun, pada titik waktu tertentu, mayoritas pemain yang berpartisipasi jahat.1.3 Pekerjaan yang Berhubungan Dekat Pendekatan bukti kerja (seperti [29] dan [4] yang dikutip) cukup ortogonal dengan pendekatan kami. Begitu juga dengan pendekatan yang didasarkan pada persetujuan Bizantium yang menyampaikan pesan atau toleransi kesalahan Bizantium yang praktis (seperti yang dikutip [8]). Memang benar, protokol-protokol ini tidak dapat dijalankan di antara semua pengguna dan tidak dapat, dalam model kami, dibatasi hanya untuk sekelompok kecil pengguna. Faktanya, musuh kita yang kuat adalah saya segera merusak semua pengguna yang terlibat dalam sekelompok kecil yang dibebankan untuk benar-benar menjalankan protokol BA. Pendekatan kami dapat dianggap terkait dengan bukti kepemilikan [2], dalam artian “kekuatan” pengguna dalam pembangunan blok sebanding dengan uang yang mereka miliki dalam sistem (berbeda dengan —katakanlah— untuk uang yang mereka masukkan ke dalam “escrow”). Makalah yang paling dekat dengan kami adalah Model Konsensus Mengantuk dari Pass dan Shi [30]. Untuk menghindari perhitungan berat diperlukan dalam pendekatan proof-of-work, makalah mereka bergantung pada (dan ramah kredit) penyortiran kriptografi rahasia Algorand. Dengan kesamaan aspek penting ini, ada beberapa ada perbedaan yang signifikan antara makalah kami. Khususnya, (1) Pengaturannya hanya diperbolehkan. Sebaliknya, Algorand juga merupakan sistem tanpa izin. (2) Mereka menggunakan protokol gaya Nakamoto, dan dengan demikian blockchain mereka sering kali bercabang. Meskipun tanpa proof-of-work, dalam protokol mereka seorang pemimpin yang dipilih secara diam-diam diminta untuk memperpanjang valid terlama (dalam arti yang lebih kaya) blockchain. Oleh karena itu, percabangan tidak dapat dihindari dan kita harus menunggunya blok tersebut cukup “dalam” di dalam rantai. Memang, untuk mencapai tujuan mereka dengan musuh mampu melakukan korupsi adaptif, mereka memerlukan blok yang memiliki kedalaman poli(N), di mana N mewakili jumlah total pengguna dalam sistem. Perhatikan hal itu, bahkan dengan asumsi bahwa sebuah blok dapat diproduksi dalam satu menit, jika ada N = 1 juta pengguna, maka seseorang harus menunggu sekitar 2 juta tahun untuk bisa mendapatkannya satu blok menjadi sedalam N 2, dan selama sekitar 2 tahun agar satu blok menjadi sedalam N. Sebaliknya, Algorand blockchain bercabang hanya dengan kemungkinan yang dapat diabaikan, meskipun Musuh korup pengguna secara cepat dan adaptif, dan blok-blok barunya dapat segera diandalkan. (3) Mereka tidak menangani perjanjian Bizantium secara individual. Dalam arti tertentu, mereka hanya menjamin “konsensus akhir mengenai rangkaian nilai yang berkembang”. Protokol mereka adalah protokol replikasi negara daripada BA, dan tidak dapat digunakan untuk mencapai kesepakatan Bizantium mengenai nilai kepentingan individu. Sebaliknya, Algorand juga dapat digunakan hanya sekali, jika diinginkan, untuk memungkinkan jutaan pengguna dengan cepat mencapai kesepakatan Bizantium mengenai nilai bunga tertentu. (4) Mereka memerlukan jam yang disinkronkan dengan lemah. Artinya, semua jam pengguna diimbangi dengan waktu yang kecil δ. Sebaliknya, di Algorand, jam hanya perlu memiliki (pada dasarnya) “kecepatan” yang sama. (5) Protokol mereka bekerja dengan pengguna yang malas tapi jujur ​​atau dengan mayoritas pengguna online yang jujur. Mereka dengan hormat memuji Algorand karena telah mengangkat masalah pengguna jujur yang online secara massal, dan untuk mengedepankan model kejujuran yang malas sebagai tanggapannya. Protokol mereka tidak hanya berfungsi pada orang yang malas model kejujuran, tetapi juga dalam model mengantuk permusuhan, di mana musuh memilih pengguna yang mana sedang online dan mana yang offline, asalkan mayoritas pengguna online selalu jujur.2 2Versi asli dari makalah mereka sebenarnya hanya mempertimbangkan keamanan dalam model mengantuk mereka yang bermusuhan. Itu versi asli Algorand, yang mendahului versi mereka, juga secara eksplisit dipertimbangkan dengan asumsi bahwa mayoritas penduduk pemain online selalu jujur, namun secara eksplisit mengecualikannya dari pertimbangan, mendukung model kejujuran yang malas. (Misalnya, jika suatu saat setengah dari pengguna jujur memilih untuk offline, maka mayoritas pengguna online mungkin sangat berbahaya. Jadi, untuk mencegah hal ini terjadi, Musuh harus memaksakan sebagian besar kekuatannya pemain yang korup untuk offline juga, yang jelas-jelas bertentangan dengan kepentingannya sendiri.) Perhatikan bahwa protokol dengan mayoritas Pemain yang malas tapi jujur akan bekerja dengan baik jika mayoritas pengguna online selalu jahat. Hal ini terjadi karena sejumlah pemain jujur, mengetahui bahwa mereka akan menjadi krusial pada suatu saat tertentu, akan memilih tidak boleh offline pada saat-saat itu, juga tidak dapat dipaksa offline oleh Musuh, karena dia tidak tahu siapa yang mungkin pemain jujur yang penting.(6) Mereka memerlukan mayoritas yang sederhana dan jujur. Sebaliknya, versi Algorand saat ini memerlukan mayoritas jujur 2/3. Makalah lain yang dekat dengan kami adalah Ouroboros: Protokol Blockchain Bukti Saham yang Terbukti Aman, oleh Kiayias, Russell, David, dan Oliynykov [20]. Sistem mereka juga muncul setelah sistem kita. Itu juga menggunakan penyortiran kriptografi untuk membuang bukti kerja dengan cara yang dapat dibuktikan. Namun, mereka Sistem ini, sekali lagi, merupakan protokol gaya Nakamoto, yang mana percabangan tidak dapat dihindari dan sering terjadi. (Namun, dalam model mereka, hambatan tidak perlu sedalam model konsensus yang mengantuk.) Selain itu, sistem mereka bergantung pada asumsi berikut: menurut penulisnya sendiri, “(1) the jaringan sangat sinkron, (2) mayoritas pemangku kepentingan terpilih tersedia sesuai kebutuhan untuk berpartisipasi dalam setiap zaman, (3) para pemangku kepentingan tidak harus offline dalam jangka waktu yang lama, (4) adaptasi korupsi tunduk pada penundaan kecil yang diukur dalam putaran linear parameter keamanan.” Sebaliknya, Algorand, dengan kemungkinan besar, bebas fork, dan tidak bergantung pada salah satu dari 4 asumsi ini. Khususnya, di Algorand, Musuh mampu melakukannya secara instan merusak pengguna yang ingin dia kendalikan.

Persiapan

2.1 Primitif Kriptografi Hash yang Ideal. Kita akan mengandalkan fungsi kriptografi hash yang dapat dihitung secara efisien, H, yang memetakan string panjang sembarang ke string biner dengan panjang tetap. Mengikuti tradisi panjang, kami menjadi model H sebagai oracle acak, pada dasarnya adalah fungsi yang memetakan setiap kemungkinan string s ke secara acak dan string biner yang dipilih secara independen (dan kemudian diperbaiki), H(s), dengan panjang yang dipilih. Dalam makalah ini, H memiliki keluaran sepanjang 256-bit. Memang, panjang tersebut cukup pendek untuk membuat sistem efisien dan cukup lama untuk membuat sistem aman. Misalnya, kita ingin H tahan benturan. Artinya, akan sulit untuk menemukan dua string berbeda x dan y sehingga H(x) = H(y). Ketika H adalah oracle acak dengan output panjang 256-bit, menemukan pasangan string seperti itu memang merupakan hal yang sulit. sulit. (Mencoba secara acak, dan mengandalkan paradoks ulang tahun, akan membutuhkan 2256/2 = 2128 cobaan.) Penandatanganan Digital. Tanda tangan digital memungkinkan pengguna untuk mengotentikasi informasi satu sama lain tanpa membagikan kunci rahasia apa pun. Skema tanda tangan digital terdiri dari tiga cepat algoritma: generator kunci probabilistik G, algoritma penandatanganan S, dan algoritma verifikasi V. Mengingat parameter keamanan k, bilangan bulat yang cukup tinggi, pengguna i menggunakan G untuk menghasilkan sepasang kunci k-bit (yaitu, string): pki kunci “publik” dan ski kunci penandatanganan “rahasia” yang cocok. Yang terpenting, a kunci publik tidak “mengkhianati” kunci rahasianya. Maksudnya, walaupun diberi ilmu pki, tidak orang lain selain saya mampu menghitung ski dalam waktu kurang dari waktu astronomi. Pengguna saya menggunakan ski untuk menandatangani pesan secara digital. Untuk setiap pesan yang mungkin (string biner) m, i terlebih dahulu hashes m lalu jalankan algoritma S pada input H(m) dan ski sehingga menghasilkan string k-bit sigpki(m) \(\triangleq\)S(H(m), ski) .3 3Karena H tahan benturan, maka secara praktis tidak mungkin bahwa, dengan menandatangani m seseorang “secara tidak sengaja menandatangani” tanda yang berbeda pesan m′.String biner sigpki(m) disebut sebagai tanda tangan digital i dari m (relatif terhadap pki), dan dapat berupa lebih sederhana dilambangkan dengan sigi(m), ketika kunci publik pki jelas dari konteksnya. Setiap orang yang mengetahui PKI dapat menggunakannya untuk memverifikasi tanda tangan digital yang dihasilkan oleh i. Secara khusus, pada memasukkan (a) kunci publik pki dari pemain i, (b) pesan m, dan (c) string s, yaitu dugaan i tanda tangan digital dari pesan m, algoritma verifikasi V mengeluarkan output YA atau TIDAK. Properti yang kami perlukan dari skema tanda tangan digital adalah: 1. Tanda tangan yang sah selalu diverifikasi: Jika s = sigi(m), maka V (pki, m, s) = Y ES; dan 2. Tanda tangan digital sulit dipalsukan: Tanpa pengetahuan ski, tidak ada waktu untuk menemukan string seperti itu bahwa V (pki, m, s) = Y ES, untuk pesan m yang tidak pernah ditandatangani oleh i, panjangnya secara astronomis. (Mengikuti persyaratan keamanan yang kuat dari Goldwasser, Micali, dan Rivest [17], ini benar bahkan jika seseorang dapat memperoleh tanda tangan dari pesan lainnya.) Oleh karena itu, untuk mencegah orang lain menandatangani pesan atas namanya, pemain harus mempertahankan miliknya menandatangani kunci rahasia ski (karenanya disebut “kunci rahasia”), dan untuk memungkinkan siapa pun memverifikasi pesan tersebut dia menandatangani, saya tertarik untuk mempublikasikan pki kuncinya (karena itu istilah “kunci publik”). Secara umum, pesan m tidak dapat diambil dari tanda tangannya sigi(m). Untuk bertransaksi secara virtual dengan tanda tangan digital yang memenuhi properti “retrievability” yang secara konseptual mudah digunakan (yaitu, untuk jaminan bahwa penandatangan dan pesan dapat dihitung dengan mudah dari sebuah tanda tangan, kami definisikan SIGpki(m) = (i, m, sigpki(m)) dan SIGi(m) = (i, m, sigi(m)), jika pki jelas. Penandatanganan Digital Unik. Kami juga mempertimbangkan skema tanda tangan digital (G, S, V) yang memuaskan mengikuti properti tambahan. 3. Keunikan. Sulit untuk menemukan string pk′, m, s, dan s′ sedemikian rupa ̸= s′ dan V (pk′, m, s) = V (pk′, m, s′) = 1. (Perhatikan bahwa properti keunikan juga berlaku untuk string pk′ yang tidak dihasilkan secara sah kunci publik. Namun secara khusus, sifat keunikan menyiratkan bahwa, jika seseorang menggunakan generator kunci tertentu G untuk menghitung pk kunci publik bersama dengan kunci rahasia sk yang cocok, dan dengan demikian mengetahui sk, pada dasarnya mustahil baginya untuk menemukan dua digital yang berbeda tanda tangan dari pesan yang sama relatif terhadap pk.) Keterangan • Dari tanda tangan unik hingga fungsi acak yang dapat diverifikasi. Relatif terhadap digital skema tanda tangan dengan properti keunikan, pemetaan m \(\to\) H(sigi(m)) diasosiasikan ke setiap kemungkinan string m, string 256-bit unik yang dipilih secara acak, dan kebenarannya pemetaan dapat dibuktikan dengan diberi tanda tangan sigi(m). Artinya, skema hashing dan tanda tangan digital yang ideal pada dasarnya memenuhi properti keunikan memberikan implementasi dasar dari fungsi acak yang dapat diverifikasi, seperti yang diperkenalkan dan oleh Micali, Rabin, dan Vadhan [27]. (Implementasi awalnya tentu saja lebih kompleks, karena mereka tidak mengandalkan hashing yang ideal.)• Tiga kebutuhan berbeda untuk tanda tangan digital. Di Algorand, pengguna yang saya andalkan adalah digital tanda tangan untuk (1) Mengautentikasi pembayaran saya sendiri. Dalam aplikasi ini, kunci dapat bersifat “jangka panjang” (yaitu, digunakan untuk jangka waktu tertentu). menandatangani banyak pesan dalam jangka waktu yang lama) dan berasal dari skema tanda tangan biasa. (2) Menghasilkan kredensial yang membuktikan bahwa i berhak bertindak pada beberapa langkah s dalam putaran r. Di sini, kuncinya bisa bersifat jangka panjang, tetapi harus berasal dari skema yang memenuhi properti keunikan. (3) Mengautentikasi pesan yang saya kirimkan pada setiap langkah tindakannya. Di sini, kuncinya harus ada bersifat sementara (yaitu, dimusnahkan setelah penggunaan pertama), tetapi dapat berasal dari skema tanda tangan biasa. • Penyederhanaan biaya yang kecil. Untuk mempermudah, kami membayangkan setiap pengguna i memiliki satu kunci jangka panjang. Oleh karena itu, kunci tersebut harus berasal dari skema tanda tangan yang memiliki keunikan properti. Kesederhanaan seperti itu memiliki biaya komputasi yang kecil. Biasanya, sebenarnya, digital unik tanda tangan sedikit lebih mahal untuk diproduksi dan diverifikasi dibandingkan tanda tangan biasa. 2.2 Buku Besar Umum yang Diidealkan Algorand mencoba meniru sistem pembayaran berikut, berdasarkan buku besar umum yang diidealkan. 1. Status Awal. Uang dikaitkan dengan kunci publik individual (dihasilkan secara pribadi dan dimiliki oleh pengguna). Membiarkan pk1, . . . , pkj menjadi kunci publik awal dan a1, . . . , aj masing-masing jumlah awal satuan uang, maka status awalnya adalah S0 = (pk1, a1), . . . , (pkj, aj) , yang dianggap sebagai pengetahuan umum dalam sistem. 2. Pembayaran. Misalkan pk adalah kunci publik yang saat ini mempunyai \(\geq\)0 unit uang, pk′ publik lainnya kunci, dan a′ bilangan non-negatif yang tidak lebih besar dari a. Kemudian, pembayaran (sah) adalah digital tanda tangan, relatif terhadap pk, yang menetapkan transfer unit moneter a′ dari pk ke pk′, secara bersamaan dengan beberapa informasi tambahan. Dalam simbol, \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), di mana saya mewakili informasi tambahan apa pun yang dianggap berguna tetapi tidak sensitif (misalnya, waktu informasi dan pengidentifikasi pembayaran), dan saya informasi tambahan apa pun yang dianggap sensitif (misalnya, alasan pembayarannya, mungkin identitas pemilik pk dan pk′, dan sebagainya). Kita menyebut pk (atau pemiliknya) sebagai pembayar, setiap pk′ (atau pemiliknya) sebagai penerima pembayaran, dan a′ sebagai jumlah pembayaran \(\wp\). Bergabung Gratis Melalui Pembayaran. Perhatikan bahwa pengguna dapat bergabung dengan sistem kapan pun mereka mau menghasilkan pasangan kunci publik/rahasianya sendiri. Oleh karena itu, kunci publik pk′ yang muncul di pembayaran \(\wp\)di atas mungkin merupakan kunci publik yang baru dibuat dan belum pernah “memiliki” uang apa pun sebelumnya. 3. Buku Besar Ajaib. Dalam Sistem Ideal, semua pembayaran valid dan muncul dalam bukti kerusakan daftar L kumpulan pembayaran yang “diposting di langit” agar semua orang dapat melihatnya: L = BAYAR 1, BAYAR 2, . . . ,Setiap blok PAY r+1 terdiri dari himpunan semua pembayaran yang dilakukan sejak munculnya blok MEMBAYAR r. Dalam sistem ideal, blok baru muncul setelah jangka waktu tertentu (atau terbatas). Diskusi. • Lebih Banyak Pembayaran Umum dan Hasil Transaksi yang Tidak Dibelanjakan. Lebih umum lagi, jika kunci publik pk memiliki sejumlah a, maka pembayaran sah \(\wp\)pk dapat mentransfer sejumlah a′ 1, sebuah′ 2, . . ., masing-masing ke kunci pk′ 1, pk′ 2, . . ., selama P j a′ j \(\leq\)a. Dalam Bitcoin dan sistem serupa, uang yang dimiliki oleh pk kunci publik dipisahkan menjadi beberapa bagian terpisah. jumlah, dan pembayaran yang dilakukan oleh pk harus mentransfer jumlah terpisah a secara keseluruhan. Jika pk ingin mentransfer hanya sebagian kecil a′ < a dari a ke kunci lain, maka pk juga harus mentransfernya saldo, keluaran transaksi yang belum terpakai, ke kunci lain, mungkin pk itu sendiri. Algorand juga berfungsi dengan kunci yang memiliki jumlah terpisah. Namun, untuk fokus pada aspek baru dari Algorand, secara konseptual lebih mudah untuk tetap menggunakan bentuk pembayaran kami yang lebih sederhana dan kunci yang memiliki satu jumlah yang terkait dengannya. • Status Saat Ini. Skema Ideal tidak secara langsung memberikan informasi tentang arus status sistem (yaitu berapa banyak unit uang yang dimiliki setiap kunci publik). informasi ini dapat dikurangkan dari Magic Ledger. Dalam sistem yang ideal, pengguna aktif terus-menerus menyimpan dan memperbarui informasi status terkini, atau dia harus merekonstruksinya, baik dari awal, atau dari yang terakhir kali dia lakukan menghitungnya. (Dalam versi selanjutnya dari makalah ini, kami akan menambah Algorand untuk mengaktifkannya pengguna untuk merekonstruksi status saat ini dengan cara yang efisien.) • Keamanan dan “Privasi”. Tanda tangan digital menjamin bahwa tidak seorang pun dapat memalsukan pembayaran pengguna lain. Dalam pembayaran \(\wp\), kunci publik dan jumlahnya tidak disembunyikan, tetapi sensitif informasi saya. Memang benar, hanya H(I) yang muncul di \(\wp\), dan karena H merupakan fungsi ideal hash, H(I) adalah nilai acak 256-bit, dan karenanya tidak ada cara untuk mengetahui apa yang lebih baik bagi saya selain dengan hanya menebaknya. Namun, untuk membuktikan siapa saya (misalnya, untuk membuktikan alasan pembayaran) tersebut pembayar boleh saja mengungkapkan I. Kebenaran I yang diungkapkan dapat diverifikasi dengan menghitung H(I) dan membandingkan nilai yang dihasilkan dengan item terakhir \(\wp\). Faktanya, karena H tahan benturan, sulit untuk menemukan nilai kedua I′ sehingga H(I) = H(I′). 2.3 Pengertian dan Notasi Dasar Kunci, Pengguna, dan Pemilik Kecuali ditentukan lain, setiap kunci publik (“singkatnya kunci”) bersifat jangka panjang dan relatif terhadap skema tanda tangan digital dengan properti keunikan. Kunci publik yang saya ikuti sistem ketika kunci publik lain j sudah ada di sistem melakukan pembayaran ke i. Untuk warna, kami mempersonifikasikan kunci. Kita mengacu pada kunci i sebagai “dia”, katakan bahwa saya jujur, yang saya kirim dan menerima pesan, dll. Pengguna adalah sinonim untuk kunci. Ketika kita ingin membedakan suatu kunci dari orang yang memilikinya, kami masing-masing menggunakan istilah “kunci digital” dan “pemilik”. Sistem Tanpa Izin dan Berizin. Suatu sistem tidak memiliki izin, jika kunci digitalnya gratis untuk bergabung kapan saja dan pemilik dapat memiliki beberapa kunci digital; dan itu diizinkan, sebaliknya.Representasi Unik Setiap objek di Algorand memiliki representasi unik. Khususnya, setiap himpunan {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} diurutkan dengan cara yang telah ditentukan sebelumnya: misalnya, pertama secara leksikografis di x, lalu di y, dan seterusnya. Jam Kecepatan Sama Tidak ada jam global: setiap pengguna memiliki jamnya sendiri. Jam pengguna tidak perlu disinkronkan dengan cara apa pun. Namun kami berasumsi bahwa semuanya memiliki kecepatan yang sama. Misalnya, jika waktu menunjukkan pukul 12 siang menurut jam pengguna i, mungkin pukul 14:30 menurut jam pengguna i. jam pengguna lain j, tetapi jika jam menunjukkan pukul 12:01 menurut jam i, maka akan menunjukkan pukul 2:31 ke jam j. Artinya, “satu menit adalah sama (pada dasarnya sama) untuk setiap pengguna”. Putaran Algorand disusun dalam satuan logika, r = 0, 1, . . ., disebut putaran. Kami secara konsisten menggunakan superskrip untuk menunjukkan putaran. Untuk menunjukkan bahwa kuantitas non-numerik Q (misalnya, string, kunci publik, himpunan, tanda tangan digital, dll.) mengacu pada putaran r, kita cukup menulis Qr. Hanya jika Q adalah bilangan asli (sebagai lawan dari string biner yang dapat ditafsirkan sebagai bilangan), lakukan kita tulis Q(r), sehingga simbol r tidak dapat diartikan sebagai eksponen dari Q. Pada (awal a) putaran r > 0, himpunan semua kunci publik adalah PKr, dan status sistemnya adalah Sr = n aku, seorang(kanan) saya, . . .  : saya \(\in\)PKro , di mana (r) saya adalah jumlah uang yang tersedia untuk kunci publik i. Perhatikan bahwa PKr dapat dikurangkan dari Sr, dan Sr tersebut juga dapat menentukan komponen lain untuk setiap kunci publik i. Untuk putaran 0, PK0 adalah himpunan kunci publik awal, dan S0 adalah status awal. Baik PK0 dan S0 diasumsikan sebagai pengetahuan umum dalam sistem. Untuk mempermudah, pada awal putaran r, jadi adalah PK1, . . . , PKr dan S1, . . . , Sr. Pada putaran r, status sistem bertransisi dari Sr ke Sr+1: secara simbolis, Putaran r: Sr −→Sr+1. Pembayaran Di Algorand, pengguna terus melakukan pembayaran (dan menyebarkannya dengan cara dijelaskan dalam sub-bagian 2.7). Pembayaran \(\wp\)dari pengguna i \(\in\)PKr memiliki format dan semantik yang sama seperti dalam Sistem Ideal. Yaitu, \(\wp\)= SIGi(saya, saya′, a, saya, H(Saya)) . Pembayaran \(\wp\)secara individual sah pada putaran r (singkatnya pembayaran putaran-r) jika (1) jumlahnya a lebih kecil atau sama dengan a(r) i , dan (2) tidak muncul di payset resmi mana pun PAY r′ untuk r′ < r. (Seperti dijelaskan di bawah, kondisi kedua berarti \(\wp\) belum menjadi efektif. Sekumpulan pembayaran bulat-r i adalah sah secara kolektif jika jumlah pembayarannya paling banyak adalah a(r) saya. Pembayaran Set pembayaran round-r P adalah himpunan pembayaran round-r sehingga, untuk setiap pengguna i, pembayarannya dari i di P (mungkin tidak ada) yang valid secara kolektif. Himpunan semua pembayaran putaran-r adalah PAY(r). Sebuah putaran-r payset P maksimal jika tidak ada superset dari P yang merupakan payset round-r. Kami sebenarnya menyarankan bahwa pembayaran \(\wp\)juga menentukan putaran \(\rho\), \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , dan tidak valid pada putaran mana pun di luar [\(\rho\), \(\rho\) + k], untuk beberapa bilangan bulat non-negatif tetap k.4 4Ini menyederhanakan pemeriksaan apakah \(\wp\) telah menjadi “efektif” (yaitu, menyederhanakan penentuan apakah suatu pembayaran PEMBAYARAN r berisi \(\wp\). Jika k = 0, jika \(\wp\)= SIGi(r, i, i′, a, I, H(I)) , dan \(\wp\)/\(\in\)PAY r, maka saya harus mengirimkan kembali \(\wp\).Pembayaran Resmi Untuk setiap putaran r, Algorand memilih secara publik (dengan cara yang dijelaskan nanti) satu set pembayaran (mungkin kosong), PAY r, set pembayaran resmi putaran tersebut. (Intinya, PAY r mewakili pembayaran putaran-r yang “sebenarnya” telah terjadi.) Seperti pada Sistem Ideal (dan Bitcoin), (1) satu-satunya cara bagi pengguna baru j untuk memasuki sistem adalah menjadi penerima pembayaran yang termasuk dalam set pembayaran resmi PAY r pada putaran r tertentu; dan (2) PAY r menentukan status putaran berikutnya, Sr+1, dari status putaran saat ini, Sr. Secara simbolis, BAYAR r : Sr −→Sr+1. Secara khusus, 1. himpunan kunci publik putaran r + 1, PKr+1, terdiri dari gabungan PKr dan himpunan semua kunci penerima pembayaran yang muncul, untuk pertama kalinya, dalam pembayaran PAY r; dan 2. jumlah uang a(r+1) saya yang dimiliki pengguna i pada putaran r + 1 adalah jumlah dari ai(r) —yaitu, jumlah uang yang saya miliki pada putaran sebelumnya (0 jika i ̸\(\in\)PKr)— dan jumlah jumlahnya dibayarkan kepada saya sesuai dengan pembayaran PAY r. Singkatnya, seperti dalam Sistem Ideal, setiap status Sr+1 dapat dikurangkan dari riwayat pembayaran sebelumnya: BAYAR 0, . . . , BAYAR r. 2.4 Blok dan Blok Terbukti Dalam Algorand0, blok Br yang berhubungan dengan putaran r menentukan: r itu sendiri; kumpulan pembayaran putaran r, BAYAR r; besaran Qr, harus dijelaskan, dan hash dari blok sebelumnya, H(Br−1). Jadi, mulai dari beberapa blok tetap B0, kita mempunyai blockchain tradisional: B1 = (1, BAYAR 1, Q0, H(B0)), B2 = (2, BAYAR 2, Q1, H(B1)), B3 = (3, BAYAR 3, Q2, H(B2)), . . . Di Algorand, keaslian sebuah blok sebenarnya dijamin oleh informasi terpisah, sebuah “sertifikat blok” CERT r, yang mengubah Br menjadi blok terbukti, Br. Oleh karena itu, Buku Besar Ajaib diimplementasikan dengan urutan blok yang terbukti, B1, B2, . . . Diskusi Seperti yang akan kita lihat, CERT r terdiri dari sekumpulan tanda tangan digital untuk H(Br), yaitu a mayoritas anggota SV r, disertai bukti bahwa masing-masing anggota tersebut memang termasuk ke SV r. Tentu saja, kita dapat memasukkan sertifikat CERT r ke dalam blok itu sendiri, namun tetap menemukannya secara konseptual lebih bersih untuk menjaganya tetap terpisah.) Dalam Bitcoin setiap blok harus memenuhi sifat khusus, yaitu harus “berisi solusi a crypto puzzle”, yang membuat pembuatan blok menjadi intensif secara komputasi dan percabangan keduanya tidak dapat dihindari dan tidak jarang. Sebaliknya, blockchain Algorand memiliki dua keunggulan utama: dihasilkan dengan komputasi minimal, dan tidak akan bercabang dengan probabilitas yang sangat tinggi. Setiap blok Bi adalah berakhir dengan aman segera setelah memasuki blockchain.2.5 Kemungkinan Kegagalan yang Dapat Diterima Untuk menganalisis keamanan Algorand kami menentukan probabilitas, F, yang ingin kami gunakan menerima bahwa ada yang tidak beres (misalnya, himpunan pemverifikasi SV r tidak memiliki mayoritas yang jujur). Seperti halnya panjang keluaran fungsi kriptografi hash H, F juga merupakan parameter. Namun, seperti dalam kasus tersebut, kami merasa berguna untuk menetapkan F ke nilai yang konkret, sehingga mendapatkan hasil yang lebih intuitif. memahami fakta bahwa memang mungkin, di Algorand, untuk menikmati keamanan yang memadai secara bersamaan dan efisiensi yang memadai. Untuk menekankan bahwa F adalah parameter yang dapat diatur sesuai keinginan, terlebih dahulu dan perwujudan kedua yang kami tetapkan masing-masing F = 10−12 dan F = 10−18 . Diskusi Perhatikan bahwa 10−12 sebenarnya kurang dari satu dalam satu triliun, dan kami percaya bahwa 10−12 adalah pilihan F memadai dalam aplikasi kita. Mari kita tekankan bahwa 10−12 bukanlah probabilitas yang dengannya Musuh dapat memalsukan pembayaran dari pengguna yang jujur. Semua pembayaran dilakukan secara digital ditandatangani, dan dengan demikian, jika tanda tangan digital yang tepat digunakan, kemungkinan pemalsuan pembayaran adalah kecil jauh lebih rendah dari 10−12, dan pada kenyataannya, pada dasarnya 0. Peristiwa buruk yang ingin kita toleransi dengan probabilitas F adalah garpu Algorand itu blockchain. Perhatikan itu, dengan pengaturan F dan putaran yang panjangnya satu menit, percabangan diperkirakan akan terjadi di Algorand blockchain sesering (kira-kira) sekali dalam 1,9 juta tahun. Sebaliknya, di Bitcoin, percabangan cukup sering terjadi. Orang yang lebih menuntut mungkin menetapkan F ke nilai yang lebih rendah. Untuk tujuan ini, dalam perwujudan kedua kami kami mempertimbangkan untuk menyetel F ke 10−18. Perhatikan bahwa, dengan asumsi bahwa sebuah blok dihasilkan setiap detik, 1018 adalah perkiraan jumlah detik yang dibutuhkan alam semesta sejauh ini: dari Big Bang hingga saat ini waktu. Jadi, dengan F = 10−18, jika sebuah balok dihasilkan dalam sedetik, maka diperkirakan umurnya adalah alam semesta untuk melihat garpu. 2.6 Model Permusuhan Algorand dirancang agar aman dalam model yang sangat bermusuhan. Mari kami jelaskan. Pengguna yang Jujur dan Berbahaya Seorang pengguna dikatakan jujur jika dia mengikuti semua instruksi protokolnya, dan sangat mampu mengirim dan menerima pesan. Seorang pengguna jahat (yaitu, Bizantium, dalam bahasa komputasi terdistribusi) jika dia dapat menyimpang secara sewenang-wenang dari instruksi yang ditentukan. Musuh The Adversary adalah algoritma yang efisien (secara teknis waktu polinomial), dipersonifikasikan untuk warna, yang dapat langsung membuat pengguna berbahaya mana pun yang diinginkannya, kapan pun ia mau (subjek hanya melebihi jumlah pengguna yang dapat dirusaknya). Musuh sepenuhnya mengendalikan dan mengoordinasikan dengan sempurna semua pengguna jahat. Dia mengambil semua tindakan atas nama mereka, termasuk menerima dan mengirim semua pesan mereka, dan dapat membiarkan mereka menyimpang instruksi yang ditentukan mereka dengan cara yang sewenang-wenang. Atau dia dapat dengan mudah mengisolasi pengiriman pengguna yang rusak dan menerima pesan. Mari kita perjelas bahwa tidak ada orang lain yang secara otomatis mengetahui bahwa pengguna i berbahaya, meskipun kejahatan saya mungkin terjadi melalui tindakan yang dilakukan Musuh. Namun musuh yang kuat ini, • Tidak memiliki kekuatan komputasi yang tidak terbatas dan tidak berhasil menempa digital tanda tangan pengguna yang jujur, kecuali kemungkinannya dapat diabaikan; Dan• Tidak boleh mengganggu pertukaran pesan di antara pengguna yang jujur ​​dengan cara apa pun. Selain itu, kemampuannya untuk menyerang pengguna yang jujur ​​dibatasi oleh salah satu asumsi berikut. Kejujuran Mayoritas Uang Kami mempertimbangkan kontinum Mayoritas Uang Jujur (HMM) asumsi: yaitu, untuk setiap bilangan bulat non-negatif k dan real h > 1/2, HHMk > h: pengguna yang jujur di setiap putaran r memiliki sebagian lebih besar dari h dari seluruh uang yang masuk sistem pada putaran r −k. Diskusi. Dengan asumsi bahwa semua pengguna jahat mengoordinasikan tindakan mereka dengan sempurna (seolah-olah dikendalikan oleh satu entitas, Musuh) adalah hipotesis yang agak pesimistis. Koordinasi sempurna di antara mereka juga banyak individu sulit dicapai. Mungkin koordinasi hanya terjadi dalam kelompok yang terpisah dari pemain jahat. Namun, karena tingkat koordinasi pengguna jahat tidak dapat dipastikan semoga kita menikmatinya, lebih baik kita aman daripada menyesal. Dengan asumsi bahwa Musuh juga dapat secara diam-diam, dinamis, dan langsung merusak pengguna pesimis. Lagi pula, secara realistis, mengambil kendali penuh atas operasi pengguna akan memakan waktu. Asumsi HMMk > h menyiratkan, misalnya, jika putaran (rata-rata) dilaksanakan dalam satu menit, sebagian besar uang pada putaran tertentu akan tetap berada di tangan yang jujur paling sedikit dua jam, jika k = 120, dan paling sedikit satu minggu, jika k = 10.000. Perhatikan asumsi HMM dan Kekuatan Komputasi Mayoritas Jujur sebelumnya Asumsi-asumsi tersebut saling terkait dalam arti bahwa, karena daya komputasi dapat dibeli dengan uang, jika pengguna jahat memiliki sebagian besar uang, maka mereka dapat memperoleh sebagian besar daya komputasi. 2.7 Model Komunikasi Kami membayangkan penyebaran pesan —yaitu, “gosip antar teman”5— menjadi satu-satunya cara untuk menyebarkan pesan. komunikasi. Asumsi Sementara: Pengiriman Pesan Tepat Waktu di Seluruh Jaringan. Untuk Pada sebagian besar makalah ini kami berasumsi bahwa setiap pesan yang disebarkan menjangkau hampir semua pengguna yang jujur secara tepat waktu. Kami akan menghapus asumsi ini di Bagian 10, saat kami menangani jaringan partisi, baik yang terjadi secara alami maupun yang disebabkan oleh faktor yang merugikan. (Seperti yang akan kita lihat, kita hanya berasumsi pengiriman pesan tepat waktu dalam setiap komponen jaringan yang terhubung.) Salah satu cara konkrit untuk menangkap pengiriman pesan yang disebarkan secara tepat waktu (di seluruh jaringan) adalah berikut ini: Untuk semua keterjangkauan \(\rho\) > 95% dan ukuran pesan \(\mu\) \(\in\)Z+, terdapat \(\lambda\) \(\rho\),\(\mu\) sehingga, jika pengguna yang jujur menyebarkan pesan \(\mu\)-byte m pada waktu t, kemudian m mencapai, pada saat t + \(\lambda\) \(\rho\),\(\mu\), setidaknya sebagian kecil \(\rho\) dari pengguna yang jujur. 5Intinya, seperti pada Bitcoin, ketika pengguna menyebarkan pesan m, setiap pengguna aktif menerima m untuk pertama kalinya, secara acak dan mandiri memilih sejumlah kecil pengguna aktif, “tetangganya”, kepada siapa dia meneruskan m, mungkin sampai dia menerima pengakuan dari mereka. Propagasi m berakhir ketika tidak ada pengguna yang menerima m untuk pertama kalinya.Namun, properti di atas tidak dapat mendukung protokol Algorand kami, tanpa secara eksplisit dan terpisah membayangkan mekanisme untuk mendapatkan blockchain terbaru —oleh pengguna/penyimpanan/dll. Faktanya, untuk membangun blok Br yang baru, tidak hanya sekelompok verifikator yang tepat yang harus menerima putaran-r secara tepat waktu pesan-pesan, tetapi juga pesan-pesan dari putaran sebelumnya, untuk mengetahui Br−1 dan semua pesan lainnya sebelumnya blok, yang diperlukan untuk menentukan apakah pembayaran dalam Br sah. Berikut ini asumsi saja sudah cukup. Asumsi Propagasi Pesan (MP): Untuk semua \(\rho\) > 95% dan \(\mu\) \(\in\)Z+, terdapat \(\lambda\) \(\rho\),\(\mu\) sedemikian rupa sehingga, untuk semua waktu t dan semua pesan \(\mu\)-byte m disebarkan oleh pengguna yang jujur sebelum t −\(\lambda\) \(\rho\),\(\mu\), m diterima, pada waktu t, oleh setidaknya sebagian kecil \(\rho\) dari pengguna yang jujur. Protokol Algorand ′ sebenarnya menginstruksikan masing-masing sejumlah kecil pengguna (yaitu, pemverifikasi suatu langkah tertentu dalam Algorand ′, untuk menyebarkan pesan terpisah dengan ukuran (kecil) yang ditentukan, dan kita perlu membatasi waktu yang dibutuhkan untuk memenuhi instruksi ini. Kami melakukannya dengan memperkaya anggota parlemen asumsi sebagai berikut. Untuk semua n, \(\rho\) > 95%, dan \(\mu\) \(\in\)Z+, terdapat \(\lambda\)n,\(\rho\),\(\mu\) sehingga, untuk semua waktu t dan semua \(\mu\)-byte pesan m1, . . . , mn, masing-masing disebarkan oleh pengguna yang jujur sebelum t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . . . , banyak diterima, pada waktu t, setidaknya oleh sebagian kecil \(\rho\) dari pengguna yang jujur. Catatan • Asumsi di atas sengaja dibuat sederhana, namun juga lebih kuat dari yang dibutuhkan dalam makalah kami.6 • Untuk mempermudah, kita asumsikan \(\rho\) = 1, sehingga tidak lagi menyebutkan \(\rho\). • Kami secara pesimistis berasumsi, asalkan dia tidak melanggar asumsi MP, maka Musuh sepenuhnya mengontrol pengiriman semua pesan. Apalagi tanpa diketahui oleh orang jujur pengguna, Musuh dia dapat secara sewenang-wenang memutuskan pemain jujur mana yang menerima pesan mana ketika, dan seenaknya mempercepat penyampaian pesan apapun yang diinginkannya.7

Protokol BA BA⋆dalam Pengaturan Tradisional

Seperti yang telah ditekankan, perjanjian Bizantium adalah unsur utama Algorand. Memang benar, itu sudah selesai penggunaan protokol BA sehingga Algorand tidak terpengaruh oleh fork. Namun, untuk amannya terhadap kami Musuh yang kuat, Algorand harus bergantung pada protokol BA yang memenuhi kemampuan penggantian pemain baru kendala. Selain itu, agar Algorand menjadi efisien, protokol BA seperti itu harus sangat efisien. Protokol BA pertama kali didefinisikan untuk model komunikasi yang diidealkan, lengkap dan sinkron jaringan (jaringan SC). Model seperti ini memungkinkan desain dan analisis protokol BA yang lebih sederhana. 6Mengingat persentase jujur h dan probabilitas kegagalan yang dapat diterima F, Algorand menghitung batas atas, N, ke jumlah maksimum anggota verifikator dalam satu langkah. Jadi, asumsi MP hanya perlu berlaku untuk n \(\leq\)N. Selain itu, sebagaimana dinyatakan, asumsi MP tetap berlaku tidak peduli berapa banyak pesan lain yang dapat disebarkan mj's. Namun, seperti yang akan kita lihat, di Algorand pesan di disebarkan dalam waktu yang pada dasarnya tidak tumpang tindih interval, selama satu blok disebarkan, atau paling banyak N pemverifikasi menyebarkan blok kecil (misalnya, 200B) pesan. Oleh karena itu, kita dapat menyatakan kembali asumsi MP dengan cara yang lebih lemah namun juga lebih kompleks. 7Misalnya, dia bisa langsung mempelajari pesan yang dikirim oleh pemain jujur. Jadi, pengguna jahat i′, siapa diminta untuk menyebarkan pesan secara bersamaan dengan pengguna yang jujur i, selalu dapat memilih pesannya sendiri berdasarkan m′ pesan m sebenarnya disebarkan oleh i. Kemampuan ini terkait dengan bergegas, dalam istilah komputasi terdistribusi sastra.Oleh karena itu, di bagian ini, kami memperkenalkan protokol BA baru, BA⋆, untuk jaringan SC dan mengabaikannya masalah penggantian pemain sama sekali. Protokol BA⋆merupakan kontribusi yang bernilai tersendiri. Memang benar, ini adalah protokol kriptografi BA paling efisien untuk jaringan SC yang dikenal sejauh ini. Untuk menggunakannya dalam protokol Algorand kami, kami memodifikasi sedikit BA⋆, untuk memperhitungkan perbedaan kami model dan konteks komunikasi, namun pastikan, di bagian X, untuk menyoroti bagaimana BA⋆ digunakan dalam protokol kami yang sebenarnya Algorand ′. Kita mulai dengan mengingat model di mana BA⋆ beroperasi dan gagasan perjanjian Bizantium. 3.1 Jaringan Lengkap Sinkron dan Musuh yang Cocok Dalam jaringan SC, terdapat jam umum yang berdetak pada setiap waktu integral r = 1, 2, . . . Pada setiap kali klik r, setiap pemain i secara instan dan bersamaan mengirimkan satu pesan Pak i,j (mungkin pesan kosong) untuk setiap pemain j, termasuk dirinya sendiri. Setiap Tuan i,j diterima pada saat itu klik r+1 oleh pemain j, beserta identitas pengirim i. Sekali lagi, dalam protokol komunikasi, seorang pemain jujur jika dia mengikuti semua yang ditentukan instruksi, dan sebaliknya berbahaya. Semua pemain jahat dikontrol sepenuhnya dan sempurna dikoordinasikan oleh Musuh, yang, khususnya, segera menerima semua pesan yang ditujukan kepadanya pemain jahat, dan memilih pesan yang mereka kirim. Musuh dapat segera membuat pengguna jujur mana pun yang dia inginkan menjadi jahat kapan pun dia mengklik yang diinginkannya, hanya bergantung pada kemungkinan batas atas jumlah pemain jahat. Artinya, Musuh “tidak dapat mengganggu pesan yang telah dikirim oleh pengguna i yang jujur”, yang mana akan terjadi disampaikan seperti biasa. Musuh juga memiliki kemampuan tambahan untuk melihat secara instan, di setiap putaran genap pesan yang dikirim oleh pemain jujur ​​saat ini, dan secara instan menggunakan informasi ini untuk memilih pesan yang dikirim oleh pemain jahat pada saat yang sama dicentang. Keterangan • Kekuatan Musuh. Pengaturan di atas sangat merugikan. Memang dalam perjanjian Bizantium literatur, banyak situasi yang tidak terlalu bermusuhan. Namun, ada beberapa pengaturan yang lebih bermusuhan juga sudah diperhatikan, dimana Musuh setelah melihat pesan yang dikirimkan oleh pemain jujur i pada waktu tertentu klik r, memiliki kemampuan untuk segera menghapus semua pesan ini dari jaringan i yang rusak, pilih pesan yang dikirim oleh i yang sekarang berbahaya pada saat klik r, dan dapatkan pesan tersebut disampaikan seperti biasa. Kekuatan Musuh yang dibayangkan cocok dengan yang dia miliki di lingkungan kita. • Abstraksi Fisik. Model komunikasi yang dibayangkan mengabstraksi model yang lebih fisik, di mana setiap pasangan pemain (i,j) dihubungkan oleh jalur komunikasi terpisah dan pribadi li,j. Artinya, tidak ada orang lain yang dapat menyuntikkan, mengganggu, atau memperoleh informasi tentang pesan yang dikirimkan li,j. Satu-satunya cara bagi Musuh untuk memiliki akses ke li,j adalah dengan merusak i atau j. • Privasi dan Otentikasi. Dalam jaringan SC, privasi dan otentikasi pesan dijamin dengan asumsi. Sebaliknya, dalam jaringan komunikasi kita, tempat pesan disebarkan dari peer to peer, otentikasi dijamin oleh tanda tangan digital, dan privasi tidak ada. Jadi, untuk mengadopsi protokol BA⋆ke pengaturan kami, setiap pesan yang dipertukarkan harus ditandatangani secara digital (lebih lanjut mengidentifikasi negara bagian pengirimannya). Untungnya, protokol BA yang kami miliki pertimbangkan untuk menggunakan di Algorand tidak memerlukan privasi pesan.3.2 Gagasan Perjanjian Bizantium Gagasan perjanjian Bizantium diperkenalkan oleh Pease Shostak dan Lamport [31] untuk kasus biner, yaitu ketika setiap nilai awal terdiri dari sedikit. Namun, hal itu segera diperpanjang ke nilai awal yang sewenang-wenang. (Lihat survei Fischer [16] dan Chor and Dwork [10].) Oleh BA protokol, yang kami maksud adalah protokol yang bernilai arbitrer. Definisi 3.1. Dalam jaringan sinkron, misalkan P adalah protokol n-pemain, yang kumpulan pemainnya sama pengetahuan di antara para pemain, t bilangan bulat positif sehingga n \(\geq\)2t + 1. Kita katakan bahwa P adalah an nilai arbitrer (masing-masing, biner) (n, t)-Protokol perjanjian Bizantium dengan kesehatan \(\sigma\) \(\in\)(0, 1) jika, untuk setiap himpunan nilai V tidak mengandung simbol khusus \(\bot\)(masing-masing, untuk V = {0, 1}), dalam suatu eksekusi di mana paling banyak t pemainnya jahat dan di mana setiap pemain saya memulai dengan sebuah nilai awal vi \(\in\)V , setiap pemain jujur j berhenti dengan probabilitas 1, mengeluarkan nilai outi \(\in\)V \(\cup\){\(\bot\)} untuk memenuhi, dengan probabilitas paling sedikit \(\sigma\), dua kondisi berikut: 1. Kesepakatan: Terdapat \(\in\)V \(\cup\){\(\bot\)} sehingga outi = out untuk semua pemain jujur i. 2. Konsistensi: jika, untuk suatu nilai v \(\in\)V , vi = v untuk semua pemain jujur, maka keluar = v. Kami menyebut out sebagai keluaran P, dan setiap outi sebagai keluaran pemain i. 3.3 Notasi BA # Dalam protokol BA kami, seorang pemain diharuskan menghitung berapa banyak pemain yang mengiriminya pesan tertentu langkah tertentu. Oleh karena itu, untuk setiap kemungkinan nilai v yang mungkin dikirim,

s

saya (v) (atau hanya #i(v) ketika s jelas) adalah jumlah pemain j yang i telah menerima v pada langkah s. Mengingat bahwa seorang pemain i menerima tepat satu pesan dari setiap pemain j, jika jumlahnya pemain adalah n, maka, untuk semua i dan s, P v #s saya(v) = n. 3.4 Protokol Biner BA BBA⋆ Pada bagian ini kami menyajikan protokol BA biner baru, BBA⋆, yang lebih mengandalkan kejujuran dari dua pertiga pemain dan sangat cepat: tidak peduli apa yang mungkin dilakukan pemain jahat, setiap eksekusi loop utamanya membuat para pemain setuju dengan probabilitas 1/3. Setiap pemain memiliki kunci publiknya sendiri dari skema tanda tangan digital yang memenuhi tanda tangan unik properti. Karena protokol ini dimaksudkan untuk dijalankan pada jaringan lengkap yang sinkron, maka tidak ada kebutuhan pemain saya untuk menandatangani setiap pesannya. Tanda tangan digital digunakan untuk menghasilkan bit acak yang cukup umum pada Langkah 3. (Dalam Algorand, tanda tangan digital juga digunakan untuk mengautentikasi semua pesan lainnya.) Protokol memerlukan pengaturan minimal: string acak umum r, tidak tergantung pada pemain kunci. (Dalam Algorand, r sebenarnya diganti dengan kuantitas Qr.) Protokol BBA⋆adalah loop 3 langkah, di mana pemain berulang kali menukar nilai Boolean, dan pemain yang berbeda dapat keluar dari putaran ini pada waktu yang berbeda. Seorang pemain saya keluar dari lingkaran ini dengan menyebarkan, pada langkah tertentu, baik nilai khusus 0∗atau nilai khusus 1∗, sehingga memerintahkan semua pemain untuk “berpura-pura” mereka masing-masing menerima 0 dan 1 dari i di semua langkah selanjutnya. (Atau dikatakan: asumsikanbahwa pesan terakhir yang diterima pemain j dari pemain lain i agak b. Lalu, dalam langkah apa pun di mana dia tidak menerima pesan apa pun dari i, j bertindak seolah-olah saya mengiriminya bit b.) Protokol ini menggunakan penghitung \(\gamma\), yang mewakili berapa kali perulangan 3 langkahnya telah dieksekusi. Pada awal BBA⋆, \(\gamma\) = 0. (Orang mungkin menganggap \(\gamma\) sebagai penghitung global, namun sebenarnya meningkat oleh masing-masing pemain setiap kali loop dijalankan.) Ada n \(\geq\)3t + 1, di mana t adalah jumlah maksimum pemain jahat yang mungkin. Sebuah biner string x diidentifikasi dengan bilangan bulat yang representasi binernya (dengan kemungkinan awalan 0) adalah x; dan lsb(x) menunjukkan bit paling signifikan dari x. Protokol BBA⋆ (Komunikasi) Langkah 1. [Langkah Koin-Tetap-Ke-0] Setiap pemain saya mengirimkan bi. 1.1 Jika #1 i (0) \(\geq\)2t + 1, lalu i set bi = 0, mengirimkan 0∗, keluaran outi = 0, dan BERHENTI. 1.2 Jika #1 i (1) \(\geq\)2t + 1, maka i menetapkan bi = 1. 1.3 Jika tidak, saya menetapkan bi = 0. (Komunikasi) Langkah 2. [Langkah Koin-Tetap-Ke-1] Setiap pemain saya mengirimkan bi. 2.1 Jika #2 i (1) \(\geq\)2t + 1, maka i menetapkan bi = 1, mengirimkan 1∗, keluaran keluari = 1, dan BERHENTI. 2.2 Jika #2 i (0) \(\geq\)2t + 1, maka saya menetapkan bi = 0. 2.3 Jika tidak, saya menetapkan bi = 1. (Komunikasi) Langkah 3. [Langkah Membalik Koin] Setiap pemain i mengirimkan bi dan SIGi(r, \(\gamma\)). 3.1 Jika #3 i (0) \(\geq\)2t + 1, maka i menetapkan bi = 0. 3.2 Jika #3 i (1) \(\geq\)2t + 1, maka i menetapkan bi = 1. 3.3 Selain itu, misalkan Si = {j \(\in\)N yang telah mengirimkan i pesan yang benar pada langkah ini 3 }, saya menetapkan bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\)))); meningkatkan \(\gamma\)i sebesar 1; dan kembali ke Langkah 1. Teorema 3.1. Kapanpun n \(\geq\)3t + 1, BBA⋆adalah protokol biner (n, t)-BA dengan tingkat kesehatan 1. Bukti Teorema 3.1 diberikan di [26]. Adaptasinya dengan lingkungan kami, dan kemampuan pemainnya untuk diganti properti adalah hal baru. Catatan Sejarah Protokol BA biner probabilistik pertama kali diusulkan oleh Ben-Or di pengaturan asinkron [7]. Protokol BBA⋆adalah adaptasi baru, terhadap pengaturan kunci publik kita, dari protokol biner BA Feldman dan Micali [15]. Protokol mereka adalah yang pertama bekerja sesuai harapan jumlah langkah yang konstan. Ini berhasil dengan meminta para pemainnya sendiri menerapkan koin yang sama, sebuah gagasan yang diajukan oleh Rabin, yang mengimplementasikannya melalui pihak eksternal yang dipercaya [32].3.5 Konsensus Bertingkat dan Protokol GC Mari kita ingat, untuk nilai-nilai yang sewenang-wenang, gagasan konsensus jauh lebih lemah dibandingkan kesepakatan Bizantium. Definisi 3.2. Misalkan P adalah suatu protokol yang himpunan semua pemainnya diketahui secara umum, dan masing-masing pemain saya secara pribadi mengetahui nilai awal yang berubah-ubah v′ saya. Kita katakan bahwa P adalah protokol konsensus dengan tingkat (n, t) jika, dalam setiap eksekusi dengan n pemain, pada kebanyakan dari mereka berbahaya, setiap pemain jujur saya berhenti mengeluarkan pasangan tingkat nilai (vi, gi), dimana gi \(\in\){0, 1, 2}, sehingga memenuhi tiga kondisi berikut: 1. Untuk semua pemain jujur i dan j, |gi −gj| \(\leq\)1. 2. Untuk semua pemain jujur ​​i dan j, gi, gj > 0 ⇒vi = vj. 3. Jika v′ 1 = \(\cdots\) = v′ n = v untuk beberapa nilai v, maka vi = v dan gi = 2 untuk semua pemain jujur i. Catatan Sejarah Gagasan tentang konsensus yang bertingkat berasal dari gagasan yang bertingkat siaran, dikemukakan oleh Feldman dan Micali di [15], dengan memperkuat gagasan tentang tentara salib perjanjian, seperti yang diperkenalkan oleh Dolev [12], dan disempurnakan oleh Turpin dan Coan [33].8 Di [15], penulis juga menyediakan protokol penyiaran bertingkat 3 langkah (n, t), yang disebut gradecast, untuk n \(\geq\)3t+1. Protokol penyiaran bertingkat (n, t) yang lebih kompleks untuk n > 2t+1 kemudian ditemukan oleh Katz dan Koo [19]. Protokol dua langkah GC berikut terdiri dari dua langkah terakhir dari gradecast, yang dinyatakan dalam kami notasi. Untuk menekankan fakta ini, dan untuk mencocokkan langkah-langkah protokol Algorand ′ bagian 4.1, kami masing-masing sebutkan 2 dan 3 langkah-langkah GC. Protokol GC Langkah 2. Setiap pemain saya mengirimkan v′ saya kepada semua pemain. Langkah 3. Setiap pemain i mengirimkan string x ke semua pemain jika dan hanya jika #2 saya (x) \(\geq\)2t + 1. Penentuan Keluaran. Setiap pemain i mengeluarkan pasangan (vi, gi) yang dihitung sebagai berikut: • Jika, untuk beberapa x, #3 i (x) \(\geq\)2t + 1, maka vi = x dan gi = 2. • Jika, untuk beberapa x, #3 i (x) \(\geq\)t + 1, maka vi = x dan gi = 1. • Lain, vi = \(\bot\)dan gi = 0. Teorema 3.2. Jika n \(\geq\)3t + 1, maka GC adalah protokol siaran bergradasi (n, t). Buktinya langsung mengikuti dari protokol gradecast di [15], dan dengan demikian dihilangkan.9 8Intinya, dalam protokol penyiaran bertingkat, (a) masukan dari setiap pemain adalah identitas pemain terkemuka pemain, pengirim, yang memiliki nilai sembarang v sebagai masukan pribadi tambahan, dan (b) keluaran harus memenuhi sifat yang sama 1 dan 2 dari konsensus bertingkat, ditambah sifat berikut 3′: jika pengirimnya jujur, maka vi = v dan gi = 2 untuk semua pemain jujur i. 9Memang, dalam protokol mereka, pada langkah 1, pengirim mengirimkan nilai pribadinya v ke semua pemain, dan setiap pemain i izinkan v′ saya terdiri dari nilai yang sebenarnya dia terima dari pengirim pada langkah 1.3.6 Protokol BA⋆ Kami sekarang menjelaskan protokol BA nilai arbitrer BA⋆melalui protokol BA biner BBA⋆dan protokol konsensus bertingkat GC. Di bawah ini, nilai awal setiap pemain i adalah v′ saya. Protokol BA⋆ Langkah 1 dan 2. Setiap pemain i menjalankan GC, pada input v′ i, untuk menghitung pasangan (vi, gi). Langkah 3,. . . Setiap pemain i mengeksekusi BBA⋆—dengan input awal 0, jika gi = 2, dan 1 sebaliknya— jadi untuk menghitung bit outi. Penentuan Keluaran. Setiap pemain i mengeluarkan vi, jika outi = 0, dan \(\bot\)sebaliknya. Teorema 3.3. Kapanpun n \(\geq\)3t + 1, BA⋆adalah protokol (n, t)-BA dengan tingkat kesehatan 1. Bukti. Pertama-tama kita buktikan Konsistensi, lalu Kesepakatan. Bukti Konsistensi. Asumsikan bahwa, untuk beberapa nilai v \(\in\)V , v′ i = v. Kemudian, berdasarkan sifat 3 dari konsensus dinilai, setelah pelaksanaan GC, semua pemain jujur keluar (v, 2). Oleh karena itu, 0 adalah bagian awal dari semua pemain jujur di akhir eksekusi BBA⋆. Demikian dengan Perjanjian properti perjanjian biner Bizantium, di akhir pelaksanaan BA⋆, outi = 0 untuk semua jujur pemain. Artinya keluaran setiap pemain jujur i di BA⋆adalah vi = v. ✷ Bukti Perjanjian. Karena BBA⋆ juga merupakan protokol BA biner (A) outi = 1 untuk semua pemain jujur i, atau (B) outi = 0 untuk semua pemain jujur i. Dalam kasus A, semua pemain jujur ​​mengeluarkan \(\bot\)di BA⋆, dan dengan demikian Perjanjian berlaku. Pertimbangkan sekarang kasus B.In dalam hal ini, dalam eksekusi BBA⋆, bit awal dari setidaknya satu pemain jujur i adalah 0. (Memang, jika bit awal dari semua pemain jujur adalah 1, maka, dengan properti Konsistensi BBA⋆, kita akan memiliki outj = 1 untuk semua j yang jujur.) Oleh karena itu, setelah eksekusi GC, i mengeluarkan pasangan (v, 2) untuk beberapa nilai v. Jadi, berdasarkan properti 1 dari konsensus bertingkat, gj > 0 untuk semua pemain jujur j. Oleh karena itu, oleh properti 2 dari konsensus bertingkat, vj = v untuk semua pemain jujur j. Ini menyiratkan bahwa, pada akhir BA⋆, setiap pemain jujur j mengeluarkan v. Jadi, Perjanjian berlaku juga dalam kasus B. ✷ Karena Konsistensi dan Perjanjian berlaku, BA⋆adalah protokol BA dengan nilai arbitrer. Catatan Sejarah Turpin dan Coan adalah orang pertama yang menunjukkan bahwa, untuk n \(\geq\)3t+1, biner apa pun (n, t)-BA protokol dapat dikonversi ke protokol dengan nilai arbitrer (n, t)-BA. Pengurangan nilai sewenang-wenang Perjanjian Bizantium terhadap perjanjian biner Bizantium melalui konsensus bertingkat lebih bersifat modular dan lebih bersih, dan menyederhanakan analisis protokol Algorand kami Algorand ′. Generalisasi BA⋆untuk digunakan di Algorand Algorand berfungsi meskipun semua komunikasi dilakukan melalui bergosip. Namun, meski disajikan dalam jaringan komunikasi tradisional dan familiar, tetap saja untuk memungkinkan perbandingan yang lebih baik dengan penemuan sebelumnya dan pemahaman yang lebih mudah, protokol BA⋆berfungsi juga di jaringan gosip. Faktanya, dalam perwujudan rinci Algorand, kami akan menyajikannya langsung untuk jaringan gosip. Kami juga harus menunjukkan bahwa hal ini memenuhi kemampuan pergantian pemain properti yang sangat penting agar Algorand aman dalam model yang sangat bermusuhan.

Protokol apa pun yang dapat diganti oleh pemain BA yang bekerja di jaringan komunikasi gosip dapat digunakan digunakan dengan aman dalam sistem Algorand yang inventif. Khususnya, Micali dan Vaikunthanatan telah memperluas BA⋆untuk bekerja dengan sangat efisien juga dengan mayoritas pemain jujur. Itu protokol juga dapat digunakan di Algorand.

Dua Perwujudan Algorand

Seperti yang telah dibahas, pada tingkat yang sangat tinggi, putaran Algorand idealnya berlangsung sebagai berikut. Pertama, secara acak pengguna yang dipilih, pemimpin, mengusulkan dan mengedarkan blok baru. (Proses ini mencakup awalnya memilih beberapa pemimpin potensial dan kemudian memastikan bahwa, setidaknya dalam jangka waktu tertentu, a muncul satu pemimpin yang sama.) Kedua, komite pengguna yang dipilih secara acak dipilih, dan mencapai persetujuan Bizantium mengenai blok yang diusulkan oleh pemimpinnya. (Proses ini mencakup itu setiap langkah protokol BA dijalankan oleh komite yang dipilih secara terpisah.) Blok yang disepakati kemudian ditandatangani secara digital oleh ambang batas (TH) tertentu dari anggota komite. Tanda tangan digital ini diedarkan sehingga semua orang yakin blok mana yang baru. (Ini termasuk mengedarkan kredensial penandatangan, dan hanya mengautentikasi hash blok baru, memastikan bahwa semua orang dijamin akan mempelajari blok tersebut, setelah hash-nya dibuat jelas.) Pada dua bagian berikutnya, kami menyajikan dua perwujudan dari Algorand, Algorand ′ 1 dan Algorand′ 2, yang bekerja berdasarkan asumsi mayoritas pengguna yang jujur. Di Bagian 8 kami menunjukkan cara menerapkan hal ini perwujudan untuk bekerja di bawah asumsi mayoritas uang yang jujur. Algorand' Saya hanya membayangkan > 2/3 anggota komite jujur. Selain itu, di Algorand' Pada tanggal 1 Januari, jumlah langkah untuk mencapai kesepakatan Bizantium dibatasi pada tingkat yang cukup tinggi nomor, sehingga kesepakatan dijamin akan dicapai dengan probabilitas yang sangat besar dalam a jumlah langkah yang tetap (tetapi mungkin memerlukan waktu lebih lama daripada langkah Algorand ′ 2). Di dalam hal yang jarang terjadi dimana kesepakatan belum tercapai pada langkah terakhir, panitia menyetujuinya blok kosong, yang selalu valid. Algorand ' 2 membayangkan bahwa jumlah anggota yang jujur dalam sebuah komite selalu lebih besar daripada atau sama dengan ambang batas tetap tH (yang menjamin hal tersebut, setidaknya dengan kemungkinan yang sangat besar 2/3 anggota panitia jujur). Selain itu, Algorand′ 2 mengizinkan persetujuan Bizantium untuk dicapai dalam sejumlah langkah yang berubah-ubah (tetapi berpotensi dalam waktu yang lebih singkat dari Algorand ′ 1). Sangat mudah untuk mendapatkan banyak varian dari perwujudan dasar ini. Khususnya, mudah, diberikan Algorand' 2, untuk mengubah Algorand ′ 1 sehingga memungkinkan tercapainya persetujuan Bizantium secara sewenang-wenang sejumlah langkah. Kedua perwujudan tersebut memiliki inti, notasi, gagasan, dan parameter yang sama. 4.1 Inti yang Sama Tujuan Idealnya, untuk setiap putaran r, Algorand akan memenuhi properti berikut: 1. Kebenaran Sempurna. Semua pengguna yang jujur ​​menyetujui blok yang sama Br. 2. Kelengkapan 1. Dengan probabilitas 1, payset Br, PAY r, maksimal.10 10Karena payset didefinisikan berisi pembayaran yang valid, dan pengguna yang jujur hanya melakukan pembayaran yang valid, PAY r berisi pembayaran “yang terutang saat ini” dari semua pengguna yang jujur.Tentu saja, menjamin kebenaran yang sempurna adalah hal yang sepele: setiap orang selalu memilih pejabatnya payset PAY r menjadi kosong. Namun dalam kasus ini, sistem akan memiliki kelengkapan 0. Sayangnya, menjamin kebenaran dan kelengkapan yang sempurna 1 tidaklah mudah di hadapan pihak yang jahat pengguna. Algorand dengan demikian mengadopsi tujuan yang lebih realistis. Secara informal, h menunjukkan persentase dari pengguna yang jujur, h > 2/3, sasaran Algorand adalah Menjamin, dengan kemungkinan besar, kebenaran sempurna dan kelengkapan mendekati h. Mengutamakan kebenaran dibandingkan kelengkapan tampaknya merupakan pilihan yang masuk akal: pembayaran tidak diproses satu putaran dapat diproses pada putaran berikutnya, tetapi garpu harus dihindari, jika memungkinkan. Perjanjian Bizantium yang Dipimpin Kebenaran Sempurna dapat dijamin sebagai berikut. Pada awalnya putaran r, setiap pengguna i membuat blok kandidatnya sendiri Br i , dan kemudian semua pengguna mencapai Bizantium kesepakatan pada satu blok kandidat. Sesuai perkenalan kami, protokol BA yang digunakan memerlukan mayoritas jujur 2/3 dan pemain dapat diganti. Setiap langkahnya dapat dilakukan oleh yang kecil dan kumpulan verifikasi yang dipilih secara acak, yang tidak berbagi variabel dalam apa pun. Sayangnya, pendekatan ini tidak mempunyai jaminan kelengkapan. Hal ini terjadi karena kandidat blok pengguna yang jujur kemungkinan besar sangat berbeda satu sama lain. Jadi, pada akhirnya blok yang disepakati mungkin selalu merupakan blok dengan pembayaran tidak maksimal. Faktanya, hal itu mungkin selalu terjadi blok kosong, B\(\varepsilon\), yaitu blok yang pembayarannya kosong. jadilah default, yang kosong. Algorand ′ menghindari masalah kelengkapan ini sebagai berikut. Pertama, pemimpin putaran r, \(\ell\)r, dipilih. Kemudian, \(\ell\)r menyebarkan blok kandidatnya sendiri, Br \(\ell\)r. Akhirnya, pengguna mencapai kesepakatan tentang pemblokiran tersebut mereka sebenarnya menerima dari \(\ell\)r. Sebab, bilamana jujur, Kebenaran dan Kelengkapan Sempurna 1 keduanya memegang, Algorand ′ memastikan bahwa \(\ell\)r jujur dengan probabilitas mendekati h. (Ketika pemimpinnya adalah jahat, kami tidak peduli apakah blok yang disepakati adalah blok dengan pembayaran kosong. Bagaimanapun, a pemimpin jahat \(\ell\)r mungkin selalu memilih Br \(\ell\)r menjadi blok kosong, dan kemudian jujur menyebarkannya, sehingga memaksa pengguna yang jujur untuk menyetujui blok kosong tersebut.) Seleksi Pemimpin Pada Algorand, blok ke-r berbentuk Br = (r, PAY r, Qr, H(Br−1). Seperti telah disebutkan dalam pendahuluan, besaran Qr−1 dikonstruksikan secara cermat sehingga menjadi pada dasarnya tidak dapat dimanipulasi oleh Musuh kita yang sangat kuat. (Nanti di bagian ini, kita akan melakukannya memberikan beberapa intuisi tentang mengapa hal ini terjadi.) Pada awal putaran r, semua pengguna mengetahui blockchain sejauh ini, B0, . . . , Br−1, yang darinya mereka menyimpulkan himpunan pengguna dari setiap putaran sebelumnya: itu adalah, PK1, . . . , PKr−1. Pemimpin potensial pada putaran r adalah pengguna i sedemikian rupa .H SIGi r, 1, Qr−1 \(\leq\)p. Mari kami jelaskan. Perhatikan bahwa, karena kuantitas Qr−1 adalah bagian dari blok Br−1, dan yang mendasarinya skema tanda tangan memenuhi properti keunikan, SIGi r, 1, Qr−1 adalah string biner secara unik terkait dengan i dan r. Jadi, karena H adalah oracle acak, H SIGi r, 1, Qr−1 adalah 256-bit acak string panjang yang diasosiasikan secara unik ke i dan r. Simbol “.” di depan H SIGi r, 1, Qr−1 adalah titik desimal (dalam kasus kita, biner), sehingga ri \(\triangleq\).H SIGi r, 1, Qr−1 adalah ekspansi biner dari a nomor acak 256-bit antara 0 dan 1 yang dikaitkan secara unik ke i dan r. Jadi kemungkinannya ri kurang dari atau sama dengan p pada dasarnya adalah p. (Mekanisme seleksi calon pemimpin kami telah dilakukan terinspirasi oleh skema pembayaran mikro Micali dan Rivest [28].) Probabilitas p dipilih sehingga, dengan probabilitas yang sangat besar (yaitu, 1 −F), setidaknya ada satu pemverifikasi potensial adalah jujur. (Jika faktanya, p dipilih sebagai probabilitas terkecil.)Perhatikan bahwa, karena i adalah satu-satunya yang mampu menghitung tanda tangannya sendiri, maka hanya dia yang bisa menentukan apakah dia berpotensi menjadi pemverifikasi putaran 1. Namun, dengan mengungkapkan kredensialnya sendiri, \(\sigma\)r saya \(\triangleq\)SIGi r, 1, Qr−1 , saya dapat membuktikan kepada siapa pun sebagai pemverifikasi potensial putaran r. Pemimpin \(\ell\)r didefinisikan sebagai pemimpin potensial yang kredensial hashnya lebih kecil dari pemimpin hashed kredensial semua pemimpin potensial lainnya j: yaitu, H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s j ). Perhatikan bahwa, karena \(\ell\)r yang jahat mungkin tidak mengungkapkan kredensialnya, pemimpin putaran r yang benar mungkin mengungkapkan kredensialnya tidak pernah diketahui, dan, kecuali ada hubungan yang mustahil, \(\ell\)r memang satu-satunya pemimpin putaran r. Mari kita akhirnya mengemukakan detail terakhir namun penting: pengguna saya bisa menjadi pemimpin potensial (dan dengan demikian pemimpin) dari suatu putaran r hanya jika dia termasuk dalam sistem setidaknya selama k putaran. Ini menjamin non-manipulasi Qr dan semua kuantitas Q di masa depan. Bahkan, salah satu calon pemimpin sebenarnya akan menentukan Qr. Seleksi Verifikasi Setiap langkah s > 1 pada putaran r dieksekusi oleh sekelompok kecil verifier, SV r,s. Sekali lagi, setiap pemverifikasi i \(\in\)SV r,s dipilih secara acak di antara pengguna yang sudah berada dalam putaran k sistem sebelum r, dan lagi melalui kuantitas khusus Qr−1. Secara khusus, i \(\in\)PKr−k adalah pemverifikasi dalam SV r,s, jika .H SIGi r, s, Qr−1 \(\leq\)p′ . Sekali lagi, hanya saya yang tahu apakah dia anggota SV r,s, tapi kalau memang begitu, dia bisa membuktikannya dengan menunjukkan kredensialnya \(\sigma\)r,s saya \(\triangleq\)H(SIGi r, s, Qr−1 ). Pemverifikasi i \(\in\)SV r,s mengirimkan pesan, mr,s saya, di langkah s pada putaran r, dan pesan ini menyertakan kredensialnya \(\sigma\)r,s i , untuk mengaktifkan pemverifikasi f langkah sarang untuk mengenali Tuan itu, s saya adalah pesan langkah yang sah. Probabilitas p′ dipilih untuk memastikan bahwa, dalam SV r,s, membiarkan #good menjadi bilangan pengguna yang jujur dan #buruk jumlah pengguna yang jahat, dengan kemungkinan besar sebagai berikut dua kondisi berlaku. Untuk perwujudan Algorand′ 1: (1) #baik > 2 \(\cdot\) #buruk dan (2) #baik + 4 \(\cdot\) #buruk < 2n, dimana n adalah kardinalitas yang diharapkan dari SV r,s. Untuk perwujudan Algorand′ 2: (1) #baik > tH dan (2) #baik + 2#buruk < 2tH, dengan tH adalah ambang batas yang ditentukan. Kondisi ini menyiratkan bahwa, dengan probabilitas yang cukup tinggi, (a) pada langkah terakhir BA protokol, setidaknya akan ada sejumlah pemain jujur ​​yang menandatangani blok baru secara digital Br, (b) hanya satu blok per putaran yang dapat memiliki jumlah tanda tangan yang diperlukan, dan (c) BA yang digunakan protokol memiliki (di setiap langkah) 2/3 mayoritas jujur yang disyaratkan. Mengklarifikasi Pembuatan Blok Jika pemimpin putaran r \(\ell\)r jujur, maka blok yang sesuai adalah dari bentuk Br = r, BAYAR r, SIG\(\ell\)r Qr−1 , H Br−1 , dimana payset PAY r maksimal. (ingatlah bahwa semua pembayaran, menurut definisi, sah secara kolektif.) Lain (yaitu, jika \(\ell\)r berbahaya), Br memiliki salah satu dari dua kemungkinan bentuk berikut: Br = r, BAYAR r, SIGi Qr−1 , H Br−1 dan Br = Br \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Br−1 .Dalam bentuk pertama, PAY r adalah set pembayaran (yang belum tentu maksimal) dan dapat berupa PAY r = \(\emptyset\); dan aku adalah calon pemimpin putaran r. (Namun, saya mungkin bukan pemimpin \(\ell\)r. Hal ini mungkin terjadi jika \(\ell\)r merahasiakan kredensialnya dan tidak mengungkapkan dirinya.) Bentuk kedua muncul ketika, dalam pelaksanaan putaran-r protokol BA, semua pemain jujur menampilkan nilai default, yaitu blok kosong Br \(\varepsilon\) dalam aplikasi kita. (Menurut definisi, kemungkinan keluaran protokol BA menyertakan nilai default, yang secara umum dilambangkan dengan \(\bot\). Lihat bagian 3.2.) Perhatikan bahwa, meskipun payset kosong pada kedua kasus, Br = r, \(\emptyset\), SIGi Qr−1 , H Br−1 dan Sdr \(\varepsilon\) adalah blok yang berbeda secara sintaksis dan muncul dalam dua situasi berbeda: masing-masing, “semua berjalan cukup lancar dalam pelaksanaan protokol BA”, dan “ada yang tidak beres di protokol BA, dan nilai defaultnya adalah keluaran”. Sekarang mari kita jelaskan secara intuitif bagaimana pembangkitan blok Br berlangsung pada putaran r Algorand ′. Pada langkah pertama, setiap pemain yang memenuhi syarat, yaitu setiap pemain i \(\in\)PKr−k, memeriksa apakah dia berpotensi pemimpin. Jika hal ini terjadi, maka saya ditanya, menggunakan semua pembayaran yang telah dilihatnya sejauh ini, dan saat ini blockchain, B0, . . . , Br−1, untuk diam-diam menyiapkan set pembayaran maksimal, MEMBAYAR r aku, dan diam-diam merakit blok kandidatnya, Br = r, BAYAR r saya, SIGi Qr−1 , H Br−1 . Artinya, bukan hanya dia saja termasuk dalam Br i , sebagai komponen kedua dari pembayaran yang baru saja disiapkan, tetapi juga, sebagai komponen ketiga, tanda tangannya sendiri pada Qr−1, komponen ketiga dari blok terakhir, Br−1. Akhirnya, dia menyebarkan miliknya pesan putaran-r-langkah-1, tuan,1 i , yang meliputi (a) blok calonnya Br i , (b) tanda tangannya yang sebenarnya dari blok kandidatnya (yaitu, tanda tangannya pada hash dari Br i , dan (c) kredensialnya sendiri \(\sigma\)r,1 saya, membuktikan bahwa dia memang berpotensi menjadi pemverifikasi putaran r. (Perhatikan bahwa, sampai saya yang jujur menyampaikan pesannya, Tuan,1 saya, Musuh tidak tahu bahwa saya adalah a pemverifikasi potensial. Jika ia ingin merusak calon pemimpin yang jujur, maka Musuh juga akan melakukan hal yang sama pemain jujur acak yang korup. Namun, begitu dia melihat Tuan, 1 i , karena berisi kredensial i, maka Musuh mengetahui dan dapat merusak i, namun tidak dapat mencegah mr,1 i , yang disebarkan secara viral, dari menjangkau semua pengguna di sistem.) Pada langkah kedua, setiap verifikator terpilih j \(\in\)SV r,2 mencoba mengidentifikasi pemimpin putaran. Secara khusus, j mengambil kredensial langkah-1, \(\sigma\)r,1 saya1 , . . . , \(\sigma\)r,1 di , terkandung dalam pesan langkah-1 yang tepat mr,1 saya dia telah menerima; hashes semuanya, yaitu menghitung H  \(\sigma\)r,1 i1  , . . . , H  \(\sigma\)r,1 di  ; menemukan kredensialnya, \(\sigma\)r,1 \(\ell\)j , yang hash minimum secara leksikografis; dan mempertimbangkan \(\ell\)r j menjadi pemimpin ronde r. Ingatlah bahwa setiap kredensial yang dipertimbangkan adalah tanda tangan digital dari Qr−1, yaitu SIGi r, 1, Qr−1 adalah ditentukan secara unik oleh i dan Qr−1, bahwa H acak oracle, dan dengan demikian setiap H(SIGi r, 1, Qr−1 adalah string acak sepanjang 256-bit yang unik untuk setiap calon pemimpin i pada putaran r. Dari sini kita dapat menyimpulkan bahwa, jika string 256-bit Qr−1 adalah dirinya sendiri secara acak dan independen dipilih, sehingga akan menjadi hash kredensial dari semua calon pemimpin putaran r. Faktanya, semuanya calon pemimpin sudah terdefinisi dengan baik, begitu pula kredensial mereka (baik yang benar-benar dihitung atau tidak). tidak). Selanjutnya, himpunan pemimpin potensial pada putaran r adalah himpunan bagian acak dari pengguna putaran r −k, dan calon pemimpin yang jujur saya selalu membangun dan menyebarkan pesannya dengan benar, Tuan saya , yang berisi kredensial saya. Jadi, karena persentase pengguna yang jujur adalah h, berapapun jumlahnya minimum yang mungkin dilakukan oleh calon pemimpin yang jahat (misalnya, mengungkapkan atau menyembunyikan kredensial mereka sendiri). hash kredensial calon pemimpin adalah milik pengguna yang jujur, yang harus diidentifikasi oleh semua orang menjadi pemimpin \(\ell\)r pada ronde r. Oleh karena itu, jika string 256-bit Qr−1 itu sendiri secara acak dan dipilih secara independen, dengan probabilitas tepat h (a) pemimpin \(\ell\)r jujur dan (b) \(\ell\)j = \(\ell\)r untuk semua verifikator langkah-2 yang jujur j. Pada kenyataannya, kredensial hashed, ya, dipilih secara acak, tetapi bergantung pada Qr−1, yaitutidak dipilih secara acak dan independen. Akan tetapi, kita akan membuktikan dalam analisis kita bahwa Qr−1 adalah cukup tidak dapat dimanipulasi untuk menjamin bahwa pemimpin suatu ronde jujur terhadap probabilitas h′ cukup dekat dengan h: yaitu, h′ > h2(1 + h −h2). Misalnya, jika h = 80%, maka h′ > 0,7424. Setelah mengidentifikasi pemimpin ronde (yang mereka lakukan dengan benar jika pemimpinnya jujur), tugas verifikasi langkah ke-2 adalah mulai melaksanakan BA dengan menggunakan nilai awal apa yang mereka yakini menjadi blok pemimpin. Sebenarnya, untuk meminimalkan jumlah komunikasi yang diperlukan, pemverifikasi j \(\in\)SV r,2 tidak menggunakan, sebagai nilai masukannya v′ j ke protokol Bizantium, blok Bj itu dia sebenarnya telah menerima dari \(\ell\)j (pengguna j diyakini sebagai pemimpin), tetapi pemimpinnya, tetapi hash dari blok itu, yaitu v′ j = H(Bi). Jadi, setelah penghentian protokol BA, verifikasi dari langkah terakhir jangan menghitung blok bulat-r yang diinginkan Br, tetapi hitung (otentikasi dan menyebarkan) H(Br). Oleh karena itu, karena H(Br) ditandatangani secara digital oleh cukup banyak verifikasi langkah terakhir dari protokol BA, pengguna dalam sistem akan menyadari bahwa H(Br) adalah hash dari yang baru blok. Namun, mereka juga harus mengambil (atau menunggu, karena eksekusinya cukup asinkron) tersebut blok Br itu sendiri, yang mana protokol memastikan bahwa memang tersedia, tidak peduli apa pun Musuhnya mungkin bisa dilakukan. Asinkroni dan Waktu Algorand' 1 dan Algorand′ 2 memiliki tingkat asinkroni yang signifikan. Hal ini dikarenakan Adversary mempunyai keleluasaan yang luas dalam menjadwalkan pengiriman pesan-pesan yang sedang dilakukannya disebarkan. Selain itu, apakah jumlah langkah dalam satu putaran dibatasi atau tidak, tetap ada varians dikontribusikan oleh jumlah langkah yang sebenarnya diambil. Begitu dia mempelajari sertifikat B0, . . . , Br−1, pengguna i menghitung Qr−1 dan mulai bekerja pada putaran r, memeriksa apakah dia calon pemimpin, atau pemverifikasi pada beberapa langkah s pada putaran r. Dengan asumsi bahwa saya harus bertindak pada langkah s, mengingat ketidaksinkronan yang dibahas, saya bergantung pada berbagai strategi untuk memastikan bahwa dia memiliki informasi yang cukup sebelum dia bertindak. Misalnya, dia mungkin menunggu untuk menerima setidaknya sejumlah pesan dari pemverifikasi langkah sebelumnya, atau tunggu waktu yang cukup untuk memastikan bahwa dia menerima pesan yang cukup banyak pemverifikasi dari langkah sebelumnya. Seed Qr dan Parameter Lihat-Kembali k Ingatlah bahwa, idealnya, besaran Qr seharusnya acak dan independen, meskipun cukup jika mereka tidak dapat dimanipulasi oleh Musuh. Sekilas, kita dapat memilih Qr−1 yang bertepatan dengan H MEMBAYAR r−1 , dan dengan demikian menghindari tentukan Qr−1 secara eksplisit di Br−1. Namun, analisis dasar mengungkapkan bahwa pengguna jahat mungkin saja melakukannya manfaatkan mekanisme seleksi ini.11 Beberapa upaya tambahan menunjukkan bahwa banyak sekali upaya lainnya 11Kita berada di awal ronde r −1. Jadi, Qr−2 = PAY r−2 diketahui publik, dan Musuh diketahui secara pribadi mengetahui siapa calon pemimpin yang ia kendalikan. Asumsikan bahwa Musuh mengendalikan 10% pengguna, dan bahwa, dengan probabilitas yang sangat tinggi, pengguna jahat w adalah calon pemimpin putaran r −1. Artinya, asumsikan itu H SIGw r −2, 1, Qr−2 Jumlahnya sangat kecil sehingga sangat kecil kemungkinannya calon pemimpin yang jujur akan menjadi pemimpin yang jujur pemimpin putaran r −1. (Ingatlah bahwa, karena kita memilih calon pemimpin melalui mekanisme penyortiran kriptografi rahasia, Musuh tidak tahu siapa calon pemimpin yang jujur.) Oleh karena itu, Musuh berada dalam posisi yang patut ditiru. posisi memilih payset PAY ′ yang diinginkannya, dan menjadikannya payset resmi pada putaran r −1. Namun, dia bisa berbuat lebih banyak. Dia juga dapat memastikan bahwa, dengan kemungkinan besar, () salah satu pengguna jahatnya akan menjadi pemimpinnya juga dari putaran r, sehingga dia dapat dengan bebas memilih berapa PAY rnya. (Dan seterusnya. Setidaknya untuk jangka waktu yang lama, yaitu, selama kejadian yang berpeluang tinggi tersebut benar-benar terjadi.) Untuk menjamin (), Musuh bertindak sebagai berikut. Biar BAYAR' menjadi pembayaran yang disukai Musuh untuk putaran r −1. Kemudian, dia menghitung H(PAY ′) dan memeriksa apakah, untuk beberapa hal pemain z yang sudah jahat, SIGz(r, 1, H(PAY ′)) sangat kecil, yaitu cukup kecil sehingga sangat tinggi probabilitas z akan menjadi pemimpin putaran r. Jika hal ini terjadi, maka dia menginstruksikan w untuk memilih blok kandidatnyaalternatif, berdasarkan jumlah blok tradisional mudah dieksploitasi oleh Musuh untuk memastikannya bahwa pemimpin yang jahat sangat sering terjadi. Kami malah mendefinisikan merek kami secara spesifik dan induktif kuantitas baru Qr sehingga dapat membuktikan bahwa ia tidak dapat dimanipulasi oleh Musuh. Yaitu, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), jika Br bukan blok kosong, dan Qr \(\triangleq\)H(Qr−1, r) sebaliknya. Intuisi mengapa konstruksi Qr ini berhasil adalah sebagai berikut. Anggaplah sejenak demikian Qr−1 benar-benar dipilih secara acak dan independen. Lalu, apakah Qr juga demikian? Ketika \(\ell\)r jujur jawabannya adalah (secara kasar) ya. Hal ini terjadi karena H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256 adalah fungsi acak. Namun ketika \(\ell\)r berbahaya, Qr tidak lagi didefinisikan secara univokal dari Qr−1 dan \(\ell\)r. Setidaknya ada dua nilai terpisah untuk Qr. Satu tetap menjadi Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), dan yang lainnya adalah H(Qr−1, r). Pertama-tama mari kita berargumen bahwa, meskipun pilihan kedua agak sewenang-wenang, pilihan kedua mutlak wajib. Alasannya adalah bahwa orang jahat selalu dapat menyebabkan masalah kandidat blok yang benar-benar berbeda untuk diterima oleh pemverifikasi yang jujur pada langkah kedua.12 Sekali jika demikian, mudah untuk memastikan bahwa blok tersebut pada akhirnya disetujui melalui protokol BA putaran r akan menjadi putaran default, dan karenanya tidak akan berisi tanda tangan digital Qr−1 siapa pun. Tapi sistem harus terus berjalan, dan untuk itu diperlukan seorang pemimpin untuk putaran r. Jika pemimpin ini otomatis dan dipilih secara terbuka, maka Musuh akan merusaknya dengan sepele. Jika dipilih oleh sebelumnya Qr−1 melalui proses yang sama, maka \(\ell\)r akan kembali menjadi pemimpin di babak r+1. Kami secara khusus mengusulkan untuk menggunakan mekanisme penyortiran kriptografi rahasia yang sama, tetapi diterapkan pada kuantitas Q baru: yaitu, H(Qr−1, r). Dengan menjadikan kuantitas ini sebagai keluaran H menjamin bahwa keluarannya acak, dan dengan memasukkan r sebagai masukan kedua dari H, sementara semua penggunaan H lainnya memiliki satu atau 3+ masukan, “menjamin” bahwa Qr tersebut dipilih secara independen. Sekali lagi, pilihan khusus kami atas alternatif Qr tidak masalah, yang penting \(\ell\)r punya dua pilihan untuk Qr, sehingga dia bisa menggandakan peluangnya untuk memiliki pengguna jahat lainnya sebagai pemimpin berikutnya. Opsi untuk Qr bahkan mungkin lebih banyak bagi Musuh yang mengendalikan \(\ell\)r jahat. Misalnya, x, y, dan z adalah tiga pemimpin potensial yang berbahaya pada putaran r sedemikian rupa sehingga H \(\sigma\)r,1 x
< H \(\sigma\)r,1 kamu
< H \(\sigma\)r,1 z
dan H  \(\sigma\)r,1 z  sangat kecil. Artinya, sangat kecil sehingga ada kemungkinan besar H  \(\sigma\)r,1 z  adalah lebih kecil dari kredensial hashed dari setiap calon pemimpin yang jujur. Kemudian, dengan meminta x untuk menyembunyikan miliknya kredensial, Musuh memiliki peluang bagus untuk membuat y menjadi pemimpin putaran r −1. Ini menyiratkan bahwa dia memiliki pilihan lain untuk Qr: yaitu SIGy Qr−1 . Demikian pula, Musuh mungkin minta x dan y untuk menahan kredensial mereka, agar z menjadi pemimpin putaran r −1 dan mendapatkan opsi lain untuk Qr: yaitu SIGz Qr−1 . Tentu saja, masing-masing opsi ini dan opsi lainnya mempunyai peluang gagal yang tidak nol, karena Musuh tidak dapat memprediksi hash tanda tangan digital calon pengguna yang jujur. Br−1 saya = (r −1, PAY ′, H(Br−2). Selain itu, dia memiliki dua pengguna jahat lainnya x dan y untuk terus menghasilkan pembayaran baru \(\wp\)′, dari satu ke yang lain, hingga, untuk beberapa pengguna jahat z (atau bahkan untuk beberapa pengguna tetap z) H (SIGz (PAY ′ \(\cup\){\(\wp\)})) adalah sangat kecil juga. Eksperimen ini akan berhenti dengan cepat. Dan ketika itu terjadi, Musuh meminta kami untuk melamar calon blok Br−1 saya = (r −1, BAYAR ′ \(\cup\){\(\wp\)}, H(Br−2). 12Misalnya, untuk membuatnya lebih sederhana (namun ekstrim), “ketika waktu langkah kedua hampir habis”, \(\ell\)r dapat langsung mengirimkan email ke kandidat blok Bi yang berbeda ke setiap pengguna i. Dengan cara ini, siapa pun pemverifikasi langkah ke-2, merekalah yang akan melakukan hal tersebut akan menerima blok yang sangat berbeda.Analisis yang cermat dan mirip rantai Markov menunjukkan hal itu, apa pun opsi yang dipilih Musuh untuk membuat pada putaran r −1, selama dia tidak dapat memasukkan pengguna baru ke dalam sistem, dia tidak dapat menguranginya probabilitas pengguna yang jujur menjadi pemimpin putaran r + 40 jauh di bawah h. Inilah alasannya yang kami minta agar calon pemimpin putaran r adalah pengguna yang sudah ada di putaran r −k. Ini adalah cara untuk memastikan bahwa, pada putaran r −k, Musuh tidak dapat mengubah kemungkinannya sebanyak itu pengguna yang jujur menjadi pemimpin putaran r. Faktanya, tidak peduli pengguna apa yang dia tambahkan ke dalamnya sistem di putaran r −k hingga r, mereka tidak memenuhi syarat untuk menjadi pemimpin potensial (dan a fortiori the pemimpin) putaran r. Jadi parameter lihat kembali k pada akhirnya adalah parameter keamanan. (Meskipun, seperti yang akan kita lihat di bagian 7, ini juga bisa menjadi semacam “parameter kenyamanan”.) Kunci Singkat Meskipun eksekusi protokol kami tidak dapat menghasilkan fork, kecuali dengan probabilitas yang dapat diabaikan, Musuh dapat menghasilkan percabangan, di blok ke-r, setelah blok sah blok r telah dibuat. Secara kasar, setelah Br dihasilkan, Musuh telah mengetahui siapa yang melakukan verifikasi pada setiap langkah dari putaran r adalah. Oleh karena itu, ia dapat merusak semuanya dan mewajibkan mereka untuk mengesahkan blok baru f Sdr. Karena blok palsu ini mungkin disebarkan hanya setelah yang sah, pengguna yang telah melakukannya memperhatikan tidak akan tertipu.13 Meskipun demikian, f Br secara sintaksis benar dan kami ingin dicegah agar tidak diproduksi. Kami melakukannya melalui aturan baru. Pada dasarnya, anggota verifikasi menetapkan SV r,s dari suatu langkah s putaran r menggunakan kunci publik sementara pkr,s saya untuk menandatangani pesan mereka secara digital. Kunci ini hanya sekali pakai dan kunci rahasianya adalah skr,s saya hancur setelah digunakan. Dengan cara ini, jika ada pemverifikasi kemudian dirusak, Musuh tidak dapat memaksanya untuk menandatangani apa pun yang tidak ia tandatangani pada awalnya. Tentu saja, kita harus memastikan bahwa Musuh tidak mungkin menghitung kunci baru g pr,s saya dan meyakinkan pengguna yang jujur bahwa ini adalah kunci pemverifikasi i \(\in\)SV r,s yang tepat untuk digunakan pada langkah s. 4.2 Ringkasan Umum Notasi, Pengertian, dan Parameter Notasi • r \(\geq\)0: bilangan bulat saat ini. • s \(\geq\)1: nomor langkah saat ini pada putaran r. • Br: blok yang dihasilkan pada putaran r. • PKr: himpunan kunci publik pada akhir putaran r −1 dan pada awal putaran r. • Sr: status sistem pada akhir putaran r −1 dan awal putaran r.14 • PAY r : payset yang terdapat pada Br. • \(\ell\)r: pemimpin putaran-r. \(\ell\)r memilih payset PAY r pada putaran r (dan menentukan Qr berikutnya). • Qr: benih dari putaran r, suatu kuantitas (yaitu, string biner) yang dihasilkan pada akhir putaran r dan digunakan untuk memilih pemverifikasi untuk putaran r + 1. Qr tidak bergantung pada pembayaran di blok dan tidak dapat dimanipulasi oleh \(\ell\)r. 13Pertimbangkan untuk merusak pembawa berita di jaringan TV besar, dan memproduksi serta menyiarkan film berita hari ini menunjukkan Menteri Clinton memenangkan pemilihan presiden terakhir. Sebagian besar dari kita akan mengenalinya sebagai tipuan. Tapi seseorang yang baru sadar dari koma mungkin akan tertipu. 14Dalam sistem yang tidak sinkron, pengertian “akhir putaran r −1” dan “awal putaran r” perlu didefinisikan secara hati-hati. Secara matematis, PKr dan Sr dihitung dari status awal S0 dan blok-bloknya B1, . . . , Br−1.• SV r,s: himpunan pemverifikasi yang dipilih untuk langkah s pada putaran r. • SV r: himpunan verifikasi yang dipilih untuk putaran r, SV r = \(\cup\)s\(\geq\)1SV r,s. • MSV r,s dan HSV r,s: masing-masing, himpunan verifier yang jahat dan himpunan verifier yang jujur dalam SV r, s. MSV r,s \(\cup\)HSV r,s = SV r,s dan MSV r,s ∩HSV r,s = \(\emptyset\). • n1 \(\in\)Z+ dan n \(\in\)Z+: masing-masing, jumlah calon pemimpin yang diharapkan di setiap SV r,1, dan jumlah verifikator yang diharapkan dalam setiap SV r,s, untuk s > 1. Perhatikan bahwa n1 << n, karena kita membutuhkan setidaknya satu anggota jujur yang jujur di SV r,1, tapi setidaknya mayoritas anggota jujur di setiap SV r,s untuk s > 1. • h \(\in\)(0, 1): konstanta yang lebih besar dari 2/3. h adalah rasio kejujuran dalam sistem. Artinya, itu sebagian kecil dari pengguna jujur atau uang jujur, tergantung asumsi yang digunakan, dalam setiap PKr setidaknya h. • H: fungsi kriptografi hash, dimodelkan sebagai oracle acak. • \(\bot\): String khusus yang panjangnya sama dengan keluaran H. • F \(\in\)(0, 1): parameter yang menentukan probabilitas kesalahan yang diperbolehkan. Probabilitas \(\leq\)F adalah dianggap “dapat diabaikan”, dan probabilitas \(\geq\)1 −F dianggap “luar biasa”. • ph \(\in\)(0, 1): probabilitas bahwa pemimpin suatu ronde r, \(\ell\)r, adalah jujur. Idealnya ph = h. Dengan adanya Adversary maka nilai ph akan ditentukan dalam analisa. • k \(\in\)Z+: parameter lihat kembali. Artinya, putaran r −k adalah tempat pemverifikasi putaran r berada dipilih dari —yakni, SV r \(\subseteq\)PKr−k.15 • p1 \(\in\)(0, 1): untuk langkah pertama putaran r, pengguna pada putaran r −k dipilih berada di SV r,1 dengan probabilitas p1 \(\triangleq\) n1 |P Kr−k|. • p \(\in\)(0, 1): untuk setiap langkah s > 1 pada putaran r, pengguna pada putaran r −k dipilih untuk berada dalam SV r,s dengan probabilitas p \(\triangleq\) n |P Kr−k|. • CERT r : sertifikat untuk Br. Ini adalah satu set tanda tangan H(Br) dari verifier yang tepat di putaran r. • Br \(\triangleq\)(Br, CERT r) merupakan blok terbukti. Seorang pengguna saya mengenal Br jika dia memiliki (dan berhasil memverifikasi) kedua bagian dari blok yang terbukti. Perhatikan bahwa CERT yang dilihat oleh pengguna yang berbeda mungkin berbeda. • τ r i : waktu (lokal) dimana pengguna yang saya kenal Br. Dalam protokol Algorand, setiap pengguna memiliki miliknya sendiri jam sendiri. Jam pengguna yang berbeda tidak perlu disinkronkan, namun harus memiliki kecepatan yang sama. Hanya untuk tujuan analisis, kami mempertimbangkan jam referensi dan mengukur kinerja para pemain. waktu terkait sehubungan dengan itu. • \(\alpha\)r,s saya dan \(\beta\)r,s i : masing-masing waktu (lokal) pengguna i memulai dan mengakhiri eksekusi Langkah s-nya putaran r. • Λ dan \(\lambda\): pada dasarnya, batas atas, masing-masing, waktu yang dibutuhkan untuk melaksanakan Langkah 1 dan waktu yang diperlukan untuk setiap langkah lain dari protokol Algorand. Parameter Λ membatasi waktu untuk menyebarkan satu blok 1MB. (Dalam notasi kami, Λ = \(\lambda\) \(\rho\),1 MB. Mengingat notasi kita, yang kita tetapkan \(\rho\) = 1 untuk kesederhanaan, dan bloknya adalah dipilih dengan panjang paling banyak 1MB, kita mempunyai Λ = \(\lambda\)1,1,1MB.) 15Sebenarnya, “r −k” seharusnya adalah “maks{0, r −k}”.Parameter \(\lambda\) melampaui waktu untuk menyebarkan satu pesan kecil per pemverifikasi dalam Langkah s > 1. (Menggunakan, seperti pada Bitcoin, tanda tangan kurva elips dengan kunci 32B, panjang pesan verifikasi adalah 200B. Jadi, dalam notasi kita, \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Kami berasumsi bahwa Λ = O(\(\lambda\)). Gagasan • Pemilihan verifikasi. Untuk setiap putaran r dan langkah s > 1, SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. Masing-masing pengguna i \(\in\)PKr−k secara pribadi menghitung tanda tangannya menggunakan kunci jangka panjangnya dan memutuskan apakah i \(\in\)SV r,s atau tidak. Jika i \(\in\)SV r,s, maka SIGi(r, s, Qr−1) adalah kredensial i (r, s), dilambangkan secara kompak oleh \(\sigma\)r,s saya. Untuk langkah pertama putaran r, SV r,1 dan \(\sigma\)r,1 saya didefinisikan dengan cara yang sama, dengan p digantikan oleh p1. Itu penguji di SV r,1 adalah pemimpin potensial. • Pemilihan pemimpin. Pengguna i \(\in\)SV r,1 adalah pemimpin putaran r, dilambangkan dengan \(\ell\)r, jika H(\(\sigma\)r,1 saya ) \(\leq\)H(\(\sigma\)r,1 j ) untuk semua potensi pemimpin j \(\in\)SV r,1. Kapan pun hashes dari kredensial dua pemain dibandingkan, kemungkinannya kecil jika terjadi ikatan, protokol selalu memutus ikatan secara leksikografis menurut (publik jangka panjang kunci dari) calon pemimpin. Berdasarkan definisi, nilai hash kredensial pemain \(\ell\)r juga merupakan yang terkecil di antara semua pengguna di PKr−k. Perhatikan bahwa seorang calon pemimpin tidak dapat secara pribadi memutuskan apakah dia seorang pemimpin atau bukan, tanpa melihat kredibilitas calon pemimpin lainnya. Karena nilai hash seragam secara acak, ketika SV r,1 tidak kosong, \(\ell\)r selalu ada dan jujur dengan probabilitas minimal h. Parameter n1 cukup besar untuk memastikan bahwa masing-masing SV r,1 tidak kosong dengan kemungkinan yang sangat besar. • Struktur blok. Balok tak kosong berbentuk Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)), dan balok kosong berbentuk Br ǫ = (r, \(\emptyset\), Qr−1, H(Br−1)). Perhatikan bahwa blok yang tidak kosong mungkin masih berisi set pembayaran kosong PAY r, jika tidak ada pembayaran yang dilakukan babak ini atau jika pemimpinnya jahat. Namun, blok yang tidak kosong menyiratkan bahwa identitas \(\ell\)r, kredensialnya \(\sigma\)r,1 \(\ell\)r dan SIG\(\ell\)r(Qr−1) semuanya telah terungkap tepat waktu. Protokol menjamin bahwa, jika pemimpinnya jujur, maka blok tersebut tidak akan kosong dengan kemungkinan yang sangat besar. • Benih Qr. Jika Br tidak kosong, maka Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), jika tidak Qr \(\triangleq\)H(Qr−1, r). Parameter • Hubungan antara berbagai parameter. — Pengukur dan calon pemimpin putaran r dipilih dari pengguna di PKr−k, dimana k dipilih sehingga Musuh tidak dapat memprediksi Qr−1 kembali pada putaran r −k −1 dengan probabilitas lebih baik daripada F: jika tidak, ia akan dapat memperkenalkan pengguna jahat untuk putaran r −k, yang semuanya akan menjadi pemimpin/pengukur potensial pada putaran r, yang berhasil

memiliki pemimpin yang jahat atau mayoritas yang jahat di SV r,s untuk beberapa langkah yang diinginkan oleh dia. — Untuk Langkah 1 setiap putaran r, n1 dipilih sehingga dengan probabilitas yang sangat besar, SV r,1 ̸= \(\emptyset\). • Contoh pilihan parameter penting. — Output H panjangnya 256-bit. — jam = 80%, n1 = 35. — Λ = 1 menit dan \(\lambda\) = 10 detik. • Inisialisasi protokol. Protokol dimulai pada waktu 0 dengan r = 0. Karena tidak ada “B−1” atau “CERT −1”, secara sintaksis B−1 adalah parameter publik dengan komponen ketiganya menentukan Q−1, dan semua pengguna mengetahui B−1 pada waktu 0.

Algorand '

1 Di bagian ini, kami membuat versi Algorand ′ yang bekerja dengan asumsi berikut. Asumsi Mayoritas Pengguna Jujur: Lebih dari 2/3 pengguna di setiap PKr adalah jujur. Di Bagian 8, kami menunjukkan cara mengganti asumsi di atas dengan Mayoritas Jujur yang diinginkan Asumsi uang. 5.1 Notasi dan Parameter Tambahan Notasi • m \(\in\)Z+: jumlah langkah maksimum dalam protokol BA biner, kelipatan 3. • Lr \(\leq\)m/3: variabel acak yang mewakili jumlah percobaan Bernoulli yang diperlukan untuk mendapatkan hasil 1, ketika setiap percobaan adalah 1 dengan probabilitas ph 2 dan paling banyak terdapat m/3 percobaan. Jika semua percobaan gagal maka Lr \(\triangleq\)m/3. Lr akan digunakan untuk membatasi waktu yang dibutuhkan untuk menghasilkan blok Br. • tH = 2n 3 + 1: jumlah tanda tangan yang diperlukan dalam kondisi akhir protokol. • CERT r : sertifikat untuk Br. Ini adalah satu set tanda tangan H(Br) dari verifier yang tepat di putaran r. Parameter • Hubungan antara berbagai parameter. — Untuk setiap langkah s > 1 pada putaran r, n dipilih sehingga, dengan probabilitas yang sangat besar, |HSV r,s| > 2|MSV r,s| dan |HSV r,s| + 4|MSV r,s| < 2n. Semakin mendekati 1 nilai h, maka n harus semakin kecil. Secara khusus, kami menggunakan (varian dari) Batas Cherno untuk memastikan kondisi yang diinginkan terpenuhi dengan kemungkinan yang sangat besar. — m dipilih sedemikian rupa sehingga Lr < m/3 dengan probabilitas yang sangat besar. • Contoh pilihan parameter penting. — F = 10−12. — n \(\approx\)1500, k = 40 dan m = 180.5.2 Menerapkan Kunci Ephemeral di Algorand ′ 1 Seperti telah disebutkan, kami berharap bahwa verifier i \(\in\)SV r,s menandatangani pesannya secara digital mr,s saya langkah s pada putaran r, relatif terhadap pkr kunci publik sementara, s i , menggunakan kunci rahasia sementara skr,s saya itu dia segera menghancurkan setelah digunakan. Oleh karena itu, kami memerlukan metode yang efisien untuk memastikan bahwa setiap pengguna dapat melakukannya verifikasi bahwa pkr,s saya memang kunci yang digunakan untuk memverifikasi tanda tangan saya pak saya. Kami melakukannya dengan (untuk yang terbaik sepengetahuan kami) penggunaan baru skema tanda tangan berbasis identitas. Pada tingkat tinggi, dalam skema seperti itu, otoritas pusat A menghasilkan kunci master publik, PMK, dan kunci master rahasia yang sesuai, SMK. Mengingat identitas, U, dari pemain U, A menghitung, melalui SMK, skU kunci tanda tangan rahasia relatif terhadap kunci publik U, dan secara pribadi memberikan skU ke U. (Memang benar, dalam skema tanda tangan digital berbasis identitas, kunci publik dari pengguna U adalah U itu sendiri!) Dengan cara ini, jika A menghancurkan SMK setelah menghitung kunci rahasia pengguna yang ingin dia aktifkan menghasilkan tanda tangan digital, dan tidak menyimpan kunci rahasia apa pun yang dihitung, maka hanya U yang melakukannya dapat menandatangani pesan secara digital relatif terhadap kunci publik U. Jadi, siapa pun yang mengetahui “nama U”, secara otomatis mengetahui kunci publik U, dan dengan demikian dapat memverifikasi tanda tangan U (mungkin juga menggunakan kunci master publik PMK). Dalam aplikasi kita, otoritas A adalah pengguna i, dan himpunan semua kemungkinan pengguna yang bertepatan dengan U pasangan langkah bulat (r, s) di —katakanlah— S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, dengan r′ diberikan putaran, dan m + 3 batas atas dengan jumlah langkah yang mungkin terjadi dalam satu putaran. Ini cara, pkr, s saya \(\triangleq\)(i, r, s), sehingga semua orang melihat tanda tangan i SIGr,s pkr, s saya (Tuan, s i ) bisa, dengan luar biasa probabilitasnya, segera verifikasi untuk jutaan putaran pertama r setelah r′. Dengan kata lain saya generate dulu PMK dan SMK. Kemudian, ia mempublikasikan bahwa PMK adalah majikannya kunci publik untuk setiap putaran r \(\in\)[r′, r′ + 106], dan menggunakan SMK untuk memproduksi dan menyimpan rahasia secara pribadi kunci skr,s saya untuk setiap rangkap tiga (i, r, s) \(\in\)S. Selesai, dia menghancurkan SMK. Jika dia memutuskan bahwa dia tidak melakukannya bagian dari SV r,s, maka saya boleh meninggalkan skr,s saya sendirian (karena protokol tidak mengharuskan dia melakukan autentikasi pesan apa pun di Langkah s pada putaran r). Kalau tidak, saya pertama kali menggunakan skr,s saya untuk menandatangani pesannya secara digital, Tuan, s saya, dan lalu hancurkan skr,s saya. Perhatikan bahwa saya dapat mempublikasikan kunci master publik pertamanya ketika dia pertama kali memasuki sistem. Artinya, pembayaran yang sama \(\wp\)yang membawa i ke dalam sistem (pada putaran r′ atau pada putaran yang mendekati r′), juga dapat tentukan, atas permintaan i, bahwa kunci master publik i untuk setiap putaran r \(\in\)[r′, r′ + 106] adalah PMK —misalnya, dengan termasuk sepasang bentuk (PMK, [r′, r′ + 106]). Perhatikan juga bahwa, karena m + 3 adalah jumlah langkah maksimum dalam satu putaran, dengan asumsi bahwa satu putaran membutuhkan waktu satu menit, simpanan kunci sementara yang dihasilkan akan bertahan selama hampir dua tahun. Pada saat yang sama waktu, kunci rahasia sementara ini tidak akan memakan waktu terlalu lama untuk diproduksi. Menggunakan berbasis kurva elips sistem dengan kunci 32B, setiap kunci rahasia dihitung dalam beberapa mikrodetik. Jadi, jika m + 3 = 180, maka seluruh 180 juta kunci rahasia dapat dihitung dalam waktu kurang dari satu jam. Ketika putaran saat ini semakin mendekati r′ + 106, untuk menangani jutaan putaran berikutnya, i menghasilkan pasangan baru (PMK′, SMK′), dan menginformasikan simpanan kunci sementara berikutnya dengan —misalnya— meminta SIGi(PMK′, [r′ + 106 + 1, r′ + 2 \(\cdot\) 106 + 1]) memasukkan blok baru, baik sebagai memisahkan “transaksi” atau sebagai beberapa informasi tambahan yang merupakan bagian dari pembayaran. Dengan melakukan hal itu, saya memberi tahu semua orang bahwa dia harus menggunakan PMK′ untuk memverifikasi tanda tangan sementara saya selanjutnya juta putaran. Dan sebagainya. (Perhatikan bahwa, dengan mengikuti pendekatan dasar ini, cara lain untuk mengimplementasikan kunci sementara tanpa menggunakan tanda tangan berbasis identitas tentu saja dimungkinkan. Misalnya, melalui Merkle trees.16) 16Dalam metode ini, saya membuat pasangan kunci rahasia publik (pkr,s saya, skr, s saya ) untuk setiap pasangan langkah bulat (r, s) di —katakanlah—Cara lain untuk mengimplementasikan kunci sementara tentu saja dimungkinkan —misalnya melalui Merkle trees. 5.3 Mencocokkan Langkah Algorand′ 1 dengan BA⋆ Seperti yang kami katakan, putaran di Algorand ′ 1 memiliki paling banyak m + 3 langkah. Langkah 1. Pada langkah ini, setiap calon pemimpin i menghitung dan menyebarkan calon bloknya Br saya , bersama dengan kredensialnya sendiri, \(\sigma\)r,1 saya. Ingatlah bahwa kredensial ini secara eksplisit mengidentifikasi i. Hal ini terjadi karena \(\sigma\)r,1 saya \(\triangleq\)SIGi(r, 1, Qr−1). Pemverifikasi potensial saya juga menyebarkan, sebagai bagian dari pesannya, tanda tangan digital H(Br saya ). Tidak berurusan dengan pembayaran atau kredensial, tanda tangan i ini bersifat relatif terhadap publiknya yang fana kunci pkr,1 i : yaitu dia menyebarkan sigpkr,1 saya (H(Br saya )). Mengingat konvensi kita, daripada menyebarkan Br saya dan sigpkr,1 saya (H(Br saya )), dia bisa saja SIGpkr yang disebarkan,1 saya (H(Br saya )). Namun, dalam analisis kami, kami perlu memiliki akses eksplisit sigpkr,1 saya (H(Br saya )). Langkah 2. Pada langkah ini, setiap verifier i menetapkan \(\ell\)r saya menjadi calon pemimpin yang memiliki kredensial hash adalah yang terkecil, dan Br saya menjadi blok yang diusulkan oleh \(\ell\)r saya. Karena, demi efisiensi, kami ingin menyetujui H(Br), daripada langsung pada Br, saya menyebarkan pesan yang ingin dia sampaikan disebarkan pada langkah pertama BA⋆dengan nilai awal v′ saya = H(Br saya ). Artinya, dia menyebarkan v′ saya, tentu saja setelah menandatanganinya sebentar. (Yaitu, setelah menandatanganinya relatif terhadap fana yang tepat kunci publik yang dalam hal ini adalah pkr,2 i .) Tentu saja, saya juga mengirimkan kredensialnya sendiri. Karena langkah pertama BA⋆ terdiri dari langkah pertama protokol konsensus bertingkat GC, Langkah 2 dari Algorand ′ sesuai dengan langkah pertama GC. Langkah 3. Pada langkah ini, setiap verifier i \(\in\)SV r,2 menjalankan langkah kedua BA⋆. Artinya, dia mengirimkan pesan yang sama yang akan dia kirimkan pada langkah kedua GC. Sekali lagi, pesan saya bersifat sementara ditandatangani dan disertai dengan kredensial saya. (Mulai sekarang, kami tidak akan lagi mengatakan bahwa verifier secara singkat menandatangani pesannya dan juga menyebarkan kredensialnya.) Langkah 4. Pada langkah ini, setiap verifier i \(\in\)SV r,4 menghitung output dari GC, (vi, gi), dan secara ephemeral menandatangani dan mengirimkan pesan yang sama seperti yang akan dikirimkannya pada langkah ketiga BA⋆, yaitu di langkah pertama BBA⋆, dengan bit awal 0 jika gi = 2, dan 1 sebaliknya. Langkah s = 5, . . . , m + 2. Langkah tersebut, jika pernah tercapai, berhubungan dengan langkah s −1 dari BA⋆, dan dengan demikian menjadi langkah s −3 dari BBA⋆. Karena model propagasi kita cukup asynchronous, kita harus memperhitungkan kemungkinan tersebut bahwa, di tengah langkah s tersebut, pemverifikasi i \(\in\)SV r,s dicapai dengan informasi yang membuktikannya blok Br itu telah dipilih. Dalam hal ini, saya menghentikan eksekusinya sendiri pada putaran r Algorand ′, dan mulai menjalankan instruksi putaran-(r + 1). {R', . . . , r′ + 106} \(\times\) {1, . . . , m+3}. Kemudian dia memesan kunci publik ini dengan cara kanonik, menyimpan publik ke-j memasukkan daun ke-j dari Merkle tree, dan menghitung nilai akar Ri, yang dipublikasikannya. Ketika dia ingin menandatangani pesan relatif terhadap kunci pkr,s saya , saya tidak hanya memberikan tanda tangan sebenarnya, tetapi juga jalur otentikasi untuk pkr,s saya relatif terhadap Ri. Perhatikan bahwa jalur autentikasi ini juga membuktikan bahwa pkr,s saya disimpan di daun ke-j. Sisanya rinciannya dapat dengan mudah diisi.Oleh karena itu, instruksi dari verifier i \(\in\)SV r,s, selain instruksi yang sesuai ke Langkah s −3 dari BBA⋆, termasuk memeriksa apakah eksekusi BBA⋆telah dihentikan sebelumnya Langkah s′. Karena BBA⋆ hanya dapat berhenti pada Langkah Koin-Tetap-ke-0 atau langkah Koin-Tetap-ke-1, maka instruksi membedakan apakah A (Kondisi Akhir 0): s′ −2 ≡0 mod 3, atau B (Kondisi Akhir 1): s′ −2 ≡1 mod 3. Faktanya, dalam kasus A, blok Br tidak kosong, dan dengan demikian diperlukan instruksi tambahan untuk melakukannya memastikan bahwa saya merekonstruksi Br dengan benar, bersama dengan sertifikat CERT r yang sesuai. Dalam kasus B, blok Br kosong, sehingga i diinstruksikan untuk menyetel Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), dan untuk menghitung CERT r. Jika, selama pelaksanaan langkah s, saya tidak melihat bukti apa pun bahwa blok Br sudah ada telah dihasilkan, lalu dia mengirimkan pesan yang sama seperti yang akan dia kirimkan pada langkah s −3 dari BBA⋆. Langkah m + 3. Jika, pada langkah m + 3, i \(\in\)SV r,m+3 melihat bahwa blok Br telah dihasilkan pada langkah sebelumnya s′, maka dia melanjutkan seperti dijelaskan di atas. Jika tidak, daripada mengirim pesan yang sama yang akan dia kirimkan pada langkah m BBA⋆, i adalah diinstruksikan, berdasarkan informasi yang dimilikinya, untuk menghitung Br dan korespondennya sertifikat CERT r. Ingatlah, faktanya, kita melakukan batas atas sebesar m + 3 jumlah total langkah dalam satu putaran. 5.4 Protokol Aktual Ingatlah bahwa, pada setiap langkah s pada putaran r, pemverifikasi i \(\in\)SV r,s menggunakan pasangan kunci rahasia publik jangka panjangnya untuk menghasilkan kredensialnya, \(\sigma\)r,s saya \(\triangleq\)SIGi(r, s, Qr−1), serta SIGi Qr−1 dalam kasus s = 1. Pemverifikasi i menggunakan kunci rahasia singkatnya skr,s saya untuk menandatangani (r, s) -pesannya tuan, s saya. Untuk mempermudah, kapan r dan s adalah jelas, kami menulis esigi(x) daripada sigpkr,s i (x) untuk menunjukkan tanda tangan sementara yang tepat dari suatu nilai x pada langkah s putaran r, dan tulis ESIGi(x) sebagai ganti SIGpkr,s i (x) untuk menyatakan (i, x, esigi(x)). Langkah 1: Blokir Proposal Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 1 pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,1 atau tidak. • Jika i /\(\in\)SV r,1, maka i segera menghentikan pelaksanaan Langkah 1. • Jika i \(\in\)SV r,1, yaitu jika i adalah calon pemimpin, maka ia mengumpulkan pembayaran putaran-r yang telah telah disebarkan kepadanya sejauh ini dan menghitung pembayaran maksimal PAY r saya dari mereka. Selanjutnya, dia menghitung “blok kandidatnya” Br i = (r, BAYAR r saya , SIGi(Qr−1), H(Br−1)). Akhirnya, dia menghitung pesannya pak,1 saya = (Sdr saya , esigi(H(Br saya )), \(\sigma\)r,1 i ), menghancurkan skr kunci rahasia fana miliknya,1 saya, dan kemudian menyebarkan Tuan,1 saya.Komentar. Dalam praktiknya, untuk mempersingkat pelaksanaan global Langkah 1, penting bahwa (r, 1)- pesan disebarkan secara selektif. Artinya, untuk setiap pengguna i dalam sistem, untuk yang pertama (r, 1)- pesan yang pernah dia terima dan berhasil diverifikasi,17 pemain saya menyebarkannya seperti biasa. Untuk semua other (r, 1)-pesan yang diterima dan berhasil diverifikasi oleh pemain i, ia menyebarkannya hanya jika hash nilai kredensial yang dikandungnya adalah yang terkecil di antara hash nilai kredensial yang dikandungnya di semua (r, 1)-pesan yang dia terima dan berhasil diverifikasi sejauh ini. Selanjutnya seperti yang disarankan oleh Georgios Vlachos, akan bermanfaat jika setiap calon pemimpin i juga menyebarkan kredensialnya \(\sigma\)r,1 saya secara terpisah: pesan-pesan kecil tersebut berjalan lebih cepat daripada blok, memastikan penyebaran mr,1 secara tepat waktu j's di mana kredensial yang terkandung memiliki nilai hash yang kecil, sedangkan kredensial yang terkandung memiliki nilai hash yang besar menghilang dengan cepat. Langkah 2: Langkah Pertama dari Protokol Konsensus Bertingkat GC Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 2 pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,2 atau tidak. • Jika i /\(\in\)SV r,2 maka i menghentikan eksekusi Langkah 2 segera. • Jika i \(\in\)SV r,2, maka setelah menunggu beberapa waktu t2 \(\triangleq\) \(\lambda\) + Λ, i bertindak sebagai berikut. 1. Dia menemukan pengguna \(\ell\)sehingga H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) untuk semua kredensial \(\sigma\)r,1 j itu adalah bagian dari pesan (r, 1) yang berhasil diverifikasi yang dia terima sejauh ini.a 2. Jika dia telah menerima dari \(\ell\)pesan yang valid, Tuan,1 \(\ell\) = (Sdr \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b lalu saya set v′ i \(\triangleq\)H(Br \(\ell\)); jika tidak, saya menetapkan v′ saya \(\triangleq\) \(\bot\). 3. saya menghitung pesan mr,2 saya \(\triangleq\)(ESIGi(v′ saya), \(\sigma\)r,2 i ),c menghancurkan kunci rahasia fananya skr,2 i , dan kemudian menyebarkan mr,2 saya. aPada dasarnya, pengguna i secara pribadi memutuskan bahwa pemimpin putaran r adalah pengguna \(\ell\). bSekali lagi, tanda tangan pemain \(\ell\) dan hashes semuanya berhasil diverifikasi, dan MEMBAYAR r \(\ell\)di Br \(\ell\)adalah pembayaran yang valid untuk putaran r —walaupun saya tidak memeriksa apakah MEMBAYAR r \(\ell\)maksimal untuk \(\ell\)atau tidak. cPesan Pak,2 saya menandakan pemain yang saya anggap v′ saya menjadi hash blok berikutnya, atau mempertimbangkan blok berikutnya blok menjadi kosong. 17Artinya, semua tanda tangan sudah benar dan blok serta hash-nya valid —walaupun saya tidak memeriksanya apakah payset yang disertakan sudah maksimal bagi pengusulnya atau tidak.

Langkah 3: Langkah Kedua GC Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah ke-3 pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,3 atau tidak. • Jika i /\(\in\)SV r,3, maka i menghentikan eksekusi Langkah 3 segera. • Jika i \(\in\)SV r,3, maka setelah menunggu beberapa saat t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ, i bertindak sebagai berikut. 1. Jika terdapat nilai v′ ̸= \(\bot\)sehingga, di antara semua pesan valid mr,2 j dia telah menerima, lebih dari 2/3nya berbentuk (ESIGj(v′), \(\sigma\)r,2 j ), tanpa kontradiksi,a lalu dia menghitung pesan mr,3 saya \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 saya ). Jika tidak, dia menghitung mr,3 saya \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 saya ). 2. aku menghancurkan skr kunci rahasianya yang fana,3 i , dan kemudian menyebarkan mr,3 saya. aArtinya, dia belum menerima dua pesan valid yang masing-masing berisi ESIGj(v′) dan ESIGj(v′′) yang berbeda, dari pemain j. Di sini dan mulai sekarang, kecuali dalam Kondisi Akhir yang ditentukan nanti, kapan pun pemain jujur menginginkan pesan dalam bentuk tertentu, pesan yang bertentangan satu sama lain tidak pernah dihitung atau dianggap valid.Langkah 4: Keluaran GC dan Langkah Pertama BBA⋆ Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 4 pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,4 atau tidak. • Jika i /\(\in\)SV r,4, maka i menghentikan eksekusi Langkah 4 dengan segera. • Jika i \(\in\)SV r,4, maka setelah menunggu beberapa saat t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ, i bertindak sebagai berikut. 1. Dia menghitung vi dan gi, keluaran dari GC, sebagai berikut. (a) Jika terdapat nilai v′ ̸= \(\bot\)sehingga, di antara semua pesan valid mr,3 j dia punya diterima, lebih dari 2/3nya berbentuk (ESIGj(v′), \(\sigma\)r,3 j ), lalu dia mengatur vi \(\triangleq\)v′ dan gi \(\triangleq\)2. (b) Sebaliknya, jika terdapat nilai v′ ̸= \(\bot\)sehingga, di antara semua pesan yang valid Tuan,3 j diterimanya, lebih dari 1/3nya berbentuk (ESIGj(v′), \(\sigma\)r,3 j ), lalu dia menetapkan vi \(\triangleq\)v′ dan gi \(\triangleq\)1.a (c) Jika tidak, ia menetapkan vi \(\triangleq\)H(Br ǫ ) dan gi \(\triangleq\)0. 2. Dia menghitung bi, masukan dari BBA⋆, sebagai berikut: bi \(\triangleq\)0 jika gi = 2, dan bi \(\triangleq\)1 jika tidak. 3. Dia menghitung pesan mr,4 saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), menghancurkan kefanaannya kunci rahasia skr,4 i , dan kemudian menyebarkan mr,4 saya. aDapat dibuktikan bahwa v′ pada kasus (b), jika ada, pasti unik.

Langkah s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Langkah BBA⋆ Koin-Tetap-Ke-0 Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,s. • Jika i /\(\in\)SV r,s, maka i menghentikan eksekusi Langkah s-nya segera. • Jika i \(\in\)SV r,s maka ia bertindak sebagai berikut. – Dia menunggu hingga selang waktu ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ berlalu. – Kondisi Akhir 0: Jika, selama penantian tersebut dan pada suatu waktu tertentu, terdapat a string v ̸= \(\bot\)dan langkah s′ sedemikian rupa sehingga (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 —yaitu, Langkah s′ adalah langkah Koin-Tetap-Ke-0, (b) saya telah menerima setidaknya tH = 2n 3 + 1 pesan valid tuan,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a dan (c) Saya telah menerima pesan yang valid, Tuan,1 j = (Sdr j , esigj(H(Br j )), \(\sigma\)r,1 j ) dengan v = H(Br j ), kemudian, saya langsung menghentikan eksekusi Langkah s (dan faktanya putaran r) tanpanya menyebarkan apa pun; himpunan Br = Br j ; dan menetapkan CERT r miliknya sendiri menjadi kumpulan pesan Tuan, s′−1 j dari sub-langkah (b).b – Kondisi Akhir 1: Jika, selama penantian tersebut dan pada suatu waktu tertentu, terdapat a langkah s′ seperti itu (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 —yaitu, Langkah s′ adalah langkah Koin-Tetap-Ke-1, dan (b') saya telah menerima setidaknya pesan yang valid tuan,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c kemudian, saya langsung menghentikan eksekusi Langkah s (dan faktanya putaran r) tanpanya menyebarkan apa pun; himpunan Br = Br ; dan menetapkan CERT r miliknya sendiri menjadi kumpulan pesan Tuan, s′−1 j dari sub-langkah (b'). – Jika tidak, di akhir penantian, pengguna i akan melakukan hal berikut. Ia menetapkan vi sebagai suara terbanyak dari vj pada komponen kedua dari semua yang sah Tuan, s−1 j itu yang dia terima. Dia menghitung bi sebagai berikut. Jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)0. Lain, jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)1. Jika tidak, dia menetapkan bi \(\triangleq\)0. Dia menghitung pesan mr, s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), menghancurkan kefanaannya kunci rahasia skr,s i , dan kemudian menyebarkan mr,s saya. aPesan seperti itu dari pemain j dihitung meskipun pemain i juga menerima pesan dari j yang menandatangani untuk 1. Hal serupa untuk Kondisi Akhir 1. Seperti yang ditunjukkan dalam analisis, hal ini dilakukan untuk memastikan bahwa semua pengguna yang jujur mengetahuinya Br dalam waktu \(\lambda\) satu sama lain. pengguna saya sekarang mengetahui Br dan penyelesaian putarannya sendiri. Dia masih membantu menyebarkan pesan sebagai pengguna umum, tapi tidak memulai propagasi apa pun sebagai pemverifikasi (r, s). Secara khusus, dia telah membantu menyebarkan semua pesan di dalamnya CERT r, yang cukup untuk protokol kami. Perhatikan bahwa ia juga harus menetapkan bi \(\triangleq\)0 untuk protokol biner BA, tetapi bi tidak diperlukan dalam kasus ini. Hal serupa untuk semua instruksi di masa depan. cDalam hal ini, tidak menjadi masalah apa pun vjnya.Langkah s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Langkah BBA⋆ Koin-Tetap-Ke-1 Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,s atau tidak. • Jika i /\(\in\)SV r,s, maka i menghentikan eksekusi Langkah s-nya segera. • Jika i \(\in\)SV r,s maka ia melakukan hal berikut. – Dia menunggu hingga selang waktu ts \(\triangleq\)(2s −3)\(\lambda\) + Λ telah berlalu. – Kondisi Akhir 0: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Kondisi Akhir 1: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Jika tidak, di akhir penantian, pengguna i akan melakukan hal berikut. Ia menetapkan vi sebagai suara terbanyak dari vj pada komponen kedua dari semua yang sah Tuan, s−1 j itu yang dia terima. Dia menghitung bi sebagai berikut. Jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)0. Lain, jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)1. Jika tidak, dia menetapkan bi \(\triangleq\)1. Dia menghitung pesan mr, s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), menghancurkan kefanaannya kunci rahasia skr,s i , dan kemudian menyebarkan mr,s saya.

Langkah s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Langkah BBA⋆ yang Benar-Benar Dibalik Koin Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,s atau tidak. • Jika i /\(\in\)SV r,s, maka i menghentikan eksekusi Langkah s-nya segera. • Jika i \(\in\)SV r,s maka ia melakukan hal berikut. – Dia menunggu hingga selang waktu ts \(\triangleq\)(2s −3)\(\lambda\) + Λ telah berlalu. – Kondisi Akhir 0: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Kondisi Akhir 1: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Jika tidak, di akhir penantian, pengguna i akan melakukan hal berikut. Ia menetapkan vi sebagai suara terbanyak dari vj pada komponen kedua dari semua yang sah Tuan, s−1 j itu yang dia terima. Dia menghitung bi sebagai berikut. Jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)0. Lain, jika lebih dari 2/3 dari seluruh mr,s−1 yang valid j yang dia terima adalah dalam bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia menetapkan bi \(\triangleq\)1. Jika tidak, misalkan SV r,s−1 saya menjadi himpunan (r, s −1)-pengukur yang darinya ia menerima valid pesan tuan, s−1 j . Dia menetapkan bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 saya H(\(\sigma\)r,s−1 j )). Dia menghitung pesan mr, s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), menghancurkan kefanaannya kunci rahasia skr,s i , dan kemudian menyebarkan mr,s saya.

Langkah m + 3: Langkah Terakhir BBA⋆a Petunjuk untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri m + 3 putaran r segera setelah dia tahu Br−1. • Pengguna i menghitung Qr−1 dari komponen ketiga Br−1 dan memeriksa apakah i \(\in\)SV r,m+3 atau tidak. • Jika i /\(\in\)SV r,m+3, maka i menghentikan eksekusi Langkah m + 3 segera. • Jika i \(\in\)SV r,m+3 maka ia melakukan hal berikut. – Dia menunggu sampai selang waktu tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ telah berlalu. – Kondisi Akhir 0: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Kondisi Akhir 1: Instruksi yang sama seperti langkah Coin-Fixed-To-0. – Jika tidak, di akhir penantian, pengguna i akan melakukan hal berikut. Dia menetapkan outi \(\triangleq\)1 dan Br \(\triangleq\)Br . Dia menghitung pesan mr,m+3 saya = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 saya ), menghancurkan miliknya kunci rahasia sementara skr,m+3 saya , dan kemudian menyebarkan mr,m+3 saya untuk mensertifikasi Br.b aDengan kemungkinan besar BBA⋆telah berakhir sebelum langkah ini, dan kami menetapkan langkah ini sebagai penyelesaian. sertifikat bA dari Langkah m + 3 tidak harus menyertakan ESIGi(outi). Kami menyertakannya untuk keseragaman saja: the sertifikat kini memiliki format yang seragam, apa pun langkah pembuatannya.Rekonstruksi Blok Round-r oleh Non-Verifiers Petunjuk untuk setiap pengguna i dalam sistem: Pengguna i memulai putarannya sendiri r segera setelah dia mengetahuinya Br−1, dan tunggu informasi blok sebagai berikut. – Jika, selama penantian tersebut dan pada suatu waktu tertentu, terdapat string v dan langkah s′ seperti itu itu (a) 5 \(\leq\)s′ \(\leq\)m + 3 dengan s′ −2 ≡0 mod 3, (b) saya telah menerima setidaknya pesan yang valid tuan,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ), dan (c) Saya telah menerima pesan yang valid, Tuan,1 j = (Sdr j , esigj(H(Br j )), \(\sigma\)r,1 j ) dengan v = H(Br j ), kemudian, saya segera menghentikan eksekusi putaran r-nya sendiri; himpunan Br = Br j; dan menetapkan CERT r-nya sendiri menjadi himpunan pesan mr,s′−1 j dari sub-langkah (b). – Jika, selama penantian tersebut dan pada suatu waktu tertentu, terdapat langkah s′ sedemikian rupa sehingga (a’) 6 \(\leq\)s′ \(\leq\)m + 3 dengan s′ −2 ≡1 mod 3, dan (b') saya telah menerima setidaknya pesan yang valid tuan,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), kemudian, saya segera menghentikan eksekusi putaran r-nya sendiri; himpunan Br = Br ; dan menetapkan CERT r-nya sendiri menjadi himpunan pesan mr,s′−1 j dari sub-langkah (b'). – Jika, selama penantian tersebut dan pada suatu waktu, saya telah menerima setidaknya pesan yang valid Tuan, m+3 j = (ESIGj(1), ESIGj(H(Br ǫ )), \(\sigma\)r,m+3 j ), lalu saya menghentikan eksekusinya sendiri pada putaran r segera, himpunan Br = Br ǫ , dan menetapkan CERT r miliknya sendiri menjadi kumpulan pesan mr,m+3 j untuk 1 dan H(Br ). 5.5 Analisis Algorand′ 1 Kami memperkenalkan notasi berikut untuk setiap putaran r \(\geq\)0, yang digunakan dalam analisis. • Misalkan T r adalah waktu ketika pengguna pertama yang jujur ​​mengetahui Br−1. • Misalkan Ir+1 adalah interval [T r+1, T r+1 + \(\lambda\)]. Perhatikan bahwa T 0 = 0 dengan inisialisasi protokol. Untuk setiap s \(\geq\)1 dan i \(\in\)SV r,s, ingat kembali hal tersebut \(\alpha\)r,s saya dan \(\beta\)r,s saya masing-masing adalah waktu mulai dan waktu berakhirnya langkah pemain i. Selain itu, ingat bahwa ts = (2s −3)\(\lambda\) + Λ untuk setiap 2 \(\leq\)s \(\leq\)m + 3. Sebagai tambahan, misalkan I0 \(\triangleq\){0} dan t1 \(\triangleq\)0. Terakhir, ingatlah bahwa Lr \(\leq\)m/3 adalah variabel acak yang mewakili jumlah percobaan Bernoulli diperlukan untuk melihat angka 1, ketika setiap percobaan adalah 1 dengan probabilitas ph 2 dan paling banyak terdapat m/3 percobaan. Jika semua uji coba gagal maka Lr \(\triangleq\)m/3. Dalam analisis kami mengabaikan waktu komputasi, karena pada kenyataannya waktu tersebut dapat diabaikan dibandingkan dengan waktu yang dibutuhkan untuk menyebarkan pesan. Bagaimanapun, dengan menggunakan \(\lambda\) dan Λ yang sedikit lebih besar, waktu komputasi bisa dimasukkan ke dalam analisis secara langsung. Sebagian besar pernyataan di bawah ini menyatakan “dengan luar biasa probabilitasnya,” dan kami mungkin tidak berulang kali menekankan fakta ini dalam analisis.5.6 Teorema Utama Teorema 5.1. Properti berikut ini memiliki probabilitas yang sangat besar untuk setiap putaran r \(\geq\)0: 1. Semua pengguna yang jujur menyetujui blok yang sama Br. 2. Ketika pemimpin \(\ell\)r jujur, blok Br dihasilkan oleh \(\ell\)r, Br berisi payset maksimal diterima oleh \(\ell\)r pada waktu \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br pada waktunya interval Ir+1. 3. Ketika pemimpin \(\ell\)r jahat, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br dalam selang waktu Ir+1. 4. ph = h2(1 + h −h2) untuk Lr, dan pemimpin \(\ell\)r jujur ​​dengan probabilitas paling sedikit ph. Sebelum membuktikan teorema utama kita, mari kita buat dua catatan. Perkataan. • Pembuatan Blok dan Latensi Sejati. Waktu untuk membangkitkan blok Br didefinisikan sebagai T r+1 −T r. Artinya, ini didefinisikan sebagai perbedaan antara pertama kali beberapa pengguna yang jujur mempelajari Br dan pertama kalinya beberapa pengguna yang jujur mempelajari Br−1. Ketika pemimpin putaran-r jujur, Properti 2 milik kita teorema utama menjamin bahwa waktu yang tepat untuk menghasilkan Br adalah waktu 8\(\lambda\) + Λ, tidak peduli berapa pun nilai yang tepat dari h > 2/3 mungkin. Ketika pemimpinnya jahat, Properti 3 menyiratkan bahwa waktu yang diharapkan untuk menghasilkan Br dibatasi oleh ( 12 ph + 10)\(\lambda\) + Λ, sekali lagi tidak peduli berapa tepatnya nilai h.18 Namun, waktu yang diharapkan untuk menghasilkan Br bergantung pada nilai h yang tepat. Memang benar, berdasarkan Sifat 4, ph = h2(1 + h −h2) dan pemimpinnya jujur dengan probabilitas paling sedikit ph, dengan demikian E[T r+1 −T r] \(\leq\)h2(1 + h −h2) \(\cdot\) (8\(\lambda\) + Λ) + (1 −h2(1 + h −h2))(( 12 h2(1 + h −h2) + 10)\(\lambda\) + Λ). Misalnya, jika h = 80%, maka E[T r+1 −T r] \(\leq\)12.7\(\lambda\) + Λ. • \(\lambda\) vs. Λ. Perhatikan bahwa ukuran pesan yang dikirim oleh verifikasi pada langkah Algorand ′ didominasi berdasarkan panjang kunci tanda tangan digital, yang dapat tetap, meskipun jumlahnya pengguna sangatlah besar. Perhatikan juga bahwa, pada setiap langkah s > 1, jumlah n verifikator yang diharapkan sama dapat digunakan apakah jumlah penggunanya 100K, 100M, atau 100M. Hal ini terjadi karena n semata-mata bergantung pada h dan F. Oleh karena itu, kecuali ada kebutuhan mendadak untuk menambah panjang kunci rahasia, nilai \(\lambda\) harus tetap sama tidak peduli seberapa besar jumlah pengguna di dalamnya masa depan yang dapat diperkirakan. Sebaliknya, untuk tingkat transaksi apa pun, jumlah transaksi bertambah seiring dengan jumlah pengguna. Oleh karena itu, untuk memproses semua transaksi baru secara tepat waktu, ukuran satu blok harus tepat juga bertambah seiring dengan jumlah pengguna, menyebabkan Λ pun bertambah. Jadi, dalam jangka panjang, kita harus melakukannya \(\lambda\) << Λ. Oleh karena itu, wajar jika memiliki koefisien yang lebih besar untuk \(\lambda\), dan sebenarnya koefisien dari 1 untuk Λ. Bukti Teorema 5.1. Kami membuktikan Properti 1–3 dengan induksi: dengan asumsi properti tersebut berlaku untuk putaran r −1 (tanpa kehilangan keumumannya, mereka secara otomatis berlaku untuk “putaran -1” ketika r = 0), kami membuktikannya putaran r. 18Memang benar, E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Karena Br−1 didefinisikan secara unik oleh hipotesis induktif, himpunan SV r,s didefinisikan secara unik untuk setiap langkah s pada putaran r. Dengan pilihan n1, SV r,1 ̸= \(\emptyset\)dengan probabilitas yang sangat besar. Kami sekarang nyatakan dua lemma berikut, dibuktikan dalam Bagian 5.7 dan 5.8. Sepanjang induksi dan masuk pembuktian kedua lemma, analisa putaran 0 hampir sama dengan langkah induktif, dan kami akan menyoroti perbedaannya ketika hal itu terjadi. Lemma 5.2. [Lemma Kelengkapan] Dengan Asumsi Properti 1–3 berlaku untuk ronde r−1, saat menjadi pemimpin \(\ell\)r jujur, dengan kemungkinan yang sangat besar, • Semua pengguna yang jujur menyetujui blok Br yang sama, yang dihasilkan oleh \(\ell\)r dan berisi maksimal payset diterima oleh \(\ell\)r pada waktu \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; dan • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br pada interval waktu Ir+1. Lemma 5.3. [Lemma Kesehatan] Dengan Asumsi Properti 1–3 berlaku untuk ronde r −1, saat menjadi pemimpin \(\ell\)r berbahaya, dengan kemungkinan besar, semua pengguna jujur menyetujui blok yang sama Br, T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br dalam interval waktu Ir+1. Sifat 1–3 berlaku dengan menerapkan Lemmas 5.2 dan 5.3 pada r = 0 dan pada langkah induktif. Akhirnya, kami menyatakan kembali Properti 4 sebagai lemma berikut, dibuktikan di Bagian 5.9. Lemma 5.4. Sifat yang diberikan 1–3 untuk setiap putaran sebelum r, ph = h2(1 + h −h2) untuk Lr, dan pemimpin \(\ell\)r jujur dengan probabilitas setidaknya ph. Dengan menggabungkan ketiga lemma di atas, Teorema 5.1 berlaku. ■ Lemma di bawah menyatakan beberapa sifat penting tentang putaran r mengingat induktifnya hipotesis, dan akan digunakan dalam pembuktian ketiga lemma di atas. Lemma 5.5. Asumsikan Properti 1–3 berlaku untuk putaran r −1. Untuk setiap langkah s \(\geq\)1 putaran r dan setiap pemverifikasi jujur saya \(\in\)HSV r,s, kami punya itu (a) \(\alpha\)r,s saya \(\in\)Ir; (b) jika pemain i telah menunggu selama beberapa waktu ts, maka \(\beta\)r,s saya \(\in\)[T r + ts, T r + \(\lambda\) + ts] untuk r > 0 dan \(\beta\)r, s saya = ts untuk r = 0; dan (c) jika pemain i telah menunggu selama beberapa waktu ts, maka dalam waktu \(\beta\)r,s i, dia telah menerima semua pesan dikirim oleh semua verifikator yang jujur j \(\in\)HSV r,s′ untuk semua langkah s′ < s. Selain itu, untuk setiap langkah s \(\geq\)3, kita memilikinya (d) tidak terdapat dua pemain berbeda i, i′ \(\in\)SV r,s dan dua nilai berbeda v, v′ yang sama panjangnya, sehingga kedua pemain telah menunggu sejumlah waktu ts, lebih dari 2/3 dari keseluruhan waktu pesan yang valid tuan,s−1 j pemain yang saya terima telah menandatangani v, dan lebih dari 2/3 dari semuanya valid pesan tuan, s−1 j pemain yang saya terima telah menandatangani v ′. Bukti. Properti (a) mengikuti langsung hipotesis induktif, karena pemain i mengetahui Br−1 di interval waktu Ir dan segera memulai langkahnya sendiri. Properti (b) mengikuti langsung dari (a): sejak pemain saya telah menunggu beberapa saat sebelum bertindak, \(\beta\)r,s saya = \(\alpha\)r,s saya + ts. Perhatikan bahwa \(\alpha\)r,s saya = 0 untuk r = 0. Sekarang kita buktikan Properti (c). Jika s = 2, maka berdasarkan Properti (b), untuk semua verifikasi j \(\in\)HSV r,1 kita punya \(\beta\)r, s saya = \(\alpha\)r,s saya + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j + Λ.Karena setiap verifier j \(\in\)HSV r,1 mengirimkan pesannya pada waktu \(\beta\)r,1 j dan pesannya sampai kepada semua orang dengan jujur pengguna paling banyak dalam waktu Λ, dalam waktu \(\beta\)r,s saya pemain saya telah menerima pesan yang dikirim oleh semua verifikator masuk HSV r,1 sesuai keinginan. Jika s > 2, maka ts = ts−1 + 2\(\lambda\). Berdasarkan Properti (b), untuk semua langkah s′ < s dan semua verifikasi j \(\in\)HSV r,s′, \(\beta\)r, s saya = \(\alpha\)r,s saya + ts \(\geq\)T r + ts = T r + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = T r + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ j + \(\lambda\). Karena setiap verifier j \(\in\)HSV r,s′ mengirimkan pesannya pada waktu \(\beta\)r,s′ j dan pesannya sampai kepada semua orang dengan jujur pengguna paling banyak dalam waktu \(\lambda\), dalam waktu \(\beta\)r,s saya pemain saya telah menerima semua pesan yang dikirim oleh semua verifikasi yang jujur dalam HSV r,s′ untuk semua s′ < s. Dengan demikian Properti (c) berlaku. Terakhir, kita buktikan Properti (d). Perhatikan bahwa verifikator j \(\in\)SV r,s−1 menandatangani paling banyak dua hal Langkah s −1 menggunakan kunci rahasia sementaranya: nilai vj yang panjangnya sama dengan keluaran dari fungsi hash, dan juga sedikit bj \(\in\){0, 1} jika s −1 \(\geq\)4. Itu sebabnya dalam pernyataan lemma kita mengharuskan v dan v′ memiliki panjang yang sama: banyak verifier yang mungkin telah menandatangani kedua nilai hash v dan sedikit b, sehingga keduanya melewati ambang batas 2/3. Asumsikan demi kontradiksi bahwa terdapat verifier i, i′ dan nilai v, v′ yang diinginkan. Perhatikan bahwa beberapa pengverifikasi jahat di MSV r,s−1 mungkin telah menandatangani v dan v′, tetapi masing-masing verifikasi jujur pemverifikasi di HSV r,s−1 telah menandatangani paling banyak salah satunya. Berdasarkan Sifat (c), baik i maupun i′ telah diterima semua pesan yang dikirim oleh semua verifikator yang jujur di HSV r,s−1. Misalkan HSV r,s−1(v) adalah himpunan verifikator jujur (r, s −1) yang telah menandatangani v, MSV r,s−1 saya set dari pemverifikasi jahat (r, s −1) yang darinya saya telah menerima pesan yang valid, dan MSV r,s−1 saya (v) itu bagian dari MSV r,s−1 saya dari siapa saya menerima pesan yang sah penandatanganan v. Dengan persyaratan untuk aku dan v, kita punya rasio \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 saya (v)| |HSV r,s−1| + |MSV r,s−1 saya |

2 3. (1) Kami tampilkan dulu |MSV r,s−1 saya (v)| \(\leq\)|HSV r,s−1(v)|. (2) Dengan asumsi sebaliknya, berdasarkan hubungan antar parameter, dengan kemungkinan yang sangat besar |HSV r,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 saya |, dengan demikian rasio < |HSV r,s−1(v)| + |MSV r,s−1 saya (v)| 3|MSV r,s−1 saya | < 2|MSV r,s−1 saya (v)| 3|MSV r,s−1 saya | \(\leq\)2 3, bertentangan dengan Ketimpangan 1. Selanjutnya, dengan Pertidaksamaan 1 yang kita dapatkan 2|HSV r,s−1| + 2|MSV r,s−1 saya | < 3|HSV r,s−1(v)| + 3|MSV r,s−1 saya (v)| \(\leq\) 3|HSV r,s−1(v)| + 2|MSV r,s−1 saya | + |MSV r,s−1 saya (v)|. Dikombinasikan dengan Ketimpangan 2, 2|HSV r,s−1| < 3|HSV r,s−1(v)| + |MSV r,s−1 saya (v)| \(\leq\)4|HSV r,s−1(v)|, yang menyiratkan |HSV r,s−1(v)| > 1 2|HSV r,s−1|.Demikian pula, dengan persyaratan untuk i′ dan v′, kita punya |HSV r,s−1(v′)| > 1 2|HSV r,s−1|. Karena pemverifikasi yang jujur j \(\in\)HSV r,s−1 menghancurkan kunci rahasia sementaranya skr,s−1 j sebelum disebarkan pesannya, Musuh tidak dapat memalsukan tanda tangan j untuk nilai yang tidak ditandatangani oleh j setelahnya mengetahui bahwa j adalah pemverifikasi. Jadi, kedua pertidaksamaan di atas menyiratkan |HSV r,s−1| \(\geq\)|HSV r,s−1(v)| + |HSV r,s−1(v′)| > |HSV r,s−1|, sebuah kontradiksi. Oleh karena itu, i, i′, v, v′ yang diinginkan tidak ada, dan Properti (d) dimiliki. ■ 5.7 Kelengkapan Lemma Lemma 5.2. [Lemma Kelengkapan, dinyatakan kembali] Dengan asumsi Properti 1–3 berlaku untuk putaran r−1, kapan pemimpinnya jujur, dengan kemungkinan besar, • Semua pengguna yang jujur menyetujui blok Br yang sama, yang dihasilkan oleh \(\ell\)r dan berisi maksimal payset diterima oleh \(\ell\)r pada waktu \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; dan • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br pada interval waktu Ir+1. Bukti. Berdasarkan hipotesis induktif dan Lemma 5.5, untuk setiap langkah s dan pemverifikasi i \(\in\)HSV r,s, \(\alpha\)r,s saya \(\in\)Ir. Di bawah ini kami menganalisis protokol langkah demi langkah. Langkah 1. Berdasarkan definisinya, setiap pemverifikasi yang jujur i \(\in\)HSV r,1 menyebarkan pesan yang diinginkan mr,1 saya di waktu \(\beta\)r,1 saya = \(\alpha\)r,1 saya , dimana tuan,1 saya = (Sdr saya , esigi(H(Br saya )), \(\sigma\)r,1 saya ), Sdr i = (r, BAYAR r saya , SIGi(Qr−1), H(Br−1)), dan MEMBAYAR r i adalah pembayaran maksimal di antara semua pembayaran yang telah saya lihat pada waktu \(\alpha\)r,1 saya. Langkah 2. Perbaiki secara sewenang-wenang pemverifikasi yang jujur i \(\in\)HSV r,2. Oleh Lemma 5.5, ketika pemain i selesai menunggu pada waktu \(\beta\)r,2 saya = \(\alpha\)r,2 saya + t2, dia telah menerima semua pesan yang dikirim oleh verifikator di HSV r,1, termasuk Tuan, 1 \(\ell\)r. Berdasarkan definisi \(\ell\)r, tidak ada pemain lain di PKr−k yang kredensialnya hash nilainya lebih kecil dari H(\(\sigma\)r,1 \(\ell\)r ). Tentu saja Musuh dapat merusak \(\ell\)r setelah melihat H(\(\sigma\)r,1 \(\ell\)r ) sangat kecil, tetapi pada saat itu pemain \(\ell\)r telah menghancurkan kunci sementaranya dan pesan mr,1 \(\ell\)r telah disebarkan. Jadi pemverifikasi saya menetapkan pemimpinnya sendiri menjadi pemain \(\ell\)r. Oleh karena itu, pada waktu \(\beta\)r,2 saya , pemverifikasi saya menyebarkan Pak,2 saya = (ESIGi(v′ saya), \(\sigma\)r,2 saya ), di mana v′ saya = H(Br \(\ell\)r). Ketika r = 0, satu-satunya perbedaan apakah itu \(\beta\)r,2 saya = t2 daripada berada dalam jangkauan. Hal serupa dapat dikatakan untuk langkah-langkah masa depan dan kita tidak akan menekankannya lagi. Langkah 3. Sewenang-wenang memperbaiki pemverifikasi yang jujur i \(\in\)HSV r,3. Oleh Lemma 5.5, ketika pemain i selesai menunggu pada waktu \(\beta\)r,3 saya = \(\alpha\)r,3 saya + t3, dia telah menerima semua pesan yang dikirim oleh verifikator di HSV r,2. Berdasarkan hubungan antar parameter, dengan probabilitas yang sangat besar |HSV r,2| > 2|MSV r,2|. Selain itu, tidak ada verifikasi yang jujur yang akan menandatangani pesan-pesan yang bertentangan, dan Musuh tidak dapat memalsukan tanda tangan pemeriksa yang jujur setelah pemeriksa tersebut memusnahkan tanda tangannya kunci rahasia sementara. Jadi lebih dari 2/3 dari semua pesan valid (r, 2) yang saya terima berasal dari verifikator yang jujur dan dalam bentuk Tuan,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), tanpa kontradiksi. Oleh karena itu, pada waktu \(\beta\)r,3 saya pemain saya menyebarkan mr,3 saya = (ESIGi(v′), \(\sigma\)r,3 saya ), dimana v′ = H(Br \(\ell\)r).Langkah 4. Memperbaiki secara sewenang-wenang pemverifikasi yang jujur i \(\in\)HSV r,4. Dengan Lemma 5.5, pemain saya telah menerima semuanya pesan yang dikirim oleh verifikator di HSV r,3 setelah selesai menunggu pada waktu \(\beta\)r,4 saya = \(\alpha\)r,4 saya + t4. Mirip dengan Langkah 3, lebih dari 2/3 dari semua pesan valid (r, 3) yang saya terima berasal dari verifikator yang jujur dan dari bentuk tuan,3 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j ). Oleh karena itu, pemain i menetapkan vi = H(Br \(\ell\)r), gi = 2 dan bi = 0. Pada waktu \(\beta\)r,4 saya = \(\alpha\)r,4 saya +t4 dia menyebar Tuan, 4 saya = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 saya ). Langkah 5. Perbaiki secara sewenang-wenang pemverifikasi yang jujur i \(\in\)HSV r,5. Dengan Lemma 5.5, pemain yang saya inginkan menerima semua pesan yang dikirim oleh verifikator di HSV r,4 jika dia menunggu sampai waktu \(\alpha\)r,5 saya + t5. Perhatikan itu |HSV r,4| \(\geq\)tH.19 Perhatikan juga bahwa semua verifikator di HSV r,4 telah menandatangani H(Br \(\ell\)r). Sebagai |MSV r,4| < tH, tidak ada v′ ̸= H(Br \(\ell\)r) yang bisa saja ditandatangani oleh tH pemverifikasi di SV r,4 (yang tentu saja jahat), jadi pemain i tidak berhenti sebelum dia melakukannya menerima pesan yang valid, Tuan, 4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j ). Biarkan T menjadi waktu kapan peristiwa terakhir terjadi. Beberapa pesan tersebut mungkin berasal dari pemain jahat, tetapi karena |MSV r,4| < tH, setidaknya salah satunya berasal dari verifikator yang jujur di HSV r,4 dan dikirim setelah waktu tertentu T r + t4. Oleh karena itu, T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, dan pada saat T pemain saya juga telah menerimanya pesannya pak,1 \(\ell\)r. Dengan konstruksi protokol, pemain i berhenti pada waktu \(\beta\)r,5 saya = T tanpa menyebarkan apa pun; himpunan Br = Br \(\ell\)r; dan menetapkan CERT r miliknya sendiri menjadi himpunan (r, 4)-pesan untuk 0 dan H(Br \(\ell\)r) yang diterimanya. Langkah s > 5. Demikian pula, untuk setiap langkah s > 5 dan setiap pemverifikasi i \(\in\)HSV r,s, pemain i akan memiliki menerima semua pesan yang dikirim oleh verifikator di HSV r,4 jika dia telah menunggu hingga waktu \(\alpha\)r,s saya + ts. Oleh analisa yang sama, pemain i berhenti tanpa menyebarkan apapun, setting Br = Br \(\ell\)r (dan mengatur sendiri CERT r dengan benar). Tentu saja, pemverifikasi jahat tidak boleh berhenti dan dapat menyebar secara sewenang-wenang pesan, tetapi karena |MSV r,s| < tH, dengan induksi tidak ada v′ lain yang dapat ditandatangani oleh pemeriksa tersebut pada setiap langkah 4 \(\leq\)s′ < s, sehingga verifikator yang jujur hanya berhenti karena mereka telah menerima validitas (r, 4)-pesan untuk 0 dan H(Br \(\ell\)r). Rekonstruksi Blok Round-r. Analisis pada Langkah 5 berlaku untuk kejujuran umum pengguna saya hampir tanpa perubahan apa pun. Memang, pemain i memulai putarannya sendiri r pada interval Ir dan hanya akan berhenti pada waktu T ketika dia telah menerima pesan (r, 4) yang valid untuk H(Br \(\ell\)r). Sekali lagi karena setidaknya satu dari pesan tersebut berasal dari verifikasi yang jujur dan dikirim setelah waktu T r + t4, pemain i punya juga menerima Tuan, 1 \(\ell\)r dengan waktu T. Jadi dia menetapkan Br = Br \(\ell\)r dengan CERT yang tepat r. Yang tersisa hanyalah menunjukkan bahwa semua pengguna yang jujur ​​menyelesaikan putarannya r dalam interval waktu Ir+1. Berdasarkan analisis pada Langkah 5, setiap verifier yang jujur i \(\in\)HSV r,5 mengetahui Br pada atau sebelum \(\alpha\)r,5 saya + t5 \(\leq\) T r + \(\lambda\) + t5 = T r + 8\(\lambda\) + Λ. Karena T r+1 adalah waktu ketika pengguna pertama yang jujur mengetahui Br, maka kita mengetahuinya T r+1 \(\leq\)T r + 8\(\lambda\) + Λ sesuai keinginan. Apalagi ketika pemain mengenal Br, dia sudah membantu menyebarkan pesan-pesan yang masuk CERT-nya r. Perhatikan bahwa semua pesan tersebut akan diterima oleh semua pengguna yang jujur dalam waktu \(\lambda\), meskipun 19Sebenarnya, hal ini terjadi dengan probabilitas yang sangat tinggi namun tidak terlalu besar. Namun, ini probabilitas sedikit mempengaruhi waktu berjalannya protokol, namun tidak mempengaruhi kebenarannya. Bila h = 80%, maka |HSV r,4| \(\geq\)tH dengan probabilitas 1 −10−8. Jika peristiwa ini tidak terjadi, maka protokol akan dilanjutkan ke peristiwa lain 3 langkah. Karena kemungkinan hal ini tidak terjadi pada dua langkah dapat diabaikan, maka protokol akan selesai pada Langkah 8. Dalam ekspektasinya, maka jumlah langkah yang dibutuhkan hampir 5.pemain saya adalah pemain pertama yang menyebarkannya. Apalagi berikut analisa diatas yang kami miliki T r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, jadi semua pengguna jujur telah menerima mr,1 \(\ell\)r menurut waktu T r+1 + \(\lambda\). Oleh karena itu, semua pengguna yang jujur mengetahui Br dalam selang waktu Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Terakhir, untuk r = 0 sebenarnya kita mempunyai T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ. Menggabungkan semuanya bersama-sama, Lemma 5.2 berlaku. ■ 5.8 Lemma Kesehatan Lemma 5.3. [Lemma Kesehatan, dinyatakan kembali] Dengan asumsi Properti 1–3 berlaku untuk putaran r −1, kapan pemimpin \(\ell\)r jahat, dengan kemungkinan besar, semua pengguna jujur ​​setuju pada blok yang sama Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ dan semua pengguna yang jujur mengetahui Br dalam selang waktu Ir+1. Bukti. Kami mempertimbangkan dua bagian protokol, GC dan BBA⋆, secara terpisah. hal. Berdasarkan hipotesis induktif dan Lemma 5.5, untuk setiap langkah s \(\in\){2, 3, 4} dan setiap langkah jujur pemverifikasi i \(\in\)HSV r,s, ketika pemain i bertindak pada waktu \(\beta\)r,s saya = \(\alpha\)r,s saya + ts, dia telah menerima semua pesan yang dikirim oleh semua pemverifikasi yang jujur pada langkah s′ < s. Kami membedakan dua kemungkinan kasus untuk langkah 4. Kasus 1. Tidak ada pemverifikasi i \(\in\)HSV r,4 menetapkan gi = 2. Dalam hal ini, menurut definisi bi = 1 untuk semua verifier i \(\in\)HSV r,4. Artinya, mereka memulai dengan kesepakatan pada 1 dalam protokol BA biner. Mereka mungkin tidak memiliki kesepakatan mengenai vi mereka, tapi ini tidak masalah seperti yang akan kita lihat di BA biner. Kasus 2. Terdapat pemverifikasi ˆi \(\in\)HSV r,4 sehingga gˆi = 2. Dalam hal ini, kami menunjukkan hal itu (1) gi \(\geq\)1 untuk semua i \(\in\)HSV r,4, (2) terdapat nilai v′ sehingga vi = v′ untuk semua i \(\in\)HSV r,4, dan (3) ada pesan yang valid mr,1 \(\ell\) dari beberapa pemverifikasi \(\ell\) \(\in\)SV r,1 sehingga v′ = H(Br \(\ell\)). Memang benar, karena pemain ˆi jujur dan menetapkan gˆi = 2, lebih dari 2/3 dari semua pesan valid mr,3 j yang dia terima adalah untuk nilai yang sama v′ ̸= \(\bot\), dan dia telah menetapkan vˆi = v′. Berdasarkan Sifat (d) dalam Lemma 5.5, untuk pemverifikasi i lainnya yang jujur (r, 4), tidak lebih dari itu. dari 2/3 dari semua pesan valid mr,3 j yang i′ terima bernilai sama v′′ ̸= v′. Oleh karena itu, jika saya menetapkan gi = 2, maka haruslah saya telah melihat > 2/3 mayoritas untuk v′ juga dan menetapkan vi = v′, sesuai keinginan. Sekarang pertimbangkan pemverifikasi sembarang i \(\in\)HSV r,4 dengan gi < 2. Mirip dengan analisis Properti (d) pada Lemma 5.5, karena pemain i telah memperoleh > 2/3 mayoritas untuk v′, lebih dari 1 2|HSV r,3| jujur (r, 3)-penguji telah menandatangani v′. Karena saya telah menerima semua pesan dari verifikasi yang jujur (r, 3). waktu \(\beta\)r,4 saya = \(\alpha\)r,4 saya + t4, dia secara khusus menerima lebih dari 1 2|HSV r,3| pesan dari mereka untuk v′. Karena |HSV r,3| > 2|MSV r,3|, saya telah melihat > ​​1/3 mayoritas untuk v′. Oleh karena itu, pemain i menetapkan gi = 1, dan Properti (1) berlaku. Apakah pemain i harus menyetel vi = v′? Asumsikan terdapat nilai yang berbeda v′′ ̸= \(\bot\)sehingga pemain yang saya juga lihat > 1/3 mayoritas untuk v′′. Beberapa dari pesan tersebut mungkin berasal dari pesan jahat penguji, tapi paling tidak salah satu dari mereka berasal dari penguji yang jujur j \(\in\)HSV r,3: tentu saja, karena |HSV r,3| > 2|MSV r,3| dan saya telah menerima semua pesan dari HSV r,3, kumpulan berbahaya pemverifikasi yang darinya saya menerima pesan valid (r, 3) dihitung < 1/3 dari semua pesan valid pesan yang dia terima.Berdasarkan definisi, pemain j harus melihat > 2/3 mayoritas untuk v′′ di antara semua pesan (r, 2) yang valid dia telah menerima. Namun, kami sudah mengetahui hal yang telah dilihat oleh beberapa pengverifikasi (r, 3) yang jujur 2/3 mayoritas untuk v′ (karena mereka menandatangani v′). Berdasarkan Sifat (d) Lemma 5.5, hal ini tidak bisa terjadi dan nilai v′′ seperti itu tidak ada. Jadi pemain i harus mengatur vi = v′ sesuai keinginan, dan Properti (2) dimiliki. Akhirnya, mengingat bahwa beberapa pengverifikasi (r, 3) yang jujur telah mendapatkan > 2/3 mayoritas untuk v′, beberapa (sebenarnya, lebih dari separuh) verifikator yang jujur (r, 2) telah menandatangani v′ dan menyebarkan pesan-pesan mereka. Dengan dibangunnya protokol tersebut, para verifikator yang jujur (r, 2) harus sudah mendapatkan surat keterangan yang sah pesan Pak, 1 \(\ell\) dari beberapa pemain \(\ell\) \(\in\)SV r,1 dengan v′ = H(Br \(\ell\)), dengan demikian Properti (3) berlaku. BBA⋆. Kami sekali lagi membedakan dua kasus. Kasus 1. Semua verifikator i \(\in\)HSV r,4 mempunyai bi = 1. Hal ini terjadi setelah Kasus 1 GC. Sebagai |MSV r,4| < tH, dalam hal ini tidak ada verifier di SV r,5 dapat mengumpulkan atau menghasilkan pesan yang valid (r, 4) untuk bit 0. Dengan demikian, tidak ada pemverifikasi yang jujur di HSV r,5 akan berhenti karena mengetahui blok yang tidak kosong Br. Selain itu, meskipun setidaknya ada pesan (r, 4) yang valid untuk bit 1, s′ = 5 tidak memuaskan s′ −2 ≡1 mod 3, sehingga tidak ada verifikator yang jujur di HSV r,5 yang akan berhenti karena dia mengetahui Br = Br . Sebaliknya, setiap pemverifikasi i \(\in\)HSV r,5 bertindak pada waktu \(\beta\)r,5 saya = \(\alpha\)r,5 saya + t5, saat dia telah menerima semuanya pesan yang dikirim oleh HSV r,4 mengikuti Lemma 5.5. Jadi pemain yang saya lihat > 2/3 mayoritas untuk 1 dan himpunan bi = 1. Pada Langkah 6 yang merupakan langkah Koin-Tetap-Ke-1, meskipun s′ = 5 memenuhi s′ −2 ≡0 mod 3, terdapat tidak ada pesan (r, 4) yang valid untuk bit 0, sehingga tidak ada pemverifikasi di HSV r,6 yang akan berhenti karena dia mengetahui blok yang tidak kosong Br. Namun, dengan s′ = 6, s′ −2 ≡1 mod 3 dan memang ada |HSV r,5| \(\geq\)tH valid (r, 5)-pesan untuk bit 1 dari HSV r,5. Untuk setiap verifier i \(\in\)HSV r,6, mengikuti Lemma 5.5, pada atau sebelum waktu \(\alpha\)r,6 saya + pemain t6 i telah menerima semua pesan dari HSV r,5, jadi saya berhenti tanpa menyebarkan apa pun dan menyetel Br = Br . CERT r-nya adalah kumpulan pesan (r, 5) yang valid mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j ) diterima olehnya ketika dia berhenti. Selanjutnya, biarkan pemain i menjadi pemverifikasi yang jujur pada langkah s > 6 atau pengguna umum yang jujur (yaitu, non-verifikasi). Mirip dengan pembuktian Lemma 5.2, pemain i menetapkan Br = Br ǫ dan menetapkan miliknya sendiri CERT r menjadi himpunan pesan (r, 5) yang valid mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j ) dia punya diterima. Terakhir, mirip dengan Lemma 5.2, Tr+1 \(\leq\) menit i\(\in\)HSV r,6 \(\alpha\)r,6 saya + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, dan semua pengguna jujur mengetahui Br pada interval waktu Ir+1, karena pengguna jujur pertama adalah siapa mengetahui Br telah membantu menyebarkan pesan (r, 5) di CERT r-nya. Kasus 2. Terdapat verifier ˆi \(\in\)HSV r,4 dengan bˆi = 0. Hal ini terjadi setelah Kasus 2 GC dan merupakan kasus yang lebih kompleks. Dengan analisis GC, dalam hal ini terdapat pesan yang valid mr,1 \(\ell\) sehingga vi = H(Br \(\ell\)) untuk semua i \(\in\)HSV r,4. Catatan bahwa pemverifikasi di HSV r,4 mungkin tidak memiliki kesepakatan mengenai bi mereka. Untuk setiap langkah s \(\in\){5, . . . , m + 3} dan pemverifikasi i \(\in\)HSV r,s, oleh pemain Lemma 5.5 saya akan memiliki menerima semua pesan yang dikirim oleh semua verifikator yang jujur di HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 jika dia telah menunggu untuk waktu ts.Sekarang kita perhatikan kejadian berikut E: terdapat langkah s∗\(\geq\)5 sehingga, untuk langkah pertama waktu dalam biner BA, beberapa pemain i∗\(\in\)SV r,s∗(baik jahat atau jujur) harus berhenti tanpa menyebarkan apa pun. Kita menggunakan “harus berhenti” untuk menekankan fakta bahwa, jika pemain i∗ berbahaya, maka dia mungkin berpura-pura tidak berhenti sesuai dengan protokol dan menyebarkan pesan pilihan Musuh. Apalagi dengan konstruksi protokolnya juga (E.a) i∗mampu mengumpulkan atau menghasilkan setidaknya pesan yang valid mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) untuk v dan s′ yang sama, dengan 5 \(\leq\)s′ \(\leq\)s∗dan s′ −2 ≡0 mod 3; atau (E.b) i∗mampu mengumpulkan atau menghasilkan setidaknya pesan yang valid mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) untuk s′ yang sama, dengan 6 \(\leq\)s′ \(\leq\)s∗dan s′ −2 ≡1 mod 3. Karena pesan jujur (r, s′ −1) diterima oleh semua pemeriksa jujur (r, s′) sebelum mereka selesai menunggu di Langkah s′, dan karena Musuh menerima semuanya selambat-lambatnya pengguna yang jujur, tanpa kehilangan sifat umum yang kami miliki s′ = s∗dan pemain i∗berbahaya. Perhatikan itu kami tidak mengharuskan nilai v di E.a menjadi hash dari blok yang valid: karena akan menjadi jelas dalam analisis, v = H(Br \(\ell\)) dalam sub-acara ini. Di bawah ini pertama-tama kita menganalisis Kasus 2 setelah peristiwa E, dan kemudian menunjukkan bahwa nilai s∗ pada dasarnya adalah didistribusikan sesuai dengan Lr (jadi kejadian E terjadi sebelum Langkah m + 3 dengan luar biasa probabilitas mengingat hubungan untuk parameter). Pertama-tama, untuk setiap langkah 5 \(\leq\)s < s∗, setiap pemverifikasi yang jujur i \(\in\)HSV r,s telah menunggu waktu ts dan menetapkan vi sebagai suara terbanyak dalam pemilu. valid (r, s−1)-pesan yang diterimanya. Sejak pemain i telah menerima semua pesan jujur (r, s−1). mengikuti Lemma 5.5, karena semua verifikator yang jujur di HSV r,4 telah menandatangani H(Br \(\ell\)) Kasus berikut 2 dari GC, dan sejak |HSV r,s−1| > 2|MSV r,s−1| untuk setiap s, dengan induksi kita mempunyai pemain i telah ditetapkan vi = H(Br \(\ell\)). Hal yang sama berlaku untuk setiap verifikator yang jujur i \(\in\)HSV r,s∗yang tidak berhenti tanpa menyebarkan apa pun. Sekarang kita pertimbangkan Langkah s∗dan membedakan empat subkasus. Kasus 2.1.a. Peristiwa E.a terjadi dan terdapat pemverifikasi yang jujur i′ \(\in\)HSV r,s∗siapa yang harus juga berhenti tanpa menyebarkan apa pun. Dalam hal ini, kita mempunyai s∗−2 ≡0 mod 3 dan Langkah s∗adalah langkah Koin-Tetap-Ke-0. Oleh definisinya, pemain i′ telah menerima setidaknya pesan (r, s∗−1) yang valid dalam bentuk (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 j ). Karena semua verifikator di HSV r,s∗−1 telah menandatangani H(Br \(\ell\)) dan |MSV r,s∗−1| < tH, kita mempunyai v = H(Br \(\ell\)). Karena setidaknya tH −|MSV r,s∗−1| \(\geq\)1 dari (r, s∗−1)-pesan yang diterima oleh i′ untuk 0 dan v dikirim oleh verifikator di HSV r,s∗−1 setelah waktu T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\) +Λ, pemain saya′ telah menerima tuan,1 \(\ell\) pada saat dia menerima pesan (r, s∗−1) tersebut. Jadi pemain aku berhenti tanpa menyebarkan apa pun; himpunan Br = Br \(\ell\); dan menetapkan CERT r miliknya sendiri menjadi kumpulan pesan valid (r, s∗−1) untuk 0 dan v yang telah diterimanya. Selanjutnya, kami tunjukkan bahwa, pemverifikasi lainnya i \(\in\)HSV r,s∗telah berhenti dengan Br = Br \(\ell\), atau telah menetapkan bi = 0 dan menyebarkan (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s saya ). Memang, karena Langkah s∗ adalah pertama kalinya beberapa verifikator berhenti tanpa menyebarkan apa pun, ternyata tidak ada langkah s′ < s∗dengan s′ −2 ≡1 mod 3 sehingga pengverifikasi tH (r, s′ −1) telah menandatangani 1. Oleh karena itu, tidak ada verifikasi di HSV r,s∗berhenti dengan Br = Br .Terlebih lagi, seperti semua verifier yang jujur ​​pada langkah {4, 5, . . . , s∗−1} telah menandatangani H(Br \(\ell\)), memang ada tidak ada langkah s′ \(\leq\)s∗dengan s′ −2 ≡0 mod 3 sehingga pengverifikasi tH (r, s′ −1) telah menandatangani beberapa v′′ ̸= H(Br \(\ell\)) —memang, |MSV r,s′−1| < th. Oleh karena itu, tidak ada pemverifikasi di HSV r,s∗stops dengan Br ̸= Br ǫ dan Br ̸= Br \(\ell\). Artinya, jika pemain i \(\in\)HSV r,s∗telah berhenti tanpa menyebarkan apa pun, dia pasti menetapkan Br = Br \(\ell\). Jika seorang pemain i \(\in\)HSV r,s∗telah menunggu waktu ts∗dan menyebarkan pesan pada waktu \(\beta\)r,s∗ saya = \(\alpha\)r,s∗ saya + ts∗, dia telah menerima semua pesan dari HSV r,s∗−1, termasuk setidaknya tH −|MSV r,s∗−1| dari mereka untuk 0 dan v. Jika saya melihat > 2/3 mayoritas untuk 1, maka dia telah melihat lebih dari 2(tH −|MSV r,s∗−1|) valid (r, s∗−1)-pesan untuk 1, dengan lebih banyak dari 2tH −3|MSV r,s∗−1| di antaranya dari pengverifikasi (r, s∗−1) yang jujur. Namun, hal ini menyiratkan |HSV r,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, bertentangan fakta itu |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n, yang berasal dari hubungan untuk parameter. Oleh karena itu, saya tidak melihat > 2/3 mayoritas untuk 1, dan dia menetapkan bi = 0 karena Langkah s∗adalah langkah Koin-Tetap-Ke-0. Seperti yang kita miliki terlihat, vi = H(Br \(\ell\)). Jadi saya menyebarkan (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i ) seperti yang kita inginkan menunjukkan. Untuk Langkah s∗+ 1, karena pemain i′ telah membantu menyebarkan pesan di CERT r-nya pada atau sebelum waktu \(\alpha\)r,s∗ saya′ + ts∗, semua verifikator yang jujur di HSV r,s∗+1 telah menerima setidaknya pesan (r, s∗−1) yang valid untuk bit 0 dan nilai H(Br \(\ell\)) pada atau sebelum selesai menunggu. Selanjutnya, pengverifikasi di HSV r,s∗+1 tidak akan berhenti sebelum menerima (r, s∗−1)- pesan, karena tidak ada pesan lain yang valid (r, s′ −1) untuk bit 1 dengan s′ −2 ≡1 mod 3 dan 6 \(\leq\)s′ \(\leq\)s∗+ 1, berdasarkan definisi Langkah s∗. Secara khusus, Langkah s∗+ 1 sendiri merupakan langkah Coin-Fixed-To-1, namun tidak ada verifier yang jujur di HSV r,s∗ yang telah disebarkan pesan untuk 1, dan |MSV r,s∗| < th. Jadi semua verifier yang jujur di HSV r,s∗+1 berhenti tanpa menyebarkan apa pun dan menetapkan Br = Sdr \(\ell\): seperti sebelumnya, mereka telah menerima tuan,1 \(\ell\) sebelum mereka menerima pesan (r, s∗−1) yang diinginkan.20 Hal yang sama juga berlaku untuk semua pemverifikasi yang jujur pada langkah selanjutnya dan semua pengguna yang jujur secara umum. Secara khusus, mereka semua mengetahui Br = Br \(\ell\)dalam selang waktu Ir+1 dan T r+1 \(\leq\) \(\alpha\)r,s∗ saya′ + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Kasus 2.1.b. Peristiwa E.b terjadi dan terdapat pemverifikasi yang jujur i′ \(\in\)HSV r,s∗siapa yang harus juga berhenti tanpa menyebarkan apa pun. Dalam hal ini kita mempunyai s∗−2 ≡1 mod 3 dan Langkah s∗adalah langkah Koin-Tetap-Ke-1. Analisisnya mirip dengan Kasus 2.1.a dan banyak rincian yang dihilangkan. 20Jika \(\ell\)berniat jahat, dia mungkin akan mengirim Tuan, 1 \(\ell\) terlambat, berharap beberapa pengguna/verifikasi yang jujur belum menerima mr,1 \(\ell\) belum ketika mereka menerima sertifikat yang diinginkan untuk itu. Namun, karena verifier ˆi \(\in\)HSV r,4 telah menetapkan bˆi = 0 dan vˆi = H(Br \(\ell\)), sebagai sebelum kita mengetahui bahwa lebih dari separuh pengverifikasi yang jujur i \(\in\)HSV r,3 telah menetapkan vi = H(Br \(\ell\)). Hal ini semakin menyiratkan lebih banyak lagi dari separuh pengverifikasi yang jujur i \(\in\)HSV r,2 telah menetapkan vi = H(Br \(\ell\)), dan (r, 2)-verifier semuanya telah menerima mr,1 \(\ell\). Sebagai Musuh tidak dapat membedakan verifikator dari non-verifikasi, ia tidak dapat menargetkan penyebaran mr,1 \(\ell\) ke (r, 2)-pengverifikasi tanpa orang yang bukan pemverifikasi melihatnya. Faktanya, dengan probabilitas tinggi, lebih dari setengah (atau pecahan konstan yang bagus) dari semua pengguna jujur telah melihat mr,1 \(\ell\) setelah menunggu t2 dari awal rondenya sendiri r. Mulai sekarang, itu waktu \(\lambda\)′ yang dibutuhkan untuk mr,1 \(\ell\) untuk menjangkau pengguna jujur lainnya jauh lebih kecil dari Λ, dan demi kesederhanaan, kami tidak melakukannya tuliskan dalam analisis. Jika 4\(\lambda\) \(\geq\) \(\lambda\)′ maka analisis berjalan tanpa perubahan apa pun: pada akhir Langkah 4, semua pengguna yang jujur akan menerima mr,1 \(\ell\). Jika ukuran balok menjadi sangat besar dan 4\(\lambda\) < \(\lambda\)′, maka pada Langkah 3 dan 4, protokol dapat meminta setiap pemverifikasi untuk menunggu \(\lambda\)′/2 daripada 2\(\lambda\), dan analisis terus berlanjut.Seperti sebelumnya, pemain i′ harus menerima setidaknya tH valid (r, s∗−1)-pesan dalam bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 j ). Sekali lagi berdasarkan definisi s∗, tidak ada langkah 5 \(\leq\)s′ < s∗dengan s′ −2 ≡0 mod 3, dimana setidaknya tH (r, s′ −1)-pengverifikasi telah menandatangani 0 dan v yang sama. Jadi pemain i′ berhenti tanpa menyebarkan apa pun; himpunan Br = Br ; dan set CERT r miliknya sendiri menjadi himpunan pesan valid (r, s∗−1) untuk bit 1 yang telah diterimanya. Selain itu, pemverifikasi i \(\in\)HSV r,s∗ lainnya telah berhenti pada Br = Br , atau telah menetapkan bi = 1 dan diperbanyak (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ saya ). Sejak player i′ telah membantu propagasi pesan (r, s∗−1) di CERT-nya r pada waktu \(\alpha\)r,s∗ saya′ + ts∗, sekali lagi semua verifier yang jujur masuk HSV r,s∗+1 berhenti tanpa menyebarkan apa pun dan mengatur Br = Br . Demikian pula semuanya jujur pengguna mengetahui Br = Br ǫ dalam interval waktu Ir+1 dan T r+1 \(\leq\) \(\alpha\)r,s∗ saya′ + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Kasus 2.2.a. Peristiwa E.a terjadi dan tidak terdapat pemeriksa yang jujur i′ \(\in\)HSV r,s∗who juga harus berhenti tanpa menyebarkan apa pun. Dalam hal ini, perhatikan bahwa pemain i∗dapat memiliki CERT r yang valid i∗terdiri dari tH yang diinginkan (r, s∗−1)-pesan yang dapat dikumpulkan atau dihasilkan oleh Musuh. Namun, yang jahat pemeriksa mungkin tidak membantu menyebarkan pesan-pesan tersebut, jadi kami tidak dapat menyimpulkan bahwa mereka jujur pengguna akan menerimanya tepat waktu \(\lambda\). Faktanya, |MSV r,s∗−1| dari pesan-pesan itu mungkin berasal pengverifikasi (r, s∗−1) jahat, yang tidak menyebarkan pesan mereka sama sekali dan hanya mengirim mereka ke pemverifikasi jahat di langkah s∗. Mirip dengan Kasus 2.1.a, di sini kita memiliki s∗−2 ≡0 mod 3, Langkah s∗adalah langkah Koin-Tetap-Ke-0, dan pesan (r, s∗−1) di CERT r i∗adalah untuk bit 0 dan v = H(Br \(\ell\)). Memang semuanya jujur (r, s∗−1)-verifier menandatangani v, sehingga Musuh tidak dapat menghasilkan pesan-pesan (r, s∗−1) yang valid untuk v′ yang berbeda. Terlebih lagi, semua pengverifikasi yang jujur (r, s∗) telah menunggu waktu ts∗dan tidak melihat > 2/3 mayoritas untuk bit 1, sekali lagi karena |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n. Demikianlah setiap verifikator yang jujur i \(\in\)HSV r,s∗set bi = 0, vi = H(Br \(\ell\)) dengan suara terbanyak, dan memperbanyak mr,s∗ saya = (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s∗ saya ) pada waktu \(\alpha\)r,s∗ saya + ts∗. Sekarang pertimbangkan pemverifikasi yang jujur ​​pada Langkah s∗+ 1 (yang merupakan langkah Koin-Tetap-Ke-1). Jika Musuh sebenarnya mengirimkan pesan di CERT r i∗kepada beberapa di antaranya dan menyebabkannya stop, lalu mirip dengan Kasus 2.1.a, semua pengguna yang jujur mengetahui Br = Br \(\ell\)dalam interval waktu Ir+1 dan T r+1 \(\leq\)T r + \(\lambda\) + ts∗+1. Jika tidak, semua verifikator yang jujur pada Langkah s∗+1 telah menerima semua pesan (r, s∗) untuk 0 dan H(Br \(\ell\)) dari HSV r,s∗setelah waktu tunggu ts∗+1, yang menghasilkan > 2/3 mayoritas, karena |HSV r,s∗| > 2|MSV r,s∗|. Jadi semua verifikator di HSV r,s∗+1 menyebarkan pesan mereka 0 dan H(Br \(\ell\)) sesuai dengan itu. Perhatikan bahwa verifier di HSV r,s∗+1 tidak berhenti pada Br = Br \(\ell\), karena Langkah s∗+ 1 bukanlah langkah Koin-Tetap-Ke-0. Sekarang pertimbangkan pemverifikasi yang jujur ​​pada Langkah s∗+2 (yang merupakan langkah Pembalikan Koin). Jika Musuh mengirimkan pesan dalam CERT r i∗kepada beberapa dari mereka dan menyebabkan mereka berhenti, sekali lagi semua pengguna yang jujur mengetahui Br = Br \(\ell\)dalam selang waktu Ir+1 dan T r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.Jika tidak, semua verifikasi yang jujur pada Langkah s∗+ 2 telah menerima semua pesan (r, s∗+ 1) untuk 0 dan H(Br \(\ell\)) dari HSV r,s∗+1 setelah waktu tunggu ts∗+2, sehingga menghasilkan > 2/3 mayoritas. Dengan demikian mereka semua menyebarkan pesannya untuk 0 dan H(Br \(\ell\)) sesuai dengan itu: itulah yang mereka lakukan bukan “melempar koin” dalam kasus ini. Sekali lagi, perhatikan bahwa mereka tidak berhenti tanpa menyebar, karena Langkah s∗+ 2 bukanlah langkah Koin-Tetap-Ke-0. Yang terakhir, bagi pemverifikasi yang jujur pada Langkah s∗+3 (yang merupakan langkah Koin-Tetap-Ke-0 lainnya), semua dari mereka akan menerima setidaknya pesan yang valid untuk 0 dan H(Br \(\ell\)) dari HSV s∗+2, jika mereka benar-benar menunggu waktu ts∗+3. Jadi, apakah Musuh mengirimkan pesan atau tidak di CERT r i∗ke salah satu dari mereka, semua verifier di HSV r,s∗+3 berhenti dengan Br = Br \(\ell\), tanpa menyebarkan apa pun. Bergantung pada bagaimana Musuh bertindak, beberapa di antaranya mungkin pernah melakukannya CERT r mereka sendiri yang terdiri dari pesan-pesan (r, s∗−1) di CERT r i∗, dan yang lainnya punya CERT mereka sendiri r yang terdiri dari pesan-pesan (r, s∗+ 2). Bagaimanapun, semua pengguna yang jujur tahu Br = Br \(\ell\)dalam selang waktu Ir+1 dan T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Kasus 2.2.b. Peristiwa E.b terjadi dan tidak terdapat pemeriksa yang jujur i′ \(\in\)HSV r,s∗who juga harus berhenti tanpa menyebarkan apa pun. Analisis dalam kasus ini mirip dengan Kasus 2.1.b dan Kasus 2.2.a, sehingga banyak rinciannya. telah dihilangkan. Secara khusus, CERT r i∗terdiri dari pesan-pesan (r, s∗−1) yang diinginkan untuk bit 1 yang dapat dikumpulkan atau dihasilkan oleh Musuh, s∗−2 ≡1 mod 3, Langkah s∗is a Langkah Coin-Fixed-To-1, dan tidak ada pemverifikasi (r, s∗) yang jujur yang dapat memperoleh > 2/3 mayoritas untuk 0. Jadi, setiap pemverifikasi i \(\in\)HSV r,s∗set bi = 1 dan menyebarkan mr,s∗ saya = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ saya ) pada waktu \(\alpha\)r,s∗ saya + ts∗. Mirip dengan Kasus 2.2.a, dalam paling banyak 3 langkah lagi (yaitu protokol mencapai Langkah s∗+3, yang merupakan langkah Koin-Tetap-Ke-1 lainnya), semua pengguna yang jujur mengetahui Br = Br ǫ dalam selang waktu Ir+1. Selain itu, T r+1 mungkin \(\leq\)T r+\(\lambda\)+ts∗+1, atau \(\leq\)T r+\(\lambda\)+ts∗+2, atau \(\leq\)T r + \(\lambda\) + ts∗+3, bergantung pada kapan pertama kalinya verifikator yang jujur dapat menghentikan tanpa menyebar. Menggabungkan empat sub-kasus, kami mendapatkan bahwa semua pengguna yang jujur mengetahui Br dalam interval waktu tersebut Ir+1, dengan T r+1 \(\leq\)T r + \(\lambda\) + ts∗dalam Kasus 2.1.a dan 2.1.b, dan T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 dalam Kasus 2.2.a dan 2.2.b. Tetap pada batas atas s∗dan dengan demikian T r+1 untuk Kasus 2, dan kami melakukannya dengan mempertimbangkan bagaimana berkali-kali langkah-langkah yang Dibalik Koin sebenarnya dijalankan dalam protokol: yaitu, beberapa pemverifikasi yang jujur sebenarnya telah melakukan lemparan koin. Secara khusus, perbaiki secara sewenang-wenang langkah Koin-Benar-Terbalik s′ (yaitu, 7 \(\leq\)s′ \(\leq\)m + 2 dan s′ −2 ≡2 mod 3), dan misalkan \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ). Untuk saat ini mari kita asumsikan s′ < s∗, karena jika tidak, tidak ada pemverifikasi yang jujur yang benar-benar melempar koin pada Langkah s′, menurut langkah sebelumnya diskusi. Berdasarkan definisi SV r,s′−1, nilai hash dari kredensial \(\ell\)′ juga merupakan yang terkecil di antara semua pengguna di PKr−k. Karena fungsi hash adalah oracle acak, idealnya pemain \(\ell\)′ jujur dengan probabilitas setidaknya h. Seperti yang akan kami tunjukkan nanti, meskipun Musuh mencoba yang terbaik untuk memprediksinya keluaran oracle acak dan memiringkan probabilitas, pemain \(\ell\)′ masih jujur dengan probabilitaspaling tidak ph = h2(1 + h −h2). Di bawah ini kami mempertimbangkan kasus ketika hal tersebut benar-benar terjadi: yaitu, \(\ell\)′ \(\in\)HSV r,s′−1. Perhatikan bahwa setiap pemverifikasi yang jujur i \(\in\)HSV r,s′ telah menerima semua pesan dari HSV r,s′−1 pada waktu \(\alpha\)r,s′ saya + ts′. Jika pemain i perlu melempar koin (yaitu, dia belum melihat > 2/3 mayoritas untuk bit yang sama b \(\in\){0, 1}), lalu ia menetapkan bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )). Jika ada yang lain jujur pemverifikasi i′ \(\in\)HSV r,s′ yang telah melihat > 2/3 mayoritas untuk bit b \(\in\){0, 1}, maka berdasarkan Properti (d) dari Lemma 5.5, tidak ada pemverifikasi yang jujur di HSV r,s′ yang akan memperoleh > 2/3 mayoritas untuk sementara waktu b′ ̸= b. Sejak lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b dengan probabilitas 1/2, semua verifier yang jujur di HSV r,s′ dapat dijangkau kesepakatan pada b dengan probabilitas 1/2. Tentu saja, jika pemverifikasi i′ tersebut tidak ada, maka semuanya ada pemverifikasi yang jujur di HSV r,s′ menyetujui bit lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) dengan probabilitas 1. Menggabungkan probabilitas untuk \(\ell\)′ \(\in\)HSV r,s′−1, kita mendapatkan bahwa pemverifikasi yang jujur dalam HSV r,s′ mencapai kesepakatan pada bit b \(\in\){0, 1} dengan probabilitas paling sedikit ph 2 = h2(1+h−h2) 2 . Selain itu, dengan induksi pada suara mayoritas seperti sebelumnya, semua verifier yang jujur di HSV r,s′ telah menetapkan vinya menjadi H(Br \(\ell\)). Jadi, setelah kesepakatan tentang b tercapai pada Langkah s′, T r+1 adalah baik \(\leq\)T r + \(\lambda\) + ts′+1 atau \(\leq\)T r + \(\lambda\) + ts′+2, tergantung pada apakah b = 0 atau b = 1, mengikuti analisis Kasus 2.1.a dan 2.1.b. Di khususnya, tidak ada langkah Pembalikan Koin lebih lanjut yang akan dijalankan: yaitu, pemverifikasi di langkah-langkah tersebut masih memeriksa apakah merekalah yang melakukan verifikasi dan dengan demikian menunggu, namun langkah-langkah tersebut akan berhenti jika tidak dilakukan menyebarkan apa pun. Oleh karena itu, sebelum Langkah s∗, berapa kali langkah Coin-GenuinelyFlipped dijalankan didistribusikan sesuai dengan variabel acak Lr. Membiarkan Langkah s′ menjadi langkah terakhir yang Benar-Benar Dibalik Koin menurut Lr, dengan konstruksi protokol kita punya s′ = 4 + 3Lr. Kapan Musuh harus membuat Langkah itu terjadi jika dia ingin menunda T r+1 sebanyak itu mungkin? Kita bahkan dapat berasumsi bahwa Musuh mengetahui realisasi Lr terlebih dahulu. Jika s∗> s′ maka percuma saja, karena verifikator yang jujur sudah mencapai kesepakatan Langkah s′. Yang pasti, dalam kasus ini s∗akan menjadi s′ +1 atau s′ +2, sekali lagi bergantung pada apakah b = 0 atau b = 1. Namun, ini sebenarnya Kasus 2.1.a dan 2.1.b, dan T r+1 yang dihasilkan sama persis dengan sama seperti dalam kasus itu. Lebih tepatnya, T r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Jika s∗< s′ −3 —yaitu, s∗adalah sebelum langkah kedua terakhir yang Membalik Koin— maka dengan analisis Kasus 2.2.a dan 2.2.b, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < T r + \(\lambda\) + ts′. Maksudnya, pihak Adversary sebenarnya membuat kesepakatan mengenai Br terjadi lebih cepat. Jika s∗= s′ −2 atau s′ −1 —yaitu, langkah Koin-Tetap-Ke-0 atau langkah Koin-Tetap-Ke-1 tepat sebelum Langkah s′— kemudian dengan analisis empat sub-kasus, verifikator yang jujur masuk Langkah s′ tidak perlu lagi melempar koin, karena sudah berhenti tanpa menyebar, atau telah melihat > 2/3 mayoritas untuk bit yang sama b. Oleh karena itu kita punya T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.Singkatnya, apa pun masalahnya, kita punya T r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = T r + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = T r + (6Lr + 10)\(\lambda\) + Λ, seperti yang ingin kami tunjukkan. Kasus terburuk adalah ketika s∗= s′ −1 dan Kasus 2.2.b terjadi. Menggabungkan Kasus 1 dan 2 dari protokol BA biner, Lemma 5.3 berlaku. ■ 5.9 Keamanan Benih Qr dan Kemungkinan Pemimpin yang Jujur Masih harus membuktikan Lemma 5.4. Ingatlah bahwa pemverifikasi pada putaran r diambil dari PKr−k dan dipilih berdasarkan kuantitas Qr−1. Alasan memperkenalkan parameter lihat kembali k adalah untuk memastikan bahwa, kembali ke putaran r −k, ketika Musuh dapat menambahkan pengguna jahat baru untuk PKr−k, dia tidak dapat memprediksi kuantitas Qr−1 kecuali dengan probabilitas yang dapat diabaikan. Perhatikan bahwa Fungsi hash adalah oracle acak dan Qr−1 adalah salah satu inputnya ketika memilih verifier untuk putaran r. Jadi, tidak peduli seberapa jahatnya pengguna yang ditambahkan ke PKr−k, dari sudut pandang Musuh masing-masing salah satu dari mereka masih terpilih menjadi pemverifikasi pada langkah putaran r dengan probabilitas yang diperlukan p (atau p1 untuk Langkah 1). Lebih tepatnya, kita mempunyai lemma berikut. Lemma 5.6. Dengan k = O(log1/2 F), untuk setiap putaran r, dengan kemungkinan besar Musuh tidak menanyakan Qr−1 ke oracle acak pada putaran r −k. Bukti. Kami melanjutkan dengan induksi. Asumsikan bahwa untuk setiap putaran \(\gamma\) < r, Musuh tidak mengajukan pertanyaan Q\(\gamma\)−1 ke oracle acak kembali pada ronde \(\gamma\) −k.21 Perhatikan permainan mental berikut yang dimainkan oleh Musuh di ronde r −k, mencoba memprediksi Qr−1. Pada Langkah 1 setiap putaran \(\gamma\) = r −k, . . . , r −1, diberikan Q\(\gamma\)−1 spesifik yang tidak ditanyakan secara acak oracle, dengan mengurutkan pemain i \(\in\)PK\(\gamma\)−k sesuai dengan nilai hash H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) semakin banyak, kita mendapatkan permutasi acak atas PK\(\gamma\)−k. Menurut definisi, pemimpin \(\ell\) \(\gamma\) adalah pengguna pertama dalam permutasi dan jujur dengan probabilitas h. Apalagi bila PK\(\gamma\)−k besar cukup, untuk sembarang bilangan bulat x \(\geq\)1, probabilitas bahwa pengguna x pertama dalam permutasi semuanya adalah berbahaya tetapi (x + 1) yang jujur adalah (1 −h)xh. Jika \(\ell\) \(\gamma\) jujur, maka Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Karena Musuh tidak dapat memalsukan tanda tangannya dari \(\ell\) \(\gamma\), Q\(\gamma\) didistribusikan secara seragam secara acak dari sudut pandang Musuh dan, kecuali dengan probabilitas yang sangat kecil,22 tidak ditanyakan ke H pada putaran r −k. Sejak masing-masing Q\(\gamma\)+1, Q\(\gamma\)+2, . . . , Qr−1 masing-masing adalah keluaran dari H dengan Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 sebagai salah satu masukan, mereka semua terlihat acak bagi Musuh dan Musuh tidak mungkin menanyakan Qr−1 hingga H di putaran r −k. Oleh karena itu, satu-satunya kasus di mana Musuh dapat memprediksi Qr−1 dengan probabilitas yang baik pada putaran tersebut r−k adalah saat semua pemimpin \(\ell\)r−k, . . . , \(\ell\)r−1 berbahaya. Sekali lagi pertimbangkan putaran \(\gamma\) \(\in\){r−k . . . , r−1} dan permutasi acak pada PK\(\gamma\)−k yang disebabkan oleh nilai hash yang sesuai. Jika untuk beberapa orang x \(\geq\)2, pengguna x −1 pertama dalam permutasi semuanya jahat dan ke-x jujur, maka Musuh mempunyai x kemungkinan pilihan untuk Q\(\gamma\): salah satu dari bentuk H(SIGi(Q\(\gamma\)−1, \(\gamma\))), dimana i adalah salah satu dari 21Karena k adalah bilangan bulat kecil, tanpa kehilangan keumumannya, kita dapat berasumsi bahwa k putaran pertama dari protokol dijalankan dalam lingkungan yang aman dan hipotesis induktif berlaku untuk putaran tersebut. 22Artinya, panjang keluaran H bersifat eksponensial. Perhatikan bahwa probabilitas ini jauh lebih kecil daripada F.pengguna jahat x−1 pertama, dengan menjadikan pemain i sebagai pemimpin putaran \(\gamma\); atau H(Q\(\gamma\)−1, \(\gamma\)), oleh memaksa B\(\gamma\) = B\(\gamma\) . Jika tidak, pemimpin putaran \(\gamma\) akan menjadi pengguna jujur pertama dalam permutasi tersebut dan Qr−1 menjadi tidak dapat diprediksi oleh Musuh. Manakah dari opsi x Q\(\gamma\) di atas yang harus dilakukan oleh Musuh? Untuk membantu Musuh jawab pertanyaan ini, dalam permainan mental kita sebenarnya membuatnya lebih kuat dari dia sebenarnya adalah, sebagai berikut. Pertama-tama, pada kenyataannya, Musuh tidak dapat menghitung hash pengguna yang jujur tanda tangan, sehingga tidak dapat memutuskan, untuk setiap Q\(\gamma\), jumlah x(Q\(\gamma\)) pengguna jahat di awal dari permutasi acak pada putaran \(\gamma\) + 1 yang diinduksi oleh Q\(\gamma\). Dalam permainan mental, kami memberinya angka x(Q\(\gamma\)) gratis. Yang kedua, pada kenyataannya, memiliki x pengguna pertama dalam permutasi semuanya bersikap jahat tidak berarti mereka semua bisa dijadikan pemimpin, karena hash nilai tanda tangannya juga harus kurang dari p1. Kami telah mengabaikan kendala mental ini permainan, memberikan Musuh lebih banyak keuntungan. Sangat mudah untuk melihat bahwa dalam permainan mental, pilihan optimal untuk Musuh, dilambangkan dengan Q\(\gamma\), adalah salah satu yang menghasilkan urutan pengguna jahat terpanjang di awal acak permutasi pada putaran \(\gamma\) + 1. Memang, mengingat Q\(\gamma\) tertentu, protokolnya tidak bergantung pada Q\(\gamma\)−1 lagi dan Musuh hanya bisa fokus pada permutasi baru di babak \(\gamma\) + 1, yang memiliki distribusi yang sama untuk jumlah pengguna jahat di awal. Oleh karena itu, di setiap putaran \(\gamma\), ˆQ\(\gamma\) yang disebutkan di atas memberinya jumlah opsi terbesar untuk Q\(\gamma\)+1 dan dengan demikian memaksimalkan kemungkinan bahwa pemimpin berturut-turut semuanya jahat. Oleh karena itu, dalam permainan mental Musuh mengikuti Rantai Markov dari putaran r −k untuk membulatkan r −1, dengan ruang keadaan menjadi {0} \(\cup\){x : x \(\geq\)2}. Negara 0 mewakili fakta bahwa pengguna pertama dalam permutasi acak pada putaran saat ini \(\gamma\) adalah jujur, sehingga Musuh gagal dalam permainan untuk memprediksi Qr−1; dan setiap negara bagian x \(\geq\)2 mewakili fakta bahwa pengguna x −1 pertama di permutasi berbahaya dan x-th jujur, sehingga Musuh memiliki opsi x untuk Q\(\gamma\). Itu probabilitas transisi P(x, y) adalah sebagai berikut. • P(0, 0) = 1 dan P(0, y) = 0 untuk sembarang y \(\geq\)2. Artinya, Musuh gagal dalam permainan satu kali saja pengguna dalam permutasi menjadi jujur. • P(x, 0) = hx untuk sembarang x \(\geq\)2. Artinya, dengan probabilitas hx, semua x permutasi acak mempunyai pengguna pertama mereka bersikap jujur, sehingga Musuh gagal dalam permainan di babak berikutnya. • Untuk setiap x \(\geq\)2 dan y \(\geq\)2, P(x, y) adalah probabilitas bahwa, di antara x permutasi acak diinduksi oleh opsi x dari Q\(\gamma\), urutan terpanjang dari pengguna jahat di awal beberapa di antaranya adalah y −1, sehingga Musuh memiliki opsi y untuk Q\(\gamma\)+1 di babak berikutnya. Artinya, P(x, kamu) = kamu−1 X saya=0 (1 −h)ih !x - kamu−2 X saya=0 (1 −h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Perhatikan bahwa keadaan 0 adalah keadaan penyerap unik dalam matriks transisi P, dan setiap keadaan lainnya x mempunyai probabilitas positif untuk menuju ke 0. Kita tertarik untuk membatasi bilangan k dari putaran yang diperlukan agar Rantai Markov menyatu ke 0 dengan probabilitas yang sangat besar: yaitu, tidak tidak peduli di negara bagian mana rantai itu dimulai, dengan kemungkinan besar Musuh kalah dalam permainan dan gagal memprediksi Qr−1 pada putaran r −k. Pertimbangkan matriks transisi P (2) \(\triangleq\)P \(\cdot\) P setelah dua putaran. Sangat mudah untuk melihat bahwa P (2)(0, 0) = 1 dan P (2)(0, x) = 0 untuk sembarang x \(\geq\)2. Untuk setiap x \(\geq\)2 dan y \(\geq\)2, karena P(0, y) = 0, kita mempunyai P (2)(x, y) = P(x, 0)P(0, y) + X z\(\geq\)2 P(x, z)P(z, y) = X z\(\geq\)2 P(x, z)P(z, kamu).Membiarkan ¯h \(\triangleq\)1 −h, kita punya P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x dan P (2)(x, kamu) = X z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. Di bawah ini kita menghitung limit P (2)(x,y) P (x, y) saat h menjadi 1 —yaitu, ¯h menjadi 0. Perhatikan bahwa yang tertinggi orde ¯h pada P(x, y) adalah ¯hy−1, dengan koefisien x. Oleh karena itu, batas jam \(\to\) 1 P (2)(x, kamu) P(x, kamu) = lim ¯ jam \(\to\) 0 P (2)(x, kamu) P(x, kamu) = lim ¯ jam \(\to\) 0 P (2)(x, kamu) x¯hy−1 + O(¯hy) = batas ¯ jam \(\to\) 0 hal z\(\geq\)2[x¯hz−1 + O(¯hz)][z¯hy−1 + O(¯hy)] x¯hy−1 + O(¯hy) = lim ¯ jam \(\to\) 0 2x¯hy + O(¯hy+1) x¯hy−1 + O(¯hy) = batas ¯ jam \(\to\) 0 2x¯hy x¯hy−1 = lim ¯jam \(\to\) 0 2¯jam = 0. Ketika h cukup mendekati 1,23, kita punya P (2)(x, kamu) P(x, kamu) \(\leq\)1 2 untuk setiap x \(\geq\)2 dan y \(\geq\)2. Dengan induksi, untuk sembarang k > 2, P (k) \(\triangleq\)P k sedemikian rupa sehingga • P (k)(0, 0) = 1, P (k)(0, x) = 0 untuk sembarang x \(\geq\)2, dan • untuk setiap x \(\geq\)2 dan y \(\geq\)2, P (k)(x, y) = P (k−1)(x, 0)P(0, y) + X z\(\geq\)2 P (k−1)(x, z)P(z, y) = X z\(\geq\)2 P (k−1)(x, z)P(z, y) \(\leq\) X z\(\geq\)2 P(x, z) 2k−2 \(\cdot\) P(z, y) = P (2)(x, y) 2k−2 \(\leq\)P(x, y) 2k−1 . Karena P(x, y) \(\leq\)1, setelah putaran 1−log2 F, probabilitas transisi ke keadaan mana pun y \(\geq\)2 dapat diabaikan, dimulai dengan keadaan apa pun x \(\geq\)2. Meskipun ada banyak negara bagian y, mudah untuk melihatnya batas kamu→+∞ P(x, kamu) P(x, y + 1) = batas kamu→+∞ (1 −¯hy)x −(1 −¯hy−1)x (1 −¯hy+1)x −(1 −¯hy)x = batas kamu→+∞ ¯hy−1 −¯hy ¯hy −¯hy+1 = 1 ¯ jam = 1 1 jam. Oleh karena itu setiap baris x matriks transisi P berkurang sebagai barisan geometri dengan laju 1 1−jam > 2 ketika y cukup besar, dan hal yang sama berlaku untuk P (k). Oleh karena itu, ketika k cukup besar namun tetap pada urutan log1/2 F, P y\(\geq\)2 P (k)(x, y) < F untuk setiap x \(\geq\)2. Artinya, dengan kemungkinan yang sangat besar Musuh kalah dalam permainan dan gagal memprediksi Qr−1 pada ronde r −k. Untuk h \(\in\)(2/3, 1], lebih analisis kompleks menunjukkan bahwa terdapat konstanta C yang sedikit lebih besar dari 1/2, sehingga mencukupi untuk mengambil k = O(logC F). Demikianlah Lemma 5.6 berlaku. ■ Lemma 5.4. (disajikan kembali) Sifat yang diberikan 1–3 untuk setiap putaran sebelum r, ph = h2(1 + h −h2) untuk Lr, dan pemimpin \(\ell\)r jujur dengan probabilitas setidaknya ph. 23Misalnya, h = 80% seperti yang disarankan oleh pilihan parameter tertentu.

Bukti. Mengikuti Lemma 5.6, Musuh tidak dapat memprediksi kembali Qr−1 pada putaran r −k kecuali dengan probabilitas yang dapat diabaikan. Perlu dicatat bahwa hal ini tidak berarti kemungkinan untuk mendapatkan pemimpin yang jujur adalah hal yang mustahil setiap putaran. Memang, mengingat Qr−1, tergantung pada berapa banyak pengguna jahat di awal permutasi acak PKr−k, Musuh mungkin mempunyai lebih dari satu pilihan untuk Qr dan dengan demikian dapat meningkatkan kemungkinan munculnya pemimpin jahat di putaran r + 1 —sekali lagi kita memberikannya beberapa kelebihan yang tidak realistis seperti pada Lemma 5.6, sehingga dapat menyederhanakan analisis. Namun, untuk setiap Qr−1 yang tidak ditanyakan ke H oleh Musuh pada putaran r −k, untuk setiap x \(\geq\)1, dengan probabilitas (1 −h)x−1h pengguna jujur pertama muncul pada posisi x dalam hasil permutasi acak dari PKr−k. Jika x = 1, peluang munculnya pemimpin yang jujur pada putaran r + 1 adalah memang h; sedangkan ketika x = 2, Musuh memiliki dua pilihan Qr dan probabilitas yang dihasilkan adalah h2. Hanya dengan mempertimbangkan dua kasus ini, kita mempunyai kemungkinan untuk mendapatkan pemimpin yang jujur r + 1 setidaknya h \(\cdot\) h + (1 −h)h \(\cdot\) h2 = h2(1 + h −h2) sesuai keinginan. Perhatikan bahwa probabilitas di atas hanya mempertimbangkan keacakan protokol dari putaran r −k untuk membulatkan r. Ketika semua keacakan dari putaran 0 hingga putaran r dipertimbangkan, Qr−1 adalah bahkan lebih sulit diprediksi oleh Musuh dan kemungkinan pemimpin yang jujur di babak r + 1 adalah paling sedikit h2(1 + h −h2). Mengganti r + 1 dengan r dan menggeser semuanya kembali satu putaran, pemimpin \(\ell\)r jujur dengan probabilitas paling sedikit h2(1 + h −h2), sesuai keinginan. Demikian pula, dalam setiap langkah Pembalikan Koin, “pemimpin” dari langkah tersebut —yaitu pemverifikasi pada SV r,s yang kredensialnya mempunyai nilai hash terkecil, jujur dengan probabilitas paling sedikit h2(1 + jam −h2). Jadi ph = h2(1 + h −h2) untuk Lr dan Lemma 5.4 berlaku. ■

Algorand '

2 Di bagian ini, kami membuat versi Algorand ′ yang bekerja dengan asumsi berikut. Asumsi Mayoritas Pengguna Jujur: Lebih dari 2/3 pengguna di setiap PKr adalah jujur. Di Bagian 8, kami menunjukkan cara mengganti asumsi di atas dengan Mayoritas Jujur yang diinginkan Asumsi uang. 6.1 Notasi dan Parameter Tambahan untuk Algorand ′ 2 Notasi • \(\mu\) \(\in\)Z+: batas atas pragmatis terhadap jumlah langkah yang, dengan kemungkinan sangat besar, sebenarnya akan diambil dalam satu putaran. (Seperti yang akan kita lihat, parameter \(\mu\) mengontrol berapa banyak ephemeral kunci yang disiapkan pengguna sebelumnya untuk setiap putaran.) • Lr: variabel acak yang mewakili jumlah percobaan Bernoulli yang diperlukan untuk mendapatkan angka 1, ketika masing-masing percobaan percobaan adalah 1 dengan probabilitas ph 2. Lr akan digunakan untuk membatasi waktu yang diperlukan untuk menghasilkan blok Br. • tH: batas bawah jumlah verifikator yang jujur pada langkah s > 1 pada putaran r, sehingga dengan probabilitas yang sangat besar (mengingat n dan p), ada > pemverifikasi yang jujur di SV r,s. Parameter • Hubungan antara berbagai parameter. — Untuk setiap langkah s > 1 pada putaran r, n dipilih sehingga, dengan probabilitas yang sangat besar,

|HSV r,s| > ini dan |HSV r,s| + 2|MSV r,s| < 2tH. Perhatikan bahwa kedua pertidaksamaan di atas secara bersama-sama menyiratkan |HSV r,s| > 2|MSV r,s|: yaitu disana adalah 2/3 mayoritas yang jujur di antara verifikator terpilih. Semakin mendekati 1 nilai h, maka n harus semakin kecil. Secara khusus, kami menggunakan (varian dari) Batas Cherno untuk memastikan kondisi yang diinginkan terpenuhi dengan kemungkinan yang sangat besar. • Contoh pilihan parameter penting. — F = 10−18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Menerapkan Kunci Ephemeral di Algorand ′ 2 Ingatlah bahwa pemverifikasi i \(\in\)SV r,s secara digital menandatangani pesannya mr,s saya langkah s di putaran r, relatif terhadap pkr kunci publik sementara i , menggunakan kunci rahasia sementara skr,s saya yang segera dia hancurkan setelah menggunakan. Ketika jumlah langkah yang mungkin diambil dalam suatu putaran dibatasi oleh jumlah langkah tertentu bilangan bulat \(\mu\), kita telah melihat cara menangani kunci sementara secara praktis. Misalnya seperti kita sudah dijelaskan di Algorand′ 1 (di mana \(\mu\) = m + 3), untuk menangani semua kemungkinan kunci sementaranya, dari putaran r′ ke putaran r′ + 106, i menghasilkan pasangan (PMK, SMK), dimana PMK public master kunci skema tanda tangan berbasis identitas, dan SMK kunci master rahasianya yang sesuai. Pengguna i mempublikasikan PMK dan menggunakan SMK untuk menghasilkan kunci rahasia dari setiap kemungkinan kunci publik sementara (dan menghancurkan SMK setelah melakukannya). Kumpulan kunci publik sementara i untuk relevan putarannya adalah S = {i} \(\times\) {r′, . . . , r′ + 106} \(\times\) {1, . . . , \(\mu\)}. (Seperti yang telah dibahas, saat putaran r′ + 106 mendekat, saya “menyegarkan” pasangannya (PMK, SMK).) Dalam prakteknya, jika \(\mu\) cukup besar, putaran Algorand ′ 2 tidak akan memakan waktu lebih dari \(\mu\) langkah. Di prinsipnya, bagaimanapun, ada kemungkinan kecil bahwa, untuk beberapa putaran r jumlah langkah sebenarnya diambil akan melebihi \(\mu\). Jika ini terjadi, saya tidak akan bisa menandatangani pesannya, Tuan saya untuk setiap langkah s > \(\mu\), karena dia telah mempersiapkan sebelumnya hanya \(\mu\) kunci rahasia untuk putaran r. Apalagi dia tidak dapat menyiapkan dan mempublikasikan simpanan kunci sementara yang baru, seperti yang telah dibahas sebelumnya. Faktanya, untuk melakukan jadi, dia perlu memasukkan PMK′ kunci master publik baru di blok baru. Tapi, harus mengitari sungai mengambil lebih banyak langkah, tidak ada blok baru yang akan dihasilkan. Namun, solusinya ada. Misalnya, saya dapat menggunakan kunci sementara terakhir dari putaran r, pkr,\(\mu\) saya , sebagai berikut. Dia menghasilkan simpanan pasangan kunci lainnya untuk putaran r —misalnya, dengan (1) menghasilkan pasangan kunci lainnya pasangan kunci utama (PMK, SMK); (2) menggunakan pasangan ini untuk menghasilkan yang lain, katakanlah, 106 kunci sementara, sk r,\(\mu\)+1 saya , . . . , sk r,\(\mu\)+106 saya , sesuai dengan langkah \(\mu\)+1, ..., \(\mu\)+106 putaran r; (3) menggunakan skr,\(\mu\) saya ke secara digital tanda tangani PMK (dan pesan (r, \(\mu\)) apa pun jika i \(\in\)SV r,\(\mu\)), relatif terhadap pkr,\(\mu\) saya ; dan (4) menghapus SMK dan skr,\(\mu\) saya . Haruskah saya menjadi pemverifikasi pada langkah \(\mu\) + s dengan s \(\in\){1, . . . , 106}, lalu saya menandatanganinya secara digital (r, \(\mu\) + s)- pesan tuan,\(\mu\)+s saya relatif terhadap pk kunci barunya r,\(\mu\)+s saya = (i, r, \(\mu\) + s). Tentu saja untuk memverifikasi tanda tangan ini dari i, yang lain perlu memastikan bahwa kunci publik ini sesuai dengan PMK kunci publik i yang baru. Jadi, selain tanda tangan ini, saya mengirimkan tanda tangan digital PMK relatif terhadap pkr,\(\mu\) saya . Tentu saja, pendekatan ini dapat diulang sebanyak yang diperlukan jika putaran r terus berlanjut untuk lebih banyak langkah! Kunci rahasia sementara terakhir digunakan untuk mengautentikasi publik master baru kunci, dan dengan demikian kumpulan kunci fana lainnya untuk putaran r. Dan sebagainya.6.3 Protokol Sebenarnya Algorand ′ 2 Ingat kembali bahwa, pada setiap langkah s pada putaran r, pemverifikasi i \(\in\)SV r,s menggunakan rahasia publik jangka panjangnya pasangan kunci untuk menghasilkan kredensialnya, \(\sigma\)r,s saya \(\triangleq\)SIGi(r, s, Qr−1), serta SIGi Qr−1 dalam kasus s = 1. Verifier i menggunakan pasangan kunci fana miliknya, (pkr,s saya, skr, s i ), untuk menandatangani pesan lain yang mungkin ada diperlukan. Untuk mempermudah, kami menulis esigi(m), bukan sigpkr,s i (m), untuk menunjukkan kefanaan i yang sebenarnya tanda tangan m pada langkah ini, dan tulis ESIGi(m) sebagai pengganti SIGpkr,s saya (m) \(\triangleq\)(saya, m, esigi(m)). Langkah 1: Blokir Proposal Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 1 pada putaran r segera setelah ia menyelesaikannya CERT r−1, yang memungkinkan i menghitung H(Br−1) dan Qr−1 secara jelas. • Pengguna i menggunakan Qr−1 untuk memeriksa apakah i \(\in\)SV r,1 atau tidak. Jika i /\(\in\)SV r,1, dia tidak melakukan apa pun untuk Langkah 1. • Jika i \(\in\)SV r,1, yaitu jika i adalah calon pemimpin, maka ia melakukan hal berikut. (a) Jika saya telah melihat B0, . . . , Br−1 sendiri (setiap Bj = Bj ǫ dapat dengan mudah diturunkan dari nilai hash-nya di CERT j dan dengan demikian diasumsikan “terlihat”), lalu dia mengumpulkan pembayaran putaran-r yang dimilikinya telah disebarkan kepadanya sejauh ini dan menghitung pembayaran maksimal PAY r saya dari mereka. (b) Jika saya belum melihat semua B0, . . . , Br−1 lagi, lalu dia menetapkan PAY r saya = \(\emptyset\). (c) Selanjutnya, saya menghitung “blok kandidat” nya Br i = (r, BAYAR r saya , SIGi(Qr−1), H(Br−1)). (c) Akhirnya, saya menghitung pesan mr,1 saya = (Sdr saya , esigi(H(Br saya )), \(\sigma\)r,1 i ), menghancurkan kefanaannya kunci rahasia skr,1 i , dan kemudian menyebarkan dua pesan, mr,1 saya dan (SIGi(Qr−1), \(\sigma\)r,1 saya ), secara terpisah namun bersamaan.a aKetika i adalah pemimpinnya, SIGi(Qr−1) memungkinkan orang lain menghitung Qr = H(SIGi(Qr−1), r).

Propagasi Selektif Untuk mempersingkat pelaksanaan global Langkah 1 dan keseluruhan putaran, penting bahwa (r, 1)- pesan disebarkan secara selektif. Artinya, untuk setiap pengguna j dalam sistem, • Untuk (r, 1)-pesan pertama yang pernah diterimanya dan berhasil diverifikasi,a apakah pesan tersebut berisi sebuah blok atau hanya kredensial dan tanda tangan dari Qr−1, pemain j menyebarkannya seperti biasa. • Untuk semua pesan (r, 1) lainnya yang diterima dan berhasil diverifikasi oleh pemain j, ia menyebarkan hanya jika nilai hash dari kredensial yang dikandungnya adalah yang terkecil di antara nilai hash dari kredensial yang terkandung dalam semua (r, 1)-pesan yang telah dia terima dan berhasil diverifikasi jauh. • Namun, jika j menerima dua pesan berbeda dalam bentuk mr,1 saya dari pemain yang sama i,b he membuang yang kedua tidak peduli berapa pun nilai hash dari kredensial i. Perhatikan bahwa, dalam propagasi selektif, akan bermanfaat jika setiap pemimpin potensial menyebarkan idenya sendiri kredensial \(\sigma\)r,1 saya terpisah dari Tuan,1 i :c pesan-pesan kecil itu menyebar lebih cepat daripada blok, pastikan propagasi tepat waktu dari mr,1 di mana kredensial yang terkandung memiliki nilai hash yang kecil, sedangkan membuat yang memiliki nilai hash besar menghilang dengan cepat. aArtinya, semua tanda tangan sudah benar dan jika berbentuk bapak,1 i , blok dan hash-nya valid —walaupun j tidak memeriksa apakah payset yang disertakan sudah maksimal untuk i atau tidak. bYang berarti saya jahat. cKami berterima kasih kepada Georgios Vlachos yang telah menyarankan hal ini.Langkah 2: Langkah Pertama dari Protokol Konsensus Bertingkat GC Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 2 pada putaran r segera setelah ia menyelesaikannya CERT r−1. • Pengguna i menunggu selama waktu maksimum t2 \(\triangleq\) \(\lambda\) + Λ. Sambil menunggu, saya bertindak sebagai berikut. 1. Setelah menunggu waktu 2\(\lambda\), dia menemukan pengguna \(\ell\)sehingga H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) untuk semua kredensial \(\sigma\)r,1 j yang merupakan bagian dari pesan (r, 1) yang berhasil diverifikasi yang diterimanya sejauh ini.a 2. Jika dia memiliki diterima sebuah blok Br−1, yang mana cocok itu hash nilai H(Br−1) terkandung dalam CERT r−1,b dan jika dia telah menerima dari \(\ell\) pesan yang valid mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c lalu saya berhenti menunggu dan menyetel v′ i \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. Jika tidak, ketika waktu t2 habis, saya menetapkan v′ saya \(\triangleq\) \(\bot\). 4. Ketika nilai v′ i telah ditetapkan, i menghitung Qr−1 dari CERT r−1 dan memeriksa apakah i \(\in\)SV r,2 atau tidak. 5. Jika i \(\in\)SV r,2, i menghitung pesan mr,2 saya \(\triangleq\)(ESIGi(v′ saya), \(\sigma\)r,2 i ),d menghancurkan kefanaannya kunci rahasia skr,2 i , dan kemudian menyebarkan mr,2 saya. Jika tidak, saya berhenti tanpa menyebarkan apa pun. aPada dasarnya, pengguna i secara pribadi memutuskan bahwa pemimpin putaran r adalah pengguna \(\ell\). bTentu saja, jika CERT r−1 menunjukkan bahwa Br−1 = Br−1 ǫ , maka saya sudah “menerima” Br−1 pada saat dia menerimanya CERT r−1. cSekali lagi, tanda tangan pemain \(\ell\) dan hashes semuanya berhasil diverifikasi, dan MEMBAYAR r \(\ell\)di Br \(\ell\)adalah pembayaran yang valid untuk putaran r —walaupun saya tidak memeriksa apakah MEMBAYAR r \(\ell\)maksimal untuk \(\ell\)atau tidak. Jika Sdr \(\ell\)berisi set pembayaran kosong sebenarnya i tidak perlu melihat Br−1 sebelum memverifikasi apakah Br \(\ell\) valid atau tidak. dPesan Pak,2 saya memberi sinyal bahwa pemain i menganggap komponen pertama dari v′ saya menjadi hash blok berikutnya, atau menganggap blok berikutnya kosong.

Langkah 3: Langkah Kedua GC Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah ke-3 pada putaran r segera setelah ia menyelesaikannya CERT r−1. • Pengguna i menunggu selama waktu maksimum t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. Sambil menunggu, aku berperan sebagai berikut. 1. Jika terdapat nilai v sehingga dia telah menerima setidaknya pesan yang valid mr,2 j dari bentuk (ESIGj(v), \(\sigma\)r,2 j ), tanpa kontradiksi apa pun,a lalu dia berhenti menunggu dan mulai terbenam v′ = v. 2. Jika tidak, ketika waktu t3 habis, ia menetapkan v′ = \(\bot\). 3. Ketika nilai v′ telah ditetapkan, saya menghitung Qr−1 dari CERT r−1 dan memeriksa apakah i \(\in\)SV r,3 atau tidak. 4. Jika i \(\in\)SV r,3, maka i menghitung pesan mr,3 saya \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 i ), menghancurkan miliknya skr kunci rahasia sementara,3 i , dan kemudian menyebarkan mr,3 saya. Kalau tidak, aku akan berhenti tanpanya menyebarkan apa pun. aArtinya, dia belum menerima dua pesan valid yang masing-masing berisi ESIGj(v) dan ESIGj(ˆv) yang berbeda, dari pemain j. Di sini dan mulai sekarang, kecuali dalam Kondisi Akhir yang ditentukan nanti, kapan pun pemain jujur menginginkan pesan dalam bentuk tertentu, pesan yang bertentangan satu sama lain tidak pernah dihitung atau dianggap valid.

Langkah 4: Keluaran GC dan Langkah Pertama BBA⋆ Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkah 4 pada putaran r segera setelah dia menyelesaikan Langkah 3 miliknya sendiri. • Pengguna i menunggu selama waktu maksimum 2\(\lambda\).a Saat menunggu, i bertindak sebagai berikut. 1. Dia menghitung vi dan gi, keluaran dari GC, sebagai berikut. (a) Jika terdapat nilai v′ ̸= \(\bot\)sehingga dia telah menerima setidaknya pesan yang valid Tuan,3 j = (ESIGj(v′), \(\sigma\)r,3 j ), lalu dia berhenti menunggu dan menetapkan vi \(\triangleq\)v′ dan gi \(\triangleq\)2. (b) Jika dia telah menerima setidaknya pesan yang valid, Tuan,3 j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), lalu dia berhenti menunggu dan menyetel vi \(\triangleq\) \(\bot\)dan gi \(\triangleq\)0.b (c) Sebaliknya, ketika waktu 2\(\lambda\) habis, jika terdapat nilai v′ ̸= \(\bot\)sehingga ia mempunyai menerima setidaknya ⌈tH 2 ⌉pesan yang valid pak, j j = (ESIGj(v′), \(\sigma\)r,3 j ), lalu dia menetapkan vi \(\triangleq\)v′ dan gi \(\triangleq\)1.c (d) Jika tidak, ketika waktu 2\(\lambda\) habis, ia menetapkan vi \(\triangleq\) \(\bot\)dan gi \(\triangleq\)0. 2. Ketika nilai vi dan gi telah ditetapkan, i menghitung bi, masukan dari BBA⋆, sebagai berikut: bi \(\triangleq\)0 jika gi = 2, dan bi \(\triangleq\)1 jika tidak. 3. i menghitung Qr−1 dari CERT r−1 dan memeriksa apakah i \(\in\)SV r,4 atau tidak. 4. Jika i \(\in\)SV r,4, ia menghitung pesan mr,4 saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), menghancurkan miliknya skr kunci rahasia sementara,4 i , dan menyebarkan mr,4 saya. Jika tidak, saya berhenti tanpa menyebarkan apa pun. aJadi, total waktu maksimum sejak i memulai Langkah 1 pada putaran r adalah t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ. bApakah Langkah (b) ada dalam protokol atau tidak, tidak mempengaruhi kebenarannya. Namun, kehadiran Langkah (b) memungkinkan Langkah 4 berakhir dalam waktu kurang dari 2\(\lambda\) jika cukup banyak pemverifikasi Langkah-3 yang “menandatangani \(\bot\).” cDapat dibuktikan bahwa v′ dalam hal ini, jika ada, pasti unik.Langkah s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Langkah BBA⋆ Koin-Tetap-Ke-0 Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia menyelesaikan Langkahnya sendiri s −1. • Pengguna i menunggu selama waktu maksimum 2\(\lambda\).a Saat menunggu, i bertindak sebagai berikut. – Kondisi Akhir 0: Jika suatu titik terdapat string v ̸= \(\bot\)dan langkah s′ sedemikian rupa sehingga (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 —yaitu, Langkah s′ adalah langkah Koin-Tetap-Ke-0, (b) saya telah menerima setidaknya pesan yang valid tuan,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b dan (c) saya telah menerima pesan yang valid (SIGj(Qr−1), \(\sigma\)r,1 j ) dengan j menjadi yang kedua komponen v, kemudian, saya berhenti menunggu dan mengakhiri eksekusi Langkah s-nya sendiri (dan sebenarnya putaran r) segera tanpa menyebarkan apa pun sebagai pemverifikasi (r, s); menetapkan H(Br) menjadi yang pertama komponen v; dan menetapkan CERT r miliknya sendiri menjadi kumpulan pesan mr,s′−1 j langkah (b) bersama dengan (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Kondisi Akhir 1: Jika suatu saat terdapat langkah s′ sedemikian rupa (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 —yaitu, Langkah s′ adalah langkah Koin-Tetap-Ke-1, dan (b') saya telah menerima setidaknya pesan yang valid tuan,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d kemudian, saya berhenti menunggu dan mengakhiri eksekusinya sendiri pada Langkah s (dan sebenarnya putaran r) dengan benar pergi tanpa menyebarkan apa pun sebagai pemverifikasi (r, s); himpunan Br = Br ; dan menetapkan miliknya sendiri CERT r menjadi himpunan pesan mr,s′−1 j dari sub-langkah (b'). – Jika di apapun titik dia memiliki diterima di setidaknya itu sah Tuan, s−1 j itu dari itu bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia berhenti menunggu dan menyetel bi \(\triangleq\)1. – Jika di apapun titik dia memiliki diterima di setidaknya itu sah Tuan, s−1 j itu dari itu bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), tetapi mereka tidak sepakat pada v yang sama, lalu dia berhenti menunggu dan menyetel bi \(\triangleq\)0. – Jika tidak, ketika waktu 2\(\lambda\) habis, i menetapkan bi \(\triangleq\)0. – Ketika nilai bi telah ditetapkan, i menghitung Qr−1 dari CERT r−1 dan memeriksa apakah saya \(\in\)SV r,s. – Jika i \(\in\)SV r,s, i menghitung pesan mr,s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) dengan vi menjadi nilai yang telah dia hitung pada Langkah 4, menghancurkan skr,s kunci rahasia fananya saya, dan kemudian menyebarkan Tuan, s saya. Jika tidak, saya berhenti tanpa menyebarkan apa pun. aJadi, total waktu maksimum sejak i memulai Langkah 1 pada putaran r adalah ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. bPesan seperti itu dari pemain j dihitung meskipun pemain i juga menerima pesan dari j yang menandatangani untuk 1. Hal serupa untuk Kondisi Akhir 1. Seperti yang ditunjukkan dalam analisis, ini untuk memastikan bahwa semua pengguna yang jujur mengetahuinya CERT r dalam waktu \(\lambda\) satu sama lain. Pengguna i sekarang mengetahui H(Br) dan penyelesaian putarannya sendiri. Dia hanya perlu menunggu hingga blok Br benar-benar berada disebarkan kepadanya, yang mungkin memerlukan waktu tambahan. Dia masih membantu menyebarkan pesan sebagai pengguna umum, tetapi tidak memulai propagasi apa pun sebagai pemverifikasi (r, s). Secara khusus, dia telah membantu menyebarkan semua pesan di dalamnya CERT r-nya, yang cukup untuk protokol kami. Perhatikan bahwa ia juga harus menetapkan bi \(\triangleq\)0 untuk protokol biner BA, tapi bi tidak diperlukan dalam hal ini. Hal serupa untuk semua instruksi di masa depan. dDalam hal ini, tidak peduli apa vjnya. 65Langkah s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Langkah BBA⋆ Koin-Tetap-Ke-1 Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia menyelesaikan Langkahnya sendiri s −1. • Pengguna i menunggu maksimal 2\(\lambda\). Sambil menunggu, saya bertindak sebagai berikut. – Kondisi Akhir 0: Instruksi yang sama seperti pada langkah Koin-Tetap-Ke-0. – Kondisi Akhir 1: Instruksi yang sama seperti pada langkah Koin-Tetap-Ke-0. – Jika di apapun titik dia memiliki diterima di setidaknya itu sah Tuan, s−1 j itu dari itu bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia berhenti menunggu dan menyetel bi \(\triangleq\)0.a – Jika tidak, ketika waktu 2\(\lambda\) habis, i menetapkan bi \(\triangleq\)1. – Ketika nilai bi telah ditetapkan, i menghitung Qr−1 dari CERT r−1 dan memeriksa apakah saya \(\in\)SV r,s. – Jika i \(\in\)SV r,s, i menghitung pesan mr,s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) dengan vi menjadi nilai yang telah dia hitung pada Langkah 4, menghancurkan skr,s kunci rahasia fananya saya, dan kemudian menyebarkan Tuan, s saya. Jika tidak, saya berhenti tanpa menyebarkan apa pun. aPerhatikan bahwa menerima pesan valid (r, s −1) yang ditandatangani untuk 1 berarti Kondisi Akhir 1. Langkah s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Langkah BBA⋆ yang Benar-Benar Dibalik Koin Instruksi untuk setiap pengguna i \(\in\)PKr−k: Pengguna i memulai Langkahnya sendiri pada putaran r segera setelah dia menyelesaikan langkahnya sendiri s −1. • Pengguna i menunggu maksimal 2\(\lambda\). Sambil menunggu, saya bertindak sebagai berikut. – Kondisi Akhir 0: Instruksi yang sama seperti pada langkah Koin-Tetap-Ke-0. – Kondisi Akhir 1: Instruksi yang sama seperti pada langkah Koin-Tetap-Ke-0. – Jika di apapun titik dia memiliki diterima di setidaknya itu sah Tuan, s−1 j itu dari itu bentuk (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia berhenti menunggu dan menyetel bi \(\triangleq\)0. – Jika di apapun titik dia memiliki diterima di setidaknya itu sah Tuan, s−1 j itu dari itu bentuk (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), lalu dia berhenti menunggu dan menyetel bi \(\triangleq\)1. – Jika tidak, ketika waktu 2\(\lambda\) habis, biarkan SV r,s−1 saya menjadi himpunan (r, s −1)-pengukur dari kepada siapa dia telah menerima pesan yang valid tuan,s−1 j , saya menyetel bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 saya H(\(\sigma\)r,s−1 j )). – Ketika nilai bi telah ditetapkan, i menghitung Qr−1 dari CERT r−1 dan memeriksa apakah saya \(\in\)SV r,s. – Jika i \(\in\)SV r,s, i menghitung pesan mr,s saya \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) dengan vi menjadi nilai yang telah dia hitung pada Langkah 4, menghancurkan skr,s kunci rahasia fananya saya, dan kemudian menyebarkan Tuan, s saya. Jika tidak, saya berhenti tanpa menyebarkan apa pun. Komentar. Pada prinsipnya, sebagaimana dibahas dalam sub-bagian 6.2, protokol dapat mengambil banyak hal secara sewenang-wenang langkah dalam beberapa putaran. Jika hal ini terjadi, seperti yang dibahas, pengguna i \(\in\)SV r,s dengan s > \(\mu\) telah habis

simpanan kunci sementara yang telah dibuat sebelumnya dan harus mengautentikasi pesan (r, s)-nya, mr,s saya oleh a “cascade” dari kunci-kunci fana. Dengan demikian pesan saya menjadi sedikit lebih panjang dan penyampaiannya menjadi lebih lama pesan akan memakan waktu lebih lama. Oleh karena itu, setelah begitu banyak langkah dalam suatu putaran tertentu, nilai parameter \(\lambda\) secara otomatis akan meningkat sedikit. (Tetapi itu kembali ke \(\lambda\) asli sekali lagi blok diproduksi dan babak baru dimulai.) Rekonstruksi Blok Round-r oleh Non-Verifiers Petunjuk untuk setiap pengguna i dalam sistem: Pengguna i memulai putarannya sendiri r segera setelah ia melakukannya CERT r−1. • Saya mengikuti instruksi dari setiap langkah protokol, berpartisipasi dalam penyebaran semuanya pesan, tetapi tidak memulai propagasi apa pun dalam suatu langkah jika dia bukan pemverifikasi di dalamnya. • i mengakhiri putarannya sendiri r dengan memasukkan Kondisi Akhir 0 atau Kondisi Akhir 1 di beberapa bagian langkah, dengan CERT r yang sesuai. • Dari sana, dia memulai putarannya r + 1 sambil menunggu untuk menerima blok Br yang sebenarnya (kecuali dia sudah menerimanya), yang hash H(Br)-nya telah ditembaki oleh CERT r. Sekali lagi, jika CERT r menunjukkan bahwa Br = Br ǫ, saya tahu Br saat dia memiliki CERT r. 6.4 Analisis Algorand′ 2 Analisis Algorand′ 2 dengan mudah diturunkan dari Algorand ′ 1. Intinya, di Algorand ′ 2, dengan kemungkinan besar, (a) semua pengguna yang jujur menyetujui blok yang sama Br; pemimpin yang baru blok jujur dengan probabilitas paling sedikit ph = h2(1 + h −h2).

Menangani pengguna Offline Jujur

Seperti yang kami katakan, pengguna yang jujur mengikuti semua instruksi yang ditentukan, termasuk instruksi online dan menjalankan protokol. Hal ini tidak menjadi beban besar di Algorand, karena perhitungan dan bandwidth yang dibutuhkan dari pengguna yang jujur cukup sederhana. Namun, izinkan kami menunjukkan bahwa Algorand bisa dapat dengan mudah dimodifikasi agar dapat berfungsi dalam dua model, di mana pengguna yang jujur diperbolehkan untuk offline di angka yang besar. Sebelum membahas kedua model ini, mari kita tunjukkan persentase pemain yang jujur adalah 95%, Algorand masih dapat dijalankan dengan mengatur semua parameter dengan asumsi h = 80%. Oleh karena itu, Algorand akan terus berfungsi dengan baik meskipun sebagian besar pemain jujur memilih untuk offline (memang merupakan kasus utama “ketidakhadiran”). Faktanya, setidaknya kapan saja 80% pemain online akan jujur. Dari Partisipasi Terus-menerus hingga Kejujuran yang Malas Seperti yang kita lihat, Algorand ′ 1 dan Algorand′ 2 pilih parameter lihat kembali k. Sekarang mari kita tunjukkan bahwa memilih k yang besar dengan benar memungkinkan seseorang untuk menghapus persyaratan Partisipasi Berkelanjutan. Persyaratan ini memastikan properti penting: yaitu, bahwa protokol BA yang mendasari BBA⋆memiliki mayoritas yang jujur. Sekarang mari kita jelaskan betapa malasnya kejujuran memberikan cara alternatif dan menarik untuk memuaskan properti ini.

Ingatlah bahwa pengguna i malas-tapi-jujur jika (1) dia mengikuti semua instruksi yang ditentukan, kapan dia diminta untuk berpartisipasi dalam protokol, dan (2) dia diminta untuk berpartisipasi dalam protokol saja sangat jarang —misalnya, seminggu sekali— dengan pemberitahuan awal yang sesuai, dan berpotensi menerima penerimaan yang signifikan imbalan ketika dia berpartisipasi. Untuk mengizinkan Algorand bekerja dengan pemain seperti itu, cukup dengan “memilih pemverifikasi putaran saat ini di antara pengguna yang sudah berada dalam sistem pada putaran sebelumnya.” Memang benar, ingatlah itu pemverifikasi untuk putaran r dipilih dari pengguna pada putaran r −k, dan pemilihan dibuat berdasarkan pada kuantitas Qr−1. Perhatikan bahwa seminggu terdiri dari sekitar 10.000 menit, dan asumsikan bahwa a putaran memakan waktu kira-kira (misalnya, rata-rata) 5 menit, jadi dalam seminggu ada sekitar 2.000 putaran. Asumsikan bahwa, pada suatu saat, pengguna ingin merencanakan waktunya dan mengetahui apakah dia akan merencanakan waktunya pemverifikasi dalam minggu mendatang. Protokol sekarang memilih pemverifikasi untuk putaran r dari pengguna di putaran r −k −2.000, dan pilihannya didasarkan pada Qr−2.001. Pada ronde r, pemain yang sudah saya kenal nilai Qr−2,000, . . . , Qr−1, karena mereka sebenarnya adalah bagian dari blockchain. Kemudian, untuk setiap M antara 1 dan 2.000, i adalah pemverifikasi pada langkah s pada putaran r + M jika dan hanya jika .H SIGi r + M, s, Qr+M−2,001 \(\leq\)p. Jadi, untuk memeriksa apakah dia akan dipanggil untuk bertindak sebagai verifikator dalam 2.000 putaran berikutnya, saya harus hitung \(\sigma\)M,s saya = SIGi r + M, s, Qr+M−2,001 untuk M = 1 sampai 2.000 dan untuk setiap langkah s, dan periksa apakah .H(\(\sigma\)M,s saya ) \(\leq\)p untuk beberapa di antaranya. Jika penghitungan tanda tangan digital membutuhkan waktu satu milidetik, maka seluruh operasi ini akan memakan waktu sekitar 1 menit komputasi. Jika dia tidak terpilih sebagai verifikator di salah satu ronde ini, maka dia bisa offline dengan “hati nurani yang jujur”. Apakah dia terus menerus berpartisipasi, pada dasarnya dia akan mengambil 0 langkah dalam 2.000 putaran berikutnya! Sebaliknya, jika dia terpilih menjadi verifier di salah satu putaran ini, lalu dia mempersiapkan diri (misalnya, dengan mendapatkan semua informasi yang diperlukan) untuk bertindak sebagai verifikator yang jujur pada putaran yang tepat. Dengan bertindak demikian, calon verifikator yang malas tapi jujur hanya akan ketinggalan berpartisipasi dalam propagasi pesan. Namun penyebaran pesan biasanya kuat. Selain itu, pembayar dan penerima pembayaran pembayaran yang baru-baru ini disebarkan diharapkan online untuk melihat apa yang terjadi pada pembayaran mereka, dan dengan demikian mereka akan berpartisipasi dalam penyebaran pesan, jika mereka jujur.

Protokol Algorand ′ dengan Mayoritas Uang yang Jujur

Kini, pada akhirnya, kami menunjukkan cara mengganti asumsi Mayoritas Pengguna yang Jujur dengan asumsi yang lebih banyak lagi asumsi Mayoritas Uang yang Jujur dan bermakna. Ide dasarnya adalah (dalam rasa proof-of-stake) “untuk memilih pengguna i \(\in\)PKr−k untuk menjadi anggota SV r,s dengan bobot (yaitu, kekuatan keputusan) sebanding dengan jumlah uang yang dimiliki oleh i.”24 Dengan asumsi HMM kita, kita dapat memilih apakah jumlah tersebut harus dimiliki pada putaran r −k atau di (awal) putaran r. Dengan asumsi bahwa kami tidak keberatan dengan partisipasi terus-menerus, kami memilih untuk ikut serta pilihan terakhir. (Untuk menghilangkan partisipasi yang berkelanjutan, kita akan memilih pilihan yang pertama. Lebih baik dikatakan, untuk jumlah uang yang dimiliki pada putaran r −k −2, 000.) Ada banyak cara untuk mengimplementasikan ide ini. Cara paling sederhana adalah dengan menahan setiap kunci paling banyak 1 satuan uang lalu pilih secara acak n pengguna i dari PKr−k sehingga a(r) saya = 1. 24Kita harus menyatakan PKr−k−2.000 untuk menggantikan partisipasi yang berkelanjutan. Untuk kesederhanaan, karena seseorang mungkin ingin membutuhkannya bagaimanapun, kita tetap menggunakan PKr−k seperti sebelumnya, sehingga mengurangi satu parameter.

Implementasi Paling Sederhana Berikutnya Implementasi paling sederhana berikutnya adalah dengan menuntut agar setiap kunci publik memiliki jumlah maksimum uang M, untuk beberapa M tetap. Nilai M cukup kecil dibandingkan dengan jumlah total uang dalam sistem, sedemikian rupa sehingga kemungkinan suatu kunci dimiliki oleh himpunan pemverifikasi lebih dari satu langkah dalam —katakanlah— k putaran dapat diabaikan. Kemudian, kunci i \(\in\)PKr−k, memiliki sejumlah uang a(r) saya pada putaran r, dipilih menjadi anggota SV r,s jika .H SIGi r, s, Qr−1 \(\leq\)p \(\cdot\) a(r) saya M . Dan semuanya berjalan seperti sebelumnya. Implementasi yang Lebih Kompleks Implementasi terakhir “memaksa peserta kaya dalam sistem untuk memiliki banyak kunci”. Implementasi alternatif, dijelaskan di bawah, menggeneralisasi pengertian status dan pertimbangan setiap pengguna i terdiri dari K + 1 salinan (i, v), yang masing-masing dipilih secara independen untuk menjadi pemverifikasi, dan akan memiliki kunci fananya sendiri (pkr,s saya,v,skr,s i,v) dalam satu langkah s pada putaran r. Nilai K tergantung pada jumlah uang a(r) saya dimiliki oleh i pada putaran r. Sekarang mari kita lihat bagaimana sistem tersebut bekerja secara lebih rinci. Jumlah Salinan Misalkan n adalah kardinalitas yang diharapkan dari masing-masing himpunan pemverifikasi, dan misalkan a(r) saya menjadi jumlah uang yang dimiliki oleh pengguna i pada putaran r. Misalkan Ar adalah jumlah uang yang dimiliki oleh pengguna di PKr−k pada putaran r, yaitu, Ar = X i\(\in\)P Kr−k sebuah (kanan) saya. Jika i adalah pengguna di PKr−k, maka salinan i adalah (i, 1), . . . , (i, K + 1), dimana K = $ n \(\cdot\) sebuah(r) saya Ar % . Contoh. Misal n = 1.000, Ar = 109, dan a(r) saya = 3,7 juta. Lalu, K = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3.7⌋= 3 . Verifikasi dan Kredensial Biarkan saya menjadi pengguna di PKr−k dengan K + 1 salinan. Untuk setiap v = 1, . . . , K, salin (i, v) milik SV r,s secara otomatis. Artinya, kredensial saya adalah \(\sigma\)r, s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), namun kondisinya menjadi .H(\(\sigma\)r,s i,v) \(\leq\)1, yaitu selalu benar. Untuk salinan (i, K + 1), untuk setiap Langkah s pada putaran r, i memeriksa apakah .H SIGi (saya, K + 1), r, s, Qr−1 \(\leq\)a(r) saya n Ar −K .

Jika ya, salinan (i, K + 1) milik SV r,s. Untuk membuktikannya, saya menyebarkan kredensial \(\sigma\)r,1 saya,K+1 = SIGi (saya, K + 1), r, s, Qr−1 . Contoh. Seperti pada contoh sebelumnya, misalkan n = 1K, a(r) saya = 3,7M, Ar = 1B, dan i punya 4 salinan: (i, 1), . . . , (saya, 4). Kemudian, 3 salinan pertama menjadi milik SV r,s secara otomatis. Untuk yang ke 4, secara konseptual, Algorand ′ secara mandiri melempar koin yang bias, yang probabilitas Kepalanya adalah 0,7. Salin (i, 4) dipilih jika dan hanya jika pelemparan koin adalah Kepala. (Tentu saja, pelemparan koin yang bias ini diterapkan dengan hashing, menandatangani, dan membandingkan —seperti yang kita lakukan telah saya lakukan selama ini dalam makalah ini— sehingga memungkinkan saya membuktikan hasilnya.) Bisnis seperti Biasa Setelah menjelaskan bagaimana verifikator dipilih dan bagaimana kredensial mereka dihitung pada setiap langkah putaran r, pelaksanaan putaran serupa dengan yang telah dijelaskan.

Menangani Fork

Setelah mengurangi kemungkinan percabangan menjadi 10−12 atau 10−18, hal ini praktis tidak perlu ditangani mereka dalam kemungkinan kecil hal itu terjadi. Algorand, bagaimanapun, juga dapat menggunakan berbagai fork prosedur penyelesaian, dengan atau tanpa bukti kerja. Salah satu cara yang mungkin untuk menginstruksikan pengguna untuk menyelesaikan percabangan adalah sebagai berikut: • Ikuti rantai terpanjang jika pengguna melihat beberapa rantai. • Jika terdapat lebih dari satu rantai terpanjang, ikuti rantai yang tidak ada blok kosong di ujungnya. Jika semuanya memiliki blok kosong di akhir, pertimbangkan blok kedua terakhirnya. • Jika terdapat lebih dari satu rantai terpanjang dengan blok-blok kosong di ujungnya, katakanlah rantai tersebut adalah dengan panjang r, ikuti salah satu yang pemimpin blok r mempunyai kredensial terkecil. Jika ada ikatan, ikuti yang blok rnya sendiri memiliki nilai hash terkecil. Jika masih ada ikatan, ikuti yang blok rnya diurutkan pertama secara leksikografis.

Menangani Partisi Jaringan

Seperti yang dikatakan, kami berasumsi waktu propagasi pesan di antara semua pengguna di jaringan dibatasi oleh \(\lambda\) dan Λ. Ini bukanlah asumsi yang kuat, karena Internet saat ini cepat dan tangguh nilai sebenarnya dari parameter ini cukup masuk akal. Di sini, izinkan kami menunjukkan bahwa Algorand ′ 2 terus berfungsi meskipun Internet kadang-kadang dipartisi menjadi dua bagian. Kasus kapan Internet dipartisi menjadi lebih dari dua bagian serupa. 10.1 Partisi Fisik Pertama-tama, partisi tersebut mungkin disebabkan oleh alasan fisik. Misalnya, gempa bumi besar mungkin terjadi akhirnya memutuskan hubungan antara Eropa dan Amerika. Dalam hal ini, pengguna jahat juga dipartisi dan tidak ada komunikasi antara kedua bagian. Jadi

akan ada dua Musuh, satu untuk bagian 1 dan satu lagi untuk bagian 2. Masing-masing Musuh masih mencoba untuk melanggar protokol di bagiannya sendiri. Asumsikan partisi terjadi di tengah putaran r. Kemudian setiap pengguna masih dipilih sebagai a verifier berdasarkan PKr−k, dengan probabilitas yang sama seperti sebelumnya. Biarkan HSV r,s saya dan MSV r,s saya masing-masing jadilah himpunan pemverifikasi yang jujur dan jahat dalam langkah s di bagian i \(\in\){1, 2}. Kita punya |HSV r,s 1 | + |MSV r,s 1 | + |HSV r,s 2 | + |MSV r,s 2 | = |HSV r,s| + |MSV r,s|. Perhatikan bahwa |HSV r,s| + |MSV r,s| < |HSV r,s| + 2|MSV r,s| < 2tH dengan kemungkinan yang sangat besar. Jika beberapa bagian saya memiliki |HSV r,s saya | + |MSV r,s saya | \(\geq\)tH dengan probabilitas yang tidak dapat diabaikan, misalnya 1%, maka probabilitas bahwa |HSV r,s 3−i| + |MSV r,s 3−i| \(\geq\)tH sangat rendah, misalnya 10−16 ketika F = 10−18. Dalam hal ini, sebaiknya kita menganggap bagian yang lebih kecil saja tidak berfungsi, karena tidak akan ada cukup verifikasi yang masuk bagian ini untuk menghasilkan tanda tangan untuk mengesahkan suatu blok. Mari kita pertimbangkan bagian yang lebih besar, katakanlah bagian 1 tanpa kehilangan sifat umum. Meskipun |HSV r,s| < tH dengan probabilitas yang dapat diabaikan di setiap langkah s, ketika jaringan dipartisi, |HSV r,s 1 | mungkin kurang dari tH dengan probabilitas yang tidak dapat diabaikan. Dalam hal ini Musuh mungkin, dengan beberapa pihak probabilitas lain yang tidak dapat diabaikan, memaksa protokol biner BA menjadi percabangan pada putaran r, dengan blok kosong Br dan blok kosong Br ǫ keduanya mempunyai tanda tangan yang sah.25 Misalnya, pada a Langkah Koin-Tetap-Ke-0, semua verifier di HSV r,s 1 ditandatangani untuk bit 0 dan H(Br), dan menyebarkannya pesan. Semua pemverifikasi di MSV r,s 1 juga menandatangani 0 dan H(Br), tetapi menahan pesan mereka. Karena |HSV r,s 1 | + |MSV r,s 1 | \(\geq\)tH, sistem mempunyai cukup tanda tangan untuk mengesahkan Br. Namun, sejak itu pemverifikasi jahat menahan tanda tangan mereka, pengguna memasukkan langkah s + 1, yang merupakan langkah Coin-Fixed-To1. Karena |HSV r,s 1 | < tH karena partisi, pemverifikasi di HSV r,s+1 1 tidak melihat itu tanda tangan untuk bit 0 dan semuanya menandatangani untuk bit 1. Semua verifier di MSV r,s+1 1 melakukan hal yang sama. Karena |HSV r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH, sistem mempunyai cukup tanda tangan untuk mengesahkan Br . Musuh kemudian membuat fork dengan melepaskan tanda tangan MSV r,s 1 untuk 0 dan H(Br). Oleh karena itu, akan ada dua Qr, yang ditentukan oleh blok-blok putaran r yang bersesuaian. Namun, percabangan tidak akan berlanjut dan hanya satu dari dua cabang yang dapat tumbuh pada putaran r + 1. Petunjuk Tambahan untuk Algorand ′ 2. Saat melihat blok Br yang tidak kosong dan kosong blok Br ǫ , ikuti yang tidak kosong (dan Qr yang ditentukan olehnya). Memang benar, dengan menginstruksikan pengguna untuk menggunakan blok yang tidak kosong dalam protokol, jika berukuran besar sejumlah pengguna jujur di PKr+1−k menyadari ada percabangan di awal putaran r +1, maka blok kosong tidak akan memiliki cukup pengikut dan tidak akan berkembang. Asumsikan Musuh berhasil melakukannya partisi pengguna yang jujur sehingga beberapa pengguna yang jujur melihat Br (dan mungkin Br ǫ), dan ada pula yang hanya melihat Sdr . Karena Musuh tidak bisa membedakan mana di antara mereka yang akan menjadi verifikasi setelah Br dan yang mana akan menjadi verifikator menyusul Sdr , pengguna yang jujur dipartisi secara acak dan masing-masing pengguna tetap menjadi verifikator (baik terhadap Br maupun terhadap Br ǫ) dalam satu langkah s > 1 dengan probabilitas hal. Untuk pengguna jahat, masing-masing dari mereka mungkin memiliki dua peluang untuk menjadi pemverifikasi, satu dengan Br dan satu lagi dengan Br ǫ, masing-masing dengan probabilitas p secara independen. Misalkan HSV r+1,s 1;Br jadilah himpunan verifikator yang jujur pada langkah s putaran r+1 setelah Br. Notasi lainnya seperti HSV r+1,s 1;Br, MSV r+1,s 1;Br dan MSV r+1,s 1;Br didefinisikan dengan cara yang sama. Dengan terikat Cherno, itu mudah 25Memiliki percabangan dengan dua blok yang tidak kosong tidak mungkin dilakukan dengan atau tanpa partisi, kecuali dengan partisi yang dapat diabaikan. kemungkinan.untuk melihatnya dengan kemungkinan yang sangat besar, |HSV r+1,s 1;Br | + |HSV r+1,s 1;Br| + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Br| < 2tH. Oleh karena itu, kedua cabang tidak dapat memiliki tanda tangan yang tepat untuk mengesahkan blok untuk putaran r + 1 pada langkah yang sama s. Terlebih lagi, karena probabilitas seleksi untuk dua langkah s dan s′ adalah sama dan pilihannya independen, juga dengan kemungkinan yang sangat besar |HSV r+1,s 1;Br | + |MSV r+1,s 1;Br | + |HSV r+1,s′ 1;Br | + |MSV r+1,s′ 1;Br | < 2tH, untuk dua langkah s dan s′. Ketika F = 10−18, dengan ikatan gabungan, selama Musuh tidak bisa mempartisi pengguna yang jujur untuk waktu yang lama (katakanlah 104 langkah, yaitu lebih dari 55 jam dengan \(\lambda\) = 10 detik26), dengan probabilitas tinggi (katakanlah 1−10−10) paling banyak satu cabang akan memiliki tanda tangan yang tepat untuk mensertifikasi blok di putaran r + 1. Terakhir, jika partisi fisik telah membuat dua bagian dengan ukuran yang kira-kira sama, maka probabilitas bahwa |HSV r,s saya | + |MSV r,s saya | \(\geq\)tH kecil untuk setiap bagian i. Mengikuti analisis serupa, bahkan jika Musuh berhasil membuat percabangan dengan probabilitas yang tidak dapat diabaikan di setiap bagiannya untuk putaran r, paling banyak satu dari empat cabang dapat tumbuh pada putaran r + 1. 10.2 Partisi Musuh Kedua, partisi tersebut mungkin disebabkan oleh Musuh, sehingga pesan disebarkan oleh pengguna jujur di satu bagian tidak akan menjangkau pengguna jujur di bagian lain secara langsung, namun Musuh mampu meneruskan pesan antara dua bagian. Tetap saja, pernah ada pesan dari seseorang bagian mencapai pengguna yang jujur di bagian lain, itu akan disebarkan di pengguna yang jujur seperti biasa. Jika Musuh rela mengeluarkan banyak uang, bisa dibayangkan dia bisa meretasnya Internet dan partisi seperti ini untuk sementara waktu. Analisisnya mirip dengan bagian yang lebih besar pada partisi fisik di atas (yang lebih kecil bagian dapat dianggap memiliki populasi 0): Musuh mungkin dapat membuat garpu dan setiap pengguna yang jujur hanya melihat satu cabang, tetapi paling banyak satu cabang dapat tumbuh. 10.3 Partisi Jaringan dalam Jumlah Meskipun partisi jaringan dapat terjadi dan percabangan dalam satu putaran dapat terjadi di bawah partisi, namun demikian tidak ada ambiguitas yang tersisa: sebuah garpu berumur sangat pendek, dan pada kenyataannya hanya bertahan paling banyak satu putaran. Di semua bagian partisi kecuali paling banyak satu, pengguna tidak dapat membuat blok baru dan karenanya (a) menyadari adanya partisi dalam jaringan dan (b) jangan pernah mengandalkan blok yang akan “hilang”. Ucapan Terima Kasih Pertama-tama kami ingin mengucapkan terima kasih kepada Sergey Gorbunov, salah satu penulis sistem Democoin yang dikutip. Terima kasih yang paling tulus kami sampaikan kepada Maurice Herlihy, atas banyak diskusi yang mencerahkan, atas petunjuknya mengetahui bahwa pipeline akan meningkatkan kinerja throughput Algorand, dan untuk meningkatkan secara signifikan 26Perhatikan bahwa pengguna menyelesaikan langkah tanpa menunggu 2\(\lambda\) waktu hanya jika dia telah melihat setidaknya tanda tangan untuk pesan yang sama. Jika tanda tangan tidak mencukupi, setiap langkah akan berlangsung selama 2\(\lambda\) kali.

eksposisi versi sebelumnya dari makalah ini. Terima kasih banyak kepada Sergio Rajsbaum, atas komentarnya versi sebelumnya dari makalah ini. Terima kasih banyak kepada Vinod Vaikuntanathan, atas beberapa diskusi mendalam dan wawasan. Terima kasih banyak kepada Yossi Gilad, Rotem Hamo, Georgios Vlachos, dan Nickolai Zeldovich untuk mulai menguji ide-ide ini, dan untuk banyak komentar dan diskusi yang bermanfaat. Silvio Micali secara pribadi ingin mengucapkan terima kasih kepada Ron Rivest atas diskusi dan bimbingannya yang tak terhitung jumlahnya dalam penelitian kriptografi selama lebih dari 3 dekade, karena ikut menulis sistem pembayaran mikro yang dikutip yang menginspirasi salah satu mekanisme seleksi verifikator Algorand. Kami berharap dapat membawa teknologi ini ke tingkat berikutnya. Sementara itu perjalanan dan persahabatan sangat menyenangkan, dan kami sangat berterima kasih.