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

    Используя протокол доказательства с нулевым разглашением из семейства SNARK, вы никогда не знаете правил игры. Эти правила устанавливают участники процедуры генерации доверенных параметров системы, однако после её завершения проверить эти правила не представляется возможным. Вы можете поверить в корректность генерации, но, если вы в ней не участвовали, стопроцентных гарантий у вас нет.



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

    Одним из наиболее изученных, а что важнее — реализованных является семейство протоколов zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge). Такой протокол используется, в частности, в криптовалюте Zcash. Популярность SNARK оправдана: протокол позволяет нам доказывать факты с нулевым разглашением, доказательства относительно невелики, и всё это с гарантиями безопасности, которые даёт нам современная криптография на эллиптических кривых.

    Однако без минусов, как обычно, не обошлось: основным недостатком этого семейства zk-протоколов является необходимость в генерации начальных (доверенных) параметров системы — этот процесс также называют церемонией. Ведь для генерации используются подлежащие уничтожению секретные параметры — их называют токсичными. Главная проблема заключается в том, что в случае сохранения токсичных параметров, владеющий ими сможет доказывать ложные факты (в случае с Zcash — генерировать криптовалюту из воздуха).

    Генерация начальных параметров


    Далее будет лишь поверхностно затронута математика, лежащая в основе SNARK протоколов. Если вам интересно в ней разобраться — советую цикл статей от Виталика Бутерина на эту тему.

    Давайте рассмотрим процесс генерации доверенных параметров. Итак, у нас есть постановка задачи, факт решения которой мы хотим доказывать с нулевым разглашением. Например, мы хотим проверять знание корня квадратного уравнения:

    $x^2-6x+5 = 0$


    По протоколу мы должны привести это уравнение к QAP (Quadratic Arithmetic Programs) виду. Далее для генерации и проверки доказательств необходимо получить начальные параметры. Оставим за скобками то, как из QAP получаются доверенные параметры, что это за параметры и как именно с их помощью можно проверять доказательства, чтобы не углубляться в тяжёлую математику. Отметим лишь, что параметры представлены в виде точек на эллиптической кривой:


    Получены они из постановки задачи в виде QAP при помощи необратимой операции умножения на эллиптической кривой с использованием токсичных параметров.

    Теперь, когда начальные параметры созданы, мы можем начать работу с доказательствами. В нашем случае можно сгенерировать и проверить доказательство того, что известен корень уравнения (например, $x = 1$). При этом доказательство не будет раскрывать значение секрета (корня уравнения) и будет состоять из нескольких точек эллиптической кривой.

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

    Церемония


    Серьезные проекты, использующие SNARK протоколы, отлично осведомлены о существовании проблемы токсичных параметров и со всей серьезностью относятся к корректности процедуры генерации начальных параметров. Самый известный пример — это церемония Zcash.

    Первая церемония прошла в октябре 2016 года, в ней приняли участие 6 известных разработчиков из криптовалютного сообщества. Протокол церемонии предоставляет достаточные гарантии безопасности. А именно, если хотя бы один участник церемонии будет честным — правильно уничтожит свою часть токсичных параметров — и не будет взломан, то церемония будет безопасной.

    Вторая, более совершенная церемония генерации доверенных параметров прошла в 2017-2018 годах. Она состояла уже из двух этапов, в первой части (Powers of Tau) приняли участие 87 человек, а в финальной части (Sapling MPC) более 90 человек. Как и в случае с оригинальной церемонией, при честности хотя бы одного участника церемония может считаться безопасной. Важной особенностью второй церемонии было то, что стать участником мог любой желающий. Таким образом, шанс получить стопроцентные гарантии корректности протокола был у всех.

    В заключение стоит отметить, что критичность церемонии и вытекающих из неё угроз следует рассматривать отдельно для каждой конкретной системы. И в то же время, для всех систем, использующих SNARK протоколы, необходима надежная процедура генерации начальных параметров с гарантиями уничтожения токсичных параметров.
    • +39
    • 7,8k
    • 7
    Ростелеком-Solar
    138,00
    Безопасность по имени Солнце
    Поделиться публикацией

    Комментарии 7

      +2

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


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

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

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

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

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

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

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

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

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

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое