블록체인 암호학 - 작업 증명(PoW), 양자 안정성, 머클 해시 트리

작업 증명(Proof of Work)

 

합의 알고리즘

많은 분산 시스템에서는 합의 알고리즘을 통해 일을 처리한다. 합의란 다수의 참여자가 적절한 합의 방법을 이용해 통일된 의사결정을 내리기 위해 사용하는 알고리즘을 말한다. 

 

상태 기계 복제(SMR, State machine Replication)

상태 기계가 같은 상태로 시작하면, 처리가 정상적으로 이루어졌을 경우 모두 같은 상태를 가지게 된다.

SMR같은 시스템은 일부가 고장나거나 악의적인 행동을 보여도 전체 시스템은 정상적으로 동작한다고 보장해야 한다. 

 

CFT(Crash Fault Tolerant)

서버가 단순히 고장난 형태에 대응할 수 있는 알고리즘이다.

 

BFT(Bizantine fault Tolerant)

서버가 악의적인 행동을 보일 때 대응할 수 있는 알고리즘이다.

 

합의 프로토콜의 핵심은 제안과 승인이다. 위와 같은 전통적인 분산 시스템에서는 일부 노드만이 제안 자격을 가졌다.

 

블록체인, 즉 탈중앙화된 시스템은 노드이 역할을 구분하지 않는다. 통일된 의사결정을 내리는 중앙(center)가 없다.

그러면 시스템이 정상적으로 동작한다고 보장할 수 없다. 그래서 작업 증명을 통해 제안 권한을 스스로 제한한다.

 

비트코인에서 작업 증명

이전 블록의 어떤 데이터에 대해 해시를 계산해서 나온 해시 값인 이전 해시 값(Previous Hash), 현재 블록에 대한 해시값, 그리고 논스(Nonce)가 있다. 이전 해시값과 현재 트랜잭션(Transaction)에 해당하는 값은 이미 정해져 있는데, 논스는 계속 바꾸며 테스트해볼 수 있다.

 

이 세 가지 값을 해시에 넣고 어떤 출력이 나오는지 확인하는 것이 작업 증명이다. 조금 더 보편적으로 말하자면, 특정 조건에 맞는 해시 값을 찾는 연산을 반복적으로 수행하는 것이다.

 

해시가 256비트라 해보자. 난이도가 $2^{250}$이라 생각해보면 앞에 0이 6개 정도 나오고, 뒤에는 아무 값이 나와도 상관 없다. 즉 $\frac{1}{64}$ 확률로 난이도보다 더 작은 값이 나올 수 있다. 대충 64번 시도하면 난이도를 만족하는 Nonce를 찾게 된다.

 

비트코인은 해시 값을 계산하는데 평균 10분이 걸리도록 난이도를 동적으로 조정한다. 그리고 해시를 두 번 적용하여 안정성과 유용성을 조금 더 갖추도록 난이도를 조절한다.

 

---

양자 안정성

월등한 연산 능력을 지닌 양자컴퓨터가 나오면 블록체인이 쓸모 없어지지 않을까 하는 의문을 품을 수 있다.

해시 함수의 내부에서는 입력 비트 값을 마구 섞는 알고리즘으로 구현되어 있다. 해시함수를 수식으로 표현할 수는 없다. 그러나 양자컴퓨터는 수식으로 정의된 문제를 해결한다. 따라서 해시 함수는 양자컴퓨터로도 충돌을 찾기 어렵다.

 

---

 

머클 해시 트리

 

 

출처: 위키피디아

 

해시 함수를 트리 구조로 만든 형태다. 가장 아래 부분이 데이터이다. 데이터 두 개를 받아 계산하는 과정을 반복해 계층적으로 만들었다.

 

자식 노드에 있는 값 중 어느 하나라도 달라지면 가장 위에 있는 루트 값이 변경된다. 즉, 루트 값이 변경되지 않았다면 자식값 역시 변경되지 않았음을 보장할 수 있다.

 

자식이 바뀌었는데 바뀌기 전 루트값과 같은 루트값이 나오도록 하려면 충돌을 찾는 것과 같은데, 해시가 충돌저항을 가졌기 떄문에 찾기 매우 어렵다.

 

멤버십 증명

내 트랜잭션이 많은 트랜잭션 중 하나임을 보이는 것이다.

내 트랜잭션을 보여주고, 트랜잭션을 받은 사람이 노드에 그 트랜잭션이 있는지 확인하면 된다.

다만 시간이 굉장히 오래 걸린다.

그래서 증명하고자 하는 노드와 인접한 값(copath)을 보내게 된다. 

 

내가 증명하고자 하는 값과 관련 있는 값들만 비교해서 루트 값을 얻어낸 후 원래 루트 값과 일치함을 보이는 것이다. 그러면 그 노드가 원래 트랜잭션에 포함되었다고 보장할 수 있다 . 트랜잭션이 1000개라면 $\log 1000$번만 비교하더라도 증명할 수 있다. 

 

비트코인에서는 트랜잭션에 대한 해시를 생성할 때 머클 해시 트리를 만들어서 루트 값만 해시에 넣는다. 나중에 어떤 거래가 더 이상 필요 없어지면 거래를 지우고, 해시 값만 남겨서 사이즈를 줄일 수 있다.

 

Coda는 트리 구조를 이용해 블록체인의 길이를 상수로 만든다.

---

참고 자료

 

매치업 - 블록체인을 위한 암호학과 보안성

임종철, 고남석. (2020). 세대별 블록체인 합의 알고리즘. 한국통신학회지(정보와통신), 37(3), 3-12.

ko.wikipedia.org/wiki/%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84_%EB%B3%B5%EC%A0%9C

wiki.hash.kr/index.php/%ED%95%A9%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

wiki.hash.kr/index.php/%EC%9E%91%EC%97%85%EC%A6%9D%EB%AA%85