Scrypt валюты: принцип работы алгоритма

В мае 2009-го года, когда алгоритм scrypt был опубликован, «эпидемию» появления криптовалют на нём сложно было предположить. Но уже к концу лета 2013 года несколько десятков криптосистем (половина из которых были форками Litecoin) заработали на scrypt, появляясь чуть ли ни каждую неделю. Не все scrypt-валюты дожили до наших дней, но к лету 2018 года по-прежнему остается актуален и сам Litecoin, и ряд других представителей семейства: Dogecoin, Syscoin, BitConnect, Bitmark, Novacoin, Fastcoin. Развернутый список криптовалют на алгоритме scrypt в несколько раз больше и представлен в статье в алфавитном порядке. Причём, формируя список, мы заодно попытались понять, как алгоритм приобрел такую популярность.

История появления и развития идеи хеш-функции

Авторство создания scrypt (чаще по-русски его называют «скрипт», хотя правильным вариантом считается «эс-крипт») принадлежит Колину Персивалю. Данная криптографическая хеш-функция (точнее – функция формирования секретного ключа из некоего массива данных) создавалась, помимо прочего, и как альтернатива хеш-функции SHA256, используемой в сети Bitcoin для доказательства выполнения работы (Proof-Of-Work, или PoW).

Сущность понятия «доказательства проделанной работы» была описана еще в 1993 году, в статье Moni Naor и Cynthia Dwork, где авторы сформулировали следующую идею: «Для подключения к общему ресурсу, пользователю необходимо вычислить функцию, которая одновременно была бы и достаточно сложной, и посильной».

Это условие можно описать примером деятельности из реального мира, когда ребёнку для получения бесплатного угощения нужно сначала навести порядок на рабочем столе и сложить игрушки. Но это условие несколько сложнее было реализовать в цифровом мире, поскольку действовало ещё одно: «Выполнение задания (то есть, вычисление функции) должно быть существенно сложнее, чем проверка полученного результата». Если бы сервер ресурса, например, просто предлагал бы пользователю перемножить два больших числа, а потом проверял бы результат, то время проверки было бы сопоставимо с временем самой работы, что не отвечало условиям задачи. Вычисление функции стали усложнять.

Очередным требованием к алгоритму стала необходимость не допустить распараллеливание функции. Важно было сделать так, чтобы время решения ряда задач было прямо пропорционально их количеству. В рамках приведенного выше примера это означало, что для получения двойного угощения ребёнку нужно было и на следующий день привести рабочий стол в порядок, поскольку «вчерашний порядок» уже не подходил. В цифровом мире примером такой функции стало вычисление корня квадратного уравнения по модулю простого числа Р.

В дальнейшем разработка темы PoW велась по нескольким направлениям:

• В проекте Hashcash задачей было хеширование одних и тех же данных с перебираемой частью, что в условиях стойкой необратимой hash-функции в оптимальном виде предполагало перебор данных.
• Второе направление развивалось в рамках идеи «memory-bound functions» – ограничения памяти. Предлагаемый алгоритм предполагал использование мегабайтов памяти в вычислениях, что считалось уже большим объёмом. Сложность при таком алгоритме представляла задержка во время обмена данных и/или объём доступной памяти. Scrypt как алгоритм представлял именно это направление.

Ещё до выхода Bitcoin в методе Хэла Финни уже предполагалось использование принципа RPoW, но там токены-доказательства рассматривались как самостоятельная ценность. В Bitcoin-сети механизм PoW рассматривался уже как средство достижения единого мнения по поводу того, какую версию блокчейна принимать как верную (достижения консенсуса). К теме проекта Hashcash автором Bitcoin был добавлен механизм изменяющейся сложности, а в качестве вычисляемой функции выбрана SHA-256. В результате очень быстро майнинг этой криптовалюты захватили владельцы GPU и ASIC-оборудования. Поэтому не удивительно, что уже в начале осени 2011 года появилась система Tenebrix – первая криптовалюта на алгоритме scrypt.

Принцип работы алгоритма и варианты реализации

Скрипт – это не совсем криптографическая функция. Это, скорее, KDF – функция формирования ключа. Задача KDF состоит в том, чтобы затруднить генерацию ключа (например, путем массового перебора паролей), но не настолько, чтобы его нельзя было использовать в прикладных задачах.

Во втором слое хэширования в схеме работы scrypt входной блок расширяется до массива, состоящего из N блоков (механизм последовательного применения псевдослучайной BlockMix-функции). Чем больше значение N, тем больший объем памяти нужен для работы алгоритма. Для Tenebrix параметры scrypt выбирались так, чтобы весь объем памяти умещался в 128Кб (это определялось объемом L2 кэша процессора). При таком раскладе в майнинг на scrypt снова включились CPU-майнеры, пока через несколько месяцев не вышел оптимизированный GPU-майнер, дающий десятикратное увеличение эффективности майнинга в тех условиях. Эффективность могла быть и другой, но в этот период на алгоритме скрипт начала активно запускаться одна валюта за другой, и вычислительные мощности «распылялись» между ними.

Однако ещё до того, как был анонсирован scrypt-ASIC, разработчики озаботились усовершенствованием алгоритма и, поработав с динамическим объёмом памяти, реализовали усовершенствования в двух вариантах:

• Scrypt-N. Среди трёх основных параметров алгоритма Скрипт (N=1024, r=1, p=1, где N увеличивает объем памяти, а r, кроме этого, ещё и добавляет число вызовов функции перемешивания) в реализации Scrypt-N периодически двукратно увеличивается число N, что требует и увеличения объема памяти.
• Scrypt-jane. В этом варианте число N тоже увеличивается, но происходит это по формуле, нелинейно определяемой текущим временем. Кроме того, добавляются ряд перемешивающих и хеш функций.

Майнинг на Скрипт

Mining на scrypt для каждого отдельного пользователя – то есть, процесс поиска хеша, подходящего для формирования нового блока, – зависит от отношения количества хешей за секунду, выдаваемых оборудованием пользователя, к общесетевому количеству вычисляемых хешей за секунду. За нахождение нового блока при добыче пользователь получает свою долю из добытых монет.

Алгоритм scrypt, по сути, использует SHA256 в качестве подпрограммы, в результате чего нужно и производить большое количество математических вычислений, и использовать быстрый доступ и большие объёмы памяти. Это определяет более высокую стоимость производства ASIC для scrypt, чем для SHA256. Однако в связи с тем, что современные GPU-устройства наделены большой памятью, некоторые пользователи всё ещё продолжают добывать монеты семейства scrypt на видеокартах, собирая их в майнинговые фермы и подключаясь к пулам.

Параметры алгоритма scrypt дают возможность участникам сети, не участвующим в майнинге, запускать клиент в режиме многозадачности, не затрагивая при этом производительность системы в целом.

Перечень криптовалют на Scrypt

Список криптовалют, работающих на scrypt, не может быть постоянно актуальным и исчерпывающим, поскольку регулярно запускаются новые криптосистемы, но ниже представлен максимально полный их перечень.

• 1Credit, 2GiveCoin, 42Coin, 66Coin.
• A: ArcticCoin, AIRcoin, AlexiumCoin, AlienCoin, AmericanCoin, Amygws, Anoncoin, AntimatterCoin, AphroditeCoin, AppCoin, AppleBytes, ARCHcoin, Argentum, Aricoin, AsiaCoin, Asiadigicoin, Astrocoin.
• B: Bata, Bitmark, BitConnec,t BelaCoin, BlackCoin, BatCoin, BBQCoin, BeaoCoin, BeatleCoin, BeaverCoin, BeeCoin, BeerCoin, BeliCoin, Bells, BillionCoin, Bitbar, BitcoinScrypt, Bitgem, BitStar, BlitzCoin, BONESCryptoCoin, Bottlecaps, BTCtalkcoin, BurbuCoin.
• C: CrevaCoin, Craftcoin, CageCoin, CanadaeCoin, Cannacoin, CarbonCoin, CashCoin, Casinocoin, Catcoin, CharityCoin, CHNCoin, Cinnamoncoin, CinniCoin, CleanWaterCoin, CloudCoin, ClubCoin, COIN, CoinmarketsCoin, Coino, CoinyeCoin, ColossusCoin, CommunityCoin, CorgiCoin, Cosmoscoin, Credit Credits, CRTcoin, CryptoBuck, CryptoBullion, CryptoEscudo, CryptographicAnomaly.
• D: DrCoin, DaMaCoin, DNotes, Dogecoin, Denarius, Diggits, DogecoinDark, DopeCoin, Doubloons, DuckDuckCoin.
• E: EarthCoin, EasyLCoin, eBoost, EBTcoin, ECCoin, EduCoin, Einsteinium, Ekrona, Electric, ElectronicGulden, Elephantcoin, Emerald, EmotiCoin, eToken, Eurokoin, Experiencecoin, Extremecoin, EZCoin.
• F: Fastcoin, Florin, FailCoin, FairCoin, FedoraCoin, FlappyCoin, Floripacoin, Fluttercoin, Forexcoin, FoxCoin, Franko, FriendshipCoin, FryCoin.
• G: Gaelcoin, Gambit, Gamecoins, Gamecredits, GermanyCoin, Ghostcoin, GlobalBoost, Globalcoin, GlobalCurrencyReserve, Goalcoin, Goldcoin, Goldcoin, Graincoin, Grandcoin, Greececoin, GrowthCoin, GrumpyCoin, Guldencoin, Guncoin.
• H: HellenicCoin, Heisenberg, HoboNickels, Hotcoin, HouseofCoins, Hypercoin.
• I: ImperialCoin, Infinitecoin, InformationCoin, InsanityCoin, Isracoin, Iticoin, IvugeoEvolutionCoin.
• J: Junkcoin.
• K: Kazcoin, KittehCoin, KlondikeCoin, Krugercoin.
• L: Litecoin, Leadcoin, Leafcoin, Lebowskis, LegendaryCoin, Leprocoin, Litebar, LitecoinDark, Lottocoin, Lovecoin, Luckycoin, LycanCoin.
• M: Myriad-scrypt, MagicInternetMoney, MagiCoin, MapleCoin, Marinecoin, Marscoin, MarteXcoin, Megacoin, MemeCoin, Mincoin, Mintcoin, Moneta, Mooncoin, Moviecoin, MtGoxCoin.
• N: Novacoin, Nanotoken, Neocoin, NeptuneCoin, Netcoin, Networkcoin, NeuCoin, NeutrinoCoin, Nibble NobleCoin, Noirbits, NyanCoin, Nybble.
• O: OctoCoin, OilCoin, OKCash, Omnicoin, OnlineGamingCoin, Operand, Orangecoin.
• P: Potcoin, P7Coin, PandaCoin, Pandacoin, PawnCoin, Payzor, Peacecoin, PenguinCoin, PeopleCoin, PesetaCoin, Philosopherstone, Phoenixcoin, piCoin, PLNcoin, PolishCoin, PowerCoin, ProCoin, ProsperCoin, Pxlcoin.
• Quatloo.
• R: Rabbitcoin, RainbowGoldCoin, RapidCoin, Razor, Redcoin, ReddCoin, RhinoCoin, RipoffCoin, RonPaulcoin, RootCoin, RoyalCoin, RubleBit, RubyCoin.
• S: Solarcoin, Sexcoin, Syscoin, SambaCoin, Sapphire, Saturn2coin, SaturnCoin, Scorecoin, SembroToken, ServX, ShadeCoin, ShadowCash, ShibeCoin, SocialCoin, SocialxBot, SongCoin, Sovereigncoin, SpartanCoin, Spec, Spots, Stablecoin, SunCoin, Surge, Swiscoin, SynCoin.
• T: TacoCoin, Tagcoin, TeslaCoin, TheCypherfunks, Tickets, TittieCoin, TopCoin, Trollcoin2.
• U: UniteCoin, UnitedScryptCoin, USDeCoin.
• V: Voxels, VeriCoin, ViaCoin, ValueCoin, VegasCoin, VirtaCoin, VpnCoin.
• W: WhiteCoin, WildBeastBitcoin. Worldcoin.
• X: XenCoin, XiaoMiCoin, Xivra, XXLcoin, YACCoin.
• Y: YellowCoin, YinYangCoin, YoshiCoin.
• Z: Zedcoin, Zeitcoin, ZombieCoin.

Если добавить к этому криптосистемы, построенные на вариантах алгоритма Scrypt-N и Scrypt-jane, то список еще расшириться. Представителями Scrypt-N являются TenfiveCoin, SpeedCoin, SpainCoin, rotoCoin, Panda. На Scrypt-jane работают ZcCoin, Yacoin, Velocitycoin, ThorCoin и другие криптосети.

Автор статьи: Κирилл Τретьяков