서론
Alpha 사이드체인에 어떤 컨센서스 개선 사항을 통합할지 결정하기 시작했을 때 우리는 비교적 많은 아이디어를 갖고 있었습니다. 그러나 시간적 제약이나 다른 이유로 인해 몇 가지 아이디어는 제외되었습니다.
포함된 변경 사항 중 하나는 비트코인에 존재했던 몇 가지 간단한 명령 코드[1]의 추가입니다. 그 중 하나인 OP_CAT는 두 개의 스택 변수를 연결합니다.
포함되지 않은 것 중 하나는 스크립팅을 위한 MAST(Merkleized Abstract Syntax Trees)입니다. 이 아이디어는 수년 간 갖고 있었지만 비트코인에서는 한번도 구현되지 않았습니다. 기본 아이디어는 스크립트의 조건을 트리로 재정렬하고 자금 사용자가 실제로 사용하는 부분만 공개하는 것입니다. 이는 크고 복잡한 많은 스크립트를 가능케 할 수 있지만 스크립트 언어를 심층적으로 재설계해야 합니다. 우리는 이 아이디어를 오랜 기간 고려해 왔지만, 바로 완성되지는 않을 것입니다.
그러나 Alpha가 출시된 직후, 추가된 OP_CAT 덕분에 Alpha의 스크립트 언어가 단순한 형태의 Merkle 트리 검증을 제공한다는 것을 알게 되었습니다. 따라서 컨센서스 규칙을 변경하지 않고도 MAST의 부분집합을 에뮬레이션할 수 있습니다. 그저 예상치 않았던 방식으로 해당 스크립트 언어를 사용하기만 하면 됩니다. 다음 섹션에서 볼 수 있듯이, 이로써 (실행된 명령 코드 및 체인 상 크기로 봤을 때) 아주 낮은 비용으로 매우 큰 멀티시그[2] 구성을 달성할 수 있습니다.
이 글의 나머지 부분에서는 기술적 세부 내용, 사용 사례, 구현에 대한 의견을 다룹니다. 기술적 세부 내용에 관심이 없으시면 이 부분은 건너 뛰셔도 됩니다.
기술적 세부 내용
(11개의 알려진 공개 키로) 1-of-11 멀티시그를 생성한다고 가정해 봅시다. 관련된 공개 키의 SHA256 해시를 계산하고 이를 Merkle 트리에 넣습니다. 아래 그래프에서 1을 제외한 모든 기호 이름은 32 바이트 해시를 나타냅니다. 1은 오른쪽 분기가 없는 경우 그 대신 단순한 상수로 사용됩니다.
R
/ \
/ \
/ \
Z1 Z2
/ \ / \
Y1 Y2 Y3 1
/ \ / \ / \
X1 X2 X3 X4 X5 X6
/ \ / \ / \ / \ / \ / \
K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11 1
우리는 Alpha 사이드체인에서 해당 스크립트를 사용하여 공개 키, 서명, Merkle 경로를 입력값으로 사용하는 스크립트를 작성할 수 있습니다. 검증 시점에, 공개 키는 루트 R을 가진 트리에 속하고, 서명은 해당 공개 키를 사용하여 확인한다는 것을 증명하는 데 Merkle 경로가 사용됩니다.
8 PICK SHA256 (SWAP IF SWAP ENDIF CAT SHA256)*4 <R> EQUALVERIFY CHECKSIG
주의할 점은 내부에 있는 작업 6개는 트리의 각 레벨마다 한 번씩 4번 반복된다는 것입니다.
이러한 작업이 가능한 이유를 보시려면, 아래 입력값으로 실행 단계를 따르시기 바랍니다. 서명은 (해시가 K10인) 10번째 키를 사용하여 나타납니다. 마지막 8개 항목이 Merkle 경로를 구성합니다. 각 레벨의 경우, 아래에서부터 위로, 실행 해시가 결합된 항목과 0 또는 1을 포함합니다. 0과 1은 각각 왼쪽, 오른쪽 노드임을 나타냅니다.
스케일링
이전 섹션에서는 Alpha 스크립트에서 1-of-11 멀티시그가 어떻게 구현되는지 보여주는 한 가지 예를 다뤘습니다. 그러나 비트코인 스크립트는 이미 1-of-11 멀티시그를 잘 수행할 수 있습니다.
이 방법의 장점은 대수적으로 확장된다는 것입니다. 유효한 공개 키의 수를 두 배로 늘리면 연관된 거래에 일정하게 40 바이트만 추가되고, (비용이 많이 드는) 서명 검증 수는 일정하게 유지됩니다. 반면, 비트코인에서는 하나의 공개 키를 추가하면 34 바이트가 추가됩니다.
스크립트의 연산 횟수에 제한이 있기 때문에 이 방법은 이론적으로 최대 1-of-4,294,967,296 멀티시그까지 가능하지만, 그 시점에 트리는 만들기 화가 날 정도로 커집니다. 하지만 최대 1-of-1,000,000 멀티시그는 가능할 것입니다.
이 방법을 사용한 1-of-250,000 멀티시그에는 Alpha 스크립트의 886 바이트가 필요합니다. 이것은 비트코인 스크립트에서 가능하다 하더라도 동일 조건보다 9,000배 이상 작습니다.
허니팟
이렇게 큰 멀티시그 구조의 사용 사례 중 하나는 허니팟입니다. 여러분이 서버 10,000개의 클러스터를 운영하고 각 서버에 BTC 약간을 남겨둔 상태에서 공격자가 코인을 훔치고 그 사실에 대해 경고 받기를 바라고 있다고 가정해 봅시다.
이를 위해 최대 10 BTC는 버려도 상관 없고 각 서버에 별도의 비트코인 지갑을 갖고 있어야 할 경우, 각 시스템마다 1 mBTC로 제한될 것인데 이는 특별히 매력적인 금액은 아닙니다.
그러나 10,000 범위의 멀티시그를 사용하면 각 시스템에 단일 키만 남겨두고도 10 BTC 전체를 이렇게 큰 멀티시그 스크립트에 할당할 수 있습니다. 모든 키는 여전히 분리되어 있고 어떤 키가 사용되었는지 서명에 나타나기 때문에 공격 받은 시스템을 찾아낼 수 있습니다.
Schnorr 서명과 통합
큰 멀티시그 구조의 다른 사용 사례도 있지만, 지금까지 설명한 방법은 M-of-N이 아닌 1-of-N만 지원합니다.
그러나 이 접근법은 Schnorr 서명[3]의 흥미로운 속성과 결합하여 보다 강력한 기능을 얻을 수 있습니다. 동일한 메시지(거래)에 대해 많은 서명을 갖고 있을 경우, 그 서명을 모두 '추가'하여 공개 키의 "합계"에 대한 서명을 얻을 수 있습니다.
즉, 3-of-3 멀티시그 스크립트를 사용하는 대신, 단순히 일반 CHECKSIG에 대한 “1-of-1” 공개 키로 포함된 공개 키 3개의 합계를 사용할 수 있습니다. 그러면 서명자들은 공개 키의 합에 유효한 서명을 생성하기 위해 모두 지출 거래에 개별적으로 서명하고 모두의 서명을 함께 추가할 수 있습니다. 즉, Schnorr 서명을 사용하면 임의의 높은 M을 가진 M-of-M 멀티시그는 블록체인에 관해서는 간단히 1-1로 줄어듭니다. 단점은 참여자들이 먼저 서명 논스에 동의해야 하기 때문에 라운드를 두 번 거쳐야 한다는 것입니다.
지금까지 서명을 어떻게 결합하는지 보셨습니다. Merkle 트리 키는 매우 큰 1-of-N을 지원합니다. Schnorr 서명은 매우 큰 M-of-M을 지원합니다. 즉, 지출 조건을 1-of-(N, M-of-M 가능)으로 기록할 수 있다면 Schnorr 결합 공개 키로 구성된 Merkle 트리를 구축할 수 있습니다. Merkle 트리의 모든 잎은 모든 참여자가 서명해야 하는 키 집합이 됩니다.
예를 들어, 키 A,B,C,D,E를 가진 4-of-5 멀티시그는 다음과 같이 작성할 수 있습니다:
이것은 5개의 잎을 가진 Merkle 트리가 되는데, 각각의 잎은 공개 키 4개의 합으로 구성됩니다. 이것은 Alpha에서는 286 스크립트 바이트를 필요로 할 것입니다. 비트코인에서 4-of-5 멀티시그는 490 바이트가 필요합니다.
또한 항상 단일의 (높은 비용이 드는) CHECKSIG 운영만 필요로 합니다. 비트코인 스크립트에서는 항상 필요한 서명자 당 하나의 CHECKSIG가 필요합니다 (M-of-N 멀티시그의 경우 M).
몇 가지 예:
일반화된 임계 트리
키 조합을 나타내는 잎을 가진 Merkle 트리를 만드는 방법은 M-of-N 조건으로 제한되지도 않습니다. 이 방법은 모든 참여자가 서명해야 하는 비교적 적은 수의 키 집합의 조합으로 표현될 수 있는 것이면 어디든 효과적으로 적용됩니다.
우리는 키 조합에 대한 이러한 조건을 설명하는 간단한 언어를 설계했습니다. 설명은 다음과 같습니다:
16진수 형식의 공개 키, 해당 키의 서명이 필요함.
OR(a,b,c,...) 여기서 a, b, c ...는 다른 설명이고, 그 중 하나는 충족되어야 함.
AND(a,b,c,...) 여기서 a, b, c…는 다른 설명이고, 모두 충족되어야 함.
THRESHOLD(n,a,b,c,...) 여기서 n은 숫자이고 a, b, c…는 다른 설명이며, 그 중 n개가 충족되어야 함.
이 언어는 "A 및 B 서명 또는 C, D, E 서명 중 2개" 같은 조건을 쉽게 표현할 수 있습니다.
속성
Greg Maxwell은 이 맥락에서 서명 체계에 대한 5가지 흥미로운 속성(ACEUP) 목록을 만들었습니다.[4]
책임 : OP_CHECKMULTISIG와 이러한 트리 서명 모두 서명 체계의 모든 참여자들에게 서명인을 알려줌.
결합성 : 복잡한 설명으로 서명을 요청하는 참여자가 두 명인 경우, 둘 중 하나의 서명을 설명하는 설명을 구성하고도 여전히 이를 처리할 수 있는 소프트웨어를 가질 수 있을까? 트리 서명은 이러한 기능이 매우 뛰어남.
효율성 : 트리 서명의 거래 크기와 검증 성능은 언제나 OP_CHECKMULTISIG보다 더 좋거나 같음. 그러나 서명 시간은 더 긺.
유용성 : 트리 서명에는 먼저 Schnorr 서명 논스가 필요하기 때문에 모든 참여자는 두 번의 라운드를 거쳐야 함.
기밀성 : 더미 추가 비용이 매우 낮기 때문에, 트리 서명의 참여자와 그 수를 훨씬 쉽게 숨길 수 있음.
구현
트리 서명을 지원하는 Alpha의 지갑 패치는 https://github.com/ElementsProject/elements/pull/48을 참조 바랍니다. 새로운 RPCs addtreesigaddress 및 createtreesig는 공개 키 트리를 구현하는 스크립트용 P2SH 주소를 생성하고, signrawtransaction은 공개 키 트리(서명 시점에 알려야 함)를 전달하기 위해 추가 변수를 취합니다.
결론
스크립팅 언어를 조금만 바꾸면 예상치 못한 이득을 얻을 수 있다는 점이 흥미롭습니다. 공개 키의 Merkle 트리를 Schnorr 결합 서명과 결합하면 아주 큰 M-of-N 멀티시그의 일부 조합을 효율적으로 지원할 수 있습니다. 이것은 사이드체인 Elements에 대한 작업의 일환으로 곧 Alpha 코드베이스에서 사용 가능할 것입니다. 이에 대한 지원은 잠재적 후속 연구에서 개선될 예정입니다.
[1] https://github.com/ElementsProject/elementsproject.github.io#new-opcodes 참조
[2] 여러 서명자의 여러 서명이 필요한 수준으로 코인을 잠그는 거래. M-of-N 멀티시그 구성에는 공개 키가 알려진 여러 서명자 N명의 서명 M개가 필요함.