Аннотация

Публичный реестр — это защищенная от несанкционированного доступа последовательность данных, которую может прочитать и дополнить каждый. Публичные реестры имеют бесчисленное множество интересных применений. Они могут обеспечить на виду все виды транзакций — таких как права собственности, продажи и платежи — в том порядке, в котором они происходят. Публичные реестры не только сдерживают коррупцию, но и позволяют использовать очень сложные приложения, такие как криптовалюты и smart contracts. Они намерены революционизировать способ построения демократического общества. действует. Однако в нынешнем виде они плохо масштабируются и не могут реализовать свой потенциал. Algorand — это действительно демократичный и эффективный способ внедрения публичного реестра. В отличие от предыдущего реализации, основанные на доказательстве работы, требуют незначительного объема вычислений и генерирует историю транзакций, которая не будет «разветвляться» с чрезвычайно высокой вероятностью. Algorand основан на (новом и сверхбыстром) византийском соглашении о передаче сообщений. Для конкретики мы будем описывать Algorand только как денежную платформу.

Введение

Деньги становятся все более виртуальными. Подсчитано, что около 80% населения США долларов сегодня существуют только в виде записей в бухгалтерской книге [5]. Другие финансовые инструменты следуют этому примеру. В идеальном мире, в котором мы могли бы рассчитывать на универсальную центральную структуру, неуязвимую для Несмотря на все возможные кибератаки, деньги и другие финансовые операции могут осуществляться исключительно электронно. К сожалению, мы живем не в таком мире. Соответственно, децентрализованные криптовалюты, такие как как Bitcoin [29] и системы «smart contract», такие как Ethereum, были предложены [4]. В сердцем этих систем является общий реестр, в котором надежно фиксируется последовательность транзакций. ∗Это более формальная (и асинхронная) версия статьи ArXiv второго автора [24], статьи сам основан на версии Горбунова и Микали [18]. Технологии Algorand являются объектом следующих патентные заявки: 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,931так же разнообразны, как платежи и контракты, и защищены от несанкционированного доступа. Технология выбора, гарантией такой защиты от несанкционированного доступа является blockchain. Блокчейны лежат в основе таких приложений, как криптовалюты [29], финансовые приложения [4] и Интернет вещей [3]. Несколько техник для управления реестрами на основе blockchain были предложены: доказательство работы [29], доказательство доли [2], практическая византийская отказоустойчивость [8] или какая-то комбинация. Однако в настоящее время управление реестрами может оказаться неэффективным. Например, proof-of-work Bitcoin. подход (основанный на исходной концепции [14]) требует огромного количества вычислений и является расточительным и плохо масштабируется [1]. Кроме того, она де-факто концентрирует власть в очень немногих руках. Поэтому мы хотим предложить новый метод реализации публичного реестра, который предлагает удобство и эффективность централизованной системы, управляемой доверенным и неприкосновенным органом, без неэффективность и слабости текущих децентрализованных реализаций. Мы называем наш подход Algorand, потому что мы используем алгоритмическую случайность для выбора на основе построенного на данный момент реестра, набор проверяющих, которые отвечают за создание следующего блока действительных транзакций. Естественно, мы гарантируем, что такие выборы будут доказуемо защищены от манипуляций и непредсказуемы до тех пор, пока в последнюю минуту, но также и то, что в конечном итоге они общеизвестны. Подход Algorand вполне демократичен в том смысле, что ни в принципе, ни де-факто он создает разные классы пользователей (как «майнеры» и «обычные пользователи» в Bitcoin). В Algorand «все власть принадлежит группе всех пользователей». Одним из примечательных свойств Algorand является то, что его история транзакций может разветвляться только при очень небольших вероятность (например, один на триллион, то есть или даже 10−18). Algorand также может касаться некоторых юридических вопросов. и политические проблемы. Подход Algorand применим к blockchain и, в более общем плане, к любому методу генерации защищенная от несанкционированного доступа последовательность блоков. Мы фактически предложили новый метод — альтернативный и более эффективен, чем blockchains — это может представлять независимый интерес. 1.1 Предположение Bitcoin и технические проблемы Bitcoin — очень изобретательная система, вдохновившая на большое количество последующих исследований. Тем не менее, это также проблематично. Давайте суммируем лежащее в его основе предположение и технические проблемы, которые фактически используются практически всеми криптовалютами, которые, например Bitcoin, основаны на proof-of-work. Для этого резюме достаточно вспомнить, что в Bitcoin пользователь может владеть несколькими открытыми ключами. схемы цифровой подписи, что деньги связаны с открытыми ключами и что платеж представляет собой цифровая подпись, которая переводит некоторую сумму денег с одного открытого ключа на другой. По сути, Bitcoin организует все обработанные платежи в цепочку блоков B1, B2, . . ., каждый из которых состоит из нескольких платежи, такие, что все платежи B1, взятые в любом порядке, за которыми следуют платежи B2 в любом порядке, и т. д. представляют собой последовательность действительных платежей. Каждый блок генерируется в среднем каждые 10 минут. Эта последовательность блоков представляет собой цепочку, поскольку она построена так, чтобы гарантировать, что любое изменение, даже в одном блоке, проникает во все последующие блоки, что облегчает обнаружение любых изменений история платежей. (Как мы увидим, это достигается за счет включения в каждый блок криптографического hash предыдущего.) Такая блочная структура называется blockchain. Предположение: честное большинство вычислительной мощности Bitcoin предполагает, что никакой злонамеренный организация (а не коалиция скоординированных злоумышленников) контролирует большую часть вычислительных ресурсов. мощность, предназначенная для генерации блоков. Фактически, такой объект сможет изменить blockchain,и таким образом переписать историю платежей, как угодно. В частности, он мог совершить платеж \(\wp\), получить оплаченные льготы, а затем «стирать» любые следы \(\wp\). Техническая проблема 1: Вычислительные отходы Подход Bitcoin proof-of-work к блокированию генерация требует огромного количества вычислений. В настоящее время насчитывается всего несколько сотен тысячи открытых ключей в системе, 500 самых мощных суперкомпьютеров могут только собрать всего 12,8% от общей вычислительной мощности, требуемой от игроков Bitcoin. Это объем вычислений значительно увеличится, если к системе присоединится значительно больше пользователей. Техническая проблема 2: Концентрация власти Сегодня из-за огромного количества требуется вычисление, пользователь, пытающийся сгенерировать новый блок, используя обычный рабочий стол (не говоря уже о сотовый телефон), рассчитывает потерять деньги. Действительно, для вычисления нового блока на обычном компьютере ожидаемая стоимость электроэнергии, необходимой для питания вычислений, превышает ожидаемое вознаграждение. Только используя пулы специально созданных компьютеров (которые не делают ничего, кроме «добычи новых блоков»), один может рассчитывать на получение прибыли за счет создания новых блоков. Соответственно, сегодня де-факто существует два разрозненные классы пользователей: обычные пользователи, которые только совершают платежи, и специализированные майнинговые пулы, которые ищут только новые блоки. Поэтому неудивительно, что с недавнего времени общая вычислительная мощность для блоков поколение находится всего в пяти пулах. В таких условиях предположение о том, что большинство Честная вычислительная мощность становится менее достоверной. Техническая проблема 3: Неясность В Bitcoin blockchain не обязательно уникален. действительно его последняя часть часто разветвляется: blockchain может быть, скажем, B1, . . . , Бк, Б' к+1, Б' k+2, согласно один пользователь и B1, . . . , Бк, Б'' к+1, Б'' к+2, Б'' k+3 по словам другого пользователя. Только после того, как пройдет несколько блоков добавлены в цепочку, можно ли быть достаточно уверенным, что первые k + 3 блока будут одинаковыми? для всех пользователей. Таким образом, нельзя сразу полагаться на выплаты, содержащиеся в последнем блоке цепь. Разумнее подождать и посмотреть, станет ли блок достаточно глубоким в blockchain и, таким образом, достаточно стабилен. Отдельно были высказаны опасения со стороны правоохранительных органов и денежно-кредитной политики в отношении Bitcoin.1. 1.2 Algorand, в двух словах Настройка Algorand работает в очень жестких условиях. Вкратце, (a) Неразрешенные и разрешенные среды. Algorand работает эффективно и безопасно даже в полностью закрытой среде, где сколь угодно много пользователей могут присоединиться к системе в любое время, без какой-либо проверки или разрешения любого рода. Конечно, Algorand работает. еще лучше в разрешенной среде. 1(Псевдо) анонимность, обеспечиваемая платежами Bitcoin, может быть использована неправомерно для отмывания денег и/или финансирования. преступников или террористических организаций. Традиционные банкноты или золотые слитки, которые в принципе предлагают идеальные анонимность должна представлять собой ту же проблему, но физическая форма этих валют существенно замедляет движение денег. переводы, чтобы обеспечить определенную степень контроля со стороны правоохранительных органов. Способность «печатать деньги» является одной из основных полномочий национального государства. Поэтому в принципе массовое принятие независимо плавающей валюты может ограничить эту власть. Однако в настоящее время Bitcoin далек от представляет собой угрозу правительственной денежно-кредитной политике и из-за проблем с масштабируемостью, возможно, никогда ею не станет.(б) Очень враждебная среда. Algorand противостоит очень сильному противнику, который может (1) мгновенно испортить любого пользователя, которого он хочет, в любое время, когда он хочет, при условии, что в неразрешенная среда, 2/3 денег в системе принадлежит честному пользователю. (В разрешенная среда, независимо от денег, достаточно, чтобы 2/3 пользователей были честными.) (2) полностью контролировать и идеально координировать всех коррумпированных пользователей; и (3) запланировать доставку всех сообщений при условии, что каждое сообщение m отправлено честным пользователем. достигает 95% честных пользователей за время \(\lambda\)m, которое зависит исключительно от размера m. Основные свойства Несмотря на присутствие нашего мощного противника, в Algorand • Требуемый объем вычислений минимален. По сути, независимо от того, сколько пользователей присутствующих в системе, каждый из полутора сотен пользователей должен выполнить не более нескольких секунд расчет. • Новый блок создается менее чем за 10 минут и фактически никогда не покидает blockchain. Например, ожидаемое время генерации блока в первом варианте меньше чем Λ + 12,4\(\lambda\), где Λ — время, необходимое для распространения блока в одноранговой сплетне независимо от того, какой размер блока вы выберете, а \(\lambda\) — это время для распространения 1500 сообщений 200Blong. (Поскольку в действительно децентрализованной системе Λ по существу является внутренней задержкой, в Algorand ограничивающим фактором при генерации блоков является скорость сети.) Второй вариант осуществления имеет фактически был протестирован экспериментально (?), что указывает на то, что блок генерируется менее чем за 40 секунды. Кроме того, blockchain из Algorand может разветвляться только с пренебрежимо малой вероятностью (т. е. менее одной в триллионе), и, таким образом, пользователи могут рассчитывать на платежи, содержащиеся в новом блоке, как только появляется блок. • Вся власть принадлежит самим пользователям. Algorand — это настоящая распределенная система. В частности, нет экзогенных объектов (таких как «майнеры» в Bitcoin), которые могли бы контролировать, какие транзакции признаны. Техники Algorand. 1. Новый и быстрый протокол Византийского соглашения. Algorand генерирует новый блок через новый криптографический протокол передачи сообщений двоичного византийского соглашения (BA), BA⋆. Протокол BA⋆не только обладает некоторыми дополнительными свойствами (которые мы вскоре обсудим), но и очень быстр. Грубо говоря, его версия с двоичным вводом состоит из трехэтапного цикла, в котором игрок i отправляет одиночный сигнал. сообщение mi всем остальным игрокам. Выполняется в полной и синхронной сети с более чем 2/3 игроков честны, с вероятностью > 1/3, после каждого цикла протокол заканчивается соглашение. (Мы подчеркиваем, что протокол BA⋆ удовлетворяет первоначальному определению византийского соглашения. Пиза, Шостака и Лэмпорта [31] без каких-либо ослаблений.) Algorand использует этот двоичный протокол BA для достижения соглашения в наших различных коммуникациях. модель, на каждом новом блоке. Согласованный блок затем сертифицируется через заданное количество цифровую подпись соответствующих проверяющих лиц и распространяется по сети. 2. Криптографическая сортировка. Несмотря на то, что протокол BA⋆ очень быстрый, его дальнейшее развитие могло бы принести пользу. скорость, когда в нее играют миллионы пользователей. Соответственно, Algorand выбирает игроков BA⋆, которые будутгораздо меньшее подмножество всех пользователей. Во избежание различного рода концентрации власти проблема, каждый новый блок Br будет построен и согласован посредством нового выполнения BA⋆, отдельным набором выбранных проверяющих, SV r. В принципе, подобрать такой набор может быть так же сложно, как и выбрав Br напрямую. Мы решаем эту потенциальную проблему с помощью подхода, который мы называем проницательное предложение Мориса Херлихи — криптографическая сортировка. Сортировка – это практика выбор должностных лиц случайным образом из большого числа подходящих лиц [6]. (практиковалась сортировка на протяжении веков: например, республиками Афин, Флоренции и Венеции. В современном судебном В системах присяжных часто используется случайный отбор. Случайная выборка также была недавно за выборы выступал Дэвид Чаум [9].) В децентрализованной системе, конечно, выбор случайные монеты, необходимые для случайного выбора членов каждого набора проверяющих SV r, проблематичны. Таким образом, мы прибегаем к криптографии, чтобы выбрать каждый набор проверяющих из совокупности всех пользователей. таким образом, который гарантированно будет автоматическим (т. е. не требующим обмена сообщениями) и случайным. По сути, мы используем криптографическую функцию для автоматического определения по предыдущему блоку Br-1, пользователь, лидер, отвечающий за предложение нового блока Br, и набор верификаторов SV r, в поручить достичь согласия по предложенному лидером блоку. Поскольку злонамеренные пользователи могут повлиять состав Br−1 (например, выбрав некоторые из его платежей) мы специально строим и используем дополнительные входные данные, чтобы доказать, что лидер r-го блока и набор проверяющих SV r действительно являются выбран случайно. 3. Количество (семя) Qr. Мы используем последний блок Br-1 в blockchain, чтобы автоматически определяет следующий набор верификаторов и лидера, отвечающего за построение нового блока Бр. Проблема с этим подходом заключается в том, что, просто выбрав немного другой платеж в В предыдущем раунде наш могущественный противник получает огромный контроль над следующим лидером. Даже если он контролировал только 1/1000 игроков/денег в системе, он мог гарантировать, что все лидеры злонамеренный. (См. раздел «Интуиция» 4.1.) Эта проблема является центральной для всех подходов proof-of-stake, и, насколько нам известно, она до сих пор не решена удовлетворительно. Чтобы решить эту задачу, мы намеренно создаем и постоянно обновляем отдельный и тщательно определенную величину Qr, которая, как доказуемо, не только непредсказуема, но и не поддается влиянию с точки зрения наших мощный противник. Мы можем называть Qr r-м семенем, поскольку именно из Qr выбирает Algorand, посредством секретной криптографической сортировки все пользователи, которые будут играть особую роль в создании й блок. 4. Секретная криптографическая сортировка и секретные учетные данные. Случайным образом и однозначно используя текущий последний блок, Br-1, для выбора набора проверяющих и ответственного лидера. строительства нового блока Бр недостаточно. Поскольку Br−1 должно быть известно до генерации Br, должна быть также известна последняя независимая величина Qr−1, содержащаяся в Br−1. Соответственно, так являются проверяющими и лидером, отвечающим за вычисление блока Br. Таким образом, наш могущественный Противник могли бы немедленно развратить их всех, прежде чем они вступят в какую-либо дискуссию о Бр, чтобы получить полный контроль над блоком, который они сертифицируют. Чтобы предотвратить эту проблему, лидеры (а фактически и проверяющие тоже) тайно узнают о своей роли, но могут вычислить правильные учетные данные, способные доказать всем, кто действительно выполняет эту роль. Когда пользователь тайно осознает, что является лидером следующего блока, сначала он тайно собирает свой самостоятельно предложенный новый блок, а затем распространяет его (чтобы его можно было сертифицировать) вместе со своим собственным учетные данные. Таким образом, хотя Противник сразу поймет, кто лидер следующего блок есть, и хотя он может развратить его сразу, Противнику будет уже слишком поздно повлиять на выбор нового блока. Действительно, он больше не может «перезвонить» посланию лидера.чем могущественное правительство сможет положить обратно в бутылку сообщение, вирусно распространенное WikiLeaks. Как мы увидим, мы не можем гарантировать ни уникальность лидера, ни то, что все точно знают, кто лидер. есть, включая самого лидера! Но в Algorand однозначный прогресс будет гарантирован. 5. Заменяемость игроков. После того, как он предложит новый блок, лидер может с тем же успехом «умереть» (или быть испорчен Противником), потому что его работа выполнена. Но для проверяющих в SV r дела обстоят сложнее. простой. Действительно, отвечая за сертификацию нового блока Br с достаточным количеством подписей, они должны сначала провести византийское соглашение по предложенному вождем блоку. Проблема в том, что независимо от того, насколько он эффективен, BA⋆ требует нескольких шагов и честности > 2/3 своих игроков. Это проблема, поскольку из соображений эффективности набор игроков BA⋆ состоит из небольшого набора SV r случайно выбранный среди множества всех пользователей. Таким образом, наш могущественный Противник, хотя и неспособный испортил 1/3 всех пользователей, безусловно, может испортить всех членов SV r! К счастью, мы докажем, что протокол BA⋆, выполняющийся путем распространения сообщений в одноранговой сети, может быть заменен игроком. Это новое требование означает, что протокол правильно и эффективно достигает консенсуса, даже если каждый его шаг выполняется совершенно новым и случайным образом и независимо выбранный набор игроков. Таким образом, при миллионах пользователей каждая небольшая группа игроков связанный с шагом BA⋆, скорее всего, имеет пустое пересечение со следующим множеством. Кроме того, наборы игроков разных ступеней BA⋆, вероятно, будут иметь совершенно разные мощности. Более того, члены каждой группы не знают, кто будет следующей группой игроков. быть, и не передавать тайно никакого внутреннего состояния. Свойство сменного игрока на самом деле имеет решающее значение для победы над динамичным и очень мощным игроком. Противника мы видим. Мы считаем, что протоколы сменных игроков окажутся решающими во многих контексты и приложения. В частности, они будут иметь решающее значение для безопасного выполнения небольших подпротоколов. встроен в большую вселенную игроков с динамичным противником, который, будучи в состоянии развратить даже небольшая часть от общего числа игроков, не имеет труда развратить всех игроков в меньших субпротокол. Дополнительное свойство/техника: ленивая честность Честный пользователь следует своим предписаниям инструкции, которые включают в себя пребывание в сети и запуск протокола. Поскольку Algorand имеет лишь скромные требования к вычислениям и связи, нахождение в сети и запуск протокола «в фон» не является большой жертвой. Конечно, некоторые «отсутствия» среди честных игроков, как те, из-за внезапной потери соединения или необходимости перезагрузки автоматически допускаются (поскольку мы всегда можем считать таких немногих игроков временно злонамеренными). Отметим, однако, что Algorand можно просто адаптировать для работы в новой модели, в которой будут честные пользователи большую часть времени офлайн. Нашу новую модель можно неформально представить следующим образом. Ленивая честность. Грубо говоря, пользователь i является ленивым, но честным, если (1) он следует всем предписанным ему правилам. инструкции, когда его просят принять участие в протоколе, и (2) его просят принять участие протоколу лишь в редких случаях и с соответствующим предварительным уведомлением. При таком смягченном представлении о честности мы можем быть еще более уверены в том, что честные люди будут под рукой, когда они нам понадобятся, и Algorand гарантирует, что в этом случае Система работает безопасно, даже если в определенный момент времени большинство участвующих игроков являются злонамеренными.1.3 Тесно связанные работы Подходы Proof-of-Work (например, упомянутые [29] и [4]) вполне ортогональны нашим. Как и подходы, основанные на византийском соглашении о передаче сообщений или практической византийской отказоустойчивости (например, процитированный [8]). Действительно, эти протоколы не могут быть запущены среди множества всех пользователей и не могут, в нашей модели быть ограничены достаточно небольшим набором пользователей. Фактически, наш могущественный противник мой немедленно испортить всех пользователей, участвующих в небольшой группе, обвиненной в фактическом запуске протокола BA. Наш подход можно считать связанным с доказательством доли [2] в том смысле, что «власть» пользователей в блочном строительстве пропорциональна деньгам, которыми они владеют в системе (в отличие, скажем, от деньги, которые они положили на «эскроу»). Наиболее близкой к нашей статье является Модель сонного консенсуса Пасса и Ши [30]. Чтобы избежать тяжелые вычисления, необходимые в подходе proof-of-work, на которые опирается их статья (и любезно кредиты) секретная криптографическая сортировка Algorand. Этот решающий аспект является общим для нескольких Между нашими статьями существуют существенные различия. В частности, (1) Их установка разрешена. Напротив, Algorand также является системой без разрешений. (2) Они используют протокол в стиле Накамото, поэтому их blockchain часто разветвляется. Хотя обходясь без proof-of-work, в их протоколе тайно выбранному лидеру предлагается удлинить самый длинный действительный (в более широком смысле) blockchain. Таким образом, вилки неизбежны и приходится ждать, чтобы блок находится достаточно «глубоко» в цепи. Ведь для достижения своих целей с противником способные к адаптивным повреждениям, они требуют, чтобы блок имел глубину поли(N), где N представляет собой общее количество пользователей в системе. Обратите внимание, что даже если предположить, что блок может быть создан в минуту, если бы было N = 1M пользователей, то пришлось бы ждать около 2M лет блок станет глубиной N 2, и в течение примерно 2 лет блок станет глубиной N. Напротив, blockchain Algorand разветвляется с незначительной вероятностью, даже несмотря на то, что Противник повредил пользователи сразу и адаптивно, и на его новые блоки можно сразу же положиться. (3) Они не занимаются отдельными византийскими соглашениями. В каком-то смысле они лишь гарантируют «возможный консенсус в отношении растущей последовательности ценностей». Это протокол репликации состояния, а не чем BA, и не может использоваться для достижения византийского соглашения об индивидуальной ценности интересов. Напротив, Algorand при желании можно использовать только один раз, чтобы позволить миллионам пользователей быстро достичь византийского соглашения о конкретной стоимости процентов. (4) Они требуют слабо синхронизированных часов. То есть часы всех пользователей смещены на небольшое время. δ. Напротив, в Algorand часы должны иметь только (по сути) одинаковую «скорость». (5) Их протокол работает с ленивыми, но честными пользователями или с честным большинством онлайн-пользователей. Они выражают благодарность Algorand за то, что он поднял вопрос о массовом выходе честных пользователей из сети, а также за в ответ выдвигая модель ленивой честности. Их протокол работает не только для ленивых модель честности, но и в их состязательной сонной модели, где противник выбирает, каких пользователей находятся онлайн, а какие оффлайн, при условии, что большинство онлайн-пользователей всегда честны.2 2Первоначальная версия их статьи фактически рассматривала только безопасность в их состязательной сонной модели.

исходная версия Algorand, которая предшествует их версии, также явно предполагала, что определенное большинство онлайн-игроки всегда честны, но явно исключили это из рассмотрения в пользу модели ленивой честности. (Например, если в какой-то момент половина честных пользователей решит выйти из сети, то большинство пользователей on-line вполне может быть вредоносным. Таким образом, чтобы этого не произошло, Противник должен форсировать большую часть своих сил. испорченные игроки тоже выходят из игры, что явно противоречит его собственным интересам.) Обратите внимание, что протокол с большинством голосов ленивых, но честных игроков прекрасно работает, если большинство онлайн-пользователей всегда являются злонамеренными. Это так, потому что достаточное количество честных игроков, зная, что они будут иметь решающее значение в какой-то редкий момент времени, выберут не выходить из сети в эти моменты, и при этом Противник не может заставить их отключиться от сети, поскольку он не знает, кто решающими могут оказаться честные игроки.(6) Они требуют простого честного большинства. Напротив, текущая версия Algorand требует честное большинство в 2/3. Еще одна близкая нам статья — «Уроборос: доказуемо безопасный протокол блокчейна с доказательством доли», Киайяс, Рассел, Дэвид и Олейников [20]. И их система появилась после нашей. Это также использует криптографическую сортировку, чтобы обойтись без доказательства работы доказуемым образом. Однако их Система, опять же, представляет собой протокол в стиле Накамото, в котором разветвления неизбежны и часты. (Однако в их модели блоки не должны быть такими глубокими, как в модели сонного консенсуса.) Более того, их система опирается на следующие предположения: по словам самих авторов, «(1) сеть высокосинхронна, (2) большинство выбранных заинтересованных сторон доступны по мере необходимости участвовать в каждой эпохе, (3) заинтересованные стороны не остаются в автономном режиме в течение длительных периодов времени, (4) адаптивность коррупции подвержена небольшой задержке, которая измеряется в раундах, линейных по параметр безопасности». Напротив, Algorand с подавляющей вероятностью не имеет вилки и не опирается ни на одно из этих 4 предположений. В частности, в Algorand Противник имеет возможность мгновенно развратить пользователей, которых он хочет контролировать.

Предварительные сведения

2.1 Криптографические примитивы Идеальное хеширование. Мы будем полагаться на эффективно вычислимую криптографическую hash функцию H, которая отображает строки произвольной длины в двоичные строки фиксированной длины. Следуя давней традиции, мы моделируем H как случайное oracle, по существу функция, отображающая каждую возможную строку s в случайную и независимо выбранная (а затем фиксированная) двоичная строка H(s) выбранной длины. В этой статье H имеет выходные данные длиной 256 бит. Действительно, такая длина достаточно коротка, чтобы сделать эффективность системы и достаточно длительный срок, чтобы сделать систему безопасной. Например, мы хотим, чтобы H был устойчив к столкновениям. То есть должно быть сложно найти две разные строки x и y такие, что H(x) = H(y). Когда H представляет собой случайное число oracle с выходными данными длиной 256 бит, найти любую такую пару строк действительно сложно. сложно. (Для случайной попытки и использования парадокса дня рождения потребуется 2256/2 = 2128. испытания.) Цифровая подпись. Цифровые подписи позволяют пользователям удостоверять подлинность информации друг друга. не разглашая никаких секретных ключей. Схема цифровой подписи состоит из трех быстрых Алгоритмы: вероятностный генератор ключей G, алгоритм подписи S и алгоритм проверки V. Учитывая параметр безопасности k, достаточно большое целое число, пользователь i использует G для создания пары k-битные ключи (т. е. строки): «открытый» ключ pki и соответствующий «секретный» ключ подписи Ski. Крайне важно, открытый ключ не «выдает» соответствующий секретный ключ. То есть, даже учитывая знание pki, нет еще один человек, кроме меня, способен рассчитать лыжи менее чем за астрономическое время. Пользователь i использует лыжи для цифровой подписи сообщений. Для каждого возможного сообщения (двоичной строки) m я сначала hashes m, а затем запускает алгоритм S на входах H(m) и на лыжах, чтобы создать k-битную строку sigpki(м) \(\triangleq\)S(H(м), лыжи) .3 3Поскольку H устойчив к коллизиям, практически невозможно, чтобы, подписав m, кто-то «случайно подписал» другой сообщение м'.Двоичная строка sigpki(m) называется цифровой подписью i m (относительно pki) и может быть проще обозначается sigi(m), когда открытый ключ pki ясен из контекста. Каждый, кто знает pki, может использовать его для проверки цифровых подписей, созданных i. В частности, на вводит (a) открытый ключ pki игрока i, (b) сообщение m и (c) строку s, то есть предполагаемый i цифровую подпись сообщения m, алгоритм проверки V выдает либо ДА, либо НЕТ. Свойства, которые нам необходимы от схемы цифровой подписи: 1. Легитимность подписей всегда проверяется: если s = sigi(m), то V (pki, m, s) = Y ES; и 2. Цифровые подписи сложно подделать: без знания лыж время найти такую строку что V (pki, m, s) = Y ES для сообщения m, никогда не подписанного i, является астрономически длинным. (Следуя строгим требованиям безопасности Голдвассера, Микали и Ривеста [17], это правда. даже если можно получить подпись любого другого сообщения.) Соответственно, чтобы никто другой не мог подписывать сообщения от его имени, игрок i должен сохранить подписывание секретного ключа (отсюда и термин «секретный ключ») и предоставление возможности любому человеку проверять сообщения. он подписывает, и я заинтересован в обнародовании его ключа PKI (отсюда и термин «открытый ключ»). В общем, сообщение m невозможно получить по его сигнатуре sigi(m). Чтобы виртуально разобраться с цифровыми подписями, которые удовлетворяют концептуально удобному свойству «извлекаемости» (т.е. гарантировать, что подписывающее лицо и сообщение легко вычислимы по подписи, мы определяем SIGpki(m) = (i, m, sigpki(m)) и SIGi(m) = (i, m, sigi(m)), если pki ясен. Уникальная цифровая подпись. Мы также рассматриваем схемы цифровой подписи (G, S, V), удовлетворяющие следующее дополнительное имущество. 3. Уникальность. Трудно найти строки pk', m, s и s' такие, что s ̸= s′ и V (pk′,m,s) = V (pk′,m,s′) = 1. (Обратите внимание, что свойство уникальности справедливо и для строк pk', которые не были сгенерированы законным образом. открытые ключи. Однако, в частности, свойство уникальности подразумевает, что если использовать указанный генератор ключей G для вычисления открытого ключа pk вместе с соответствующим секретным ключом sk, и, таким образом, зная sk, для него было бы практически невозможно найти два разных цифровых подписи одного и того же сообщения относительно pk.) Примечания • От уникальных подписей до проверяемых случайных функций. По отношению к цифровому схеме подписи со свойством единственности отображение m \(\to\) H(sigi(m)) соответствует каждая возможная строка m, уникальная, случайно выбранная 256-битная строка, и правильность этого отображение можно доказать с помощью сигнатуры sigi(m). То есть идеальная hashing и схема цифровой подписи, по существу удовлетворяющая свойству уникальности. обеспечить элементарную реализацию проверяемой случайной функции, как это было введено и Микали, Рабин и Вадхан [27]. (Их первоначальная реализация была обязательно более сложной, поскольку они не полагались на идеальное hashing.)• Три различных потребности в цифровых подписях. В Algorand пользователь i полагается на цифровые подписи для (1) Аутентификация собственных платежей. В этом приложении ключи могут быть «долгосрочными» (т.е. использоваться для подписывать множество сообщений в течение длительного периода времени) и исходят из обычной схемы подписи. (2) Генерация учетных данных, доказывающих, что i имеет право действовать на каком-то этапе s раунда r. Здесь, ключи могут быть долгосрочными, но должны исходить из схемы, удовлетворяющей свойству уникальности. (3) Аутентификация сообщения, которое я отправляю на каждом этапе своих действий. Здесь ключи должны быть эфемерны (т. е. уничтожаются после первого использования), но могут исходить из обычной схемы подписи. • Небольшое упрощение. Для простоты мы предполагаем, что у каждого пользователя i будет один долгосрочный ключ. Соответственно, такой ключ должен исходить из схемы подписи с уникальностью собственность. Такая простота требует небольших вычислительных затрат. Обычно, по сути, уникальные цифровые Изготовление и проверка подписей немного дороже, чем обычные подписи. 2.2 Идеализированный публичный реестр Algorand пытается имитировать следующую платежную систему, основанную на идеализированном публичном реестре. 1. Исходное состояние. Деньги связаны с отдельными открытыми ключами (генерируемыми частным образом и принадлежат пользователям). Сдача pk1, . . . , pkj — начальные открытые ключи и a1, . . . , адж их соответствующие начальные суммы денежных единиц, то начальный статус S0 = (pk1, a1), . . . , (pkj, aj) , которая считается общеизвестной в системе. 2. Платежи. Пусть pk — открытый ключ, имеющий в данный момент \(\geq\)0 денежных единиц, pk’ — другой открытый ключ. ключ и a' - неотрицательное число, не превышающее a. Тогда (действительный) платеж \(\wp\) является цифровым подпись относительно pk, определяющая перевод a' денежных единиц из pk в pk' вместе с некоторой дополнительной информацией. В символах, \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), где я представляю любую дополнительную информацию, которая считается полезной, но не конфиденциальной (например, время информацию и идентификатор платежа), а также любую дополнительную информацию, которая считается конфиденциальной (например, причина платежа, возможно, личности владельцев ПК и ПК' и так далее). Мы называем pk (или его владельца) плательщиком, каждого pk' (или его владельца) - получателем платежа, а a' - сумма платежа \(\wp\). Бесплатное присоединение через платежи. Обратите внимание, что пользователи могут присоединиться к системе, когда захотят. генерация собственных пар открытого/секретного ключей. Соответственно, открытый ключ pk', который появляется в платеж \(\wp\)выше может быть недавно сгенерированным открытым ключом, который никогда не «владел» деньгами раньше. 3. Волшебная книга. В идеализированной системе все платежи действительны и отображаются в защищенном от несанкционированного доступа виде. список L наборов платежей, «размещенных на небе» на всеобщее обозрение: L = ПЛАТИТЕ 1, ПЛАТИТЕ 2, . . . ,Каждый блок PAY r+1 состоит из совокупности всех платежей, совершенных с момента появления блока ПЛАТИТЬ р. В идеальной системе новый блок появляется через фиксированное (или конечное) время. Обсуждение. • Больше общих платежей и неизрасходованных выходных транзакций. В более общем смысле, если открытый ключ pk владеет суммой a, то действительный платеж \(\wp\)pk может перевести суммы a' 1, а' 2, . . ., соответственно клавишам pk' 1, пк' 2, . . ., пока P джа' j \(\leq\)а. В Bitcoin и подобных системах деньги, принадлежащие ПК с открытым ключом, разделены на отдельные суммы, и платеж \(\wp\), произведенный pk, должен передать такую отдельную сумму a полностью. Если pk хочет передать на другой ключ только часть a' < a, то он должен также передать баланс, неизрасходованный вывод транзакции, на другой ключ, возможно, на сам ПК. Algorand также работает с ключами, имеющими отдельные суммы. Однако для того, чтобы сосредоточиться на новые аспекты Algorand, концептуально проще придерживаться наших более простых форм платежей и ключи, имеющие одну связанную с ними сумму. • Текущий статус. Идеализированная схема не предоставляет напрямую информацию о текущем состоянии. статус системы (т. е. сколько денежных единиц имеет каждый открытый ключ). Эта информация выводится из Magic Ledger. В идеальной системе активный пользователь постоянно сохраняет и обновляет самую свежую информацию о состоянии. иначе ему пришлось бы восстанавливать его либо с нуля, либо с того момента, когда он в последний раз вычислил это. (В следующей версии этой статьи мы дополним Algorand, чтобы сделать его пользователи могут эффективно восстановить текущий статус.) • Безопасность и «Конфиденциальность». Цифровые подписи гарантируют, что никто не сможет подделать платеж другой пользователь. При платеже \(\wp\) открытые ключи и сумма не скрыты, а конфиденциальные информация я есть. Действительно, в \(\wp\) появляется только H(I), и поскольку H — идеальная hash функция, H(I) — это случайное 256-битное значение, и поэтому нет способа выяснить, в чем я был лучше, чем с помощью просто догадываюсь об этом. Тем не менее, чтобы доказать, кем я был (например, доказать причину выплаты), плательщик может просто раскрыть I. Правильность раскрытого I можно проверить, вычислив H(I) и сравниваем полученное значение с последним элементом \(\wp\). Фактически, поскольку H устойчив к столкновениям, трудно найти второе значение I′ такое, что H(I) = H(I′). 2.3 Основные понятия и обозначения Ключи, пользователи и владельцы Если не указано иное, каждый открытый ключ («ключ» для краткости) является долгосрочным и относится к схеме цифровой подписи со свойством уникальности. Открытый ключ, к которому я присоединяюсь системе, когда другой открытый ключ j, уже находящийся в системе, производит платеж i. Для цвета мы персонифицируем ключи. Мы называем ключ i «он», говорим, что я честен, что я посылаю и получает сообщения и т. д. Пользователь — синоним ключа. Когда мы хотим отличить ключ от лицу, которому он принадлежит, мы соответственно используем термины «цифровой ключ» и «владелец». Безразрешительные и разрешенные системы. Система является недоступной, если цифровой ключ свободен. присоединиться в любое время, и владелец может владеть несколькими цифровыми ключами; и это разрешено, в противном случае.Уникальное представление Каждый объект в Algorand имеет уникальное представление. В частности, каждое множество {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} упорядочивается заранее заданным образом: например, сначала лексикографически по x, затем по y и т. д. Односкоростные часы Глобальных часов нет: у каждого пользователя свои часы. Пользовательские часы ни в коем случае не нужно синхронизировать. Однако мы предполагаем, что все они имеют одинаковую скорость. Например, если по часам пользователя i сейчас 12:00, по часам пользователя i это может быть 14:30. часы другого пользователя j, но когда по часам i будет 12:01, по часам i будет 2:31 на часы Джей. То есть «одна минута одинакова (достаточно, по сути одинакова) для каждого пользователя». Раунды Algorand организован в логических единицах, r = 0, 1, . . ., называемые раундами. Мы постоянно используем верхние индексы для обозначения раундов. Чтобы указать, что нечисловая величина Q (например, строка, открытый ключ, набор, цифровая подпись и т. д.) относится к раунду r, мы просто пишем Qr. Только когда Q является настоящим числом (в отличие от двоичной строки, интерпретируемой как число), выполните мы пишем Q(r), так что символ r нельзя интерпретировать как показатель степени Q. В (начале a) раунда r > 0 набор всех открытых ключей равен PKr, а состояние системы равно Ср = н я, а(р) я, . . .  : я €PKro , где а(г) я это сумма денег, доступная для открытого ключа i. Заметим, что PKr выводится из Sr, и что Sr может также указывать другие компоненты для каждого открытого ключа i. Для раунда 0 PK0 — это набор начальных открытых ключей, а S0 — начальный статус. И ПК0, и Предполагается, что S0 являются общеизвестными в системе. Для простоты в начале раунда r, так что ПК1, . . . , ПКр и S1, . . . , сэр. В раунде r статус системы меняется с Sr на Sr+1: символически, Раунд r: Sr −→Sr+1. Платежи В Algorand пользователи постоянно совершают платежи (и распространяют их описано в подразделе 2.7). Платеж \(\wp\) пользователя i \(\in\)PKr имеет тот же формат и семантику. как в идеальной системе. А именно, \(\wp\)= SIGi(i, i′, a, I, H(I)) . Платеж \(\wp\) индивидуально действителен в раунде r (для краткости это платеж в раунде r), если (1) его сумма a меньше или равно a(r) i , и (2) он не появляется ни в одном официальном наборе выплат PAY r' для r' < r. (Как поясняется ниже, второе условие означает, что \(\wp\) еще не вступило в силу. Набор раундов r платежей i является коллективно действительным, если сумма их сумм не превышает a(r) я. Платёжные системы Набор выплат P в раунде r — это набор платежей в раунде r, такой, что для каждого пользователя i платежи из i в P (возможно, ни одного) являются коллективно действительными. Набор всех наборов выплат раунда r равен PAY(r). Раунд-р набор выплат P является максимальным, если ни один надмножество P не является набором выплат раунда r. Фактически мы предполагаем, что платеж \(\wp\)также определяет раунд \(\rho\), \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , и не может быть действительным ни в одном раунде за пределами [\(\rho\), \(\rho\) + k] для некоторого фиксированного неотрицательного целого числа k.4 4Это упрощает проверку того, стал ли \(\wp\) «эффективным» (т. е. упрощает определение того, является ли некоторый набор выплат PAY r содержит \(\wp\). Когда k = 0, если \(\wp\)= SIGi(r, i, i′, a, I, H(I)) и \(\wp\)/\(\varepsilon\)PAY r, то я должен повторно отправить \(\wp\).Официальные платежные системы В каждом раунде r Algorand публично выбирает (способом, описанным ниже) один (возможно, пустой) набор выплат, PAY r, официальный набор выплат раунда. (По сути, PAY r представляет собой платежи раунда R, которые «на самом деле» произошли.) Как и в идеальной системе (и Bitcoin), (1) единственный способ для нового пользователя j войти в систему должен быть получателем платежа, принадлежащего официальному набору платежей PAY r данного раунда r; и (2) PAY r определяет статус следующего раунда Sr+1 на основе статуса текущего раунда Sr. Символически, ПЛАТА r : Sr −→Sr+1. В частности, 1. набор открытых ключей раунда r+1, PKr+1, состоит из объединения PKr и множества всех ключи получателя платежа, которые впервые появляются в платежах PAY r; и 2. количество денег a(r+1) я которым владеет пользователь i в раунде r + 1, представляет собой сумму ai(r) — т. е. сумма денег, которой я владел в предыдущем раунде (0, если i ̸\(\varepsilon\)PKr) — и сумма сумм выплачивается i согласно выплатам PAY р. В целом, как и в идеальной системе, каждый статус Sr+1 выводится из предыдущей истории платежей: ПЛАТИТЬ 0, . . . , ПЛАТИТЕ р. 2.4 Блоки и проверенные блоки В Algorand0 блок Br, соответствующий раунду r, определяет: сам r; набор платежей круглый r, ЗАПЛАТИТЕ r; количество Qr, которое необходимо объяснить, и hash предыдущего блока, H(Br-1). Таким образом, начиная с некоторого фиксированного блока B0, мы имеем традиционный blockchain: B1 = (1, ПЛАТИТЬ 1, Q0, H(B0)), B2 = (2, ПЛАТИТЬ 2, Q1, H(B1)), B3 = (3, ПЛАТИТЬ 3, Q2, H(B2)), . . . В Algorand подлинность блока фактически подтверждается отдельной информацией, «сертификат блока» CERT r, который превращает Br в проверенный блок, Br. Таким образом, Волшебная книга реализуется последовательностью проверенных блоков, Б1, Б2, . . . Обсуждение Как мы увидим, CERT r состоит из набора цифровых подписей для H(Br), большинства членов SV r вместе с доказательством того, что каждый из этих членов действительно принадлежит до СВ р. Мы могли бы, конечно, включить сертификаты CERT r в сами блоки, но обнаружили бы, что концептуально чище, если держать его отдельно.) В Bitcoin каждый блок должен удовлетворять специальному свойству, то есть должен «содержать решение задачи». крипто-головоломка», что делает генерацию блоков вычислительно интенсивной и форки неизбежны. и не редкость. Напротив, Algorand blockchain имеет два основных преимущества: он генерируется с помощью минимальные вычисления, и он не будет разделяться с чрезвычайно высокой вероятностью. Каждый блок Bi безопасным финалом, как только он войдет в blockchain.2,5 Приемлемая вероятность отказа Чтобы проанализировать безопасность Algorand, мы указываем вероятность F, с которой мы готовы признать, что что-то идет не так (например, что набор проверяющих SV r не имеет честного большинства). Как и в случае с выходной длиной криптографической hash функции H, F также является параметром. Но, как и в этом случае, мы считаем полезным присвоить F конкретное значение, чтобы получить более интуитивное представление. понимание того факта, что в Algorand действительно возможно одновременно наслаждаться достаточной безопасностью и достаточная эффективность. Чтобы подчеркнуть, что F — это параметр, который можно установить по желанию, в первом и второй варианты осуществления мы соответственно установили Ф = 10−12 и Ф = 10−18 . Обсуждение Обратите внимание, что 10−12 на самом деле меньше одного на триллион, и мы считаем, что такое выбор F является адекватным для нашего приложения. Подчеркнем, что 10−12 — это не вероятность с помощью которого Злоумышленник может подделать платежи честного пользователя. Все платежи в цифровом формате подписано, и, таким образом, если используются надлежащие цифровые подписи, вероятность подделки платежа намного ниже, чем 10−12, и фактически равно 0. Плохое событие, которое мы готовы терпеть с вероятностью F то, что blockchain Algorand разветвляется. Обратите внимание, что с нашими настройками F и продолжительностью в одну минуту, ожидается, что вилка будет происходить в blockchain Algorand так редко, как (примерно) раз в 1,9 миллиона лет. Напротив, в Bitcoin вилки возникают довольно часто. Более требовательный человек может установить F на более низкое значение. Для этого в нашем втором варианте мы рассматриваем установку F равным 10−18. Обратите внимание: если предположить, что блок генерируется каждую секунду, 1018 — приблизительное количество секунд, затраченное Вселенной на данный момент: от Большого взрыва до настоящего времени. время. Таким образом, при F = 10−18, если блок генерируется за секунду, следует ожидать возраста Вселенная, чтобы увидеть развилку. 2.6 Состязательная модель Algorand предназначен для обеспечения безопасности в очень состязательной модели. Давайте объясним. Честные и злонамеренные пользователи Пользователь честен, если он следует всем инструкциям протокола и прекрасно способен отправлять и получать сообщения. Пользователь является злонамеренным (т.е. византийским, в на языке распределенных вычислений), если он может произвольно отклоняться от предписанных инструкций. Противник Противник — это эффективный (технически полиномиальный) алгоритм, олицетворяемый цветом, который может немедленно сделать злонамеренным любого пользователя, которого он хочет, в любое время, когда он захочет (субъект только до верхнего предела числа пользователей, которых он может испортить). Злоумышленник полностью контролирует и прекрасно координирует всех злоумышленников. Он предпринимает все действия от их имени, включая получение и отправку всех их сообщений, и может позволить им отклоняться от предписанные им инструкции произвольным образом. Или он может просто изолировать отправку поврежденного пользователя и получение сообщений. Уточним, что никто больше автоматически не узнает, что пользователь i является злонамеренным, хотя моя злонамеренность может проявиться в действиях, которые Противник заставляет его предпринять. Однако этот могущественный противник • Не обладает неограниченной вычислительной мощностью и не может успешно создавать цифровые подпись добросовестного пользователя, за исключением случаев с незначительной вероятностью; и• Не может каким-либо образом вмешиваться в обмен сообщениями между честными пользователями. Более того, его способность атаковать честных пользователей ограничена одним из следующих предположений. Честность Большинство денег Мы рассматриваем континуум честного большинства денег (HMM). предположения: а именно, для каждого неотрицательного целого числа k и действительного h > 1/2, HHMk > h: честные пользователи в каждом раунде r владели долей, большей, чем h, от всех денег в система на раунде r −k. Обсуждение. Если предположить, что все злоумышленники прекрасно координируют свои действия (как будто контролируют одним существом, Противником) — довольно пессимистическая гипотеза. Идеальная координация между собой многим людям трудно достичь. Возможно, координация происходит только внутри отдельных групп. злонамеренных игроков. Но, поскольку нельзя быть уверенным в уровне координации злоумышленников может понравится, лучше перестраховаться, чем потом сожалеть. Предполагать, что Злоумышленник может тайно, динамически и немедленно развращать пользователей, также является неверным. пессимистичный. В конце концов, на самом деле получение полного контроля над действиями пользователя должно занять некоторое время. Предположение HMMk > h подразумевает, например, что если раунд (в среднем) реализуется в одну минуту, то большая часть денег в данном раунде останется в честных руках на не менее двух часов, если k = 120, и не менее одной недели, если k = 10 000. Обратите внимание, что предположения HMM и предыдущее «Честное большинство вычислительных мощностей» предположения связаны в том смысле, что, поскольку вычислительную мощность можно купить за деньги, если злоумышленники владеют большей частью денег, то они могут получить большую часть вычислительной мощности. 2,7 Коммуникационная модель Мы считаем, что распространение сообщений — то есть «одноранговые сплетни»5 — будет единственным средством общение. Временное предположение: своевременная доставка сообщений по всей сети. Для Большую часть этой статьи мы предполагаем, что каждое распространяемое сообщение достигает почти всех честных пользователей. своевременно. Мы устраним это предположение в разделе 10, где будем иметь дело с сетью перегородки, возникающие естественным путем или вызванные враждебностью. (Как мы увидим, мы только предполагаем своевременная доставка сообщений внутри каждого подключенного компонента сети.) Одним из конкретных способов обеспечения своевременной доставки распространяемых сообщений (во всей сети) является следующее: Для любой достижимости \(\rho\) > 95% и размера сообщения \(\mu\) \(\in\)Z+ существует \(\lambda\) \(\rho\),\(\mu\) такое, что если честный пользователь распространяет микробайтовое сообщение m в момент времени t, тогда m к моменту времени t + \(\lambda\) \(\rho\),\(\mu\) достигнет, по крайней мере, части \(\rho\) честных пользователей. 5По сути, как и в Bitcoin, когда пользователь распространяет сообщение m, каждый активный пользователь i получает m впервые, случайным образом и независимо выбирает достаточно небольшое количество активных пользователей, своих «соседей», которым он пересылает m, возможно, пока он не получит от них подтверждение. Распространение m прекращается, когда ни один пользователь не получает м впервые.Однако указанное выше свойство не может поддерживать наш протокол Algorand без явного и отдельного обеспечения механизма получения последней версии blockchain другим пользователем/хранилищем/и т. д. Фактически, чтобы построить новый блок Br, необходимо не только правильное множество верификаторов своевременно получить round-r сообщения, но и сообщения предыдущих раундов, чтобы знать Br-1 и все остальные предыдущие раунды. блоков, что необходимо для определения достоверности платежей в рублях. Следующие вместо этого достаточно предположения. Допущение о распространении сообщений (MP): Для всех \(\rho\) > 95% и \(\mu\) \(\in\)Z+ существует \(\lambda\) \(\rho\),\(\mu\) такие, что для всех моментов времени t и всех \(\mu\)-байтовых сообщений m, переданных честным пользователем до t −\(\lambda\) \(\rho\),\(\mu\), m к моменту времени t получает по крайней мере часть \(\rho\) честных пользователей. Протокол Algorand ’ фактически инструктирует каждого из небольшого числа пользователей (т. е. проверяющих заданный шаг раунда в Algorand ′, чтобы распространить отдельное сообщение (маленького) заданного размера, и нам нужно ограничить время, необходимое для выполнения этих инструкций. Мы делаем это, обогащая депутата предположение следующим образом. Для всех n, \(\rho\) > 95% и \(\mu\) \(\in\)Z+ существует \(\lambda\)n,\(\rho\),\(\mu\) такие, что для всех моментов времени t и всех \(\mu\)-байт сообщения m1, . . . , mn, каждый из которых был распространен честным пользователем до t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . . . , млн получено, к моменту времени t, по крайней мере, долей \(\rho\) честных пользователей. Примечание • Вышеупомянутое предположение намеренно простое, но в то же время более сильное, чем необходимо в нашей статье.6 • Для простоты мы предполагаем \(\rho\) = 1 и поэтому оставляем упоминание \(\rho\). • Мы пессимистично предполагаем, что, если он не нарушит предположение МП, Противник полностью контролирует доставку всех сообщений. В частности, незаметно для честных пользователей, Противник может произвольно решить, какой честный игрок какое сообщение получит, когда, и произвольно ускорять доставку любого сообщения, которое он хочет.7

Протокол BA BA⋆ в традиционной обстановке

Как уже подчеркивалось, византийское соглашение является ключевым ингредиентом Algorand. Действительно, это через использование такого протокола BA, на который Algorand не влияет вилка. Однако, чтобы быть в безопасности от наших Могущественный противник, Algorand должен полагаться на протокол BA, который удовлетворяет новой возможности замены игроков. ограничение. Кроме того, чтобы Algorand был эффективным, такой протокол BA должен быть очень эффективным. Протоколы BA были впервые определены для идеализированной модели связи, синхронной полной сети (сети SC). Такая модель позволяет упростить разработку и анализ протоколов БА. 6 Учитывая честный процент h и приемлемую вероятность отказа F, Algorand вычисляет верхнюю границу N, максимальному числу членов проверяющих на шаге. Таким образом, предположение MP должно выполняться только при n \(\leq\)N. Кроме того, как уже говорилось, предположение MP сохраняется независимо от того, сколько других сообщений может распространяться одновременно с MJ's. Однако, как мы увидим, в Algorand сообщения at распространяются практически за неперекрывающееся время. интервалы, в течение которых либо распространяется один блок, либо не более N верификаторов распространяются небольшой (например, 200B) сообщение. Таким образом, мы могли бы переформулировать предположение MP в более слабом, но и более сложном виде. 7Например, он может сразу узнать сообщения, отправленные честными игроками. Таким образом, злонамеренный пользователь i', который которого попросили распространить сообщение одновременно с честным пользователем i, всегда может выбрать свое собственное сообщение m' на основе сообщение m фактически распространяется i. Эта способность связана с спешкой, на языке распределенных вычислений. литература.Соответственно, в этом разделе мы вводим новый протокол BA, BA⋆, для сетей SC и игнорируя вообще вопрос взаимозаменяемости игроков. Протокол BA⋆ представляет собой вклад отдельной ценности. Действительно, это наиболее эффективный из известных на сегодняшний день криптографических протоколов BA для сетей SC. Чтобы использовать его в нашем протоколе Algorand, мы немного модифицируем BA⋆, чтобы учесть наши различные модель и контекст общения, но не забудьте в разделе X указать, как используется BA⋆. в рамках нашего фактического протокола Algorand ′. Начнем с напоминания о модели, в которой действует BA⋆, и о понятии византийского соглашения. 3.1 Синхронные полные сети и соответствующие противники В сети SC имеются общие часы, отсчитывающие время каждого целого числа r = 1, 2, . . . При каждом четном нажатии r каждый игрок i мгновенно и одновременно отправляет один сообщение мистеру i,j (возможно, пустое сообщение) каждому игроку j, включая себя. Каждый мистер я, j получен в момент времени щелкните r + 1 игроком j вместе с личностью отправителя i. Опять же, в протоколе связи игрок честен, если он следует всем предписанным ему правилам. инструкции и злонамеренные в противном случае. Все злонамеренные игроки полностью контролируются и прекрасно координируется Противником, который, в частности, немедленно получает все сообщения, адресованные злонамеренные игроки и выбирает сообщения, которые они отправляют. Злоумышленник может немедленно сделать злонамеренным любого честного пользователя, которого он захочет, в любое нечетное время. он хочет, с учетом только возможного верхнего предела числа злонамеренных игроков. То есть, Противник «не может вмешиваться в сообщения, уже отправленные честным пользователем i», которые будут доставили как обычно. Противник также имеет дополнительную возможность мгновенно, в каждом четном раунде, видеть сообщения, которые отправляют честные на данный момент игроки, и мгновенно использовать эту информацию для выбора сообщения, которые злоумышленники отправляют одновременно, отмечаются галочкой. Примечания • Сила противника. Вышеуказанная установка является очень враждебной. Действительно, в Византийском договоре литературе, многие параметры менее враждебны. Однако есть еще некоторые состязательные настройки. также рассматривалось, где Противник, увидев сообщения, отправленные честным игроком, в данный момент нажмите r, есть возможность стереть все эти сообщения из сети, сразу поврежденный i, выберите сообщение, которое теперь отправляет вредоносный i, нажмите r и получите его доставили как обычно. Предполагаемая сила Противника соответствует той, которую он имеет в наших условиях. • Физическая абстракция. Предполагаемая модель коммуникации абстрагирует более физическую модель, в котором каждая пара игроков (i, j) связана отдельной частной линией связи li,j. То есть никто другой не может внедрять сообщения, вмешиваться в них или получать информацию о них. Ли, Дж. Единственный способ для злоумышленника получить доступ к li,j — это повредить i или j. • Конфиденциальность и аутентификация. В сетях SC гарантируется конфиденциальность и аутентификация сообщений. по предположению. Напротив, в нашей сети связи, где распространяются сообщения между узлами аутентификация гарантируется цифровыми подписями, а конфиденциальность отсутствует. Таким образом, чтобы адаптировать протокол BA⋆ к нашим условиям, каждое обмениваемое сообщение должно быть подписано цифровой подписью. (дальнейшее определение состояния, в котором оно было отправлено). К счастью, протоколы БА, которые мы рассмотрите возможность использования в Algorand не требующих конфиденциальности сообщений.3.2 Понятие византийского соглашения Понятие византийского соглашения было введено Пизом Шостаком и Лэмпортом [31] для двоичный случай, то есть когда каждое начальное значение состоит из бита. Однако его быстро продлили. произвольным начальным значениям. (См. обзоры Фишера [16] и Чора и Дворка [10].) Бакалавр протокол, мы имеем в виду протокол произвольного значения. Определение 3.1. В синхронной сети пусть P — протокол для n игроков, набор игроков которого общий. знаний среди игроков, t — положительное целое число такое, что n \(\geq\)2t + 1. Мы говорим, что P является произвольного (соответственно двоичного) (n, t)-византийского протокола согласования с корректностью \(\sigma\) \(\in\)(0, 1) если для любого набора значений V, не содержащего специального символа \(\bot\) (соответственно, для V = {0, 1}), в исполнение, в котором не более t игроков являются злонамеренными и в котором каждый игрок i начинает с начальное значение vi \(\in\)V , каждый честный игрок j останавливается с вероятностью 1, выдавая значение outi \(\in\)V \(\cup\){\(\bot\)} так, чтобы с вероятностью не менее \(\sigma\) удовлетворить следующим двум условиям: 1. Соглашение: существует out \(\in\)V \(\cup\){\(\bot\)} такой, что outi = out для всех честных игроков i. 2. Непротиворечивость: если для некоторого значения v \(\in\)V vi = v для всех честных игроков, то out = v. Мы называем out выходом P, а каждый outi — выходом игрока i. 3.3 Обозначение BA В наших протоколах БА игрок обязан посчитать, сколько игроков отправили ему заданное сообщение в заданный шаг. Соответственно, для каждого возможного значения v, которое может быть отправлено,

с

я (в) (или просто #i(v), если s ясно) — это количество игроков j, от которых я получил v на шаге s. Вспоминая, что игрок i получает ровно одно сообщение от каждого игрока j, если число игроков равно n, то для всех i и s P в #с я(v) = п. 3.4 Бинарный протокол BA BBA⋆ В этом разделе мы представляем новый бинарный протокол BA, BBA⋆, который опирается на честность большего количества чем две трети игроков и очень быстро: что бы ни делали злонамеренные игроки, каждое выполнение основного цикла приводит игроков к соглашению с вероятностью 1/3. Каждый игрок имеет свой открытый ключ схемы цифровой подписи, удовлетворяющий требованиям уникальной подписи. собственность. Поскольку этот протокол предназначен для работы в полной синхронной сети, нет нужно, чтобы игрок подписывал каждое свое сообщение. Цифровые подписи используются для генерации достаточно распространенного случайного бита на этапе 3. (В Algorand цифровые подписи также используются для аутентификации всех остальных сообщений.) Протокол требует минимальной настройки: общая случайная строка r, независимая от игроков. ключи. (В Algorand r фактически заменяется величиной Qr.) Протокол BBA⋆ представляет собой трехэтапный цикл, в котором игроки неоднократно обмениваются логическими значениями, а разные игроки могут выйти из этого цикла в разное время. Игрок i выходит из этого цикла, распространяя на каком-то этапе либо специальное значение 0∗, либо специальное значение 1∗, тем самым инструктируя всех игроков «представьте», что они получают соответственно 0 и 1 от i на всех последующих шагах. (В качестве альтернативы: предположимчто последнее сообщение, полученное игроком j от другого игрока i, было битом b. Тогда на любом шаге в котором он не получает никакого сообщения от i, j действует так, как если бы я отправил ему бит b.) В протоколе используется счетчик \(\gamma\), показывающий, сколько раз был выполнен трехэтапный цикл. В начале BBA⋆ \(\gamma\) = 0. (Можно думать о \(\gamma\) как о глобальном счетчике, но на самом деле он увеличен каждым отдельным игроком каждый раз при выполнении цикла.) Их n \(\geq\)3t + 1, где t — максимально возможное количество злоумышленников. Бинарный файл строка x идентифицируется с целым числом, двоичное представление которого (с возможными начальными нулями) равно x; а lsb(x) обозначает младший значащий бит числа x. Протокол BBA⋆ (Связь) Шаг 1. [Шаг фиксирования монеты до 0] Каждый игрок i отправляет bi. 1.1 Если №1 i (0) \(\geq\)2t + 1, затем я устанавливает bi = 0, отправляет 0∗, выводит outi = 0, и ОСТАНАВЛИВАЕТСЯ. 1.2 Если №1 i (1) \(\geq\)2t + 1, то тогда я устанавливаю bi = 1. 1.3 В противном случае я устанавливаю bi = 0. (Связь) Шаг 2. [Шаг фиксированной монеты-1] Каждый игрок i отправляет bi. 2.1 Если №2 i (1) \(\geq\)2t + 1, то я устанавливаю bi = 1, отправляет 1∗, выходы outi = 1, и ОСТАНАВЛИВАЕТСЯ. 2.2 Если №2 i (0) \(\geq\)2t + 1, то я устанавливаю bi = 0. 2.3 В противном случае я устанавливаю bi = 1. (Общение) Шаг 3. [Шаг истинного подбрасывания монеты] Каждый игрок i отправляет bi и SIGi(r, \(\gamma\)). 3.1 Если №3 i (0) \(\geq\)2t + 1, то я устанавливаю bi = 0. 3.2 Если №3 i (1) \(\geq\)2t + 1, то я устанавливаю bi = 1. 3.3 Иначе, полагая Si = {j \(\in\)N, который отправил i правильное сообщение на этом шаге 3 }, я устанавливаю bi = c \(\triangleq\)lsb(minj\(\varepsilon\)Si H(SIGi(r, \(\gamma\)))); увеличивает \(\gamma\)i на 1; и возвращается к шагу 1. Теорема 3.1. Всякий раз, когда n \(\geq\)3t + 1, BBA⋆ является бинарным (n, t)-протоколом BA с надежностью 1. Доказательство теоремы 3.1 приведено в [26]. Его адаптация к нашим условиям и возможность замены игроков. свойства являются новыми. Историческое замечание Вероятностные бинарные протоколы БА были впервые предложены Бен-Ором в асинхронные настройки [7]. Протокол BBA⋆ — это новая адаптация к нашим условиям открытого ключа двоичный протокол BA Фельдмана и Микали [15]. Их протокол был первым, который сработал ожидаемым образом. постоянное количество шагов. Это сработало благодаря тому, что игроки сами реализовали общую монету. идея, предложенная Рабином, который реализовал ее через внешнюю доверенную сторону [32].3,5 Градуированный консенсус и Протокол GC Давайте вспомним, что касается произвольных ценностей, понятие консенсуса, гораздо более слабое, чем византийское соглашение. Определение 3.2. Пусть P — протокол, в котором множество всех игроков общеизвестно, и каждый игрок i лично знает произвольное начальное значение v' я. Мы говорим, что P является (n, t)-градуированным протоколом консенсуса, если в каждом исполнении с n игроками в большинство из которых являются вредоносными, каждый честный игрок i прекращает выводить пару ценных значений (vi, gi), где gi \(\in\){0, 1, 2}, чтобы удовлетворить следующим трем условиям: 1. Для всех честных игроков i и j |gi −gj| \(\leq\)1. 2. Для всех честных игроков i и j gi, gj > 0 ⇒vi = vj. 3. Если v' 1 = \(\cdots\) = v′ n = v для некоторого значения v, тогда vi = v и gi = 2 для всех честных игроков i. Историческая справка Понятие дифференцированного консенсуса просто вытекает из понятия дифференцированного консенсуса. трансляция, выдвинутая Фельдманом и Микали в [15], путем укрепления понятия крестоносца соглашение, представленное Долевым [12] и уточненное Терпином и Коаном [33].8 В [15] авторы также предоставили трехэтапный (n, t) протокол вещания Gradecast для n \(\geq\)3t+1. Позже был найден более сложный (n, t)-градуированный протокол вещания для n > 2t+1. Кац и Ку [19]. Следующий двухэтапный протокол GC состоит из двух последних этапов Gradecast, выраженных в нашем обозначения. Чтобы подчеркнуть этот факт и соответствовать шагам протокола Algorand ′ раздела 4.1, мы соответственно назовите 2 и 3 шаги GC. Протокол GC Шаг 2. Каждый игрок i отправляет v' я всем игрокам. Шаг 3. Каждый игрок i отправляет всем игрокам строку x тогда и только тогда, когда #2 я (х) \(\geq\)2t + 1. Определение выхода. Каждый игрок i выводит пару (vi, gi), рассчитанную следующим образом: • Если для некоторого x, #3 i (x) \(\geq\)2t + 1, тогда vi = x и gi = 2. • Если для некоторого x, #3 i (x) \(\geq\)t + 1, тогда vi = x и gi = 1. • В противном случае vi = \(\bot\) и gi = 0. Теорема 3.2. Если n \(\geq\)3t + 1, то GC является (n, t)-градуированным широковещательным протоколом. Доказательство непосредственно следует из протокола Gradecast в [15] и поэтому опускается9. 8По сути, в протоколе дифференцированного вещания (а) вклад каждого игрока представляет собой личность выдающегося игрок, отправитель, который имеет произвольное значение v в качестве дополнительных частных входных данных, и (б) выходные данные должны удовлетворять те же свойства 1 и 2 градуированного консенсуса, плюс следующее свойство 3': если отправитель честен, то vi = v и gi = 2 для всех честных игроков i. 9Действительно, в их протоколе на шаге 1 отправитель отправляет свое личное значение v всем игрокам, и каждый игрок i позволяет v' я состою из значения, которое он фактически получил от отправителя на шаге 1.3.6 Протокол BA⋆ Теперь мы опишем протокол BA с произвольными значениями BA⋆ через двоичный протокол BA BBA⋆ и протокол постепенного консенсуса GC. Ниже начальная стоимость каждого игрока i равна v' я. Протокол BA⋆ Шаги 1 и 2. Каждый игрок i выполняет GC на входе v' i, чтобы вычислить пару (vi, gi). Шаг 3, . . . Каждый игрок i выполняет BBA⋆ — с начальным вводом 0, если gi = 2, и 1 в противном случае — так что как вычислить бит outi. Определение выхода. Каждый игрок i выводит vi, если outi = 0, и \(\bot\) в противном случае. Теорема 3.3. Всякий раз, когда n \(\geq\)3t + 1, BA⋆ представляет собой (n, t)-BA-протокол с надежностью 1. Доказательство. Сначала мы доказываем непротиворечивость, а затем согласие. Доказательство согласованности. Предположим, что для некоторого значения v \(\in\)V , v′ i = v. Тогда по свойству 3 градуированный консенсус, после выполнения GC, все честные игроки выводят (v, 2). Соответственно, 0 начальный бит всех честных игроков в конце исполнения BBA⋆. Таким образом, Соглашением свойство бинарного византийского соглашения, в конце исполнения BA⋆, outi = 0 для всех честных игроки. Это означает, что результат каждого честного игрока i в BA⋆ равен vi = v. ✷ Доказательство соглашения. Поскольку BBA⋆ — это двоичный протокол BA, либо (A) outi = 1 для всех честных игроков i, или (B) outi = 0 для всех честных игроков i. В случае А все честные игроки выводят \(\bot\)в BA⋆, и, таким образом, Соглашение выполняется. Рассмотрим теперь случай Б. В в этом случае при выполнении BBA⋆ начальный бит хотя бы одного честного игрока i равен 0. (Действительно, если начальный бит всех честных игроков был равен 1, то, согласно свойству согласованности BBA⋆, мы бы имели outj = 1 для всех честных j.) Соответственно, после выполнения GC i выводит пару (v, 2) для некоторых значение v. Таким образом, по свойству 1 градуированного консенсуса gj > 0 для всех честных игроков j. Соответственно, по свойство 2 градуированного консенсуса: vj = v для всех честных игроков j. Это означает, что в конце BA⋆, каждый честный игрок j выводит v. Таким образом, Соглашение справедливо и в случае B. ✷ Поскольку соблюдаются как согласованность, так и согласованность, BA⋆ является протоколом BA с произвольным значением. Историческая справка Терпин и Коан первыми показали, что при n \(\geq\)3t+1 любой бинарный (n, t)-BA протокол может быть преобразован в протокол произвольного значения (n, t)-BA. Приведение произвольного значения Византийское соглашение к бинарному Византийское соглашение посредством ступенчатого консенсуса является более модульным и чище и упрощает анализ нашего Algorand протокола Algorand ′. Обобщающий BA⋆для использования в Algorand Algorand работает, даже если вся связь осуществляется через сплетни. Однако, несмотря на то, что они представлены в традиционной и знакомой сети связи, так как Чтобы обеспечить лучшее сравнение с предшествующим уровнем техники и облегчить понимание, работает протокол BA⋆. также в сетях сплетен. Фактически, в наших детальных вариантах реализации Algorand мы представим его непосредственно для сетей сплетен. Отметим также, что оно удовлетворяет заменимости игроков свойство, которое имеет решающее значение для безопасности Algorand в предусмотренной очень состязательной модели.

Любой заменяемый игроком BA протокол, работающий в сети сплетничающей связи, может быть надежно используется в системе Algorand изобретения. В частности, Микали и Вайкунтханатан. расширили BA⋆, чтобы он мог очень эффективно работать и с простым большинством честных игроков. Это протокол тоже можно использовать в Algorand.

Два варианта реализации Algorand

Как уже говорилось, на очень высоком уровне раунд Algorand в идеале протекает следующим образом. Сначала случайно выбранный пользователь, лидер, предлагает и распространяет новый блок. (Этот процесс первоначально включает в себя выбрать несколько потенциальных лидеров, а затем убедиться, что, по крайней мере, значительную часть времени, появляется единый общий лидер.) Во-вторых, выбирается случайно выбранный комитет пользователей, и достигает византийского соглашения по предложенному вождём блоку. (Этот процесс включает в себя каждый шаг протокола БА выполняется отдельно выбранной комиссией.) Согласованный блок затем подписывается цифровой подписью заданного порогового значения (TH) членов комитета. Эти цифровые подписи распространяются так, чтобы все были уверены в том, какой блок является новым. (Это включает в себя распространение учетные данные подписывающих сторон и аутентифицируя только hash нового блока, гарантируя, что каждый гарантированно изучит блок, как только его hash станет ясным.) В следующих двух разделах мы представляем два варианта реализации Algorand, Algorand ′ 1 и Algorand ′ 2, это работает при предположении большинства честных пользователей. В разделе 8 мы покажем, как принять эти варианты реализации, работающие в предположении честного большинства денег. Algorand ′ 1 предусматривает лишь то, что > 2/3 членов комитета будут честными. Кроме того, в Algorand ′ 1, количество шагов для достижения византийского соглашения ограничено достаточно высоким число, так что соглашение гарантировано будет достигнуто с подавляющей вероятностью в течение фиксированное количество шагов (но потенциально требующее больше времени, чем шаги Algorand ′ 2). В В отдаленном случае, когда соглашение еще не достигнуто на последнем этапе, комитет согласовывает пустой блок, который всегда действителен. Algorand ′ 2 предусматривает, что число честных членов комитета всегда больше, чем или равен фиксированному порогу tH (который гарантирует, что с подавляющей вероятностью по крайней мере 2/3 членов комитета честные). Кроме того, Algorand ′ 2 позволяет византийскому соглашению быть достигнуто за произвольное количество шагов (но потенциально за более короткое время, чем Algorand ′ 1). Легко получить множество вариантов этих основных вариантов осуществления. В частности, это легко, учитывая Algorand ′ 2, чтобы изменить Algorand ′ 1, чтобы дать возможность достичь византийского соглашения в произвольном порядке. количество шагов. Оба варианта осуществления имеют следующее общее ядро, обозначения, понятия и параметры. 4.1 Общее ядро Цели В идеале для каждого раунда r Algorand должен удовлетворять следующим свойствам: 1. Совершенная корректность. Все честные пользователи согласны с тем же блоком Бр. 2. Полнота 1. С вероятностью 1 набор выплат Br, PAY r, является максимальным10. 10Поскольку наборы выплат должны содержать действительные платежи, а честные пользователи должны совершать только действительные платежи, максимальный PAY r содержит «невыплаченные на данный момент» платежи всех честных пользователей.Конечно, гарантировать абсолютную правильность само по себе тривиально: каждый всегда выбирает официальную версию. payset PAY r должен быть пустым. Но в этом случае система имела бы полноту 0. К сожалению, гарантировать как абсолютную правильность, так и полноту 1 непросто при наличии вредоносных пользователи. Таким образом, Algorand ставит более реалистичную цель. Неформально, пусть h обозначает процент честных пользователей, h > 2/3, цель Algorand — Гарантируя с подавляющей вероятностью полную правильность и полноту, близкую к h. Отдавать предпочтение правильности перед полнотой кажется разумным выбором: платежи не обрабатываются в один раунд может быть обработан в следующем, но следует по возможности избегать вилок. Под руководством Византийского соглашения Совершенную правильность можно гарантировать следующим образом. В начале раунда r каждый пользователь i создает свой собственный блок-кандидат Br i, а затем все пользователи доходят до Byzantine соглашение по одному кандидатскому блоку. Согласно нашему введению, используемый протокол BA требует честное большинство в 2/3 и возможность замены игрока. Каждый его шаг может быть выполнен маленьким и случайно выбранный набор проверяющих, которые не имеют общих внутренних переменных. К сожалению, этот подход не имеет гарантий полноты. Это так, потому что кандидат блоки честных пользователей, скорее всего, кардинально отличаются друг от друга. Таким образом, в конечном итоге согласованный блок всегда может быть блоком с немаксимальным набором выплат. На самом деле, это всегда может быть пустой блок B\(\varepsilon\), то есть блок, набор выплат которого пуст. ну, это будет пустое значение по умолчанию. Algorand ′ позволяет избежать этой проблемы полноты следующим образом. Сначала выбирается лидер раунда r, \(\ell\)r. Затем \(\ell\)r распространяет свой собственный блок кандидатов, Br \(\ell\)р. Наконец, пользователи достигают соглашения по блокировке они фактически получают от \(\ell\)r. Потому что всякий раз, когда \(\ell\)r честен, Совершенная правильность и полнота 1 оба верны, Algorand ′ гарантирует, что \(\ell\)r честен с вероятностью, близкой к h. (Когда лидер вредоносный, нас не волнует, является ли согласованный блок блоком с пустой платёжной системой. В конце концов, злонамеренный лидер \(\ell\)r всегда может злонамеренно выбрать Br \(\ell\)r быть пустым блоком, а потом честно распространять его, тем самым заставляя честных пользователей согласиться на пустой блок.) Выбор лидера В Algorand r-й блок имеет вид Br = (r, PAY r, Qr, H(Br-1). Как уже упоминалось во введении, величина Qr−1 тщательно строится так, чтобы быть по сути, нашим очень могущественным противником невозможно манипулировать. (Далее в этом разделе мы рассмотрим дайте некоторое представление о том, почему это так.) В начале раунда r все пользователи знают blockchain на данный момент, B0, . . . , Br−1, из которого они выводят набор пользователей каждого предыдущего раунда: есть, ПК1, . . . , ПКр−1. Потенциальным лидером раунда r является пользователь i такой, что .Х СИГи г, 1, Qr−1 \(\leq\)р. Давайте объясним. Обратите внимание, что, поскольку величина Qr−1 является частью блока Br−1, а лежащее в ее основе схема подписи удовлетворяет свойству уникальности SIGi г, 1, Qr−1 однозначно является двоичной строкой связанный с i и r. Таким образом, поскольку H является случайным oracle, H СИГи г, 1, Qr−1 это случайный 256-битный длинная строка, однозначно связанная с i и r. Символ «.» перед Х СИГи г, 1, Qr−1 это десятичная (в нашем случае двоичная) точка, так что ri \(\triangleq\).H СИГи г, 1, Qr−1 представляет собой двоичное разложение случайное 256-битное число от 0 до 1, однозначно связанное с i и r. Таким образом, вероятность того, что ri меньше или равно p, по существу, p. (Наш механизм отбора потенциальных лидеров был вдохновлен схемой микроплатежей Микали и Ривеста [28].) Вероятность p выбирается так, чтобы с подавляющей (т. е. 1 −F) вероятностью хотя бы один потенциальный проверяющий честен. (Если это действительно так, то p выбирается как наименьшая такая вероятность.)Обратите внимание: поскольку i — единственный, кто способен вычислить свои собственные подписи, он один может определить, является ли он потенциальным проверяющим в раунде 1. Однако, раскрыв свои собственные учетные данные, \(\sigma\)р я \(\triangleq\)SIGi г, 1, Qr−1 , я могу доказать любому, что являюсь потенциальным проверяющим раунда r. Лидером \(\ell\)r считается потенциальный лидер, чьи учетные данные hash меньше, чем у hashed учетные данные всех остальных потенциальных лидеров j: то есть H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s дж). Обратите внимание: поскольку злонамеренный \(\ell\)r может не раскрыть свои полномочия, правильный лидер раунда r может никогда не будет известно, и что, если не считать невероятных связей, \(\ell\)r действительно является единственным лидером раунда r. Давайте, наконец, коснемся последней, но важной детали: пользователь i может быть потенциальным лидером (и, следовательно, лидер) раунда r только в том случае, если он принадлежал системе не менее k раундов. Это гарантирует невозможность манипулирования Qr и всеми будущими Q-величинами. Фактически один из потенциальных лидеров фактически определит Qr. Выбор проверяющего Каждый шаг s > 1 раунда r выполняется небольшим набором проверяющих SV r,s. Опять же, каждый верификатор i \(\in\)SV r,s выбирается случайным образом среди пользователей, уже находящихся в системе k раундов. перед r и снова через специальную величину Qr−1. В частности, i \(\in\)PKr−k является верификатором в SV r,s, если .Х СИГи г, с, Qr−1 \(\leq\)p'. Опять же, только я знаю, принадлежит ли он к SV r,s, но если это так, то он мог бы доказать это, предъявляя свои полномочия \(\sigma\)r,s я \(\triangleq\)H(SIGi г, с, Qr−1 ). Верификатор i \(\in\)SV r,s отправляет сообщение mr,s я, в шаг s раунда r, и это сообщение включает его учетные данные \(\sigma\)r,s i , чтобы дать возможность верификаторам Следующий шаг, чтобы признать, что мистер, с я является законным сообщением шага. Вероятность p' выбирается так, чтобы гарантировать, что в SV r,s, пусть #good будет числом честные пользователи и #bad количество злонамеренных пользователей, с подавляющей вероятностью следующее выполняются два условия. Для варианта реализации Algorand ′ 1: (1) #хорошо > 2 \(\cdot\) #плохо и (2) #good + 4 \(\cdot\) #bad < 2n, где n — ожидаемая мощность SV r,s. Для варианта реализации Algorand ′ 2: (1) #good > tH и (2) #good + 2#bad < 2tH, где tH — заданный порог. Из этих условий следует, что с достаточно большой вероятностью: (а) на последнем шаге БА протоколу, будет как минимум заданное количество честных игроков, которые подпишут цифровой подписью новый блок Br, (б) только один блок за раунд может иметь необходимое количество подписей, и (в) используемый БА протокол имеет (на каждом этапе) необходимое честное большинство в 2/3. Уточнение генерации блоков Если лидер раунда \(\ell\)r честен, то соответствующий блок имеет форму Бр = r, PAY r, SIG\(\ell\)r Qr−1 , Ч Бр-1 , где набор выплат PAY r является максимальным. (напомним, что все наборы выплат по определению действительны коллективно.) В противном случае (т. е. если \(\ell\)r является вредоносным), Br имеет одну из следующих двух возможных форм: Бр = р, ПЛАТИТЕ р, СИГи Qr−1 , Ч Бр-1 и Бр = Бр \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Бр-1 .В первой форме PAY r — это (не обязательно максимальный) набор выплат, и это может быть PAY r = \(\emptyset\); и я потенциальный лидер раунда r. (Однако я не могу быть лидером \(\ell\)r. Это действительно может случиться, если \(\ell\)r хранит в тайне свои полномочия и не раскрывает себя.) Вторая форма возникает, когда при выполнении раунда-r протокола БА все честные игроки выведите значение по умолчанию, то есть пустой блок Br \(\varepsilon\) в нашем приложении. (По определению, возможный выходные данные протокола BA включают значение по умолчанию, обычно обозначаемое \(\bot\). См. раздел 3.2.) Обратите внимание: хотя в обоих случаях платежные наборы пусты, Br = r, \(\emptyset\), СИГи Qr−1 , Ч Бр-1 и Бр \(\varepsilon\) являются синтаксически разными блоками и возникают в двух разных ситуациях: соответственно, «все в исполнении протокола БА прошло достаточно гладко», а «что-то пошло не так в протокол BA, и было выведено значение по умолчанию». Давайте теперь интуитивно опишем, как происходит генерация блока Br в раунде r Algorand ′. На первом этапе каждый подходящий игрок, то есть каждый игрок i \(\in\)PKr−k, проверяет, является ли он потенциальным игроком. лидер. Если это так, то меня спрашивают, используя все платежи, которые он видел до сих пор, и текущий blockchain, B0, . . . , Br−1, чтобы тайно подготовить максимальный набор выплат, PAY r я и тайно собирает свой блок кандидатов, Br = р, ПЛАТИТЕ р я, СИГи Qr−1 , Ч Бр-1 . То есть он не только включить в руб. i , в качестве второго компонента только что подготовленный набор выплат, но также, в качестве третьего компонента, его собственная подпись Qr−1, третьего компонента последнего блока, Br−1. Наконец, он пропагандирует свою сообщение round-r-step-1, мистер, 1 i , который включает в себя (а) его блок-кандидат Br я , (б) его собственная подпись своего блока-кандидата (т. е. его подпись hash Br i , и (c) его собственные полномочия \(\sigma\)r,1 я, доказывая что он действительно является потенциальным проверяющим раунда r. (Обратите внимание, что до тех пор, пока честный i не выдаст свое сообщение mr,1 i, Противник понятия не имеет, что я потенциальный проверяющий. Если он захочет развратить честных потенциальных лидеров, Противник также может коррумпированные случайные честные игроки. Однако, как только он увидит мистера,1 i , поскольку он содержит учетные данные i, Противник знает и может испортить меня, но не может предотвратить мистера,1 i , который распространяется вирусно, из охват всех пользователей системы.) На втором этапе каждый выбранный проверяющий j \(\in\)SV r,2 пытается определить лидера раунда. В частности, j принимает учетные данные шага 1, \(\sigma\)r,1 я1 , . . . , \(\sigma\)r,1 in , содержащийся в соответствующем сообщении шага 1 mr,1 я он получил; hashпроверяет все из них, то есть вычисляет H  \(\sigma\)р,1 я1  , . . . , Ч  \(\sigma\)р,1 в  ; находит удостоверение, \(\sigma\)р,1 \(\ell\)j , hash которого является лексикографически минимальным; и считает \(\ell\)r j стать лидером раунда r. Напомним, что каждая рассматриваемая учетная запись представляет собой цифровую подпись Qr-1, что SIGi г, 1, Qr−1 есть однозначно определяется i и Qr−1, что H является случайным oracle и, таким образом, каждый H(SIGi г, 1, Qr−1 — это случайная 256-битная длинная строка, уникальная для каждого потенциального лидера i раунда r. Отсюда мы можем заключить, что если бы 256-битная строка Qr−1 сама была случайным и независимым выбраны, чем будут hashed полномочия всех потенциальных лидеров раунда r. Фактически, все потенциальные лидеры четко определены, как и их полномочия (будь то фактически вычисленные или нет). Далее, множество потенциальных лидеров раунда r представляет собой случайное подмножество пользователей раунда r −k, и честный потенциальный лидер i всегда правильно формирует и распространяет свое послание, мистер я, который содержит мои учетные данные. Таким образом, поскольку процент честных пользователей равен h, независимо от злонамеренные потенциальные лидеры могут сделать (например, раскрыть или скрыть свои полномочия), как минимум hashed удостоверение потенциального лидера принадлежит честному пользователю, которого все обязательно идентифицируют. быть лидером \(\ell\)r раунда r. Соответственно, если бы 256-битная строка Qr-1 сама была случайной и независимо выбираются с вероятностью ровно h (а) лидер \(\ell\)r честен и (б) \(\ell\)j = \(\ell\)r для всех честные проверяющие второго этапа j. В действительности, да, учетные данные hashed выбираются случайным образом, но зависят от Qr-1, которыйвыбраны не случайно и независимо. Однако в нашем анализе мы докажем, что Qr−1 достаточно не поддается манипулированию, чтобы гарантировать, что лидер раунда честен с вероятностью h′ достаточно близко к h: а именно h′ > h2(1 + h −h2). Например, если h = 80%, то h' > 0,7424. Определив лидера раунда (что они правильно делают, если ведущий честен), задача верификаторов шага 2 — начать выполнение БА, используя в качестве начальных значений то, что они считают быть блоком лидера. На самом деле, чтобы минимизировать объем необходимого общения, верификатор j \(\in\)SV r,2 не использует в качестве входного значения v′ j к византийскому протоколу, блок Bj, который он фактически получил от \(\ell\)j (пользователь j считает себя лидером), но лидер, но hash этого блока, то есть v' j = H(Bi). Таким образом, по завершении протокола БА верификаторы последнего шага не вычисляют желаемый блок round-r Br, а вычисляют (аутентифицируют и распространять) H(Br). Соответственно, поскольку H(Br) имеет цифровую подпись достаточного числа верификаторов последнем этапе протокола BA, пользователи системы поймут, что H(Br) — это hash нового блок. Однако они также должны получить (или дождаться, поскольку выполнение достаточно асинхронно) заблокировать сам Br, что протокол гарантирует, что он действительно доступен, независимо от того, что делает Противник может сделать. Асинхронность и время Algorand ′ 1 и Algorand ' 2 имеют значительную степень асинхронности. Это происходит потому, что Противник имеет большую свободу в планировании доставки сообщений. распространяется. Кроме того, независимо от того, ограничено ли общее количество шагов в раунде или нет, существует вклад дисперсии зависит от количества фактически предпринятых шагов. Как только он узнает сертификаты B0, . . . , Br−1, пользователь i вычисляет Qr−1 и начинает работать в раунде r, проверяя, является ли он потенциальным лидером или проверяющим на некоторых шагах s раунда r. Предполагая, что я должен действовать на шагах s, в свете обсуждаемой асинхронности я полагаюсь на различные стратегии, позволяющие гарантировать, что он располагает достаточной информацией, прежде чем действовать. Например, он может дождаться получения хотя бы заданного количества сообщений от проверяющих предыдущий шаг, или подождите достаточно времени, чтобы убедиться, что он получил сообщения достаточно многие проверяющие предыдущего шага. Начальное значение Qr и параметр обратного анализа k Напомним, что в идеале величины Qr должны случайны и независимы, хотя для того, чтобы ими было достаточно не поддаваться манипулированию со стороны Противник. На первый взгляд, мы могли бы выбрать Qr−1 таким, чтобы он совпадал с H ПЛАТИТЬ r−1 и, таким образом, избежать задайте Qr−1 явно в Br−1. Однако элементарный анализ показывает, что злонамеренные пользователи могут воспользоваться этим механизмом отбора.11 Некоторые дополнительные усилия показывают, что мириады других 11Мы находимся в начале раунда r−1. Таким образом, Qr−2 = PAY r−2 общеизвестно, а Противник — конфиденциально. знает, кто является потенциальными лидерами, которых он контролирует. Предположим, что Злоумышленник контролирует 10% пользователей и что с очень высокой вероятностью злонамеренный пользователь w является потенциальным лидером раунда r−1. То есть предположим, что Ч СИГв г −2, 1, Qr−2 настолько мал, что крайне маловероятно, что честный потенциальный лидер действительно окажется лидер раунда r−1. (Напомним, что, поскольку мы выбираем потенциальных лидеров с помощью секретного механизма криптографической сортировки, Противник не знает, кто такие честные потенциальные лидеры.) Противник, следовательно, находится в завидном положении. позицию выбора набора выплат PAY ′, который он хочет, и сделать его официальным набором выплат в раунде r −1. Однако, он может сделать больше. Он также может гарантировать, что с высокой вероятностью () один из его злонамеренных пользователей станет лидером. также раунда r, чтобы он мог свободно выбирать, какой будет PAY r. (И так далее. По крайней мере, надолго, т.е. до тех пор, пока эти события с высокой вероятностью действительно происходят.) Чтобы гарантировать (), Противник действует следующим образом. Пусть ПЛАТИТ' — набор выплат, который противник предпочитает для раунда r −1. Затем он вычисляет H(PAY ′) и проверяет, существует ли для некоторых уже злонамеренного игрока z, SIGz(r, 1, H(PAY ′)) особенно мал, то есть настолько мал, что с очень высоким вероятность z будет лидером раунда r. Если это так, то он дает команду w выбрать блок-кандидат на рольальтернативы, основанные на традиционном количестве блоков, легко могут быть использованы злоумышленником для обеспечения что злонамеренные лидеры встречаются очень часто. Вместо этого мы конкретно и индуктивно определяем наш бренд. новую величину Qr, чтобы иметь возможность доказать, что Противник не может манипулировать ею. А именно, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), если Br не пустой блок, и Qr \(\triangleq\)H(Qr−1, r) в противном случае. Интуиция того, почему эта конструкция Qr работает, заключается в следующем. Предположим на мгновение, что Qr-1 действительно выбирается случайно и независимо. Тогда Qr будет таким же? Когда \(\ell\)r честен, ответ (грубо говоря) да. Это так, потому что H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→ {0, 1}256 является случайной функцией. Однако когда \(\ell\)r является злонамеренным, Qr больше не определяется однозначно из Qr-1. и \(\ell\)р. Существует как минимум два отдельных значения для Qr. Один продолжает оставаться Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), а другой — H(Qr−1, r). Давайте сначала покажем, что, хотя второй выбор несколько произволен, второй выбор абсолютно обязателен. Причина этого в том, что злонамеренный \(\ell\)r всегда может вызвать совершенно разные блоки-кандидаты, которые будут получены честными проверяющими на втором этапе.12 Однажды это так, легко гарантировать, что блокировка в конечном итоге будет согласована через протокол BA раунд r будет использоваться по умолчанию и, следовательно, не будет содержать ничьей цифровой подписи Qr-1. Но система должна продолжать свое существование, а для этого ей нужен лидер раунда r. Если этот лидер автоматически и открыто выбран, то Противник банально развратит его. Если он выбран предыдущим Qr−1 посредством того же процесса, тогда \(\ell\)r снова станет лидером в раунде r+1. Мы специально предлагаем использовать тот же секретный механизм криптографической сортировки, но примененный к новой величине Q: а именно, H(Qr−1, r). Поскольку эта величина является выходом H, гарантируется, что результат будет случайным, и включив r в качестве второго входа H, в то время как все другие варианты использования H имеют один или более 3 входов, «гарантирует», что такой Qr будет выбран независимо. Опять же, наш конкретный выбор альтернативы Qr не имеет значения, важно то, что у \(\ell\)r есть два варианта для Qr, и, таким образом, он может удвоить свои шансы чтобы следующим лидером стал еще один злонамеренный пользователь. Вариантов Qr может быть даже больше для Противника, который управляет злонамеренным \(\ell\)r. Например, пусть x, y и z — три потенциальных злонамеренных лидера раунда r такие, что Ч \(\sigma\)р,1 х
< Ч \(\sigma\)р,1 й
< Ч \(\sigma\)р,1 я
и Х  \(\sigma\)р,1 я  особенно мал. То есть настолько мал, что есть большая вероятность, что H  \(\sigma\)р,1 я  есть меньший из __PH_0004__ed удостоверений каждого честного потенциального лидера. Затем, попросив x скрыть свое Если у вас есть полномочия, Противник имеет хорошие шансы на то, что y станет лидером раунда r −1. Это подразумевает, что у него есть другой вариант для Qr: а именно SIGy Qr−1 . Аналогично, Противник может попросить x и y скрыть свои полномочия, чтобы z стал лидером раунда r −1. и получаем еще один вариант для Qr: а именно SIGz Qr−1 . Однако, конечно, каждый из этих и других вариантов имеет ненулевой шанс потерпеть неудачу, поскольку Злоумышленник не может предсказать hash цифровых подписей честных потенциальных пользователей. Бр-1 я = (r −1, PAY ′, H(Br−2). В противном случае у него есть еще два злоумышленника x и y, которые продолжат генерировать новый платеж. \(\wp\)', от одного к другому, пока для какого-нибудь злонамеренного пользователя z (или даже для какого-то фиксированного пользователя z) H (SIGz (PAY ′ \(\cup\){\(\wp\)})) не станет особенно маленький. Этот эксперимент прекратится довольно быстро. И когда это произойдет, Противник попросит нас предложить блок-кандидат Br−1 я = (r−1, PAY ′ \(\cup\){\(\wp\)}, H(Br−2). 12Например, для простоты (но экстремальности): «когда время второго шага подходит к концу», \(\ell\)r мог бы напрямую отправьте по электронной почте разные блоки-кандидаты Bi каждому пользователю i. Таким образом, кем бы ни были верификаторы второго шага, они получат совершенно другие блоки.Тщательный анализ, подобный цепочке Маркова, показывает, что независимо от того, какие варианты выберет Противник сделать в раунде r-1, пока он не может ввести в систему новых пользователей, он не может уменьшить вероятность того, что честный пользователь окажется лидером раунда r + 40, намного ниже h. Это причина для чего мы требуем, чтобы потенциальными лидерами раунда r были пользователи, уже существующие в раунде r −k. Это способ гарантировать, что в раунде r −k Противник не сможет существенно изменить вероятность того, что честный пользователь станет лидером раунда r. Фактически, независимо от того, каких пользователей он может добавить в системе в раундах от r −k до r, они не имеют права стать потенциальными лидерами (и, тем более, лидер) раунда r. Таким образом, параметр обратного просмотра k в конечном итоге является параметром безопасности. (Хотя, как мы увидим в разделе 7, он также может быть своего рода «параметром удобства».) Эфемерные ключи Хотя выполнение нашего протокола не может генерировать форк, кроме как с помощью с незначительной вероятностью, злоумышленник может сгенерировать форк в r-м блоке после законного блок r был сгенерирован. Грубо говоря, как только Br был сгенерирован, Противник узнал, кто является проверяющим каждого шага. круглых r. Таким образом, он мог бы испортить их всех и обязать сертифицировать новый блок. ж Бр. Поскольку этот фальшивый блок может распространяться только после легитимного, пользователи, которые были обративший внимание не будет обманут.13 Тем не менее, f Br было бы синтаксически правильно, и мы хочу предотвратить производство. Мы делаем это посредством нового правила. По сути, члены проверяющего множества SV r,s шага s раунда r использовать эфемерные открытые ключи pkr,s я подписывать свои сообщения цифровой подписью. Эти ключи предназначены только для одноразового использования, а соответствующие им секретные ключи skr,s я уничтожаются после использования. Таким образом, если проверяющий позже испорченный, Противник не может заставить его подписать что-либо еще, что он не подписывал изначально. Естественно, мы должны гарантировать, что Противник не сможет вычислить новый ключ g пр,с я и убедить честного пользователя, что это правильный эфемерный ключ проверяющего устройства i \(\in\)SV r,s для использования на шаге s. 4.2 Общая сводка обозначений, понятий и параметров Обозначения • r \(\geq\)0: текущий номер раунда. • s \(\geq\)1: текущий номер шага в раунде r. • Br: блок, созданный в раунде r. • PKr: набор открытых ключей к концу раунда r−1 и в начале раунда r. • Sr: состояние системы к концу раунда r−1 и к началу раунда r.14. • PAY r: набор выплат, содержащийся в Br. • \(\ell\)r: лидер раунда r. \(\ell\)r выбирает набор выплат PAY r в раунде r (и определяет следующий Qr). • Qr: начальное число раунда r, величина (т. е. двоичная строка), которая генерируется в конце раунда r. и используется для выбора верификаторов для раунда r + 1. Qr не зависит от наборов выплат в блоках и им нельзя манипулировать с помощью \(\ell\)r. 13Подумайте о том, чтобы подкупить ведущего новостей крупной телесети, а сегодня создать и транслировать кинохронику. показывая, что госсекретарь Клинтон победила на последних президентских выборах. Большинство из нас признало бы это мистификацией. Но кого-то, выходящего из комы, можно обмануть. 14В несинхронной системе понятия «конец раунда r −1» и «начало раунда r» необходимо тщательно определить. Математически PKr и Sr вычисляются из исходного состояния S0 и блоков В1, . . . , Бр−1.• SV r,s: набор верификаторов, выбранных для шага s раунда r. • SV r: набор верификаторов, выбранных для раунда r, SV r = \(\cup\)s\(\geq\)1SV r,s. • MSV r,s и HSV r,s: соответственно набор злонамеренных проверяющих и набор честных проверяющих. в СВ р,с. MSV r,s \(\cup\)HSV r,s = SV r,s и MSV r,s ∩HSV r,s = \(\emptyset\). • n1 \(\in\)Z+ и n \(\in\)Z+: соответственно ожидаемое количество потенциальных лидеров в каждом СВ r,1, и ожидаемое количество проверяющих в каждом SV r,s для s > 1. Обратите внимание, что n1 << n, так как нам нужен хотя бы один честный честный член в SV r,1, но хотя бы большинство честных членов в каждом СВ r,s при s > 1. • h \(\in\)(0, 1): константа больше 2/3. h — коэффициент честности в системе. То есть доля честных пользователей или честных денег, в зависимости от использованного предположения, в каждом PKr составляет по крайней мере ч. • H: криптографическая функция hash, смоделированная как случайная oracle. • \(\bot\): специальная строка той же длины, что и выходные данные H. • F \(\in\)(0, 1): параметр, определяющий допустимую вероятность ошибки. Вероятность \(\leq\)F равна считается «незначительной», а вероятность \(\geq\)1 −F считается «подавляющей». • ph \(\in\)(0, 1): вероятность того, что лидер раунда r, \(\ell\)r, честен. В идеале ph = h. С существования Противника, значение ph будет определено в ходе анализа. • k \(\in\)Z+: параметр просмотра назад. То есть раунд r −k — это место, где проверяющими для раунда r являются выбран из — а именно SV r \(\subseteq\)PKr−k.15 • p1 \(\in\)(0, 1): на первом этапе раунда r пользователь в раунде r−k выбирается находящимся в SV r,1 с вероятность p1 \(\triangleq\) n1 |П Кр−к|. • p \(\in\)(0, 1): для каждого шага s > 1 раунда r пользователь в раунде r−k выбирается для пребывания в SV r,s с вероятность р \(\triangleq\) н |П Кр−к|. • CERT r: сертификат для Br. Это набор tH сигнатур H(Br) от собственных проверяющих в круглый р. • Br \(\triangleq\)(Br, CERT r) — проверенный блок. Пользователь i знает Br, если он владеет (и успешно верифицирует) обе части проверенного блока. Обратите внимание, что CERT r, видимый разными пользователями, может быть разным. • τ р i : (местное) время, в которое пользователь i знает Br. В протоколе Algorand каждый пользователь имеет свой собственные часы. Часы разных пользователей не обязательно должны быть синхронизированы, но должны иметь одинаковую скорость. Только в целях анализа мы рассматриваем эталонные часы и измеряем результативность игроков. связанные с ним времена. • \(\alpha\)r,s я и \(\beta\)r,s i : соответственно (локальное) время, когда пользователь i начинает и заканчивает выполнение шагов s круглый р. • Λ и \(\lambda\): по сути, верхние границы времени, необходимого для выполнения Шага 1 и Шага 1, соответственно. время, необходимое для любого другого шага протокола Algorand. Параметр Λ ограничивает время распространения одного блока размером 1 МБ. (В наших обозначениях Λ = \(\lambda\) \(\rho\),1MB. Вспоминая наши обозначения, мы установили \(\rho\) = 1 для простоты и что блоки если длина выбрана не более 1 МБ, то Λ = \(\lambda\)1,1,1MB.) 15Строго говоря, «r−k» должно быть «max{0, r−k}».Параметр \(\lambda\) ограничивает время распространения одного небольшого сообщения на одного верификатора за шаг s > 1. (При использовании, как в Bitcoin, подписей в форме эллиптической кривой с ключами длиной 32 байта, длина проверяющего сообщения составляет 200 байт. Таким образом, в наших обозначениях \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Предположим, что Λ = O(\(\lambda\)). Понятия • Выбор проверяющего. Для каждого раунда r и шага s > 1 SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. Каждый пользователь i \(\in\)PKr-k конфиденциально вычисляет свою подпись, используя свой долгосрочный ключ, и решает, стоит ли i \(\in\)SV r,s или нет. Если i \(\in\)SV r,s, то SIGi(r, s, Qr−1) является (r, s)-удостоверением i, компактно обозначаемым по \(\sigma\)r,s я. Для первого шага раунда r SV r,1 и \(\sigma\)r,1 я определяются аналогично, с заменой p на p1. проверяющие в SV r,1 являются потенциальными лидерами. • Выбор лидера. Пользователь i \(\in\)SV r,1 является лидером раунда r, обозначается \(\ell\)r, если H(\(\sigma\)r,1 i ) \(\leq\)H(\(\sigma\)r,1 j) для всех потенциальных лидеры j \(\in\)SV r,1. Всякий раз, когда сравниваются hash учетных данных двух игроков, в маловероятном случае В случае возникновения связей протокол всегда разрывает связи лексикографически в соответствии с (долгосрочными публичными ключи) потенциальных лидеров. По определению, значение hash учетных данных игрока \(\ell\)r также является наименьшим среди всех пользователей в ПКр−к. Обратите внимание, что потенциальный лидер не может в частном порядке решить, является он лидером или нет. не видя полномочий других потенциальных лидеров. Поскольку значения hash случайны и однородны, когда SV r,1 непусто, \(\ell\)r всегда существует и честный с вероятностью не менее h. Параметр n1 достаточно велик, чтобы гарантировать, что каждый SV r,1 непусто с подавляющей вероятностью. • Блочная структура. Непустой блок имеет вид Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)), а пустой блок имеет вид Br \(\varepsilon\) = (r, \(\emptyset\), Qr−1, H(Br−1)). Обратите внимание, что непустой блок все еще может содержать пустой набор платежей PAY r, если в в этом раунде или если лидер злонамерен. Однако непустой блок подразумевает, что тождество \(\ell\)r, его полномочия \(\sigma\)r,1 \(\ell\)r и SIG\(\ell\)r(Qr-1) были своевременно обнаружены. Протокол гарантирует что если лидер честен, то блок с подавляющей вероятностью окажется непустым. • Семена Qr. Если Br непусто, то Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), иначе Qr \(\triangleq\) H(Qr−1, r). Параметры • Отношения между различными параметрами. — Проверяющие и потенциальные лидеры раунда r выбираются из пользователей PKr−k, где k выбрано таким образом, чтобы противник не мог предсказать Qr−1 обратно в раунде r −k −1. с вероятностью лучше F: в противном случае он сможет внедрить злонамеренных пользователей для раунда r −k, все из которых будут потенциальными лидерами/проверяющими в раунде r, добившимися успеха в

наличие злонамеренного лидера или злонамеренного большинства в СВ для некоторых шагов, желаемых его. — Для шага 1 каждого раунда r n1 выбирается так, чтобы с подавляющей вероятностью SV r,1 ̸= \(\emptyset\). • Пример выбора важных параметров. — Выходные данные H имеют длину 256 бит. — h = 80%, n1 = 35. — Λ = 1 минута и \(\lambda\) = 10 секунд. • Инициализация протокола. Протокол начинается в момент 0 с r = 0. Поскольку не существует «B-1» или «CERT-1», синтаксически B-1 является общедоступным параметром, третий компонент которого определяет Q-1, и все пользователи знать B-1 в момент времени 0.

Algorand ′

1 В этом разделе мы создадим версию Algorand ′, работающую при следующем предположении. Допущение о честном большинстве пользователей: более 2/3 пользователей в каждом PKr честны. В разделе 8 мы покажем, как заменить приведенное выше предположение желаемым «Честным большинством». Денежное предположение. 5.1 Дополнительные обозначения и параметры Обозначения • m \(\in\)Z+: максимальное количество шагов в бинарном протоколе BA, кратное 3. • Lr \(\leq\)m/3: случайная величина, представляющая количество испытаний Бернулли, необходимых для получения 1, когда каждое испытание равно 1 с вероятностью ph 2 и имеется не более m/3 испытаний. Если все испытания провалятся, то Lr \(\triangleq\)м/3. Lr будет использоваться для верхней границы времени, необходимого для генерации блока Br. • ТН = 2n 3 + 1: количество подписей, необходимое в конечных условиях протокола. • CERT r: сертификат для Br. Это набор tH сигнатур H(Br) от собственных проверяющих в круглый р. Параметры • Отношения между различными параметрами. — Для каждого шага s > 1 раунда r n выбирается так, чтобы с подавляющей вероятностью |HSV r,s| > 2|MSV r,s| и |HSV r,s| + 4|MSV r,s| < 2н. Чем ближе к 1 значение h, тем меньше должно быть n. В частности, мы используем (варианты из) границ Чернова, обеспечивающих выполнение желаемых условий с подавляющей вероятностью. — m выбирается таким, что Lr < m/3 с подавляющей вероятностью. • Пример выбора важных параметров. — F = 10−12. — n \(\approx\)1500, k = 40 и m = 180.5.2 Реализация эфемерных ключей в Algorand ′ 1 Как уже упоминалось, мы хотим, чтобы проверяющий i \(\in\)SV r,s подписывал свое сообщение цифровой подписью mr,s я шага s в раунде r относительно эфемерного открытого ключа pkr,s i, используя эфемерный секретный ключ skr,s я что он сразу уничтожает после использования. Таким образом, нам нужен эффективный метод, гарантирующий, что каждый пользователь сможет убедитесь, что pkr,s я это действительно ключ, который можно использовать для проверки моей подписи мистера. я. Мы делаем это (в лучшем случае насколько нам известно) новое использование схем подписи на основе идентичности. На высоком уровне в такой схеме центральный орган A генерирует открытый главный ключ PMK, и соответствующий секретный главный ключ SMK. Учитывая личность U игрока U, A вычисляет: через SMK, секретный ключ подписи skU относительно открытого ключа U, и конфиденциально передает skU U. (Действительно, в схеме цифровой подписи на основе личности открытый ключ пользователя U — это сам U!) Таким образом, если А уничтожит SMK после вычисления секретных ключей пользователей, которых он хочет разрешить создавать цифровые подписи и не хранить никакого вычисленного секретного ключа, то U — единственный, кто может подписывать сообщения цифровой подписью относительно открытого ключа U. Таким образом, любой, кто знает «имя U», автоматически знает открытый ключ U и, таким образом, может проверить подписи U (возможно, используя также открытый главный ключ ПМК). В нашем приложении авторитетом A является пользователь i, а набор всех возможных пользователей U совпадает с пара круговых шагов (r, s) в, скажем, S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, где r′ — заданное раунд, а m + 3 — верхняя граница количества шагов, которые могут произойти в течение раунда. Это путь, пкр, с я \(\triangleq\)(i, r, s), чтобы все видели подпись i SIGr,s пкр,с я (мистер, с я) могу, с подавляющим вероятности, немедленно проверьте ее для первого миллиона раундов r, следующих за r'. Другими словами, сначала я генерирую PMK и SMK. Затем он заявляет, что ПМК — мой хозяин. открытый ключ для любого раунда r \(\in\)[r', r' + 106] и использует SMK для частного создания и хранения секрета. ключ скр,с я для каждой тройки (i, r, s) \(\in\)S. Сделав это, он уничтожает СМК. Если он решит, что он не часть СВ р,с, тогда я могу уйти из скр,с я один (поскольку протокол не требует, чтобы он аутентифицировал любое сообщение на шаге s раунда r). В противном случае я сначала использую skr,s я поставить цифровую подпись на своем сообщении, мистер, с я и затем уничтожает скр,с я. Обратите внимание: я могу опубликовать его первый открытый мастер-ключ, когда он впервые войдет в систему. То есть, тот же самый платеж \(\wp\), который приводит i в систему (в раунде r' или в раунде, близком к r'), может также указать по запросу i, что его открытый главный ключ для любого раунда r \(\in\)[r', r' + 106] равен PMK — например, включая пару вида (ПМК, [r', r' + 106]). Также обратите внимание, что, поскольку m + 3 — максимальное количество шагов в раунде, предполагая, что раунд занимает минуту, запаса созданных таким образом эфемерных ключей хватит почти на два года. В то же время Со временем изготовление этих эфемерных секретных ключей не займет много времени. Используя эллиптическую кривую В системе с 32B ключей каждый секретный ключ вычисляется за несколько микросекунд. Таким образом, если m + 3 = 180, тогда все 180 миллионов секретных ключей можно будет вычислить менее чем за час. Когда текущий раунд приближается к r' + 106, для обработки следующего миллиона раундов i генерирует новую пару (PMK', SMK') и сообщает, какой у него следующий запас эфемерных ключей. Например, если SIGi(PMK', [r' + 106 + 1, r' + 2 \(\cdot\) 106 + 1]) вводит новый блок, либо как отдельная «транзакция» или как некоторая дополнительная информация, являющаяся частью платежа. Тем самым, я сообщаю всем, что он/она должен использовать PMK' для проверки своих эфемерных подписей в следующем миллион раундов. И так далее. (Обратите внимание, что, следуя этому базовому подходу, другие способы реализации эфемерных ключей без использование подписей на основе личности, безусловно, возможно. Например, через Merkle trees.16) 16В этом методе я генерирую пару публично-секретных ключей (pkr,s я, скр,с я ) для каждой пары шагов раунда (r, s) в —скажем—Конечно, возможны и другие способы реализации эфемерных ключей — например, через Merkle trees. 5.3 Соответствие шагам Algorand ′ 1 с таковыми у BA⋆ Как мы уже говорили, раунд в Algorand ′ 1 имеет не более m + 3 шагов. Шаг 1. На этом этапе каждый потенциальный лидер i вычисляет и распространяет свой блок-кандидат Br я, вместе с собственным удостоверением \(\sigma\)r,1 я. Напомним, что эти учетные данные явно идентифицируют i. Это так, поскольку \(\sigma\)r,1 я \(\triangleq\)SIGi(r, 1, Qr−1). Потенциальный проверяющий i также распространяет как часть своего сообщения свою собственную цифровую подпись H(Br я). Не имеющая отношения к платежу или учетным данным, эта подпись i относится к его эфемерному обществу. ключ пкр,1 i: то есть он распространяет sigpkr,1 я (H(Br я)). Учитывая наши условности, вместо того, чтобы пропагандировать Бр я и сигпкр,1 я (H(Br я )) он мог бы распространяется SIGpkr,1 я (H(Br я)). Однако в нашем анализе нам необходим явный доступ к сигпкр,1 я (H(Br я)). Шаг 2. На этом этапе каждый верификатор i устанавливает \(\ell\)r Я буду потенциальным лидером, чьи полномочия hashed самый маленький, а Br i - блок, предложенный \(\ell\)r я. Поскольку в целях эффективности мы желает договориться о H(Br), а не непосредственно о Br, я распространяю сообщение, которое он хотел бы получить распространяется на первом этапе BA⋆с начальным значением v' я = H(Br я). То есть он распространяет v' я, после эфемерного подписания, конечно. (А именно, после его подписания относительно правого эфемерного открытый ключ, в данном случае это pkr,2 я .) Конечно, я также передаю свои собственные полномочия. Поскольку первый шаг BA⋆ состоит из первого шага протокола градуированного консенсуса GC, шаг 2 из Algorand соответствует первому шагу GC. Шаг 3. На этом шаге каждый верификатор i \(\in\)SV r,2 выполняет второй шаг BA⋆. То есть он отправляет то же сообщение, которое он отправил бы на втором этапе GC. Опять же, мое сообщение эфемерно подписано и сопровождается удостоверением личности. (В дальнейшем мы не будем говорить, что верификатор эфемерно подписывает свое сообщение, а также распространяет свои полномочия.) Шаг 4. На этом этапе каждый верификатор i \(\in\)SV r,4 вычисляет выходные данные GC (vi, gi) и эфемерно подписывает и отправляет то же сообщение, которое он отправил бы на третьем этапе BA⋆, то есть на первый шаг BBA⋆, с начальным битом 0, если gi = 2, и 1 в противном случае. Шаг s = 5, . . . , m + 2. Такой шаг, если он когда-либо был достигнут, соответствует шагу s−1 BA⋆ и, следовательно, шаг s−3 BBA⋆. Поскольку наша модель распространения достаточно асинхронна, мы должны учитывать возможность что в середине такого шага s проверяющий i \(\in\)SV r,s достигает информации, доказывающей его этот блок Br уже выбран. В этом случае я прекращает собственное выполнение раунда r Algorand ′ и начинает выполнять инструкции раунда (r + 1). {р', . . . , r′ + 106} \(\times\) {1, . . . , м + 3}. Затем он упорядочивает эти публичные ключи каноническим образом, сохраняет j-й публичный вводит j-й лист Merkle tree и вычисляет корневое значение Ri, которое он публикует. Когда он хочет подписать сообщение относительно ключа pkr,s я , я предоставляю не только фактическую подпись, но и путь аутентификации для pkr,s я относительно Ри. Обратите внимание, что этот путь аутентификации также доказывает, что pkr,s я хранится в j-м листе. Остальное детали могут быть легко заполнены.Соответственно, инструкции верификатора i \(\in\)SV r,s, помимо инструкций, соответствующих до шага s−3 BBA⋆, включая проверку того, остановлено ли выполнение BBA⋆ ранее. Шаг с'. Поскольку BBA⋆can только останавливается на этапе с фиксированной монетой на 0 или на шаге с фиксированной монетой на 1, инструкции различают, A (Конечное условие 0): s′ −2 ≡0 mod 3, или B (Конечное условие 1): s′ −2 ≡1 mod 3. Действительно, в случае А блок Br непуст, и поэтому необходимы дополнительные инструкции для убедитесь, что i правильно реконструирует Br вместе с соответствующим сертификатом CERT r. В случае Б, блок Br пуст, и поэтому мне дано указание установить Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), и вычислить CERT r. Если во время выполнения шага s я не увижу никаких свидетельств того, что блок Br уже был сгенерирован, то он отправляет то же сообщение, которое он отправил бы на шаге s-3 BBA⋆. Шаг m + 3. Если на шаге m + 3 i \(\in\)SV r,m+3 видит, что блок Br уже был сгенерирован в предыдущий шаг s', то он действует так же, как объяснено выше. В противном случае, вместо отправки того же сообщения, которое он отправил бы на шаге m BBA⋆, i ему было поручено на основе имеющейся у него информации вычислить Br и соответствующий ему сертификат CERT r. Напомним, что мы ограничиваем общее количество шагов раунда сверху m + 3. 5.4 Фактический протокол Напомним, что на каждом шаге s раунда r проверяющий i \(\in\)SV r,s использует свою долговременную пару публично-секретных ключей. предъявить свои полномочия, \(\sigma\)r,s я \(\triangleq\)SIGi(r, s, Qr−1), а также SIGi Qr−1 в случае s = 1. Верификатор i использует свой эфемерный секретный ключ skr,s я подписать его (r,s)-сообщение mr,s я. Для простоты, когда r и s равны ясно, мы пишем esigi(x), а не sigpkr,s i (x) для обозначения собственной эфемерной подписи значения i. x на шаге s раунда r и напишите ESIGi(x) вместо SIGpkr,s i (x) для обозначения (i, x, esigi(x)). Шаг 1. Блокируйте предложение Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный шаг 1 раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,1 или нет. • Если i /\(\varepsilon\)SV r,1, то я немедленно прекращает выполнение шага 1. • Если i \(\in\)SV r,1, то есть если i является потенциальным лидером, то он собирает выплаты в раунде r, которые было передано ему на данный момент и вычисляет максимальный набор выплат PAY r я от них. Далее он вычисляет свой «кандидатский блок» Br i = (r, PAY r i , SIGi(Qr−1), H(Br−1)). Наконец, он вычисляет сообщение мистер 1 я = (Бр i , esigi(H(Br i ))), \(\sigma\)r,1 i ), уничтожает свой эфемерный секретный ключ skr,1 я, а потом распространяет г-на, 1 я.Замечание. На практике, чтобы сократить глобальное выполнение шага 1, важно, чтобы (r, 1)- сообщения распространяются выборочно. То есть для каждого пользователя i в системе для первого (r, 1)- сообщение, которое он когда-либо получает и успешно проверяет17, игрок i распространяет его как обычно. Для всех другие (r, 1)-сообщения, которые игрок i получает и успешно проверяет, он распространяет их только в том случае, если hash значение содержащихся в нем учетных данных является наименьшим среди hash значений содержащихся учетных данных во всех (r, 1)-сообщениях, которые он получил и успешно проверил на данный момент. Кроме того, как предложил Георгиос Влахос, полезно, чтобы каждый потенциальный лидер i также распространял свои полномочия \(\sigma\)r,1 я отдельно: эти небольшие сообщения передаются быстрее, чем блоки, что обеспечивает своевременное распространение mr,1 Джей где содержащиеся учетные данные имеют небольшие значения hash, а те, которые содержат большие значения hash быстро исчезнуть. Шаг 2: Первый шаг Протокола поэтапного консенсуса GC Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный шаг 2 раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,2 или нет. • Если i /\(\varepsilon\)SV r,2, то я немедленно прекращает выполнение шага 2. • Если i \(\in\)SV r,2, то после ожидания времени t2 \(\triangleq\) \(\lambda\) + Λ i действует следующим образом. 1. Он находит пользователя \(\ell\) такого, что H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) для всех учетных данных \(\sigma\)r,1 дж которые являются частью успешно проверенные (r, 1)-сообщения, которые он получил на данный момент. 2. Если он получил от \(\ell\)действительное сообщение mr,1 \(\ell\) = (Бр \(\ell\), esig\(\ell\)(H(Br \(\ell\))) \(\sigma\)r,1 \(\ell\)),b, то я устанавливаю v' я \(\triangleq\)H(Br \(\ell\)); в противном случае я устанавливаю v' я \(\triangleq\) \(\bot\). 3. я вычисляю сообщение mr,2 я \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),c уничтожает свой эфемерный секретный ключ скр, 2 i , а затем распространяет mr,2 я. aПо сути, пользователь i в частном порядке решает, что лидером раунда r является пользователь \(\ell\). bОпять же, подписи игрока \(\ell\) и hash успешно проверены, и PAY r \(\ell\)в Бр \(\ell\)действителен для round r — хотя я не проверяю, PAY ли r \(\ell\)максимальен для \(\ell\)или нет. c Сообщение г-н, 2 я сигнализирует о том, что игрок i рассматривает v' i быть hash следующего блока или считать следующий блок должен быть пустым. 17То есть все подписи верны и и блок, и его hash валидны — хотя я и не проверяю является ли включенный набор выплат максимальным для его предлагающего или нет.

Шаг 3: Второй шаг GC Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный Шаг 3 раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,3 или нет. • Если i /\(\varepsilon\)SV r,3, то я немедленно прекращает выполнение шага 3. • Если i \(\in\)SV r,3, то после ожидания времени t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ я действую следующим образом. 1. Если существует значение v′ ̸= \(\bot\) такое, что среди всех допустимых сообщений mr,2 дж он получил, из них более 2/3 имеют вид (ESIGj(v′), \(\sigma\)r,2 j ), без всякого противоречия,a затем он вычисляет сообщение mr,3 я \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 я). В противном случае он вычисляет mr,3 я \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 я). 2. я уничтожаю его эфемерный секретный ключ skr,3 i , а затем распространяет mr,3 я. aТо есть он не получил двух действительных сообщений, содержащих ESIGj(v') и другой ESIGj(v'') соответственно, от игрока j. Здесь и далее, за исключением Конечных условий, определенных позже, всякий раз, когда честный игрок хочет сообщений заданной формы, сообщения, противоречащие друг другу, никогда не учитываются и не считаются действительными.Шаг 4: Выходные данные GC и первый шаг BBA⋆ Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный Шаг 4 раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,4 или нет. • Если i /\(\varepsilon\)SV r,4, то он немедленно прекращает выполнение шага 4. • Если i \(\in\)SV r,4, то после ожидания времени t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ я действую следующим образом. 1. Он вычисляет vi и gi, выходные данные GC, следующим образом. (a) Если существует значение v′ ̸= \(\bot\) такое, что среди всех допустимых сообщений mr,3 дж у него есть полученных, более 2/3 из них имеют вид (ESIGj(v′), \(\sigma\)r,3 j ), то он устанавливает vi \(\triangleq\)v′ и gi \(\triangleq\)2. (б) В противном случае, если существует значение v′ ̸= \(\bot\) такое, что среди всех допустимых сообщений мистер, 3 дж он получил, более 1/3 из них имеют вид (ESIGj(v′), \(\sigma\)r,3 j ), тогда он устанавливает vi \(\triangleq\)v′ и gi \(\triangleq\)1.a (c) В противном случае он полагает vi \(\triangleq\)H(Br \(\varepsilon\) ) и gi \(\triangleq\)0. 2. Он вычисляет bi, вход BBA⋆, следующим образом: bi \(\triangleq\)0, если gi = 2, и bi \(\triangleq\)1 в противном случае. 3. Он вычисляет сообщение mr,4 я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 я), уничтожает его эфемерное секретный ключ скр, 4 i , а затем распространяет mr,4 я. aМожно доказать, что v′ в случае (b), если он существует, должен быть единственным.

Шаг s, 5 \(\leq\)s \(\leq\)m + 2, s−2 ≡0 mod 3: шаг BBA⋆ с фиксированной монетой до 0 Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,s. • Если i /\(\varepsilon\)SV r,s, то я немедленно прекращает выполнение шага s. • Если i \(\in\)SV r,s, то он действует следующим образом. – Он ждет, пока не пройдет время ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. – Конечное условие 0: Если во время такого ожидания и в любой момент времени существует строка v ̸= \(\bot\) и шаг s′ такой, что (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 — то есть шаг s′ является шагом с фиксированной монетой до 0, (б) я получил как минимум tH = 2н 3 + 1 действительных сообщений mr,s′−1 дж = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 дж ),а и (c) я получил действительное сообщение, мистер 1 дж = (Бр j , esigj(H(Br j )), \(\sigma\)r,1 j ) с v = H(Br дж), затем я немедленно прекращаю выполнение шага s (и фактически раунда r), не пропаганда чего-либо; устанавливает Br = Br Дж; и устанавливает свой собственный CERT r как набор сообщений г-н,с'-1 дж подэтапа (b).b – Конечное условие 1: Если во время такого ожидания и в любой момент времени существует шаг s′ такой, что (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 — то есть шаг s′ является шагом с фиксированной монетой-1, и (b’) я получил как минимум tH действительных сообщений mr,s′−1 дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 дж ),с затем я немедленно прекращаю выполнение шага s (и фактически раунда r), не пропаганда чего-либо; устанавливает Br = Br й; и устанавливает свой собственный CERT r как набор сообщений г-н,с'-1 дж подэтапа (b’). – В противном случае в конце ожидания пользователь i выполняет следующее. Он устанавливает vi как большинство голосов vj во вторых компонентах всех действительных мистер, с-1 дж он получил. Он вычисляет bi следующим образом. Если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)0. В противном случае, если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)1. В противном случае он устанавливает bi \(\triangleq\)0. Он вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s я), уничтожает его эфемерное секретный ключ скр,с i , а затем распространяет mr,s я. aТакое сообщение от игрока j засчитывается, даже если игрок i также получил сообщение от j, подписавшегося за 1. Аналогично для Конечного условия 1. Как показано в анализе, это сделано для того, чтобы все честные пользователи знали Br за время \(\lambda\) друг от друга. bUser i теперь знает Br и свои собственные варианты завершения раунда r. Он по-прежнему помогает распространять сообщения как обычный пользователь, но не инициирует никакого распространения в качестве (r, s)-верификатора. В частности, он помогал распространять все сообщения в своей CERT r, чего достаточно для нашего протокола. Обратите внимание, что ему также следует установить bi \(\triangleq\)0 для бинарного протокола BA, но bi в любом случае в этом случае не нужен. Аналогичные вещи для всех будущих инструкций. cВ этом случае не имеет значения, кто такие виджеи.Шаг s, 6 \(\leq\)s \(\leq\)m + 2, s−2 ≡1 mod 3: шаг BBA⋆ с фиксированной монетой-1 Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,s или нет. • Если i /\(\varepsilon\)SV r,s, то я немедленно прекращает выполнение шага s. • Если i \(\in\)SV r,s, то он делает следующее. – Он ждет, пока не пройдет время ts \(\triangleq\)(2s −3)\(\lambda\) + Λ. – Конечное условие 0: те же инструкции, что и для шагов Coin-Fixed-To-0. – Конечное условие 1: те же инструкции, что и для шагов Coin-Fixed-To-0. – В противном случае в конце ожидания пользователь i выполняет следующее. Он устанавливает vi как большинство голосов vj во вторых компонентах всех действительных мистер, с-1 дж он получил. Он вычисляет bi следующим образом. Если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)0. В противном случае, если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)1. В противном случае он устанавливает bi \(\triangleq\)1. Он вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s я), уничтожает его эфемерное секретный ключ скр,с i , а затем распространяет mr,s я.

Шаг s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Шаг BBA⋆ с подбрасыванием монеты Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr-1 из третьего компонента Br-1 и проверяет, принадлежит ли i SV r,s или нет. • Если i /\(\varepsilon\)SV r,s, то я немедленно прекращает выполнение шага s. • Если i \(\in\)SV r,s, то он делает следующее. – Он ждет, пока не пройдет время ts \(\triangleq\)(2s −3)\(\lambda\) + Λ. – Конечное условие 0: те же инструкции, что и для шагов Coin-Fixed-To-0. – Конечное условие 1: те же инструкции, что и для шагов Coin-Fixed-To-0. – В противном случае в конце ожидания пользователь i выполняет следующее. Он устанавливает vi как большинство голосов vj во вторых компонентах всех действительных мистер, с-1 дж он получил. Он вычисляет bi следующим образом. Если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)0. В противном случае, если более 2/3 всех действительных mr,s−1 дж которые он получил, имеют вид (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он полагает bi \(\triangleq\)1. Иначе, пусть SV r,s−1 я — множество (r, s−1)-верификаторов, от которых он получил валидное сообщение мистер, с-1 дж . Он устанавливает bi \(\triangleq\)lsb(minj\(\varepsilon\)SV r,s−1 я H(\(\sigma\)r,s−1 дж )). Он вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s я), уничтожает его эфемерное секретный ключ скр,с i , а затем распространяет mr,s я.

Шаг m + 3: Последний шаг BBA⋆a Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный шаг m + 3 раунда r, как только он знает Br−1. • Пользователь i вычисляет Qr−1 из третьего компонента Br−1 и проверяет, принадлежит ли i SV r,m+3 или нет. • Если i /\(\varepsilon\)SV r,m+3, то я немедленно прекращает выполнение шага m + 3. • Если i \(\in\)SV r,m+3, то он делает следующее. – Он ждет, пока не пройдет время tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ. – Конечное условие 0: те же инструкции, что и для шагов Coin-Fixed-To-0. – Конечное условие 1: те же инструкции, что и для шагов Coin-Fixed-To-0. – В противном случае в конце ожидания пользователь i выполняет следующее. Он устанавливает outi \(\triangleq\)1 и Br \(\triangleq\)Br. й. Он вычисляет сообщение mr,m+3 я = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 я ), уничтожает его эфемерный секретный ключ skr,m+3 я , а затем распространяет mr,m+3 я сертифицировать Бр.б aС огромной вероятностью BBA⋆ завершился до этого шага, и мы указываем этот шаг для полноты. b Сертификат, полученный на этапе m + 3, не обязательно должен включать ESIGi(outi). Мы включили его только для единообразия: сертификаты теперь имеют единый формат независимо от того, на каком этапе они создаются.Реконструкция блока Round-r неверификаторами Инструкции для каждого пользователя i в системе: Пользователь i начинает свой собственный раунд r, как только узнает Br-1 и ожидает информацию о блоке следующим образом. – Если во время такого ожидания и в любой момент времени существует строка v и шаг s′ такие что (a) 5 \(\leq\)s′ \(\leq\)m + 3 с s′ −2 ≡0 mod 3, (b) я получил как минимум tH действительных сообщений mr,s′−1 дж = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 дж ), и (c) я получил действительное сообщение, мистер 1 дж = (Бр j , esigj(H(Br j )), \(\sigma\)r,1 j ) с v = H(Br дж), затем я немедленно останавливаю его собственное выполнение раунда r; устанавливает Br = Br дж; и устанавливает свой собственный CERT r быть набором сообщений mr,s′−1 дж подэтапа (b). – Если во время такого ожидания и в любой момент времени существует шаг s′ такой, что (a’) 6 \(\leq\)s′ \(\leq\)m + 3 с s′ −2 ≡1 mod 3, и (b’) я получил как минимум tH действительных сообщений mr,s′−1 дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 дж ), затем я немедленно останавливаю его собственное выполнение раунда r; устанавливает Br = Br й; и устанавливает свой собственный CERT r быть набором сообщений mr,s′−1 дж подэтапа (b’). – Если во время такого ожидания и в любой момент времени я получил хотя бы tH действительных сообщений мистер, м+3 дж = (ESIGj(1), ESIGj(H(Br ϫ )) \(\sigma\)r,m+3 дж ), затем я останавливаю его собственное выполнение раунда r сразу устанавливает Br = Br ǫ и устанавливает свой собственный CERT r как набор сообщений mr,m+3 дж за 1 и H(Br й). 5,5 Анализ Algorand ′ 1 Введем следующие обозначения для каждого раунда r \(\geq\)0, используемого в анализе. • Пусть T r — это время, когда первый честный пользователь узнает Br−1. • Пусть Ir+1 — интервал [T r+1, Tr+1 + \(\lambda\)]. Обратите внимание, что T 0 = 0 при инициализации протокола. Напомним, что для каждого s \(\geq\)1 и i \(\in\)SV r,s \(\alpha\)r,s я и \(\beta\)r,s я соответственно время начала и время окончания шага s игрока i. Более того, напомним, что ts = (2s −3)\(\lambda\) + Λ для каждого 2 ⩽ s ⩽ m + 3. Кроме того, пусть I0 \(\triangleq\){0} и t1 \(\triangleq\)0. Наконец, напомним, что Lr \(\leq\)m/3 — случайная величина, представляющая количество испытаний Бернулли. нужно увидеть 1, когда каждое испытание равно 1 с вероятностью ph 2 и имеется не более m/3 испытаний. Если все испытания терпят неудачу, тогда Lr \(\triangleq\)m/3. В анализе мы игнорируем время вычислений, поскольку оно на самом деле незначительно по сравнению с необходимым временем. для распространения сообщений. В любом случае, используя немного большие \(\lambda\) и Λ, время вычисления может включаться непосредственно в анализ. Большинство приведенных ниже утверждений справедливы «с подавляющим вероятность», и мы не можем неоднократно подчеркивать этот факт в анализе.5,6 Основная теорема Теорема 5.1. Следующие свойства с подавляющей вероятностью выполняются для каждого раунда r \(\geq\)0: 1. Все честные пользователи согласны с тем же блоком Бр. 2. Когда лидер \(\ell\)r честен, блок Br генерируется \(\ell\)r, Br содержит максимальный набор выплат. получено \(\ell\)r за время \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ, и все честные пользователи знают Br за время интервал Ir+1. 3. Когда лидер \(\ell\)r злонамерен, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ и все честные пользователи знают Br в интервале времени Ir+1. 4. ph = h2(1 + h−h2) для Lr, и лидер \(\ell\)r честен с вероятностью не ниже ph. Прежде чем доказывать нашу основную теорему, сделаем два замечания. Замечания. • Генерация блоков и реальная задержка. Время генерации блока Br определяется как T r+1 -T r. То есть, это разница между первым разом, когда честный пользователь изучает Br, и когда честный пользователь впервые узнает Br-1. Когда лидер раунда R честен, Свойство 2 наше. Основная теорема гарантирует, что точное время генерации Br составляет 8\(\lambda\) + Λ времени, независимо от того, что точное значение h > 2/3 может быть. Когда лидер злонамерен, свойство 3 подразумевает, что ожидаемое время генерации Br ограничено сверху ( 12 ph + 10)\(\lambda\) + Λ, опять же независимо от точного значение h.18 Однако ожидаемое время генерации Br зависит от точного значения h. Действительно, по свойству 4 ph = h2(1 + h−h2) и лидер честен с вероятностью не менее ph, таким образом 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\) + Λ). Например, если h = 80%, то E[T r+1 −T r] \(\leq\)12,7\(\lambda\) + Λ. • \(\lambda\) против Λ. Обратите внимание, что размер сообщений, отправленных проверяющими на этапе Algorand ′, доминирует. длиной ключей цифровой подписи, которая может оставаться фиксированной, даже если число пользователей огромно. Также обратите внимание, что на любом шаге s > 1 одно и то же ожидаемое количество n проверяющих может использоваться независимо от того, составляет ли количество пользователей 100 тыс., 100 млн или 100 млн. Это так, потому что n исключительно зависит от h и F. Таким образом, в целом, если не считать внезапной необходимости увеличить длину секретного ключа, значение \(\lambda\) должно оставаться неизменным независимо от того, насколько велико количество пользователей в сети. обозримое будущее. Напротив, при любой скорости транзакций количество транзакций растет с увеличением количества пользователи. Следовательно, для своевременной обработки всех новых транзакций размер блока должен также растут вместе с числом пользователей, в результате чего Λ тоже растет. Таким образом, в долгосрочной перспективе мы должны иметь \(\lambda\) << Λ. Соответственно, правильно иметь больший коэффициент для \(\lambda\), и фактически коэффициент 1 для Λ. Доказательство теоремы 5.1. Свойства 1–3 докажем по индукции: предполагая, что они выполняются для раунда r −1 (без ограничения общности они автоматически справедливы для «раунда -1» при r = 0), докажем их для круглый р. 18Действительно, E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Поскольку Br−1 однозначно определяется по предположению индукции, множество SV r,s однозначно определяется для каждого шага s раунда r. По выбору n1 SV r,1 ̸= \(\emptyset\) с подавляющей вероятностью. Мы сейчас сформулируйте следующие две леммы, доказанные в разделах 5.7 и 5.8. На протяжении всей индукции и в доказательства двух лемм, анализ для раунда 0 практически аналогичен индуктивному шагу, и мы выделим различия, когда они возникнут. Лемма 5.2. [Лемма о полноте] Предполагая, что свойства 1–3 выполняются для раунда r−1, когда лидер \(\ell\)r честен, с подавляющей вероятностью, • Все честные пользователи соглашаются на один и тот же блок Br, который генерируется \(\ell\)r и содержит максимальное набор выплат, полученный \(\ell\)r к моменту времени \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; и • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ и все честные пользователи знают Br в интервале времени Ir+1. Лемма 5.3. [Лемма о надежности] Предполагая, что свойства 1–3 выполняются для раунда r −1, когда лидер \(\ell\)r является вредоносным, с подавляющей вероятностью все честные пользователи согласны с одним и тем же блоком Br, T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ и все честные пользователи знают Br на интервале времени Ir+1. Свойства 1–3 выполняются при применении лемм 5.2 и 5.3 к r = 0 и индуктивному шагу. Наконец, переформулируем свойство 4 в виде следующей леммы, доказанной в разделе 5.9. Лемма 5.4. Учитывая свойства 1–3 для каждого раунда до r, ph = h2(1 + h −h2) для Lr и лидер \(\ell\)r честен с вероятностью не менее тел. Объединив вместе предыдущие три леммы, теорема 5.1 верна. ■ В приведенной ниже лемме утверждается несколько важных свойств раунда r с учетом индуктивности. гипотезу и будет использоваться при доказательстве трех приведенных выше лемм. Лемма 5.5. Предположим, что свойства 1–3 выполняются для раунда r−1. Для каждого шага s \(\geq\)1 раунда r и каждого честного проверяющего i \(\in\)HSV r,s, мы имеем, что (а) \(\alpha\)r,s я €Ир; (б) если игрок i ждал некоторое время ts, то \(\beta\)r,s я \(\in\)[T r + ts, Tr + \(\lambda\) + ts] для r > 0 и \(\beta\)р,с я = ts для r = 0; и (c) если игрок i ждал некоторое время ts, то к времени \(\beta\)r,s я, он получил все сообщения отправлено всеми честными проверяющими j \(\in\)HSV r,s′ для всех шагов s′ < s. Более того, для каждого шага s \(\geq\)3 имеем (г) не существует двух разных игроков i, i′ \(\in\)SV r,s и двух разных значений v, v′ одного и того же такой длины, что оба игрока ждали время ts, более 2/3 всех действительные сообщения mr,s-1 дж игрок, которого я получаю, подписался на v, и более 2/3 всех действительных сообщения г-н, с-1 дж игрок i' получает, подписался на v'. Доказательство. Свойство (a) следует непосредственно из индуктивного предположения, поскольку игрок i знает Br−1 в интервал времени Ir и сразу же начинает свой собственный шаг s. Свойство (б) непосредственно следует из (а): поскольку игрок i ждал некоторое время ts, прежде чем действовать, \(\beta\)r,s я = \(\alpha\)r,s я + ц. Заметим, что \(\alpha\)r,s я = 0 для р = 0. Теперь мы докажем свойство (в). Если s = 2, то по свойству (б) для всех верификаторов j \(\in\)HSV r,1 имеем \(\beta\)р,с я = \(\alpha\)r,s я + ts \(\geq\)T r + ts = Tr + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 дж + Л.Поскольку каждый верификатор j \(\in\)HSV r,1 отправляет свое сообщение в момент времени \(\beta\)r,1 дж и сообщение дойдет до всех честных пользователей не более чем за Λ время, за время \(\beta\)r,s я Игрок i получил сообщения, отправленные всеми верификаторами в HSV r,1 по желанию. Если s > 2, то ts = ts−1 + 2\(\lambda\). По свойству (b) для всех шагов s′ < s и всех верификаторов j \(\in\)HSV r,s′ \(\beta\)р,с я = \(\alpha\)r,s я + ts \(\geq\)T r + ts = Tr + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = Tr + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ дж + \(\lambda\). Поскольку каждый верификатор j \(\in\)HSV r,s′ отправляет свое сообщение в момент времени \(\beta\)r,s′ дж и сообщение дойдет до всех честных пользователей не более чем за \(\lambda\) время, за время \(\beta\)r,s я игрок i получил все сообщения, отправленные всеми честными проверяющими в HSV r,s′ для всех s′ < s. Таким образом, свойство (c) выполнено. Наконец, мы докажем свойство (d). Обратите внимание, что верификаторы j \(\in\)SV r,s−1 подписывают не более двух вещей в Шаг s-1 с использованием их эфемерных секретных ключей: значение vj той же длины, что и выходные данные hash, а также бит bj \(\in\){0, 1}, если s−1 \(\geq\)4. Поэтому в формулировке леммы мы требуем, чтобы v и v' имели одинаковую длину: многие верификаторы могли подписать оба значения hash v и бит b, таким образом, оба проходят порог 2/3. Предположим от противного, что существуют искомые верификаторы i, i' и значения v, v'. Обратите внимание, что некоторые злонамеренные проверяющие в MSV r,s-1 могли подписать как v, так и v', но каждый честный верификатор в HSV r,s−1 подписал не более одного из них. По свойству (c) и i, и i′ получили все сообщения, отправленные всеми честными проверяющими в HSV r,s-1. Пусть HSV r,s−1(v) — множество честных (r, s−1)-верификаторов, подписавших v, MSV r,s−1 я набор злонамеренных (r, s−1)-верификаторов, от которых i получил допустимое сообщение, и MSV r,s−1 я (v) подмножество MSV r,s−1 я от которого я получил действительную подпись сообщения v. По требованиям к я и в, у нас есть отношение \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 я (в)| |HSV r,s−1| + |MSV r,s−1 я |

2 3. (1) Мы сначала показываем |MSV r,s−1 я (в)| \(\leq\)|HSV r,s−1(v)|. (2) Если предположить обратное, то по соотношениям параметров с подавляющей вероятностью |HSV r,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 я |, таким образом отношение < |HSV r,s−1(v)| + |MSV r,s−1 я (в)| 3|MSV r,s−1 я | < 2|MSV r,s−1 я (в)| 3|MSV r,s−1 я | \(\leq\)2 3, противоречит неравенству 1. Далее, по неравенству 1 имеем 2|HSV r,s−1| + 2|MSV r,s−1 я | < 3|HSV r,s−1(v)| + 3|MSV r,s−1 я (в)| \(\leq\) 3|HSV r,s−1(v)| + 2|MSV r,s−1 я | + |MSV r,s−1 я (в)|. В сочетании с неравенством 2, 2|HSV r,s−1| < 3|HSV r,s−1(v)| + |MSV r,s−1 я (в)| \(\leq\)4|HSV r,s−1(v)|, что подразумевает |HSV r,s−1(v)| > 1 2|HSV r,s−1|.Аналогично, согласно требованиям к i′ и v′, имеем |HSV r,s−1(v′)| > 1 2|HSV r,s−1|. Поскольку честный проверяющий j \(\in\)HSV r,s−1 уничтожает свой эфемерный секретный ключ skr,s−1 дж перед распространением свое сообщение, Противник не может подделать подпись j для значения, которое j не подписывал, после узнав, что j является проверяющим. Таким образом, из двух приведенных выше неравенств следует |HSV r,s−1| \(\geq\)|HSV r,s−1(v)| + |HSV r,s−1(v′)| > |HSV r,s−1|, противоречие. Соответственно, искомых i, i′, v, v′ не существует, и Свойство (d) выполнено. ■ 5,7 Лемма о полноте Лемма 5.2. [Лемма о полноте, переформулированная] Предполагая, что свойства 1–3 выполняются для раунда r−1, когда лидер \(\ell\)r честен, с подавляющей вероятностью, • Все честные пользователи соглашаются на один и тот же блок Br, который генерируется \(\ell\)r и содержит максимальное набор выплат, полученный \(\ell\)r к моменту времени \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; и • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ и все честные пользователи знают Br в интервале времени Ir+1. Доказательство. По индуктивному предположению и лемме 5.5 для каждого шага s и верификатора i \(\in\)HSV r,s \(\alpha\)r,s я €Ир. Ниже мы шаг за шагом анализируем протокол. Шаг 1. По определению, каждый честный проверяющий i \(\in\)HSV r,1 распространяет желаемое сообщение mr,1 я в время \(\beta\)r,1 я = \(\alpha\)r,1 я, где мистер, 1 я = (Бр i , esigi(H(Br i ))), \(\sigma\)r,1 я ), Бр i = (r, PAY r i , SIGi(Qr−1), H(Br−1)), и ПЛАТИТЬ р i — максимальный набор выплат среди всех платежей, которые я видел к моменту времени \(\alpha\)r,1 я. Шаг 2. Произвольно зафиксируем честный проверяющий элемент i \(\in\)HSV r,2. По лемме 5.5, когда игрок i закончил ожидание во время \(\beta\)r,2 я = \(\alpha\)r,2 я + t2, он получил все сообщения, отправленные верификаторами в HSV r,1, включая мистер, 1 \(\ell\)р. По определению \(\ell\)r, в PKr-k не существует другого игрока, чьи полномочия hash значение меньше, чем H(\(\sigma\)r,1 \(\ell\)р). Конечно, Противник может испортить \(\ell\)r, увидев, что H(\(\sigma\)r,1 \(\ell\)р) очень мал, но к этому моменту игрок \(\ell\)r уничтожил свой эфемерный ключ и сообщение mr,1 \(\ell\)р был распространен. Таким образом, проверяющий i назначает своим лидером игрока \(\ell\)r. Соответственно, в момент времени \(\beta\)r,2 я, проверяющий i распространяет mr,2 я = (ESIGi(v′ i), \(\sigma\)r,2 i ), где v′ я = H(Br \(\ell\)р). Когда r = 0, единственная разница это \(\beta\)r,2 я = t2, а не находиться в диапазоне. То же самое можно сказать и о будущих шагах, и мы не буду подчеркивать их снова. Шаг 3. Произвольно зафиксируем честный проверяющий элемент i \(\in\)HSV r,3. По лемме 5.5, когда игрок i закончил ожидание во время \(\beta\)r,3 я = \(\alpha\)r,3 я + t3, он получил все сообщения, отправленные верификаторами в HSV r,2. По соотношениям параметров с подавляющей вероятностью |HSV r,2| > 2|МСВ г,2|. Более того, ни один честный проверяющий не стал бы подписывать противоречивые сообщения, а Противник не может подделать подпись честного проверяющего после того, как последний уничтожил свою соответствующую подпись. эфемерный секретный ключ. Таким образом, более 2/3 всех действительных (r, 2)-сообщений, которые я получил, поступили от честные проверяющие и в форме mr,2 дж = (ESIGj(H(Br \(\ell\)r)) \(\sigma\)r,2 j ), без противоречия. Соответственно, в момент времени \(\beta\)r,3 я Игрок я распространяет мистера, 3 я = (ESIGi(v′), \(\sigma\)r,3 i ), где v′ = H(Br \(\ell\)р).Шаг 4. Произвольно зафиксируем честный проверяющий элемент i \(\in\)HSV r,4. По лемме 5.5 игрок i получил все сообщения, отправленные верификаторами в HSV r,3, когда он закончил ожидание в момент времени \(\beta\)r,4 я = \(\alpha\)r,4 я + т4. Похоже на: Шаг 3: более 2/3 всех действительных (r, 3)-сообщений, которые я получил, получены от честных проверяющих и формы г-н,3 дж = (ESIGj(H(Br \(\ell\)r)) \(\sigma\)r,3 дж). Соответственно, игрок i устанавливает vi = H(Br \(\ell\)r), gi = 2 и bi = 0. В момент времени \(\beta\)r,4 я = \(\alpha\)r,4 я +t4 он размножается мистер, 4 я = (ESIGi(0), ESIGi(H(Br \(\ell\)r)) \(\sigma\)r,4 я). Шаг 5. Произвольно зафиксируем честный проверяющий элемент i \(\in\)HSV r,5. По лемме 5.5 у меня был бы игрок получил все сообщения, отправленные верификаторами в HSV r,4, если он дождался времени \(\alpha\)r,5 я + т5. Обратите внимание, что |HSV р,4| \(\geq\)tH.19 Также обратите внимание, что все верификаторы в HSV r,4 подписались за H(Br \(\ell\)р). Так как |MSV r,4| < tH, не существует v′ ̸= H(Br \(\ell\)r), который мог быть подписан tH проверяющие в SV r,4 (которые обязательно будут злонамеренными), поэтому игрок i не останавливается, пока не получил действительные сообщения г-н, 4 дж = (ESIGj(0), ESIGj(H(Br \(\ell\)r)) \(\sigma\)r,4 дж). Пусть Т — время, когда происходит последнее событие. Некоторые из этих сообщений могут исходить от злонамеренных игроков, но поскольку |МСВ р,4| < tH, хотя бы одно из них от честного верификатора в HSV r,4 и отправлено спустя время Т р +t4. Соответственно, T \(\geq\)T r +t4 > Tr +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, и к моменту T игрок i также получил сообщение мистер 1 \(\ell\)р. По построению протокола игрок i останавливается в момент \(\beta\)r,5 я = Т без пропаганда чего-либо; устанавливает Br = Br \(\ell\)р; и устанавливает свой собственный CERT r как набор (r, 4)-сообщений для 0 и H(Br \(\ell\)r), что он получил. Шаг s > 5. Аналогично, для любого шага s > 5 и любого проверяющего i \(\in\)HSV r,s игрок i будет иметь получил все сообщения, отправленные верификаторами в HSV r,4, если он дождался времени \(\alpha\)r,s я + ц. По тот же анализ, игрок i останавливается, ничего не распространяя, устанавливая Br = Br \(\ell\)r (и устанавливая свой собственный CERT r правильно). Конечно, злонамеренные верификаторы могут не останавливаться и распространять произвольные сообщений, но поскольку |MSV r,s| < tH, по индукции никакое другое v' не может быть подписано проверяющими tH на любом шаге 4 \(\leq\)s' < s, таким образом, честные проверяющие останавливаются только потому, что они получили действительный результат. (r, 4)-сообщения для 0 и H(Br \(\ell\)р). Реконструкция блока «Раунд-р». Анализ шага 5 применим к общему честному пользователь i почти без каких-либо изменений. Действительно, игрок i начинает свой раунд r в интервале Ir и остановится в момент T только тогда, когда он получит tH действительных (r, 4)-сообщений для H(Br \(\ell\)р). Опять же, потому что хотя бы одно из этих сообщений отправлено честными проверяющими и отправлено через время T r + t4, игрок i имеет также получил мистер 1 \(\ell\)r на время T. Таким образом, он устанавливает Br = Br \(\ell\)r с соответствующим CERT r. Осталось только показать, что все честные пользователи завершают свой раунд r за интервал времени Ir+1. Согласно анализу шага 5, каждый честный проверяющий i \(\in\)HSV r,5 знает Br на или раньше \(\alpha\)r,5 я + t5 \(\leq\) Т r + \(\lambda\) + t5 = T r + 8\(\lambda\) + Λ. Поскольку T r+1 — это момент, когда первый честный пользователь ir узнает Br, мы имеем Т r+1 \(\leq\)T r + 8\(\lambda\) + Λ по желанию. Более того, когда игрок знает Br, он уже помогает распространять сообщения в его CERT р. Обратите внимание, что все эти сообщения будут получены всеми честными пользователями в течение времени \(\lambda\), даже если 19Строго говоря, это происходит с очень высокой вероятностью, но не обязательно ошеломляющей. Однако это вероятность незначительно влияет на время работы протокола, но не влияет на его корректность. Когда h = 80%, то |HSV р,4| \(\geq\)tH с вероятностью 1−10−8. Если это событие не произойдет, протокол продолжится еще 3 шага. Поскольку вероятность того, что это не произойдет за два шага, ничтожна, протокол завершится на шаге 8. ожидание, то количество необходимых шагов будет почти 5.игрок ir был первым игроком, который их распространил. Более того, согласно приведенному выше анализу, мы имеем Т r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, таким образом, все честные пользователи получили mr,1 \(\ell\)r по времени T r+1 + \(\lambda\). Соответственно, все честные пользователи знают Br в интервале времени Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Наконец, при r = 0 фактически имеем T 1 ⩽t4 + \(\lambda\) = 6\(\lambda\) + Λ. Соединив всё воедино, Лемма 5.2 справедлива. ■ 5,8 Лемма о разумности Лемма 5.3. [Лемма о правильности, переформулированная] Предполагая, что свойства 1–3 выполняются для раунда r −1, когда лидер \(\ell\)r является вредоносным, с подавляющей вероятностью все честные пользователи соглашаются на один и тот же блок Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ, и все честные пользователи знают Br на интервале времени Ir+1. Доказательство. Мы рассматриваем две части протокола, GC и BBA⋆, отдельно. ГК. По индуктивному предположению и лемме 5.5 для любого шага s \(\in\){2, 3, 4} и любого честного верификатор i \(\in\)HSV r,s, когда игрок i действует в момент времени \(\beta\)r,s я = \(\alpha\)r,s я + тс, он получил все отправленные сообщения всеми честными проверяющими на шагах s' < s. Выделим два возможных случая для шага 4. Случай 1. Ни один верификатор i \(\in\)HSV r,4 не устанавливает gi = 2. В этом случае по определению bi = 1 для всех верификаторов i \(\in\)HSV r,4. То есть они начинаются с соглашение о 1 в бинарном протоколе BA. У них может не быть согласия по поводу их VI, но это не имеет значения, как мы увидим в двоичном BA. Случай 2. Существует верификатор ˆi \(\in\)HSV r,4 такой, что gˆi = 2. В данном случае мы показываем, что (1) gi \(\geq\)1 для всех i \(\in\)HSV r,4, (2) существует значение v′ такое, что vi = v′ для всех i \(\in\)HSV r,4, и (3) существует допустимое сообщение mr,1 \(\ell\) из некоторого верификатора \(\ell\) \(\varepsilon\)SV r,1 такого, что v′ = H(Br \(\ell\)). Действительно, поскольку игрок ˆi честен и устанавливает gˆi = 2, более 2/3 всех действительных сообщений mr,3 дж он получил для того же значения v′ ̸= \(\bot\) и установил vˆi = v′. По свойству (d) леммы 5.5 для любого другого честного (r, 4)-верификатора i не может быть более чем 2/3 всех действительных сообщений mr,3 дж которые i' получил, относятся к одному и тому же значению v'' ̸= v'. Соответственно, если я устанавливаю gi = 2, должно быть так, что я также видел > 2/3 большинства для v 'и установил vi = v', по желанию. Теперь рассмотрим произвольный верификатор i \(\in\)HSV r,4 с gi < 2. Аналогично анализу свойства (d) в лемме 5.5, поскольку игрок ˆi получил большинство > 2/3 за v′, более 1 2|HSV г,3| честный (r, 3)-верификаторы имеют знак v'. Поскольку я получил все сообщения от честных (r, 3)-верификаторов время \(\beta\)r,4 я = \(\alpha\)r,4 я + t4, в частности он получил более 1 2|HSV г,3| сообщения от них для v'. Поскольку |HSV r,3| > 2|MSV r,3|, я набрал > 1/3 большинства за v'. Соответственно, игрок я устанавливаю gi = 1, и свойство (1) выполняется. Обязательно ли игрок i устанавливает vi = v′? Предположим, что существует другое значение v′′ ̸= \(\bot\) такое, что игрок i также получил большинство в > 1/3 за v''. Некоторые из этих сообщений могут быть от вредоносного верификаторов, но по крайней мере один из них принадлежит какому-то честному верификатору j \(\in\)HSV r,3: действительно, поскольку |HSV г,3| > 2|МСВ г,3| и я получил все сообщения от HSV r,3, набора вредоносных верификаторы, от которых я получил валидное (r, 3)-сообщение, составляют <1/3 всех валидных сообщений. сообщения, которые он получил.По определению, игрок j должен был видеть > 2/3 большинства для v'' среди всех действительных (r, 2)-сообщений. он получил. Однако мы уже знаем, что некоторые другие честные (r, 3)-верификаторы видели 2/3 большинства за v' (потому что они подписались v'). По свойству (г) леммы 5.5 это не может случаются, и такого значения v'' не существует. Таким образом, игрок i должен установить vi = v′ по своему желанию, и свойство (2) выполнено. Наконец, учитывая, что некоторые честные (r, 3)-верификаторы получили большинство > 2/3 для v', некоторые (фактически, более половины) честных (r, 2)-верификаторов подписались за v' и распространили свои сообщения. Согласно построению протокола, эти честные (r, 2)-верификаторы должны были получить действительный сообщение, мистер 1 \(\ell\) от некоторого игрока \(\ell\) \(\varepsilon\)SV r,1 такого, что v′ = H(Br \(\ell\)), поэтому свойство (3) выполнено. ББА⋆. Мы снова различаем два случая. Случай 1. Все верификаторы i \(\in\)HSV r,4 имеют bi = 1. Это происходит после случая 1 GC. Так как |MSV r,4| < tH, в этом случае верификатора в SV r,5 нет. мог бы собрать или сгенерировать tH действительных (r, 4)-сообщений для бита 0. Таким образом, ни один честный верификатор в HSV r,5 остановился бы, потому что знает непустой блок Бр. Более того, хотя для бита 1 существует не менее tH допустимых (r, 4)-сообщений, s′ = 5 не удовлетворяет s′ −2 ≡1 mod 3, поэтому ни один честный проверяющий в HSV r,5 не остановится, потому что он знает Br = Br й. Вместо этого каждый верификатор i \(\in\)HSV r,5 действует в момент времени \(\beta\)r,5 я = \(\alpha\)r,5 я + t5, когда он получит все сообщения, отправленные HSV r,4 согласно лемме 5.5. Таким образом, игрок i получил большинство в 2/3 за 1. и устанавливает bi = 1. На шаге 6, который представляет собой шаг с фиксированной монетой до 1, хотя s′ = 5 удовлетворяет условию s′ −2 ≡0 mod 3, существует не существует действительных (r, 4)-сообщений для бита 0, поэтому ни один верификатор в HSV r,6 не остановится, потому что он знает непустой блок Бр. Однако при s′ = 6 s′ −2 ≡1 mod 3 и существуют |HSV р,5| \(\geq\)tH действительных (r,5)-сообщений для бита 1 из HSV r,5. Для каждого верификатора i \(\in\)HSV r,6, согласно лемме 5.5, в момент времени \(\alpha\)r,6 или раньше я + игрок t6 я получил все сообщения от HSV r,5, поэтому останавливаюсь, ничего не распространяя, и устанавливаю Бр = Бр й. Его CERT r представляет собой набор действительных (r, 5)-сообщений mr,5. дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 к) получено им, когда он останавливается. Далее, пусть игрок i будет либо честным проверяющим на шаге s > 6, либо обычным честным пользователем (т. е. не проверяющий). Аналогично доказательству леммы 5.2, игрок i устанавливает Br = Br ǫ и устанавливает свой собственный CERT r — набор действительных (r, 5)-сообщений mr,5. дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 к) у него есть получил. Наконец, аналогично лемме 5.2, Т р+1 \(\leq\) мин i\(\varepsilon\)HSV r,6 \(\alpha\)r,6 я + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, и все честные пользователи знают Br в интервале времени Ir+1, потому что первый честный пользователь i, который знает, что Br помог распространить (r, 5)-сообщения в своем CERT r. Случай 2. Существует верификатор ˆi \(\in\)HSV r,4 такой, что bˆi = 0. Это происходит после случая 2 GC и является более сложным случаем. По анализу GC, в этом случае существует допустимое сообщение mr,1 \(\ell\) такая, что vi = H(Br \(\ell\)) для всех i \(\in\)HSV r,4. Примечание что верификаторы в HSV r,4 могут не прийти к согласию относительно своих bi. Для любого шага s \(\in\){5, . . . , m + 3} и проверяющий i \(\in\)HSV r,s, по лемме 5.5 игроку я бы получил все сообщения, отправленные всеми честными проверяющими в HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1, если он дождался за время ц.Теперь рассмотрим следующее событие E: существует шаг s∗\(\geq\)5 такой, что для первого время в двоичном BA, какой-то игрок i∗\(\varepsilon\)SV r,s∗ (злонамеренный или честный) должен остановиться ничего не пропагандируя. Мы используем слово «следует остановиться», чтобы подчеркнуть тот факт, что, если игрок i∗ злонамерен, то он может сделать вид, что не должен останавливаться по протоколу и распространять сообщения по выбору Противника. Более того, по построению протокола либо (E.a) i∗ способен собирать или генерировать не менее tH действительных сообщений mr,s′−1 дж = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 дж ) для тех же v и s′, при этом 5 \(\leq\)s′ \(\leq\)s∗ и s′ −2 ≡0 mod 3; или (E.b) i∗ способен собирать или генерировать не менее tH действительных сообщений mr,s′−1 дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 дж ) для того же s′, где 6 \(\leq\)s′ \(\leq\)s∗ и s′ −2 ≡1 mod 3. Поскольку честные (r, s′ −1)-сообщения принимаются всеми честными (r, s′)-верификаторами до того, как они закончились ожидания в Шагах s', и поскольку Противник получает все не позднее, чем честные пользователи, без ограничения общности имеем s′ = s∗ и игрок i∗ является злонамеренным. Обратите внимание, что мы не требовали, чтобы значение v в E.a было hash допустимого блока: как станет ясно при анализе v = H(Br \(\ell\)) в этом подсобытии. Ниже мы сначала анализируем случай 2, следующий за событием E, а затем показываем, что значение s∗ существенно распределяется соответственно Lr (таким образом, событие E происходит до шага m + 3 с подавляющим вероятность с учетом соотношений параметров). Начнем с того, что для любого шага 5 \(\leq\)s < s∗ каждый честный проверяющий i \(\in\)HSV r,s ждал время ts и установил vi как большинство голосов действительные (r, s−1)-сообщения, которые он получил. Поскольку игрок i получил все честные (r, s−1)-сообщения следуя лемме 5.5, поскольку все честные верификаторы в HSV r,4 имеют подпись H(Br \(\ell\)) следующий случай 2 GC, и поскольку |HSV r,s−1| > 2|MSV r,s−1| для каждого s по индукции мы имеем игрока i установил vi = H(Br \(\ell\)). То же самое справедливо для каждого честного проверяющего i \(\in\)HSV r,s∗, который не останавливается, не распространяя что угодно. Теперь рассмотрим шаг s∗ и выделим четыре подслучая. Случай 2.1.а. Событие E.a происходит и существует честный проверяющий i′ \(\in\)HSV r,s∗, который должен также остановиться, ничего не пропагандируя. В этом случае мы имеем s∗−2 ≡0 mod 3 и шаг s∗ — это шаг с фиксированной монетой до 0. Автор Согласно определению, игрок i получил не менее tH действительных (r, s∗−1)-сообщений вида (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 дж ). Поскольку все верификаторы в HSV r,s∗−1 имеют знак H(Br \(\ell\)) и |MSV r,s∗−1| < tH, имеем v = H(Br \(\ell\)). Поскольку хотя бы tH −|MSV r,s∗−1| \(\geq\)1 (r, s∗−1)-сообщений, полученных i′ для 0 и v отправляются верификаторами в HSV r,s∗−1 через время T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\) +Λ, игрок i' получил мистера, 1 \(\ell\) к тому моменту, когда он получит эти (r, s∗−1)-сообщения. Таким образом, игрок я останавливаюсь, ничего не распространяя; устанавливает Br = Br \(\ell\); и устанавливает свой CERT r в качестве набор действительных (r, s∗−1)-сообщений для 0 и v, которые он получил. Далее мы покажем, что любой другой верификатор i \(\in\)HSV r,s∗ либо остановился с Br = Br \(\ell\), или установил bi = 0 и распространил (ESIGi(0), ESIGi(H(Br \(\ell\))) \(\sigma\)r,s я). Действительно, поскольку шаг s∗ это первый раз, когда какой-то верификатор должен остановиться, ничего не распространяя, здесь нет существует шаг s′ < s∗ с s′ −2 ≡1 mod 3 такой, что tH (r, s′ −1)-верификаторы имеют знак 1. Соответственно, ни один верификатор в HSV r,s∗ не останавливается с Br = Br й.Более того, поскольку все честные проверяющие на этапах {4, 5, . . . , s∗−1} имеют знак H(Br \(\ell\)), есть не существует шага s′ \(\leq\)s∗ с s′ −2 ≡0 mod 3 такого, что tH (r, s′ −1)-верификаторы подписались некоторый v′′ ̸= H(Br \(\ell\)) — действительно, |MSV r,s′−1| < тХ. Соответственно, ни один верификатор в HSV r,s∗ не останавливает где Br ̸= Br ϫ и Br ̸= Br \(\ell\). То есть, если игрок i \(\in\)HSV r,s∗ остановился без распространяя что-либо, он, должно быть, установил Br = Br \(\ell\). Если игрок i \(\in\)HSV r,s∗ ждал время ts∗ и распространил сообщение в момент времени \(\beta\)r,s∗ я = \(\alpha\)r,s∗ я + ts∗, он получил все сообщения от HSV r,s∗−1, включая как минимум tH −|MSV r,s∗−1| из них для 0 и v. Если я видел > 2/3 большинства за 1, то он видел более 2(tH −|MSV r,s∗−1|) допустимых (r, s∗−1)-сообщений для 1, причем более чем 2tH−3|MSV r,s∗−1| из них от честных (r, s∗−1)-верификаторов. Однако это подразумевает |HSV r,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, что противоречит тот факт, что |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n, который исходит из отношений для параметров. Соответственно я не вижу > 2/3 большинство за 1, и он устанавливает bi = 0, поскольку шаг s∗ — это шаг с фиксированной монетой до 0. Как у нас есть видно, vi = H(Br \(\ell\)). Таким образом, i распространяет (ESIGi(0), ESIGi(H(Br \(\ell\))) \(\sigma\)r,s я) как мы и хотели показать. Для шага s∗+ 1, поскольку игрок i′ помог распространить сообщения в своем CERT r не позднее времени \(\alpha\)r,s∗ я' + ts∗, все честные проверяющие в HSV r,s∗+1 получили как минимум tH допустимых (r, s∗−1)-сообщений для бита 0 и значения H(Br \(\ell\)) не позднее, чем они будут готовы ожидание. Более того, верификаторы в HSV r,s∗+1 не остановятся, пока не получат те (r, s∗−1)- сообщений, поскольку не существует других действительных (r, s′ −1)-сообщений для бита 1 с s′ −2 ≡1 mod 3 и 6 \(\leq\)s′ \(\leq\)s∗+ 1 по определению шага s∗. В частности, Шаг s∗+ 1 сам по себе является шагом Coin-Fixed-To-1, но ни один честный верификатор в HSV r,s∗ не распространил сообщение для 1 и |MSV r,s∗| < тХ. Таким образом, все честные верификаторы в HSV r,s∗+1 останавливаются, ничего не распространяя, и устанавливают Br = Бр \(\ell\): как и прежде, они получили г-н,1 \(\ell\) прежде чем они получат желаемые (r, s∗−1)-сообщения.20 То же самое можно сказать обо всех честных верификаторах будущих шагов и обо всех честных пользователях в целом. В частности, все они знают Br = Br \(\ell\)в интервале времени Ir+1 и Т r+1 \(\leq\) \(\alpha\)r,s∗ я' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Случай 2.1.б. Событие E.b происходит и существует честный проверяющий i′ \(\in\)HSV r,s∗, который должен также остановиться, ничего не пропагандируя. В этом случае мы имеем s∗−2 ≡1 mod 3 и шаг s∗ — это шаг с фиксированной монетой до 1. Анализ аналогичен случаю 2.1.а, но многие детали опущены. 20Если он злонамерен, он может послать господина,1 \(\ell\) поздно, надеясь, что некоторые честные пользователи/верификаторы не получили mr,1 \(\ell\) еще когда они получат за это желаемый сертификат. Однако, поскольку верификатор ˆi \(\in\)HSV r,4 установил bˆi = 0 и vˆi = H(Br \(\ell\)), как прежде чем мы увидим, что более половины честных проверяющих i \(\in\)HSV r,3 установили vi = H(Br \(\ell\)). Это далее подразумевает больше более половины честных проверяющих i \(\in\)HSV r,2 установили vi = H(Br \(\ell\)), и все эти (r, 2)-верификаторы получили mr,1 \(\ell\). Как Злоумышленник не может отличить проверяющего от непроверяющего, он не может нацелиться на распространение mr,1 \(\ell\) к (r, 2)-верификаторам так, чтобы это не увидели те, кто не проверял. На самом деле, с большой вероятностью, более половины (или хорошая постоянная доля) всех честных пользователей видели mr,1 \(\ell\) после ожидания t2 с начала своего раунда r. С этого момента время \(\lambda\)′, необходимое для mr,1 \(\ell\) чтобы охватить оставшихся честных пользователей, намного меньше Λ, и для простоты мы не напишите это в анализе. Если 4\(\lambda\) \(\geq\) \(\lambda\)′, то анализ проходит без изменений: к концу шага 4 все честные пользователи получили бы mr,1 \(\ell\). Если размер блока становится огромным и 4\(\lambda\) < \(\lambda\)′, то на шагах 3 и 4 протокол может попросить каждого проверяющего дождаться \(\lambda\)'/2, а не 2\(\lambda\), и анализ продолжится.Как и раньше, игрок i′ должен получить не менее tH действительных (r, s∗−1)-сообщений вида (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 дж ). Опять же, по определению s∗, не существует шага 5 \(\leq\)s′ < s∗ с s′ −2 ≡0 mod 3, где по крайней мере tH (r, s′ −1)-верификаторов имеют знак 0 и тот же v. Таким образом, игрок i' останавливается, ничего не распространяя; устанавливает Br = Br й; и наборы его собственный CERT r — это набор действительных (r, s∗−1)-сообщений для бита 1, которые он получил. Более того, любой другой верификатор i \(\in\)HSV r,s∗ либо остановился с Br = Br ϫ или установил bi = 1 и распространяется (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ я ). Поскольку игрок i' способствовал распространению (r, s∗−1)-сообщения в его CERT r к моменту времени \(\alpha\)r,s∗ я' + ts∗, снова все честные проверяющие в HSV r,s∗+1 останавливаемся, ничего не распространяя, и устанавливаем Br = Br й. Аналогично, все честно пользователи знают Br = Br ϫ в интервале времени Ir+1 и Т r+1 \(\leq\) \(\alpha\)r,s∗ я' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Случай 2.2.а. Событие E.a происходит, и не существует честного проверяющего i′ \(\in\)HSV r,s∗, который также должен остановиться, ничего не распространяя. В этом случае обратите внимание, что игрок i∗ может иметь действительный CERT r i∗состоящий из желаемого tH (r, s∗−1)-сообщения, которые Противник может собирать или генерировать. Однако злонамеренный проверяющие могут не способствовать распространению этих сообщений, поэтому мы не можем заключить, что честный пользователи получат их за время \(\lambda\). В самом деле, |MSV r,s∗−1| из этих сообщений могут быть от злонамеренные (r, s∗−1)-верификаторы, которые вообще не распространяли свои сообщения, а только отправляли их злонамеренным проверяющим на этапе s∗. Как и в случае 2.1.a, здесь мы имеем s∗−2 ≡0 mod 3, шаг s∗ — это шаг с фиксированной монетой до 0, и (r, s∗−1)-сообщения в CERT r i∗ относятся к биту 0 и v = H(Br \(\ell\)). Действительно, все честно (r, s∗−1)-верификаторы знака v, поэтому Противник не может сгенерировать tH действительных (r, s∗−1)-сообщений для другого v'. Более того, все честные (r, s∗)-верификаторы дождались времени ts∗ и не увидели > 2/3 большинства для бита 1, опять же потому, что |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2н. Таким образом, каждый честный проверяющий i \(\in\)HSV r,s∗sets bi = 0, vi = H(Br \(\ell\)) большинством голосов и распространяет mr,s∗ я = (ESIGi(0), ESIGi(H(Br \(\ell\))) \(\sigma\)r,s∗ я ) в момент времени \(\alpha\)r,s∗ я + тс∗. Теперь рассмотрим честных проверяющих на шаге s∗+ 1 (это шаг с фиксированной монетой до 1). Если Злоумышленник фактически отправляет сообщения в CERT r. i∗ к некоторым из них и заставляет их стоп, тогда аналогично случаю 2.1.а все честные пользователи знают Br = Br \(\ell\)в пределах временного интервала ИК+1 и Т r+1 \(\leq\)T r + \(\lambda\) + ts∗+1. В противном случае все честные проверяющие на шаге s∗+1 получили все (r, s∗)-сообщения для 0 и Ч(Бр \(\ell\)) от HSV r,s∗ после времени ожидания ts∗+1, что приводит к большинству > 2/3, поскольку |HSV r,s∗| > 2|MSV r,s∗|. Таким образом, все верификаторы в HSV r,s∗+1 распространяют свои сообщения для 0 и H(Br \(\ell\)) соответственно. Обратите внимание, что верификаторы в HSV r,s∗+1 не останавливаются на Br = Br. \(\ell\), потому что шаг s∗+ 1 не является шагом с фиксированной монетой до 0. Теперь рассмотрим честных проверяющих на шаге s∗+2 (который является шагом подбрасывания монеты). Если злоумышленник отправляет сообщения в CERT r i∗ к некоторым из них и заставляет их остановиться, опять же все честные пользователи знают Бр = Бр \(\ell\)в интервале времени Ir+1 и Т r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.В противном случае все честные проверяющие на шаге s∗+ 2 получили все (r, s∗+ 1)-сообщения для 0 и H(Br \(\ell\)) от HSV r,s∗+1 после времени ожидания ts∗+2, что приводит к большинству > 2/3. Таким образом, все они распространяют свои сообщения для 0 и H(Br \(\ell\)) соответственно: вот они и делают в данном случае не стоит «подбрасывать монетку». Опять же, обратите внимание, что они не прекращаются, не распространяясь. потому что шаг s∗+ 2 не является шагом с фиксированной монетой до 0. Наконец, для честных проверяющих на этапе s∗+3 (который является еще одним шагом Coin-Fixed-To-0) все из них получили бы как минимум tH действительных сообщений для 0 и H(Br \(\ell\)) из HSV s∗+2, если они действительно ждут время ts∗+3. Таким образом, независимо от того, отправляет ли Противник сообщения в CERT р i∗ к любому из них, все верификаторы в HSV r,s∗+3 останавливаются с Br = Br \(\ell\), без пропагандируя что-либо. В зависимости от того, как действует Противник, некоторые из них могут иметь собственный CERT r, состоящий из этих (r, s∗−1)-сообщений в CERT r i∗, а остальные имеют свой собственный CERT r, состоящий из этих (r, s∗+ 2)-сообщений. В любом случае, все честные пользователи знать Br = Br \(\ell\)в интервале времени Ir+1 и Т r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Случай 2.2.б. Событие E.b происходит, и не существует честного проверяющего i′ \(\in\)HSV r,s∗, который также должен остановиться, ничего не распространяя. Анализ в этом случае аналогичен анализам в случае 2.1.b и случае 2.2.a, поэтому много деталей. были опущены. В частности, CERT r i∗состоит из tH искомых (r, s∗−1)-сообщений для бита 1, который противник может собрать или сгенерировать, s∗−2 ≡1 mod 3, шаг s∗ — это Шаг Coin-Fixed-To-1, и ни один честный (r, s∗)-верификатор не смог бы увидеть большинство > 2/3 для 0. Таким образом, каждый верификатор i \(\in\)HSV r,s∗ устанавливает bi = 1 и распространяет mr,s∗ я = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ я ) в момент времени \(\alpha\)r,s∗ я + тс∗. Как и в случае 2.2.а, не более чем за 3 шага (т. е. протокол достигает шага s∗+3, что является еще одним шагом Coin-Fixed-To-1), все честные пользователи знают Br = Br ψ в интервале времени Ir+1. Более того, T r+1 может быть \(\leq\)T r+\(\lambda\)+ts∗+1 или \(\leq\)T r+\(\lambda\)+ts∗+2, или \(\leq\)T r + \(\lambda\) + ts∗+3, в зависимости от того, когда честный проверяющий впервые сможет остановить без распространения. Объединив четыре подслучая, мы получаем, что все честные пользователи знают Br в пределах временного интервала. ИК+1, с T r+1 \(\leq\)T r + \(\lambda\) + ts∗ в случаях 2.1.a и 2.1.b, и T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 в случаях 2.2.a и 2.2.b. Осталось оценить сверху s∗ и, следовательно, T r+1 для случая 2, и мы делаем это, рассматривая, как много раз этапы «Genuinely-Flipped» действительно выполняются в протоколе: то есть некоторые честные проверяющие действительно подбросили монетку. В частности, произвольно зафиксируйте шаг «подлинно подброшенной монеты» s′ (т. е. 7 \(\leq\)s′ \(\leq\)m + 2 и s′ −2 ≡2 mod 3), и пусть \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 дж ). А пока предположим, что s′ < s∗, потому что в противном случае ни один честный проверяющий на самом деле не подбросит монету на шагах s', согласно предыдущему дискуссии. По определению SV r,s'-1, значение hash учетных данных \(\ell\)' также является наименьшим среди все пользователи в PKr-k. Поскольку функция hash является случайной oracle, в идеале игрок \(\ell\)′ честен с вероятность не менее h. Как мы покажем позже, даже если Противник изо всех сил старается предсказать исход событий, выведите случайный oracle и наклоните вероятность, игрок \(\ell\)' все еще честен с вероятностьюхотя бы ph = h2(1 + h−h2). Ниже мы рассмотрим случай, когда это действительно имеет место, т. е. \(\ell\)′ \(\in\)HSV r,s′−1. Обратите внимание, что каждый честный проверяющий i \(\in\)HSV r,s′ получил все сообщения от HSV r,s′−1 по время \(\alpha\)r,s′ я + ц'. Если игроку i нужно подбросить монетку (т. е. он не набрал большинства более 2/3 за тот же бит b \(\in\) {0, 1}), то он устанавливает bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)' )). Если существует еще один честный проверяющий i′ \(\in\)HSV r,s′, который набрал > 2/3 большинства для бита b \(\in\) {0, 1}, то по свойству (d) из леммы 5.5 ни один честный проверяющий в HSV r,s' какое-то время не получил бы большинства > 2/3 б′ ̸= б. Поскольку lsb(H(\(\sigma\)r,s′−1 \(\ell\)' )) = b с вероятностью 1/2 все честные проверяющие в HSV r,s′ достигают согласие по b с вероятностью 1/2. Конечно, если такого верификатора i' не существует, то все честные верификаторы в HSV r,s' согласовывают бит lsb(H(\(\sigma\)r,s'−1 \(\ell\)' )) с вероятностью 1. Объединив вероятность для \(\ell\)′ \(\in\)HSV r,s′−1, мы получаем, что честные проверяющие в HSV r,s′ достичь согласия по биту b \(\in\){0, 1} с вероятностью не менее ph 2 = h2(1+h−h2) 2 . Более того, путем индукции по большинству голосов, как и раньше, все честные проверяющие в HSV r,s' имеют набор vi быть H(Br \(\ell\)). Таким образом, как только на шаге s будет достигнуто соглашение по b, Tr+1 будет либо \(\leq\)T r + \(\lambda\) + ts′+1, либо \(\leq\)T r + \(\lambda\) + ts′+2, в зависимости от того, b = 0 или b = 1, после анализа случаев 2.1.a и 2.1.b. В В частности, дальнейший шаг Coin-Genuinely-Flipped выполняться не будет: то есть проверяющие в такие шаги по-прежнему проверяют, что они являются проверяющими, и поэтому ждут, но все они остановятся без пропагандируя что-либо. Соответственно, перед шагом s∗ количество раз выполнения шагов Coin-GenuinelyFlipped распределяется согласно случайной величине Lr. Позволяя шагу s' быть последним шагом действительно подброшенной монеты согласно Lr, согласно построению протокола у нас есть s′ = 4 + 3Lr. Когда Противнику следует сделать Шаг s∗, если он хочет задержать T r+1 настолько, насколько возможно? Можно даже предположить, что Противник заранее знает реализацию Lr. Если s∗> s′, то это бесполезно, потому что честные проверяющие уже пришли к соглашению в Шаг с'. Конечно, в этом случае s∗ будет s′ +1 или s′ +2, опять же в зависимости от того, b = 0 или b = 1. Однако на самом деле это случаи 2.1.a и 2.1.b, и результирующий T r+1 в точности соответствует так же, как и в том случае. Точнее, Т r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Если s∗< s′ −3, то есть s∗ находится перед предпоследним шагом «подлинного подбрасывания монеты», то по анализ случаев 2.2.а и 2.2.б, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < Tr + \(\lambda\) + ts′. То есть Противник фактически ускоряет достижение соглашения по Бр. Если s∗= s′ −2 или s′ −1, то есть шаг Coin-Fixed-To-0 или шаг Coin-Fixed-To-1 непосредственно перед шагом s', а затем путем анализа четырех подслучаев честные проверяющие в Шаги s' больше не могут подбрасывать монеты, потому что они либо остановились, не распространяясь, или видели > 2/3 большинства для того же бита b. Поэтому у нас есть Т r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.В общем, как бы то ни было, мы имеем Т r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = Т r + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = Т г + (6Lr + 10)\(\lambda\) + Λ, как мы хотели показать. Худший случай — когда s∗= s′ −1 и имеет место случай 2.2.b. Объединяя случаи 1 и 2 бинарного протокола BA, лемма 5.3 верна. ■ 5,9 Безопасность начального Qr и вероятность честного лидера Осталось доказать лемму 5.4. Напомним, что верификаторы в раунде r берутся из PKr−k и выбираются по величине Qr−1. Причина введения параметра ретроспективного анализа k состоит в том, чтобы убедиться, что на этапе r -k, когда Противник сможет добавить новых злонамеренных пользователей относительно PKr−k, он не может предсказать величину Qr−1, кроме как с пренебрежимо малой вероятностью. Обратите внимание, что Функция hash представляет собой случайную oracle, а Qr-1 является одним из ее входных данных при выборе проверяющих для раунда r. Таким образом, сколько бы злонамеренных пользователей ни добавляли в PKr-k, с точки зрения Злоумышленника каждый один из них по-прежнему выбирается в качестве проверяющего на этапе раунда r с требуемой вероятностью p (или p1 для шага 1). Точнее, имеем следующую лемму. Лемма 5.6. При k = O(log1/2 F) в каждом раунде r с подавляющей вероятностью Противник не запрашивал Qr-1 случайному oracle еще в раунде r -k. Доказательство. Мы действуем по индукции. Предположим, что для каждого раунда \(\gamma\) < r Противник не запрашивал Q\(\gamma\)−1 случайному oracle в раунде \(\gamma\) −k.21. Рассмотрим следующую мысленную игру, в которую играет Противник на раунде r−k пытается предсказать Qr−1. На шаге 1 каждого раунда \(\gamma\) = r −k, . . . , r−1, учитывая конкретный Q\(\gamma\)−1, не запрашиваемый в случайном oracle, упорядочив игроков i \(\in\)PK\(\gamma\)−k в соответствии со значениями hash H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) все чаще мы получаем случайную перестановку над PK\(\gamma\)−k. По определению, лидер \(\ell\) \(\gamma\) – это первый пользователь в перестановке и честен с вероятностью h. Более того, когда PK\(\gamma\)−k велико достаточно, чтобы для любого целого числа x \(\geq\)1 вероятность того, что все первые x пользователей в перестановке являются злонамеренный, но (x + 1)-й честный — это (1 −h)xh. Если \(\ell\) \(\gamma\) честный, то Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Поскольку Противник не может подделать подпись от \(\ell\) \(\gamma\), Q\(\gamma\) распределяется равномерно случайным образом с точки зрения Противника и, за исключением с экспоненциально малой вероятностью22 не был запрошен H на этапе r −k. Поскольку каждый Q\(\gamma\)+1, Q\(\gamma\)+2, . . . , Qr−1 соответственно является выходом H с Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 в качестве одного из входов, все они кажутся противнику случайными, и противник не мог запросить Qr-1 к H в раунд r −k. Соответственно, единственный случай, когда Противник может с хорошей вероятностью предсказать Qr-1 на раунде r−k — это когда все лидеры \(\ell\)r−k, . . . , \(\ell\)r−1 являются вредоносными. Снова рассмотрим раунд \(\gamma\) \(\in\){r−k. . . , r−1} и случайная перестановка над PK\(\gamma\)-k, вызванная соответствующими значениями hash. Если для некоторых x \(\geq\)2, все первые x−1 пользователей в перестановке являются злонамеренными, а x-й — честными, тогда У противника есть x возможных вариантов выбора Q\(\gamma\): любой из форм H(SIGi(Q\(\gamma\)−1, \(\gamma\))), где i — один из 21Поскольку k — небольшое целое число, без ограничения общности можно предположить, что первые k раундов протокола выполняются в безопасной среде, и индуктивная гипотеза справедлива для этих раундов. 22То есть экспоненциально зависит от длины вывода H. Обратите внимание, что эта вероятность намного меньше, чем F.первых x-1 злоумышленников, сделав игрока i фактическим лидером раунда \(\gamma\); или H(Q\(\gamma\)−1, \(\gamma\)), по формуле заставляя B\(\gamma\) = B\(\gamma\) й. В противном случае лидер раунда \(\gamma\) будет первым честным пользователем в перестановке. и Qr-1 становится непредсказуемым для Противника. Какой из вышеперечисленных x вариантов Q\(\gamma\) должен использовать Противник? Чтобы помочь противнику ответьте на этот вопрос, в мысленной игре мы на самом деле делаем его более могущественным, чем он есть на самом деле заключается в следующем. Прежде всего, на самом деле Злоумышленник не может вычислить hash аккаунта честного пользователя. подпись, таким образом, не может определить для каждого Q\(\gamma\) количество x(Q\(\gamma\)) злонамеренных пользователей в начале случайной перестановки в раунде \(\gamma\) + 1, индуцированной Q\(\gamma\). В мысленной игре мы даем ему числа x(Q\(\gamma\)) бесплатно. Во-вторых, на самом деле, если в перестановке есть первые x пользователей, то все злонамеренность не обязательно означает, что их всех можно сделать лидерами, потому что hash значения их сигнатур также должны быть меньше p1. Мы проигнорировали это ограничение в мысленном игре, давая Противнику еще больше преимуществ. Легко видеть, что в мысленной игре оптимальный вариант Противника, обозначаемый ˆQ\(\gamma\), тот, который создает самую длинную последовательность злонамеренных пользователей в начале случайного перестановка в раунде \(\gamma\) + 1. Действительно, при заданном Q\(\gamma\) протокол не зависит от Q\(\gamma\)−1 больше, и Противник может сосредоточиться исключительно на новой перестановке в раунде \(\gamma\) + 1, которая имеет такое же распределение по количеству злоумышленников в начале. Соответственно, в каждом раунде \(\gamma\), упомянутый выше ˆQ\(\gamma\) дает ему наибольшее количество вариантов для Q\(\gamma\)+1 и тем самым максимизирует вероятность того, что все последовательные лидеры являются злонамеренными. Таким образом, в ментальной игре Противник следует Цепи Маркова с раунда r −k. для округления r−1, при этом пространство состояний равно {0} \(\cup\){x : x \(\geq\)2}. Состояние 0 представляет собой тот факт, что первый пользователь в случайной перестановке в текущем раунде \(\gamma\) честен, таким образом, Противник терпит неудачу игра по предсказанию Qr−1; и каждое состояние x \(\geq\)2 представляет собой тот факт, что первые x −1 пользователей в перестановки вредоносны, а x-я честна, таким образом, у Противника есть x вариантов для Q\(\gamma\). вероятности перехода P(x, y) следующие. • P(0, 0) = 1 и P(0, y) = 0 для любого y \(\geq\)2. То есть Противник проигрывает игру, как только первый раз пользователь в перестановке становится честным. • P(x, 0) = hx для любого x \(\geq\)2. То есть с вероятностью hx все случайные перестановки x имеют их первые пользователи честны, поэтому Противник проигрывает игру в следующем раунде. • Для любых x \(\geq\)2 и y \(\geq\)2 P(x, y) — это вероятность того, что среди случайных перестановок x вызванный опциями x Q\(\gamma\), самой длинной последовательностью злонамеренных пользователей в начале некоторые из них равны y−1, поэтому у Противника есть y вариантов для Q\(\gamma\)+1 в следующем раунде. То есть, Р(х, у) = у-1 Х я = 0 (1 −h)ih !х − у-2 Х я = 0 (1 −h)ih !х = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Обратите внимание, что состояние 0 является уникальным поглощающим состоянием в матрице перехода P, а любое другое состояние x имеет положительную вероятность перехода к 0. Нас интересует ограничение сверху числа k раундов, необходимых для того, чтобы цепь Маркова с подавляющей вероятностью сошлась к 0: то есть нет независимо от того, в каком состоянии начинается цепочка, с подавляющей вероятностью Противник проиграет игру и не может предсказать Qr−1 на раунде r−k. Рассмотрим матрицу перехода P (2) \(\triangleq\)P \(\cdot\) P после двух раундов. Легко видеть, что P (2)(0, 0) = 1 и P (2)(0, x) = 0 для любого x \(\geq\)2. Для любых x \(\geq\)2 и y \(\geq\)2, поскольку P(0, y) = 0, имеем P (2)(x, y) = P(x, 0)P(0, y) + Х z\(\geq\)2 P(x, z)P(z, y) = Х z\(\geq\)2 Р(х, z)Р(z, у).Полагая ¯h \(\triangleq\)1 −h, имеем P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x и Р (2)(х, у) = Х z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. Ниже мы вычисляем предел P (2)(x,y) Р (х,у) когда h стремится к 1, то есть ¯h стремится к 0. Обратите внимание, что наивысший порядок ¯h в P(x, y) равен ¯hy−1 с коэффициентом x. Соответственно, Лим ч→1 Р (2)(х, у) Р(х, у) = Лим ¯ч→0 Р (2)(х, у) Р(х, у) = Лим ¯ч→0 Р (2)(х, у) x¯hy−1 + O(¯hy) = Лим ¯ч→0 П z\(\geq\)2[x¯hz−1 + O(¯hz)][z¯hy−1 + O(¯hy)] x¯hy−1 + O(¯hy) = Лим ¯ч→0 2x¯hy + O(¯hy+1) x¯hy−1 + O(¯hy) = Лим ¯ч→0 2x¯hy x¯hy−1 = lim ¯h \(\to\) 0 2¯h = 0. Когда h достаточно близко к 1,23, мы имеем Р (2)(х, у) Р(х, у) \(\leq\)1 2 для любых x \(\geq\)2 и y \(\geq\)2. По индукции для любого k > 2 P (k) \(\triangleq\)P k таково, что • P (k)(0, 0) = 1, P (k)(0, x) = 0 для любого x \(\geq\)2 и • для любых x \(\geq\)2 и y \(\geq\)2, P (k)(x, y) = P (k−1)(x, 0)P(0, y) + Х z\(\geq\)2 P (k−1)(x, z)P(z, y) = Х z\(\geq\)2 P (k−1)(x, z)P(z, y) \(\leq\) Х z\(\geq\)2 Р(х, г) 2k−2 \(\cdot\) P(z, y) = P (2)(x, y) 2k−2 \(\leq\)Р(х, у) 2к-1. Поскольку P(x, y) \(\leq\)1, после 1−log2 F раундов вероятность перехода в любое состояние y \(\geq\)2 пренебрежимо мала, начиная с любого состояния x \(\geq\)2. Хотя таких состояний много, легко видеть, что Лим y→+∞ Р(х, у) Р(х, у + 1) = Лим y→+∞ (1 −¯hy)x −(1 −¯hy−1)x (1 −¯hy+1)x −(1 −¯hy)x = Лим y→+∞ ¯hy−1 −¯hy ¯hy −¯hy+1 = 1 ¯h = 1 1-ч. Поэтому каждая строка x матрицы перехода P убывает как геометрическая последовательность со скоростью 1 1−h > 2 когда y достаточно велико, и то же самое справедливо и для P (k). Соответственно, когда k достаточно велико, но все же порядка log1/2 F, P y\(\geq\)2 P (k)(x, y) < F для любого x \(\geq\)2. То есть с большой вероятностью Противник проигрывает игру и не может предсказать Qr−1 в раунде r −k. Для h \(\in\)(2/3, 1] более комплексный анализ показывает, что существует константа C, немного большая, чем 1/2, такая, что ее достаточно взять k = O(logC F). Таким образом, лемма 5.6 верна. ■ Лемма 5.4. (переформулировано) Учитывая свойства 1–3 для каждого раунда до r, ph = h2(1 + h −h2) для Lr, а лидер \(\ell\)r честен с вероятностью не менее тел. 23Например, h = 80%, как следует из конкретного выбора параметров.

Доказательство. Согласно лемме 5.6, противник не может предсказать Qr-1 обратно в раунде r-k, за исключением случаев, когда ничтожная вероятность. Обратите внимание, что это не означает, что вероятность честного лидера равна h для каждый раунд. Действительно, учитывая Qr-1, в зависимости от того, сколько злоумышленников было в начале случайной перестановки PKr−k, противник может иметь более одного варианта для Qr и таким образом, может увеличить вероятность злонамеренного лидера в раунде r + 1 — мы снова даем ему некоторые нереальные преимущества, как в лемме 5.6, чтобы упростить анализ. Однако для каждого Qr−1, который не был запрошен H противником в раунде r −k, для любой x \(\geq\)1, с вероятностью (1−h)x−1h первый честный пользователь встречается на позиции x в результирующем случайная перестановка PKr−k. При x = 1 вероятность честного лидера в раунде r + 1 равна действительно ч; а когда x = 2, у Противника есть два варианта Qr, и результирующая вероятность равна ч2. Только рассмотрев эти два случая, мы получаем, что вероятность честного лидера в раунде r + 1 равно как минимум h \(\cdot\) h + (1 −h)h \(\cdot\) h2 = h2(1 + h −h2), как и хотелось. Обратите внимание, что приведенная выше вероятность учитывает только случайность в протоколе из раунда r −k. округлить р. Если принять во внимание всю случайность от раунда 0 до раунда r, Qr−1 равен еще менее предсказуем для Противника и вероятность честного лидера в раунде r+1 равна минимум h2(1 + h −h2). Заменив r+1 на r и сдвигая всё назад на один раунд, лидер \(\ell\)r честно с вероятностью не менее h2(1 + h−h2), как и хотелось. Аналогично, на каждом этапе «подлинного подбрасывания монеты» «лидер» этого шага — то есть проверяющий. в SV r,s, чьи учетные данные имеют наименьшее значение hash, честны с вероятностью не менее h2(1 + ч − h2). Таким образом, ph = h2(1 + h −h2) для Lr и лемма 5.4 выполнена. ■

Algorand ′

2 В этом разделе мы создадим версию Algorand ′, работающую при следующем предположении. Допущение о честном большинстве пользователей: более 2/3 пользователей в каждом PKr честны. В разделе 8 мы покажем, как заменить приведенное выше предположение желаемым «Честным большинством». Денежное предположение. 6.1 Дополнительные обозначения и параметры для Algorand ′ 2 Обозначения • \(\mu\) \(\in\)Z+: прагматическая верхняя граница числа шагов, которые с подавляющей вероятностью фактически будет принято за один раунд. (Как мы увидим, параметр \(\mu\) контролирует количество эфемерных ключи, которые пользователь готовит заранее для каждого раунда.) • Lr: случайная величина, представляющая количество испытаний Бернулли, необходимых для получения 1, когда каждое испытание равно 1 с вероятностью ph 2 . Lr будет использоваться для верхней границы времени, необходимого для генерации блок Бр. • tH: нижняя граница числа честных проверяющих на этапе s > 1 раунда r, такая, что при с подавляющей вероятностью (при n и p), в SV r,s имеется > tH честных проверяющих. Параметры • Отношения между различными параметрами. — Для каждого шага s > 1 раунда r n выбирается так, чтобы с подавляющей вероятностью

|HSV r,s| > ТХ и |HSV r,s| + 2|МСВ г,с| < 2tH. Обратите внимание, что из двух приведенных выше неравенств вместе следует |HSV r,s| > 2|MSV r,s|: т.е. составляет 2/3 честного большинства среди выбранных проверяющих. Чем ближе к 1 значение h, тем меньше должно быть n. В частности, мы используем (варианты из) границ Чернова, обеспечивающих выполнение желаемых условий с подавляющей вероятностью. • Пример выбора важных параметров. — F = 10−18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Реализация эфемерных ключей в Algorand ′ 2 Напомним, что верификатор i \(\in\)SV r,s подписывает свое сообщение mr,s цифровой подписью. я шага s в раунде r относительно эфемерный открытый ключ pkr,s i, используя эфемерный секретный ключ skr,s я что он тут же уничтожает после использования. Когда количество возможных шагов, которые может сделать раунд, ограничено заданным целое число \(\mu\), мы уже видели, как практически обрабатывать эфемерные ключи. Например, как мы объяснили в Algorand ′ 1 (где \(\mu\) = m + 3), чтобы обрабатывать все возможные эфемерные ключи, начиная с от раунда r' до раунда r' + 106, я генерирует пару (PMK, SMK), где публичный мастер PMK ключ схемы подписи на основе идентичности, а SMK — соответствующий секретный главный ключ. Пользователь я публикует PMK и использует SMK для генерации секретного ключа каждого возможного эфемерного открытого ключа (и после этого уничтожает SMK). Набор эфемерных открытых ключей i для соответствующих раундов составляет S = {i} \(\times\) {r′, . . . , r′ + 106} \(\times\) {1, . . . , \(\mu\)}. (Как уже говорилось, по мере приближения раунда r' + 106 «обновляю» его пару (ПМК, СМК).) На практике, если \(\mu\) достаточно велико, раунд Algorand ′ 2 не займет более \(\mu\) шагов. В Однако в принципе существует отдаленная вероятность того, что для некоторого раунда r число шагов фактически принятое значение будет превышать \(\mu\). Когда это произойдет, я не смогу подписать его сообщение, мистер С. я для любой шаг s > \(\mu\), поскольку он заранее подготовил только \(\mu\) секретных ключей для раунда r. Более того, он не смог подготовить и опубликовать новый запас эфемерных ключей, как обсуждалось ранее. На самом деле, чтобы сделать поэтому ему нужно будет вставить новый открытый главный ключ PMK' в новый блок. Но если вокруг r делать все больше и больше шагов, новые блоки не будут генерироваться. Однако решения существуют. Например, я могу использовать последний эфемерный ключ раунда r, pkr,\(\mu\) я , следующим образом. Он генерирует еще один запас пар ключей для раунда r — например, с помощью (1) создания еще одного пара мастер-ключей (ПМК, СМК); (2) использование этой пары для генерации еще, скажем, 106 эфемерных ключей, ск г, \(\mu\)+1 я , . . . , ск г, \(\mu\)+106 я , соответствующий шагам \(\mu\)+1, ..., \(\mu\)+106 раунда r; (3) используя skr,\(\mu\) я в цифровом формате подпишите PMK (и любое (r, \(\mu\))-сообщение, если i \(\in\)SV r,\(\mu\)) относительно pkr,\(\mu\) я ; и (4) стирание SMK и skr,\(\mu\) я . Должен ли я стать проверяющим на шаге \(\mu\) + s с s \(\in\) {1, . . . , 106}, то я подписываю его цифровую подпись (r, \(\mu\) + s)- сообщение г-н,\(\mu\)+s я относительно его нового ключа ПК r,\(\mu\)+s я = (i, r, \(\mu\) + s). Разумеется, для проверки этой подписи из i другие должны быть уверены, что этот открытый ключ соответствует новому открытому главному ключу PMK i. Таким образом, в дополнение к этой подписи i передает свою цифровую подпись ПМК относительно pkr,\(\mu\) я . Конечно, этот подход можно повторять столько раз, сколько необходимо, если раунд r продолжится. для все большего и большего количества шагов! Последний эфемерный секретный ключ используется для аутентификации нового главного публичного ключа. ключ и, таким образом, еще один запас эфемерных ключей для раунда r. И так далее.6.3 Фактический протокол Algorand ′ 2 Напомним еще раз, что на каждом шаге s раунда r проверяющий i \(\in\)SV r,s использует свою долгосрочную общедоступную тайну. пара ключей для получения его учетных данных, \(\sigma\)r,s я \(\triangleq\)SIGi(r, s, Qr−1), а также SIGi Qr−1 в случае s = 1. Верификатор i использует свою пару эфемерных ключей (pkr,s я, скр,с i ), чтобы подписать любое другое сообщение m, которое может быть требуется. Для простоты будем писать esigi(m), а не sigpkr,s. i (m), чтобы обозначить собственное эфемерное значение i подпись m на этом этапе и напишите ESIGi(m) вместо SIGpkr,s i (m) \(\triangleq\) (i, m, esigi(m)). Шаг 1. Блокируйте предложение Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный шаг 1 раунда r, как только он CERT r−1, который позволяет i однозначно вычислить H(Br−1) и Qr−1. • Пользователь i использует Qr-1, чтобы проверить, принадлежит ли i SV r,1 или нет. Если i /\(\varepsilon\)SV r,1, он ничего не делает на шаге 1. • Если i \(\in\)SV r,1, то есть если я потенциальный лидер, то он делает следующее. (a) Если я увидел B0, . . . , сам Br−1 (любой Bj = Bj ǫ можно легко получить из его значения hash в CERT j и, таким образом, считается «просмотренным»), то он получает платежи раунда r, которые было передано ему на данный момент и вычисляет максимальный набор выплат PAY r я от них. (b) Если я не видел все B0, . . . , Br−1, то он устанавливает PAY r я = \(\emptyset\). (c) Далее я вычисляю его «блок кандидатов» Br i = (r, PAY r i , SIGi(Qr−1), H(Br−1)). (c) Наконец, я вычисляю сообщение mr,1 я = (Бр i , esigi(H(Br i ))), \(\sigma\)r,1 я), уничтожает его эфемерное секретный ключ скр,1 i , а затем распространяет два сообщения, mr,1 я и (SIGi(Qr−1), \(\sigma\)r,1 я), отдельно, но одновременно. aКогда i является лидером, SIGi(Qr-1) позволяет другим вычислить Qr = H(SIGi(Qr-1), r).

Выборочное распространение Чтобы сократить глобальное выполнение шага 1 и всего раунда, важно, чтобы (r, 1)- сообщения распространяются выборочно. То есть для каждого пользователя j в системе • Для первого (r, 1)-сообщения, которое он когда-либо получает и успешно проверяет, содержит ли оно блок или является просто учетными данными и подписью Qr-1, игрок j распространяет его как обычно. • Для всех остальных (r, 1)-сообщений, которые игрок j получает и успешно проверяет, он распространяет это только в том случае, если значение hash содержащихся в нем учетных данных является наименьшим среди значений hash учетных данных, содержащихся во всех (r, 1)-сообщениях, которые он получил и успешно проверил, далеко. • Однако, если j получает два разных сообщения вида mr,1 я от того же игрока я,б он отбрасывает второй независимо от значения hash учетных данных i. Обратите внимание, что при избирательном распространении полезно, чтобы каждый потенциальный лидер i распространял свой учетные данные \(\sigma\)r,1 я отдельно от мистера 1 i :c эти маленькие сообщения передаются быстрее, чем блоки, убедитесь, что своевременное распространение г-на,1 Здесь содержащиеся учетные данные имеют небольшие значения hash, а заставьте те, у кого большие значения hash, быстро исчезнуть. aТо есть все подписи верны и, если она имеет вид mr,1 i, и блок, и его hash действительны — хотя j не проверяет, является ли включенный набор выплат максимальным для i или нет. bЭто означает, что я злонамерен. cМы благодарим Георгиоса Влахоса за это предложение.Шаг 2: Первый шаг Протокола поэтапного консенсуса GC Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный шаг 2 раунда r, как только он CERT r-1. • Пользователь i ожидает максимальное время t2 \(\triangleq\) \(\lambda\) + Λ. Во время ожидания я действую следующим образом. 1. Подождав время 2\(\lambda\), он находит пользователя \(\ell\) такого, что H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 к) для всех учетные данные \(\sigma\)r,1 дж которые являются частью успешно проверенных (r, 1)-сообщений, которые он получил пока.а 2. Если он имеет получил а блокировать Бр−1, который спички тот hash ценность Н(Бр-1) содержится в CERT r-1,b, и если он получил от \(\ell\) действительное сообщение mr,1 \(\ell\) = (Бр \(\ell\), esig\(\ell\)(H(Br \(\ell\))) \(\sigma\)r,1 \(\ell\)),c, то я перестаю ждать и устанавливаю v′ я \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. В противном случае, когда время t2 истечет, я устанавливаю v' я \(\triangleq\) \(\bot\). 4. Когда значение v' i был установлен, я вычисляет Qr-1 из CERT r-1 и проверяет, i \(\in\)SV r,2 или нет. 5. Если i \(\in\)SV r,2, i вычисляет сообщение mr,2 я \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 я ),д уничтожает его эфемерное секретный ключ скр,2 i , а затем распространяет mr,2 я. В противном случае я останавливаюсь, не распространяя что угодно. aПо сути, пользователь i в частном порядке решает, что лидером раунда r является пользователь \(\ell\). bКонечно, если CERT r−1 указывает, что Br−1 = Br−1 ψ , то я уже «получил» Br−1 в тот момент, когда он CERT r-1. cОпять же, подписи игрока \(\ell\) и hash успешно проверены, и PAY r \(\ell\)в Бр \(\ell\)действителен для round r — хотя я не проверяю, PAY ли r \(\ell\)максимальен для \(\ell\)или нет. Если Бр \(\ell\)содержит пустой набор выплат, тогда на самом деле мне нет необходимости видеть Br−1, прежде чем проверять, является ли Br \(\ell\)действителен или нет. d Сообщение мистера, 2 я сигнализирует о том, что игрок i рассматривает первый компонент v' i быть hash следующего блока, или считает следующий блок пустым.

Шаг 3: Второй шаг GC Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный Шаг 3 раунда r, как только он CERT r-1. • Пользователь i ожидает максимальное время t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. Во время ожидания я действую как следует. 1. Если существует значение v такое, что он получил как минимум tH действительных сообщений mr,2 дж из вид (ESIGj(v), \(\sigma\)r,2 j ), без всякого противоречия,a тогда он перестает ждать и устанавливает v' = v. 2. В противном случае, когда время t3 истечет, он установит v′ = \(\bot\). 3. Когда значение v' установлено, я вычисляет Qr-1 из CERT r-1 и проверяет, i \(\in\)SV r,3 или нет. 4. Если i \(\in\)SV r,3, то я вычисляет сообщение mr,3 я \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 я), уничтожает его эфемерный секретный ключ skr,3 i , а затем распространяет mr,3 я. В противном случае я остановлюсь без пропагандируя что-либо. aТо есть он не получил двух действительных сообщений, содержащих ESIGj(v) и другой ESIGj(ˆv) соответственно, от игрока j. Здесь и далее, за исключением Конечных условий, определенных позже, всякий раз, когда честный игрок хочет сообщений заданной формы, сообщения, противоречащие друг другу, никогда не учитываются и не считаются действительными.

Шаг 4: Выходные данные GC и первый шаг BBA⋆ Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свой собственный Шаг 4 раунда r, как только он завершает свой Шаг 3. • Пользователь i ожидает максимальное время 2\(\lambda\).a. Во время ожидания я действует следующим образом. 1. Он вычисляет vi и gi, выходные данные GC, следующим образом. (a) Если существует значение v′ ̸= \(\bot\) такое, что он получил как минимум tH действительных сообщений мистер, 3 дж = (ESIGj(v′), \(\sigma\)r,3 j ), затем он перестает ждать и устанавливает vi \(\triangleq\)v′ и gi \(\triangleq\)2. (b) Если он получил хотя бы tH действительных сообщений mr,3 дж = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), затем он останавливается ждет и устанавливает vi \(\triangleq\) \(\bot\) и gi \(\triangleq\)0.b (c) В противном случае, когда время 2\(\lambda\) истечет, если существует значение v′ ̸= \(\bot\) такое, что он имеет получил не менее ⌈tH 2 ⌉действительные сообщения mr,j дж = (ESIGj(v′), \(\sigma\)r,3 j ), то он устанавливает vi \(\triangleq\)v′ и gi \(\triangleq\)1.c (d) В противном случае, когда время 2\(\lambda\) истечет, он установит vi \(\triangleq\) \(\bot\) и gi \(\triangleq\)0. 2. Когда значения vi и gi установлены, я вычисляет bi, вход BBA⋆, следующим образом: bi \(\triangleq\)0, если gi = 2, и bi \(\triangleq\)1 в противном случае. 3. i вычисляет Qr−1 из CERT r−1 и проверяет, принадлежит ли i SV r,4 или нет. 4. Если i \(\in\)SV r,4, он вычисляет сообщение mr,4 я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 я), уничтожает его эфемерный секретный ключ skr,4 i и распространяет mr,4 я. В противном случае я останавливаюсь, не распространяя что угодно. aТаким образом, максимальное общее количество времени с момента начала первого шага раунда r может составлять t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ. bОтсутствие шага (b) в протоколе не влияет на его правильность. Однако наличие этапа (b) позволяет шагу 4 завершиться менее чем за 2\(\lambda\), если достаточное количество верификаторов шага 3 имеют «подпись \(\bot\)». cМожно доказать, что v′ в этом случае, если он существует, должен быть единственным.Шаг s, 5 \(\leq\)s \(\leq\)m + 2, s−2 ≡0 mod 3: шаг BBA⋆ с фиксированной монетой до 0 Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он завершает свой шаг s−1. • Пользователь i ожидает максимальное время 2\(\lambda\).a. Во время ожидания я действует следующим образом. – Конечное условие 0: если в любой точке существует строка v ̸= \(\bot\) и шаг s′ такие, что (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 — то есть шаг s′ является шагом с фиксированной монетой до 0, (b) я получил как минимум tH действительных сообщений mr,s′−1 дж = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 дж ),б и (c) я получил действительное сообщение (SIGj(Qr-1), \(\sigma\)r,1 j), где j является вторым компонент v, затем я перестаю ждать и заканчиваю выполнение шага s (и фактически раунда r) сразу, ничего не выдавая в качестве (r,s)-верификатора; устанавливает H(Br) в качестве первого компонент v; и устанавливает свой собственный CERT r как набор сообщений mr,s′−1 дж шага (б) вместе с (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Конечное условие 1: Если в какой-либо точке существует шаг s′ такой, что (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 — то есть шаг s′ является шагом с фиксированной монетой-1, и (b’) я получил как минимум tH действительных сообщений mr,s′−1 дж = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 дж ),д затем я перестаю ждать и заканчиваю выполнение шага s (и фактически раунда r) правильно прочь, не распространяя ничего в качестве (r, s)-верификатора; устанавливает Br = Br й; и устанавливает свой собственный CERT r — набор сообщений mr,s′−1 дж подэтапа (b’). – Если в любой точка он имеет получил в минимум тХ действительный мистер, с-1 дж х из тот форма (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он перестает ждать и устанавливает bi \(\triangleq\)1. – Если в любой точка он имеет получил в минимум тХ действительный мистер, с-1 дж х из тот форма (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), но они не соглашаются на одно и то же v, тогда он останавливается ждет и устанавливает bi \(\triangleq\)0. – В противном случае, когда время 2\(\lambda\) истечет, я устанавливаю bi \(\triangleq\)0. – Когда значение bi установлено, i вычисляет Qr-1 из CERT r-1 и проверяет, i \(\in\)SV r,s. – Если i \(\in\)SV r,s, i вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) с vi, являющимся значение, которое он вычислил на шаге 4, уничтожает его эфемерный секретный ключ skr,s я, а потом пропагандирует мистера, с я. В противном случае я останавливаюсь, ничего не распространяя. aТаким образом, максимальное общее количество времени с момента начала первого шага раунда r может составлять ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s−3)\(\lambda\) + Λ. bТакое сообщение от игрока j засчитывается, даже если игрок i также получил сообщение от j, подписавшегося за 1. Аналогично для конечного условия 1. Как показано в анализе, это сделано для того, чтобы все честные пользователи знали CERT r в пределах времени \(\lambda\) друг от друга. cПользователь i теперь знает H(Br) и результаты своего раунда r. Ему просто нужно дождаться, пока собственно блок Br не будет передается ему, что может занять некоторое дополнительное время. Он по-прежнему помогает распространять сообщения как обычный пользователь. но не инициирует никакого распространения в качестве (r, s)-верификатора. В частности, он помогал распространять все сообщения в его CERT r, которого достаточно для нашего протокола. Обратите внимание, что ему также следует установить bi \(\triangleq\)0 для бинарного протокола BA, но bi в этом случае в любом случае не нужен. Аналогичные вещи для всех будущих инструкций. dВ этом случае не имеет значения, кто такие виджеи. 65Шаг s, 6 \(\leq\)s \(\leq\)m + 2, s−2 ≡1 mod 3: шаг BBA⋆ с фиксированной монетой-1 Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он завершает свой шаг s−1. • Пользователь i ожидает максимальное время 2\(\lambda\). Во время ожидания я действую следующим образом. – Конечное условие 0: те же инструкции, что и на этапе Coin-Fixed-To-0. – Конечное условие 1: те же инструкции, что и на этапе Coin-Fixed-To-0. – Если в любой точка он имеет получил в минимум тХ действительный мистер, с-1 дж х из тот форма (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), затем он перестает ждать и устанавливает bi \(\triangleq\)0.a – В противном случае, когда время 2\(\lambda\) истечет, я устанавливаю bi \(\triangleq\)1. – Когда значение bi установлено, i вычисляет Qr-1 из CERT r-1 и проверяет, i \(\in\)SV r,s. – Если i \(\in\)SV r,s, i вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) с vi, являющимся значение, которое он вычислил на шаге 4, уничтожает его эфемерный секретный ключ skr,s я, а потом пропагандирует мистера, с я. В противном случае я останавливаюсь, ничего не распространяя. aОбратите внимание, что получение tH действительных (r, s −1)-сообщений, подписанных за 1, будет означать конечное условие 1. Шаг s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Шаг BBA⋆ с подбрасыванием монеты Инструкции для каждого пользователя i \(\in\)PKr−k: Пользователь i начинает свои собственные шаги раунда r, как только он завершает свой шаг s−1. • Пользователь i ожидает максимальное время 2\(\lambda\). Во время ожидания я действую следующим образом. – Конечное условие 0: те же инструкции, что и на этапе Coin-Fixed-To-0. – Конечное условие 1: те же инструкции, что и на этапе Coin-Fixed-To-0. – Если в любой точка он имеет получил в минимум тХ действительный мистер, с-1 дж х из тот форма (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он перестает ждать и устанавливает bi \(\triangleq\)0. – Если в любой точка он имеет получил в минимум тХ действительный мистер, с-1 дж х из тот форма (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 дж ), то он перестает ждать и устанавливает bi \(\triangleq\)1. – В противном случае, когда время 2\(\lambda\) истечет, позволяя SV r,s−1 я — множество (r, s−1)-верификаторов из которому он получил действительное сообщение mr,s−1 дж , я устанавливаю bi \(\triangleq\)lsb(minj\(\varepsilon\)SV r,s−1 я H(\(\sigma\)r,s−1 дж )). – Когда значение bi установлено, i вычисляет Qr-1 из CERT r-1 и проверяет, i \(\in\)SV r,s. – Если i \(\in\)SV r,s, i вычисляет сообщение mr,s я \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) с vi, являющимся значение, которое он вычислил на шаге 4, уничтожает его эфемерный секретный ключ skr,s я, а потом пропагандирует мистера, с я. В противном случае я останавливаюсь, ничего не распространяя. Замечание. В принципе, как указано в подразделе 6.2, протокол может занимать сколь угодно много шаги в каком-то раунде. Если это произойдет, как обсуждалось, пользователь i \(\in\)SV r,s с s > \(\mu\) исчерпал

его запас заранее сгенерированных эфемерных ключей и должен подтвердить подлинность своего (r, s)-сообщения mr,s я по «каскад» эфемерных ключей. Таким образом, мое сообщение становится немного длиннее, и его передача длиннее. сообщения займут немного больше времени. Соответственно, после стольких шагов данного раунда значение параметр \(\lambda\) автоматически немного увеличится. (Но он возвращается к исходному \(\lambda\) при каждом новом блок создается и начинается новый раунд.) Реконструкция блока Round-r неверификаторами Инструкции для каждого пользователя i в системе: Пользователь i начинает свой собственный раунд r, как только он CERT r-1. • я следую инструкциям каждого шага протокола, участвует в распространении всех сообщений, но не инициирует никакого распространения на шаге, если он не является на нем проверяющим. • я заканчиваю свой раунд r, введя либо Конечное условие 0, либо Конечное условие 1 в каком-либо шаг, с соответствующим CERT r. • С этого момента он начинает свой раунд r + 1, ожидая получения фактического блока Br (если только он уже получил его), чей hash H(Br) был зафиксирован CERT r. Опять же, если CERT r указывает, что Br = Br ϫ, я узнает Бр в тот момент, когда у него есть CERT r. 6.4 Анализ Algorand ′ 2 Анализ Algorand ′ 2 легко получить из Algorand ′ 1. По сути, в Algorand ′ 2, с подавляющая вероятность, (а) все честные пользователи согласны на один и тот же блок Br; лидер нового блок честен с вероятностью не менее ph = h2(1 + h −h2).

Обращение с честными пользователями в режиме оффлайн

Как мы уже говорили, честный пользователь следует всем предписанным ему инструкциям, в том числе и по нахождению в сети. и запускаем протокол. Это не является большой нагрузкой в Algorand, поскольку вычисления и Требуемая пропускная способность от честного пользователя весьма скромна. Тем не менее, отметим, что Algorand может легко модифицировать для работы в двух моделях, в которых честным пользователям разрешено находиться в автономном режиме отличные цифры. Прежде чем обсуждать эти две модели, отметим, что если процент честных игроков составляли 95 %, Algorand все равно можно было запустить, задав все параметры, предполагая, что вместо этого h = 80 %. Соответственно, Algorand продолжит работать корректно, даже если не более половины честных игроков решил уйти в офлайн (действительно, это серьезный случай «прогулов»). Фактически, в любой момент времени, по крайней мере, 80% игроков онлайн будут честными. От постоянного участия к ленивой честности Как мы видели, Algorand ′ 1 и Algorand ′ 2 выбрать параметр ретроспективного просмотра k. Покажем теперь, что выбор k должным образом большим позволяет удалить требование постоянного участия. Это требование обеспечивает важнейшее свойство: а именно: что базовый протокол BA BBA⋆ имеет надлежащее честное большинство. Давайте теперь объясним, насколько ленивы честность обеспечивает альтернативный и привлекательный способ удовлетворить это свойство.

Напомним, что пользователь i является ленивым, но честным, если (1) он следует всем предписанным инструкциям, когда его просят участвовать в протоколе, и (2) его просят участвовать только в протоколе очень редко — например, раз в неделю — с соответствующим предварительным уведомлением и потенциально получая значительные награды, когда он участвует. Чтобы Algorand мог работать с такими плеерами, достаточно «выбрать верификаторы текущий раунд среди пользователей, уже находящихся в системе в гораздо более раннем раунде». Действительно, напомним, что проверяющие для раунда r выбираются из пользователей в раунде r -k, и выбор делается на основе от величины Qr−1. Обратите внимание, что неделя состоит примерно из 10 000 минут, и предположим, что раунд занимает примерно (например, в среднем) 5 минут, поэтому в неделе около 2000 раундов. Предположим что в какой-то момент пользователь хочет спланировать свое время и знать, будет ли он проверяющий на следующей неделе. Протокол теперь выбирает проверяющих для раунда r из пользователей в раунд r-k-2000, а выбор основан на Qr-2001. В раунде R игрок, которого я уже знаю значения Qr−2000, . . . , Qr-1, поскольку они фактически являются частью blockchain. Тогда для каждого М между 1 и 2000, i является проверяющим на шаге s раунда r + M тогда и только тогда, когда .Х СИГи г + М, с, Qr+M−2,001 \(\leq\)р. Таким образом, чтобы проверить, будет ли он вызван для выполнения функций проверяющего в следующих 2000 раундах, я должен вычислить \(\sigma\)M,s я = СИГи г + М, с, Qr+M−2,001 для M = от 1 до 2000 и для каждого шага s и проверьте является ли .H(\(\sigma\)M,s я ) \(\leq\)p для некоторых из них. Если вычисление цифровой подписи занимает миллисекунду, то вся эта операция займет у него около 1 минуты вычислений. Если он не выбран в качестве проверяющего в любом из этих раундов он может выйти из игры с «чистой совестью». Если бы он постоянно участвовал, то в любом случае он, по сути, сделал бы 0 шагов в следующих 2000 раундах! Если вместо этого его выбирают в качестве проверяющего в одном из этих раундов, затем он готовится (например, получая все необходимую информацию), чтобы выступать в качестве честного проверяющего на соответствующем раунде. Действуя таким образом, ленивый, но честный потенциальный проверяющий только упускает возможность участвовать в распространении информации. сообщений. Но распространение сообщений обычно является надежным. При этом плательщики и получатели ожидается, что недавно распространенные платежи будут онлайн, чтобы наблюдать, что происходит с их платежами, и, таким образом, они будут участвовать в распространении сообщений, если они честны.

Протокол Algorand ′ с честным большинством денег

Теперь мы, наконец, покажем, как заменить предположение о честном большинстве пользователей гораздо более значимое предположение о честном большинстве денег. Основная идея такова (в варианте proof-of-stake) «выбрать пользователя i \(\in\)PKr−k, принадлежащего SV r,s, с весом (т. е. способностью решения), пропорциональным количество денег, принадлежащих i»24. Согласно нашему предположению HMM, мы можем выбрать, будет ли эта сумма принадлежать в раунде r -k. или в (начале) раунда r. Предполагая, что мы не против постоянного участия, мы выбираем последний выбор. (Чтобы исключить постоянное участие, мы бы выбрали первый вариант. Проще говоря, для суммы денег, имевшейся в раунде r −k −2 000.) Есть много способов реализовать эту идею. Самый простой способ - удержать каждую клавишу не более 1 денежной единицы, а затем случайным образом выберите n пользователей i из PKr−k таких, что a(r) я = 1. 24Мы должны сказать PKr-k-2000, чтобы заменить постоянное участие. Для простоты, поскольку можно пожелать потребовать В любом случае постоянное участие мы используем PKr-k, как и раньше, чтобы нести на один параметр меньше.

Следующая простейшая реализация Следующей простейшей реализацией может быть требование, чтобы каждый открытый ключ владел максимальным количеством ключей. денег М при некоторой фиксированной величине М. Стоимость М достаточно мала по сравнению с общей суммой денег М. денег в системе, так что вероятность того, что ключ принадлежит набору проверяющих, состоящему из более чем одного шаг за, скажем, k раундов пренебрежимо мал. Тогда ключ i \(\in\)PKr−k, владеющий суммой денег a(r) я в раунде r выбирается принадлежащим SV r,s, если .Х СИГи г, с, Qr−1 \(\leq\)p \(\cdot\) а(г) я М . И все идет по-прежнему. Более сложная реализация Последняя реализация «заставила богатого участника системы владеть множеством ключей». Альтернативная реализация, описанная ниже, обобщает понятие статуса и рассматривает каждый пользователь i должен состоять из K + 1 копий (i, v), каждая из которых независимо выбирается в качестве проверяющего, и будет владеть собственным эфемерным ключом (pkr,s я,в,скр,с i,v) на шаге s раунда r. Значение K зависит от суммы денег a(r) я принадлежит мне в раунде r. Давайте теперь посмотрим, как работает такая система более подробно. Количество копий Пусть n — целевая ожидаемая мощность каждого набора проверяющих, и пусть a(r) я быть суммой денег, принадлежащей пользователю i в раунде r. Пусть Ar — общая сумма денег, принадлежащих пользователями в PKr−k в раунде r, то есть Ар = Х i\(\varepsilon\)P Кр−k а (р) я. Если я — пользователь в PKr-k, то его копиями будут (i, 1), . . . , (i, K + 1), где К = $ п \(\cdot\) а(г) я Ар % . Пример. Пусть n = 1000, Ar = 109 и a(r) я = 3,7 миллиона. Тогда, К = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3,7⌋= 3 . Подтверждающие лица и учетные данные Пусть я пользователь в PKr−k с K + 1 копией. Для каждого v = 1, . . . , K, копия (i, v) автоматически принадлежит SV r,s. То есть мои учетные данные \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), но соответствующее условие принимает вид .H(\(\sigma\)r,s i,v) \(\leq\)1, что всегда правда. Для копии (i, K + 1) для каждого шага s раунда r я проверяю, .Х СИГи (i, K + 1), r, s, Qr−1 \(\leq\)а(г) я н Ар-К.

Если да, то копия (i, K + 1) принадлежит SV r,s. Чтобы доказать это, я распространяю учетные данные \(\sigma\)р,1 i,K+1 = SIGi (i, K + 1), r, s, Qr−1 . Пример. Как и в предыдущем примере, пусть n = 1K, a(r) я = 3,7M, Ar = 1B, а у меня 4 копии: (i, 1), . . . , (я, 4). Тогда первые три копии автоматически принадлежат SV r,s. Для 4-го, концептуально Algorand ′ независимо бросает смещенную монету, вероятность выпадения орла которой равна 0,7. Копировать (i, 4) выбирается тогда и только тогда, когда монета подбрасывается орлом. (Конечно, это предвзятое подбрасывание монеты реализуется путем hash подписания, подписи и сравнения — поскольку мы все это сделал в этой статье, чтобы иметь возможность доказать свой результат.) Бизнес как обычно Объяснив, как отбираются проверяющие и как проверяются их полномочия вычисляется на каждом шаге раунда r, выполнение раунда аналогично уже объясненному.

Обработка форков

Уменьшив вероятность вилок до 10−12 или 10−18, обрабатывать их в малой вероятности того, что они произойдут. Однако Algorand также может использовать различные вилки. процедуры урегулирования, с подтверждением работы или без него. Один из возможных способов проинструктировать пользователей о разрешении вилок заключается в следующем: • Следуйте самой длинной цепочке, если пользователь видит несколько цепочек. • Если существует более одной самой длинной цепочки, следует следовать той, у которой в конце есть непустой блок. Если все они имеют пустые блоки в конце, считайте их предпоследними блоками. • Если существует более одной самой длинной цепочки с непустыми блоками на конце, скажем, что цепочки длины r, следуйте за тем, чей лидер блока r имеет наименьшие полномочия. Если есть связи, следовать за тем, чей блок r имеет наименьшее значение hash. Если связи еще остались, следуйте тот, чей блок r лексикографически упорядочен первым.

Обработка сетевых разделов

Как уже говорилось, мы предполагаем, что время распространения сообщений среди всех пользователей в сети ограничено сверху значениями \(\lambda\) и Λ. Это не слишком сильное предположение, поскольку современный Интернет является быстрым и надежным, и фактические значения этих параметров вполне разумны. Здесь отметим, что Algorand ′ 2 продолжает работать, даже если Интернет иногда разделяется на две части. Тот случай, когда Интернет разделен более чем на две части аналогично. 10.1 Физические разделы Прежде всего, перегородка может быть вызвана физическими причинами. Например, сильное землетрясение может в конечном итоге полностью разорвёт связь между Европой и Америкой. В этом случае злонамеренные пользователи также разделены, и между двумя частями нет связи. Таким образом

будет два Противника: один для части 1, другой для части 2. Каждый Противник по-прежнему пытается нарушить протокол в своей части. Предположим, что раздел происходит в середине раунда r. Тогда каждый пользователь по-прежнему выбирается в качестве верификатор на основе PKr−k с той же вероятностью, что и раньше. Пусть HSV r,s я и MSV r,s я соответственно — множество честных и злонамеренных проверяющих на шаге s в части i \(\in\) {1, 2}. У нас есть |HSV r,s 1 | + |MSV r,s 1 | + |HSV r,s 2 | + |MSV r,s 2 | = |HSV r,s| + |MSV r,s|. Обратите внимание, что |HSV r,s| + |MSV r,s| < |HSV r,s| + 2|МСВ г,с| < 2tH с подавляющей вероятностью. Если какая-то часть i имеет |HSV r,s я | + |MSV r,s я | \(\geq\)tH с немалой вероятностью, например, 1%, то вероятность того, что |HSV r,s 3−i| + |MSV r,s 3−i| \(\geq\)tH очень низкое, например, 10–16, когда F = 10–18. В этом случае мы можем с таким же успехом рассматривать меньшую часть как отключенную, потому что в ней не будет достаточного количества верификаторов. эта часть предназначена для генерации подписей для сертификации блока. Рассмотрим большую часть, скажем, часть 1, не ограничивая общности. Хотя |HSV r,s| < tH с пренебрежимо малой вероятностью на каждом шаге s, когда сеть разделена, |HSV r,s 1 | может быть меньше, чем tH с некоторой немалой вероятностью. В этом случае Противник может с некоторым другая, немалая вероятность, приведет к разветвлению двоичного протокола BA в раунде r с непустым блоком Br и пустым блоком Br. ƫ оба имеют действительные подписи.25 Например, в Шаги Coin-Fixed-To-0 s, все верификаторы в HSV r,s 1 подписались для бита 0 и H(Br) и распространили их сообщения. Все верификаторы в MSV r,s 1 также подписали 0 и H(Br), но свои сообщения воздержали. Потому что |HSV r,s 1 | + |MSV r,s 1 | \(\geq\)tH, в системе достаточно подписей для сертификации Br. Однако, поскольку злонамеренные верификаторы скрыли свои подписи, пользователи вводят шаг s + 1, который является шагом Coin-Fixed-To1. Поскольку |HSV r,s 1 | < tH из-за разделения, верификаторы в HSV r,s+1 1 не видел этого подписи для бита 0, и все они подписаны для бита 1. Все верификаторы в MSV r,s+1 1 сделал то же самое. Потому что |HSV r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH, в системе достаточно подписей для сертификации Br й. Противник затем создает форк, освобождая подписи MSV r,s 1 для 0 и H(Br). Соответственно, будет два Qr, определяемых соответствующими блоками раунда r. Однако, вилка не будет продолжаться, и в раунде r + 1 может вырасти только одна из двух ветвей. Дополнительные инструкции для Algorand ′ 2. При виде непустого блока Br и пустого блок Бр ϫ , следует за непустым номером (и определяемым им Qr). Действительно, поручив пользователям использовать непустой блок в протоколе, если большой количество честных пользователей в PKr+1−k понимают, что в начале раунда r +1 происходит разветвление, тогда у пустого блока не будет достаточно подписчиков, и он не будет расти. Предположим, что противнику удастся разделите честных пользователей так, чтобы некоторые честные пользователи видели Br (и, возможно, Br ǫ), а некоторые видят только Бр й. Потому что Противник не может сказать, какой из них будет проверяющим после Br, а какой будет проверяющим после Br ϫ, честные пользователи распределяются случайным образом, и каждый из них по-прежнему становится проверяющим (либо по отношению к Br, либо по отношению к Br ϫ) на шаге s > 1 с вероятностью п. У злоумышленников каждый из них может иметь два шанса стать проверяющим, один с Бр и другой с Бр ϫ, каждый с вероятностью p независимо. Пусть HSV r+1,s 1;Бр — множество честных проверяющих на шагах s раунда r+1 после Br. Другие обозначения например HSV r+1,s 1;Br , MSV r+1,s 1;Бр и MSV r+1,s 1; Брю определяются аналогично. По Чернову легко 25Иметь вилку с двумя непустыми блоками невозможно ни с перегородками, ни без них, кроме как с пренебрежимо малыми вероятность.увидеть это с подавляющей вероятностью, |HSV r+1,s 1;Бр | + |HSV r+1,s 1;Бру | + |MSV r+1,s 1;Бр | + |MSV r+1,s 1;Бру | < 2tH. Соответственно, две ветви не могут обе иметь правильные подписи, удостоверяющие блок для раунда. r + 1 на том же шаге s. Более того, поскольку вероятности выбора для двух шагов s и s′ равны то же самое, и выборы независимы, также с подавляющей вероятностью |HSV r+1,s 1;Бр | + |MSV r+1,s 1;Бр | + |HSV r+1,s' 1; Брю | + |MSV r+1,s' 1; Брю | < 2tH, для любых двух шагов s и s'. Когда F = 10−18, по объединению, пока Противник не может разделять честных пользователей на длительное время (скажем, 104 шага, это более 55 часов при \(\lambda\) = 10 секунд26), с высокой вероятностью (скажем, 1−10−10) не более одной ветки будет иметь tH правильных сигнатур. для подтверждения блока в раунде r + 1. Наконец, если в физическом разделе созданы две части примерно одинакового размера, то вероятность того, что |HSV r,s я | + |MSV r,s я | \(\geq\)tH мало для каждой части i. После аналогичного анализа даже если Противнику удастся создать форк с некоторой немалой вероятностью в каждой части в раунде r не более одной из четырех ветвей может вырасти в раунде r + 1. 10.2 Состязательный раздел Во-вторых, перегородка может быть вызвана Противником, поэтому сообщения распространялись честными пользователями в одной части, не дойдет напрямую до честных пользователей в другой части, но Противник может пересылать сообщения между двумя частями. И все же однажды сообщение от одного часть доходит до честного пользователя в другой части, в последней она будет распространяться как обычно. Если Злоумышленник готов потратить много денег, вполне возможно, что он сможет взломать Интернет и разделите его на некоторое время вот так. Анализ аналогичен анализу большей части физического раздела выше (меньшая часть часть можно рассматривать как имеющую население 0): Противник может создать вилку и каждый честный пользователь видит только одну из ветвей, но может вырасти не более одной ветки. 10.3 Сетевые разделы в сумме Несмотря на то, что сетевые разделы могут возникнуть, а под разделами может произойти ветвление за один раунд, Нет никакой затяжной двусмысленности: вилка очень недолговечна и фактически длится не более одного раунда. В все части раздела, кроме не более чем одной, пользователи не могут создать новый блок и, следовательно, (а) понимать, что в сети есть раздел, и (б) никогда не полагаться на блоки, которые «исчезнут». Благодарности Прежде всего мы хотели бы выразить признательность Сергею Горбунову, соавтору упомянутой системы Democoin. Самая искренняя благодарность Морису Херлихи за множество поучительных обсуждений и за указание что конвейеризация улучшит производительность Algorand, а также значительно улучшит 26Обратите внимание, что пользователь завершает шаг s, не дожидаясь времени 2\(\lambda\), только если он увидел хотя бы tH подписей для то же сообщение. Если подписей недостаточно, каждый шаг будет длиться 2\(\lambda\).

изложение более ранней версии этой статьи. Большое спасибо Серджио Райсбауму за его комментарии по поводу более ранняя версия этой статьи. Большое спасибо Виноду Вайкунтанатану за несколько глубоких обсуждений. и идеи. Большое спасибо Йосси Гиладу, Ротему Хамо, Георгиосу Влахосу и Николаю Зельдовичу. за начало проверки этих идей, а также за множество полезных комментариев и обсуждений. Сильвио Микали хотел бы лично поблагодарить Рона Ривеста за бесчисленные обсуждения и рекомендации. в криптографических исследованиях на протяжении более трех десятилетий за соавторство упомянутой системы микроплатежей. это послужило вдохновением для создания одного из механизмов выбора верификатора Algorand. Мы надеемся вывести эту технологию на новый уровень. Тем временем путешествие и общение это очень весело, за что мы очень благодарны.