불릿프루프 (Bulletproofs)

불릿프루프(Bulletproofs)는 2018년 베네딕트 뷘츠(Benedikt Bünz), 조너선 부틀, 댄 보네, 앤드루 포엘스트라, 피터 위일, 그레그 맥스웰이 발표한 영지식 증명 체계입니다. 신뢰 설정 없이 이산 로그 가정만으로 짧은 증명을 만들 수 있고, 특히 '숨겨진 금액이 0 이상 2⁶⁴ 미만'처럼 값이 범위 안에 있음을 보이는 범위 증명(range proof)에 많이 쓰입니다.

자세히 알아보기

비밀 거래에서는 금액을 페더슨 커밋먼트로 숨기는데, 이때 음수 금액을 넣어 돈을 무에서 만들어 내는 공격을 막아야 합니다. 범위 증명이 바로 그 역할을 합니다. 불릿프루프는 내적 논증(inner product argument)을 재귀적으로 반씩 접는 방식으로, 증명 크기를 비트 수에 대해 로그 크기로 줄였습니다. 64비트 범위 증명은 약 수백 바이트 수준이며, 여러 범위 증명을 합치면 크기가 거의 늘지 않습니다.

장점은 신뢰 설정이 없고 표준적인 타원곡선만 있으면 된다는 점입니다. 단점은 검증 시간이 증명하는 명제 크기에 선형으로 늘어난다는 것입니다. 그래서 범위 증명처럼 작은 명제에는 매우 효율적이지만, 큰 범용 계산에는 SNARK나 STARK가 더 적합합니다. 또한 이산 로그에 기반하므로 양자 컴퓨터에는 안전하지 않습니다. 2020년에는 한국 연구진(Heewon Chung, Jae Hong Seo 등)이 증명을 더 줄인 Bulletproofs+를 발표했습니다. 64비트 범위 증명 기준으로 약 672바이트가 576바이트로 줄었습니다.

불릿프루프는 피아트-샤미르 변환으로 비대화형이 됩니다. 검증 비용은 선형이지만 여러 증명을 묶어 일괄 검증하면 다중 스칼라 곱셈을 공유할 수 있어, 블록 전체의 범위 증명을 한꺼번에 확인할 때 비용이 크게 줄어듭니다.

블록체인·암호화폐에서는

Monero는 2018년 10월 불릿프루프를 도입해 트랜잭션 크기와 수수료를 크게 줄였고, 2022년 8월 하드포크에서 Bulletproofs+로 교체했습니다. Grin, Beam 같은 Mimblewimble 기반 코인도 범위 증명에 불릿프루프를 사용합니다. 이런 프라이버시 코인은 금액이 공개되지 않기 때문에, USDT처럼 금액과 주소가 공개된 토큰과 달리 블록 탐색기에서 이체 금액을 확인할 수 없습니다.

쉽게 말하면

봉투 속 금액을 보여 주지 않고도 '이 봉투에는 0원 이상, 한도 이하의 돈이 들어 있다'는 것을 증명하는 방법입니다.

예시

Monero 트랜잭션의 출력 금액 v는 페더슨 커밋먼트 C = v·G + r·H로 숨겨지고, 불릿프루프는 0 ≤ v < 2⁶⁴임을 증명합니다. 출력이 여러 개라면 범위 증명을 하나로 묶을 수 있으며, 출력 수가 두 배가 되어도 증명 크기는 군 원소 두 개 정도만 늘어납니다.