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