Язык

Параметры 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.