이더리움의 작동방식 (8) | 채굴, 작업증명 PoW, DAG

* 이 글은 How does Ethereum work, anyway? 라는 글을 읽어가며 이해한 바를 한국어로 번역하여 정리하는 글입니다. 시리즈의 형태로 끊어가며 업로드되었으니, 참고 부탁드립니다.

 

이더리움 블록체인의 구성 요소

 

이더리움 블록체인은, 

계정 / 상태 / 가스 및 수수료 / 상호작용 / 블록 / 상호작용의 집행 / 채굴 / 작업 증명 

등으로 구성된다. 

 

지난 글에 이어서 계속 설명한다.

 

8. 채굴 및 작업 증명

이더리움의 작업 증명 방식은 Ethash, 이더해시라 한다. 

대거-하시모토 알고리즘으로도 알려져 있다.

Ethash is the planned PoW algorithm for Ethereum 1.0. It is the latest version of Dagger-Hashimoto, although it can no longer appropriately be called that since many of the original features of both algorithms have been drastically changed in the last month of research and development. 

The general route that the algorithm takes is as follows:
1. There exists a seed which can be computed for each block by scanning through the block headers up until that point.
2. From the seed, one can compute a 16 MB pseudorandom cache. Light clients store the cache.
3. From the cache, we can generate a 1 GB dataset, with the property that each item in the dataset depends on only a small number of items from the cache. Full clients and miners store the dataset. The dataset grows linearly with time.
4. Mining involves grabbing random slices of the dataset and hashing them together. Verification can be done with low memory by using the cache to regenerate the specific pieces of the dataset that you need, so you only need to store the cache.

https://eth.wiki/en/concepts/ethash/ethash

이더해시(Ethash)는 이더리움(Ethereum)의 작업증명(PoW) 합의 알고리즘이다.
이더해시는 비탈릭 부테린(Vitalik Buterin)의 대거(Dagger) 알고리즘과 타데우스 드리자(Thaddeus Dryja)의 하시모토 알고리즘(Hashimoto algorithm)의 조합인 대거-하시모토(Dagger-Hashimoto)의 진화된 알고리즘을 사용한다. 이더해시는 방향성 비순환 그래프(directed acyclic graph, DAG)로 알려진 대규모 데이터 세트의 생성 및 분석에 의존한다. DAG의 초기 크기는 약 1GB이고, 천천히 선형으로 크기가 커지며, 매 순간 업데이트된다. DAG의 목적은 자주 접근하는 대규모 데이터 구조를 유지하는 데 필요한 이더해시 작업증명 알고리즘을 만드는 것이다. 이는 이더해시가 에이식(ASIC) 저항성을 갖게 만들려는 것으로, GPU 채굴 장비를 만들기가 더 어려워진다는 의미다. 이더리움의 창립자는 특수 실리콘 제조 공장 및 대규모 예산에 접근할 수 있는 사람들이 채굴 인프라를 지배하고 합의 알고리즘의 보안을 훼손할 수 있는 작업증명 채굴의 중앙 집중화를 피하고자 했다.

다음은 이더해시의 채굴 과정이다.
1. 32개 길이의 배열의 에포크(Epoch)수만큼 해싱한다. 그 값을 시드(Seed)값으로 삼는데, 이 시드값을 30,000블록마다 변경된다.
2. 시드 값으로 무작위 추출(pseudo-random)한 캐시 데이터(cache data)를 생성한다. 생성 시 메모리를 사용하게 되는데 메모리를 타 용도로 사용한다면 캐시 데이터의 생성 속도가 매우 느려지므로 주의한다.
3. 1GB 이상의 데이터 세트을 생성한다. 이때 풀 클라이언트(full client)와 채굴자는 데이터세트 DAG를 저장하며, 데이터 세트는 선형으로 커진다. DAG 파일은 캐시 데이터를 이용해 생성하는데 한 번에 64바이트의 데이터를 생성하고 이를 데이터 사이즈만큼 생성하도록 반복한다.
4. 채굴 과정에서 데이터 세트의 일부를 같이 해싱한다.
5. Keccak156해시를 해 결과값이 조건에 맞으면 채굴에 성공한다.
6. 다이제스트와 논스는 블록헤더에 포함되는데 다이제스트 필드, 논스 필드가 포함되지 않아 해시값에 변경이 없다.

http://wiki.hash.kr/index.php/%EC%9D%B4%EB%8D%94%ED%95%B4%EC%8B%9C

 

이더해시의 작업 증명 알고리즘은 이렇게 정의된다.

https://preethikasireddy.medium.com/how-does-ethereum-work-anyway-22d1df506369

여기서 m은 믹스해시, n은 논스, Hn은 신규 블록의 헤더 (논스 및 믹스해시 등 연산 필요 부분 제외), 두번째 Hn은 블록헤더의 논스, d는 DAG로 큰 데이터 셋을 의미한다.

 

앞에서 이야기한 것을 돌이켜보면, 블록 헤더의 2가지 구성요소인 믹스해시와 논스는, 

"블록이 충분히 연산되었음을 증명"하는 용도로 사용한다. 

작업증명 함수는 이 둘을 검증/평가하는 데에 사용한다.

 

조금 추상적으로, 대략적으로 그 과정을 이야기해보자. 

 

1. 시드

시드는 각 블록마다 계산된다. 시드는 에폭마다 다른데, 하나의 에폭은 30000개 블록 정도로 길다.

에폭(epoch)은 블록체인의 검증인들이 검증 작업을 하는 체크포인트의 블록 간격을 지칭하는 말이다. 에폭은 다수의 블록을 하나의 단위로 묶은 것으로서, 보통 블록 50개를 묶어서 하나의 에폭을 구성한다. 에포크라고도 불린다. 다수의 슬롯 이후에 유효성 검사기가 위원회에서 재구성된다. FFG에 반영된 것은 아니지만, 에폭의 길이를 증가시키자는 비탈릭 부테린(Vitalik Buterin)의 제안이 있다.

http://wiki.hash.kr/index.php/%EC%97%90%ED%8F%AD

Epoch is a period of mining. The epoch increases for every 30,000 blocks for all ETH and other Ethash coins and 60,000 blocks for ETC.

https://minerstat.com/dag-size-calculator

For example, within the Ethereum protocol, an epoch is the amount of time it takes for 30,000 blocks to be finalized on the chain. The physical time an epoch lasts is variable as the speed for processing transactions and reaching consensus can vary. However, the speed generally remains stable at around 100 hours.

https://bisontrails.co/epoch/

 

2. 캐시의 계산

 

첫번째 에폭의 시드는 0으로 이루어진 32바이트의 수열이다.

매 에폭마다, 지난 시드 해시의 해시가 새로운 시드가 된다.

이 시드를 활용해, 노드는 pseudo-random “cache"를 계산한다.

(의사난수/유사난수는, 컴퓨터에서 생성할 수 없는 난수를 유사하게 구현한 것을 의미한다.)

 

이 캐시는, 라이트 노드의 개념을 구현하는 데에 결정적이다.

라이트노드는, 일부 노드들은 전체 블록체인 데이터를 저장하는 부담 없이, 트랜잭션을 효율적으로 검증하는 노드를 마련하는 차원에서 구현되는 것으로, 라이트노드는 이 캐시를 기반으로 트랜잭션의 유효성을 확인한다. 이 캐시를 활용하면 검증하고자 하는 특정 블록을 재생성할 수 있기 때문이다.

 

3. DAG 데이터셋 생성

 

캐시를 활용해, 노드는 DAG라 하는 데이터셋을 생성할 수 있다. DAG 데이터셋의 각각의 항목들은 캐시에서 유사-랜덤하게 선택된 몇몇 항목들에 의존한다. 채굴자가 되기 위해서는, 이 전체 데이터셋을 생성하고, 모든 풀-클라이언트와 채굴자들은 이 데이터셋을 저장해야 하며, 이 데이터셋은 시간에 따라 선형적으로 증가한다는 특징이 있다.

방향성 비순환 그래프

방향성 비순환 그래프(DAG; Directed Acyclic Graph)란 개별 요소들이 특정한 방향을 향하고 있으며, 서로 순환하지 않는 구조로 짜여진 그래프를 말한다. 유향 비순환 그래프라고도 한다. 간략히 DAG(대그)라고 쓴다. DAG를 적용한 블록체인 프로젝트로는 아이오타(IOTA)에 적용된 탱글 알고리즘과 헤데라 해시그래프에 적용된 해시그래프 그리고 로커스체인(Locus Chain)에 적용된 DAG-AWTC 등이 있다. 방향성 비순환 그래프에서 개별 요소들은 블록체인처럼 여러 개의 트랜잭션을 하나의 블록으로 묶지 않고, 각 개별 요소들끼리 상호 연결되어 있다. 방향성 비순환 그래프는 시간적으로 이전 트랜잭션에 대해 그 이후 트랜잭션이 검증하는 구조로 되어 있다. 시간 t를 기준으로 그 다음에 이어질 시간 t+1의 상태를 추측하기 위해 마르코프 체인 몬테 카를로(MCMC; Markov Chain Monte Carlo) 알고리즘을 사용한다.

http://wiki.hash.kr/index.php/%EB%B0%A9%ED%96%A5%EC%84%B1_%EB%B9%84%EC%88%9C%ED%99%98_%EA%B7%B8%EB%9E%98%ED%94%84

 

4. 믹스해시와 논스의 생성

 

채굴자는 그뒤 데이터셋에서 임의로 몇몇 부분들을 가지고 수학적인 함수를 통해 하나로 합쳐 해시하는데, 이를 믹스해시라 한다.

채굴자는 원하는 논스가 나올 때까지 반복적으로 믹스 해시를 생성한다.

결국 결과값이 요구사항을 충족하면, 이 논스는 유효하다고 인식하고 체인에 블록을 추가한다.

 

 

보안 메커니즘으로서의 채굴

작업증명은, 암호학적으로 안전한 방식으로,

(논스와 같은) 결과값을 생성하는 데에 일정량의 연산량이 증가하였음을 증명하는 것이 목적이다.

모든 경우의 수를 나열하는 것 외에 주어진 임계값 아래의 논스를 찾는 더 나은 방식이 없기 때문에 우리는 안전하다고 인식한다.

해시 함수로부터 반복적으로 나오는 결과값은 균등하게 분포되어(모든 결과값의 확률이 동일), 

평균적으로 논스를 찾는 데에 걸리는 시간이 난이도 임계값에 따라 조절되는 것을 보장한다.

난이도가 높을수록, 논스값을 찾는 데에 더 오랜 시간이 걸리기 때문에, 

작업증명 알고리즘에는 난이도라는 개념이 있고, 튼튼한 블록체인 보안 체계를 만들 수 있다.

 

블록체인 보안이란?

모두가 믿는 블록체인을 만든다는 것이다. 

체인이 하나로 유일해서 유효성 검증을 합리적으로 진행할 수 있어야 하고,

블록체인에 저장된 상태값을 모두가 납득해야 하기 때문에, 

모두가 믿는, 유일하게 인정받는 블록체인이 필요하다.

 

https://preethikasireddy.medium.com/how-does-ethereum-work-anyway-22d1df506369

 

그리고 그 신뢰는 작업증명 알고리즘에 기반한다.

특정 블록체인이 미래에도 인정을 받기 위해서는,

공격자로 하여금 새로운 블록을 생성해 이전 역사를 조적하려 하는 시도가 불가능하도록 해야 한다.

공격자가 블록 조작을 성공하기 위해서는 지속적으로 네트워크의 모든 공동체 구성원 중 가장 빠르게 논스를 계산하는 일을 지속적으로 해내야만 한다. 고스트 프로토콜의 원리에 따라, 구성원들은 가장 무거운 체인을 신뢰하기 때문이다. 이는 공격자들의 채굴력이 체인 전체 채굴력의 절반을 초과하는 <다수의 공격>일 때만 가능하다.

 

부의 분배 메커니즘으로서의 채굴

작업 증명은 보안 체계를 만들어주는 기여자들에 대한 부의 분배 체계이기도 하다.

채굴자가 블록을 채굴하면, 

1. 가장 먼저 채굴할 경우 정해진 블록 보상을 받게 되고 (콘스탄티노플 이후 2 이더리움)

2. 블록의 거래 시 가스 수수료를 얻게 되고

3. 가장 먼저 채굴하지 못하더라도 Ommer 블록 채굴자로서 추가 보상을 얻게 된다.

 

작업 증명 합의 메커니즘이 보안과 부의 분배 측면에서 지속 가능하기 위해, 

이더리움은 아래의 2가지 특징을 가진다.

 

1. 최대한 많은 사람들이 접근하도록 한다.

특정인 혹은 특정 하드웨어가 알고리즘을 운영해서는 안된다. 부의 분배 모델이 최대한 공개되도록 해서, 어느 누구나 자신이 원하는만큼 컴퓨팅 파워를 제공하고 이더리움을 그 보상으로써 수령해야 한다.

 

2. 하나의 노드가 불균형적인 이익을 얻지 못하게 한다.

소수의 노드가 이익을 독과점하게 되면, 특정 노드가 블록체인에 지대한 영향을 끼치게 되고, 이는 네트워크 보안 측면에서도 취약점을 발생시킨다.

 

비트코인 블록체인에서는, 작업증명 알고리즘이 SHA256이라는 해시 함수를 사용한다는 데에 있어서 문제가 발생했다.

이 함수는, ASICs, 특정 하드웨어를 사용하면 다른 하드웨어와 대비해서 무척 빠르게 컴퓨팅을 진행할 수 있기 때문이다.

ASIC(에이식, application-specific integrated circuit, 특정 용도용 집적 회로)는 범용 용도가 아닌 특정 용도에 맞게 맞춤 제작된 집적 회로를 말한다. 주문형 반도체라고도 한다. 예를 들어 디지털 음성 녹음기 또는 고효율 비트코인 채굴기에서 실행되도록 설계된 칩은 ASIC이다.
https://ko.wikipedia.org/wiki/ASIC

중국의 우지한(吴忌寒, 오기한, Wu Jihan)이 이끄는 비트메인(Bitmain) 회사는 목표값 이하의 해시를 빠르게 찾아낼 수 있는 주문형 반도체인 에이식(ASIC)을 이용한 채굴기를 제작했다. ASIC 장비는 기존 GPU 방식의 채굴기에 비해 전기 사용량이 적을 뿐 아니라 채굴 성능이 월등히 뛰어나다. 비트메인의 뒤를 이어 이노실리콘, 바이칼, 할롱마이닝 등 여러 업체들이 ASIC 채굴기를 대량 생산함에 따라, 기존의 GPU 채굴기 시대는 막을 내리고 ASIC 채굴기 경쟁 시대로 접어들게 되었다.
https://ko.wikipedia.org/wiki/%EC%B1%84%EA%B5%B4%EA%B8%B0

 

이를 막기 위해, 이더해시 작업증명 알고리즘은, sequentially memory-hard하게 만들어졌다.

이는 논스 계산을 위해 메모리와 대역폭을 많이 요구하도록 설계되었다는 의미다.

메모리를 많이 요구한다는 것은, 컴퓨터가 동시 다발적으로 여러 논스를 찾아가는 과정에서 

그 메모리를 평행하게 활용하기 어렵도록 만드는 것이다.

높은 대역폭을 요구한다는 것은, 매우 빠른 컴퓨터가 동시 다발적으로 여러 논스를 찾기 어렵게 한다는 것이다.

즉, 중앙화의 위험을 막고 더 많은 노드들이 증명 작업에 참여하도록 설계되었다.

In cryptography, a memory-hard function (MHF) is a function that costs significant amount of memory to evaluate. It is different from a memory-bound function; the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of proof of work.
https://en.wikipedia.org/wiki/Memory-hard_function

Put another way, a sequential memory-hard function is one where not only the fastest sequential algorithm is memory-hard, but additionally where it is impossible for a parallel algorithm to asymptotically achieve a significantly lower cost. Since memory-hard algorithms asymptotically come close to using the most space possible given their running time, and memory is the computationally usable resource general-purpose computers have which is most expensive to reproduce in hardware , we believe that, for any given running time on a sequential general-purpose computer, functions which are sequential memory-hard come close to being the most expensive possible functions to compute in hardware.
https://crypto.stackexchange.com/questions/87352/what-does-sequential-memory-hard-mean

 

 

참고로, 이더리움은 작업증명 합의 메커니즘을, 지분 증명 메커니즘, PoS로 옮기고자 한다.

지분증명(PoS, Proof of Stake)이란 해당 암호화폐를 보유하고 있는 지분율에 비례하여 의사결정 권한을 주는 합의 알고리즘이다. 주주총회에서 주식 지분율에 비례하여 의사결정 권한을 가지는 것과 유사하다. 채굴 과정이 필요 없다. 포스라고도 읽는다. 카르다노(에이다), 큐텀, 피어코인 등의 암호화폐가 지분증명 방식을 사용하고 있다. 이더리움도 현재 작업증명 방식을 벗어나 지분증명 방식으로 변경할 예정이다.

http://wiki.hash.kr/index.php/%EC%A7%80%EB%B6%84%EC%A6%9D%EB%AA%85

 

 

더 읽어볼 자료 - 이더리움 황서

GitHub - ethereum/yellowpaper: The "Yellow Paper": Ethereum's formal specification