Al-Kharba Dec 14 2021 at 22:47

Пара слов о Solana и ed25519

11 min

16K

Децентрализованные технологии развиваются всё быстрее, капитализации проектов растут, рынок наполняется новыми вакансиями. Нет сомнений, что эта сфера уже оказывает сильное влияние на мир. Об этом, конечно, можно долго и интересно рассуждать, но моя статья о другом. В фокусе статьи две вполне себе конкретные вещи: on-chain программы Solana и алгоритм цифровой подписи ed25519. К чьему-то сожалению здесь не будет ничего об уязвимостях, потому что мне не хватает компетенций в таких вопросах. Зато я расскажу о программной модели Solana, которая позволяет строить децентрализованные приложения, а также о том, какое место в ней занимает алгоритм цифровой подписи ed25519 и как он математически работает.

Solana

Solana - это молодой быстрорастущий проект, который представляет из себя блокчейн и платформу для децентрализованного исполнения программ. Одной из главных целей Solana является достижение высокой скорости работы сети, сопоставимой скорости централизованных сетей. Родоначальником идей, лежащих в основе проекта Solana, а также текущим CEO Solana Foundation является Анатолий Яковенко, который ранее достаточно долго работал в Qualcomm. Служебный токен сети носит одноименное название (кратко SOL), а его минимальная единица - lamport (ру. лэмпорт), равный $10^{-9}$ SOL. Solana использует Proof-of-Stake в качестве алгоритма консенсуса, а также алгоритм Proof-of-History для быстрого и безопасного определения порядка транзакций, который, к слову, для Solana и был придуман.

Account

Одной из функциональных единиц Solana являются аккаунты. Формально аккаунт - это пара из 32-байтной последовательности, называемой адресом, и соответствующей структуры данных, существующей по этому адресу. Упрощенно аккаунт можно представить следующим образом:

pub struct Account {
    pub lamports: u64,
    pub data: Vec<u8>,
    pub owner: Pubkey,
    pub executable: bool,
  	pub rent_epoch: Epoch,
}

Среди полей аккаунта:

Баланс в лэмпортах lamports
Вектор байтов data, в котором можно хранить любую полезную (или бесполезную) информацию
Владелец owner - 32-байтный адрес on-chain программы, владеющей аккаунтом (об этом далее)
Флаг executable, равный true, если по данному адресу существует on-chain программа

Поле rent_epoch не очень интересно в рамках статьи. Замечу, что тип Pubkey я намеренно назвал 32-байтным адресом. Физический смысл этих 32 байтов будет раскрыт позже, а пока буду называть это просто адресом.

On-chain program

On-chain программа Solana - программа, исполняемая распределенно. Это означает, что при вызове она исполняется несколькими серверами (валидаторами) сети, и истинный результат исполнения определяется путём принятия консенсуса. В других сетях (например Ethereum и Near) эти программы называются смарт-контрактами. On-chain программы Solana принято писать на языке Rust (хотя можно на C), они компилируются в динамические библиотеки для виртуальной машины BPF. Каждая on-chain программа имеет точку входа в виде некоторой функции:

entrypoint!(process_instruction);
pub fn process_instruction(
    program_id: &Pubkey,
    accounts: &[AccountInfo],
    instruction_data: &[u8],
) -> ProgramResult {
    process_somehow(program_id, accounts, instruction_data)
}

Среди аргументов этой функции:

program_id - адрес этой программы
accounts - массив аккаунтов, с которыми (и только с которыми) программа может работать в рамках данного вызова
instruction_data - массив байтов, в котором программе может быть передана любая информация

Вызов программы происходит следующим образом. Предположим, программа уже написана и загружена в сеть. Любой клиент, зная адрес программы, может собрать список аккаунтов, которые хочет передать ей, сформировать инструкцию и с помощью запроса к одному из RPC серверов сети Solana "вызвать" программу с данными аргументами. Теперь посмотрим на структуру AccountInfo, которая появилась в вышеприведённом коде:

pub struct AccountInfo<'a> {
    pub key: &'a Pubkey,
    pub is_signer: bool,
    pub is_writable: bool,
    pub lamports: Rc<RefCell<&'a mut u64>>,
    pub data: Rc<RefCell<&'a mut [u8]>>,
    pub owner: &'a Pubkey,
    pub executable: bool,
    pub rent_epoch: u64,
}

Много непонятных символов для читателей, незнакомых с Rust. Это механизмы языка для подсчета ссылок, контроля "прогулки" ссылок по стеку вызовов и прочее. Не будем на этом останавливаться, а рассмотрим три поля, которых не было в структуре Account:

key - адрес этого аккаунта
is_signer - флаг, означающий факт подписания транзакции, вызывающей эту программу, приватным ключом данного аккаунта
is_writable - флаг, разрешающий программе менять поля этого аккаунта

is_signer и is_writable определяются на стороне клиента перед вызовом программы. Теперь приведу правила, на основе которых в Solana можно гибко строить различную бизнес-логику:

Если аккаунт is_writable, и программа, которой он передан при вызове, является owner'ом этого аккаунта, она может уменьшать поле lamports и менять массив data (увеличивать поле lamports может любая программа)
Поле is_signer программа может проверить, чтобы понять, вызвал ли её физический владелец данного аккаунта

Кажется, становится сложнее. Теперь стоит вернуться к Pubkey, который я до текущего момента называл просто адресом, и прояснить ситуацию. Оказывается, что в Solana адреса программ и аккаунтов зачастую являются публичными ключами из алгоритма цифровой подписи ed25519. Таким образом владельца приватного ключа (будь то человек, хранящий приватный ключ у себя на компьютере, или робот, генерирующий ключи автоматически) можно в некотором смысле считать физическим владельцем аккаунта. В реальности любой клиент может вызвать любую программу, подложив ей в аргументы любые аккаунты. Но факт подписи позволяет строить безопасную логику. Теперь разберём алгоритм ed25519. Я приведу его шаги и покажу корректность проверки подписи в режиме "следите за руками", без доказательств некоторых утверждений. Понимание алгоритма позволит нам на кончиках пальцев почувствовать ещё один механизм Solana, позволяющий строить ещё более гибкую логику.

ed25519

Алгоритм ed25519, кроме прочего, красив тем, что его реализацию для конкретной аппаратуры можно сделать очень быстрой. Вот ряд его свойств, приятных с точки зрения аппаратуры

Быстрая проверка одной подписи

Разработчики алгоритма заточили программное обеспечение под x86_64 набор инструкций и получили высокую скорость проверки подписи на некоторых процессорах Intel.

Ещё более быстрая проверка набора подписей

Проверка набора из 64 подписей позволила разработчикам экономить время за счёт сохранения промежуточных результатов в регистрах и их переиспользования на следующих итерациях. Также было выяснено, что код / данные укладываются в iL1 / dL1 кэш процессора, что также оказывает положительный эффект на скорость проверки набора подписей и предотвращает войну за кэши (cache contention) при многопоточной проверке.

Очень быстрая подпись

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

Быстрая генерация ключей

Вычисление публичного ключа из приватного также оказалось довольно быстрым. Тем не менее, значительную задержку даёт системный вызов Linux, возвращающий случайное число.

Нет обращений к секретным данным

С точки зрения обращений в память ПО спроектировано таким образом, чтобы паттерн обращений в память был полностью предсказуем, а секретные данные не могли утечь через кэш.

Нет условных переходов на основе секретных данных

Паттерн условных переходов также полностью предсказуем, ПО защищено от утечек секретных данных, вызванных ошибками предсказателя переходов

Маленькие подписи

Подпись в сжатом виде имеет длину 64 байта

Маленькие ключи

Публичный (в сжатом виде) и приватный ключи имеют длину по 32 байта каждый

Аппаратура - штука интересная, и говорить о ней можно долго. Я не буду на этом останавливаться, но оставлю полезные ссылки в конце. Теперь поговорим немного о математике. Алгоритм цифровой подписи ed25519 определяется выбором 7 параметров:

Целое число $b \geqslant 10$
Криптографическая хэш-функция H, дающая на выходе - битное число
Простое число $q \cong 1 \ (mod\ 4)$ , задающее поле Галуа
Число $d \in GF(q)$ , не являющееся квадратом в этом поле (это также называют квадратичный невычет)
Точка $B \in E, B \neq (0, 1)$ , где - это группа точек эллиптической кривой над
$E = \{(x, y) \in GF(q) \times GF(q) : -x^2 + y^2 = 1 + dx^2y^2\}$
Простое $l \in [2^{b-4};\ 2^{b-3}]$ такое, что (нейтральный элемент группы)
Способ - битного кодирования элементов

Данная эллиптическая кривая называется скрученной кривой Эдвардса (Twisted Edwards Curve). Групповой закон на ней выглядит следующим образом:

$(x_1, y_1) + (x_2, y_2) = \left(\frac{x_1y_2 + x_2y_1}{1 + dx_1x_2y_1y_2}, \frac{y_1y_2 + x_1x_2}{1 - dx_1x_2y_1y_2}\right)$

Далее определим некоторые числа из GF(q) , как “отрицательные”. Для выбранного способа кодирования будем считать отрицательным, если кодирование лексикографически больше кодирования q-x . Например для q=13 в поле $GF(q) = \{0, 1, 2, 3, 4, 5, .., 12\}$ при little-endian кодировании отрицательными будут считаться $\{1, 3, 5, 7, 9, 11\}$ . Таким образом для кодирования точки на кривой (x, y) достаточно бит: b-1 бит для кодирования и один бит для знака , а сам можно вычислить (в поле GF(q) , разумеется):

$x = \pm \sqrt{(y^2 - 1) / (dy^2 + 1)}$

Ключи, подпись и проверка

Сгенерируем случайным образом -битное число , которое будет являться приватным ключом. Возьмём от него хэш $H(k) = (h_0, h_1, h_2, ..., h_{2b-1})$ , где h_i - биты вычисленного хэша. Вычислим число следующим образом:

$a = 2^{b-2} + \sum_{ 3\leqslant i \leqslant b-3}{2^ih_i}$

Публичным ключом $\underline{A}$ будем считать кодирование точки A = aB (далее кодирования точек буду обозначать подчёркиванием). Ввиду групповой структуры эллиптической кривой точка также лежит на этой кривой. Для подписи сообщения :

Вычислим число $r = H(h_b, h_{b+1}, ..., h{2b-1}, M)$
Найдём точку
Найдём число $S = (r + H(\underline{R}, \underline{A}, M))\ mod\ l$
Сигнатурой будем считать - битную строку $(\underline{R}, \underline{S})$

Для верификации подписи проверяющая сторона должна:

Восстановить точку $R \in E$
Восстановить точку $A \in E$
Восстановить целое число $S \in[0; l-1]$
Проверить равенство $SB = R + H(\underline{R}, \underline{A}, M)A$

Выясним корректность такой проверки.

Домножим на :

$SB = ((r + H(\underline{R}, \underline{A}, M)a)\ mod \ l)B$

Пусть $S^* = r + H(\underline{R}, \underline{A}, M)a$ , тогда для некоторого целого справедливо:

$S^* = nl + S^* \ mod \ l\\S^*\ mod \ l = S^* - nl$

В терминах S^* исходное выражение примет следующий вид:

$SB = (S^* - nl)B\\SB=S^*B-nlB$

Но и выбраны так, что lB = (0,1) - нейтральный элемент, а значит

$SB = S^*B\\SB=rB + H(\underline{R}, \underline{A}, M)aB\\SB=R+H(\underline{R}, \underline{A}, M)A$

Таким образом видно, что равенство выполнено для любого сообщения, подписанного истинным приватным ключом. Параметры, которые разработчики алгоритма рекомендуют к использованию, выглядят следующим образом:

$q = 2^{255} - 19$
SHA-512
Кодирование чисел из - простой little-endian
$l = 2^{252} + 27742317777372353535851937790883648493$
$B = \left(x, \frac{4}{5}\right)$ , положительно в терминах битового кодирования

Таким вот (не)хитрым образом работает алгоритм ed25519. Теперь важно отметить, что из публичного ключа всегда восстанавливается точка на кривой. Но в Solana переменные типа Pubkey не всегда содержат кодирование точки на кривой. Здесь мы подошли к ещё одному механизму безопасности Solana, который называется Program Derived Addresses (PDA).

PDA

Факт того, что какая-то точка не лежит на кривой, с точки зрения ed25519 означает, что не существует приватного ключа такого, что подпись сообщения этим ключом проходила бы проверку относительно публичного ключа $\underline{A}$ . В Solana это научились использовать для того, чтобы наделить on-chain программы возможностью якобы ставить подпись на транзакцию. Сперва важно отметить, что on-chain программа P_1 может быть вызвана не только каким-то off-chain клиентом. Она также может быть вызвана другой on-chain программой P_2 . При этом P_1 может передать в P_2 только те аккаунты, которе есть среди переданных в P_1 . Представим, что в P_1 был передан аккаунт , поле is_signer которого равно false. Если этот аккаунт обладает особым адресом, то P_1 может передать его в P_2 c is_signer: true. Особый адрес вычисляется следующим образом:

Выберем какой-то сид seed (массив байтов), который будет всем известен
Найдём такое 8-битное число bump_seed, что SHA256(p1_id, seed, bump_seed) возвращает 32-байтное число, которое не может быть декодировано в точкуна кривой

Под p1_id здесь я имею в виду адрес программы P_1 . Для полученного адреса не существует приватного ключа, а также он зависит от адреса программы. Рантайм может проверить, что адрес аккаунта с полем is_signer: false действительно вычисляется из адреса вызывающей программы и указанных сидов, и передать вызываемой программе этот аккаунт с полем is_signer: true. Таким образом в Solana программа может быть в некотором смысле физическим владельцем аккаунта. Но осталась пара вопросов:

Почему существуют такие 32-байтные последовательности, из которых нельзя восстановить ?
Как найти bump_seed?

32-байтная последовательность не всегда может быть декодирована в точку ввиду того, что выражение для , которое я приводил выше, вычислимо не для каждого , так как не для каждого числа в поле порядка существует квадратный корень. Элементы поля, для которых существует квадратный корень, называются квадратичными вычетами. Для проверки того, что (x, y) нельзя восстановить из 32-байтной последовательности, можно, например, воспользоваться критерием Эйлера:

$a^{{(q-1)/2}}\cong -1\ mod\ q,\\a = \frac{y^2 - 1}{dy^2 + 1}$

Вот код функции, которая используется в Solana для восстановления точки:

pub fn decompress(&self) -> Option<EdwardsPoint> {
  let Y = FieldElement::from_bytes(self.as_bytes());
  let Z = FieldElement::one();
  let YY = Y.square();
  let u = &YY - &Z;                            // u =  y²-1
  let v = &(&YY * &constants::EDWARDS_D) + &Z; // v = dy²+1
  let (is_valid_y_coord, mut X) = FieldElement::sqrt_ratio(&u, &v);

  if is_valid_y_coord.unwrap_u8() != 1u8 { return None; }

  // FieldElement::sqrt_ratio always returns
  // the nonnegative square root,
  // so we negate according to the supplied sign bit.
  let compressed_sign_bit = Choice::from(self.as_bytes()[31] >> 7);
  X.conditional_negate(compressed_sign_bit);

  Some(EdwardsPoint{ X, Y, Z, T: &X * &Y })
}

Она вернёт None, если не удастся извлечь корень. Ниже код для извлечения корня. Функция возвращает байт, по которому можно определить, удалось ли найти ненулевой корень, а также сам результат.

pub fn sqrt_ratio(
  u: &FieldElement,
  v: &FieldElement
) -> (u8, FieldElement) {
  // Using the same trick as in ed25519 decoding, we merge the
  // inversion, the square root, and the square test as follows.
  //
  // To compute sqrt(α), we can compute β = α^((p+3)/8).
  // Then β^2 = ±α, so multiplying β by sqrt(-1) if necessary
  // gives sqrt(α).
  //
  // To compute 1/sqrt(α), we observe that
  //    1/β = α^(p-1 - (p+3)/8) = α^((7p-11)/8)
  //                            = α^3 * (α^7)^((p-5)/8).
  //
  // We can therefore compute sqrt(u/v) = sqrt(u)/sqrt(v)
  // by first computing
  //    r = u^((p+3)/8) v^(p-1-(p+3)/8)
  //      = u u^((p-5)/8) v^3 (v^7)^((p-5)/8)
  //      = (uv^3) (uv^7)^((p-5)/8).
  //
  // If v is nonzero and u/v is square, then r^2 = ±u/v,
  //                                     so vr^2 = ±u.
  // If vr^2 =  u, then sqrt(u/v) = r.
  // If vr^2 = -u, then sqrt(u/v) = r*sqrt(-1).
  //
  // If v is zero, r is also zero.

  let v3 = &v.square()  * v;
  let v7 = &v3.square() * v;
  let mut r = &(u * &v3) * &(u * &v7).pow_p58();
  let check = v * &r.square();

  let correct_sign_sqrt = check.ct_eq(   u);
  let flipped_sign_sqrt = check.ct_eq(&(-u));

  let r_prime = &constants::SQRT_M1 * &r;
  r.conditional_assign(&r_prime, flipped_sign_sqrt);

  let was_nonzero_square = correct_sign_sqrt | flipped_sign_sqrt;

  (was_nonzero_square, r)
}

Тут используются некоторые трюки для ускорения вычислений, не будем на них останавливаться. Главное, что мы поняли основные идеи того, как именно механизм работает в Solana. Осталось только понять, как найти bump_seed. Какого-то умного алгоритма нет, но он и не нужен. Можно просто в цикле от 255 до 0 перебирать сиды, генерируя новый адрес и проверяя, лежит ли он на кривой. В большинстве случаев поиск останавливается на 255 или 254.

pub fn try_find_program_address(
  seeds: &[&[u8]],
  program_id: &Pubkey
) -> Option<(Pubkey, u8)> {
  let mut bump_seed = [std::u8::MAX];
  for _ in 0..std::u8::MAX {
    let mut seeds_with_bump = seeds.to_vec();
    seeds_with_bump.push(&bump_seed);
    match Self::create_program_address(&seeds_with_bump, program_id) {
      Ok(address) => return Some((address, bump_seed[0])),
      Err(PubkeyError::InvalidSeeds) => (),
      _ => break,
    }
  	bump_seed[0] -= 1;
  }
	None
}

Теперь у нас есть целостное понимание того, как работает PDA и зачем это нужно. В целом я затронул большую часть от всей программной модели Solana. Перейду к заключению

Заключение

В заключение хочется отметить, что Solana - технически очень интересный и сложный проект. Среди самых известных децентрализованных приложений, реализованных на Solana, можно выделить Metaplex - платформу для минта и продажи NFT, а также Serum - первую децентрализованную биржу, торговля на которой производится с помощью ордебука (сейчас они позиционируют себя, как Serum Core - инструментарий для разработки DeFi приложений на Solana). Оба проекта имеют открытый исходный код, который богат примерами для начинающих разработчиков. На этом у меня всё.

Мне удалось затронуть достаточно разные темы, каждая из которых по-своему интересна. Если говорить о Solana, то следующие источники смогут помочь разобраться с ней:

Официальная документация Solana
Репозиторий example-helloworld - то, с чего стоит начать
Репозиторий Solana Program Library - коллекция on-chain программ, написанных разработчиками Solana
Репозитории Metaplex и Agonostic orderbook (on-chain ордербук от Serum)
Мои первые попытки сделать что-то на Solana. Хотя я был молод и глуп, для начала тоже может быть полезно

По части криптографии, которую я затронул, могу порекомендовать следующие материалы:

Нигель Смарт "Криптография" - книга, в которой есть все основы
Доступно о криптографии на эллиптических кривых - длинная, но легкочитаемая статья, поможет начинающим быстро понять суть происходящего
Статья от разработчика из Near о реализации ed25519. В ней можно посмотреть одну из эффективных реализаций
И, конечно же, оригинальная статья о ed25519 со всеми подробностями и сравнениями с другими алгоритмами

Также я достаточно мимолётно упомянул об аппаратной "дружелюбности" ed25519 и о его стойкости к утечками через кэши или миспредикты предсказателя переходов. О том, как работает аппаратное обеспечение компьютеров, и почему есть такие уязвимости, можно узнать в следующих книгах:

Дэвид М. Харрис и Сара Л. Харрис "Цифровая схемотехника и архитектура компьютера"
David A. Patterson, John L. Hennessy "Computer Organization and Design: Hardware / Software Interface"
David A. Patterson, John L. Hennessy "Computer Architecture: A Quantitative Approach"

А по языку Rust на мой взгляд лучшие источники - это:

Rust by examples - примеры от Rust community
The Rust Programming Language - книга, покрывающая (наверное) все механизмы языка (неофициально растбук)
Rust in Action - несколько проектов на Rust под руководством авторов книги
Jim Blandy, Jason Orendorff, Leonora F .S. Tindall "Programming Rust" - полный учебник, аналог растбука

Tags:

Hubs: