Для начала познакомимся с первыми 3 понятиями: публичный криптоключ, цифровая подпись и криптографическая хеш-функция.
Ключ — это секретная информация, используемая криптографическим алгоритмом при зашифровании/расшифровании сообщений, постановке и проверке цифровой подписи, вычислении кодов аутентичности (MAC). При использовании одного и того же алгоритма результат шифрования зависит от ключа. Для современных алгоритмов сильной криптографии утрата ключа приводит к практической невозможности расшифровать информацию.
Асимметричные ключи — ключи, используемые в асимметричных алгоритмах. Более точно, они являются ключевой парой, поскольку состоят из двух ключей:
Закрытый ключ — ключ, известный только своему владельцу. Только сохранение пользователем в тайне своего закрытого ключа гарантирует невозможность (при современных вычислительных мощностях практически невозможно) подделки злоумышленником документа и цифровой подписи от имени заверяющего.
Открытый ключ — ключ, который может быть опубликован и используется для проверки подлинности подписанного документа, а также для предупреждения мошенничества со стороны заверяющего лица в виде отказа его от подписи документа. Открытый ключ подписи вычисляется, как значение некоторой функции от закрытого ключа, но знание открытого ключа не дает возможности определить закрытый ключ.
Главное свойство ключевой пары: по секретному ключу легко вычисляется открытый ключ, но по известному открытому ключу практически невозможно вычислить секретный. В алгоритмах ЭЦП (электронной цифровой подписи) подпись обычно ставится на секретном ключе пользователя, а проверяется на открытом. Таким образом, любой может проверить, действительно ли данный пользователь поставил данную подпись. Тем самым асимметричные алгоритмы обеспечивают не только целостность информации, но и её аутентичность. При шифровании же наоборот, сообщения шифруются на открытом ключе, а расшифровываются на секретном. Таким образом, расшифровать сообщение может только адресат и больше никто (включая отправителя). Использование асимметричных алгоритмов снимает проблему распространения ключей пользователей в системе, но ставит новые проблемы: достоверность полученных ключей. Эти проблемы более-менее успешно решаются в рамках инфраструктуры открытых ключей (PKI).
Теперь обратимся к математике, как это работает на простейших примерах:
Вернемся частично к понятию симметричный и асимметричный алгоритм. Симметричный алгоритм (функция) - это например удвоение числа. Т.е. изначально было число 4, мы его умножили на 2, получили 8. Можно совершить обратную операцию над 8 и получить 4. Асимметричный алгоритм (функция) - это например вычисление по модулю (вида Y^x(mod P)). В качестве примера можно воспользоваться алгоритмом Диффи-Хеллмана:
(https://image.ibb.co/fV3Pgw/alice.jpg) (https://imgbb.com/)
Или видео:
Вернемся конкретно к асимметричному шифрованию. В общем суть данного алгоритма заключается в том, что принимающая сторона перед приемкой сообщения генерирует пару ключей на основе алгоритма модульной арифметики (принцип такой же как и в алгоритме Диффи-Хеллмана), собственно приватный и публичный ключ. Отправитель перед отправкой получает публичный ключ и шифрует сообщение данным ключом, после чего данное сообщение можно расшифровать только приватным ключом, который хранится в секрете у принимающей стороны.
(https://image.ibb.co/fMeY8b/Alice_2.jpg) (https://imgbb.com/)
Хеширование, реже хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Теперь рассмотрим данное определение подробнее.
Воспользуемся следующей хеш-функцией: f(x) = x mod M. M - количество выходных данных. Т.е. результат работы хеш-функции - остаток от деления на число всех возможных хешей.
Попробуем ей воспользоваться. Пусть x=15,8,10; M=4. Т.е. f(x) = x mod 4. На выходе получим значения f(x)=3,0,2. Для более надежного использования данной хеш-функции, следует использовать большое простое число M. Также стоит отметить такой случай как коллизии, т.е. при разных входных данных получаются одинаковые хеш-функции. В качестве примера в функцию f(x) = x mod 4 подставим числа 15 и 23, они дадут одинаковый результат - 3. В общих чертах - результат работы хеш-функции должен быть уникальным, для ее стойкости.
Углубимся, и перейдем непосредственно к криптографическим хеш-функциям.
1. Хеш-функции должны быть непредсказуемыми, то есть выглядеть похожими на случайные генераторы битовых наборов. Если исходная строка x изменилась немного (на 1 бит), то хеш-значение f(x) должно измениться в большинстве из h бит. (Данный эффект называется лавинным)
2. Должно быть трудно найти прообраз для любого заданного хеш-значения (стойкость к восстановлению прообраза). (Предполагается, что все хеши уникальны, или крайне близки к этому)
3. По заданному тексту x должно быть трудно найти z со свойством f(x) = f(z) (стойкость хеш-функции к коллизиям первого рода или поиску второго прообраза). (Пример с модулем выше)
4. Должно быть трудно найти произвольные x = z, такие что f(x) = f(z) (стойкость хеш-функции к коллизиям второго рода).
Соответственно, метод с остатком от деления не подойдет. Для этого используются сложные функции типа MD, SHA-1, SHA-2 и прочие. Хеш-функция биткоина - SHA-256, является вариацией алгоритма SHA-2. Более подробно про данный алгоритм можно прочитать https://ru.wikipedia.org/wiki/SHA-2.
Для чего нам нужны такие сложности и как это применить (на примере биткоина):
Bitcoin оперирует хеш-суммой публичного ключа, как адрес для передачи монет. Объявить чей-либо bitcoin адрес во всеуслышание — ничего не стоит. Узнать исходный ключ по его хешу не предоставится возможным исходя из сложности алгоритма хеш-функции. А сама пара ключей будет использована лишь однажды — при передаче прав собственности. На этом жизнь пары ключей заканчивается.
(https://image.ibb.co/fZpF4G/HASH.jpg) (https://imgbb.com/)
PUB1 — публичный ключ
PRIV1 — секретный ключ
HASH1 или HASH(PUB1) — хеш-сумма публичного ключа (биткойн-адрес).
HASH2 или HASH(PUB2) — хеш публичного ключа следующего владельца.
Возьмем пример попроще. Пусть у нас есть владелец автомобиля, в чьем праве собственности никто не сомневается.
— Собственник на публичном собрании (ярмарке, телевизионном шоу) показывает всем хеш своего публичного ключа HASH(PUB1), заводской номер автомобиля, и все соглашаются с этим — никто не предъявляет претензий.
— До момента продажи оба ключа PUB1, PRIV1 продавца остаются в секрете. Известен только HASH(PUB1) и соответствующий ему заводской номер автомобиля.
— Как только собственник хочет продать автомобиль какому-либо покупателю — он пишет открытое письмо, в котором указывает заводской номер и хеш-сумму публичного ключа второго владельца HASH(PUB2). И конечно же подписывает письмо своим секретным ключом PRIV1, прилагая публичный ключ PUB1.
— После передачи собственности секретный ключ перестает быть актуальным — второго такого письма быть не может. Публичным ключом можно проверить само письмо, удостоверить второго собственника.
— О втором собственнике ничего неизвестно кроме HASH(PUB2), до тех пор пока он не передаст права третьему владельцу. И эта цепочка может быть бесконечной.
— Подписывая передачу прав с использованием ЭЦП, собственник не только удостоверяет себя, но и накладывает на себя обязательство передачи. Как говорится: «слово — не воробей, вылетит — не поймаешь».
— Благодаря HASH(PUB) получается двойная защита. Первая загадка — узнать публичный ключ по его хешу. Вторая загадка — подписаться чужим секретным ключом.
(https://preview.ibb.co/hCOiPG/HASH2.jpg) (https://ibb.co/kQHorw)
Если заменить автомобиль на bitcoin, то вместо заводского номера выступает хеш предыдущей транзакции. А вся цепочка собственников хранится публично у каждого пользователя.
Теперь обратимся к вопросу - чем же занимаются майнеры и как с этим связаны хеш-функции.
Чтобы не было возможности дважды потратить монеты, должна быть единая история всех сделок. Тогда в журнал будет попадать только первая транзакция (письмо передачи прав на монеты), или в крайнем случае одна из нескольких. Для этого транзакции объединяются в блоки и признаются только «красивые» блоки. «Красивый блок» трудно найти, это подобно тому как из тонн золотой руды попадается лишь один стоящий самородок. В нашем случае хеш-сумма блока должна содержать определенное количество нулей.
Блок состоит из предыдущего блока (хеш-суммы), хеш-суммы всех включенных транзакций, и случайно перебираемого числа.
Пример bitcoin-блока с сайта blockexplorer.com:
* Hash: 00000000000001c21dbf4715d5da1a288061faa21e950dd8df6ae25c8b55d868
* Previous block?: 000000000000056a7dcf283f627c2a17c55ffe1937a6ed2bc467d9c524311da2
* Difficulty: 1 690 895.803052 ("Bits": 1a09ec04)
* Transactions: 184
* Total BTC: 4251.63216933
* Size: 58.913 kilobytes
* Merkle root: 98c5d975bf556f0344770eee7ab31688a1c108223c14cea908ff99b0ab8fe947
* Nonce: 3723473450
Видите сколько нулей в начале хеш-суммы блока? Вот поэтому его так трудно было найти. Но каждый легко может проверить подлинность «красоты» блока. Количество нулей в хеше выбирается таким образом, чтобы каждый блок появлялся на свет приблизительно раз в 6-10 минут. За нахождение блока выдается поощрение(coins). Также нашедшему выдаются все сборы от платежей (transactions fees), за те транзакции, которые включены в его блок.
Единая история достигается за счет того, что всегда побеждает наиболее длинная цепочка блоков. (Проблема "51% атаки" и "double-spending"). Не проблема, если от биткойн-сети будет отколот изолированый кусочек пользователей — впоследствии все отколотые транзакции войдут в более длинную цепочку (с учетом сложности).
Немного тонкостей работы:
— На деле в транзакции указывается алгоритм проверки, помимо самого биткойн-адреса. Внутри биткойн встроен собственный примитивный, намеренно обрезанный язык программирования, который позволяет сделать сложные транзакции. Например можно запрограммировать, чтобы деньги отправлены нескольким адресатам (как сейфовая ячейка с несколькими ключами). Или включить ограничения по времени на трату денег (не раньше 2013 года) и т.д.
— Транзакции в блок укладываются в виде дерева хешей. Таким образом в дальнейшем можно будет выкидывать завершенные транзакции для экономии места на диске, не нарушая целостности блоков.
— Биткойн-адрес содержит в себе контрольную сумму. Поэтому в адресе нельзя ошибиться пропустив или заменив одну или несколько символов.