Преамбула
В контексте блокчейна zk-SNARK — это передовая технология безопасности, которая повышает конфиденциальность и обеспечивает прозрачность криптографических транзакций.
Zk-SNARK позволяет доказать знание, не раскрывая эти знания, сохраняя информацию пользователя абсолютно защищенной.
Zcash, ведущая криптовалюта, использует технологию zk-SNARK для полной анонимизации транзакций, обеспечивая высокий уровень безопасности и не раскрывая личную информацию пользователей. Это повышает безопасность и надежность пользователей при совершении онлайн-транзакций.
В первой части серии исследований «Изучение ZK-SNARK» я подробно и легко для вас углублюсь в важные детали о zk-SNARK, а также в базовые алгоритмы и шифрование, лежащие в основе этой технологии.
Концепция и механизм действия зк-СНАРК
Основы zk-СНАРК
Zk-SNARK расшифровывается как Краткий неинтерактивный аргумент знания с нулевым разглашением, что примерно переводится как «Краткое и неинтерактивное доказательство раскрытия незнания» (я перевел это так для простоты понимания). Это конструкция доказательства, которая позволяет одной стороне (доказывающему) доказать, что она обладает определенной информацией, например секретным ключом, без необходимости раскрывать эту информацию и не требуя сотрудничества с другой стороной (проверяющей).
В настоящее время zk-SNARK является самой популярной используемой системой доказательств.
Мы разобьем аббревиатуру "zk-SNARK" на более мелкие компоненты, чтобы наиболее четко понять их значение.
«Нулевое разглашение»: это означает, что входная информация будет скрыта и не будет раскрыта проверяющему лицу. Другими словами, проверяющий не может знать ничего об этих знаниях, кроме их достоверности.
«Краткий» (короткий): это означает, что сгенерированные доказательства имеют небольшой размер, около нескольких сотен байт, и проверяются быстро. Это первое преимущество, которое приносит SNARK.
«Неинтерактивный»: это второе преимущество SNARK, обе стороны (доказывающий и проверяющий): доказательство состоит из одного сообщения от доказывающего к проверяющему без необходимости двусторонней связи.
«Аргумент знания»: технический термин, означающий, что если проверяющий принимает доказательство, то доказывающий действительно должен знать секрет, связанный с утверждением, которое доказывается проверкой (вместо того, чтобы просто убеждать проверяющего в том, что утверждение верно).
Механизм действия
Математически zk-SNARK состоит из 3 алгоритмов:
Генерация ключей (KG): это алгоритм генерации ключей, который генерирует пару ключей: один для доказательства (pk) и один для проверки (vk). Алгоритм генерации ключей принимает на вход параметр безопасности λ и программу C, а затем выводит ключи. Этот шаг также называется этапом доверенной настройки. Мы углубимся в подробности в следующем разделе. (pk, vk) = KG(λ, C)
Доказательство (P): Этот алгоритм доказательства будет доказывать, принимая в качестве входных данных ключ доказательства pk, утверждение x и свидетеля w. Результатом является доказательство prf.prf = P(pk, x, w)
Проверка (V): Алгоритм проверки принимает на вход ключ проверки vk, оператор x и доказательство prf. Выход — принять или отклонить.
Результат проверки = V(вк, х, прф)
Преимущества ЗК-СНАРК
ZK-SNARKs приносят множество важных преимуществ, особенно в плане повышения анонимности, безопасности, масштабируемости и эффективности транзакций в различных приложениях. Вот два ключевых преимущества программных приложений:
Конфиденциальность: атрибут «нулевого разглашения» позволяет скрыть конфиденциальные данные, связанные с расчетами, при этом доказывая правильность утверждения. Другими словами, zk-snark выполняет транзакции, не раскрывая личную информацию, сохраняя анонимность и безопасность информации о транзакциях. Это полезно в таких криптовалютах, как Zcash, где пользователи могут отправлять средства, не раскрывая сумму, происхождение или назначение транзакций.
Масштабируемость: благодаря небольшому размеру доказательства и короткому времени проверки проверяющее лицо быстро узнает, что вычисление было выполнено точно, без необходимости повторного запуска вычисления, тем самым сокращается время и ресурсы, необходимые для проверки сложных вычислений, что повышает производительность и надежность системы. а также помогает снизить затраты и повысить масштабируемость.
Церемония доверительной установки
Процесс установления доверия — это важный шаг, выполняемый только один раз для создания необходимого набора данных, которые будут использоваться позже при каждом развертывании криптографических протоколов.
В ZK-SNARK этот шаг настройки доверия необходим для создания ключей доказательства и проверки. Эти ключи затем становятся общедоступными, что позволяет участникам использовать их для создания и проверки доказательств.
Для каждой новой программы на C необходимо выполнить новую доверенную настройку, поскольку она зависит от деталей этой программы на C. Во время установки процесс генерации ключа KG использует секретную лямбду и программу C в качестве входных данных для генерации открытого ключа (pk) и ключа проверки (vk).
(pk, vk) = KG(λ, C)
Поэтому процесс надежной установки не является стандартным и должен проводиться отдельно для каждой новой программы.
Токсичные отходы (Токсичные отходы)
Для надежной настройки необходим секретный параметр под названием lamda . Этот параметр, часто называемый «токсичными отходами», иногда затрудняет применение zk-SNARK в практических целях.
Это потому, что тот, кто владеет этим параметром, имеет возможность создавать фальшивые доказательства. В частности, держатель лямбды может сгенерировать поддельное доказательство, называемое fakeProof, для любой программы C с общедоступными входными данными x, например, что
V(vk,x,fakeProof)=истина
признано правдивым без знания тайного свидетеля w. Это катастрофа!
Самый эффективный способ сгенерировать общедоступные параметры для zk-SNARK – создать пару открытого и закрытого ключей, аналогичную паре ключей ECDSA, а затем уничтожить закрытый ключ. Однако вопрос, вызывающий обеспокоенность, заключается в том, как мы можем быть уверены, что эта сторона действительно уничтожила эти «токсичные отходы» ?
Поэтому для решения этой проблемы применяется многостороннее вычисление (Multi-Party Computation, MPC).
MPC — это криптографический протокол, который позволяет нескольким сторонам участвовать в распределенных вычислениях, при этом ни одна из сторон не имеет доступа к конфиденциальным данным другой стороны.
В каждом процессе установления доверия несколько сторон вместе участвуют в процессе для создания необходимых криптографических компонентов, таких как открытый ключ (pk) и ключ проверки (vk). Каждая сторона вносит в этот процесс часть своих конфиденциальных данных.
Конечная цель каждой стороны после этого процесса — полностью исключить токсичные отходы. В этом случае предположение о надежности состоит в том, что, пока один из n участников честен, конечный результат гарантированно будет безопасным.
Во время установки доверия каждая из n сторон использует свою секретную лямбду для совместной генерации ключей доказательства и проверки.
Чтобы эта схема провалилась, необходимо, чтобы все n сторон имели плохие намерения и поделились своими секретами друг с другом. Однако до тех пор, пока одна из сторон решит не раскрывать свою тайну, процесс установления траста все равно будет успешным, что делает невозможным производство ложных доказательств.
Математика и программирование, лежащие в основе zk-snark
Математические основы
Теория групп
ZK-SNARK использует преимущества теории групп при выполнении вычислений над эллиптическими кривыми и другими группами, особенно при использовании билинейных пар и связанных с ними алгоритмов.
Проще говоря, группа — это набор элементов {a, b, c,…}, объединенных бинарной операцией, которую мы здесь обозначим как «•».
Множество и операция называются группой, если они удовлетворяют следующим свойствам:
Замыкание: Для всех a и b в группе G операция a • b также должна находиться в G.
Ассоциативность: Для всех a, b и c в G операция (a • b) • c должна равняться a • (b • c).
Элемент идентичности: В G должен существовать такой элемент e, что для каждого элемента a в G операции e • a и a • e равны a. Этот элемент уникален.
Обратный элемент: Для каждого элемента a в G должен существовать элемент b в G, часто называемый a^-1, такой, что операции a • b и b • a равны единице e.
Подгруппы
Когда подмножество элементов в группе подчиняется всем свойствам группы, этот набор называется подгруппой исходной группы.
Поля
Поле — это специальная алгебраическая структура, в которой набор элементов выполняет две основные операции: сложение и умножение. Каждое поле должно соответствовать ряду основных аксиом, которые определяют и гарантируют его общие свойства.
Ниже приведены аксиомы, которым должно удовлетворять поле, где a, b и c являются любыми элементами поля F:
Ассоциативность сложения и умножения: a + (b + c)= (a + b) + c и a · (b · c) = (a · b) · c
Коммутативные свойства сложения и умножения: a + b = b + a и a · b = b · a
Уравнение сложения и умножения: существуют два разных элемента 0 и 1 в F такие, что a + 0 = a и a · 1 = a.
Аддитивный обратный: для каждого a в F существует элемент в F, обозначаемый -a, называемый аддитивным обратным к a, такой что a + (-a) = 0
Обратное умножение: для каждого a≠ 0 в F существует элемент в F, обозначаемый a^ -1, называемый мультипликативным обратным умножением a, такой что a · a^ -1 = 1
Распределение умножения по сложению: a · (b + c) = (a · b) + (a · c)
Примеры полей включают набор действительных чисел со сложением и умножением, а также целые числа по модулю простого числа, где определены как сложение, так и умножение.
Конечные поля
В ZK-SNARK все операции выполняются в конечных полях, где значения и операции определяются по модулю простого числа или на основе простого многочлена.
Конечное поле — это поле с конечным числом элементов, например набор целых чисел по модулю p, где p — простое число.
Количество элементов в поле, называемое порядком поля, для конечного поля может быть:
Некоторые простые числа (простое поле)
Или степень простого числа (расширенное поле)
В простом простом поле элемент может быть представлен целым числом от 0 до p-1, где Zp = {0, 1, …, p-1}.
Расширение Zp, называемое мультипликативной группой Zp*, состоит из элементов, взаимно простых с p, т. е. Zp* = {1, …, p-1}.
Генераторы конечных полей
В каждом конечном поле существует элемент, называемый генератором, который способен генерировать все элементы в группе, используя возведение в степень.
Например, рассмотрим группу Z5* в простом поле Z5 = {0, 1, 2, 3, 4}, тогда Z5* = {1, 2, 3, 4}. В группе Z5* умножение является двоичной операцией и умножение выполняется по модулю 5; Например, умножение 3 × 4 дает не 12, а 2, поскольку 12 по модулю 5 = 2.
Группа Z5* циклическая и имеет образующие 2 и 3, потому что:
С генератором 2 мы имеем:
2^0 = 1,
2^1 = 2,
2^2 = 4,
2^3 = 3,
2^4 = 1 (повторить цикл)
И с генератором 3 мы имеем:
3^0 = 1,
3^1 = 3,
3^2 = 4,
3^3 = 2,
3^4 = 1 (повторить цикл)
Эти свойства делают Z5* мощной группой для криптографических операций, и она обычно используется в криптографических алгоритмах, таких как ZK-SNARK.
Групповые гомоморфизмы
Гомоморфизмы — это отображения между двумя похожими алгебраическими структурами, такими как группы или поля, и они сохраняют операции внутри этой структуры.
В частности, гомоморфизм — это отображение f группы A в группу B, когда две группы выполняют одну и ту же бинарную операцию, например умножение или сложение. Такое сопоставление сохраняет операцию, что означает:
Если ⋅ — бинарная операция в структуре групп A и B, то для каждого элемента a и b в группе A отображение f удовлетворяет условию:
ж ( Икс ⋅ у )= ж ( Икс )⋅ ж ( у )
Это гарантирует, что результат операции, примененной к элементам в группе A, после сопоставления с группой B через f, остается эквивалентным операции, выполненной непосредственно над группой B.
Гомоморфизмы имеют фундаментальное значение для обработки свойств билинейных пар, делая процесс генерации и проверки доказательств в zk-SNARK более эффективным.
Полиномы
Полиномы являются основным компонентом при создании программ квадратичной арифметики (QAP), где проблемы представляются посредством полиномов и решаются посредством полиномиальной оценки и принятия обязательств.
Полином — это математическое выражение, состоящее из переменных и констант, использующее сложение, умножение и возведение в степень с неотрицательными целочисленными показателями.
Например, хорошим примером является многочлен 5x² + 2x + 8.
При рассмотрении полиномиального уравнения оно может представлять собой бесконечное количество различных уравнений между числами. Например, если у нас есть уравнение A(x) + B(x) = C(x), что верно, то оно также будет верно при всех значениях x, например:
А(0) + В(0) = С(0)
А(1) + Б(1) = С(1)
А(2) + Б(2) = С(2)
А(3) + Б(3) = С(3)
и так далее.
Что касается степени многочлена, то она определяется наибольшей степенью переменной в многочлене. Например, многочлен 6x⁴ + 2x³ + 3 имеет степень 4, поскольку высшая степень переменной x равна 4.
Криптография
Хэш-функции
Хэш-функции широко используются для создания «обязательств» в криптографических протоколах, помогая гарантировать, что данные не могут быть изменены без обнаружения.
Хэш-функция – это алгоритм или математическая функция, которая преобразует строку входных данных переменной длины в выходную строку фиксированной длины, называемую хеш-значением.
Формулу представления хеш-функции можно описать следующим образом:
ж ( м )= ЧАС
где f — хэш-функция, m — сообщение, а H — результирующее значение хеш-функции.
Хэш-функции обладают множеством важных свойств, что делает их очень полезными во многих криптографических приложениях. Эти атрибуты включают в себя:
Сопротивление прообразу: математически получить исходное сообщение по хеш-значению очень сложно.
Сопротивление второму прообразу: учитывая конкретное входное сообщение и его хэш-значение, трудно найти другое сообщение, которое дает такое же хеш-значение.
Устойчивость к коллизиям: трудно найти два разных сообщения, которые дают одинаковое значение хеш-функции.
Очень желательным свойством хороших хеш-функций является лавинный эффект. Это свойство, при котором небольшое изменение входных данных вызывает большое изменение выходных данных, в результате чего выходные данные кажутся случайными и неразличимыми.
Шифрование
Проще говоря, шифрование – это процесс преобразования входного сообщения (открытого текста) в кажущийся случайным вывод (зашифрованный текст), так что только авторизованные люди могут декодировать и понять эту информацию. Шифрование основано на использовании криптографического ключа, который представляет собой набор математических значений, которые и отправитель, и получатель используют для шифрования и расшифровки информации.
Существует два типа алгоритмов шифрования: симметричное шифрование и асимметричное шифрование.
Симметричное шифрование
При симметричном шифровании один и тот же ключ используется всеми сторонами, участвующими в процессе связи, для шифрования и расшифровки сообщения. Этот ключ хранится в секрете между сторонами для обеспечения безопасности обмениваемой информации.
Асимметричное шифрование
В асимметричном шифровании, также известном как шифрование с открытым ключом, существует два типа ключей: открытый ключ, используемый для шифрования, и закрытый ключ, используемый для дешифрования. Закрытый ключ хранится получателем в секрете (отсюда и «закрытый ключ»), тогда как открытый ключ может быть широко распространен среди всех, кто хочет отправить конфиденциальную информацию (отсюда и «открытый ключ»).
Асимметричное шифрование широко используется в следующих ситуациях:
Отправка защищенного сообщения: отправитель использует открытый ключ получателя для шифрования сообщения, а затем отправляет его получателю. Только получатель, владеющий секретным ключом, может расшифровать и прочитать сообщение.
Доказательство владения (знания) закрытого ключа. В процессе доказательства владения закрытым ключом отправитель шифрует (или подписывает) сообщение своим закрытым ключом, а затем отправляет его получателю. Получатель использует открытый ключ отправителя для расшифровки сообщения. Этот процесс часто называют цифровой подписью, а зашифрованное таким образом сообщение называется «цифровой подписью». Таким образом, цифровая подпись доказывает, что сообщение было отправлено кем-то, кто владеет соответствующим закрытым ключом, а также помогает проверить целостность информации в сообщении.
Гомоморфное шифрование (Гомоморфное шифрование)
Гомоморфное шифрование оказывает большое влияние на разработку высокоуровневых доказательств с нулевым разглашением, поскольку оно позволяет выполнять вычисления над зашифрованными данными без необходимости их расшифровки.
Гомоморфное шифрование – это особый тип шифрования, который позволяет выполнять вычисления непосредственно над зашифрованными данными. Это означает, что дополнительные вычисления могут выполняться с зашифрованными данными без необходимости использования секретного ключа. Результаты этих вычислений остаются зашифрованными, что обеспечивает безопасность без раскрытия исходного содержимого данных.
На практике полностью гомоморфное шифрование, позволяющее выполнять любые произвольные вычисления над зашифрованными данными, все еще имеет множество ограничений и пока не получило широкого применения. Однако выполнение некоторых операций над гомоморфными структурами возможно и используется в практических приложениях.
Эти операции включают сложение и умножение зашифрованных данных, что открыло новые возможности для безопасной обработки данных без расшифровки.
Криптография эллиптических кривых (ECC)
В ZK-SNARK эллиптические кривые играют важную роль благодаря операциям группировки, на которых достигается билинейное спаривание. ECC (криптография на основе эллиптических кривых) предоставляет эффективную платформу для создания и проверки доказательств с нулевым разглашением.
Эллиптическая кривая — это набор точек, удовлетворяющих определенному математическому уравнению. Уравнение эллиптической кривой имеет следующий вид:
Где a и b — известные константы. График этого уравнения выглядит следующим образом:
Существует множество различных представлений эллиптических кривых, но этот метод в основном заключается в поиске точек, удовлетворяющих определенному математическому уравнению.
Свойства эллиптических кривых делают их очень важными во многих областях математики и особенно в области криптографии.
Интересным свойством эллиптических кривых является их горизонтальная симметрия. Любая точка кривой может быть отражена по оси X, сохраняя при этом кривую неповрежденной. Это означает, что если вы возьмете любые две точки кривой и проведете через них линию, эта линия пересечет кривую в третьей точке.
Представьте себе, что это игра в бильярд, мяч стреляют из точки, и когда он попадает на эллиптическую кривую, он отскакивает прямо вверх или прямо вниз, в зависимости от его положения относительно оси X.
Интересное свойство эллиптических кривых заключается в том, что вы можете «расставить точки» на двух точках кривой, чтобы создать новую точку. Вы также можете последовательно «расставить точки» над самой собой, чтобы создать разные точки на кривой.
Но интересно то, что если вы знаете конечную точку и начальную точку, вычислить количество «точек», необходимых для перехода от начальной точки до конечной, очень сложно!
Представьте себе человека, играющего в одиночестве в комнате и отбивающего мяч по правилам игры. Затем приходит кто-то еще и видит окончательное положение мяча. Даже если бы они знали начальную позицию и правила игры, они не смогли бы узнать, сколько раз мяч был ударен, чтобы попасть туда, не просмотрев всю игру с самого начала. Это создает особое свойство криптографии, называемое необратимостью, и является основой для многих мощных приложений, таких как функция лазейки.
Дискретные логарифмы на эллиптических кривых — сложная проблема, лежащая в основе криптографии на основе эллиптических кривых. В отличие от факторизации, не существует ярлыка, который мог бы решить эту проблему, что значительно усложняет взлом криптографии с эллиптическими кривыми, чем с помощью RSA и Диффи-Хеллмана.
Хотя ECC обеспечивает высокий уровень безопасности за счет более коротких ключей, он по-прежнему сохраняет хорошую производительность на устройствах с низким энергопотреблением. Это делает ECC идеальным выбором для криптографических приложений на мобильных устройствах и системах с ограниченными ресурсами.
В конце этого раздела я изложил некоторые основные математические концепции и концепции кодирования, лежащие в основе zk-SNARK. В следующей части я подробно остановлюсь на более продвинутых концепциях, таких как программы квадратичной арифметики и пары эллиптических кривых.
Спасибо, что дочитали до этого места. Если вам понравилась эта статья, не забудьте подписаться на нее и поаплодировать.
Источник статьи: Team Tech/Research – AlphaTrue
Справочный источник:
1. Нгуен: Райтвиснер, К. (2016). zkSNARKs в двух словах. Блог Ethereum, 6, 1–15. https://chriseth.github.io/notes/articles/zksnarks/zksnarks.pdf
2. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-7-61d639c2ef02
3. https://celo.academy/t/zk-snarks-proofs-as-a-privacy-solution-on-the-blockchain/1961.
4. Нгуен: Чен Т., Лу Х., Кунпиттая Т. и Луо А. (2022). Обзор zk-snarks. Препринт arXiv arXiv:2202.06877. https://arxiv.org/pdf/2202.06877.pdf
5. https://medium.com/coinmonks/from-zero-to-hero-in-zero-knowledge-proofs-part-8-262f923f1537
6. https://medium.com/@hira.siddiqui/from-zero-to-hero-in-zero-knowledge-proofs-part-2-ef17ce470f2d
7. Исттом, В. (2022). Современная криптография: прикладная математика для шифрования и информационной безопасности. Спрингер Природа.
8. https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
