:RU: Представляем Ofelimos: консенсусный протокол с доказательством полезной работы

[dmitry.stas]

Перевод статьи Introducing Ofelimos: a proof-of-useful-work consensus protocol - IOHK Blog

Исследовательский департамент IOG представляет новый, доказуемо безопасный консенсусный протокол для минимизации потерь энергии в блокчейнах с консенсусом с доказательством работы PoW.

Минимизация затрат на энергию proof of work (PoW) и углеродного следа является одной из наиболее горячо обсуждаемых тем в крипто пространстве. Замена примитива PoW в протоколе с самой длинной цепочкой Накамото доказательством полезной работы (PoUW) долгое время теоретизировалась как идеальное решение во многих отношениях, но до сих пор этой концепции не хватало убедительно безопасной реализации.

Сегодня на ведущей международной конференции по криптологии Crypto, Input Output Global, Inc (IOG) представляет Ofelimos, новый блокчейн протокол на основе PoUW, механизм консенсуса которого одновременно реализует задачу оптимизации децентрализованных решений. Механизм консенсуса использует работу для решения вычислительных задач, представляющих практический интерес для поддержания блокчейна.

Доказательство работы против доказательства полезной работы

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

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

Одной из задач PoUW является решение следующей дилеммы: если проблемы, которые необходимо решить, действительно полезны (исходят из реального мира), злоумышленник может направить систему на постановку легко разрешимых (или уже решенных злоумышленником) задач. Это позволило бы использовать ресурсы злоумышленника для создания большего количества блоков, чем сможет честный участник с тем же количеством ресурсов, и, таким образом, снизило бы безопасность блокчейна. С другой стороны, сведение к минимуму возможностей злоумышленника увеличивать производство своих блоков может потребовать создания случайных проблемных случаев, что делает вычисления системы бесполезными на практике.

Ofelimos решает эту дилемму вместе с формальным анализом безопасности и полезности.

Обзор Ofelimos

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

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

По нескольким причинам в PoUW также желательно поддерживать один запрос (относительно) быстро, что сводит к минимуму вероятность одновременной публикации нескольких блоков, например. С другой стороны, примеры клиентских задач должны быть нетривиальными для решения, чтобы аутсорсинг вычислений был привлекательным. Таким образом, для PoUW естественно стремиться к классам вычислений, которые являются сложными в целом, но делятся на небольшие “равномерные” шаги. Каждый шаг должен требовать одинакового объема работы (в ожидании) и соответствовать одному запросу чистого PoW.

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

Поэтапное преобразование из PoW в PoUW

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

Давайте реконструируем процесс, как преобразовать чистый PoW в PoUW в этой настройке.

1. В чистом PoW майнер должен расширить свою самую длинную цепочку на новый блок, повторно хешируя новый блок в отношении с заданной целью (изменяя счетчик, включенный в блок). В качестве первого шага повторяющееся хеширование мы заменяем повторным вычислением M шага поиска SLS предыдущим S состоянием поиска, сохраненного в цепочке, где блок определяет случайное начальное значение для шага поиска. См. Рисунок 1 (правая сторона): Предыдущее S состояние поиска расширяется рандомизированным M шагом поиска с использованием начального значения, полученного в результате хеширования блока вместе с состоянием S, что приводит к новому (возможно, лучшему) S’ состоянию поиска. Этот процесс повторяется до тех пор, пока не будет выполнено еще не указанное условие “?”, позволяющее майнеру опубликовать блок. Во время этого процесса майнер отслеживает наилучшее состояние Sbest, которое было найдено во время этого повторяющегося процесса.

Рисунок 1: Хеширование по отношению к целевому T (PoW, слева). Повторение М шага поиска (PoUW, справа).

2. Теперь мы исправляем отсутствующее условие успеха “?”. Для достижения хороших стохастических свойств, которые не зависят от конкретного вычисления, поиск блока отделяется от качества вычисленного состояния S’ путем добавления после шага поиска “пост-хеш” к шагу поиска (повторное использование начального значения) – см. Рисунок 2 – и блок имеет право на публикацию, если это значение хеша ниже некоторого целевого значения T3. Помимо лучшего на данный момент решения Sbest, это вводит новое состояние St, которое должно быть опубликовано вместе с блоком, состояние, которое приводит к хешу ниже T3, чтобы доказать право на публикацию блока. Обратите внимание, что только Sbest служит в качестве обновления состояния (для дальнейшего изучения майнерами), в то время как St служит только свидетелем права на публикацию блока.

Рисунок 2: Рандомизация права на публикацию блока

3. Учитывая, что M сложнее вычислить, чем H, и что не все примеры M могут потребовать одинакового объема работы, злоумышленник может дробить начальные состояния, которые позволят ему ускорить свои M-вычисления по сравнению с честным майнером, тем самым получая преимущество в более быстром производстве блоков и снижении безопасности системы. Мы делаем невыгодным такое дробление, требуя, чтобы начальный хеш был ниже целевого значения T1. Например, перед выполнением М шага поиска майнер должен найти более низкое значение хеша, изменяя счетчик блоков в соответствии с чистым PoW. См. Рисунок 3. Конкретно, T1 выбирается таким образом, чтобы ожидаемая работа по нахождению хеш-значения ниже целевого T1 стоила по меньшей мере столько же, сколько наихудшая временная сложность вычисления M – обеспечение того, чтобы дробление для простого примера было таким же дорогостоящим, как вычисление “неудобного” примера M. Триплет (Bctr, Sbest, St), удовлетворяющий вышеуказанным условиям, таким образом, представляет собой PoUW.

Рисунок 3: Защита от дробления путем предварительного хеширования в отношении целевого T1

4. В отличие от чистого PoW, мы не можем позволить себе, чтобы ноды проверяли PoUW, повторяя M-вычисления майнера, поскольку это означало бы огромное количество повторяемых вычислений и, таким образом, значительно уменьшило бы долю действительно полезных вычислений в системе. Чтобы избежать этого, после “нахождения” публикуемого блока майнер должен создать краткий неинтерактивный аргумент (SNARG), чтобы доказать такой успех - с тем преимуществом, что сложность проверки становится независимой от сложности вычисления M. Кроме того, доказано правильное вычисление наилучшего решения Sbest. См. Рисунок 4.

Рисунок 4: Минимизация распределенной проверки путем добавления неинтерактивного доказательства

5. Чтобы воспользоваться преимуществами распределенного параллельного майнинга, пример SLS распараллеливается (например, путем поддержания нескольких путей поиска), поскольку в противном случае все майнеры одновременно искали бы одно и то же состояние, вводя множество (значительно) избыточных шагов поиска. Обратите внимание, что по соображениям безопасности производство блоков в стандартном “Nakamoto” PoW происходит медленно, и что обновления состояний привязаны к блокам. С другой стороны, обновление состояний должно происходить быстро, чтобы майнеры не искали "устаревшие” состояния. Таким образом, мы вводим два типа блоков: “трудно находимые” блоки ранжирования с той же функцией, что и в консенсусе Накамото, и “легко находимые” входные блоки, которые функционируют как транзакции, на которые в конечном итоге ссылаются блоки ранжирования. Таким образом, лучшее решение майнера может быть распространено относительно быстро, что позволяет держать всех майнеров в курсе последних событий. В частности, это достигается путем предварительной оценки конечного хеша по отношению к “легкой” цели T3. Если он находится ниже, он квалифицируется как публикуемый блок, но только если цель находится ниже “более сложной” цели T2, блок квалифицируется как “соответствующий консенсусу” блок ранжирования - в противном случае он определяется как входной блок. См. Рисунок 5.

Рисунок 5: Пост-хеш ниже T2 квалифицирует блок как блок ранжирования. Пост-хеш между T2 и T3 квалифицирует блок как входной блок

Свойства протокола

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

Безопасность блокчейна:

• Дробление: у злоумышленника нет никакого преимущества при дроблении для простых в вычислении примеров M. Это достигается путем адаптации порога предварительного хеширования T1 таким образом, что вычисление M в любом примере не сложнее, чем поиск нового предварительного хеша ниже T1 (в ожидании).
• Сопротивление преимуществу злоумышленника: Преимущество противника в более быстром вычислении PoUW, чем сделают это честные стороны, ограничено. Это достигается путем отделения успеха блока от фактического вычисления и предварительного хеширования ниже целевого значения T1. В частности, следуя стандартной модели в [GKL14, PSS16] и предполагая, что у злоумышленника нет преимущества в вычислении M быстрее, чем у честных сторон, протокол допускает, что злоумышленник контролирует какое-то меньшинство вычислительной мощности, выделенной для сети, – как и Bitcoin. Напротив, даже если злоумышленник должен иметь возможность вычислять M без затрат в каждом примере, протокол по–прежнему допускает, что злоумышленник контролирует до трети всех вычислительных ресурсов, поскольку они все равно будут работать с “половиной” затрат из-за предварительного хеширования в отношении T1.
• Переменная сложность: В протоколах консенсуса PoW/PoUW сложность поиска блока должна постоянно адаптироваться к текущему уровню вычислительной мощности, выделенной для системы. В Ofelimos это легко достигается путем адаптации целевого значения T2 для (одиночного) пост-хеша, выполняемого после шага поиска, который соответствует требованиям для публикации блока ранжирования.

Эффективность:

• Частые обновления: Разделение между блоками ранжирования и блоками ввода гарантирует быстрое распространение обновлений состояний.

• Полезность: Под полезностью мы определяем соотношение общей вычислительной работы, которая затрачивается на задачу SLS (это упрощение – более тщательное определение и анализ можно найти в этой статье). Основными источниками “бесполезной” работы в системе являются повторяющееся предварительное хеширование по отношению к T1 и вычисление SNARG. Обратите внимание, что:

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

• SNARG должен быть вычислен только в отношении двух из многих M-вызовов, того, который дает St (подразумевающий успех блока) и Sbest (лучшее решение). Таким образом, накладные расходы, вызванные вычислением SNARGs, могут быть сведены к минимуму за счет снижения порога T3, который определяет успешность блока, в качестве компромисса с более медленными обновлениями состояния.

Полезность зависит от характеристик M. Если время выполнения M достаточно сконцентрировано, сложность предварительного хеширования может быть установлена на уровне, близком к средней сложности M. Учитывая приведенные выше наблюдения, полезность достигает примерно 50%, поскольку майнер тратит примерно половину своего времени на вычисления M. Многие классические проблемы SLS, по-видимому, попадают в эту категорию. Однако, если M не “хорошо себя ведет”, полезность может быть близка к нулю. Таким образом, выбор конкретных алгоритмов SLS и их M шагов поиска имеет решающее значение для достижения PoUW с разумной полезностью.

Вывод

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

Исследовательская работа "Ofelimos: комбинаторная оптимизация с помощью доказательства полезной работы” была впервые опубликована в октябре 2021 года.

Я хотела бы поблагодарить Маттиаса Фитци (Matthias Fitzi) за его вклад и поддержку в подготовке этого поста в блоге.

// От переводчика: для получения дополнительных переведенных на русский язык статей о Cardano посетите русскоязычный раздел на форуме Cardano. Видеоролики о Cardano на русском можно найти на YouTube канале нашего замечательного амбасадора Тимура Сахабутдинова, а также на канале Чарльз Хоскинсон на русском. Хотите поговорить или задать вопрос о Cardano по-русски? Приглашаем вас в наше уютное сообщество в Telegram. Оставайтесь на связи, все только начинается!