Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

Язык

Параметры Zcash и их настройка

Ariel Gabizon | Sep 22, 2016

В освнове Zcash лежит zkSnark - новая криптографическая технология, предотвращающая утечку информации, которая представляет из себя доказательство с нулевым разглашением, не требующее больших затрат. Zcash - первый проект, в котором эта технология применяется в таких крупных масштабах. Для того, чтобы запустить zkSnark, для начала необходимо задать "системные параметры". Этот процесс довольно похож на установку параметров для криптосистем с открытым ключом, но с некоторой оговоркой: после создания пары ключей (\(\mathsf{privkey},\) \(\mathsf{pubkey}\)), закрытый ключ \(\mathsf{privkey}\) уничтожается. На деле отсутствие закрытого ключа \(\mathsf{privkey}\) у участников является важнейшим условием для системы, претендующей на высокий уровень безопасности.

Параметры открытого ключа \(\mathsf{pubkey}\) соответствуют системным параметрам. Закрытый ключ \(\mathsf{privkey}\) является чем-то вроде криптографического мусора, который его обладатель может использовать для генерации фальшивых коинов (но при этом он не сможет узнать личную информацию о пользователе). Подробнее здесь.

Чтобы улучшить безопасность, команда Zcash разработала многопользовательский протокол, который генерирует открытый ключ \(\mathsf{pubkey}\). При этом закрытый ключ \(\mathsf{privkey}\) определяется секретной рандомной связью между участниками. Таким образом, закрытый ключ \(\mathsf{privkey}\) не будет уничтожен только если каждый из участников является злоумышленником.

Цель этой статьи - дать более-менее простое объяснение, как выглядит открытый ключ \(\mathsf{pubkey}\) и каким образом происходит его генерация.

Как выглядит открытый ключ \(\mathsf{pubkey}\)

Предположим, что \(g\) с высокой вычислительной сложностью является генератором для некоторой группы \(G\). Мы присваиваем \(G\) порядок \(r\) для некоторого натурального числа \(r,\) и задаем группу вычислений. И так, для \(s\in \mathbb{F}\), где \(\mathbb{F}\) является множеством значений \(r\), мы можем найти скалярное произведение \(g\) через \(s\) путем \(s\cdot g\); это значит, что \(s\cdot g\) находится путем копирования \(g\) \(s\) раз. В упрощенном варианте пары (\(\mathsf{privkey},\) \(\mathsf{pubkey}\)) закрытый ключ \(\mathsf{privkey}\) является всего лишь рандомным элементом \(s\in \mathbb{F}^*\) , а открытый ключ \(\mathsf{pubkey}\) - последовательностью группы элементов

\(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\)

Где \(\mathbb{F}^*\) множество отличных от 0 элементов для \(\mathbb{F}.\)

Генерация открытого ключа \(\mathsf{pubkey}\)

Позже мы в 2-х словах расскажем, почему \(\mathsf{pubkey}\) выглядит именно так и как это применимо на практике. А сейчас я предлагаю сконцентрироваться на разработке протокола генерации \(\mathsf{pubkey}\).

Для простоты и наглядности предположим, что \(d=2\); , а также опустим 1-й элемент публичного ключа \(g\), потому как иначе он слишком упрощает генерацию. Рассмотрим процесс генерации на примере 2-х сторон - Алисы и Боба, которые хотят сгенерировать надежный открытый ключ \(\mathsf{pubkey}=\) \((s\cdot g, s^2\cdot g)\). И они хотят это сделать таким образом, чтобы никто из них не знал значения \(s.\) Давайте сначала разберем более простой пример, где они просто хотят сгенерировать \(s\cdot g\), но с тем же условием (никто из них не должен знать значения \(s.\)). Тогда они используют следующий протокол:

  1. Алиса выбирает случайное значение для \(a\in \mathbb{F}^*\), и отправляет \(M_1:= a\cdot g\) Бобу.
  2. Боб выбирает случайное значение для \(b\in \mathbb{F}^*\) и умножает \(M_1\) на \(b\). Далее он отправляет Алисе сообщение \(M:= b\cdot M_1\).

По итогу у нас получается \(M=b\cdot a \cdot g = (a b)\cdot g\). Обозначим s как \(s:= a b\).

Обратите внимание, что

  • Боб не может узнать значение \(a\) из сообщения \(M_1,\) т.к. мы приняли, что задача обращения функции в \(G\) обладает высокой вычислительной сложностью. То же касается значения \(b\) для Алисы. При этом, никто из них не знает значения \(s\), которое вычисляется через \(a\) и \(b\).
  • Для любого заданного \(a\in \mathbb{F}^*\), \(a b\) является случайным элементом \(\mathbb{F}^*\), когда случайным является \(b\). Таким образом, даже если Алиса попытается обмануть Боба не выбирая каждый раз случайное значение, а постоянно выбирая, например, \(a=4\), \(s\) все равно останется неизвестным случайным числом. То же самое касается и Боба.

Отсюда следует, что если хотя бы один из них выполняет все правила, то \(M=s\cdot g\) будет правильно работать.

А теперь давайте попробуем применить схожий подход к генерации \((s\cdot g, s^2\cdot g)\):

  1. Алиса присваивает случайное значение \(a\in \mathbb{F}^*,\) и отправляет \((A,B)\), где \(A:= a\cdot g\) , а \(B := a^2\cdot g.\)
  2. Боб выбирает случайное значение \(b\in \mathbb{F}^*,\) и отправляет \(M=(b\cdot A, b^2\cdot B).\) Если оба следовали протоколу, мы получаем \(M= (b a \cdot g, b^2 a^2 \cdot g) = ( a b\cdot g, (a b)^2\cdot g).\) Получаем вектор со значением \(s:= ab.\)

Но возникает одна проблема: а что если Боб попытается обмануть, задав значение \(B\) как, например, \(c\neq b^2\)? Тогда мы получим \((ab\cdot g, a^2 c \cdot g),\) что уже не сможет принять форму \((s\cdot g, s^2\cdot g)\) при любом значении \(s.\) Для многих групп это считается неэффективным, и это то, что называется проблемой принятия решения Диффи-Хеллмана. По крайней мере в нашем примере мы рассматриваем группу с билинейным спариванием. Это путь \(e:G\times G\to G_T, к группе G_T,\) с порядком \(r\) и генератором \(\mathbf{g},\), что в мультипликативной записи выглядит как

\(e(a\cdot g, b\cdot g) = \mathbf{g}^{ab}\)

для любого \(a,b\in\mathbb{F}.\) Это дает нам возможность проверить, имеет ли \(M\)  правильное значение. А проверяем мы так

\(e(g,B) = e(A,A).\)

Давайте убедимся на практике, что если никто не сжульничал, то проверка будет пройдена. Вот, что у нас получится, когда каждый поступил честно \(A=s\cdot g,\) и \(B=s^2\cdot g.\) Отсюда

\(e(g,B) = e(g,s^2\cdot g) =\mathbf{g}^{s^2}\),

а также

\(e(A,A) = e(s\cdot g,s\cdot g) = \mathbf{g}^{s^2}.\)

Любой может проделать подобные вычисления и убедиться, что когда \(M\) задано неверно, то значения будут различаться, и проверка не будет пройдена.

Как использовать \(\mathsf{pubkey}\)

Вспомним, что полином \(P\) в степени \(d\) для \(\mathbb{F}\) определяется следующей формулой

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\)

На данном этапе мы можем вычислить полином \(s\in \mathbb{F}\) заменив \(s\) на \(X,\) и высчитав конечную сумму. Немаловажный факт состоит в том, что если \(P\) и \(Q\) являются разнозначными полиномами в наивысшей возможной степени \(d,\) то они могут совпадать в большинстве точек \(d\). В схеме Zcash отправитель должен особым образом воспроизвести два полинома в степени \(d\), и тогда под действием магии математики они станут идентичны. Т.е. получится \(P=Q,\), но только в случае правильной транзакции.

\(\mathsf{pubkey}\) can now be used to test if \(P\) и \(Q\) are equal at a point \(s\) not known by the sender. Say

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\)

и

\(Q(X) = b_0 + b_1\cdot X + b_2\cdot X^2 + \ldots + b_d\cdot X^d\)

Используя \(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g),\) проверяющий может вычислить

\(P(s)\cdot g = a_0\cdot g + a_1 s \cdot g + a_2s^2 \cdot g + \ldots + a_d s^d\cdot g\)

и compute \(Q(s)\cdot g\) similarly. The verifier can then check if they are equal.

Since the sender of a non-valid transaction has to construct distinct \(P\) и \(Q\) without knowing \(s,\) the chance that \(P(s)=Q(s)\) is very small.

Дисклеймер

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

References

Our zkSNARKS use SCIPR Lab's implementation of the Pinnochio protocol, which in turn is based on the work of Gennaro, Gentry, Parno и Raykova. Our protocol for parameter generation builds on a previous work of Ben-Sasson, Chiesa, Green, Tromer и Virza.