Многие видят в квантовых компьютерах угрозу для Биткойна. Двое ученых все посчитали: есть ли у квантовых компьютеров преимущество перед классическими майнерами? И если да, то представляет ли это угрозу для Биткойна?
Угрожают ли квантовые компьютеры будущему Биткойна? Появится ли однажды квантовый компьютер, который опустошит все кошельки и намайнит все биткойны разом с помощью своей превосходной вычислительной мощности? Кто-то говорит, что да, в долгосрочной перспективе это может произойти. Другие считают, что нет никаких причин об этом беспокоиться по крайней мере еще очень долгое время.
Мы уже писали о квантовых компьютерах и алгоритме подписи ECDSA. А сегодня я хочу рассказать вам о выводах из статьи, в которой два канадских профессора компьютерных наук анализируют, представляют ли квантовые майнеры опасность для Биткойна, и если да, то в чем именно она заключается.
Тема нетривиальная, особенно для дилетантов в математике. Но поскольку она может представлять интерес для всех, кто интересуется Биткойном и будущим компьютерных технологий, я постараюсь изложить общее содержание статьи как можно более простыми словами.
Содержание:
Качественный рывок в развитии
Основой для вопроса, на который отвечает исследование, послужила следующая теория: если майнер становится слишком могущественным, он может представлять угрозу для сети. Если он контролирует абсолютное большинство вычислительных мощностей сети, то может провести атаку 51%, но и с меньшей долей он может нанести сети серьезный урон посредством «агрессивного» или «эгоистичного» майнинга.
А что, если майнер получит подобное преимущество через использование квантовых вычислений, в результате чего его доля в общем хешрейте сети вырастет непропорционально?
Сам по себе вопрос нам хорошо знаком и звучит даже довольно тривиально: технический прогресс ускоряет майнинг. При этом прогресс не обязательно развивается постепенно: зачастую изменения происходят скачкообразно. С 2011 года видеокарты вытеснили ведущие процессоры, а с 2013 на смену им пришли ASIC-майнеры. С такими переходами эффективность возрастает не линейно, но квадратично или экспоненциально. Теперь, когда ASIC по большому счету исчерпали потенциал классических чипов, квантовые компьютеры могут совершить следующий гигантский технологический скачок.
Само по себе это не должно представлять проблемы. Теоретико-игровая механика Биткойна мотивирует рациональных игроков соблюдать правила самим и держать под контролем остальных участников. Тем не менее технологический скачок может быть очень резким и, возможно, открыть вектор атаки для враждебных сил, действующих иррационально с целью нанести вред Биткойну.
Поэтому имеет смысл знать, когда что-то подобное может случиться. Что должно произойти, чтобы квантовые компьютеры вытеснили ASIC из биткойн-майнинга?
Поиск в несортированных базах данных
Биткойн-майнинг можно рассматривать как генерацию майнерами лотов с помощью своих вычислительных мощностей. Они генерируют случайные хеши, и если какой-то из этих хешей удовлетворяет определенным требованиям, майнер находит блок. Это работает как атака простым перебором по отношению к хеш-функции SHA256.
Как это сформулировали наши два профессора, «майнеры пытаются частично инвертировать криптографическую хеш-функцию». Это «частичное инвертирование хеш-функции» «эквивалентно поиску меченого элемента в неупорядоченном списке (неструктурированный поиск)». Звучит как незначительный момент, но на самом деле он имеет основополагающее значение для всего дальнейшего рассуждения.
Потому что квантовые компьютеры не то чтобы многое умеют. Но одна из тех задач, в которых они абсолютно превосходят классические компьютеры, — это как раз поиск определенного элемента в неупорядоченном списке.
При поиске в несортированной базе данных — по сути атаке простым перебором — классический компьютер может обрабатывать по одной записи за раз. Это как указатель в двумерном пространстве, перемещаемый от элемента к элементу. Когда он просматривает половину записей, вероятность попадания превышает 50 процентов. Следовательно, классическому компьютеру требуется в среднем N/2 операций, где N — общее количество возможных элементов.
У квантовых компьютеров в отношении есть преимущество: кубит может быть 0 и 1 одновременно, поэтому несколько кубитов могут одновременно представлять все возможные варианты. Продолжая аналогию с указателем, это можно представить как указатель, перемещаемый в N измерениях. Если кубиты находятся в этой «суперпозиции», решение уже находится в них. Оно там.
Но производя расчет, вы разрушаете решение. Это знаменитая квантовая дилемма: производя расчет, вы заставляете кванты принимать определенное, но случайное состояние. Так что квантовый компьютер уже знает решение, но, парадоксальным образом, оно обесценивается, как только вы пытаетесь его получить.
Алгоритм Гровера: квадратное практическое ускорение
Здесь-то и вступает в дело алгоритм Гровера. Разработанный Ловом Гровером в 1996 году алгоритм представляет собой метод проверки результата. Комбинируя различные «квантовые вентили» (суть операции в квантовых компьютерах), кубиты обнаруживают некорректные результаты и подавляют их. Таким образом, вероятность получить корректный результат увеличивается с каждым повторением — так называемой итерацией Гровера.
Всё это безумно сложно объяснять в деталях. Но одно ясно: при правильном количестве итераций алгоритм Гровера может значительно ускорить такие поиски. В конце концов, чтобы найти элемент в несортированном списке, Гроверу нужно всего √n попыток. То есть это почти квадратично быстрее.
Два примера: для поиска в списке из четырех элементов и классическим, и квантовым компьютерам хватит двух попыток. Если же элементов будет 5 198 400, то квантовому компьютеру для поиска нужного понадобится не более 2280 попыток, а классическому — более двух миллионов.
Разница огромна, особенно для чрезвычайно сложных задач или высоких значений N (числа элементов), как в биткойн-майнинге. Эта разница и есть так называемое квантовое преимущество. Это один из тех скачков в развитии, какие меняют целые экосистемы. По крайней мере, в теории.
Квантовое преимущество тает
На практике квантовый майнер сталкивается с особой проблемой: он не может найти блок, пока не измерит результат, и потому останавливает процесс. Он должен заранее знать, сколько итераций выполнит.
А это сложный вопрос. Потому что у слишком большого и слишком малого значений есть свои недостатки. Большее число итераций увеличивает вероятность нахождения корректного решения, но и риск того, что другой майнер найдет его быстрее. С другой стороны, меньшее число итераций уменьшает вероятность найти валидный результат, а значит, и квантовое преимущество.
Без ограничения по времени квантовый компьютер мог бы использовать свое квантовое преимущество на полную. Но в майнинге это невозможно. Ему придется искать компромисс между слишком большим и слишком малым числом итераций.
Чтобы рассчитать оптимальный компромисс, исследователи сформировали цепь Маркова с возможными сценариями. Цепь Маркова — это математическая формулировка возможных, преимущественно случайных или частично неожиданных последовательностей. Такая цепочка указывает, какие пути через джунгли вероятностей в среднем приводят к наилучшим результатам: какая настройка алгоритма Гровера была бы идеальной.
Удивительно, но это заняло бы 16 минут.
Два замечательных открытия
Предположим, что квантовый майнер ждет 16 минут, чтобы прочитать результат алгоритма Гровера. В этом случае преимущество над классическими майнерами достигает максимума по отношению к недостаткам, возникающим из-за длительности. Согласно ученым, это преимущество существует независимо от сложности.
Результат очень примечателен, поскольку имеет явные практические следствия. Серьезных следствий я бы выделил два:
Во-первых, майнер с такой тактикой дисквалифицирует себя из примерно 80 процентов блоков, потому что они находятся быстрее, чем за 16 минут. Однако он максимизирует свои шансы на успех с оставшимися 20 процентами. Это должна быть максимальная майнинговая мощность, которую квантовые компьютеры могут достичь без ущерба эффективности.
Во-вторых, большинство криптовалют имеют меньшие интервалы между блоками. В Dogecoin и Litecoin это несколько минут, в Ethereum и Ripple — всего несколько секунд. И с этими блокчейнами квантовые майнеры расквасят себе нос, поскольку квантовое преимущество здесь неприменимо. Они уже квантово-безопасны, по крайней мере в отношении майнинга.
Распараллеливание квантовых компьютеров тоже видится тупиковым вариантом. Хотя это возможно сделать с помощью алгоритма Гровера, по расчетам авторов, он повышает производительность только в √m раз. Для классических компьютеров элемент равен m, что квадратично больше. Это ставит под сомнение то, будут ли квантовые компьютеры когда-либо применимы для майнинга.
78 мегахешей
Эти расчеты уже значительно снижают опасность квантовых компьютеров для блокчейнов. Однако важнейший вопрос остается без ответа: что должно произойти, чтобы квантовые майнеры получили преимущество перед «классическими»? В какой момент (если вообще когда-либо) найти валидный блок станет дешевле с квантовым компьютером?
Решающими для этого являются два фактора: стоимость одной итерации Гровера и отношение требуемого для блока количества хешей к числу необходимых итераций Гровера. Авторы рассчитали это на примере типичного в настоящее время квантового компьютера с «тактовой частотой» 66,7 МГц и получили ответ 224 итерации Гровера в секунду.
Что это значит? 224 итерации Гровера соответствуют хешрейту 78 мегахешей в секунду. Это микроскопическая доля хешрейта Биткойна, лишь крошечная часть того, что на что способны современные ASIC. Пытаться представить это как опасность просто смешно.
Предположительно более энергоэффективные в будущем
Если квантовые компьютеры не представляют угрозы, являются ли они по крайней мере более эффективными? Возможен ли по крайней мере постепенный переход к квантовому майнингу? И если да, то в какой момент?
Для большей эффективности, затраты на электроэнергию на итерацию Гровера должны быть не более чем в 3,49 x 105 раз выше стоимости «классического» хеша. По сравнению с классическими майнерами, имеющими энергоэффективность 10–10 джоулей на хеш, квантовому компьютеру потребуется энергоэффективность выше 3,49 x 105 x 10–10, или около мкДж на итерацию Гровера. Или даже 2240 мкДж в секунду.
Цифра выглядит нереально малой. Но квантовые компьютеры очень энергоэффективны. Когда система охлаждается до 15 милликельвинов, что близко к абсолютному нулю, квантовые биты становятся сверхпроводниками: они практически не нуждаются в электричестве и почти не выделяют тепла. На сегодня охлаждение по отношению к мощности всё ещё делает квантовый компьютер неэкономичным. Но это должно измениться с развитием технологий.
Так что в целом биткойнеры, похоже, могут спать спокойно, без кошмаров о том, как квантовые компьютеры в одночасье разрушают всё, на чём основывается работа Биткойна.
Источник: bitnovosti.com