Проблемы криптовалют: PoW, запутывание кода и квантовая устойчивость

B продолжении цикла статей “Проблемы криптовалют”, автор Виталик Бутерин (сооснователь Bitcoin Мagazine и проекта Ethereum) рассматривает основные вопросы, стоящие сейчас перед криптовалютным сообществом, и возможные направления развития биткойна и криптовалют в целом.

В первой статье данного цикла мы дали определение криптоэкономики и обсудили вопросы масштабируемости и метки времени. В этой статье мы порассуждаем о доказательствах работы, обфускации кода и устойчивости используемой криптографии против атаки с использованием квантовых компьютеров.

3. Произвольное доказательство проделанных вычислений

Возможно, наиболее существенным результатом науки о доказательствах с нулевым разглашением является концепция доказательства проделанных вычислений произвольного вида: для данной программы P и входных данных I, задача — создать доказательство с нулевым разглашением, что программа P была запущена со входными данными I и завершилась с выходными данными O, такое, чтобы проверить его было просто (т. е. за полилогарифмическое или, в идеальном случае, константное время), даже если сами вычисления требовали очень большого количества шагов. В идеальной модели доказательство могло бы даже прятать значение I, доказывая лишь то, что P была запущена на каких-то входных данных и в качестве результата выдала O. Если I необходимо сделать публичным, должна быть возможность указать это в коде программы. Такой примитив, если он возможен, сделал бы возможными следующие применения криптовалют:

1. Мы бы значительно приблизились к решению проблемы масштабируемости блокчейна. Вместо того чтобы публиковать блоки, содержащие список транзакций, майнеры публиковали бы доказательство того, что они запускали программу, обновляющую состояние блокчейна, и получили определенный результат; таким образом, вместо системы, в которой каждый узел сети должен проверять каждую транзакцию, они могли бы проверяться одним майнером, а другие майнеры и пользователи могли бы быстро проверить, что вычисления были выполнены, и если это так, принять новое состояние блокчейна. Это не полное решение, потому что всё еще остается необходимость передачи данных, но проблема существенно облегчилась бы с таким мощным базовым инструментом.
2. Мы бы значительно приблизились к решению проблемы приватности блокчейна. Решение проблемы масштабируемости блокчейна, описанное выше, скрывало бы детали об отдельных транзакциях, разглашая только тот факт, что все они легитимны. Транзакции были бы скрыты для всех, кроме отправителя и получателя.
3. Стало бы вычислительно возможно использовать Тьюринг-полную сеть консенсуса в качестве распределенной сети облачных вычислений общего назначения. Если у вас есть вычисления, которые вы хотите выполнить, вы могли бы опубликовать программу, и майнеры могли бы запустить ее для вас и вернуть вам результат вместе с доказательством проделанных вычислений.

Существует множество исследований в этой области, в том числе протокол известный как SCIP (succint computation intefrity and privacy), уже работающий в тестовых окружениях, хотя и с ограничением, что доверенная третья сторона должна изначально установить ключи; предполагается, что в том числе другие разработчики могли бы в дальнейшем основываться на этой работе.

Задача: создать программы POC_PROVE(P, I) → (O, Q) и POC_VERIFY(P, O, Q) → {0, 1} такие, что POC_PROVE запускает программу P на входных данных I и возвращает O и доказательство проделанных вычислений Q, а POC_VERIFY принимает на вход P, O, Q и определяет, были ли Q и O легитимно порождены алгоритмом POC_PROVE с P в качестве параметра.

Дополнительные предположения и требования

• Время работы POC_PROVE должно составлять O(n*polylog(n)), где n — количество вычислительных шагов, требуемое для выполнения P.
• Время работы POC_VERIFY должно быть или константным, или логарифмическим по количеству шагов, и точно не более чем линейным по объему памяти.
• Протокол не должен требовать наличия доверенной третьей стороны. Если это необходимо, протокол должен включать в себя механизм, аналогичный использованию защищенной многопользовательской вычислительной платформы.

4. Запутывание кода

Уже много лет мы знаем, как зашифровывать информацию. Простые, надежные, протестированные алгоритмы существуют как для симметричной (где один ключ используется для шифрования и расшифровки), так и для асимметричной криптографии (где ключи для шифрования и расшифровки различаются, и один нельзя получить из другого). Тем не менее, существует еще один вид шифрования, который потенциально мог бы быть очень полезен, но для которого у нас пока нет хорошего алгоритма: шифрование (обфускация, или запутывание) программ. Первоочередная задача — создать обфускатор O такой, что для каждой программы P он порождает программу O(P) = Q такую, что P и Q возвращают одинаковый результат и, что важно, Q не раскрывает никакой информации о внутреннем содержании P. Внутри Q можно спрятать пароль или приватный ключ; кроме того, Q можно использовать для сокрытия принципов работы самого алгоритма P.

В 2007 году было доказано, что идеального «черного ящика» не существует; главная причина — существует разница между обладанием доступом к программе по принципу «чёрного ящика» и обладанием исходным кодом этой программы, неважно, в какой степени запутанным; кроме того, можно определить классы программ, противодействующих обфускации. Как бы то ни было, существует более слабое определение обфускации, известное как «неотличимая» (indistinguishability) обфускация, реализация алгоритма для которой, как представляется, вполне возможна. Определение «неотличимого» обфускатора O таково: взяв две эквивалентные (т. е. на всех одинаковых данных дающих одинаковый результат) программы A и B и вычислив O(A) = P и O(B) = Q, для внешнего наблюдателя должно быть вычислительно невозможно определить, получена ли P из A или из B.

Этот вид обфускации может показаться имеющим существенные ограничения, но, тем не менее, его достаточно для многих приложений. В качестве эвристического аргумента в защиту этого тезиса рассмотрим две программы F и G, где F содержит в коде и просто печатает 32-байтную строку, содержащую хэш от «12345», а G вычисляет и печатает хэш от «12345». По определению «неотличимого» обфускатора, не существует вычислительно приемлемого способа отличить O(F) от O(G). Тем не менее, из O(G) можно получить «12345», поэтому для того, чтобы O(F) и O(G) были неотличимы, из O(F) тоже должно быть можно получить «12345» — что фактически означало бы нахождение прообраза по значению хэш-функции.

Недавно Крэгом Гентри (Craig Gentry), Амитом Сахаи (Amit Sahai) и другими был открыт алгоритм, который для решения этой задачи использует конструкцию, известную как «multilinear jugsaw puzzles». Их алгоритм обещает решить проблему «неотличимого» обфускатора, хотя и дорогой ценой: алгоритм требует использование полностью гомоморфного шифрования (fully homomorphic encryption) — крайне неэффективной конструкции, приводящей к необходимости провести миллиард вычислительных шагов заранее.

Если эту конструкцию можно было бы улучшить, потенциальная польза была бы огромной. Самая интересная идея в мире криптовалют — идея контракта в блокчейне, содержащего конфиденциальную информацию. Это бы позволило, по сути, экспортировать возможности скриптов, написанных на Тьюринг-полных языках, как в Ethereum, в любую другую финансовую или нефинансовую систему в интернете; например, можно представить себе Ethereum-контракт, содержащий пароль от онлайн-банка пользователя, который в случае выполнения определенных условий инициирует HTTPS-соединение с банком, используя какой-то узел в качестве промежуточного, заходит в банковский аккаунт пользователя с его паролем и делает заранее определенный перевод. Поскольку контракт был обфусцирован, промежуточный узел, как и другие узлы в блокчейне, не сможет изменить запрос или получить пароль пользователя. Такую же технику можно применить с любым другим веб-сайтом или, что гораздо проще, с «базовым» блокчейном, например, биткойна.

Задача: реализовать достаточно эффективный механизм «неотличимой» обфускации.

Дополнительные предположения и требования

• Успешные атаки должны осуществляться за время порядка 2^80.
• Алгоритм должен быть достаточно быстрым, так что стандартная ECDSA-подпись или AES-шифрование могли бы быть доступны в рамках 10^8 вычислительных шагов (точнее, 10^8 единиц «топлива» виртуальной машины Ethereum).

5. Цифровая подпись с защитой от квантовых компьютеров

Одна из надвигающихся угроз для криптовалют и для криптографии в целом — квантовые компьютеры. Сейчас эта проблема не выглядит слишком угрожающей: все квантовые компьютеры либо относятся к классу адиабатических, эффективных только на очень ограниченном множестве задач и, возможно, ничем не превосходящих традиционные компьютеры, либо имеют крайне малое число кубитов, не позволяющее разлагать на простые множители числа больше 35. Тем не менее, в будущем квантовые компьютеры могут стать гораздо более мощными, а недавние разоблачения в отношении федеральных агентств США, таких как АНБ, породили слухи (не очень правдоподобные), что армия США уже обладает квантовым компьютером. Принимая во внимание эти факты, имеет смысл рассматривать развитие устойчивой к квантовым компьютерам криптографии в качестве приоритетной задачи.

На настоящий момент все схемы защиты от взлома квантовым компьютером делятся на две категории. Первая из них — алгоритмы на базе решетчатых структур, основанные на алгоритмической сложности нахождения линейной комбинации векторов, сумма которых гораздо короче, чем каждый из векторов. Такие алгоритмы, по всей видимости, мощны и достаточно эффективны, но многие им не доверяют, так как они основываются на сложных математических объектах и строго не доказанных предположениях. Тем не менее, существует и другой класс «квантоустойчивых» алгоритмов: алгоритмы на основе хэш-функций. Один из примеров — классическая подпись Лэмпорта: создать дерево Мёркла из 164 вершин (число подобрано специально, чтобы соответствовать 160 битам безопасности), опубликовать его корень и использовать в качестве подписи для документа подмножество из 82 узлов, псевдослучайно выбранных на основе хэша документа. Такая подпись может использоваться только один раз и довольно неэкономична (около 3000 байт), но выполняет свою задачу.

Можно ли улучшить этот результат? Существует подход, известный как «хэш-лестницы» (hash ladders), позволяющий уменьшить размер подписи до 420 байт. Кроме того, можно использовать деревья Мёркле на другом уровне, увеличивая количество всевозможных подписей за счет добавления 100-300 байт к размеру подписи. В любом случае, даже эти подходы не идеальны, так что криптография на основе хэш-функций должна быть существенно усовершенствована, прежде чем она сможет на равных конкурировать с существующими алгоритмами.

Задача: создать алгоритм цифровой подписи, не опирающийся ни на какое предположение о безопасности, кроме предположения о псевдослучайности значений хэш-функции, и обеспечивающий 160-битную безопасность при атаке классическим компьютером (а значит, согласно алгоритму Гровера, 80-битную при атаке квантовым компьютером) с оптимальным размером подписи и прочими характеристиками.

Дополнительные предположения и требования
Вычислительные затраты на создание подписи не должны превышать 2^24 вычислительных шагов в предположении, что хэширование требует 2^8 шагов (разумное предположение ввиду возможности аппаратной оптимизации и возможного в будущем встраивания в чипы специализированных микросхем для хэширования).
Размер подписи должен быть как можно меньше.
Размер публичного ключа должен быть как можно меньше.
Алгоритм цифровой подписи должен быть масштабируемым и допускать добавление любого количества использований, возможно, ценой добавления константного количества байт на подпись для каждого удвоения максимального количества использований. Если возможно, время перенастройки в таком случае должно быть сублинейно относительно количества использований.

По материалам Ethereum wiki. Автор — Виталик Бутерин.

Продолжение следует.