Представляю вашему вниманию перевод статьи «Доказательство работы в криптовалютах: краткая история.
Часть 1" Рэй Паттерсон с сайта Байтекоин.
орг .
До начала времени
Понятие Proof-of-work — «доказательство (проделанной) работы» — впервые появилось в работе «Ценообразование посредством обработки или борьбы с нежелательной почтой» за 16 до Рождества Биткойна в 1993 году.И хотя такого термина в этой статье пока не существует (он появится через 6 лет), мы будем называть его именно так (сокращенно PoW).
Какую идею предложили в своей работе Синтия Дворк и Мони Наор? «Чтобы получить доступ к общему ресурсу, пользователь должен вычислить некоторую функцию: довольно сложную, но осуществимую; таким образом вы сможете защитить ресурс от злоупотреблений" Если провести аналогию, Рыбнадзор обязывает Джереми Уэйд немного поработайте, чтобы получить доступ к местному пруду – например, посадите несколько деревьев и пришлите фотографии саженцев.
При этом Джереми должен суметь справиться с ней в разумные сроки: до того, как вся рыба будет отравлена веществами, выброшенными в окружающую среду.
Но, с другой стороны, работа не должна быть элементарной, иначе толпы рыбаков быстро опустошат весь пруд. В цифровом мире придумать пример такой работы на самом деле не так уж и тривиально.
Сервер может, например, попросить пользователя перемножить два случайных длинных числа, а затем проверить результат. Проблема очевидна: проверка происходит ненамного быстрее самой работы, т. е.
сервер просто не справляется с большим потоком клиентов.
Следующая попытка: сервер находит два длинных простых числа, умножает их и сообщает результат пользователю.
Последний должен выполнить факторизацию, это сложнее.
Здесь есть нюансы, но в целом схема стала лучше: соотношение «время работы/время проверки» выросло в разы.
Это основное требование, сформулированное в статье: «Вычисление функции на заданных входных данных должно быть намного сложнее, чем проверка результата».
Кроме того, требовалось, чтобы функция не амортизировалась (читай: не распараллеливалась), т.е.
чтобы время решения нескольких задач было пропорционально их количеству (Если Джереми хочет получить двойную квоту на ловлю рыбы, то ему нужно работать в два раза дольше: вчерашние или чужие фото не подойдут).
В качестве примера таких функций было предложено (среди прочих) вычислить квадратный корень по модулю простого числа P: здесь у нас есть log(P) умножений на решение и только одно умножение для проверки).
Входное значение может быть предоставлено либо сервером (сгенерировать x, вывести x^2), либо выбрано автономно: выберите x, найдите sqrt(hash(x)).
В последнем случае необходим небольшой файл: не каждый элемент в Z_p является квадратом.
Но это мелочи.
В последующие годы появились и другие работы с ключевыми словами «доказательство работы».
Среди них следует отметить два: Проект Hashcash, Адам Бэк , посвященный той же защите от спама.
Задача была сформулирована следующим образом: «Найти такое значение x, чтобы хеш SHA(x) содержал N ведущих нулевых битов».
То есть по сути работа сводилась к хешированию одних и тех же данных (буквы) с перебираемой частью.
Поскольку используется сильная, необратимая хэш-функция, нет ничего лучше грубой силы; а средний объём работы зависит от N экспоненциально.
Очень простая схема, правда? «Умеренно сложные функции, ограниченные памятью» .
Ключевое слово здесь — привязанность к памяти.
К началу 2000-х годов стало заметно, что разница между младшими и высокопроизводительными процессорами слишком велика, чтобы PoW-задачи могли красить всех под одну кисть.
Предложенный в статье алгоритм первым использовал в расчетах сравнительно большие (мегабайтные) объемы памяти.
Узким местом в таких схемах была не скорость процессора, а задержка обмена данными с оперативной памятью или сам объем требуемой памяти, который в компьютерах варьировался в более узких пределах.
Одним из таких алгоритмов был сценарий , Но об этом позже.
Одноклеточный
Было бы неправильно сказать, что Сатоши был первым, кто придумал использовать PoW для электронных денег.Идея под названием «многоразовое доказательство работы» циркулировал в криптоанархистских кругах (и даже был частично реализован), но популярности в исходном виде не обрел.
Концепция RPoW от Хала Финни предполагал, что «токены доказательства» сами по себе будут представлять собой независимую ценность (монеты), тогда как в Биткойне механизм PoW использовался как средство достижения распределенного консенсуса (общего мнения о том, какая версия блокчейна считается правильной).
И это была ключевая идея взлетевшего Биткойна.
В качестве схемы доказательства работы была выбрана идея Hashcash, а вычисляемой функцией была SHA-256 — самая популярная на тот момент хеш-функция (2008 г.
).
Скорее всего, решающими факторами оказались простота Hashcash и «стандартность» SHA-256. Сатоши добавил в Hashcash механизм переменной сложности (уменьшение и увеличение N — необходимого количества нулей — в зависимости от суммарной мощности участников) и этим, казалось бы, обеспечил всем безоблачное децентрализованное будущее.
Но потом произошло то, что произошло: GPU, FPGA, ASIC и даже централизованный облачный майнинг.
Вы можете найти подробную историю (в трех томах) развития майнинга Биткойн.
Здесь .
Единого мнения о том, «предвидел» ли Сатоши все это безобразие или нет, нет, но факт таков: уже в сентябре 2011 года появилась первая криптовалюта с принципиально иной функцией PoW: Tenebrix использовал скрипт вместо SHA-256. .
Мутация
Так почему же вместо таких полезных и важных изменений в коде Биткойна, как общее количество монет, начали менять важнейший элемент — алгоритм консенсуса? Причина очевидна: в 2011 году уже полным ходом шли GPU-фермы, собирались предзаказы на FPGA и потенциально маячили ASIC — т.е.вклад рядового пользователя CPU был практически нулевым.
Но в чем причина? Конечно, все можно объяснить обычными негодование или желание «заработать»: до Тенебрикса уже были форки, премайны и памп-н-дампы.
Но доводы сторонников функции «ASIC-устойчивости» вполне обоснованы: Популяризация.
Поскольку каждый компьютер (теоретически) производит примерно одинаковый хэшрейт, в майнинге будет участвовать больше людей, пусть даже и в фоновом режиме.
Сотни миллионов офисных машин, слегка нагружая свой процессор, будут способствовать защите сети и получать за это монеты, которые затем пойдут в обращение.
Децентрализация.
Тут даже два аспекта: во-первых, производители железа.
Большинство ASIC производятся на нескольких заводах в Китае, и лишь немногие из них обладают компетенцией в производстве.
Другое дело — ПК общего назначения.
Во-вторых, географическое положение горняков.
Если не брать в расчет пулы, то универсальный CPU-Friendly алгоритм имеет большую ареал распространения: запустить майнер может позволить себе каждый.
Стоимость атаки составляет 51%.
Конечно, всегда можно спроектировать специальное устройство, решающее определенную задачу более эффективно (по времени или энергопотреблению), чем обычный ПК.
Другой вопрос: сколько будет стоить НИОКР такого устройства, какой масштаб производства должен быть, чтобы весь проект был экономически выгоден и т.д.? Есть мнение, что в любом случае это будет дороже, чем в нынешних реалиях Биткойн.
(Здесь имеется в виду не абсолютная оценка стоимости атаки: а относительная, грубо говоря, к уровню зрелости всей сети.
Так, скажем, сеть даже с самым супер-крутым ASIC-устойчивым алгоритмом может быть атаковать дешево, если на нем сейчас майнит всего два десятка машин ) Конечно, по каждому пункту всегда можно возразить, но я просто хочу показать, что при выборе PoW-функции имеет смысл задуматься о ее «ASIC-безопасности».
На самом деле, этот аспект был неявно упомянут в самой первой статье! Именно незатухающий характер функции можно с натяжкой считать безопасностью ASIC. Теперь немного технических подробностей о том, как работает алгоритм scrypt, который лег в основу Tenebrix, а позже и Litecoin (который, как вы знаете, стал второй по популярности криптовалютой).
Строго говоря, scrypt — это не криптографическая хеш-функция, а функция деривации ключей (KDF).
Такие алгоритмы используются именно там, где вы могли подумать: для получения секретного ключа из некоторых данных (парольной фразы, случайных битов и т. д.).
Примеры включают PBKDF2 и bcrypt. Основная цель KDF — затруднить генерацию окончательного ключа: не настолько, чтобы его можно было использовать в прикладных задачах, но настолько, чтобы предотвратить случаи злонамеренного использования (например, массовый перебор паролей).
Формулировка что-то очень напоминает, не правда ли? Неудивительно, что они встретились – как Зита и Гита – PoW и KDF. Как работает скрипт Первый слой: Входные данные передаются через PBKDF2.
Разделен на p блоков, каждый из которых обрабатывается функцией SMix.
Результат снова склеивается и пропускается через PBKDF2.
Обратите внимание, что здесь каждый из p блоков может обрабатываться отдельно.
Те.
scrypt теоретически допускает распараллеливание (но по умолчанию p=1) Второй слой: Входной блок расширяется до массива из N блоков путем последовательного применения псевдослучайной функции BlockMix. Блок X, полученный из последнего элемента, интерпретируется как целое число j, а элемент Vj считывается из массива X = BlockMix(X xили Vj) Шаги 2-3 повторяются N раз.
Результатом является текущее значение блока X.
Именно здесь происходит самое интересное.
Чем большее значение N мы выбираем, тем больше памяти требует алгоритм.
И хотя на каждом шаге 2-3 нам нужен только один элемент из всего массива, мы не можем освободить память до шага 5: ведь этот элемент выбирается псевдослучайно, в зависимости от последнего результата! Таким образом, если сама функция BlockMix (см.
ниже) выполняется быстро, узким местом становится задержка.
Третий слой.
Вход разделен на 2r блока
Каждый блок связывается с предыдущим и хешируется функцией H.
Результат дан в переставленном порядке
Функция H — Salsa20/8. Да, это не хэш-функция, а поточный шифр.
Но для целей скрипта устойчивость к коллизиям не требуется, а нужны только быстрые и псевдослучайные результаты, поэтому Salsa хорошо подошла.
По умолчанию scrypt предлагает r=8, но в криптовалюте выбрали r=1 (скорее всего для скорости).
О последствиях напишем позже.
Подробности относительно выбора тех или иных параметров в алгоритме можно найти здесь .
Параметры скрипта для Tenebrix были выбраны так, чтобы общий объем требуемой памяти укладывался в 128 КБ: это может уместиться в кэше L2 процессора.
А по умолчанию использовалось 16 Мб! Эксперимент оказался более чем удачным: в игру быстро включились процессорные майнеры, забытые на обочине прогресса.
Подавляющее большинство новых форков уже ответвились от Litecoin, унаследовав scrypt вместо SHA256. Как ни странно, пользователей не смутил тот факт, что параметры 128 КБ оказались для видеокарт довольно жесткими.
Оптимизированный майнер на GPU появился через несколько месяцев и дал в среднем десятикратный прирост эффективности.
«Но не в 100 раз, как в Биткойне!» — сказали они, — «Но не 1000 раз!» Увеличение соотношения мощностей GPU/CPU (вытесненное из Биткойна новыми ASIC) было не таким резким, вероятно, потому, что оно было компенсировано бумами форков: новая криптовалюта scrypt появлялась почти раз в неделю, поглощая новую мощность.
И все же понимание того, что scrypt далек от идеальной PoW-функции, появилось еще раньше, чем анонс scrypt-ASIC. Головокружение от успеха прошло, культ Сатоши немного поутих, а идеи новых кандидатов в PoW стали появляться словно после дождя.
Читайте в следующем выпуске :
«Скрещивай и умножай: алгоритмы X11 и Ко!» «Атавизмы против рудиментов: SHA3 или scrypt-janeЭ» «Парадоксы истории: парадокс импульса и дня рождения» «Где вершина эволюции: в теоретической информатике или в практической? CuckooCycle и CryptoNight» Теги: #криптография #биткойн #криптовалюты #история #история #криптография #криптовалюта #биткойн #перевод #криптография-
Попай И Био-Рам
19 Oct, 24 -
Монтирование Тома На Основе Lvm (Lvm-In-Lvm)
19 Oct, 24 -
Необычное Использование Генератора Отчетов
19 Oct, 24 -
Заработные Платы Разработчиков В Армении
19 Oct, 24
