بيتكوين: نظام نقد إلكتروني من نظير إلى نظير
Abstract
Полностью одноранговая версия электронных денег позволила бы отправлять онлайн-платежи напрямую от одной стороны к другой без участия финансового учреждения. Цифровые подписи обеспечивают часть решения, но основные преимущества теряются, если для предотвращения двойного расходования по-прежнему требуется доверенная третья сторона. Мы предлагаем решение проблемы двойного расходования с использованием одноранговой сети. Сеть присваивает транзакциям временные метки, хешируя их в непрерывную цепочку proof-of-work на основе хешей, формируя запись, которую невозможно изменить без повторного выполнения proof-of-work. Самая длинная цепочка служит не только доказательством последовательности наблюдавшихся событий, но и доказательством того, что она создана наибольшим пулом вычислительной мощности CPU. Пока большая часть мощности CPU контролируется узлами, не участвующими в атаке на сеть, они будут генерировать самую длинную цепочку и опережать атакующих. Сама сеть требует минимальной структуры. Сообщения рассылаются по принципу максимальных усилий, и узлы могут покидать сеть и присоединяться к ней по желанию, принимая самую длинную цепочку proof-of-work как доказательство того, что произошло в их отсутствие.
Abstract
إن نسخة peer-to-peer بالكامل من النقد الإلكتروني ستسمح بإرسال المدفوعات عبر الإنترنت مباشرة من طرف إلى آخر دون المرور عبر مؤسسة مالية. توفر digital signatures جزءاً من الحل، لكن الفوائد الرئيسية تضيع إذا كان لا يزال هناك حاجة إلى طرف ثالث موثوق لمنع double-spending. نقترح حلاً لمشكلة double-spending باستخدام شبكة peer-to-peer. تقوم الشبكة بوضع timestamps على المعاملات عن طريق تحويلها إلى hash ضمن سلسلة مستمرة من proof-of-work القائم على hash، مما يشكل سجلاً لا يمكن تغييره دون إعادة تنفيذ proof-of-work. لا تعمل السلسلة الأطول كدليل على تسلسل الأحداث التي شوهدت فحسب، بل كدليل أيضاً على أنها جاءت من أكبر مجمع لقدرة CPU. طالما أن غالبية قدرة CPU يتحكم بها nodes لا تتعاون لمهاجمة الشبكة، فإنها ستولد السلسلة الأطول وتتفوق على المهاجمين. تتطلب الشبكة نفسها حداً أدنى من البنية. يتم بث الرسائل على أساس best effort، ويمكن لـ nodes مغادرة الشبكة والانضمام إليها مجدداً حسب رغبتها، مع قبول أطول سلسلة proof-of-work كدليل على ما حدث أثناء غيابها.
Introduction
Коммерция в Интернете стала почти исключительно зависеть от финансовых учреждений, выступающих в роли доверенных третьих сторон для обработки электронных платежей. Хотя система достаточно хорошо работает для большинства транзакций, она по-прежнему страдает от врожденных слабостей модели, основанной на доверии. Полностью необратимые транзакции фактически невозможны, поскольку финансовые учреждения не могут избежать посредничества в спорах. Стоимость посредничества увеличивает транзакционные издержки, ограничивая минимальный практический размер транзакции и исключая возможность мелких повседневных транзакций, а также существует более широкая цена в виде утраты возможности осуществлять необратимые платежи за необратимые услуги. С возможностью отмены потребность в доверии распространяется. Продавцы должны с осторожностью относиться к своим клиентам, запрашивая у них больше информации, чем было бы необходимо в ином случае. Определенный процент мошенничества принимается как неизбежный. Эти издержки и неопределенности платежей можно избежать при личных расчетах с использованием физической валюты, но не существует механизма для осуществления платежей по каналу связи без доверенной стороны.
Необходима электронная платежная система, основанная на криптографическом доказательстве вместо доверия, позволяющая любым двум желающим сторонам совершать сделки напрямую друг с другом без необходимости в доверенной третьей стороне. Транзакции, которые вычислительно непрактично отменить, защитили бы продавцов от мошенничества, а обычные механизмы условного депонирования могли бы быть легко реализованы для защиты покупателей. В данной работе мы предлагаем решение проблемы двойного расходования с использованием одноранговой распределенной системы серверов временных меток для генерации вычислительного доказательства хронологического порядка транзакций. Система безопасна до тех пор, пока честные узлы совместно контролируют больше вычислительной мощности CPU, чем любая кооперирующаяся группа атакующих узлов.
Introduction
أصبحت التجارة على الإنترنت تعتمد بشكل شبه حصري على المؤسسات المالية التي تعمل كأطراف ثالثة موثوقة لمعالجة المدفوعات الإلكترونية. بينما يعمل النظام بشكل جيد بما يكفي لمعظم المعاملات، إلا أنه لا يزال يعاني من نقاط الضعف المتأصلة في النموذج القائم على الثقة. المعاملات غير القابلة للعكس بشكل كامل ليست ممكنة فعلياً، حيث لا تستطيع المؤسسات المالية تجنب التوسط في النزاعات. تزيد تكلفة الوساطة من تكاليف المعاملات، مما يحد من الحد الأدنى العملي لحجم المعاملة ويقطع إمكانية المعاملات الصغيرة العرضية، وهناك تكلفة أوسع تتمثل في فقدان القدرة على إجراء مدفوعات غير قابلة للعكس مقابل خدمات غير قابلة للعكس. مع إمكانية العكس، تنتشر الحاجة إلى الثقة. يجب على التجار أن يكونوا حذرين من عملائهم، ومضايقتهم للحصول على معلومات أكثر مما يحتاجون إليه. يتم قبول نسبة معينة من الاحتيال على أنها أمر لا مفر منه. يمكن تجنب هذه التكاليف وحالات عدم اليقين في الدفع شخصياً باستخدام العملة المادية، لكن لا توجد آلية لإجراء مدفوعات عبر قناة اتصالات دون طرف موثوق.
ما هو مطلوب هو نظام دفع إلكتروني قائم على cryptographic proof بدلاً من الثقة، يسمح لأي طرفين راغبين بالتعامل مباشرة مع بعضهما البعض دون الحاجة إلى طرف ثالث موثوق. المعاملات التي يكون عكسها غير عملي حسابياً ستحمي البائعين من الاحتيال، ويمكن تنفيذ آليات escrow الروتينية بسهولة لحماية المشترين. في هذه الورقة، نقترح حلاً لمشكلة double-spending باستخدام خادم timestamp موزع peer-to-peer لتوليد إثبات حسابي للترتيب الزمني للمعاملات. النظام آمن طالما أن nodes الصادقة تتحكم مجتمعة في قدرة CPU أكبر من أي مجموعة متعاونة من nodes المهاجمة.
Transactions
Мы определяем электронную монету как цепочку цифровых подписей. Каждый владелец передает монету следующему, подписывая цифровой подписью хеш предыдущей транзакции и открытый ключ следующего владельца и добавляя их в конец монеты. Получатель платежа может проверить подписи для верификации цепочки владения.
Проблема, разумеется, в том, что получатель платежа не может проверить, не потратил ли один из владельцев монету дважды. Распространенное решение заключается во введении доверенного центрального органа, или монетного двора, который проверяет каждую транзакцию на предмет двойного расходования. После каждой транзакции монета должна быть возвращена на монетный двор для выпуска новой монеты, и только монеты, выпущенные непосредственно монетным двором, считаются не потраченными дважды. Проблема этого решения в том, что судьба всей денежной системы зависит от компании, управляющей монетным двором, и каждая транзакция должна проходить через них, как через банк.
Нам нужен способ, позволяющий получателю платежа знать, что предыдущие владельцы не подписывали никаких более ранних транзакций. Для наших целей самая ранняя транзакция является определяющей, поэтому нас не беспокоят последующие попытки двойного расходования. Единственный способ подтвердить отсутствие транзакции — быть осведомленным обо всех транзакциях. В модели монетного двора монетный двор знал обо всех транзакциях и решал, какая поступила первой. Чтобы достичь этого без доверенной стороны, транзакции должны быть объявлены публично [^1], и нам нужна система, позволяющая участникам согласовать единую историю порядка, в котором они были получены. Получателю платежа нужно доказательство того, что в момент каждой транзакции большинство узлов согласились, что она была получена первой.
Transactions
نعرّف العملة الإلكترونية كسلسلة من digital signatures. يقوم كل مالك بنقل العملة إلى المالك التالي عن طريق التوقيع الرقمي على hash للمعاملة السابقة وpublic key للمالك التالي وإضافة هذه إلى نهاية العملة. يمكن للمستلم التحقق من signatures للتحقق من سلسلة الملكية.
المشكلة بالطبع هي أن المستلم لا يمكنه التحقق من أن أحد المالكين لم يقم بـ double-spend للعملة. الحل الشائع هو تقديم سلطة مركزية موثوقة، أو mint، تتحقق من كل معاملة بحثاً عن double spending. بعد كل معاملة، يجب إعادة العملة إلى mint لإصدار عملة جديدة، ولا يُوثق بعدم double-spend إلا العملات الصادرة مباشرة من mint. مشكلة هذا الحل هي أن مصير النظام النقدي بأكمله يعتمد على الشركة التي تدير mint، حيث يجب أن تمر كل معاملة من خلالها، تماماً مثل البنك.
نحتاج إلى طريقة تمكّن المستلم من معرفة أن المالكين السابقين لم يوقعوا على أي معاملات سابقة. لأغراضنا، المعاملة الأقدم هي التي تُعتد بها، لذلك لا نهتم بالمحاولات اللاحقة لـ double-spend. الطريقة الوحيدة لتأكيد غياب معاملة هي أن تكون على علم بجميع المعاملات. في النموذج القائم على mint، كان mint على علم بجميع المعاملات وقرر أيها وصل أولاً. لتحقيق ذلك بدون طرف موثوق، يجب الإعلان عن المعاملات بشكل عام [^1]، ونحتاج إلى نظام يتفق فيه المشاركون على تاريخ واحد للترتيب الذي استُلمت به. يحتاج المستلم إلى إثبات أنه في وقت كل معاملة، وافقت غالبية nodes على أنها كانت أول معاملة مستلمة.
Timestamp Server
Предлагаемое нами решение начинается с сервера временных меток. Сервер временных меток работает, беря хеш блока элементов, которым нужно присвоить временную метку, и широко публикуя этот хеш, например, в газете или посте Usenet [^2] [^3] [^4] [^5]. Временная метка доказывает, что данные, очевидно, должны были существовать в это время, чтобы попасть в хеш. Каждая временная метка включает предыдущую временную метку в свой хеш, образуя цепочку, где каждая дополнительная временная метка усиливает предыдущие.
Timestamp Server
يبدأ الحل الذي نقترحه بخادم timestamp. يعمل خادم timestamp عن طريق أخذ hash لمجموعة من العناصر المراد وضع timestamp عليها ونشر hash على نطاق واسع، كما هو الحال في صحيفة أو منشور Usenet [^2] [^3] [^4] [^5]. يثبت timestamp أن البيانات كانت موجودة بالضرورة في ذلك الوقت لكي تدخل في hash. يتضمن كل timestamp الـ timestamp السابق في hash الخاص به، مشكلاً سلسلة، حيث يعزز كل timestamp إضافي ما سبقه.
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 определяется скользящим средним, нацеленным на среднее количество блоков в час. Если они генерируются слишком быстро, сложность возрастает.
Proof-of-Work
لتنفيذ خادم timestamp موزع على أساس peer-to-peer، سنحتاج إلى استخدام نظام proof-of-work مشابه لـ Hashcash الخاص بـ Adam Back [^6]، بدلاً من منشورات الصحف أو Usenet. يتضمن proof-of-work البحث عن قيمة عند تحويلها إلى hash، مثلاً باستخدام SHA-256، يبدأ hash بعدد من zero bits. يكون متوسط العمل المطلوب أسياً (exponential) في عدد zero bits المطلوبة ويمكن التحقق منه بتنفيذ hash واحد.
بالنسبة لشبكة timestamp الخاصة بنا، ننفذ proof-of-work عن طريق زيادة nonce في block حتى يتم العثور على قيمة تمنح hash الـ block عدد zero bits المطلوب. بمجرد إنفاق جهد CPU لجعله يستوفي proof-of-work، لا يمكن تغيير block دون إعادة تنفيذ العمل. نظراً لأن blocks اللاحقة مرتبطة بعده في سلسلة، فإن عمل تغيير block سيشمل إعادة تنفيذ جميع blocks التي تليه.
يحل proof-of-work أيضاً مشكلة تحديد التمثيل في اتخاذ قرار الأغلبية. إذا كانت الأغلبية تعتمد على one-IP-address-one-vote، فيمكن تقويضها من قبل أي شخص قادر على تخصيص العديد من عناوين IP. proof-of-work هو في جوهره one-CPU-one-vote. يتم تمثيل قرار الأغلبية بأطول سلسلة، التي استُثمر فيها أكبر جهد proof-of-work. إذا كانت غالبية قدرة CPU يتحكم بها honest nodes، فإن السلسلة الصادقة ستنمو بأسرع معدل وتتفوق على أي سلاسل منافسة. لتعديل block سابق، سيتعين على المهاجم إعادة تنفيذ proof-of-work لذلك block وجميع blocks التي تليه ثم اللحاق بعمل honest nodes وتجاوزه. سنبين لاحقاً أن احتمال لحاق مهاجم أبطأ يتناقص أسياً (exponentially) مع إضافة blocks لاحقة.
للتعويض عن زيادة سرعة الأجهزة والاهتمام المتغير بتشغيل nodes بمرور الوقت، يتم تحديد صعوبة proof-of-work بواسطة متوسط متحرك يستهدف عدداً متوسطاً من blocks في الساعة. إذا تم إنشاؤها بسرعة كبيرة، تزداد الصعوبة.
Network
Шаги для работы сети следующие:
- Новые транзакции рассылаются всем узлам.
- Каждый узел собирает новые транзакции в блок.
- Каждый узел работает над поиском сложного proof-of-work для своего блока.
- Когда узел находит proof-of-work, он рассылает блок всем узлам.
- Узлы принимают блок, только если все транзакции в нем действительны и не были потрачены ранее.
- Узлы выражают свое принятие блока, работая над созданием следующего блока в цепочке, используя хеш принятого блока в качестве предыдущего хеша.
Узлы всегда считают самую длинную цепочку правильной и продолжают работать над ее удлинением. Если два узла одновременно рассылают разные версии следующего блока, некоторые узлы могут получить одну или другую первой. В этом случае они работают над той, которую получили первой, но сохраняют другую ветвь на случай, если она станет длиннее. Ничья будет разрешена, когда будет найден следующий proof-of-work и одна ветвь станет длиннее; узлы, работавшие над другой ветвью, тогда переключатся на более длинную.
Рассылка новых транзакций не обязательно должна достигать всех узлов. Пока они достигают многих узлов, они попадут в блок в скором времени. Рассылка блоков также устойчива к потере сообщений. Если узел не получает блок, он запросит его при получении следующего блока, осознав, что пропустил один.
Network
خطوات تشغيل الشبكة هي كالتالي:
- يتم بث transactions الجديدة إلى جميع nodes.
- يجمع كل node الـ transactions الجديدة في block.
- يعمل كل node على إيجاد proof-of-work صعب لـ block الخاص به.
- عندما يجد node الـ proof-of-work، يبث block إلى جميع nodes.
- تقبل nodes الـ block فقط إذا كانت جميع transactions فيه صالحة ولم يتم إنفاقها مسبقاً.
- تعبر nodes عن قبولها لـ block بالعمل على إنشاء block التالي في السلسلة، باستخدام hash الـ block المقبول كـ previous hash.
تعتبر nodes دائماً أطول سلسلة هي الصحيحة وتستمر في العمل على تمديدها. إذا بث node-ان نسختين مختلفتين من block التالي في وقت واحد، فقد تستقبل بعض nodes إحداهما أو الأخرى أولاً. في تلك الحالة، تعمل على أول نسخة استقبلتها، لكنها تحفظ الفرع الآخر في حال أصبح أطول. سيُكسر التعادل عندما يُعثر على proof-of-work التالي ويصبح أحد الفرعين أطول؛ ستنتقل nodes التي كانت تعمل على الفرع الآخر عندئذ إلى الأطول.
لا يتطلب بث transactions الجديدة بالضرورة الوصول إلى جميع nodes. طالما أنها تصل إلى العديد من nodes، ستدخل في block قبل وقت طويل. كما أن بث blocks متسامح مع الرسائل المفقودة. إذا لم يستقبل node block ما، فسيطلبه عندما يستقبل block التالي ويدرك أنه فاته واحد.
Incentive
По соглашению, первая транзакция в блоке является специальной транзакцией, которая создает новую монету, принадлежащую создателю блока. Это добавляет стимул для узлов поддерживать сеть и обеспечивает способ первоначального распределения монет в обращение, поскольку нет центрального органа для их выпуска. Постоянное добавление фиксированного количества новых монет аналогично тому, как золотодобытчики тратят ресурсы для добавления золота в обращение. В нашем случае расходуется процессорное время и электроэнергия.
Стимул также может финансироваться за счет комиссий за транзакции. Если выходное значение транзакции меньше ее входного значения, разница представляет собой комиссию за транзакцию, которая добавляется к стимулирующему значению блока, содержащего транзакцию. Как только заранее определенное количество монет поступит в обращение, стимул может полностью перейти на комиссии за транзакции и быть полностью свободным от инфляции.
Стимул может помочь побудить узлы оставаться честными. Если жадный атакующий сможет собрать больше вычислительной мощности CPU, чем все честные узлы, ему придется выбирать между использованием ее для обмана людей путем возврата своих платежей или использованием ее для генерации новых монет. Ему должно быть выгоднее играть по правилам, которые дают ему больше новых монет, чем всем остальным вместе взятым, чем подрывать систему и обесценивать собственное богатство.
Incentive
بحسب الاتفاق، فإن أول transaction في block هو transaction خاص يبدأ عملة جديدة يملكها منشئ block. هذا يضيف حافزاً لـ nodes لدعم الشبكة، ويوفر طريقة لتوزيع العملات في التداول مبدئياً، حيث لا توجد سلطة مركزية لإصدارها. إن الإضافة المستمرة لكمية ثابتة من العملات الجديدة تشبه منقبي الذهب الذين ينفقون الموارد لإضافة الذهب إلى التداول. في حالتنا، إنه وقت CPU والكهرباء التي يتم إنفاقها.
يمكن أيضاً تمويل الحافز من خلال transaction fees. إذا كانت قيمة output الـ transaction أقل من قيمة input، فإن الفرق هو transaction fee تُضاف إلى قيمة حافز block الذي يحتوي على ذلك transaction. بمجرد دخول عدد محدد مسبقاً من العملات في التداول، يمكن أن ينتقل الحافز بالكامل إلى transaction fees ويكون خالياً تماماً من التضخم.
قد يساعد الحافز في تشجيع nodes على البقاء صادقة. إذا كان مهاجم جشع قادراً على تجميع قدرة CPU أكبر من جميع honest nodes، فسيتعين عليه الاختيار بين استخدامها للاحتيال على الناس بسرقة مدفوعاته، أو استخدامها لتوليد عملات جديدة. ينبغي أن يجد اللعب وفق القواعد أكثر ربحية، قواعد تمنحه عملات جديدة أكثر من جميع الآخرين مجتمعين، بدلاً من تقويض النظام وصلاحية ثروته الخاصة.
Reclaiming Disk Space
Как только последняя транзакция в монете оказывается погребена под достаточным количеством блоков, потраченные транзакции до нее могут быть отброшены для экономии дискового пространства. Чтобы обеспечить это без нарушения хеша блока, транзакции хешируются в дереве Меркла (Merkle Tree) [^7] [^2] [^5], и только корень включается в хеш блока. Старые блоки затем могут быть сжаты путем отсечения ветвей дерева. Внутренние хеши не нужно хранить.
Заголовок блока без транзакций занимал бы около 80 байт. Если предположить, что блоки генерируются каждые 10 минут, 80 байт * 6 * 24 * 365 = 4,2 МБ в год. При том, что компьютерные системы обычно продавались с 2 ГБ ОЗУ по состоянию на 2008 год, а закон Мура предсказывает текущий рост в 1,2 ГБ в год, хранение не должно быть проблемой, даже если заголовки блоков необходимо хранить в памяти.
Reclaiming Disk Space
بمجرد أن يُدفن أحدث transaction في عملة تحت عدد كافٍ من blocks، يمكن التخلص من transactions المنفقة قبله لتوفير مساحة القرص. لتسهيل ذلك دون كسر hash الـ block، يتم تحويل transactions إلى hash في Merkle Tree [^7] [^2] [^5]، مع تضمين الجذر فقط في hash الـ block. يمكن بعد ذلك ضغط blocks القديمة عن طريق قطع فروع الشجرة. لا يلزم تخزين hashes الداخلية.
سيكون حجم block header بدون transactions حوالي 80 bytes. إذا افترضنا أن blocks يتم إنشاؤها كل 10 دقائق، فإن 80 bytes * 6 * 24 * 365 = 4.2MB سنوياً. مع أنظمة الكمبيوتر التي تُباع عادة بذاكرة 2GB من RAM اعتباراً من عام 2008، وقانون Moore الذي يتنبأ بنمو حالي قدره 1.2GB سنوياً، لا ينبغي أن يكون التخزين مشكلة حتى لو كان يجب الاحتفاظ بـ block headers في الذاكرة.
Simplified Payment Verification
Можно проверять платежи, не запуская полный сетевой узел. Пользователю нужно лишь хранить копию заголовков блоков самой длинной цепочки proof-of-work, которую он может получить, опрашивая сетевые узлы, пока не убедится, что имеет самую длинную цепочку, и получить ветвь Меркла, связывающую транзакцию с блоком, в котором она получила временную метку. Он не может проверить транзакцию самостоятельно, но, связав ее с местом в цепочке, он может увидеть, что сетевой узел принял ее, и блоки, добавленные после нее, дополнительно подтверждают, что сеть ее приняла.
Таким образом, проверка надежна, пока честные узлы контролируют сеть, но более уязвима, если сеть захвачена атакующим. В то время как сетевые узлы могут самостоятельно проверять транзакции, упрощенный метод может быть обманут сфабрикованными транзакциями атакующего, пока тот может продолжать доминировать в сети. Одной из стратегий защиты от этого было бы принятие предупреждений от сетевых узлов при обнаружении ими недействительного блока, побуждающих программное обеспечение пользователя загрузить полный блок и отмеченные транзакции для подтверждения несоответствия. Предприятия, получающие частые платежи, вероятно, по-прежнему захотят запускать собственные узлы для более независимой безопасности и более быстрой проверки.
Simplified Payment Verification
من الممكن التحقق من المدفوعات دون تشغيل node شبكة كامل. يحتاج المستخدم فقط إلى الاحتفاظ بنسخة من block headers لأطول سلسلة proof-of-work، والتي يمكنه الحصول عليها بالاستعلام من nodes الشبكة حتى يقتنع بأن لديه أطول سلسلة، والحصول على فرع Merkle الذي يربط transaction بالـ block الذي وُضع فيه timestamp. لا يمكنه التحقق من transaction بنفسه، لكن بربطه بمكان في السلسلة، يمكنه رؤية أن node في الشبكة قد قبله، والـ blocks المضافة بعده تؤكد أيضاً أن الشبكة قبلته.
وبالتالي، يكون التحقق موثوقاً طالما أن honest nodes تتحكم في الشبكة، لكنه أكثر عرضة للخطر إذا تغلب مهاجم على الشبكة. بينما يمكن لـ nodes الشبكة التحقق من transactions بأنفسها، يمكن خداع الطريقة المبسطة بـ transactions ملفقة من المهاجم طالما يستطيع المهاجم الاستمرار في التغلب على الشبكة. تتمثل إحدى استراتيجيات الحماية ضد ذلك في قبول تنبيهات من nodes الشبكة عند اكتشافها block غير صالح، مما يدفع برنامج المستخدم إلى تنزيل block الكامل والـ transactions المنبه عنها لتأكيد التناقض. من المرجح أن ترغب الشركات التي تتلقى مدفوعات متكررة في تشغيل nodes خاصة بها لمزيد من الأمان المستقل والتحقق الأسرع.
Combining and Splitting Value
Хотя было бы возможно обрабатывать монеты по отдельности, было бы неудобно создавать отдельную транзакцию для каждого цента при переводе. Чтобы позволить разделение и объединение стоимости, транзакции содержат несколько входов и выходов. Обычно будет либо один вход от более крупной предыдущей транзакции, либо несколько входов, объединяющих меньшие суммы, и не более двух выходов: один для платежа и один для возврата сдачи, если таковая имеется, отправителю.
Следует отметить, что разветвление (fan-out), когда транзакция зависит от нескольких транзакций, а те, в свою очередь, зависят от еще большего числа, здесь не является проблемой. Никогда нет необходимости извлекать полную самостоятельную копию истории транзакции.
Combining and Splitting Value
على الرغم من أنه سيكون من الممكن التعامل مع العملات بشكل فردي، إلا أنه سيكون من غير العملي إجراء transaction منفصل لكل سنت في التحويل. للسماح بتقسيم القيمة ودمجها، تحتوي transactions على inputs و outputs متعددة. عادة سيكون هناك إما input واحد من transaction سابق أكبر أو inputs متعددة تجمع مبالغ أصغر، وعلى الأكثر output-ان: أحدهما للدفع، والآخر لإرجاع الباقي، إن وُجد، إلى المرسل.
تجدر الإشارة إلى أن fan-out، حيث يعتمد transaction على عدة transactions، وتلك transactions تعتمد على المزيد، ليست مشكلة هنا. لا توجد حاجة أبداً لاستخراج نسخة مستقلة كاملة من تاريخ transaction.
Privacy
Традиционная банковская модель обеспечивает определенный уровень конфиденциальности, ограничивая доступ к информации вовлеченными сторонами и доверенной третьей стороной. Необходимость публично объявлять все транзакции исключает этот метод, но конфиденциальность все еще может быть сохранена путем прерывания потока информации в другом месте: путем сохранения анонимности открытых ключей. Общественность может видеть, что кто-то отправляет сумму кому-то другому, но без информации, связывающей транзакцию с кем-либо. Это аналогично уровню информации, публикуемой фондовыми биржами, где время и объем отдельных сделок, «лента», делаются публичными, но без указания того, кем были стороны.
В качестве дополнительного барьера для каждой транзакции следует использовать новую пару ключей, чтобы предотвратить их привязку к общему владельцу. Некоторая связь по-прежнему неизбежна при транзакциях с несколькими входами, которые неизбежно раскрывают, что их входы принадлежали одному владельцу. Риск состоит в том, что если владелец ключа будет раскрыт, связывание может раскрыть другие транзакции, принадлежавшие тому же владельцу.
Privacy
يحقق نموذج البنوك التقليدي مستوى من الخصوصية عن طريق تقييد الوصول إلى المعلومات على الأطراف المعنية والطرف الثالث الموثوق. إن ضرورة الإعلان عن جميع transactions علنياً تستبعد هذه الطريقة، لكن يمكن الحفاظ على الخصوصية عن طريق كسر تدفق المعلومات في مكان آخر: بالحفاظ على public keys مجهولة الهوية. يمكن للجمهور رؤية أن شخصاً ما يرسل مبلغاً إلى شخص آخر، لكن بدون معلومات تربط transaction بأي شخص. يشبه هذا مستوى المعلومات الصادرة عن البورصات، حيث يُعلن عن وقت وحجم الصفقات الفردية، "الشريط"، لكن دون الكشف عن هوية الأطراف.
كجدار حماية إضافي، يجب استخدام key pair جديد لكل transaction لمنع ربطها بمالك مشترك. لا يزال بعض الربط حتمياً مع transactions متعددة inputs، والتي تكشف بالضرورة أن inputs-ها كانت مملوكة لنفس المالك. الخطر هو أنه إذا كُشفت هوية مالك key، فإن الربط قد يكشف transactions أخرى تنتمي لنفس المالك.
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
Calculations
ندرس سيناريو محاولة مهاجم توليد سلسلة بديلة أسرع من السلسلة الصادقة. حتى لو تحقق ذلك، فإنه لا يفتح النظام لتغييرات عشوائية، مثل خلق قيمة من العدم أو أخذ أموال لم تكن أبداً ملكاً للمهاجم. لن تقبل nodes transaction غير صالح كدفعة، ولن تقبل honest nodes أبداً block يحتوي عليها. يمكن للمهاجم فقط محاولة تغيير أحد transactions الخاصة به لاسترداد أموال أنفقها مؤخراً.
يمكن وصف السباق بين السلسلة الصادقة وسلسلة المهاجم بأنه Binomial Random Walk. حدث النجاح هو تمديد السلسلة الصادقة بـ block واحد، مما يزيد تقدمها بمقدار +1، وحدث الفشل هو تمديد سلسلة المهاجم بـ block واحد، مما يقلل الفجوة بمقدار -1.
إن احتمال لحاق المهاجم من عجز معين مماثل لمسألة Gambler's Ruin. لنفترض أن مقامراً ذا رصيد غير محدود يبدأ بعجز ويلعب عدداً لا نهائياً محتملاً من المحاولات للوصول إلى نقطة التعادل. يمكننا حساب احتمال وصوله إلى نقطة التعادل، أو لحاق المهاجم بالسلسلة الصادقة، كالتالي [^8]:
p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
بالنظر إلى افتراضنا أن p q، ينخفض الاحتمال أسياً (exponentially) مع زيادة عدد blocks التي يجب على المهاجم اللحاق بها. إذا لم يحقق قفزة محظوظة للأمام في وقت مبكر، تصبح فرصه ضئيلة للغاية كلما تخلف أكثر.
ندرس الآن المدة التي يحتاج مستلم transaction جديد إلى الانتظار قبل أن يكون واثقاً بما يكفي أن المرسل لا يستطيع تغيير transaction. نفترض أن المرسل مهاجم يريد إقناع المستلم بأنه دفع له لفترة، ثم يحوّل الدفع لنفسه بعد مرور بعض الوقت. سيتم تنبيه المستلم عند حدوث ذلك، لكن المرسل يأمل أن يكون قد فات الأوان.
يولد المستلم key pair جديداً ويعطي public key للمرسل قبل التوقيع بقليل. هذا يمنع المرسل من تحضير سلسلة blocks مسبقاً بالعمل عليها باستمرار حتى يحالفه الحظ ويتقدم بما فيه الكفاية، ثم ينفذ transaction في تلك اللحظة. بمجرد إرسال transaction، يبدأ المرسل غير الأمين بالعمل سراً على سلسلة موازية تحتوي على نسخة بديلة من transaction الخاص به.
ينتظر المستلم حتى يُضاف transaction إلى block ويتم ربط z من blocks بعده. لا يعرف مقدار التقدم الدقيق الذي أحرزه المهاجم، لكن بافتراض أن honest blocks استغرقت الوقت المتوقع المتوسط لكل block، فإن التقدم المحتمل للمهاجم سيكون توزيع Poisson بقيمة متوقعة:
\[
\lambda = z\frac{q}{p}
\]
للحصول على احتمال أن المهاجم لا يزال يمكنه اللحاق الآن، نضرب كثافة Poisson لكل مقدار تقدم يمكن أن يكون قد أحرزه في احتمال اللحاق من تلك النقطة:
\[
\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.
\]
بإعادة الترتيب لتجنب جمع الذيل اللانهائي للتوزيع...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
تحويل إلى كود 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;
}
بتشغيل بعض النتائج، يمكننا رؤية أن الاحتمال ينخفض أسياً مع 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
Мы предложили систему электронных транзакций, не основанную на доверии. Мы начали с обычной структуры монет, созданных из цифровых подписей, которая обеспечивает надежный контроль над собственностью, но является неполной без способа предотвращения двойного расходования. Для решения этой проблемы мы предложили одноранговую сеть, использующую proof-of-work для записи публичной истории транзакций, которую быстро становится вычислительно непрактично изменить для атакующего, если честные узлы контролируют большую часть мощности CPU. Сеть устойчива в своей неструктурированной простоте. Узлы работают одновременно с минимальной координацией. Их не нужно идентифицировать, поскольку сообщения не направляются в какое-либо конкретное место и должны быть доставлены лишь по принципу максимальных усилий. Узлы могут покидать сеть и присоединяться к ней по желанию, принимая цепочку proof-of-work как доказательство того, что произошло в их отсутствие. Они голосуют своей вычислительной мощностью CPU, выражая принятие действительных блоков работой над их продлением и отклоняя недействительные блоки отказом работать над ними. Любые необходимые правила и стимулы могут быть реализованы с помощью этого механизма консенсуса.
Conclusion
لقد اقترحنا نظاماً للمعاملات الإلكترونية دون الاعتماد على الثقة. بدأنا بالإطار المعتاد للعملات المصنوعة من digital signatures، الذي يوفر تحكماً قوياً في الملكية، لكنه غير مكتمل بدون طريقة لمنع double-spending. لحل هذا، اقترحنا شبكة peer-to-peer تستخدم proof-of-work لتسجيل تاريخ عام لـ transactions يصبح بسرعة غير عملي حسابياً لمهاجم تغييره إذا كانت honest nodes تتحكم في غالبية قدرة CPU. الشبكة متينة في بساطتها غير المنظمة. تعمل nodes جميعها في آن واحد بأقل قدر من التنسيق. لا تحتاج إلى التعريف بهويتها، حيث أن الرسائل لا تُوجَّه إلى مكان محدد وتحتاج فقط إلى التسليم على أساس best effort. يمكن لـ nodes مغادرة الشبكة والانضمام إليها مجدداً حسب رغبتها، مع قبول سلسلة proof-of-work كدليل على ما حدث أثناء غيابها. تصوت بقدرة CPU الخاصة بها، معبرة عن قبولها لـ blocks الصالحة بالعمل على تمديدها ورفض blocks غير الصالحة بالامتناع عن العمل عليها. يمكن فرض أي قواعد وحوافز ضرورية من خلال آلية consensus هذه.
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.
