# Mergeable aggregated signatures proposal

## Preliminary

Для упрощения разметки, я буду рассматривать eliptic curve group как аддитивную, т.е. использовать записи вида Sa = S1\*a1 + S2\*a2 + .. + Sn\*an. Это популярный вариант в околонаучных постах.
Пока на русском, потом переведу.

## Problem

Для масштабирования протоколов, т.е. при работе с большим кол-во подписей, требуется сжимать наборы подписей (для экономии места на диске, пропускной способности сети, времени на верификацию). Для этой цели служат multisugnatures (same message signed by all signers) и aggregated signatures (different messages), которые требуют места много меньше, чем конкатенация отдельных подписей.

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

Простой вариант состоит в том чтобы сложить (перемножить, при мультипликативном view) подписи. Однако, тут обычно возникает требование, чтобы сливаемые агрегаты не пересекались по сообщениям/подписчикам. Т.е. мы не можем просто так слить агрегаты вида {S1,S2} и {S2,S3}. Точная проблема мне пока неизвестна, но это упоминается в двух работах ([Handel](https://arxiv.org/pdf/1906.05132.pdf) и [Compact Multi-signatures for smaller blockchains](https://eprint.iacr.org/2018/483.pdf)). Это момент, который мне нужно будет прояснить.

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

Иными словами, в распределенной системе, хотелось бы уметь агрегировать подписи не по дереву (что просто), а по (направленному) графу.

## Насколько это полезно?

Рассмотрим такую конфигурацию. У нас есть n подписей, которые нужно сагрегировать. У нас будут два базовых варианта, n=100К и n=16К. 100К соответствуют случаю когда у нас 1млн аттестаций, но равномерно распределенным по 100К нодам, так что нам нужно агрегировать лишь 100К подписей (предполагаем, что каждая нода рассылает уже преагрегированные подписи).
Вариант 16К соответствует 16К валидаторам, раскиданным по 100К нодам, так что у нас примерно 14.5К нод, где есть хотя бы один валидатор. Для простоты считаем что у нас 16К подписей.

Допустим у нас есть две частично агрегированные подписи, которые содержат k подписей. Какова вероятность, что они пересекаются? По пародоксу дней рождений, вероятность примерно равна exp(-k^2/n), если k<<n. Считается примерно так, возьмем какую-то подпись из первого агргегата, вероятность что он *не* попадет во второй агрегат, равна (1-k/n), для двух подписей из первого агрегата, вероятность, что их нету во втором агрегате, соответственно будет примерно (1-k/n)^2, ну и т.о. для всех k из первого агрегата вероятность не пересечься со второым, будет (1-k/n)^k = exp(-k^2/n), подразумевая, что k<<n.

В случае n=16К, у нас вероятность 1/2, что два частичных агрегата размера k=105, пересекутся. Анлогично, для n=100К, два агрегата размером k=263 пересекутся также с вероятностью 1/2.

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

Мои приблизительные расчеты говорят, что если у нас есть около 30 агрегатов размера 350 для случая n=16К, то у нас примерно 1/2 найти пару непересекающихся.
Аналогично, это будет 850 для случая 100К.
Т.е. это примерные предельные размеры частичных агрегаций, в случае когда мы сливаем агрегации случайно, а не применяем tree overlay, типа как в Handel.

Т.е. такая агрегация будет содержать примерно 0.85% всех аттестаций для n=100К, и 2.2% для n=16К.

Получается, что у нас будет в районе 50-100 частичных агрегаций, которые пересекаются, а значит мы их не можем смержить стандартным алгоритмом. Если же мы берем как основу размер агрегаций в 105/263 подписей, то мы получаем цифры 150-400 агрегаций. Это примерно соответствует размеру пакетов в 100-400К, считая, что каждая агрегация будет содержать примерно 4 байта на подпись. Хотя тут возможно применение компрессированых битмасок.

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

## Aggregation of BLS signatures

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

Если мы говорим о слиянии двух агрегированных подписях, когда множества аттестеров пересекаются, то соответствующие коэффициенты складываются. Т.е. если у нас два агрегата S1+S2 и S2+S3, то при сложении мы получаем S1+2\*S2+S3. Т.е. агрегированная подпись содержит индивидуальные подписи не только лишь с коэффициентом 1 (если включена) или 0 (если не включена), а может включать любые целые числа.

По этой причине, Handel работает с частичной merge функцией, что вводит ограничени на протокол. Особенно это неприятно в случае с Byzantine сеттингом. Поэтому Handel вместе с агрегатом посылает индивидуальные подписи. И отсеивает подписи, которые он не умеет агрегировать.

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

## Bilinear Aggregate Signature

Есть другой вариант агрегации подписей (детали [тут](https://crypto.stanford.edu/~dabo/papers/aggsurvey.pdf
) либо [тут](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf
)), устойчивые к rougue key attack, при котором агегатная подпись формируется следующим образом:
Sa = S1\*a1 + S2\*a2 + .. + Sn\*an
где ai зависит от всех публичных ключей, ai = H(Pi, {P1,P2,..,Pn}).
Анaлогично формируется агрегированный ключ
Pa = P1\*a1 + P2\*a2 + .. + Pn\*an

Коэффициенты ai нелинейно зависят от всех публичных ключей, поэтому подпись не подделываема (при каких-то криптографическх допущениях, см [тут](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf)). При этом коэффициенты можно восстановить из известной информации (набора публичных ключей).

## Proposal

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

Поэтому относительно просто комбинировать подписи.

### Рекурсивная агрегация подписей

Допустим есть две агрегированные подписи Sa1 и Sa2, и агрегированные ключи Pa1 и Pa2.
Можно получить новый агрегат спользуя Bilinear Aggregation Signature, рассматривая Sa1 и Sa2 как обычные подписи.
Sb = Sa1\*b1 + Sa2\*b2
Pb = Pa1\*b1 + Sa2\*b2
где bi = H(Pai, {Pa1,Pa2})
При этом bi можно восстановить зная Pa1, Pa2, а их можно восстановить зная соответствующие публичные ключи, из которых они получены, посчитав соответствующие коэффициенты.

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

Так как для Bilinear Aggregation есть [доказательство](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf) неподделываемости, то иожно надеяться, что оно сработает и для такой рекурсивной схемы. По крайней мере, мы агрегируемые подписи выглядят как обычные BLS-стайл подписи (подпись и публичный ключ есть точки на эллиптической кривой). Но это неточно.

## Возможные проблемы

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

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

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

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

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

### Добавление битов случанойсти

vbuterin в [посте](https://ethresear.ch/t/fast-verification-of-multiple-bl) высказывает опасение, что при быстрой проверке набора BLS подписей путем агрегации их в единую подпись, злоумышленник может воспользоваться знанием коэффициентов и исказить подписи, так что проверка агрегатной подписи пройдет успешно. При этом отдельная проверка подписей выявит проблему. Для решения предлагается генерировать случайные ненулевые коэффициенты, тогда злоумышленник не сможет подобрать искажение подписей.

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

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

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

vbuterin в [том же самом посте](https://ethresear.ch/t/fast-verification-of-multiple-bl) указывает, что нежелательно объединять все подписи в одну единую, ибо это помешает accountability (затруднит детекцию slashing conditions).

Т.е. на практике, в конечном итоге должно быть несколько агрегатов подписей. Которые в совокупности достигают нужного покрытия. И их можно независимо верифицировать. Например, у нас есть набор из 100 компактных агрегаций по 1000 подписей, которые слабо пересекаются, и в совокупности покрывают допустим 50 тысяч подписей.
Также если у нас есть дерево/граф агрегаций, то в сообщение можно включать некоторые поддеревья/подграфы. Например, агрегировать только несколько нижних уровней.
Так как в p2p сети будет приходить большое кол-во избыточной информации от разных нод, то это можно использовать для усиления протокола.

### Дополнительные и секвентальные подписи

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

## Итого

Ограничение при слиянии агрегатов (когда они пересекаются по валидаторам), довольно неудобно в распределенной системе, особенно при наличии сбойных нод (которые могут присылать произвольные агрегаты, например с высоким риском получить пересечение). Handel, чтобы избежать этого строит overlay tree structure, в котором получается дерево слияний (а не граф), в дополнение пересылает индивидуальные подписи, а также отсеивает подписи при агрегации.
Для реализации более гибких подходов к сбору и рассылке аттестацией, хотелось бы иметь способ мерджить частичные агрегации, свободные от этой проблемы.
Описанный в данном тексте подход, позволяет надеяться, что такой способ возможен, хотя и не без проблем.

**NB** Я добавил выше расчет, который позволяет предположить, что на практике будет достаточно применить такую рекурсивную агрегацию один, максимум два раза, когда размеры частичных агрегатов достигли примерно sqrt(n). Таким образом, применение такой агрегации не несет особых рисков, но позволит упростить алгоритм, отказавшись от ограничений в виде overlay tree structure, etc. И одновременно позволит скомпрессировать трафик.

Предварительный список сцыл
[1] [A Survey of Two Signature Aggregation Techniques](https://crypto.stanford.edu/~dabo/papers/aggsurvey.pdf)
[2] [Aggregate and Verifiably Encrypted Signatures from Bilinear Maps](https://crypto.stanford.edu/~dabo/pubs/papers/aggreg.pdf)
[3][Fast verification of multiple BLS signatures](https://ethresear.ch/t/fast-verification-of-multiple-bls-signatures/5407)
[4][Handel](https://arxiv.org/pdf/1906.05132.pdf)
[5][Compact Multi-signatures for smaller blockchains](https://eprint.iacr.org/2018/483.pdf)