Masalah perbelanjaan berganda dan jeneral-jeneral Byzantine

Ingin tahu

1. Jika fail digital boleh disalin dengan sempurna dan serta-merta, apa yang menghalangnya daripada digunakan dua kali?
2. Bagaimanakah sekumpulan orang asing yang tidak mempunyai identiti bersama dapat bersetuju mengenai sejarah yang sama tanpa pemimpin untuk menyelesaikan pertikaian?
3. Apa yang menjadikan undian dalam rangkaian terbuka lebih berharga daripada kata-kata orang lain?

Teroka

1. Token digital hanyalah sebuah fail. Berbeza dengan wang tunai fizikal, ia boleh disalin bit demi bit tanpa sebarang kos dan tanpa penurunan kualiti. Jika Alice menghantar sepuluh unit kepada Bob, dia tetap memegang fail asal dan boleh menghantar sepuluh unit yang sama kepada Charlie pada masa yang sama. Sehingga tahun 2008, setiap sistem wang tunai digital yang berfungsi bergantung pada penerbit yang dipercayai: skema dalam talian menyemak setiap pembayaran secara berpusat, manakala skema luar talian hanya dapat mengenal pasti pelaku perbelanjaan berganda selepas kejadian.
2. DigiCash ciptaan David Chaum mewajibkan setiap penerima bayaran mendepositkan syiling ke bank, yang menyemak setiap nombor siri dengan senarai syiling yang telah dibelanjakan. Reusable Proofs of Work ciptaan Hal Finney pula bergantung pada satu pelayan yang menjalankan kod sumber terbuka di atas perkakasan selamat untuk menjejak token yang telah dibelanjakan. b-money ciptaan Wei Dai mencadangkan pelayan yang meletakkan deposit dan boleh didenda jika menipu, tetapi ia tidak pernah dibina. Setiap reka bentuk ini mengekalkan pihak yang dipercayai, atau kumpulan yang diketahui, di pusatnya.
3. Pada tahun 1982, Leslie Lamport, Robert Shostak, dan Marshall Pease telah memformalkan Masalah Jeneral Byzantine dalam jurnal ACM Transactions on Programming Languages and Systems. Para jeneral yang mengelilingi sebuah bandar perlu bersetuju sama ada untuk menyerang atau berundur, tetapi ada di antara mereka yang merupakan pengkhianat yang menghantar mesej yang bercanggah; para utusan itu sendiri pula boleh dipercayai. Dengan mesej tanpa tandatangan, persetujuan hanya dapat dicapai jika kurang daripada satu pertiga jeneral merupakan pengkhianat (n ≥ 3f+1); sekiranya satu pertiga atau lebih yang menjadi pengkhianat, tiada protokol yang dapat menjaminnya.
4. Protokol toleransi kesalahan klasik seperti PBFT memerlukan sekumpulan peserta yang tetap dan diketahui. Pendekatan ini berkesan untuk buku akaun dalaman bank, tetapi gagal dalam rangkaian terbuka di mana sesiapa sahaja boleh menyertai. John Douceur mengenal pasti serangan Sybil pada tahun 2002: penyerang boleh menjana identiti palsu tanpa had untuk mencairkan undian yang jujur atau mengawal kuorum. Dalam rangkaian peer-to-peer yang terbuka, identiti murah dan tidak terhad, jadi sebarang skema yang mengira identiti boleh diambil alih oleh satu pihak sahaja.
5. Kertas putih Satoshi Nakamoto menangani perkara ini secara langsung. Abstraknya membentangkan bitcoin sebagai penyelesaian kepada perbelanjaan berganda tanpa pihak ketiga yang dipercayai. Daripada bergantung pada identiti atau kepercayaan institusi, sistem ini mengikat setiap blok kepada bukti kerja terkumpul. Undian ditimbang mengikut pengiraan, yang tidak boleh digandakan dengan mereka-reka identiti; penyerang perlu mengatasi kuasa pengiraan rangkaian yang jujur untuk menulis semula sejarah.
6. Hasilnya ialah kemuktamadan probabilistik. Sesuatu transaksi tidak muktamad secara kekal dari segi matematik, tetapi menjadi semakin selamat apabila setiap blok baharu memanjangkan rantaian. Selagi penyerang menguasai kurang daripada separuh kuasa hashing, peluang pembalikan berkurangan secara eksponen dengan setiap pengesahan. Kompromi ini menerima kemungkinan teori pembalikan demi mencapai ketakbolehubahan praktikal tanpa kawalan pusat. Buka peneroka blok dan perhatikan bagaimana kerja terkumpul bertambah dengan setiap ketinggian blok; kos terkumpul inilah yang menambat buku akaun kepada realiti fizikal.

Fakta utama

Latihan sembilan, enam, tiga, satu

Semakan fakta

Tarikh, angka dan dakwaan telah disemak berbanding dengan sumber yang diterbitkan yang disenaraikan di bawah.

• L. Lamport, R. Shostak, M. Pease, 'The Byzantine Generals Problem', ACM TOPLAS (1982)
• J. Douceur, 'The Sybil Attack', Peer-to-Peer Systems (2002)
• S. Nakamoto, 'Bitcoin: A Peer-to-Peer Electronic Cash System' (2008)
• M. Castro & B. Liskov, 'Practical Byzantine Fault Tolerance', OSDI (1999)