Криптовалюты: обзор алгоритмов
24.
September.
2017
На сегодняшний день существует более 1000 криптовалют, работающих на различных алгоритмах.Сейчас мы рассмотрим самые распространенные алгоритмы.
1. SHA256 - алгоритм Bitcoin
SHA-2 (англ. Secure Hash Algorithm Version 2 — безопасный алгоритм хеширования, версия 2) — семейство криптографических алгоритмов — однонаправленных хеш-функций, включающее в себя алгоритмы SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224.
Хеш-функции предназначены для создания «отпечатков» или «дайджестов» для сообщений произвольной длины. Применяются в различных приложениях или компонентах, связанных с защитой информации.
Хеш-функции семейства SHA-2 построены на основе структуры Меркла — Дамгарда.
Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64 или 80 итерациями (раундами). На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Тем не менее, инициализация внутреннего состояния производится результатом обработки предыдущего блока. Поэтому независимо обрабатывать блоки и складывать результаты нельзя.
2. Scrypt - алгоритм Litecoin
scrypt (читается эс-крипт) — адаптивная криптографическая функция формирования ключа на основе пароля, созданная офицером безопасности FreeBSD Колином Персивалем для системы хранения резервных копий Tarsnap. Функция создана таким образом, чтобы усложнить атаку перебором при помощи ПЛИС. Для её вычисления требуется значительный объём памяти со случайным доступом. 17 сентября 2012 года алгоритм scrypt был опубликован IETF в виде Internet Draft, планируется его внесение в RFC. Используется, например, в качестве доказательства выполненной работы в криптовалюте Litecoin.
Основанные на пароле функции формирования ключа (password-based key derivation function, PBKDF) обычно разрабатываются таким образом, чтобы требовать относительно большого времени вычисления (по порядку величины — сотни миллисекунд). При использовании легальным пользователем требуется вычислить подобную функцию один раз (например при аутентификации) и такое время допустимо. Но при проведении атаки полного перебора атакующему требуется произвести миллиарды вычислений функции и её вычислительная сложность делает атаку более медленной и дорогой.
Однако ранние функции PBKDF (например PBKDF2, разработанная RSA Laboratories) вычисляются сравнительно быстро, и их перебор может быть эффективно реализован на специализированном оборудовании (FPGA или ASIC). Такая реализация позволяет запускать масштабные параллельные атаки перебора грубой силы, например, с использованием сотен экземпляров функции в каждой микросхеме FPGA.
3. Ethash - алгоритм Ethereum
Ethash (модифицированная версия Dagger-Hashimoto) - предполагает поиск такого nonce-входа в алгоритм, чтобы результат был ниже некоего предела, в зависимости от трудности. При использовании PoW-алгоритма нет лучшего способа поиска нонса, чем перечисление возможностей, тогда как подтверждение решения является простым и дешевым. Если результаты имеют равномерное распределение, тогда мы можем гарантировать, что в среднем время, необходимое для нахождения нонса, зависит от порога трудности, что позволяет контролировать время нахождения нового блока простым манипулированием трудностью.
Трудность динамически подстраивается таким образом, что в среднем один блок производится целой сетью каждые 12 секунд. Синхронизация системного состояния прерывается этим сердцебиением, гарантирующим невозможность параллельных процессов (позволяющих двойные затраты) или переписывания истории до тех пор, пока в атаке на систему не участвуют свыше половины майнинговых мощностей сети (так называемая атака 51%).
Любой узел сети может быть майнером, и ожидаемый доход от майнинга прямо пропорционален (относительной) мощности майнинга или хэшрейту, то есть числу нонсов в секунду, поделённому на общий хэшрейт сети.
Ethash PoW занимает фиксированное количество памяти, что делает его устойчивым к ASIC. Это значит, что для вычисления PoW требуется выбрать подмножества из фиксированных ресурсов в зависимости от нонса и заголовка блока. Этот ресурс (данные объёмом несколько гигабайт) называется DAG. DAG состоит из 30000 абсолютно разных блоков (100-часовой интервал называется epoch (эпоха)) и генерируется быстро. Если DAG зависит только от высоты блока, его можно сгенерировать заранее, в противном случае клиент должен ждать окончания процесса, чтобы произвести блок.
4. Eqhash - алгоритм Zcash
Equihash это алгоритм доказательства работы, разработанный Александром Бирюковым и Дмитрием Ховратовичем. Он базируется на информатике и криптографической концепции, которая носит название Обобщенная проблема дня рождения.
У Equihash есть очень эффективная проверка. Это может быть полезно в будущем при создании легких клиентов для мобильных устройств, или для имплементации клиента Zcash в Эфириум (наподобие BTC Relay, но для Zcash).
Equihash является чувствительным к количеству оперативной памяти алгоритмом доказательства работы, и это значит, что производительность майнинга во многом определяется тем, сколько у вас памяти RAM. Мы думаем, что маловероятно для кого-либо создать специализированные аппаратные средства (ASIC) для майнинга в обозримом будущем.
Мы также думаем, маловероятно, что любая существенная оптимизация Equihash даст преимущество майнерам, которые знают о такой оптимизации. Это связано с тем, что Обобщённая проблема дня рождения давно исследуется учёными и криптографами, и Equihash близок к Обобщённой проблеме дня рождения. Следовательно: похоже, что успешная оптимизация Equihash также станет оптимизацией Обобщённой проблемы дня рождения.
Тем не менее, мы не можем знать наверняка, что Equihash защищён от этих проблем, и мы можем изменить алгоритм доказательства работы снова, если найдём недостатки в Equihash или обнаружится другой алгоритм доказательства работы, который предложит более высокий уровень гарантий.
5. X11 - алгоритм Dash
X11 — алгоритм хэширования, который был впервые использован в валюте Darkcoin.
Данный алгоритм использует одиннадцать раундов хэширования одиннадцатью различными хэш-функциями (blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo), что делает его одним из самых надежных в современном мире криптовалют.
X11 позволяет решать ряд задач, с которыми не справляются SHA256 и scrypt. Специалисты не исключают возможности взлома SHA256, что поставит под угрозу всю сеть биткоина. Для «прорыва» X11 нужно найти уязвимость во всех одиннадцати хэшах, что намного сложнее. Даже если один из хэшей не оправдает себя, то это будет сигналом для разработчиков, которые смогут проанализировать проблему и заменить проблемный хэш.
Разработчики алгоритма утверждают, что хотя биткоин и лайткоин являются лидерами рынка, инвесторы смотрят с опаской на них. Лидирующим криптовалютам так и не удалось убедить инвесторов в отсутствии угрозы взлома, которая может повлечь уничтожение системы и обесценивание валют.
Цепочный алгоритм хэширования в разы надежнее по сравнению с однохэшевыми алгоритмами. Evan Duffield — разработчик Darkcoin’а и X11 — считает, что усиленная защита может привлечь тех самых инвесторов, которые боялись вкладывать деньги в биткоин или лайткоин.