[리서치] Hedera Hashgraph part 2
#Hedera Hashgraph #Gossip protocol #이더리움연구회
작성일 : 2019.01.14
Research by ‘이더리움 연구회’
(이더리움 연구회 : www.etherstudy.net )
앞선 리서치에서는 해시그래프의 주요 특징 중 두 가지인 가십프로토콜(Gossip Protocol)과 가상투표(Virtual Voting)를 예시를 통해 살펴보았다. 이번 글에서는 더욱 자세한 이해를 위해 해시그래프에서 공개한 수도코드를 통해 알아보고자 한다.
해시그래프는 아래와 같은 순서로 진행된다.
HashGraph의 가장 큰 특징 두가지가 있다.
1. 가십 프로토콜(Gossip Protocol)
2. 가상 투표 (Virtual Voting)
이 두가지를 활용하여 기존 BFT가 가지고 있던 문제점을 훌륭히 해결했다고 말한다. 이들은 진짜 투표하는게 아닌 이미 서로 답을 알고있기에 투표를 했다고하고 넘어가는 가상 투표를 통해서 처리량을 줄였다. 또한, Paxos나 Raft 그리고 텐더민트와같이 리더가 있고 그 밑에 노드가 있는 구조가 아니기 때문에 리더의 디도스공격과 같은 것들로부터 안전하다고 한다.
Alice가 가지고있는 HashGraph A와 Bob이 가지고 있는 HashGraph B가 있다고하자. 이들은 어떠한 순간에는 조금 다른 HashGraph를 가지고 있을 수 있다. 그러나 똑같이 될것이다. 여기서 똑같다는 의미는 가령 A와 B 둘다 이벤트 x를 포함하고있다면 그들은 정확히 같은 x의 선조 이벤트들을 포함한다는 것이다. 결국 같은 edge들을 가지고있다는 것이다.
이들은 서로가 정직하다면 각자가 모르는것을 서로로 부터 가십 프로토콜을 통해 빠르게 배울 수 있다.
위 수도코드에서는 ‘sync all known events to a random member’가 가십프로토콜이 작동되는 부분이라고 할 수 있다. 랜덤 멤버들에게 알고있는 이벤트의 정보를 싱크하는 것이다.
가십 프로토콜(Gossip Protocol)
가십 프로토콜은 해시그래프에서 처음 제시한 개념이 아니다. 기존 클라우드 컴퓨팅이나 분산 네트워크 환경에서 분산된 네트워크에게 데이터를 효율적으로 전달하기 위한 개념으로 등장하였다. 이 개념은 해시그래프 뿐만 아니라 대표적으로 하이퍼레저 패브릭에서도 사용하고있다.
가십프로토콜에서는 내가 알고있는 정보를 B에게 전달하되 나는 알지만 B는 모르는 정보만 전달하고, 반대로 B역시 나에게 정보를 알려준다. 그러나 패브릭과 해시그래프는 가십의 전달 방식에서 조금 차이가 있다.
위 그림은 패브릭의 WorkFlow이다. 피어 중에서도 리더 피어가있으며 리더 피어가 가십을 받아서 나머지 피어들에게 퍼트리는 역할을 한다. 그림을 보면 피어끼리는 연결이 안되어있는 것을 볼 수 있다.
해시그래프의 가십 프로토콜 그림을 보자.
일단 해시그래프에서는 리더가 존재하지 않는다. 모든 노드가 동등한 위치에 있으며 랜덤으로 아무나 선정해서 가십을 보낸다.
네트워크에 참여하는 모든 노드들은 내가 모르는 이벤트 정보를 랜덤의 노드에게 받고 또 나만 알고있는 이벤트 정보를 랜덤으로 다른 랜덤의 노드에게 보내면서 노드들이 공통의 해시그래프를 가지게 된다. (해시그래프란 가십을 저장하는 데이터구조이다.)
공통의 해시그래프를 가진다는 것은 공통된 원장을 가진다는 것이다.
백서의 수도코드를 풀어서 이야기해보자.
1. 각 멤버는 다른 멤버를 랜덤으로 선택하고 서로 병렬로 싱크를 맺는다.
2. 앨리스가 밥에게 싱크를 했을때 앨리스는 자기가 알고있고 밥은 모르는 모든 이벤트를 보낸다.
3. 밥은 이러한 이벤트들을 해시그래프에 추가한다.
4. 추가할때는 유효한 자기의 부모 이벤트 해시값이 유효한 이벤트만 추가한다.
— 앨리스는 랜덤으로 다른 멤버 밥을 선택한다. 그리고 그에게 그녀가 알고있는 모든 이벤트들을 가십한다. 밥은 유효한 가십을 기록하기 위해 새 이벤트를 만든다. 이것만으로 BFT를 만족시키기에 충분하지만 효율성을 올리기 위해 해시그래프에서는 여러 방법을 추가하였다.
— 앨리스와 밥은 그들이 이미 알고있는 정보를 서로 얘기할 것이다. 그러면 앨리스는 자기는 알지만 밥은 모르는 정보를 보낸다. 프로토콜은 앨리스가 위상적인 순서로 이벤트들을 보내고, 밥은 그 이벤트를 받기 전에 이벤트의 부모를 보유하도록 요구한다.
— 앨리스는 동시에 여러 멤버들과 싱크한다.
싱크를 마치고 나서, 맴버는 최대한 여러 이벤트들에 대한 합의를 위해 가상 투표를 진행하고 가상투표 투표가 진행되며 합의가 되는데 세 가지 프로세스를 거치게 된다.
가상투표 (Virtual Voting)
해시그래프의 합의 알고리즘은 BFT기반의 알고리즘이라고 할 수 있다. 네트워크의 전체 참여자의 2/3 이상이 동의하면 올바른 이벤트로 받아들이고 그 이하면 아니게 된다. (본문에서는 Supermajority라고 이야기 한다)
가상투표란 투표하는 과정이 네트워크에서 일어나는게 아니라 로컬에서 일어난다는 것이다. 또한 투표 결과를 다른 노드에게 전달하지않는다. 그냥 yes/no만 가지고 있을 뿐이다. 따라서 네트워크에서 노드가 하는 일이 매우 적어지므로 투표를 전파하는데 걸리는 복잡도가 없다.
백서에서는 다음을 가정하고있다.
1. 1개의상의 n개의 멤버가있을때 2n/3 이상의 노드는 정직한노드, n/3이하의 노드는 악의적이다.
2. 모든 시스템은 비동기다. 네트워크 안정성과 전송 timeout 등은 고려하지않는다.
3. 공격자는 메세지를 삭제하거나 지연시킬수있도록 모든 네트워크를 통제할 수 있다.
위의 수도코드에서 앞서 말한 세 가지 프로세스인 ‘divideRounds’, ‘decideFame’, ‘findOrder’ 함수들이 가상투표가 진행되면서 실행된다.
맨 위 수도코드를 풀어서 설명하면 다음과 같다.
1. 알려진 모든 이벤트들은 라운드안에서 나누어진다.
2. 증인이라고 불리는 각 라운드의 첫번째 이벤트들은 local 비잔틴 동의기반 가상 투표에 의해 유명한 증인이 될지 안될지 결정된다.
3. 충분한 정보를 가지고 이벤트들의 전체 순서를 매길수있다. 만약 두개의 멤버들이 독립적으로 이벤트의 순서를 할당하면, 그들은 다른 정보가 들어와도 절대 변하지 않을 같은 위치에 할당된것을 보장받는다.
4. 각 이벤트는 확률이 1인 위치에 할당된다.
해시그래프의 합의에서는 투표과정에서 라운드를 나눈 후, 유명 증인을 결정하고, 유명 증인이 결정되면 투표 결과를 통해 2/3 이상이 동의하에 timestamp를 찍고 이벤트들의 순서를 결정한다.
그리고 다시 다음 라운드를 진행하고 위 프로세스를 계속 실행한다. 모든 네트워크의 모든 이벤트들이 싱크가 되고 투표를 통해 합의 결과가 도출될때까지 진행된다. (이때 BFT의 확률 1이란 모든 이벤트들이 다 다른 증인들에게 보이게 되는 것을 말한다.)
해시그래프는 모든 참여자가 투표를 하지 않는다. 해시그래프에는 이전글에서 설명한 증인과 유명한 증인이라는 개념이있는데, 이 증인들이 투표를하여 이벤트가 유효한지 검사한다. 증인은 각 라운드의 첫번째 이벤트를 말한다. 유명한 증인은 증인들을 잘 볼수 있는 증인이다.
divideRounds를 살펴본다.
조상의 이벤트에 대해 각 이벤트의 라운드 넘버를 정의한다. divideRounds에서, 모든 알려진 이벤트에는 조상의 라운드 수에 대한 함수로v 정수 round number (정의 5.2)가 지정된다.
정의5.2: x의 round number는 r + i로 정의 될 수 있다. r은 x의 부모의 최대 라운드 넘버이고(부모가 없다면 1이다) i는 x가 라운드 r에서 2n/3 이상의 증인을 strongly see 할 수 있다면 1이고, 그렇지 않다면 0이다.
즉 이벤트 x가 round R에서 2/3 이상의 증인들을 ‘strongly see’ 할 수 있다면 다음 라운드로 넘어간다.
해시그래프에서 strongly see 할 수 있고, famous 증인인가를 YES/NO로 결정하는 것이 투표이고 선거이다. 다음 예를 통해 좀 더 이해해보자.
Alice 해시그래프 A안에 있는 이벤트를 통해 전체 순서를 계산할 수 있다. 해시그래프에는 선거의 순서가 있다. 각 선거에는, A안에 있는 어떤 이벤트는 투표를 하는 것으로 고려될것이고, 일부는 투표를 받는 것으로 고려될 것이다.
선거는 다음 라운드의 증인들이 그 이벤트를 보았는지 확인하는 작업이다. 이 선거에서 다음 라운드의 각 증인들은 이전 라운드의 증인들이 famous 증인인지 아닌지 투표한다.
Alice는 다수의 선거들을 계산할 것이다. 만약 이벤트가 Bob에 의해 만들어 졌다고하면, 우리는 Bob이 투표를 했다고 말할 것이다. 그러나 실제 멤버 Bob은 포함되어있지 않다. Bob이 실제로 인터넷을 통해 Bob이 Alice에게 보냈다는 투표를 한다면 이것은 순전히 Alice의 로컬에서 계산된다.
Alice가 정직하다면 정직한 가상의 Bob 투표를 계산한다. 만약 Bob이 Cheater라고 해도, Bob은 가상의 Bob을 만들어 올바르지 않은 투표를 통해 Alice를 공격할 수 없다.
Bob은 다른 방법으로 공격할 수 있다. Bob이 이벤트 x를 만든다. 이 이벤트는 그의 이전 이벤트 z의 해시를 포함한다. 그리고 Bob은 새로운 이벤트 y를 만든다. 이 이벤트 y에는 x의 해시가 주어져야 하지만 z가 주어지게 된다. 포크가 되었고 Bob의 그 이벤트는 체인이 될 수 없다. 이 이벤트는 트리가 되어야 한다.
만약 Bob이 Alice와 Carol에게 이벤트 x를 가십한다고하자, 둘은 한동안은 포크를 알지 못한다. 그리고 Alice는 Carol의 y에 대한 가상투표와는 다른 x에 대한 가상투표를 계산할 수 있다. 그래서 포크가 해시그래프를 통해 퍼질 수 있다. 이 경우에는, Alice는 x를 포함하지만 y는 포함하지 않은 해시그래프를 가지고, Carol은 y를 가지고 x를 가지고있지 않은 해시그래프를 가지게된다. 포크가 되었기에 그들은 어떤게 맞는지 알 수 없는 순간이 있다.
해시그래프 합의 알고리즘은 이러한 공격을 ‘seeing’과 ‘strongly seeing’를 사용하여 예방한다.
이 둘은 모든 이벤트는 그 자체의 조상이자 자기의 조상으로 간주된다는 조상과 자기 -조상의 정의를 기본으로 한다.
만약 Bob이 x, y 두개의 이벤트를 만들었다고 하자. 이 둘은 서로의 자기-조상이 아니며 Bob은 fork를 통해 치팅한것이다. 만약 어떤 이벤트 w가 x를 조상으로 가지고 있고 y를 조상으로 가지고 있다고하면, 이벤트 w는 이벤트 x를 볼 수 있다. 그러나 x, y 둘다 w의 조상이라고 하면 이벤트 w는 x, y중 하나를 보지 못하거나 같은 creator가 다른 이벤트를 보지 못하도록 정의된다.
만약 n개의 맴버가 있고, 이벤트 w가 다른 멤버들의 2n/3 이상의 이벤트를 볼수있다면 x를 strongly see 할수있고 각 이벤트는 x를 볼 수 있다.
맨위 yellow이벤트는 맨 아래 orange이벤트들중 하나를 strongly see 할 수 있다. 5개의 멤버가 있다. 2n/3 보다 큰 가장 작은 수는 4이다. 그림 d에서 하나의 orange이벤트는 중간의 red 이벤트와 yellow 이벤트의 조상이다. 그러므로 yellow 이벤트는 orange 이벤트를 strongly see 할 수 있다. 만약 4개의 모든 orange이벤트와 yellow이벤트의 부모들이 라운드 r에 만들어졌다면, yellow이벤트는 r+1 라운드에 만들어진것이다. 라운드 r의 서로 다른 2n/3 이상의 증인을 strongly see 할 수 있기 때문이다. 모든 이벤트는 그 자체의 조상과 자기-조상으로 정의된다.
다시말해서, d에서 yellow 이벤트는 4개의 다른 멤버들의 red 이벤트를 볼 수 있다. 또한 a, b, c에서도 4개 이상의 red 이벤트를 볼 수 있다.
이런 컨샙이 실제 투표 없이 단순 로컬 가상 투표로만 BFT를 이룰 수 있도록 한다. 가상투표에서, 이벤트 x는 YES/NO를 투표한다. 어떤 다른 이벤트가 유명한가 안유명한지를 투표하는 것이다. 투표는 순전히 x의 조상 함수로 계산된다. 투표는 오직 x로 부터 내려온 자손 w가 x를 strongly see 할수있는가가 고려 대상이다.
이벤트 x, y가 비정상적인 포크로 인해 다른 브랜치에 있다면, w는 x, y중 하나만 strongly see 할 수 있다. 둘다 할수는 없다. 만약 해시그래프 A, B가 모두 일치하다면, 해시그래프 A에서 하나의 이벤트가 x를 strongly see 할 수 없고, 해시프래프 B에서 다른 이벤트가 y를 strongly see 할 수 없다.
이것은 공격자가 포킹을 통해 공격을 시도하려할때, 다른 멤버들이 다른 주문을 결정할 수 없도록 한다. 역사적으로, 몇 비잔틴 동의 알고리즘들은 그들이 받은 각 투표바다 “Receipts”를 발송하여 앨리스가 밥과 캐롤에게 일관성없는 투표를 보내는 것을 막도록했다.
이 공격과 해시그래프 포킹 공격 그리고 receitps와 strongly see를 사이에는 연관성이 있다.
Sum-up
위에서 설명한 내용을 정리하면 다음과 같다.
1. 다음 라운드에서 이전 라운드 이벤트 x를 2n/3명 이상이 봤다고 하면 x는 famous 증인이다.
2. 자손 이벤트 w가 조상 이벤트 x를 봤다 -> 이벤트 w는 famous하다고 YES라고 투표한다.
3. 모두에게 YES 표를 받았다고 해서 현재 famous 증인은 아니다. -> 다음 라운드에 투표를 계산해야한다.
4. w는 x를 strongly see 한다 -> w가 x를 보기 위해 2n/3명 이상 지나간다.
5. 다음라운드에서 w가 정말 strongly see 하는지 확인한다. -> 확인 결과 2n/3명 이상 YES가 확인되면 x는 famous 증인이된다.
라운드는 증인들이 투표하고 결과가 받아들여지기까지가 한 라운드이다.
DecideFame
다음으로 decideFame 과정을 한번 살펴보도록한다.
특정 멤버의 경우, 각 라운드에서 첫 번째로 생성되는 이벤트를 증인이라고한다. 가상 투표를 보내고 받는 것은 오직 증인 이벤트이다. 이 과정(가상 투표를 보내고 받는)은 비잔틴 동의가 필요하다. 각 증인들은 증인이 famous 한지 여부를 결정한다.
증인은 많은 증인들이 다음라운드에서 그 증인을 볼 수 있으면 유명하다. 비잔틴 동의 프로토콜이 각 증인들이 유명한가를 투표를 할때 돌아간다. 라운드 r의 증인 x가 있고, 각 증인은 r+1라운드에 있으면 각 증인들은 x를 볼 수 있으면 x가 famous 하다고 투표할 것이다. 만약 2n/3 이상의 멤버가 유명하다고 투표한다면 투표는 종료된다.
투표가 균형을 이루면 필요에 따라 많은 라운드가 진행되며, 이전 라운드에서 strongly see 할수있는 다수의 증인들에 의해 normal round 투표로 진행된다.
인터넷을 컨트롤하는 공격자에 대항하기 위해, 주기적으로 coin round가 있다. coin round에서는 증인이 pseudorandomly 투표를 할 수 있다. 이것은 공격자가 투표를 조심스럽게 나누기 위해 인터넷 상에서 모든 메세지를 컨트롤 할 수 있다고 해도, 커뮤니티가 2n/3의 임계치를 임으로 초과할 가능성이 있음을 의미한다. 그리고 2n/3에 도달하면 확률은 1이된다.
알고리즘은 d=1에서 d=2로 바뀌면 진행된다. 만약 모든 증인의 famous 여부가 결정거나 2n/3 보다 작거나 같은 멤버들이 투표했다면 알고리즘은 다시 돌아간다. 이 알고리즘에서 이 백서의 모든 theorem들은 BFT의 증명을 포함하여 모두 true가 된다.
새로운 선거를 위한 라운드 trigger는 합의 시간의 20%정도 증가시킨다. 그러나 그것은 매우 적게 일어날 것이고 그것이 일어난다면 공평성을 늘리기 위해 증인의 수를 늘린다.
한 라운드에서 증인이 유명한가에 대한 합의가 이루어지면 오래된 이벤트들의 전체 합의 timestamp와 합의 순서를 정하는 것은 쉽다.
라운드에서 증인들이 아닌 이벤트들을 유명 증인들이 이벤트들에 대해서 timestamp를 찍어서 합의를 마친다. 이 과정을 findOrder라고 한다.
(여기서 증인들이 나머지 이벤트들에 timestamp를 찍는 과정이 정확히 설명되어있지가 않다. )
FindOrder
FindOrder에서는 라운드 r에서 모든 증인들의 famous함이 결정되고 나면 famous 증인의 집합을 찾고, 다른 famous 증인과 같은 creater인 famous 증인은 삭제되고 남은 famous 증인들이 unique famous witness이다.
unique famous 증인들이 이벤트들의 timestamp를 찍고 합의를 마친다.
timestamp는 이벤트 x에 수신 된 라운드의 r과 해당 구성원이 처음 수신 한 시간의 중앙값이다. 합의를 마치면 변경되지않는다.
Conclusion
해시그래프에서는 투표가 네트워크 안에서 이뤄지는게 아니라 로컬에서 계산하고 계산 결과만 네트워크에 뿌린다. 이를 통해 네트워크 안에서 이뤄지는 연산량은 줄어드는 게 맞는 것 같다. 또한, 모든 증인이 라운드 내에서 투표하는게 아니라 유명 증인이 투표하는거니 투표량도 줄어들 것이다.
이미 존재하는 가십 프로토콜을 활용하여 모든 노드들의 원장을 일치화 하고, 일치하는 과정에서 BFT를 사용해서 2/3 이상이 동의한 이벤트만 올바른 이벤트로 확정을 짓게 되는 것이고, 그 2/3 이상이 동의한다는 투표를 로컬에서 진행하여 BFT의 속도를 높힌다.
이것이 HashGraph의 동작 방식이다.
이더리움 연구회의 1,2,3,4기 정기 발표나 향후 업데이트 되는 5기 연구 자료는 http://etherstudy.net을 통해서 확인 하실 수 있습니다.
