06.10.2020 07:16
eatmore 1 763 Источник

Когда пишут о том, как разрабатывать безопасные приложения, один из частых советов звучит так: не пишите криптографию самостоятельно, а используйте какую-нибудь проверенную библиотеку. К сожалению, при разработке блокчейнов этот совет часто не работает: нужные алгоритмы либо не реализованы вовсе, либо существующие реализации не годятся по множеству возможных причин — даже потому, что они недостаточно безопасны. Вот и в этом случае нужно было проверять подписи, использующие Ed25519 — весьма популярный тип подписей, для которого существует множество реализаций, ни одна из которых, однако, нам не подошла. А всё потому, что проверка должна была выполняться из смарт-контракта, работающего на блокчейне Ethereum.


Что такое смарт-контракт

Смарт-контракт — это специальная программа, которая в некотором смысле выполняется «внутри блокчейна». Технически это реализовано так: каждый узел, поддерживающий блокчейн, выполняет код смарт-контракта и проверяет, что результат выполнения, записанный в блокчейне, совпадает с ожидаемым. В результате смарт-контракты обеспечивают намного более высокий уровень безопасности для критических вычислений: в то время как для того, чтобы изменить результат работы обычной программы, достаточно взломать только тот компьютер, на котором она выполняется, для вмешательства в смарт-контракт необходимо взять под контроль бо?льшую часть узлов. Если какой-то один узел выполнит смарт-контракт неправильно, другие узлы не примут его результат. Благодаря механизму голосования, в итоге в блокчейне останется тот результат, на котором сошлось большинство узлов.


В чём же проблема?


В Ethereum смарт-контракты выполняются в специальном окружении — так называемой виртуальной машине Ethereum (Ethereum virtual machine, EVM).


Что такое EVM

EVM — абстрактная виртуальная машина, специально разработанная для выполнения смарт-контрактов. Одним из критически важных требований к ней является повторяемость: любая без исключения программа, будучи выполненной с одинаковыми входными данными, должна гарантированно вернуть одинаковый результат — вне зависимости от реализации виртуальной машины, аппаратной архитектуры или любых других внешних факторов. Это необходимо, потому что иначе возможна ситуация, когда разные узлы получат разный результат при выполнении одного и того же смарт-контракта, что приведёт к нарушению работы сети.


EVM разработана, чтобы быть простой в реализации, но ценой этого является низкая эффективность. Кроме того, все вычисления на блокчейне повторяются всеми узлами, поэтому стоимость этих вычислений на порядки больше, чем, например, стоимость вычислений на облачном сервере. По этой причине смарт-контракты приходится тщательно оптимизировать. Поскольку EVM существенно отличается от окружения, в котором работает большинство программ, программы, написанные на обычных языках программирования, не работают в EVM. Если бы обычные языки и допускали трансляцию в EVM-байткод, из-за различий архитектуры код практически любой реализации Ed25519 был бы слишком неэффективен — настолько, что ресурсов, выделяемых на обработку одной транзакции, не хватило бы даже, чтобы проверить одну подпись. Вместо них, для EVM разработано несколько специальных языков, и самый популярный из них — Solidity.


EVM существенно отличается как от популярных процессорных архитектур, так и от часто используемых абстрактных виртуальных машин, таких как JVM или WASM. В то время как большинство архитектур содержат операции для работы с 32- и 64-битными числами, в EVM единственный тип данных — 256-битное целое число. Для реализации Ed25519 это очень удобно, так как все необходимые вычисления производятся над числами, помещающимися в 256 бит.


Как устроена подпись Ed25519

Ed25519 — подпись на основе схемы Шнорра и эллиптической кривой Curve25519. Точки на кривой задаются парами координат $(x, y)$, причём вычисления с координатами производятся по модулю простого числа $p$, равного $2^{255}-19$ — отсюда и название кривой. Для точек определена операция сложения, вместе с которой множество точек образует циклическую группу, размер которой равен $8\cdot l$, где $l=2^{252}+27742317777372353535851937790883648493$ — простое число. При этом используется только подгруппа размера $l$.


Через операцию сложения точек можно эффективно реализовать операцию умножения точки на число. Обратная же операция — поиск числа, которое, будучи умноженной на заданную точку, даст другую заданную точку — не имеет известного эффективного решения. На этом основана безопасность системы: закрытый ключ — это число $a$, а открытый — точка $A=a\cdot G$ ($G$ — фиксированная точка, имеющая порядок $l$). Зная $a$, можно легко вычислить $A$, в то время как обратная задача, вероятно, не имеет эффективного решения (хотя строго это не доказано).


Для создания подписи Ed25519 необходимо сгенерировать случайное число $r$ и вычислить точку $R=r\cdot G$. Затем вычислить хеш SHA-512 от конкатенации $R$, $A$ (открытого ключа) и подписываемого сообщения: $h=H(R||A||m)$ (здесь $H$ — хеш-функция, а $||$ обозначает конкатенацию, чтобы не путать со сложением). Затем вычислить $s=r+ha\bmod l$ — в этом месте необходим закрытый ключ. Значением подписи будет пара $(R,s)$. На самом деле $r$ генерируется не случайно, а путём хеширования сообщения с частью закрытого ключа, но это делается для того, чтобы не зависеть от наличия безопасного генератора случайных чисел, и не влияет на правильность подписи.


Для проверки подписи нужно также вычислить $h=H(R||A||m)$ и проверить, что $s\cdot G=R+h\cdot A$. Несложно убедиться, что любая правильно сгенерированная подпись гарантировано пройдёт проверку. Предполагается, что, не имея закрытого ключа, сгенерировать правильную подпись практически невозможно, даже имея несколько существующих подписей.


Другое важное отличие EVM — стоимость операций. В то время как в «обычных» виртуальных машинах время выполнения отдельных инструкций может различаться от реализации к реализации, в EVM точное количество используемых ресурсов является частью спецификации, ведь за выполнение смарт-контрактов нужно платить пропорционально затраченным ресурсам. Затраты ресурсов измеряются величиной, называемой газ (gas), и, зная затраты газа для выполнения каждой инструкции, можно точно определить, сколько будет стоить выполнение той или иной программы. И здесь кроется ещё один подвох: относительная стоимость отдельных инструкций существенно отличается от того, что стоило бы ожидать для обычной программы. Например, для обычной программы стоило бы ожидать, что умножение 256-битных чисел, тем более по модулю, занимает на порядок больше времени, чем сложение. А в EVM эти операции стоят одинаково. Значит, обычные криптографические алгоритмы, которые оптимизируют для минимизации количества умножений, для EVM могут быть не оптимальны.


Ещё EVM предусматривает раздельные области хранения данных: код, память и хранилище (storage). Память доступна на чтение и запись, но её содержимое не сохраняется между выполнениями смарт-контракта. Код доступен только на чтение. Хранилище доступно на чтение и запись, но доступ к нему, даже на чтение, намного дороже, чем доступ к коду или памяти. Оптимальная реализация Ed25519 использует таблицы заранее подсчитанных данных. Если держать их в хранилище, то при каждом использовании придётся считывать их оттуда, а это дорого. Оптимально держать их в коде, но для этого нужно генерировать код на Solidity программой на каком-то другом языке (хотя Solidity и позволяет вычислять значения во время выполнения конструктора контракта и «зашивать» их в код, ограничения этой функции делают её неподходящей для этой цели). Кроме того, компилятор Solidity не умеет производить некоторые нужные оптимизации (например, разворачивание циклов), которые можно решить генерацией исходного кода. Поэтому я решил генерировать код на Solidity программой на JavaScript.


Чтобы понимать, что написано дальше, стоит посмотреть JavaScript-код, который генерирует код на Solidity, а также сам сгенерированный код на Solidity.


Первый шаг: хеш-функция SHA-512


Первая вещь, которую должна сделать функция проверки Ed25519 — посчитать хеш-функцию SHA-512. И даже это сделать нетривиально. В EVM доступна встроенная поддержка нескольких хеш-функций: SHA-256, Keccak-256 (почти SHA-3-256), даже древняя RIPEMD-160, а вот поддержки SHA-512 нет. И при попытке скомпилировать реализацию SHA-512 возникает проблема. EVM — это стековая машина, и Solidity хранит все локальные переменные на стеке. Хотя стек может содержать до 1024 элементов, напрямую можно обращаться только к последним 16 из них. Если попытаться обратиться к локальной переменной, расположение которой на стеке не входит в одну из последних 16, то код не скомпилируется — лично я считаю, что это серьёзная недоработка компилятора, но приходится пользоваться тем, что есть.


Вот псевдокод основной части SHA-512 — обработки блока:


w[0..15] := блок сообщения
for i in 16 .. 79:
    s0 := (w[i-15] ror 1) ^ (w[i-15] ror 8) ^ (w[i-15] >> 7)
    s1 := (w[i-2] ror 19) ^ (w[i-2] ror 61) ^ (w[i-2] >> 6)
    w[i] := w[i-16] + s0 + w[i-7] + s1

a, b, c, d, e, f, g, h := h0, h1, h2, h3, h4, h5, h6, h7
for i in 0 .. 79:
    S0 := (a ror 28) ^ (a ror 34) ^ (a ror 39)
    S1 := (e ror 14) ^ (e ror 18) ^ (e ror 41)
    ch := (e & f) ^ (~e & g)
    maj := (a & b) ^ (a & c) ^ (b & c)
    temp1 := h + S1 + ch + k[i] + w[i]
    temp2 := S0 + maj
    a, b, c, d, e, f, g, h := temp1 + temp2, a, b, c, d + temp1, e, f, g
h0, h1, h2, h3 := h0 + a, h1 + b, h2 + c, h3 + d
h4, h5, h6, h7 := h4 + e, h5 + f, h6 + g, h7 + h

Как видно, во втором цикле используется больше 16 переменных, а ведь ещё есть промежуточные значения, которые тоже занимают место на стеке. Чтобы получить работающий код, пришлось использовать множество ухищрений: использовать блоки, чтобы ограничить время жизни переменных, менять порядок переменных таким образом, чтобы нужные переменные были ближе к концу стека, менять структуру выражений. Заодно можно слегка оптимизировать выражения: вместо (e & f) ^ (~e & g) использовать (e & (f ^ g)) ^ g, а вместо (a & b) ^ (a & c) ^ (b & c) — (a & (b | c)) | (b & c) (хотя можно и (a & (b ^ c)) ^ (b & c)). Для вычисления побитовых поворотов работает такой приём: чтобы вычислить побитовый поворот x, нужно взять число x | (x << 64) и вычислять его побитовые сдвиг (перед этим нужно очистить все биты x, кроме младших 64). Поскольку требуется вычислять по три побитовых поворота от одного и того же числа, выражение x | (x << 64) можно вычислить один раз и использовать три раза.


Поскольку в первом цикле для вычисления w[i] используются значения не новее w[i-2] (т. е. w[i-1] не используется), можно вычислять элементы w парами (использовать 256-битные операции как своеобразный SIMD). Тот же приём для побитовых поворотов работает, чтобы вычислять повороты от двух чисел сразу.


Общая схема алгоритма такая: использовать первые 16 значений w, затем вычислить следующие 16 значений, затем использовать их, и так далее. Сами значения w хранятся в четырёх переменных, упакованные по четыре, это позволяет избегать использования массивов. При этом внутренние циклы (по 16 итераций) развёрнуты, остаётся только внешний цикл, который выполняет 4,5 итерации.


Распаковка точек


Следующий этап: распаковка точек. Хотя точки на кривой Curve25519 задаются парами координат $(x, y)$, хранить обе координаты слишком расточительно: каждому значению $x$ соответствует не более двух значений $y$, и наоборот. Поэтому точки хранятся так: значение $y$ хранится целиком, а дополнительно хранится один бит, определяющий, какое из двух возможных значений $x$ нужно использовать. Поскольку значения координат берутся по модулю $p=2^{255}-19$, такая запись помещается в 32 байта. Однако, для вычислений нужны обе координаты, поэтому нужно восстановить значение $x$.


Значение $x$ восстанавливается по формуле $x=\pm\sqrt{(y^2-1)/(dy^2+1)}$. Поскольку $-d$ не является квадратичным вычетом по модулю $p$, значение знаменателя не может быть равно нулю, однако, значение квадратного корня существует только для чуть более половины возможных значений $y$. Здесь представляет интерес только деление и извлечение квадратного корня. Оказывается, эти операции можно совместить. Пусть необходимо вычислить $\sqrt{u/v}$, причём $v\ne0$. Для этого оригинальная статья Ed25519 предлагает такую процедуру (использующую тот факт, что $p\equiv5\pmod8$):


  • Посчитать $\beta=uv^3(uv^7)^{(p-5)/8}$.
  • Если $v\beta^2=u$, то ответ равен $\pm\beta$.
  • Иначе, если $v\beta^2=-u$, то ответ равен $\pm\sqrt{-1}\beta$.
  • Иначе, ответа не существует.

Почему это работает? Заметим, что $\beta^8=u^8v^{24}(uv^7)^{p-5}=u^{p+3}v^{7p-11}=(u/v)^4$, откуда следует, что $\beta^2=\pm u/v$ или $\beta^2=\pm\sqrt{-1}u/v$. Если выполняется второе равенство (и $u\ne0$), то квадратного корня из $u/v$ не существует, поскольку $\sqrt{-1}$ не является квадратичным вычетом. Если $\beta^2=-u/v$, то $(\sqrt{-1}\beta)^2=u/v$. Таким образом, в любом случае эта процедура находит ответ, если он существует.


Оказывается, эту процедуру можно слегка упростить: вместо $\beta=uv^3(uv^7)^{(p-5)/8}$ вычислять $\beta=u(uv)^{(p-5)/8}$. При этом $\beta^8=u^8(uv)^{p-5}=u^{p+3}v^{p-5}=(u/v)^4$, дальше доказательство полностью аналогично предыдущему варианту. Для этого вычисления используется вспомогательная функция, которая для произвольного значения $v$ вычисляет $v^{2^{250}-1}$ и $v^{11}$ по модулю $p$, эта же функция в дальнейшем используется для вычисления обратного по модулю $p$ (в этой функции реализована подобранная вручную аддитивная цепочка).


Двойное умножение


Вспомним, что для проверки подписи нужно проверить, что $sG=R+hA$. Кажется, что для этого нужно распаковать две точки ($R$ и $A$), но многие реализации, в том числе и эта, делают по-другому: вычисляют значение $sG-hA$, запаковывают и сравнивают с запакованным значением $R$. Таким образом, всё, что остаётся — это вычислить $sG-hA$.


Для вычисления такого выражения есть несколько методов. Можно посчитать отдельно $sG$ и отдельно $hA$, но это неэффективно. Более эффективный метод — «удвоить и прибавить» (double-and-add), в псевдокоде это выглядит примерно так:


result := 0
for bit_index in n-1 .. 0:
    result := double(result)
    if s & (1<<bit_index) != 0:
        result := add(result, G)
    if h & (1<<bit_index) != 0:
        result := subtract(result, A)

Здесь $n$ — число бит в $s$ и $h$. Этот алгоритм сканирует биты в $s$ и $h$, начиная со старшего, и при обнаружении единичного бита прибавляет $G$ к текущему результату (или вычитает $A$). Этот алгоритм выполняет $n$ удвоений и $n$ (в среднем) сложений, если считать, что биты чисел $s$ и $h$ принимают значения $0$ и $1$ с равной вероятностью. Но и его можно ускорить. Заметим, что каждым сложением он «покрывает» один бит в числе $s$ или $h$, а можно сделать так, чтобы он покрывал сразу несколько. А именно, если для некоторого $k$ предпосчитать кратные $A$ и $G$ с коэффициентами от $2^k$ до $2^{k+1}-1$, то прибавлением такого кратного можно обработать сразу $k+1$ бит! Это выглядит примерно так:


result := 0
for bit_index in n-1 .. k:
    result := double(result)
    if s & (1<<bit_index) != 0:
        result := add(result, Gmul[s >> (bit_index-k)])
        s := s & ((1 << (bit_index-k)) - 1)
    if h & (1<<bit_index) != 0:
        result := subtract(result, Amul[h >> (bit_index-k)])
        h := h & ((1 << (bit_index-k)) - 1)

Этот алгоритм, обнаружив единичный бит, обрабатывает сразу и его, и $k$ следующих бит. Затем он «вырезает» эти биты из текущего значения $s$ или $h$, чтобы не обрабатывать их повторно. Правда, у этого алгоритма есть небольшая проблема: $k$ младших бит могут быть не обработаны. Для решения этой проблемы я использовал два подхода:


  • Для $s$ и $G$ и воспользовался тем, что кратные $G$ посчитаны заранее и зашиты в код. Я умножил значение $s$ на $2^k$, а кратные $G$ — на $2^{-k}\bmod l$. Результат не меняется, но после умножения на $2^k$ младшие $k$ бит у $s$ гарантированно нулевые.
  • Для $h$ и $A$ этот способ не работает. Я рассматривал вариант умножить $h$ на $2^{-k}\bmod l$ и затем на $2^k$, но проблема в том, что $A$ является частью входных данных и не обязательно лежит в подгруппе размера $l$. Если $A$ не лежит в подгруппе размера $l$, то умножение на $(h2^{-k}\bmod l)\cdot2^k$ не эквивалентно умножению на $h$, а если вместо $l$ использовать $8l$ (полный размер группы), то по этому модулю нельзя вычислить $2^{-k}$. В итоге, я решил сделать так: вместо $h$ использовать $h+8l-2^k$ (то же самое, что $h-2^k$ по модулю $8l$), а в конце сделать ещё одно сложение: result := subtract(result, Amul[(1 << k) + h]), то есть дообработать то, что осталось от $k$ младших бит, при этом прибавка $2^k$ нужна, потому что кратные $A$ посчитаны только для коэффициентов от $2^k$ до $2^{k+1}-1$.

В этой реализации я использую значение $k=3$, которое обеспечивает баланс между затратами на предпосчёт, использованием памяти и экономией вычислений в основном цикле.


Следующий вопрос: как реализовать сложение, вычитание и удвоение точек. Обычные реализации в криптографических библиотеках оптимизированы в расчёте на то, что умножение по модулю $p$ намного дороже сложения. В EVM эти операции стоят почти одинаково, поэтому стоило подобрать формулу вручную. В этом очень помогает база данных формул для операций на эллиптических кривых — Explicit-Formulas Database. Вот страница с формулами для того типа кривой, к которым относится Curve25519. Как видно, в качестве источника для всех формул указана одна и та же статья. В этой статье содержится важная информация, которой нет в EFD, в частности, о том, какие формулы являются полными, а какие нет. Неполные формулы представляют опасность: они будут работать на случайных тестах, но на специально подобранных входных данных они могут дать неправильный результат. В частности, формулы для сложения, у которых наименование заканчивается на -2 или -4 (см. список), являются неполными, поэтому их использовать не стоит (хотя они и более эффективные). В итоге я использовал в качестве основы формулу «madd-2008-hwcd-3» для сложения и «dbl-2008-hwcd» для удвоения (там нет большого выбора). Однако, я внёс некоторые изменения.


Во-первых, я изменил используемые координаты. Там предлагается использовать так называемые расширенные проективные координаты (extended projective coordinates) — такие числа $X$, $Y$, $Z$ и $T$, что $x=X/Z$, $y=Y/Z$ и $xy=T/Z$. Однако, в формуле для удвоения $T$ не используется, поэтому от его вычисления можно попробовать избавиться, если следующая операция — удвоение. Для этого можно заметить, что как при сложении, так и при удвоении результат сначала вычисляется в виде координат $X$, $U$, $Y$ и $V$, таких что $x=X/U$ и $y=Y/V$, а затем эти координаты переводятся в обычные, для этого требуется четыре умножения (или три, если не вычислять $T$). Я решил хранить точки в виде $X$, $U$, $Y$, $V$, это позволяет сэкономить одно умножение при удвоении из-за отсутствия необходимости вычислять $T$.


Во-вторых, я продумал формат для предпосчитанных точек. Формулы madd реализуют так называемое смешанное сложение (mixed addition) — сложение, при котором можно заранее посчитать часть промежуточных значений для одной из точек, чтобы уменьшить количество вычислений. Мне это очень удобно: у меня восемь точек посчитано ещё на этапе генерации кода и ещё восемь генерируется во время выполнения; переведя их в оптимальную для вычислений форму, можно сэкономить на сложениях в основном цикле, которых около ста. Я выбрал такое представление: $((y+x)/2, (y-x)/2, xyd)$. По сравнению с некоторыми более очевидными представлениями (например, $(y+x, y-x, xy\cdot2d)$, которое используется в libsodium) это позволяет сэкономить одно умножение на 2, которое в EVM стоит, как обычное умножение. В результате псевдокод для сложения выглядит так:


// Входные данные:
// Точка 1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
// Точка 2: (s2, d2, t2), s2=(y+x)/2, d2=(y-x)/2, t2=x*y*d.
// Выходные данные:
// Точка 3: (x3, u3, y3, v3), x=x3/u3, y=y3/v3.

// Точка (x4, y4, z4, t4) - то же самое, что и точка 1, но в других координатах.
x4 := x1 * v1
y4 := y1 * u1
z4 := u1 * v1
t4 := x1 * y1

// Далее см. формулы madd-2008-hwcd-3.
s4 := y4 + x4
d4 := y4 - x4
a := d4 * d2 // (y4-x4)*(y2-x2)/2, соответствует A/2.
b := s4 * s2 // (y4+x4)*(y2+x2)/2, соответствует B/2.
c := t4 * t2 // Соответствует C/2.
             // D/2 - это просто z4, вычислять не надо.
x3 := b - a  // E/2.
u3 := z4 + c // G/2.
y3 := b + a  // H/2.
v3 := z4 - c // F/2.
// Значения x3, u3, y3, v3 отличаются от E, G, H, F коэффициентом 1/2, но это не важно, потому что значения x3/u3 и y3/v3 те же самые.

Псевдокод для удвоения выглядит так:


// Входные данные:
// Точка 1: (x1, u1, y1, v1), x=x1/u1, y=y1/v1.
// Выходные данные:
// Точка 2: (x2, u2, y2, v2), x=x2/u2, y=y2/v2.

// Точка (x3, y3, z3) - то же самое, что и точка 1, но в других координатах. Значение t3 не нужно.
x3 := x1 * v1
y3 := y1 * u1
z3 := u1 * v1

// Далее см. формулы dbl-2008-hwcd.
xx := x3 * x3 // A.
yy := y3 * y3 // B.
xy := x3 * y3 // А вот здесь выгоднее вычислить E как 2xy, а не так, как там.
zz := z3 * z3
x2 := xy + xy // E.
u2 := yy - xx // G.
y2 := yy + xx // -H.
v2 := zz + zz - u2 // -F.
// Опять же, коэффициент -1 у значений y2 и v2 не влияет на правильность результата.

Ещё одна оптимизация: для сложения не обязательно использовать инструкцию addmod (сложение по модулю). Если слагаемые меньше, чем $2^{255}$, то можно использовать обычное сложение (оно дешевле), так как результат гарантированно не переполнит 256-битный тип. Результат такого сложения, однако, можно использовать только в операциях, использующих значение по модулю. Например, если нужно сложить три числа, то из двух сложений по модулю можно заменить на обычное сложение только одно.


Проверка результата


Наконец, полученную точку нужно упаковать. Это несложно: посчитать $x=X/U$ и $y=Y/V$, затем записать младший бит $x$ на место старшего бита $y$. Поскольку нахождение обратного по модулю — затратная операция (она реализована посредством возведения в степень $p-2$), используется оптимизация, позволяющая находить обратное только один раз: для этого вычисляется $(UV)^{-1}$, из него можно вычислить $U^{-1}=(UV)^{-1}V$ и $V^{-1}=(UV)^{-1}U$. Упакованная точка сравнивается со значением $R$, записанным в подписи. Если совпала, то подпись правильная. Вот и всё.


Заключение


К счастью, в NEAR нет нужды в подобных извращениях с кодом. Смарт-контракты можно писать на Rust и AssemblyScript (похож на TypeScript) с использованием существующих библиотек.


Посмотреть, как выглядит разработка под NEAR, и поэкспериментировать в онлайн-IDE можно здесь.


Следить за всеми новостями на русском можно в группе в Телеграме и в группе ВКонтакте, а на английском в официальном твиттере.


До скорых встреч!