스텔라 합의 프로토콜(SCP)
연합 비잔틴 동의(FBA)를 기반으로 한 안전하고 효율적인 합의 메커니즘
1. FBA와 SCP 정의
FBA(Federated Byzantine Agreement)란
개인 노드간이 아닌 복수 노드로 구성된 쿼럼 슬라이스간 합의를 이루는 방식을 의미한다.
개별 노드는 자신이 신뢰하고자 하는 쿼럼 슬라이스를 선택할 수 있다.
SCP(Stella Consensus Protocol)란
연합 투표(federated voting)를 기반으로한 nomination protocol 및 ballot protocol로 구성된 합의 메커니즘을 의미한다.
2. FBA와 SCP 등장배경
FBA 등장 배경
BFT상에서는 합의에 참여하는 전체 노드의 2/3가 내린 결과에 따라 합의가 이뤄진다. BFT하에서 악의적 노드가 전체 노드의 1/3이상의 계정 생성시 네트워크는 보안에 취약해지는 한계가 있다.
반면, FBA상에서는 악의적 노드가 정직한 노드로 구성된 쿼럼 슬라이스에 포함되지 않는 이상 해당 쿼럼 슬라이스 내 합의 과정에 영향을 끼칠 수 없다. 따라서 악의적 노드가 네트워크 공격에 성공하기 위해서는, 정직한 노드로 구성된 다수의 쿼럼 슬라이스가 다수의 악의적 계정을 골고루 편입시킬 수 있도록 해야 한다. 이는 악의적 노드가 단순 BFT 네트워크를 공격하는것보다 훨씬 어렵다.
SCP(Stella Consensus Protocol) 등장 배경
FBA는 쿼럼 슬라이스간 서로 다른 합의 결과를 도출하는 불상사를 방지(즉, safety 보장)하기 위해 쿼럼간 교차(quorum intersection)를 사용한다. 반면, 교차 지점에 속한 노드가 악의적인 노드 일시 해당 노드가 속해있는 두 쿼럼 슬라이스가 합의를 이루지 못하여 올바른 트랜잭션을 처리하는게 중단되는 문제(즉, liveness 보장 불가)가 발생할 수 있다.
SCP는 FBA상에서 safety와 liveness가 보장될 수 있도록 nomination protocol과 ballot protocol을 기반으로 한 스텔라 자체 합의 메커니즘(stella consensus protocol)이다.
(*참고:
safety: 서로 모순된 트랜잭션은 정직한 노드에 의해 절대 받아들이지 않는 상태
liveness: 올바른 트랜잭션은 정직한 노드에 의해 반드시 처리되는 상태)
3. 미리 알아야할 개념; 쿼럼 슬라이스, 쿼럼, 블로킹 셋
쿼럼 슬라이스(quorum slice)
특정 노드가 집합의 합의 결과에 동의하도록 설득하는 노드 집합이다.
노드는 자신이 어떤 쿼럼 슬라이스에 들어갈지 선택할 수 있다.
쿼럼(quorum)
합의를 이루기에 충분한 수의 노드의 집합이다.
쿼럼의 부분 집합이 쿼럼 슬라이스이며, 쿼럼의 노드 수는 쿼럼 슬라이스와 동일하거나 크다.
쿼럼은 해당 쿼럼에 있는 개별 노드가 속해있는 쿼럼 슬라이스를 모두 포함한다.
예를 들어, 위 그림처럼 각 노드간 쿼럼 슬라이스가 화살표로 표시되어있을 시, 초록색으로 표시된 집합은 쿼럼인 반면, 빨간색으로 표시된 집합은 쿼럼이 될 수 없다.
예를 들어, v1에 대한 쿼럼 슬라이스는 {v1, v2, v3} 이며, v2에 대한 쿼럼슬라이스는 {v2, v3, v4}이다.
초록색 쿼럼 집합 {v2, v3, v4}은 v2, v3, v4각각에 대한 쿼럼 슬라이스를 모두 포함하는 반면, 빨간색 쿼럼 집합 {v1, v2, v3}은 v1에 대한 쿼럼 슬라이스만 포함하고 v2, v3에 대한 쿼럼 슬라이스를 포함하지 못하기에 때문이다. 따라서 빨간색으로 표시된 집합은 v1에 대한 쿼럼 슬라이스이지만 쿼럼은 아니다.
v1이 포함되어 있는 쿼럼 집합은 {v1, v2, v3, v4}이다.
블로킹 셋(blocking set)
쿼럼 내 해당 노드 집합 없이는 합의가 불가한 노드 집합이다.
예를 들어, 합의에 대한 임계값이 3인 4개 노드 집합(즉, 4개 노드중 3개 노드 이상만 동의시 합의가 완료됨)에서 어떠한 2개 노드의 조합이든 블로킹 셋이 될 수 있다. 노드 4개 중 2개가 다른 값에 동의할 시 3개 이상의 노드가 동일한 값에 합의하는 것은 불가능하기 때문이다.
예를 들어, 위 그림에서 노드A는 왼쪽 쿼럼 슬라이스에 대해 블로킹 셋 역할을 가진다. 이에 따라 왼쪽 집합은 노드A의 동의없이 합의가 불가하다.
4. Federated voting
Federated Voting은 총 3단계(Vote, Accept, Confirm)로 구성되며, 각 단계별로 쿼럼 슬라이스간 합의를 위해 따르는 규칙이 있다.
Federated voting 규칙 및 프로세스(그림 예시 참고)
쿼럼 슬라이스: {1, 2, 3, 4}, {1, 5}, {5, 6, 7}
쿼럼: {1, 2, 3, 4, 5, 6, 7}, {1, 2, 3, 4}
투표(Vote)
행위: 개별 노드는 처리하고자 하는 트랜잭션 상태에 대해 X값 혹은 Y값에 투표를 하며, 투표 내용을 네트워크에 전파한다.
규칙: 해당 트랜잭션에 이미 투표를 진행한 노드는 기존 투표값과 모순되는 값에 투표하는 것이 불가능하다.
예시 설명: 그림 (a)~(b)에 따라, 각 쿼럼 슬라이스내 개별 노드는 투표를 진행한다.
승인(Accept)
행위: 개별 노드는 아래와같은 규칙에 따른 조건 충족 시 트랜잭션에 대한 X값을 승인한다.
규칙:
자신이 포함된 쿼럼 슬라이스 내 모든 노드가 X값에 투표하였거나 승인하였거나 혹은
쿼럼 슬라이스내 블로킹 셋이 X값을 승인할 경우 노드는 X값 승인한다(노드가 이전에 Y값에 투표했을지라도 X값에 승인할 수 있다.).
예시 설명:
그림(c)에 따라, 쿼럼 슬라이스{1, 2, 3, 4}에 있는 모든 노드는 X값에 투표함에 따라 쿼럼{1, 2, 3, 4}에 있는 노드는 X값을 승인한다.
그림(d)에 따라, 쿼럼 슬라이스{1, 5}에서 노드1(X값 투표 및 승인)과 노드5(Y값 투표)는 서로 상반된 투표 결과를 갖는다. 반면, 쿼럼 슬라이스{1, 5}에서 블로킹 셋인 노드1이 A를 승인했음에 따라 노드5 역시 A를 승인한다.
그림(e)에 따라, 노드6, 7 역시 쿼럼 슬라이스{5, 6, 7}의 블로킹 셋인 노드5의 X값에 대한 승인에 따라 X값을 승인한다.
확정(Confirm)
행위: 개별 노드는 아래와같은 규칙에 따른 조건 충족 시 트랜잭션에 대한 X값을 확정한다.
규칙: 자신이 포한된 쿼럼 슬라이스 내 모든 노드가 X값을 승인할 경우 노드는 X값을 확정한다.
예시 설명: 그림에는 없으나, 노드1, 3, 4, 5, 6, 7 모두 X값을 승인함에 따라 쿼럼{1, 2, 3, 4, 5, 6, 7}은 X값을 확정한다.
Federated voting이 3단계를 거치는 이유
블로킹 셋에 악의적 노드가 존재할 시, 쿼럼 슬라이스는 악의적 노드가 주는 거짓 정보를 기반으로 잘못된 결과에 합의 할 수 있으며, 이에 따라 쿼럼 슬라이스간 동일한 값에 합의하는 것이 불가능해진다.
Federated voting의 3단계에 걸친 투표 방식은 모든 노드가 특정 값에 대해 동의하게 함으로서 safety를 보장한다.
SCP에서 Federated voting이 활용되는 방식
Nomination protocol: 블록체인에 등록할 후보 트랜잭션 집합 선정(즉 처리(proceed)하고자 하는 후보 트랜잭션 집합)
Ballot protocol: 네트워크가 만장일치로 트랜잭션 집합에 대한 상태 값을 확정(처리 완료)
5. 스텔라 합의 프로토콜
스텔라 합의 프로토콜은 후보 트랜잭션 집합을 확정하는 Nomination protocol과 확정된 후보 트랜잭션 집합에 대한 상태를 확정하는 Ballot protocol로 구성된다. 이때 각 프로토콜은 앞서 설명한 Federated voting을 사용함으로서 안전한 합의 상태가 보장되도록 한다.
Nomination protocol
요약
Federated voting을 통해 네트워크에서 처리할 수 있는 유효한 후보 트랜잭션 집합을 선택하기 위한 프로토콜이다.
Nomination protocol을 통해 확정(confirm)된 트랜잭션 집합은 Ballot protocol을 통해 처리됨으로써 최종적으로 스텔라 블록체인에 기록된다.
노드는 Federated voting을 통해 확정된 후보 트랜잭션 집합 발생 시 즉시 해당 트랜잭션 집합에 대해 Ballot protocol을 실행한다.
노드는 한편으로는 앞서 확정된 트랜잭션 집합에 대해 Ballot protocol을 실행하면서도 계속해서 Nomination protocol을 통해 다른 후보 tx집합을 확정하기 위한 Federated voting을 진행한다.
Nomination protocol의 노드간 후보 트랜잭션 집합 수렴(convergence) 방식
개별 노드는 네트워크에서 처리가능한 유효한 트랜잭션 집합을 네트워크에 소개 및 투표(vote)함으로서 해당 트랜잭션 집합에 대한 Federated voting을 진행한다.
노드는 Federated voting을 통해 처음으로 후보 트랜잭션 집합이 확정될 시, 새로운 후보 트랜잭션 집합을 소개 및 투표하는 행위를 멈춘다.
반면 노드는 계속해서 다른 노드에 의해 확정된 후보 트랜잭션 집합 혹은 블로킹 셋이 승인한 후보 트랜잭션 집합을 승인(accept) 및 확정(confirm)한다.
따라서 위와같이 모든 노드가 다른 노드가 확정한 후보 트랜잭션 집합을 확정 시 노드는 모두 동일한 후보 트랜잭션 집합 리스트를 보유할 수 있게 된다.
Ballot protocol
요약
Nomination protocol을 통해 후보 등록이 확정된 트랜잭션 집합(composite value)에 대한 상태를 확실하게 합의하기 위한 프로토콜이다.
Ballot protocol은 'Prepare'와 'Commit' 두 단계로 구성되며, 각 단계는 Federated voting을 통해 진행된다.
Ballot protocol상에서 노드간 합의가 지연될 시(stuck상태), 노드는 다시 새로운 트랜재견 집합에 대한 합의를 시작하거나, 이전에 자신이 투표한 값을 버리고 블로킹 셋이 승인한 값에 투표를 하여 다시 합의를 진행함으로서 liveness를 보장한다(원래 Federated voting에서는 한 번 투표한 값과 상반되는 값에 다시 투표할 수 없음).
Ballot protocol의 Prepare와 Commit
Prepare: 노드의 쿼럼 슬라이스가 유효한 후보 트랜잭션 집합을 갖고 있으며, 이를 commit하고자 하는지를 검증하는 단계
Commit: 노드의 쿼럼 슬라이스가 실제로 해당 트랜잭션 집합을 commit하는 단계
6. SCP기반 합의 프로세스
쿼럼 슬라이스 구조
그림과 같이 두개의 쿼럼 슬라이스가 있다고 가정해 보자. 앞서 설명한 바와 같이 노드 A는 왼쪽 쿼럼 슬라이스에 대한 블로킹 셋이다.
이때 왼쪽 집합은 노드A로 인해 일방적으로 오른쪽 집합에 의존하는 관계를 가짐에 따라 왼쪽 집합은 쿼럼 슬라이스인 반면 오른쪽 집합은 쿼럼이다.
노드A는 쿼럼인 오른쪽 쿼럼 슬라이스에 포함되어 있음에 따라, 노드A의 상태는 오른쪽 쿼럼 슬라이스의 합의 결과에 따라 결정된다. 따라서 왼쪽 쿼럼 슬라이스는 블로킹 셋인 노드A로 인해 오른쪽 쿼럼의 합의 결과에 영향을 받게된다.
합의 라운드는 노드A가 트랜잭션 집합인 txC를 후보로 등록(nominate)하기 위한 투표(vote)를 함으로써 시작된다. 노드A로부터 txC를 소개받은 다른 노드는 txC에 대해 투표를 결정하고, 이에 대한 메시지를 네트워크에 전파한다.
양쪽 쿼럼 슬라이스 모두 노드 A로부터 txC에 대한 메시지를 전파받으며, txC가 유효할 시 txC에 투표(vote)를 한다.
Federated voting에 따라, 쿼럼 슬라이스내 모든 노드가 txC를 후보로 등록하는 것에 투표했을 시 노드는 txC에 대한 후보 등록을 승인(accept)할 수 있다. 따라서 노드는 txC의 후보 등록에 승인한다.
반면, 쿼럼 슬라이스마다 노드간 소통의 질 차이는 다를 수 있다. 오른쪽 쿼럼 슬라이스의 경우 왼쪽 쿼럼 슬라이스보다 크기때문에 노드간 소통 지연으로 인해 쿼럼 슬라이스 전체가 txC를 승인하지 못할 수 있다. 반대로 왼쪽 쿼럼 슬라이스는 블로킹 셋인 노드A 포함하여 모든 노드가 txC를 승인하였음에 따라 왼쪽 쿼럼 슬라이스는 txC를 확정(confirm)한다.
앞서 Nomination protocol에서 설명한 바와 같이, Nomination단계에서 확정된 tx집합은 Ballot protocol의 후보 트랜잭션 집합 리스트에 등록된다. 이처럼 왼쪽 쿼럼 슬라이스는 txC를 후보 리스트에 추가함으로서 txC에 대한 Ballot protocol을 시작한다(왼쪽 쿼럼 슬라이스는 Ballot protocol의 첫 번째 단계인 txC에 대한 prepare을 먼저 진행한다.).
오른쪽 쿼럼 슬라이스는 여전히 ''txC를 후보로 승인"하는 것에 합의가 완료되지 않은 도중에, 쿼럼 슬라이스 내 다른 노드는 새로운 트랜잭션 집합인 txD를 소개 및 투표함으로써 해당 메시지를 네트워크에 전파한다.
txD에 대한 메시지를 전파받은 노드A는 txD가 유효함에 따라 이에 투표(vote)를 한다. 이때 노드A는 확정(comfirm)한 트랜잭션이 없음에 따라 새로운 트랜잭션에 대한 투표가 가능한 반면, 왼쪽 쿼럼 슬라이스는 이미 txC를 확정했음에 따라 새로운 트랜잭션인 txD를 투표할 수 없다.
노드A가 아직 txC를 확정하기 않는 이유는 노드A가 포함된 쿼럼인 오른쪽 쿼럼 슬라이스에서 txC에 대해 확정을 하지 않았기 때문이다.
오른쪽 쿼럼슬라이스내 모든 노드가 txD에 후보 등록 투표를 함에 따라 해당 쿼럼슬라이스에 포함된 노드는 txD에 대해 승인(accept)을 한다.
오른쪽 쿼럼 슬라이스내 모든 노드가 txD에 대해 승인(accept)을 함에 따라 노드는 txD를 확정(confirm)한다. 이때 노드는 특정 트랜잭션에 대한 결정 상태를 네트워크에 전파 시 이전에 투표하거나 승인한 트랜잭션도 함께 전파함에 따라, 노드간 소통이 느려 이전에 전파받지 못한 트랜잭션을 함께 전파받은 노드는 해당 트랜잭션을 자신의 후보 트랜잭션 리스트에 추가한다. 예를 들어, 노드A가 txD에 대한 메시지 전파 시 이전에 승인한 txC에 대한 메시지도 함께 포함하여 전파하기에 오른쪽 쿼럼 슬라이스 노드는 궁극적으로 후보 트랜잭션 리스트에 txC, txD모두 포함하게 된다.
오른쪽 쿼럼 슬라이스 역시 Nominate protocol을 통해 Ballot protocol에서 실행할 후보 트랜잭션이 확정됨에 따라 Ballot protocol을 시작하게 된다. 이때 오른쪽 쿼럼 슬라이스는 txD를 선택하여 Ballot protocol을 시작한다.
오른쪽 쿼럼 슬라이스내 모든 노드가 "prepareD"에 투표를 함에 따라, 해당 쿼럼 슬라이스에 포함된 노드는 "prepareD"를 승인하고 해당 결정을 네트워크에 전파한다.
이때 노드A는 왼쪽 쿼럼 슬라이스의 블로킹 셋임에 따라 왼쪽 슬라이스는 노드A가 "prepareD"를 승인한 메시지를 전파받고 왼쪽 쿼럼슬라이스 노드 역시 이전에 "prepareC"에 투표했음에도 불구하고 "prepareD"를 승인한다.
오른쪽, 왼쪽 쿼럼슬라이스에 포함된 모든 노드가 "prepareD"를 승인함에 따라 쿼럼(오른쪽, 왼쪽 쿼럼 슬라이스의 합집합)은 "prepareD"를 확정한다.
쿼럼이 Ballot protocol에서의 prepare가 완료되면 commit으로 넘어가 Federated voting이 시작된다. 모든 노드가 txD를 처리해도 안전하다는 것에 동의하는 의미로 "commitD"를 확정할 시 노드는 블록체인에 txD기록을 등록한다.
