StateTrie: 최상의 호환성을 위한 해시 트리(hash tree)

희소 머클 트리(sparse Merkle tree) 개선을 통한 더 빠르고 효율적인 상태 인증(state authentication). AERGO Discord 커뮤니티에 참여하세요.

Han Kim

Published in

Aergo blog

19 min readOct 27, 2018

Translated by the AERGO team. English version found here.

https://github.com/aergoio/aergo/tree/master/pkg/trie

지금껏 수많은 스타트업과 연구 기관, 개발자들이 폐쇄적인 블록체인 네트워크를 한 데 엮고 가치와 데이터의 체인 간 연동을 위해 호환성(interoperability)이라는 주제를 탐구해왔습니다. AERGO의 N-티어 아키텍쳐 디자인의 핵심 주제 역시 호환성입니다. 퍼블릭과 프라이빗 블록체인 기술을 연동하며, 이를 기반으로 기업들이 탈중앙화와 데이터 무결성을 비롯한 주요 요소를 타협하지 않고 디앱(dApp)을 만들 수 있는 유연성을 제공하기 위함입니다. 미래 고객사와 사용자들이 다양한 블록체인에 저장된 가치와 데이터를 옮길 수 있게 하려면 체인 간 안전한 커뮤니케이션과 자산 연동(asset bridging)이 필수적입니다. 자산 연동을 위해선 각기 다른 체인의 상태를 효율적으로 확인하고 인증하는 메커니즘이 요구됩니다. 이러한 목표를 이루기 위한 한 가지 방법은 다른 블록체인 상태(자산 이동이 요청된 상태)의 머클 증명(Merkel Proof)을 스마트 컨트랙트를 통해 확인하는 것입니다. 이러한 증명은 스마트 컨트랙트의 가스 사용을 최소화하기 위해 가볍고 효율적이어야 합니다.

이더리움은 상태 데이터를 검증하기 위해 머클 패트리샤 트리(modified Merkle Particia tree)를 사용합니다. 하지만 이더리움의 패트리샤 트리는 16진법 구조인 반면, 각각의 노드는 16개의 하위 구조(child)를 지니고 있습니다. 이런 구조는 이진 트리(binary tree)에 비해 덜 효율적이고 난이도 역시 높습니다. 블록체인 기술 상용화에 필요한 수준의 성능과 속도를 달성하기 위해선 상태 인증이 최대한 효율적이어야 합니다. 우리가 희소 머클 트리(sparse Merkle tree) 구조에 집중한 이유입니다.

우리는 초기 반복 설계 과정에서 표준 희소 머클 트리부터 시작했습니다. 표준 희소 머클 트리는 일정한 간격으로 지속적으로 업데이트될 수 있는 해시트리 구조입니다. 하지만 이런 구조조차도 AERGO 플랫폼에서 요구되는 처리량에는 훨씬 못 미쳤습니다. 표준 희소 머클 트리가 값을 트리 최하단(height= 0)에 저장해 한 키를 업데이트하기 위해선 256번의 해싱 작업이 필요하다는 한계점 때문이었습니다.

AERGO 체인의 처리량을 높이기 위해 우리의 핵심 개발자 중 한 명인 피에르 알랭 오브라(Pierre-Alain Ouvrard)는 희소 머클 트리를 개선함과 동시에, 구현체를 오픈소스로 공개했습니다.

AERGO StateTrie를 공개합니다.

AERGO StateTrie는 빠르고 효율적인 상태 인증을 가능케 합니다. 이번 포스트를 통해 어떻게 구현됐는지, 어떤 특징이 있는지, 그리고 어떻게 사용하는지 자세히 설명하고자 합니다.

AERGO StateTrie는 개선된 희소 머클 트리 구현체로서, 한 개의 키만을 지닌 subtree에 값을 저장합니다. 이를 통해 얻어지는 장점은, 평균적으로 N개의 랜덤 키를 지닌 트리의 키 하나를 수정하기 위해 필요한 해싱 과정이 log(N)번으로 충분하다는 점입니다.

AERGO에 적용된 개선된 희소 머클 트리 구조의 특징은 다음과 같습니다:

효율적인 머클 증명 인증 (이진 트리 구조)
노드 배칭(batching)을 통한 효율적인 데이터베이스 읽기 및 저장
데이터 저장공간 축소 (subtree의 각 leaf 노드는 하나의 키를 저장)
해시 연산 과정 축소 (subtree의 각 leaf 노드는 하나의 키를 저장)
goroutine을 통한 다중 키 동시 업데이트

희소 머클 트리(Sparse Merkle tree)

희소 머클 트리는 가능한 모든 암호화 해시 함수(cryptographic hash function) 결과값에 대응하는 leaf를 가지는 구조입니다.

**그림1.** 3개의 키를 가진 4 단계(4-bit keys) 높이 희소 머클 트리 예시. 3개 키는 빨강과 파랑으로 표시. Default node는 녹색으로 표시. Non-default 노드는 보라색으로 표시.

각 키(non-default keys)는 최하위(height=0) leaf에 저장됩니다. 만약 기본값이 D0일 경우, 높이 1(height 1)의 모든 default node는 D1=Hash(D0,D0) 값을 가집니다. 빈 트리의 root는 높이 4(height 4)의 기본 해시값을 가집니다. 키가 트리에 입력되면, leaf 노드의 값은 기본값(D0)에서 해당 키 값으로 변경되며 트리의 수정된 부분만 다시 연산하면 됩니다.

예를 들어, 이미 파랑키가 입력되어 있는 트리에 빨강값를 추가하면 H1, H2, H3, 그리고 Root만 연산해 트리의 새로운 root를 얻을 수 있습니다. 빨강값은 트리의 왼쪽에 추가됐기 때문에 h3는 수정이 필요 없게 됩니다.

256 bits을 표현하는 해시 연산의 경우, 트리는 256개의 레벨로 이루어집니다. 다시 말해 2²⁵⁶개의 키 조합이 가능하며 재구성이 불가능합니다.

이러한 트리 구조를 희소(sparse)라고 부르며, 만약 해당 트리가 (넓게 분포된)랜덤 키만을 가지고 있다면 노드 대부분은 각 노드의 높이에 따라 구분되는 기본값들을 저장하게 됩니다. 따라서, 기본 노드만 처음 저장한다면 전체 트리를 구현할 수 있고 나머지 non-default 노드 역시 구현할 수 있게 됩니다.

SMT와 머클 증명에 대한 더 자세한 설명은 이 포스트를 참조하세요.

희소 머클 트리의 개선안

트리의 키 업데이트에 필요한 해싱 연산 횟수를 줄이기위해 leaf 노드를 생성합니다. leaf 노드는 한 개의 non-default key만을 가진 subtree의 최상위에 저장됩니다. 해당 트리의 해싱은 높이 0(height 0)이 아닌, leaf 노드에서부터 시작됩니다. 만약 트리에 N개의 랜덤 키가 들어있다면, 평균적으로 약 log(N)의 높이에 leaf 노드가 생성됩니다.

AERGO Trie의 또 다른 장점은 Default Hash가 더 이상 필요없다는 점입니다. H(0,0) = 0 이라는 성질을 hash 기능에 추가했기 때문입니다. 그림 2에서 처럼, D1 = Hash(D0,D0) = Hash(byte(0),byte(0)) = byte(0) = D2 = … = D256으로 표현됩니다.

**그림 2.** H3가 하나의 키를 가진 가장 높은 subtree였습니다(빨강으로 표시). 따라서 개선된 희소 머클 트리에서 주요한 역할을 담당합니다.

파랑으로 표시된 키는 마지막 bit를 제외하고는 동일하기 때문에 분산돼있지 않으며, 해당 트리의 최하단에 같이 위치합니다. 희소 머클 트리에서 랜덤 키를 사용하는 중요한 이유입니다.

머클 증명(Merkle proofs)

머클 증명이 키의 모든 연결 정보를 가져야 하는 패트리샤 트리와는 달리, 이진 트리는 머클 증명을 쉽고 간편하게 만들어줍니다. 패트리샤 트리의 모든 노드는 16개의 하위 구조(children)를 가지고 있어 더 많은 데이터가 필요하며, 이진 트리보다 증명하기에 직관적이지 않습니다.

위의 예시에서 빨강 키의 머클 증명은 빨강으로 표시된 노드(h3)로 이루어 집니다. 이 증명은 이전 예시의 증명([D0, D1, D2, h3])보다 훨씬 짧다는 것을 확인할 수 있습니다. 값들이 최하위(height 0)에 저장되지 않기 때문입니다. 해당 증명의 verifier는 Hash(LeafNode, h3)를 연산하고 Root와 비교해서 확인하게 됩니다.

축약된 머클 증명(Compressed Merkle proofs): 표준 희소 머클 트리와 비슷하게, 머클 증명 역시 축약될 수 있습니다. 머클 증명의 거의 모든 노드가 default이기 때문에, 비트맵(bitmap)을 사용해 해당 증명의 default가 아닌 모든 인덱스에 bit를 지정할 수 있습니다. 파랑 LeafNode1이 트리에 포함됐다는 증명은 다음과 같습니다. [LeafNode2, D1, D2, LeafNode]. 이 증명은 다시 1001[LeafNode2, LeafNode]로 축약될 수 있습니다. 해당 축약머클 증명의 verifier는 D1을 통해 h2를 계산할 수 있습니다. 비트맵의 두 번째 인덱스가 0이며, D2를 세 번째 증명 요소로 볼 수 있기 때문입니다.

블록에 포함되지 않았다는 증명(Proofs of non-inclusion)

키가 트리에 포함되지 않다는 증명(proofs of non-inclusion)은 두 가지 방법을 통해 가능합니다.

다른 키의 leaf 노드가 해당 트리에 포함되어 있으며 non-included 키의 경로에 있다는 증명
default node (byte(0))이 해당 크리에 포함되어 있으며 non-included 키의 경로에 있다는 증명

예를 들어, key=0000이 어떤 트리에 포함되지 않았다는 증명은 LeafNode가 키의 경로에 있다는 것과 해당 트리에 포함됐다는 것으로 판단할 수 있습니다. Key=1111이 트리에 포함되지 않았다는 것은 D2가 해당 키의 경로에 있으며 트리에 포함되어 있다는 것으로 증명할 수 있습니다.

트리에서 삭제하기

한 leaf가 트리에서 제거될 때, subtree 최상단의 leaf 노드들이 하나의 키만 가지고 있도록 Update() 기능을 통해 특별하게 관리됩니다. 그렇지 않다면 만약 한 노드가 트리의 다른 위치에 있을 때 모든 키와 값이 같더라고 결과 trie root가 달라지기 때문입니다.

따라서, 키가 삭제될 때 Update() 기능은 형제(sibling)노드 역시 leaf 노드임을 확인하고, non-default 키 만을 지닌 최상단 subtree root까지 끌어올리게 됩니다.

노드 배칭(Node batching)

각각의 노드를 2개의 하위 구조(children)을 지닌 root로 저장할 경우, 저장해야 할 노드의 숫자는 빠르게 증가하며 메모리에서 노드를 읽는 다중 처리 과정에서 병목현상이 발생합니다. Hex 형식의 머클 트리를 통해 이런 문제점을 해결할 수 있습니다. 각 키가 16개의 하위 구조(children)와 64라는 낮은 높이(height of 64, 256/4)를 가지기 때문입니다. 하지만 앞서 말한 것처럼 이진 트리 구조가 필요합니다. Hex 형식의 트리가 가지는 장점을 노드 배칭을 통해 이룰 수 있습니다.

하나의 노드에 2개의 하위 구조를 저장하는 대신, 높이 4를 가지는 서브트리를 저장합니다. 높이가 4인 트리는 최하위에 16개의 leaf가 있으며 이는 hex 트리와 동일합니다. 따라서, 한 노드의 값은 4-bit 트리의 모든 노드를 포함한 배열(array)과 동일합니다. 트리의 index i에 위치한 노드의 하위 구조는 index 2*i+1과 2*i+2에서 찾을 수 있습니다.

노드는 다음과 같이 암호화됩니다.

{ Root : [ [ byte(0/1) to flag a leaf node ], 3–0, 3–1, 2–0, 2–1, 2–2, 2–3, 1–0, 1–1, 1–2, 1–3, 1–4, 1–5, 1–6, 1–7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f ] }

예를 들어, 배열의 index id=1에 위치한 node 3–0의 하위구조를 얻기 위해선 왼쪽 하위구조 2–0, index (2*id +1) = index 3와 오른쪽 하위구조 2–1, index (2*id+2) = index 4에 접근할 수 있어야 합니다.

각각의 노드에 byte flag를 덧붙여 leaf 노드를 구분합니다. Root는 사전에 알아낼 수 없기 때문에 byte flag는 노드 배열의 첫 번째 index에 저장됩니다.

**그림 4.** 노드 배칭 시각화. 첫 번째 배치(batch)는 파랑으로, 배치의 16개 leaf는 초록으로 표시된 다른 배치의 root. 하나의 배치는 30개의 노드를 포함.

그림 2의 예시는 다음과 같이 암호화됩니다.

{Root : [ [byte(0)], LeafNodeHash, h3, LeafNodeKey, LeafNodeValue, h2, D2=nil, nil, nil, nil, nil, h1, D1=nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, nil, LeafNode1Hash, LeafNode2Hash, nil, nil, nil, nil, nil, nil ]}

LeafNodeHash = Hash(key, value, height) 인 경우

이 배치를 데이터베이스에 저장하기 위해선, 비트맵을 통해 직렬화돼야 합니다. 이는 non default 노드만 저장할 수 있도록 합니다. 비트맵은 4 bytes = 32 bits 길이입니다. 처음 30 bits는 batch 노드에 사용되며, 31번째 bit는 shortcut batch(오직 3–0과 3–1에만 키와 값을 저장하는)를 위한 flag입니다. 32번째 bit는 사용되지 않습니다.

그림 2의 예시는 아래처럼 직렬화됩니다.

11111000001000000000001100000010 [LeafNodeHash][h3][LeafNodeKey][LeafNodeValue][h2][h1][LeafNode1Hash][LeafNode2Hash]

이와 같은 노드 배칭은 두 가지 장점이 있습니다.

데이터베이스 읽기 횟수 감소
락 없이 4의 높이를 가지는 subtree의 일괄 업데이트

goroutines을 활용한 다수의 키 동시 업데이트

키들을 하나하나 업데이트하는 대신, 단일 update call로 키를 제한 없이 트리의 다른 부분들을 동시에 업데이트할 수 있습니다. 키들은 배열에 들어가 있어야 하며, 상응하는 값들은 별도의 배열 안에 동일한 인덱스 값을 가져야 합니다. (Usage 참조)

트리에서 키를 삭제하기 위해선, 해당 키의 값을 높이 0(D0)의 default 값으로 지정하기만 하면 됩니다.

Usage

NewTrie

func NewTrie(root []byte, hash func(data …[]byte) []byte, store db.DB) *Trie {

빈 트리를 만들 경우, root를 nil로 설정하면 됩니다. Nil root는 해당 높이의 default 값과 동일하다는 의미입니다. 노드를 커밋할 계획이라면 커스텀 해시 기능이나 Hasher를 사용해 데이터베이스를 특정하면 됩니다.

Update

func (s *Trie) Update(keys, values [][]byte) ([]byte, error) {

‘keys [][]byte’는 정리된 키 배열이며, ‘values [][]byte’는 키에 상응하는 값을 가지고 있습니다.

Update는 트리를 반복적으로 찾아 내려가며, 키와 값을 트리의 좌우에 따라 해당하는 곳으로 나눠 구분합니다. 트리의 여러 부분을 일괄적으로 업데이트할 수 있게 됩니다.

만약 update가 커밋되기 전에 수차례 호출되면, 마지막 상태만 커밋됩니다.

AtomicUpdate

func (s *Trie) AtomicUpdate(keys, values [][]byte) ([]byte, error) {

AtomicUpdate는 Update와 비슷하게 트리의 정리된 키와 값을 업데이트합니다. 하지만 AtomicUpdate가 커밋 전 여러 번 호출된다면, AtomicUpdate가 호출된 모든 중간 상태가 기록됩니다. 이 기능은 각각의 블록 상태를 데이터베이스에 당장 커밋하지 않고 인증할 경우 유용하게 쓰일 수 있습니다.

Get

func (s *Trie) Get(key []byte) ([]byte, error) {

키가 default(저장되지 않았거나, nil을 출력한다면)인 경우, 키의 값을 가져옵니다.

Commit

func (s *Trie) Commit() error {

커밋을 통해 데이터베이스에 노드를 업데이트 합니다. update가 호출되면 새로운 노드는 smt.db.updatedNodes 저장됩니다. 그리고 Commit을 통해 스크를 저장합니다.

StageUpdates

func (s *Trie) StageUpdates(txn *db.Transaction) {

StageUpdates 는 지정된 데이터베이스 트랜젝션에 노드를 업데이트합니다. 이를 통해 외부 데이터베이스 트랜젝션에 trie를 커밋할 수 있습니다.

Stash

func (s *Trie) Stash(rollbackCache bool) error {

Stash 기능을 통해 커밋 없이 업데이트를 되돌립니다.

Revert

func (s *SMT) Revert(toOldRoot []byte) error {

Revert가 호출되면, 롤백을 위한 트리(현재 트리와 toOldRoot사이에 있는)가 데이터베이스에서 삭제됩니다.

MerkleProof

func (s *Trie) MerkleProof(key []byte) ([][]byte, bool, []byte, []byte, error) {

MerkleProof 는 키의 inclusion/non-inclusion의 머클 증명을 생성합니다. 머클 증명은 해시의 배열입니다.

만약 키가 포함되어 있지 않다면, MerkleProof는 해당 키 경로에 증명 leaf와 함께 false를 반환합니다.

MerkleProofPast

func (s *Trie) MerkleProofPast(key []byte, root []byte) ([][]byte, bool, []byte, []byte, error) {

MerkleProofPast는 주어진 trie root에서 키의 inclusion/non-inclusion 증명을 생성합니다. 이는 가장 최근 블록 이외에 다른 블록에서의 상태를 조회하는데사용됩니다.

MerkleProofCompressed

func (s *Trie) MerkleProofCompressed(key []byte) ([]byte, [][]byte, uint64, bool, []byte, []byte, error) {

MerkleProofCompressed는 MerkleProof와 같은 머클 증명을 생성하지만, 비트맵을 사용해 축약합니다.

VerifyInclusion

func (s *Trie) VerifyInclusion(ap [][]byte, key, value []byte) bool {

키-값 쌍이 현재 Root의 트리 안에 포함되어 있는지 확인합니다.

VerifyNonInclusion

func (s *Trie) VerifyNonInclusion(ap [][]byte, key, value, proofKey []byte) bool {

non-inclusion 증명을 확인합니다. leaf(proofKey, proofValue, height)나 빈 subtree가 non-included key의 경로에 있음을 확인합니다.

VerifyInclusionC

func (s *Trie) VerifyInclusionC(bitmap, key, value []byte, ap [][]byte, length int) bool {

축약된 inclusion 증명을 확인합니다. ‘length’는 확인된 해당 leaf key-value와 동일합니다.

VerifyNonInclusionC

func (s *Trie) VerifyNonInclusionC(ap [][]byte, length int, bitmap, key, value, proofKey []byte) bool {

축약된 non-inclusion 증명을 확인합니다. leaf(proofKey, proogValue, height)나 빈 subtree가 non-included key의 경로에 있는지 확인합니다.

결론

서로 다른 블록체인 시스템 간의 커뮤니케이션은 분산형 네트워크와 엔터프라이즈 블록체인의 미래에 있어 필수적인 요소입니다. 체인 간의 가치나 비즈니스 데이터의 전송을 원활하게 하기 위해서는 효율적인 상태 인증 수단(authenticating state)이 필요합니다. 표준 희소 머클트리는 우리가 요구하는 기준에 못 미쳤기 때문에 코드를 수정했고, 이렇게 개발한 솔루션을 오픈소스로 개방했습니다. AERGO StateTrie는 AERGO 플랫폼에 적용되어 체인 간 자산 연결(asset bridging)과 지갑과 라이트 클라이언트 같은 안전한 상태 검증이 필요한 어플리케이션을 위해 빠르고 효율적인 상태 인증(authenticating state)을 지원할 예정입니다. 만약 이 외에도 다른 적용 사례들에 대한 아이디어를 가지고 계시거나, AERGO와 기술적인 협약을 맺고 싶으시다면 아래의 채널을 통해 연락주세요.