Topic: Экзотические алгоритмы консенсуса (Read 451 times)

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

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

Да там на самом деле много алгоритмов на BFT, даже сложно определить кто откуда содрал Поэтому 11-м пунктом просто указал Византийская отказоустойчивость, ибо это заслуживает отдельной статьи...которую я возможно опишу. А ровнять их под одну гребенку...самые знаменитые: Practical Byzantine Fault Tolerance (о чем Вы и написали) и Federated Byzantine Agreement частично (или полностью?) используют в Stellar и Ripple. Есть и другие, но там все сложно))

Если все хорошо с техническим английским, то можно почитать вот этот прекрасный тех документ - http://pmg.csail.mit.edu/papers/osdi99.pdf

Кстати к экзотическим алгоритмам консенсуса можно еще отнести Catchain. Это алгоритм консенсуса на котором должен был работать Дуровский тон. Я сейчас про него статью читал, пишут, что этот алгоритм построен на основе  practical Byzantine Fault Tolerance, но имеет ряд отличительных особенностей, поэтому его целесообразно отнести к самостоятельному классу алгоритмов

Большущее спасибо!🙏
Добавил в стартовый пост, по-свободе изучу детальнее + возможно напишу статью.

Ловите+


Сейчас практически все используют наработки с BFT, даже Сатоши четко описал, что его заинтересовала "Задача Византийских Генералов" и он включил этот принцип при разработке первой криптовалюты.
Я тоже практически не изучал IoTeX, но на первый взгляд похоже на стандартный DPoS с элементами Proof of Importance (PoI)...гибрид что-ли. Вообще интересно, однозначно изучу этот алгоритм, явно нечто прикольное))

Ловите плюс). Хоть я и не пользуюсь айотексом, но для коллекции алгоритмов консенсуса вполне годно. Я точно не знаю, но, по-моему, есть сейчас много разных версий BFT-консенсуса. Они немного отличаются друг от друга. Было бы здорово, если бы кто-нибудь на форуме взялся провести классификацию и привести примеры с подробным разбором того, чем разные версии этого консенсуса отличаются друг от друга. Боюсь ошибиться, но, насколько я знаю, на форуме нет пока такого топика. ТС упомянул о них лишь вскользь.  Можно было бы, кстати, и сравнить их по преимуществам, недостаткам и удобству для конкретного пользователя. Например, в плане делегирования токенов в стейк. Это бы сильно облегчило жизнь многим людям.

Немного дополню одним алгоритмом

Roll-DPoS - (A Randomized Delegated Proof of Stake) Рандомизированное делегированное доказательство доли

Кто использует
На сегодняшний день алгоритм консенсура Roll-DPoS уже больше года успешно используется проектом IoTeX для функционирования сети Интернета Доверенных Вещей.

Чтобы иметь быстрый и эффективный механизм консенсуса с мгновенным завершением блоков в контексте IoT, разработчики объединили концепции DPoS, PBFT и VRF (Verifiable Random Functions).

Как работает алгоритм

Roll-DPOS имеет четыре фазы: выбор кандидатов, формирование комитета, предложение блока и завершение блока.


Набор кандидатов
В этой фазе могут участвовать — т.е. голосовать за кандидатов комитета —все узлы сети. Чтобы мотивировать узлы на голосование, система удостоверяется, что делегаты разделяют полученные вознаграждения с голосующими. Кандидаты формируют группу минимум из 97 делегатов; в будущем это число будет увеличиваться, во избежание в дальнейшем централизации майнинг-мощностей. Выбранные кандидаты вносятся в одну эпоху, которая состоит из 47 итераций.

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

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

Завершение блока
В том же раунде все остальные узлы голосуют за/против блока-кандидата посредством PBFT. Если более 2/3 узлов комитета соглашаются о валидности блока-кандидата, он завершается и добавляется каждым в сети к блокчейну. После этого, процессы предложения и завершения блока осуществляются в следующем раунде; если текущая итерация заканчивается, перед осуществлением процессов предложения и завершения блока формируется другой случайный комитет.

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

Ну здесь больше философский вопрос "что это":

Источник - https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%B6%D0%B8%D0%BD%D0%B3

Как по мне, то это составляющая процесса майнинга...одна из частей алгоритма)

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

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

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

Упомянул :

https://ru.minter.wiki/Proof_of_Importance_(PoI)

Тестовую сеть запустили еще осенью 2014 года...можно сказать это "старый-новый" экзотический блокчейн. Лет ему много, но вот использует только NEM. Я думаю это связано с большой "заумностью" этого алгоритма, ведь даже не каждый криптан с первого раза поймет что такое форжинг, а именно его систему в конкретном алгоритме (сам башку поломал + на листике рисовал). А еще - это полная централизация сети китами - "крутой в итоге станет еще круче"

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

Окей, если заговорили о Directed Acyclic Graphs, то что еще можно добавить? Я думаю, что графы в чистом виде нельзя использовать, ведь будет не совсем эффективно (ну реально тот же dPoS круче). Но, если интегрировать DAG в уже рабочий блокчейн, или мутировать уже существующий механизм с помощью графа...то здесь будет "Бинго!". А все потому, что в алгоритме механизме нет блоков в чистом виде - это как вирус, которым можно заразить целый Мир! Транзакции в сети не должны "ждать своей очереди", их подтверждают ноды в автоматическом порядке, в этой сети нет майнеров. DAG исполняет идентичную с любым блокчейном функцию, вот только транзакции не стоят в цепочке (как обычно в блокчейне), а напоминают дерево с множеством ветвей - от больших к меньших и т.д.

Мне очень понравилась вот эта статья (англ) - https://hazelcast.com/glossary/directed-acyclic-graph/, все кратко и понятно - рекомендую.

P.S. Если я правильно понял информацию, то DAG в теперешнем виде создал Серхио Демьян Лернер еще в 2012 году, правда самостоятельно так и не смог реализовать свою идею не в одном крипто проекте. А если говорить о графах в чистом виде...то это математика, я хз даже когда из придумали и когда начали использовать

Да нет там по большему счету ничего нового, теории графов уже куча лет и в чем ее только не применяли https://www.sites.google.com/a/labore.ru/teoria-grafov-i-ee-primenenie/vvedenie-v-teoriu Можно сказать, что даже сам протокол TCP IP построен на основе данной теории, как и большинство современных блокчейнов. Тут больше маркетинговая уловка, взять не особо популярное и известное наименование, но запоминающееся и вынести его в название консенсуса. Есть некоторые в нем относительно уникальные аспекты, но вряд ли они натянут на что-то по настоящему значимое и революционное.

Waves конечно молодцы, что разработали собственный алгоритм, но разработали они его не с нуля, а на основе Proof of Stake.
А про Directed Acyclic Graphs видимо придется читать дополнительно, потому я совсем не понял принцип работы. Я насколько помню проект Vite тоже использует DAG, я за ними следил одно время, но даже тогда не вник что такое DAG

Ну не все и эксперементальные. Я хоть и не особо люблю Waves, но Иванов разработал довольно добротный Leased Proof of Stake (LPoS), на котором и работает проект 4 года. Proof of Importance (PoI) внедрили в  NEM еще в 2014 году...есть примеры нормальные + не все алгоритмы я успел описать (времени маловато). Но да, Вы правы, в большинстве случаев это непонятные алгоритмы, которые практически никто не использует.

P.S. Directed Acyclic Graphs хоть НЕ алгоритм, но этот механизм можно интегрировать практически в любой блокчейн...как по мне очень забавно

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

Тогда не странно, что на этом алгоритме работает мало проектов. А тот же Slimcoin имеет Trading Volume $4.34, то есть можно сказать, что проект и не существует толком.
Вообще такие экзотические алгоритмы консенсуса выглядят скорее как попытка не очень удачного эксперимента и видимо создавались именно как эксперементальные

Спасибо
Да, алгоритм не лишен "черных пятен":
Можно с уверенностью сказать, что прибыль получат только самые крупные холдеры, которые постоянно реинвестируют в определенную монету. Для "бедных" нет гарантий...и да, это проблема.
На самом деле, мало кто использует Proof-of-Burn как основной алгоритм распределенного механизма. Как описал в статье только 2 более-менее знаменитых проектах используют этот алгоритм: Slimcoin и Counterparty (XCP). Второй использует Proof-of-Burn как доп алгоритм, а первый...ну все можно посмотреть здесь - https://www.coingecko.com/en/coins/slimcoin. Т.е. он еще очень "жидкий".