[이더리움2.0 깊이보기 시리즈] 스태이트리스 클라이언트(Stateless Client)[7편]
Introduce a new Accumulator and Execution Model
이더리움2.0 깊이보기 시리즈는 개발이 진행되고 있는 이더리움2.0에 관한 스펙과 작동원리에 대해서 이해의 저변을 넓히고자 하는 목적으로 온더에서 기획되었습니다. 연재는 다음 순서로 이어집니다.
[1편] — ETH 2.0 Explained: Phase 0
[2편] — Cross Shard Communication -1- 비동기 커뮤니케이션
[3편] — Cross Shard Communication -2- 동기 커뮤니케이션
[4편] — CBC casper explained (1/2)
[5편] — CBC casper explained (2/2)
[6편] — ETH 2.0 Explained: Phase 1
[7편] — 스태이트리스 클라이언트(Stateless Client)
[8편] — ETH 2.0 Explained: Phase 2
[9편] — Execution Environment
이더리움 2.0에서 밸리데이터(validator)들은 셔플링(shuffling)되어 각각의 샤드 체인에 배정됩니다. 밸리데이터가 샤드 체인에 배정되면, 밸리데이터는 샤드 체인의 전체 상태 트리(entire state trie)를 새로 다운로드하여 상태를 싱크(sync)하게 됩니다. 밸리데이터가 샤드 체인에 배정될 때마다 전체 상태 트리를 새로 다운로드 받는 일은 밸리데이터에게 큰 부담이 됩니다. 만약 밸리데이터의 노드가 Stateless하다면 이러한 부담을 크게 줄일 수 있습니다. Stateless 클라이언트는 전체 상태 트리를 가지지 않고 상태 루트(state root)값만을 가지기 때문입니다.
본 글은 이더리움 재단 소속 리서처인 Justin Drake의 Stateless 클라이언트에 대한 연구 결과물을 기반으로 합니다. Justin Drake의 최종 연구 결과물은 Double-batched Log Accumulator와 State-minimised 실행 모델이며, 본 글은 이를 이해하기 위한 내용으로 구성되어 있습니다.
Stateless Client Concept
Stateless 클라이언트에 대한 컨셉은 비탈릭 부테린이 처음 “Stateless client concept”라는 글을 통해 제안되었습니다. 현재 이더리움 1.0은 트랜잭션을 실행하면서 상태(state)에 접근하기 위해서는 전체 상태 트리(entire state trie)를 필요로 합니다. Stateless 클라이언트는 전체 상태 트리를 가지지 않고 상태 루트(state root)만을 가집니다. Stateless 클라이언트에서 전체 상태 트리에 대한 접근없이 트랜잭션을 성공적으로 처리하기 위해선 트랜잭션과 함께 witness 데이터를 필요로 합니다. witness 데이터란 트랜잭션이 실행하면서 접근하게 되는 어카운트 또는 스토리지 키에 접근하기 위해 필요한 데이터를 말합니다. 머클 트리를 예로 들면, 머클 트리의 리프 노드와 해당 리프 노드가 머클 트리에 존재함을 입증해줄 수 있는 머클 경로(merkle path)가 witness라고 볼 수 있습니다.
Stateless 클라이언트에서는 트랜잭션이 witness에 포함되어 있지 않은 어카운트나 스토리지 키에 접근하면 에러를 발생시킵니다. 트랜잭션이 성공적으로 처리되면 Stateless 클라이언트는 새로운 상태 루트를 가집니다.
이와 같이 Stateless 클라이언트는 상태 루트만을 가지며, witness 데이터들은 마이너(miner)가 제공합니다. 그렇기 때문에 마이너는 항상 전체 상태 트리를 가지고 있습니다. 이에 대한 대안으로 트랜잭션 송신자(transaction sender)가 전체 상태 트리를 가지도록 해서 witness 제공에 대한 책임을 트랜잭션 송신자에게 넘기는 방식도 있습니다. 그렇게 되면 마이너 또한 Stateless해질 수 있습니다.
하지만 이와 같은 Stateless 클라이언트 개념은 현재 이더리움 1.0에 적용하기에는 다음과 같은 문제가 있습니다. 현재 이더리움 1.0에서의 어카운트에 대한 접근은 동적(dynamic)입니다. 여기서 동적이다라는 의미는 누구나 임의의 어카운트에 접근할 수 있음을 의미합니다. 예를 들어 getcodesize(sha3(sha3(…sha3(x)…)) % 2**160) 같은 코드가 스마트 컨트랙트에 구현되어 있으면 이 컨트랙트는 임의의 어카운트에 접근하여 해당 어카운트의 코드 사이즈를 리턴하게 됩니다. 이 예시에서는 트랜잭션 송신자가 트랜잭션과 함께 witness를 보내더라도 해당 witness가 포함하고 있지 않은 어카운트에 접근하게 될 확률이 매우 높기 때문에 결국 이 트랜잭션은 에러를 발생시킵니다.
이러한 문제를 해결하기 위해 트랜잭션 외부에 어카운트 리스트를 두는 방식을 채택할 수 있습니다. 이 방법은 트랜잭션을 미리 실행해보고 트랜잭션이 실행되면서 접근하는 어카운트들의 리스트를 트랜잭션과 함께 보내는 것을 말합니다. 이때 witness 데이터도 함께 보내집니다. 하지만 이는 또 다른 문제를 가집니다. 트랜잭션과 어카운트 리스트를 보낼 때의 시점과 실제로 트랜잭션이 블록에 포함되어 처리되는 시점에 시간적 간격이 존재합니다. 그 사이에서 해당 어카운트의 상태의 변경이 이루어지면 witness의 정확성(correctness)가 깨지게 됩니다(트랜잭션을 보낼 때의 witness는 정확성(correctness)을 가졌지만).
위와 같은 문제는 마이너가 블록에 트랜잭션을 포함하기 전에 마이너가 witness를 다시 조정할 수 있게 해주는 방식으로 해결될 수 있습니다. 예를 들어 24시간 동안 마이너 노드로 보내진 트랜잭션들, 즉 마이너 노드의 트랜잭션 풀(transaction pool)에 존재하는 트랜잭션이 접근하게 될 모든 어카운트에 대한 상태 트리 노드들을 마이너가 가지도록 한다면 마이너가 정확성(correctness)가 깨진 witness를 다시 조정해줄 수 있습니다. 왜냐하면 마이너가 갖고 있는 상태 트리 노드들로부터 witness를 다시 생성할 수 있기 때문입니다.
정리하면, 결국 Stateless 클라이언트는 전체 상태 트리를 가지지 않고 상태 루트만을 가지는 클라이언트입니다.
advantage
Stateless 클라이언트는 다음의 장점을 가집니다.
- Stateless한 마이너들과 노드들은 전체 상태 트리를 가지지 않아도 됩니다. 그렇기 때문에 노드들간의 동기화가 매우 빠르게 이루어질 수 있습니다.
- 스토리지에 접근에 필요한 SLOAD와 SSTORE opcode에 대한 가스 측정은 이더리움 네트워크 상황에 따라 동적으로 변경될 수 있습니다(상태 트리가 커짐에 따라 이스탄불 하드포크에서는 SLOAD의 가스 비용을 200에서 800으로 늘렸습니다). 특히 SSTORE는 스토리지를 비우는 행위, 즉 스토리지의 값을 0으로 만들면 가스를 리펀드 해주는 것과 같이 다소 복잡한 스펙을 가지고 있습니다. Stateless 클라이언트는 상태에 접근하지 않기 때문에 이러한 스킴(scheme)을 가지지 않아도 됩니다.
- Stateless 클라이언트에서는 전체 상태 트리에 접근하기 위해 필요한 디스크 입출력(Disk IO)을 필요로 하지 않습니다. 디스크 입출력은 상태의 값을 읽거나 쓸 때 발생하는 것으로 이더리움 네트워크의 상태 트리가 커짐에 따라 디스크 입출력의 비용이 비싸져, 이더리움 네트워크에서 항상 도스 (DoS, Denial-of-Service) 공격 벡터로 작용했습니다.
- 트랜잭션과 함께 어카운트 리스트를 명시하는 것은 트랜잭션의 처리에 대한 병렬화를 가능하게 해줍니다. 두 개의 트랜잭션이 존재할 때 각각의 트랜잭션이 접근하는 어카운트가 겹치지 않으면, 두 개의 트랜잭션을 병렬로 처리해도 큰 문제가 되지 않을 것입니다.
- 트랜잭션과 함께 어카운트 리스트를 명시하면 클라이언트에서 해당 어카운트의 스토리지 데이터를 미리 가져올 수 있습니다.
- 샤딩에서 밸리데이터들은 각 샤드에 셔플링되어 배정됩니다. 밸리데이터들이 셔플링되어 샤드 체인에 배정될 때 샤드 체인의 상태를 새로 다운로드 하여 싱크를 맞추게 됩니다. Stateless한 밸리데이터가 샤드 체인에 배정될 때 상태 루트 값만을 다운로드하면 되기 때문에 밸리데이터가 셔플링되어 배정되는 과정이 간소화될 수 있습니다.
Reference
- https://ethresear.ch/t/the-stateless-client-concept/172
- https://medium.com/@akhounov/data-from-the-ethereum-stateless-prototype-8c69479c8abc
Accumulator
Stateless 클라이언트 개념이 제안된 이후 Stateless 클라이언트에 대한 리서치가 활발하게 진행되었습니다. 이더리움 재단 소속 리서처인 Justin Drake는 Stateless 클라이언트에서 사용할 새로운 Accumulator를 제안합니다. 이를 소개하기 전에 Accumulator에 대해 좀더 알아보고자 합니다.
머클 트리는 가장 대표적인 Accumulator 입니다. 머클 트리의 머클 루트 값은 머클 트리가 가지고 있는 엘리먼트(element)들을 대표하는 값입니다. 그리고 특정 엘리먼트에 대한 머클 패스는 해당 엘리먼트가 머클 트리에 포함되어 있음을 증명하기 위해 사용됩니다. 머클 트리의 머클 루트 값은 Accumulator에서 “Accumulator value”라고 부르고 머클 패스는 “Membership witness”라고 부릅니다.
그리고 보통 머클 트리와 같은 Accumulator 구조를 “Strong”하다고 표현하는데, 여기서 Strong이라는 의미는 Accumulator를 생성하고 새로운 엘리먼트를 Accumulator에 추가하기 위해 누군가를 신뢰(trust)하지 않아도 된다는 뜻으로 사용됩니다. 즉 신뢰를 필요로 하지 않은(trustless한) Accumulator를 Strong Accumulator라고 부릅니다.
정리하면, Accumulator는 Accumulator value를 가지며 새로운 엘리먼트가 추가될 때마다 해당 Accumulator value가 변경되고 특정 엘리먼트가 Accumulator에 존재하고 있음을 Membership witness를 통해 증명 가능한 구조를 말합니다.
Reference
History, state, and asynchronous accumulators in the stateless model
Justin Drake는 Asynchronous Accumulator를 소개하며, 이 Asynchronous Accumulator가 Stateless 클라이언트 모델에 매우 적합하게 사용될 수 있음을 말합니다. (참고로, Asynchronous Accumulator는 Leonid Reyzin 그리고 Sophia Yakoubov의 Efficient Asynchronous Accumulators for Distributed PKI 논문에서 제안된 Accumulator입니다.)
Asynchronous Accumulator
머클 트리(또는 머클 패트리샤 트리)와 같은 Accumulator는 새로운 엘리먼트가 추가될 때마다 Membership witness가 업데이트 됩니다. 즉 Membership witness의 업데이트는 새로 추가될 엘리먼트의 개수에 완전히 비례(Linear)합니다.
Asynchronous Accumulator는 일반적인 Accumulator와 다르게 Low update frequency의 특성을 가집니다. Low update frequency 특성은 Membership witness의 업데이트가 새로 추가되는 엘리먼트의 개수에 완전히 비례하지 않음(Sub-linear 함)을 말합니다.
Asynchronous Accumulator의 구조는 위의 그림과 같습니다. Asynchronous Accumulator는 여러 개의 머클 트리의 머클 루트 값으로 이루어집니다. 실제로 Asynchronous Accumulator에 저장되는 값은 이러한 머클 루트 값의 리스트가 됩니다.
Asynchronous Accumulator의 Membership witness는 머클 트리의 리프 노드에서부터 해당 리프 노드를 가지고 있는 머클 루트까지의 머클 패스가 됩니다. 예를 들어 위의 그림에서 h(xt-5)에 대한 Membership witness는 점선으로 그려진 h(xt-6)과 z, 그리고 이 둘을 해시한 값(머클 루트)이 됩니다.
위 그림에서 주목할 점은 Membership witness의 업데이트는 머클 트리가 머지(merge)될 때만 발생한다는 점입니다. 그리고 Accumulator에 저장되는 머클 루트 값들은 업데이트되는 것이 아니라 추가만(append-only)되는 것을 확인할 수 있습니다. 이러한 특성은 Asynchronous Accumulator의 또 다른 특성인 Old-Accumulator Compatibility 특성을 가지게 합니다.
Old-Accumulator Compatibility 특성이란 최신의 Membership witness를 가지고 이전 상태(최신 상태가 아닌)의 Accumulator 상태에서의 특정 데이터 Membership 검증이 가능한 특성을 말합니다. 왜냐하면 Membership witness는 추가만 되기(append-only 하기)때문에, 이전 Accumulator 상태에서 특정 데이터의 Membership 검증을 하기 위해서는 그저 이전에 생성된 Membership witness를 사용하면 되기 때문입니다.
정리하면, Asynchronous Accumulator는 Low update frequency 특성과 Old-Accumulator Compatibility 특성을 가지는 Accumulator입니다.
History in the stateless model
Asynchronous Accumulator를 포함해서 일반적인 Accumulator는 히스토리(history) 데이터만을 다룹니다. “히스토리”란 변경이 불가능하며 오직 추가만 가능한(append-only한) 데이터를 말합니다. 이더리움에서 사용하는 히스토리는 트랜잭션(transaction) 히스토리, 블록(block) 히스토리 그리고 리십트(receipt) 히스토리가 있습니다. 그리고 컨트랙트 코드 또한 불변이기 때문에 히스토리라고 볼 수 있습니다.
Stateless 클라이언트에서는 witness가 트랜잭션과 함께 제공되기 때문에 Stateless 클라이언트는 데이터를 찾는 행위, 즉 상태(state)를 필요로 하지 않습니다. 그렇기 때문에 Stateless 클라이언트에서는 동적(데이터의 수정이 가능한 것을 말함.)인 상태를 다루는 것보다 정적(데이터의 수정이 불가능하고 오직 데이터의 추가만 발생하는 것을 말함.)인 히스토리를 다루는 것이 더욱 쉬워집니다.
정리하면, Asynchronous Accumulator는 history를 다루는 Accumulator로서, Low update frequency 특성과 Old-Accumulator Compatibility 특성 또한 가지기 때문에 Justin Drake는 이러한 Asynchronous Accumulator가 Stateless 클라이언트에 사용되기에 매우 적합하다고 말합니다.
이에 대해, 비탈릭은 Asynchronous Accumulator은 Merkle Mountain Ranges의 자료 구조와 같으며 새로운 아이디어가 아니라고 피드백을 줍니다. 이후 Justin Drake는 Merkle Mountain Ranges를 바탕으로 새로운 Accumulator를 제안하게 됩니다.
Reference
- https://ethresear.ch/t/history-state-and-asynchronous-accumulators-in-the-stateless-model/287
- https://eprint.iacr.org/2015/718.pdf
Merkle Mountain Ranges (MMR)
Merkle Mountain Ranges(MMR)는 아래의 그림과 같이 생긴 자료 구조를 말합니다.
MMR의 데이터들은 모두 다이제스트(digest)이며 오직 추가만 가능(append-only)합니다. 여기서 “다이제스트”란 어떤 값을 해시 함수에 넣어서 나온 결과값을 말합니다. 위 그림에서 MMR 각 노드의 숫자들은 노드가 생성된 순서를 의미합니다. MMR에 새로운 노드는 왼쪽에서 오른쪽 방향으로 추가(append)되며, 왼쪽 자매(left-sibling) 노드가 존재하면 부모(parent) 노드를 생성하는 방식으로 만들어집니다. 예를 들어 1번 노드가 생성되어 추가될 때 왼쪽 자매 노드인 0번 노드가 존재하기 때문에 2번 부모 노드가 생성됩니다. 이와 같이 11개의 리프 노드가 추가되면 위의 그림과 같은 산(Mountain)의 모양을 만들게 됩니다. 이러한 자료 구조의 형태를 “Merkle Mountain Ranges”라고 합니다.
MMR에 새로운 노드를 추가하는 것은 다른 MMR 노드들의 변경을 야기하지 않기 때문에 값싼 연산이 됩니다(Merkle Patricia Trie 같은 경우 새로운 노드가 생김에 따라 중간(intermediate) 노드의 변경이 일어납니다.). 그리고 새로운 노드가 생김에 따라 새로운 꼭대기 노드(peak)가 만들어집니다. 여기서 꼭대기 노드란 두 개의 노드가 하나의 산(Mountain) 모양을 이루면서 생기는 것을 말합니다. 위의 그림에서는 14번 노드와 17번 노드 그리고 18번 노드가 꼭대기 노드가 됩니다. 꼭대기 노드는 이처럼 새로운 노드가 생기면서 변경될 수 있습니다.
이에 더해 MMR은 다음의 특징을 가집니다.
(1) 리프(leaf) 노드의 개수를 통해 MMR의 높이(height)를 구할 수 있습니다. 리프 노드의 개수가 n일 때, MMR의 가장 큰 산(Moutain)의 높이는 log2(n)를 내림한 값과 같습니다. 여기서 리프 노드의 개수는 7개고, 이에 따라 가장 큰 산(Mountain)의 높이가 2임을 알 수 있습니다.
(2) MMR의 꼭대기 노드(peak)는 항상 왼쪽에서 먼저 생깁니다. 그렇기 때문에 가장 높은 꼭대기 노드 역시 왼쪽의 산(Mountain)에서 먼저 생깁니다. 이러한 꼭대기 노드들은 모두 2^n-1의 포지션에 존재합니다. 예를 들어 총 11개의 노드를 가지는 MMR이 있을 때 꼭대기 노드(peak)를 구하는 방법은 아래과 같습니다.
2^0 - 1 = 0, and 0 < 11
2^1 - 1 = 1, and 1 < 11
2^2 - 1 = 3, and 3 < 11
2^3 - 1 = 7, and 7 < 11
2^4 - 1 = 15, and 15 is not < 11이와 같이 총 11개의 노드를 가지는 MMR에서 가장 큰 산(Mountain)의 꼭대기 노드의 포지션은 7이 됩니다.
(3) 꼭대기(peak) 노드를 찾은 후((2) 과정을 통해) 다음 꼭대기 노드를 찾기 위해서 오른쪽 자매(right-sibling)노드로 점프하거나 왼쪽 자식(left-child) 노드를 취합니다. 오른쪽 자매 노드로 점프하기 위해서는 해당 노드 포지션에서 2^(h+1)-1를 더한 포지션을 취합니다. 왼쪽 자식 노드로 이동하기 위해서는 해당 노드의 포지션에서 2^h를 뺀 포지션을 취합니다. 여기서 h는 높이를 의미합니다.
merkle root (Accumulator value)
그러나 MMR에서는 MMR을 대표하는 단 하나의 머클 루트(merkle root)가 존재하지 않습니다. MMR에서 머클 루트를 만들기 위해서는 “bagging”이라는 작업이 필요합니다. bagging은 MMR에 존재하는 꼭대기 노드(peak)들(위의 그림에선 14, 17, 18번 노드의 다이제스트)을 이어 붙인 다음 이를 해싱하는 것을 말합니다. 이 해시된 값이 바로 MMR을 나타낼 수 있는 머클 루트값이 됩니다.
merkle path (Membership witness)
MMR은 Membership witness를 가집니다. Membership witness를 가지고 특정 데이터가 MMR의 멤버임을 입증할 수 있습니다. MMR의 머클 경로(merkle path)가 바로 Membership witness입니다.
포지션 10의 리프 노드에 대한 머클 경로는 다음의 데이터를 포함하게 됩니다.
(1) 머클 루트 (꼭대기 노드들을 bagging해서 만든 MMR을 대표하는 해시값).
(2) 꼭대기 노드 데이터들: 17번, 18번.
(3) 이외의 데이터들: 11번(merge(10, 11) = 12), 9번(merge(9, 12) = 13), 6번(merge(6, 13) = 14).
위의 머클 경로 데이터들을 이용해서 포지션 10의 리프 노드가 해당 MMR의 멤버임을 입증할 수 있게 됩니다.
정리하면, Merkle Mountain Ranges(MMR)는 히스토리(history)를 다루는 Accumulator이며 Asynchronous Accumulator의 구조와 동일하기 때문에 MMR 역시 Low update frequency 특성과 Old-Accumulator Compatibility 특성을 가집니다.
Reference
- https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md
- https://github.com/mimblewimble/grin/blob/master/doc/mmr.md
Log Accumulator
JustinDrake는 MMR을 이용해 새로운 Accumulator인, Log Accumulator를 제안합니다.
Log Accumulator는 히스토리를 저장합니다. 이 히스토리를 Log Accumulator에선 로그(log)라고 부릅니다. Log Accumulator는 3MR을 사용하는데, 3MR은 multi-MMR의 약자로 MMR의 집합을 의미합니다.
Stateless 클라이언트에서 각각의 샤드들은 2^n개로 구성된 3MR을 가집니다. 그리고 각각의 3MR은 0, 1, …, (2^n)-1로 라벨링됩니다. 예를 들어 n이 2일 때 각각의 샤드들은 4개의 MMR로 구성된 3MR을 가지며 4개의 MMR은 각각 0, 1, 2, 3으로 라벨링됩니다.
샤드 체인에서의 블록(Block)을 컬레이션(Collation)이라 부르고, 컬레이션을 생성하는 주체를 컬레이터(Collator)라고 부릅니다.
우선 높이가 i인 컬레이션(collation)을 받으면 컬레이션에 포함된 로그(log)들을 가지고 머클 트리를 만듭니다. 이렇게 만들어진 머클 트리의 루트 해시 값을 로그 배치 루트(log batch root)라고 부릅니다. 로그 배치 루트를 만드는 과정을 배칭(batching)이라고 합니다.
배칭(batching) 작업이 끝나면 “cyclic partitioning” 작업을 수행합니다. 배칭(batching) 작업으로 만들어진 로그 배치 루트(log batch root)는 샤드가 갖고 있는 2^n개의 MMR 중 하나에 삽입하게 됩니다. 높이(height)가 i인 컬레이션에서의 로그 배치 루트는 (i mod 2^n) 나머지 연산을 통해 나온 숫자로 라벨링된 MMR에 삽입됩니다. 예를 들어 n이 2이고 높이가 10인 컬레이션으로부터 생긴 로그 배치 루트는 4개의 MMR 중에 2(=10 mod 4)로 라벨링된 MMR에 삽입됩니다.
이제 특정 로그(log)가 Log Accumulator의 멤버임을 입증할 수 있어야 합니다. 이를 위해서는 witness가 필요한데, witness는 아래의 데이터로 이루어집니다.
- 로그 l을 가진 리프 노드에서부터 로그 배치 루트(log batch root)까지의 머클 경로 (merkle tree의 merkle path — “batching”).
- MMR에 삽입된 로그 배치 루트를 가지는 리프 노드에서부터 MMR의 머클 루트까지의 머클 경로 (MMR의 merkle path — “cyclic partitioning”).
이 Log Accumulator는 MMR을 향상시킨 것으로, 향상된 부분은 다음과 같습니다.
- Deterministic witness update events
: 배칭(batching) 작업으로 인해, 높이 i인 컬레이션(collation) 포함된 로그(log)들을 포함하는 로그 배치 루트(log batch root)는 2^n개의 MMR중 하나의 MMR, m1(예를 들어, 1로 라벨링 된 MMR)에 추가됩니다. 여기서 결정적(deterministic)이라는 의미는 m1의 witness 업데이트가 컬레이션의 높이에만 의존하기 때문에 해당 MMR, m1의 witness 업데이트가 언제 이루어질지 예측이 가능함을 말합니다. - Reduced witness update events
: “partitioning”을 하기 때문에, 각각의 MMR에서의 witness 업데이트는 1/2^n(2^n == MMR의 개수)만큼 발생합니다. 왜냐하면 Log Accumulator는 2^n개의 MMR로 구성되어 있기 때문입니다. - Cheap historical data availability
: 로그가 주어졌을 때, witness를 새로 업데이트하기 위해서는 제네시스(genesis) 이후부터 만들어진 모든 컬레이션(collation)의 로그 배치 루트(log batch root)만을 가지고 있으면 됩니다. 만약 이 로그 배치 루트를 컬레이션 헤더에 기록하면, 특정 샤드에 대한 모든 SPV(Simplified Payment Verification) 노드 역시 로그 witness 업데이트에 필요한 데이터들을 제공할 수 있게 됩니다. 이것이 가능한 이유는 SPV 노드는 컬레이션 헤더만을 저장하는데, 이 컬레이션 헤더에 로그 배치 루트가 기록되어 있기 때문입니다.
Reference
- https://ethresear.ch/t/batching-and-cyclic-partitioning-of-logs/536
- https://ethresear.ch/t/multi-tries-vs-partial-statelessness/391
Double-batched Merkle Log Accumulator
Double-batched Merkle Log Accumulator는 Log Accumulator에 로그(log)가 추가되면서 생기는 witness의 업데이트를 최소화 하도록 발전시킨 Accumulator입니다.
Double-batched Merkle Log Accumulators는 Log Accumulator의 배칭(batching) 부분을 two layer로 나눕니다. 이를 위해 모든 샤드에게 32 바이트(byte) 해시를 저장하는 두 개의 버퍼를 제공합니다.
- Bottom buffer
: 2^n개의 엔트리를 가지는 고정된 사이즈로 각각의 엔트리가 0, 1, …, 2^n-1로 라벨링되어 있는 버퍼. - Top buffer
: 컬레이션 높이에 따라 사이즈가 증가하는 버퍼.
우선 높이가 i인 컬레이션의 로그(log)들을 배칭(batching)해서 로그 배치 루트(log batch root)를 만듭니다. 이 로그 배치 루트를 Bottom buffer의 (i mod 2^n) 나머지 연산으로 나온 숫자의 값으로 라벨링된 엔트리에 넣습니다. 만약 Bottom buffer의 마지막 엔트리, 즉 2^n-1이라고 라벨링된 엔트리에 로그 배치 루트가 삽입되면, Bottom buffer의 모든 엔트리들은 로그 배치 루트가 삽입된 상태가 됩니다. 그러면 바로 이 모든 엔트리들을 가지고 머클 트리를 만들어서 머클 루트 값인, 배치 해시(batch hash)를 만듭니다. 이렇게 만들어진 배치 해시를 Top buffer에 추가(append)합니다. 즉 Bottom buffer의 모든 로그 배치 루트를 가지고 머클 트리를 만들고, 이 머클 트리의 머클 루트 값을 Top buffer에 추가하는 것입니다.
여기서 중요한 것은 Bottom buffer 마지막 엔트리의 값이 채워질 때에만 witness의 업데이트가 이루어진다는 사실입니다.
Double-batched Merkle Log Accumulator에서의 Membership witness는 pre-witness와 permanent witness를 가집니다.
- pre-witness: 로그 l에서부터 Bottom buffer의 엔트리에 포함된 로그 배치 루트까지의 머클 패스.
- permanent witness: 로그 배치 루트(log batch root)값들로 이루어진 머클 트리에서의 머클 패스와 pre-witness를 묶어서(concatenating) 만들어진 것.
최종적으로 해당 Double-batched Merkle Log Accumulator의 사이즈는 32 * (2^n + h/2^n) 바이트(bytes)가 됩니다. 여기서 h는 컬레이션(collation)의 높이입니다. 예를 들어 컬레이션 인터벌이 8초고 n = 13이라고 가정해보겠습니다. 그럼 Bottom buffer는 250kB의 고정된 사이즈를 갖게 됩니다. 그리고 Top buffer의 크기는 51년이 지나면 750kB가 됩니다.
Justin Drake는 Double-batched Merkle Log Accumulator가 Stateless 클라이언트가 사용할 최적의 Log Accumulator라고 말합니다.
Reference
State-minimised executions
Justin Drake는 Double-batched Merkle Log Accumulator를 기반으로 새로운 컨트랙트 실행 모델인 State-minimised 실행 모델을 제안합니다. 이때 각각의 샤드 체인은 Double-batched Merkle Log Accumulator를 가지며 유저로부터 로그(log)를 받으면 해당 로그를 이 Accumulator에 저장합니다. 이러한 샤드 체인을 로그 샤드(log shard)라고 부릅니다.
이 모델에서는 State-minimised 컨트랙트를 사용합니다. 기존 (stateful한)컨트랙트는 nonce, balance, storageRoot, codeHash를 가지는데 반해 state-minimised 컨트랙트는 storageRoot만을 가집니다. State-minimised 컨트랙트가 저장하는 상태 루트(state root)를 가상 상태 루트(virtual state root)라고 부르고 State-minimised의 상태 변경(state transition)을 가상 상태 변경(virtual state transition)이라 부릅니다. 가상 상태 변경은 다음의 과정을 통해 이루어집니다.
- 유저는 [Log T] 형태의 트랜잭션을 로그 샤드에게 보냅니다. 이러한 트랜잭션을 가상 트랜잭션(virtual transaction)이라고 부릅니다. 보내진 가상 트랜잭션은 로그 샤드의 Double-batched Merkle Log Accumulator에 푸시(push)되어 저장됩니다.
- State-minimised 컨트랙트에 대한 가상 트랜잭션(virtual transaction)이 로그 샤드에 제출되면, executor들은 State-minimised 컨트랙트의 컨펌되지 않은 새로운 가상 상태 루트(virtual state root)를 제안합니다. 여기서 executor는 가상 상태 루트를 새로 제안하는 사람을 말합니다. executor가 가상 상태 루트를 제안하기 위해서는 일정량의 담보물을 예치(deposit)해야 합니다.
- executor가 제안한 가상 상태 루트(virtual state root)는 올바르지 않은(invalid한) 값일 수 있습니다. 이에 대해 누구나 챌린지(challenge)를 신청할 수 있으며, 챌린지가 성공하면 executor는 자신이 예치한 담보물을 잃게 됩니다. 만약 새로 제안한 가상 상태 루트가 챌린지 없이 성공적으로 컨펌되면 executor는 일정 금액의 보상을 얻게 되며 State-minimised 컨트랙트의 가상 상태 루트 값은 변경됩니다.
여기서 주목해야 할 점은 가상 트랜잭션(virtual transaction)을 보낼 때 witness를 함께 보내지 않는다는 점입니다. 왜냐하면 가상 트랜잭션은 기존의 stateful한 노드에서 실행되는 트랜잭션을 기반으로 만들어지기 때문입니다. 즉 executor는 가상 트랜잭션에 대한 트랜잭션을 자신의 노드, 즉 stateful한 노드에서 실행하여 witness 없이도 상태에 접근할 수 있게 됩니다. 따라서 유저는 단지 가상 트랜잭션만을 보내면 됩니다. 기존에 제안된 Stateless 클라이언트 개념에서는 Stateless 클라이언트에 트랜잭션을 보낼 때 항상 witness를 필요로 했습니다.
정리하면, State-minimised exeuction 모델에서 로그 샤드가 저장하고 있는 로그(log)로부터 데이터 가용성(data availability)을 확보하고 있으며, 담보물을 걸고 가상 상태 루트(virtual state root)를 제안하는 것과 같은 방식의 암호경제학적(cryptoeconomic)인 실행(execution) 모델로 데이터 유효성(validity)을 확보하는 것을 확인할 수 있습니다. 이에 더해 유저들이 트랜잭션을 보낼 때 witness 또한 필요로 하지 않습니다.
그리고 executor는 밸리데이터(validator)와 달리 각각의 샤드 체인에 셔플링되어 배정되지 않습니다. executor가 하는 일은 오직 State-minimised 컨트랙트에 대한 컨펌되지 않은 가상 상태 루트를 제공해주는 것입니다. 그렇기 때문에 executor는 자신이 관리하는(또는 관심있어 하는) State-minimised 컨트랙트가 속해 있는 특정 샤드에서만 활동합니다(Ethereum 2.0에서의 각각의 샤드 체인들은 완전히 별개의 어카운트들을 관리합니다.). 즉 executor들은 샤드(로그 샤드) 체인에서 발생하는 가상 트랜잭션(virtual transaction)에 대해 특정 State-minimised 컨트랙트와 관련이 있는 것들만 처리하여 이에 대한 가상 상태 루트를 제공합니다.
Conclusion
Justin Drake는 이와 같은 Double-batched Merkle Log Accumulator와 State-minimised 실행 모델이 샤드 프로토콜 레벨에서 구현될 수 있다고 말합니다. 이를 기반으로 Stateless 클라이언트가 만들어진다면 밸리데이터(validator) 셔플링(shuffling) 과정이 더욱 빨라질 것이고, Stateless 클라이언트를 기반으로 라이트 노드(light node)의 대중화를 이끌 수 있습니다.
