[리서치] Hedera Hashgraph

이더리움 연구회

Published in

ether study

13 min readJan 16, 2019

#Hedera Hashgraph #Gossip protocol #이더리움연구회

작성일 : 2019.01.14
Research by ‘이더리움 연구회’
(이더리움 연구회 : www.etherstudy.net )

1. 개요

Hedera Hashgraph(이하 해시그래프)는 블록체인의 블록 생성과 같은 개념이 아니다. 해시그래프는 트랜잭션들이 연결되어있는 자료구조 형태를 가진다.

해시그래프에서는 두 가지 개념을 강조한다. 각각 Gossip Protocol(가십 프로토콜)’, ‘Virtual Voting(가상 투표)’이다.

해시그래프는 이 두가지 개념을 활용하여 기존 BFT 구조의 블록체인이 가지는 문제점을 해결할 수 있다고 한다. 기존 BFT는 투표를 할 때 많은 시간이 걸리지만 해시그래프는 진짜 투표를 하지 않고 이미 서로 투표를 어떻게 할지 알고 있다고 가정하고 가상으로 투표하여 넘어간다.

이는 Paxos나 Raft, 텐더민트와 같이 리더와 리더 아래 하위 노드가 있는 구조가 아닌 동등한 노드이므로 디도스(DDoS) 공격에서 안정하다고 한다.

2. Core Concept

해시그래프를 좀 더 깊게 살펴보면 다음과 같은 Core Concept을 가지고 있다. 이를 잠시 짚고 넘어가자.

Transaction

Any member can create a signed transaction at any time. All members get a copy of it, and the community reaches Byzantine agreement on the order of those transactions.

언제든 트랜잭션을 만드는 멤버다. 모든 멤버는 트랜잭션의 복사본을 가지고있고, 모든 커뮤니티는 트랜잭션 순서에 따라 비잔티움 동의에 다다를것이다.

Fairness

It should be difficult for a small group of attackers to unfairly influence the order of transactions that is chosen as the consensus.

소규모 집단의 공격자가 합의로 이루어진 트랜잭션에 악영향을 미치는 것은 어렵다.

Gossip

Information spreads by each member repeatedly choosing another member at random, and telling them all they know.

정보가 퍼진다 각자 멤버가 서로 반복적으로 서로 다른 랜덤으로 선택한 멤버에게. 그들이 아는 모든걸 말한다.

Hashgraph

A data structure that records who gossiped to whom, and in what order.

가십이 저장되는 자료구조

Gossip about gossip

The hashgraph is spread through the gossip protocol. The information being gossiped is the history of the gossip itself, so it is “gossip about gossip”. This uses very little bandwidth overhead beyond simply gossiping the transactions alone.

해시그래프는 가십 프로토콜에 의해 퍼진다. 가십된 정보는 가십 그 자체의 history이다. 그래서 가십 about 가십이라고 한다. 이는 트랜잭션 하나를 가시핑하는 것과 같이 매우 적은 오버해드를 가진다.

Virtual voting

Every member has a copy of the hashgraph, so Alice can calculate what vote Bob would have sent her, if they had been running a traditional Byzantine agreement protocol that involved sending votes. So Bob doesn’t need to actually her the vote. Every member can reach Byzantine agreement on any number of decisions, without a single vote ever being sent. The hashgraph alone is sufficient. So zero bandwidth is used, beyond simply gossiping the hashgraph.

모든 멤버들은 해시그래프의 복사본을 가지고있다. 앨리스와 밥이 투표하는 것에 대한 비잔티움 동의 프로토콜을 실행하고있었다면 투표 내용을 계산할 수 있다. 그래서 밥은 실제로 엘리스에게 투표할 필요가 없다. 모든 회원은 실제 투표할 필요 없이 여러 결정에 대한 비잔티움 동의에 이를 수 있다. 해시그래프만있으면 충분하다.

Famous witnesses

The community could put a list of n transactions into order by running separate Byzantine agreement protocols on O(n log n) different yes/no questions of the form “did event x come before event y?” A much faster approach is to pick just a few events (vertices in the hashgraph), to be called witnesses, and define a witness to be famous if the hashgraph shows that most members received it fairly soon after it was created. Then it’s sufficient to run the Byzantine agreement protocol only for witnesses, deciding for each witness the single question “is this witness famous?” Once Byzantine agreement is reached on the exact set of famous witnesses, it is easy to derive from the hashgraph a fair total order for all events.

커뮤니티는 이벤트 x가 이벤트 y이전에 온거니?처럼 생긴 yes/no 로 대답할수있는 O(nlogn)개의 질문에 관한 비잔티움 동의 프로토콜의 실행에 의해 n개의 트랜잭션을 순서대로 배치할 수 있다.
더 빠른 접근은 증인이라고 불리는 단지 몇개의 이벤트들을 고르는 것이다. 그리고 해시 그래프가 생성 된 직후 대부분의 멤버가 트랜잭션을 수신했다는 것을 보여주는 경우 이 증인을 Famous 증인이라고 정의한다. 그러면 “이게 Famous 증인이니?”라는 하나의 질문에 대한 대답만으로도 각 증인이 비잔틴 동의 프로토콜을 실행하기 충분하다.

Strongly seeing

Given any two vertices x and y in the hashgraph, it can be immediately calculated whether x can strongly see y, which is defined to be true if they are connected by multiple directed paths passing through enough members. This concept allows the key lemma to be proved: that if Alice and Bob are both able to calculate Carol’s virtual vote on a given question, then Alice and Bob get the same answer. That lemma forms the foundation for the rest of the mathematical proof of Byzantine agreement with probability one.

해시그래프에서 주어진 두개의 정점 x, y에서 x는 y를 strong see 할수있다는 것이 바로 계산된다. 충분히 많은 멤버들에 의해 여러 길로 연결되어있으면 true이다. 이 개념은 key lemma가 증명되도록 한다. Alice와 Bob 둘다 Carol의 가상 투표를 계산할 수 있으면 질문에 같은 대답을 얻을 수 있다. 이 lemma는 비잔팁 동의 확률 1의 수학적 증명의 나머지 부분의 기초를 형성한다.

3. Gossip Protocol

해시그래프가 가지고 있는 가장 중요한 두 개념을 통해 해시그래프가 어떻게 합의를 하는지 알아보았다. 먼저 가십 프로토콜이다.

가십 프로토콜은 사실 해시그래프에서 처음 제시한 개념이 아니다. 기존 클라우드 컴퓨팅이나 분산 네트워크 환경에서 분산된 네트워크에게 데이터를 효율적으로 전달하기 위한 개념으로 등장하였다. 하이퍼렛져의 Fabric에도 가십 프로토콜 개념이 사용된다. Fabric은 리더 피어가 존재 하고 리더 피어가 가십을 받아서 나머지 노드에게 퍼트리는 역할을 한다. 해시그래프는 리더가 존재하지 않으며 모든 노드가 이벤트를 주고받는다.

해시그래프에서의 가십 프로토콜이 어떻게 동작하는지 예시를 통해 더 자세하게 알아보자.

여기 4개의 노드가 있다.(이들은 정보를 모두 가지고 있는 풀노드(Full-node)이다.) 이 각각의 노드는 이벤트(event)를 생성한다. 이벤트는 메모리 안에 있는 작은 데이터 구조로써 0개 혹은 이상의 트랜잭션들을 담고 있다.
해시그래프의 합의알고리즘은 이벤트의 순서를 합의하는 것과 각 이벤트의 합의를 타임스탬프로 기록한다. 이는 공격자가 합의를 변경하는 것이 어렵도록 한다. 따라서 앞서 말한 디도스 공격 등을 방지하여 더욱 안전한 네트워크를 만들기 위함이다.

다음의 예제에서는 B가 랜덤하게 D를 선택하여 이벤트를 보내는 것으로 시작한다. D는 현재 인터넷으로 B와 연결이 되어있지만 이벤트를 보낸 것을 인지 못하고 있다.

인지를 D가 하게 되면 D는 새로운 이벤트를 생성한다. 이후 B와 D가 어떻게 통신을 했는지 이벤트에 기록한다. D는 이제 2개의 해시를 담게 된다. (Self-parent: D의 첫 이벤트, other-parent: B의 첫 이벤트)

D가 이벤트를 만들게 되면 이 이벤트에는 다음과 같은 것들이 기록이 된다.
- D가 이벤트를 생성했을 때의 타임스탬프
- D가 네트워크로 보내고 싶은 트랜잭션들
- Self-Parent의 해시(이 경우 D의 첫 이벤트)
- Other-parent의 해시(이 경우 B의 첫 이벤트)

이후 D는 생성된 이벤트를 B에게 전달하게 된다. 따라서 B는 새로운 이벤트를 생성하고 이를 기록하게 된다.

B는 현재 자신한테 온 이벤트와 A에게 보내는 이벤트까지 총 4개의 이벤트를 A에게 보내게 된다. 앞선 과정과 같이 A는 새로운 이벤트를 만들게 된다.

이렇게 이벤트를 랜덤한 노드에게 전파하는 과정이 지속되면 그래프처럼 되어있는 암호학적 해시들이 길게 이어지게 된다. 이를 해시그래프라 부른다.
각 이벤트들은 이때 이전의 이벤트의 내역을 가지고 있다.

4. Virtual Voting

해시그래프에서는 랜덤한 노드에게 전파를 하여 이벤트가 진행이 되는 가십프로토콜을 각 이벤트에 따라 라운드로 정의한다. 각 라운드 안에서 실제 투표가 아닌 가상투표(Virtual Voting)을 통해 최종 합의를 이루게 된다.
이 때 각 Child 이벤트는 Parents 이벤트가 생성이 되기 전까지는 라운드를 만들 수 없게 했다.

본 예시에서는 A가 생성한 라운드의 첫 이벤트를 증인(Witness)라고 부른다. (위 예시에서는 A1, A2, A3가 해당된다.) 라운드에서 증인은 꼭 있는 것이 아닌 있을 수도 없을 수도 있다.

다음과 같이 각 라운드에 증인이 결정이 되면 해시그래프에서는 이 증인이 제대로된 증인인지를 판단하게 된다. (해시그래프에서는 Famous Witness라고 표현한다.) 유명한 정도를 판단하기 위해서 각 라운드 안에서 선거(Election)이 진행이 된다. 이때 각 노드는 공평한 위치에 있으므로 같은 선거권을 가진다.

위 예시를 토대로 선거를 진행해보자. 맨 좌측의 그림의 경우 증인 A3는 B2의 이벤트 내역을 볼 수 있다. 이때 B2는 A3의 조상이고, A3는 B2의 후손이다. 내역을 본 후 A3는 YES라고 투표를 한다.
마찬가지로 가운데 그림을 통해 B3는 B2를 보고 YES라고 투표를 하게 된다.
다음으로 C3는 B2를 보고 YES라고 투표를 하게 된다.

마지막으로 D3는 B2를 보고 YES라고 투표를 하게 된다.
다음과 같은 선거과정을 라운드 안에서 진행하여 4명의 증인이 모두 YES로 투표를 했다. 투표결과 B2가 충분히 유명하다고 결론을 내리게 된다.
유명해진 B2를 Finalize하기 위해 다음 라운드의 증인은 이전 투표를 카운트하게 된다. 여기서는 B4와 D4가 진행하며, A4와 C4가 생성이 되면 이들도 투표를 카운트하게 된다.