이더리움 Merkle-Patricia Trie

Merkle Tree

- Merkle Proof 는 머클트리에 존재하는 데이터가 올바른 데이터인지 입증하는 절차

 

- Merkle proof에는 다음 값들이 필요함

> 증명하려는 데이터와 그것의 해시값

> 머클트리의 루트 해시값

> branch(데이터에 해당하는 리프노드에서 루트노드까지의 경로 노드들을 계산하는데 필요한 해시값들)

> 데이터의 해시값과 branch 해시값들을 이용해 경로에 해당하는 노드들의 해시값을 구할 수 있고, 이를 반복해 루트 노드의 해시값을 구할 수 있음

> 구한 루트노드의 해시값과 기존에 알고 있던 루트노드의 해시값이 같다면 검증한 데이터가 올바른 데이터임을 입증 할 수 있다.

 

- 머클 트리의 한계

> 상태 정보는 [키와 값] 의 Map 구조
키 : 어카운트 주소
값 : 이더 잔액, 넌스, 컨트랙트일 경우 컨트랙트 소스. 스토리지 등

> 상태 정보는 수시로 변하기 때문에 update가 될 때 마다 전체 머클트리를 재 계산해야함

> 이더리움은 TX마다 State가 바뀌고, 10초마다 블럭이 생성되므로 머클트리로는 무리가 있음.

 

한계를 극복하고자 머클 패트리샤 트리를 도입

> 트리의 깊이를 한정 지음 => 깊이가 무한대로 내려가 성능 저하가 되는 것을 방지

> 머클 루트를 값에 한정되도록 함 => 상태정보가 변경되더라도 머클루트는 변경이 안됨

> 노드에 값까지의 경로를 명시할 수 있는 페트리시아 트리를 도임

 

머클트리와의 차이점

- 경로를 찾아가는 트리구조.

- 순서도를 따라가면 Account의 정보에 접근할 수 있다.

- Node를 확장해나가는 방식이라 내용을 추가하거나 고치기 쉬움.

 

Ethash Consensus

이더리움에서 사용한 합의 알고리즘 : Proof of Work (Ethash)

- Ethash : PoW를 수정한 이더리움의 합의 알고리즘

- 매 30,000블록마다 DAG(2차원 배열 데이터) 라는 데이터를 생성하여 Mining 작업에 사용하도록 하여 많은 Memory 용량과 IO 를 사용하게 만들었음. 이를 통해 기존 PoW에서 사용하던 ASIC 을 사용하지 못하게 설계

- 약 12초(10~15)마다 블록 생성될 수 있도록 설계

- 고속으로 생성되는 블록으로 인해 생기는 엉클블록이 이더리움 보안성을 저하시킴

- 엉클블록 : 블록생성에 성공하고 검증에 오류가 없지만 더 빨리 전파된 다른 채굴자들에 의해 순위가 밀려 메인체인에 들어가지 못한 블록

- GHOST 프로토콜을 통해 이를 해결, 엉클블록 에게도 기존 보상 3 Ether의 87.5% 지급.

 

DAG

- 30,000 블록마다 갱신되는 난수 DAG(임의의 데이터 셋)를 마이닝 과정에서 사용

- 2~4GB의 DAG(Directed acyclic graph) 를 메모리에 상주시키도록 요구.

- GPU를 사용하고 있는지 확인하고 있기에, 반드시 GPU 를 사용하도록 유도.

- 데이터값이 맞는지, 계산이 잘 되었는지 확인하는 역할도 함.

- ASIC칩으로는 마이닝을 할 수 없도록 함

- KECCAK256(sha3) 사용

- Nonce 와 블록 헤더에 의해 반복적으로 결정되는 (mix)에 의해 지정되는 DAG 페이지를 반복적으로 접근(64회)

- 최종 믹스의 해시값인 mix digest 를 난이도 목표 임계값과 비교

 

이더리움 해싱 알고리즘                                                                        DAG 데이터셋

1. 현재의 넌스값과 이전블록의 헤더값을 넣음

2. DAG를 64번 볶음

3. MIX HASH 넣기 (5번위치)

4. <= : 조건충족. 원하는 nonce값 찾음.

5. 성공!

 

이더리움의 10초

-> 전파 -> 확인 -> tx처리 -> PoW -> 넌스값 -> 전파 

 

Mining Pool

- 분산화된 마이닝 풀

- 마이닝의 중앙화의 문제가 있음.

-