GRIN GRIN
1,128 (0.00013231 BTC, -10.39%)
mimblewimble.txt (밈블윔블 백서)
최초작성 : 8개월 전 / 최종수정 : 8개월 전 / 번역자 : misskiwi

역자의 말. 이 파일은 Tom Elvis Jedusor 라는 익명의 인물이 올린 밈블윔블에 대한 백서 입니다. 엄밀히 GRIN의 백서는 아니며, GRIN은 밈블윔블 프로토콜을 기반으로 역시 익명의 개발자 Ignotus Peverell에 의해 진행 중인 프로젝트 입니다.

MIMBLEWIMBL
Tom Elvis Jedusor
19 July, 2016

\****/
서론(Introduction)
/****\

비트코인은 상태의 검증에 필요한 모든 데이터를 암호학적으로 누구나 확인할 수 있는 최초의 통용되는 금융 시스템이다. 하지만 비트코인은 이를 블록체인이라 불리는 공개된 데이터베이스에 모든 정보를 저장하는 방법으로 구현하였고, 누군가 이를 확인하고자 하면 모든 데이터를 내려받은 뒤 검증하도록 설계되어 있다. 그러나 실상 대부분의 거래는 최종 상태에는 큰 영향을 주지 않는 것들이다(이들 대부분은 출력의 형태로 다른 거래에 포함되어 사라지게 된다).

이 글을 작성하는 지금, 1억 5천만개의 거래가 블록체인에 등록되어 있지만, 정작 마지막 상태는 4백만개 정도의 미사용출력(unspent output)으로 구성될 뿐이다.

검증(audit)하는 입장에서는 출력만 확인하는 것이 훨씬 편하다. 하지만 블록체인의 특성 상 이어지는 서명 등을 통한 이전 데이터와의 연관성을 확인해야만 유효성을 보장받을 수 있기 때문에 출력만 확인하는 간편한 방법을 이용하는 것은 현실적으로 불가능하다. 다시 말하면, 가장 최근의 마지막 상태의 유효성은 모든 전체 블록체인 데이터가 유효해야만 보장되는 것이다.

여기에 더하여, 이러한 거래(transacition)들은 암호학적 동시성(atomic)을 지닌다. 출력이 개별 거래에 어떤 영향을 주며, 어떻게 병합되는지는 명확하게 표시된다. 이로 인해 거래 흐름(transaction graph)을 통해 충분한 정보를 얻을 수 있으며, 많은 회사들은 이를 모니터링하는 것을 사업 모델로 삼고 있다. 이는 사용자들의 개인 정보를 심각하게 침해하고, 나아가 위협할 수도 있다.

이를 개선하기 위한 방안은 여러 가지로 제안된 바 있다. Greg Maxwell은 보내는 금액을 암호화하여 거래는 익명화하되, 검증은 가능한 방법을 제시하였다1. Dr. Maxwell 은 또한 CoinJoin을 통해 Bitcoin 유저들이 거래를 불분명하게 섞는 방법도 제시하였다. Nicolas van Saberhagen은 거래의 입력(entry)을 은닉화하는 방법을 제시하였다(게다가 사용자의 상호 작용을 필요로 하지도 않는다)3. 이후 Shen Noether는 Maxwell과 van Saberhagen의 접근방식을 조합하여 비밀 거래(confidental transaction)를 활용하는 방안을 제시하였다4.

위의 해결책들 모두 매우 뛰어난 방법으로, 비트코인의 안전한 사용을 가능케 할 것이다. 하지만 너무 많은 정보를 요구하여 발생되는 문제로부터 자유로울 수 없다. 비밀 거래는 수 킬로바이트(Kb)에 달하는 증명을 모든 출력(output)에 삽입해야 한다. 이 서명은 실제 언제 사용되었는지 확인이 어렵기 때문에 모든 출력에 영구적으로 기록되어야 하는 것이다.

Dr. Maxwell의 CoinJoin은 사용자에게 요구하는 상호활동이 문제가 된다. Dr. Yuan Horas Mouton은 거래를 자유롭게 병합하는 방식5으로 이를 개선하였지만, 대칭을 기반으로 하는 암호학을 사용할 수 밖에 없었는데 이는 훨씬 느리고, 어려운 방식으로 신뢰를 얻는 형태다. 그는 이를 단방향 합산 서명(one-way aggregate signature, OWAS)이라 칭했다.

OWAS는 거래를 조합하여 블록을 만든다는 참신한 아이디어를 기반으로 한다. 블록을 건너 뛰어 (접착작용을 하는 어떤 데이터와 함께) 붙일 수 있다면 생성되는 출력과 소멸되는 출력을 합하여 그 두 출력이 존재하지 않았던 것으로 취급할 수 있다. 그런 상황 하에서 사용자가 전체 체인을 검증하기 위해 필요한 정보는, 언제 추가적인 돈이 시스템에 들어왔는지(비트코인이나 모네로 또는 사이드 체인을 통한 페깅과 각 블록당 생성되는 새로운 돈6)와 최종 미사용 출력 뿐이며, 나머지는 삭제하거나 무시해도 상관 없다. 이를 통해 우리는 거래 금액과 흐름을 불투명하게 만드는 OWAS를 숨긴 비밀 거래를 만들면서도, 오히려 비트코인 보다 전체 블록체인 검증에 사용되는 공간을 적게 구성할 수 있다. 게다가 대칭을 기반으로 한 암호학이나 신규 가설도 필요로 하지 않는다.

나는 이를 밈블윔블(Mimblewimble)이라 부르기로 하였다. 왜냐하면 이는 블록체인이 사용자 정보에 집중하는 것을 막는데 효과적이기 때문이다7.

\****/
비밀 거래와 OWAS(Confidential Transactions and OWAS)
/****\

첫 번쨰로 해야할 일은 비트코인 script를 제거하는 일이다. 슬프긴 하지만 이는 너무 강력하여 일반적인 script로 거래를 병합할 수 없게 한다. 우리는 Dr. Maxwell의 비밀 거래가 (조금의 수정을 거치면) 출력 소비를 인증하고 사용자의 상호동작 없이도 거래를 병합할 수 있음을 증명할 것이다. 이는 근본적으로 OWAS와 같은 방식이며, 중계하는 노드가 거래 수수료를 취하거나 수령인이 거래 수수료를 변경할 수 있도록 한다. 이러한 추가적인 사안은 비트코인은 할 수 없는 일이지만, 우리는 이를 쉽게 얻을 수 있다.

독자의 편의를 위해 비밀 거래가 작동하는 방식을 되짚어보는 것에서 시작하도록 하자. 우선, 총액은 아래 수식의 형태로 코딩한다:

C = r*G + v*H

페더슨 커미트먼트(Pedersen commitment)를 C라 하고, G와 H는 nothing-up-my-sleeve 타원곡선 생성을 위한 고정된 값이며, v는 총액, r은 숨겨진 비밀 난수 키이다.

이 출력에 덧붙여 v는 [0, 2^64]라는 구간증명(rangeproof)이고, 사용자는 오버플로우(overflow) 어택 등을 행할 수 없음을 뜻한다.

거래를 검증하기 위해, 검증인은 모든 출력의 투입을 더한다. f*H (f는 주어진 거래 수수료)를 더하고 모든 입력의 투입을 제한다. 결과는 0(zero)이어야 하고, 이는 전체적으로 조금의 금액도 새로 생겨나거나 삭제되지 않았음을 증명한다.

우리가 이러한 거래를 만들기 위해서는, 사용자가 모든 투입의 시작이 되는 r의 전체 총액을 알아야만 한다는 것을 알고 있다. 그러므로 r의 값(그리고 그들의 총합)은 비밀키로 사용할 수 있다. 만약 우리가 r 출력값을 수신인만 알게 할 수 있다면, 우리는 인증 시스템을 만든 셈이다! 만약 모든 출력을 더하여 0이 되는 조건을 계속 유지해야한다면 불행히도 지금의 논의는 불가능하게 된다. 송신자는 자신의 모든 r 값의 합을 알고 있기 때문에 다른 모든 수취인의 r 값을 제하면 0이 되기 떄문이다. 그러므로 이 방법 대신 합이 0이 아닌 다른 값, k*G가 되는 것을 허용하고, 빈 문자열과 이를 서명한 키 값을 필요 항목으로 제시하여 총액을 구성하는 것들의 합이 0이 되도록 증명할 수 있도록 만들어야 한다.

우리는 거래들이 최대한 많은 k*G 값을 서명과 합의 값을 갖고 이를 검증할 수 있도록 한다.

거래를 만들기 위해 송신인과 수신인은 다음의 조건을 따른다:

  • 송신인과 수신인은 보낼 총액에 대해 합의하며 이를 b라 한다.
  • 송신인은 모든 입력과 변화된 출력(들)으로 거래를 만든다. 그리고 수신인에게 가려진 전체 요소(입력에서 r 값을 뺀 변화된 r 값)를 전달한다. 따라서 투입의 합은 r*G - b*H 이다.
  • 수신인은 그의 출력 중 임의의 r 값을 고른 뒤, b 에서 수수료를 뺀 값을 더하고 이를 (범위 증명과 함께)거래에 추가한다. 이제 투입의 합은 k*G - fee*H 이며 임의의 k는 수신인만 알고 있는 값이다.
  • 수신인은 k를 포함한 서명을 거래에 추가하고, 수수료를 명시한다. 이것으로 완성되었다.

이와 같은 방식으로 거래를 생성하면 OWAS 또한 해결된다. 이를 증명하기 위해, k1*G와 k2*G 만큼의 초과분과 이에 대한 서명을 가진 두 거래가 있다고 가정하자. k1*G와 k2*G를 섞어 두 거래의 입력과 출력을 결합할 수 있으며, 이 거래 또한 유효하다. 병합을 통해 어떤 출력 혹은 거래가 어느 거래에서 온 것인지 확인할 수 없게 된다.

이로 인해, 우리는 비트코인의 블록 형식에서 다음과 같은 형태로 변화할 필요가 있다:

  • 신규 유입된 돈의 정확한 총액 (블록 생산에 대한 보상이나 사이드체인의 페깅)과 필요로 하는 데이터. 사이드체인 페깅의 경우 아마도 k*G 값을 초과하는 비트코인 거래의 정보를 포함할 것이다.
  • 모든 거래의 입력들
  • 모든 거래의 출력들
  • 모든 거래의 초과 k*G 값들

이들 각각은 그룹으로 묶을 수 있는데, 원 거래의 경계가 의미 없기 때문이다. 추가하자면 두 번째부터 네 번째의 항목은 빠른 확인과 블록 생성자의 정보 누락을 방지하기 위해 알파벳 순으로 코딩 되어야할 것이다.

출력들은 쉽게 변할 수 있는 거래 내의 위치가 아닌 해시의 형태로 고유화된다. 이는 두 개의 미사용 출력을 정확히 함으로써 혼란을 방지하기 위함이다.

\****/
블록을 넘어선 거래 병합(Merging Transactions Across Blocks)
/****\

우리는 Dr. Maxwell의 비밀 거래를 통해 사용자의 상호 활동을 필요로 하지 않는 CoinJoin을 만들었다. 하지만 아직 Dr. Maxwell의 마지막 놀라움을 다 확인한 것은 아니다. 우리는 다른 아이디어가 필요하다. 이는 거래 컷스루(cut-through)로 그가 기술한 바 있다8. 다시 한번 우리는 상호 활동이 필요없는 버전을 유지하면서, 여러 블록에 걸쳐 이를 구현해보겠다.

우리는 이제 각각의 블록을 하나의 거대한 거래로 볼 수 있다. 이를 검증하기 위해서 우리는 모든 출력 투입을 더하고, 모든 입력 투입과 k*G 값, 그리고 모든 명확한 출력 H를 제하였다. 이를 통해 두 블록을 병합할 수 있으며, 이를 하나의 블록으로 만들 수 있고, 이 또한 유효한 거래가 된다. 다만 이제 어떤 출력 투입은 이와 정확히 일치하는 입력 투입 쌍을 가지고 첫 블록의 출력은 두번째 블록에서 소비될 수 있다. 우리는 여기서 쌍이되는 두 투입을 삭제하더라도 거래의 유효성을 유지할 수 있다. 사실 삭제된 출력의 범위 증명을 검증할 필요도 없다.

이 아이디어를 제네시스 블록부터 최종 블록까지 전체로 확장하면, 우리는 출력과 연결된 명확하지 않은 모든 입력을 삭제할 수 있다. 남는 것은 미사용 출력 뿐이며, 명확한 입력량과 k*G 값이 이에 해당한다. 그리고 이러한 뒤섞임은 하나의 거래의 형태로 검증이 가능하다: 모든 미사용 출력 투입을 더하고, k*G 값을 제하여 명확한 입력량을 검증하고(만약 검증할 어떤 것이 있다면) 그리고 여기에서 최종적으로 H를 뺀다. 만약 합이 0이라면 전체 체인은 정상으로 판단할 수 있다.

이는 무엇을 의미하는가? 어떤 사용자가 체인을 다운로드, 업로드를 한다면 매 블록 아래 데이터를 필요로 한다:

  • 신규 유입된 돈(블록 보상이나 사이드체인 페깅으로 인한) 명확한 총액 그리고 이와 관련된 어떤 형태의 데이터
  • 모든 거래의 미사용 출력이 머클 증명의 형태로 원래의 블록에 구현된 정보
  • 모든 거래의 초과된 k*G 값

현재 비트코인은 약 423,000 블록을 생성하였고, 이는 총 80GB에 달한다. 전체를 검증한다는 것은 이 방대한 데이터를 모두 살펴보는 것을 뜻한다. 이들 정보는 1억 5천만개의 거래와 5백만 개의 공개된 미사용 출력으로 구성된다. 이를 밈블윔블 체인으로 얼마나 줄일 수 있을지 예측해보자. 각각의 미사용 출력은 약 3Kb의 범위증명과 머클 증명으로 처리된다. 각 거래는 또한 약 100 바이트를 추가로 필요로 한다: k*G 값과 서명이 이에 해당한다. 블록 헤더들과 명확한 총액은 무시해도 될 정도의 양이다. 이를 다 더하고도 30Gb가 남는다 -- 더불어 명확한 거래와 (개인정보를 위한) 모호한 거래 흐름까지!

\****/
의문과 직감(Questions and Intuition)
/****\

아래는 수 주 동안 나를 악몽에 시달리게 한 내용들이다. 하지만 결과적으로 괜찮을 것 같다.

Q. 만약 거래 출력을 삭제하면, 사용자는 범위증명을 통해 검증하지 못하고 이는 결과적으로 부채 출력을 만드는 것이 아닌가?

A. 이는 괜찮다. 전체 거래의 검증 차원에서 부채 출력은 이미 삭제되었어야만 한다. SPV 보안을 통해 불법적인 인플레이션이 일어나지 않았다는 것을 알고, 지금 시점에서도 그렇다면 현재 인플레이션은 없음을 의미한다.

Q. 만약 입력을 삭제하면 이중 지불(double spending)도 일어날 수 있지 않은가?

A. 이 얘기는 사실 이렇게 풀 수 있다: 만약 누군가가 어떤 미사용 출력이 이전에 사용되었다고 선언한 것이다. 하지만 이는 불가능하다. 애초에 연결된 거래의 합은 0이기 때문이다.
예외는 출력의 총액이 0일 때인데, 두 가지 가능성이 있다. 상대적으로 상쇄될 때와, 어떤 룰도 깨지않고 쌍으로 회복될 때이다. 합의 문제를 피하기 위해, 출력 총액이 0인 것은 제외해야 한다. 간단히 H를 모든 출력에 더하여 모든 출력이 최소한 1이 되도록 하면 된다.

\****/
보완을 필요로 하는 연구(Future Research)
/****\

아래 내용은 작성 시점에 내가 답하지 못하는 것들이다.

  • 어떤 script를 지원할 수 있는가? 우리는 스크립트 작업을 어떤 다른 형태의 정보로 변환할 필요가 있다.
  • 우리는 사용자가 모든 k*G 값을 체크하도록 한다. 이는 그들의 사용한 합이 k*G를 구성할 때이다. 서명을 사용하는 대신 결합이 가능한 다른 증명 방식은 없는가?
  • 사용자가 체인 데이터를 다운로드 받을 때 수 기가바이트(Gb)에 달하는 잘못된 미사용 출력을 제공하는 DoS 공격이 가능하다. 사용자는 도중에 결과가 0이 아니더라도 문제가 무엇인지 확인할 수 없다.
    지금 시점에서는 아마도 사용자가 블록체인 데이터를 합리적으로 믿을 만한 토렌트나 유저가 많은 곳에서 다운로드 받아야만 한다.

1 https://people.xiph.org/~greg/confidential_values.txt

2 https://bitcointalk.org/index.php?topic=279249.0

3 https://cryptonote.org/whitepaper.pdf

4 https://eprint.iacr.org/2015/1098.pdf

5 https://download.wpsoftware.net/bitcoin/wizardry/horasyuanmouton-owas.pdf

6 http://blockstream.com/sidechains.pdf

7 http://fr.harrypotter.wikia.com/wiki/Sortilège_de_Langue_de_Plomb

8 https://bitcointalk.org/index.php?topic=281848.0