The Consensus Number of Untraceable Cryptocurrencies

거대한 디지털 강탈 사건: 눈앞에서 숨기

모두가 비밀을 속삭이고 있는 붐비는 방 안에 있다고 상상해 보십시오. 암호화폐의 디지털 세계에서 이 방은 누가 누구에게 돈을 보냈는지 기록하는 거대한 공공 노트인 "원장(ledger)"입니다. 보통 이 노트는 유리 벽과 같아서, 비록 실제 이름은 모르더라도 누가 누구에게 지불했는지를 정확히 볼 수 있습니다. 하지만 만약 당신이 군중 속의 '어떤 사람'이 실제로 현금을 건넸는지 아무도 모르게 결제를 하고 싶다면 어떻게 될까요? 이것이 바로 "송신자 추적 불가능성(sender untraceability)"이라는 과제입니다.

이를 해결하기 위해 암호학자들은 "마스킹 세트(masking set)"라는 기술을 사용합니다. 당신이 결제하는 사람이라고 가정하되, 열 명의 친구들과 함께 서 있다고 상상해 보십시오. 여러분 모두는 똑같이 생긴 봉투를 들고 있습니다. 외부 관찰자에게는 열 명의 친구 중 누구라도 결제했을 수도 있는 것처럼 보이지만, 그들은 정확히 누구인지 알 수 없습니다. 우리가 살펴보고 있는 논문은 이러한 그룹의 메커니즘을 깊이 파고듭니다. 이 논문은 매우 구체적이고 거의 철학적인 질문을 던집니다. 만약 우리가 그룹 안에 송신자를 숨기고자 한다면, 그 숨기는 행위가 그룹의 작동 방식까지 변화시키는가? 구체적으로, 그것이 그룹이 다음에 일어날 일에 대해 합의하는 것을 더 어렵게 만드는가? 저자들은 "합의 수(consensus number)"라는, 협력을 위해 얼마나 많은 조정이 필요한지를 측정하는 세련된 방식을 조사하고 있습니다. 이것을 "교통 체증 측정기"라고 생각하십시오. 숫자가 낮으면 차들이 서로 쉽게 지나갈 수 있다는 뜻이고, 숫자가 높으면 차들이 멈춰 서서 기다리며 누가 먼저 갈지 논쟁해야 한다는 뜻입니다.

두 가지 은닉 방법: "전부 유지하기" vs "전부 바꾸기"

이 논문은 송신자를 숨기기 위한 이러한 친구 그룹(마스킹 세트)을 관리하는 두 가지 서로 다른 전략을 비교합니다. 이들을 각각 **선형 전략(Linear Strategy)**과 **상수 전략(Constant Strategy)**이라고 부르겠습니다.

선형 전략 (LUAT): 끝없이 늘어나는 초대 명단
누군가 결제할 때마다 단순히 그룹 속에 숨는 것이 아니라, 벽에 "이 그룹 중 누군가가 결제했다!"라는 영구적인 메모를 남기는 파티를 상상해 보십시오. 이 파티는 이 메모들을 절대 삭제하지 않습니다. "잠재적 결제자(allow-set)"의 목록은 계속 늘어나고, "이미 결제한 사람(deny-set)"의 목록도 계속 늘어납니다.

• 좋은 소식: 이 방법은 놀라울 정도로 여유롭습니다. 목록이 거대해지더라도 "교통 체증 측정기"는 매우 낮은 수준을 유지합니다. 저자들은 그룹의 규모가 아무리 커지더라도 시스템이 한 번에 단 2명만을 위해 조정될 필요가 있다는 것을 증명했습니다. 이는 마치 모든 사람이 자유롭게 움직일 수 있는 댄스 플로어와 같습니다. 누군가와 부딪히더라도 누가 먼저 움직였는지 알아내기 위해 파티 전체를 중단시킬 필요는 없습니다.
• 문제점: 파티 벽은 영원히 포스트잇으로 뒤덮이게 됩니다. 결제했을 수도 있는 모든 사람을 기억하는 데 필요한 저장 공간은 모든 거래와 함께 선형적으로 증가합니다. 이는 마치 수년 전에 문을 통과했던 모든 사람을, 설령 그들이 떠난 지 오래되었더라도 기억하려고 애쓰는 것과 같습니다.

상수 전략 (CUAT): 마법 같은 재무작위화(Re-Randomization)
이제 다른 파티를 상상해 보십시오. 누군가 결제할 때, 그들은 단순히 메모를 남기는 데 그치지 않습니다. 대신, 친구 그룹 전체가 즉시 옷을 갈 바꾸고, 이름과 정체성을 바꿉니다. 기존의 그룹은 사라지고 완전히 새로운 그룹이 나타납니다. 이를 통해 방 안의 총 인원수를 일정하게 유지하므로 "벽"이 지저ک지 않게 됩니다. 이것이 Quisquis와 같은 시스템에서 사용하는 방식입니다.

• 문제점: 여기서 혼란이 발생합니다. 그룹 전체가 바뀌기 때문에, 만약 두 사람이 동시에 결제를 시도하고 그들의 그룹이 겹친다면(단 한 명이라도 공통된 사람이 있다면), 그들은 충돌하게 됩니다. 두 사람 모두 성공할 수 없습니다.
• 결과: "교통 체증 측정기"가 폭발합니다. 저자들은 여기서 필요한 조정량이 그룹 크기에 따라 **이차 함수적(quadratically)**으로 증가한다는 것을 발견했습니다. 그룹에 10명이 있다면, 필요한 조정량은 대략 100입니다. 100명이 있다면, 10,000의 조정이 필요합니다! 이는 마치 의자 뺏기 게임과 같아서, 두 그룹이 단 하나의 의자라도 공유한다면 게임 전체를 멈추고 누가 어디에 앉을지 다시 시작해야 하는 것과 같습니다.

프라이버시 vs 진보의 트레이드오프

이 논문의 가장 큰 발견은 엄격한 트레이드오프(절충 관계)입니다. 당신은 프라이버시를 가질 수 있지만, 그 대가로 두 가지 통화 중 하나를 지불해야 합니다. 바로 저장 공간 또는 동기화입니다.

1. 저장 공간으로 지불하기 (선형 전략): 역사를 영원히 유지합니다. 시스템은 빠르고 조율하기 쉽지만(합의 수 2), 하드 드라이브가 가득 차게 됩니다.
2. 동기화로 지불하기 (상수 전략): 역사를 작고 깔끔하게 유지합니다. 하지만 그렇게 하기 위해서, 시스템이 엄청나게 조율하도록 강요해야 합니다. 더 많은 사람 사이에 숨으려 할수록, 사람들이 사건의 순서에 합의하는 것은 더욱 어려워집니다.

저자들은 또한 **강력한 추적 불가능성(Strong Untraceability)**이라는 "초-프라이버시" 모드도 살펴보았습니다. 이것은 파티의 단 한 순간만이 아니라 전체 역사를 지켜보는 탐정이 있는 것과 같습니다. 저자들은 만약 장기간의 역사 동안 송신자를 완벽하게 숨기고 싶다면, 친구 그룹들이 매우 특정한 수학적 패턴(예: 완벽한 격자나 사영 평면)으로 배치되어야 한다는 점을 발견했습니다. 만약 이들을 완벽하게 배치하지 않는다면, 탐정은 너무 많은 그룹에 등장하는 사람을 보고 누가 결제했는지 추측할 수 있습니다. 이러한 완벽한 배치를 강제하면, "교통 체집 측정기"는 그룹 크기에 기반한 특정하고 높은 천장에 도달하게 됩니다.

기아 문제 (The Starvation Problem): 평균 스케줄러

마지막으로, 이 논문은 상수 전략의 어두운 면인 기아(Starvation) 문제를 다룹니다.
파티에서 음악을 제어하는 불량배("적대적 스케줄러")가 있다고 상상해 보십시오. 선형 전략에서는 당신이 결제할 준비가 되었다면, 불량배가 당신을 막으려 하더라도 결국에는 결제할 수 있습니다. 하지만 상수 전략에서는 그룹 전체가 바뀌기 때문에, 불량배가 당신의 특정 그룹에 대해 계속해서 "리셋" 버튼을 누를 수 있습니다.
저자들은 상수 전략에서 불량-스케줄러가 한 사람은 영원히 결제하게 만들면서, 다른 한 사람은 영원히 기다리게 만들 수 있음을 증명했습니다. 기다리는 사람이 돈도 있고 결제할 준비도 되어 있음에도 불구하고 말입니다. 기다리는 사람은 계속 시도하지만, 그가 완료하기 직전에 불량배가 그룹을 리셋해 버립니다. 이것은 시스템이 상태를 작게 유지하도록 설계되어 있다면 수학적으로 방지할 수 없는 "서비스 거부(denial of service)"입니다.

결론

이 논문은 단순히 "어느 하나가 더 낫다"라고 말하는 것이 아닙니다. 그것은 당신의 선택에 따른 정확한 비용을 지도화합니다.

• 만약 당신이 공간이 부족해지지 않고 모두에게 공평한 시스템을 원한다면, 과거의 거래 목록이 영원히 늘어나는 것을 받아들여야 합니다 (선형).
• 만약 당신이 작고 깔끔한 역사를 유지하고 싶다면, 더 많은 사람을 추가함에 따라 조율이 믿기 힘들 정도로 느려지고 복잡해지며, 일부 사용자를 굶주리게(starve) 만들 수 있다는 점을 받아들여야 합니다 (상수).

저자들은 수학적 확실성을 가지고 이러한 한계들을 증명했습니다. 그들은 당신이 두 마리 토가 토끼를 잡을 수 없음을 보여주었습니다. 즉, 작고 깔한 역사와 빠르고 공정하며 조율하기 쉬운 시스템을 동시에 가질 수는 없습니다. 암호화폐의 세계는 프라이버시를 위해 대가를 요구하며, 이 논문은 당신이 정확히 얼마를 지불해야 하는지를 알려줍니다.