모든 것은 경쟁이고 나카모토는 항상 승리한다
사토시님은 모두의 위에 계셨다
Hyunbin Jeong in CURG
Title : Everything is a Race and Nakamoto Always Wins
Authors : Amir Dembo, Sreeram Kannan, Ertem Nusret Tas, David Tse, Pramod Viswanath, Xuechao Wang, Ofer ZeitouniPrincipal Keyword : Security
2020. 10 ACM SIGSAC CCS (link)본 포스팅은 ACM CCS 2020에 Accepted 된 논문 ‘Everything is a Race and Nakamoto Always Wins’ 의 내용을 바탕으로 쓰여졌으며, 해당 논문의 도입부와 논문의 저자들이 제시하는 접근법을 간략히 소개(라 쓰고 적당히 직역이라 읽음)함으로써 본 논문을 읽고자 하는 분들에게 조금이나마 도움을 주고자 하였다.
비트코인 개발자 사토시 나카모토는 Longest Chain Protocol을 고안하였고, Private Double-Spend Attack (정직한 노드와 공격자 노드 간 더 긴 체인을 만들기 위한 경쟁) 방법을 분석하여 자신의 프로토콜이 안전함을 주장했다. 하지만 과연 그 공격이 최악의 공격 방법이었을까?
본 논문의 저자들은 위 질문에 답하기 위해 아래의 서로 다른 합의 모델로 설계된 세 가지 종류의 Longest Chain Protocol의 보안을 분석하고,
- 나카모토의 오리지널 작업증명 (PoW) 프로토콜
- 우로보로스(Ouroboros)와 스노우화이트(SnowWhite) 지분증명 (PoS) 프로토콜
- 치아(Chia) 공간증명 (PoSpace) 프로토콜
그 결과 다음에 대한 정확한 정의(exact characterization)를 얻는다.
‘네트워크 지연에 의해 정규화되는 평균 블록 생성 시간에 따라, 각 프로토콜에서 허용 가능하게 되는 공격자 파워의 상한’ (The maximum tolerable adversary power for each protocol as a function of the average block time normalized by the network delay)
또한 이 세 가지 프로토콜의 보안을 분석하는 과정에서 저자들이 고안한 새로운 접근법이 도입되었으며, 저자들은 이를 논문의 주요 기여 사항으로 언급하고 있다.
비허가형(permissionless) 환경에서 가치가 부여된 자산의 원장을 유지하는 데에 있어 Longest Chain Protocol의 가장 중요한 속성은 보안이다. 이미 확정된 거래를 되돌려 프로토콜을 공격하기 위해 공격자는 어느 정도의 리소스를 투입해야 하는가?
λh와 λa를 각각 정직한(honest) 노드와 공격자(adversary)의 해시 파워에 따른 블록 채굴 비율(rate)이라 하자.
만약 λa > λh 일 경우, 체인의 깊이(deep) k가 얼마나 큰가에 관계없이 공격자는 높은 확률로 공격에 성공할 것이고, 반대로 λa < λh 일 경우, 공격 성공 가능성은 k의 값에 따라 기하급수적으로 감소할 것이다.
정직한 노드들 간에 Δ 만큼 네트워크 지연이 있다고 가정하면, 식 λa < λh 로부터 다음을 얻는다.
여기서 λgrowth(λh, Δ)는 최악의 분기 상황(worst-case forking)에서 정직한 체인의 블록 증가율을 의미한다.
많은 정직한 노드가 각각 작은 채굴 파워를 가진 완전히 탈중앙화된 환경에서, [SZ15](Secure high-rate transaction processing in bitcoin, link)는 식 1의 우변을 다음과 같이 계산하는데,
이 때 공격자의 파워 비중(fraction of power)을 β 라 하면, 식 1 로부터 다음을 얻는다.
λ - 전체 채굴 비율 (total mining rate)
λΔ - 네트워크 지연에 따라 채굴된 블록의 수 (the number of blocks mined per network delay)
1 / (λΔ) - 네트워크 지연에 의해 정규화된 블록 생성 속도 (block speed normalized by the network delay)
식 2 의 부등호를 등호로 치환하여 β에 대해 풀면 보안 임계값(security threshold) βpa(λΔ)를 얻는데, 만약 λΔ의 값이 작으면 βpa(λΔ)는 0.5에 수렴하고, 이는 [Nak08](Bitcoin: A peer-to-peer electronic cash system, link)에서의 나카모토의 다음과 같은 주장과 상통한다.
‘채굴 비율이 낮게 설정되어 있고 공격자가 전체 해시 파워의 50% 미만의 파워를 갖는 한 Longest Chain Protocol은 안전하다’ (The longest chain protocol is secure as long as the adversary has less than 50% of the total hashing power and the mining rate is set to be low)
블록체인의 속도를 높이기 위한 더 공격적인 채굴 속도는 보안 임계값을 낮추게 되고, 따라서 식 2는 보안과 블록 생성 속도 간의 트레이드오프를 나타낸 것으로도 볼 수 있다.
위 그림은 기존 연구에서 제시된 보안 임계값과 비교한 ‘진짜(true)’ 보안 임계값 β*(λΔ)이 그리는 곡선(파란색)을 보여주는데, (a) PoW 모델과 (b) PoS 모델에서 그 값이 같음을 알 수 있다.
또한 모든 케이스에 대하여 β*(λΔ) (True Security Threshold)와 βpa(λΔ) (Private Attack Threshold)가 같음을 알 수 있으며, 이를 다음과 같이 표현한다.
저자들은 모든 프로토콜에서 True Security Threshold와 Private Attack Threshold가 같은 것은 우연이 아니며, 이는 Private Attack과 그 외 일반적인 공격 방법들 간의 밀접한 연관성 때문이라고 설명하는데, 이 연관성을 드러내기 위한 접근법으로 아래의 두 가지 핵심 개념을 정의한다.
- blocktree partitioning
- Nakamoto blocks
이 두 개념을 통해 어떠한 공격 방법이라도 공격자와 정직한 체인들 간의 경쟁(race)으로 간주(view)할 수 있다.
Private Attack의 경우, 정직한 블록과 공격자 블록 모두로 구성된 전체 blocktree가 특히 단순해지고 그림 2 (a)와 같이 한 개의 정직한 체인과 다른 한 개의 공격자 체인으로 나눌 수 있다.
반대로 공격자가 다수의 상황에서 공개 블록들을 만들어낼 수 있는 일반적인 공격 상황의 경우 그림 2 (b)의 왼쪽과 같이 더 복잡한 blocktree가 생길 수 있다.
여기서 저자들이 주목한 것은, 이 한 개의 복잡한 blocktree를 그림 2 (b)의 오른쪽과 같이 ‘하나의 정직한 블록을 루트로 하고 나머지 전체가 공격자 블록으로 구성되어 있는’ 여러 개의 서브 트리(sub-trees)로 분할(partitioning)하면, 이러한 공격 상황을 ‘다수의 공격자 서브 트리가 정직한 블록으로만 구성된 가상의 단일 체인과 경쟁하는’ 것으로 볼 수 있다는 점이다.
각 공격자 서브 트리의 성장속도는 Private Attack에 쓰인 공격 체인의 성장 속도에 의해 제한되고(The growth rate of each of these adversary sub-trees is upper bounded by the growth rate of the adversary chain used in the private attack), 따라서 만약 Private Attack이 실패할 경우 각 공격자 트리의 성장 속도가 가상의 정직한 체인보다 낮았으리라 생각할 수있다.
논문을 통해 저자들이 보이고자 한 것은, 앞서 언급한 세 종류의 프로토콜에 대하여, 위와 같은 상황에서 ‘정직한 체인이 생성한 뒤로 어떠한 공격자 트리도 절대로 따라잡을 수 없는’ 속성을 가진 정직한 블록이 반드시 존재하고, 이러한 블록을 나카모토 블록(Nakamoto blocks)이라 명명한 것이다.
나카모토 블록은 블록체인을 안정시키는 역할을 하고, 그러한 블록이 blocktree에 포함되면, 그 blocktree의 복잡도에 관계없이 해당 블록까지의 Longest Chain은 이후 불변으로 남을 것임이 보장된다.
논문 저자 주 _ 따라서, 나카모토 블록은 마치 신과 같은 영속성을 가지고 있으며, 그것이 존재하여도 누구도 그 블록이 나카모토 블록이라는 것을 모른다.(Thus, Nakamoto blocks have a god-like permanence, they exist, but nobody knows which block is a Nakamoto block.)
나카모토 블록이 빈번하게 등장할 수록, 블록체인의 지속성(persistence)과 동시성(liveness)이 보장된다.
이제 본문을 읽기 위한 준비가 끝났다.
논문 이야기 끝
결론을 빙자한 잡담
최근 ACM CCS에 통과된 논문 목록을 보다가 재밌어 보이는 제목으로 쓴 것이 눈에 띄었고, 저자들의 출신이 스탠포드로 근본이었기 때문에 흥미를 갖고 읽어보게 되었다.
도입부를 읽으며 느낀 것은 이 논문의 저자들이 사토시 나카모토를 정말로 신성시하고 있구나 하는 일종의 감탄스러움이었다.
본래 계획은 논문의 2챕터를 제외한 나머지 3~5챕터까지 다루는 것이었으나, 필자의 독해 속도 부족과 평소 필자가 말하는 ‘글을 대강 이해하는 것과 제대로 이해한 뒤 설명하는 것은 다른 영역’ 에 따라 본 논문을 완전히 이해하기에는 필자의 시간과 근성이 부족했기 때문에 논문의 1챕터인 도입부를 가능한 끄적인 것으로 봐 주었으면 하는 바람이다.
필자가 추측하건대 본 논문의 저자들은 아마도 2020년 상반기에 스탠포드 공대에서 열렸던 블록체인 확장성 강의(link)의 교수 및 수강생들인 것으로 보인다. 따라서 본 논문의 내용을 훑어본 뒤에 관심이 있다면 해당 강의의 자료를 찾아가 보는 것도 괜찮지 않을까 생각한다.
