Квантовите компютри се смятат за заплаха за Биткойн. Двама учени са направили изчисления: Наистина ли квантовите миньори имат предимство пред класическите? И ако е така – представлява ли това заплаха за биткойн?
Биткойн и квантови компютри: Тази тема сме я обсъждали един или два пъти и всъщност тя преследва Биткойн от самото начало.
Заплашват ли квантовите компютри биткойн? Дали един ден ще се появи квантов компютър, който чрез превъзходната си изчислителна мощ ще изпразни всички портфейли и ще изкопае всички биткойни? Някои казват „да“, в дългосрочен план това може да се случи, други казват „не“, няма да има и грам притеснение за много дълъг период от време.
Вече сме писали за квантовите компютри, биткойн и алгоритъма за подписване ECDSA. Днес разглеждаме статия, в която двама канадски професори по компютърни науки анализират дали квантовите миньори представляват опасност и ако да, каква е тя.
Темата не е тривиална, особено за математическите лаици. Но тъй като това е вълнуващо за всеки, който се интересува от Биткойн и бъдещето на компютрите, ще се опитам да представя статията възможно най-просто.
Скачащият прогрес
Основната рамка, върху която авторите изграждат своя въпрос, е следната теория: Ако един миньор стане твърде силен, той може да застраши мрежата. Ако разполага с абсолютно мнозинство, той може да води 51% атаки, но дори и под тази граница може да причини щети чрез „агресивен“ или „егоистичен“ добив.
А какво ще стане, ако даден миньор получи такова предимство чрез квантовите изчисления, че неговият дял от хешрата нарасне непропорционално?
В общи линии, всичко това вече сме го разглеждали и е доста тривиално: технологичният прогрес ускорява добива. Това не се случва постепенно, а често със скокове. От 2011 г. графичните карти изместват основните процесори, а от 2013 г. Asics измества графичните карти. В такива моменти ефективността вече не се увеличава линейно, а квадратично или експоненциално. След като Ascis изглежда до голяма степен е изчерпал потенциала на класическите чипове, квантовите компютри могат да доведат до следващия голям скок.
Само по себе си това не би трябвало да представлява проблем. Теоретичната механика на играта на биткойн мотивира рационалните играчи да бъдат честни и да се контролират взаимно. Все пак технологичният скок може да бъде труден и може да се превърне във врата за враждебни сили, които действат ирационално, за да навредят на биткойн.
Затова е логично да знаете кога може да се случи. Какво трябва да се случи, за да може квантовите компютри да изместят класическите Asics от добива на Bitcoin?
Извършване на търсене в несортирани бази данни
Можете да мислите за добива на биткойни като за миньори, които генерират много с изчислителната си мощ. Те генерират случайни хешове и ако даден хеш отговаря на определени много редки изисквания, миньорът намира блок. Може да се нарече и атака с груба сила срещу хеш функцията 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 Megahashes
Тези изчисления значително намаляват опасността от квантовите компютри. Но основният въпрос все още остава без отговор: Какво трябва да се случи, за да могат квантовите миньори действително да имат предимство пред класическите миньори? В кой момент ще стане по-евтино да се намери блок с квантов компютър – ако изобщо стане?
Два фактора са решаващи за това: разходите за итерация на Grover и съотношението между броя на хешовете, необходими за блока, и броя на необходимите итерации на Grover. Авторите изчисляват това на примера на разпространен в момента квантов компютър със скорост на порта 66,7 мегахерца. Вратите са квантовите операции. Учените са изчислили, че този квантов компютър ще се справи с 224 итерации на грувър в секунда.
Значение? 224 итерации на Гроувър съответстват на скорост на хеширане от 78 мегахеша в секунда. Това е абсолютно микроскопична част от хашрата на Биткойн, а всъщност само малка част от това, което постигат съвременните Асикс. Би било нелепо да усещаме опасност тук.
Вероятно ще бъдат по-енергийно ефективни в бъдеще
Но ако квантовите миньори не представляват заплаха – дали поне са по-ефективни? И така, може ли поне постепенно да се премине към квантов добив? И в кой момент?
За да бъде по-ефективна, енергийните разходи за итерация на Гроувър трябва да са най-много 3,49 x 105 пъти по-големи от разходите за класическо хеширане. В сравнение с класическите миньори, които имат енергийна ефективност от 10-10 джула на хеш, квантовият компютър ще се нуждае от ефективност, по-добра от 3,49 x 105 x 10-10, или около 10 μJ на итерация на Гроувър. Или 2240 μJ в секунда.
Това звучи изключително ниско. Но квантовите компютри са много енергийно ефективни. Щом системата се охлади до 15 миликалвина, т.е. близо до абсолютната нула, квантовите битове се превръщат в свръхпроводник: те не се нуждаят от електричество и не произвеждат почти никаква топлина. Понастоящем охлаждането в зависимост от мощността все още прави квантовия компютър неикономичен. Но това вероятно ще се промени с напредването на технологиите.
И така, като цяло, като биткойнисти можем да спим спокойно и малко по-мъдро и да мечтаем без страх за бъдещето на квантовите компютри.
