Хеш и алгоритмы хеширования — это ключевые понятия, с которыми знакомятся новички в сфере блокчейна и которые которые всегда идут об руку с безопасностью. Для поддержания децентрализованных сетей и консенсусных механизмов, среди которых Биткойн или Ethereum с тысячью узлов, соединённых с помощью p2p, необходимо «отсутствие доверия» и эффективная система подтверждения. Этим сетям нужны компактные способы шифрования информации, которые позволяли бы участникам проводить быструю и безопасную проверку.
Блок — одна из основных составляющих Биткойна и Ethereum. Блок содержит информацию о транзакциях, временных метках и прочие существенные метаданные. Огромную роль в обеспечении безопасности играет возможность сжимать большие объёмы информации о глобальном состоянии сети в короткие стандартные сообщения, которые при необходимости можно легко проверить. Эти сообщения и есть хеш.
Если изменить хотя бы один символ входящего значения, получится совершенно другой хеш!
Криптографические хеши используются везде, начиная с хранения паролей и заканчивая системами проверки. Их суть заключается в использовании детерминированного алгоритма, который берёт входные данные и создаёт строку с фиксированной длиной. Таким образом, одни и те же входные данные всегда будут преобразованы в одинаковые выходные данные.
Детерминизм важен не только для хешей, ведь даже если изменить один бит входных данных, получится совершенно другой хеш.
Проблема алгоритмов хеширования заключается в неизбежности коллизий. Так как длина строки такого хеша фиксированна, то могут существовать и другие входные данные, образующие тот же хеш. Коллизии — это плохо. Это значит, что злоумышленник может создавать коллизии по запросу, может передавать вредоносные файлы или данные с корректным хешем и выдавать эти данные за правильные. Хорошая функция хеширования должна максимально усложнять для злоумышленников процесс поиска путей создания входных данных с тем же значением хеша.
Процесс расчёта хеша не должен быть слишком эффективным, так как в этом случае злоумышленники легко могут вычислить коллизии. Алгоритмы хеширования должны быть устойчивыми к атакам нахождения прообраза. Необходимо максимально усложнять процесс расчёта шагов для нахождения исходного значения, из которого был создан хеш (например, прообраза).
Необходимо, чтобы способ вычисления x для s= hash(x) был практически невозможным.
Итак, «достойные» алгоритмы хеширования должны иметь три свойства:
- Если изменить один бит входящих данных, должен образоваться лавинный эффект и получиться совершенно другой хеш;
- Небольшая вероятность коллизий;
- Эффективность, которая не жертвует коллизионной устойчивостью.
Взлом хешей
Один из первых стандартов алгоритмов хеширования — хеш MD5. Этот алгоритм пользовался популярностью для проверки целостности файлов (контрольные суммы) и хранения хешированных паролей в базах данных веб-приложений. Его функционал достаточно прост — он выдаёт строку с фиксированной длиной в 128 бит для каждого входного значения и использует стандартные односторонние операции в нескольких циклах для вычисления детерминированного выходящего значения. Из-за короткой длины выходного значения и простоты операций хеш MD5 очень легко поддаётся взлому, в частности атаке «дней рождения».
Атака «дней рождения»
Существует известное утверждение о том, что если в комнате находятся 23 человека, то шанс того, что у двое из них родились в один день, равняется 50%. Если в комнате находятся 70 человек, то эта вероятность увеличивается до 99,9%. Это происходит согласно принципу Дирихле, который утверждает, что если поместить 100 голубей в 99 коробок, то в одной из коробок окажется два голубя. Ограничение фиксированной длины выходящего значения означает, что существует фиксированный уровень комбинаций для коллизий.
Тут слишком много голубей! По крайней мере в одной из коробок окажется два попугая.
Хеш MD5 настолько уязвим к коллизиям, что даже на простом процессоре Pentium с частотой 2,4 ГГц можно вычислить коллизии хеша всего за несколько секунд. Более того, широкое применение этого хеша на заре существования сети создало миллионы прообразов MD5, которые можно было найти с помощью обычного поиска Google по их хешу.
Разнообразие и эволюция алгоритмов хеширования
Начало: SHA1 и SHA2
АНБ (да-да, АНБ) уже в течение долгого времени является пионером по созданию стандартов алгоритмов хеширования. Именно АНБ предложило алгоритм Secure Hashing Algorithm или SHA1 с фиксированной длиной выходящего значения в 160 бит. К сожалению, SHA1 ненамного превосходил MD5 благодаря увеличению значения, количества односторонних операций и их сложности, но этот хеш не предлагал основательных улучшений защиты от более мощных машин, создающих разные векторы атаки.
Как же улучшить алгоритм хеширования?
SHA3
В 2006 году Национальный институт стандартов и технологий США (NIST — National Institute of Standards and Technology) объявил конкурс на создание альтернативы алгоритму SHA2, которая должна была фундаментально отличаться по своему дизайну и стать новым стандартом. Из схемы алгоритмов хеширования под названием KECCAK (произносится как «кечак») появился алгоритм SHA3.
Хотя SHA3 и имеет схожее с предыдущими алгоритмами название, он сильно отличается по своей внутренней структуре механизмом криптографической губки. Этот механизм осуществляет случайные перестановки для поглощения и создания данных, служа источником случайности для входящих данных, которые будут попадать в алгоритм хеширования в будущем.
Обработка входящих данных с помощью криптографической губки KECCAK256
SHA3 сохраняет изначальное состояние с большим количеством битов информации, чем в выходящем значении, и тем самым превосходит ограничения прежних алгоритмов. Этот алгоритм стал стандартом NIST в 2015 году.
Хеширование и доказательство выполненной работы
В рамках внедрения алгоритма хеширования в протокол блокчейна для алгоритма доказательства выполненной работы Bitcoin использовал SHA256, а появившийся позже Ethereum — модифицированную версию SHA3 (KECCAK256). При выборе хеш-функции для блокчейна с доказательством выполненной работы очень важна эффективность вычисления хеша.
SHA256 Биткойна может быть крайне эффективно вычислен с помощью специального аппаратного обеспечения — специализированных интегральных микросхем (ASIC — Application Specific Integrated Circuits). Об использовании ASIC в майнинговых пулах и о том, как они приводят к централизации вычисления, написано очень много. Доказательство выполненной работы провоцирует создание пулов из групп эффективных в вычислительном отношении машин, благодаря чему увеличивается так называемая «хеш-мощность» или количество хешей, которые может вычислять машина за определённый период времени.
[прим.ред.: Майнинг в пуле против соло-майнинга никак не увеличивает хэш-мощность участвующего. скорость нахождения хэшей при фиксированной хэш-мощности оборудования участника не меняется, если сравнивать с соло-майнингом. Однако, собранная от разных участников хэш-мощность всех участников пула, позволяет находить блоки чаще, чем у каждого из единичных участников пула. Соответственно, пул находит блоки чаще и выплачивает вознаграждение за блок всем участникам пула в единицу времени пропорционально хэш-мощности, участвующей в пуле — за вычетом комиссии пула. Например, участник с 1Ghash/s при майнинге Биткойна соло мог бы ожидать событие «нахождение блока» — и получение за него награды в размере 12,5 BTC — когда-нибудь в течение пяти лет (например!). Участие же в пуле той же мощностью 1Ghash/s (при условии не изменения сложности на интервале пяти лет!) позволяет тому же майнеру получать 12,5 BTC частями, равномерно в течение тех же пяти лет. Это решает проблему майнера с выплатами фиата в реале на поддержание фермы].
В Ethereum внедрён модифицированный алгоритм SHA3 — KECCAK256. Алгоритм доказательства выполненной работы Ethereum под названием Dagger-Hashimoto требовал от аппаратного обеспечения слишком много памяти для вычислений.
