Кратко об алгоритмах консенсуса

README.md

pBFT = Practical Byzantine Fault Tolerant

• Требуется n = 3f + 1 узлов, чтобы противостоять сговору и злонамеренным действиям f участников.
• 1999 Barbara Liskov et al.
• Для достижения консенсуса участники обмениваются сообщениями в три этапа.
  • на двух этапах каждый участник отправляет сообщения всем остальным. Каждое из них нужно отдельно подписать.
    • для консенсуса между 7 участниками нужно отправить 71 сообщение
    • для консенсуса между 10 участниками нужно отправить 142 сообщения
• Не масштабируется из-за того, что необходимо отправлять квадратичное (от числа участников) количество сообщений.

PoA = Proof of Authority

• Byzantine fault, "но есть ньюансы"
• Достаточно подписи одного Authority, чтобы выпустить блок.
  • Можно настроить, чтобы было больше.
• Любой Authority в любой момент времени может выпустить новый блок.
• Чтобы не было злоупотреблений, вводятся ограничения:
  • В цепочке из N/2 блоков, не может быть двух и более блоков, подписанных одним и тем же участником. (N = число Authority)
  • Чтобы уменьшить вероятность форков, участники должны подождать случайное количество миллисекунд перед выпуском блока. Если кто-то злоупотребляет правом выпускать блоки, его банят.
• Можно делать много Authority, количество сообщейни растёт линейно.

PoET = Proof of Elapsed Time

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

Raft = Reliable, Replicated, Redundant, And Fault-Tolerant

• Crash Fault Tolerant
  • как и любой CFT, требует n = 2f + 1 узлов, чтобы выдерживать f одновеременно вышедших из строя узлов.
• Современная замена очень сложного Paxos
  • Paxos придумал Leslie Lamport в 1989
  • Raft придумали в 2014
• Используется в etcd
• Участники выбирают лидера, который в течение следующего раунда будет решать какие блоки выпускать.
  • Выбор лидера не предполагает защиты от манипуляций. Алгоритм работает только если все участники следуют протоколу.
  • Протокол гарантирует, что выбирается один лидер и что у всех участников единое представление о том, кто лидер сейчас.