Краткий обзор

1. OpenAI заявляет об опровержении гипотезы об экспоненциальном времени, в то время как исследователи организуют независимую проверку полученных результатов.
2. Раскрытое ускорение решения задачи SAT не доказывает возможности практической атаки на процесс майнинга или подписи транзакций в Биткоине.
3. Формализация в системе Lean охватывает более слабую подэкспоненциальную временную границу, чем самая сильная заявленная в публикации.

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

В данном контексте ETH означает «гипотезу об экспоненциальном времени», а не «Эфир». Речь идет о задаче 3-SAT, головоломке, в которой компьютер должен найти значения «истина» или «ложь», удовлетворяющие набору логических правил. Гипотеза утверждает, что решение этих задач требует экспоненциального времени в зависимости от количества переменных в худшем случае.

OpenAI заявляет, что результаты были проверены в Lean, системе поддержки доказательств, хотя в примечании к области применения описывается более слабая временная граница, чем самая сильная, заявленная в публикации. Исследователи, организующие проверку результатов сообществом, прямо отказались подтвердить их. В их письме говорится: «Наше участие не следует рассматривать как подтверждение данного утверждения».

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

Раскрытая граница не доказывает существование алгоритма за полиномиальное время и не решает вопрос P=NP, то есть вопрос о том, можно ли решить каждую задачу принятия решений, решения которой можно проверить за полиномиальное время, также за полиномиальное время.

Анализ CryptoSlate ограничен вводными страницами 1–8 публикации, а не полным доказательством.

Утверждение о задаче SAT. Отсутствует связь с атакой на Биткоин.

Заявленное OpenAI опровержение гипотезы ETH касается решения формул. Майнинг и транзакции представляют собой различные конкретные задачи.

Изучите задачу Биткоина

Изучите задачу Биткоина МайнингТранзакции

Поиск допустимого хеша заголовка блока. Теоретическая граница SAT не доказывает наличие измеримого преимущества в майнинге.

Подписи авторизуют транзакции. Утверждение о задаче SAT не демонстрирует восстановления закрытого ключа secp256k1.

Само по себе наличие субэкспоненциальной границы для задачи SAT не доказывает возможность практической атаки на Bitcoin.

Опровержение гипотезы ETH – это утверждение OpenAI, которое требует независимой проверки. Доказательства, представленные в статье, ограничены вводными страницами 1–8. Не приводятся данные о времени атаки, размерах кодирования, результатах тестирования или независимом криптографическом аудите.

Источники и доказательства

Источники

1. Объявление OpenAI
2. Рукопись, вводные страницы 1–8
3. Официальная область применения Lean
4. Письмо с результатами независимой проверки
5. Bitcoin BIP340
6. Правила майнинга Bitcoin
7. Подписи транзакций Bitcoin

Подтверждающие факты

• Компания OpenAI заявила 26 октября, что её система разработала опровержение гипотезы об экспоненциальном времени, и что этот результат впоследствии был проверен в системе Lean; независимая проверка сообществом продолжается. [1] [4]
• В рукописи утверждается, что разработан детерминированный алгоритм для точного подсчета допустимых решений булевых формул фиксированной ширины за субэкспоненциальное время и в полиномиальном пространстве. [2] [3]
• Раскрытое ограничение на субэкспоненциальное время для задачи SAT не устанавливает алгоритм полиномиального времени и не решает вопрос о равенстве P=NP. [2] [3]
• В пояснительной записке OpenAI, касающейся формализации, указано, что для системы Lean установлено более слабое логарифмическое ограничение по времени, чем более точное ограничение, представленное в рукописи от 25 октября. [3]
• В письме сообщества, подписанном Расселом Импальяццо, Рамамоханом Патури и Райаном Уильямсом, говорится, что их участие не следует рассматривать как сертификацию и призывается к тщательной независимой проверке. [4]
• Bitcoin использует ECDSA и подписи Шнорра на основе кривой secp256k1; BIP340 определяет предположения о безопасности подписей Шнорра, связанные с дискретными логарифмами и хеш-функциями, и указывает на более строгие предположения для доказательств безопасности ECDSA. [5] [7]
• Майнинг Bitcoin заключается в поиске хеша заголовка блока, который меньше заданного значения, в то время как подписи транзакций авторизуют проведение операций; это разные криптографические задачи. [6] [7] [5]
• Раскрытое теоретическое ускорение решения задачи SAT само по себе не демонстрирует практическую атаку на Bitcoin; для его применения потребуется конкретное кодирование и сравнение затрат для соответствующей криптографической задачи. [2] [3] [5] [6]
• Сложность Bitcoin пересчитывается каждые 2016 блоков, но этот механизм отделен от авторизации подписей.

[6] [7] – OpenAI утверждает, что для того, чтобы превратить теоретические достижения в практические улучшения, необходимы дальнейшие значительные исследования. [1]

Методология

Качественная схема, использующая утверждение OpenAI, задокументированную область применения Lean, независимое заключение эксперта и документацию протокола Bitcoin. Геометрия представлена в виде схемы, а не в виде масштаба производительности. Нативные панели сравнивают задачи майнинга и осуществления транзакций.

Область применения

Опровержение ETH – это утверждение OpenAI, которое ожидает независимой проверки. Доказательства, представленные в статье, ограничены вводными страницами 1–8. Не установлены временные рамки атак, размеры кодирования, эталонные показатели или независимый криптографический аудит.

Инфографика от CryptoSlate

У Bitcoin есть два различных аспекта безопасности

Для Bitcoin майнинг и авторизация транзакций – это отдельные задачи. Майнеры ищут хеш заголовка блока, который меньше целевого значения. Подписи подтверждают право на осуществление транзакции. Системы подписей Bitcoin включают ECDSA и Schnorr на эллиптической кривой secp256k1, как описано в BIP340.

Представленные там предположения о безопасности касаются дискретных логарифмов эллиптической кривой и хеш-функций. Основной вопрос безопасности заключается в том, может ли злоумышленник вывести закрытый ключ из его открытого аналога. Опровержение предположения о наихудшем случае решения SAT не показывает само по себе, как обойти эти конкретные механизмы. Для практической атаки все равно потребуется подходящее кодирование, реализация и сравнение затрат на атакуемую задачу.

Количество переменных в формуле SAT также нельзя напрямую приравнять к битовой длине криптографического ключа или хеша. Область применения Lean измеряет ее границы, используя переменные закодированной формулы и длину входных данных. Замена знакомого количества криптографических бит на эти границы приведет к тому, что будет пропущена работа, необходимая для представления реальной проблемы.

Регулировка сложности в Bitcoin пересчитывает целевое значение майнинга каждые 2016 блоков. Это касается создания блоков, а не авторизации подписей. Это не сделает преимущество в частном майнинге несущественным.

Это различие возникло в ходе дискуссии, которую CryptoSlate освещала 7 октября, когда Джастин Дрейк призвал к подготовке к «режиму бункера» после предыдущего выпуска математических исследований OpenAI. Это предупреждение касалось возможной будущей атаки; предыдущее объявление не демонстрировало практического взлома ECDSA или RSA. Утверждение об ETH от 26 октября касается другого результата.

Райан Уильямс, опубликовавший сообщение под ником @rrwilliams, заявил, что ему, Расселу Импальяццо и Мохану Патури было предложено организовать открытую, независимую проверку без соглашений о неразглашении и без какой-либо компенсации.

В отдельном сообщении @rrwilliams сообщил, что попросил OpenAI проверить, не были ли скомпрометированы существующие криптосистемы, и передал, что, по всей видимости, они в безопасности. Это его рассказ о проверке, запрошенной у OpenAI, а не независимый криптографический аудит.

Сама компания OpenAI утверждает, что для достижения практических улучшений необходимы дальнейшие значительные исследования. На вопрос о том, какую пользу разработчики могут извлечь из этого, @rrwilliams ответил, что не знает, допустив как возможность прогресса в течение 12 месяцев, так и отсутствие такового. Организаторы планируют делиться результатами по мере проведения проверки.

Контекст статьи.