해시드 한국어 블로그에서는 탈중앙화와 관련된 세계의 좋은 글들을 한국어로 번역하여 소개합니다.
이번 글은 이더리움 창시자로 잘 알려져 있는 비탈릭 부테린(Vitalik Buterin)이 쓴 A Guide to 99% Fault Tolerant Consensus를 번역한 글입니다. ‘원활한 합의를 위해 악의적인 노드의 비율이 전체 네트워크에서 얼마보다 작아야 하는가’ 하는 문제는 분산컴퓨팅 분야에서 ‘비잔틴 장군 문제’로도 잘 알려져있습니다. 이번 글을 통해 비탈릭 부테린은 99%의 악의적인 (혹은 일시적으로 정상동작을 하지 못하는) 행동을 하는 노드가 있다하더라도 합의에 이를 수 있는 방법에 대해 설명하고자 했습니다. 분산 컴퓨팅과 합의 알고리즘에 관심있으신 많은 분들께 도움이 되셨으면 좋겠습니다. (다만, 이 글은 비잔틴 장군 문제나 PBFT에 대한 기본적인 지식이 있는 독자들을 대상으로 쓴 글이라 배경지식이 없다면 약간 이해하기 어려운 부분이 있을 수 있습니다.)
감수: Brian Choi
원글을 감수해준 Emin Gun Sirer님께 특별히 감사를 표한다.
정직한 노드에 의해 브로드캐스팅 되는 메시지가 알려진 시간 이내에 다른 정직한 노드들에게 도달되는 것이 보장된 ‘동기화 네트워크’에서는, 최대 50% 장애허용 합의를 이루는 것이 가능하다고 흔히 알려져 있다. (만약 공격자가 50%보다 많다면 ‘51% 공격’을 수행할 수 있고, 이와 유사한 어떤 타입의 알고리즘으로도 공격이 가능하게 된다.) 또한 동기성 가정을 완화시키면, 장애허용 한도가 떨어지긴 하지만 최대 33%까지는 허용될 수 있는 ‘비동기 하에서도 안전한’ 알고리즘이 있다는 사실도 알려져 있다. (PBFT, Casper FFG, 등이 모두 이 범주 안에 속한다) 그러나 혹시 여기서 가정 몇 개를 더하면 (관측자라고 불리는 특별한 개체가 필요하다. 이들은 합의에 적극적으로 참여하지는 않지만, 합의 결과를 단순히 다운로드 받기만 하는게 아니라, 합의의 과정을 유심히 지켜보고 결과에도 상당한 신경을 쓰는 주체이다), 장애허용 한도를 99%까지 늘릴 수 있다는 사실을 알고 있는가?
사실, 이는 꽤 오래전부터 알려져 온 이야기이다. 1982년 Leslie Lamport의 유명한 논문 ‘비잔틴 장군 문제’에 이 알고리즘에 대한 설명이 포함되어 있다. 아래 문단부터는 내 나름대로 이해한 바를 토대로 해당 알고리즘을 더 간단한 형태로 재구성해서 설명해보겠다.
합의에 참여하는 N개의 노드들이 있고, 모두가 미리 이 노드들이 누구인지 알고 있다고 가정해보자. (이 노드들은 맥락에 따라, 신뢰할 수 있는 단체에 의해 선정되거나, 혹은 더 강력한 탈중앙화가 필요한 상황이라면 PoW나 PoS에 의해 선정될 수 있다) 이 노드들을 0….N-1까지 레이블링 하겠다. 또한 네트워크의 시간지연과 노드들의 시계오차의 합이 최대 D를 넘지 않는다고 가정하자. (eg. D = 8초) 각각의 노드들은 특정 시점 T에 어떤 특정한 값을 발행할 능력이 있다. (악의적인 노드들도 당연히 T 이전 혹은 이 후에 값들을 제안할 수 있다) 모든 노드들은 (N-1) * D 초동안 기다린 후, 다음 연산을 수행한다. 또한, x : i 를 ‘노드 i 에 의해 서명된 값 x’로 정의하고, x : i : j 는 ‘노드 i에 의해 서명된 값 x를 의미하되, 그 값과 서명이 다시 한번 다른 노드 j에 의해 서명되었음’을 의미하는 것으로 정의한다. 첫 번째 스테이지에서 발행된 제안들은 v: i의 형태이고, 해당 값을 제안한 노드의 서명이 포함되어 있다.
만약 검증자 i가 v : i[1] : … : i[k]와 같은 어떤 메시지를 받았다고 가정해보자. 이 때, 메시지 v는 i[1] … i[k] 노드들이 순서대로 서명했고(k=0이면 서명이 없으니 메시지는 v이고, k=1이면 서명이 하나만 있으니 메시지를 v:i로 표현할 수 있다), 검증자는 (i)현재 시각이 T + k * D보다 이르다는 것을 확인하고, (ii) v를 포함하는 유효한 메시지를 아직까지 본 적이 없다는 것을 확인해야 한다. 만약 두 조건을 모두 만족할 경우, 비로소 검증자는 v : i[1] : … : i[k] : i를 발행하게 된다.
시각 T + (N-1) * D 에, 노드들은 리스닝을 멈춘다. 바로 이 때, 정직한 노드들은 모두 ‘유효하다고 체크한’ 동일한 값의 집합을 갖고 있다는 것이 보장된다.
노드 1(빨강)은 악의적인 노드이고, 노드 0과 2(회색)는 정직한 노드들. 최초에 두 개의 정직한 노드들은 y와 x값을 각각 제안했고, 공격자는 w 와 z를 더 늦게 제안한다. w는 노드 0에는 제 시간 안에 도착했으나 노드 2에는 타임라인 안에 제안하지 못했고, z는 양쪽 노드 모두에 제 시간에 도착하지 못했다. 시각 T + D에 노드 0과 2는 본인들이 관측은 했으나 아직 브로드캐스팅하지 않았던 모든 값들(노드 0은 x 와 w를, 노드 2는 y)에 본인들의 서명을 덧붙여서 다시 브로드캐스팅한다. 두 개의 정직한 노드들은 모두 {x, y, w} 메시지를 관측한 상태가 된다.
만약 하나의 값만을 선택해야 한다면, 노드들은 어떤 ‘선택’ 함수(예를 들어, 해시값이 가장 작은 값을 선택하는 방식)를 사용하여 그들이 관측한 값들 중에서 하나의 값을 고를 수 있다. 이후, 노드들은 이 값에 대해서 동의할 수 있게 된다.
이제, 이 방법이 왜 잘 동작하는지 알아보자. 우리는 ‘하나의 정직한 노드가 특정한 유효한 값을 관측했을 때, 모든 다른 정직한 노드들 또한 해당 값을 관측하게 된다’는 사실을 증명해야 한다. (그리고 이 사실을 증명하면 모든 정직한 노드들이 똑같은 값들의 set을 관측해서 갖고 있게 되는 셈이고, 정직한 노드들이 같은 선택 함수를 사용한다면 결국 하나의 똑같은 값을 선택하게 될 것이다.) 한 정직한 노드가 v : i[1] : … : i[k] 메시지를 받았고, 이 메시지의 서명에 참여한 노드들이 이를 유효한 값이라고 여기는 상황을 가정해보자. (즉, 메시지는 T + k * D 이전에 도착한 것이다) x를 다른 정직한 노드들의 인덱스라고 두면, x는 {i[1] … i[k]}중 하나의 노드이거나 아닌 상황이 된다.
- 첫째로 (이 메시지에 대해 x = i[j] 라고 가정), 우리는 정직한 노드 x가 이미 해당 메시지를 브로드캐스팅했다는 사실을 알 수 있게 되고, 이전에 서명한 다른 노드들 또한 각각 T + (j-1) * D 시각 이전에 메시지를 받았고, 제한시간 내에 j-1 개의 서명이 담긴 메시지를 본인의 서명과 함께 브로드캐스팅 했다는 사실을 알 수 있다. 결국, 메시지 x는 모든 정직한 노드들에 의해 T + j * D 시각이전에 받아들여졌다고 생각할 수 있다.
- 둘째로, 정직한 노드는 T + k * D시각 이전에 메시지를 볼 것이기 때문에, 메시지 x를 포함한 해당 노드의 서명은 브로드캐스팅 되어 T + (k+1) * D시각 이전에 다른 모든 노드들이 메시지를 받게 될 것이다.
이 알고리즘에서, 한 노드가 본인의 서명을 추가하는 행동이 메시지의 종료시간을 늘려주는 일종의 ‘완충’ 역할을 하게 된다. 이 속성은 하나의 정직한 노드가 메시지를 제때 보았다면, 본인을 제외한 다른 모든 노드들 또한 해당 메시지를 제때 보았다는 것을 보장해준다. 여기서 ‘제때’의 정의는 추가된 서명들 모두의 네트워크 시간지연(latency)보다 커져야 한다.
한 개의 노드가 정직한 경우를 살펴보자. 우리는 수동적인 관측자들(즉, 합의에 참가하지는 않지만, 결론에는 관심이 있는 노드들)이 전 과정을 지켜보도록 강제하면서 올바른 결론을 볼 수 있도록 보장할 수 있을까? 지금까지 써둔 과정을 그대로 따라할 경우, 한 가지 문제가 발생한다. 지휘관 하나와 k개의 악의적인 관측자들의 일부가 메시지 v : i[1] : …. : i[k]를 생성하고, 이를 ‘희생자’들에게 T + k * D시각 이전에 브로드캐스팅 한다고 가정해보겠다. 희생자들은 ‘제때’에 메시지를 받아보긴 하겠지만, 그들이 해당 메시지를 다시 브로드캐스팅하면 다른 모든 합의에 참가하는 정직한 노드들은 T + k * D시각 이후에 메시지를 받아볼 것이기 때문에 이 메시지를 거절할 것이다.
하지만 우리는 이 구멍을 메울 수 있다. 제한시간 D를 네트워크 시간지연(latency)과 시계 오차의 합의 2배로 세팅한다. 그리고 나서 관측자들을 위한 시간제한을 새로 설정한다: 관측자는 메시지 v : i[1] : …. : i[k]를 T + (k — 0.5) * D시각 이전에 수락하도록 한다. 관측자가 메시지를 보면 수락한다고 가정하면, 정직한 노드들에게 T + k * D시각 이전까지 이 메시지를 브로드캐스팅할 수 있을 것이고, 정직한 노드는 본인의 서명을 덧붙여서 메시지를 발행할 것이다. 이 메시지는 다른 모든 관측자들에게 T + (k + 0.5) * D 시각(k+1개의 서명이 담긴 메시지의 시간제한) 이전에 도달하게 될 것이다.
본 알고리즘을 활용한 다른 합의 알고리즘의 개조
위에서 이야기한 알고리즘은 이론적으로 독립적인 합의 알고리즘으로 사용될 수 있고, 심지어 PoS 블록체인 위에서도 사용될 수 있을것이다. N+1번째 합의 라운드의 관측자 셋은 N번째 합의 라운드에서 결정될 수 있다. (예를 들어, 각각의 합의 라운드는 “입금”과 “출금” 트랜잭션을 받아들일 수 있고, 올바로 서명된 트랜잭션이 받아들여진다면 다음 라운드에서 관측자를 추가하거나 뺄 수 있게 된다.) 이 때 가장 중요한 부분은 누가 블록을 제안할 것인가를 결정하는 메커니즘이다.(예를 들어, 각각의 라운드는 한 명의 지정된 제안자가 있을 수 있다) 이러한 메커니즘은 PoW 블록체인에서도 사용될 수 있게 수정할 수 있다. 가령, 합의에 참여하는 노드들이 실시간으로 그들의 퍼블릭 키 위에 PoW 해답을 발행할 때, 그들 스스로가 ‘제안자라고 선언’하는 메시지를 함께 서명하여 발행하는 방법을 사용할 수 있을 것이다.
하지만 동기성 가정은 매우 강한 조건이기에, 우리는 33% 또는 50% 장애허용보다 더 높은 수치가 필요 없는 환경에서는 동기성 가정 없이도 잘 동작하는 시스템을 설계하고자 한다. 이를 달성할 수 있는 방법이 있다. 합의결과가 ‘때때로-온라인’인 관측자들에 의해서 관측될 수 있는 다른 합의 알고리즘(예. PBFT, Casper FFG, chain-based PoS)을 가정해보자. (이 알고리즘을 ‘임계치 의존적 합의 알고리즘’(threshold-dependent consensus algorithm)이라고 부르고, 반대되는 개념인 앞서 설명한 합의 알고리즘을 ‘시간지연 의존적 합의 알고리즘’(latency-dependent consensus algorithm) 이라고 부르겠다.) 임계치 의존적 합의 알고리즘이, 체인에 새로운 블록들을 일정한 속도로 ‘확정(finalizing)’하는 모드로 계속해서 실행되고 있다고 가정하겠다. (즉, 확정된 값은 이전에 확정된 값을 “부모”로 가리키게 된다. 만약 A -> … -> B와 같은 연속된 포인터가 있다고 가정하면, 우리는 A를 B의 자손이라고 부를 수 있다.)
우리는 ‘항상-온라인’인 관측자들에게 ‘강한 확정성’을 지니는 체크포인트에 대한 접근 권한을 줌으로써, 시간지연 의존적 알고리즘을 ~95% 장애허용 구조로 개조할 수 있다. (더 많은 관측자를 추가하고 더 긴 시간동안 블록을 처리하도록 하면 장애허용을 거의 100%에 가깝게 올릴 수 있다.)
시간이 4096초의 배수에 도달할 때마다, 512개의 랜덤 노드들을 선택해서 합의에 참여하도록 함으로써 시간지연 의존적 알고리즘을 실행할 수 있다. 임계치 의존적 알고리즘에 의해 확정된 값들로 구성된 체인은 유효한 제안이 될 수 있다. 만약 한 노드가 T + k * D(D = 8초)시각 이전에 k개의 서명이 포함된 확정된 값을 본다면, 해당 노드는 본인이 알고있는 체인집합에 해당 체인을 넣고 본인의 서명을 추가하여 다시 브로드캐스팅할 것이다; 관측자들은 T + (k — 0.5) * D를 시간제한 임계치로 사용하게 된다.
마지막에 사용될 ‘선택’ 함수는 간단하다:
- 이전 라운드에서 이미 확정된 값이라고 동의한 값의 자손이 아닌 확정값들은 무시됨
- 유효하지 않은 확정된 값들은 무시됨
- 두 개의 유효한 확정된 값들이 존재하면, 해시값이 더 낮은 것을 택함
만약 관측자들의 5%가 정직하고, 512개의 랜덤하게 선택된 노드들중에 정직한 노드가 하나도 없을 확률은 대략 1조 분의 1이 된다. 네트워크 시간지연과 시계 오차의 합이 D/2보다 작다는 조건이 있다면, 심지어 임계치 의존적 알고리즘의 장애허용 조건이 만족되지 못해 상충하는 여러 개의 확정값들이 존재하더라도, 위의 알고리즘은 특정한 하나의 확정값을 가리키도록 잘 동작할 것이다.
만약 임계치 의존적 합의 알고리즘의 장애허용 조건이 만족된다면(보통 50% 또는 67%가 정직하다고 가정), 임계치 허용 합의 알고리즘은 그 어떤 새로운 체크포인트도 확정하지 못하거나, 서로서로 호환가능한(예를 들어, 체크포인트들이 줄지어 있고, 이전의 체크포인트가 이후의 체크포인트의 부모가 되는 상황) 새로운 체크포인트들을 확정할 수 있게 된다. 그래서 네트워크 시간지연이 D/2(심지어 D까지도)를 초과하여 시간지연 의존적 알고리즘에 참여하는 노드들이 본인이 수락한 값에 대해 합의를 이루지 못하더라도, 각각이 수락한 값들은 여전히 같은 체인에 포함되어 있어서 실질적인 불일치는 없도록 할 수 있다. 미래의 라운드에서 시간지연이 정상상황으로 복구되면, 시간지연 의존적 합의는 ‘동기화’된 상태로 복구될 것이다.
만약 임계치 의존적 합의와 시간지연 의존적 합의에 대한 가정이 둘 다 동시에(혹은 연이은 라운드에 대해서 각각) 깨져있다면 알고리즘은 동작하지 않는다. 예를 들어 한 라운드에서 임계치 의존적 합의가 Z -> Y -> X를 확정지었고, 시간지연 의존적 합의가 Y와 X의 사이에 대해 동의하지 않으며, 이 다음 라운드에서 임계치 의존적 합의가 X의 자손 W(Y의 자손이 아님)를 확정지었다고 가정해보자. 시간지연 의존적 합의에서 Y에 동의한 노드들은 W를 받아들이지 않을 것이다. 그러나 X에 동의한 노드들은 W를 받아들일 것이다. 안타깝게도 이러한 일은 피할 수 없다. 1/3초과 장애허용을 가지는 ‘비동기하의 안전한 합의’에서의 불가능성(위와 같은 케이스)은 비잔틴 장애 허용 이론에서 이미 잘 알려져 있는 사실이다. 이는 심지어 오프라인이 될 수도 있는 관측자들로 이루어져 있고, 동기화 가정까지 만족하는 1/2 초과 장애허용 시스템에서조차 불가능한 일일 것이다.
[Hashed Community]
Hashed Website: hashed.com
Facebook: facebook.com/hashedfund
Medium: medium.com/hashed-official
twitter: twitter.com/hashed_official
Telegram: t.me/hashedchannel
