2015년, 우리는 Elements의 주요 기능인 기밀 거래를 발표했습니다. 이 기능을 통해 거래 금액은 페데르센 커밋먼트(Pedersen commitments)로 대체되었습니다. 거래 금액을 숨기는 암호화 도구인 페데르센 커밋먼트를 사용하면 누구나 모든 특정 거래 내에서 거래 금액이 균형을 이루고 있는지 검증할 수 있습니다.
기밀 거래의 가장 큰 단점은 거래가 검증하기엔 매우 크고 느렸다는 것입니다. 각 거래 출력에는 금액이 오버플로우하기에는 너무 작다는 것을 증명하는 영지식 증명(zero-knowledge proof)의 한 종류인 범위 증명(rangeproof)이 포함되어 있어야 했기 때문입니다. 일반적인 디지털 서명은 100 바이트 미만이고 검증하는 데 100 마이크로 초도 걸리지 않는데 반해, 이러한 범위 증명은 용량이 수 킬로바이트였고 검증에 수 밀리 초가 소요됐습니다. 실제로, 범위 증명을 사용한 모든 거래에서 거래 데이터의 대부분을 차지하는 것은 범위 증명이었습니다.
보로메오 고리(Borromean ring) 서명을 기반으로 한 우리의 범위 증명은 문헌상 (필요했던 범위 크기에 비해, 신뢰 설정 없이) 가장 빠르고 가장 작았지만, 여전히 크기는 상당했습니다.
2015년부터 범위 증명의 효율을 개선하기 위한 연구가 진행되었습니다. 2017년 초, Adam Back은 범위 증명의 크기를 24% 줄였으나 검증 성능의 개선은 이루어지지 않았습니다. 우리는 이 때쯤 스탠포드에 근무하는 친구이자 동료 암호학자인 Dan Boneh와 Benedikt Bünz에게 이 문제를 언급했는데, 이 두 사람은 개선의 여지가 있다고 확신했습니다.
그리고 마침내 놀라운 결과물을 내놓았습니다.
더 작고, 더 빠르고, 더 강력한
2016년 Bootle 외가 이산로그 기반의 영지식 증명의 공간 효율을 개선하면서, Bulletproof는 훨씬 공간 효율적인 형식의 영지식 증명으로 거듭났습니다. 이 증명은 특히 우리의 목적에 맞게 페데르센 커밋먼트 같은 커밋된 값과 공개 키를 기본적으로 지원합니다. 이를 통해, 영지식에 타원 곡선 연산의 복잡한 절차를 구현하지 않고도 이 종합적인 영지식 프레임워크에 범위 증명 같은 것을 구현할 수 있습니다.
더 강력한 기능. 거래의 크기를 제한하기 위해 기존의 범위 증명은 출력 크기의 범위를 2^32로 제한했습니다. 이는 출력을 약 43 BTC로 제한했지만, 증명의 세분성(granularity)을 1 사토시(satoshi)에서 10 또는 100으로 줄이거나 최소값을 0 보다 크게 높임으로써 이를 증가시킬 수 있었습니다. 이렇게 조정은 가능했지만, 명시적인 금액을 사용하여 시스템에서 제공되는 개인정보 보호를 제한했습니다.
이러한 32 비트의 범위 증명의 크기는 약 2.5 KiB였습니다. Adam의 최적화를 사용하면 2 KiB로 줄어들 수 있었습니다. Bulletproof를 사용하면 610 바이트까지 줄어들 수도 있었습니다. 이렇게 작은 크기를 사용하면 범위를 64 비트로 두 배 늘릴 수 있으므로 비기밀 조정의 필요성이 없어집니다. 그러면 겨우 610 바이트였던 크기가 1220으로 늘어날 것입니다. 그럴까요? 아닙니다. 사실, 64 비트 Bulletproof 범위 증명은 674 바이트에 불과합니다.
더 작은 크기. 증명 크기에 단지 64 바이트만 추가하면서 범위 크기를 두 배로 늘릴 수 있는 이유는 두 크기가 로그적으로 증가하기 때문입니다. Bootle 외의 2016년 논문에서는 이를 내적 독립 변수의 변량을 사용하여 수행합니다 (Jonathan Bootle 또한 Benedikt와 Dan이 Bulletproof를 개발하는 데 기여했습니다). 구체적으로 보자면, 이 논문에 기술된 로그적으로 변하는 내적 독립 변수는 Bulletproof에서 6 log(N) 곡선점에서 2 log(N)로 훨씬 더 줄었습니다.
같은 방식으로, 한 거래의 여러 개의 범위 증명을 하나로 집계할 수 있는데, 다시 말하지만 증가되는 크기는 작습니다. 범위 증명 두 개의 집합은 738 바이트, 네 개는 802 바이트, 여덟 개는 866 바이트가 될 것입니다. 64 비트의 전형적인 범위 증명 여덟 개는 40000 바이트가 넘을 것입니다!
더 빠른 속도. 이렇게 차지 공간을 줄일 수 있다는 점은 훌륭하지만, 우리가 수행한 초기 기술 분석에 따르면 검증은 기존의 범위 증명보다 느릴 것입니다. 64 비트 증명 하나를 검증하는 데 200개 이상의 스칼라 점 곱셈이 필요한 것으로 나타났고 각 곱셈은 50 마이크로 초가 걸리는 번거로운 작업이었던 반면, 기존의 범위 증명은 128개의 곱셈 작업만 필요로 했습니다.
그러나 추가 분석 결과, 이 많은 곱셈들을 통합하여 총 곱셈 수를 147개로 줄일 수 있었습니다. 더 중요한 것은, 기존의 범위 증명과는 달리 이러한 곱셈들은 서로 종속적이지 않았고, 모든 곱셈을 하나의 큰 배치에서 수행할 수 있었습니다. 집합 서명에 대한 연구 덕분에, 우리는 배치 곱셈을 매우 빠르게 수행하는 방법을 알고 있었습니다. 저는 Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman와 함께 몇 달 동안 이 문제를 연구했고, 147개 곱셈의 각 속도를 15.5 마이크로 초로 줄임으로써 Bulletproof의 총 검증 시간을 기존의 증명에 소요되는 5.8 ms에서 2.3 ms로 줄였습니다.
이는 속도가 두 배 이상으로 증가한 것인데, 우리의 배치 곱셈은 더 많은 점(point)을 줄수록 빨라지기 때문에 집계의 성능 수치는 훨씬 더 좋아집니다. 64 비트 Bulletproof 여덟 개의 집합은 불과 10.7 ms만에 검증될 수 있어 46.5 ms가 소요되는 기존 증명에 비하면 4배 빠른 속도입니다.
그런데 성능은 이보다 더 좋아집니다. Bulletproof는 매우 효율적인 형태의 배치 검증을 지원합니다. 우리가 해야 할 147개의 곱셈 중 130개는 모든 Bulletproof에 대해 동일한 점을 사용합니다. 즉, 배치 검증 과정에서 이 130개의 곱셈은 통합될 수 있어 17개의 새로운 곱셈만 남길 수 있는 것입니다. 실제로, 이러한 한계 비용은 로그적으로만 증가합니다: 범위 2개의 집합은 각 추가 증명에 19개의 점이 더 필요하고, 범위 4개의 집합은 21개의 점이 필요합니다.
지금까지 비슷하지만 다른 두 개의 개념을 소개했습니다: 집계는 증명자가 여러 개의 범위 증명을 하나로 통합하는 경우인 반면, 배칭(batching)은 검증자가 여러 개의 개별 증명을 한 번에 확인하는 경우입니다.
이는 64 비트 범위 증명 두 개가 2.7 ms 미만 동안, 즉 범위 당 1.3 ms 동안 검증될 수 있다는 것을 의미합니다. 범위 증명 천 개는 239 ms, 즉 범위 당 0.24 ms 동안 검증될 수 있는데, 이는 기존 증명보다 23배 개선된 것입니다. 그러나 이러한 결과는 집계를 통해 더욱 개선됩니다. 8배 집합 천 개(즉, 총 8000개의 범위)는 588 ms, 즉 범위 당 74 마이크로 초 동안 검증될 수 있는데, 이는 기존 범위 증명에 비해 78배 개선된 수치입니다.
이러한 효과는 점점 효율이 높아지는 스칼라 점 곱셈이 우세 효과를 멈추는 약 64개 증명의 집합에서 마침내 최고조에 달합니다. 이 시점에서 범위 당 49 마이크로 초(120jj 개선) 내로 배치 검증을 할 수 있습니다. 참고로, 타원 곡선 디지털 서명 알고리즘(Elliptic Curve Digital Signature Algorithm) 서명은 약 49 마이크로 초가 걸리기 때문에 이 수준의 집계에서 범위 증명은 거래 검증의 주요한 부분도 아닙니다. 물론, 블록체인에서 64 출력 거래가 많이 이루어질 가능성은 낮지만, Provisions 같은 비블록체인 환경에서 이런 속도는 확실히 가능합니다.
또한, 이 검증은 메모리 효율적이고, 하나의 범위 증명을 검증하는 데 100 KiB 미만이 소요되며, 크기는 선형으로 변합니다.
무엇이든 (사실이라면) 증명할 수 있습니다
Bulletproof는 범위 증명보다 훨씬 일반적입니다. 영지식에서 Bulletproof는 임의의 진술을 증명하는 데 사용될 수 있습니다. Bulletproof의 효과는 SNARKs나 STARKs와 동일하지만, 타원 곡선 공개 키와 페데르센 커밋먼트를 기본적으로 지원합니다 (따라서 증명된 프로그램 내에서 타원 곡선 수학을 구현할 필요가 없습니다). 또한, SNARKs와는 달리 신뢰 설정 없이 표준 가정하에 완전한 128 비트 보안을 갖습니다. 그리고 STARKs와는 달리 일반적인 컴퓨팅 하드웨어에서 합리적인 크기의 문제를 증명하고 검증할 수 있을 정도로 빠릅니다.
구체적인 예를 들자면, SHA2 압축 함수의 단일 실행이 있습니다. 우리 증명자는 SHA2 원상(preimage)에 대한 지식을 증명하는 데 30 MiB 미만의 메모리와 약 13초의 시간을 필요로 합니다. 검증에는 약 23 MiB의 메모리와 435 ms가 필요하지만, 우리는 추가 증명을 각각 약 28 ms와 13.4 KiB 내로 배치 검증할 수 있습니다. 결과 증명은 1379 바이트에 불과합니다.
우리의 증명자는 SNARKs의 증명자보다 메모리 효율이 뛰어납니다: 동일한 시스템에서 SHA2에 대한 SNARK 증명은 4초밖에 걸리지 않지만 75 MiB의 메모리가 필요합니다. 검증에는 각 회로(증명되어야 할 진술의 설명)에 대해 대규모의 일회성 사전 컴퓨팅이 필요하지만, 검증 시간은 3~5 ms에 불과하고 메모리가 거의 필요하지 않습니다. 이러한 수치는 회로의 크기에 따라 증가하지 않기 때문에, 수천 개 이상의 게이트에서 SNARKs는 우리의 배치 검증과 비교해 봤을 때도 확실히 우수합니다. 안타깝게도, 이를 위해 신뢰 설정과 새로운 암호화 가정은 희생해야 합니다.
증명자와 검증자 모두에서 Bulletproof를 더욱 최적화할 수 있는 여지는 충분히 남아있습니다.
Bulletproof 또는 SNARKs, STARKs에 의한 임의의 진술을 증명할 수 있는 이러한 기능은 여러 가지로 응용될 수 있습니다. (추적 가능한) 고리 서명, 임계값 서명 등 일반적인 디지털 서명을 구현하는 데 사용될 수 있는데, 고리가 큰 경우 검증 시간과 증명 크기 모두 기존의 체계보다 더욱 효율적일 수 있습니다. 응용 분야는 이뿐만이 아닙니다. 스도쿠 문제를 무신뢰 판매하는 데 사용될 수도 있습니다. 다자간 계산에도 사용되어 비밀 데이터를 갖고 있더라도 각 당사자가 정직하게 행동하고 있다는 것을 증명할 수 있습니다. (특히 MuSig 같은 다중 서명 체계에서 서명인들의 상태 유지나 논스 재사용 공격에 대한 저항력을 요구하지 않고도 결정론적인 논스를 생성할 수 있습니다.) 해시 원상을 증명하는 데 사용될 수도 있습니다.
해시 원상에 대한 응용이 특히 흥미로운데, (수백만 또는 수십억 개의 요소가 있는) 거대한 세트 내 포용의 효율적인 증명인 영지식 머클 증명(Merkle proofs)을 만드는 데 활용할 수 있기 때문입니다. 더 자세한 내용은 향후 게시물에서 다룰 것입니다.
결론
● Bulletproof는 (SNARKs 같은) 종합적인 영지식 증명
● Bulletproof는 다중 서명 또는 영지식 불확정 지급(Zero-Knowledge Contingent Payments) 같은 다자간 프로토콜을 확장하는 데 사용될 수 있음
● Bulletproof는 훨씬 효율적인 버전의 기밀 거래 범위 증명을 제공 (배치 검증 시 속도는 23배 이상 증가)
● 이러한 범위 증명은 로그 크기만 증가한 거래 내에서 집계 가능
● 배치 검증은 Provisions에서와 같이 충분한 집계를 통해 기존의 증명보다 120배 이상 빨라짐
이 모든 연구 결과를 이끌어낸 내적 독립 변수를 개발한 Bootle 외, 진보적 연구를 수행한 우리의 공동 저자인 Benedikt Bünz와 Dan Boneh님께 감사의 말씀을 전합니다. 또한, 산술 회로 최적화에 대한 연구를 이끈 Sean Bowe와 Daira Hopwood님께도 감사 드립니다.
모든 계산은 2.70GHz에서 Intel i7-6820HQ CPU의 싱글 코어로 수행되었습니다.
링크
● 전체 논문