Generalized Bulletproofs и дивизоры

На чём держится доказательство пути в дереве — без доверенного setup

Что такое «арифметическая схема»

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

В Bulletproofs схема простая и фиксированная: «эти 64 числа — биты, и они складываются в сумму». В FCMP++ схема сложнее: на каждом уровне дерева нужно проверить, что выбранный ребёнок есть среди детей узла и что узел правильно вычислен из детей.

Generalized Bulletproofs

Обычные Bulletproofs принимают на вход отдельные обязательства Педерсена. Generalized Bulletproofs (Eagen, Kamp, Parker и др.) позволяют подавать в схему векторные обязательства — одна точка фиксирует сразу много чисел. Это ровно то, что нужно для дерева: «хеш» узла и есть векторное обязательство к координатам его детей (см. Curve Trees). Схема получает узел как вход и может рассуждать о его содержимом.

Свойства те же, что и у Bulletproofs:

• нет доверенного setup;
• размер доказательства растёт логарифмически от размера схемы;
• проверка линейна по размеру схемы, но хорошо пакетируется (batch verification) — проверка многих доказательств сразу дешевле, чем по одному.

Проблема: умножение точки на скаляр внутри схемы

Перерандомизация требует проверить в схеме что-то вида Õ = O + r_o·T. Умножение точки на 255-битный скаляр «в лоб» — это сотни удвоений и сложений точек, каждое из которых — несколько умножений в поле. В схеме это тысячи ограничений на одну операцию, и доказательство стало бы огромным.

Дивизоры: проверять, а не вычислять

Идея Лиама Игена (Liam Eagen, «Zero Knowledge Proofs of Elliptic Curve Inner Products from Principal Divisors and Weil Reciprocity»): чтобы убедиться, что набор точек P₁ … Pₙ складывается в ноль, не нужно их складывать. Достаточно предъявить рациональную функцию f на кривой, у которой нули ровно в этих точках (её дивизор), и проверить одно алгебраическое тождество в случайной точке (вызов от проверяющего).

Умножение r·T записывается как сумма Σ bᵢ·(2ⁱ·T) по битам r, то есть как сумма точек, — и проверяется одним дивизором. Количество ограничений падает примерно на порядок.

Две схемы — две кривые

Уровни дерева чередуются между Selene и Helios. Арифметика каждого уровня естественна в поле одной из кривых, поэтому membership proof состоит из двух Generalized Bulletproofs: один над Selene (уровни Selene и проверка перерандомизации листа, координаты которого — элементы поля Ed25519), второй над Helios. Связь между ними — через общие перерандомизированные узлы.

Размер и стоимость

Размер доказательства зависит от глубины дерева и ширины узлов. При сотнях миллионов выходов и ширине узлов в десятки детей глубина — несколько уровней. Ориентировочно один вход FCMP++ занимает несколько килобайт, а проверка на порядок дороже CLSAG; разработчики оптимизируют и то, и другое (пакетная проверка, многовходовые доказательства). Точные цифры — в отчётах о бенчмарках к релизу.