MPC란 무엇인가요?

블록체인 애호가들은 신뢰에 대해 이야기하는 것을 좋아하는데, 그럴 만한 이유가 있습니다. 신뢰는 우리 문명의 토대입니다. 가족과 이웃에 대한 신뢰가 초기 인류 집단의 기능을 유지해 주었습니다. 정부, 법정화폐, 법치와 같은 인간이 만든 제도에 대한 신뢰는 현대 문명의 원동력이 되어 왔습니다. 하지만 이러한 모든 사례에는 부적절한 행동이 발생할 경우를 대비한 ‘그렇지 않으면’이라는 조건이 필요합니다. 가까운 사람들에게 외면당하거나, 전통적인 소송을 당하는 식이죠. 그러나 지난 수십 년간, 특히 게임 이론과 암호학 분야의 새로운 수학적 발전은 부적절한 행동이 불가능한 시스템을 우리에게 선사했다. 우리는 이러한 시스템이 우리가 나아가고 있는 사회의 기초가 될 것이라고 주장한다. 깨질 수 없는 계약은 '깨지면 안 되지만, 그렇지 않을 경우'라는 조건이 붙은 계약보다 언제나 더 큰 신뢰를 불러일으킬 것이다.

지금까지 이러한 열정의 대부분은 화폐 제도에 집중되어 왔다. 비트코인은 본질적으로 자체 가치의 건전성을 보장하는 글로벌 네트워크라는 개념을 대중화했다. 하지만 이러한 신뢰의 전환이 시사하는 바는 훨씬 더 광범위하며, 그 잠재력의 진면목을 진정으로 파악한 사람은 거의 없다. 이러한 기술들은 단순히 화폐를 변화시킬 뿐만 아니라, 우리가 정보를 다루는 방식까지 바꿔놓을 것이다.

수백만 달러를 들여 방대한 이미지 라이브러리를 제작하고 확보한 대형 이미지 저장소 운영자라고 가정해 보십시오. 하지만 당연히도, AI 기업이 정당한 금전적 보상 없이 귀사의 데이터를 빼돌려 자사 모델 훈련에 활용할까 봐 우려하고 계실 것입니다. 당신은 라이선스 계약서와 비밀유지계약서(NDA)를 작성하기 위해 법무팀 전체를 고용하고, 설령 고객사의 남용 행위를 발견한다 해도 이를 제재하기 위해 수백만 달러를 소송 비용으로 지출해야 할지도 모릅니다. 하지만 그 대신, 당신과 고객 모두가 정직하게 행동하도록 보장해 주는 기술이 존재한다면 어떨까요? 수많은 변호사가 아닌, 암호학이 공정한 규칙의 이행을 보장해 준다면 어떨까요?

다자간 연산(MPC)은 바로 그러한 기술 중 하나입니다. 비트코인이 부정직한 참여자가 존재하더라도 화폐의 가치가 유지되는 게임의 모범 사례라면, MPC는 정보 소유권 측면에서 이에 상응하는 개념이라 할 수 있습니다. 위의 시나리오에서 이미지 라이브러리는 자신들과 고객 사이에 게임을 설정할 수 있는데, 이를 통해 고객은 자신의 이미지로 모델을 훈련할 수 있지만 단 한 번만 가능하다. 프라이버시가 판도를 바꾸는 이러한 상황은 AI, 의료, 산업 연구개발, 정치 등 수많은 분야에서 끊임없이 발생한다. 이 사례에서는 법적 계약을 타당하게 집행할 수 있는 제도적 권한이 존재했지만, 많은 상황(예: 지정학)에서는 그러한 권한이 존재하지 않습니다. MPC는 서로를 신뢰하지 않는 당사자들 간의 협력을 가능하게 함으로써 인류에게 완전히 새로운 가능성을 열어주며, 새로운 형태의 협력, 과학, 무역, 그리고 자유가 꽃피울 수 있도록 합니다.

이번 시리즈에서는 MPC를 심층적으로 살펴보며, 핵심 개념을 소개한 후 Arcium이 이를 활용해 블록체인에 프로그래머블 프라이버시를 구현하는 방법에 대해 중점적으로 다룰 예정입니다.

MPC는 다양한 시나리오에 맞춰 여러 형태로 존재하며, 크게 네 가지 유형으로 나뉩니다. 피어(peer) 대다수가 정직하게 행동할 것이라고 믿을 수 있다면, 정직한 다수결 프로토콜을 선택하게 될 것입니다. 오직 자신만을 신뢰할 수 있다면, 부정직 다수 프로토콜을 선택하게 됩니다 . 마찬가지로, 모든 피어가 프로토콜을 일탈 없이 따를 것이라고 가정할 수 있다면, 반정직( 또는 더 구체적으로는 '정직하지만 호기심 많은'이라고도 함) 프로토콜을 선택하게 됩니다. 반대로, 어떤 공격자로부터도 안전한 프로토콜은 악의적 공격에 대한 안전성을 갖춘 것으로 불립니다.

완전히 안전한 방법이 있는데 굳이 덜 안전한 방법을 선택할 이유가 있을까요? 한마디로 ‘효율성’ 때문입니다. 이러한 더 강력한 가정들은 더 안전한 대안들에서는 불가능한 강력한 최적화와 단축 경로를 가능하게 합니다. 더 빠른 연산, 더 적은 대역폭, 더 적은 통신 횟수는 모두 매력적인 요소들입니다. 이러한 안전성이 낮은 프로토콜들은 공개 블록체인 같은 적대적 환경에서 때때로 사용되기도 하지만, 항상 보안을 보완하기 위해 다른 기본 요소들과 결합됩니다. 예를 들어, Stoffel MPC는 신뢰 실행 환경(TEE)을 사용하고, TACEO는 coSNARKS를 사용하는데, 이 둘 모두 추가적인 보장을 제공하지만 그 자체로 일련의 장단점을 수반합니다.

Arcium은 MPC의 가장 안전한 형태인 ‘부정직한 다수( dishonest majority )’ 및 ‘악의적인 보안(malicious security)’ 방식을 활용합니다. 이는 또한 이번 시리즈에서 가장 집중적으로 다룰 방식이기도 합니다. 다른 방식에 대한 탐구를 원하신다면, Daniel Escudero의 ‘MPC 입문 강좌(A Crash Course in MPC )’ 시리즈를 읽어보시기를 추천합니다.

대략적으로 말해, 우리가 사용하는 MPC 방식은 ‘오프라인 단계 ’와 ‘온라인 단계’라는 두 단계로 작동합니다 . 오프라인 단계(이름과는 달리 여전히 통신이 수반됩니다!)는 '전처리'라는 형태의 연료를 생산하는 지속적인 과정으로 생각할 수 있습니다 . 온라인 단계에서 실제 계산이 수행될 때 , 이 연료의 일부가 소비됩니다 . 이 모델의 장점은 느리고 부피가 큰 암호화 작업을 언제든지 수행할 수 있는 오프라인 단계로 옮길 수 있다는 점입니다. 무거운 작업이 미리 완료되었기 때문에 온라인 단계는 매우 간결하게 유지될 수 있으며, 이는 더 빠른 계산 속도와 더 나은 사용자 경험(UX)으로 이어집니다. 이 두 단계는 상당히 구별되므로, 두 단계 중 더 간단한 온라인 단계부터 시작하여 별도의 섹션에서 다루겠습니다.

온라인 단계

비밀 분산

분산 연산은 정보의 공유를 전제로 합니다. 하지만 이 데이터가 비공개로 유지되어야 한다는 조건은 문제를 야기합니다. 당사자들이 전혀 알지 못하는 데이터로 어떻게 연산을 수행할 수 있겠습니까? 그 해답은 바로 ‘비밀 분산’입니다!

비밀 분할 방식은 암호학의 핵심 원시 기법 중 하나입니다. 이 방식을 통해 서로 다른 사람들이 비밀의 일부를 각각 보유하게 되며, 특정 조건(일반적으로 N개 조각 중 T개를 조합하여 비밀을 복원하는 것)을 충족하지 않는 한 그 비밀에 대해 아무것도 알 수 없습니다. 여러 방식이 존재하지만, 여기서는 가장 간단한 방식인 가산 비밀 분할에 초점을 맞추겠습니다.

Additive secret sharing takes a secret \( x \) and encodes it over a field.  
It generates \( N \) random-looking secret shares (our fragments) \( \{x_i\} \) such that:

\[
\sum_{i=1}^{N} x_i = x
\]

\( x_i \)는 모두 무작위처럼 보이기 때문에, 단 하나의 셰어만 빠져도 결과는 무작위처럼 보이며 \( x \)에 대한 정보를 전혀 드러내지 않습니다. 모든 참여자가 \( x \)를 재구성하기 위해 자신의 셰어를 방송할 때, 이를 \( x \) 를 공개한다고 합니다. 공개 과정은 네트워크 통신의 가장 큰 비중을 차지하는데, 이는 모든 참여자가 다른 모든 참여자에게 \( S \)바이트를 전송하고, 모든 참여자로부터 동일한 양의 데이터를 수신해야 하기 때문입니다. 대역폭 사용량은 \( \mathcal{O}(N^2) \)의 비율로 증가한다고 말합니다.

이제 우리는 신뢰 없이도 정보를 공유할 수 있는 방법을 갖게 되었습니다. 만약 이 정보를 바탕으로 연산을 수행할 수만 있다면… 바로 이것이 온라인 단계의 핵심입니다! 이 단계는 공유값 \( \lbrack\!\lbrack x \rbrack\!\rbrack \)와 \( \lbrack\!\lbrack y \rbrack\!\rbrack \)에서 \( \lbrack\!\lbrack x + y \rbrack\!\rbrack \)의 공유값으로, \( \lbrack\!\lbrack x * y \rbrack\!\rbrack \) 등의 지분을 만드는 방법을 설명하는 일련의 작은 프로토콜들을 모아놓은 것입니다. 소수의 연산만으로도 우리는 이 산술 형식으로 어떤 프로그램이든 작성할 수 있으며, 이를 산술 회로라고 부릅니다. 가장 중요한 프로토콜인 덧셈과 곱셈에 대해 살펴보겠습니다.

덧셈은 가장 간단합니다. \( \lbrack\!\lbrack x + y \rbrack\!\rbrack \)을 \( \lbrack\!\lbrack x \rbrack\!\rbrack \)과 \( \lbrack\!\lbrack y \rbrack\!\rbrack \)을 얻으려면, 각 항을 국소적으로 더하면 됩니다. 즉, \( \lbrack\!\lbrack x \rbrack\!\rbrack + \lbrack\!\lbrack y \rbrack\!\rbrack \)입니다. 이는 쉽게 알 수 있습니다:

\[ \left[
\right] \sum_i x_i + \sum_i y_i = \sum_i (x_i + y_i) = x + y \
\]

자, 곱셈은 어떻게 할까요? 단순한 접근 방식이라면 위와 마찬가지로 두 항을 서로 곱하는 것입니다. 왜 이것이 맞지 않는지 살펴보겠습니다: \[ \left
\sum_i (x_i y_i)\neq \left( \sum_i x_i \right)\!\left( \sum_i y_i \right) \
\]

사실, 단순히 공유량을 곱하는 것만으로는 충분하지 않습니다. 총합에는 자신의 공유량과 다른 당사자들의 공유량 간의 곱도 포함되기 때문입니다. 직관적으로 보면, 이는 어떤 형태의 소통이 필요함을 의미합니다. 비밀 공유량끼리 서로 곱하는 방법은 무엇일까요?

이 단계에서 앞서 언급한 전처리 과정 중 일부가 적용됩니다. 오프라인 단계에서 각 당사자는 비버 3원조(Beaver triple)의 공유값을 생성하는데, 이는 \( a * b = c \)라는 관계로 묶인 세 개의 랜덤 필드 원소 \( (a, b, c) \)입니다. 각 당사자는 \( a \), \( b \), \( c \)의 비밀 분할을 받습니다. 이 분할들이 준비되면, 두 분할 \( \lbrack\!\lbrack x \rbrack\!\rbrack \)와 \( \lbrack\!\lbrack y \rbrack\!\rbrack \)를 곱하는 지침은 다음과 같습니다:

1. 각 당사자 \( P_i \)는 \( \lbrack\!\lbrack \varepsilon \rbrack\!\rbrack_i = \lbrack\!\lbrack x \rbrack\!\rbrack_i - \lbrack\!\lbrack a \rbrack\!\rbrack_i \)와 \( \lbrack\!\lbrack \delta \rbrack\!\rbrack_i = \lbrack\!\lbrack y \rbrack\!\rbrack_i - \lbrack\!\lbrack b \rbrack\!\rbrack_i \)를 계산한다.
2. 두 분수를 모두 펼치면 \( \varepsilon \)과 \( \delta \)를 구할 수 있다.
3. 각 당사자 \( P_i \)는 \( \lbrack\!\lbrack x * y \rbrack\!\rbrack_i = \lbrack\!\lbrack c \rbrack\!\rbrack_i + \lbrack\!\lbrack a \rbrack\!\rbrack_i * \delta + \lbrack\!\lbrack b \rbrack\!\rbrack_i * \varepsilon \)를 계산한다.

\( a * b = c \)라는 사실을 떠올리면, 이 관계가 성립하는 이유를 쉽게 알 수 있습니다. 우리가 본질적으로 한 일은 입력 선들을 마스킹하여, \( \varepsilon \)과 \( \delta \)를 열었을 때 누구도 유용한 정보를 알아낼 수 없게 하면서도, 이를 통해 곱의 일부를 추론할 수 있도록 한 것입니다.

평문을 다루는 다른 연산들(예: 공개 값 \( c \)에 비밀 공유 \( \lbrack\!\lbrack x \rbrack\!\rbrack \)을 곱하는 연산)은 매우 간단하며 거의 항상 로컬에서 수행됩니다.

보시다시피, 특정 작업에는 당사자 간의 통신이 필요합니다. 눈치 빠른 독자라면 위협 모델에 대한 짧은 소개를 기억하실 것입니다. 동료들이 정직하게 행동할 것이라고 믿을 수 없다면, 그들이 올바른 정보를 보냈는지 어떻게 알 수 있을까요? 사실입니다. 비밀 공유 정보만 따로 보낸다면, 올바른 데이터와 잘못된 데이터를 구분할 수 없습니다. 이러한 시나리오에서 MPC 프로토콜은 종종 간단하지만 다소 마법 같은 기본 요소인 MAC(메시지 인증 코드)을 활용합니다.

프로토콜의 각 단계에서 모든 비밀 분할 데이터가 인증된다고 가정할 수 있는데, 이는 수신자가 해당 데이터가 올바른지 확인하는 데 도움이 되는 추가 정보가 함께 제공된다는 것을 의미합니다. MAC 방식이 안전하려면 위조가 불가능해야 합니다. 즉, 악의적인 발신자가 잘못된 데이터 조각에 대해 수신자가 받아들일 만한 MAC을 찾아낼 수 없어야 하며, 극히 낮은 확률을 제외하고는 그러한 일이 발생해서는 안 됩니다.

In our protocol, BDOZ, a secret share is authenticated in the following way: say \( x \) is your secret share, \( K = (\alpha, \beta) \) is the receiver’s MAC key, and \( \mathrm{MAC}(x) = \alpha * x + \beta \) is the MAC. Since the sender does not know \( K \), she is not able to compute a correct MAC for any other secret share. And of course, the receiver does not know the sender’s secret share \( x \) in advance. In addition, the scheme is additively homomorphic, meaning there is a way to add two authenticated secret shares together such that the MACs and keys remain correct:

\[ \left[
\right] \left[x\right] \left[y\right] = \{x + y, \mathrm{MAC}(x) + \mathrm{MAC}(y)\}, \quad K_x + K_y = (\alpha, \beta_x + \beta_y) \
\]

이를 통해 우리는 참여자들이 비밀 분할값과 평문을 처리할 때, 규칙을 어기는 참여자가 반드시 적발되도록 하는 방안을 마련할 수 있습니다! 물론, 여기서는 프로토콜의 일부만 소개하고 있습니다. 전체 개요를 확인하시려면 이 프로토콜이 처음 소개된 훌륭한 [BDOZ11] 논문을 읽어보시기를 권합니다. 또한, 발신자와 수신자는 서로의 값을 알지 못한 채 어떻게 안전하게 MAC과 키를 생성할까요? 이 모든 비밀은 '오프라인 단계' 섹션에서 공개하겠습니다!

BDOZ에서 Cerberus로

원래 BDOZ 온라인 단계는 복잡한 산술 연산이 필요 없어 이미 매우 효율적이지만, 저희는 자체 개발한 Cerberus 프로토콜을 통해 이를 다양한 방식으로 확장하고 개선했습니다.

지금까지는 단일 소수 체 위에서의 연산에 대해서만 다루었습니다. 하지만 Cerberus는 하나의 회로 내에서 임의의 수의 소수 체가 공존할 수 있도록 허용하며, 이들 간 변환을 가능하게 하는 이진 백엔드를 추가합니다. 또한, 타원 곡선(EC) 점에 대한 회로를 허용합니다. 이는 EC 점에 대한 로컬 프로토콜(예: 많은 제로 지식 증명 방식)이 EC 산술을 에뮬레이트할 필요 없이 다자간 환경에서 네이티브로 실행될 수 있음을 의미합니다(이를 소위 coSNARK라고 합니다). 이를 통해 우리는 많은 암호 프로토콜을 추가적인 오버헤드 없이 손쉽게 MPC 환경으로 이식할 수 있었으며, 지금까지 ElGamal 암호화와 Bulletproofs 등이 그 예입니다.

또한, 많은 연산 작업을 효율적으로 묶어 처리할 수 있어 계산 비용과 통신 부하를 모두 줄일 수 있습니다. 예를 들어, \( M \)개의 인증된 비밀 분할을 상대방에게 전송해야 한다고 가정해 봅시다. 각 비밀 분할마다 MAC을 하나씩 전송하는 대신, 전체 묶음을 인증하는 단일 MAC을 전송하면 됩니다. 이는 다음과 같은 방식으로 피아트-샤미르 변환(Fiat-Shamir transform)을 사용하여 수행할 수 있습니다:

1. 발신자는^{공유된 트랜스크립트1에} 자신의 값을 추가하면, 이를 통해 시드 \( s \)가 생성됩니다. \( s \)를 사용하여 난수 생성기(RNG)가 초기화됩니다.
2. 사용 중인 난수 생성기(RNG)를 사용하여 \( M \)개의 난수 \( \{ r_0, ..., r_{M-1} \} \)을 생성하십시오.
3. Sender computes the batched MAC by doing a random linear combination: $\mathrm{MAC}(\lbrace x_i \rbrace_{i < M}) = \sum_i \mathrm{MAC}(x_i)\, r_i$
4. Receiver performs a batched check, i.e. she checks that $\sum_i r_i (\alpha x_i + \beta_i) = \mathrm{MAC}(\lbrace x_i \rbrace_{i < M})$, which is equal to the batched MAC she received.

점근적으로 볼 때, 이는 일반적인 BDOZ 구현에 비해 대역폭 사용량을 사실상 절반으로 줄여줍니다. 또한, 우리는 멀티캐스트(multicast)라고 불리는 잘 알려지지 않은 네트워크 기본 요소를 활용합니다. 멀티캐스트를 사용하면 피어가 데이터를 \( N \)번 재전송할 필요 없이, \( N \)개의 수신자 그룹에 데이터를 브로드캐스트할 수 있습니다. 이를 통해 전체 대역폭 요구량이 \( \mathcal{O}(N^2) \)에서 훨씬 관리하기 쉬운 \( \mathcal{O}(N) \) 수준으로 감소합니다.

또한, 기존 BDOZ는 ‘중단 시에만 안전한(secure-with-abort)’ 방식(즉, 부정행위를 목격한 당사자는 프로토콜을 중단할 수는 있지만, 누가 부정행위를 저질렀는지 다른 당사자들에게 증명할 수는 없음)인 반면, Cerberus는 ‘공개적으로 식별 가능한 중단(PID-abort)’ 기능을 통합할 계획입니다. 이 시나리오에서는 부정행위를 목격한 당사자가 외부에서 검증 가능한 증명을 생성할 수 있게 되어, 누구나 해당 당사자가 올바르게 중단했는지 확인하고 부정행위를 한 당사자를 식별할 수 있게 됩니다. 이는 [BMRS24]의 컴파일러를 사용하여 수행되며, 향후 발표될 문서를 통해 더 자세히 설명될 예정입니다.

All these improvements bring down bandwidth usage significantly, which is one of the main bottlenecks of MPC. The other, latency, is mostly tied to how far apart the parties are from each other. However, since Arcium’s decentralization is guaranteed by the network itself, the computing parties do not need to be geographically far apart, which greatly mitigates these problems: this allows us to easily assume <5ms of latency while preserving trustlessness.

‍

각주:

¹: 피아트-샤미르 변환이 모두 그렇듯이 이 과정에는 어느 정도 주의가 필요하며, 보안을 보장하기 위해 모든 공개 매개변수를 포함하고 적절한 영역 분리를 확실히 적용합니다.