Consensus Algorithm 기본
Blockchain 의 가장 중요한 개념 중에 하나인 consensus algorithm에 대한 친절하게 설명합니다. Consensus를 어렵게 하는 가장 기본적 문제인 Byzantine fault를 먼저 살펴보고, 이를 극복하기 위해서 제시되었던 3m + 1 processor algorithm, pBFT의 주요 원리를 설명합니다. 다음으로, 전혀 다른 접근으로 Byzantine fault 극복을 시도하는 PoW의 동작 원리와 PoW에서 본질적으로 발생하는 finality 문제를 설명하고, 이 finality 문제를 획기적으로 개선하기 위해 Ethereum 2.0에 가장 먼저 적용될 것으로 계획되어 있는 Casper FFG를 살펴봅니다.
이 글은 blockchain에 대해 일반적인 관심을 가진 독자나 blockchain을 활용하여 시스템을 개발하는 software engineer를 대상으로 하며, 주요 algorithm의 목적과 특성 및 동작 원리를 중심으로 설명합니다. Algorithm에 대한 증명 등은 다루지 않습니다.
Byzantine Fault
분산 환경에서 다수의 노드들이 정해진 규칙에 따라 동작하면서 동일한 결론에 이르는 과정 또는 상태를 consensus라 하며, 이 때 사용되는 규칙을 consensus algorithm 또는 consensus protocol이라고 합니다.
분산 환경에서 consensus 는 다자 간 문제로 기본적으로도 복잡하지만, 여러가지 제약 조건들이 포함되면 더욱 복잡해집니다. 다양한 제약 조건들 중에서도 가장 본질적이고 어려운 것 중 하나가 Byzantine fault입니다.
Byzantine fault는 노드들 중에서 고장으로 인해서 비정상적으로 동작하거나, 심지어는 해킹 또는 사적인 이익을 위해서 의도적으로 이상 동작하는 노드가 포함되어 있을 수 있다는 제약 조건입니다. Byzantine 이라는 고대 그리스 시대 도시 이름에서 이 문제가 아주 오래된 것으로 예상하기 쉬우나 분산 환경에서 Byzantine fault 에 대한 분석과 극복 방법 등은 1980년대 전후에서 본격적으로 연구되기 시작했습니다.
1982년에 발표된 초기 논문¹에서 Byzantine fault는 다음 그림과 같은 문제로 설명되었습니다.
적군을 둘러싸고 Byzantine 장군들이 각자 진영을 차리고 있습니다. 이들은 공격할 것인지 퇴각할 것인지 결정해야 하는데, 서로가 전령을 통해서 자신의 의사를 전달할 수는 있지만, 장군들 중에서 배신자들이 있을 수 있다는 문제가 있습니다. 이들은 결정을 위한 의사 교환 과정에서 교란 작전을 펼쳐 정상적인 장군들이 동일한 결정을 내리는 것을(consensus에 도달하는 것을) 방해할 수 있습니다. 예를 들어 장군들 중에서 6번 장군이 배신자라고 하면, 6번 장군은 다음 그림에서 보는 것과 같이 1번 장군에게는 공격 의사를 전달하고 2번과 5번 장군에게는 퇴각 의사를 전달하여 전체적인 consensus 형성에 부정적인 영향을 줄 것입니다.
만약 배신자가 한 명도 없다면, 각 장군들은 다른 모든 장군들의 의사를 수집하고 본인의 의사를 더하여 과반수 규칙에 따라 결정을 내린다면, 모든 장군들이 항상 동일한 결정을 내릴 수 있을 것입니다. 그런데, 만약 6명의 장군 중에서 1명의 배신자가 있다면 이 배신자의 교란으로 인해서 정상적인 장군들 중 일부는 공격을 결정하고 나머지 정상적인 장군들은 퇴각을 결정하는 최악의 상황을 방지하는 규칙을 정의할 수 있을까요? 2명의 배신자가 있다면 어떻게 될까요?
위와 같은 상황에서 어떤 consensus algorithm이 정상적인 장군들이 서로 다른 결정을 내리는, 원하지 않는 상황을 허용하지 않는다면 이때 우리는 이 consensus algorithm 이 Byzantine fault tolerant하다고 합니다. 그리고 consensus algorithm 에 대한 이러한 특성 또는 요건을 Byzantine fault tolerance, 약자로 BFT라 합니다.
Byzantine fault 또는 Byzantine fault tolerance에 대한 보다 명확한 이해를 위해서 가장 간단한 경우에 대해서 비교적 자세히 살펴보겠습니다.
전체 장군은 3명이며 이 중에서 1명이 배신자입니다. Consensus algorithm은 서로의 의사를 모두 수집해서 과반수로 공격 또는 퇴각을 결정하는 규칙입니다.
위의 그림 case 1, case 2에서 보듯이 정상적인 두 장군이 동일한 의견을 가졌을 때에는 배신자의 교란에 관계 없이 두 장군은 동일한 결론에 이르게 됩니다. 그러나, case 3과 같이 정상적인 두 장군이 서로 다른 의견을 가졌을 때에는 배신자의 교란에 의해 두 장군은 서로 다른 결론을 내리게 됩니다. 다시 말해서 consensus에 실패할 뿐만 아니라 서로 다른 행동을 취하게 됩니다. 따라서, 과반수 기반의 consensus algorithm은 Byzantine fault tolerance하지 않습니다. 그렇다면 이 상황에서 규칙을 어떻게 정의하면 Byzantine fault tolerance를 보장할 수 있을까요?
이론적으로 이 상황(전체 장군 3명 중에 배신자가 1명)에서 메시지 서명(signing)을 적용하지 않는다면 Byzantine fault tolerance한 알고리즘은 존재하지 않는다는 것이 증명¹되어 있습니다.
Consensus에는 Byzantine fault 이외에도 다양한 제약 사항들이 있습니다. 예를 들어 메시지 전달이 synchronous(sync) 인지 asynchronous(async) 인지 여부, 메시지 서명 여부, 네트워크의 연결 수준 등이 있습니다. 메시지 전달이 sync하다는 것은 일정한 시간 이내에 메시지가 전달되는 것을 보장한다는 뜻이고, async는 인터넷과 같이 메시지 전달이 예상을 훨씬 초과하여 지연되거나 중간에 손실될 수 있다는 뜻입니다. 당연히 async 조건에서 BFT를 만족하는 algorithm을 찾는 것이 일반적으로 더욱 어렵습니다. 메시지 서명²을 적용하지 않은 상황에서는 배신자가 다른 장군으로부터 받은 메시지를 조작하여 다른 장군들에게 중계(relay)할 수 있습니다. 그러나 메시지 서명을 적용하면 배신자는 자신의 의사는 받는 장군들마다 다르게 보낼 수 있으나, 다른 장군으로부터 받은 메시지를 조작할 수는 없습니다. 메시지 서명을 활용하면 보다 효율적인 consensus algorithm을 만들 수 있습니다.
[1] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem”, 1982
[2] 전자 서명
3m + 1 Processor Algorithm
Byzantine fault tolerance를 보장하는 범용 algorithm에 대한 최초의 성과는 1980년 논문¹에서 증명한 3m + 1 processor algorithm입니다.
이 논문에서는 m개의 fault 노드를 포함한 sync 네트워크에서 Byzantine fault tolerant한 algorithm이 존재하기 위해서는 전체 노드 개수가 3m + 1 개 이상이어야 한다는 것을 먼저 증명합니다. 다시 말해서 3m + 1 은 Byzantine fault tolerant한 algorithm을 위한 전제 조건이 됩니다.
예를 들어서 아래 그림과 같이 fault 노드가 1개인 경우 전체 노드 개수가 3개이면 Byzantine fault tolerance한 algorithm이 존재할 수 없습니다. 이 경우 왼쪽 2번째와 같이 전체 노드 개수가 4개(3m + 1, m = 1)이거나 그 이상이면 Byzantine fault tolerance한 algorithm이 존재합니다. 같은 논리에 의해 fault 노드가 2개인 경우, 전체 노드의 개수가 6개 이하이면 Byzantine fault tolerance한 algorithm이 존재하지 않으며, 아래 그림 맨 오른쪽과 같이 노드 개수가 7개(3m + 1, m = 2) 또는 그 이상이어야만 Byzantine fault tolerant한 algorithm이 존재합니다.
그러면 3m + 1 전제 조건을 만족하는 상황에서 consensus algorithm은 어떤 규칙일까요? 이를 이해하기 위해서 메시지 중계를 고려한 간단한 표기법을 먼저 살펴보겠습니다.
위 그림에서 노드 ①에서 노드 ④로 메시지를 전달하는 방법은 중계를 고려하면 모두 5가지 경우가 있습니다. 직접 전달하는 경우가 1 가지 있고, 중간에 하나의 노드를 경유하는 경우가 2 가지, 중간에 두 개의 노드를 경유하는 경우가 2 가지 있습니다.
이 때 각 경우를 다음과 같이 표시합니다.
v:1:4
v:1:2:4
v:1:3:4
v:1:2:3:4
v:1:3:2:4예를 들어 v:1:3:2:4 는 노드 ①에서 시작해서 노드 ③과 노드 ②를 차례로 거쳐 노드 ④에 전달되었다는 의미입니다.
3m + 1 processor algorithm에서 규칙은 메시지를 충분한 횟수만큼 중계하도록 정하고 있습니다. 보다 정확히 말해서 fault 노드가 m개 포함된 3m + 1 노드 분산 네트워크의 경우 각 메시지들은 m회 중계가 되어야 합니다. 그리고 각 노드는 다른 특정 노드의 의사를 결정할 때, 직접 전달된 메시지로부터 m번 중계 전달된 메시지들까지 포함하여 다수결로 결정합니다.
결함 노드가 1개(m = 1)인 경우, 각 노드는 직접 전달된 메시지(OM(1))와 1번 중계 전달된 메시지(OM(0)) 까지 받은 다음 다수결로 결정합니다. m = 1 인 경우 전체 노드 개수는 최소 4개(3m + 1) 이므로 2번 중계도 가능하지만 1번 중계된 메시지까지만 수집합니다. 결함 노드가 2개(m = 2)인 경우, 각 노드는 직접 전달된 메시지(OM(2)), 1번 중계 전달된 메시지(OM(1)), 2번 중계 전달된 메시지(OM(0)) 까지 수집하여 다수결로 결정합니다. m = 2인 경우 전체 노드 개수는 최소 7개이므로 2 ~ 5번 중계도 가능하지만 이들은 수집하지 않습니다.
일반화하여 결함 노드가 m개인 경우, 각 노드는 직접 전달된 메시지(OM(m))부터 m번 중계 전달된 메시지(OM(0))까지 수집하여 다수결로 결정합니다. 전체 노드의 개수는 최소 3m + 1이므로 3m - 1번 중계까지 가능하지만 m + 1번 이상 중계는 수집하지 않습니다. 메시지를 중계할 때에는 앞서 거쳐온 노드로는 보내지 않습니다.
Simplest Case
가장 간단한 경우(m = 1)에 대해 중계가 Byzantine fault를 극복에 작동하는 역할에 대한 단서를 살펴보겠습니다. 아래 그림은 노드 ②가 결함 노드인 상황에서, 노드 ①, 노드 ③, 노드 ④가 각각 노드 ②가 3m + 1 processor algorithm에 맞추어 보낸 메시지를 수집하는 경우를 보여줍니다.
노드 ②가 노드 ①, 노드 ③, 노드 ④에게 직접 의사를 전달하는 경우는 아래 표에서 v:2:1, v:2:3, v:2:4 열의 조합과 같이 모두 6가지 입니다. 노드 ②가 모두에게 동일한 의사를 전달하면 정상 동작에 해당하므로, 서로 다른 의사를 전달하는 경우만 검토합니다. 노드 ①, 노드 ③, 노드 ④가 노드 ②에서 직접 전달 받은 메시지(OM(1)) 로만 결정한다면, 노드 ②에 대해 서로 다른 의견을 가지게 됩니다. 따라서, 노드 ②를 제외한 다른 노드들로부터 받은 메시지를 통합하여 다수결로 결정을 내릴 때, 서로 다른 결정을 내릴 수 있습니다.
그러나, 노드 ②의 의사를 1번 중계한 메시지까지 수집하면 상황이 달라집니다. 아래 표에서 보듯이 노드 ①이 받는 중계 메시지는 모든 경우(case 1 ~ case 6)에서 노드 ③, 노드 ④가 직접 받은 메시지와 동일합니다. 다시 말해서 v:2:3:1 = v:2:3, v:2:4:1 = v:2:4 입니다. 동일한 논리에 따라서 노드 ③이 받는 중계 메시지는 노드 ①, 노드 ④가 직접 받은 메시지와 동일하며, 노드 ④가 받는 중계 메시지는 노드 ①, 노드 ③이 직접 받는 메시지와 동일합니다.
특정 노드가 중계로 받은 메시지는 다른 두 개 노드가 직접 받은 메시지와 같이 때문에, 결국 각 노드가 직접 받든 메시지를 모두 받게 됩니다. 따라서, 노드 ①, 노드 ③, 노드 ④ 가 직접 받은 메시지와 1회 중계로 받은 메시지의 합은 3개의 노드가 직접 받은 메시지의 합과 동일합니다. 이 합은 동일 경우(case 1 ~ case 6) 안에서는 동일하므로 노드 ①, 노드 ③, 노드 ④은 노드 ②에 대해서 동일한 의사를 확인하게 됩니다.
다시 말해서 노드 ②는 교란 목적에서 서로 다른 노드에 가능한 서로 다른 메시지를 보냈지만, 메시지 중계에 의해 각 노드는 다른 정상 노드들이 직접 받은 메시지까지 모두 확인하였기 때문에 노드 ②에 대해서 동일한 결정을 내리게 됩니다.
v:2:3:1 = v:2:3
v:2:4:1 = v:2:4
v:2:::1 = v:2:1 + v:2:3:1 + v:2:4:1 = v:2:1 + v:2:3 + v:2:4v:2:1:3 = v:2:1
v:2:4:3 = v:2:4
v:2:::3 = v:2:3 + v:2:1:3 + v:2:4:3 = v:2:3 + v:2:1 + v:2:4v:2:1:4 = v:2:1
v:2:3:4 = v:2:3
v:2:::4 = v:2:4 + v:2:1:4 + v:2:3:4 = v:2:4 + v:2:1 + v:2:3 v:2:::1 = v:2:::3 = v:2:::4
정상 노드들인 노드 ①, 노드 ③, 노드 ④의 결정은 노드 ②의 의사 뿐만 아니라, 자신을 제외한 다른 정상 노드들의 의사까지 수집해서 결정하게 됩니다. 위와 동일한 논리를 따라서 정상 노드에서 다른 정상 노드로 전달한 메시지도 중간에 노드 ②가 교란을 목적으로 변조한 값이 중계를 통해서 모두 전달되기 때문에 정상 노드들은 모든 경우에 동일한 메시지의 합을 확인하고 동일한 결정을 내릴 수 있습니다.
동일한 방식으로 결함 노드가 더 많은 경우에도 메시지를 충분히 중계하면 결함 노드가 교란 목적으로 서로 다른 노드들에게 다르게 보낸 메시지들이 각 노드에 모두 수집 되어 각 노드들이 동일한 결정을 내릴 수 있다는 것이 3m + 1 processor algorithm의 기본 원리입니다.
3m + 1 processor algorithm 은 재귀 수행 기반의 간단한 규칙으로 결함 노드의 개수에 관계없이 적용할 수 있는 더할 나위 없이 보편적이고 유용한 algorithm으로 보입니다. 그러나, 3m + 1 processor algorithm은 그 복잡도에 의해서 확장성에 상당한 제약이 있습니다. 아래 표에서 보는 것처럼 중계를 반복할 수록 메시지 전달 횟수는 급격히 늘어나며 결함 노드가 m 개일 때 복잡도는 O(nᵐ) 이 됩니다. 따라서, 3m + 1 processor algorithm은 그 규모가 일정 이하에서만 현실적으로 활용 가능합니다.
[1] M. Pease, R. Shostak, and L. Lamport, “ Reaching Agreement in the Presence of Faults”, 1980
Practical Byzantine Fault Tolerance (pBFT)
@TODO
Proof of Work
앞서 살펴본 3m + 1 processor algorithm이나 pBFT algorithm에서는 노드들이 서로 협업을 통해서 결함을 극복합니다. 결함 노드의 교란 또는 방해를 극복하기 위해서 정상 노드의 개수가 충분히 많아야 하는 조건이 발생하며, 정도의 차이는 있지만 복잡도 - 3m + 1 processor algorithm의 경우 O(nᵐ), pBFT의 경우 O(n²) - 에 의해서 확장성에 상당한 제약이 존재합니다.
Proof of Work (PoW) algorithm은 이와는 전혀 다른 접근 방식을 취합니다. PoW 에서 각 노드들은 협업하지 않으며 경쟁합니다. 일반적으로 풀기는 매우 어려우나 검증하기는 매우 쉬운 수학적인 퍼즐에 도전해서 먼저 풀이에 성공하는 노드가 해당 시점의 전체 의사를 결정합니다. 이 수학 퍼즐은 특정 조건을 만족하는 hash 값의 계산이나 매우 큰 자연수의 소인수 분해¹ 등과 같이 단순 시도의 반복에 의해 확률적으로만 성공하는 문제입니다. 이런 문제들은 특별한 공식이나 기법을 상대적으로 빠르게 풀 수가 없습니다. 따라서, 모든 노드들이 문제 풀이에 집중한다면 각 노드들이 전체 의사를 결정할 가능성은 확률적으로 주어집니다. 다시 말해서 특정 노드 또는 결함 노드가 지속적으로 결정권을 가져갈 가능성의 매우 낮습니다. Bitcoin과 Ethereum 등과 같이 PoW를 활용하는 분산 환경에서는 누구나 consensus 에 참여할 수 있도록 환경을 열어두어 연산력(computing power)가 특정 노드 또는 노드 그룹에 집중되는 것을 최대한 방지합니다.
Bitcoin 및 Ethereum 과 같은 blockchain 네트워크에서는 주어진 퍼즐은 각 노드가 반영하고자 하는 transaction 들을 포함한 block header 데이터에 nonce라 불리는 특정한 값을 더하여 hash 계산을 하였을 때 그 값이 특정한 조건을 만족하도록 하는 nonce값을 찾는 것입니다. 이해하기 쉽게 조건을 보다 단순하게 하면 다음과 같습니다.
Find Nonce for SHA-256(Data + Nonce) to start with '0000'Hash 함수²는 주어진 데이터 또는 문자열을 일정한 길이의 다른 문자열로 변환하는 함수입니다. Hash 함수는 몇 가지 중요한 특징이 있는데, 첫 번째는 결과값으로부터 계산 전의 값을 역으로 알아 낼 수 없다는 점입니다. 수학적으로 표현하면 hash 함수는 역함수가 존재하지 않습니다.
예를 들어 아래 표에서 “Hello, world!”에 대한 SHA-256³ hash 함수 적용 결과가 “0x315f5bdb76d0…”이 되는 것은 계산하기 쉬우나 이 “0x315f5bdb76d0…”이 주어졌을 때 여기에 대응하는 SHA-256 hash 입력값 “Hello, world!”를 역으로 계산하는 것은 불가능합니다.
두 번째 특성은 Hash 함수는 입력값의 아주 작은 변화에도 그 결과값은 매우 크게 달라진다는 점입니다. Hash 함수는 입력값들을 그 결과값 공간에 충분히 고르게 분산하는 것이 주요한 요건이기에 나타나는 자연스러운 특성입니다. 아래 표에서 보듯이 “Hellow, world!” 문자열 바로 뒤에 nonce로 0, 1, 2, … 등을 바꾸어 가면서 SHA-256을 계산하면 (입력값은 맨 마지막 문자 하나만 차례로 바뀌지만) 그 결과값들은 전혀 다른 값들로 매우 크게 바뀌는 것을 확인할 수 있습니다.
따라서, “Hello, world!” 뒤에 nonce를 변경하면서 hash 계산을 할 때, 그 결과값이 “0x0000…” 로 시작하려면 “Hello, world!4250” 이어야 한다는 아래 표의 마지막 행의 계산은 역산이나 또는 어떤 고도의 수학적 기법을 동원해서 알아낼 수가 없으며, 오로지 임의의 값을 바꾸어 가면서 시행착오를 통해서 찾을 수 밖에 없습니다.
Ethereum 에서 사용하는 PoW algorithm의 정확한 명칭은 Ethash⁴ 입니다. Ethash에서는 Keccak-256⁵ 이라는 hash 함수를 사용하며, 연산 조건은 hash 결과값을 지정한 숫자보다 작게 만드는 nonce값을 찾는 것입니다.
위의 함수는 Ethash spec 에 제시되어 있는 Python 함수 입니다. Bitcoin 및 Ethereum에서는 주어진 조건을 만족하는 nonce 값을 찾아 퍼즐을 푸는 작업을 mining(채굴) 이라고 합니다. 문제를 풀면 그 시점에서 blockchain 네트워크에 추가될 transaction 들을 결정할 뿐만 아니라, 그 보상으로 암호화폐를 지급 받기 때문입니다.
위의 mine 함수를 보면 내부에서 nonce 값을 차례로 바꾸어 가면서 hash 함수 값이 목표값(target) 이하가 되는 경우에 연산에 성공하게 됩니다. 그 목표값( target)은 2²⁵⁶ 을 지정한 난이도(difficulty) 로 나눈 값입니다. 따라서 목표값은 2²⁵⁶보다 작은 수이며, 2²⁵⁶에 맞추어 16진수로 표현하면 전체 64자리 중에서 앞 부분은 0으로 시작하게 됩니다. 예를 들어 목표값이 2²²⁷ 이면 앞 부분 7개의 숫자가 0이며, 목표값이 2²⁰⁵이면 앞 부분 12개의 숫자가 0이 됩니다.
목표값(target)과 난이도(difficulty)의 곱은 2²⁵⁶ 으로 상수입니다. 난이도를 높이면 목표값은 작아지며 따라서, 조건을 만족하는 hash 값은 더 많은 0으로 시작해야 합니다.
SHA-256 함수 hash 값의 가능한 모든 경우의 수는 2²⁵⁶ 이며, mining에 성공하는 경우의 수는 목표값(target)과 같습니다. 따라서, 목표값을 2²⁵⁶ 으로 나눈 값은 단일 hash 함수 계산이 mining에 성공할 확률이며, 이것은 난이도의 역수와 동일합니다.
아래 표는 실제 Ethereum 네트워크에서 몇몇 block의 난이도와 목표값을 보여주고 있습니다. 난이도를 일정하게 유지한다면, mining을 수행하는 노드들의 개수 또는 그들이 소모하는 전력량에 따라 block 생성 주기가 변경될 것입니다. Ethereum 에서는 이런 현상을 방지하고 가능한 일정한 주기로 block이 생성되도록 하기 위해서 최근 block 생성 주기를 바탕으로 매번 새로운 block을 위한 난이도를 자동으로 계산합니다.
Bitcoin 및 Ethereum 에서 모든 transaction은 디지털 서명이 되어 노드에 전달됩니다. 따라서, 결함 노드가 transaction 들을 조작할 수는 없습니다. 그리고 PoW에서 사용하는 퍼즐은 풀기는 매우 어렵지만 검증은 아주 간단하기 때문에, 결함 노드가 의도적이든 그렇지 않든 거짓으로 보낸 block 은 바로 다른 정상적인 노드들에 의해서 거부됩니다. 다시 말해서 Bitcoin과 Ethereum의 PoW는 공개키 기반 메시지 서명과 결합되어 Byzantine fault tolerance를 제공합니다.
PoW는 협업이 아닌 경쟁 기반으로 작동하므로, 그 복잡도는 전체 노드 개수와는 무관하며, 퍼즐의 난이도에 따라서 성능이나 확장성이 결정됩니다. 따라서 PoW는 앞서 살펴본 협업 중심의 pBFT 등에 비해서 대규모 네트워크에 훨씬 유리한 방식이지만 여전히 중요한 문제를 내포하고 있습니다.
가장 잘 알려진 문제는 노드들 사이의 치열한 경쟁에 따른 막대한 에너지 소비이며, 또 다른 문제는 이어서 설명할 finality 문제입니다.
Finality Problem
앞서 설명한 바와 같이 PoW 기반 blockchian에서 문제풀이는 mining이라는 용어로 자주 표현하며, 문제풀이 또는 mining에 성공한다는 것은 blockchain 새로 추가할 block을 생성하였다는 의미입니다. Mining에 성공하면 보상을 받기 때문에 많은 노드들이 치열하게 경쟁합니다. PoW mining의 상세 규칙을 보면 조건을 만족하는 nonce를 구하기 위한 hash 계산 대상에는 transaction 데이터 뿐만 아니라, 이전 block header의 hash 값도 포함하고 있습니다. 이는 blockchian이 1차원 chain 구조를 유지하면서 생성되도록 하기 위한 규칙이며, blockchain이 데이터 무결성을 최대한 보장하는 근본 원리이기도 합니다. 대부분의 경우, mining 성공은 충분한 시간을 두고 발생하기 때문에 block들은 1차원 chain 구조를 유지할 수 있습니다.
그러나, PoW 네트워크에서 mining 성공은 확률적으로 발생하기 때문에 그 가능성이 매우 낮기는 하나 서로 다른 두 개 이상의 노드가 거의 동시에 mining성공하는 경우도 발생합니다. 생성된 block의 전파와 검증은 간단한 작업이기는 하나, 전세계에 걸친 노드들에게 모두 전파되려면 일정한 시간이 소요되므로, 이 경우 지역에 따라서 노드가 가진 최종 blockchain 모습은 약간씩 다르게 됩니다.
예를 들어 아래와 같이 서로 공간적으로 멀리 떨어져 있는 두 노드 A와 B에서 거의 동시에 block B(m)과 block B(n) 생성에 성공하면, 충분한 시간이 지나 네트워크 전체에 B(m) 과 B(n)이 모두 전파되기 전에는 노드 A 주변에서는 block B(m)을 최종 block으로, 노드 B 주변에서는 block B(n)을 최종 block으로 보며, 두 노드로부터 적절히 떨어진 노드들에서는 두 개의 block이 모두 최종 block으로 보일 것입니다.
PoW에서 두 노드는 서로 협업하지 않으며, 자신이 수집한 transaction들을 자신이 유리하다고 생각하는 방식에 따라서 mining을 시도하므로 B(m)과 B(n)이 동일한 block일 가능성은 실제로 0입니다. 따라서, B(m)과 B(n)은 서로 선후 관계를 가질 수 없고, 동일한 이전 block을 바탕으로 생성된 형제와 같은 상태가 됩니다. Ethereum에서는 이를 uncle block이라고 합니다.
이 때 두 block을 모두 전달받은 노드들(아래 그림에서 중간 영역)에서는 blockchain이 실제로는 1차원 chain 구조를 벗어나 2개 이상의 branch들로 fork가 발생한 구조가 됩니다. 아래 그림 중간 영역 노드들이 가지는 blockchain 구조를 보면 1차원 chain 구조를 가지지 못하고 B(m) branch와 B(n) branch가 생성되어 있는 것을 볼 수 있습니다.
노드들은 보상을 위해서 지속적으로 mining을 도전합니다. B(m)을 먼저 받은 노드들은 B(m)을 기반으로 다음 block을 위한 mining을 수행할 것이고, B(n)을 먼저 받은 노드들은 B(n)을 기반으로 다음 block을 위한 mining을 수행할 것입니다. 대부분의 경우 다음 mining 성공은 충분한 시간 간격을 가지고 발생하여 장기적으로는 B(m) branch 또는 B(n) branch 둘 중에서 하나만이 살아남을 것입니다. 그러나, 매우 희박하기는 하지만 노드 A, 노드 B 주변에서 각각 B(m)과 B(n)을 기반으로 또다시 거의 동시에 서로 다른 노드들이 mining에 성공할 가능성도 있습니다. 이 경우, 아래 그림과 같이 중간 영역에 있는 노드들은 두 branch 가 동시에 성장하는 blockchain 구조를 가질 수도 있습니다.
이렇게 2개 이상의 branch 들이 일정 개수 이상 엇비슷하게 생성되는 현상은 일정 시간 지속될 수 있지만 오래가지는 못합니다.
Bitcoin 이나 Ethereum 에서는 longest chain rule을 따릅니다. Longest chain rule은 검증한 block을 전파하거나 block 내부의 데이터를 조회할 때, branch들이 있으면, 가장 긴 branch를 선택해야 하는 규칙입니다. 따라서, branch 들이 형성되어도 일단 어느 한 branch가 더 빠르게 성장하기 시작하면 그 속도는 가속되어 전체적으로 특정 branch만 살아남게 됩니다. 따라서, 장기적으로는 단일 chain이 유지됩니다.
위와 같은 과정에서 PoW 네트워크의 finality 문제가 발생합니다. Finality 문제란 정상적인 mining에 의해서 block이 생성된 이후에도 PoW algorithm이 본질적으로 가지는 동시 mining 상황에 따라서 이후 해당 block이 다시 취소되는 현상입니다.
아래 그림은 하나의 노드가 시간이 지남에 따라 보유하는 blockchain의 변화입니다. ②에서 blockchain에는 tx(n)을 포함하는 B(n) block을 받아 검증하고 chain의 맨 끝에 추가하였습니다. 그런데, B(n) block 과 거의 동시에 생성된 B(m) block이 바로 이어 도착하여 ③에서와 같이 fork가 발생하였습니다. 이후 두 branch는 일정 기간은 엇비슷하게 성장하다가, 결국에는 특정 branch가 더 빨리 성장하고 다른 branch는 더 이상 block이 쌓이지 않게 될 것입니다. 예를 들어 ⑥에서와 같이 결국 B(m) branch가 살아남는다면 여기에서 중요한 문제가 발생합니다. 만약 B(m) branch 에 tx(n) 이 포함되어 있지 않다면, tx(n)은 ② 시점에서는 유효한 transaction 이었고, 이에 따라서 a와 b의 상태가 변화하였는데, 이후 ⑥ 시점에서 이 transaction이 무효화 되고 따라서 a와 b의 상태도 원래로 되돌아 가는 현상이 발생합니다.
이와 같이 PoW 네트워크에서는 block 이 정상적으로 생성되었다 하더라고 이후 충분한 시간까지는 확정되지 못하는 (다시 말해서 이 block이 무효화될 가능성이 남아 있는) 문제점이 발생하는데 이를 finality 문제라고 합니다.
Finality 문제를 우회하기 위해서 client는 자신이 보낸 transaction이 성공적으로 mining이 되었다 하더라도, 그 block 이후로 일정 개수의 block이 계속 이어지는지 확인해야 합니다. 보통 Bitcoin에서는 6 block 정도를 Ethereum에서는 12 block 정도를 일반적으로 확정에 필요한 개수로 봅니다. 물론 transaction 의 중요도에 따라서 더 기다릴 수도 덜 기다릴 수도 있을 것입니다. Ethereum의 block time은 15초 정도에 맞추어져 있습니다. 15초 정도에 맞추어 앞서 설명한 difficulty가 자동으로 지속적으로 조정되고 있습니다. 그런데 12 block을 기다리면 이 시간은 3분 가량이 됩니다. 다시 말해서 원하는 transaction이 바로 mining에 성공하였다 하여도 3분을 기다려야 안심할 수 있다는 의미입니다.
Finality 문제는 blockchain의 핵심 가치 중에 하나인 데이터 무결성에 영향을 미치는 중대한 문제이며, 일부 transaction 의 손실 정도가 아니라, 이를 악용하여 blockchain 전체의 안정성을 훼손할 수 있는 매우 위험한 문제입니다. 만약 누군가 악의적인 의도를 가지고 전체 mining 역량의 50% 이상을 확보한다면, 이들은 blockchain 의 기본적인 신뢰도를 저하시킬 수 있습니다. 예를 들어 고가의 상품을 구매하고 이를 ETH로 결제하면서 tx를 blockchain에 기록했다가, 이후에 mining 역량 를 집중하여 fork를 만들고 이어서 다른 branch에 의도적으로 mining을 집중하여 tx를 무효화 할 수 있습니다. 이를 “51% 공격”⁶ 이라고 합니다. 수 백 이상의 노드들이 참여하는 public blockchain 네트워크에서 50% 이상의 mining 역량을 확보한다는 것은 거의 불가능한 일로 생각할 수도 있지만, 이는 이미 실제로 발생하고 있는 위협입니다. 2019년 1월에는 Ethereum Classic(ETC)가 공격을 받았으며⁷ 2020년 1월에는 Bitcoin Gold(BTG)가 공격을⁸ 받았습니다.
Ethereum에서는 finality 문제를 개선하기 위해서 Casper FFG 라는 이름의 새로운 consensus algorithm 을 준비하였으며, Ethereum 2.0 의 가장 중요한 목표로 진행하고 있습니다.
[1] Prime Factorization
[2] Hash 함수
[3] SHA-256
[4] Ethash Specification
[5] Keccak-256
[6] 51% 공격이란 무엇인가요?
[7] ETC 51 % attack — what happened and how it was stopped (2019/01/14)
[8] Bitcoin Gold Blockchain Hit by 51% Attack Leading to $70K Double Spend (2020/01/27)
Casper FFG
Casper FFG는 앞서 살펴본 finality 문제를 획기적으로 개선할 것으로 기대되는 새로운 consensus algorithm입니다. Casper FFG 는 2017년 Vitalik Buterin 과 Virgil Griffith 이 발표한¹ PoS(Proof Of Stake) 계열의 algorithm 으로 몇 가지 독특한 특성을 지니고 있습니다.
첫째 Casper FFG는 consensus 과정에서 finality 확정 만을 담당하는 partial algorithm입니다. Casper FFG에는 block 생성을 정하는 규칙은 포함되어 있지 않습니다. PoW algorithm에 의해서 생성되는, fork 발생이 가능한 block들, 다시 말해서 엄밀하게는 candidate block들을 대상으로 finality를 보다 신속히 결정하는 새로운 규칙을 정의하고 있습니다. 기존 PoW 위에 새로운 규칙을 추가하여 작동한다는 의미에서 Casper FFG는 overlay algorithm이라 분류하기도 합니다.
둘째로 Casper FFG는 별도로 선택된 node들에 의해 운영되는 PoS 계열의 algorithm입니다. PoS 계열 algorithm에서 consensus 과정에 참여하는 node들을 validator라고 하며, validator가 되기 위해서는 일정한 지분(stake)를 유치해야 합니다. Validator들은 유치한 지분에 비례하는 의사결정권을 가집니다.
셋째 Casper FFG에는 incentive 규칙 뿐만 아니라 penalty 규칙이 포함되어 있습니다. pBFT를 포함한 기존의 pBFT 계열 algorithm에는 penalty 조항이 없기 때문에 악의적인 node가 consensus를 방해하는 동작을 고의로 수행하여도 이를 효과적으로 막을 수 없었습니다. 대표적으로 “Nothing at stake”² 문제가 있습니다. 그러나, Casper FFG에서는 참여자들이 규칙을 지키지 않을 경우 지분을 모두 몰수당하는 불이익(penalty)을 받도록 설계하여 이런 문제 발생을 방지하고 있습니다.
Caper FFG는 기존의 pBFT 계열 algorithm과 비슷하게 정해진 시간 간격의 round을 반복하며 진행합니다. 각 round에서 모든 validator들은 투표를 수행하며, 이 때 2개의 규칙을 지켜야 합니다. 2개의 규칙 중에서 하나라도 위반하면 해당 validator는 지분을 몰수되고, validator 자격을 상실합니다. 이런 의미에서 이 규칙들을 slashing condition이라고 합니다.
특정 round에서 2/3 이상의 validator 들의 투표를 받은 block은 justified block이 됩니다. Justified block 들은 여전히 fork 발생이 가능하여 최종적으로 확정된 block 이 아닙니다. 그러나, 인접한(부모/자식 관계로 연결된) 두 block 이 연속해서 justified가 되면 이 때 부모 block은 최종적으로 확정(finalized) block 이 됩니다. 이 block은 전체 validator 들의 1/3 이상이 지분을 몰수되는 댓가를 치르지 않고는 무효화할 수가 없습니다.
누구나 제약 없이 mining node로 참여할 수 있는 PoW 와는 달리, Casper FFG에서는 validator 선정에서 동일 세력에 의해서 결정력이 훼손되지 않도록 여러가지 장치가 고려될 수 있으며, incentive와 함께 slashing condition을 적용하여 validator들의 보다 적극적인 협업을 유도할 수 있습니다. 따라서, Casper FFG는 현재 Ethash에서 활용하고 있는 longest chain rule 보다 훨씬 더 효과적으로 finality를 개선할 수 있습니다.
현재의 Ethereum 을 혁신적으로 확장할 Ethereum 2.0³에서는 초기에 현재의 Ethash 위에 Casper FFG를 overlay하여 finality 성능 개선을 담보할 것으로 계획하고 있습니다.
[1] Vitalik Buterin and Virgil Griffith, “Casper the Friendly Finality Gadget”, 2017
[2] PoS 지분증명에서 ‘nothing at stake’의 의미
[3] Ethereum 2.0 Info
Summary
현재의 Ethereum 1.0 네트워크는 15 TPS 안팎의 낮은 성능과 함께 심각한 finality 문제를 겪고 있습니다. 이를 극복하기 위해서 Ethereum 2.0에서는 PoS 계열의 Casper FFG를 준비하고 있습니다. Ethereum 1.0 finality 문제의 원인, 그리고 Casper FFG가 이를 극복하는 방법 등을 이해하기 위해서는, consensus 의 가장 중요한 문제의 하나인 Byzantine fault와 이를 해결하기 위해 진화 발전해 온 다양한 algorithm 들을 접하고 이해하는 것이 필요합니다.
이 글에서는 Byzantine fault, Byzantine fault tolerance 부터 시작해서 3m + 1 processor algorithm, pBFT, PoW, 그리고 Casper FFG 까지 주요 algorithm 들의 핵심 concept을 정리해 보았습니다.