이더리움 Ethash 연구

bero

Published in

TOMAK

11 min readJul 25, 2018

서태후

1. 요약

Ethash 알고리즘의 구성을 확인하고 기존의 PoW를 이용한 마이닝 방법과의 차이를 확인하여 왜 Ethash 알고리즘은 ASIC 저항성을 가지는지 이해한다.

2. 필요한 배경지식

비트코인의 PoW
Hash Algorithm(SHA, Keccak)
컴퓨터 구조(CPU, 메모리, 캐시, 디스크, VGA)
ASIC

3. 서론

일반적으로 비트코인에서 사용하는 ASIC의 경우 500GH~15TH 까지의 연산량을 보인다. 이는 일반적인 GPU 1~20GH (멀티채널 구성 시)보다 압도적으로 계산량이 높다는 것을 알 수 있다. 이 경우 ASIC을 활용한 특정 집단이 일방적으로 높은 Hash Power를 가지는 중앙 집중화 문제가 발생한다. 이에 대응하여 Ethash는 이런 ASIC에 대한 저항성을 가지고 만들어진 알고리즘이다. 이번 연구에서는 Ethash의 구조 이해를 통해 어떻게 ASIC 저항성을 가지고 있고, 이더리움 Mining을 수행하는지 알아보도록 한다.

4. 본론

Ethash의 동작구조를 간략하게 아래와 같이 나타낼 수 있다. (이 flow를 기억해 두는 것이 다음 본론의 내용들을 이해하는데 도움이 될 것이다.) 그리고 동작 구조를 조금 더 명확하게 보기 위해 ethereum-wiki에서 제공하는 python으로 간략하게 나타낸 코드를 인용할 것이다.

현재 포인트까지 블록의 헤더를 스캔해 Seed를 계산(seed는 30000블록 마다 바뀜)
이 Seed를 통해 pseudo-random 하게 cache data 생성
cache data로 1GB 이상의 dataset을 생성. full client와 miner는 이 dataset(DAG)을 저장(dataset은 시간에 따라 linear하게 커짐)
mining을 수행할 때 이 dataset의 일부를 함께 해싱

Definition

앞으로 나올 계산 과정에서 위 Definition 들을 숙지하면 좀 더 수월하다.

parameters

먼저 cache size와, dataset의 사이즈를 정의하는 부분인데 이 부분은 이미 아래와 같이 하드코딩 되어 있다.

위 코드를 따라가며 현재(5월 20일 기준)의 cache_size와 data_size를 계산해 보자.

cache_size

block_number // EPOCH_LENGTH = 현재 기준 블록 (≈ 566만) / 30000 = 188
sz = 16777216 + (131072 x 188) = 41418752
4.sz — HASH_BYTES = 41418752–64 = 41418688
sz = 41418688
sz / HASH_BYTES 의 값이 소수가 될 때까지 2 x HASH_BYTES = 128 만큼 sz 를 감소
최종 sz = 41286208

data_size

sz = 1073741834 + (8388608 x 188) = 2650800138
sz — MIX_BYTES = 2650800138–128 = 2650800010
sz = 2650800010
sz / MIX_BYTES 의 값이 소수가 될 때까지 2 x MIX_BYTES = 256 만큼 sz 를 감소
최종 sz = 2642407552 ≈ 2.46GB

다음으로는 위에서 구한 cache_size 만큼의 cache data를 생성할 것이다.

n = 41286208 / 64 = 645097
2. 5행에서 o의 첫 번째 부분을 64바이트의 해시값으로 세팅
6~7행에서 1 ~ (645097–1) 횟수만큼 기존 배열 o 의 마지막 요소 다음에 append
o의 size = [1(초기 세팅) + 645096(반복)] x 64 bytes = 41286208 bytes = 39.5 MB
10~13행 : Strict Memory Hard Hashing Functions (2014) 알고리즘을 사용하여 계산 수행에 필요한 메모리 크기에 비해 계산에 사용할 수 있는 메모리 크기를 줄이면 연산 속도가 기하급수적으로 증가하도록 구성

5번 내용을 조금 더 살펴보자.

Strict Memory Hard Hashing Functions의 SeqMemoHash pseudo code

SeqMemoHash(s, R, N) 
(1) Set M[0] := s
(2) For i := 1 to N − 1 do set M[i] := H(M[i − 1]) 
(3) For r := 1 to R do 
       (a) For b := 0 to N − 1 do 
              (i) M[b] :=H(M[(b − 1 + N) mod N] || M[b])

H : 고정된 길이 input 두 개를 같은 길이의 output으로 출력하는 함수(One-Way compression function)
D : Digest size, (SHA3–512의 경우 512bit = 64 bytes)
s : 사이즈가 D인 master-secret, sha3_512(seed) 에 해당
M[i] : 0<= i <= N 인 배열. 각 셀 당 D(64ytes) 만큼 저장 가능
R : 라운드

로 구성되어 있고 마이너가 메모리 전부를 다른 작업을 하는데 사용하게 하는 것을 막는 용도라고 생각하면 편할 것 같다. 이 방법을 사용하게 되면 어떤 데이터를 생성할 때 일정 양 이상의 메모리를 사용하지 않으면 이 데이터를 만들어 내는데 소모되는 시간이 아래 그림처럼 기하급수적으로 증가한다.(연산 비교횟수가 급격하게 증가하게 되고, 메모리가 부족하면 디스크에 저장해야 하기 때문에, 이를 store/load 하는 시간이 추가되고, 이 시간은 메모리에 접근하는 시간에 비해 상대적으로 오래 걸리기 때문이다)

mkcache 함수와 연관지어 생각해 보면, cache data를 생성하는데 메모리를 사용하게 되는데, 위와 같은 방법을 사용하면 메모리 전부를 다른 용도로 사용했을 때 cache data 생성 속도가 굉장히 느려진다. 즉 역으로 보면 cache data를 정상적으로 생성했다는 것은 특정 메모리 만큼은 이 작업을 수행하는데 사용했다는 것을 증명하는 셈이 되는 것이다.

이제 이 cache data를 이용해서 DAG 파일을 만들 것이다. 이것은 한번에 큰 파일이 만들어지는 것이 아니라 cache data를 이용해 한번에 64bytes의 데이터를 만들어 내고 이를 앞에서 구한 Data size 크기만큼 생성하도록 반복하는 과정을 거친다.

compute 64-byte item

9행의 DATASET_PARENTS는 Definition에서 256으로 정의되어 있다. 이어서 fnv라는 함수로 cache에서 256개의 인덱스를 pseudo-random하게 만들고, 11행에서는 이를 이용해 mix를 만들어내고 마지막으로 이것을 sha3_512(실제로는 keccak)으로 해싱한 64bytes 데이터를 반환한다.

Ethash 에서 사용하는 FNV(Folwer-Noll-Vo) 함수를 잠깐 소개하겠다.

hash = FNV_offset_basis
   for each byte_of_data to be hashed
   	hash = hash × FNV_prime
   	hash = hash XOR byte_of_data
   return hash

1. 출력 비트에 따라 FNV_offset_basis 값을 정함

2. 이 입력 바이트에 대해 FNV 소수라는 FNV함수의 출력 비트에 따라 정해지는 소수를 곱한다. (32비트 출력의 경우 FNV_PRIME = 16777619)

3. 이를 입력 바이트와 XOR 연산을 수행

대강 이런 구조로 이루어져 있다.

이것을 Ethash에서는 위 코드처럼 FNV_offset_basis를 첫 번째 파라미터인 v1으로, byte_of_data를 두 번째 파라미터인 v2를 사용했다. FNV 함수는 보는 것처럼 매우 간단하고, 그렇기 때문에 결과가 상대적으로 빨리 생성되어 비암호화 해시로 불린다. 두 개의 파라미터를 결합해 빠르게 해시를 생성하는 과정이라고 생각하는 것이 쉬울 것 같다.

generate full dataset

차례대로 full_size = 2642407552, HASH_BYTES = 64를 대입해2642407552 / 64 = 41287618 라는 횟수 만큼 calc_dataset_item 함수를 수행하면

64bytes × 41287618, 약 2.46GB 크기의 DAG(Directed Acyclic Graph, 방향성을 가진 비순환 그래프)를 생성한다. 위 flow를 아래처럼 그릴 수 있다.

다음으로 마이닝이 진행되는 과정을 살펴보자

mining

6번째 라인만 보면 일반적인 PoW처럼 target값 보다 작은 nonce를 찾는 것 처럼 보인다. hashimoto_full 함수의 내용을 보면 왜 Ethash는 일반적인 PoW와는 다른지 알 수 있다.

6~10행 : nonce를 거꾸로 뒤집은 값과 헤더를 해싱하여 생성한 seed 를 mix 배열 끝에 두 번 복사
12~17행 : new data에 DAG 파일에서 연속한 두 개의 원소(64bytes x 2 = 128bytes)를 랜덤하게 선택하여 저장한 후 이 배열을 mix 배열과 fnv 함수로 결합
19~25 : mix의 연속된 4개의 인덱스를 차례로 fnv 로 결합하여 append한 cmix를 생성한 후 32bit로 압축한 결과 리턴

조금 더 쉽게 이해하기 위해 아래 그림을 보면 6번 직전까지의 과정들이 hashimoto_full 함수에서 동작하는 내용들이다.

번호 순서대로 다시 한 번 내용을 정리해 보자.

전처리된 header와 최근 nonce를 해싱하여 초기 mix를 세팅한다.
전체 DAG 파일에서 128bytes(연속된 두 개의 DAG 페이지) 크기의 랜덤한 페이지를 불러온다
mix와 불러온 DAG 페이지를 결합(fnv로)하는 과정을 수행한다
위 과정을 64회 반복한다
Compress 과정을 통해 32bit의 결과를 생성한다.
32bit의 mix digest 값과 target 값을 비교하여 mix digest 값이 target값 보다 크면 Fail로 판단하고 nonce를 증가시켜 1~6과정을 반복하고, 작으면 Success

5. 결론

Ethash 알고리즘이 비트코인과 같은 PoW 구조와 다르게 ASIC 저항성을 갖추는 메커니즘이 보이는가?

컴퓨터에서는 캐시를 이용하면 반복되는 연산의 속도를 빠르게 할 수 있다. 마이닝 과정에서 128bytes 크기의 페이지를 DAG에서 읽어오는 과정을 보면 페이지를 불러올 때 mix 과정을 통해 다음에 불러올 페이지를 예측할 수 없게 설계되어 있다. 만약 DAG의 용량이 작았다면 다음 페이지 예측이 불가능하더라도 이것을 모두 캐시에 넣어 사용할 수 있겠지만, 캐시 용량은 8KB~32MB로 굉장히 작기 때문에 수 GB 짜리의 DAG를 저장하는 것은 불가능 할 뿐더러, 그렇다고 해서 그 중 일부를 캐시에 저장하는 것은 ‘캐시 미스’가 발생할 확률이 너무 높기 때문에 의미가 없다. 이러한 점 때문에 Ethash 알고리즘은 Memory Hard 또는 Memory Bound 라고 불리며 단순히 해싱만 반복해 nonce를 찾는 PoW 구조와 달라 ASIC 저항성을 갖추게 되는 것이다.

하지만 결과적으로 Ethash 또한 중앙 집중화된 시스템을 완벽하게 분산화하는 데 성공을 거두지는 못했고, 비용적 문제나 불필요한 작업을 수행한다는 점은 여전히 남아있다. 따라서 전환하려고 하는 PoS 구조의 설계가 앞으로 이더리움 생태계에 가장 큰 영향을 미칠 것이라고 예상한다.

이더리움 Ethash 연구

1. 요약

2. 필요한 배경지식

3. 서론

4. 본론

5. 결론

6. Reference

Published in TOMAK

Written by bero