Curve Trees, Helios и Selene

Дерево Меркла, в котором вместо хешей — точки, а доказательство пути занимает килобайты

Дерево Меркла: напоминание

Дерево Меркла хеширует данные попарно (или группами), потом хеширует хеши, и так до одного корня. Чтобы доказать, что элемент есть в дереве, достаточно показать путь — соседей на каждом уровне. Путь длины log n.

Но нам нужно доказать путь с нулевым разглашением — не показывая ни лист, ни соседей. Для этого надо закодировать «вычисление хеша» в арифметическую схему и доказать её. Обычные хеши (Keccak, SHA) в таких схемах очень дорогие: десятки тысяч ограничений на один хеш.

Идея Curve Trees

Возьмём в качестве «хеша» векторное обязательство Педерсена:

Это хорошая хеш-функция для наших целей (найти коллизию так же трудно, как решить дискретный логарифм), и в арифметической схеме она почти бесплатна — если числа xᵢ являются скалярами той кривой, на которой лежат Gᵢ.

Проблема: дети — точки на кривой E₁, их координаты — элементы базового поля E₁. Чтобы использовать их как скаляры, нужна кривая E₂, у которой скалярное поле = базовое поле E₁. А на следующем уровне — наоборот. Пара таких кривых называется циклом кривых.

Helios и Selene

Для Monero подобрали специальный цикл, «привязанный» к Ed25519: координаты точек Ed25519 живут в поле F_p, p = 2²⁵⁵ − 19, и у одной из кривых цикла (Selene) скалярное поле — ровно это F_p. Поэтому листья (координаты O, I, C на Ed25519) можно сразу «хешировать» на Selene, затем координаты точек Selene — на Helios, и так далее, чередуясь.

Названия — от греческих богов Солнца (Гелиос) и Луны (Селена): две кривые, которые «вращаются» друг вокруг друга.

Как доказывается путь

Для каждого уровня доказывающий показывает не саму точку-родителя, а её перерандомизацию (точку + случайное кратное ещё одного генератора), и доказывает в схеме над соответствующей кривой:

1. «я знаю детей, один из которых — перерандомизированная точка предыдущего уровня»;
2. «эти дети в сумме с генераторами дают (перерандомизированного) родителя».

Чтобы проверять операции на кривой внутри схемы эффективно, используются дивизоры (техника Liam Eagen): вместо пошагового умножения точки на скаляр доказывается свойство рациональной функции на кривой, что гораздо дешевле. Подробнее — Generalized Bulletproofs и дивизоры.

Все уровни над одной кривой доказываются одним Generalized Bulletproof, над другой — вторым. Итог — два доказательства, размер которых растёт с глубиной дерева, то есть логарифмически от числа выходов.

Обновление дерева

Когда выход проходит 10-блочную блокировку, узел добавляет его в дерево и пересчитывает путь до корня. Векторное обязательство обновляется инкрементально: добавить ребёнка — значит прибавить к родителю x·Gᵢ, без пересчёта остальных. При реорганизации цепочки изменения откатываются.