비트코인 마이닝

채굴(마이닝)

채굴(마이닝, Mining)이란 새로운 블럭을 블럭체인에 추가하는 작업으로서, 비트코인과 같이 Proof of Work (PoW) 알고리즘을 사용하는 경우, 어느 정도 난이도 있는 작업을 수행했음을 증명하여야만 블럭을 새로 추가할 수 있게 된다. Proof of Work(PoW)이란 블럭을 쉽게 추가하지 못하게 하면서 일정 기간 특정 작업(예: 블럭해싱)을 수행하도록 하고, 이 작업을 가장 먼저 성공한 노드에게 새 블럭을 추가할 수 있도록 하는 것이다. 새로운 블럭을 추가하는 노드는 그 댓가로 Block Reward 비트코인을 얻게 된다.

비트코인 채굴은 추가하고자 하는 블럭의 블럭 해시값이 네트워크에서 지정한 Target 해시값보다 작을 경우 채굴이 성공하도록 하는 방식을 사용한다. 이는 다르게 표현하여, 블럭 해시값의 앞부분 N 개의 비트들이 0 이면, 채굴에 성공한 것으로 인정하는 것이다. 이때, 이 N개의 비트는 블럭헤더에 Bits (혹은 nBits)로 표시되며, "블럭해시를 찾는 것이 얼마나 어려운가"를 나타내기 때문에 흔히 "Difficulty"라고 불리운다. Difficulty가 낮으면 블럭해시를 구하기가 쉬울 것이고, Difficulty가 높으면 블럭해시를 구하기가 어려울 것이다.

Difficulty는 매 2016개의 블럭마다 비트코인 네트워크에서 다시 설정된다. 이는 비트코인의 블럭 생성시간을 평균 10분으로 맞추기 위한 것이다. 만약 Difficulty가 너무 낮으면 너무 빨리 블럭이 생성될 것이고, 반대로 Difficulty가 너무 높으면 블럭생성이 10분을 넘길 것이다. 따라서, 2016 블럭마다 평균 블럭 생성 기간을 계산해서, 다음 2016 블럭들에 대한 Difficulty (즉, nBits)를 계산하게 된다.

해시캐시 (Hashcash)

해시캐시(Hashcash)는 암호학적 해시에 기반한 작업증명(Proof of Work) 알고리즘으로, 1997년 Adam Back에 의해 제안되었다. 해시캐시는 어떤 데이타를 해싱한 결과가 어떤 정해진 조건을 만족하도록 계속해서 해싱을 반복하도록 하는 것으로, 특정 조건을 갖는 해시값을 알아내는 것을 어느 정도의 수준에서 어렵지만, 이를 검증하는 것은 매우 쉽다는 특성을 가지고 있다.

1992년 Dwork & Naor는 "Pricing via Processing or Combatting Junk Mail" 페이퍼에서 스팸 이메일을 방지하기 위하여 사용자가 이메일 사용 전에 어느 정도의 작업을 수행하도록 하는 아이디어를 발표하였다.

"Pricing via Processing or Combatting Junk Mail"
We present a computational technique for combatting junk mail in particular and controlling access to a shared resource in general. The main idea is to require a user to compute a moderately hard, but not intractable, function in order to gain access to the resource, thus preventing frivolous use. To this end we suggest several pricing functions, based on, respectively, extracting square roots modulo a prime, the Fiat-Shamir signature scheme, and the Ong-Schnorr-Shamir (cracked) signature scheme.

1997년 영국의 암호전문가 Adam Back은 Dwork & Naor와 비슷한 개념의 해시캐시(Hashcash)를 발표하였다. 해시캐시는 수신자의 이메일 주소가 포함된 간단한 이메일 헤더를 SHA1 으로 해싱하여 그 해시값의 처음 20비트가 0 인지를 체크한다. 이메일 헤더에는 카운터(counter)가 들어가는데, 만약 앞의 20비트가 0 이 아니면, 이 카운터를 하나 증가시켜 다시 해싱을 진행한다. 이러한 방식으로 타겟이 되는 해시값을 찾으면, 이메일을 보낼 수 있게 된다.

아래는 Hashcash 헤더의 예인데, 첫부분 1은 버전을 의미하고, 20은 20비트가 0이어야 함을 뜻한다. 1613932843은 현재 시간을 나타내는 Timestamp이고, 그 다음에는 수신자의 이메일 주소 (혹은 IP 등과 같은 리소스)가 들어간다. 다음 컬럼은 버전 1에서 무시되고, 그 다음은 랜덤 문자열을 Base64 인코딩한 값(McMybZIhxKXu57jd)이 들어가고, 마지막 ckvi은 카운터를 Base64 인코딩한 값이다.

    X-Hashcash: 1:20:1613932843:alex@cryptostudy.xyz::McMybZIhxKXu57jd:ckvi

해시캐시를 통해 일반 이메일 사용자는 메일 작업에 거의 불편을 느끼지 않겠지만, 스팸 이메일을 보내는 측은 짧은 시간에 수많은 이메일을 보내는 것이 매우 힘들어지게 될 것이다.

기술적으로 해시캐시의 기본적인 아이디어는 "적당하게 어려운" 작업을 만들어 내는 것이다. 해시값으로부터 원래의 메시지는 찾는 것은 현재 기술적으로 불가능한(computationally intractable) 작업이지만, 해시값의 일부가 0 인 것을 찾는 것은 어느 정도 시간이 소요되겠지만 가능한 일이다.

해시캐시의 이메일 스팸 방지 기능은 처음에 일부 이메일 서비스에서 사용되었지만, 점차 사용되지 않게 되었다. 하지만, 해시캐시의 이러한 작업증명 방식은 뒤에 비트코인의 Proof of Work에서 사용되면서 다시 한번 널리 알려지게 되었다.

마이닝 타겟

블럭헤더에는 Difficulty를 표현하는 Bits (nBits)라는 필드가 있는데, 이것을 통해 Target 값을 구하게 된다. 만약 계산된 블럭 해시값이 이 Target 값보다 작다면 마이닝에 성공하게 된다.

블럭헤더에 있는 Bits 필드^{(4 바이트)}는 Target 값^{(32 바이트)}을 축약해서 표현하고 있는데, Bits는 (일반적인 10진수 대신) 256 진수를 사용하여 유효자리 표기법으로 표현한다. Bits는 4 바이트 수인데, 뒤의 3 바이트가 유효자리 수를 나타내고, 맨앞의 1 바이트가 지수를 나타낸다. 예를 들어, Bits = 0x181b8330 인 경우, 1b8330 가 유효자리(significand) 수이다. 첫번째 바이트 0x18은 256 비트^{(32 바이트)}의 지수(exponent)를 의미한다. 단, 유효숫자 3자리이므로 256 ^ (0x18 - 3) 와 같이 유효숫자를 빼고 계산한 후, 여기에 다시 유효숫자 1b8330 을 곱하게 된다. 이것을 식으로 나타내면 아래와 같다.

    Target = significand * 256 ^ (exponent - 3)

    사례) nBits = 0x181b8330
            = 0x1b8330 (significand) * 256 ^ (0x18 - 3)  

        256 ^ 0x18 : 전체 자리수를 나타냄
        18 - 3 : 유효자리수(significand)가 항상 3 바이트이므로 전체 지수에서 3을 뺌 
        256 ^ (0x18 - 3) : 총 21 개의 0x00 바이트가 뒤에 붙음
        => 0x1b8330000000000000000000000000000000000000000000

아래는 nBits를 Target값을 변환하는 C# 코드이다.

    public static BigInteger GetTarget(uint nBits)
    {
        uint significand = (nBits << 8) >> 8;  1 ~ 3 bytes of nBits
        int exponent = (int)(nBits >> 24);     first byte of nBits

        BigInteger target = significand * BigInteger.Pow(256, exponent - 3);
        return target;
    }

블럭 마이닝

블럭 마이닝(Block Mining)은 기본적으로 블럭헤더의 Nonce값을 증가시켜 가면서 Target 해시값보다 낮은 블럭 해시값을 구하는 작업이다. 블럭해시는 블럭헤더만을 해싱하여 구하며, 블럭바디는 직접적으로 포함되지 않는다. 블럭바디의 트랜잭션 데이타들은 이를 해시로 요약한 Merkle Tree에 의해 표현될 수 있고, Merkle Tree의 해시들을 요약한 Merkle Root가 블럭헤더에 포함되어 있으므로, 블럭바디가 간접적으로 블럭해시에 포함된다고 볼 수 있다.

일반적으로 Nonce값을 증가시키면서 Target에 맞는 블럭해시값을 구할 수 있지만, 32bit의 Nonce를 모두 소진해도 Target을 찾지 못하는 경우에는, 블럭바디의 첫번째 트랜잭션인 Coinbase 트랜잭션 안의 데이타를 변경해 가면서 블럭해시를 찾는다. Coinbase 트랜잭션이 변경되면 Merkle Root가 변경되어 다시 블럭헤더가 변경되는 효과가 있다. 또다른 방식으로 블럭헤더의 Timestamp를 약간 변경하거나 새 트랜잭션을 블럭에 추가하면서 블럭해시를 찾을 수도 있다.

public class Block
{
    ...생략...

    public bool MineBlock(uint startNonce = 0, uint endNonce = uint.MaxValue)
    {
        if (!ValidateBlock()) return false;

        BlockHeader hdr = this.Header.Clone();
        BigInteger target = GetTarget(hdr.Bits);
        bool found = false;

         hashcash proof of work
        for (uint i = startNonce; i <= endNonce; i++)
        {
            hdr.Nonce = i;
            var h = hdr.Serialize().ToDoubleHash();
            
            var revhash = new BigInteger(h, true, false);  reversed hash
            if (revhash <= target)
            {
                this.Header.Nonce = hdr.Nonce;
                found = true;
                break;
            }
        }

         still not found?
         - use extraNonce in coinbase if not found
         - timestamp can be adjusted (which is why the timestamp in mined blocks is often wrong). 
         - add new tx 
         ...

        return found;
    }
}