Как стать автором
Обновить

Комментарии 14

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

Вот эта тема совсем не раскрыта. Как вы в итоге защитились от случая, когда фэйковый девайс шлет одно и то же сообщение всем, а не каждому уникальное?
Можно чуть подробнее про кейс который о котором вы спрашиваете?
Попробуем чуть подробнее описать валидацию сообщений. Каждая запись в журнале имеет открытый ключ участника, который эту запись добавил, контрольную сумму записи, и цифровую подпись, сгенерированную закрытым ключом для [запись + контрольная сумма предыдущей записи этого участника]. То есть у нас получается не цепочка блоков, а цепочки записей каждого из участников. Тогда добавление записи в журнал выглядит примерно так: участник определяет контрольную сумму которую добавил именно он сам, формирует цифровую подпись, отправляет запись и подпись лидеру, лидер валидирует цифровую подпись, добавляет в свой локальный журнал, и рассылает ее фоловерам, каждый фоловер также валидирует цифровую подпись и добавляет к себе в журнал. Если подпись оказывается невалидной – запись просто обрезается до нулевого размера. Таким образом – добавить запись от имени другого участника только узнав его закрытый ключ

да в мтс походу реально разрабы сидят без дела переизобретают велосипеды

не переживайте, наши разработчики все успевают)

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


2 фундаментальных проблемы:


  1. RAFT работает, пока все пиры соблюдают протокол. Злоумышленник может перехватить генерацию и как минимум фильтровать поступающие данные.
  2. RAFT подразумевает, что перечень пиров фиксирован и известен заранее всем пирам. Управление перечнем пиров происходит через управление конфигурацией сети. Динамическое добавление/удаление пиров может привести к появлению форков.
1. RAFT работает, пока все пиры соблюдают протокол. Злоумышленник может перехватить генерацию и как минимум фильтровать поступающие данные.

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

2.RAFT подразумевает, что перечень пиров фиксирован и известен заранее всем пирам. Управление перечнем пиров происходит через управление конфигурацией сети. Динамическое добавление/удаление пиров может привести к появлению форков.

Как у нас реализовано добавление в кластер – чтобы новому участнику подключиться к кластеру нужно знать адрес хотя-бы одного действующего участника кластера, подключившись к нему, новичок сообщает свой адрес и получает список адресов всех активных участников, далее он повторяет данный шаг для всего только что полученного списка участников (причем на каждом шаге список может дополняться), до тех пор пока в списке не останется ни одного участника, с которым не было обмена адресами (все это происходит параллельно). Таким образом весь кластер достаточно быстро “узнает” адрес нового участника, а новый участник “узнает” адреса всех активных участников кластера. Как мы “выкидываем” из кластера “offline” участников – кроме адреса участника, мы также храним дату\время последней успешной коммуникации с ним, и если коммуникации не было слишком долго, мы с некоторый периодичностью начинаем отправлять ему PING-запросы, и если коммуникации не было совсем очень долго – просто удаляем такого участника из списка. Таким образом, если в качестве кванта времени для RAFT считать интервал между Heartbeat-ми (а у нас это секунды), то условие, что перечень пиров фиксирован и известен заранее всем пирам – вполне себе выполняется.
  1. И что мешает злоумышленнику запустить 10 пиров для лидеров? 100 пиров? 1000? А учитывая IPv6 это будет физически одна машина, но с несколькими адресами. Проблема не в том, что лидером может стать злоумышленник. Проблема в том, что кто угодно в любой момент может провести перевыбор лидера и стать этим лидером.
  2. В такой схеме даже простой сбой сети может привести к форку, не говоря уже о злонамеренных атаках. В идеале список пиров синхронизируется средствами RAFT, чтобы все пиры в каждый момент времени оперировали строго одним и тем же списком пиров. Если не ошибаюсь, было видео от яндекса про RAFT (достаточно длинное видео с какого-то выступления), где ближе к концу упоминалась эта проблема и описывалось их решение.

Мы немного по разному смотрим на проблемы RAFT. Я говорю о них как о фундаментальных — их не обойти различного вида ухищрениями. Если мат.модель позволяет атаку — значит сеть уязвима. Усложнить жизнь злоумышленника — да, можно. Но не защититься от атак полностью.


Повторюсь, RAFT — очень крутой алгоритм. Он простой, он понятный, он быстрый. Но RAFT далеко не идеален.
Он применим исключительно в закрытых сетях, где есть гарантии, что все соблюдают протокол взаимодействия. Фиксированный список пиров — это скорее особенность протокола, ее реально смягчить, но и полностью динамического списка пиров не получить.

«И что мешает злоумышленнику запустить 10 пиров для лидеров? 100 пиров? 1000?”

Вы описываете атаку “51%”, когда злоумышленник получает контроль над большей частью ресурсов распределенной системы, и абсолютной защиты от этой атаки нет в принципе, ей подвержены все открытые сети.

“А учитывая IPv6 это будет физически одна машина, но с несколькими адресами”.

Все не так просто: один пир – это один уникальный IPv6 адрес, принадлежащий диапазону адресов мобильного оператора, иначе мы запрещаем подключение к кластеру, то есть один пир – одна SIM-карта и одно мобильное устройство. Но еще раз, атака 51% — это лишь вопрос наличия достаточных ресурсов, а не особенность математической модели, данной атаке подвержены все открытые сети, абсолютной защиты от нее не существует.

“Проблема в том, что кто угодно в любой момент может провести перевыбор лидера и стать этим лидером”

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

Не совсем понятно о чем идет речь, “split-brain” или что-то еще? Если приведете конкретный кейс, с техническими деталями – будем признательны.

“Если мат.модель позволяет атаку — значит сеть уязвима. Усложнить жизнь злоумышленника — да, можно. Но не защититься от атак полностью”

Полностью согласны, более того, не существует абсолютно идеальной мат. модели, и соответственно абсолютно неуязвимой для атак сети. Успешная атака на любую существующую открытую сеть – вопрос приложенных усилий и средств, поэтому их защита строится на принципе, когда затрачиваемые ресурсы не окупаются полученной выгодой от атаки, что очевидно делает саму атаку бессмысленной.
 
На самом деле мы сейчас проводим некоторые исследования с целью расширения протокола RAFTдля защиты от “византийских” атак, и мы не одни движемся в этом направлении – поиск по ключевому слову “BFT Raft” выдает несколько достаточно интересных научных статей.
  1. Причем здесь "атака 51%"? Я о том, что достаточно 1 измененного пира как минимум для остановки сети (если говорить о классическом RAFT). Небольшие изменения протокола принципиально ничего не меняют (1 пир/10 пиров — разница не принципиальна). Да, для атаки надо, чтобы пир был синхронизирован с остальной сетью. Но это существенное ограничение? Его сложно обойти?
  2. Не сильно знаком с термином "split-brain". Я о том, что возможен форк истории блоков (если можно так сказать) даже сам по себе, а значит злоумышленник может ситуацию воспроизвести искусственно (и тогда можно говорить об "атаке 51%"), или воспользоваться моментом естественных проблем в сети (и тогда нужны гораздо меньшие усилия).
    В рамках RAFT ситуация с форками никак не решается — потому как в RAFT ветвлений не должно происходить в принципе.
    Если говорить о примере, то у меня очень мало данных о вашей сети. Тут возможно множество нюансов. Но если говорить о классическом RAFT — то там сложное управление списком пиров исключительно из-за того, что при пограничных ситуациях неаккуратное добавление нового пира может привести к форку: скажем пройдет выбор лидера с неполной историей. При этом пиры с полной историей могут выбрать своего лидера, в результате чего пойдет формирование уже двух историй. Это худший сценарий. Возможно, вся сеть просто остановится (на сколько помню, есть сценарии, когда при добавлении нового пира могут не пройти выборы нового лидера вообще). Понятное дело, что в общем случае этих проблем не будет — я говорю именно о пограничных условиях. Пограничные условия — это около 50% пиров активны, еще около 50% непонятно чем занимаются и добавляемый пир как раз меняет эти условные "51%/49%" на "51%/51%" (возможно как раз термин "split-brain" тут применим). К слову, при статичном списке пиров это невозможно в принципе — RAFT просто остановится, пока не соберет кворум в сети.

"BFT Raft" — это хорошо, но это пока на уровне идей? Есть рабочий алгоритм? Есть открытый блокчейн на нем? После всех изменений в "BFT Raft", сколько в нем от оригинального RAFT?


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


P.S. причина появления оригинального комментария в том, что в самой статье нет ни одного упоминания о проблемах RAFT. Причем, на мой взгляд, RAFT в принципе не подходит для указанного применения. Я хочу, чтобы у читателя складывалась полная картина об алгоритме.


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


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


P.P.S. на сколько вижу, R&D Центр МТС прекрасно понимает описанные проблемы. Но почему-то в статье их упустил… Как понимаю, не все ловушки удалось обойти...


В общем дальнейший диалог считаю бессмысленным. Я говорю, что RAFT тут не подходит, причем совершенно не подходит. Вы говорите, что "RAFT + подпорки — и все ОК". ОК, с вас полное описание всех "подпорок", чтобы можно было конструктивно обсудить квест по натягиванию совы на глобус (и можно ли после всего результат назвать RAFTом?).


Ну или как вариант — вы реально применили чистый RAFT в открытой сети… Хотя "местное голосование" — это ни разу не открытый враждебный мир… Но тогда хочется привести слова Пушкина:


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

Как нам кажется, Вы ссылаетесь на раздел «6 Cluster membership changes» вот этого описания протокола raft.github.io/raft.pdf. Мы не зря в самом первом ответе писали про таймауты и квант времени: в данной статье в качестве значения electionTimeout используются миллисекунды, а конфигурация узлов описана примерно так «нужно остановить все узлы, поправить конфигурацию и запустить, и лучше не делать это вручную, так как если запуститься в процессе конфигурации запуститься процедура выбора лидера (интервал которой напомним предполагается от 10-500 мс), то есть вероятность, что случится что-то страшное». Очевидно здесь предполагается, что время, необходимое для конфигурации кластера сопоставимо либо намного больше значения electionTimeout, действительно в этом случае возможен выбор лидера когда кластер находится в каком-то промежуточном состоянии. Мы же значение electionTimeout установили более 10 секунд (на порядки больше чем в статье!), а добавление единичного узла у нас выглядит так – одновременно всем узлам рассылается команда, которая: останавливает таймер election, добавляет новый узел в список узлов, запускает таймер election. Время выполнения этой команды –  примерно миллисекунды, ну либо десятки миллисекунд. То есть в нашем случае, время конфигурации кластера на несколько порядков(!) меньше значения electionTimeout, и вероятность инициации выбора лидера в процессе конфигурации стремится к нулю. Само собой мы многократно проверяли данный механизм и на стенде, и на «бою», то есть мониторили состояние кластера в течение всего процесса голосования пользователями на мобильных устройствах, и его корректная работоспособность полностью подтвердилась.
 
«В рамках RAFT ситуация с форками никак не решается — потому как в RAFT ветвлений не должно происходить в принципе»
 
Даже если обратиться к «классическому» алгоритму, это не совсем так, в том же документе выше вполне ясно описана процедура разрешения конфликтов в журнале (форков\ветвлений, назвать можно как угодно) «If an existing entry conflicts with a new one (same index but different terms), delete the existing entry and all that follow it (§5.3)» Само собой в рамках тестов нашей реализации мы не раз «соединяли» в один кластер множество узлов у которых журналы отличались начиная с определенного элемента или даже полностью. Вполне ожидаемо, лидер всегда выбирался из большинства узлов с одинаковым журналом, и успешно реплицировал его меньшинству, замещая их версии, соблюдая тем самым наше основное требование – у всех участников единая копия журнала, а возникновение кратковременных «форков» для нас не является критичным (кстати, такая известная «открытая» блокчейн-сеть как «Bitcoin» допускает «форки» и ситуация с ними никак не решается, позволяя тем самым успешно проводить такие атаки, как например «Double-spending», но тем не менее она все-таки «подходит»).
 
В любом случае спасибо за интересную дискуссию и предоставленную информацию, мы ее обязательно учтем.

Мы немного по разному смотрим на проблемы…
Вы говорите о том, что вероятность возникновения проблем ничтожно мала.
Для меня же сам факт наличия подобной вероятности является проблемой. Какая бы вероятность не была — если проблема теоретически возможна, то ее следует устранить. Законы Мерфи еще ни кто не отменял… А ручной старт распределенного сервиса после рассинхронизации — удовольствие крайне сомнительное даже в закрытых сетях… А уж в открытых, тем более если говорить о IoT устройствах...


Что касается форков…
Да, в классических блокчейнах форки — это норма жизни. Но там о них знают, там о них помнят, там их учитывают.


RAFT же допускает форки исключительно в неподтвержденной (незакоммиченной) части истории. Они решаются достаточно просто — "следуй за лидером и не парься".
При этом RAFT дает гарантию, что закомиченная запись не откатится никогда!


RAFT тем и крут (помимо прочего) — закомиченная часть не откатывается, закомиченным данным сервиса можно полностью доверять! Базы данных не зря зачастую именно RAFT используют! Атаки вида "double-spending" невозможны в принципе!


А Вы готовы дать подобную гарантию?

Молодцы, было интересно почитать. Вспомнился сериал Кремниевая долина)
А подскажите какие-нибудь материалы по теме распределённого реестра на мобильных устройствах?

Это открывает множество возможностей по использованию данной технологии на IoT-устройствах...
Можете привести несколько конкретных примеров?
«А подскажите какие-нибудь материалы по теме распределённого реестра на мобильных устройствах?»

Мы подобных материалов найти не смогли, так что будем рады любой информации.

«Это открывает множество возможностей по использованию данной технологии на IoT-устройствах…

Можете привести несколько конкретных примеров?»

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