Прогресс гранта Фонда Ethereum

Прошлым летом Ethereum Foundation (EF) предоставил StarkWare исследовательский грант, чтобы порекомендовать STARK-Friendly Hash (SFH), а затем выпустить эффективное программное обеспечение производственного качества для системы STARK для SFH (по лицензии, одобренной EF) для использования экосистема разработчиков Ethereum. EF установил высокую планку эффективности, значительно превышающую возможности libSTARK (а также libSNARK и BulletProofs).): доказывающий должен генерировать STARK-пруфы для многочисленных повторных вызовов хеш-функции, а скорость создания пруфов (не путать с hash-rate — скоростью хэширования) должна быть не менее 100 хэшей/с, измеренных на квадроцикле. основная машина с 16 ГБ оперативной памяти. Кроме того, доказательство STARK для 100 000 хэшей должно быть проверено за 10 мс на одном ядре и должно иметь размер менее 200 КБ.

Стандартные хеш-функции, такие как SHA2, SHA3 и Blake, и стандартные симметричные шифры, такие как AES, являются золотым стандартом с точки зрения безопасности. Однако эти функции были выбраны для оптимизации набора ограничений, связанных с оборудованием и потреблением электроэнергии. Реализации систем ZKP в то время не существовало, и поэтому «дружелюбие к STARK» не было приоритетом.

Это должно измениться. Масштабируемость блокчейна (и конфиденциальность) требует кратких систем проверки, которые могут подтвердить утверждения о хешированных (и зашифрованных) данных. Часто самые тяжелые части построения доказательства связаны с криптографическими примитивами. Например, так обстоит дело с Zcash Sapling ZK-SNARK , который защищает платежи: большая часть времени (и сложности) проверки приходится на проверку утверждений о вызовах хеш-функций Pedersen и Blake2b. (Цели, поставленные EF для StarkWare, связаны с масштабируемостью, а не конфиденциальностью, но наличие эффективно доказуемых хеш-функций важно в обоих случаях).

Наш проект начался с довольно простой цели: StarkWare должен был собрать и изучить существующие хэш-функции с хорошо зарекомендовавшими себя параметрами безопасности и выбрать среди них наиболее дружественные. Тем не менее, мы быстро поняли, что есть лучший и более амбициозный способ служить сообществу Ethereum, который может принести пользу и другим проектам в этой области: запрашивать новые хеш-функции, оптимизированные для STARK. (Хотя хеш-функции, совместимые с SNARK и BulletProof, не являются целью этого проекта, некоторые из предложенных функций, совместимых со STARK, могут также быть дружественными к этим системам ZKP.)

Мы обратились к двум внешним академическим командам криптографов и профинансировали их исследования, которые привели к двум парам конструкций: пара Vision/Rescue и пара Starkad/Poseidon . Эти конструкции идут парами: один тип работает с двоичными полями, а другой работает с простыми полями. В то же время мы узнали о третьей исследовательской работе под названием GMiMC , которая не запрашивалась и не финансировалась StarkWare. Каждая из трех групп основана на разных принципах проектирования. К этим конструкциям следует добавить старейшую из «дружественных к конечному полю» конструкций — MiMC. Это наш текущий шорт-лист претендентов на звание дружественной к STARK хеш-функции (SFH) (мы всегда в поиске новых). Мы уже запросили экспертную оценку алгебраической безопасности этих кандидатов, но этого далеко не достаточно. Итак, теперь мы приглашаем общественность пинать шины этих кандидатов с помощью общедоступного набора головоломок, вознаграждаемых эфиром и раздаваемых смарт-контрактами. Подробности следуют.

Испытания на столкновение — выиграй немного Ether!

Доктор Томер Ашур согласился провести испытание SFH от имени StarkWare. Он консультировался с различными командами, создававшими кандидатов, и разработал набор головоломок, каждая из которых просила найти коллизию в версии одного из кандидатов SFH (коллизия — это пара различных входных данных с одинаковым хэшем). Существует четыре диапазона параметров: низкий уровень безопасности (предполагается, что он будет взломан примерно через 2⁴⁵ попыток), средний уровень безопасности (возможность взлома примерно через 2⁸⁰ попыток), целевая безопасность (доступен для взлома примерно через 2¹²⁸ шагов) и высокий уровень безопасности (около 2²⁵⁶ шагов). сломать).

Призовой фонд составляет более 200 ETH (> 40 000 долларов США на момент написания статьи) — это большая сумма, но стоимость взлома SFH после его развертывания и массового использования может быть на порядки выше. Первый решатель каждой головоломки будет награжден в соответствии с уровнем безопасности головоломки: 1, 2, 4 или 8 ETH за каждую решенную головоломку. Наш текущий план состоит в том, чтобы выполнить это испытание до конца марта 2020 года, но мы можем продлить его и/или изменить некоторые головоломки позже.

Примечание. Помимо этой задачи, StarkWare НЕ раздает эфир и не проводит ICO. Остерегайтесь мошенников!

Для тех головоломок, которые определены в простых полях, мы внедряем смарт-контракты на Ethereum, которые автоматически присуждают приз тому, кто первым решит. Вы также можете отправить решение напрямую нам вне сети, и мы соберем приз ETH и отправим его вам, но обратите внимание, что мы будем принимать решения только с даты запуска смарт-контрактов. Для бинарных полей офчейн — единственный способ получить приз (виртуальная машина Эфириума, естественно, не поддерживает умножение бинарных полей). За красивые атаки и информацию о них по нашему усмотрению могут быть выданы дополнительные призы.

Следующий шаг — Отборочная комиссия SFH

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

Имея в руках эту рекомендацию, StarkWare начнет писать код для доказывающего и проверяющего, а затем проведет ряд аудитов кода внешними сторонами, прежде чем доставить код в Ethereum Foundation, который поделится им со своим сообществом разработчиков.

У нас очень плотный график, перед нами стоят серьезные задачи, и мы ценим то, что поставлено на карту. Мы сделаем все возможное, чтобы оправдать ожидания сообщества разработчиков Ethereum. Мы просим вашей помощи: пожалуйста, пните шины, выиграйте немного эфира. Подробности и характеристики здесь .

Эли Бен-Сассон

StarkWare