Pairing-based Cryptography와 BLS signature의 이해 — Part 3
우리는 Part 1과 Part 2를 거쳐서 Elliptic Curve Cryptography(이하 ECC)와 Pairing-based Cryptography (이하 PBC)의 중요한 개념을 살펴봤다.
Part 3은 이 개념들을 바탕으로 BLS signature가 가진 특징에 대해 살펴보고 최근 rogue attack 방지를 위한 개선된 내용을 설명한다. 그리고 BLS signature를 사용할 때 채택할 수 있는 옵션, 특히 G1과 G2의 용도에 대해 최근 이더리움 2.0에서 채택된 방법을 중심으로 기술하겠다.
다음으로는 zk-SNARKs에서 어떻게 PBC를 사용하는지 살펴볼텐데 zk-SNARKs의 전체 구성에 대해서 이해하고 있다면 더 좋겠지만 그렇지 않더라도 대강의 내용을 이해할 수 있도록 설명해 보겠다.
BLS signature 개요
BLS signature의 발명자(Dan Boneh, Ben Lynn, Hovav Shacham)들이 2001년 BLS signature를 처음 소개한 논문의 제목은 ‘Short signatures from the Weil pairing’이다.
이 논문은 BLS signature의 가장 큰 장점인 signature aggregation보다는 서명 데이터의 크기를 줄이는 새로운 서명 알고리즘을 제안하는 것이 목적이었다.
사용자가 서명 데이터를 수기로 입력하거나 low-bandwidth 통신 환경일 경우에는 서명 데이터의 사이즈를 축소시키는 것이 의미가 있었다. 이 논문에서 초기 발표된 내용은 G1과 G2가 같은 symmetric pairing을 기반으로 하고 Part 2의 [그림 3]에 나온 내용과 아주 유사하다. 그러나 이후에 나온 대부분의 연구는 G1과 G2가 다른 asymmetric pairing을 기준으로 한다.
이 내용은 지금도 의미가 있다고 볼 수 있는데 서명 데이터를 G1으로 표현하고 공개키를 G2로 표현할 경우 서명 데이터의 크기는 48bytes가 된다 (Part 2의 [그림 4] 참고). 그런데, ECDSA의 경우 서명은 32bytes 크기를 가지는 두 숫자(r, s)로 표현되므로 64bytes가 필요하다.
[그림 1]은 BLS signature의 알고리즘을 ECDSA와 비교해서 설명한다.
[그림 1] ECDSA와 BLS Signature의 알고리즘 비교
Part 2에서 설명한 서명 알고리즘과 다른 점은 G1에 서명을, G2에 공개키를 배치했다는 점이다 (위 논문에서 제시한 signature size를 줄이는 setup이다).
[그림 1]에서 보는 바와 같이 BLS signature는 G1, G2, GT, e(∙,∙) 등의 구성 요소가 ECDSA에 비해 복잡하고 많기는 하지만 서명과 검증 절차는 매우 간단하다. 특히 서명 방식이 매우 단순하기 때문에 뒤에서 나오는 signature aggregation이 가능해진다.
BLS signature가 장점만을 가지는 것은 아니다. 가장 큰 단점은 바로 속도가 느리다는 점이다.
현재 지속적으로 개선되고 있는 표준문서인 IETF draft에는 다음과 같은 문구가 있다.
“For 128 bits security, ECDSA takes 37 and 79 micro-seconds to sign and verify a signature on a typical laptop. In comparison, for the same level of security, BLS takes 370 and 2700 micro-seconds to sign and verify a signature.
In terms of sizes, ECDSA uses 32 bytes for public keys and 64 bytes for signatures; while BLS uses 96 bytes for public keys, and 48 bytes for signatures. Alternatively, BLS can also be instantiated with 48 bytes of public keys and 96 bytes of signatures. BLS also allows for signature aggregation. In other words, a single signature is sufficient to authenticate multiple messages and public keys.”
https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/?include_text=1
이 글을 보면 BLS signature는 ECDSA에 비해 서명(sign)은 10배의 시간이 걸리고, 검증(verification)에는 34배 이상의 시간이 걸린다.
[그림 2]는 ECDSA와 BLS signature의 key generation, sign, verify를 각각 1000회 실행했을 때의 소요 시간을 필자가 직접 측정한 결과를 보여준다.
[그림 2] ECDSA와 BLS signature의 벤치마킹 결과 — ECDSA는 golang standard library(P256 curve)를, BLS signature는 herumi C library(go-wrapper)를 이용함
A, B의 결과를 보면 golang과 C의 속도 차이, herumi 라이브러리의 pairing 속도 수준에 의해 IETF draft에서의 언급과는 다소 차이가 있으나 sign과 verify에서 BLS signature가 ECDSA에 비해 상당히 느린 것을 알 수 있다.
[그림 2]의 C, D가 가지는 의미는 아래 signature aggregation에서 다시 설명하겠다.
서명이 오래 걸리는 이유는 [그림 1]의 hashToG1 함수 때문이다. Part 2의 [그림 6]을 자세히 보면 Z_23의 모든 x 값에 대해 타원곡선 공식을 만족하는 y가 항상 존재하지는 않는다(예를 들면 1, 2, 3). hashToG1 함수는 먼저 메시지에 1을 붙이고(concatenation) hash 함수를 실행해서 x 값을 얻고 타원곡선 공식을 만족하는 y가 존재하면 (x, y)를 결과값으로 한다. 식을 만족하는 y 값이 없으면 메시지에 2를 붙여서 같은 행동을 반복한다. 이런 식으로 (x, y)가 발견될 때까지 진행하는데 hash 값으로 어떤 값이 나올지 예측할 수 없으므로 경우에 따라서는 여러 번 반복하는 일이 발생한다. 따라서 hashToG1의 속도가 저하될 수 있는데 이 부분은 속도를 개선하기 위한 다양한 시도들이 진행되고 있으며 성과를 보이고 있다.
그런데 보다 심각한 문제는 검증에 시간이 많이 걸린다는 것이다. 그 이유는 검증 시 ‘두 번 실행되는 pairing 함수’가 느리다는 것이다. 아무리 Millier’s algorithm을 극도로 개선한다고 해도 또 다른 breakthrough한 이론이 나오기 전까지는 optimal Ate pairing을 확실히 능가하는 대안이 출현하기는 쉽지 않을 듯하다.
따라서 BLS signature를 쓸 경우에는 이 pairing 함수의 실행을 최소화하는 데에 초점을 맞추게 된다.
Signature aggregation
이러한 성능상의 단점에도 불구하고 BLS signature를 빛나게 하는 큰 장점은 위 IETF draft 문구의 말미에 나와 있는 signature aggregation이다. Signature aggregation에 대해서는 위 논문의 저자들과 Craig Gentry가 공저한 2003년 논문에서 처음 소개된다.
주) Craig Gentry는 Dan Boneh 교수의 지도로 fully homomorphic encryption(동형암호)의 존재를 증명한 것으로 Stanford에서 박사학위를 받았고, zk-SNARKs의 초기 핵심 프로토콜이었던 Pinocchio Protocol을 공동 발명한 사람이다. 그리고 Harvard에서 J.D.를 받은 변호사이기도 하다. 공부에 대해서는 인류 최강 중 한명인 것 같다.
Signature aggregation이란 다수의 서명자가 각 자의 개인키로 각자의 message를 서명했을 때 모든 서명자의 공개키들을 합쳐서 일괄적으로 서명들을 검증하는 것이 가능하다는 것이다.
아래 [그림 3]은 N명의 서명자(signer)가 각자의 개인키로 서로 다른 메시지를 서명하고 검증자(verifier)가 N개의 서명을 합쳐서 서명하는 것을 보여준다.
[그림 3] Signature Aggregation 예시 (N명이 서로 다른 메시지를 서명할 경우)
한 서명을 검증하려면 두 번의 pairing 함수를 실행해야 했다. 그런데 [그림 3]에서와 같이 다수의 서명을 한 번에 검증할 경우 아래 식에 의해서 2N이 아닌 N+1번의 pairing 함수를 실행해서 N개의 서명을 검증하는 것이 가능하다. 조금 더 설명하면 N개의 검증 식들의 좌변과 우변을 각자 모두 곱한 후 좌변을 아래 식으로 줄이면 [그림 3]에서 보는 바와 같이 N+1개의 pairing 함수만 남게 된다.
e(sig_1, Q)∙e(sig_2, Q)∙…∙e(sig_N, Q) = e(∑sig_i, Q) = e(aggSig, Q)
aggSig는 N개의 서명을 합친 것이다.
주) 서명이 타원곡선 그룹의 원소, 즉 포인트이므로 여기에서 합친다는 말은 Part 1에서 설명한 Point Addition 연산을 말한다.
검증 처리해야 할 서명이 아주 많을 경우 배치 형태로 빠른 서명 검증이 가능하므로 훌륭한 기능이다. [그림 2]의 C를 보면 각각 서명하는 B에 비해 약 50%의 속도 개선이 이루어졌음을 알 수 있다.
그러나 BLS 서명 검증 시간이 약 절반으로 단축되었다 하더라도 아직은 ECDSA 대비 속도 측면에서는 상당히 느리다. [그림 2] A와 C의 Verify 소요 시간 차이를 보면 알 수 있다. 따라서 아직은 BLS signature를 쓰는 이유가 명확하지 않다.
그런데 만약 모든 서명자가 같은 메시지를 서명한다면 어떨까?
아래 [그림 4]과 같은 방식으로 signature aggregation을 실행할 경우 단 두 번의 pairing 함수 실행으로 N명의 서명을 한 번에 검증할 수 있다. [그림 3]의 설명에서 좌변의 pairing 함수 곱을 하나의 함수로 합칠 수 있었는데, 이번에는 우변의 함수들을 아래의 식으로 하나로 합칠 수 있다.
e(H, pk_1)∙e(H, pk_2)∙…∙e(H, pk_N) = e(H, ∑pk_i) = e(H, aggPK)
이 후 두 번의 pairing 함수 연산으로 e(aggSig, Q)와 e(H, aggPK)를 계산해서 두 계산값이 같으면 전체 서명이 모두 검증된다.
[그림 4] Signature Aggregation 예시 (N명이 같은 메시지를 서명할 경우)
만약 이게 가능하다면 IETF draft에 나온 성능을 기준으로 17명 이상의 서명을 한 번에 처리할 경우 ECDSA 대비 속도 개선 효과를 볼 수 있다는 얘기다. [그림 2]의 D를 보면 1000개 서명의 Verify에 2.16ms가 소요되었으므로 A의 ECDSA 연산에 비해서도 굉장히 빠르다. 추가로 소요되는 signature aggregation 연산(SignAgg)은 빠르게 실행되므로 이걸 감안하더라도 상당한 속도 개선이 가능하다. 이것이 BLS signature가 가지는 힘이다.
Rogue attack과 해결 방안
하지만 우리가 극복해야할 문제가 하나 있는데 바로 rogue attack이다. Rogue attach을 설명하기 위해 예를 들어보자. Alice와 Bob이 서명에 참여하고 Verifier인 Carol은 두 사람의 서명을 통합 검증한다. 이때 통신 구성 상의 이유로 Alice가 Bob에게 서명을 전달하고 Bob이 이를 통합해서 검증자인 Carol에게 전달하는 구성을 생각해보자. 이때 Carol은 사전에 두 사람의 공개키를 합쳐서 aggPK를 만들어 놓은 후에 Bob이 aggSig를 전달할 때마다 두 번의 pairing 함수를 써서 Alice와 Bob의 두 서명을 통합 검증하게 된다.
그런데 Bob이 Malicious User라고 가정해보자. 이때 [그림 5]와 같이 Alice는 자신의 공개키 pk1을 Carol에게 전달하고 Bob은 자신의 공개키pk2에서 Alice의 공개키 pk1을 뺀 pk2’을 자신의 공개키인 척하고 Carol에게 전달한다. Carol은 pk1과 pk2’을 합친 aggPK를 계산하는데 실제로는 Bob의 공개키인 pk2가 된다. 이후에는 Alice의 동의 없이 Bob이 단독으로 서명을 전달하고 이는 Alice와 Bob의 통합 서명인 것처럼 Carol의 검증을 통과하게 된다.
[그림 5] Rogue Attack 예시
이 과정을 실제 코드로 시뮬레이션해보면 [그림 6]과 같다.
[그림 6] Rogue Attack 시뮬레이션 코드 (golang, herumi library)
Rogue attach을 막기 위해 생각할 수 있는 가장 쉬운 방법은 모든 서명자의 메시지가 다를 경우와 마찬가지로 서명자 수 N에 대해 N+1의 pairing 함수를 실행하는 것이다 ([그림 3]과 동일). 하지만 이 경우 [그림 2]의 D와 같은 현격한 속도 개선 효과를 포기해야 한다.
Rogue attack 문제를 해결하면서 [그림 4]와 같은 통합 검증을 가능하게 하는 두 가지 방법이 제안되었다. 첫번째는 2007년 Thomas Ristenpart와 Scott Yilek가 제안한 proof-of-possession을 이용하는 방식으로 특정 주체(혹은 검증자)가 공개키 등록을 수행하는 registered key model을 사용한다. 각 서명자는 서명에 참여하기 전에 자신의 공개키를 제출하는 데 이때 공개키 데이터 자체를 개인키로 sign해서 서명을 같이 제출한다 (공개키의 서명을 proof-of-possession이라고 한다). [그림 5]에서 ECDLP에 의해 Bob은 조작된 공개키인 pk2’ (= pk2 — pk1)에 해당하는 개인키를 알 수 없고 따라서 pk2’에 대한 proof-of-possession을 만들 수 없다.
[그림 7]에서는 이 일련의 과정을 코드로 보여준다.
[그림 7] Proof-of-possession 시뮬레이션 코드 (golang, herumi library)
[그림 7]의 코드에 있는 proof-of-possession 생성(GetPop)과 검증(VerifyPop)은 IETF draft에 각각 PopProve, PopVerify라는 이름으로 표준 명세가 기술되어 있다. 실제 개발에서 BLS signature를 이용하기 위해서는 아래 링크에 공개되어 있는 IETF draft를 꼭 읽어 두기를 권한다.
참조 링크: https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/?include_text=1
Rogue attack을 방지하는 두 번째 방식은 BLS signature를 개발했던 Boneh 교수팀이 2018년에 제안한 방식으로 signature aggregation과 pubkey aggregation 시 서명 참여자별 ID를 적용하는 것이다. 두번째 방식을 간단하게 기술하자면 다음과 같다.
1) 서명 참여자 수가 N일 때 hash(pk_1, pk_2, …, pk_N) = (t_1, t_2, …, t_N) 형태로 N개의 ID를 산출한다. 이때 ID는 2¹²⁸ 보다 작은 크기를 가지고, hash 함수이므로 ID를 조작하거나 입력된 공개키(pk_i)를 역추적할 수 없다.
2) 공개키 결합 공식을 다음과 같이 조정한다: aggPK = ∑(t_i∙pk_i) (원래는 aggPK = ∑pk_i 이었음)
3) 서명 결합 공식을 다음과 같이 조정한다: aggSig = ∑(t_i∙sig_i) (원래는 aggSig = ∑sig_i 이었음)
이외의 key gen, sign, verify 알고리즘들은 BLS signature의 기본 알고리즘을 동일하게 수행한다.
이에 대한 자세한 설명은 원 저자들이 요약한 아래 링크를 참고하자 (사실 시간이 있다면 이분들의 원 논문을 천천히 읽어보는 것을 권한다).
https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html
조금 더 쉬운 설명을 원한다면 아래 링크를 참고하라.
https://medium.com/cryptoadvance/bls-signatures-better-than-schnorr-5a7fe30ea716
두 방식 중 어느 방식을 쓰더라도 동일한 메시지를 다수가 서명할 경우 [그림 2]의 D와 같은 극적인 성능 개선 효과를 보면서 rogue attack을 방지할 수 있다.
첫번째 방식이 더 간결하고 BLS signature의 기본 라이브러리를 그대로 쓸 수 있기 때문에 개발자 입장에서도 복잡성이 낮다고 볼 수 있다. 단점이라면 전체 서명자가 처음 한번은 공개키와 함께 proof-of-possession을 제출하고 검증자가 하나씩 검증하는 절차가 필요하다는 것이다.
정리하자면 다수의(되도록 많은) 서명자가 동일한 메시지를 서명하고, 서명자가 처음 한번은 proof-of-possession을 제출하는 절차를 진행할 경우 첫번째의 proof-of-possession 방식으로 signature aggregation의 장점을 활용할 수 있다.
이더리움 2.0에서 사용되는 구조
이 두 조건이 잘 맞는 경우가 바로 이더리움2.0이다.
첫째, PoS(Proof-of-Stake)를 채용하는 이더리움 2.0에서는 블록 컨펌을 위해서 무작위로 다수의 밸리데이터 committee를 구성하게 되고 다수의 밸리데이터가 attestation(즉 디지털서명)을 한다. 이때 블록당(정확하게는 slot당) committee의 최소 참여자는 128 밸리데이터이고 한 committee에 속한 모든 밸리데이터는 ‘같은 데이터에 대해 서명’을 하게 된다. 따라서 BLS의 signature aggregation을 통해서 속도를 개선할 수 있는 아주 좋은 상황이다.
Signature aggregation을 이용한 속도 개선과 함께 이더리움 2.0이 얻는 또 다른 효과는 노드의 공간 절약이다. 모든 밸리데이터들의 서명을 모두 보관하지 않고 합쳐진 서명(aggregated signature)만 보관하면 서명 저장을 위해 필요한 공간이 1/128 정도 축소되는 효과가 나타난다.
주) 서명 대상이 되는 데이터는 AttestationData라고 하며 여기에는 slot 번호, committee 인덱스, 비콘체인 및 체크포인트 정보 등이 들어 있다. 자세한 정보는 아래 참고 링크를 보면 되겠다. 이 글을 위해 알아야 할 점은 한 committee에 속한 모든 밸리데이터는 같은 AttestationData를 메시지로 서명한다는 것이다. 참고 링크: https://notes.ethereum.org/@djrtwo/Bkn3zpwxB
둘째, 이더리움 2.0에 참여하는 밸리데이터는 이더리움 1.0의 스마트컨트랙에 32 이더를 deposit하게 되는데 이때 스마트컨트랙에 밸리데이터 서명을 위한 공개키를 등록한다. 이때가 바로 proof-of-possession을 제출하는 시점이다.
아래 [그림 8]은 이 과정을 개괄적으로 보여준다. 벨리데이터가 되기 위해서는 1번 과정에서 밸리데이터가 되기 위한 최소 예치금을 송금하면서 BLS 공개키, 출금용 공개키의 hash(withdrawal_credentials), deposit 금액(gwei 단위 amount) 등을 포함한 데이터에 디지털 서명을 적용해서 proof-of-possession을 만들어서 함께 스마트컨트랙에 전송한다 (DepositData). 2번 과정에서는 비콘체인에서 DepositData를 받아가고, 3번 과정에서 DepositData 안의 공개키를 이용해서 포함된 서명(proof-of-possession)을 검증한다.
[그림 8] 이더리움 2.0에서의 proof-of-possession 처리 과정
이 과정을 통해서 이더리움 2.0에서는 [그림 5]와 같은 rogue attack을 방지한다.
이와 같은 두가지 이유로 이더리움 2.0은 proof-of-possession 기반 BLS signature를 적용하기에 적합한 조건을 만족시킨다. 또 한가지 주목할 점은 G1, G2 타원곡선 그룹의 용도이다. Part 2에서 G1의 원소는 48 byte로, G2의 원소는 96 byte로 표현된다고 했다. G2 타원곡선 그룹은 원소의 크기가 큰 만큼 타원곡선 연산(addition, doubling)도 느리다. 앞에서 설명한대로 BLS의 발명자들은 서명의 크기를 줄이는 목적이 있었으므로 서명을 G1, 공개키를 G2로 배치했다. 그런데 이더리움 2.0의 경우에는 공개키의 크기를 줄이고, 공개키 연산을 빠르게 해야 하므로 공개키를 G1, 서명을 G2로 배치한다. 앞에서 설명한 대로 밸리데이터의 공개키는 스마트컨트랙(이더리움 1.0)과 비콘체인에 저장되고 이 공개키는 향후 attestation 과정에서 수많은 전송을 겪게 된다. 또한 각 노드에서는 committee의 공개키를 aggregation하는 역할을 반복하게 된다. 따라서 공개키의 크기는 작을수록 좋고 타원곡선 연산도 빠를수록 좋다.
반면 서명의 경우 committee 내에서 통합 서명(aggregated signature)를 만들어서 비콘 체인에 전송하게 된다. 따라서 비콘 체인의 저장 공간, 노드간 통신량, 타원곡선 연산 측면에서 부담이 훨씬 적다. 따라서 공개키를 G1, 서명을 G2로 하는 구성이 적합하다.
공개키의 경우 x, y 좌표의 숫자가 381 bits이고 이를 48 bytes의 compressed form으로 관리할 경우 몇 바이트가 남는데 여기에 compressed/uncompressed 여부, point of infinity인지 여부, y 측의 sign 등의 정보를 넣는다.
주) 이 글에서 이더리움 2.0을 더 자세히 설명하지는 않는다. 이더리움 2.0에 대해 이해하고 싶은 분들은 다른 글들이 많이 있으니 참고하면 되겠다. 예를 들면 https://eth2.info 등이 좋은 시작점이다.
BLS signature의 구현체
이 글을 쓰는 현재 가장 빠른 것으로 알려진 herumi와 blst, 두 라이브러리를 소개하고자 한다. Herumi는 Shigeo Mitsunari가 장기간 개발해왔고 기존의 BLS 라이브러리보다 2~3배 빠른 성능을 보이는 것으로 알려져 있다 (blst를 제외한). 또한 BLS 표준의 변화에 대해 빠르게 대응하고 있는 것으로 보인다. 이더리움 재단에서는 herumi에게 이더리움2.0에 최적화된 라이브러리 구성(검증 시간 최적화 등)을 위해 그랜트를 제공했고, herumi 측에서는 이미 이더리움2.0에 적합한 구성을 가진 golang, rust, WebAssembly라이브러리들을 github에 공개한 상태이다.
Golang: https://github.com/herumi/bls-eth-go-binary
Rust: https://github.com/herumi/bls-eth-rust
WebAssembly: https://github.com/herumi/bls-eth-wasm
이 글 앞쪽에서 BLS의 속도 측정에 사용한 라이브러리도 herumi이며 함수 구성도 사용하기 쉽게 되어 있다. 사용하기 쉽고 상당한 고속 연산을 지원하며 다양한 언어를 지원한다는 것은 큰 장점이다. 하지만 thread-safe하지 않다는 단점을 가지고 있다.
주) thread-safe하다는 것은 multi-thread 프로그래밍에서 함수나 변수를 여러 thread에서 동시 접근할 경우 프로그램에 문제가 없다는 것을 의미한다. 필자도 얼마전 herumi library를 써서 개발할 때 thread-safe 하지 않다는 것이 상당히 불편했던 기억이 있다.
두 번째로 주목되는 라이브러리는 최근 이더리움재단에서 herumi의 또 다른 대안으로 검토하고 있는 고속 라이브러리인 blst가 있다.
[그림 9]는 [그림 2]의 벤치마킹 코드에 blst를 포함해서 실행한 결과이다.
[그림 9] herumi와 blst의 벤치마킹 결과 — ECDSA는 golang standard library (P256 curve), BLS signature는 herumi C library(go-wrapper)와 blst C library(go-wrapper)를 이용함
주목할 점은 B, C, D의 Verify 연산 속도인데 herumi에 비해 blst가 25% 이상의 속도 개선을 이루어 냈다는 것이다. 이더리움 2.0에서 sign의 경우 밸리데이터 클라이언트에서 이루어지므로 어느 라이브러리를 써도 문제될 게 없다([그림 9]에서 보는 바와 같이 herumi가 더 빠름). 그런데 verify, 즉 서명 검증의 경우 블록체인 전체의 속도에 영향을 끼치므로(비콘 체인 노드와 클라이언트에서 모두 사용) 속도가 빠를수록 좋다. 현재 이더리움재단에서는 두 라이브러리를 모두 audit할 것으로 알려져 있으며 클라이언트들도 이에 대비해서 두 가지 라이브러리에 모두 대비하고 있다. [그림 10]은 현재 가장 많이 사용되고 있는 이더리움 2.0 테스트넷 클라이언트인 Prysm의 소스코드 중 일부이다. Herumi가 default로 되어 있으나 blst가 활성화된 경우 blst를 쓰도록 되어 있는 것을 볼 수 있다.
[그림 10] Prysmatic Labs의 이더리움 2.0 클라이언트 코드 예시(as of 21 Sep 2020)
(출처: https://github.com/prysmaticlabs/prysm/blob/master/shared/bls/bls.go)
Blst의 경우 herumi에 비해 역사가 짧은 관계로 아직은 go, rust wapper만 제공하고 있으나 현재 빠르게 코드를 수정 및 확장해 나가고 있으므로 곧 다양한 언어를 지원할 것으로 예상된다.
Blst github에 인상적인 문구가 있어서 원문을 소개한다. Part 2를 읽은 독자분들은 이 질문에 대한 답을 잘 알고 계시리라 생각한다.
“Programming is understanding, and understanding implies mastering the lingo. So we have a pair of additive groups being mapped to multiplicative one… What does it mean?”
라이브러리에서 제공하는 PrivateKey, PublicKey, Signature 객체의 구조도 모른 체 Sign, Verify 함수만 단순히 쓰는 것은 누구나 할 수 있는 일이다. 그런데 BLS signature의 각 객체들이 어떤 수체계와 데이터 구조를 가지고 있고, 어떤 로직으로 Sign, Verify를 실행하며, BLS signature가 어떤 경우에 강점을 가지고 어떻게 운용해야 하는지에 대해 이해하는 것이 고수준의 개발을 위해서는 반드시 필요하다고 생각한다.
“Programming is understanding.” 좋은 말이다.
zk-SNARKs에서의 PBC 적용 사례
영지식증명은 prover가 어떤 문제의 해답을 알고 있다는 것을 verifier에게 해답이 아닌 일종의 증명(proof)을 전달하고, verifier는 해답이 없는 상태에서 증명만으로 prover가 해답을 알고 있다는 것을 검증하게 하는 것이다. 개인키를 보여주지 않고도 서명만으로 개인키를 보유하고 있음을 증명하는 디지털 서명도 같은 부류라고 볼 수 있다.
문제의 유형에 따라 다양한 방식의 영지식증명 기법이 존재한다. 공개키에 대한 개인키 보유 유무 (DLP), RSA와 같은 소인수 분해 문제의 해답, 특정 범위 내에서의 데이터 입력 여부(range proof), 암호문에 대한 평문 보유 여부 등 그 종류는 매우 다양하다. zk-SNARKs의 경우 문제의 유형에 따라 다른 기법을 사용해야 하는 방식이 아닌 일반화된 기법으로 다양한 문제에 대한 영지식 증명 생성과 검증을 가능하게 한다.
zk-SNARKs 자체가 또 다른 시리즈를 연재해야 할 만큼 긴 설명이 필요한 주제이다. 이 글에서는 zk-SNARKs에 대한 설명보다는 PBC가 여기에 어떻게 쓰이는 지에 대해서만 간략하게 설명하고자 한다.
주) 물론 zk-SNARKs를 알고 있다면 이 글이 더 잘 이해될 것이다. 이 글과는 좀 다른 주제이기는 하지만 zk-SNARKs에 대해 알고 싶은 독자는 아래 링크의 블로그 시리즈를 참고하기 바란다.
참고 링크: https://electriccoin.co/blog/snark-explain/
Zcash는 zk-SNARKs를 이용해서 프라이버시를 보존하면서 트랜잭션을 실행하게 하는 블록체인 프로젝트이다. zk-SNARKs를 지속적으로 개선해온 Zcash의 프로젝트 팀은 zk-SNARKs의 중요한 요소인 PBC 자체와 BN curve, BLS curve 등을 개발하고 실용화해 왔다. 그렇다면 이들은 왜 PBC가 필요했던 것일까.
결론을 먼저 말하자면 zk-SNARKs에서는 pairing 함수를 통해서 zk-SNARKs의 증명 검증(proof verification)을 하게 된다.
zk-SNARKs에서는 prover가 자신이 증명하고자 하는 문제를 다항식(polynomial)으로 변환할 수 있도록 한다. 그리고, prover는 문제에 대한 해답을 알고 있다는 것을 증명하기 위해서 이 다항식의 두 가지 결과값, s와 t의 hiding 두 개, h(s)와 h(t)를 verifier에게 보낸다. 사실 prover도 s와 t는 모르고 h(s)와 h(t)를 산출할 뿐이다.
이상하게 들릴지 몰라도 그 이유는 hiding h의 방식을 additive homomorphic하게 구성하고 입력값을 hiding 형태로 받으면 가능하다. 예를 들면 f(x) = a + b∙x + c∙x² 라는 다항식을 prover가 알고 있을 때(다항식을 안다는 것은 a, b, c를 안다는 것과 동일함) prover에게 h(1), h(n), h(n²)가 주어지면 a∙h(1) + b∙h(n) + c∙h(n²) = h(a + b∙n + c∙n²) = h(f(n)) 형태의 additive homomorphic 성질을 이용해서 f(n)의 hiding을 구할 수 있다. 그러므로 prover는 n은 물론 결과값인 f(n)로 모르는 상태에서 f(n)의 hiding인 h(f(n)만 산출하게 된다.
주) Zcash 블로그에서 이를 encryption이라고 부르지 않고 hiding으로 부르는 이유는 decryption할 필요가 없고 단지 숫자를 역산하지 못하게(즉 h(x)에서 x를 도출 못하게) 하면 되기 때문이다. 예를 들면 공개키는 개인키의 hiding이라고 볼 수 있다. 또한 homomorphic하다는 것은 h(x) + h(y) = h(x+y)와 c∙h(x) = h(c∙x)를 만족시키는 성질을 의미한다.
이 예를 조금 더 확장해 보자.
prover에게는 두 hiding set, {h(1), h(n), h(n²)} 그리고 {h(α), h(α∙n), h(α∙n²)}가 전달된다. 이때 s와 t는 바로 f(n)과 α∙f(n)이 된다. prover는 n과 α를 알지 못하고 다항식의 계수 a, b, c를 아는 상태에서 두 결과값 s와 t의 hiding들을 아래와 같은 방식으로 계산한다.
h(s) = a∙h(1) + b∙h(n) + c∙h(n²) = h(a + b∙n + c∙n²) = h(f(n))
h(t) = a∙h(α) + b∙h(α∙n) + c∙h(α∙n²) = h(a∙α + b∙α∙n + c∙α∙n²) = h(α∙f(n))
주) 개념적으로 설명하다 보니 zk-SNARKs의 원래 수식을 굉장히 축약해서 적은데 대해 이해를 해주시기 바란다.
여기에서 만약 prover가 다항식을 알고 있고 제대로 계산했다면 t는 s의 α배이어야 한다. verifier가 검증하는 것이 바로 이것이다.
이때 s와 t를 α-pair라고 한다. 이 때 α 라는 숫자 역시 prover와 verifier가 둘 다 모르는 상태이어야 한다. 그럼 α는 누가 정할까? zk-SNARK에 익숙한 분들은 잘 아시겠지만 α에 대한 hiding들은 프로토콜 실행 전에 설정된 CRS (Common Reference String)에 있고 여기에도 α 값은 없다 (즉 α는 세상 누구도 몰라야 한다). 이런 식의 CRS를 이용한 구성을 통해서 zk-SNARK의 non-interactivity 특성이 가능해진다.
주) 물론 prover는 다항식을 아무렇 게나 구성해도 위의 조건을 만족시킬 수 있다. 이걸 방지하는 방법이 zk-SNARKs에 물론 있다. 아래 링크의 Extended Version of KCA를 참고하자.
참조 링크: https://electriccoin.co/blog/snark-explain6/
Verifier에게는 검증을 위해 h(α)가 주어진다. 따라서 Verifier는 prover에게 받은 h(s), h(t), 그리고 주어진 h(α)로 α∙s = t 인지를 확인할 수 있어야 한다. 어딘지 PBC에서 본 구성과 비슷해 보이지 않는가?
이 구성을 이렇게 바꾸면 된다.
P와 Q를 각각 G1과 G2의 generator라 하고 h(s) = sP, h(t) = tQ, h(α) = αQ 로 구현한다.
즉 hiding 방식을 타원곡선 그룹의 scalar multiplication으로 정의한다 (ECDLP에 의해 hiding이 가능해짐). 위의 {h(1), h(n), h(n²)}를 {P, n∙P, n²∙P}로 하고 {h(α), h(α∙n), h(α∙n²)}를 {α∙Q, α∙n∙Q, α∙n²∙Q}로 하면 h(s) = sP, h(t) = tQ가 된다.
이후 Verifier는 아래와 같이 pairing 함수를 실행해서 A와 B가 같은지를 체크하면 α∙s와 t가 같은지를 볼 수 있게 된다.
A = e(sP, αQ) = e(P, Q)^(α∙s)
B = e(P, tQ) = e(P, Q)^t
ZCash의 경우 단일 트랜잭션을 검증하기 위해 위와 같은 pairing 함수를 실행해야 하기 때문에 효율적인 pairing 함수 실행과 이에 걸맞는 타원곡선 그룹을 지속적으로 연구해왔다. 그 결과가 BN curve와 BLS curve인 것이다.
이 글에서는 zk-SNARKs에 대해 설명하기 보다는 PBC가 zk-SNARKs에서 어떻게 사용되는지를 개념적으로 기술했다. zk-SNARKs에서의 PBC 사용 방식에 대해 더 상세하게 이해하고 싶은 분들은 아래 링크를 참고하기 바란다.
참고 링크: Explaining SNARKs Part VII: https://electriccoin.co/blog/snark-explain7/
시리즈를 마치며
먼저 긴 글을 읽어 주신 모든 독자 분들께 감사드린다.
개인적으로는 pairing 함수를 이해하는 것이 너무 어렵다는 것이 BLS signature 나아가 PBC의 큰 약점이라고 생각한다.
암호를 사용하기 위해서는 일종의 사회적 합의가 반드시 선행되어야 한다. 즉 암호를 이용하는 모든 주체들이 암호의 로직과 보안성에 대해 이해하고, 사용하기로 합의해야 한다는 것이다.
ECDSA, EdDSA, EC-Schnorr 등의 대표적인 타원곡선 기반 디지털 서명 알고리즘들의 식을 보면 서명과 검증 과정을 산술적으로 누구나 쉽게 이해할 수 있다. 반면 BLS signature의 경우 대부분의 사람들에게는 검증에 사용되는 pairing 함수가 블랙박스와 같이 느껴진다. 전문가들이 검증했으니 ‘안전하다 치고 그냥 써라’라는 식으로 접근해서는 광범위하게 사용되기 어렵다. 이것이 pairing 함수가 1940년대부터 개발되었고, BLS signature가 나온 지 거의 20년이 되었음에도 아직 대중화되지 못했던 이유중의 하나가 아닐까.
최근 블록체인 기술의 혁신을 통해서 PBC와 BLS signature가 가진 잠재력을 끌어 올리고, 대중화를 촉진할 수 있게 된 점은 PBC 암호학자들에게는 천금 같은 기회라고 볼 수 있겠다. 또한 이제는 새로운 블록체인 기술을 이해하기 위해서는, 특히 개발자로 참여하기 위해서는 PBC에 대해 어느 정도는 이해할 필요가 있다.
이 글을 통해서 수학이나 암호학을 전공하지 않은 분들도 PBC와 BLS signature의 기본 지식을 쌓는 데에 도움이 될 수 있기를 바란다. 혹시 글에 오류가 있거나 보완이 필요할 경우 언제든지 조언을 해주시기를 바라면서 이 글을 마친다.
