[Перевод] 10.3 секунды на хеш: майнинг на бортовом управляющем компьютере КА Аполлон
Нам удалось восстановить Бортовой управляющий компьютер КА Аполлон. И теперь, когда у нас на руках имеется единственный в мире работающий экземпляр, мне пришла в голову идея написать для него код. Хотя мысль о добыче биткоинов с помощью компьютера из далеких 60-х казалась бессмысленной, попытаться все же стоило. Реализация Алгоритма шифрования Биткоина на ассемблерном коде с помощью 15-битного компьютера далась тяжело, но мне таки удалось заставить его работать. К сожалению, компьютер оказался настолько медленным, что на формирование блока биткоина ушла бы вечность.
Бортовой управляющий компьютер КА Аполлон / Apollo (AGC) был разработан в 1960-х годах, проводил вычисления и контролировал движение, навигацию, управлял командным и лунным модулями во время полетов по программе Аполлон. В эпоху, когда габариты ЭВМ могли варьироваться от размера холодильника и до размера комнаты, Apollo Guidance был достаточно мал для полетов в космос. Этот исторический компьютер был одним из первых, где использовались интегральные схемы. Весила такая машина почти 32 кг.
Бортовой управляющий компьютер КА Аполлон сыграл весомую роль в вопросе становления разработки программного обеспечения, под руководством Маргарет Гамильтон.
Маргарет Гамильтон возглавляла отдел разработки программного обеспечения (ПО) лаборатории измерительных систем Массачусетского технологического института (MIT). Отдел разрабатывал бортовое программное обеспечение для космической программы НАСА «Аполлон»
.
Apollo (AGC) был оснащен операционной системой реального времени с кооперативной многозадачностью, несколько приоритетных задач могли выполняться одновременно, была функция обнаружения и устранения неисправностей. Большая часть ПО была на ассемблере, для AGC был разработан интерпретатор, который позволял запускать 5–7 виртуальных машин одновременно в два килобайта памяти.
Как работает майнинг биткоинов
Совсем не новость: будучи ведущей цифровой валютой, Биткоин находится в эпицентре внимания последние несколько лет. Система Биткоин может рассматриваться как бухгалтерская книга, в которой ведется, кому какие биткоины принадлежат, это позволяет трансферить их от одного пользователя другому. Революционная особенность Биткоина — полная децентрализация, нет центрального администратора или какого-либо его аналога. Вместо этого записи распространяются на тысячи машин в Интернете, и система работает без посторонней помощи.
Это своего рода журнал, в котором фиксируются все транзакции без возможности изменения каких-либо данных, а лишь их дополнение. Своего рода копия такого журнала находится на системах всех участников этой сети и все транзакции и информация относительно обращения и накопления средств тоже находится на всех этих журналах.
Чтобы убедиться, что все согласны с тем, какие транзакции действительны, Биткоин использует процесс называемый майнингом, — примерно каждые 10 минут добывается блок ожидающих транзакций, это делает этот блок «официальным». Система Биткоин спроектирована таким образом, что для майнинга блока требуется огромное количество вычислительных мощностей, и это исключает «захват власти» одним майнером. Майнеры (добытчики биткоинов) конкурируют друг с другом, генерируя триллионы триллионов случайных «хешей», пока кому-то не посчастливится найти начинающийся на 18 нулей. Этот хеш образует успешно сгенерированный блок, после все переходят к добыче следующего блока. Идея: случайное получение 18 нулей подряд крайне маловероятно, поэтому требуется огромное количество попыток, прежде чем кому-то это удастся. Что ж, это схоже с лотереей, где майнеры продолжают пытаться, пока кто-то не «выиграет», поиск хеш-кода сравним с поиском определенной песчинки во всем песке на Земле.
Каждый раз, после добычи блока, создаются новые Биткоины; в настоящее время успешный майнер может получить 12,5 новых Биткоинов (стоимостью $140 000), а также комиссионные за транзакции. Сама мысль о возможности заполучать $140 000 каждые 10 минут побуждает майнеров строить центры обработки данных, заполненные специализированным оборудованием, используя огромное количество электроэнергии.
Диаграмма выше показывает, что на самом деле входит в добываемый блок. Желтая часть — это заголовок блока (который хешируется), за ним следуют транзакции, которые входят в блок. Каждый блок содержит хеш предыдущего блока, в результате чего все блоки соединяются вместе, образуя цепочку блоков. Справа видно, что хеш успешен, так как начинается с большого количества нулей.
Подводя итог процесса майнинга: вы собираете новые биткоин-транзакции и создаете заголовок, как показано на диаграмме выше. Вы генерируете криптографический хеш блока. Если по какой-то невероятной случайности результат начинается с 18 нулей, вы отправляете блок в сеть Биткоин и «выигрываете» $140 000 в биткоинах. В противном случае вы слегка изменяете заголовок и повторяете попытку. Если же кому-то еще удается добыть блок, вы начинаете все сначала с нового блока и новых транзакций.
Алгоритм хеширования SHA-256, используемый биткоинами
Откуда появились эти хеши? Процесс майнинга Биткоинов основан на криптографии с «хеш-функцией», которая преобразует блок данных в практически случайное хеш-значение. Алгоритм хеширования разработан так, чтобы его можно было легко реализовать, но при этом он криптографически надежен: не существует известного способа быстро найти успешный хеш, кроме как перепробовать миллионы хешей с помощью «грубой силы». В частности, Биткоин использует стандартную криптографическую хеш-функцию под названием SHA-256. Этот алгоритм прост, но с его помощью можно зашифровать данные совершенно непредсказуемо.
SHA-256 представляет собой однонаправленную функцию для создания цифровых отпечатков фиксированной длины (256 бит, 32 байт) из входных данных размером до 2,31 эксабайт (2⁶⁴ бит) и является частным случаем алгоритма из семейства криптографических алгоритмов SHA-2
Алгоритм SHA-256 описан примерно на странице псевдокода
Хеш-функции семейства SHA-2 построены на основе структуры Меркла — Дамгарда. Исходное сообщение после дополнения разбивается на блоки, каждый блок — на 16 слов. Алгоритм пропускает каждый блок сообщения через цикл с 64 итерациями. На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова. Результаты обработки каждого блока складываются, сумма является значением хеш-функции. Так как инициализация внутреннего состояния производится результатом обработки предыдущего блока, то нет возможности обрабатывать блоки параллельно.
Шаг кодирования информации, называемый еще «раундом», повторяется 64 раза. На приведенной выше диаграмме показан один раунд, который принимает восемь 4-байтовых хеш-значений, от A до H, выполняет несколько операций и генерирует новые значения для A-H. Как видно из диаграммы, только A и E изменяются за раунд, в то время как другие просто сдвигаются. Тем не менее, после 64 раундов входные данные полностью скремблированы, что и приводит к непредсказуемому выводу хеша.
Операции в SHA-256 являются простыми битовыми операциями. Красные поля выше обозначают 32-битное сложение, генерирующие новые значения для A и E. Блок Ch «избирательный» выбирает биты из F или G, основываясь на значении входа E. «Суммарные» блоки Σ вращают и суммируют биты. Блок Ма «Большинство» оценивает биты в каждой позиции A, B и C и выбирает, какое значение будет в большинстве. Значения Kt является константой. Входные данные поступают в алгоритм через значение Wt. Эти операции можно легко реализовать на компьютере с использованием простых арифметических и логических операций.
Процессор управляющего компьютера КА Аполлон
У Apollo (AGC) не было микропроцессора, поскольку он был построен за долго до разработки микропроцессоров как таковых. Вместо этого процессор состоял примерно из 5600 NOR вентилей.
Эти вентили соединялись между собою для создания схем таких как триггеры, регистры, двоичные сумматоры, логика управления и так далее. AGC — один из первых компьютеров, в котором использовались интегральные схемы; каждая интегральная схема содержала два вентиля NOR. В компьютере было 24 логических модуля, похожих на приведенный ниже. Каждый логический модуль имел 120 интегральных схем (240 вентилей NOR). Например, регистры и ALU были реализованы с четырьмя модулями, каждый из которых реализовывал 4 бита процессора.
Архитектура компьютера была необычной по современным меркам: в ней использовалось 15-битное слово наряду с четностью (в то время компьютеры часто имели размер слова, который соответствовал приложению, и не обязательно 2). У AGC было всего 2K слов в RAM, 36K слов в ROM. Постоянное запоминающее устройство (ПЗУ) было с линейной выборкой многократно прошитых сердечников, «вязаная» память. Управляющий компьютер Apollo работал медленно даже по стандартам 1960-х годов; он мог выполнять около 40000 операций в секунду. Основным преимуществом AGC был I/O: он имел сотни соединений ввода / вывода и мог обеспечить контроль космического корабля в реальном времени.
Реализация SHA-256 на навигационном компьютере Apollo
Моя реализация алгоритма хеширования SHA-256 очень близко следует псевдокоду. Однако я столкнулся с некоторыми трудностями, поскольку в наборе команд AGC отсутствуют многие функции современных компьютеров. Например, AGC (как и многие компьютеры 1960-х годов) не имели стека, поэтому приходилось отслеживать адрес возврата для каждого вызова подпрограммы.
Другая сложность заключалась в том, что алгоритм SHA-256 использует 32-битные беззнаковые числа, в то время как AGC использовал 15-битные знаковые числа, давно устаревшие единицы, поэтому даже операция сложения требовала сложного кода. Чтобы вписать 32-битное число в AGC, я разбил каждое слово на один 4-битный и два 14-битных фрагментов. (Я использовал 14-битные фрагменты, а не 15-битные, потому что мне нужно было использовать беззнаковую арифметику).
Следующей проблемой оказалась память AGC, вернее ее размер. В управляющем компьютере, как и большинстве компьютеров 1960-х годов, использовалась память на магнитных сердечниках, каждый бит сохранялся в крошечном намагниченном ферритовом кольце. Так как память ядра была довольно громоздкой, у AGC было приблизительно 4 Кбайта оперативной памяти. Схема адресации AGC еще больше усложнила задачу, поскольку получить доступ можно было только к 256 словам, если не использовать неудобный механизм коммутации блоков памяти. Проблема заключалась в том, что алгоритм SHA-256 использовал восемь (32-битных) хеш-значений, 64-словную таблицу подтверждений и 8 слов промежуточных значений. Только эти три массива использовали 240 слов AGC, оставляя около 16 слов для всего остального (временные значения, адрес возврата из программы, счетчики циклов, указатели и т. д.) Мне удалось свести все в один блок памяти, повторно используя эти 16 слов для различных целей, но я потратил много времени на отладку проблемы, в то время когда переменная занимала место, которое все еще использовалось.
Большинство современных компьютеров имеет специальные команды shift/rotate, чтобы оперировать словами, но в AGC вместо этого использовались три специальных регистра.
Алгоритм SHA-256 использует много 32-битных сдвигов и поворотов, которые мне пришлось преобразовать в циклы с использованием 15-битного циклический регистр. Хоть операция сдвига, такая как x >> 10, тривиальна, мне потребовалось реализовать целую подпрограмму, чтобы провернуть это на КА Аполлон.
Чтобы сохранить набор инструкций и небольшой размер кода, для AGC существовало несколько инструкций с неожиданными «побочными эффектами». Например, инструкция TS (передача в запоминающее устройство) записывала значение в память, что на первый взгляд являлось·бесхитростным процессом. Но если предыдущее дополнение имело переполнение (то есть перенос), TS пропускала следующую инструкцию и заряжала накапливающий регистр на +1 или -1. Другими словами, простая запись значения в память могла привести к скачку потока управления и изменению регистра. Это позволяло обрабатывать переносы для арифметических операции с многократно увеличенной точностью, большинство компьютеров просто реализуют это при помощи инструкции «Добавить с переносом».
Запуск программы
На видео ниже — моя биткоин-программа, работающая на настоящем бортовом управляющем компьютере КА Apollo, результаты выводятся на наш DSKY (сокращение от Display / Keyboard — дисплей / клавиатура). У DSKY была простая цифровая клавиатура с кнопками, достаточно большими, чтобы космонавты могли нажимать их, будучи в перчатках. Компьютер выводил результаты в цифрах; астронавты должны были знать в каких единицах выходные данные: в футах, секундах, градусах и т.д. Мы использовали копию DSKY, созданную Карлом, поскольку никто не позволил бы нам работать на настоящей DSKY.
Компьютер Apollo имел очень простой пользовательский интерфейс. Астронавт выбирал действие, нажав клавишу «Verb» (Глагол), вводил номер глагола и нажимал «Enter». Потом выбирал заданное значение, введя «Noun» (Существительное). (У астронавтов имелась справочная карточка со списком всех глаголов и существительных). Я добавил майнинг Биткоинов как Глагол 65 в программе под названием Borealis; Вы можете видеть, как Майк вводит Глагол 65 в начале видео.
На создание одного хеша SHA-256 у компьютера Apollo ушло 5,15 секунды. Поскольку Биткойн использует двойной хеш, скорость хеширования составляет 10,3 секунды. В настоящее время сеть Биткоин выполняет около 65 EH / с (65 квинтиллионных хешей в секунду). Бортовому управляющему компьютеру, чтобы добыть блок потребуется 4×10^23 секунд. А это по времени в миллион раз превосходит возраст Вселенной (4.3×10^17).
Учитывая астрономическую сложность процесса майнинга, вы можете задаться вопросом, как я успешно добыл блок. Все просто — для этой демонстрации я использовал в качестве входных данных блок, который был успешно добыт в прошлом, в частности, блок #286819. Таким образом, алгоритм работал быстро, но так как это был старый блок, денег я на этом не заработал.
Чтобы оценить производительность майнинга компьютера Apollo, сравним его с производительностью компактных USB-майнеров. На одном таком устройстве выполняется 130 миллиардов хешей в секунду, а его стоимость составляет менее 70 долларов. Это не сравнимо с $150 000 за управляющий компьютер Apollo. В свое время Apollo был чрезвычайно компактной системой с низким энергопотреблением, потреблявшей 55 Вт. USB-майнер, тем не менее, потребляет 12 Вт и легко вмещается в руке. Огромная разница в производительности связана с экспоненциальным ростом быстродействия вычислительной машины, описанного в законе Мура, а заодно и с преимуществом нынешнего пользовательского оборудования для майнинга биткоинов.
Программирование AGC — тогда и сейчас
В 1960-х годах код для бортового управляющего компьютера был написан на перфокартах и собран на ленту с использованием программной системы под названием YUL. Эта система была более продвинутой, чем можно было ожидать в 1960-х годах, она включала систему управления исходным кодом, трекала и включала изменения. Для полета ПО было установлено на ПЗУ с линейной выборкой многократно прошитых сердечников (в «вязанной» памяти), причем провода физически проходили вокруг сердечников для 0 или через сердечники для 1. Другими словами, каждый такой сердечник был изготовлен по индивидуальному заказу, а данные сохранялись в схеме плетения проводов. Это обеспечивало надежное хранение ПЗУ высокой плотности, но требовало несколько недель на изготовление.
Поскольку было непрактично производить новый веревочный сердечник для каждого изменения, во время разработки использовался другой подход. Симулятор запоминающего устройства на магнитных сердечниках позволял загружать программу в бортовой компьютер из внешнего запоминающего устройства. Этот симулятор — часть контрольного устройства размером с холодильник (ниже на изображении) — интерфейс отладки к AGC через диагностический разъём на бортовом компьютере. Монитор позволял программистам устанавливать точки останова, проверять регистры и т. д., используя индикаторы и переключатели.
В моем случае я написал программное обеспечение на своем ноутбуке и собрал его с yaYUL, современной версией YUL, написанной командой Virtual AGC. Я протестировал программное обеспечение на смоделированной AGC, используя Code: Blocks IDE, который предоставляет функции отладки, несколько похожие на те, что были в 1960-х годах. Чтобы запустить код на реальном AGC, мы не производили сердечники. К счастью, Майк Стюарт построил плату для загрузки кода в AGC, используя тот же тестовый разъем AGC, который первоначально использовался контрольным устройством.
Заключение
Я реализовал алгоритм хеширования SHA-256 и запустил его на бортовом управляющем компьютере Apollo, который нам удалось восстановить, этот процесс занял 10,3 секунды на хеш. Это не первый мой эксперимент с абсурдным майнингом биткоинов. Я пробовал добывать их вручную при помощи карандаша и бумаги; скорость хеширования составляла 0,67 хешей в день. Использование мэйнфрейм компьютера IBM с перфокартами начала 1960-х годов обеспечило скорость хеширования до 80 секунд на хеш. Моя самая быстрая реализация была на Xerox Alto (знаменитый компьютер 1973 года, вдохновитель Macintosh), он выполнял 1,5 хеша в секунду. Таким образом, бортовой компьютер Apollo смог превзойти старый компьютер IBM на базе транзисторов, но не Alto.
Стоимость программы Apollo в 1973 год составила 25,4 миллиарда долларов, что эквивалентно примерно 150 миллиардам долларов сегодня. В настоящее время рыночная капитализация Биткоина составляет 200 миллиардов долларов, поэтому, если бы НАСА занималось майнингом Биткойнов, они могли бы заплатить за всю программу Apollo и при этом даже скопить денег. Но есть один недостаток такого плана — низкая производительность компьютера Apollo, поскольку майнинг блока занял бы гораздо больше времени жизни вселенной.
Мой код доступен на Github; код майнинга находится в BITCOIN.agc. CuriousMarc имеет серию видео AGC, которые вы можете посмотреть для получения дополнительной информации о проекте восстановления.
Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас, оформив заказ или порекомендовав знакомым, 30% скидка для пользователей Хабра на уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5–2650 v4 (6 Cores) 10GB DDR4 240GB SSD 1Gbps от $20 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).
Dell R730xd в 2 раза дешевле? Только у нас 2 х Intel TetraDeca-Core Xeon 2x E5–2697v3 2.6GHz 14C 64GB DDR4 4×960GB SSD 1Gbps 100 ТВ от $199 в Нидерландах! Dell R420 — 2x E5–2430 2.2Ghz 6C 128GB DDR3 2×960GB SSD 1Gbps 100TB — от $99! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5–2650 v4 стоимостью 9000 евро за копейки?
