Биткоин: система электронных денег на основе одноранговой сети
Abstract
Sebuah versi murni peer-to-peer dari uang elektronik akan memungkinkan pembayaran online dikirim langsung dari satu pihak ke pihak lain tanpa melalui lembaga keuangan. Tanda tangan digital menyediakan sebagian dari solusi, tetapi manfaat utama akan hilang jika pihak ketiga yang tepercaya masih diperlukan untuk mencegah double-spending. Kami mengusulkan solusi untuk masalah double-spending menggunakan jaringan peer-to-peer. Jaringan memberi cap waktu pada transaksi dengan melakukan hash ke dalam rantai proof-of-work berbasis hash yang berkelanjutan, membentuk catatan yang tidak dapat diubah tanpa mengulang proof-of-work. Rantai terpanjang tidak hanya berfungsi sebagai bukti urutan peristiwa yang disaksikan, tetapi juga bukti bahwa rantai tersebut berasal dari kumpulan daya CPU terbesar. Selama mayoritas daya CPU dikendalikan oleh node yang tidak bekerja sama untuk menyerang jaringan, mereka akan menghasilkan rantai terpanjang dan mengungguli penyerang. Jaringan itu sendiri memerlukan struktur minimal. Pesan disiarkan berdasarkan upaya terbaik, dan node dapat meninggalkan dan bergabung kembali dengan jaringan sesuka hati, menerima rantai proof-of-work terpanjang sebagai bukti atas apa yang terjadi saat mereka pergi.
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Introduction
Perdagangan di Internet telah bergantung hampir sepenuhnya pada lembaga keuangan yang bertindak sebagai pihak ketiga tepercaya untuk memproses pembayaran elektronik. Meskipun sistem ini berfungsi cukup baik untuk sebagian besar transaksi, sistem ini masih mengalami kelemahan bawaan dari model berbasis kepercayaan. Transaksi yang benar-benar tidak dapat dibatalkan sebenarnya tidak mungkin dilakukan, karena lembaga keuangan tidak dapat menghindari mediasi sengketa. Biaya mediasi meningkatkan biaya transaksi, membatasi ukuran transaksi minimum yang praktis dan menghilangkan kemungkinan transaksi kecil kasual, dan ada biaya yang lebih luas dalam hilangnya kemampuan untuk melakukan pembayaran yang tidak dapat dibatalkan untuk layanan yang tidak dapat dibatalkan. Dengan kemungkinan pembatalan, kebutuhan akan kepercayaan menyebar. Pedagang harus waspada terhadap pelanggan mereka, mengganggu mereka untuk mendapatkan lebih banyak informasi daripada yang seharusnya mereka butuhkan. Persentase tertentu dari penipuan diterima sebagai hal yang tidak dapat dihindari. Biaya-biaya dan ketidakpastian pembayaran ini dapat dihindari secara langsung dengan menggunakan mata uang fisik, tetapi tidak ada mekanisme yang ada untuk melakukan pembayaran melalui saluran komunikasi tanpa pihak yang tepercaya.
Yang dibutuhkan adalah sistem pembayaran elektronik berdasarkan bukti kriptografi alih-alih kepercayaan, yang memungkinkan dua pihak yang bersedia untuk bertransaksi langsung satu sama lain tanpa memerlukan pihak ketiga yang tepercaya. Transaksi yang secara komputasional tidak praktis untuk dibatalkan akan melindungi penjual dari penipuan, dan mekanisme escrow rutin dapat dengan mudah diimplementasikan untuk melindungi pembeli. Dalam makalah ini, kami mengusulkan solusi untuk masalah double-spending menggunakan server cap waktu terdistribusi peer-to-peer untuk menghasilkan bukti komputasional dari urutan kronologis transaksi. Sistem ini aman selama node jujur secara kolektif mengendalikan lebih banyak daya CPU daripada kelompok node penyerang mana pun yang bekerja sama.
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Transactions
Kami mendefinisikan koin elektronik sebagai rantai tanda tangan digital. Setiap pemilik mentransfer koin ke pemilik berikutnya dengan menandatangani secara digital hash dari transaksi sebelumnya dan kunci publik (public key) pemilik berikutnya, lalu menambahkannya ke ujung koin. Penerima pembayaran dapat memverifikasi tanda tangan untuk memverifikasi rantai kepemilikan.
Masalahnya tentu saja adalah penerima tidak dapat memverifikasi bahwa salah satu pemilik tidak melakukan double-spending terhadap koin tersebut. Solusi umum adalah memperkenalkan otoritas pusat tepercaya, atau percetakan uang, yang memeriksa setiap transaksi untuk double-spending. Setelah setiap transaksi, koin harus dikembalikan ke percetakan uang untuk menerbitkan koin baru, dan hanya koin yang diterbitkan langsung dari percetakan uang yang dipercaya tidak di-double-spend. Masalah dengan solusi ini adalah nasib seluruh sistem uang bergantung pada perusahaan yang menjalankan percetakan uang, dengan setiap transaksi harus melewati mereka, sama seperti bank.
Kita membutuhkan cara bagi penerima untuk mengetahui bahwa pemilik sebelumnya tidak menandatangani transaksi yang lebih awal. Untuk tujuan kita, transaksi paling awal adalah yang dihitung, jadi kita tidak peduli tentang upaya double-spending selanjutnya. Satu-satunya cara untuk mengonfirmasi ketiadaan suatu transaksi adalah mengetahui semua transaksi. Dalam model berbasis percetakan uang, percetakan uang mengetahui semua transaksi dan memutuskan mana yang tiba lebih dulu. Untuk mencapai ini tanpa pihak tepercaya, transaksi harus diumumkan secara publik [^1], dan kita membutuhkan sistem bagi peserta untuk menyepakati satu riwayat urutan penerimaan. Penerima membutuhkan bukti bahwa pada saat setiap transaksi, mayoritas node menyetujui bahwa transaksi tersebut adalah yang pertama diterima.
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Timestamp Server
Solusi yang kami usulkan dimulai dengan server cap waktu. Server cap waktu bekerja dengan mengambil hash dari blok item yang akan diberi cap waktu dan mempublikasikan hash tersebut secara luas, seperti di surat kabar atau posting Usenet [^2] [^3] [^4] [^5]. Cap waktu membuktikan bahwa data pasti sudah ada pada saat itu, tentunya, agar dapat masuk ke dalam hash. Setiap cap waktu menyertakan cap waktu sebelumnya dalam hash-nya, membentuk rantai, dengan setiap cap waktu tambahan memperkuat yang sebelumnya.
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Proof-of-Work
Untuk mengimplementasikan server cap waktu terdistribusi secara peer-to-peer, kita perlu menggunakan sistem proof-of-work yang mirip dengan Hashcash milik Adam Back [^6], alih-alih surat kabar atau posting Usenet. Proof-of-work melibatkan pemindaian nilai yang ketika di-hash, seperti dengan SHA-256, hash-nya dimulai dengan sejumlah bit nol. Rata-rata kerja yang diperlukan bersifat eksponensial terhadap jumlah bit nol yang diperlukan dan dapat diverifikasi dengan mengeksekusi satu hash.
Untuk jaringan cap waktu kami, kami mengimplementasikan proof-of-work dengan menambah nonce di blok sampai ditemukan nilai yang memberikan hash blok jumlah bit nol yang diperlukan. Setelah upaya CPU dikeluarkan untuk memenuhi proof-of-work, blok tidak dapat diubah tanpa mengulangi pekerjaan. Karena blok-blok selanjutnya dirangkai setelahnya, pekerjaan untuk mengubah blok akan mencakup pengulangan semua blok setelahnya.
Proof-of-work juga memecahkan masalah penentuan representasi dalam pengambilan keputusan mayoritas. Jika mayoritas didasarkan pada satu-alamat-IP-satu-suara, itu bisa disubversi oleh siapa saja yang mampu mengalokasikan banyak IP. Proof-of-work pada dasarnya adalah satu-CPU-satu-suara. Keputusan mayoritas diwakili oleh rantai terpanjang, yang memiliki upaya proof-of-work terbesar yang diinvestasikan di dalamnya. Jika mayoritas daya CPU dikontrol oleh node jujur, rantai jujur akan tumbuh paling cepat dan mengungguli rantai pesaing manapun. Untuk memodifikasi blok masa lalu, penyerang harus mengulangi proof-of-work blok tersebut dan semua blok setelahnya, lalu mengejar dan melampaui pekerjaan node jujur. Kami akan menunjukkan nanti bahwa probabilitas penyerang yang lebih lambat mengejar berkurang secara eksponensial saat blok-blok berikutnya ditambahkan.
Untuk mengkompensasi peningkatan kecepatan perangkat keras dan variasi minat dalam menjalankan node dari waktu ke waktu, kesulitan proof-of-work ditentukan oleh rata-rata bergerak yang menargetkan rata-rata jumlah blok per jam. Jika dihasilkan terlalu cepat, kesulitannya meningkat.
Proof-of-Work
Для реализации распределенного сервера временных меток на одноранговой основе нам потребуется использовать систему proof-of-work, аналогичную Hashcash Адама Бэка [^6], вместо газет или постов Usenet. Proof-of-work включает поиск значения, хеш которого, например при использовании SHA-256, начинается с определенного количества нулевых битов. Средний объем работы, необходимый для этого, экспоненциально зависит от количества требуемых нулевых битов и может быть проверен выполнением одного хеширования.
Для нашей сети временных меток мы реализуем proof-of-work путем увеличения nonce в блоке до тех пор, пока не будет найдено значение, дающее хешу блока требуемое количество нулевых битов. После того как затрачена вычислительная мощность CPU для удовлетворения proof-of-work, блок не может быть изменен без повторного выполнения работы. Поскольку последующие блоки связываются после него, работа по изменению блока включала бы повторное выполнение всех блоков после него.
Proof-of-work также решает проблему определения представительства при принятии решений большинством. Если бы большинство определялось по принципу один-IP-адрес-один-голос, оно могло бы быть подорвано любым, кто способен выделить множество IP-адресов. Proof-of-work — это, по сути, один-CPU-один-голос. Решение большинства представлено самой длинной цепочкой, в которую вложен наибольший объем работы proof-of-work. Если большая часть мощности CPU контролируется честными узлами, честная цепочка будет расти быстрее всех и опережать любые конкурирующие цепочки. Чтобы изменить прошлый блок, атакующему пришлось бы повторно выполнить proof-of-work этого блока и всех последующих блоков, а затем догнать и превзойти работу честных узлов. Позже мы покажем, что вероятность того, что более медленный атакующий догонит, экспоненциально уменьшается по мере добавления последующих блоков.
Для компенсации возрастающей скорости оборудования и меняющегося интереса к запуску узлов с течением времени сложность proof-of-work определяется скользящим средним, нацеленным на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.
Network
Langkah-langkah untuk menjalankan jaringan adalah sebagai berikut:
- Transaksi baru disiarkan ke semua node.
- Setiap node mengumpulkan transaksi baru ke dalam sebuah blok.
- Setiap node bekerja untuk menemukan proof-of-work yang sulit untuk bloknya.
- Ketika sebuah node menemukan proof-of-work, node tersebut menyiarkan blok ke semua node.
- Node menerima blok hanya jika semua transaksi di dalamnya valid dan belum dibelanjakan.
- Node mengekspresikan penerimaan mereka terhadap blok dengan bekerja membuat blok berikutnya dalam rantai, menggunakan hash dari blok yang diterima sebagai hash sebelumnya.
Node selalu menganggap rantai terpanjang sebagai yang benar dan akan terus bekerja untuk memperpanjangnya. Jika dua node menyiarkan versi berbeda dari blok berikutnya secara bersamaan, beberapa node mungkin menerima satu atau yang lainnya terlebih dahulu. Dalam kasus itu, mereka bekerja pada yang pertama diterima, tetapi menyimpan cabang lainnya untuk berjaga-jaga jika menjadi lebih panjang. Seri akan diputuskan ketika proof-of-work berikutnya ditemukan dan satu cabang menjadi lebih panjang; node yang bekerja pada cabang lain kemudian akan beralih ke yang lebih panjang.
Siaran transaksi baru tidak harus mencapai semua node. Selama mereka mencapai banyak node, mereka akan masuk ke blok dalam waktu singkat. Siaran blok juga toleran terhadap pesan yang hilang. Jika sebuah node tidak menerima blok, node tersebut akan memintanya ketika menerima blok berikutnya dan menyadari bahwa ada yang terlewat.
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Incentive
Secara konvensi, transaksi pertama dalam sebuah blok adalah transaksi khusus yang memulai koin baru yang dimiliki oleh pembuat blok. Ini menambahkan insentif bagi node untuk mendukung jaringan, dan menyediakan cara untuk mendistribusikan koin ke dalam peredaran pada awalnya, karena tidak ada otoritas pusat untuk menerbitkannya. Penambahan tetap sejumlah koin baru secara stabil dianalogikan dengan penambang emas yang mengeluarkan sumber daya untuk menambahkan emas ke peredaran. Dalam kasus kita, yang dikeluarkan adalah waktu CPU dan listrik.
Insentif juga dapat didanai dengan biaya transaksi. Jika nilai output suatu transaksi kurang dari nilai inputnya, selisihnya adalah biaya transaksi yang ditambahkan ke nilai insentif blok yang berisi transaksi tersebut. Setelah sejumlah koin yang telah ditentukan masuk ke peredaran, insentif dapat beralih sepenuhnya ke biaya transaksi dan sepenuhnya bebas inflasi.
Insentif dapat membantu mendorong node untuk tetap jujur. Jika penyerang serakah mampu mengumpulkan lebih banyak daya CPU daripada semua node jujur, ia harus memilih antara menggunakannya untuk menipu orang dengan mencuri kembali pembayarannya, atau menggunakannya untuk menghasilkan koin baru. Ia seharusnya menemukan bahwa bermain sesuai aturan lebih menguntungkan, aturan yang memberinya lebih banyak koin baru daripada semua orang lain digabungkan, daripada merusak sistem dan validitas kekayaannya sendiri.
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Reclaiming Disk Space
Setelah transaksi terbaru dalam sebuah koin terkubur di bawah cukup banyak blok, transaksi yang sudah dibelanjakan sebelumnya dapat dibuang untuk menghemat ruang disk. Untuk memfasilitasi ini tanpa merusak hash blok, transaksi di-hash dalam Merkle Tree [^7] [^2] [^5], dengan hanya root yang disertakan dalam hash blok. Blok-blok lama kemudian dapat dipadatkan dengan memangkas cabang-cabang pohon. Hash interior tidak perlu disimpan.
Header blok tanpa transaksi akan berukuran sekitar 80 byte. Jika kita mengasumsikan blok dihasilkan setiap 10 menit, 80 byte * 6 * 24 * 365 = 4,2MB per tahun. Dengan sistem komputer yang biasanya dijual dengan RAM 2GB pada tahun 2008, dan Hukum Moore memprediksi pertumbuhan saat ini sebesar 1,2GB per tahun, penyimpanan seharusnya tidak menjadi masalah meskipun header blok harus disimpan di memori.
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Simplified Payment Verification
Dimungkinkan untuk memverifikasi pembayaran tanpa menjalankan node jaringan penuh. Pengguna hanya perlu menyimpan salinan header blok dari rantai proof-of-work terpanjang, yang bisa didapatkan dengan menanyakan node jaringan sampai yakin memiliki rantai terpanjang, dan mendapatkan cabang Merkle yang menghubungkan transaksi ke blok tempat transaksi tersebut diberi cap waktu. Pengguna tidak dapat memeriksa transaksi sendiri, tetapi dengan menghubungkannya ke tempat di rantai, pengguna dapat melihat bahwa node jaringan telah menerimanya, dan blok yang ditambahkan setelahnya semakin mengonfirmasi bahwa jaringan telah menerimanya.
Dengan demikian, verifikasi dapat diandalkan selama node jujur mengendalikan jaringan, tetapi lebih rentan jika jaringan dikuasai oleh penyerang. Sementara node jaringan dapat memverifikasi transaksi sendiri, metode yang disederhanakan dapat ditipu oleh transaksi palsu penyerang selama penyerang dapat terus menguasai jaringan. Satu strategi untuk melindungi terhadap ini adalah menerima peringatan dari node jaringan ketika mereka mendeteksi blok yang tidak valid, mendorong perangkat lunak pengguna untuk mengunduh blok penuh dan transaksi yang diperingatkan untuk mengonfirmasi inkonsistensi. Bisnis yang menerima pembayaran sering mungkin masih ingin menjalankan node mereka sendiri untuk keamanan yang lebih independen dan verifikasi yang lebih cepat.
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Combining and Splitting Value
Meskipun dimungkinkan untuk menangani koin secara individual, akan sangat merepotkan untuk membuat transaksi terpisah untuk setiap sen dalam transfer. Untuk memungkinkan nilai dipecah dan digabungkan, transaksi berisi banyak input dan output. Biasanya akan ada satu input dari transaksi sebelumnya yang lebih besar atau beberapa input yang menggabungkan jumlah lebih kecil, dan paling banyak dua output: satu untuk pembayaran, dan satu mengembalikan kembalian, jika ada, ke pengirim.
Perlu dicatat bahwa fan-out, di mana suatu transaksi bergantung pada beberapa transaksi, dan transaksi-transaksi tersebut bergantung pada lebih banyak lagi, bukanlah masalah di sini. Tidak pernah ada kebutuhan untuk mengekstrak salinan mandiri lengkap dari riwayat transaksi.
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Privacy
Model perbankan tradisional mencapai tingkat privasi dengan membatasi akses informasi kepada pihak-pihak yang terlibat dan pihak ketiga tepercaya. Keharusan mengumumkan semua transaksi secara publik menghalangi metode ini, tetapi privasi masih dapat dipertahankan dengan memutus aliran informasi di tempat lain: dengan menjaga kunci publik tetap anonim. Publik dapat melihat bahwa seseorang mengirim sejumlah uang kepada orang lain, tetapi tanpa informasi yang menghubungkan transaksi kepada siapa pun. Ini mirip dengan tingkat informasi yang dirilis oleh bursa saham, di mana waktu dan ukuran perdagangan individual, yaitu "tape," dipublikasikan, tetapi tanpa memberi tahu siapa pihak-pihaknya.
Sebagai firewall tambahan, pasangan kunci baru harus digunakan untuk setiap transaksi agar tidak terhubung ke pemilik yang sama. Beberapa penautan masih tidak terhindarkan dengan transaksi multi-input, yang secara niscaya mengungkapkan bahwa input-inputnya dimiliki oleh pemilik yang sama. Risikonya adalah jika pemilik suatu kunci terungkap, penautan dapat mengungkapkan transaksi lain yang milik pemilik yang sama.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Calculations
Kita mempertimbangkan skenario penyerang yang mencoba menghasilkan rantai alternatif lebih cepat dari rantai jujur. Bahkan jika ini tercapai, sistem tidak terbuka untuk perubahan sewenang-wenang, seperti menciptakan nilai dari udara kosong atau mengambil uang yang tidak pernah milik penyerang. Node tidak akan menerima transaksi tidak valid sebagai pembayaran, dan node jujur tidak akan pernah menerima blok yang berisi transaksi tersebut. Penyerang hanya dapat mencoba mengubah salah satu transaksinya sendiri untuk mengambil kembali uang yang baru saja dibelanjakannya.
Perlombaan antara rantai jujur dan rantai penyerang dapat dikarakterisasi sebagai Jalan Acak Binomial. Peristiwa sukses adalah rantai jujur diperpanjang satu blok, meningkatkan keunggulannya sebesar +1, dan peristiwa gagal adalah rantai penyerang diperpanjang satu blok, mengurangi jarak sebesar -1.
Probabilitas penyerang mengejar dari defisit tertentu analog dengan masalah Kebangkrutan Penjudi. Misalkan seorang penjudi dengan kredit tak terbatas mulai dari defisit dan memainkan jumlah percobaan yang berpotensi tak terbatas untuk mencoba mencapai titik impas. Kita dapat menghitung probabilitas ia pernah mencapai titik impas, atau bahwa penyerang pernah mengejar rantai jujur, sebagai berikut [^8]:
p = probabilitas node jujur menemukan blok berikutnya
q = probabilitas penyerang menemukan blok berikutnya
q = probabilitas penyerang akan pernah mengejar dari z blok di belakang
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
Mengingat asumsi kita bahwa p q, probabilitas turun secara eksponensial seiring bertambahnya jumlah blok yang harus dikejar penyerang. Dengan peluang melawannya, jika ia tidak membuat lompatan beruntung ke depan di awal, peluangnya menjadi sangat kecil saat ia semakin tertinggal.
Sekarang kita mempertimbangkan berapa lama penerima transaksi baru perlu menunggu sebelum cukup yakin bahwa pengirim tidak dapat mengubah transaksi. Kita mengasumsikan pengirim adalah penyerang yang ingin membuat penerima percaya bahwa ia telah membayarnya untuk sementara waktu, kemudian mengalihkan pembayaran kembali ke dirinya sendiri setelah beberapa waktu berlalu. Penerima akan diperingatkan ketika itu terjadi, tetapi pengirim berharap sudah terlambat.
Penerima menghasilkan pasangan kunci baru dan memberikan kunci publik kepada pengirim sesaat sebelum menandatangani. Ini mencegah pengirim menyiapkan rantai blok lebih awal dengan terus bekerja sampai cukup beruntung untuk cukup jauh di depan, lalu mengeksekusi transaksi pada saat itu. Setelah transaksi dikirim, pengirim yang tidak jujur mulai bekerja secara rahasia pada rantai paralel yang berisi versi alternatif transaksinya.
Penerima menunggu sampai transaksi ditambahkan ke blok dan z blok telah ditautkan setelahnya. Ia tidak mengetahui jumlah pasti kemajuan yang telah dibuat penyerang, tetapi dengan mengasumsikan blok jujur mengambil rata-rata waktu yang diharapkan per blok, potensi kemajuan penyerang akan berupa distribusi Poisson dengan nilai harapan:
\[
\lambda = z\frac{q}{p}
\]
Untuk mendapatkan probabilitas penyerang masih bisa mengejar sekarang, kita mengalikan densitas Poisson untuk setiap jumlah kemajuan yang mungkin telah dibuatnya dengan probabilitas ia bisa mengejar dari titik tersebut:
\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]
Menyusun ulang untuk menghindari penjumlahan ekor tak terbatas dari distribusi...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
Mengonversi ke kode C...
```c
#include math.h
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k = z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i = k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
Menjalankan beberapa hasil, kita dapat melihat probabilitas turun secara eksponensial dengan z.
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
Menyelesaikan untuk P kurang dari 0,1%...
P 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
Calculations
Рассмотрим сценарий, в котором атакующий пытается сгенерировать альтернативную цепочку быстрее, чем честная цепочка. Даже если это удастся, это не открывает систему для произвольных изменений, таких как создание стоимости из ничего или присвоение денег, которые никогда не принадлежали атакующему. Узлы не примут недействительную транзакцию в качестве платежа, и честные узлы никогда не примут блок, содержащий такие транзакции. Атакующий может лишь попытаться изменить одну из своих собственных транзакций, чтобы вернуть деньги, которые он недавно потратил.
Гонку между честной цепочкой и цепочкой атакующего можно охарактеризовать как биномиальное случайное блуждание. Событие успеха — это удлинение честной цепочки на один блок, увеличивающее ее отрыв на +1, а событие неудачи — это удлинение цепочки атакующего на один блок, сокращающее разрыв на -1.
Вероятность того, что атакующий наверстает упущенное с заданного отставания, аналогична задаче о разорении игрока. Предположим, что игрок с неограниченным кредитом начинает с дефицита и играет потенциально бесконечное число раундов, пытаясь выйти в ноль. Мы можем рассчитать вероятность того, что он когда-либо выйдет в ноль, или что атакующий когда-либо догонит честную цепочку, следующим образом [^8]:
p = вероятность того, что честный узел найдет следующий блок
q = вероятность того, что атакующий найдет следующий блок
q = вероятность того, что атакующий когда-либо догонит, отставая на z блоков
\[ qz = \begin{cases} 1 & \text{если } p \leq q \\ \left(\frac{q}{p}\right) z & \text{если } p > q \end{cases} \]
Учитывая наше предположение, что p q, вероятность экспоненциально падает с увеличением числа блоков, которые атакующему нужно наверстать. При неблагоприятных шансах, если он не сделает удачный рывок в самом начале, его шансы становятся исчезающе малыми по мере дальнейшего отставания.
Теперь рассмотрим, как долго получатель новой транзакции должен ждать, прежде чем быть достаточно уверенным, что отправитель не может изменить транзакцию. Мы предполагаем, что отправитель — атакующий, который хочет заставить получателя поверить, что он заплатил ему, на некоторое время, а затем переключить платеж на себя после истечения некоторого времени. Получатель будет предупрежден, когда это произойдет, но отправитель надеется, что будет слишком поздно.
Получатель генерирует новую пару ключей и передает открытый ключ отправителю незадолго до подписания. Это предотвращает подготовку отправителем цепочки блоков заранее путем непрерывной работы над ней, пока ему не посчастливится достаточно продвинуться вперед, а затем выполнить транзакцию в этот момент. После отправки транзакции нечестный отправитель начинает тайно работать над параллельной цепочкой, содержащей альтернативную версию его транзакции.
Получатель ждет, пока транзакция не будет добавлена в блок и z блоков не будут связаны после него. Он не знает точный объем прогресса атакующего, но предполагая, что честные блоки создавались за среднее ожидаемое время на блок, потенциальный прогресс атакующего будет иметь распределение Пуассона с математическим ожиданием:
\[ \lambda = z\frac{q}{p} \]
Чтобы получить вероятность того, что атакующий все еще может догнать, мы умножаем плотность Пуассона для каждого объема прогресса, который он мог сделать, на вероятность того, что он сможет догнать с этой точки:
\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{ \begin{array}{cl} \left(\frac{q}{p}\right)^{(z-k)} & \text{если } k \leq z \\ 1 & \text{если } k > z \end{array} \right. \]
Преобразуя, чтобы избежать суммирования бесконечного хвоста распределения...
\[ 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right) \]
Преобразуя в код на C...
#include math.h
double AttackerSuccessProbability(double q, int z)
{
double p = 1.0 - q;
double lambda = z * (q / p);
double sum = 1.0;
int i, k;
for (k = 0; k = z; k++)
{
double poisson = exp(-lambda);
for (i = 1; i = k; i++)
poisson *= lambda / i;
sum -= poisson * (1 - pow(q / p, z - k));
}
return sum;
}
Выполнив некоторые расчеты, мы можем видеть, как вероятность экспоненциально падает с z.
q=0.1
z=0 P=1.0000000
z=1 P=0.2045873
z=2 P=0.0509779
z=3 P=0.0131722
z=4 P=0.0034552
z=5 P=0.0009137
z=6 P=0.0002428
z=7 P=0.0000647
z=8 P=0.0000173
z=9 P=0.0000046
z=10 P=0.0000012
q=0.3
z=0 P=1.0000000
z=5 P=0.1773523
z=10 P=0.0416605
z=15 P=0.0101008
z=20 P=0.0024804
z=25 P=0.0006132
z=30 P=0.0001522
z=35 P=0.0000379
z=40 P=0.0000095
z=45 P=0.0000024
z=50 P=0.0000006
Решая для P менее 0,1%...
P 0.001
q=0.10 z=5
q=0.15 z=8
q=0.20 z=11
q=0.25 z=15
q=0.30 z=24
q=0.35 z=41
q=0.40 z=89
q=0.45 z=340
Conclusion
Kami telah mengusulkan sistem untuk transaksi elektronik tanpa bergantung pada kepercayaan. Kami memulai dengan kerangka biasa koin yang dibuat dari tanda tangan digital, yang memberikan kontrol kuat atas kepemilikan, tetapi tidak lengkap tanpa cara untuk mencegah double-spending. Untuk mengatasi ini, kami mengusulkan jaringan peer-to-peer yang menggunakan proof-of-work untuk mencatat riwayat publik transaksi yang dengan cepat menjadi tidak praktis secara komputasi bagi penyerang untuk diubah jika node jujur mengendalikan mayoritas daya CPU. Jaringan ini kuat dalam kesederhanaan tidak terstrukturnya. Node bekerja sekaligus dengan sedikit koordinasi. Mereka tidak perlu diidentifikasi, karena pesan tidak dirutekan ke tempat tertentu manapun dan hanya perlu dikirimkan berdasarkan upaya terbaik. Node dapat meninggalkan dan bergabung kembali dengan jaringan sesuka hati, menerima rantai proof-of-work sebagai bukti atas apa yang terjadi saat mereka pergi. Mereka memilih dengan daya CPU mereka, mengekspresikan penerimaan blok valid dengan bekerja memperpanjangnya dan menolak blok tidak valid dengan menolak bekerja pada blok tersebut. Setiap aturan dan insentif yang diperlukan dapat ditegakkan dengan mekanisme konsensus ini.
Conclusion
Мы предложили систему электронных транзакций, не основанную на доверии. Мы начали с обычной структуры монет, созданных из цифровых подписей, которая обеспечивает надежный контроль над собственностью, но является неполной без способа предотвращения двойного расходования. Для решения этой проблемы мы предложили одноранговую сеть, использующую proof-of-work для записи публичной истории транзакций, которую быстро становится вычислительно непрактично изменить для атакующего, если честные узлы контролируют большую часть мощности CPU. Сеть устойчива в своей неструктурированной простоте. Узлы работают одновременно с минимальной координацией. Их не нужно идентифицировать, поскольку сообщения не направляются в какое-либо конкретное место и должны быть доставлены лишь по принципу максимальных усилий. Узлы могут покидать сеть и присоединяться к ней по желанию, принимая цепочку proof-of-work как доказательство того, что произошло в их отсутствие. Они голосуют своей вычислительной мощностью CPU, выражая принятие действительных блоков работой над их продлением и отклоняя недействительные блоки отказом работать над ними. Любые необходимые правила и стимулы могут быть реализованы с помощью этого механизма консенсуса.
References
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
References
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
