지난 월요일, Blockstream은 Schnorr 서명을 기반으로 한 다중 서명 체계인 MuSig를 소개하는 논문을 발표했습니다. 이 게시물은 MuSig의 구성과 비트코인에 대한 몇 가지 응용 방법에 대해 다룰 것입니다.
MuSig는 다음을 통합하는 데 획기적인 간단한 다중 서명 체계입니다.
- 키 집계 지원
- 일반 공개 키 모델의 보안
MuSig에는 두 가지 버전이 있는데, 이는 통신 라운드 수에 따라 다릅니다. 두 가지 모두 안전성은 입증 가능하지만, 3 라운드 MuSig는 ECDSA도 의존하는 DL(Discrete Logarithm) 가정에만 의존합니다. 반면, 2 라운드 MuSig는 조금 더 강력한 OMDL(One-More Discrete Logarithm) 가정에 의존합니다.
이 글은 비트코인의 Schnorr 서명에 대한 연구 결과이지만, MuSig는 다른 응용 프로그램에 유용할 수 있는 암호의 구성입니다. 논문과 이 게시물은 주로 MuSig의 암호화 속성에 대해 설명하며, 비트코인에 대한 직접적인 제안은 아닙니다.
다중 서명 체계는 서명과 검증 알고리즘의 조합으로, 여러 서명자(각각 자신의 개인/공개 키를 가짐)가 단일 메시지에 서명하여 단일 서명을 생성합니다. 그러면 해당 메시지와 서명자들의 공개 키를 알고 있는 사람이라면 누구나 이 단일 서명을 검증할 수 있습니다. 비트코인의 맥락에서 "멀티시그"라는 용어는 일반적으로 k-of-n 정책을 나타내는데, 여기서 k는 n과 다를 수 있습니다. 반면 암호화 논문에서 다중 서명은 n-of-n 위에 k-of-n을 쉽게 구성할 수 있지만, 실제로 n-of-n 정책만을 일컫습니다.
우리는 단일 키 서명처럼 보이는 다중 서명을 언급할 때 키 집계라는 용어를 사용하지만, 집계된 공개 키의 경우 이는 오직 해당 참가자들의 공개 키의 기능입니다. 즉, 검증인은 더 이상 원래 참가자들의 공개 키를 알 필요가 없다는 것입니다. 대신 간단하게 집계된 키만 받을 수 있습니다. 일부 사용 사례를 보면, 이를 통해 개인정보 보호 및 성과가 개선됩니다. MuSig는 사실상 Schnorr 서명을 위한 키 집계 체계입니다.
실질적으로 Schnorr 서명에 대한 키 집계를 제공하는 몇 가지 다중 서명 체계가 이미 존재하지만, 여기에는 참가자들이 보유하고 있다고 주장하는 공개 키에 상응하는 개인 키를 실제로 가지고 있는지 검증해야 하는 점 등 몇 가지 주의가 따릅니다. 일반 공개 키 모델의 보안은 이러한 주의가 존재하지 않는다는 것을 의미합니다. 참가자들로부터 요청해야 하는 것은 공개 키뿐입니다.
비트코인에서 다중 서명 활용
비트코인에서 멀티 서명을 사용하는 가장 확실한 사례는 n-of-n 다중 서명 스크립트 및 여러 가지 가능한 키 조합(key trees 또는 MAST, 기존의 임계값 체계를 사용한 k-of-n 포함)을 허용하는 기타 정책을 보다 효율적으로 대체하는 것입니다. 이러한 경우, 본래의 다중 서명 체계는 거래 입력 당 하나의 서명이 남아있음을 의미합니다. 또한, 키 집계 체계를 사용하면 입력 당 공개 키 수를 하나로 줄일 수 있습니다. 사용자가 해당 스크립트에 모두 포함시키는 대신 모든 관련 키의 집계에 코인을 보낼 수 있기 때문입니다. 이로써 온체인 차지 공간(on-chain footprint)은 더 작아지고, 검증은 더 빨라지며, 개인정보 보호는 더욱 개선됩니다. 결과적으로, 여기서 MuSig는 좋은 선택입니다.
그러나 이를 더욱 발전시킬 수도 있습니다. 입력 당 하나의 서명으로 제한하는 대신, 실제로 전체 거래에 대해 하나의 서명을 얻을 수 있습니다. 공개 키는 출력에 의해 커밋되고(committed) 독립적으로 사용될 수 있기 때문에, 키 집계는 여러 입력에 걸쳐 사용될 수 없습니다. 여기에서 (검증인이 수행하는 키 집계를 통해) MuSig가 사용될 수 있지만, 키 집계를 지원하지 않는 더욱 잘 알려진 일반 공개 키 다중 서명 체계인 Bellare-Neven(BN)으로도 충분합니다. 흥미롭게도 개별 키가 MuSig 집계인 BN 다중 서명을 사용할 수 있습니다.
엄밀히 따지면, 모든 거래 입력의 서명을 하나로 통합하기 위해서는 다중 서명 체계가 아니라 집단 서명 체계가 필요합니다. 둘의 차이점을 쉽게 설명하자면, 집단 서명에서는 각 서명자가 모두가 공유하는 하나의 메시지가 아닌 자신만의 메시지를 가지고 있다는 점입니다. 집단 서명은 상호작용 또는 비상호작용 유형으로 분류할 수 있습니다: 상호작용형 집단 서명(IAS)은 서명자들이 협력해야 하는 반면, 비상호작용형 체계에서는 누구나 집계를 수행할 수 있습니다. DL 가정에만 의존하는 비상호작용형 집계 체계는 알려진 것이 없지만, 상호작용형 체계는 쉽게 구성할 수 있습니다. 다중 서명 체계를 취하고 모든 참가자에게 모든 메시지의 집합에 서명하도록 하면 됩니다. Blockstream의 논문에서는 이것이 항상 바람직한 구성 방법은 아니라는 것을 보여주며 대신 더 우수한 특성을 지닌 BN의 IAS 변형을 제시합니다.
세부 내용
표기법:
● x, x1, x2, …는 상응하는 공개 키가 X, X1, X2, …인 개인 키(Xi = xiG, G 는 생성기)
● 서명되고 있는 메시지는 m
● H() 는 암호화 해시 함수
Schnorr 서명
복습 차원에서, Schnorr 서명과 관련된 공식은 다음과 같습니다:
● 서명은 (R,s) = (rG, r + H(X,R,m)x). 여기서 r은 서명자가 선택한 임의의 논스.
● 검증에는 sG = R + H(X,R,m)X가 필요
원시적인 Schnorr 다중 서명
다중 서명을 지원하기 위해 다음과 같이 단순한 일반화가 가능합니다:
● X는 Xi 포인트의 합이라 함
● 각 서명자는 임의의 논스 ri,를 선택하고 다른 서명자들과 Ri = riG를 공유
● R은 Ri 포인트의 합이라 함
● 각 서명자는si = ri + H(X,R,m)xi를 산출
● 최종 서명은 (R,s). 여기서 s는 si 값의 합
● 검증에는 sG = R + H(X,R,m)X가 필요. 여기서 X는 개별 공개 키의 합
흥미롭게도, 이는 위에서 언급한 “여러 당사자가 키의 합에 대해 유효한 단일 키 서명인 하나의 서명을 공동으로 생성할 수 있다”는 키 집계 체계의 정의를 충족합니다. 이렇게나 간단하다면 도대체 무엇이 문제일까요?
물론, 문제는 이 체계가 안전하지 않다는 것입니다. 다음 시나리오를 생각해 보세요. Alice와 Bob은 함께 다중 서명을 생성하고자 합니다. Alice는 키 페어 (xA,XA)를, Bob은 (xB,XB)를 가지고 있습니다. 그러나 Bob이 공개 키를 XB’ = XB - XA라고 주장하는 것을 막을 수 있는 것이 없습니다. 만약 Bob이 그렇게 주장한다면, 다른 사람들은 XA + XB’가 Alice와 Bob이 서명하기 위해 협력해야 하는 집계 키라고 생각할 것입니다. 안타깝게도, 그 합은 XB와 동일하고, Bob은 분명 여기에 혼자 서명할 수 있습니다. 이를 불량키(rogue-key) 공격이라 부르는데, 이러한 공격을 방지하는 한 가지 방법은 먼저 Alice와 Bob이 자신이 주장한 공개 키에 상응하는 개인 키를 소유하고 있다는 것을 증명하도록 하는 것입니다. 그러나 이런 방법이 언제나 가능한 것은 아니고, 가능하다 해도 충분하지 않습니다. Blockstream은 이상적 방안으로서 해당 키의 대역 외 검증에 의존하지 않는 보안 체계를 구성합니다.
Bellare-Neven
앞서 언급한 바와 같이, BN 다중 서명 체계는 이러한 위험 없이 안전합니다. 이유는 다음과 같습니다:
● L = H(X1,X2,…)
● 각 서명자는 임의의 논스 ri를 선택하고 다른 서명자들과 Ri = riG를 공유
● R은 Ri 포인트의 합이라 함
● 각 서명자는 si = ri + H(L,Xi,R,m)xi를 산출
● 최종 서명은 (R,s). 여기서 s는 si 값의 합
● 검증에는 sG = R + H(L,X1,R,m)X1 + H(L,X2,R,m)X2 + …가 필요
사실상, BN은 서명자들이 Ri 포인트를 공개하기 전에 서로 H(Ri)를 먼저 공개하는 프리커밋(precommit) 라운드를 거칩니다. 이 단계는 DL 가정 하에서 보안을 증명하는 데 필요하지만, OMDL 가정을 대신 채택하면 이 단계를 거치지 않아도 됩니다. 이것은 2 라운드와 3 라운드 MuSig의 또 다른 차이점입니다.
2019-02-19 업데이트 : Drijvers 외의 논문에 비추어 봤을 때, 위 문단의 내용이 옳지 않다는 것이 밝혀졌습니다. MuSig에서 프리커밋 라운드를 거치지 않는 것은 안전하지 않습니다.
또한, IAS가 바람직한 경우(각 서명자가 자신의 메시지를 가지고 있는 경우), 본 논문의 부록 A는 대신 L = H((X1,m1),(X2,m2),…)를 사용하고 서명(및 유사 검증)에는 si = ri + H(L,R,i)xi.를 사용할 것을 제안합니다.
어떠한 경우든, 결과적인 서명은 더 이상 일반 Schnorr 공식이나 공개 키 조합의 함수로 작성될 수 있는 그 어떤 공식도 충족하지 않습니다. 즉, 일반 공개 키 모델에서 보안을 확보하기 위해 키 집계의 특성은 잃게 된 것입니다.
MuSig
여기에서 MuSig가 등장합니다. MuSig는 다음과 같이 보안을 희생시키지 않고도 키 집계의 특성을 복구시켜 줍니다:
● L = H(X1,X2,…)
● X 는 모든 H(L,Xi)Xi의 합이라 함
● 각 서명자는 임의의 논스 ri를 선택하고 다른 서명자들과 Ri = riG를 공유
● R 은 Ri 포인트의 합이라 함
● 각 서명자는 si = ri + H(X,R,m)H(L,Xi)xi를 산출
● 최종 서명은 (R,s). 여기서 s는 si 값의 합
● 검증은 다시 sG = R + H(X,R,m)X를 충족
됐습니다! 해결책은 X를 개별 공개 키 Xi의 단순 합계가 아니라 해당 키의 배수의 합으로 정의하는 것이었습니다 (곱셈 계수는 모든 참여 키의 해시에 의존).
감사의 말
MuSig의 보안을 검토하고, 보안 증명을 작성하며, MuSig라는 이름을 짓는 데 도움을 주신 Yannick Seurin님께 감사의 말씀을 전합니다.