I. Введение

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

II. Доверие против проверки

«Старый мир»: доверие или делегированная ответственность

Финансовые системы (банки, брокеры, биржи и т. д.) должны работать добросовестно, чтобы выполнять свои социальные функции. Какие механизмы стимулируют их действовать добросовестно? «Старый мир» предполагает доверие как показатель честности. Мы доверяем банкам, пенсионным фондам и т. д., чтобы они работали честно. Давайте спустимся в кроличью нору и изучим основу этого доверия, игнорируя «театр честности» — высокие здания и причудливые костюмы — призванные произвести на нас впечатление. С чисто рациональной и утилитарной точки зрения, то, что мешает финансовой системе конфисковать все наши средства, — это угроза социального позора, тюрьмы и штрафов. Есть и пряник — репутация, которая привлекает будущих клиентов и приносит прибыль в будущем. Подписывая финансовые отчеты своими именами, люди из «старого мира»поставить свою личную свободу, существующие и будущие финансы в качестве залога честности, и мы, общественность, основываем наше доверие на этом соглашении. Проверка этой целостности делегирована таким экспертам, как бухгалтеры, аудиторы и регулирующие органы. Мы будем называть это делегированной ответственностью. Это неплохая система: она уже довольно давно верой и правдой служит современной экономике.

Новым вариантом подхода «старого мира» является Trusted Execution Environment (TEE). Надежный производитель оборудования (например, Intel) производит физическую машину (например, микросхему SGX), которая не может отклоняться от заданных вычислений и подписывает правильные состояния, используя секретный ключ, известный только этой физической машине. Целостность теперь основана на доверии к оборудованию и его производителю, а также на предположении о невозможности извлечения секретных ключей из таких физических устройств.

«Новый мир»: проверка, или всеобъемлющая подотчетность

Блокчейны предлагают более прямой способ достижения целостности, отраженный девизом «Не доверяй, проверяй». Этот «новый мир» не требует театра честности, он не полагается на бухгалтеров, а его разработчики и специалисты по обслуживанию сетей не ставят на карту свою личную свободу, чтобы завоевать общественное доверие. Целостность гарантируется инклюзивной подотчетностью: узел со стандартной вычислительной установкой (ноутбук, подключенный к Интернету) должен иметь возможность проверять целостность всех транзакций в системе.

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

• Конфиденциальность: если каждый сможет проверять все транзакции, конфиденциальность может быть нарушена. Отсутствие конфиденциальности отпугивает бизнес, поскольку это означает, что конфиденциальная информация может не оставаться в собственности. Это также отпугивает людей, поскольку подрывает человеческое достоинство .
• Масштабируемость. Требование, чтобы система соответствовала стандартному ноутбуку, означает, что она не может масштабироваться, просто переходя на более крупные компьютеры и более широкую полосу пропускания. Это приводит к жесткому ограничению пропускной способности системы.

Системы доказательств (обсуждаемые далее) являются отличным решением обеих проблем. Системы доказательства с нулевым разглашением (ZK) в настоящее время являются признанным инструментом для обеспечения конфиденциальности в блокчейнах и превосходно объяснены в нескольких сообщениях Zcash [ 1 , 2 , 3 ]. Хотя ZK-STARK предлагает нулевое знание, в этом посте это не обсуждается, а основное внимание уделяется масштабируемости и прозрачности (S и T в STARK).

III. Системы доказательств

Proof Systems началась с введения Гольдвассером, Микали и Ракоффом модели Interactive Proof (IP) в 1985 году. Интерактивные доказательства — это протоколы, в которых участвуют два типа объектов: доказывающий и проверяющий , которые взаимодействуют в течение нескольких раундов, отправляя Сообщения. У доказывающего и проверяющего есть конфликтующие цели: доказывающий хочет убедить проверяющего в целостности определенных вычислений, а проверяющий является подозрительным привратником, которому публика доверила задачу различать трюизмы и ложность. Доказывающий и проверяющий взаимодействуют интерактивно, по очереди отправляя сообщения друг другу. Эти сообщения зависят от доказываемого утверждения, от предыдущих сообщений, а также могут использовать некоторую случайность.На стороне доказывающего случайность используется для достижения нулевого знания, а на стороне проверяющего случайность необходима для генерации запросов к доказывающему.В конце интерактивного процесса верификатор выводит решение либо принять новое состояние, либо отклонить его.

Хорошей аналогией является процесс экспертизы, практикуемый в суде, когда одна сторона подает иск, а ее контрагент сомневается в его обоснованности. Для того чтобы утверждение было признано верным, ответы заявителя (доказывающего) на вопросы экзаменатора (проверяющего) должны быть непротиворечивыми и достоверными. Ожидается, что процесс проверки выявит любое несоответствие между утверждением и реальностью и, таким образом, разоблачит его как ложное.

Мы говорим, что система доказательств решает CI, если при обновлении системы из состояния A в состояние B выполняются следующие свойства:

• Полнота: если доказывающий действительно знает, как допустимым образом изменить состояние с A на B , то доказывающему удастся убедить проверяющего принять изменение.
• Надежность: если доказывающий не знает, как изменить состояние с A на B , то проверяющий заметит несоответствие во взаимодействии и отклонит предложенный переход состояния. Остается крошечная вероятность ложного срабатывания, т. е. вероятность того, что верификатор примет недействительное доказательство. Эта вероятность является параметром безопасности системы, который можно установить на приемлемом уровне, таком как 1/(2¹²⁸), что аналогично шансам на выигрыш Powerball пять раз подряд.

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

IV.STARK

К настоящему времени существует довольно много теоретических конструкций систем доказательств, а также их реализации. Некоторые из них развернуты в криптовалютах, например, SNARK , используемые Zerocash / Zcash , и Bulletproofs (BP), развернутые в Monero . (Для получения общей информации о системах доказательств см. здесь .) Что отличает STARK , так это сочетание следующих трех свойств: масштабируемость (S в STARK), прозрачность (T в STARK) и экономичная криптография.

Масштабируемость — экспоненциальное ускорение проверки

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

• Масштабируемый прувер: время работы прувера «почти линейно» по сравнению со временем, которое потребовалось бы доверенному компьютеру для проверки CI путем простого повторного выполнения вычислений и проверки того, соответствует ли результат тому, что утверждает кто-то. Соотношение «накладных расходов» (время, необходимое для создания доказательства/время, необходимое для простого запуска вычислений) остается достаточно низким.
• Масштабируемый верификатор: время работы верификатора является полиномиальным в логарифме простого времени воспроизведения. Другими словами, время выполнения верификатора экспоненциально меньше , чем простое воспроизведение вычислений (напомним, что «воспроизведение» — это текущий метод блокчейна для достижения инклюзивной подотчетности).

Примените это понятие масштабируемости к блокчейну. Вместо текущего режима проверки с помощью наивного воспроизведения представьте, как все будет выглядеть, когда блокчейн перейдет к проверке с использованием систем доказательства. Вместо того, чтобы просто отправлять транзакции для добавления в цепочку блоков, узел проверки должен будет сгенерировать доказательство, но благодаря Scalable Prover время его работы почти линейно по сравнению со временем работы простого решения воспроизведения. А Scalable Verifier выиграет от экспоненциального сокращения времени проверки. Кроме того, по мере увеличения пропускной способности блокчейна большую часть эффекта будут брать на себя узлы проверки (которые могут работать на выделенном оборудовании, например, майнеры), в то время как узлы проверки, составляющие большинство узлов в сети, вряд ли будут затронуты. .

Давайте рассмотрим конкретный гипотетический пример, предполагая, что время проверки (в миллисекундах) масштабируется как квадрат логарифма количества транзакций (tx). Предположим, мы начинаем с 10 000 транзакций/блок. Тогда время работы верификатора равно

VTime = ( log₂ 10 000)² ~ (13,2)² ~ 177 мс

Теперь увеличьте размер блока в сто раз (до 1 000 000 транзакций/блок). Новое время работы верификатора

VTime = ( log₂ 1 000 000)² ~ 20² ~ 400 мс

Другими словами, увеличение пропускной способности транзакций в 100 раз привело только к увеличению времени работы верификатора в 2,25 раза!

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

Прозрачность: с доверием к никому, с честностью для всех

Прозрачность означает² отсутствие доверенной настройки — использование секретов при настройке системы. Прозрачность дает много преимуществ. Это устраняет процедуру генерации настройки параметров, которая представляет собой единую точку отказа. Отсутствие надежной системы позволяет даже влиятельным организациям — крупным корпорациям, монополиям и правительствам, которые контролируют финансовую систему «старого мира», — доказывать КИ и добиваться общественного признания своих утверждений, потому что нет известного способа подделать СТАРК доказательства ложности, даже самыми могущественными сущностями. На более тактическом уровне это значительно упрощает развертывание новых инструментов и инфраструктуры и изменение существующих без необходимости сложных церемоний генерации параметров. Самое главное,Перефразируя Авраама Линкольна , прозрачные системы позволяют работать, не доверяя никому и честно для всех.

Бережливая криптография: безопасная и быстрая

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

• Постквантовая безопасность: STARK, вероятно, защищены от эффективных квантовых компьютеров.
• Конкретная эффективность: для данного вычисления прувер STARK как минимум в 10 раз быстрее, чем прувер SNARK и Bulletproofs. Верификатор STARK как минимум в 2 раза быстрее, чем верификатор SNARK, и более чем в 10 раз быстрее, чем верификатор Bulletproof. Поскольку StarkWare продолжает оптимизировать STARK, эти показатели, скорее всего, улучшатся. Однако длина доказательства STARK примерно в 100 раз больше, чем у соответствующего SNARK, и примерно в 20 раз больше, чем у BulletProofs.

V. Резюме

Мы начали с объяснения «нового мира» блокчейнов без разрешения, девизом которого является «Не доверяй, проверяй». Принцип инклюзивной подотчетности требует, чтобы целостность финансовой системы могла быть легко проверена кем угодно, в отличие от делегированной подотчетности «старого мира». Чтобы блокчейны могли масштабироваться, нам нужны методы, позволяющие проверять вычислительную целостность быстрее, чем простое воспроизведение.

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

В следующем посте мы углубимся в математику построения STARK.

Благодарим Виталика Бутерина и Артура Брайтмана за рецензирование черновиков этого сообщения в блоге.

Майкл Рябзев и Эли Бен-Сассон
StarkWare Industries

¹Сохранение конфиденциальности (ZK) предъявляет требования к коду доказывающего, чтобы сообщения доказывающего не пропускали информацию о свидетеле по сторонним каналам. Но надежность не требует никаких доверительных предположений.

² Формально прозрачная система проверки — это система, в которой все сообщения верификатора представляют собой общедоступные случайные строки. Такие системы также известны как протоколы Артура-Мерлина .

³Эта минимальность криптографических допущений справедлива для интерактивных STARK (iSTARK). Неинтерактивные STARK (nSTARK) требуют эвристики Fiat-Shamir, которая является другим зверем.