Mitigating Collusion in Proofs of Liabilities

이 논문은 사용자가 협력하지 않아도 부정한 거래소 운영자를 탐지할 수 있도록 허가된 벡터 약속 (PVC) 과 KZG/BLS 암호 기술을 결합한 새로운 '허가형 증명 (Permissioned PoL)' 모델을 제안하여, 기존 증명 방식의 결함을 해결하고 서버 성능을 최대 10 배까지 향상시켰음을 보여줍니다.

핵심

1. 배경: "은행장"과 "고객"의 신뢰 게임

상상해 보세요. 거대한 **금고 (거래소)**가 있습니다. 수만 명의 고객이 금고에 돈을 맡겼고, 금고를 관리하는 **은행장 (거래소 운영자)**이 있습니다.

고객들은 은행장이 "내 돈은 다 있어요"라고 말만 믿고 싶지 않습니다. 그래서 은행장은 매달 **"책임 증명서 (Proof of Liabilities, PoL)"**를 공개합니다. 이 증명서에는 "모든 고객의 잔고 합계는 X 원입니다"라고 적혀 있어야 합니다.

기존 방식의 문제점: "모두가 감시해야 하는 고단함"
지금까지의 방식은 다음과 같았습니다:

• 은행장이 증명서를 발표하면, 모든 고객이 직접 "내 이름과 잔고가 이 목록에 정확히 들어있나?"를 하나하나 확인해야 했습니다.
• 문제 1 (지루함): 고객이 수백만 명인데, 모두 매번 확인하는 건 불가능에 가깝습니다.
• 문제 2 (합작의 위험): 이것이 가장 큰 치명적인 약점입니다.
  • 상황: 은행장이 자금이 부족해서 파산할 위기에 처했다고 칩시다.
  • 사기극: 은행장은 **특정 고객 (가령 '앨리스')**과 비밀리에 거래를 합니다. "앨리스야, 너의 잔고를 증명서에 '0 원'으로 적어줄게. 대신 너는 내 돈을 빼돌릴 때 먼저 빼가게 해주고, 이자도 더 줄게."
  • 결과: 앨리스는 자신의 잔고가 0 으로 줄어든 것을 확인하지 않거나 (혹은 확인하고도 묵인하고), 은행장은 전체 부채를 줄여서 "파산 안 함" 척합니다.
  • 결론: 앨리스는 이득을 보고, 은행장은 파산을 모면합니다. 하지만 진짜 피해자는 나머지 정직한 고객들입니다. 기존 시스템은 이런 '내부자 합작'을 막을 수 없었습니다.

---

2. 이 논문의 해결책: "허가증 (Permission) 이 있는 금고"

이 논문은 **"고객이 매번 확인하지 않아도, 은행장이 함부로 돈을 조작할 수 없게 만드는 시스템"**을 제안합니다. 이를 **'허가된 책임 증명 (Permissioned PoL)'**이라고 부릅니다.

핵심 아이디어: "서명 없는 변경은 불가능하다"
기존 시스템은 "고객이 확인해야만 조작이 들통난다"면, 이 시스템은 **"고객이 서명 (허가) 하지 않은 변경은 아예 기술적으로 불가능하다"**는 원리입니다.

🏪 비유: "자동화 된 은행 창구"

이 시스템을 자동화 된 은행 창구로 비유해 볼까요?

1. 기존 방식 (수동 확인):

   • 은행장이 장부를 바꿉니다.
   • 고객들은 "내 이름이 있나?"라고 창구 앞에 줄을 서서 확인해야 합니다.
   • 은행장이 "앨리스는 0 원이야"라고 적어놨을 때, 앨리스가 확인하러 오지 않으면 그 거짓말은 영원히 숨겨집니다.

2. 새로운 방식 (허가된 시스템 - PPoL):

   • 은행장에게 장부를 수정할 권한이 없습니다. 오직 **고객의 전자 서명 (디지털 도장)**이 있어야만 수정이 가능합니다.
   • 은행장이 "앨리스의 잔고를 0 으로 줄여야겠다"고 생각한다고 칩시다.
   • 은행장은 앨리스에게 "서명해 줘"라고 요청해야 합니다.
   • 앨리스가 서명하지 않으면? 은행장은 기술적으로 그 숫자를 바꿀 수 없습니다. 시스템이 거절합니다.
   • 앨리스가 서명했다면? 그건 더 이상 은행장의 사기가 아니라, 앨리스가 자발적으로 돈을 인출하거나 양도한 것입니다.

결국, 은행장은 "앨리스가 서명하지 않은 채로 잔고를 조작할 수 없기 때문에", 합작을 하더라도 앨리스가 서명해야만 조작이 가능합니다. 앨리스가 서명하면, 그것은 더 이상 "은행장의 사기"가 아니라 "앨리스의 동의"가 되어, 은행장은 더 이상 파산 위기를 숨길 수 없게 됩니다.

---

3. 기술적 마법: "허가된 벡터 약속 (PVC)"

이 시스템을 가능하게 하는 기술적 핵심은 **'PVC(Permissioned Vector Commitment)'**라는 도구입니다.

• 비유: "디지털 도장과 암호화된 장부"
  • 은행장은 장부 (데이터) 를 암호화해서 공개합니다.
  • 하지만 이 장부에 어떤 숫자를 적으려면, 그 숫자의 주인 (고객) 이 **"이게 내 돈이야"라고 찍은 디지털 도장 (서명)**이 있어야만 장부에 반영됩니다.
  • 감시자 (감사관) 는 장부를 볼 필요 없이, **"이 장부에 적힌 모든 숫자는 고객들의 도장이 찍혀 있는가?"**만 확인하면 됩니다.
  • 도장이 없거나, 도장이 위조된 숫자가 있다면 감시자는 즉시 "이 장부는 가짜다"라고 선언할 수 있습니다.

이 방식의 가장 큰 장점은 고객이 매번 확인할 필요가 없다는 것입니다. 은행장이 함부로 숫자를 바꿀 수 없기 때문에, 고객은 "내 돈이 사라졌나?"라고 걱정하며 매번 확인할 필요가 없습니다. 은행장이 조작을 시도하면, 시스템이 자동으로 막아내기 때문입니다.

---

4. 성능: "더 안전하면서도 더 빠르다"

보통 보안이 강화되면 시스템이 느려지기 마련입니다. 하지만 이 논문은 놀라운 결과를 보여줍니다.

• 기존 방식: 2,000 명 정도의 고객 데이터를 처리하는 데 약 3 분 (180 초) 이 걸렸습니다.
• 새로운 방식: 같은 작업을 30 초 (10 배 빠름) 만에 처리했습니다.
• 이유: 기존 방식은 모든 고객의 데이터를 매번 처음부터 다시 계산해야 했지만, 이 새로운 방식은 변경된 부분만 효율적으로 업데이트하는 기술을 사용했기 때문입니다.

---

5. 요약: 왜 이것이 중요한가?

1. 합작 방지: 은행장과 특정 고객이 짜고 자산을 숨기는 '내부자 사기'를 원천 차단합니다.
2. 고객의 편의: 고객들은 매번 잔고를 확인하러 다니는 수고를 덜 수 있습니다. 시스템 자체가 조작을 막아주기 때문입니다.
3. 빠른 속도: 보안이 강화되었음에도 불구하고, 기존 시스템보다 10 배나 빠르게 작동합니다.

한 줄 요약:

"이 논문은 **'은행장이 고객 허락 없이 돈을 조작할 수 없는 금고'**를 만들어, 고객들이 안심하고 돈을 맡길 수 있게 하고, 동시에 은행장도 더 빠르고 효율적으로 일할 수 있게 해주는 혁신적인 시스템입니다."

이제 암호화폐 거래소가 "우리는 solvent(파산하지 않음) 입니다"라고 말할 때, 우리는 그 말에 훨씬 더 큰 신뢰를 가질 수 있게 될 것입니다.

기술 요약

1. 문제 정의 (Problem Statement)

현재 암호화폐 거래소 (CEX) 는 사용자의 신뢰를 확보하기 위해 부채 증명 (Proof of Liabilities, PoL) 을 제공합니다. 이는 거래소가 보유한 자산이 사용자의 예치금 (부채) 을 충분히 커버할 수 있음을 증명하는 과정입니다. 그러나 기존 PoL 설계에는 다음과 같은 치명적인 결함이 존재합니다.

• 사용자 - 제공자 공모 (Collusion) 공격의 취약성:
  • 기존 PoL 은 거래소 (공급자) 가 악의적으로 총 부채를 과소평가하는 것을 방지하기 위해 설계되었으나, 악의적인 공급자와 특정 사용자가 공모할 경우 탐지하지 못합니다.
  • OTB (Off-the-Books) 공격 시나리오: 거래소가 파산 위기에 처했을 때, 특정 사용자 (Alice) 와 공모하여 Alice 의 실제 잔고를 0 으로 조작하거나 누락시킵니다. 대신 Alice 는 거래소로부터 우대 혜택이나 우선 인출 권한을 받습니다.
  • 기존 시스템은 사용자가 자신의 잔고가 증명서에 포함되어 있는지 직접 확인해야만 부정을 탐지할 수 있습니다. Alice 가 확인을 거부하거나 "확인하는 것을 잊었다"고 주장하면, 거래소는 전체 부채를 줄여 solvent(파산하지 않음) 한 것처럼 보이게 할 수 있습니다. 이는 시스템 전체의 신뢰를 무너뜨립니다.
• 사용자 부담 및 확장성 문제:
  • 기존 방식은 모든 사용자가 매번 증명서를 확인해야 하거나, 최소한의 사용자만 무작위로 확인해야 한다는 가정에 의존합니다. 이는 사용자에게 부담을 주며, 공격자가 어떤 사용자가 확인할지 예측하거나 공모할 경우 보안 가정이 무너집니다.
  • 또한, 기존 증명 생성 (예: Notus, DAPOL+) 은 수백만 명의 사용자 데이터에 대해 증명 생성 시간이 길어 (수 분 소요) 실시간 대응이 어렵습니다.

2. 제안된 방법론 (Methodology)

저자들은 권한 부여된 부채 증명 (Permissioned PoL, PPoL) 이라는 새로운 모델을 제안하며, 이는 사용자의 협력 없이도 공급자의 부정을 탐지하고 예방할 수 있습니다.

핵심 원리: Permissioned Vector Commitment (PVC)

PPoL 의 핵심은 권한 부여된 벡터 커미트먼트 (PVC) 라는 새로운 암호학적 원시 (Primitive) 입니다.

• 개념: PVC 는 공급자가 관리하는 데이터베이스 (사용자 잔고) 가 오직 사용자가 명시적으로 서명한 값들만 포함하도록 보장합니다.
• 작동 방식:
  1. 사용자 서명: 사용자가 잔고 업데이트를 요청할 때, 해당 업데이트에 대해 개인 키로 서명합니다.
  2. 공급자 검증 및 커미트: 공급자는 이 서명을 검증하고, 서명된 업데이트만 데이터베이스에 반영하여 커미트먼트를 생성합니다.
  3. 감사 (Auditor) 검증: 감사는 공급자가 제출한 전역 증명 (Global Proof) 을 통해, 데이터베이스의 모든 업데이트가 해당 사용자의 서명이 없으면 불가능했음을 수학적으로 검증합니다.
  4. 결과: 만약 공급자가 Alice 의 잔고를 0 으로 조작하려 한다면, Alice 의 서명이 없으므로 감사가 이를 즉시 탐지합니다. 따라서 Alice 는 공급자와 공모하여 "확인하지 않음"을 주장할 수 없게 됩니다.

기술적 구현 (Cryptographic Construction)

PPoL 은 다음과 같은 암호학적 기법들을 효율적으로 결합하여 구현되었습니다.

• KZG 커미트먼트 (KZG Commitments): 벡터 데이터 (잔고 목록) 에 대한 효율적인 커미트먼트 및 오픈 증명 생성에 사용.
• BLS 기반 서명 및 APK (Aggregate Public Key) 증명: 여러 사용자의 서명을 하나로 집계하여 검증 효율성을 높임.
• Quotient-based Signature Aggregation: 서명 집계를 위한 새로운 몫 (Quotient) 기반 기법 도입.
• Append-only Proof: 사용자 키 목록 (S) 이 삭제되거나 변경되지 않고, 새로운 키만 추가됨을 보장하는 증명.
• Zero-Knowledge (영지식성): 사용자의 잔고 값은 공개되지 않도록 마스킹 (Masking) 기술을 적용하여 프라이버시를 보호합니다.

3. 주요 기여 (Key Contributions)

1. 기존 PoL 의 한계 분석: 현재 상용화 및 학술적 PoL 설계가 사용자 - 공급자 공모 (OTB 공격) 에 취약하며, 이로 인해 대규모 채택이 어렵다는 것을 규명했습니다.
2. PPoL 모델 제안: 사용자의 사전 확인 없이도 공급자의 부정을 방지할 수 있는 새로운 '권한 부여된 PoL' 모델을 정의했습니다.
3. PVC (Permissioned Vector Commitment) 도입: PKI(공개키 기반 구조) 통합을 명확히 캡처하는 새로운 추상화를 제시했습니다. 이는 PoL 외에도 다른 투명성 시스템에 적용 가능한 독립적인 원시입니다.
4. 효율적인 구현 및 최적화: KZG 커미트먼트와 BLS 서명을 결합하여, 강력한 보안성을 유지하면서도 기존 방식보다 최대 10 배 빠른 성능을 보이는 프로토타입을 구현했습니다.

4. 실험 결과 (Results)

저자들은 Go 언어로 프로토타입을 구현하고 (gnark-crypto 사용), 최신 PoL 솔루션 (DAPOL+, Notus, Xiezhi) 과 비교 평가했습니다.

• 성능 (Performance):
  • 증명 생성 속도: 2^16 (약 65,536) 명의 사용자가 있는 환경에서, PPoL 은 단일 코어 기준 약 4 초, 32 코어 병렬 처리 시 약 1 초 내에 전역 증명을 생성했습니다.
  • 비교: 기존 솔루션 (Notus, DAPOL+) 은 동일 환경에서 수백 초 (최대 1,000 초 이상) 가 소요되었습니다. PPoL 은 기존 방식 대비 최대 10 배 이상의 성능 향상을 보였습니다.
  • 처리량 (Throughput): PPoL 은 초당 300 건 이상의 잔고 업데이트를 처리할 수 있는 반면, 기존 방식은 훨씬 낮은 처리량을 보였습니다.
• 검증 시간:
  • 사용자 포함 증명 (Inclusion Proof) 및 감사 전역 증명 검증 시간은 모두 1 초 미만 (대부분 10~70ms) 으로 매우 빠릅니다.
• 확장성:
  • PPoL 은 업데이트가 필요한 사용자만 로그 (log) 복잡도로 처리하므로, 전체 사용자 수가 증가하더라도 성능 저하가 적습니다.

5. 의의 및 결론 (Significance & Conclusion)

이 논문은 암호화폐 거래소의 신뢰성 문제를 해결하는 데 있어 중요한 전환점을 제시합니다.

• 보안 패러다임의 변화: 기존 PoL 이 "사용자가 감시한다"는 수동적 모델에서, "시스템이 자동으로 권한을 통제한다" 는 능동적 모델로 전환했습니다. 이는 사용자가 항상 감시할 필요가 없게 하여 사용자 경험을 개선하면서도, 공모 공격을 근본적으로 차단합니다.
• 실용성: 강력한 보안 강화가 오히려 성능 저하를 초래한다는 통념을 깨고, 오히려 기존 방식보다 더 빠르고 확장성 있는 솔루션을 제시했습니다.
• 미래 영향: 제안된 PPoL 모델과 PVC 원시는 암호화폐 거래소뿐만 아니라, 중앙 집중형 데이터베이스의 투명성과 무결성을 검증해야 하는 다양한 투명성 시스템 (Transparency Systems) 에도 적용될 수 있는 잠재력을 가집니다.

요약하자면, 이 연구는 사용자 서명을 필수 조건으로 하는 암호학적 구조 (PVC) 를 통해 거래소와 사용자의 공모를 원천 차단하면서도, 고성능 증명 생성을 가능하게 함으로써 현실 세계의 암호화폐 거래소 감사에 실질적으로 적용 가능한 솔루션을 제시했습니다.