[이더리움 Stateless] 3. 버클트리의 검증
서울대학교 블록체인 학회 디사이퍼(Decipher) After the merge 팀에서 이더리움의 로드맵 중 하나인 Stateless에 대한 글을 시리즈로 연재합니다. 본 글은 이더리움 Stateless 시리즈의 세번째 편으로 버클트리 검증을 설명합니다.
Authors
신우진(@pangyoalto)
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
Reviewd by 임요한
[이더리움 Stateless]
[목차]
- 버클 트리의 도입 이유
- 트리의 proof는 왜 필요한가
- 머클 트리의 검증 방식
- 버클 트리의 proof
- 버클 트리의 검증 방식 — KZG commitment
- 버클 트리의 검증 방식 — Pedersen vector commitment
- 마무리
1. 버클 트리의 도입 이유
비탈릭은 A state expiry and statelessness roadmap에서 stateless를 달성하기 위한 두 가지 방법을 제시하였습니다.
- State expiry
- Weak statelessness
State expiry와 Weak statelessness에 대해서는 앞선 1편에서 자세히 다루었습니다. 간단히 내용을 복기하면 Weak statelessness는 블록 제안자만 상태 저장이 요구되고 검증하는 노드들은 상태를 저장할 필요 없이 검증할 수 있도록 합니다. 블록 제안자가 특정 값이 특정 위치에 포함 여부를 알려주는 witness를 제출하면 검증자 노드들은 상태를 저장할 필요가 없습니다.
Weak statelessness는 witness 크기의 감소가 필수적입니다. 블록이 생성될 때마다 witness를 만들고 전송해야 하기 때문입니다. 현재 머클 트리가 생성하는 witness는 트리의 깊이와 너비가 커질수록 증가해 적합하지 않습니다. 버클 트리는 상수 크기로 witness를 만들 수 있어 채택 가능성이 유력합니다.
2. 트리의 proof는 왜 필요한가
witness는 특정 값이 특정 위치에 포함되어 있는지/없는지를 알려주는 proof입니다. State expiry가 witness의 크기를 줄이기 위해 버클 트리를 도입할 정도로 witness는 매우 중요합니다. 그러면 현재 이더리움은 풀노드가 상태를 전부 저장하고 있으니 proof는 필요 없는 개념일까요?
이더리움의 노드는 3가지 종류로 나눌 수 있습니다. 아카이브 노드, 풀 노드, 라이트 노드입니다. 아카이브 노드는 모든 데이터를 저장하는 노드입니다. 풀 노드는 제네시스 블록부터의 모든 데이터를 가지고 있지만 과거의 상태를 가지고 있지 않습니다. 그렇지만 풀 노드는 현재의 상태를 제공할 수 있습니다. 라이트 노드는 블록 헤더만 가지고 있는 노드입니다.
라이트 노드는 데이터를 다른 노드 및 클라이언트한테 제공할 수 없고 자신이 받은 데이터가 올바른지 확인하기 위해 풀 노드에 proof를 받아야 합니다. 라이트 노드는 proof와 자신이 가지고 있는 블록 헤더의 state root를 통해 데이터를 검증합니다.
따라서 아카이브 노드와 풀 노드는 proof가 필요 없습니다. 이 두 노드는 데이터를 가지고 있기 때문에 자신이 받은 요청을 검증할 수 있기 때문입니다. Proof는 자신이 받은 요청을 스스로 검증할 수 없는 라이트 노드를 위한 것입니다.
그러나 proof는 이더리움을 사용하는 사용자에게 중요하게 쓰일 수 있습니다. Devcon 6에서 발표되었던 Light Clients After the Merge에서 소개된 한 예시를 들어보겠습니다.
사람들이 많이 사용하는 지갑 중 하나인 메타마스크는 메인넷에 요청을 보내려면 메인넷 노드가 제공하는 RPC URL을 입력해야 합니다. 이때 사용자가 풀 노드를 돌리지 않는다면 다른 누군가가 제공해주는 노드의 URL을 사용해야 합니다. 그런데 만약 믿고 추가했던 노드가 악의적인 노드라면 어떤 일이 일어날 수 있을까요?
메타마스크는 별도로 데이터를 검증하는 과정을 거치지 않습니다. 메타마스크는 노드 RPC URL로 질의를 날려 현재 지갑에 로그인된 주소의 이더 및 토큰 개수 정보들을 가져옵니다. 그렇기 때문에 만약 쿼리를 받은 노드가 고의로 이더 개수를 다르게 알려줘도 메타마스크는 알 수 없고 그대로 사용자에게 표시해줍니다. 예를 들어 유저가 트랜잭션으로 1이더를 보냈음에도 노드가 일부러 이더의 개수가 줄지 않은 것처럼 속일 수 있다는 것입니다. 그러면 사용자는 자신의 트랜잭션이 실패한 것으로 생각하고 다시 한번 1이더를 보내는 트랜잭션을 수행할 수 있습니다.
따라서 메타마스크를 안전하게 사용하려면 메타마스크 앞단에 proof를 같이 받아와 검증하는 프록시를 사용하는 것이 좋습니다. 노드가 잘못된 데이터를 알려주더라도 proof를 같이 받아온다면 데이터를 검증할 수 있습니다.
따라서 proof는 라이트 노드가 사용할 뿐만 아니라 실 사용자에게도 중요한 역할을 수행하고 있습니다.
3. 머클 트리의 검증 방식
트리는 데이터를 저장할 수 있는 데이터 구조입니다. 트리의 최상위 노드를 루트 노드(root node), 자식 노드가 있는 노드를 내부 노드(internal node), 자식 노드가 없는 노드를 잎 노드(leaf node)라고 합니다.
머클 트리는 데이터를 잎 노드에 저장하고 내부 노드는 자식 노드를 해시 함수에 넣은 값을 가지고 있습니다. 데이터만 가지고 있지 않고 굳이 해시값을 트리에 포함하는 이유는 proof를 생성하기 위함입니다.
이더리움의 상태를 머클 트리에 저장한다면 라이트 노드는 루트 노드의 값(머클 루트)만 가지고 있어도 proof를 통해 특정 값이 머클 트리에 존재하는지 알 수 있습니다.
예를 들어 위 그림에서 C가 머클 트리에 존재함을 보이고 싶다면 라이트 노드에 D, H(A-B), H(E-H)를 proof로 제출하면 됩니다. 라이트 노드는 C와 proof로 받은 D로 H(C-D)를 계산하고, H(C-D)와 proof로 받은 H(A-B)로 H(A-D)를 계산할 수 있습니다. 마지막으로 H(E-H)와 H(A-B)를 입력값으로 해시값을 계산한 후 자신이 가지고 있는 루트 노드의 값(머클 루트)과 비교해 같다면 머클 트리에 C가 존재함을 검증할 수 있습니다.
이더리움은 머클 패트리샤 트리를 사용합니다. 머클 패트리샤 트리는 머클 트리와 패트리샤 트리의 성질을 모두 만족하는 트리입니다. 패트리샤 트리는 키로 사용되는 문자열의 prefix를 이용해 내부 노드 및 잎 노드를 배치하는 트리입니다. 패트리샤 트리를 사용하면 특정 키로 데이터가 들어오거나 삭제해도 트리의 정렬을 위해 모든 노드를 옮기지 않아도 되는 장점이 있습니다.
이더리움에서 사용하는 트리는 hexary 머클 패트리샤 트리로 예시와 다르게 자식 노드가 최대 16개입니다. 비탈릭은 자신의 글에서 머클 트리는 자식 노드가 2개일 때 최대 효율을 발휘한다고 밝혔습니다.
그런데도 자식노드를 16개 사용하는 이유는 이더리움은 “상태”를 트리에 저장하기 때문입니다. 이더리움은 키가 주소이고 값이 balance, nonce, code 등인 트리가 존재합니다. 이 트리의 문제점은 주소가 가지고 있는 balance, nonce와 같은 값이 바뀌고, 사용자유입으로 새로운 주소도 생성됩니다. 즉, 수정 및 삽입이 자주 발생해 이 비용을 줄여야 합니다. 그래서 이더리움은 최적화를 위해 키를 hexary로 인코딩하여 자식 노드를 16개를 두게 되었습니다. 최적화에 대한 내용은 이 글의 주제에서 벗어나기에 궁금하신 분들은 다음 글을 참고 부탁드립니다.
Hexary 머클 패트리샤 트리는 proof의 크기가 매우 크다는 단점이 있습니다. Proof를 생성할 때 같은 높이에 있는 모든 형제 노드를 포함해야 하기 때문입니다. 이진 트리는 형제 노드가 1개였지만 hexary 트리는 형제 노드가 15개라 크기가 더 커집니다. Stateless를 도입하면 상태를 없애는 대신 proof를 자주 사용하기에 proof의 크기 문제는 큰 걸림돌이 됩니다.
버클 트리는 머클 트리와 같은 기능을 제공하면서도 proof 크기 문제를 해결했습니다. 다음 단락부터 버클 트리의 검증 및 proof의 크기를 줄인 방법을 알아보도록 하겠습니다.
4. 버클 트리의 proof
버클 트리는 머클 트리와 다르게 proof의 크기가 상수입니다. 이것이 가능한 이유는 proof에 형제 노드들을 포함하지 않아도 되기 때문입니다.
머클 트리에서 키 4ce에 값 HORSE가 있다는 것을 증명하려면 Inner node들은 자신의 해시값에 자기 자식 모두(빨간색)를 포함해야 합니다.
그러나 버클 트리는 그렇지 않습니다. 버클 트리는 proof 크기 문제를 vector commitment을 사용하여 해결했습니다. Vector commitment scheme은 간단히 말하면 특별한 타입의 해시 함수입니다. 버클 트리는 각 레벨의 proof 크기가 형제 노드의 개수와 상관없어 width를 늘리는 데 부담이 없습니다. 실제로 width는 256~1024로 논의 중입니다.
머클 트리는 값의 존재 증명을 위해 내부 노드에 값을 보관했습니다. 버클 트리도 내부 노드가 값을 가지고 있는데, 이를 commitment라고 합니다. Commitment는 머클 트리와 달리 단순히 해시를 취해서 구하는 것은 아니지만, 자식 노드들의 값이 필요합니다. Commitment를 어떻게 계산하는지에 따라 버클 트리의 검증 방법이 달라집니다. Commitment가 proof 생성에 영향을 미치기 때문입니다.
버클 트리에서 사용하는 proof를 생성하는 식을 Opening이라고 합니다. Opening인 Open(C, x, i, v)은 Commitment가 C일 때 x_i = v임을 증명합니다.
Opening으로 생성된 proof들은 하나로 압축이 가능합니다. 따라서 레벨마다 하나씩 있어 총 log(n) 개였던 proof들은 최종적으로 한 개로 압축되어 O(1)의 크기를 갖게 됩니다.
그렇다면 어떻게 proof의 크기가 자식 노드 개수와 상관없이 상수 크기가 될 수 있었을까요? 이것을 완벽히 이해하려면 높은 수학 지식이 뒷받침돼야 합니다. 하지만 이번 글은 쉽게 이해할 수 있게 최대한 수학적 증명을 빼고 큰 그림만 살펴볼 것입니다. 먼저 버클 트리 논의 초기에 언급되었던 KZG commitment를 먼저 살펴보고, 현재 채택 가능성이 유력한 Pedersen commitment를 살펴볼 것입니다.
5. 버클 트리의 검증 방식 — KZG commitment
자식을 최대 d개까지 가지는 d-ary 버클 트리를 생각해봅시다. 각 내부 노드는 자식 노드들을 통해 계산한 commitment를 가지고 있고, 특정 자식 노드를 가지고 있다는 것을 증명하는 proof를 생성할 수 있습니다.
KZG commitment는 다항식을 사용해 commitment를 생성합니다. 다항식을 만들어 commitment를 생성하는 방법은 다음과 같습니다.
- w^d = 1, 0≤i<d에 대해 w^i≠1을 만족하는 w를 잡습니다.
- 라그랑주 보간법을 사용해 0≤i<d에 대해 f(w^i)=v_i을 만족하는 d-1차 다항식 f를 유일하게 정의할 수 있습니다.
- f에 특정 값 s를 넣어 f(s)를 계산합니다.
- f(s)를 타원 곡선으로 대응시켜 [f(s)]를 계산합니다(타원 곡선에 대한 설명은 비탈릭 부테린의 글로 갈음하겠습니다).
- [f(s)]를 commitment로 사용합니다.
즉 i번째 자식 노드의 값 v_i를 사용해 다항식 f를 만들고, 이를 이용해 commitment를 계산하는 것입니다. 이때 전제 조건이 있는데, Commitment를 만드는 데 사용되는 값 s는 아무도 몰라야 합니다. 만약 s가 노출된다면 f’(x) = f(x)-x+s와 같이 f(x)는 다르면서 commitment는 같은 다항식을 만들 수 있습니다. 즉, 자식 노드의 값을 위조하고 해당 값이 존재함을 보이는 opening 생성이 가능하기에 절대 노출이 되면 안 됩니다.
f(w^i) = v_i를 만족할 때, proof는 [(f(s)-v_i)/(s-w^i)]입니다. 풀어 설명하면 f(w^i) = v_i을 반영하였으므로 q(x) = {f(x)-v_i}/(x-w^i)도 다항식입니다. 이 다항식이 바로 Opening이고, Opening에 s를 넣은 값이 바로 Proof가 됩니다. 즉 proof는 q(s)입니다. Proof를 이렇게 계산하면 다음 식을 만족합니다.
여기서 e는 타원 곡선의 pairing 개념입니다. 위 수식을 만족하는 이유는 박성완님의 글과 Dankrad Feist의 글로 갈음합니다.
저 수식의 의미하는 바는 무엇일까요? 우리가 버클 트리를 가지고 있는 노드라고 생각해봅시다. 우리는 Commitment, 즉 f(s)를 알고 있습니다. 이때 어떤 사용자가 내부 노드의 i번째 자식 노드의 값이 v_i라고 주장하며 proof를 제출했습니다. 우리는 f(s)를 이미 알고 있었고 사용자로부터 v_i와 w^i, 그리고 proof인 [q(s)]를 받음으로써 저 수식의 모든 요소를 알게 됩니다. 이제 저 등호가 성립하는지 직접 계산해서 확인할 수 있습니다. 등호가 성립하면 사용자의 주장대로 i번째 자식 노드 값이 v_i입니다.
정리하면 버클 트리의 층마다 Commitment가 존재하고 그에 따른 proof를 제출하면 자식 노드의 값 존재를 증명할 수 있습니다.
하지만 Stateless의 조건인 상수 크기의 proof는 만족하지 않습니다. 층마다 proof가 필요하기에 총개수는 O(logn)이기 때문입니다. 상수 크기로 만들려면 이 proof들을 다시 한번 압축해야 합니다. 아주 간단히 말하면 위에서 보았던 방법을 확장해 proof에 대해서 Polynomial을 만듭니다. 자세한 설명은 Dankrad Feist의 글(PCS multiproofs)을 참고해주세요.
여기까지 따라오셨다면 간략하게 KZG commiment를 이용해 버클 트리 proof의 크기를 상수로 줄이는 과정을 이해한 것입니다. 그러나 KZG commitment 방식은 치명적인 단점이 있습니다. 바로 아무도 알지 못하는 s를 생성하기가 매우 어렵다는 것입니다. s를 아는 공격자는 위조된 opening을 생성해 없는 값을 존재한다고 증명할 수 있을 것입니다. 다음 단락에서는 s를 사용하지 않는 Pederson vector commitment를 알아봅니다.
6. 버클 트리의 검증 방식 — Pedersen vector commitment
Pedersen vector commitment(이하 Pedersen)는 commitment를 만드는 scheme입니다. IPA(Inner Product Arguments)는 Pedersen 위에서 Opening을 만드는 scheme입니다. Pedersen과 IPA를 같이 사용하면 KZG가 필요했던 신뢰할 수 있는 값(trusted setup)없이 proof를 만들어낼 수 있습니다.
단점은 위 표에서 볼 수 있듯이 proof의 크기가 커지고 검증 시간도 길어지는 것입니다. 로그 크기도 충분히 작기 때문에 proof의 크기는 감당할 수 있을지 몰라도 검증 시간이 선형 크기로 증가하는 것은 어플리케이션에 치명적일 수 있습니다.
이 단점을 보완하기 위해 앞에서 잠깐 보았던 multiproof 압축과 Halo 프로토콜이 사용됩니다. (1)여러 proof들을 하나의 proof로 모으고 (2)Halo를 사용하면 합쳐진 Opening을 검증하는 데 적은 시간이 듭니다. Halo 프로토콜은 검증 단계를 k개로 나누어 각각의 스텝마다 따로 proof를 만들고 합치는 식으로 검증하여 거의 O(k) 시간에 검증을 할 수 있습니다.
IPA에 Halo를 적용하면 KZG보다는 크지만 검증 시간이 상수로 줄어드는 것을 확인할 수 있습니다. 즉 trusted setup이 없으면서 proof의 크기가 작고 검증 시간도 적어 버클 트리에 적용하기 적합합니다.
Halo는 Zcash에 적용되는 프로토콜로 SNARK 기반 체인에서 작동하는 것이 전제입니다. 즉 IPA 기반 SNARK의 블록이어야 Halo 적용이 가능합니다. 실제로 Verge의 로드맵을 보면 최종 목표는 fully SNARKed ethereum입니다. SNARK를 위한 Verkle proof를 만들면 proof의 크기 및 검증 시간을 줄일 수 있을 것이고, stateless로 가기 위한 준비가 될 것입니다.
Pedersen과 IPA, Halo의 동작에 대해 좀 더 알고 싶은 분들은 Dankrad Feist의 글과 비탈릭의 글을 참고해주세요.
7. 마무리
버클 트리는 트리의 특정 위치에 특정 값이 존재 했음/하지 않았음을 증명하기 위한 proof(witness) 크기를 줄이기 위해 제안되었습니다. Stateless가 적용되면 노드와 사용자가 witness를 자주 주고받기 때문에 꼭 필요합니다. 버클 트리를 구현하는 방법은 여러 방식이 있고, 그중 pedersen vector commitment 방식이 유력한 상황입니다.
이번 글은 버클 트리의 도입 이유와 검증 방식을 간략하게 다뤄보았습니다. 다음 글에서 머클 트리와 버클 트리의 구조가 무엇이 다른지 살펴보겠습니다.
