ключ формирования кодов используется для
СОДЕРЖАНИЕ
Ключевые выводы
Растяжка ключей и усиление ключей
Функции получения ключей также используются в приложениях для получения ключей из секретных паролей или парольных фраз, которые обычно не имеют желаемых свойств, которые можно использовать непосредственно в качестве криптографических ключей. В таких приложениях, как правило, рекомендуется сделать функцию получения ключа намеренно медленной, чтобы предотвратить атаку методом перебора пароля или словарной атаки на входное значение пароля или ключевой фразы.
Сложность атаки методом перебора увеличивается с количеством итераций. Практическим ограничением количества итераций является нежелание пользователей мириться с ощутимой задержкой при входе в компьютер или просмотре расшифрованного сообщения. Использование соли не позволяет злоумышленникам предварительно вычислить словарь производных ключей.
Хеширование паролей
История
В июне 2017 года Национальный институт стандартов и технологий США (NIST) выпустил новую редакцию своих руководящих принципов цифровой аутентификации, NIST SP 800-63B-3, заявив, что: «Верификаторы ДОЛЖНЫ хранить запомненные секреты [т.е. пароли] в форме который устойчив к атакам в автономном режиме. Запомненные секреты ДОЛЖНЫ быть обработаны и хешированы с использованием подходящей односторонней функции получения ключа. Функции получения ключей принимают пароль, соль и фактор стоимости в качестве входных данных, а затем генерируют хеш пароля. Их цель состоит в том, чтобы сделать каждую попытку подбора пароля злоумышленником, получившим хэш-файл паролей, дорогостоящим и, следовательно, стоимость атаки подбора пароля высока или непомерно высока ».
«Криптография в блокчейнах»: о хеш-функциях, ключах и цифровых подписях
Криптография — это сердце блокчейна, которое обеспечивает работу системы. Архитектура блокчейна предполагает, что доверие между участниками сети базируется на принципах математики и экономики, то есть является формализованным. Криптография также гарантирует безопасность, причем основанную на прозрачности и проверяемости всех операций, а не на традиционном для индустрии ограничении видимости системы (perimeter security).
Различные криптографические техники гарантируют неизменность журнала транзакций блокчейна, решают задачу аутентификации и контролируют доступ к сети и данным в блокчейне в целом. В сегодняшнем материале мы поговорим о хеш-функциях, ключах и цифровых подписях.
Хеш-функции
Хеширование — это процесс преобразования массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины. Например, хеш-функция может принимать строку с любым количеством знаков (одна буква или целое литературное произведение), а на выходе получать строку со строго определенным числом символов (дайджест).
Хеш-функции имеются практически в любом языке программирования. Например, они используются для реализации хеш-таблиц и множеств (HashMap/HashSet в Java, dict и set в Python, Map, Set и объекты в JavaScript и так далее). Отдельная категория хеш-функций — криптографические хеш-функции. К ним предъявляются существенно более строгие требования, чем к функциям, обычно используемым в хеш-таблицах. Поэтому и применяются они в более «серьезных» случаях, например для хранения паролей. Криптографические хеш-функции вырабатываются и тщательно проверяются исследователями по всему миру.
Поэкспериментировать с хеш-функциями можно, написав простую программу на Python:
Функция hash_hex() рассчитывает представление хеша в шестнадцатеричной записи для строки. В приведенном примере используется функция SHA-256 — та же, что и в биткойне.
Хорошая хеш-функция обеспечивает защиту от коллизий (невозможно получить два одинаковых хеша при разных начальных данных) и обладает так называемым эффектом лавины, когда малейшее изменение входных данных значительно преобразует выходное значение. Эффект лавины в хеш-функции SHA-256 выглядит следующим образом:
Хеш-функции в блокчейнах гарантируют «необратимость» всей цепочки транзакций. Дело в том, что каждый новый блок транзакций ссылается на хеш предыдущего блока в реестре. Хеш самого блока зависит от всех транзакций в блоке, но вместо того, чтобы последовательно передавать транзакции хеш-функции, они собираются в одно хеш-значение при помощи двоичного дерева с хешами (дерево Меркла). Таким образом, хеши используются как замена указателям в обычных структурах данных: связанных списках и двоичных деревьях.
За счет использования хешей общее состояние блокчейна — все когда-либо выполненные транзакции и их последовательность — можно выразить одним-единственным числом: хешем самого нового блока. Поэтому свойство неизменности хеша одного блока гарантирует неизменность всего блокчейна.
Ниже приведена рекурсивная реализация дерева Меркла, используемая в биткойне, на языке Python (по ссылке вы найдете примеры работы). На вход функции подается список хешей транзакций. На каждом этапе вычисления последовательные пары хешей склеиваются при помощи хеш-функции; если хешей нечетное число, то последний дублируется. В результате остается единственный хеш, который и является конечным хеш-значением для всего списка.
Хеш-деревья имеют много применений помимо блокчейнов. Они используются в файловых системах для проверки целостности файлов, распределенных БД для быстрой синхронизации копий и в управлении ключами для надежного журналирования выдачи сертификатов. Git использует обобщение хеш-деревьев — направленные ациклические графы на основе хешей. В блокчейне использование хеш-деревьев продиктовано соображениями производительности, так как они делают возможным существование «легких клиентов», которые обрабатывают лишь малую часть транзакций из блокчейна.
Цифровые подписи
Цифровые подписи в блокчейнах базируются на криптографии с открытым ключом. В ней используются два ключа. Первый — закрытый ключ — нужен для формирования цифровых подписей и хранится в секрете. Второй — открытый ключ — используется для проверки электронной подписи. Открытый ключ реально вычислить на основе закрытого ключа, а вот обратное преобразование требует невозможного на практике объема вычислений, сравнимого с брут-форсом.
Существует множество различных схем криптографии с открытым ключом. Две самые популярные из них — это схемы на основе разложения на множители (RSA) и схемы на основе эллиптических кривых. Последние более популярны в блокчейнах из-за меньшего размера ключей и подписей. Например, в биткойне используется стандарт эллиптической криптографии ECDSA вместе с эллиптической кривой secp256k1. В ней закрытый ключ имеет длину 32 байта, открытый — 33 байта, а подпись — около 70 байт.
Общая идея подписей с открытым ключом выглядит следующим образом. Предположим, что Алиса хочет перевести Бобу один биткойн. Для этого она формирует транзакцию, где записывает, откуда его следует брать (указание на предыдущую транзакцию, в которой Алиса получила биткойн от кого-то еще) и кому отправить (открытый ключ Боба). Алиса знает открытый ключ Боба из сторонних источников — Боб может послать его Алисе через мессенджер или даже опубликовать его на сайте.
Затем Алиса подписывает транзакцию, используя свой секретный ключ. Любой узел в биткойн-сети может проверить, что транзакция подписана определенным открытым ключом (аутентификация), с которым до выполнения транзакции был ассоциирован один биткойн (авторизация). Если эти условия выполнены, то переведенный биткойн начинает ассоциироваться с открытым ключом Боба.
Поскольку в блокчейне нет центрального узла, который может авторизовать произвольные транзакции, безопасность системы становится децентрализованной, а вероятность успешного вмешательства в работу блокчейна снижается практически до нуля.
Таким образом, блокчейн использует цифровые подписи для аутентификации и обеспечения целостности транзакций (и иногда блоков). В случае криптовалюты процесс аутентификации означает, что потратить средства может только тот человек, которому они были посланы другой, более ранней, транзакцией. Особенность блокчейна состоит в том, что информация об аутентификации «вшита» в каждую транзакцию, а не отделена от бизнес-логики, поэтому блокчейн считается более защищенным. В обычной системе можно взломать или административно обойти механизм аутентификации и провести манипуляции с бэкэндом, а в блокчейне сделать этого не получится по определению.
HKDF: как получать новые ключи и при чем тут хэш-функции
Часть 1. Общий принцип работы KDF
Замечательная статья с введением в тему: ссылка
затем значение, сгенерированное на первом шаге, «растягивается» в ключ заданной длины или в несколько ключей. Во втором случае задается их суммарная длина.
Рис 1. Алгоритм работы KDF [4]
Рассмотрим каждый из шагов работы функции более детально.
Key Expansion:
На втором шаге из полученного ранее псевдослучайного ключа (PRK) создается ключ заданной длины L, или же набор ключей той же суммарной длины. Также представим этот процесс в виде функции:
Можно заметить, что с достижением первоначальной цели получения ключа заданной заранее длины второй шаг алгоритма справляется в одиночку. Так для чего вообще нужен первый? Не является ли это пустой тратой вычислительных ресурсов?
Оказывается, в этом переходе между шагами кроется наибольшая сложность в разработке функций формирования ключа. Если главный ключ не является случайным или псевдослучайным, KDF не может «растянуть» его так, чтобы получившийся ключ был криптографически стойким. Этим обосновывается необходимость первого шага, на котором из «неидеальных» входных данных формируется псевдослучайный ключ, который служит основой для последующей генерации выходного ключа.
Часть 2. HKDF
HKDF (HMAC Key Derivation Function) является одной из реализаций механизма KDF. В алгоритме KDF в качестве псевдослучайной функции (обозначенной выше как PRF*), а также экстрактора псевдослучайной ключа, используется механизм HMAC.
Зная это, алгоритм HKDF можно записать в виде:
где XTS, SKM и CTXInfo обозначают то же, что и в общем принципе работы KDF, а значения K(i), i = 1. t определяются согласно правилу:
K(1) = HMAC-Hash(PRK, CTXinfo || 0),
K(i+1) = HMAC-Hash(PRK, K(i) || CTXinfo || i), 1 ≤ i Рис 2. Схема работы HKDF [4]
@nusr_et via Instagram
Еще одним необязательным аргументом является контекстная информация. Однако для некоторых приложений она является необходимым условием работы. Дело в том, что контекст позволяет связать получившийся в результате работы алгоритма «длинный» ключ с информацией, специфичной для приложений и пользователей. Такой информацией может служить, например, номера протоколов, идентификаторы алгоритмов и т.д. Это становится особенно важным, когда разные приложения используют HKDF с одним и тем же входным главным ключом, потому что в этом случае контекст позволяет генерировать различные выходные данные. Единственным и крайне важным условием для контекстной информации является ее независимость от входного ключа SKM.
Часть 3. Реализация HKDF
Схема HKDF реализована во многих языках программирования: Java, JavaScript, PHP, Python. Рассмотрим, например, реализацию на питоне, чтобы разобраться в принципе ее работы не только на уровне описания алгоритма, но и работающей функции:
Убедимся в работоспособности примера:
Как можно увидеть, наша функция hkdf сгенерировала ключ output на основе входного ключа «input_key» и соли «add_some_salt». Обратите внимание, что на вход подаются не строки, а последовательности байтов, они лишь представлены в виде строк для наглядности. Конвертируется одно в другое вот так. Длина выходного ключа составила 100 байт, именно столько, сколько мы потребовали первым аргументом!
Иерархическая генерация ключей
Deterministic wallet
В первую очередь давайте определим, что такое детерминистический кошелек (deterministic wallet). Когда мы говорим о генерации ключей, мы часто употребляем слово “кошелек”, потому что в контексте криптовалют владение личным ключом является доказательством владения монетами, а в данном случае кошелек и ключ имеют похожий смысл.
Deterministic wallet — это кошелек, в котором все используемые личные ключи были порождены из одного общего для всех ключей секрета. Особенность состоит в том, что есть возможность из одного секрета породить сколько-угодно пар ключей для электронной подписи. Можно использовать новые адреса для каждого входящего платежа и сдачи.
Удобно, что ключи такого кошелька можно легко перенести на другое устройство, сделать резервную копию и потом восстановить, потому что фактически нужно резервировать только один основной секрет. Кроме того, все порожденные из основного секрета личные ключи, друг с другом никак не связаны. Нельзя проследить и связь между порожденными адресами (определить что все они принадлежат одному пользователю), а имея порожденный личный ключ, нельзя восстановить общий секрет.
Кодирование основного секрета
Теперь поговорим о кодировании основного секрета. Здесь имеется некоторый стандартизированный подход, который был определен в BIP39. Это так называемое Check Encoding кодирование основного секрета в мнемоническую фразу — набор слов, который легко записать на бумагу и при необходимости запомнить. При вводе есть возможность проверить контрольную сумму, то есть выявить ошибку, если такая имеется, с довольно большой вероятностью.
Как это работает? Фактически у вас есть основной секрет (Entropy) — данные, из которых разворачиваются все личные ключи кошелька. Этот секрет может иметь разную длину. Что касается контрольной суммы: на каждые 32 бита Entropy приходится 1 бит контрольной суммы, то есть Checksum по формуле рассчитывается, как длина Entropy в битах, разделенная на 32.
Entropy конкатенируется с контрольной суммой, которая рассчитывается, как двойной хеш SHA-256 (SHA-2 на длине 256 бит), после чего отрезается необходимое количество битов. Конкатенированные данные переводятся в другую систему счисления: из двоичной в систему счисления по основанию 2048 (как видим, 2048 — это 
). И если сложить длину битов Entropy и контрольной суммы, то получится число, кратное 11-ти. Таким образом, мы получаем количество слов в выходной мнемонической фразе.
Фактически данные “нарезаются” частями по 11 бит. Есть словарь, состоящий из 2048 слов (), к которым применены определенные требования. По умолчанию язык словаря английский, но может использоваться любой. Слова не должны превышать определенную длину (обычно предел до 7 символов). Все они должны быть закодированы в UTF-8 с определенной нормализацией всех символов. Обязательной является уникальность каждого слова по первым четырем символам.
Первые четыре символа однозначно определяют слово в словаре, а остальные символы используются, чтобы завершить это слово до удобной формы для чтения, запоминания и т. д. Таким образом каждый фрагмент данных, состоящий из 11-ти бит, получает однозначное соответствие в виде слова из словаря. Если Entropy вашего секрета составляет 256 бит, то данные для кодирования составят 264 бита, а ваша мнемоническая фраза будет содержать 24 слова. Это основной подход к кодированию секрета кошельков в BIP39, который применяется на практике чаще всего.
Для того чтобы в будущем делать резервную копию и использовать ее, вам предлагается выписать эту фразу на внешний носитель. Лучше всего подойдет бумага, которую вы будете хранить в надежном месте. Так вы можете восстановить полный доступ ко всем своим ключам.
Типы детерминистических кошельков
Детерминистические кошельки бывают двух типов. Рассмотрим основные их отличия.
Первый из них самый простой. Основной секрет здесь конкатенируется с индексом дочернего ключа, который мы хотим получить, после чего конкатенированные данные хешируются. Чаще всего это происходит с помощью хеш-функции SHA-256.
Ко второму типу относятся иерархические детерминистические кошельки (hierarchical deterministic wallets, HD wallets), принципы которых определены в BIP32, и являются очень распространенным подходом к иерархической генерации ключей.
Deterministic generation
Рассмотрим отличия этих типов кошельков на схеме.
Обычный детерминистический кошелек имеет некоторый seed, из которого напрямую генерируется огромное множество личных ключей. Их количество может быть ограничено только размерностью индекса, который конкатенируется к секрету перед хешированием. Обычно это 4 байта, то есть пространство возможных вариантов допускает около 4 миллиардов уникальных ключей детерминистического кошелька. На практике этого должно хватить для любой ситуации.
Hierarchical deterministic generation
Перейдем к иерархическому детерминистическому кошельку, схема разворачивания ключей которого представлена пока в упрощенном виде. Есть seed, из которого напрямую получается пара мастер-ключей. Если в обычном детерминистическом кошельке мы получаем личный ключ, то здесь мы получаем пару ключей. Более того, есть уровни иерархии, на каждом из которых мы рассчитываем индекс для порождения дочернего ключа. Мы также можем строить ветки открытых ключей и ветки личных ключей.
Уровни иерархии
В отношении HD кошельков стоит отметить, что согласно правилам BIP32 на каждом уровне иерархии узел порождения имеет три объекта: личный ключ (private key), открытый ключ (public key) и код цепочки (chain code), который используется для порождения следующего уровня иерархии.
Схема иерархической генерации
Рассмотрим более детально схему генерации ключей по BIP32.
Все начинается с seed, его еще называют master seed, из которого рассчитывается нулевой уровень иерархии — пара master keys и chain code.
Из пары мастер-ключей может генерироваться огромное множество пар ключей с определенными индексами. Формируется новый уровень иерархии, который используется для генерации аккаунтов. Допустим, у одного пользователя есть seed и он хочет создать несколько адресов, которые будут отличаться друг от друга. Монеты этих адресов не будут смешиваться, не будут публиковаться вместе, а в готовых транзакциях между ними нельзя будет найти связь. Данные ключи будут использоваться полностью отдельно друг от друга. В одном из аккаунтов группа ключей будет использоваться для рабочего бюджета, в другом — для личного бюджета, а еще один аккаунт — для черной бухгалтерии. Монеты не будут смешиваться друг с другом.
Следующий уровень иерархии определяет разные цепочки генерирования ключей. Чаще всего используются цепочки с индексами 0 и 1. Цепочка с индексом 0 будет генерировать конечные ключи для формирования адреса для входящих платежей, а цепочка с индексом 1 будет генерировать кошельки, на которые будут приходить монеты, отправленные пользователем себе, то есть сдача. Это нужно, чтобы кошелек на программном уровне отличал отправленные извне платежи от сдачи, рассчитывал изменения баланса каждой транзакции и составлял наглядный список с историей всех платежей. Это упрощает разработку кошелька и его использование для повседневных платежей.
Hash-based message authentication code
Теперь давайте перейдем к математической составляющей процессов иерархической генерации ключей. Начнем с того, что рассмотрим hash-based message authentication code. Это другой класс расчета хеш-функций. Отличается она тем, что принимает на вход два значения, а не одно. Первое значение — это секретный ключ, а второе — само сообщение.
K — ключ
m — сообщение
opad, ipad — некоторые константные значения, необходимые для формирования отличающихся друг от друга ключей на разных этапах хеширования.
В качестве хеш-функции используется SHA-512.
Особенность состоит в том, что для использования HMAC, нужно владеть секретным ключом, для того чтобы получить правильное хеш-значение сообщения.
Итак, для расчета хеш-значения по HMAC значение ключа XOR-ится с константным значением ipad, после чего результат хешируется. К этому значению конкатенируется сообщение, после чего рассчитывается XOR ключа с константным значением, конкатенируется с хеш-значением, после чего снова хешируется. В итоге мы получаем 512 бит хеш-значения.
Функции деривации
Давайте рассмотрим несколько функций, которые используются при расчете иерархических ключей.
Первым делом нас интересует преобразование master seed в пару master key. После этого нужно получить из личного родительского ключа дочерний личный ключ и дочерний открытый ключ. Во втором случае используется точно такая же функция, как и в первом, но добавляется умножение числа на базовую точку, поэтому отдельно не будет рассматриваться. Далее следует получение из открытого родительского ключа дочернего открытого. Стоит отметить, что получение из родительского открытого ключа дочернего личного невозможно. Это ограничение обусловлено определенными свойствами, присущими HD кошелькам, которые мы рассмотрим дальше.
Итак, пройдемся по каждой из функций порождения отдельно.
Для получения мастер-ключа из мастер-сида используется функция HMAC, где в качестве ключа передается константная строка “Bitcoin seed”, а в качестве сообщения сами данные основного секрета. Таким образом, получается хеш-значение длиной 512 бит, которое мы рассматриваем как две части: левую и правую. Левая часть является master private key, а правая часть будет chain code. Дальше эти значения будут использоваться для порождения последующих уровней дочерних ключей.
Для того чтобы получить master public, достаточно умножить значение базовой точки на значение master private key. Как видим, это происходит по аналогии с обычными ключами в группе точек на эллиптической кривой.
Теперь посмотрим как происходит дочерний личный ключ из родительского личного.
Снова воспользуемся функцией HMAC. В качестве ключа мы передаем chain code текущего уровня иерархии, а в качестве сообщения — конкатенацию, где первой частью будет личный родительский ключ, умноженный на базовую точку. Фактически это приведение к точке и сериализация этой точки. Конкатенация происходит с индексом дочернего ключа, который мы хотим получить, сериализованного в 32 бита, то есть в 4 байта.
По результату работы функции HMAC мы получаем значение I, и снова его рассматриваем по отдельности: левую и правую части выходных значений по 256 бит. Тогда дочерний личный ключ 
мы рассчитываем путем прибавления к левому выходному значению 
значения родительского личного ключа. Сложение выполняем по модулю n, где n — это порядок базовой точки эллиптической кривой, для того чтобы не превысить максимальное значение личного ключа. Таким образом, мы получили дочерний личный ключ.
Соответственно, дочерний chain code будет равен правому выходному значению функции HMAC, то есть 
. Если мы хотим из личного родительского ключа найти дочерний открытый ключ, умножаем значение на значение базовой точки на эллиптической кривой. Так мы получим открытый ключ 
.
Как же нам рассчитать из открытого родительского ключа дочерний открытый ключ?
Здесь расчет будет немного иным. Мы передаем в качестве ключа chain code текущего уровня иерархии в функцию HMAC, после чего мы сериализируем родительский открытый ключ и конкатенируем его с нужным индексом, сериализованным в 32 бита. Входные данные получены точно таким же образом, как и в предыдущем случае. Для расчета открытого ключа мы берем левую часть выходного значения функции HMAC, и рассматриваем его, как 256 бит, взятых по модулю порядка базовой точки, приводим к точке на эллиптической кривой, то есть умножаем на базовую точку, после чего складываем результат с родительским открытым ключом. Результатом сложения будет тоже точка, и это будет открытый дочерний ключ. Chain code для данного ключа будет правая часть выходного значения функции HMAC.
Соответствие ключей друг другу
Тут может возникнуть логический вопрос о том, как личный и открытый ключи, полученные разным образом, будут соответствовать друг другу. Действительно ли из порожденного публичным образом открытого ключа можно получить точно такое же значение, взяв личный ключ, полученный другим образом, и умножив его на базовую точку? Это легко проверить.
Если вспомнить, как мы рассчитывали личный дочерний ключ, и умножить его на базовую точку, то есть привести к функции point, а потом вспомнить расчет дочернего открытого ключа и сравнить эти расчеты, то мы увидим, что если рассматривать родительский открытого ключ как произведение личного родительского ключа на базовую точку, то мы увидим, что были произведены одни и те же расчеты, просто в разном порядке.
В одном случае мы сложили личные ключи и умножили на базовую точку, а во втором случае мы сначала умножили значения на базовую точку, а потом сложили их и получили результат. Основываясь на том, что операция сложения точек на эллиптической кривой является аддитивной, мы можем сказать, что эти два значения равны — мы получим один и тот же открытый ключ, рассчитанный двумя способами.
Пример открытого ключа
Ради интереса мы можем посмотреть на пример открытого ключа, который был получен для тестовых значений и расчетов BIP32. Если наша Entropy состояла из 128 бит, то в шестнадцатеричной системе счисления это будет выглядеть, как на изображении ниже.
Это же значение, закодированное в мнемоническую фразу по BIP39, будет выглядеть как показанные 12 слов. Если использовать эту мнемоническую фразу как мастер-сид для иерархической генерации ключей, то вы получите такой master private key с соответствующим chain code по 256 бит.
Расширенные ключи
Есть еще такие понятия как расширенный открытый ключ и расширенный личный ключ. Как это используется? Чтобы лучше понять, опишем наглядную ситуацию.
Допустим, у нас есть определенный пользователь и некоторый сервис. Сервис с определенной частотой передает платежи, например в биткоинах, пользователю. И пользователь, и сервис заинтересованы в том, чтобы использовать для каждого платежа новый адрес, для того чтобы усложнить для внешнего наблюдателя установление факта и запутывание истории взаимодействия друг с другом.
В самом простом случае это выглядело бы так: пользователь для каждого входящего платежа формирует новую пару ключей, вычисляет адрес, который передает сервису, после чего сервис может сформировать транзакцию и выполнить платеж. Однако это неудобно ни для одной из сторон, если интенсивность этих платежей высокая.
Расширенный открытый ключ
В подобной ситуации от неудобств помогает избавиться расширенный открытый ключ (extended public key, xPubKey). Пользователь может дать возможность стороннему сервису вместо себя генерировать такие адреса, которые будут известны сервису, но личные ключи будут только у пользователя. Сервис может генерировать какое-угодно количество адресов без ведома пользователя и отправлять на них средства, а пользователь может, когда ему будет удобно, развернуть личные ключи и получить доступ к любому из этих адресов.
Как это работает? Пользователю нужно сгенерировать новый аккаунт на втором уровне иерархии ключей, рассчитать для него открытый ключ и chain code для текущего уровня. После этого нужно передать сервису и открытый ключ, и chain code. Для удобства было введено кодирование Base58Check Encoding, о котором мы говорили (здесь есть специальная версия). Далее, конкатенируется открытый ключ, chain code и контрольная сумма. Это все кодируется в систему счисления по основанию 58 и мы получаем уже закодированный по определенному стандарту открытый расширенный ключ. Он начинается с символов “xpub”, что легко распознается. Он будет выглядеть, как показано на изображении.
Сервис может принять такой ключ и развернуть по BIP32 открытые ключи для пользователя, из них получать адреса и платить на них. Однако соответствующие личные ключи может вычислить только пользователь.
Hardened derivation
В иерархическом порождении ключей есть такое понятие, как hardened derivation. Это такой подход, который не позволяет рассчитывать дочерние открытые ключи из соответствующего родительского открытого ключа. От нормального порождения это отличается тем, что в нем мы используем в качестве сообщения функции HMAC конкатенацию сериализованной точки как родительского открытого ключа, а в hardened derivation мы используем сериализацию родительского личного ключа.
Кроме того, отличается вычисление индекса. Индекс в нормальном порождении напрямую сериализуется в 32 бита, а в hardened derivation он несколько преобразуется: к нему добавляется константное значение 
, что устанавливает старший бит в 1 (становится легко отличать типы деривации). Соответственно, пространство вариантов возможных ключей одинаково как для нормального порождения, так и для hardened derivation и равно .
Таким образом, имея родительский открытый ключ и hardened derivation, невозможно рассчитать дочерние открытые ключи. Если злоумышленник получит родительский открытый ключ, то он не сможет вычислить дочерние ключи. Следовательно, не сможет вычислить адреса и связь их с полученным родительским ключом. В случае normal derivation, то есть в обычном, такой функцией можно пользоваться и прослеживать взаимосвязь адресов между собой.
Пути порождения
Давайте поговорим о путях, по которым могут порождаться ключи.
На каждом уровне иерархии есть определенный индекс, который определяет аспекты порождения ключей. Путь от Мастер-ключа до конечного ключа может записываться через слэши в виде индексов. Если речь идет о личном ключе то запись начинается с маленькой “m”, а если речь о порождении открытого ключа, то с большой “M”. Если индекс обозначен апострофом, то следует понимать, что речь идет о hardened derivation, без апострофа — normal derivation.
Рассмотрим один из популярных путей порождения ключей, который используется в BIP32, где и были определены иерархические ключи.
Он использует такой путь, где нулевым уровнем иерархии является мастер-ключ. Далее следуют индексы аккаунтов, которые обозначают одного и того же пользователя, после чего идут цепочки, где могут быть цепочки адресов, которые публикуются вовне для принятия входящих платежей, а с индексом 1 будут создаваться те цепочки, на которые сам пользователь отправляет себе платежи (чаще всего это сдача). Конечный индекс будет использоваться для порождения тех ключей, из которых будут рассчитываться адреса.
Для того чтобы по стандарту BIP32 рассчитать самый первый ключ с индексом 0, мы будем иметь m, 0 с порождением hardened, chain — 0, индекс — 0 (m/0’/0/0). Так мы получим путь для первого иерархически порожденного ключа.
Существует предложение по улучшению Биткоина, оно называется BIP43, которое предполагает запись в первый уровень иерархии номера улучшения, которое предлагает новый путь порождения (m/bip_number’/*).
Таким образом, появился BIP44, который использовал особенность предыдущего предложения, то есть для первого уровня иерархии записывается индекс 44, а предложил следующие улучшения: в индексе второго уровня иерархии записывать определенное значение, которое будет соответствовать типу монеты, которую мы используем для данного кошелька. Теперь в одном кошельке могут разворачиваться и использоваться ключи для разных валют.
Для Биткоина путь будет выглядеть, как “m/44’/0’/0’/0/0”, для Bitcoin testnet — “m/44’/1’/0’/0/0”, для Litecoin — “m/44’/2’/0’/0/0”, для Dash — “m/44’/5’/0’/0/0”. Интересно, что Ethereum использует точно такую же эллиптическую кривую для расчета ключей и электронно-цифровой подписи и для его кошелька путь будет выглядеть так “m/44’/60’/0’/0/0”.
Есть еще одно улучшение — BIP45. Улучшение нацелено на то, чтобы определить правила порождения ключей в случае их использования в multisignature кошельках и формирования адресов по BIP16, то есть P2SH. Он включает в себя предложение BIP43 и указывает на первом уровне иерархии индекс 45, на втором же уровне иерархии он требует указания подписанта (cosigner).
Например, есть правило мультиподписи 3-из-5. Следовательно есть 5 подписантов, но чтобы потратить монеты, нужно как минимум 3 подписи. Таким образом, каждый из подписантов будет иметь HD кошелек со своим мастер-сидом, а в своем пути будет указывать свой порядковый номер. Он может быть рассчитан, как индекс при сортировке ключей, порожденных на первом уровне иерархии каждого пользователя. Допустим, на первом уровне произошло порождение ключей у каждого пользователя, они обмениваются друг с другом, сортируют и узнают, у кого какой индекс для второго уровня иерархии. Это нужно, чтобы в дальнейшем исключить необходимость взаимодействовать подобным образом, а сразу правильно генерировать адреса и знать свой порядковый номер.
То есть можно единожды обменяться расширенным открытым ключом, чтобы потом самостоятельно, независимо от других участников группы, формировать multisignature адреса и принимать на них платежи.
Вопросы
Перейдем к часто задаваемым вопросам.
— Как отличаются master seeds в разных монетах?
Seed — это случайно сгенерированное число, какая-то последовательность бит, либо это мнемоническая фраза, сгенерированная, например, по BIP39, которая используется для порождения ключей. Она может быть использована как для одной монеты, так и для любой другой — не обязательно использовать разные мнемонические фразы для разных валют. Тем более, что есть BIP44, который определяет правила генерации ключей для разных валют из одной и той же мнемонической фразы. Эти личные ключи не будут пересекаться друг с другом, а будут использоваться для разных адресов разных валют.
— Словарь из BIP39, где 2048 слов для мнемонической фразы стандартизирован? Можно ли его использовать во всех кошельках и приложениях?
Дело в том, что этот стандарт описан для BIP39. Именно для BIP39 есть словари: английский, два японских, китайский, итальянский, русский, украинский и т. д. То есть если некоторое приложение заявляет, что оно использует BIP39 и дает возможность импортировать и экспортировать мнемоническую фразу, значит и набор слов оно использует тот же. Однако есть кошельки, которые используют не BIP39, а свою модификацию. Нужно смотреть описание кошелька и использовать либо стандартизированную, либо свою собственную разработку, либо разработку сервиса, который предлагает кошелек.
— На биржах и централизованных хранилищах типа Coinbase ключи кошельков всех пользователей генерируются из одной общей для всех сид-фразы или нет?
Сложно сказать, потому что они свою внутреннюю структуру не открывают, но те новые сервисы, которые появляются, могут либо отдельно генерировать ключи, либо использовать стандарт BIP32, либо использовать его модифицированную версию. Те сервисы, которые существовали еще до того, как появились стандарты по иерархической генерации ключей, скорее всего, продолжают генерировать просто отдельные личные ключи. Возможно, так ими проще управлять, если идет большой оборот всех ключей.
— Ключ — это точка на эллиптической кривой, то есть два очень больших числа X и Y?
Открытый ключ — да, это точка на эллиптической кривой, а личный ключ — это натуральное число, которое показывает, сколько раз саму с собой нужно сложить базовую точку. Сам открытый ключ состоит из двух значений — это координаты X и Y, каждая из которых имеет размер 256 бит.
— Что такое “приведение к точке” и сериализация точки и индекса?
Приведение к точке значит, что есть натуральное число, которое мы рассматриваем, как личный ключ. Базовую точку мы складываем саму с собой столько раз, то есть в группе точек на эллиптической кривой определена операция только сложения, то можно произвести умножение точки на натуральное число. Под сериализацией точки подразумевается запись определенным образом двух координат. Возможно, это сжатая запись, но не обязательно. Сжатая в смысле, что одну из координат, а именно Y преобразуют в знак, потом данные подставляются в уравнение и смотрят, где находится точка: выше или ниже. В случае сериализации индекса нужно понимать, что обычное число, которое, в зависимости от размера, можно записать в байтах или битах. Чем больше число, тем больший объем данных понадобится. В случае с теми вычислениями, которые мы рассмотрели, требуется число определенной длины. Нужно сериализовать его в определенную длину — 4 байта. В итоге, имеется в виду приведение индекса к 4-х байтовому числу. Если там остаются незаполненными старшие значения, значит они будут нулевыми.
— Кто придумал эти расчеты для derivation функций HD кошельков? Почему именно такие формулы, где есть обоснования и где можно подробнее об этом почитать?
Подробнее можно почитать именно в BIP32, если вас интересует мнемоническая фраза, то в BIP39, и т. д. Можно открыть GitHub, найти пользователя под ником Bitcoin. У него есть репозиторий Bitcoin, где хранится исходный код Биткоина, а есть репозиторий BIPs (первоисточник), где записаны все предложения по улучшению Биткоина.
Придумали делать расчеты именно так, потому что это завязано на группе точек эллиптической кривой. Когда хотели добиться такой функциональности, которая позволяет рассчитывать отдельно ветки открытых и личных ключей, при этом сохранить их соответствие друг другу, это был самый простой вариант реализации. Фактически разработчики использовали самый простой вариант, который позволяет добиться интересных свойств, используя ту криптографию, которая проверена временем. Авторов предложенных улучшений достаточно много. Сообщество Биткоина, участники которого предлагают какие-то разработки улучшений и математических преобразований, достаточно большое.
— Hardened derivation всегда только на втором уровне иерархии?
Все зависит от ситуации. В случае с порождением ключей для мультиподписи имеет смысл делать hardened derivation только на первом уровне иерархии. В BIP44 hardened derivation применяется к первым трем уровням: на первом уровне находится номер самого BIP, на втором — номер аккаунта, где это актуально, на третьем — номер валюты, где это тоже имеет смысл. Допустим, вам вряд ли понравится, если вы выложите открытый ключ, а через него люди смогут отследить все ваши адреса в Биткоине. Если вы используете аккаунт для получения платежей от определенных сервисов, тогда вы можете разглашать этот ключ и hardened derivation вам здесь не нужен.
— Где возможно применить иерархическую генерацию ключей?
Можно применить при работе с биржей, чтобы биржа все время вам платила на разные адреса. Хотя в данном случае лучше уж вручную все это организовать. Наиболее актуально это для цифровых кошельков повседневного использования, потому что здесь очень простой процесс создания резервной копии личных ключей и восстановления кошелька. Также поддерживается генерация ключей для разных валют, а сам стандарт уже используется в разных реализациях цифровых кошельков. Ключи между такими кошельками удобно переносить, используя одну и ту же мнемоническую фразу.
Данной теме посвящена одна из лекций онлайн-курса по Blockchain “Иерархическая генерация ключей”.