이더리움의 합의 알고리즘 - 작업증명(PoW : ethash)

비트코인의 작업증명에서 설명한것처럼 이더리움도 동일한 작업증명을 합의 알고리즘으로 사용하고 있습니다. 현재 지분증명(Proof of Stake : PoS) 방식인 캐스퍼(Casper)로 변환을 하기 위한 작업이 진행되고 있으며, 과도기적으로 작업증명과 지분증명을 함께 사용하는 하이브리드 캐스퍼가 진행중이지만, 이번 포스팅에서는 작업증명을 위주로 설명을 하도록 하겠습니다.

이더리움은 다음과 같은 방식으로 nonce 값을 찾아내도록 동작되고 있습니다.

1. 마이너는 일정시간동안의 트랜잭션을 모아 하나의 신규 블록을 구성한다.

2. N+1 블록 등록을 위해 N번째 블록헤더의 hash값과 트랜잭션 머클루트, 임의의 값인 nonce를 함께 hash 암호화합니다. 이 결과가 계산된 난이도값보다 작은값이 되는 nonce 값이 발견될때까지 nonce를 계속 변화시킵니다. 보통 nonce는 일반적으로 0부터 시작하여 순차적으로 중가시켜가며 목표값을 찾는 무작위대입방식을 사용합니다.

3. nonce 값보다 작은 목표값을 찾으면 해당 블록에 nonce를 저장하고 해당 블록을 주변노드로 브로드캐스팅합니다.

비트코인의 합의 알고리즘은 강력한 Hash연산이 필요합니다. 따라서 이러한 Hash 연산에 특화된 ASIC 장치가 출현하게 되었으며, 이러한 ASIC 장비로 인해 채굴자는 점점 연산력이 대형화되고, 중앙집중화되어가게 되었습니다. 따라서 이더리움의 합의 알고리즘인 이대시(Ethash)은 기본적으로 Hash 계산에 특화된 ASIC 장비를 무력화한후 Hash 연산이 중앙집중화되는것을 막고, 경량 클라이언트에서 블록을 검증할수 있는것을 목표로 개발되었습니다.

이대시(ethash)는 메모리 기반의 이더리움 작업증명 알고리즘으로, ASIC 장비를 무력화하기 위해 메모리를 쓰는 방식을 채택하고 있습니다. 이대시는 컴퓨터 메모리상의 일정량의 데이타를 읽은후 이것을 nonce와 함께 hash 계산하는 방식을 반복합니다. 일반적으로 메모리를 읽고 복사하는 속도가 hash 연산보다 느리기 때문에 hash 연산력만 높이는 것은 작업증명에 큰 의미가 없어지게 됩니다. 따라서 ASIC 장비가 무력화되어 일반 PC에서 GPU를 사용한 마이닝이 가능하게 되었습니다. 이대시는 10~15초마다 새로운 블록이 생성되도록 설계되어 있으며, DAG 알고리즘을 사용합니다.

geth 클라이언트에서 마이닝을 동작시키면 캐시영역을 확보하기위해 시드해시를 생성하게 됩니다. 시드해시로부터 생성된 약 2GB 정도의 캐시 데이타집합을 DAG(Directed Acyclic Graph) 파일이라고 합니다. 현재 30,000 블록을 주기로 이 DAG 파일 전체를 다시 재생성하게 되며, 이러한 30,000 블록 단위를 에포크(Epoch)라고 합니다. 시드해시는 각각의 블록마다 계산이 되어지며, 각각의 에포크(epoch)마다 달라지게 됩니다. 첫번째 에포크에서 시드해시는 0으로 이루어진 32바이트의 hash 값입니다. 이어지는 에포크에는 이전 시드해시의 hash값이 다시 새로운 시드해시로 사용되어집니다.

EPOCH_LENGTH = 30000              # blocks per epoch

def get_seedhash(block):
     s = '\x00' * 32
     for i in range(block.number // EPOCH_LENGTH):
         s = serialize_hash(sha3_256(s))
     return s

위의 그림에서 seed hash로부터 cache를 계산하는 과정은 다음과 같습니다.

먼저 cache사이즈와 full data 사이즈를 블록번호에 맞게 계산합니다.

def get_cache_size(block_number):
    sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
    sz -= HASH_BYTES
    while not isprime(sz / HASH_BYTES):
        sz -= 2 * HASH_BYTES
    return sz

def get_full_size(block_number):
    sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)
    sz -= MIX_BYTES
    while not isprime(sz / MIX_BYTES):
        sz -= 2 * MIX_BYTES
    return sz

위에서 계산한 cache 사이즈와 seed hash를 사용하여 cache(최초 16메가)를 생성합니다. 

캐시 생성과정에서 Sergio Demian Lerner's RandMemoHash 알고리즘을 사용합니다. (Strict Memory Hard Hashing Functions (2014))

이 알고리즘을 사용하여 연산시에 메모리가 특정 임계치보다 낮으면 연산 속도가 기하급수적으로 증가하도록 설계되어, 이를 통해 특정시간동안 특정량의 메모리가 해당 연산을 위해서만 사용되었음을 증명할수 있다고 합니다.

def mkcache(cache_size, seed):
    n = cache_size // HASH_BYTES

    # Sequentially produce the initial dataset
    o = [sha3_512(seed)]
    for i in range(1, n):
        o.append(sha3_512(o[-1]))

    # Use a low-round version of randmemohash
    for _ in range(CACHE_ROUNDS):
        for i in range(n):
            v = o[i][0] % n
            o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))

    return o

위와같이 생성한 cache 데이타를 사용하여 DAG 풀데이타를 생성하는 과정은 다음과 같습니다.

def calc_dataset_item(cache, i):
    n = len(cache)
    r = HASH_BYTES // WORD_BYTES
    # initialize the mix
    mix = copy.copy(cache[i % n])
    mix[0] ^= i
    mix = sha3_512(mix)
    # fnv it with a lot of random cache nodes based on i
    for j in range(DATASET_PARENTS):
        cache_index = fnv(i ^ j, mix[j % r])
        mix = map(fnv, mix, cache[cache_index % n])
    return sha3_512(mix)

def calc_dataset(full_size, cache):
    return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]

이제 마지막으로 DAG 화일을 사용하여 마이닝을 하는 과정은 다음과 같습니다.

hashimoto 함수의 입력으로 전달되는 header는 nonce와 mixHash를 제외한 블록의 헤더를 RLP 엔코딩후 sha3 hash한 결과입니다.

def hashimoto(header, nonce, full_size, dataset_lookup):
    n = full_size / HASH_BYTES
    w = MIX_BYTES // WORD_BYTES
    mixhashes = MIX_BYTES / HASH_BYTES
    # combine header+nonce into a 64 byte seed
    s = sha3_512(header + nonce[::-1])
    # start the mix with replicated s
    mix = []
    for _ in range(MIX_BYTES / HASH_BYTES):
        mix.extend(s)
    # mix in random dataset nodes
    for i in range(ACCESSES):
        p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes
        newdata = []
        for j in range(MIX_BYTES / HASH_BYTES):
            newdata.extend(dataset_lookup(p + j))
        mix = map(fnv, mix, newdata)
    # compress mix
    cmix = []
    for i in range(0, len(mix), 4):
        cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))
    return {
        "mix digest": serialize_hash(cmix),
        "result": serialize_hash(sha3_256(s+cmix))
    }

def hashimoto_light(full_size, cache, header, nonce):
    return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))

def hashimoto_full(full_size, dataset, header, nonce):
    return hashimoto(header, nonce, full_size, lambda x: dataset[x])

def mine(full_size, dataset, header, difficulty):
    target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
    from random import randint
    nonce = randint(0, 2**64)
    while hashimoto_full(full_size, dataset, header, nonce) > target:
        nonce = (nonce + 1) % 2**64
    return nonce

다음은 cache와 dag 데이타의 크기를 계산하는 공식입니다.

아래와 같이 DAG화일과 cache 크기는 30000 블록(에포크)마다 재계산되어 생성되며, 블록이 증가될수록 선형적으로 증가하도록 되어있고, 현재 2048 에포크까지 크기가 미리 계산되어 있습니다.

EPOCH_LENGTH = 30000              # blocks per epoch

def get_datasize(block_number):
    return data_sizes[block_number // EPOCH_LENGTH]

def get_cachesize(block_number):
    return cache_sizes[block_number // EPOCH_LENGTH]

data_sizes = [
1073739904, 1082130304, 1090514816, 1098906752, 1107293056, 
1115684224, 1124070016, 1132461952, 1140849536, 1149232768, 
1157627776, 1166013824, 1174404736, 1182786944, 1191180416, 
1199568512, 1207958912, 1216345216, 1224732032, 1233124736, 
1241513344, 1249902464, 1258290304, 1266673792, 1275067264, 

cache_sizes = [
16776896, 16907456, 17039296, 17170112, 17301056, 17432512, 17563072, 
17693888, 17824192, 17955904, 18087488, 18218176, 18349504, 18481088, 
18611392, 18742336, 18874304, 19004224, 19135936, 19267264, 19398208, 
19529408, 19660096, 19791424, 19922752, 20053952, 20184896, 20315968, 
20446912, 20576576, 20709184, 20840384, 20971072, 21102272, 21233216, 

위에서 알고리즘을 설명한 마이닝과정을 정리하면 다음과 같습니다.

mixHash는 작업증명 계산을 할때 nonce를 사용하여 생성되는 중간단계의 128바이트 hash값으로, 이 계산과정은 아주 복잡하고 많은 부하를 발생합니다. 

다음은 이대시 알고리즘의 계산식입니다.

  m : mixHash

  n : nonce

  Hn(ex) : nonce와 mixHash를 제외한 새로운 블록의 헤더

  Hn : 블록의 nonce

  d : 대용량 DAG 화일

이대시의 목적은 정확한 mixHash와 nonce값을 계산하는것입니다. 이대시가 DAG 화일을 사용하여 nonce 값을 계산하는 과정은 다음과 같습니다.

1. 이전 블록의 헤더와 임의로 추정된 nonce를 keccak256 해시를 하여 첫번째 mixHash를 구성합니다.

2. 첫번째 mixHash를 사용하여 DAG로부터 첫번째 페이지를 추출합니다.

3. 이더리움의 믹싱함수를 사용하여 추출된 DAG의 첫번째 페이지와 첫번째 mixHash로부터 다음번 mixHash를 생성합니다.

4. 이 과정을 64회 반복하여 64번째 mixHash를 생성해냅니다.

5. 64번째 mixHash값을 사용하여 32바이트의 mixDigest 값을 구성합니다.

6. 믹스다이제스트값과 미리 정의된 32바이트의 마이닝 목표값과 비교하여 믹스다이제스트값이 마이닝목표값보다 작거나 같다면 nonce는 성공한것으로 판단하고 이 nonce 값을 블록에 포함하여 다른 노드들에 브로드캐스팅합니다. 만약 믹스다이제스트값이 마이닝목표값보다 크다면  nonce 값을 하나 증가하여 앞의 과정을 반복합니다.

목표값은 / 난이도 이며, 난이도가 높아질수록 목표값이 작아지기 때문에, 마이닝시에는 더 작은 목표값을 만족하는 nonce 값을 찾기위해 더많은 hash 연산을 수행해야 하기 때문에 블록생성시간이 길어지게 됩니다. 

즉, 난이도가 낮으면 목표값이 커지고(0x0011111111....) 목표값을 만족하는 nonce를 찾기가 쉬워져서 블록생성시간이 짧아집니다.

난이도가 높으면 목표값이 작아지고(0x00000000111...) 목표값을 만족하는 nonce를 찾기가 어려워져서 블록생생시간이 길어지게 됩니다.

난이도를 계산하는 공식은 다음과 같습니다.

[비잔티움 버전의 난이도 공식]

난이도 = (부모 블록의 난이도 + 

                (부모 블록의 난이도 / 2048 * 최대값((부모 블록의 엉클블록이 조재하면 2 아니면 1) 

                 - ((현 블록  생성 타임스탬프 - 부모블록 생성 타임스탬프) // 9), -99) ) ) 

                + 난이도 폭탄

[홈스테드 버전의 난이도 공식]

난이도 = (부모 블록의 난이도 + 

                (부모 블록의 난이도 / 2048 * 최대값(1-(현 블록 생성 타임스탬프 - 부모 블록 생성 타임스탬프) 

                // 10, -99) ) ) + 난이도 폭탄

(// 는 정수형 나누기)

마지막에 존재하는 난이도 폭탄은 작업증명 방식의 마이닝을 줄이고, 신규로 개발중인 지분증명방식으로 전환하기 위해 사용됩니다.