초보자도 이해하기 쉬운 Secure MPC 기반 Multi-party ECDSA 이야기
아톰릭스랩 배경일
TL;DR Multi-party ECDSA(Elliptic Curve Digital Signature Algorithm)에서는 다수의 주체가 협력하여 하나의 ECDSA 개인키를 생성하되 각자는 개인키의 쉐어를 나눠 갖고, 이 중 어느 누구도 온전한 개인키를 알지 못합니다. 또한 개인키를 복원하지 않고도 다수가 협력하여 ECDSA 서명을 생성함으로써 BTC 혹은 ETH와 같은 디지털자산을 이체할 수 있습니다. 이후에도 각자는 개인키는 물론 다른 사람의 쉐어 정보조차 알지 못합니다. 얼핏 보면 이 과정이 약간은 마술같이 느껴집니다. 암호학의 초보적인 지식만 있으면 누구나 Multi-party ECDSA가 어떻게 가능한지를 쉽게 이해할 수 있게 하는 것이 이 글의 목적입니다. 그리고 실용적인 2 Party ECDSA에 대해서는 조금 더 자세하게 설명하고자 합니다. 물론 이를 안전하게 구현하고 상용화하는 것은 더욱 어려운 과정을 필요로 합니다만 이 글만으로도 기초적인 개념을 이해할 수 있을 것입니다.
블록체인이 가지는 핵심 가치는 디지털 자산의 관리 혹은 단체가 수행하는 행위(투표, 경매, 거래 등)를 중앙화된 서비스 공급자 없이 온전히 탈중앙화된 형태로 수행할 수 있다는 것입니다. 예를 들면 개인이 보유한 디지털자산을 금융사의 중개 없이 블록체인 상에서 보관 및 이체할 수 있으며, 심지어 탈중앙화 금융(이하 ‘DeFi’)을 통해서 대출을 하거나 디지털 자산간 교환을 할 수도 있습니다. 또한 스마트컨트랙이 작동 가능한 이더리움 같은 블록체인에서는 중앙화된 관리자 없이, 그리고 위변조 위험 없이 투표, 경매 등의 단체 행위를할 수 있습니다.
중앙화된 서비스 공급자를 거치지 않기 때문에 비용 절감(수수료 등), 규제 장벽 해소(국경간 거래 등), 서비스 공급자의 위변조 및 도산에 의한 손실 방지 등의 장점을 가질 수 있습니다.
그러나, 세상에 공짜는 없는 법. 그 이면에는 단점도 있습니다. 기존 시스템에서 중앙화된 서비스 공급자가 사용자들에게 제공하던 편의성을 기대하기 힘들다는 겁니다. 예를 들면 은행에 내 자산을 예치할 경우에는 통장 분실 시 언제든지 통장 재발급이 가능합니다. 또한 현금인출카드를 도난 당할 경우 은행에 연락해서 카드 사용을 중지시킬 수 있습니다. 블록체인의 경우 개인키를 분실할 경우 복구하는 것이 불가능하므로 개인키 분실은 곧 디지털자산의 분실을 의미합니다. 또한 제3자가 내 개인키를 알게 되면 자기 자산인 것처럼 언제든지 어느 위치에서든지 디지털자산을 이체하는 것이 가능합니다.
블록체인에서는 개인키를 알고 있는 것이 디지털자산을 소유하는 것과 같은 효과를 가집니다. 따라서 사용자로서 블록체인을 처음 접하는 분들이 가장 어려워하는 것이 바로 이 개인키의 관리입니다. 블록체인상 디지털자산의 보유자는 개인키를 잃어버리지 않고 잘 보관하는 것도 힘든데, 개인키를 제3자에게 유출되지 않도록 비밀리에 보관해야 한다는 어려움이 있는 겁니다.
사실 암호학계에서는 이러한 개인키 관리 상의 어려움을 해결하기 위해서 블록체인이 나오기 이전에도 수십년간 새로운 기술이 개발되어 왔으나 실생활에서는 상당히 제한적으로 활용되어 왔습니다. 그러나 비트코인이나 이더리움 같은 블록체인이 출현하고 이들의 디지털자산인 BTC, ETH 등의 가치가 상승하면서 기존에 암호학에서 발전해온 기법들이 최근에 급격하게 발전하고 있고 상용화가 시작되고 있습니다. Binance와 같은 암호화폐 거래소에서도 해당 분야를 심도 있게 연구개발하고 있으며 Multi-party ECDSA 전문 기업들이 높은 기업 가치를 인정받고 있습니다.
이 글에서는 기존 암호학에서 다루었던 개인키에 대한 고민과 해법들을 간략하게 소개하고 이중 가장 간단한 형태의 2 Party ECDSA 모델의 개념을 좀 더 자세히 설명하고자 합니다.
들어가기에 앞서 이 글은 암호학에 대한 기본 지식만 있으면 누구나 쉽게 이해할 수 있도록 구성되어 있습니다. ECDSA의 공개키가 개인키 X G (generator)로 생성된다는 것과 공개키로부터 개인키를 유추할 수 없다는 것(즉 개인키 X G 로부터 개인키를 알 수 없음, ECDLP)을 어느 정도 이해하고 있다면 아래의 내용을 바로 읽어도 좋습니다. 만약 기본적인 내용을 좀 더 체계적으로 이해하고 싶은 분들은 아래의 제 다른 글을 먼저 읽으시기를 권해드립니다:
개인키 사용상의 문제들과 암호학자들의 해법
문제: 개인키 분실 및 도난
앞서 말한 바와 같이 개인키를 분실하는 것은 디지털자산을 분실하는 것과 같습니다. 또한 제3자가 개인키를 알게 될 경우 해당 디지털자산을 언제든지 자기 것처럼 통제할 수 있습니다. 이때 자연스럽게 떠 오르는 방어책은 개인키를 분리해서 보관하는 것입니다. 예를 들면 개인키가 15일 경우 이를 나누어서 Alice가 3, Bob이 7, Carol이 5를 개인키 쉐어로서 가지는 겁니다. 이때 제3자는 이 중 한 명의 쉐어를 탈취해도 개인키가 15라는 것을 유추할 수 없습니다.
* 사실 ECDSA에서 개인키는 2^256에 가까운 굉장히 큰 수입니다. 여기에서는 쉬운 이해를 위해서 작은 수를 예시로 사용했습니다.
그런데 여기에는 문제가 좀 있습니다. 만약 Carol이 쉐어 5를 분실할 경우 Alice와 Bob이 가진 정보만으로는 개인키 15를 유추할 수 없다는 것입니다. 해커에 대한 방어력은 높아졌지만 분실 가능성은 결과적으로 더 높아진 거죠. 이에 대한 해법으로 제안된 것이 그 유명한 Shamir secret sharing입니다. (Shamir, Adi (1979), “How to share a secret”).
Shamir secret sharing을 이용하면 위 예에서 Alice, Bob, 그리고 Carol이 개인키 15를 분리한 숫자를 하나씩 알고 있게 하면서, 이 중 두 명의 정보 만으로 개인키 15를 복구 가능하게 합니다. 따라서 한 명이 쉐어를 잃어버려도 나머지 두 명의 쉐어들로 복구가 가능합니다. 또한 해커가 한 쉐어를 탈취하더라도 개인키를 유추할 수 없습니다.
[그림 1]은 비밀정보(개인키) 15를 (2,3) Shamir Secret Sharing 형태로 Alice, Bob, Carol에게 배분하는 것을 개념적으로 보여줍니다. 먼저 개인키를 알고 있는 딜러는 Y축의 15를 지나는 직선을 만드는데 이때 직선의 기울기는 랜덤하게 결정하고, 기울기는 딜러 외에 아무도 몰라야 합니다 ([그림 1]에서는 3이 기울기).
그리고, 직선 위의 점 (1, 18), (2, 21), (3, 24)를 Alice, Bob, Carol에게 각각 비밀리에 전달합니다. 이때 세 사람 중 누구도 자기가 가진 정보로는 15를 알 수가 없습니다. 예를 들면 Bob의 (2, 21)을 지나는 직선은 무한대로 많으므로 Bob은 15를 알 수가 없습니다.
그런데 세 사람 중 두 사람이 정보를 공유하는 순간 직선의 공식이 알려지고 직선과 Y축이 만나는 Y절편값인 비밀정보를 알게 됩니다(Lagrange interpolation). 물론 원래의 목적대로 한 명이 정보를 잃어버려도 다른 두 명의 정보 만으로 비밀정보를 복구할 수 있게 됩니다.
이런 식으로 t-1차 곡선을 활용하면 일반적인 (t, n) 방식의 Shamir secret sharing이 가능해집니다. 예를 들면 Y절편을 비밀값으로 하는 랜덤한 3차 곡선을 만든 후 곡선 위의 서로 다른 여섯 개의 점을 여섯 명에게 나눠주게 되면, 이 중 네 명의 정보 만으로 3차 곡선을 알게 되고 따라서 Y절편의 비밀값을 얻게 되죠. 이를 (4, 6) Shamir Secret Sharing이라고 합니다.
* 일반적으로 암호학에서는 해커가 탈취해도 개인키를 알 수 없는 최대 임계값(threshold)으로 t를 표기하여 네 명의 쉐어가 모여야 복구가 가능할 경우 t = 3으로 표기합니다. 그러나 이 글에서는 이해하기 쉽도록 t = 4로 표기하겠습니다.
문제: 개인키를 누가 나눌 것인가?
그런데 여기에도 문제가 하나 있습니다. 처음 키를 분배하는 과정에서 누군가(딜러)가 온전한 개인키를 알고 있다는 점입니다. 특히 블록체인과 같이 중앙화된 서비스 공급자가 없는 구조에서는 믿을 만한 개인키 분배 주체를 찾기가 어렵죠. 이러한 동기에서 분산 키 생성(이하 ‘DKG,’ distributed key generation) 이론이 발전하게 됩니다. 여기에서도 가장 간단한 예는 Alice, Bob, Carol이 각각 난수를 쉐어로 생성하고 이 수들의 합을 개인키로 하자고 합의하는 겁니다. 예를 들면 각자 3, 7, 5를 가지고 있을 때 15가 개인키가 됩니다. 딜러 없이 개인키를 정했으므로 아무도 개인키를 모르게 됩니다.
하지만 이전에 언급한 바와 같이 셋 중 한 명만 키를 분실해도 온전한 개인키를 복구하는 것이 불가능하게 됩니다. 이러한 문제를 해결하기 위해서 딜러 없이 다수가 개인키의 쉐어를 생성하되 생성된 쉐어들이 Shamir secret sharing이 되도록 하는 방식이 고안되었습니다.
[그림 2]는 딜러 없이 (2, 3) Shamir secret sharing을 만드는 DKG 기본 프로토콜의 예시를 보여줍니다.
* 뒤에서 소개하겠지만 [그림 2]는 참여자가 프로토콜을 왜곡하지 않고 수행하는 passive security 버전이며 또한 참여자가 결과를 검증할 수 없습니다.
Alice, Bob, Carol은 각자 생각한 난수를 자체적으로 Shamir secret sharing으로 분해하여 참여자들에게 비밀리에 쉐어를 전송합니다. 이후 각 참여자는 [그림 2]에서와 같이 자신이 보유한 쉐어와 다른 참여자들에게서 받은 쉐어들을 더해서 최종 쉐어를 생성합니다.
[그림 2]를 주의 깊게 살펴보면 세 참여자가 가지는 쉐어는 f(x) + g(x) + h(x) = 4x + 15로부터 생성된 Shamir secret share들임을 알 수 있습니다. 이 함수의 Y절편인 15는 개인키이며 기울기 4는 삼자가 랜덤하게 생성한 기울기들의 합이므로 아무도 모르는 상태입니다.
실제 시스템에서는 각 참여자가 자체적으로 자신의 쉐어가 맞는지와 다른 참여자가 프로토콜을 왜곡하지 않았는지를 검증할 수 있는 Verifiable secret sharing을 사용합니다 (P. Feldman, “A practical scheme for non-interactive verifiable secret sharing,” 1987).
문제: 누가 개인키를 복구하고 서명할 것인가?
위와 같은 방식으로 Alice, Bob, Carol이 Shamir secret share들을 가지고 있다고 해봅시다. 이후 개인키를 복구해서 디지털서명을 하고자 할 때 누군가는 두 개의 쉐어로 개인키를 복구해야 합니다. 그런데 복구하는 사람이 이 과정에서 온전한 개인키를 알게 됩니다. 만약 개인키로 1,000억원 가치의 디지털자산을 관리하고 있을 경우 한 사람이 개인키를 알게 되는 상황은 다른 두 사람이 쉽사리 용인하기 힘들 수 있을 겁니다.
* 이 글에서는 이더리움, 비트코인 등의 주류 블록체인에서 채택한 ECDSA를 가정해서 설명합니다. BLS 혹은 EC-Schnorr의 경우에는 개인키를 복원하지 않고 각자의 쉐어로 디지털서명하고 서명들을 합하는(signature aggregation)을 쉽게 할 수 있습니다. 이더리움 2.0에서 사용하는 BLS의 사례는 아래의 제 다른 글을 참고하세요:
이러한 이유로 인해 이 상황에 잘 맞는 암호 기법인 다자간보안컴퓨팅(이하 ‘Secure MPC,’ Secure Multi-party Computation)이 적용되기 시작합니다. Secure MPC는 다수의 파티들이 보유한 비밀 정보를 유출하지 않으면서(privacy preserving) 모든 비밀 정보가 있어야 계산이 가능한 수식을 계산할 수 있게 하는 암호학 방법론입니다. 또한 Secure MPC를 통해 산출된 결과는 각 파티들에 의해 검증 가능(verifiable)합니다. 예를 들면 Alice, Bob, Carol이 각자의 재산을 공개하지 않으면서 가장 재산이 많은 사람을 알아낸다든가, 세 사람 재산의 평균값을 계산할 수 있습니다.
* Secure MPC 자체도 40년 정도의 역사를 가진 암호학의 중요한 분야입니다. 이에 대한 일반적인 소개는 다음 글로 기약하겠습니다.
Secure MPC를 적용하면 위의 개인키 예에서 Alice, Bob, Carol이 (2,3) Shamir secret share를 가지고 있다고 할 때 이 중 두 사람이 각자의 쉐어를 공개하지 않으면서도 디지털 서명을 할 수 있습니다. 디지털 서명도 일정의 수식이니까요. 아래 [그림 3]의 (1) 수식에서 random number k에 타원곡선 base point G를 곱한 값(포인트)의 x 좌표를 r로 하고 개인키, 메시지 해시값(msghash), r, k 값으로 s를 계산합니다. 바로 이 (r, s) 값이 ECDSA의 서명값입니다.
만약 Alice와 Bob이 각각 share1과 share2를 가지고 있고 이 둘의 합이 개인키라면 두 사람의 쉐어를 이용한 서명값은 (2)와 같이 될 겁니다.
얼핏 보면 굉장히 간단한 연산으로 보이고 쌍방의 share 값을 공유하지 않고도 쉽게 서명값을 만들 수 있을 것처럼 보입니다. 그런데 여기에 복병이 하나 있는데 바로 k 값입니다. 만약 이 k 값이 유출되면 디지털 서명을 받은 사람이 아주 쉽게 개인키를 유추할 수 있습니다 ((1)의 s를 산출하는 공식 참조).
따라서 서명하는 자 외에 누구도 k 값을 몰라야 하므로 k를 ephemeral key라고 부릅니다. 그런데 Multi-party ECDSA에서는 서명에 다수가 참여하므로 이들이 서명 후에도 개인키를 모르게 하려면 이들 역시 서명에 사용된 k 값을 몰라야 합니다.
바로 이 점이 Multi-party ECDSA를 어렵게 만듭니다.
또 하나 유의할 점은 서로 다른 메시지를 서명할 때 k 값이 재사용 되면 안 된다는 겁니다. [그림 3]의 (3)을 보면 서로 다른 메시지에 대해 같은 k를 사용할 경우 (즉 r도 같아짐) s1과 s2를 아는 사람은 아주 쉽게 개인키를 알 수 있습니다.
* 가끔 ‘deterministic k’를 언제나 같은 k 값을 쓰는 것으로 오해하는 분들이 계십니다. 같은 메시지에 대해 k 값이 같다는 의미이지, 다른 메시지일 경우 위 내용대로 반드시 다른 k 값을 써야 합니다. 그래서 deterministic k는 개인키와 메시지에 HMAC을 적용해서 도출됩니다.
요약해 보면 개인키를 다수가 쉐어 형태로 생성하되 온전한 개인키는 아무도 모릅니다. 그리고, 디지털서명을 할 때는 Secure MPC를 적용하여 개인키를 복원하지 않고 디지털 서명을 가능하게 합니다.
대표적인 Multi-party ECDSA 방법론
현재 실용화되고 가장 광범위하게 구현되고 있는 방식은 다음 세가지가 있습니다:
* 이 세가지를 대표적으로 소개하는 건 순전히 제 개인적인 의견일 수도 있음을 먼저 밝힙니다. 국지적인 알고리즘 개선과 새로운 방식에 대한 제안은 지금도 계속되고 있습니다. 또 하나 짚고 넘어갈 것은 이 방법론들은 하루 아침에 나온 게 아니며 2000년대 초부터 제안된 다양한 시도들을 수없이 개선하고 조합한 끝에 나온 것들입니다.
Lindell17: 2 Party ECDSA
Yahuda Lindell 교수에 의해 2017년에 소개된 상당히 효율적인 암호 프로토콜입니다. 이 방식은 Alice와 Bob이 개인키의 쉐어를 나눠 가진 상태에서 두 쉐어를 공개하지 않고 디지털서명을 할 수 있게 합니다. Shamir secret sharing을 적용한 것은 아니므로 둘 중 한사람이 쉐어를 잃어버리면 개인키를 복구할 수 없습니다. 그러나 속도가 빠르고 알고리즘이 비교적 단순한 관계로 실제로는 상당히 유용한 기법입니다. 이 글 후반부에서는 2 Party ECDSA에 대해 더 자세히 설명하도록 하겠습니다.
GG18: ECDSA Threshold Signature Scheme
Rosario Gennaro 교수와 당시 대학원생인 Steven Goldfeder에 의해 2018년에 제안된 기법으로 위에서 언급한 Shamir secret sharing 방식으로 N명이 개인키를 공동 생성한 후 이 중 T명(threshold+1)이 공동 연산해서 디지털서명을 수행합니다. 2 파티로 제한되어 있는 Lindell17에 비해 2명이 넘는 다수의 공동 사인을 지원하는 것이 가능하고, Shamir secret sharing을 적용하므로 일부 개인키 유실에 대비할 수 있습니다. 이 글에서 자세한 로직을 설명하지 않겠지만 다음 글을 기약하겠습니다.
GG20: One round Threshold ECDSA
GG18을 개선한 알고리즘입니다. GG18의 경우 디지털서명을 하기 위해서 다수의 참여자(T명)가 암호화된 통신을 여러 번 수행합니다. 따라서 T가 증가할수록 그 속도가 현저하게 느려집니다. GG20에서는 디지털서명 이전에 사전 준비를 미리 해놓고(Secure MPC에서는 offline processing이라 함) 디지털서명을 해야 하는 시점에는 한번의 통신(one round)으로 디지털서명을 할 수 있게 합니다. 특정 유즈케이스의 경우 매우 유용한 방식입니다. 예를 들면 야간에 배치로 많은 수의 사전 준비를 하고 주간에는 빠른 디지털 서명을 할 수 있습니다.
아톰릭스랩에서는 위 세 가지 방식의 암호 프로토콜을 모두 사용하고 있고 서비스 특성에 따라서 적합한 방식을 채택해서 쓰고 있습니다. 예를 들면 개인용 블록체인 지갑의 경우 Lindell17을 적용하고, 기업용 Hot Wallet의 경우 GG18 혹은 GG20을 적용합니다.
Lindell17 2 Party ECDSA
Secure MPC에서는 보안 수준을 passive security와 active security로 나눕니다. Passive security란 각 참여자가 프로토콜을 정확하게(즉 왜곡 없이) 수행하는 것을 가정하되 전체 과정에서 각 파티는 다른 파티의 비밀 정보를 알 수 없습니다. Active security는 특정 파티가 프로토콜을 왜곡해서 다른 파티의 정보를 탐지하려 하거나, 결과를 자신이 의도한 방식으로 유도하는 것을 방지합니다.
* 프로토콜의 왜곡을 통해서 결과를 유도하는 대표적인 예가 rogue attack입니다. 필자가 쓴 다음 링크의 글을 보시면 rogue attack과 이의 방지법에 대해 자세하게 보실 수 있습니다:
Lindell17, GG18, GG20 모두 active security를 보장하는 기법입니다. Active security를 보장하기 위해서 모든 참여자들은 본인이 속이지 않는다는 것을 commitment 혹은 zero-knowledge proof를 이용해서 프로토콜의 각 단계에서 지속적으로 증명해야 합니다. 사실 이 부분이 프로토콜을 이해하거나 구현하는 데에 있어서 노력이 상당히 많이 들어가는 부분이기도 합니다.
이글에서는 알고리즘을 쉽게 이해하는 것을 목표로 하므로 passive security 방식으로 단순화해서 설명하고자 합니다. Active security를 위해 사용된 암호 기법(primitive)들에 대해 보다 자세히 이해하기 위해서는 Lindell17의 원 논문과 해당 논문의 레퍼런스 논문들을 읽기를 권해드립니다.
Preliminary — Paillier encryption
Paillier 암호는 대표적인 반동형(partially homomorphic) 암호 체계로 암호문 두 개를 더해서 두 암호문 내 두 평문의 합에 대한 암호문을 생성하는 것이 가능합니다. 예를 들면 Enc(a) ⊕ Enc(b) = Enc(a+b), c ⊗ Enc(d) = Enc(c∙d) 방식의 연산이 가능한 ⊕, ⊗ 연산이 존재하는 거죠. 이때 공개키로 암호화하고 개인키로 복호화하게 됩니다. 만약 Enc(g) ⊗ Enc(h) = Enc(g∙h)를 만족시키는 ⊗ 연산도 가능하다면 이를 완전동형(fully homomorphic) 암호라고 합니다. Lindell17은 물론 GG18과 GG20에서는 반동형 암호인 Paillier 암호 기법을 사용합니다. [그림 4]는 Paillier 암호의 기본 기능을 Python으로 작동시킨 예시입니다.
키 생성 프로토콜 (passive security)
Lindell17에서 Alice와 Bob이 개인키의 쉐어를 나눠 가지는 방식은 multiplicative sharing 방식입니다. 예를 들면 Alice가 a를 가지고 Bob이 b를 가지면 개인키는 a∙b가 됩니다. 이때 a와 b는 양쪽에서 생성하는 난수를 사용하므로 누구도 개인키 a∙b를 알지 못합니다.
[그림 5]는 Lindell17 2 Party ECDSA의 키 생성 프로토콜을 보여줍니다. 실제 구현에서 active security를 보장하기 위해 사용되는 zero-knowledge proof와 commitment 과정은 생략하고, passive security 버전으로 단순화했습니다.
(1) Alice와 Bob은 비밀 정보인 a와 b를 난수로 생성합니다. 이후 Alice는 Bob에게 a∙G를, Bob은 Alice에게 b∙G를 보냅니다.
(2) 각자 상대방에게 받은 값에 자신의 비밀 정보를 곱합니다. 결과적으로 Alice와 Bob은 각각 a∙(b∙G)와 b∙(a∙G)를 가지게 되므로 a∙b의 공개키, 즉 (a∙b)∙G를 양 측이 모두 알게 됩니다.
(3) Bob은 Paillier 개인키(dk, 복호화키)와 공개키(ek, 암호화키)를 생성합니다. 이후 Paillier 공개키를 이용해 b를 암호화한 β = Enc(b)를 계산합니다.
(4) Bob은 ek와 β를 Alice에게 전달합니다.
이제 Alice와 Bob은 개인키를 알지 못하지만 같은 공개키를 알게 되었고 Alice는 Bob의 Paillier 공개키 ek와 β를, Bob은 Paillier 개인키 dk를 알고 있습니다. 바로 이 정보들을 이용해서 Secure MPC 방식의 서명 생성 프로토콜이 작동합니다.
이제 서명 생성 프로토콜을 살펴보겠습니다.
서명 생성 프로토콜 (passive security)
앞에서 말한대로 ECDSA 서명에서 사용되는 난수 k는 서명자 외에는 누구도 몰라야 합니다. 그런데 2 Party ECDSA에서는 서명자가 둘이고 둘 다 서명 후에도 개인키를 몰라야 하므로 서명에 사용되는 k 역시 둘 다 모르게 적용해야 합니다.
어떻게 할까요?
바로 키 생성 프로토콜과 동일한 방식으로 k의 multiplicative share를 생성해서 이용합니다. 위에서 설명한 키 생성 프로토콜과 상당히 유사하죠.
아래 [그림 6]은 Lindell17 2 Party ECDSA의 서명 생성 프로토콜을 보여줍니다. 여기에서도 active security를 보장하기 위한 zero-knowledge proof와 commitment 과정은 생략하고, passive security 버전으로 단순화했습니다. 그리고 Alice와 Bob은 서명 대상 메시지의 해시값인 h를 둘 다 알고 있다고 가정합니다.
(1) Alice와 Bob은 각자 k의 multiplicative share인 k1과 k2를 난수로 생성합니다. 이후 Alice는 Bob에게 k1∙G를, Bob은 Alice에게 k2∙G를 보냅니다.
(2) 각자 상대방에게 받은 값에 자신의 값을 곱합니다. Alice와 Bob은 각각 k1∙(k2∙G)와 k2∙(k1∙G)를 가지게 되므로 (k1∙k2)∙G의 x 좌표값인 r 값을 양 측이 모두 알게 됩니다.
(3) Alice는 Bob의 Paillier 공개키를 이용해서 위 [그림 6]과 같이 다음 c 값을 산출해서 Bob에게 전달합니다: c = Enc(k1^–1 ∙ h + k1^–1 ∙ r ∙ a ∙ b)
(4) Bob은 Paillier 개인키로 c를 복호화한 후 여기에 k2의 역수를 곱해서 s값을 산출합니다.
(5) Bob은 생성된 서명값인 r과 s를 PubKey와 h로 검증합니다.
Bob은 서명값인 r과 s 값을 산출하게 되고 이를 직접 사용하거나 Alice에게 전달합니다. Alice와 Bob은 모두 ECDSA 공개키(a∙b∙G)와 메시지 해시 h를 가지고 있으므로 서명을 검증할 수 있습니다 (verifiable).
또한 (4)번 과정에서 Bob은 c를 복호화해도 Alice의 비밀정보인 a와 k1 값을 알 수 없습니다 (privacy-preserving, 비밀정보들의 곱으로 이루어져 있기 때문에 무수하게 많은 경우의 수가 나오기 때문). 실제 Lindell의 논문과 구현 과정에서는 좀 더 엄격한 비밀 유지를 위해서 약간의 트릭을 부가합니다만 이 글에서는 쉬운 이해를 위해서 이 정도만 소개하겠습니다.
결과적으로 Alice와 Bob은 각자 가지고 있는 multiplicative share인 a와 b를 유출하지 않으면서 디지털 서명 값인 r과 s를 도출할 수 있게 됩니다. 또한 제3자가 이들 간의 교신 내용을 중간에서 도청한다고 해도 Alice와 Bob이 가진 쉐어를 유추할 수 없습니다.
글을 마무리하며
개인키의 쉐어가 나눠져 있기 때문에 가지는 가장 큰 장점은 보안성입니다. 해커가 한 사용자의 쉐어를 탈취한다고 해도 하나의 쉐어만으로는 완전한 개인키를 유추할 수 없기 때문에 보다 안전합니다.
또한 쉐어가 나눠져 있기 때문에 양자 간의 합의가 없이는 서명을 할 수가 없게 됩니다. 따라서 기존의 멀티시그 방식을 대체할 수 있습니다. 멀티시그 자체도 상당히 유용한 기법이기는 하지만 블록체인마다 다른 구현 방식을 써야 하며 서명 시 높은 트랜잭션 수수료를 소비해야 합니다. 반면 Multi-party ECDSA의 경우에는 ECDSA가 사용되는 모든 블록체인에 동일한 방식으로 적용 가능하고 한번의 트랜잭션 수수료만 내면 됩니다.
이외에도 기존 블록체인 지갑 대비 특별한 가치를 부여할 수 있는데 예를 들면 안전한 룰 적용(이체 한도, whitelist, blacklist 등)과 2FA(2 Factor Authentication)가 가능해집니다.
개인키가 사용자 단말 혹은 서버 중 한 곳에 존재한다면 그 지점에서 해커가 룰을 조작해서 트랜잭션을 성공시키는 것이 가능합니다. 예를 들면 하드웨어 지갑의 경우 데스크탑 어플리케이션과 하드웨어 단말 사이의 데이터 송수신을 조작해서 암호화폐를 탈취하는 경우가 있었습니다. 그러나 쉐어가 나눠져 있을 경우에는 양쪽에서 룰을 체크하므로 해커로부터 보다 안전합니다.
또한 개인키가 어느 한쪽에 있을 경우에는 2FA 자체가 불가능하나 한 쉐어를 사용자가, 나머지 쉐어를 서버가 가지고 있을 경우 서버는 사용자에게 2FA 인증을 요구함으로써 보다 보안성을 높이는 것이 가능해집니다.
이상으로 Lindell17의 passive security 버전을 설명했습니다. 만약 Alice와 Bob이 절대 조작할 수 없는 소프트웨어 프로그램으로 구성되어 있다면 이 글에 있는 passive security 버전만으로도 원하는 결과를 얻을 수 있을 겁니다. 그런데 이러한 가정은 현실세계에서는 불가능하고 특히 일반 사용자의 모바일 단말 혹은 웹 브라우저 환경에서는 프로그램이 언제든지 해킹될 수 있습니다. 따라서 반드시 active security를 보장하는 형태로 어플리케이션을 구현해야 합니다.
Lindell17, GG18, GG20 등의 논문에서 제시된 active security 프로토콜을 적용할 때 가질 수 있는 큰 장점은 프로토콜의 보안성이 수학적으로 검증되어 있다는 것입니다. 즉 일부 파티 혹은 제3자가 다른 파티의 정보를 유추해 내거나 결과를 자신이 의도한 대로 왜곡시키는 것이 불가능하다는 것을 수학적으로 검증한 것입니다.
그럼에도 불구하고 실제 어플리케이션을 개발할 경우에는 논문에 기술된 기본 프로토콜 외에도 상당히 많은 부분을 고려해야 합니다. 제 경험상 블록체인과의 상호작용, 백업, 보안 통신, 멀티 유저 동시 처리 등 많은 부분에서 기본 프로토콜 외의 암호학적인 고려가 필요합니다.
또한 개발 측면에서도 기본 프로토콜의 보안성을 훼손하지 않는 한에서 플랫폼(모바일, 데스크탑, 웹브라우저 등)에 따라 최적화를 해야 합니다. 대부분의 암호 프로토콜은 작동되는 플랫폼의 성능상 제약에 대해 고려하고 있지 않으며, 일부 암호 연산의 경우에는 상당히 많은 컴퓨팅 자원을 동원해야 할 수도 있습니다. 따라서 플랫폼 별로 사용자가 받아 들일만한 응답 속도를 내게 만드는 것은 온전히 개발자의 몫이며 이때 개발자는 기본 프로토콜에 대해 정확하게 이해하고 있어야 합니다.
아톰릭스랩은 2년반동안 이러한 과정을 거친 끝에 개인용 지갑 Dekey를 출시하였습니다. 기본 프로토콜은 Lindell17의 active security 버전을 적용하였으며 상당히 긴 기간동안 블록체인 인터페이스, 백업, 보안 통신, 플랫폼 최적화 과정을 거쳤습니다.
Dekey가 많은 분들의 안전한 암호화폐 보관과 사용에 기여하기를 바랍니다. 자세한 내용은 Dekey 홈페이지 http://dekey.app을 참조하시기를 바랍니다.
다음 글에서는 아톰릭스랩의 기업용 지갑에 적용된 GG18과 GG20에 대해 알기 쉽게 설명해 보도록 하겠습니다.
긴 글 읽어 주셔서 고맙습니다.
