Перейти к содержанию
Financial Context Wiki

Криптографические аккумуляторы

Руководство по криптографическим аккумуляторам с акцентом на проверку: схемы на основе RSA и хешей, свидетели членства и нечленства, динамические обновления, применение в блокчейнах и операционные риски.

Обновлено

Только в образовательных целях; материал не является инвестиционной консультацией или руководством по реализации криптографических систем. Доказательство аккумулятора удостоверяет утверждение относительно одного обязательства, но не достоверность исходных данных, состояние консенсуса или доступность данных.

Краткий ответ

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

Аккумулятор называют статическим, если после изменения множества его требуется построить заново, динамическим, если при добавлении или удалении можно эффективно обновить аккумулятор и свидетелей, и универсальным, если он поддерживает доказательства как членства, так и нечленства. Эти определения описывают отдельные свойства: динамическая схема не обязательно является универсальной.

В блокчейнах можно фиксировать транзакции, неизрасходованные выходы, учетные записи, валидаторов или записи об отзыве. Компактное обязательство способно уменьшить объем состояния, хранимого некоторыми участниками, однако системе по-прежнему необходимо распространять исходные данные и актуальных свидетелей, удостоверять обновления, обрабатывать реорганизации цепочки и определять, кто вправе изменять множество.

Как это работает

  1. Точно определить множество. Задайте каноническое кодирование элементов, правила обработки дубликатов и, где применимо, порядок элементов, разделение доменов и точную версию обязательства. Доказательство для одного способа кодирования или одного корня состояния ничего не говорит о другом.

  2. Выполнить настройку схемы. Аккумулятор на основе хешей может использовать только открытые параметры хеширования. В RSA-аккумуляторе применяется группа неизвестного порядка, обычно полученная из модуля RSA N; для безопасности необходимо, чтобы неуполномоченные стороны не могли воспользоваться его факторизацией. В других схемах могут применяться спаривания, группы классов, решетки или дополнительные открытые параметры с иными предположениями о доверии.

  3. Отобразить элементы в алгебраическую структуру. В упрощенной конструкции RSA каждый элемент x_i детерминированно отображается в уникальное простое число-представитель p_i. При основании g аккумулятор имеет вид:

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. Создать свидетель членства. Для элемента, представленного числом p_i, его множитель исключают из показателя степени:

    w_i = g^(product of p_j for all j != i) mod N

  5. Проверить относительно конкретного аккумулятора. Проверяющая сторона контролирует каноничность входных данных и проверяет равенство:

    w_i^(p_i) mod N = A

    При выполнении предположения о безопасности схемы получить такое равенство для элемента вне накопленного множества должно быть практически невозможно. Само равенство не подтверждает истинность элемента или наличие разрешения на него.

  6. Обрабатывать обновления и нечленство отдельно. Динамические схемы определяют, как добавления и удаления изменяют A и как обновляются затронутые свидетели. Универсальные схемы добавляют отдельный свидетель нечленства и алгоритм его проверки. Реализация должна отклонять устаревших свидетелей и обновления, привязанные к другому состоянию.

  7. Сравнивать структуры на основе хешей по их фактическим затратам. Дерево Меркла в широком смысле является аккумулятором на основе хешей: его корень компактен, а доказательство членства содержит хеши соседних узлов вдоль пути и поэтому растет логарифмически с числом листьев. Схемы типа RSA могут предоставлять отдельные свидетели постоянного размера, однако генерация доказательств, поддержание свидетелей, настройка и вычисления требуют иных затрат.

Практические примеры

  • Размер доказательства Меркла. Для сбалансированного двоичного дерева Меркла с 1,048,576 = 2^20 листьями один путь включения содержит 20 хешей соседних узлов. При длине хеша 32 байта это составляет 20 * 32 = 640 bytes без учета данных листа, битов позиции и накладных расходов на сериализацию. Корень по-прежнему занимает 32 байта.
  • Постоянный размер не означает постоянный объем работы. В упрощенной конструкции RSA и A, и отдельный w_i остаются каждый одним элементом группы независимо от роста множества. При этом вычисление произведения в показателе степени, получение простых чисел-представителей, пакетные обновления и распространение обновленных свидетелей могут по-прежнему требовать значительных вычислений или вспомогательных данных.
  • Аккумулятор UTXO меняет распределение хранения. Узел с компактным состоянием может хранить аккумулятор неизрасходованных выходов и проверять расходование, только получив сам выход и актуальное доказательство членства. Другие участники все равно хранят достаточно состояния для создания таких доказательств, а обновления должны удалять израсходованные выходы и добавлять вновь созданные.
  • Для отзыва действует та же граница. Владелец учетных данных может доказать, что идентификатор остается в аккумуляторе активных участников, либо с помощью универсальной конструкции доказать его отсутствие во множестве отозванных записей. Доказательство удостоверяет множество, зафиксированное издателем, но не доказывает справедливость или правильность примененной им политики отзыва.

Риски

  • Использование неоднозначного или неканонического кодирования элементов, при котором один логический объект отображается по-разному.
  • Неправильное отображение элементов в простые числа-представители или отсутствие требуемых схемой средств контроля коллизий.
  • Доверие модулю RSA, факторизация которого может быть известна стороне, проводившей настройку, или злоумышленнику.
  • Признание многосторонней церемонии настройки безопасной без проверки ее протокола, предположений об участниках и привязки параметров.
  • Возможность для администратора заменить открытые параметры или версии аккумулятора без удостоверенных правил миграции.
  • Проверка свидетеля относительно устаревшего, не финализированного или выбранного злоумышленником значения аккумулятора.
  • Применение добавления, удаления или обновления свидетеля из неверного блока, форка, эпохи или версии множества.
  • Предположение, что свидетель членства также подтверждает действительность элемента, право собственности, авторизацию или экономическую ценность.
  • Предположение, что компактное обязательство обеспечивает доступность или восстановление исходного множества.
  • Утрата данных или сервиса, необходимых для построения актуальных свидетелей, из-за чего корректное состояние становится непригодным к использованию.
  • Отсутствие поддержки нечленства при неявной зависимости приложения от доказательств отсутствия.
  • Ошибочное представление о пути Меркла, свидетеле RSA, открытии полиномиального обязательства и доказательстве действительности как о взаимозаменяемых объектах.
  • Игнорирование стоимости удалений, трафика обновления свидетелей, задержки генерации доказательств или входных данных для атак типа «отказ в обслуживании».
  • Отсутствие привязки доказательств к протоколу, цепочке, контракту, корню состояния, домену и версии сериализации.
  • Опора на единственную реализацию без аудита или на собственную арифметику без независимых тестовых векторов.
  • Предположение, что классическая стойкость RSA, спариваний или дискретного логарифма сохранится при появлении криптографически значимого квантового компьютера.

Распространенные заблуждения

  • Аккумулятор содержит сжатую копию множества. Это связывающее обязательство, а не обратимый архив.
  • Любой аккумулятор доказывает отсутствие. Для нечленства нужна схема, специально разработанная и проверенная с учетом этой возможности.
  • Свидетель постоянного размера означает постоянные совокупные затраты. Настройка, генерация доказательств, обновления, хранение и распространение свидетелей остаются отдельными статьями затрат.
  • Отсутствие состояния означает, что состояние не хранит никто. Некоторым участникам необходимо хранить или восстанавливать достаточно данных для создания элементов, обновлений и свидетелей.
  • Действительное доказательство делает зафиксированный элемент истинным. Оно лишь связывает элемент с одним удостоверенным обязательством при заданных предположениях.
  • Деревья Меркла и RSA-аккумуляторы имеют одинаковые профили доверия и производительности. Они решают общую задачу обязательства для множества, но используют разные предположения, размеры доказательств, процедуры обновления и характеризуются разными видами отказов.

Связанные темы

Источники

Навигация

Поиск по вики...