[MIT OCW] 2. Proof of Work and Mining

이 글은 MIT OpenCourseWare 의 MAS.S62 - Cryptocurrency Engineering and Design의 강의를 요약, 정리 한 것입니다..

글을 읽으실 때 이해를 위하여 원 강의를 함께 보시는 것을 추천합니다.

*글에 포함된 이미지는 강의에서 제공되는 Lecture Note로부터 캡쳐한 것입니다.

 

1. Problems of Digital token transfer

디지털 결제 시스템에서 나타날 수 있는 잠재적인 문제로는 아래와 같은 것들이 있습니다.

 

• 보안 문제 (Intercept transfer and steal funds)
  • 다른 사용자가 결제 전송을 가로채서 자금을 훔칠 가능성을 방지해야 합니다.
  • 시스템이 이러한 기본적인 보안을 제공하지 못하면 신뢰를 얻을 수 없으며 사용자가 이를 채택하지 않을 것입니다.
• 허가되지 않은 지출 방지 (Spend money without authorization)
  • 사용자가 허가 없이 돈을 사용할 수 없도록 보장하는 메커니즘이 필요합니다.
  • 예를 들어, 앨리스가 결제를 요청할 때, 시스템이 실제로 앨리스임을 확인할 수 있어야 합니다.
• 이중 지출 문제 (Double Spend Problem)
  • 디지털 토큰은 쉽게 복제될 수 있으므로, 한 번 사용된 토큰이 다시 사용되지 않도록 해야 합니다.
  • 단순히 고유한 문자열을 사용하는 방식은 이 문제를 해결할 수 없습니다. 추가적인 설계가 필요합니다.
• 모순 문제 (Equivocation Problem)
  • 결제가 이루어진 후 쉽게 취소되거나 변경되지 않도록 해야 합니다.
  • 앨리스가 결제한 후, 이를 번복할 수 없도록 시스템이 설계되어야 합니다.

탈중앙화된 디지털 토큰 거래를 구현하기 위해서는, 아래와 같은 특징을 가져야 할 것입니다.

 

• 아무나 사용할 수 있다.(Anyone can use it) -> Permissionless (무허가성)
• 신원이 확인된 거래 (Authoritative transfer) -> No double spends(이중 지불 문제 해결)
• 완료된 거래에 대한 번복 불가(Can't undo spend) -> Tamper-proof (철회 방지)

2. Fault Tolerance

분산 네트워킹에서 이러한 특성들을 구현하기 위해 필요한 것이 Distributed Consensus(분산 합의)입니다.

이는 여러 노드가 하나의 문제에 대해 동의하는 과정을 의미하며, 모든 참여자가 동일한 순서로 데이터를 처리하도록 보장합니다.

그러나 분산 네트워킹의 경우, 일부 노드가 사라지거나, 악의적인 공격을 하는 등의 방해가 생길 수 있습니다. 이러한 상황에서도 분산 네트워크의 데이터 일관성을 유지하기 위해 Fault Tolerance(장애 허용)의 개념이 만들어집니다.

 

단순히 일부 노드가 사라지는 경우의 장애를 허용하는 것을 Crash Fault Tolerance(CFT)라고 하며, 이는 기존의 Paxos, ZooKeeper, Raft와 같은 프로토콜이 해당합니다.

 

비잔틴 장애 허용(Byzantine Fault Tolerance)은 분산 네트워크 상에서 악의적인 장애를 일으키려는 노드들을 일부 허용함에도 합의가 올바르게 이뤄질 수 있도록 합니다.

 

이러한 시스템의 단점은, 현재 모든 노드의 신원을 우리가 알고 있을 때 가능하다는 것입니다. 만약 악의적인 공격을 위해 여러 가짜 신원들을 생성하여 네트워크에 참여하는 경우,(이를 Sybil Attack이라 합니다.) 정상적인 합의 과정이 일어나지 않을 것입니다. 이를 해결하는 방법 중 하나는, 신원을 생성하는데 비용이 들도록 하는 것입니다. 악의적인 노드들이 네트워크에 해를 입히기에 부담이 되도록 하는 것입니다.

 

3. Proof of Work

비용이라는 것은 신원을 만들어 내는데의 작업에 소모되는 무언가들을 말할 것입니다.

그렇다면 그 작업은 어떤 특성을 지녀야 할까요?

 

• 시간 소모적 (time consuming):
  • 조건을 만족하는 해시 값을 찾기 위해 많은 계산이 필요.
  • 이는 시스템의 보안을 강화하고 악의적인 행동을 어렵게 만듦.
• 검증 용이성(scalable):
  • 작업 증명 결과는 계산 비용이 크지만, 결과의 검증은 매우 빠르고 간단. ( Verify에 대한 시간복잡도 : O(1) )
• 기억 없는 특성 (Memoryless):
  • 이전 시도의 실패 여부와 상관없이 각 시도가 독립적.
  • 이는 모든 참여자가 공정하게 작업에 기여할 수 있도록 보장.

이러한 작업의 과거 사례로, 1997년에 등장한 아이디어인 hashcash가 있습니다. 

hashcash는 이메일 스팸을 막기 위해 나타난 아이디어인데, 이는 메일 헤더에 nonce(임시값)을 추가하고, 메일을 해싱하였을 때 결과값이 최대한 낮게 만들어 '0'의 값과 부분 충돌이 일어날 때 메일을 전송할 수 있도록 하는 것입니다.

 

 

 

간단화된 작업 증명 과정에서는, 해싱의 결과값으로 앞의 0이 몇개인지에 따라 작업을 더 열심히 하였는지 알 수 있습니다.

(0의 갯수가 많을 수록 더 작은 수를 찾았다는 의미기 때문)

그리고 이 작업은, 악의적인 노드가 equivocation을 일으키려 할 때의 비용을 요구할 것이기에, sybil attack에 대한 저항성을 가집니다.

또한 한번의 작업에 대해서 O(n)의 시간복잡도를 가지나, 그 결과를 확인하고 증명하는데의 시간복잡도가 O(1)이기에 아무리 처리용량이 늘어나더라도 적합한 합의 과정이라 할 수 있습니다. (확장성을 보유하고 있다고 말할 수 있습니다.)

 

그렇다면, 이것이 왜 필요한 것일까요?

바로, 메세지(거래내역)의 순서를 기록하며 이중지불 문제를 해결하기 위해, 체인형 작업 증명을 사용하여 분산된 타임스탬프를 구현하기 때문입니다.

 

 

체인형 작업증명을 만들기 위한 메세지(m), nonce(r),목표값(t)의 관계는 아래와 같습니다.

hash(m, r) = h; h < t

m_n (block n에 대한 메세지) = (data, h_n-1 : n-1번째 block의 해시값)

예를 들어, block 2 에 대한 메세지는 block 2의 data와, block 1의 data, 그리고 r 의 해시값인 h_1를 가집니다.

ex) m_2 = (data_2, hash(data_1, r))

 

이렇게 구현되는 작업증명의 경우, 특정 메세지가 악의적으로 변경하려고 하였을 때, 그 값이 포함된 블록의 해시값이 바뀌면서 그 다음 블록이 가지고 있는 prev : (hash) 값 포인터가 정상적으로 작동하지 않을 것입니다. 그로 인하여 체인이 유지되지 못하기에 그러한 악의적 변경이 허가되지 않을 것입니다.

 

가끔씩은, 하나의 블록에 대하여 여러 블록이 같은 시기에 생성되어 여러 분기를 가지게 될 수도 있습니다. 이 경우에는 몇 블록이 지난 후에 더 많은 작업이 진행된 분기를 메인 체인으로 정하게 되고, 다른 분기에 있는 것에 대한 정보는 재구조화(reorganization)가 될 수 있습니다.

 

4. Pros & Cons about Proof of Work

 

이러한 작업증명 방식은 여러 장단점을 보유하고 있습니다.

 - Pros

• Anonymous (익명성)
  • 신원 확인이나 서명이 필요하지 않음.
  • 누구나 작업 증명에 참여 가능.
  • 시도는 무작위로 이루어지며, 사람이나 봇의 제한이 없음.
• Memoryless
  • 작업 증명은 Poisson 분포를 따르며, 각 시도가 독립적.
  • 실패한 시도와 관계없이 다음 시도는 동일한 성공 확률을 가짐.
  • 작업량이 두 배로 늘어나면 성공 확률도 두 배로 증가. (선형적임)
• Scalable (확장성)
  • 작업 증명은 더 많은 작업을 수행할수록 난이도가 증가.
  • 검증 시간은 작업량과 관계없이 일정.
  • 예: 1조 번의 시도를 수행한 블록도 검증 시간은 동일.
• Non-interactive(비상호작용성)
  • 작업 증명은 실패한 시도를 보고할 필요가 없음.
  • 블록이 생성되었을 때만 네트워크에 통신.
  • 독립적인 작업이 가능하며, 간단한 메시지 프로토콜 사용.
• Tied to real world(실물자원을 사용)
  • 작업 증명은 전기와 계산 자원을 사용하여 신뢰를 형성.
  • 물리적 자원의 소모를 통해 이중 지출 방지와 네트워크 보안 유지.

- Cons

•  ~all nonces fail (비효율성)
  • 대부분의 Nonce(작업 증명 시도)가 실패.
  • 소규모 참여자는 높은 작업량 요구로 인해 참여가 어려움.
  • 부분 작업에 대한 보상이 없어 작은 작업량은 무의미.
• uses watts & chips
  • 작업 증명은 막대한 전력을 소비.
  • GPU 및 하드웨어 시장에 영향을 미침.
  • 장기적으로 전기 가격 상승 가능성.
• irregular
  • 작업 증명은 Poisson 분포를 따르며, 블록 생성 간격이 일정하지 않음.
  • 몇 초 만에 블록이 생성되거나 한 시간이 걸릴 수도 있음.
  • 특정 사용 사례에 적합하지 않을 수 있음.
• 51% attacks
  • 네트워크의 51% 이상의 계산 능력을 가진 참여자가 블록체인을 조작 가능.
  • 트랜잭션 기록을 변경하거나 무효화 가능.
  • 익명성으로 인해 공격자를 식별하기 어려움.
• people hate it (부정적 인식)
  • 작업 증명은 비효율적이고 자원 낭비라는 비판을 받음.
  • 막대한 전력 소비와 계산 자원의 낭비로 인해 부정적인 평가.

 

현재 비트코인에서의 작업증명은 십 수년간 안정적으로 작동하였으며, 대부분의 블록 재구성은 1~2개의 블록 깊이에서 발생해왔습니다. 또한 기존의 거래에 대한 재작성이 사실상 불가능하도록 설계되었습니다.

 

이러한 작업증명에서의 특이한 점 중 하나는, 네트워크 전체에서 수행된 총 작업을 추정하기 위해서는 가장 낮은 해시값만 찾으면 된다는 것입니다. 가장 낮은 해시 하나로 모든 작업을 증명할 수 있기 때문입니다. (관련하여 궁금한 경우 HyperLogLog에 관한 논문을 볼 것을 추천합니다.)