2025-11-21T20:28:23.433071

OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA

Chen
In this work, we propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA. This protocol achieves MVBA consensus on a message $\boldsymbol{w}$ with expected $O(n |\boldsymbol{w}|\log n + n^2 \log q)$ communication bits, expected $O(n^2)$ messages, expected $O(\log n)$ rounds, and expected $O(\log n)$ common coins, under optimal resilience $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. When error correction codes with a constant alphabet size (e.g., Expander Codes) are used, $q$ becomes a constant. An MVBA protocol that guarantees all required properties without relying on any cryptographic assumptions, such as signatures or hashing, except for the common coin assumption, is said to be information-theoretically secure (IT secure). Under the common coin assumption, an MVBA protocol that guarantees all required properties in all executions is said to be error-free. We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^2 \log n)$ communication bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under a relaxed resilience (RR) of $n \geq 5t + 1$. Additionally, we propose a hash-based asynchronous MVBA protocol, called OciorMVBAh. This protocol achieves MVBA consensus with expected $O(n |\boldsymbol{w}| + n^3)$ bits, expected $O(1)$ rounds, and expected $O(1)$ common coins, under optimal resilience $n \geq 3t + 1$.
academic

OciorMVBA: Асимптотически оптимальный безошибочный асинхронный MVBA

Основная информация

  • ID статьи: 2501.00214
  • Название: OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA
  • Автор: Jinyuan Chen
  • Классификация: cs.CR (Криптография и безопасность), cs.DC (Распределённые вычисления), cs.IT (Теория информации), math.IT (Теория информации)
  • Дата публикации: 31 декабря 2024 г. (препринт arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2501.00214

Аннотация

В данной работе предложен протокол OciorMVBA — безошибочный, информационно-теоретически безопасный протокол асинхронного многозначного верифицируемого византийского соглашения (MVBA). Протокол достигает консенсуса MVBA для сообщения w в сети из n узлов с оптимальной отказоустойчивостью n ≥ 3t + 1 со следующими сложностями: ожидаемая сложность связи O(n|w|log n + n²log q) бит, ожидаемое количество сообщений O(n²), ожидаемое количество раундов O(log n) и ожидаемое количество общих монет O(log n). Кроме того, предложены два варианта протокола: OciorMVBArr достигает сложности O(1) раундов при ослабленной отказоустойчивости n ≥ 5t + 1, а основанный на хешировании OciorMVBAh достигает сложности O(1) раундов при оптимальной отказоустойчивости.

Исследовательский контекст и мотивация

Определение проблемы

Многозначное верифицируемое византийское соглашение (MVBA) является ключевым строительным блоком распределённых систем и криптографии, введённым Cachin и соавторами в 2001 году. В MVBA распределённые узлы предлагают свои входные значения и стремятся достичь консенсуса по одному из значений, удовлетворяющему предопределённой функции предиката (внешняя валидность).

Значимость исследования

  1. Теоретическая основа: Фундаментальная работа Fischer, Lynch и Paterson показала, что в асинхронной среде не существует детерминированного протокола MVBA, поэтому любой асинхронный протокол MVBA должен вводить случайность
  2. Практические требования: Распределённые системы нуждаются в надёжном консенсусе в асинхронных сетях при наличии византийских сбоев
  3. Требования безопасности: Необходимо обеспечить информационно-теоретическую безопасность без зависимости от криптографических предположений (кроме общей монеты)

Ограничения существующих подходов

Из сравнения в таблице I видно, что существующие протоколы MVBA имеют следующие проблемы:

  • Большинство полагаются на криптографические предположения, такие как пороговые подписи или хеширование
  • Высокая сложность связи, особенно без криптографических предположений
  • Неоптимальная сложность раундов и эффективность использования общей монеты

Основные вклады

  1. Предложение протокола OciorMVBA: Первый безошибочный, информационно-теоретически безопасный асинхронный протокол MVBA, достигающий асимптотически оптимальной сложности связи O(n|w|log n + n²log q) при оптимальной отказоустойчивости n ≥ 3t + 1
  2. Разработка протокола OciorMVBArr: Протокол, достигающий сложности связи O(n|w| + n²log n) и сложности раундов O(1) при ослабленной отказоустойчивости n ≥ 5t + 1
  3. Построение протокола OciorMVBAh: Основанный на хешировании протокол, достигающий сложности связи O(n|w| + n³) и сложности раундов O(1) при оптимальной отказоустойчивости
  4. Введение новых примитивов: Предложены асинхронное смещённое двоичное византийское соглашение (ABBBA) и асинхронное полное информационное рассеивание (ACID) в качестве новых строительных блоков

Подробное описание методов

Определение задачи

Вход: Каждый честный узел предлагает входное значение w, удовлетворяющее функции предиката Predicate(w) = true Выход: Все честные узлы в итоге выдают одно и то же значение w', причём Predicate(w') = true Ограничения: Удовлетворение трём свойствам: согласованность, завершение и внешняя валидность

Архитектура протокола OciorMVBA

Общий дизайн

OciorMVBA является рекурсивным протоколом, основные компоненты которого включают:

  • RMVBA(ID, p): Рекурсивный протокол MVBA
  • SHMDM: Сильное честное большинство распределённого мультикаста
  • OciorRBA: Надёжное византийское соглашение
  • ABBBA: Асинхронное смещённое двоичное византийское соглашение
  • ABBA: Асинхронное двоичное византийское соглашение

Основной алгоритм

  1. Разделение сети: Разделение сети Sp на два непересекающихся подмножества S2p и S2p+1
  2. Рекурсивные вызовы: Параллельное выполнение подпротоколов RMVBA на подсетях
  3. Распространение сообщений: Распространение выходов подпротоколов через протокол SHMDM
  4. Проверка согласованности: Верификация надёжности сообщений с использованием OciorRBA
  5. Механизм выбора: Определение окончательного выхода через упорядоченный выбор и протоколы ABBBA/ABBA

Ключевые технические детали

Процесс Ready-Finish-Confirm:

Шаг 1: Выход подпротокола → распространение SHMDM
Шаг 2: Выход SHMDM → верификация OciorRBA
Шаг 3: Выход OciorRBA vi=1 → установка Iready[θ]=1, отправка сообщения READY
Шаг 4: Получение достаточного количества сообщений READY → установка Ifinish[θ]=1, отправка сообщения FINISH
Шаг 5: Получение достаточного количества сообщений FINISH → установка Iconfirm[θ]=1

Протокол ABBBA:

  • Вход: Двоичная пара (a1, a2)
  • Смещённая валидность: Если t+1 честных узлов вводят a2=1, то выход равен 1
  • Смещённая полнота: Если выход равен 1, то по крайней мере один честный узел вводит a1=1 или a2=1

Разработка протокола OciorRBA

Расширение на основе протоколов COOL и OciorCOOL, включающее три этапа:

  1. Этап 1: Обмен символами и обновление индикаторов связи
  2. Этап 2: Обработка индикаторов успеха
  3. Этап 3: Онлайн исправление ошибок и восстановление сообщений

Технические инновации

  1. Рекурсивная архитектура: Достижение логарифмической сложности раундов через разделение сети и рекурсивные вызовы
  2. Смещённое соглашение: Протокол ABBBA обеспечивает быстрое завершение при определённых условиях
  3. Онлайн исправление ошибок: Использование кодов Рида-Соломона или кодов Expander для эффективного исправления ошибок
  4. Отсутствие криптографических предположений: Независимость от любых криптографических примитивов, кроме общей монеты

Экспериментальная установка

Теоретическая аналитическая база

Статья в основном проводит теоретический анализ, верифицируя свойства протокола следующим образом:

Анализ сложности:

  • Сложность связи: Анализ рекурсивных соотношений
  • Сложность раундов: Анализ глубины сетевого дерева
  • Сложность сообщений: Статистика взаимодействий протокола

Доказательство безопасности:

  • Согласованность: Доказана в Лемме 3
  • Завершение: Доказано через анализ сетевых цепей (Леммы 2, 4)
  • Внешняя валидность: Гарантирована верификацией предиката

Сравнительные ориентиры

Сравнение с существующими протоколами MVBA, включая:

  • Cachin et al. 1 - Фундаментальная работа по MVBA
  • Abraham et al. 8 - Оптимизированная схема пороговых подписей
  • Dumbo-MVBA 9 - Эффективный протокол пороговых подписей
  • Duan et al. 10 - Протокол на основе хеширования и без криптографических предположений

Результаты экспериментов

Основные теоретические результаты

Производительность OciorMVBA:

  • Сложность связи: O(n|w|log n + n²log q) бит
  • Сложность сообщений: O(n²)
  • Сложность раундов: O(log n)
  • Общая монета: O(log n)

Производительность OciorMVBArr (n ≥ 5t + 1):

  • Сложность связи: O(n|w| + n²log n) бит
  • Сложность раундов: O(1)
  • Общая монета: O(1)

Производительность OciorMVBAh:

  • Сложность связи: O(n|w| + n³) бит
  • Сложность раундов: O(1)
  • Общая монета: O(1)

Анализ сложности

Через рекурсивное соотношение:

fTB(ñp) = β1ñp|w| + β2ñp²log q + fTB(⌊ñp/2⌋) + fTB(⌈ñp/2⌉)

доказана общая сложность связи O(n|w|log n + n²log q).

Корректность протокола

Через ряд лемм доказано, что протокол удовлетворяет трём основным свойствам MVBA:

  • Теорема 1: Согласованность и завершение
  • Теорема 2: Внешняя валидность
  • Теорема 3: Сложность связи и раундов

Связанные работы

Развитие протоколов MVBA

  1. Ранние работы: Cachin и соавторы впервые предложили концепцию MVBA
  2. Методы на основе подписей: Abraham и соавторы, Dumbo-MVBA и другие оптимизировали протоколы на основе пороговых подписей
  3. Методы без подписей: Duan и соавторы предложили протоколы на основе хеширования без подписей
  4. Информационно-теоретическая безопасность: Данная работа является первой, достигающей асимптотически оптимальной производительности информационно-теоретически безопасного протокола при оптимальной отказоустойчивости

Технические основы

  • Протоколы COOL/OciorCOOL: Обеспечивают примитивы UA и HMDM
  • Теория кодов исправления ошибок: Применение кодов Рида-Соломона и кодов Expander
  • Византийское соглашение: Развитие от классических работ Pease, Shostak и Lamport

Заключение и обсуждение

Основные выводы

  1. При оптимальной отказоустойчивости n ≥ 3t + 1 реализован первый асимптотически оптимальный безошибочный информационно-теоретически безопасный асинхронный протокол MVBA
  2. Путём ослабления отказоустойчивости или введения предположения о хешировании можно достичь постоянной сложности раундов
  3. Рекурсивный дизайн и механизм смещённого соглашения являются ключевыми для достижения высокой производительности

Ограничения

  1. Постоянные множители: Хотя асимптотическая сложность оптимальна, постоянные множители могут быть значительными
  2. Зависимость от общей монеты: По-прежнему требуется O(log n) общих монет
  3. Разделение сети: Рекурсивное разделение может вводить дополнительные издержки в реальных сетях
  4. Выбор кода исправления ошибок: Производительность зависит от размера алфавита q кода исправления ошибок

Направления будущих исследований

  1. Оптимизация постоянных множителей: Снижение постоянных множителей в протоколе
  2. Эффективность общей монеты: Дальнейшее снижение использования общей монеты
  3. Практическая реализация: Разработка эффективной практической реализации и оценка производительности
  4. Расширение приложений: Применение протокола в конкретных распределённых системах

Глубокая оценка

Преимущества

  1. Теоретический прорыв: Достижение асимптотически оптимальной сложности связи в информационно-теоретически безопасной установке
  2. Умный дизайн: Комбинация рекурсивной архитектуры и смещённого соглашения весьма инновативна
  3. Строгий анализ: Предоставлены полные доказательства корректности и анализ сложности
  4. Практическая ценность: Предложены несколько вариантов для адаптации к различным сценариям применения

Недостатки

  1. Отсутствие экспериментальной верификации: Статья в основном содержит теоретический анализ, без практической реализации и тестирования производительности
  2. Постоянная сложность: Хотя асимптотически оптимально, реальные постоянные множители могут влиять на практическую применимость
  3. Предположения: Предположение об общей монете может быть сложно реализовать в реальных системах
  4. Читаемость: Описание протокола достаточно сложно, что затрудняет понимание и реализацию

Влияние

  1. Теоретический вклад: Предоставляет новый теоретический ориентир для области MVBA
  2. Техническое вдохновение: Рекурсивный подход проектирования может вдохновить разработку других распределённых протоколов
  3. Практический потенциал: Имеет применимость в критических системах с высокими требованиями безопасности
  4. Направление исследований: Предоставляет новые идеи для последующей оптимизации протоколов MVBA

Применимые сценарии

  1. Высокие требования безопасности: Критические системы, требующие гарантий информационно-теоретической безопасности
  2. Крупномасштабные сети: Распределённые системы с большим количеством узлов
  3. Асинхронная среда: Среды с непредсказуемыми сетевыми задержками
  4. Отказоустойчивые системы: Системы, требующие толерантности к византийским сбоям

Библиография

Статья цитирует 17 связанных работ, основные из которых:

  • 1 Cachin et al. - Фундаментальная работа по MVBA
  • 5-7 Chen - Серия протоколов COOL и OciorCOOL
  • 8-12 Важные достижения в недавних протоколах MVBA
  • 13-15 Теоретические основы кодов исправления ошибок
  • 17 Li-Chen - Протокол асинхронного византийского соглашения