PLONK: разбираем уязвимости криптографического протокола / forpes.ru

Главная
PLONK: разбираем уязвимости криптографического протокола

PLONK: разбираем уязвимости криптографического протокола +15

22.04.2026 13:49

coffee_with_snarks 0 4700 Источник

Привет, Хабр!

Я Ирина Слонкина из отдела безопасности распределенных систем Positive Technologies. Вместе с коллегами исследую безопасность смарт‑контрактов и блокчейн‑приложений. Конечно, всегда интересно вникнуть вглубь каждой технологии, вышедшей на рынок. В этой статье я расскажу про криптографический протокол PLONK, один из самых интересных протоколов в блокчейн‑индустрии.

PLONK (Permutations over Lagrange‑bases for Oecumenical Noninteractive arguments of Knowledge) — zk‑SNARK*, разработанный в 2019 году Ариэлем Габизоном и соавторами (Zachary J. Williamson, Oana Ciobotaru). PLONK позволяет доказать знание набора переменных, удовлетворяющего некоторой детерминированной программе (арифметической схеме), не разглашая их. Значения некоторых из этих переменных могут быть фиксированы. Например, можно доказать знание строки, хеш от которой равен определенному числу.

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

*_{zk‑SNARK (Succinct Non‑interactive ARgument of Knowledge, краткие неинтерактивные аргументы знания) — один из ключевых типов доказательств с нулевым разглашением наравне со STARKs (Scalable Transparent ARgument of Knowledge, краткие прозрачные аргументв знания), DARK (Diophantine Arguments of Knowledge, диофантовы аргументы знания) и Bulletproofs. Отличительными чертами являются небольшой размер доказательства (<1 КБ), высокая скорость верификации и необходимость доверенной настройки в начале протокола. Так как в PLONK используется универсальная доверенная настройка, его иногда выделяют из SNARK'ов в отдельный тип доказательства.}_{Вот здесь}_{можно почитать подробнее про zk‑SNARKs}_.

Арифметическая схема

Программа задается посредством арифметической схемы из n узлов, каждый из которых имеет два входа (a_i, b_i) и один выход (c_i) — элементы поля ? простого порядка. Между ними выполняется соотношение ,
где QL_i, QR_i — коэффициенты при каждом из входов, QO_i — при выходе, QM_i — при произведении входов и QC_i — при единице. Например, для второго узла представленной схемы коэффициент при входе a₂ равен 1, при b₂ — 2; монома, содержащего их произведение a₂b₂, в выражении нет, поэтому QM равняется 0; QC равняется трем, а выходу соответствует коэффициент −1.

Селекторы для примера арифметической схемы из рисунка выше

Помимо операций внутри узлов, важно закодировать соотношения между ними, а именно равенство между входами и выходами различных узлов. Для этого в мультипликативной группе поля ? выбирается элемент g порядка n (если такого не существует — минимального порядка, превышающего n) и строится подгруппа $H = \{1, g, \dots, g^{n-1}\}$ из n элементов, которыми индексируются узлы схемы и входы a_i. Ее смежные классы k₁H, k₂H исаользуются для индексации b_i и c_i.

Колонки таблицы SA, SB, SC изначально заполняются элементами H, k₁H и k₂H соответственно. Затем в ней меняются между собой местами индексы равных между собой элементов: c₁ и a₂ (розовые ячейки; с₁ изначально соответствовал индекс k₂, a₂ — индекс g), c₂ и b₃ (голубые ячейки; с₂ индексируется элементом k₂g, b₃ — k₁g₂).

Итак, арифметическая схема задается посредством наборов селекторов для каждого узла $(QL_i,QR_i,QO_i,QM_i,QC_i )_{i=1}^n$ и подстановки σ, кодирующей равенство между определенными переменными внутри схемы. В ходе предобработки для них с помощью базиса Лагранжа — $L_i(g^j) = \{ \matrix {1} \\ {0}$ , если i = j; 0 в противном случае — строятся многочлены

$\begin{alignat*}{3} q_L(X) &= \sum\limits_{i=1}^{n} QL_i L_i(X), \quad & q_M(X) &= \sum\limits_{i=1}^{n} QM_i L_i(X), \quad & q_O(X) &= \sum\limits_{i=1}^{n} QO_i L_i(X) \\[1ex] q_R(X) &= \sum\limits_{i=1}^{n} QR_i L_i(X), \quad & q_C(X) &= \sum\limits_{i=1}^{n} QC_i L_i(X), \quad & S_{\sigma_1}(X) &= \sum\limits_{i=1}^{n} SA(i) L_i(X) \\[1ex] S_{\sigma_2}(X) &= \sum\limits_{i=1}^{n} SB(i) L_i(X), \quad & S_{\sigma_3}(X) &= \sum\limits_{i=1}^{n} SC(i) L_i(X), \end{alignat*}$

которые в точке g^i-1, соответствующей узлу i, принимают значение селектора/подстановки qL_i, …, SC_j в этом узле.

Как работает протокол PLONK

На вход протокола PLONK подаются три разновидности параметров: входы доказывающего, входы проверяющего и общие входы.

Общие входы:
- задающие схему — $n,q_L( X),q_R( X),q_M(X),q_C(X),q_O(X),S_{σ_1}(X),S_{σ_2}(X),S{σ_3}(X)$
- общие переменные Public Input — например, значение хеш-функции, знание прообраза для которой доказывается;
- reference string ${[1]_1, x[1]_1, ... , x^{n+2}[1]_1}$ — базовая точка эллиптической кривой [1]₁, умноженная на различные степени секретного числа x. Само число х удаляется сразу же после формирования r.s. Если доказывающему нужно посчитать коммитмент (то есть значение какого-либо многочлена в точке x), он может сделать это, только складывая между собой компоненты r.s., домноженные на коэффициенты многочлена при соответствующих степенях. Так как дискретное логарифмирование на эллиптической кривой в общем случае сложная операция, а умножение и деление друг на друга для точек эллиптической кривой не определено, предоставление валидного коммитмента в случае безошибочной реализации протокола с близкой к единице вероятностью означает знание коэффициентов многочлена, а также принципиальную возможность домножить на них точку эллиптической кривой;
Входы доказывающего:
- весь набор переменных a_i, b_i, c_i — так называемый witness;
Входы проверяющего:
- $[qL]_1,[qR]_1,[qM]_1,[qC]_1,[qO]_1,[S_{σ_1}]_1,[S_{σ_2}]_1,[S_{σ_3}]_1,x[1]_2$ — коммитменты многочленов в точке x: (произведение базовой точки эллиптической кривой на qL(x)).

В ходе выполнения протокола доказывающий должен убедить проверяющего, что его набор назначений соответствует:

общим входам PI;
селекторам схемы;
подстановкам.

Для этого, в частности, требуется evaluation proof — доказательство того, что значение многочлена в заданной точке соответствует его коммитменту.

Доказательство соответствия селекторам

Корректные входы a_i, b_i и выходы c_i узлов схемы должны удовлетворять условию .

Из общих входов доказывающему доступны многочлены , в каждой точке, соответствующей узлу i, принимающие значения, равные соответствующим коэффициентам. В первом раунде он строит такие же многочлены для входов/выходов, а в третьем перемножает их между собой в соответствии с изначальным условием, получая многочлен $eq(X)=a(X)b(X)_{q_M}(X)+a(X)_{q_L}(X)+b(X)_{q_R}(X)+c(X)_{q_O}(X)+PI(X)+q_C(X)$ . Ожидается, что в каждой точке группы H он будет принимать значение 0. Для доказательства этого факта строится обнуляющий многочлен Z_H, корнями которого являются все элементы группы H. Если назначения удовлетворяют селекторам, многочлен eq(X) будет делиться на Z_H нацело. Этот факт доказывается с помощью коммитмента. Так как доказывающему не известно x, он не может посчитать числитель и знаменатель отдельно и произвести деление. В результате получается многочлен t(X).

Первые слагаемые многочленов a(X),b(X),c(X) вида (r_iX + r_j)Z_H служат для маскировки назначений. Они не влияют на делимость eq и позволяют выполнить условие zero knowledge: значение a(X) в определенной точке не дает информации о соответствующем назначении.

Раунд 1

$\begin{alignat*}{2} &r_i: \text{random} \\ &Z_H(X) = \prod\limits_{i=1}^{n} (X - g^i) \\ &a(X) = (r_1 X + r_2) Z_H(X) + \sum\limits_{i=1}^{n} a_i L_i(X) \\ &b(X) = (r_3 X + r_4) Z_H(X) + \sum\limits_{i=1}^{n} b_i L_i(X) \\ &c(X) = (r_5 X + r_6) Z_H(X) + \sum\limits_{i=1}^{n} c_i L_i(X) \\ &\text{Output: } [a]_1, [b]_1, [c]_1 \end{alignat*}$

В третьем раунде t(X) разбивается на три части в целях оптимизации.

Раунд 3

$\begin{alignat*}{2} eq(X) &= a(X)b(X)q_M(X) + a(X)q_L(X) + b(X)q_R(X) + c(X)q_O(X) + PI(X) + q_C(X) \\ t(X) &= \frac{eq(X)}{Z_H(X)} + \dots \\ t(X) &= t_{lo}(X) + X^n t_{mid}(X) + X^{2n} t_{hi}(X) \\[1ex] \text{Output}&: [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1 \end{alignat*}$

В интерактивном протоколе челленджи (случайные переменные) доказывающий получает от проверяющего. В неинтерактивном они заменяются хешами от переменной transcript, в которую при инициализации помещаются PI и common input, а после каждого раунда — новые компоненты доказательства. С помощью transcript доказывающий и проверяющий могут генерировать одинаковые случайные переменные: первый — в ходе создания доказательства, второй — в ходе его проверки. В реализациях со слабым преобразованием Фиата — Шамира в transcript отсутствуют некоторые входы протокола, что позволяет сгенерировать их уже после доказательства.

Доказательство соответствия PI

Многочлен PI(X), построенный аналогичным образом, входит в eq(X) в качестве слагаемого. Поправка на PI закладывается в многочлен qC(X) на этапе его генерации из селекторов схемы.

Доказательство соответствия подстановке

Даны две последовательности . Утверждается, что они одинаковы. Как можно проверить этот факт без использования понятия упорядоченности?

В PLONK для этих целей вводится индексация последовательностей с помощью компонентов witness: . Задав случайные коэффициенты β и ɣ, можно поставить в соответствие последовательностям произведения: ...

Если последовательности идентичны — сравнение $\prod\limits_{i=1}^{n} \frac{(a_i + \beta g^{i-1} + \gamma)}{(a_i + \beta SA_i + \gamma)} \stackrel{?}{=} 1$ будет

выполнено. Обратное в общем случае неверно, но вероятность «ложного срабатывания» достаточно мала, особенно если коэффициенты действительно случайны и неподконтрольны доказывающему.

Во втором раунде формируется многочлен ρ(X), соответствующий значению выражения под произведением в левой части этого сравнения (за тем исключением, что, кроме левых входов, включает также правые входы и выходы). Но доказывающий не может просто перемножить ρ(X) для всех X∈H и отправить коммитмент для 1.

Раунд 2

$\begin{flalign*} &\beta = H(transcript, 0), \gamma = H(transcript, 1) &\\ &f(X) = (a(X) + \beta X + \gamma)(b(X) + \beta k_1 X + \gamma)(c(X) + \beta k_2 X + \gamma) &\\ &q(X) = (a(X) + \beta \sigma(X) + \gamma)(b(X) + \beta k_1 \sigma(X) + \gamma)(c(X) + \beta k_2 \sigma(X) + \gamma) &\\ &\rho(X) = \frac{f(X)}{q(X)} &\\ &z(X) = (r_7 X^2 + r_8 X + r_9) Z_H(X) + L_1(X) + \sum\limits_{i=1}^{n-1} L_{i+1}(X) \prod\limits_{j=1}^{i} \rho(g^j) &\\ &\text{Output}: [z]_1 & \end{flalign*}$

Для доказательства с помощью базиса Лагранжа строится многочлен z(X), для каждого элемента множества H равный произведению $z(g^i) = \rho(g) \dots \rho(g^{i-1}):$

$\begin{flalign*} &z(g) = 1, \quad z(g^2) = \rho(g), \quad z(g^3) = \rho(g)\rho(g^2), \quad..., \quad &z(g^n) = z(1) = \rho(g)\rho(g^2) \dots \rho(g^{n-1}). & \end{flalign*}$

Доказывающему необходимо доказать, что:

=1, то есть $\forall X \in H \quad L_1(X)(z(X) - 1) = 0$ ;
корректны все шаги по построению , то есть $\forall X \in H \quad z(Xg) = z(X)\rho(X)$ .

Это делается в третьем раунде с помощью уже упоминавшегося здесь многочлена t(x): второй его компонент доказывает второе утверждение, а третий — первое. Если числитель не обнуляется во всех точках H — он не делится на Z_H нацело, а следовательно, для него не может быть вычислен коммитмент в секретной точке x с использованием reference string.

Раунд 3

$\begin{flalign*} &\alpha = H(transcript) &\\ &t(X) = \frac{eq(X)}{Z_H(X)} + \alpha \frac{f(X)z(X) - q(X)z(Xg)}{Z_H(X)} + \alpha^2 \frac{(z(X) - 1)L_1(X)}{Z_H(X)} &\\ &t(X) = t_{lo}(X) + X^n t_{mid}(X) + X^{2n} t_{hi}(X), &\\ &\text{Output}: [t_{lo}]_1, [t_{mid}]_1, [t_{hi}]_1 & \end{flalign*}$

Evaluation proof

В ходе выполнения протокола проверяющий должен непосредственно убедиться, что все полученные им коммитменты вычислены верно и соответствуют друг другу. Для этого проверяющий самостоятельно повторяет действия доказывающего, составляя компоненты доказательства из коммитментов. Так как проверяющий не может перемножать между собой коммитменты (точки на эллиптической кривой) и не должен выполнять вычислительно сложные действия, доказывающий вычисляет целочисленные evaluations — открывает значения компонентов доказательства в случайной точке $\zeta: \bar{a} = a(\zeta), \quad \bar{b} = b(\zeta), \quad \bar{c} = c(\zeta), \quad \bar{s}{\sigma_1} = S{\sigma_1}(\zeta), \quad \bar{s}{\sigma_2} = S{\sigma_2}(\zeta)$ ,

после чего формирует линеаризационный многочлен R(X), заменяя в числителе t(x) многочлены на их evaluations $\bar{a}, \bar{b}, \bar{c}, \bar{s}{\sigma_1}, \bar{s}{\sigma_2}, \bar{z}$ .

В пятом раунде доказывается соответствие evaluations ранее сформированным коммитментам. Согласно теореме Безу, многочлен F(X)−F(ζ) делится без остатка на X−ζ. Только в этом случае доказывающий может вычислить коммитмент для частного (F(X)−F(ζ))/(X−ζ). Аналогичным образом W_zg(Х) служит для доказательства значения z(X) в точке ζg.

Раунд 4

$\begin{flalign*} &\zeta = H(transcript) &\\ &\bar{a} = a(\zeta), \quad \bar{b} = b(\zeta), \quad \bar{c} = c(\zeta), \quad \bar{s}_{\sigma_1} = S_{\sigma_1}(\zeta), \quad \bar{s}_{\sigma_2} = S_{\sigma_2}(\zeta), \quad \bar{z}_g = z(\zeta g) &\\ &\text{Output: } \bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma_1}, \bar{s}_{\sigma_2}, \bar{z}_g & \end{flalign*}$

Раунд 5

$\begin{align*} R(X) &= (\bar{a}\bar{b}q_M(X) + \bar{a}q_L(X) + \bar{b}q_R(X) + \bar{c}q_O(X) + q_C(X)) \\ &+ \alpha(\bar{a} + \beta\zeta + \gamma)(\bar{b} + \beta k_1\zeta + \gamma)(\bar{c} + \beta k_2\zeta + \gamma) z(X) \\ &- \alpha(\bar{a} + \beta\bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma)(\bar{c} + \beta S_{\sigma_3}(X) + \gamma)\bar{z}_g \\ &+ \alpha^2 (z(X) - 1) L_1(X) \\ r(X) &= R(X) - Z_H(X)(t_{lo}(X) + \zeta^n t_{mid}(X) + \zeta^{2n} t_{hi}(X)) \\ v &= H(transcript) \\ W_\zeta(X) &= \frac{1}{X - \zeta} \left( r(X) + v(a(X) - \bar{a}) + v^2(b(X) - \bar{b}) + v^3(c(X) - \bar{c}) + v^4(S_{\sigma_1}(X) - \bar{s}_{\sigma_1}) + v^5(S_{\sigma_2}(X) - \bar{s}_{\sigma_2}) \right) \\ W_{\zeta g}(X) &= \frac{z(X) - \bar{z}_g}{X - \zeta g} \\ &\text{Output: } [W_\zeta]_1, [W_{\zeta g}]_1 \end{align*}$

Проверка доказательства

В ходе проверки в первую очередь определяется принадлежность компонентов доказательства заявленному множеству, затем с помощью transcript из общих входов, PI и компонентов доказательства вычисляются челленджи $\beta, \gamma, \alpha, \zeta, v$ , равные аналогичным челленджам доказывающего, и u. Вычисляются

$Z_H(\zeta) = \zeta^n - 1, \quad L_1(\zeta) = \frac{\zeta^n - 1}{n(\zeta - 1)}, \quad PI(\zeta) = \sum\limits_{i=1}^{l} L_i(\zeta) w_i$

Затем проверяющий повторяет вычисление r(X), в целях оптимизации разбивая его на две части: полиномиальную r’(X) и константную . формируется из самостоятельно вычисленных челленджей, значений многочленов в точке и полученных от доказывающего evaluations; при построении r’(X) также используются коммитменты для cелекторов и подстановок из входов проверяющего и коммитменты для $[z]_1, [t{_lo}]_1, [t_{mid}]1, [t_{hi}]_1$ , переданные доказывающим:

$\begin{align*} r_0 &= PI(\zeta) - L_1(\zeta)\alpha^2 - \alpha(\bar{a} + \beta \bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma)(\bar{c} + \gamma) \bar{z}_g \\ [r']_1 &= \bar{a}\bar{b}[q_M]_1 + \bar{a}[q_L]_1 + \bar{b}[q_R]_1 + \bar{c}[q_O]_1 + [q_C]_1 + \alpha^2 L_1(\zeta)[z]_1 \\ &+ \alpha(\bar{a} + \beta\zeta + \gamma)(\bar{b} + \beta k_1 \zeta + \gamma)(\bar{c} + \beta k_2 \zeta + \gamma)[z]_1 \\ &- \alpha(\bar{a} + \beta \bar{s}_{\sigma_1} + \gamma)(\bar{b} + \beta \bar{s}_{\sigma_2} + \gamma)\beta [s_{\sigma_3}]_1 \bar{z}_g \\ &- Z_H(\zeta)([t_{lo}]_1 + \zeta^n [t_{mid}]_1 + \zeta^{2n} [t_{hi}]_1) \end{align*}$

После этого проверяющий формирует из коммитментов и evaluations аналог $W_\zeta (_X - \zeta) + uW{_\zeta g}(X - \zeta g)$ :

$\begin{align*} [D]_1 &= [r']_1 + u[z]_1 \\ [F]_1 &= [D]_1 + v[a]_1 + v^2[b]_1 + v^3[c]_1 + v^4[s_{\sigma_1}]_1 + v^5[s_{\sigma_2}]_1 \\ [E]_1 &= (-r_0 + v\bar{a} + v^2\bar{b} + v^3\bar{c} + v^4\bar{s}_{\sigma_1} + v^5\bar{s}_{\sigma_2} + u\bar{z}_g)[1]_1 \end{align*}$

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

$e([W_\zeta]_1 + u[W{_\zeta g}]_1, [x]_2) \stackrel{?}{=} e(\zeta[W_\zeta]_1 + u\zeta g[W{_\zeta g}]_1 + [F]_1 - [E]_1, [1]_2)$

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

тождественность: e(P,P) = 1;
билинейность — спаривание суммы равняется произведению спариваний по любому из аргументов:

$\begin{flalign*} &e(P_1 + P_2, Q) = e(P_1, Q)e(P_2, Q) &\ &e(P, Q_1 + Q_2) = e(P, Q_1)e(P, Q_2) & \end{flalign*}$

следствие билинейности — коэффициент при любом из аргументов можно вынести как степень спаривания:
невырожденность: $e(P, Q) \neq 1 \quad \forall P, Q \mid P \neq \mathcal{O}, Q \neq \mathcal{O}$ ;
существование эффективного алгоритма вычисления.

Как правило, в реализациях протокола используется спаривание Вейля.

Сравнение спариваний соответствует проверке следующего утверждения:

$W_\zeta x + uW_{\zeta g} x \stackrel{?}{=} \zeta W_\zeta + u\zeta g W_{\zeta g} + F - E \implies W_\zeta (x - \zeta) + uW_{\zeta g} (x - \zeta g) \stackrel{?}{=} F - E$

Итак, мы разобрались, как устроен PLONK. Далее речь пойдет про уязвимости протокола.

Некоторые известные уязвимости PLONK

Отсутствие маскирующих многочленов

Эта уязвимость приводит к нарушению свойства нулевого разглашения (см. доказательство соответствия селекторам), при этом эксплуатация ее на практике для подбора witness слишком вычислительно сложна для практического осуществления атаки.

Пример исправленной уязвимости в коде Dusk Network

Frozen Heart

Проверяющий не знает witness и не может непосредственно проверить соответствие ему всех компонентов доказательства. Пользуясь этим, нечестный доказывающий может выбрать случайные $a(X), b(X), c(X), t_{lo}(X), t_{mid}(X), t_{hi}(X)$ и вычислить соответствующие им коммитменты $[a]_1, [b]_1, [c]_1, [t{_lo}]_1, [t_{mid}]_1, [t_{hi}]_1$ , в конце каждого раунда добавляя их к доказательству и к transcript и получая псевдослучайные челленджи $\beta, \gamma, \alpha, \zeta, v$ . В случае если transcript не была инициализирована с помощью PI, доказывающий может вычислить PI уже после доказательства и осуществить подмену, если архитектура приложения этому благоприятствует (проверяющий принимает PI от доказывающего, как, например, было в snarkjs до исправления уязвимости):

$\begin{align*} \sum\limits_{i \in I_1 \cup I_2 \cup I_3} PI_i L_i(\zeta) &= Z_H(\zeta)(t_{lo}(\zeta) + \zeta^n t_{mid}(\zeta) + \zeta^{2n} t_{hi}(\zeta)) - eq'(\zeta) - \alpha per(\zeta) - \alpha^2(z(\zeta)-1)L_1(\zeta), \\ eq'(\zeta) &= a(\zeta)b(\zeta)q_M(\zeta) + a(\zeta)q_L(\zeta) + b(\zeta)q_R(\zeta) + c(\zeta)q_O(\zeta) + q_C(\zeta) \\ per(\zeta) &= (a(\zeta) + \beta\zeta + \gamma)(b(\zeta) + \beta k_1\zeta + \gamma)(c(\zeta) + \beta k_2\zeta + \gamma)z(\zeta) - \\ &- (a(\zeta) + \beta\sigma(\zeta) + \gamma)(b(\zeta) + \beta k_1\sigma(\zeta) + \gamma)(c(\zeta) + \beta k_2\sigma(\zeta) + \gamma)z(\zeta g) \end{align*}$

Авторы этой статьи проанализировали 12 реализаций PLONK. В пяти была обнаружена уязвимость, в четырех из них она была исправлена к моменту публикации статьи. Для демонстрации атаки авторы выбрали Dusk Network — сохраняющий приватность распределенный ledger-протокол, использующий основанную на UTXO модель транзакций Phoenix, работающая с записями (notes), которые хранит ledger. Упрощенно, каждая запись является коммитментом для некоторого значения. Транзакция состоит из множества входных записей (in₁, . . . , in_m), множества новосформированных выходных записей (out₁, . . . , out_n) и доказательства корректности. Чтобы потратить запись, создатель транзакции должен раскрыть ее nullifier (идентификатор входа, позволяющий предотвратить двойное расходование), при этом не разглашая саму запись. В Dusk nullifier вычисляется как хеш индекса записи в дереве Меркла.

Секретным входом доказывающего (witness) являются входные записи, их openings, пути в дереве Меркла и openings для выходных записей. Целью доказательства является подтверждение того, что каждый nullifier соответствует валидной входной записи, каждая входная запись имеет валидный путь к корню дерева Меркла и выходные суммы равны входным.

Исправленная уязвимость в коде Dusk Network

Атака на слабое преобразование Фиата — Шамира позволила получить валидное доказательство для транзакции с выбранным произвольно nullifier (единственная проверка, которой подвергается эта переменная, — проверка того, что ранее то же значение не использовалось). Таким образом, атакующий мог переводить себе произвольные суммы с несуществующих входов.

00 bug

Критическая уязвимость в Aztec PLONK Verifier, обнаруженная вьетнамским исследователем по имени Нгуен Тхой Минь Куан, в результате которой любое доказательство принималось как валидное, если $[W_\zeta]_1, [W{_\zeta g}]_1$ были равны точке на бесконечности O эллиптической кривой. Атака стала возможной благодаря сразу нескольким ошибкам в реализации проверки доказательства.

Проверяющий убеждается в том, что точки $[W_\zeta]_1, [W{_\zeta g}]_1$ лежат на кривой, но в противном случае его программа не прекращает работу мгновенно, как следовало бы, а исключает нулевые точки из некоторых последующих вычислений. Финальная проверка при этом все равно осуществляется;
В другом фрагменте кода, призванном исключить возможность того, что $[W_\zeta]_1 + u[W_{\zeta g}]_1$ является точкой на бесконечности, проверяется, что старший значащий бит точки не равен 1, но точка проходит проверку;
Для инверсии по модулю p используется метод, основанный на малой теореме Ферма. Так как входные данные не проверяются на корректность, обратным для 0 оказывается 0^(p-2) = 0, что математически некорректно;
Перед проверкой спаривания Вейля осуществляется переход от проективных координат точек (x, y, z) к аффинным (z=1). В этих целях используется пакетная нормализация, в результате которой ненулевая точка также становится нулевой под влиянием $[W_\zeta]_1 + u[W{_\zeta g}]_1$ , и финальная проверка сводится к $e(O, [x]_2) \stackrel{?}{=} e(O, [1]_2)$ ;
В завершение, если точка не лежит на кривой согласно первой проверке и не является точкой на бесконечности согласно второй, по логике verifier результат ее спаривания с любой точкой равняется 1.

Заключение

Хорошо исследованные криптографические протоколы не гарантируют безопасность продукта. Атаки на преобразование Фиата — Шамира показали, что ошибки реализации в современных zk-приложениях могут привести к нарушению свойства нулевого разглашения, создать возможность формирования валидного доказательства без обладания соответствующим знанием и в прикладном сценарии даже открыть путь к созданию неограниченного количества валюты. Более того, сама исходная спецификация PLONK потребовала исправления, чтобы корректно обеспечить заявленное свойство нулевого разглашения.

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

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

Полезные материалы по теме

Gabizon A., Williamson Z. J., Ciobotaru O.
PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive Arguments of Knowledge. — 2019. https://eprint.iacr.org/2019/953.pdf.

The Trail of Bits blog.
The Frozen Heart vulnerability in PlonK. — 2022. https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/.

Dusk.
PLONK Critical Vulnerability Successfully Remediated. — 2022. https://dusk.network/news/plonk-vulnerability-remediated.

Dao Q., Miller J. и др.
Weak Fiat-Shamir Attacks on Modern Proof Systems. — 2023. https://eprint.iacr.org/2023/691.pdf.

Sefranek M.
How to Simulate PLONK: A Formal Security Analysis of a zk-SNARK. — 2023. https://repositum.tuwien.at/bitstream/20.500.12708/188597/1/Sefranek%20Marek%20-%202023%20-%20How%20to%20Simulate%20PLONK%20A%20Formal%20Security%20Analysis%20of%20a...pdf.

Sefranek M.
How (Not) to Simulate PLONK. — 2024. https://eprint.iacr.org/2024/848.pdf.

Nguyen Q. T. M.
00: A Critical Vulnerability in Aztec PLONK Verifier. — 2021. https://eprint.iacr.org/2021/1638.
0xPARC.
zk-bug-tracker: https://github.com/0xPARC/zk-bug-tracker.

Dusk Network.
Check the zero-knowledge property of PlonK. — GitHub issue #773. https://github.com/dusk-network/plonk/issues/773.
The Risen Crypto blog. PlonK. https://risencrypto.github.io/Plonk/