# **Распространение аттестаций по сети (WIP)**

# Задача

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

В общем случае, кол-во/суммарный размер сообщений может достигать O(n^2), что не есть масштабируемо. n - кол-во нод в сети, предполагаем византийское поведение нод, отсутствие компрессии аттестаций, а также, что кол-во аттестеров пропорционально кол-ву нод.

Поэтому, [specs/networking](https://github.com/ethereum/eth2.0-specs/blob/dev/specs/networking/libp2p-standardization.md#topics) задает, что аттестации сперва агрегируются в подсетях, а потом отправляются в beacon сеть.

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

Таким образом, есть две подзадачи:
* агрегация аттестаций в подсетях - O(k^2) worst case, где k - размер подсети, k << n
* распространение агрегированных аттестаций по всей сети, O(n/k\*p), p - кол-во подписчиков, может быть сопостовимо с n

# Вводные данные

NB Наши вводные данные (кол-во нод, валидаторов) немного отличаются от того, что обсуждается в [p2p/issues](https://github.com/ethresearch/p2p/issues/) и [Networking Requirements](https://notes.ethereum.org/QFLP8uBYSRiAbzpx1Rr9Rw#). Есть [issue](https://github.com/ethresearch/p2p/issues/13) на апдейт требований к сети, но там нет каментов.

Общее кол-во нод - 100К нод (валидаторы плюс обычные ноды). В p2p/issues обсуждается 20К обычных нод плюс какое-то кол-во валидаторских нод (300 валидаторов на шард).
Кол-во валидаторов - 1М. p2p/issues - 300К (300 на шард).

На каждый слот, выбирается несколько комитетов (от 1 до 16, в зависимости от кол-ва валидаторв), по одному на шард. В комитет входит от 128 до 4К валидаторов. Мы ориентируемся на 1000 валидаторов (всего 1М валидаторов, распределенных по 1024 шардам). Я так понял, что валидатор прикреплен к шарду на длительный период - 1 мес.
p2p/issues обсуждает ситуацию, что на каждый шард подписаны 200 обычных нод и 300 валидаторов. При этом, так как всего 20К обычных нод, то каждая обычная нода в среднем подписана на 10 шардов.

Основное требование - распространить аттестации за пол-слота (== 3 секунды).
Дополнительное требование - если не успели за пол-слота, то все равно надо распространять, чтобы включили в следующий блок.

Размер аттестации - примерно 300 байт.
Агрегированной аттестации - примерно 500 байт.
При этом криптографическая подпись занимает 96 байт.

Мы можем агрегировать аттестации, с целью уменьшения размера. Пока предполагаем, что агрегат содержит подписи для одного и того же сообщения. Кроме того, структура блока предполагает, что каждая подпись включена не более одного раза.
Также custody bit входит в подписывыемое сообщение. Это значит что строго говоря, в агрегированной подписи могут быть разные сообщения (отличающиеся битом).
Текущая структура блока подразмевает, что в него включены не более 128 агрегированных аттестаций.

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

# Простой вариант и его анализ/критика

Рассмотрим сперва идеалистический случай, который позволит понять и сформулировать проблемы реализации задачи на практике.

## Анализ агрегации по дереву (идеальный вариант)

Допустим у нас n нод (в подсети), и мы можем огранизовать их в бинарное дерево, тогда можно получить агрегацию за O(n) сообщений, O(log n) шагов, и суммарный объем сообщений O(n log n), если аттестации не компрессируются, а просто конкатенируются (размер агрегированной аттестации, пропорциональна кол-ву аттестаций в ней).
Например, может быть такая схема построения дерева: ноды нумеруются от 0 до n-1, на первой итерации нечетные ноды (с номером 2k+1) шлют сообщение ноде с номером 2k. На следующем шаге, ноды с номером 4k+2 шлют сообщения ноде с номером 4k и т.д. Суммарное кол-во аттестаций, пересылаемых на каждом шаге равно n/2, кол-во сообщений убывает геометрически, кол-во шагов - log n.

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

## Отличия идеальной схемы от реальности

### Структура p2p-сети/подсети

В сабнете присутствует несколько комитетов плюс обычные нод (не валидаторы). Сабнет есть оверлей в общей p2p сети, т.е. пересылка сообщений будет проходить через транзитные ноды.

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

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

Рост кол-ва нод (по сравнению с одним комитетом в подсети) не окажет существенного влияния на идеальную схему (увеличит задержку из-за ограничений связанности и транзитных нод), но может оказать существенное влияние в общем случае, когда затраты устремляются к O(n^2) - в этом случае, объединение 8 шардов в подсеть может потенциально привести к росту издержек в 64 раза.

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

### Византийские сбои

Агрегация по дереву совершенно неустойчива к сбоям нод, а тем более к византийским сбоям. По видимому, в суровом византийском случае неизбежен рост затрат до O(n^2) - придется посылать индивидуальные аттестации всем нодам.

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

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

### Ограничение компрессии аттестаций

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

В разных комитетах будут подписываться разные сообщения, кроме того, даже в рамках одного комитета возможно несколько разных вариантов сообщений (view аттестеров на текущее состояние блока и/или шарда).

Это вносит ограничения на возможности компрессии. Т.е. в общем случае, агрегированная аттестация не может иметь фиксированный размер, ибо зависит от кол-ва различных сообщений. Мы примерно ожидаем около 4 сообщений на шард, т.е. 4\*t сообщений в подсети, если там объединено t шардов.

Информацию об агрегированных аттестациях скорее всего придется пересылать с каждым сообщением. Хотя возможен вариант, когда attestation data агрегируется отдельно, а в агрегируемых аттестациях используется только hash(attestation.data).

### Агрегация по графу

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

Есть несколько вариантов решить эту проблему:
* Координация агрегации, например, агрегация по дереву. Затруднена в визайнтийском случае, но возможна (см Handel). В случае gossip протоколов, которые привлекательны отсутствием координации, и для которых характерна случайная передача, это может представлять существенную проблему.
* Можно откладывать агрегацию до момента, когда будет возможна "безопасная" агргеация (например, мы можем заполнить промежуточный уровень в дереве). Это вариант координации, но при этом неизбежно будет рост размера сообщений, либо рост кол-ва сообщений (запросы на заполнение дырок, координация между нодами, избыточные сообщения для увеличения возможностей безопасной агрегации).
* Позволить частичным агрегатам пересекаться по аттестерам. Например, можно агрегировать аттестации обычным образом (когда низка вероятность пересечения), но допускать пересекающиеся частичные агрегации на конечном этапе (когда их невозможно избежать без координации). Например, можно отправлять частичные агргеаты с какого-то размера, сразу на beacon_attestation, а пропоузеры уже соберут финальную агрегацию (формат блока допускает хранение нескольких частичных агрегатов, правда за счет роста общего их количества).
* Разновидностью предыдущего варианта является формат агрегированных аттестаций, который позволяет индивидуальным аттестациям входить в агргеат несколько раз. Т.е. вместо обычной бит маски (кодирующей либо 0 либо 1 вхождение индивидуальной аттестации), мы можем ввести два бита (0..3 вхождений), либо три бита (0..7 вхождений), etc. Есть два возражения против этой схемы: нужно менять формат агрегированной аттестации в блоке (не есть проблема, кроме необходимости согласования), и потенциальное снижение криптостойкости, в силу того, что злоумышленик может пытаться подделать подписи путем подбора комбинаций коэффициентов (можно снизить риск ограничением кол-ва вхождений индвидуальных аттестаций, либо ввести дополнительное хэширование в схему построения коэффициентов).

### Неполная агрегация

В силу требования устойчивости к византийским атакам, нам не обязательно выполнять полную агрегацию аттестаций. Т.е. начиная с какого-то размера агрегата, ноды могут посылать эти частичные агрегаты пропоузерам (beacon_attestation), чтобы они выполняли финальную агрегацию (например в составе блока, который они пропоузят). Это уменьшит задержку, а заодно включает в себя определенную устойчивость к сбоям, ибо разные ноды пошлют свои частичные агрегаты, и их будет сложнее перехватить/блокировать.
Так как результат все равно должен отправляться избыточно, то имеет смысл сэкономить 1-2 hop'а, посылая частичные агрегаты.

Итого, можно представить такие фазы агрегации:
1. начальный этап, когда частичные агрегаты небольшого размера. Это значит что они либо сливаются с высокой вероятностью, либо их можно просто конкатенировать, ибо это влечет небольшое увеличение размера сообщения. Например, для 10 агрегаций, мы можем сэкономить (10-1)\*96 = 864 байт, если сольем подписи в одну (и не сможем на другой ноде ее декомпозировать). При небольшом размере сообщения, это может слабо влиять на общую задержку, ибо есть заметный лейтенси даже на нулевого сообщение. Примерный порог - sqrt(n)/2, т.е. 10-15 аттестаций для случая 1000 аттестеров в комитете.
2. Промежуточный этап, когда агрегаты уже приличного размера, так что их надо компрессировать для экономии трафика. С другой стороны, так как уже прошло несколько раундов передачи информации, то есть больше возможностей слить аттестации "безопасным" образом (например по уровням в бинарном дереве).
3. Финальный этап. На этом этапе можно допустить, чтобы частичные агрегаты пересекались по аттестерам и кодировать их соответствующим образом. Этот этап могут выполнять пропоузеры при конструировании блока.

### Ограничения формата агрегированной аттестации в спецификации

Спецификация Eth 2.0 предполагает, что в агрегированной аттестации все подписывают одно и то же сообщение (может различаться custody bit, что формально приводит к тому, что на уровне криптографии, сообщения разные). При этом каждая подпись входит в агрегат не более одного раза. Общее кол-во аттестаций в блоке - не более 128.
Так как в слоте может быть 16 комитетов, в каждом из которых может быть несколько разных view - а значит и разных attestation.data, плюс в блок могут включаться аттестации из предыдущих слотов. Что означает, что суммарное кол-во различных сообщений может быть существенно больше 128. Пересекающиеся частичные агрегаты еще больше усугубят проблему, ибо их надо включать в блок как отдельные агрегированные аттестации.

Тут есть два варианта (они комбинируются):
* Увеличить максимальное кол-во аттестаций в блоке, 128 выглядит как явно недостаточно.
* Увеличить кол-во бит для кодирования нескольких вхождений аттестаций в агрегированную подпись. Т.е. чтобы некоторые аттестации могли входить 2-3 (возможно больше) раз. В принципе, можно просто записывать пересекающиеся агрегаты как отедельные агрегированные аттестации, но это менее эффективная схема (избыточное хранение сообщений).

Ранее предлагался вариант, агрегировать в одной агрегированной аттестации разные сообщения, но анализ показывает, что от этого нет особой пользы, в то же время, могут быть проблемы с аккаунтабилити. Т.е. на мой взгляд, оптимальный подход на данный момент - хранить одну агрегированную аттестацию на каждое возможное сообщений (attestation.data, без учета custody bit), но допустить вхождение индивидуальных подписей в агрегированную подпись более одного раза (для чего добавить соответствующих bitset или подобных схем). Можно ввести ограничения на общее кол-во вхождений аттестаций по отношению к кол-ву индивидуальных аттестаций, например, сумма всех коэффициентов должна быть не больше чем в два раза больше, чем кол-во индивидуальных аттестаций в агрегате, sum(c(i)) <= 2\*sum(c(i) > 0).

# Варианты решения отдельных проблем

Здесь я перечисляю отдельные опции, которые можно комбинировать при решении проблемы.

## Слияние агрегированных аттестаций

Индивидуальная аттестация состоит в основном из подписываемого сообщения (attestation.data) и криптографической подписи. Также туда явно или неявно входит айди аттестера и custody bit.

Я предполагаю, что разные сообщения (attestation.data) кодируются/агрегируются отдельно.
Т.е. агрегированная аттестация содержит одно сообщение (attestation.data), список аттестеров (обычно это bitset), список custody bits, а также агрегированная подпись.

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

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

### Конкатенация подписей

Конкатенация по размеру равна сумме размеров отдельных подписей. Тем не менее, она может быть разумна на первой фазе агрегации, когда агрегаты содержат мало индивидуальных аттестаций. Т.е. 10-15 конкатенированных подписей (порядка 1-1.5К) не перегрузят сообщения, но дадут больше простора в выборе вариантов слияния агрегаций на последующей фазе.
В случае если формат блока не позволяет, то мы можем быть вынуждены использовать конкатенацию подписей (аттестаций), если два частичных агргеата пересекаются по аттестерам.
В случае gossip протокола, без доп координации будет крайне сложно избежать появления пересекающихся частичных агрегатов на последней фазе. Поэтому, при некоординируемом слиянии (по графу), конкатенация скорее всего неизбежна, в случае ограничений формата блока.

### Простое суммирование подписей (точек на эллиптической кривой)

Позволить сэкономить в районе 96 байт на подпись.
Простое суммирование означает, что мы храним аттестеров в bitset'е, т.е. у нас коэффициент при подписи 0 или 1. А значит мы не можем таким образом сливать пересекающиеся по аттестерам агрегаты.

### Суммирование подписей с коэффициентами

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

## Протокол агрегации

Агрегация по дереву в чистом виде неустойчива к сбоям, поэтому тут возможен либо gossip протокол либо hybrid протокол агрегации (координированный gossip а ля Handel).

### gossip

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

### hybrid

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

## Участие нод в агрегации

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

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

Таким образом, один из вариантов - требовать от транзитных нод проверять подписи транзитных сообщений. Это можно делать с помощью [идеи](https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407), высказанной Виталиком Бутериным.

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

Ноды которые не входят в активный комитет в шарде (скорее всего он один), не являются источником исходных сообщений, тем не менее, так как через них проходят аттестации, они могут принимать участие в агрегации. В случае координированной агрегации по дереву (а ля Handel) в этом возможно нет особого смысла. Но при gossip протоколе, после первого раунда рассылки, они становятся обладателями примерной той же инфы (аттестаций), что и остальные ноды. Так что они могут принять участие в агрегации. В частности, чтобы затруднять Sybil-like атаки, деанонимизацию и проч.
Насколько это увеличит общие затраты на агрегацию - пока не понятно. Но расширение кол-ва участников агрегации потенциально может привести к удорожанию атак против системы.
Также некомитетные ноды могут участвовать в протоколах а-ля [Dandelion](https://github.com/ethresearch/p2p/issues/11).

## Вспомогательные сообщения

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

# **!!!111!!!ДАЛЬШЕ ЧИТАТЬ НЕ ОБЯЗАТЕЛЬНО!!!111!!!** WORK IN PROGRESS

# Анализ возможных проблем

## Коммуникации в subnet'е

Спека предполагает агрегацию аттестаций в subnet'ах, однако их кол-во отличается от кол-ва шардов и оно равно SHARD_SUBNET_COUNT (не удалось найти значение).
Это значит, что на один топик, соответствующий подсети, будут подписаны валидаторы из нескольких шард, а также какое-то кол-во обычных нод.
Т.е. кол-во нод, среди которых происходит агрегация, возрастает в несколько раз (1024/SHARD_SUBNET_COUNT и дополнительно ориентировочно в 1.5 раза из-за обычных нод).
Коммуникация в подсети может требовать вплоть до O(n^2) сообщений, хотя конечно мы стремимся к O(n) или O(n log n). Но из-за Византийских нод, может реально доходить до O(n^2), если византийские ноды будут блокировать сообщения. И тогда протокол должен "деградировать" до O(n^2) путем посылки сообщений всем в подсети. Но не факт, что это возможно в рамках pubsub.
С другой стороны, рост размера subnet'а усложняет Sybil attack (см соответстввующий [issue](https://github.com/ethresearch/p2p/issues/6)). Плюс, скорее всего, сделает сложнее блокировку потока сообщений визайнтийскими нодами, ибо чем больше subnet, тем также нужно больше визайнтийских нод, чтобы в нем доминировать.

## Агрегация по дереву vs графу

Протоколы агргеации в p2p бывают трех видов: tree-based, gossip-based и hybrid. Handel есть пример tree-based протокола, однако, фактически он "деградирует" до O(n^2) в случае большого кол-ва Византийских сбоев. Т.е. это hybrid протокол.

Проблема tree-based протоколов, в том, что нужно конструировать дерево. Т.е. чтобы был консенсус относительно участников. В принципе, такой консенсус есть - это комитет. Т.е. построить дерево можно. Однако, по идее ноды должны знать адреса друг друга, чтобы эффективно слать сообщения, как это предполагает агрегация по дереву.
Но тут у нас возникает противоречие с анонимностью. Т.е. даже если мы строим дерево, то все равно рассылка будет идти через топик pubsub. Что означает, что мы фактически теряем часть преимуществ от агрегации по дереву.

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

## Визайнтийское поведение нод

Sybil attack
Блокирование сообщений
Флуд
Кривые сообщения

# Анализ затрат ресурсов

## Сетевая коммуникация

Агрегация по дереву позволяет минимизировать затраты на коммуникацию. Т.е. аттестер шлет сообщения O(log n) нодам, суммарно получается O(n log n). Однако, Византийское поведение нод может потребовать O(n^2) коммуникации.
Gossip протоколы пытаются получить тоже O(n log n) с бОльшей, но ограниченной константой. Т.е. каждая нода шлет сообщения некоторому кол-ву пиров, чтобы они пересылают некоторому кол-ву пиров дальше. Если D - диаметр дерева, то чтобы распространить инфу по сети нужно в районе O(D*n*k) сообщений, если D = O(log n), то мы имеем примерно тот же O(n log n) но более высокая константа. Однако меньше затраты на координацию (не нужно строить дерево), и есть определенная отказоустойчивость.

Так как в subnet'е объединены несколько шардов/комитетов, а также обычные ноды, то затраты на коммуникацию могут расти. Тут есть несколько вариантов.

# Варианты решения проблемы

# Протоколы агрегации

## Tree-based
## Gossip
## Hybrid

# related links

[topic per shard comment](https://github.com/ethresearch/p2p/issues/9#issuecomment-464242807)