
HybridDKG — одна из новейших схем распределенной генерации ключей, которая может работать в асинхронной среде, что делает ее наиболее жизнеспособной схемой DKG для использования через Интернет
Введение
В предыдущем сообщении мы обсудили важные конструкции VSS и DKG и представили Aggregatable DKG. Теперь, когда читатель лучше понимает DKG, в этой статье рассматривается другая схема DKG, называемая HybridDKG, опубликованная в разделе Генерация распределенных ключей в дикой природе.
HybridDKG — это DKG, работающий в рамках модели асинхронной связи, которая является гораздо более реалистичной моделью, чем синхронная модель, на которой основано большинство других схем DKG. Базовый VSS, называемый HybridVSS, основан на AVSS, который является компонентом HybridDKG, позволяющим ему работать асинхронно. Поскольку HybridDKG работает по асинхронной модели, он требует, чтобы оба протокола VSS и DKG использовали механизмы консенсуса, чтобы узлы согласовывали секреты.
Предположения
Как и любая криптографическая конструкция, HybridDKG опирается на определенные предположения, чтобы доказать свои свойства безопасности.
Модель коммуникации
HybridDKG использует асинхронную модель связи, в которой часы узлов могут быть неточными (то есть они могут быть не синхронизированы), а сообщения могут задерживаться на произвольный период времени. В этой модели предполагается, что злоумышленник управляет каналами связи и может задерживать сообщения по своему усмотрению. HybridDKG предполагает, что реальный злоумышленник не может контролировать каналы связи для всех честных узлов и, следовательно, что злоумышленник (в конечном итоге) доставляет все сообщения между двумя неповрежденными узлами.
Более строгое предположение, называемое слабой синхронностью, используется только для того, чтобы доказать жизнеспособность протокола. В предположении слабой синхронности разница во времениделай(Т)между моментом отправки сообщения (Т), и время его получения не увеличивается бесконечно с течением времени.
Слабая синхронизация не обязательна для корректности протокола.
Также предполагается, что все коммуникации аутентифицированы и злоумышленник не может подделать сообщения.
Неисправности
HybridDKG может допускать невизантийные сбои узлов, невизантийские разрывы каналов связи и византийские сбои. Он группирует невизантийные сбои и невизантийные одиночные нарушения связи под одним и тем же типом неисправности. Византийский противник считается статичным, что означает, что он не может изменить свой выбор узлов с течением времени.
Протокол может допускать:
- Вплоть дотвизантийские узлы
- Вплоть дожневизантийские сбойные узлы и невизантийские неудачные соединения в любой момент времени
- д(�)максимальное количество сбоев, которые может совершить злоумышленник за время своего существования
Количество участников:
$$
n \ge 3t+2f+1
$$
Противник
Предположение, введенное конкретной схемой полиномиального обязательства, используемой в этом HybridVSS, заключается в том, что злоумышленник вычислительно ограничен в DLP параметром безопасности.�.
Предварительные условия
Сначала перечислим некоторые математические свойства, которые пригодятся в дальнейшем:
- Чтобы восстановить одномерный полином степенитнам нужнот+1точки на этом многочлене
- Имея двумерный полином�(Икс,й)степени2т, мы можем генерировать одномерные полиномы, фиксируя значениеИкс(илий):
аИкс"="Икс'(й)"="�(Икс',й) - Если двумерный полином симметричен, то верно, что�(Икс,й)"="�(й,Икс)
- Из вышесказанного мы можем вывести это для симметричного�оно держитсяаИкс'(й)"="ай(Икс')
HybridVSS
В асинхронной модели каждый узел следует двум предположениям: достаточное количество узлов получит свои доли и достаточное количество узлов будет участвовать в реконструкции. Чтобы исключить необходимость делать предположения, HybridVSS делает еще один шаг вперед и предоставляет узлам механизм отслеживания количества других узлов и их состояний вместо того, чтобы полагаться на приведенные выше предположения.
Теперь мы определим этапы совместного использования, реконструкции и восстановления HybridVSS. Все сообщения, описанные ниже, помечены уникальным идентификатором сеанса.(пд,�), спдбыть дилером сессии и�уникальный номер.
Совместное использование
Инициализация
Дилер:
- создает случайный симметричный двумерный полином�(Икс,й)"="∑я,дж"="0т�яджИксяйджс секретом, закодированным как постоянный коэффициент�(0,0)"="�00.
- вычисляет гомоморфное обязательствоСк многочлену, который является матрицей сСядж"="г�ядж.
Сможет использоваться узлами для проверки того, что: - заданный одномерный полиномая(Икс)"="∑л"="0тая,лИкслпринадлежит�проверив:
гая,л"="?∏дж"="0т(Сджл)ядж,∀л€[0,т] - заданное значение�соответствует�(м,я)проверив:
г�"="?∏дж,л"="0т(Сджл)мджял
Дилерство
пдзатем раздается каждому узлупяодномерный полиномая(Икс)"="�(Икс,я)отправив сообщение под названиемсенд.
Это сообщение также доставляется С.
Стакже отправляется вместе со всеми другими типами сообщений между узлами, чтобы любые два участника могли проверить обязательства дилера и предотвратить разделение узлов злонамеренным дилером путем совместного использования разных обязательств.
Каждыйпякоторый получаетсенд, проверяетая(Икс)с использованиемС.
Этот полином позволяет пядля создания точки, принадлежащей многочленуадж(Икс)другого узлапджсая(дж)"="адж(я)из-за�Симметрия.
Проверка и консенсус на основе сплетен
Каждыйпякоторый получает действительныйсендсообщение, отправляет сообщение под названиемесчасок каждому узлупджсообщить им о том, что дилер вышел на связь.
есчасонесетая(дж)в качестве доказательства того, что оно было признано действительнымая(Икс).
После отправкиесчасоко всем узлам,пяпереходит в состояние прослушивания, где он прослушивает два типа сообщений,есчасоиреадй.
За каждое полученноеесчасоиз узлапджполучательпя:
- проверяетадж(я)противСи если проверено, он сохраняет точку(дж,адж(я))в набореАся←(дж,адж(я))дж
- если достаточно(⌈н+т+12⌉) действительныйесчасосообщения с таким же обязательствомСпринимаются, чтобы убедитьпячто дилер достиг достаточного количества узлов, он использует очки вАсяинтерполировать полиномаˉя(Икс)
- отправляетреадйвсем остальным узлам, несущим точкуаˉя(дж)как доказательство того, что он получил достаточноесчасос
За каждое полученное и проверенноереадй,пя:
- сохраняет полученную точкуаˉдж(я)в том же набореАся
- если достаточно(т+1)реадйсообщения с таким же обязательствомСполучены для возможности интерполяции многочлена степенит,пяинтерполируетаˉя(Икс)
- отправляетреадйкоторый несетаˉя(дж)к каждому узлупдж
- если достаточнореадйСообщения (н−т−ж) с тем же обязательствомСполучены запячтобы убедиться, что достаточное количество узлов знает, что участвует достаточное количество узлов, он вычисляет свою долюся"="аˉя(0)и останавливается.
Дополнительные примечания
Узел завершает процесс совместного использования, если он получил (н−т−ж) реадйСообщения. Здесь узел следит за наличием достаточного количества честных узлов с долями. Другими словами, он следит за тем, чтобы участвующие честные узлы формировали большинство при наличии дотвизантийские противники и до фф разбившихся узлов.
Если узел получилреадйот другого узла, это означает, что другой узел отправил эхо, но оно так и не было получено. Т.е.,реадйподразумеваетесчасо. Узел может завершить фазу совместного использования, только получив достаточное количество готовых сообщений. В этом случае необходимо интерполироватьаˉя(Икс)для того, чтобы вычислить его долю, поскольку интерполяция весчасообработка не произошла. Это причина шага интерполяции при обработкереадйсообщение.
Важно отметить, что узел будет обрабатывать только первыйсенд,есчасоисчасаресообщения, которые он получил от определенного узлапяво время сеанса(пд,�). Это делается для того, чтобы убедиться в том, что:
- узлы'есчасоиреадйзлоумышленник не может манипулировать счетчиками путем повторения сообщений
- любые сообщения восстановления в обращении не изменят состояние системы (это станет ясно из подраздела восстановления ниже)
Реконструкция
Давайте сначала объясним, как доли связаны с секретом.
Доля пяявляетсяся"="аˉя(0)"="аˉ0(я), что означает, что данноет+1доли, которые мы можем интерполироватьаˉ0(Икс)"="�(0,Икс).
Затем мы можем оценить этот полином как 0чтобы получить секретс"="аˉ0(0)"="�(0,0).
Чтобы восстановить секрет, каждый узел отправляет свою долюсявсем остальным узлам, используя сообщениересонстртыстсчасаре. Он также прослушиваетресонстртыстсчасареСообщения. За каждое полученноересонстртыстсчасареиз узлапдж, он сначала проверитадж(0)против обязательстваС:
гся"="?∏дж"="0т(Сдж0)мдж
и если точка проверена, он сохранит ее.
Когда узел соберет т+1точек, он готов к интерполяцииаˉ0(Икс)а затем получить секретаˉ0(0).
Восстановление
Обозначимд(�)(�— параметр безопасности системы) максимальное количество сбоев, которые злоумышленнику разрешено совершить за время его существования.
Во время восстановления ранее вышедший из строя узел попросит других узлов помочь воспроизвести свое предыдущее общение. Каждый узел хранит запись всех исходящих сообщений вместе с их предполагаемыми получателями в наборе.Б, иБлуказывает на подмножествоБпредназначен для узлапл. Кроме того, каждый узел поддерживает два счетчика.снтиснтл. Первый отслеживает общее количество (в масштабах всей системы) запросов на помощь, а второй — количество запросов на помощь, отправленных каждым узлом.пл.
Аварийный узел, который только что восстановился, сначала отправитчаселпсообщение всем узлам. Он также будет воспроизводить сообщения вБ. Когда узел получаетчаселпсообщение, он сначала удостоверится, что пределы помощи не превышены:снт≤(т+1)д(�)иснтл≤д(�)и если эти проверки пройдут, он воспроизведет все сообщения вБл, что помогает воспроизвести историю сообщений, относящуюся к восстановленному узлу.
Учитывая вышеизложенное, мы видим, что если бы сообщения о восстановлении были обработаны, многие, если не все, счетчики пакетов будут считать восстановленный узел дважды.
HybridVSS
Как и другие конструкции DKG, HybridDKG поставляет все узлы HybridVSS дилерам. Каждый узел генерирует коллекцию общих ресурсов из нескольких экземпляров HybridVSS, и его окончательная доля будет суммой этих общих ресурсов. В отличие от DKG, работающих в синхронном режиме, асинхронная модель вводит требование соглашения как минимум по(т+1)успешные экземпляры HybridVSS для набора честных узлов. Дополнительная сложность асинхронной настройки заключается в необходимости различать сломанные и медленные узлы.
HybridDKG вводит роль лидера (л), который отвечает за предложение набора готовых экземпляров HybridVSS для использования. Поскольку лидер может быть вредоносным или выйти из строя, вводится механизм смены лидера. Узлы используют таймауты, чтобы решить, следует ли считать лидера аварийным.
HybridVSS расширен сообщением:счасаредкоторый отправляется каждым узлом, завершающим этап совместного использования HybridVSS. Он несет в себе всереадйсообщения для сеанса(пд,�)и подписи над ними, что помогает лидеру предоставить доказательство действительности своего предложения.
HybridDKG использует две фазы: оптимистическую и пессимистическую: первая отвечает за генерацию ключей и обеспечивает восстановление после сбоя; последний отвечает за выполнение потенциальных операций по смене лидеров.
Оптимистическая фаза
Выполнение гибридного VSS
Оптимистическая фаза начинается на каждом узлепдстать дилером сессии HybridVSS ради секретасд. В конце сеанса HybridVSS каждый узелпятранслирует(пд,�,счасаред,Сд,ся,д,рд)сообщение. Наборрдвключаетн−т−жподписанореадйсообщения для сеанса(пд,�),ся,дэто доля узлапяиСдэто его обязательство. Все узлы собираютпдирдполученныхсчасаредСообщения:
вопрос^←вопрос^∪пд
р^←р^∪рд
Предложение ВСС
Один разлобработалт+1 счасаредсообщения, он будет транслироватьсендсообщение, предлагающее набор экземпляров VSS, которые этисчасаредсообщения соответствуют. Это сообщение относится только к HybridDKG, и его не следует путать с сообщениемсендсообщение HybridVSS.
сенднесетвопрос^что представляет собойлПредложение по набору экземпляров HybridVSS для использования. Он также несетр^в качестве доказательства того, что заседания, на которые ссылаютсявопрос^действительны.
Условие смены лидера
Любой узел, кромел, что обработанот+1 счасаредсообщения запускают локальный таймер, который останавливается последелай(Т). Если таймер узла останавливается до того, как узел достиг конца протокола, узел предполагает, что лидер либо вышел из строя, либо является вредоносным, и запрашивает смену лидера. Запрос на смену лидера выполняется путем трансляциилеадсчассообщение. Мы откладываем объяснение логики смены лидеров до тех пор, пока не закончим оптимистическую фазу.
Проверка и консенсус на основе сплетен
Все узлы, кромел, начну слушатьсенд,есчасоиреадйСообщения. Опять же, эти сообщения специфичны для HybridDKG, и их не следует путать с их синонимом HybridVSS. Однако концептуально эти сообщения служат тем же целям, что и в HybridVSS.
Анесчасосообщение отправляется после получения действительногосенд. Цельесчасосостоит в том, чтобы сообщить получателю, что с отправителем связалсялс действительным предложением.есчасонесет в себе предлагаемый наборвопрос.
Ареадйсообщение отправляется узлами, которые получили достаточно (⌈н+т+12⌉)есчасосообщения для одного и того же наборавопросили достаточно(т+1)реадйсообщения для одного и того же наборавопрос. На этом этапе узел знает, что протокол может завершиться успешно, поскольку ему известно достаточное количество участвующих узлов иреадйсообщение информирует получателей об этом факте. Узел также обновит своювопрос^установлен ввопрос, так как на данный момент набор согласован, и сохраните соответствующую подписьесчасоилиреадйсообщения в качестве доказательства. Это обновление набора служит заметкой о том, на основании чего были согласованы экземпляры VSS, и используется при смене лидера (подробнее об этом в разделе, объясняющем пессимистическую фазу).
Долевое строительство
Наконец, когда узел получает достаточно (н−т−ж)реадйсообщений, он может завершить протокол совместного использования, вычислив свою долю:
ся"="∑пд€вопросся,д
и его матрица обязательств, созданная на основе матриц обязательств каждого экземпляра HybridVSS:
С"="Сп,д"="∏пд€вопрос(Сд)п,д
Пессимистическая фаза
Узел вступает в эту фазу, когда его не устраивает текущий лидер. Причины такого недовольства могут быть связаны с тайм-аутом или получением некорректного сообщения от лидера.
Предполагается, что предопределенная циклическая перестановка узлов согласована заранее. Для простоты будем считать, что лидеры отсортированы в простом порядке возрастания.
При входе в эту фазу узел будет транслировать сообщение, называемоелеадсчас, информируя другие узлы о том, что он предлагает смену лидера. Сообщения несет предлагаемый лидерлˉна который узлы хотят измениться. Неудовлетворенный узел предлагает узел, следующий (в порядке очереди) за своим текущим лидером.
Между узлами необходимо согласовать две вещи: происходит ли смена лидера и, если да, то какой узел будет новым лидером.
Узел, который получаетт+ж+1 леадсчассообщения будут убеждены в том, что происходит смена лидера, и будут транслироватьлеадсчаспредложив наименьшего предложенного лидера, который он получил. Если узел получаетт+ж+1 леадсчас сообщений, предлагающих одного и того же лидера, он примет этого лидера, поскольку достигнут консенсус относительно лидера.
Затем, если узел не является следующим лидером, он перезапустит свой счетчик и войдите в оптимистичный режим.
В случае, если узел является следующим лидером, он будет использовать ранее сохраненныйвопрос^установите в качестве набора VSS для использования. Он будет транслироватьсендсообщение с этим набором и сопровождающими его подписанными пакетами (счасаред,есчасоилиреадй) в качестве доказательства, а затем войдите в оптимистический режим.
Восстановление после сбоя
Для восстановления вышедшего из строя узла используется тот же подход, что и в HybridVSS.
Реконструкция
Реконструкция секрета HybridDKG выполняется так же, как и в HybridVSS. Каждый узел передает свою долю и собирает доли от других узлов. Когда узел соберет достаточное количество долей, он интерполирует соответствующий полином и вычислит его как0вычислить секрет.
Производительность
HybridVSS
Предполагаем, что сбоев нет и, следовательно, нет сообщений о восстановлении:
Размер сообщений HybridVSS во многом зависит от размера обязательства Скоторый имеетт(т+1)2групповые элементы и, следовательно, битовая сложность протокола равнаО(�н4). Существует улучшение, которое уменьшает сложность битов доО(�н3) с использованием устойчивой к коллизиям хэш-функции (AVSS, раздел 3.4).
В После расчетов будем считать, что это улучшение использовано. Сложность сообщения О(н2).
Принимая во внимание сообщения о восстановлении, сложность сообщения становитсяО(тдн2)и битовая сложностьО(�тдн3)былид"="д(�).
HybridDKG
С донЭкземпляры VSS могут завершиться без каких-либо пессимистических фаз.О(тдн3)сложность сообщения иО(�тдн4)битовая сложность.
Если считать пессимистические фазы, то мы имеем не болееО(д)Операции по смене лидера. Каждая операция по смене лидера имеетО(тдн2)сообщение иО(�тдн3)битовая сложность. Таким образом, общие издержки пессимистической фазы составляютО(тд2н2)сообщение иО(�тд2н3)битовая сложность.
Добавляя пессимистические накладные расходы к сложностям HybridDKG, мы получаемО(тдн2(н+д))сообщение иО(�тдн3(н+д))немного сложностей.
Написано Джорджем Гкитсасом, ранее исследователем криптографии с нулевым разглашением & разработчик протокола в Heliax, команде, создающей протокол Anoma.
Если вас интересуют вакансии разработчиков криптографии с нулевым разглашением и передовых криптографических протоколов в Rust, ознакомьтесь с открытыми вакансиями в Heliax.