blockchained

7 лет назад

📝 Поиск консенсуса о консенсусе – DPoS или алгоритм делегированного доказательства долей и задача двух генералов. (Ian Grigg)

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

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

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

Положения войск. Армиям A1 и A2 необходимо обеспечить связь друг с другом, но их посланники могут быть перехвачены армией B.

Ранее два генерала приняли решение атаковать, но не согласовали время нападения. Для успешного штурма требуется, чтобы оба генерала атаковали город одновременно, а штурм, предпринятый только одной армией, обречен на провал.
Таким образом, генералы должны обеспечить связь друг с другом, чтобы определить и согласовать время нападения, чтобы при этом каждый генерал был уверен в том, что план штурма согласован.
Поскольку уведомление о получении исходного сообщения может быть перехвачено так же легко, как и само исходное сообщение, то для достижения консенсуса требуется потенциально бесконечная серия сообщений.
Мысленный эксперимент предполагает рассмотрение того, как они могут прийти к консенсусу. В его простейшей форме один генерал является лидером, который определяет время штурма и должен сообщить это время другому генералу. Проблема состоит в разработке алгоритма, который могут использовать генералы для отправки и обработки полученных сообщений, и позволяющего им сделать следующий вывод:
Да, мы оба начинаем штурм в согласованное время.
Учитывая, что согласовать время штурма довольно-таки просто (т.е. достаточно одного сообщения со временем начала штурма и одного сообщения, подтверждающего получение первого), коварство “Задачи двух генералов” заключается в невозможности разработки алгоритма для безопасного согласования генералами времени штурма, при этом позволяющего сделать вывод, приведенный выше.

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

Давайте рассмотрим эволюцию этой задачи.

Централизованная защита от двойной траты

Исходным механизмом финансовой криптографии является простой клиент-сервер или доверенная третья сторона (например, Systemics Open Transaction), то есть эмитент актива, подлежащего двойной трате (например, монеты), запускает один сервер, который предотвращает двойные расходы. Как правило, запросы помещаются в очередь по принципу “первым пришёл — первым ушёл” (FIFO), что в наши дни является стандартом для баз данных.

Рисунок 1 – SOX, одна из первых систем электронной наличности, использующая клиент-серверную централизованную эмиссию как решение проблемы двойной траты.

Слепая электронная подпись монеты

Одним из примечательных вариантов централизованной защиты от двойной растраты было применение технологии слепой подписи монет. Понятие слепой подписи было изобретено Дэвидом Шаумом в конце 1980-х (Дэвид Шаум, Achieving Electronic Privacy).

Монета, подписанная слепой подписью, как любой денежный токен, была свободно используемой (верифицируемой), но, как и все данные, Алиса могла передать ее одновременно и Бобу, и Кэрол.

Раньше решение заключалось в том, чтобы Боб вернул монету на сервер эмиссии, известный как монетный двор, и потребовал обратно только что подписанную монету. Кэрол должна сделать то же самое и быть быстрее!

Рисунок 2 – Электронная наличность со слепой подписью и использованием реально страшной математики

Итак, особый секрет слепой подписи токена заключался в том, что когда он проходил через модифицированный вариант алгоритма шифрования RSA, он мог трансформироваться, создавая новую подпись, которую не создал эмитент, но все еще являющуюся действительной и поэтому имеющей возможность идентифицировать настоящую монету.
Таким образом, слепая подпись означала, что эмитент не мог отследить, что Алиса сделала с ее монетами - весьма полезная штука! Еще один трюк с eCash состоял в том, что если бы Алиса попыталась потратить монету дважды, монетный двор мог бы использовать какой-либо шифр, чтобы объединить некогда потраченные монеты, снять псевдоанонимную защиту и раскрыть непослушную девчонку.

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

Голосование

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

Ранние простые мажоритарные схемы голосования несли в себе массу проблем, и сейчас у всех на слуху алгоритмы нахождения консенсуса Паксос и PBFT (практическая византийская парадигма отказоустойчивости). Но имейте в виду, что за ними стоят Лампорт, теория, спорящие византийские генералы, доктора философии, бумаги и премии Тьюринга, подумать только!

Перечисленные выше вариации на эту тему страдают от некоторых довольно серьезных ограничений, главными из которых являются следующие:

они административно централизованы и / или / поэтому
все участники известны.

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

Алгоритм доказательства выполнения работы

Сатоши отметил, что любой централизованный компонент может быть атакован и, вероятно, так и случится (Накамото, Биткойн: система цифровой пиринговой наличности). Это замечание оказалось верным: MTB закрыл eCash из-за непредусмотренных покупок для взрослых, DigiCash был взломан властями, WebMoney пострадал от атаки на репутацию, e-gold был закрыт ФБР, так же как и LibertyReserve. DigiGold и e-Bullion потерпели неудачу из-за действий своих основателей. Этот список утомителен, и ваш расстроенный автор был ближе к некоторым из этих бедствий, чем хотелось бы. Вы должны провести свое собственное исследование, чтобы избавиться от вины, забывчивости и прочих предубеждений.

Это было отмечено несколькими источниками (см., например, «Иллюзия майнига»), но именно Биткойн представил решение.

Поэтому, по словам Сатоши, нам необходимо исключить централизованную сторону уязвимости (CVP), также известную, как доверенная третья сторона (TTP). И используя метод дедукции делаем вывод: поскольку мы не можем доверять голосованию известных сторон, все мы должны публиковать и подтверждать одни и те же данные, должны принимать и наслаждаться легким входом и выходом – псевдоанонимность.

Отлично, но мы всё еще не решили проблему двойной траты, а только переместили ее из узкой области в область намного более масштабную.

Изящным и известным решением проблемы двойной траты является принцип доказательства выполнения работы (POW) или подпись Накамото – лотерея, основанная на хэш-головоломке о правильном блоке транзакций. Криптографический характер этой хэш-лотереи выбирает одного случайного майнера, который производит блок. Сочетание дорогостоящего хеш-поиска, называемого майнингом, с вознаграждением, как и добавление сложной теории игр и вероятности предназначено для того, чтобы наставить майнеров на путь истинный. См. комикс.

Рисунок 3 – В принципе доказательства выполненной работы робот должен обработать множество плохих чисел, чтобы найти число-победитель вида 000000000374af72

Биткойн – это блестящее и элегантное решение, потому что он открывает нашему разуму возможность полностью распределенных финансовых приложений. Но принцип доказательства выполнения работы PoW сжигает энергию до ценности, которую может выдержать рынок, что выливается в ужасный налог на всю стоимость валюты (на момент написания статьи 4% на Биткойн и 11% на Ethereum - весьма большой!). И так как блокчейн Биткойна базируется на комиссиях, комиссии будут сильно кусаться, делая Биткойн недоступным для большинства людей. Высокие вознаграждения и растущая цена также привели к использованию эффекта масштаба в майнинге, что неизбежно приводит к объединению майнеров. Несмотря на то, что сама система спокойно продолжает работу, негативным последствием цензуроустойчивой концепции является то, что власть цензуры сейчас сосредоточена в руках около десятка предприятий, причем большинство из них находятся в одной стране, которая отнюдь не славится тем, что сопротивляется стремлению к цензуре.

Принцип доказательства владения долей

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

Так гласит теория. На практике же вышесказанное было подвержено критике за (1) возложение власти в руки тех, кто имеет наибольшую долю, а также (2) за проблему «нулевой ставки», которая возникает, когда ставка на альтернативную цепочку ничего не стоит, если она не выживает.

Простое доказательство доли, похоже, не работает. Давайте посмотрим, что сработает – проанализируем проблему.

Давайте посетим конференцию по централизации майнинга

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

И эти майнеры могут вступить в сговор. Пока они предпочли не делать этого или, по крайней мере, не делать это открыто.Так как эта ситуация исторически не имеет доказательства достоверности, возможно, вознаграждение и этические принципы помогут поддержать систему?

Только вознаграждение и моральные принципы удерживают майнеров от вступления в сговор: это как в том случае, когда майнеры откатили случайную ошибку ввода данных (“эффект толстого пальца”), когда трейдер случайно отправил в качестве комиссии Биткойны вместо Сатоши, поэтому моральные принципы играют здесь определенную роль. С другой стороны, некоторые майнеры добывали пустые блоки, даже в случае очереди ожидающих транзакций или переполнения памяти пула (mempool).

Не только современные объединение и сотрудничество майнеров были непредвиденными, но и концепция сети Биткойн была намеренно сфокусирована на альтернативном видении. Является ли честность майнеров перспективой для устойчивого развития? Честность - это фактор, который не доказал свою надежность исторически, например, в банковском деле, поэтому, возможно, нам следует продолжать укреплять моральные принципы и вознаграждения блокчейна?

Что, если мы начнем работать в обратном направлении и примем тот факт, что майнеры могут объединяться? И что мы знаем, кто они? Или, что еще более спорно: что майнеры должны быть объединены и их личности должны быть установлены?

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

Принцип делегированного доказательства владения долей – как управлять генералами

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

Рисунок 4. Производитель подготавливает блок

проверить набор
добавить награду производителю блока
внести в каталог каждое входящее сообщение
акт от каждого (внутреннее состояние)
проверить набор / нет двойной траты
распределить подписанный набор

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

Производитель блоков (майнер) выбирается в качестве принимающего решения лица для предотвращения двойной траты в одном блоке. См. рисунок 4. Каждый произведенный блок вознаграждается новой валютой (здесь без изменений).
Остальные производители блоков избираются и по очереди участвуют в раунде блоков, создавая таким образом конкурентный рынок в рамках раунда, обеспечивая общую надежность системы и вынося решение по поводу форков. См. рисунок 5.
Блокчейн проводит среди сообщества открытое голосование для управления производителями, в котором каждый участник может голосовать согласно доказательству владения долей. Производители блоков выбираются и отстраняются от работы одинаково – с помощью аукциона на следующий раунд. См. рисунок 6.

Рисунок 5 – Раунд с 7 генералами, решающими задачу 7 производителей

Затем сообществу требуется управлять своей цепью:

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

Политическая экономика?

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

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

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

Точная модель этого механизма – сберегательный счет, количество производителей блоков, размер блока, продолжительность раунда, ответы на вопросы “что произойдет, если… ?” – очевидно, глубокий и интересный вопрос. Но сегодня мы не будем говорить об этом.

Как это работает?

Работа DPOS была продемонстрирована, по крайней мере, в двух крупных система: Bitshares и Steem, и конечно же, будет использоваться и в EOS. Также он был выбран для Tezos, PeerPlays и Ark.io.

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

Принцип доказательства владения долей недостаточно эффективен из-за проблемы “нулевой ставки” (nothing at stake), но это имеет значение только когда на кону стоит прямой вопрос о блоке. Делегирование решает эту проблему – в DPOS ставка нужна для голосования за производителей, в то время как блок обрабатывается прямым производителем. Разделение за счет делегирования решает проблему “нулевой ставки”.
Существует возможность того, что производители блоков будут недостойно себя вести – они могут подвергать транзакции цензуре. Но на самом деле эту проблему можно превратить в преимущество, потому как производители, ведущие себя недостойно, могут быть отстранены – в этом и заключается суть делегирования. В отличие от нынешней недобросовестности сети Биткойн в плане месяца майнинга пустых блоков, DPOS работает намного лучше, потому что в нем предусмотрен механизм наказания.
Существует возможность вступления в сговор. Конечно, сговор возможен и в других цепях, что иллюстрирует представленная выше картинка. Вопрос в том, какая система будет функционировать лучше в случае сговора, и пока что наши деньги идут на организованное управление из-за наличия наказания – заинтересованности в игре.
Самоорганизованный или неуправляемый механизм чистого PoW означает, что майнеры не могут быть наказаны, даже если они решили осуществить легендарную атаку 51%. В DPOS как только всплывает угроза сговора, можно настроить правила управления, чтобы с ней справиться – будь то 51% или 1%.
Приверженец Биткойна заметит, что добавив уровень управления, мы нарушили “не требующий доверия” (trustless) характер блокчейна. Это не так, потому что ненужность доверия основывается на заблуждениях:

Заблуждение, что в других цепях отсутствует уровень управления. Фактически уровни управления существуют, но они неформальны, отрицаются, а также непостоянны или нечестны. По сути, мы заменяем самоорганизованное управление (анархию? захват власти?) на оформленное, конституционное, официальное и прозрачное управление. Вопрос заключается не в том, добавляет ли DPOS управление, а является ли управление в явной форме эффективнее, чем скрытая интрига.
Заблуждение, что концепция Биткойна означает, что нам не нужно доверять майнерам. Вспомним о проблеме пустых блоков: теперь мы вынуждены доверять майнерам производить полные блоки для сообщества, и они этого не делают, что демонстрирует пробел между математической природой блокчейна и человеческой природой «доверия». Блокчейн с принципом принятия консенсуса PoW устраняет некоторую часть доверия, но не полностью, и в этом случае он разрушает возможность доверия, когда оно необходимо.

DPOS обладает некоторыми преимуществами, которые также заслуживают внимания:

Поскольку он не использует хеш-майнинг, он намного дешевле, чем принцип доказательства выполнения работы. Фактически, мы освобождаем сообщество от налога на майнинг – на момент написания составляющий 4% в сети Биткойн и 11% в Ethereum.
И мы очищаем планету :-) DPOS рекомендуется для любого блокчейна с сердцем ♡
Добавив уровень формализованного управления, мы также подготовили почву для обновления программного обеспечения. То есть, у пользователей есть реальный механизм для голосования по поводу изменений, и у производителей блоков есть реальные голоса. Этот механизм в значительной степени ускоряет обсуждение форков и делает блокчейн гибким и динамичным – он может быстро развиваться в соответствии с меняющимися потребностями, так например, нерешенные принципом PoW кошмары DAO и дебаты о размере блока решаются в рамках DPOS.
Формализованное управление также обеспечивает сообществу право голоса в своей цепи.
DPOS работает над тем, чтобы направить процесс принятия решений на высокопроизводительную и высокоэффективную платформу, обеспечивающую по-настоящему большую пропускную способность.
Давайте оставим обсуждение производительности для других статей, но стоит сказать, что согласно проведенным тестам производительность Bitshares в 1000 раз превысила производительность, которой способен достичь Биткойн в своей текущей форме. Такая производительность позволяет прощать ошибки.

Конечно же, для некоторых преимущества являются грехами, но всё это такие грехи, которые предприятия и частные лица могут понять и оценить.

Свежие новости в Телеграм: t.me/EOS_RU

Переведено @rusteemitblog

Оригинал поста: ЗДЕСЬ