[블록체인]PBFT

- 비잔티움 장군 문제가 발생할 수 있는 상황에서도 네트워크 합의를 보장하는 알고리즘

= 네트워크에 배신자 노드가 어느 정도 있다고 해도 네트워크 내에서 이루어지는 합의의 신뢰를 보장하는 알고리즘

- Safety를 확보하고 Liveness를 일부 희생하면서, 비동기 네트워크에서도 합의를 이룰 수 있는 알고리즘

- 비동기 네트워크에서 배신자 노드 f개가 있을 때, 총 노드 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘

1. 클라이언트가 상태 변환 요청 메시지 m을 Primary Node에게 전송

2. Primary Node가 상태 변환 요청을 받으면 Pre-prepare 절차 시행

해당 상태 변환 요청에 해당하는 Sequential Number N을 생성

네트워크의 나머지 모든 노드에게 Pre-prepare 메시지 전송

form : <Pre-prepare, V, N, D(m)>

3. 네트워크 내의 임의의 Backup Node i가 Pre-prepare 메시지를 받고 D(m), V, N이 서로 대응되는 값인지 검증한다.

1) 서로 대응되면 prepare 메시지를 생성해 나머지 네트워크의 모든 노드에게 전송한다.

2) 서로 대응되지 않으면 Pre-prepare 메시지를 수용하지 않는다.

form : <Prepare, V, N, D(m), i>

즉, 모든 노드가 메시지를 검증하고 검증한 결과가 참일 경우 자신을 제외한 나머지 노드에게 prepare 메시지를 보낸다.

4. 각각의 노드는 Pre-prepare 메시지와 prepare 메시지를 수집한다.

Pre-prepare메시지가 2f+1개, prepare 메시지가 2f개 이상인 경우를 "prepared certificate"라고 하며, 해당 노드는 "prepared the request" 상태가 된다.

5. "prepared certificate" 건을 만족하는 노드는 네트워크의 모든 노드에게 commit 메시지를 전송한다.

form : <Commit, V, N, i>

6. 각각의 노드는 commit 메시지를 수집한다.

commit 메시지가 2f+1개가 모이면 해당 노드는 "commit certificate" 상태가 된다.

"prepared certificate" + "commit certificate" 일 경우,

해당 노드는 "committed certificate"가 되며, 클라이언트가 요청한 request를 수용해 상태 변화 함수를 시행한다.

-> request를 수용할 경우, 네트워크 어느 노드에서나 상태 변화를 수용했기 때문에 safety를 충족한다.

그러나, 네트워크 합의 요건을 충족하지 못한 request는 기각되기 때문에 liveness를 희생했다고 할 수 있다.

-> 내용상 아무런 문제가 없는 블록이라 해도 2f+1 노드가 인정하지 않으면 체인에 올라갈 수 없다.

728x90

seunghee