- PVSM.RU - https://www.pvsm.ru -
Привет! Представляю вашему вниманию перевод статей блога ZCash, в которых рассказывается о механизме работы системы доказательств с нулевым разглашением SNARKs, применяемых в криптовалюте ZCash (и не только).
Предыдущая статья: Объяснение SNARKs. Гомоморфное скрытие и слепое вычисление полиномов (перевод) [1]
В этой статье мы рассмотрим тест на принятый коэффициент и слепое вычисление полиномов, поддающихся проверке. Поехали…
В предыдущей статье мы увидели, как Алиса может слепо вычислить скрытие ее многочлена P порядка d, в точке s принадлежащей Бобу. Мы назвали это «слепым» вычислением, так как Алиса не получает значение s в процессе вычисления.
Однако в этом протоколе что-то отсутствует. Тот факт, что Алиса может вычислить не гарантирует, что она действительно отправит Бобу, а не какое нибудь другое значение.
Таким образом, нам нужен способ «заставить» Алису правильно следовать протоколу. В статье мы подробно объясним, как достигнуть этого. Давайте сначала рассмотрим и объясним принцип действия основного инструмента, необходимого для этого. Мы называем его «Тест знания о коэффициенте» (Knowledge of Coefficient (KC) Test).
Как и раньше, обозначим через g генератор группы G порядка , где дискретное логарифмирование является тяжелой задачей. Для удобства, начиная с данного места будем работать с нашей группой аддитивно, а не мультипликативно. То есть, для $inline$α ∈ F_p, α⋅g$inline$ обозначает сложение α раз копии g.
Для , будем называть пару элементов в "-парой", если и .
обозначает ненулевые элементы . Это то же самое, что и описанные в предыдущей статье [1].
Тестирование происходит следующим образом.
Теперь давайте подумаем, когда Алиса может успешно ответить на вызов? Предположим, что она знает α. В этом случае она может просто выбрать любой a' из G и вычислить , а затем вернуть новую α-пару .
Однако, поскольку единственная информация об α содержится в выражении и группа G имеет сложную дискретную задачу логарифмирования, мы полагаем, что Алиса не сможет найти .
Итак, как же она может успешно ответить на запрос, не зная α?
Простой способ сделать это заключается в следующем: Алиса просто выбирает некое и отвечает парой $inline$( a', b') = ( γ⋅ a , γ⋅ b )$inline$
В этом случае мы имеем:
$inline$b'= γ⋅ b = γα ⋅ a = α ( γ⋅ a ) = α ⋅ a'$inline$
Таким образом пара является α-парой, как и требовалось.
Обратите внимание, что если Алиса ответила, используя этот вариант, она знает, чему равно отношение a к a', То есть, она знает такой коэффициент , чтобы .
Знание о принятом коэффициенте (ЗПК — The Knowledge of Coefficient Assumption (KCA)) утверждает, что это всегда так:
ЗПК: Если Алиса возвращает верный ответ на запрос Боба то с большой вероятностью, независимо от выбора Бобом , она знает такой коэффициент , чтобы .
В литературе это обычно называется «знанием о принятой экспоненте», так как традиционно оно использовалось для мультипликативных групп [2].
Тест Знания и Принятый Коэффициент будут важными инструментами в следующей части статьи.
Вы можете задаться вопросом, как мы можем сформулировать ЗПК в конкретном математическом выражении? В частности, как мы сформулируем представление о том, что «Алиса знает» в математическом определении?
Это делается примерно так: мы говорим, что помимо Алисы у нас есть другая сторона, которую мы называем Экстрактором Алисы. Экстрактор Алисы имеет доступ к внутреннему состоянию Алисы.
Теперь мы можем сформулировать ЗПК следующим образом: каждый раз, когда Алиса успешно отвечает -парой , Экстрактор Алисы возвращает , такой что .
Полное формальное определение ЗПК определяет Экстрактор «несколько слабее» и вместо этого он сигнализирует о вероятности успешного ответа Алисы, а не выводит , который является малозначительным в данном случае
Далее, опираясь на предыдущий материал, мы разработаем протокол для достоверного слепого вычисления полиномов, определения которым будет дано ниже. В последующих частях (и статьях) будет показано, как этот протокол можно использовать для построения SNARKs, поэтому наберитесь еще немного терпения для изучения SNARKs :).
Предположим, что, Алиса имеет многочлен P порядка d, а у Боба есть точка , которую он выбрал случайно. Мы хотим создать протокол, который позволил бы Бобу узнать , т.е. скрытие P в точке s, с двумя дополнительными свойствами:
Это называется проверкой слепого вычисления полинома. Протокол в предыдущей статье дал нам только первый пункт, но не второй. Чтобы получить достоверность, нам понадобится расширенная версия знания о принятом коэффициенте (ЗПК).
Свойства достоверности и конфиденциальности полезны вместе, потому что они заставляют Алису решить, какой полином P она будет использовать, не видя значения s. Это в некотором смысле обязывает Алису к «ответу полиномом», не видя «точечный запрос» s. Эта логика станет более понятной далее.
В полном формальном доказательстве некоторые вещи описаны более тонко. Например то, что Алиса все же получает некую информацию об s, прежде чем принять решение о ее полиноме P. Например она получает скрытия
ЗПК, в том виде, который мы определили выше, звучит примерно так: если Боб дает Алисе некоторую -пару , а затем Алиса генерирует еще одну -пару , то она знает такое значение c, чтобы . Говоря иначе, Алиса знает соотношение между a' и a.
Теперь предположим, что вместо одной Боб посылает Алисе несколько -пар (для одной и той же ). И теперь снова Алиса, получив эти пары, должна сгенерировать другие другие -пары . Важно, что Алиса должна это сделать, при этом она не знает значение .
Как было описано выше, Алисы может создать -пару простым способом. Для этого нужно взять одну из пар , полученную от Боба и умножить оба элемента на некоторый . Если была -парой, то тоже будет -парой. Но может ли Алиса сгенерировать -пары для большего количества полученных -пар? И возможно ли получить новую -пару, используя сразу несколько полученных -пар?
Ответ: Да. Например, Алиса может выбрать два значения и вычислить пару $inline$( a', b') = ( c_1⋅ a_1+ c_2⋅ a_2, c_1⋅ b_1+ c_2⋅ b_2)$inline$. Простые преобразования показывают, что для любой , отличной от нуля, это тоже является -парой:
$inline$b'= c_1⋅ b_1+ c_2⋅ b_2= c_1α ⋅ a_1+ c_2α ⋅ a_2= α ( c_1⋅ a_1+ c_2⋅ a_2) = α ⋅ a'$inline$
В более общем случае Алиса может взять любую линейную комбинацию полученных d пар. Для этого нужно выбрать любые и определить .
Обратите внимание, что если Алиса использует эту стратегию для генерации ее -пар, то она будет знать некоторую линейную зависимость между и . То есть она знает такие, что .
Расширенное ЗПК утверждает, по сути, что это единственный способ, которым Алиса может генерировать -пару. Таким образом, когда она успешна сгенерирована, Алиса будет знать линейную зависимость между и . Более формально предположим, что G представляет собой группу размера p с генератором g, описанные аддитивно в начале статьи. Знание о принятом коэффициенте порядка d (d-ЗПК) в G можно записать следующим образом:
d-ЗПК: Предположим, что Боб выбирает случайные и , и отправляет Алисе -пары $inline$( g, α ⋅ g), ( s ⋅ g, α s ⋅ g) , ... , ( s^d⋅ g, αs^d⋅ g)$inline$. Предположим, что затем Алиса отвечает другой -парой . Тогда, с большой вероятностью, Алиса знает такие, что .
D-KCA (d-ЗПК) была представлена в журнале [3] Йенса Грота.
Заметим, что в Боб не посылает случайный набор -пар, а посылает набора с определенной «полиномиальной структурой». Пользу этого мы увидим в приведенном ниже протоколе.
Предположим, что наше ГС (гомоморфное скрытие) является отображением для генератора g из G, описанного выше.
Для простоты мы представляем протокол для этого конкретного E:
Во-первых, заметим, что полученные коэффициенты , являются линейной комбинацией и , а является линейной комбинацией $inline$α ⋅ g, α s ⋅ g, ... , α s^d⋅ g$inline$. Таким образом, аналогично протоколу в предыдущей статье, Алиса действительно может вычислить эти значения из сообщений Боба для полинома P, который она знает.
Во-вторых, согласно d-ЗПК, если Алиса посылает такие, что , то почти наверняка она знает такие , что . В этом случае для многочлена известного Алисе. Другими словами, вероятность того, что Боб примет ответ на шаге 3 и при этом Алиса не знает такого многочлена P является ничтожной.
Резюмируя все это, используя d-ЗПК, мы разработали протокол для достоверного слепого вычисления полиномов. В следующих статьях мы увидим, как этот механизм используется в конструкциях SNARK.
Продолжение следует…
Автор: AgentRX
Источник [4]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/269847
Ссылки в тексте:
[1] Объяснение SNARKs. Гомоморфное скрытие и слепое вычисление полиномов (перевод): https://habrahabr.ru/post/343054/
[2] мультипликативных групп: https://ru.wikipedia.org/wiki/%D0%9C%D1%83%D0%BB%D1%8C%D1%82%D0%B8%D0%BF%D0%BB%D0%B8%D0%BA%D0%B0%D1%82%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%B3%D1%80%D1%83%D0%BF%D0%BF%D0%B0_%D0%BA%D0%BE%D0%BB%D1%8C%D1%86%D0%B0_%D0%B2%D1%8B%D1%87%D0%B5%D1%82%D0%BE%D0%B2
[3] журнале: http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf
[4] Источник: https://habrahabr.ru/post/343468/
Нажмите здесь для печати.