Сооснователь и идейный вдохновитель Эфириума, Виталик Бутерин, представил "Лиловую книгу" (Mauve Paper), описывающую перспективную версию Эфириума 2.0, которая выйдет под названием Casper. Точная дата релиза не определена, на данный момент он предполагается летом 2017 года.

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

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

Доказательство работы ( PoW) – механизм консенсуса, чаще всего использующийся в существующих системах. По мнению сторонников PoS, он требует колоссальных затрат электроэнергии для работы. Но эти оценки, как правило, безосновательно завышены. Сеть Биткойна – крупнейший блокчейн, использующий PoW, по косвенным подсчетам потребляет менее гигаватта, а достоверный расчет по имеющимся публичным данным невозможен. (В оригинальной статье Виталик ссылается на устаревший расчет Национального университета Ирландии, авторы которого изначально оперировали недостоверными данными - прим. ред. )

Статья предлагает решение этих проблем, основанное на комбинации механизма Распределения доли (PoS) и шардинга. Идея PoS не нова, она существует с 2011 года, однако новый алгоритм обладает значительным преимуществом, он устраняет недостатки предыдущих систем, и добавляет новые свойства, которые отсутствуют в PoW. 

Распределение доли можно представить как «виртуальный майнинг»: если в PoW участники за настоящие деньги покупают настоящие компьютеры, которые потребляют энергию, и стохастически производят блоки со скоростью, пропорциональной затратам, то в PoS они за настоящие деньги покупают виртуальные монеты внутри системы, затем протокол конвертирует эти монеты в виртуальные компьютеры, которые, в свою очередь, стохастически производят блоки, со скоростью, пропорциональной затратам – то же, что и первом случае, только без энергозатрат. Однако, такой метод вынуждает хранить монеты в кошельке, а не тратить их.

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

Поставленные цели:

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

  2. Время генерации блока – максимально короткое время, но без ущерба безопасности.

  3. Экономическая завершенность (Finality) – через определенное время после генерации блока должно возникнуть состояние, в котором большинство валидаторов высказывают «полное согласие» с этим блоком. Это означает, что валидаторы, в историях которых этот блок отсутствует, потеряют свои ETH депозиты. Такое условие желательно, оно означает, что даже «сговор большинства» не сможет провести атаку 51%, не потеряв свой депозит; предполагается, что обычные валидаторы проводят консервативную стратегию в том, что касается принятия решений с высокой ценой, так что для честных валидаторов риск очень мал.

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

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

  6. Вычисляемое сопротивление цензуре – Даже если большинство валидаторов на всех шардах вступят в сговор для того, чтобы не допустить включения каких-либо транзакций в блок, протокол должен предотвращать такие ситуации. Такая функция в облегченной форме существует и в Эфириуме 1.0: «Сопротивление цензуре посредством остановки», но можно сделать механизм существенно сильнее, добавив понятие гарантированного расписания и гарантированных сообщений между разными шардами.

Далее описан алгоритм, который решает задачи (1) и (2), второй алгоритм решает (3), третий алгоритм частично решает (4) и (5): лимит, примерно пропорциональный квадрату вычислительной мощности узла в (4); 24 часовая задержка для перекрестных сообщений между шардами, с возможностью создания более быстрого обмена сообщениями в виде надстройки, с помощью депозитов двойного назначения в (5). Окончательное решение (4) и (5), и решение (6) оставлено за рамками этой работы, и будет решаться в Эфириуме 2.1 и 3.0.

Константы и целевые параметры

Заданы параметры

  • BLOCK_TIME: 4 секунды (задача-минимум)
  • SKIP_TIME: 8 секунд (задача-минимум)
  • EPOCH_LENGTH: 10800 (то есть 12 часов при благоприятных обстоятельствах)
  • ASYNC_DELAY: 10800 (то есть 12 часов при благоприятных обстоятельствах)
  • CASPER_ADDRESS: 255
  • WITHDRAWAL_DELAY: 10000000, 4 месяца (срок, на который замораживается валидаторский депозит)
  • GENESIS_TIME: будущая временная метка, означающая старт блокчейна, например 1500000000
  • REWARD_COEFFICIENT: 3 / 1000000000 (коэффициент вознаграждения)
  • MIN_DEPOSIT_SIZE: 32 ETH
  • MAX_DEPOSIT_SIZE: 131072 ETH
  • V_LOSS_MAXGROWTH_FACTOR: 32
  • FINALITY_REWARD_COEFFICIENT:0,6/ 1000000000
  • MIN_BET_COEFF: 0.25
  • NUM_SHARDS: 80 (число шардов)
  • VALIDATORS_PER_SHARD: 120 (количество валидаторов на 1 шард)

Минимальный протокол – Распределение доли (PoS)

Замечание: В этой и следующей частях предполагается, что читатель знаком с Эфириумом 1.0

Создадим минимальный алгоритм PoS следующим образом (Завершение транзакций, пункт (6) и шардинг не включены). Определяем, что по адресу CASPER_ADDRESS существует «контракт Casper», в котором содержится история набора валидаторов. Обращение к контракту является частью валидации заголовка блока, кроме того контракт включен в нулевой блок (Genesis Block), а не добавлен через транзакцию. Набор валидаторов определяется в нулевом блоке, а впоследствии может модифицироваться следующими функциями:

  • deposit(validation_code:str, randao:bytes32, withdrawal_address:address): принимает депозит с определенной суммой ETH. Отправитель назначает «validation_code» (EVM байтовый код, он служит публичным ключом, который используется при верификации блоков и других консенсусных сообщений), обязательство randao (32-байтный хэш, используемый для определения валидатора; см ниже) и адрес для вывода депозита в будущем. Отметим, что вывод происходит на адрес, который условно разблокирует средства, например, для двойного использования страхового депозита. Если параметры принимаются, функция добавляет валидатора к набору валидаторов через одну эпоху от текущей (если вызов deposit произошел в эпоху n, валидатор будет добавлен в набор в эпоху n+2, здесь эпоха – период EPOCH_LENGTH блоков). Хэш кода валидации (vhash) может служить идентификационным номером валидатора.

  • startWithdrawal(vchash:bytes32, sig:str): начинает процесс вывода депозита. Требует подписи, удовлетворяющей коду валидации данного валидатора. После проверки подписи функция удаляет валидатора из списка, через одну эпоху от текущей. Отметим, что эта функция не выводит ETH.

  • withdraw(vchash) – выводит депозит ETH + вознаграждение - штрафы на адрес вывода, после того, как валидатор исключен из набора функцией startWithdrawal, через минимум WITHDRAWAL_DELAY.

Формально, код валидации – программа, на входе которой хэш заголовка блока + подпись; она возвращает 1, если подпись подлинная, и 0, если нет. Такой механизм служит для того, чтобы валидаторы не были ограничены алгоритмом одной подписи, а использовали код валидации, который верифицирует подписи от множественных приватных ключей, вместо одного, с использованием подписей Лэмпорта, если нужен механизм защиты от квантового компьютера. Программа оформлена как «черный ящик» с новым кодом CALL_BLACKBOX, ее выполнение не зависит от внешнего состояния; это важно, чтобы избежать возможных хитростей, например, если валидатор запускает код валидации, который возвращает 1 при обстоятельствах, благоприятных для валидатора, и 0, если нет (т. н. Dunkle inclusion).

Величина randao в функции deposit есть результат вычисления длинной цепочки хэшей: sha3(sha3(sha3(.....(sha3(x))...))) для некоторого секретного x. Величина randao, полученная от каждого валидатора, хранится в коде Casper.

Контракт Casper также содержит переменную globalRandao, которая инициализируется как 0. Функция getValidator(skips) возвращает код валидации валидатора, который должен генерировать следующий блок после заданного числа пропусков (skips): getValidator(0) возвращает первого валидатора (валидатор, который должен генерировать блок в порядке очереди), getValidator(1) возвращает второго валидатора (валидатор, который будет генерировать блок, если первый недоступен) и так далее. Каждый из этих валидаторов выбирается псевдослучайным образом из текущего набора активных валидаторов, причем случайность взвешивается размером начального депозита и выдается контрактом в globalRandao. Кроме подписи, корректный блок должен содержать прообраз записанного randao валидатора – владельца подписи; этот прообраз затем заменяет сохраненную величину randao, и в зашифрованном XOR-алгоритмом виде записывается в globalRandao контракта. Следовательно, каждый блок, который создает валидатор потребует «снятия» одного слоя с randao валидатора.

Каспер 2

Минимальный временной отрезок, после которого может быть создан новый блок определяется как: GENESIS_TIME + BLOCK_TIME * <block height> + SKIP_TIME * <полное число пропущенных валидаторов с момента генезиса>. На практике это означает, что после того, как блок опубликован, 0-skip валидатор может публиковать следующий блок после BLOCK_TIME секунд, 1-skip валидатор после BLOCK_TIME+SKIP_TIME секунд, и так далее.Если валидатор публикует блок слишком рано, другие валидаторы проигнорируют его до окончания периода, и только после этого обработают. (Этот механизм полностью описан здесь; асимметрия между коротким BLOCK_TIME и более продолжительным SKIP_TIME гарантирует, что среднее время генерации блока в нормальной ситуации останется коротким, и обеспечит стабильность при задержках в сети.

Если валидатор производит блок, который включается в сеть, он получает вознаграждение за блок, равное полному количеству ETH в активном наборе валидаторов во время данной эпохи, умноженное на REWARD_COEFFICIENT * BLOCK_TIME. Таким образом, REWARD_COEFFICIENT становится для валидатора «ожидаемым процентным доходом в секунду», при условии, что валидаторы всегда поступают правильно; умножив примерно на 32 миллиона, получаем годовую процентную ставку. Если валидатор производит блок, который не включается в сеть, то заголовок этого блока может быть включен в сеть в любое время в будущем (до момента, когда валидатор вызовет withdraw) в качестве «dunkle» с помощью функции Casper includeDunkle(header:str); при этом валидатор потеряет сумму равную вознаграждению за блок. Следовательно, валидатор должен генерировать блок только если он более чем на 50% уверен, что блок пройдет в цепочку, это отбивает желание подтверждать все цепочки разом. Общие суммы валидаторских депозитов, включающие вознаграждения и штрафы, записываются в состоянии контракта Casper.

Принимая размер набора валидаторов постоянным, мы легко можем определить правило выбора форка: считаем блоки, самая длинная цепочка побеждает. Однако, в случае, если набор валидаторов может увеличиваться и уменьшаться, это не работает, поскольку форк, поддерживаемый меньшинством, сможет начать производить блоки так же быстро, как и форк, поддерживаемый большинством. Следовательно, определяем правило выбора форка: считаем блоки, и присваиваем каждому блоку вес, равный вознаграждению за блок. Так как вознаграждение за блок пропорционально полной сумме ETH, активно участвующей в валидации, то это гарантирует, что цепочки с большим ETH весом будут иметь большее значение.

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

Алгоритм прост, и скорее всего, он подойдет для реализации PoS.

Экономическая завершенность (Finality)

Следующий шаг – реализация понятия экономической завершенности. В заголовке блока, в дополнение к указателю на хэш предыдущего блока, валидатор делает следующий запрос: какова вероятность того, что некий предыдущий блок FINALIZATION_TARGET завершен. Запрос оформляется в виде ставки: «я верю, что блок 0x5e81d…будет завершен, и я готов потерять V_LOSS во всех историях, где это ложь, при условии, что я заработаю V_GAIN во всех историях где это – истина». Валидатор выбирает параметр odds, а V_LOSS и V_GAIN вычисляются следующим образом (пусть total_validating_ether – полная сумма ETH в активном наборе валидаторов, MAX_REWARD – максимально допустимая награда за блок, а bet_coeff – коэффициент, который будет определен ниже)

  • BASE_REWARD = FINALITY_REWARD_COEFFICIENT * BLOCK_TIME * total_validating_ether
  • V_LOSS = BASE_REWARD * odds * bet_coeff
  • V_GAIN = BASE_REWARD * log(odds) * bet_coeff

Ставки завершения/финализации. Выигрыш и проигрыш

Каспер 3

FINALIZATION_TARGET: на блоке 1 равно 0. bet_coeff в момент блока генезиса задан как 1, а другая переменная cached_bet_coeff равна 0. Теперь, на каждом блоке задаем bet_coeff=-bet_coeff/FINALITY_REWARD_DECAY_FACTOR, а cached_bet_coeff=-cached_bet_coeff/FINALITY_REWARD_DECAY_FACTOR, причем bet_coeff не может быть ниже MIN_BET_COEFF (это гарантирует, что мотивация сделать ставку есть всегда). При производстве блока, валидатор получает BASE_REWARD * log(MAXODDS) * cached_bet_coeff, где MAXODDS – максимально возможный мультипликатор выигрыша, равный MAX_DEPOSIT_SIZE / BASE_REWARD. Цель такого механизма: когда блок завершен, валидаторы получают награду за него, как если бы они продолжали делать ставки с максимальным мультипликатором; это гарантирует что у валидаторов не будет мотива искусственно задерживать завершение для получения максимального дохода.

К огда контракт Casper определяет, что блок FINALIZATION_TARGET завершен ( т. е., получает информацию, что величина value-at-loss проходит некий порог), устанавливаем новый FINALIZATION_TARGET, равный текущему блоку, cached bet_coeff +=bet_coeff и bet_coeff сбрасывается на 1. Начиная со следующего блока, процесс завершения начинается снова для нового FINALIZATION_TARGET. Если цепочка раздваивается, то процесс завершения какое-то время идет на нескольких блоках одновременно, причем эти блоки могут даже оказаться на разной высоте; однако, учитывая консервативную стратегию валидаторов (ставка на блок с минимальным риском потери), мы ожидаем, что будет сделан выбор в пользу одного (аргументы те же, что и при минимальном Распределении доли).

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

Отметим, что мы не можем дать валидаторам полную свободу при выборе мультипликатора. Причина в том, что если есть два конкурирующих блока, B1 и B2 ( то есть, существуют две цепочки, в одной из которых FINALIZATION_TARGET присвоен B1, а в другой FINALIZATION_TARGET – B2) , и вокруг B1 начинает формироваться консенсус, то валидатор-злоумышленник может сделать высокую ставку на B2, перебить консенсус, и включить форк. Следовательно, мы ограничиваем мультипликатор, ограничивая V_LOSS по следующим правилам:

  • Пусть V_LOSS_EMA экспоненциальная средняя величина, заданная следующим образом. V_LOSS_EMA сначала равна награде за блок. В течение каждого блока, V_LOSS_EMA приравнивается к V_LOSS_EMA * (V_LOSS_MAXGROWTH_FACTOR - 1 - SKIPS) /( V_LOSS_MAXGROWTH_FACTOR + V_LOSS), где SKIPS равно числу пропусков, а V_LOSS – V_LOSS выбранная в этом блоке .
  • Установить V_LOSS_MAX равной V_LOSS_EMA * 1.5. Ограничить V_LOSS этой величиной.

Отметим, что это правило вводит предохранители: валидатор может рисковать 1,5*Х, только после того, как минимум две трети других валидаторов рискнули Х. Это аналогично шаблонам предварительное обязательство/обязательство в консенсусе, устойчивом к Византийскому сговору, когда валидатор ожидает, чтобы две трети других валидаторов сделали шаг, перед тем, как самому предпринять следующий шаг. Это дает некоторую безопасность, и гарантирует, что даже сговор большинства не сможет провести атаку (вынудить других валидаторов поместить ставки с высоким value-at-loss на блок, а затем толкнуть консенсус в другую сторону), без высоких расходов: фактически, такой сговор будет терять деньги быстрее, чем жертвы; это очень выгодная особенность, так как она гарантирует, что даже при условиях враждебного большинства, недобросовестные игроки будут «вымываться со временем».

Если блок включен как dunkle, запросы обрабатываются, и в результате могут появиться как штрафы, так и вознаграждения. Например, пусть на высоте 5000 существуют два блока – A1 и A2, и два блока – B1 и B2 (оба, с A1 в качестве предка) на высоте 5050, а валидатор генерирует блок C над B1, делая запрос к A1, тогда, если B2 включается в главную цепь, а B1 и C становятся dunkle, то C будет ошрафован за ставку на B1 против B2, но получит награду за «правильный» A1.

Однако предположим, что V_LOSS в C такова, что V_LOSS < V_LOSS_MAX если в цепь включен B1, но V_LOSS > V_LOSS_MAX если в цепь включен B2. Тогда, чтобы сохранить желаемые свойства value-at-loss, мы накладываем дополнительный штраф: валидатор наказывается на V_LOSS - V_LOSS_MAX даже если его ставка оказывается верной. Таким образом, эффективно раскладываем ставку размера V_LOSS в комбинацию (1) ставку с value-at-loss V_LOSS_MAX и (2) V_LOSS - V_LOSS_MAX, таким образом гарантируя, что эта избыточная ставка всего навсего сдвигает правило выбора форка на V_LOSS_MAX.

Это означает, что ставки, в некотором смысле, не являются «чистыми», поскольку ставка на блок может привести к штрафу, даже если блок завершен, но слишком много его потомков заканчиваются форком. Потеря чистоты в модели ставок считается приемлемым разменом на выигрыш в чистоте в правиле выбора форка value-at-loss.

Расчет и реализация стратегии

Расчет величины value-at-loss реализуется с помощью следующего алгоритма:

  • Следить за последним завершенным блоком. Если их несколько, возвращать ошибку, поскольку это говорит о том, что какое-то событие имело место в уже завершенном блоке, и для того, чтобы определить, что именно произошло, пользователь, видимо, должен использовать источники извне этой цепочки.
  • Следить за всеми блоками – кандидатами на завершение, которые являются «детьми» данного блока. Для каждого сохранять запись v a lue-at-loss.
  • Следить за самой длинной цепочкой от каждого кандидата на завершение, начиная с последнего завершенного блока.
  • «Полный вес» цепочки – value-at-loss ее кандидата на завершение плюс длина цепочки умноженная на награду за блок. Если в цепочке нет кандидата на завершение, тогда используется длина цепочки, умноженная на награду за блок. «Голова» – самый поздний блок в цепочке , обладающий максимальным полным весом.

Каспер 4

Простая стратегия валидатора: стараться создавать блоки только в голове, и делать ставки на завершение с value-at-loss в 80% от максимума.

Синхронизация легкого клиента

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

Каспер 5

  1. Пусть X – Последнее подтвержденное состояние (В начале цепи – блок генезиса)
  2. Запрос в сеть последней цели на завершение либо в той же эпохе, что и X, или в следующей эпохе (цель завершения – блок, в течение которого протокол считает предыдущую цель на завершение завершенной). Назовем самую последнюю цель на завершение Fn, а предыдущую цель Fp
  3. Запрос в сеть k блоков непосредственно перед Fn. Эти блоки сделают ставки, а весь их ETH пул будет поставлен на Fp.
  4. Аутентификация валидаторов, которые генерировали эти блоки посредством получения ветви запросов Меркла по отношению к уже подтвержденному состоянию, подтвердить их присутствие и позицию в наборе валидаторов, подтверждение предыдущего состояния первых k блоков.
  5. Установить X завершенному состоянию Fp.
  6. Повторять до достижения последнего завершенного блока. С этого момента использовать стратегию нахождения головы цепочки, описанную выше.

Шардинг

Рассмотрим переход от одного шарда к множеству. Построим модель следующим образом. Вместо единого блокчейна имеем множество взаимозависимых цепей, которые назовем «шарды». Существуют NUM_SHARDS шардов, в которых шард 0 работает как обычный PoS блокчейн, его состояние завершенности описано выше, однако работа шардов 1...NUM_SHARDS построена иначе. В начале каждой эпохи случайно выбираются VALIDATORS_PER_SHARD, они назначаются валидаторами этого шарда на следующую эпоху (валидаторы на эпоху n+1 назначаются в начале эпохи n). Функция getValidator(skips) определяет валидатора для шарда, она случайным образом выбирает его из списка (распределение равномерное, поскольку взвешивание по размеру депозита уже проведено во время выбора валидаторов). Запросы «завершенности» делаются в шарде 0 и рассматриваются только позле завершения следующей эпохи (запросы завершенности блоков в эпохе n+1 рассматриваются в шарде 0 в начале эпохи n+3).

Каспер 6

Если валидатор выбран для определенного шарда, он должен вызвать функцию контракта Casper registerForShard(vchash, shard, index, randao), в которой vchash – хэш код валидатора, определяемый функцией vhash=getShardValidator(shard, index), shard – ID шарда, index – величина 0 <= index < VALIDATORS_PER_SHARD

Эта функция генерирует ответ, который затем подтверждается на целевом шарде функцией

confirmReceipt(uint256 receiptId) чтобы подтвердить валидатора.

GetShardValidator – функция с логикой, аналогичной getValidator, но с другим механизмом случайного выбора.

Ставки на завершенность в перекрестных шардах (диагонали на картинке) записываются НЕ в заголовке блока, чтобы не перегружать легкие клиенты. Вместо этого валидатор должен создать транзакцию registerFinalityBets(bytes32[] hashes, bytes logodds) в любом своем блоке, в котором есть NUM_SHARDS хэшей и байтовый массив длиной NUM_SHARDS байт, где каждый байт представляет мультипликатор для соответствующего хэша блока.

Типичная работа валидатора заключается в поддержке «полного узла» для шарда 0 и сохранять истории всех шардов, на которые он будет назначен.

Когда валидатор назначается на шард,он должен скачать все состояние, используя дерево доказательств Меркла, и начать создавать блоки, в то же время он должен делать ставки на завершенность на всех шардах, так или иначе пересекающихся с его шардом, обращая внимание на (1) самую длинную цепочку на каждом шарде (2) ставки на завершенность от других валидаторов и (3) различные эвристические методы, которые могут помочь идентифицировать успешные 51% атаки внутри шарда (доказательства мошенничества) Отметим, что вероятность назначения на любой конкретный шард пропорциональна количеству ETH в депозите валидатора; следовательно, валидатору, у которого в два раза больше депозит, придется делать в два раза больше вычислений. Это свойство крайне желательно, поскольку оно увеличивает вероятность честного поведения, снижает мотив создания депозитных пулов, и реализует механизм, в котором обработка транзакций и сохранение блокчейна сами становятся формой «гибридного подтверждения работы».

Цель механизма отбора – обеспечить безопасность против атаки, даже если атакующие сосредотачивают до ~33-40% от размеров всех депозитов (меньше 50%, злоумышленник с 33 — 50% депозитов может «попытать счастья» на отдельном шарде), при том, что только несколько валидаторов реально подтверждают транзакции; поскольку отбор случайный, атакующие не смогут сконцентрировать всю свою ставку на отдельном шарде (критическая уязвимость на схемах шардинга в PoW). Даже если шард атакован, есть вторая линия обороны: если другие валидаторы обнаруживают признаки атаки, они могут отказаться делать запросы завершенности, которые должны следовать за форком атакующих, а вместо того подтверждать цепочку, которая создана честными узлами. Если злоумышленник, атакующий шард, пытается создать цепочку из неверных блоков, и это видят валидаторы других шардов, они обращают особое внимание на этот шард и его запросы завершенности в шарде 0.

Перекрестные коммуникации

Создаем опкод ETHLOG с двумя аргументами (to, value), который создает лог: в нем есть тема (topic) – пустая строка (именно пустая строка, а не 32 нулевых байта, традиционный лог сделать это не может); строка данных – 64 битная строка, содержит адрес назначения и величину. Создаем опкод GETLOG, который получает аргумент ID (определяется как block.number * 2**64 + txindex * 2**32 + logindex, где txindex – индекс транзакции, которая содержит лог в блоке, а logindex – индекс лога в ответе на транзакцию), и пытается получить лог, делает запись в состоянии, информирующую, что лог поглощен, и помещает данные лога в целевой массив. Если лог имеет пустую строку в topic, это переводит ETH получателю. Для того, чтобы лог был успешно получен, транзакция, которая вызывает этот опкод, должна ссылаться на его ID. Если v=0, мы допускаем, что величина r в подписи может быть переназначена для этой цели (Заметим, это значит, что это возможно только при EIP86 транзакциях, мы надеемся, что к моменту реализации транзакции EIP86 станут доминирующей формой).

Абстракция консенсуса – больше не единая цепь, она представляет собой набор цепей, c[0] ... c[NUM_SHARDS - 1]. Функция переноса состояния больше не stf(state, block) -> state'; теперь это stf(state_k, block, r_c[0] ... r_c[NUM_SHARDS - 1]) -> state_k' where r_c[i] is the set of receipts from chain i from more than ASYNC_DELAY blocks in the past.

Есть несколько способов «удовлетворить» эту абстракцию. Один подход: «каждый пользователь – полный узел»: все узлы сохраняют у себя состояние всех шардов, поддерживают цепи всех шардов, и таким образом, имеют информацию, достаточную для вычисления всех функций переноса состояния. Однако такой подход не масштабируем, поэтому он неинтересен.

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

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

В предлагаемой схеме есть ограничение масштабируемости, пропорциональное квадрату вычислительной мощности узла. Причины: (1) чтобы вычислить вознаграждение на шарде 0 требуется вычислительная мощность, пропорциональная количеству шардов. (2) Все клиенты должны быть легкими клиентами на всех шардах. Следовательно, если узлы имеют N мощности, тогда у нас есть O(N) шардов, и каждый шард имеет O(N) вычислительной мощности, а полная мощность O(N2). Чтобы преодолеть это ограничение нужен более сложный протокол шардинга, соединяющий запросы валидаторов в некое подобие древовидной структуры, но это находится за рамками нашего рассмотрения.

Задел на будущие доработки

  • Снизить ASYNC_DELAY так, чтобы перекрестные подтверждения могли быть получены сразу, как только блок на другом шарде будет завершен.
  • Снизить ASYNC_DELAY до времени, сравнимого с задержкой сети. Это даст возможность сделать перекрестные коммуникации между шардами более плавными, однако за это придется платить: реорганизация в одном шарде повлечет за собой реорганизацию в другом, для управления этими процессами нужны новые механизмы.
  • Создать понятие «гарантированные перекрестные вызовы». Здесь два компонента. Первый, возможность для пользователей покупать «будущий газ» на каком-нибудь шарде, обеспечивая страховку от перебоев в газе (вероятно, вызванными атаками спама в транзакциях). Второй: механизм, согласно которому, если из шарда i в шард j прошло сообщение, и если есть газ, то сообщение должно быть включено в блок как можно скорее, иначе валидаторы, которые не включили сообщение вовремя будут оштрафованы (причем размер штрафа будет быстро увеличиваться, до размеров депозита). Это гарантирует, что сообщение будет быстро обработано за время порядка < 10 блоков.
  • Создать версию без ограничения О(N2).
  • Более глубокий взгляд на теорию атомизированных транзакций (atomic transactions).