Криптографические примитивы GRIMM.

Неинтерактивные схемы

Обычно криптографические доказательства предполагают интеракцию между Prover и Verifier. Что-то вроде P разглашает какие-то данные, V посылает challenge, P высчитывает и посылает ответ, V подтверждает ответ. В зависимости от схемы может быть много циклов запросов-ответов, причём порядок передачи информации (transcript) имеет решающее значение.

Существует возможность превратить такие криптографические доказательства в неинтерактивные, используя т.н. “random oracle model”. Идея в том чтобы в процессе доказателсьтва запрос поступал не от реального V, а мог быть получен детерминистическим способом. При этом должно соблюдаться следующее:

• Запрос должен быть посчитан на основе всех данных которые P разгласил к настоящему моменту.
• Алгоритм должен быть “непрозрачным”, т.е. исключать практическую возможность подгона.

Практически для этого используется хэш-функция (в MM используется SHA256), вводом для неё служит полный транскрипт к текущему моменту.

Получается что с одной стороны у P есть преимущество: он знает какой будет вызов прежде, чем он разгласил свои данные. Но с другой стороны нет практической возможности подгона: если он меняет данные, то это влечёт за собой изменение вызова таким образом что практической возможности подогнать вызов под данные у него нет.

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

Подпись Шнорра (Schnorr’s signature)

Подпись Шнорра является (в определённом смысле) альтернативой ECDSA, и по сути является обобщением доказательства знания приватного ключа k (пример который мы уже рассмотрели) с использованием неинтерактивной схемы, которая завязана также на сообщении которое необходимо подписать.

Дано: A хочет подписать сообщение M используя приватный ключ k, причём публичный ключ C = k*G общеизвестен.

• A генерирует случайный нонс k1 и вычисляет C1 = k1*G
• A высчитывает challenge по формуле e = H(C1 | M)
• A высчитывает k2 = k1 + e*k

Сигнатура: (C1, k2)

B проверяет сигнатуру:

• B высчитывает challenge по формуле e = H(C1 | M)
• B проверяет: C1 = k2*G - e*C

Примечания:

• В основе этой схемы лежит неинтерактивная схема, при которой обе стороны могут независимо вычислить вызов e
• Формула обязательно учитывает и подписываемое сообщение, и часть сигнатуры C1.
• Размер сигнатуры можно скомпрессировать. Например, вместо точки C1 она может содержать лишь её координату x, или её хэш-функцию (т.е. H(C1)). При этом, разумеется, формула для вычисления вызова e должна быть соответственно изменена, и использовать лишь то, что есть в сигнатуре.

Мультиподпись (multisignature)

Одно из преимуществ подписи Шнорра в том, что её легко можно обобщить на случай при котором N участников хотят коллективно подписать сообщение M, причём размер подписи не зависит от количества участников. Это возможно благодаря тому, что подпись по сути представляет из себя скаляр и точку на кривой, причём оба образуют группу по сложению. Т.е. мультиподпись является по сути суммой подписей. Нюанс заключается лишь в том чтобы все участники подписи и, впоследствие, проверяющий (verifier) использовали один вызов e.

Дано: N участников, обозначены как P[i], хотят подписать сообщение M используя приватные ключи k[i], причём публичные ключи C[i] = k[i]*G общеизвестны.

• Каждый из участников P[i] генерирует случайный нонс k1[i], и вычисляет C1[i] = k1*G
• Участники суммируют полученные C1[i]. Результат обозначаем C1
• Каждый из участников высчитывает challenge по формуле e = H(C1 | M)
• Каждый из участников высчитывает k2[i] = k1[i] + e*k[i]
• Участники суммируют полученные k2[i]. Результат обозначаем k2

Сигнатура: (C1, k2)

V проверяет сигнатуру:

• V высчитывает challenge по формуле e = H(C1 | M)
• V суммирует все публичные ключи C[i]. Результат обозначаем C.
• V проверяет: C1 = k2*G - e*C

Примечания:

• Легко видеть что эта схема является обобщением случая с одним подписывающим.
• Как и для одного подписывающего, сигнатуру можно сократить если использовать C1.x или H(C1).
• Каждый из подписывающих видит, что именно он подписывает (сообщение M), и его часть подписи невозможно использовать для чего-то другого (т.е. украсть подпись).
• Подписывающие могут не знать с кем вместе они подписывают сообщение, в определённом смысле это им даёт некую анонимность.

Pedersen commitments (обязательства)

Предположим что у нас есть значение v которое мы хотим закодировать. Строго говоря v может быть любым, но это не случайно выбранное значение (рандом), а некий параметр, который атакующий может попробовать угадать, и на практике это может быть относительно небольшое число (по сравнению с 256-бит).

Поэтому если мы его закодируем по стандартной схеме v*G, то это можно легко сломать, т.е. угадать/подобрать нужный v.

Чтобы решить это мы расширяем нашу задачу. До этого момента мы работали с 1 генератором G. Теперь мы добавляем дополнительный генератор: точку H, которая является общеизвестной. Значение кодируется через выражение: C = kG + vH.

• k - это приватный ключ (также как и прежде)
• v - это значение которое мы кодируем

Это называется “обязательство” (commitment). Оно обладает следующими свойствами:

• Hiding: из этого выражения невозможно получить никакой информации про v.
• Binding: Если кто-то сгенерировал C, то он не сможет получить тот же Cиспользуя другие k,v. Если впоследствие надо будет раскрыть (reveal) его содержимое, то придётся разгласить именно эти k,v.

Примечание:

• Важно чтобы никто не знал соотношение между G и H, т.е. чтобы никто не знал x так что H = x*G. В противном случае теряется Binding, т.к. можно будет менять k,v сохраняя при этом commitment.
• По этой причине мы не можем просто заявить что токи G,H выбраны нами рандомально, могут заподозрить что мы взяли H = x*G, где x - известен только нам.
• Мы должны раскрыть схему по которой точки G,H были выбраны. Например, можно взять разные строчки, и пропустив их через хэш-функцию получить точки G,H.

Доказательство знания раскрытия

Дано commitment C = k*G + v*H, A хочет доказать что он знает его содержимое, не разглашая при этом деталей.

• A генерирует рандомальные k1,v1
• A Вычисляет и разглашает C1 = k1*G + v1*H
• B посылает challenge e
• A вычисляет и посылает k2 = k1 + e*k, v2 = v1 + e*v.
• B проверяет: k2*G + v2*H = C1 + e*C

Примечания:

• Легко видеть что схема в которой присутствуют 2 генератора и 2 параметра также является гомоморфной, т.е. C(k1+k2,v1+v2) = C(k1,v1) + C(k2,v2).
• Транскрипт доказательства является обощением доказательства для одного параметра, и его также можно превратить в неинтерактивную схему, и для более компактной формы достаточно использовать C1.x вместо C1.

Range proofs

При помощи Pedersen commitment можно эфективно кодировать значения v. Но важно помнить про следующие нюансы:

• Их можно “менять” не зная содержимое. Т.е. зная C(k,v) можно легко создать C(k+dk,v+dv) = C(k,v) + C(dk,dv)
• Значение v может быть любым в диапазоне [0 - p].

В MimbleWimble, как мы в последствие увидим, v интерпретируется как сумма, и во время транзакций commitments складываются/вычитаются, соответственно складываются/вычитаются заявленные суммы. Поэтому важно чтобы значение vбыло ограничено, и чтобы в процессе арифметических действий не возникал overflow. По сути значения v близкие к p эквивалентны отрицательным значениям, чего допускать нельзя.

Существуют схемы доказательства того что v находится в определённом диапазоне, при этом не разглашающие никакой информации кроме непосредственно этого утверждения.

Pedersen commitment в совокупности с Range proof позволяют проверить следующее:

• Доказательство того что v находится в определённом диапазоне значений.
• Доказательство того что создатель range proof знает раскрытие commitment, и что его с тех пор никто не менял.

В GRIMM используется усовершенствованный Range Proof (Bulletproof).

Grimm

Grimm cryptocurrency. Privacy protected blockchain powered by mimblewimble.

GrimmRU