EOS EOSIO DApp 개발 – '나도 백서 읽는다' 시리즈 4. Consensus Algorithm (BFT-DPOS)

내용을 이해하는데 정말 필요 없다고 생각하는 부분을 제외하곤 대부분 충실히 원문 내용을 반영하려고 노력했습니다. 내용 자체가 쉽지 않기 때문에 글 제일 뒷 부분에 참고할 만한 링크들을 추가했습니다.

Consensus Algorithm (BFT-DPOS)

EOS.IO software utilizes the only known decentralized consensus algorithm proven capable of meeting the performance requirements of applications on the blockchain, Delegated Proof of Stake (DPOS). Under this algorithm, those who hold tokens on a blockchain adopting the EOS.IO software may select block producers through a continuous approval voting system. Anyone may choose to participate in block production and will be given an opportunity to produce blocks, provided they can persuade token holders to vote for them.

합의 알고리즘으로 DPOS(Delegated Proof of Stake)를 사용한다.
투표를 통해 블록 생산자(Block Producer, 이하 BP)를 선출한다.

The EOS.IO software enables blocks to be produced exactly every 0.5 second and exactly one producer is authorized to produce a block at any given point in time. If the block is not produced at the scheduled time, then the block for that time slot is skipped. When one or more blocks are skipped, there is a 0.5 or more second gap in the blockchain.

블록은 0.5초 마다 생산된다.
특정 시점에서 블록을 생산할 수 있는 권한은 정확히 한 BP에게만 부여된다.
예정된 시간내에 블록이 생산되지 않으면 그 블록 생산은 무시된다. 무시되는 블록의 수에 따라 0.5초 이상의 갭이 생긴다.

Using the EOS.IO software, blocks are produced in rounds of 126 (6 blocks each, times 21 producers). At the start of each round 21 unique block producers are chosen by preference of votes cast by token holders. The selected producers are scheduled in an order agreed upon by 15 or more producers.

라운드마다 21 BP들이 투표지분에 따라 선정되고 블록을 생산한다.
블록 생산 순서는 15 이상의 BP들의 합의에 의해 정해진다. 합의를 봐야할 때는 언제나 2/3 + 1 규칙이 적용.
라운드마다 각각의 BP는 6개의 블록을 생산함으로, 라운드마다 생산되는 총 블록은 126개가 된다.

If a producer misses a block and has not produced any block within the last 24 hours they are removed from consideration until they notify the blockchain of their intention to start producing blocks again. This ensures the network operates smoothly by minimizing the number of blocks missed by not scheduling producers who are proven to be unreliable.

BP가 블록을 놓치고 지난 24시간 내에 블록을 생산하지 않은 경우 BP에서 제외된다. 블록 생산을 다시 시작할 거라고 블록체인에 알리기 전까지.

Under normal conditions a DPOS blockchain does not experience any forks because, rather than compete, the block producers cooperate to produce blocks. In the event there is a fork, consensus will automatically switch to the longest chain. This method works because the rate at which blocks are added to a blockchain fork is directly correlated to the percentage of block producers that share the same consensus. In other words, a blockchain fork with more producers on it will grow in length faster than one with fewer producers, because the fork with more producers will experience fewer missed blocks.

일반적인 상황에서는 포크가 발생하지 않는다. BP는 경쟁이 아닌 협력을 하니까.
포크가 발생하면 합의는 자동적으로 가장 긴 체인이 된다.

Furthermore, no block producer should be producing blocks on two forks at the same time. A block producer caught doing this will likely be voted out. Cryptographic evidence of such double-production may also be used to automatically remove abusers.

BP는 동시에 두 포크에서 블록을 생성할 수 없다. 이런 짓을 하면 투표로 퇴출 될 것이다. 암호학적 증거를 사용해서 자동적으로 퇴출 시킬 수도 있다.

Byzantine Fault Tolerance is added to traditional DPOS by allowing all producers to sign all blocks so long as no producer signs two blocks with the same timestamp or the same block height. Once 15 producers have signed a block the block is deemed irreversible. Any byzantine producer would have to generate cryptographic evidence of their treason by signing two blocks with the same timestamp or blockheight. Under this model a irreversible consensus should be reachable within 1 second.

EOS 합의 알고리즘은 DPOS에서 끝이 아니다. 여기에 BFT(Byzantine Fault Tolerance)가 더해진다. 그래서 BFT-DPOS라는 것.
같은 타임스탬프 또는 같은 블록 높이를 갖는 두 개의 블록에 사인하지 않는 한, 모든 BP는 모든 블록에 사인할 수 있다. 이것이 BTF라는 것.
15 BP가 블록에 사인하면 그 블록은 비가역적인 것이 된다. 되돌릴 수 없는 것. 확정되었다는 것.

나쁜 짓을 하려는 놈(byzantine producer)은 같은 타임스탬프 또는 블록높이를 가진 두 블록에 서명함으로 나쁜 짓(반역)에 대한 암호학적 증거를 생성하게 된다. #나쁜 짓을 하면 표시가 난다는 거지.#
이 모델하에서 비가역적 합의는 1초 내에 도달할 수 있어야 한다.

Transaction Confirmation
Typical DPOS blockchains have 100% block producer participation. A transaction can be considered confirmed with 99.9% certainty after an average of 0.25 seconds from time of broadcast.
In addition to DPOS, EOS.IO adds asynchronous Byzantine Fault Tolerance (aBFT) for faster achievement of irreversibility. The aBFT algorithm provides 100% confirmation of irreversibility within 1 second.

트랜잭션은 전파 시간부터 평균 0.25초가 지나면 99.9% 확실성으로 확정되었다고 여길 수 있다.
DPOS에 aBFT(asynchronous Byzantine Fault Tolerance)를 더하면 더 빠른 비가역성을 달성할 수 있다.
aBFT 알고리즘은 1초 내에 비가역성에 대한 100% 확정을 제공한다.
비가역성이 확정되면 다시 되될릴 수 없다는 것. 트랜잭션이 정상적으로 처리되어 블록체인에 포함될 것이 확정되었다는 것.

Transaction as Proof of Stake (TaPoS)
The EOS.IO software requires every transaction to include part of the hash of a recent block header. This hash serves two purposes:
1.prevents a replay of a transaction on forks that do not include the referenced block; and
2.signals the network that a particular user and their stake are on a specific fork.

Over time all users end up directly confirming the blockchain which makes it difficult to forge counterfeit chains as the counterfeit would not be able to migrate transactions from the legitimate chain.

모든 트랜잭션은 최근 블록 헤더의 해쉬를 포함해야 한다. 이 해쉬는 두 가지 목적을 위한 것이다.

1. 참조 블록을 포함하지 않는 포크에서 트랜잭션이 다시 사용되는 것을 막기 위해
2. 특정 사용자와 그들의 지분이 특정 포크 상에 있음을 네트워크에 알리기 위해
   트랜잭션에도 뭔가 특별한 조치를 해 두겠다는 거지. 나쁜 놈들이 나쁜 짓을 저지르지 못하도록.

이를 통해 합법적인 체인에 있는 트랜잭션을 위조 블록이 다시 가져다 사용할 수 없게 됨으로 가짜 체인들이 더 뻗어나가는 것을 어렵게 한다. 뭘 해도 금방 들킨다는 것.

백서의 내용 만 보면 BFT-DPOS는 정말 막강합니다. 정말 그럴지는 두고 봐야겠지만.
위임된 소수의 BP만으로도 안정적이고, 매우 빠른 트랜잭션 처리와 확정이 가능하도록 하기 위해 취할 수 있는 생각할 수 있는 모든 것을 다 반영했다라고 할 수 있습니다. 더 이상 뭘 더 할 수 있을지 의문이 들 정도
Dan, you are a great friend!

*같이 읽어보면 도움이 될 만한 것들 *
Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-1-byzantine-fault-tolerance-245f46fe8419
Understanding Blockchain Fundamentals, Part 2: Proof of Work & Proof of Stake
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-2-proof-of-work-proof-of-stake-b6ae907c7edb
Understanding Blockchain Fundamentals, Part 3: Delegated Proof of Stake
https://medium.com/loom-network/understanding-blockchain-fundamentals-part-3-delegated-proof-of-stake-b385a6b92ef
DPOS Consensus Algorithm - The Missing White Paper
https://steemit.com/dpos/@dantheman/dpos-consensus-algorithm-this-missing-white-paper
DPOS BFT— Pipelined Byzantine Fault Tolerance
https://medium.com/eosio/dpos-bft-pipelined-byzantine-fault-tolerance-8a0634a270ba

Daniel Larimer가 직접 설명하는 동영상
EOS: Explanation of DPoS+BFT w/ Daniel Larimer - Part 1 of 2

EOS: Explanation of New BFT+DPoS w/ Daniel Larimer - Part 2 of 2