Хеширование, реже хэширование (англ. 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 адрес во всеуслышание — ничего не стоит. Узнать исходный ключ по его хешу не предоставится возможным исходя из сложности алгоритма хеш-функции. А сама пара ключей будет использована лишь однажды — при передаче прав собственности. На этом жизнь пары ключей заканчивается.
PUB1 — публичный ключ
PRIV1 — секретный ключ
HASH1 или HASH(PUB1) — хеш-сумма публичного ключа (биткойн-адрес).
HASH2 или HASH(PUB2) — хеш публичного ключа следующего владельца.
Возьмем пример попроще. Пусть у нас есть владелец автомобиля, в чьем праве собственности никто не сомневается.
— Собственник на публичном собрании (ярмарке, телевизионном шоу) показывает всем хеш своего публичного ключа HASH(PUB1), заводской номер автомобиля, и все соглашаются с этим — никто не предъявляет претензий.
— До момента продажи оба ключа PUB1, PRIV1 продавца остаются в секрете. Известен только HASH(PUB1) и соответствующий ему заводской номер автомобиля.
— Как только собственник хочет продать автомобиль какому-либо покупателю — он пишет открытое письмо, в котором указывает заводской номер и хеш-сумму публичного ключа второго владельца HASH(PUB2). И конечно же подписывает письмо своим секретным ключом PRIV1, прилагая публичный ключ PUB1.
— После передачи собственности секретный ключ перестает быть актуальным — второго такого письма быть не может. Публичным ключом можно проверить само письмо, удостоверить второго собственника.
— О втором собственнике ничего неизвестно кроме HASH(PUB2), до тех пор пока он не передаст права третьему владельцу. И эта цепочка может быть бесконечной.
— Подписывая передачу прав с использованием ЭЦП, собственник не только удостоверяет себя, но и накладывает на себя обязательство передачи. Как говорится: «слово — не воробей, вылетит — не поймаешь».
— Благодаря HASH(PUB) получается двойная защита. Первая загадка — узнать публичный ключ по его хешу. Вторая загадка — подписаться чужим секретным ключом.
Если заменить автомобиль на 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 года) и т.д.
— Транзакции в блок укладываются в виде дерева хешей. Таким образом в дальнейшем можно будет выкидывать завершенные транзакции для экономии места на диске, не нарушая целостности блоков.
— Биткойн-адрес содержит в себе контрольную сумму. Поэтому в адресе нельзя ошибиться пропустив или заменив одну или несколько символов.
Latest news: 
Shop
Show Posts
