December 12, 2017

A Primer to LFT (Loop Fault Tolerance) Consensus Algorithm

by 2infiniti

LFT is a proprietary high-performance consensus algorithm that supports Byzantine Fault Tolerance (BFT), it an an evolution of practical solutions to the Byzantine Generals Problem.

Byzantine Generals Problem

The Byzantine General’s problem is one of many in the field of agreement protocols that was described back in 1982 by Leslie Lamport. In this problem, a leader general and a group of other generals surround a castle, the only way to ensure victory is by coordinating a simultaneous attack.  Since they’re dispersed around the castle, they must send messages to relay the attack time. There is however, loyal and traitor generals, and there’s no way to find out.

Papers on solutions to this problem were dated as far as few decades ago, but recently popularized as solutions to blockchain consensus. In a blockchain, any transaction sent to a ledger (messages) must be verified, there are millions of nodes (generals) sending transactions to a network, some may contain malicious intentions, so how do we trust these messages?

Public Blockchain Solution

POW (Proof of Work), as name suggests, is a validation of work that happened and proving it correct. The idea is simple, prover presents the result of a computation which is difficult to compute but easy to verify, and by verifying the solution anyone can be sure that prover performed a certain amount of computational power to generate the result.

Bitcoin was the first to apply POW to a blockchain, the core of its application is to ensure that all nodes cannot create blocks at the same time, a node in the chain will continually assign arbitrary value and only when a target data condition is met, a block will be generated.

In this model, consensus abandons finality of traditional BFT design in exchange for permission-less (open admission) security model. This however has a vulnerability when malicious actor controls more than 50% of the hashpower known as 51% attack. Also the ever-expanding racks of GPUs, consuming ridiculous amounts of energy, performing complex calculation that has pretty much no value.

POS (Proof of Stake) was later proposed as an alternative to POW, with same intentions to provide consensus and prevent doublespend. In contrast to POW’s complicated cryptographical puzzles to validate and create new blocks, POS requires user to show ownership of X amount of tokens.

The creator of a new block is chosen randomly, depending on a validator’s respective age of the stake, blocks are then validated and minted. In typical POS networks, tokens are pre-allocated and non-minable, validators receive transaction fees as rewards. While the staking concept may be similar, internal operations are very different depending on the algorithms applied.

(This is a super overly simplified explanation of POS, the complexity is way beyond the scope of this article so I’ll stop here)

Dated but still interesting article by Vitalik, What Proof of Stake is and why it matters

These algorithms are commonly found in public blockchains, they prioritize on validity (in POW: Nonce, in POS: amount and age of stake). Let’s further investigate into BFT algorithms, a more practical approach to private chains.

Private Blockchain Solution

PBFT (Practical Byzantine Fault Tolerance)

Practical algorithm for state machine replication that tolerates Byzantine faults. The algorithm offers both liveness and safety provided at most (n-1)/3 out of a total of n replicas are simultaneously faulty. This means that clients eventually receive replies to their requests and those replies are correct according to linearizability. The algorithm works in asynchronous systems like the Internet and it incorporates important optimizations that enable it to perform efficiently.

So in simpler words, PBFT is a consensus algorithm to ensure all nodes participating in a distributed system can successfully negotiate when Byzantine nodes exist. The algorithm is a form of state machine replication, let’s first outline some fundamental properties

Asynchronous Network

Transactions within the network are asynchronous, steps occur at different times, it is impossible to achieve consensus in an async network with one bad node.

Sequential Consistency

The results of any execution is the same executed in some sequential order

Linearizability

Sequential consistency + respecting real-time order of events

Problem

In a BFT algorithm, we assume there will be Byzantine nodes, any “bad things” can happen, be it drop, delay, duplicate or re-order messages.

Goal

A linearizable replicated state machine (replication for fault prevention, not scalability)

The basic idea here is to get same messages from enough nodes to know that non-faulty nodes are in same state

*Assume 3f+1 nodes, with at most faults

*Assume signed messages

*Assume deterministic behavior

*Assume no systematic failures

f+1 nodes, one node must be non-faulty, ensuring correct answer

2f+1 nodes, a majority of nodes must be non-faulty, providing ‘quorum’

3f+1 nodes, a quorum must be available, even if f nodes are faulty

Solution
  1. A client sends a request to invoke a service operation to the primary
  2. The primary multicasts the request to the backups
  3. Replicas execute the request and send a reply to the client
  4. The client waits for f+1 replies from different replicas with the same result; this is the result of the operation.

In a normal case, the leader node run a 3-phase protocol to coordinate w replicas

As illustrated above, a leader(primary) node will sort client’s request sequence, write the result of the request and broadcast to other nodes.

For further studies please visit

Full Reading on Practical Byzantine Fault Tolerance

Topic of interest include properties of a quorum, view change algorithms, faulty primary node, details of each phase in pre-prepare, prepare and commit etc.

Public and Private Blockchain Solution

Tendermint (DPOS + PBFT)

Tendermint is a consensus algorithm based on the PBFT algorithm, to better fit both public and private blockchains, w DPOS concept added. Participants in the protocol are called validators (delegates), who take turn proposing blocks of transactions and voting on them. When a block fail to be committed, protocol moves to the next round, and a new validator gets to propose a block for that new height. Two stages of voting are required to successfully commit a block (pre-vote and pre-commit). A block is committed when more than 2/3 of validators pre-commit for the same block in the same round (they call this a polka, like polka dance), every pre-commit must be justified by a polka in the same round. Wonder if the name polkadot has anything to do w this 😉

In Tendermint driven blockchains, validators don’t have the same ‘weight’ in the consensus protocol. So proportions of the total voting power may not uniformly distribute across individual validators.

To briefly summarize the difference, PBFT will vote for one node in a single vote, and accept the most valid votes. In Tendermint, vote will be based on stake and stakes are more important than the number votes.

During a vote, Tendermint uses a locking mechanism to freeze voting shares on the network and release them to prevent double voting problems and keep the network as a stakeholder.

Tendermint blocks can commit to finality in the order of 1 second, processing around 10,000 transactions per second for 250 byte transactions. It is a high-performance, scalable consensus algorithm for BFT applications.

Tendermint (technical) in a nutshell

Full Reading on Tendermint Consensus

Another excellent article comparing Tendermint BFT and EOS DPOS.

Finally, let’s get to LFT

LFT (Loop Fault Tolerance)

LFT is a continuation of Tendermint to improve BFT consensus algorithms, it is currently what ICON uses as its consensus algorithm.

Do note that ICON is an interchain so that connecting blockchains will retain their consensus algorithms.

LFT reduces communication overhead by consolidating messages from the network

LFT aims to create a high performance consensus algorithm, consensus solely based on message relay among participants without intermediaries. In traidtional BFT design we have 3 steps from “pre-prepare”, “prepare” to “commit”, where LFT reduces to 2 steps, limited number of nodes for block generator broadcasts and remaining nodes participate in voting process only.

LFT is using a technique called “Spinning“, to simplify the overly complicated algorithm of selecting the primary node.

The figure above shows the a normal LFT consensus process, when the network is started, the verification nodes transmit the desired transaction to the reader nodes that have been determined. The primary node uses collected transactions to generate a block and sends it along w signature to all validation nodes.

When each validation node receives a block it verifies

  1. The current reader has generated a block
  2. Checks whether the height of the block and previous block hash are correct
  3. Verifies that data in the block is correct
  4. If 1-3 are correct, it generates Vote data and propagates it to all nodes in the network

This article introduces the basics of LFT and the origin and evolution of this algorithm, for now the technical whitepaper is only in Korean version, you can access it here

LFT : High-Performance Byzantine Fault Tolerance

 

TD;DR

LFT is a continuation to a series of evolution of Byzantine Fault Tolerance solutions, resulting in one of the most secure, high-performance and scalable blockchain consensus algorithms today.

63 thoughts on “A Primer to LFT (Loop Fault Tolerance) Consensus Algorithm”

  1. Anonymous says:

    interesting

  2. Anonymous says:

    amazing article!

  3. Pingback: click to go
  4. Pingback: click to continue
  5. reptilian says:

    Ꭲhese are actually wonderfᥙl ideas in about blogging.
    You have touched some pleasant factors һere.

    Any way keep up wrinting.

  6. Martinhet says:

    Hi All im newbie here. Good article! Thx! Thx!

  7. Janbrall says:

    Комплексные услуги Seo продвижения
    базы доменов
    Блог

  8. Donaldchuff says:

    Эффективное продвижение в интернете.
    купить базы для allsubmitter
    база для xrumer 2014
    ICQ 726166382

  9. Donaldchuff says:

    Эффективное продвижение в интернете.
    allsubmitter базы 2017 torrent
    лендинг пейдж
    ICQ 726166382

  10. Janbrall says:

    Комплексные услуги Seo продвижения
    реклама в соцсетях
    http://interpult.ru/ – Поисковое продвижение

  11. Pingback: follow this post
  12. Donaldchuff says:

    Эффективное продвижение в интернете.
    базы для allsubmitter
    http://bit.ly/2yvpbEy – продвижение сайтов в яндекс топ
    ICQ 726166382

  13. r-z-r_bal says:

    Приветствуем Вас, предлагаем Вам профессиональное продвижение Вашего сайта, подробнее о нас http://r-z-r.ru/rackrutka_cayta.html
    .

  14. WalterSwAmy says:

    Сегодня я очень хочу заработать 1000$, а это, что значит вы заработаете 10 000$. Не против? Сразу закреплю ссылку на торговую площадку: http://bit.ly/2HZeSta Конечно же мы будем торговать на реальном счету. Я буду онлайн работать вместе с вами и в первые же 30 минут вы увеличите любую вложенную сумму в 10 раз!

  15. Donaldchuff says:

    Эффективное продвижение в интернете.
    база allsubmitter 2017 скачать
    базы каталогов для allsubmitter
    ICQ 726166382

  16. What a stuff of un-ambiguity and preserveness of valuable
    familiarity regarding unexpected emotions.

  17. There is noticeably a bundle to know about this. I assume you made certain nice points in features also.

  18. Lincolnper says:

    http://bit.ly/2wv8usA
    Пояс Ems-trainer (990р)
    Ems-trainer – миостимулятор нового поколения. Отличается высокочастотными импульсами, бьющими точно в цель мышечных волокон и жировых клеток. Всего 23 минуты в день – и ваше тело как с обложки журнала.

  19. AndrewOrigh says:

    РАСПРОДАЖА БРЕНДОВЫХ ЧАСОВ. СКИДКА ДО 50% НА ВЕСЬ КАТАЛОГ! НАЖМИТЕ НА ССЫЛКУ, ЧТОБЫ УЗНАТЬ О НИХ ПОДРОБНЕЕ http://bit.ly/2H01Jk8
    купить механические часы
    Прямые поставки с заводов производителя

    =Good=

  20. Your site is so fantastic. I’m going to come back here again.

  21. Гепатит основная группа препаратов для лечения

    http://gepatitu-c.net/page/gepatit-osnovnaya-gruppa-preparatov-dlya-lecheniya/

    .

  22. Pingback: as reported here
  23. Pingback: visit the source
  24. Pingback: article source
  25. Pingback: visit the source
  26. Pingback: visit the source
  27. Pingback: visit web page
  28. AndrewOrigh says:

    РАСПРОДАЖА БРЕНДОВЫХ ЧАСОВ. СКИДКА ДО 50% НА ВЕСЬ КАТАЛОГ! НАЖМИТЕ НА ССЫЛКУ, ЧТОБЫ УЗНАТЬ О НИХ ПОДРОБНЕЕ http://bit.ly/2H01Jk8
    магазин брендовых часов
    Доставка по стране 7 – 14 дней с момента заказа

    =Good=

  29. Pingback: click at this page
  30. Michaeldreno says:

    http://bit.ly/2ruxPho
    Nokia 6700 и часы Rolex в подарок
    Культовый телефон от компании Nokia. Уникальный дизайн, поддержка двух сим-карт, и, конечно же, противоударный корпус из нержавеющей стали.
    Более 100 миллионов продаж по всему миру!

  31. Pingback: read article
  32. AndrewOrigh says:

    РАСПРОДАЖА БРЕНДОВЫХ ЧАСОВ. СКИДКА ДО 50% НА ВЕСЬ КАТАЛОГ! НАЖМИТЕ НА ССЫЛКУ, ЧТОБЫ УЗНАТЬ О НИХ ПОДРОБНЕЕ http://bit.ly/2H01Jk8
    брендовые часы мужские
    Скидка до 50%

    =Good=

  33. This site is absolutely fabulous!

  34. Davidtaure says:

    http://bit.ly/2I3GhhE
    Торнадо – ручной культиватор
    Уникальный ручной инструмент для сада и огорода. Многофункционален, абсолютно безопасен и прост в использовании. Вдобавок, при работе с ним полностью отсутствует нагрузка на позвоночник и укрепляются мышцы спины!

  35. Reggie Prey says:

    I can’t believe how great this site is. You keep up the good work. That’s my advice pal.

  36. Georgeviopy says:

    http://bit.ly/2IdcinA Щетка для удаления шерсти FUR WIZARD и перчатка для расчёсывания шерсти в подарок
    Щетка Fur Wizard – это компактный прибор для сбора шерсти, комочков пуха и волосков. Поверхность ролика покрыта материалом с большим количеством мелких щетинок, которые цепляют все загрязнения и втягивают их в специальный контейнер.
    Fur Wizard очищает любые поверхности одним движением!

Leave a Reply

Your email address will not be published.