Обратная сторона zero knowledge: бэкдор в zk-SNARK, который невозможно обнаружить

[Disasm]

Насколько я помню, в zk-SNARK доказательство нельзя построить без уравнения (или, если точнее, то системы ограничений), а значит, это уравнение известно всем. Что мешает проверить, что оно получено из "честного" исходного кода?

Кроме того, в отличие от оригинальной идеи zk-SNARK, в Zcash применён распределённый алгоритм генерации начальных параметров, который призван исключить ситуацию с сохранением "токсичных" данных (если только все участники генерации не окажутся "предателями").

[DryginAlexander]

По первой части:

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

Тё доказательство строится на основе публичных параметров (известных всем), но это не исходная задача.

По второй: действительно, в Zcash используется распределённый алгоритм генерации (церемония). Её безопастность/корректность это тема для отдельного исследования и соотвественно статьи. Выше лишь описываются проблемы, которые она должна решать.

[Disasm]

Тё доказательство строится на основе публичных параметров (известных всем), но это не исходная задача.

А вы смотрели, что входит в эти публичные параметры? Для генерации доказательства нужен prover key (про который мы ничего не можем сказать) и функция (уравнение) вместе с R1CS. Без функции вы не сможете сгенерировать подтверждающие значения для системы R1CS (ровно как и без самой R1CS). Так что мешает эту функцию проверить на соответствие исходной задаче?

[DryginAlexander]

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

[Disasm]

Размер prover key непосредственно зависит от количества уравнений в системе R1CS. Как вы собираетесь генерировать prover key, который подойдёт и для этой системы и для другой?

[DryginAlexander]

Вы правы, удалил недостоверную информацию из статьи. Спасибо за ваши комментарии.

[eup]

На смену zk-SNARKs и STARKs уже приходят Bulletproofs (можно найти в Monero, Grin), такие же не интерактивные док-ва с нулевым разглашением, но которые при этом не требуют установки доверенных параметров, избавляя всех от паранойи. В проекте bulletproofs-dalek вообще скоро реализуют возможность помимо range proof генерировать доказательства для любой заранее заданной R1CS, как это сейчас позволяют делать zk-SNARKs, для любых арифметических цепей.