그래서 비트코인이 뭔데?

chris0205.eth·2022년 5월 8일

Bitcoin blockchain consensus algorithm

비트코인

목록 보기

1/2

비트코인이 해결하고자 하는 것

기존의 금융권은 투명하지 않고, 접근성에 제한이 있었기 때문에 이에 대한 대안으로 사토시 나카모토(가명)란 사람(혹은 기관)이 비트코인을 2009년도에 개발하였다.
다음 이미지를 보자.

디지털 화폐로써의 가치를 갖기 위해선 두 가지 문제를 해결해야 한다.

신원인증
이중지불문제

So...

각각의 문제들에 대한 해결책을 제시한 것이 2009년 나온 사토시의 비트코인 백서이다.
사토시는 위와 같은 문제들을 다음과 같이 해결하였다.

전자서명(digital signature)
합의 알고리즘(PoW)

각각에 대해서 자세하게 한번 살펴보자.

전자서명

digital signature

트랜잭션을 보낼때, 전자서명을 하는 기술을 통해서 신원 인증 과정을 제거하였다.

트랜잭션

자산의 상태를 변화시키는 단위이며, 디지털 자산의 거래에 대한 데이터(송금 및 결제)를 담을 수 있다.

이러한 디지털 자산에 대한 소유권을 가진 참여자만이 해당 트랜잭션을 발생시킬 수 있어야 한다.

그러기 위해선, 전자서명 기술이 필요하고, 이때 사용되는 것이 공개 키(Public key) 암호화 방식이다.

공개키 암호화 방식(비대칭키 방식)

암호화와 복호화에 쓰이는 키(각각 비공개키, 공개키)가 다른 암호화 방식이다.

private key는 정보를 암호화하는데 사용되므로, 본인만이 가지고 있어야 하는 키이다.

RSA 등이 대표적인 공개키 방식이다.

CHF(Cryptographic Hash Function), 암호학적 해시 함수

임의의 데이터(message)를 일정한 길이의 문자열(hash value, message digest)로 바꿔주는 단방향(one-way)함수이다.

단방향 함수는 input으로 output을 도출해내긴 쉽지만, output으로 input을 찾기는 매우 어렵다. message가 아주 조금만 바뀌어도 digest는 전혀 다른값을 출력(avalanche effect)하기 때문에 output으로 input을 추론하기 어렵다.

또한, 같은 input은 항상 같은 output을 출력하므로, 결정적(deterministic)이며, 검증(verification)이 쉽다.

전자서명 생성 과정

트랜잭션을 해시 함수를 이용해 해싱하고, 그 값을 private key로 암호화하여 전자서명을 만든다.

이때, 트랜잭션과 암호화한 전자서명 두가지를 모두 비트코인 네트워크로 보낸다.

전자서명을 이용한 트랜잭션 검증 과정

사용자가 private key로 만든 전자서명과 트랜잭션을 비트코인 네트워크로 보내면, 이 네트워크에서 공개키로 트랜잭션의 유효성을 확인할 수 있다.

우선, 전자서명을 생성할 때 사용한 해시함수와 동일한 것으로 해시값을 얻는다. 그리고 전자서명을 공개키로 복호화하여서 해싱한 해시값과 같은 값을 가지는지 확인을 한다.

이 두개의 값이 같다면 해당 공개키에 대응하는 비밀키를 가진 사용자가 보낸 트랜잭션이 맞으므로 신원이 인증되었다고 볼 수 있다.

즉, 비밀키로 자신의 자산에 대한 소유권을 주장할 수 있다.

그러나, 이러한 전자서명만으로 해결되지 않는 문제가 있는데, 그것은 바로 이중지불문제(double-spending problem)이다.

합의 알고리즘(PoW)

전자서명을 이용하면, 디지털 자산이 소유자만이 그 자산을 거래하는 트랜잭션을 발생시킬 수 있다.
그러나, 한 사람이 여러 개의 모순되는(incompatible) 트랜잭션들을 발생시키는 것은 막을 수 없다.

이러한 이중지불문제가 발생했을 때, PoW라는 합의 알고리즘(consensus algorithm)을 통해 해결할 수 있다.

이중지불문제

한 사람이 한 가지 자산을 여러사람에게 보내지 못하도록 하여야 한다.

비잔틴 장군 문제

Byzantine General’s Problem

이중지불문제는 비잔틴장군문제로 치환 가능하다.

다른 왕국을 정복하기 위해 장군들은 공격을 한번에 해야하는데, 배신자들이 그러한 공격 명령을 조작하는 것이다. 이러한 상황에서 어떻게 공격을 성공적으로 합의할 수 있을지에 대한 논의가 비잔틴 장군 문제이다.

가정) 모든 메세지가 올바르게 전달되고, 믿을만한 채널을 사용하며, 모든 메세지가 동기적으로 전달.

이런 상황에서 배신자의 수가 전체 장군의 1/3 미만이면 합의에 도달할 수 있다!

BFT / PBFT

위와 같은 비잔틴 장군 문제로부터 나온 합의 알고리즘이 pBFT이다. 더 자세한 내용은 전에 작성한 ‘합의 알고리즘 : PBFT’를 참고하기 바란다.

간단하게 설명하자면, 앞의 가정을 만족시키기 위해서 제한된 참여자가 각각 하나의 투표권을 행사하기 때문에 1)과반 이상의 노드가 시스템에서 나가거나, 2)시스템에 참여하면 시스템이 망가지거나 중단될 수 있다.

또한, 배신자 수(t)와 노드 수(n)에 따라 합의를 위해 필요한 메세지의 수가 기하급수적으로 증가( $O(n^{t-1})$ 에 비례해서 증가) 하기 때문에 많은 배신자를 감당하기 위해 노드를 많이 늘릴수가 없는 상황이다.

따라서 전통적인 합의 알고리즘으로는 비잔틴 장애를 허용하는 개방형 네트워크를 만들 수 없다.

Nakamoto’s consensus

PBFT는 메세지 패싱 방식의 합의 알고리즘이기 때문에 노드 수가 많아지거나 적어지면 합의에 어려움이 생기기도 한다. 따라서 사토시 나카모토는 비트코인에 다른 합의 알고리즘, PoW를 적용한다.

합의의 단위 : 블록(block)

블록은 합의 및 P2P 네트워크의 상태를 동기화시키는 단위이다. 이 블록에는 서로 모순되지 않는 트랜잭션들을 모아서 처리하고 블록 상태(block state)를 만든다. 이때, 블록 상태는 각 트랜잭션의 모든 과정을 나타내지 않고 각 트랜잭션의 마지막 트랜잭션, 즉 UTXO(Unspent Transaction Output)들의 합으로 표현된다.

블록체인(blockchain)

블록은 이전 블록을 참조함으로써 순서를 명시하기 때문에 블록체인이라고 불린다.

이때, block state는 UTXO의 집합이고, UTXO의 부분집합이 최신 블록에서소비되고 새로운 UTXO들을 만들어냄으로써 block state가 업데이트된다.

따라서 최신 블록 상태를 알기 위해서는 모든 블록을 탐색하면서 UTXO 집합을 완성해야 한다.

블록의 전파(propagation)

블록은 위와 같이 트랜잭션들(UTXO)를 담은채로 체인과 같이 생성된다.

그렇담 이러한 블록이 어떤식으로 노드들에게 전파가 되는 것일까?

Gossip protocol(epidemic protocol)

P2P 네트워크에서 각 노드가 이웃 노드에게 데이터를 전달하는 방법이다.

Bandwidth(대역폭)의 낭비를 줄이면서도 데이터를 빠르고 안정적으로 전파할 수 있으며, 대부분의 블록체인은 가십 프로토콜을 사용하여 트랜잭션 및 블록을 다른 노드들에게 전파한다.

이렇게 블록을 모든 노드들이 동기화하여 갖고 있게 되면, 다음 블록을 생성하여 다시 전파를 하는 방식으로 진행된다.

그런데, 누가 블록을 생성할지에 대해선 아직 논의하지 않았다.

블록의 생성

앞서 언급한 PBFT 방식에선 보통 노드 수가 정해져 있고, view change protocol에 의해 노드들이 돌아가면서 블록을 생성한다. 그러나, Nakamoto’s consensus는 그런식으로 할 수 없다. 노드의 수가 정해져있지 않은 개방형 네트워크이기 때문이다. 따라서, 누구나 블록을 생성할 수 있도록 해야 한다.

악의적인 블록 생성자와 race condition(블록생성속도>네트워크 전파 속도)을 방지하기 위해 어떤 장치가 필요한데 그것을 random timer로 해결한다. 블록생성 속도를 의도적으로 늦추어서 모든 노드들이 같은 블록으로 동기화한 후에 새로운 블록을 전파하면 문제가 해결된다.

한 논문에 의하면, 90%이상의 노드에게 블록이 전파되기 전에 블록이 생성되면, 블록체인이 하나의 블록으로 수렴할 수 없다는 결과가 있다.

Cheat-resistant timer

각 노드가 random timer를 조작할 수 없어야 한다.
동시에 블록 생성 속도를 원하는 범위로 조절할 수 있어야 한다.
속도가 너무 빠르면, 늦추고, 너무 늦으면 가속화할 수 있어야 한다.(노드의 수가 달라지기 때문)

Proof-of-Work

랜덤 타이머를 작업 증명 방식을 사용해서 만든다.

블록을 만들때, 일정량의 컴퓨팅 파워를 소모하도록 한다. 그 컴퓨팅 파워로 확률적으로 어떤 값을 찾도록 만들고, 그 값을 찾은 노드만이 블록을 만들 수 있도록 해주고, 이러한 작업증명은 블록을 seal(봉인)할 수 있게 해준다. sealing block만이 유효한 블록으로써 네트워크에 전파될 수 있다.

좀 더 자세하게 설명하자면, 컴퓨팅 파워를 소모해서 nonce라고 하는 블록에 포함되어 있는 값을 찾는 것이다. 블록을 해싱해서 나오는 nonce값이 특정 값과 같아질때까지 nonce값을 변경하여서 trial을 반복한다.

작업 증명은

DoS(Denial of Service) 공격이나 스팸 메일 등 시스템이나 네트워크에 악영향을 끼치는 행위를 방지하기 위한 기술
시스템이나 네트워크를 이용할때 경제적인 비용이 청구되도록함으로써 대량의 요청을 할 수 없도록 방지한다.

Hashcash (Adam Back, 2002)

output 값이 특정 조건을 만족할 때까지, 해시함수에 무차별대입(brute-force)하여 조건을 만족하는 input을 찾는 방법이다.
해시는 단방향 함수이기 때문에, 조건을 만족하는 input을 찾았단 것은 컴퓨팅 파워를 소비했다는 증거이다.
증명하고자 하는 메세지에 특정 길이의 논스를 붙이고, 이 논스를 변화시키며 조건을 만족시키는 output을 찾는다.

hashcash에선 sha-1 함수를 사용하는데, 이는 160bits의 값을 제공한다. 즉, 40자리의 수가 나온다.

보통 output 조건은 leading zeros가 몇개냐로 결정하는데, 만약 leading zero를 12개가 나오도록 output 값을 조절하라고 하면, 걸리는 평균 시간의 역수는 다음과 같이 표현될 수 있다.

(이때, 논스는 16진수이다.)

$N=\frac{16^{28}}{16^{40}} \times hashrate(H/s)$

비트코인의 PoW

비트코인에서는 헤더 값을 sha256으로 해시해서 나오는 값이 특정 난이도로 계산되는 값보다 작도록 nonce를 조절하고 찾는다. 이렇게 찾아진 hash값이 해당 블록의 block hash가 되는 것이고, 블록 헤더가 이전 블록의 hash값을 포함하기 때문에 블록들은 순서를 가지며, 리스트 형태로 체인을 구성한다.

이러한 nonce 값을 찾는 과정을 mining이라고 한다.

이러한 과정을 통해 블록을 누구나 만들 수 있지만, 아무나 만들순 없게 설정했다.

그러나, PoW를 적용해도 여러 블록이 동시에 생성되어서 전파될 수도 있다.

이러한 경우에 체인 선택 규칙을 적용한다.

Longest chain rule

타이머(PoW)를 이용하여도 여러 블록이 동시에 생성될 수 있다. 이러한 경우, 비트코인은 가장 긴 체인을 선택하는 규칙을 적용하여 나카모토 컨센서스를 완성하였다.

가장 긴 체인을 canonical chain이라고 부르며, longest chain rule에 의하여 canonical chain이 바뀌는 현상을 reorg(reorganization)이라고 부른다. 이러한 reorg가 자주 일어나지 않아야지 안정적으로 서비스가 가능할 것이다.(최신 블록이 자주 바뀌면 혼란이 가중된다.)

PoW와 Longest chain rule을 합쳐 Nakamoto’s consensus라고 부른다.

비트코인의 security

나카모토 컨센서스 상에서 공격자가 네트워크를 공격하기 위해선 side chain을 채굴하여 canonical chain보다 길어지도록 reorg를 유도해야 할 것이다.

공격자가 정직한 노드보다 많은 컴퓨팅 파워를 소모해야 하므로, 정직한 노드가 가진 컴퓨팅 파워가 전체 컴퓨팅 파워의 절반이상이면 안전하다.

사토시는 정직한 노드가 가진 컴퓨팅 파워가 공격자의 컴퓨팅 파워보다 크단 것을 가정하고(51% rule), 푸아송 분포를 이용해 공격자가 6개의 블록을 지나는 동안 canonical chain을 유지하는 것이 거의 불가능함을 수학적으로 증명했다.

따라서, 특정 트랜잭션이 포함된 블록 뒤에 6개의 블록이 더 생성되면, 확률적으로 reorg가 발생할지 않을 것이므로 트랜잭션의 finality를 보장할 수 있다.

마치며

블록체인의 시작이라고 볼 수 있는 비트코인의 원리(전자서명, 합의알고리즘)에 대해 다뤄보았다.

블록의 크기와 블록 인터벌을 함부로 조작하면, 보안이 취약해지는 영향이 있을 수 있단 것을 알게 되었다. 비트코인 외의 다른 레이어1의 블록체인들을 살펴보며, 비트코인과 어떤 점이 다르고, 블록체인 트릴레마(탈중앙성, 보안성, 확장성)을 어떤식으로 해결해나가고 있는지 살펴볼 계획이다.