• TL;DR
• 비트코인(블록체인 기반 가상자산) 개요
  • 블록체인의 개념?
  • 블록체인의 신뢰성을 보장하는 기반 기술
    • 분산 네트워크
    • 암호기술
    • 이중 거래 방지
    • 합의 기법
  • 블록체인의 구조
• 공격 기법 설명(대략적)
  • Double-Spending With a Sybil Attack
    • 개요
    • 공격 시나리오
• How to Mitigate: 2 ways will be combined
  • Charging an Identity Fee
  • Setting a Deadline
• Economic Analysis
  • 원래 상태에서 공격자의 공격 비용
  • Combined mitigation 하에서 공격자의 공격 비용
  • 공격자의 손익분기점 구하기
    • Case 1: 데드라인보다 z개 블록 컨펌 시간이 짧아 이상거래를 숨길 수 있을 때
    • Case2: 데드라인보다 z개 블록 컨펌 시간이 길어 이상거래를 숨길 수 없을 때
    • Case1 + Case2: 공격자 이득의 기댓값과 손익분기점
  • 다양한 조건 하에서 공격자의 손익분기점
  • 
    
    
    

TL;DR

이번에 읽은 논문은 "Mitigations on Sybil-Based Double-Spend Attacks in Bitcoin"(Shijie Zhang and Jong-Hyouk Lee)이다. 이 논문은 블록체인 기반 가상자산에 대한 공격과 그 대비책을 논한다.

• 먼저 Sybil Attack을 이용한 이중 지출 공격을 분석했던 지난 연구를 기반으로(이 논문… 시리즈다..)
• 두 가지 관점의 대비책을 제시한 다음
• 제시된 두 대비책을 결합한 새로운 대비책을 제시하고 그 효과를 입증한다.

당연히 저작권을 존중해 이미지의 무단 사용, 지나치게 많은 내용 정리 등은 지양할 것이다. 그러니 원본이 보고 싶으신 분들은 여기(링크)로!

근데 우리 과 교수님이 쓰신 거라서 좀 자세하게 정리할게요 교수님 죄송함다! ㅎㅎ

---

잡설: 정보보안기사 붙고 나니까 시간이 널널해져서 너무 좋다. 논문도 읽고 학교 공부도 하는데 시간이 남는 삶 너무 워라벨 만점이다… 근데 올초부터 하고 싶던 퍼징 연구는 학기가 끝나야 가능할 듯 싶어서 좀 슬프다. 리뷰 논문으로 포문을 열었는데 포문 연 상태로 6개월 방치중임 ㅋㅋ

근데… 나 저번에 에어갭 와이파이로 깨는 거 읽은 다음에 핸드폰 자이로스코프 모듈로 에어갭 깨는 거 하나랑 NIC 모듈에 붙어있는 LED로 에어갭 깨는 것도 읽었는데 이거 독후감 언제 쓰지? 이래서 무계획적인 독서는 좋지 않습니다 그치만 취미생활인데-

비트코인(블록체인 기반 가상자산) 개요

해당 논문에는 블록체인이 어떻게 구성되어 있는지, 블록체인을 이용한 가상자산이 어떻게 보안성을 보장받는지, 블록체인을 이용한 금전 거래가 어떻게 작동하는지에 대해 매우 간략하게 정리되어 있다. 그리고 이 글을 읽을 독자들 또한 블록체인에 대해 그렇게까지 디테일한 지식을 요구하지 않을 것이다. 본인들이 이미 알고 있을 테니까…

그래도 조금 자세히 써 보겠다. 혹시라도 모를 사람들을 위해!

참고문헌: “알기사 정보보안기사 필기 1권”(지안에듀), “세종대 정보보호학과 네트워크해킹과 보안 교안”(이종혁)

블록체인의 개념?

블록체인은 한 마디로, 거래 장부의 ‘탈중앙화’를 현실 세계에 구현한 것이다. 그 누구도 모든 거래 내역에 대한 권한을 독점할 수 없고, 모든 사용자가 1) 거래 내역에 대한 일정 권한(검증, 승인, 합의)을 가지고 2) 동일한 내용의 거래 장부를 모두가 한 부씩 가짐으로써 3) 신뢰성을 보장하는 것이다.

이름에서도 알 수 있듯이, 블록체인은 ‘블록’이 연결된 ‘체인’이다. 하나의 거래 내역(Transaciton)은 곧 하나의 블록을 구성한다. 블록은 생성되자마자 네트워크를 타고 모든 사용자에게 공유된다. 따라서, 모든 참가자들은 모든 거래 내역을 볼 수 있다. 그렇기에 거래의 ‘투명성’이¹ 보장된다.

그런데, 앞서서 블록체인은 ‘블록’이 연결된 ‘체인’ 이라고 했다. ‘체인’은 모든 구성 요소가 순차적으로 연결되어 하나라도 건드리면 모든 요소에 영향을 주는 구조를 의미한다(화학 반응에서의 Chain Reaction 등을 생각해보자). 블록체인 또한 그런 의미를 가진다. 새로운 블록 B가 체인에 연결될 때는 바로 앞 블록 자체의 해시와 또 다른 요소를 고려하여 생성한 해시값을 가져야만 한다. 즉, B가 연결되는 시점에서 모든 체인의 정보가 해시의 형태로 저장되므로 B가 연결된 이후에는 체인 중간의 어느 한 블록을 임의로 수정하거나 삭제할 수 없다. 따라서 블록체인은 체인의 ’불변성’을 보장받는다.

또한, 블록체인의 데이터는 모든 참여자의 스토리지에 동일하게 복사되어 저장(분산 저장 = 분산 장부)되므로, 누구 하나가 문제를 일으킨다고 해서 시스템의 연속성이 침해받지 않는다. 이런 점에서 블록체인은 ’가용성’을 보장한다.

형광펜으로 표시된 4개의 성질이 바로 블록체인의 기술적 특성이다. 블록체인의 기술적 특성이 블록체인의 개념을 이루기 때문에 이처럼 서술해 보았다.

블록체인의 신뢰성을 보장하는 기반 기술

분산 네트워크

블록체인에 참여하는 각 주체를 ‘노드’라고 한다. 각 노드는 동일한 거래 내역, 즉 블록 체인을 자신의 스토리지에 저장해 관리한다. 이를 ‘분산 저장’이라고 한다.

분산 저장된 상태의 블록체인에 거래(Transaction, 블록)를 포함시키기 위해서는, ‘분산 합의 제도’ 라는 제도로 거래를 승인하는 과정이 필요하다. 이는 제 3의 중재자 없이 P2P로 블록에 대한 검증이 이루어지는 것을 의미한다.

이 분산 합의 제도를 따르는 블록 체인의 경우,

조건에 맞는 해시를 찾았을 때² → 해당 정보를 각 노드들에게 브로드캐스트하고 → 유효성 검증을 수행한 다음 → 합의(전체 노드의 51% 이상이 신뢰성을 보장해야 합의가 승인된다)를 통해 블록을 승인한다.

암호기술

블록체인을 위한 암호기술은 크게 3가지가 사용된다. 각 기술은 다른 Surface에 대해 사용된다.

• 공개키 암호와 전자서명
  • 익명의 공개키를 계좌 정보(지갑)로 사용한다. 즉 소유자의 가용성과 익명성을 보장한다.
  • 전자서명³으로는 거래 정보의 무결성을 보장하며 거래 내역의 인증과 부인방지기능 또한 보장한다.
• 해시함수
  • 추가될 블록을 포함한 블록체인의 무결성을 증명하고, 새로운 블록에 삽입될 넌스값을 찾을 때 사용한다.
  • 블록체인의 무결성을 검증하기 쉽게 하기 위해 해시가 ‘머클 트리’ 구조를 취하게끔 했다. 따라서 머클 트리의 루트 해시만 검증하면 변조 여부를 알 수 있다.

이중 거래 방지

이중 거래 공격이란, 악의적 목적으로 동시에 두 곳 이상의 계좌로 송금하는 행위를 의미한다. 이를 방지하기 위해 크게 두 가지 메커니즘을 사용한다.

• 총 통화량
  • 전체 코인의 수를 정해 놓고, 이중 거래 발생 시 총 코인 수가 초과됨을 감지해 차단한다.
• The Longest Chain Wins
  • 블록체인이 모종의 이유로 인해 분기(Fork)될 경우, 길이가 더 긴 체인(=블록 생성 속도가 더 빠른 체인)을 적법한 체인으로 간주해 main branch에 merge한다.

합의 기법

합의란,

1. 주어진 새 블록을 체인에 연결할 때 블록에 삽입할 ‘조건을 만족하는’ 넌스값을 찾고
2. 주어진 트랜젝션(블록)이 변조된 것이 아닌지를 모든 노드가 참여하여 판단하는 과정을 의미한다.

이 때, 1. 조건을 만족하는 넌스를 찾는 행위를 채굴이라 한다. 채굴을 가장 먼저 성공한 노드는 블록 체인의 생성에 기여한 것으로 판단, 보상을 받는다.

합의 기법에는 크게 두 가지가 있다. (가장 기본적인 것만 나열할 거라 두 가지다. 기존의 두 가지를 발전시켜 현재는 다양한 기법들이 있다)

1. PoW(Proof of Work, 작업 증명)

   : 대부분의 블록체인 기반 가상자산들이 사용하는 방법으로, 채굴 속도에 영향을 주는 변인이 ‘컴퓨팅 파워’이다. 이 점은 에너지 낭비와 느린 속도라는 단점을 가져온다.

2. PoS(Proof of Stake, 지분 증명)

   : 채굴 속도에 영향을 주는 변인이 ‘자신이 소유한 가상 통화의 양’이다. 즉, 자신의 지분(stake)에 따라 블록을 생성하고 추가적으로 발행되는 코인을 받는다. 그러나 이는 부익부 빈익빈, 그리고 PoW에 비해 돈만 들이면 장악하기 쉬운 구조라는 단점을 가져온다.

블록체인의 구조

사실 그리려고 했는데, 내가 지금 시간이 없다… 나중에 천천히 그려서 올리는 걸로 하고(아마 날 잡고 하겠지)

일단은 책에 나온 사진만 올려놓겠다.

공격 기법 설명(대략적)

서론이 길었다! 드디어 논문 내용에 대해 이야기해볼 차례다. 이 논문은 새로운 형태의 블록체인에 대한 복합 공격을 이야기하고, 그에 대한 방어책을 설명한 다음, 그 방어책의 효과를 검증하는 식으로 내용을 구성했다. 따라서 가장 먼저 이 논문이 어떤 공격을 다루고 있는지에 대해 서술하겠다.

Double-Spending With a Sybil Attack

개요

일반적인 Sybil Attack은 Sybil Node⁴를 조작된 정보를 브로드캐스트하기 위해 사용한다. 그렇기 때문에 탐지가 가능하다.

이 논문에서는 조금 다른 Sybil Attack을 제시한다. 이 복합 공격에서는 Sybil Node들을 블록 정보 전파를 방해하는 데만 사용하고, 조작된 정보를 브로드캐스트하는 데에는 사용하지 않는다.

일단 이 논문은 방어책에 중점을 둔 논문인지라, 해당 공격에 관한 자세한 내용은 이 논문의 시리즈 논문에서 찾아볼 수 있다.

공격 시나리오

1. 공격자는 아주 많은 수의 가짜 노드들(Sybil nodes)를 비트코인 네트워크 상에 등록한다.
   • 이 때, 하나의 Sybil node는 여러 개의 가짜 ID를 가진다.
   • 하나의 정상 노드는 하나의 ID만을 가지는 것과 대조된다.
   • 한 Sybil node가 가지는 여러 fake ID들로 인해 정상 노드들은 자기가 각자 다른 노드들과 통신한다고 착각한다.
   • 이때, Sybil nodes는 블록 마이닝에 전혀 참여하지 않고, 블록 정보 전파에만 참여한다.
2. 공격자는 어떤 상품을 사기 위해 트랜잭션 TX1을 생성해 판매자에게 전송한다.
3. TX1은 브로드캐스트되어 유효성 검증을 통과한다.
4. 그럼 이제 TX1을 체인에 추가하기 위한 합의 과정이 필요하다. 그런데 이 합의가 이루어져 TX1이 높이 H 위치의 블록 안에 들어가기 전에, 공격자는 TX2를 생성해 사전에 계획을 짠 다른 공격자의 지갑으로 전송한다.
5. 이 TX2는 TX1의 트랜잭션 결과 정보를 똑같이 가지고 있다.
   • 이는 분명히 비트코인 트랜잭션의 정책에 위배된다. UTXO 정책은 하나의 트랜잭션 결과는 단 한 번만 사용될 수 있도록 했기 때문이다.
6. UTXO를 위배했다는 사실이 걸리지 않도록 공격자는 TX2가 들어 있는 블록을 퍼블릭 체인에 publish하지 않고, TX2가 들어 있는 블록에 자신이 채굴한 블록들을 이어 붙임으로써 블록체인의 높이 H위치에서 fork된 프라이빗 체인을 만들어 둔다.
7. 이제 앞에서 설명했던 ‘The Longest Chain Wins’ 규칙을 생각해 보자. 이 규칙을 악용하기 위해 공격자는 Sybil node를 이용한다.
8. 만일 Sybil node가 아닌 정상 노드가 새로운 블록을 채굴하는 데 성공했다면, Sybil node는 자신이 가진 여러 개의 가짜 ID를 이용해서 아직 새로운 블록 채굴 소식을 전달받지 못한 정상 노드들에게 inv 메시지⁵를 마구 보낸다.
9. inv 메시지를 받은 정상 노드들은 당연히 getdata 메시지를 보낸다.
10. 하지만 Sybil node는 절대 블록 정보를 회신해 주지 않는다.

11. 회신받지 못한 정상 노드들은 계속해서 블록 정보를 요청하며 기다리는 상태가 된다.

    → 이 일련의 과정은 DDoS 방법 중 TCP SYN Flood Attack과 닮았다.

12. 정상 노드들은 이게 반복되면 자신의 이웃 노드 목록에서 답신이 없었던 ID를 빼버리고 다른 ID를 넣을 수 있다. 하지만 Sybil node는 여러 개의 가짜 ID를 가지고 있기 때문에, 그렇게 다른 ID를 가진 블록과 통신하려는 시도는 무용지물이다. 따라서 매우 높은 확률로 정상 노드들은 계속해서 getdata 를 보내며 회신을 기다리는 상태에 빠진다.
13. 이렇게 블록 데이터를 기다리는 데 할당된 시간이 모두 지나면, 노드들은 데이터를 받길 포기하고 다음 채굴 라운드를 시작한다.
14. 8~13 과정으로 인해 합의 과정이 계속해서 지연되고, 노드들 간에 가지고 있는 블록체인이 달라져 자연스럽게 블록 체인의 fork가 발생한다.
    • 이 시점에서 블록 체인에 발생한 fork에는 총 세 개 종류가 있다.
      1. 공격자가 몰래 만들고 있는 프라이빗 체인 (6번 참고)
      2. 8~13 과정 때문에 새 블록 생성의 시간이 계속 늦어지고 있는 메인 체인
      3. 네트워크 분할 현생 때문에 생겨나는-그러나 메인 체인의 연산 자원을 낭비해 더 느려지게 만드는-자연스러운 체인들
15. 이런 지연이 누적되어 공격자가 가진 프라이빗 체인이 현존하는 forked chains중 가장 길어질 때, 그리고 판매자로부터 구매했던 상품을 공격자가 수신했을 때, 공격자는 자신의 프라이빗 체인을 release한다.
16. 다시 한 번 짚어보자. 메인 체인의 높이 H 블록에는 TX1이 들어가 있다. 공격자가 가진 프라이빗 체인의 높이 H블록에는 TX2가 들어가 있다. 이 상황에서 공격자의 체인 길이가 메인 체인보다 길다. 그리고 ‘The Longest Chain Rule’이 존재한다. 즉, 공격자의 프라이빗 체인이 높이 H부터 메인 체인을 덮어쓴다.
17. 어라? 판매자에게 송금했던 트랜잭션 TX1은 이제 존재하지 않는다. 대신 공격자가 다른 공격자와 짜고 만들었던 TX2만 존재한다. 즉, 공격자는 15에서 상품을 수신해 놓고 아무 돈도 지불하지 않는 이득을 보았다.

How to Mitigate: 2 ways will be combined

방어책은 크게 두 가지 갈래로 나뉜다.

1. 공격자의 Attack Cost를 높이는 방식: Creating an Identity Fee
2. 네트워크 Delay 탐지 기법을 적용한 방식: Setting a Deadline

그리고 이 논문에서는 이 둘을 합친 복합 방어책을 제시하고, 그것이 매우 효과적임을 입증한다.

Charging an Identity Fee

앞서 설명한 공격의 전제는 공격자가 무수한 ID를 만들고 유지할 수 있다는 것이었다. 이 전제가 성립될 수 없게 하는 방어 기법이다.

노드가 최초로 체인에 참여할 때 Entry fee를 징수하고, 추가로 노드가 합의 과정에 참여할 때마다 Participation fee를 징수한다. 이 때, Participation fee는 각 채굴 라운드의 시작 전에 징수된다.

Setting a Deadline

앞서 설명한 공격의 핵심은 공격자가 합의(consensus)에 걸리는 시간을 마음먹은 만큼 지연시키는 게 가능하다는 점이었다. 그러나 그것이 불가능하다면?

평균적으로 하나의 트랜잭션이 블록에 삽입되기 위해서는 6개의 블록이 컨펌되기를 기다려야 한다. 대기열에 내 앞으로 통상 6개의 블록이 들어있다는 것이다.

그렇다면 이렇게 봐도 되지 않을까? 판매자가 수신했던 TX1을 블록에 삽입하려고 기다리는데, 일반적으로 6개 블록이 컨펌되는 시간 내에 앞선 6개 블록이 컨펌되지 않아 더 오래 기다려야 한다면, 지금 공격을 받고 있는 상황이라고?

그렇다면 ‘일반적으로 6개 블록이 컨펌되는 시간’의 개념을 포함할 수 있는 시간을 정하고, 그것을 데드라인 D라고 하자. 판매자는 TX1을 수신한 시간으로부터 D가 지났는데도 6개 블록의 컨펌이 이루어지지 않았다면 구매자에게 상품을 넘겨주길 거부할 수 있게 된다.

이렇게 되면 공격자는 자신이 딜레이시킬 수 있는 시간이 최대 D인 데다가, 그것을 초과하는 순간 이제까지 채굴해 놨던 블록들과 짜고 쳤던 트랜잭션 TX2가 포함된 블록이 있는 프라이빗 체인을 유지할 이유가 전혀 없어진다. 그렇다고 D 안에 목표를 이루기엔 전제부터가 안된다. 정상 시간이 D이기 때문에 무조건 D를 넘겨야 뭐라도 해볼 수 있기 때문이다. 정상 시간 D 안에 뭘 하려면 컴퓨팅 파워를 더 올려야 한다.

즉 손해만 남는 장사인 것이다.

---

잡설: 육참골단! 예전에 읽었던 사기열전에서 손빈이 ‘급소를 치고 빈틈을 공격하여 형세를 불리하게 만들면 모든 것은 저절로 풀릴 것입니다’라고 했던 말이 생각난다. 이렇게 영리하게 급소를 분석해서 그걸 공략해야 효과적인 방안을 만들 수 있구나… 근데 이거 당연한 거 아닌가 아 근데 당연한 것일수록 생각해내기 어렵다.

아무튼 나중에 연구할 때 꼭 마인드에 가지고 있어야지.

Economic Analysis

어차피 수식이고 다들 알 것 같으니… 수식과 각 변수가 의미하는 바만 서술한다.

원래 상태에서 공격자의 공격 비용

\[C_{original} = (1-Φ)(v+12.5k_z)\]

\(C_{original}\)은 공격자가 앞서 설명한 방어 기법이 적용되지 않은 상황에서 지출해야 하는 공격 비용이다.

공격자가 \(Φ\)의 확률로 공격을 성공할 때, 공격 실패 확률은 확률의 정의에 의거해 \((1-Φ)\)이다.

공격자가 구매한 상품의 가격이 v이고, 현재 평균적으로 채굴 성공에 따라오는 보상은 12.5 BTC 이며, 공격자가 프라이빗 체인을 더 길게 구성하기 위해 따로 채굴한 블록의 수가 \(k_z\)일 때, 공격자가 실패할 경우 지불해야만 하는 비용은 \(v+12.5k_z\)이다.

따라서 실비용은 발생확률*지출비용이라는 공식에 따라 위와 같은 식이 도출된다.

Combined mitigation 하에서 공격자의 공격 비용

\[C_{combined} = \begin{cases} (1-Φ)(v+12.5k_z) + (ε+zσ)γμN, S_z≤D \\ (v+12.5k_D) + (ε+zσ)γμN, S_z>D \end{cases}\]

\(k_D\)는 D 시간 내에 공격자가 채굴한 블록의 수다. D는 앞서 말한 데드라인 시간이다.

\(ε\)는 Entry Fee이다.

\(σ\)는 Participation Fee이다.

\(z\)는 participation fee를 요구하는 채굴 라운드의 수다.

\(γ\)는 하나의 Sybil Node가 가진 ID의 수다.

\(μ\)는 현재 블록 체인에 관여하는 전체 노드의 수에서 Sybil node가 차지하는 비율이다.

\(N\)은 현재 블록 체인에 관여하는 전체 노드의 수다.

\(S_z\)는 \(z\)개 블록이 컨펌되기까지 걸리는 시간이다.

공격자의 손익분기점 구하기

먼저 공격자가 어떤 경우에서 얼마만큼의 기본 이득을 보장받는지 보자. (+\로 붙어 있는, 즉 상수로 존재하는 지출 비용은 고려하지 않는다. 진짜로 얼마만큼의 이익이 들어오는지를 보는 것이다. 순이익이 아니다!!!)

Case 1: 데드라인보다 z개 블록 컨펌 시간이 짧아 이상거래를 숨길 수 있을 때

공격자가 D시간 내에 블록을 하나도 채굴하지 못했더라도 최초 거래 TX1으로 얻은 상품 가격 \(v\)만큼의 이득만은 반드시 보장된다.

Case2: 데드라인보다 z개 블록 컨펌 시간이 길어 이상거래를 숨길 수 없을 때

공격자는 아무 이득도 얻지 못한다.

Case1 + Case2: 공격자 이득의 기댓값과 손익분기점

\(Φ_2\)를 \(S_z ≤ D\) 일 때의 확률이라고 하자. 그렇다면 모든 경우를 고려할 때 공격자가 가질 수 있는 이득의 기댓값은 \(Φ_2v\)가 된다.

손익분기점은 공격 비용이 공격자의 이득 기댓값과 일치하는 지점이다. 따라서 아래와 같은 수식을 세울 수 있다.

\[Φ_2v = C_{combined}\]

다양한 조건 하에서 공격자의 손익분기점

여기 내용은 대부분의 내용을 생략한다. 결론은 당연히 Combined mitigation이 Sybil node가 늘어남에 따라 공격자의 손익분기점을 기하급수적으로 높인다-즉 공격자가 공격에 더 큰 비용을 써야 한다는 것을 시사한다. 이는 아무 mitigation도 적용되지 않았을 때와 정반대의 손익분기점 경향성을 보인다.

다양한 조건 하에서 공격자의 손익분기점을 구하기 위해 논문의 글쓴이는 앞서 말한 수식의 파라미터 값을 현실성 있는 값으로 바꿔가며 계산했고, \(Φ_2v\)를 구하기 위해 확률 모델을 사용해 추가적인 계산을 진행했다.