[이더리움2.0 깊이보기 시리즈] Cross Shard Communication — Async [2편]

비동기 샤드 간 커뮤니케이션(Async Cross Shard Communication)

출처 https://nearprotocol.com/blog/unsolved-problems-in-blockchain-sharding/

이더리움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의 핵심은 네트워크를 여러 부분으로 나누어 각 부분이 동시에 서로 다른 거래를 처리할 수 있으며 그로 인해 성능을 획기적으로 끌어올릴 수 있다는 것입니다. 여러 부분으로 나누어진 체인, 즉 샤드 체인은 독립적인 체인으로 각각 별도의 데이터를 저장하고 처리합니다. 하지만 각 샤드 체인이 독립적인 체인으로서의 기능만 한다면 샤드 체인은 별도의 이더리움 체인들이 각각 작동하는 것과 크게 다를 것이 없습니다. 샤드 간 통신(Cross Shard Communication)은 독립적인 샤드 체인을 서로 연결할 수 있는 기술이며 이더리움 2.0을 완성하는 핵심적인 기능이라 할 수 있습니다. 샤드 간 통신(Cross Shard Communication)은 이더리움 2.0 Phase 2에서 구현될 예정이며 현재 구현을 위한 스펙 정의 및 리서치 둘 다 활발히 진행되는 분야입니다.

기차와 호텔 문제(Train and Hotel Problem)

기차와 호텔 문제(Train and Hotel Problem)란 사용자가 기차표를 예약하고 호텔을 예약하는 상황을 가정 했을 때 생길 수 있는 문제입니다. 예를 들어 여행을 가려고 하는 데 여행을 가는 곳은 기차로만 갈 수 있고 숙박할 수 있는 곳은 단 하나의 호텔 밖에 없다고 가정해보겠습니다. 여행을 가기 전에 기차표와 호텔을 예약 했는데 막상 여행을 가니 기차표는 문제 없이 예약이 되었는데 호텔이 예약이 취소가 되버렸습니다. 또는 호텔은 문제없이 예약이 됐는데 기차표가 취소가 되었습니다. 전자라면 기차로 여행지에 도착해도 숙박할 수가 없고 후자라면 아예 여행지에 도착할 수가 없을 것입니다. 두 경우 다 곤란하기는 마찬가지일 것입니다. 따라서 기차와 호텔 문제(Train and Hotel Problem)를 해결하는 방법은 기차표 예약과 호텔 예약이 두 개 다 가능하거나 둘 중 하나가 가능하지 않다면 둘 다 가능하지 않게 해야 합니다.

그럼 샤딩 프로토콜에서 기차와 호텔 문제(Train and Hotel Problem)를 생각해 보겠습니다. 만약 기차 예약 컨트랙트와 호텔 예약 컨트랙트가 같은 샤드에 있다면 이 문제를 해결하는 것은 쉬울 것입니다. 동시에 두 예약을 하는 거래를 보내고 둘 중의 하나가 성공하지 못 했다면 원래 상태로 되돌리게(revert) 만들면 될 것입니다. 하지만 두 개의 예약 컨트랙트가 각자 다른 샤드에 있다면 문제는 단순하지 않습니다. 우선 두 샤드 간에 서로 통신할 수 있는 방법을 만들어야 합니다.

현재 샤드 간 통신(Cross Shard Communication)의 연구 방향은 샤드 간 통신 방식으로 분류하여 비동기 커뮤니케이션 방법과 동기 커뮤니케이션 방법으로 나눌 수 있습니다.

기차와 호텔 문제(Train and Hotel Problem)에서 비동기 커뮤니케이션 모델을 가정한다면 각각 기차표를 예약하고 호텔을 예약한 다음(순서는 중요치 않습니다.) 둘 다 예약 확인이 되었다면 최종적으로 예약이 성공하도록 해야 합니다. 비동기 커뮤니케이션을 가정한 상황에서 예약을 원활히 하기 위해서는 사용자가 기차표를 예약하고 호텔을 예약할 때까지 어느 정도 시간 여유를 주어야 합니다. 기차표 예약과 호텔예약은 순차적으로 이루어지지 않기 때문입니다. 기차표를 예약한다면 일정 기간 동안 다른 사용자의 접근을 제한하거나 여유분을 확보 했을 때 다른 사용자의 예약을 받아야 합니다. 따라서 비동기 커뮤니케이션은 정해진 시간내에 샤드 간 통신이 이루어져야 한다는 가정이 있어야 합니다.

동기 커뮤니케이션은 비동기 커뮤니케이션과는 달리 최종 예약 성공(기차표, 호텔)을 위해 일정 시간을 기다려야 한다는 가정이 필요 없습니다. 하나의 거래로 기차표 예약, 호텔 예약을 처리하는 것입니다. 같은 샤드 체인의 예와 같이 두 예약을 하는 하나의 거래를 보내고 기차표 예약과 호텔 예약 둘 다 성공하면 최종 예약 성공, 하나라도 실패하면 상태를 되돌리게(revert) 됩니다. 하지만 두 개의 샤드 체인간에 이 모델을 어떻게 구현하는 가는 상당히 어려운 문제입니다.

현재 샤드 간 통신(Cross Shard Communication)의 연구 방향은 기차와 호텔 문제(Train and Hotel Problem)에 빗대어 문제를 푸는 방법으로 연구되고 있으며 비동기 / 동기 방식으로 나누어져 있습니다. 지금부터 하나씩 살펴보고 이슈 및 연구 진행방향에 대해 논의해보겠습니다.

Contract Yanking

Contract Yanking이란 Cross Shard Locking Scheme에서 확장하여 기차와 호텔문제(Train And Hotel Problems)를 해결할 수 있는 방법입니다. Cross Shard Locking Scheme의 기본 개념은 샤드 A의 컨트랙트를 “locking”하면 컨트랙트의 상태를 상태 변경 제한(freezing)하여 상태를 Receipt에 저장합니다. 그 다음 receipt을 이용하여 샤드 B로 컨트랙트를 가져와 작업을 수행하고 다시 또 다른 receipt을 생성하여 샤드 A에 컨트랙트를 다시 보내는 것입니다.

Contract Yanking은 locking 개념을 좀 더 확장한 것이라고 볼 수 있습니다. Contract Yanking Scheme에서는 샤드 A의 컨트랙트를 지운 다음, 컨트랙트의 상태(bytecode, storage등)와 거래를 보낼 샤드(target_shard) 정보를 포함한 Receipt을 생성합니다. 그 다음 이 Receipt을 기반으로 샤드 B에서 샤드 A의 컨트랙트를 생성합니다. 샤드 B에서 생성된 컨트랙트에서 임의의 작업을 수행한 후 다시 yanking하여 샤드 A로 보냅니다. 따라서 비동기 방식으로 기차와 호텔 문제(Train And Hotel Problem)을 해결할 수 있습니다.

구현과정에 대한 구체적 예를 들어보면,

EVM opcode에 YANK라는 opcode를 추가할 수 있을 것입니다. YANK는 인자로 하나의 스택(stack) (e.g. target_shard id)을 사용합니다. 호텔 예약 컨트랙트에 reserve()는 호텔 방을 예약하는 함수, move_to_shard(uint256 shard_id)는 다른 샤드로 컨트랙트를 보내는 함수로 구현할 수 있을 것입니다. 따라서 먼저 호텔 예약 컨트랙트에 reserve()함수를 호출하여 호텔을 예약하고 move_to_shard(target_shard)를 호출하여 컨트랙트를 target_shard(기차표 예매 컨트랙트가 있는 샤드 체인)에 “Yanking” 합니다. 더 나아가서 호텔 컨트랙트에 추가로 book()함수를 구현하여 예약(reserve) 이후 대금을 지불하여 확정짓는 단계(예매)를 만들고 self-destruct 하도록 할 수도 있습니다. 컨트랙트를 지운다음 상태를 다시 Receipt에 담아 원래 샤드체인(source_shard)에 보내게 됩니다.

이런 방식으로 비동기적으로 기차와 호텔 문제(Train And Hotel Problems)를 해결할 수 있습니다. 하지만 이를 구현하기 위해서는 ‘Yanking’할 컨트랙트의 상태의 크기가 Receipt에 담을 수 있을만큼 작아야 할 것입니다. 또한 가스비용도 Receipt의 컨트랙트의 상태 크기(저장정보 크기)에 따라 계산할 수 있어야 합니다.

또한 Yanking의 구조상 많은 사용자가 동시에 Yanking 하길 원한다면 거래 처리가 상당히 늦어질 수 있습니다. 만약 기차와 호텔문제(Train And Hotel Problems) 가정 하에서 여러 사용자가 각각의 샤드에 한 명씩 있고 거의 동시에 예약을 원한다면 사용자들은 다른 사용자의 Yanking이 끝나고 일정 시간을 기다린 후(약 6분) 본래 컨트랙트가 있던 샤드 체인에서 다시 Yanking을 하여 예약을 해야 합니다.

이 두가지 문제, 즉 상태 크기와 거래 처리문제로 인해 컨트랙트를 구현할 때는 한명의 상호통신(Interaction)만 가능하도록 상태를 나누는 것도 방법이 될 수 있습니다. 예를 들어 호텔 예약 컨트랙트를 만들어 내는 Factory 컨트랙트를 만들어 필요 시 한명만 상호통신(Interaction)이 가능한 호텔 예약 컨트랙트를 생성하는 것도 방법이 될 수 있습니다.

ETH 2.0 Phase 2 spec

현재 ETH 2.0 Phase 2의 샤드 간 거래(Cross Shard Transaction)에 관한 스펙은 비컨체인(Beacon Chain)의 Cross Shard Receipts를 기반으로 하는 비동기 방식인 Contract Yanking방식입니다. 현재 리서치가 진행되고 있는 분야이기 때문에 변경될 수 있습니다.

Cross Shard Receipts

• target : 타겟 샤드(target shard)와 계정 주소입니다.
  계정 주소의 형식은 다음과 같습니다.
  [1 byte: version number] [2 bytes: shard] [29 bytes: address in shard]
• wei_amount: 전송할 ETH입니다.
• index: receipt마다 부여하는 식별 번호입니다. 이중 지불(Double Spending)을 방지하기 위해 사용됩니다.
• slot: 이더리움 2.0에서는 시간 개념을 도입한 슬롯(slot)을 사용합니다. 하나의 슬롯(slot)에(6초) 하나의 블록을 마이닝(제출)합니다. 블록을 마이닝(제출)하지 않으면 빈 블록을 넣게 됩니다.
• calldata: 거래를 실행하기 위한 함수와 함수가 사용하는 인자를 나타내는 바이트 어레이(byte array)입니다. 컨트랙트의 함수를 호출할 때 사용합니다.
• init_data: “yank”한 컨트랙트를 타겟 샤드에 생성할 때 필요한 정보입니다.

InitiationData

• salt : 타겟 샤드에 컨트랙트 생성시 주소를 만들기 위해 사용합니다
• code : “yank”할 컨트랙트의 바이트 코드(byte code)입니다.
• storage : “yank”할 컨트랙트의 저장 정보입니다.

또한 각 샤드에는 샤드 간 통신을 주고 받는 특별한 컨트랙트가 있습니다.

CROSS_SHARD_MESSAGE_SENDER : 통신을 보내는 컨트랙트로 두 개의 함수가 있습니다.

• Regular Send : 1) target : address, 2) calldata를 인자로 받아 Cross Shard Receipt을 생성합니다.

Cross Shard Receipt은 Regular Send의 인자를 받아 다음과 같이 생성됩니다.

• target=target,
• wei_amount=msg.value,
• index=self.storage.next_indices[target.shard] (생성된 후 1씩 증가합니다. self.storage.next_indices[target.shard] += 1),
• slot=current_slot,
• calldata=calldata,
• init_data=None

여기서 index의 역할은 한번 사용된 Receipt을 재 사용하는 것(이중 지불)을 막기 위해서 입니다.

• Yank : target_shard를 인자로 받아 CrossShardReceipt를 생성합니다.

CrossShardReceipt은 source_shard에 있는 컨트랙트를 삭제하고 target_shard에 컨트랙트 생성에 필요한 바이트 코드(byte code)와 저장정보(storage)를 저장합니다.

• target=Address(0, target_shard, msg.sender),
• wei_amount=get_balance(msg.sender),
• index=self.storage.next_indices[target.shard] (incrementing
• self.storage.next_indices[target.shard] += 1 after doing this),
• slot=current_slot,
• calldata=”’’,
• init_data=InitiationData(0, get_code(msg.sender), get_storage(msg.sender))

CROSS_SHARD_MESSAGE_RECEIVER : CrossShardReceipt, source_shard, Merkle Branch를 인자로 받습니다. Merkle Branch는 데이터 베이스의 정보로서 (key, value)형식의 데이터라고 생각하면 됩니다.

• Merkle Branch가 유효한지 검증합니다. Merkle Branch는 source_shard에서 yanking한 컨트랙트의 상태에 해당하는 Merkle Branch입니다. 이를 이용하여 yanking한 컨트랙트의 상태가 유효한지 검증합니다.
• Merkle Branch를 머클 연산하여 상태 루트 해쉬값을 산출하고 source_shard의 상태 루트 해쉬값과 비교하여 유효한지 검증합니다.
• index를 확인하여 Receipt이 전에 사용된 적이 없는 지 확인합니다. self.current_used_indices[source_shard][receipt.index] == 0

만약 slot이 너무 오래전 이라면 index 비교 대신 추가적으로 이에 대한 Merkle Proof를 제출해야 합니다. 보다 더 자세한 내용을 알고 싶으시면 아래 링크를 참고해 주세요.

https://ethresear.ch/t/cross-shard-receipt-and-hibernation-waking-anti-double-spending/4748

지금까지 비동기 샤드 간 거래 방식을 살펴봤습니다. 또한 Phase 2 Pre Spec에서 어떤 식으로 구현할 지에 대해서도 알아보았습니다. 이 방식은 느린 비동기 샤드 간 거래(Slow Asynchronous Cross Shard Transactions)라고도 불립니다. 거래가 확정되기 위해서는

1) A 샤드에서 컨트랙트 정보를 담은 Receipt을 만들어 B 샤드에 보냅니다.

2) 비컨 체인(Beacon Chain)에 있는 Crosslink(각 샤드의 상태 루트(State Root) 또는 Receipt Root가 저장되어 있습니다. 주기적(약 6분)으로 각 샤드 체인은 비컨 체인(Beacon Chain)에 Crosslink를 올리게 됩니다.) 와 Merkle Branch를 통해 유효성을 검증합니다.

3) B 샤드에서 A 샤드의 Receipt에 따라 컨트랙트를 생성하고 작업을 수행합니다.

4) 또 다른 Receipt을 생성하여 다시 A 샤드에 보냅니다.

5) 그 다음 A 샤드는 비컨 체인(Beacon Chain)의 Crosslink를 확인하여 Receipt의 유효성을 검증할 수 있습니다.

그렇다면 B 샤드에서 컨트랙트에 대한 작업을 수행하고 바로 Receipt을 생성하여 올렸다고 해도 거래가 확정되기 까지는 최소 6분이 필요합니다. 이 가정은 비컨 체인(Beacon Chain)에 Crosslink를 올릴 때 네트워크 지연을 고려하지 않은 가정입니다. 따라서 실제 구현을 위해서 보다 빠르게 만들 필요가 있습니다.

Fast Asynchronous Cross Shard Transactions

빠른 비동기 샤드 간 거래(Fast Asynchronous Cross Shard Transactions)는 기존 느린 비동기 샤드 간 거래(Slow Asynchronous Cross Shard Transactions)를 확장하여 보다 빠른 거래를 하기 위해 제시된 모델입니다.

이 모델에 대한 가정은 다음과 같습니다.

• 샤드 간 호출(Cross Shard Call)은 비동기 방식으로 Receipt에 의해 실행됩니다. 다시 말하면, 이더리움 2.0 Phase 2 현재 스펙인 Contract Yanking 방식을 기반으로 실행됩니다.
• 샤드 간 통신(Cross Shard Communication)을 위해 각 샤드의 상태 루트(State Root)를 검증하는 것 대신 비컨체인(Beacon Chain)에서 전역 상태 루트(Global State Root)를 만들어 검증합니다. (ie. merkle_root([get_state_root(shard=0), … , get_state_root(shard=SHARD_COUNT-1)]))
• 전역 상태 루트(Global State Root)는 비컨 체인(Beacon Chain)에서 해당 블록 높이 N에서 모든 상태루트를 받아야 하므로 대략 1 ~ 2 epoch 정도의 지연시간을 갖습니다. (1 epoch = 약 6분) 비컨 체인(Beacon Chain)에서 전역 상태 루트(Global State Root)를 만들면 각 샤드는 전역 상태 루트(Global State Root)에 접근할 수 있습니다.
• 비컨 체인(Beacon Chain)의 클라이언트에서 전역 상태 루트(Global State Root)를 연산하여 전파하는 것보다 전역 상태 루트 (Global State Root)를 “먼저 예측”할 수 있는 “optimistic”한 방법이 있다고 가정합니다. 우선 일종의 “Crypto Economical Design”을 설계합니다. 간단한 예를 들어 상태 루트(State Root)를 각 노드가 연산하여 검증하는 것과 달리, 각 검증자는 자신이 옳다고 생각하는 상태 루트에 예치금을 걸고 많은 예치금이 걸린 상태 루트가 유효한 상태 루트가 됩니다. “optimistic”한 방법이란 기본적으로 검증하기 위해 상태 루트(State Root) 연산을 매번 하지 않지만, 네트워크에서 잘 못된 상태 루트(State Root)가 있다고 판단될 때에는 (eg. 10%이상의 검증자가 상태 루트가 옳지 않다고 주장하는 경우) 직접 연산을 통해 상태루트를 검증하게 됩니다. 따라서 검증자 혹은 사용자(네트워크에 참여한 누구라도 상관없습니다.)는 상태 루트(State Root)를 직접 연산할 클라이언트를 갖고 있거나(풀 노드), 풀 노드로부터 상태를 가져올 수 있어야 합니다. (라이트 클라이언트) 이에 덧붙여 별도의 트루빗 검증 게임과 같은 시스템을 구현할 수도 있을 것입니다.
• 각 샤드 체인은 비컨 체인(Beacon Chain)의 전역 상태 루트(Global State Root)와 함께 예측 상태루트(Predicted Newer State Roots)를 기록하는 expected_roots를 관리합니다. 예측 상태 루트(Predicted Newer State Roots)는 예상은 되지만(사용자는 자신이 직접 연산하거나 또는 연산결과를 받을 수 있는 능력이 있으므로) 아직 확정되지 않은 상태 루트입니다. expected_roots 목록은 1) 새로운 예측 루트(Predicted Root)가 추가되거나 2) 예측 매커니즘으로 인해 다른 새로운 예측 루트(Predicted Root)로 바뀔 수 있습니다.

이 방식의 핵심은 조건적 상태 개념을 도입하여 구현하는 것입니다. 예를 들어 샤드 B에 있는 Bob이 50 코인을 가지고 있고 샤드 A에 있는 Alice가 Bob에게 20 코인을 전송한다고 하겠습니다. 하지만 샤드 B는 아직 샤드 A의 상태를 모르기 때문에 Alice의 거래가 유효하다고 할 수 없습니다. 따라서 Bob의 상태는 Alice의 거래가 유효하다는 것을 알 때까지 “Alice의 거래가 유효하다면 70 코인, 아니라면 50 코인”이라는 조건적 상태를 가지게 됩니다.

샤드 A의 상태를 검증할 수 있는 클라이언트를 가지고 있는 노드는 이 거래의 확정성(finality)을 거의 즉시 검증할 수 있습니다. 다시 말하면 클라이언트는 샤드 B가 샤드 A의 상태 루트(Alice의 거래가 담긴)를 모르는 상황에서도 거래의 확정성(finality)을 예측할 수 있습니다. 따라서 만약 이러한 클라이언트를 사용하는 지갑 서비스가 있다면 지갑은 Alice의 거래를 거의 즉시 반영해 Bob이 70 coin을 가지고 있는 것처럼 작동할 수 있습니다. 물론 실제로 Bob은 70 coin을 가지게 될 것입니다. 게다가 Bob은 또다른 사용자인 Charlie에게 Alice에게 받은 코인을 바로 전송할 수 있을 것입니다. 물론 Charlie가 받은 코인을 사용하기 위해서는 샤드 A의 상태 루트(State Root)를 검증할 수 있어야 합니다.

그러면 구체적으로 어떻게 작동할 수 있는 지 살펴보겠습니다.

우선 각 계정에 상태가 있다고 가정합니다. 논의의 단순화를 위해 상태는 논스(nonce), 잔고(balance)로 하겠습니다. 각각의 상태는 의존성(dependency)을 가지고 있습니다. 의존성(dependency)은 yes dependency, no dependency, 또는 zero로 구성되어 있습니다. 의존성(dependency)은 (slot, root)로 구성되어 있으며, 의미는 “slot X에서 전역 루트(global root)는 Y이다.” 입니다. 상태는 yes dependency가 expected_roots 목록에 있다면 “활성화(active)”하다고 합니다. 물론 no dependency는 목록에 없어야 합니다.

거래에 따른 상태의 변경은 다음과 같습니다. 1) 거래의 의존성(dependency)이 계정이 갖고 있는 상태(balance)의 의존성(dependency)과 같다면 단순히 상태만 변경됩니다. 2) 만약 거래의 의존성(dependency)이 새로운 것이라면 계정의 상태가 변경되고 의존성(dependency)은 새로운 거래의 의존성(dependency)으로 업데이트 됩니다. 또한 “대안 상태(alternate state)”가 생성되는 데 기존의 yes dependency를 그대로 사용하고 새로운 dependency는 no dependency로 사용하게 됩니다. 상태는 변경되기 전 상태입니다.

예를 들어, Alice라는 계정이 50 코인을 가지고 있다고 하겠습니다. 이 상태의 의존성(dependency)은 “원숭이의 키가 최소한 100cm이상이고 곰은 유럽 사람이 아니다” 입니다. 그 다음 Alice에게 10 코인을 주는 거래를 “원숭이는 최소한 키가 150cm이다”라는 의존성(dependency)과 함께 보냅니다. 그렇다면 Alice의 계정의 상태는 “만약 원숭이의 키가 최소한 150cm이고 곰은 유럽사람이 아니라면 60 코인”이 됩니다. 그리고 계정의 대안 상태(alternate state)는 “만약 원숭이의 키가 최소한 100cm에서 150cm 미만이고 곰은 유럽사람이 아니라면 50코인”이 됩니다.

만약 실제 원숭이키는 130cm라고 한다면 Alice 계정의 상태는 더 이상 활성화(active)되지 않으며 대안 상태(alternate state)가 활성화(active)된 상태가 됩니다.

보다 구체적으로 다른 예를 들어보겠습니다. Bob이라는 계정이 50 코인을 가지고 있고 yes dependency는 (1, DEF)입니다. no dependency는 없습니다. (i.e. {yes: (1, DEF), no: [], balance: 50}) 그리고 expected_roots는 [ABC, DEF]라고 하겠습니다.

Bob에게 10 코인을 전송하는 거래를 보냅니다. 의존성(dependency)은 (1, DEF) 입니다. 거래의 dependency의 루트(root)는 expected_roots 목록에 있고 상태의 yes dependency가 동일하므로 Bob의 상태는 {yes: (1, DEF), no: [], balance: 60} 가 됩니다.

Bob에게 10 코인을 전송하는 다른 거래를 보냅니다. dependency는 (1, MOO) 입니다. 이 거래는 dependency의 상태가 expected_roots 목록에 없기 때문에 거절(reject)됩니다.

expected_roots는 이제 [ABC, DEF, GHI]가 되었습니다. Bob에게 20 코인을 전송하는 거래를 보냅니다. 의존성(dependency)은 (2, GHI)입니다. 새로운 dependency이기 때문에 Bob의 상태는 {yes: (2, GHI), no: [], balance: 80}가 되고 대안 상태(alternate state)는 {yes: (1, DEF), no: [(2, GHI)], balance: 60}가 추가됩니다.

(2, GHI)가 상태가 되돌려져(revert) (2, GHJ)로 새롭게 추가되는 경우를 가정해보겠습니다. Bob의 상태는 더 이상 활성화(active)되지 않습니다.

(3, KLM)이 추가되어 expected_roots 목록은 [ABC, DEF, GHJ, KLM]이 됩니다. 그리고 Charlie는 5 코인을 받습니다. Charlie의 state는 {yes: (3, KLM), no: [], balance: 5}가 됩니다.

(4, NOP)가 추가되어 expected_roots 목록은 [ABC, DEF, GHJ, KLM, NOP]가 됩니다.

만약 Bob이 Charlie에게 5 코인을 보내고 싶다면 Bob은 재구성(reorg) 즉 대안 상태(alternate state)를 주 상태(main state)로 바꾸기 위해 거래를 보냅니다. 따라서 Bob의 상태는 {yes: (1, DEF), no: [(2, GHI)], balance: 60}가 되고 대안 상태(alternate state)는 {yes: (2, GHI), no: [], balance: 80}가 됩니다. 그다음 5코인을 전송하는 거래를 보냅니다. dependency는 (3, KLM)입니다. 그러면 Bob의 상태는 {yes: (3, KLM), no: [(2, GHI)], balance: 55}가 되고 대안상태는 [{yes: (2, GHI), no: [], balance: 80}], {yes: (1, DEF), no: [(3, KLM)], balance: 60}]이 됩니다. Charlie의 상태는 {yes: (3, KLM), no: [], balance: 5}]가 됩니다.

기존의 느린 샤드 간 통신(Slow Cross Shard Communication)은 최소 1 epoch (~약 6분) 정도의 시간을 기다리는 것과는 달리 위 매커니즘을 도입한다면 상태 루트(state root)의 실제 검증을 기다릴 필요없이 상태 루트(state root)를 직접 또는 간접적으로 연산하여 유효한 상태 루트(state root)를 예측할 수 있습니다. 따라서 거래가 확정되길 기다리지 않고 조건적 상태를 기반으로 거래를 확정될 것으로 예측하고 이를 바탕으로 또 다른 거래를 생성할 수 있게 됩니다. 이로써 기존 모델보다 현저히 빠른 샤드 간 거래(Cross Shard Transaction)를 구현할 수 있습니다.

여기서 가정한 “optimistic” 방법은 지연 상태 실행(delayed state execution)이라는 개념에 기반한 방법입니다. 또한 동기적 샤드간 거래(Synchronous Cross Shard Transfers) 구현에 대한 논의도 지연 상태 실행(delayed state execution)개념에 기반을 두고 있기도 합니다. 다음 포스팅에서는 지연 상태 실행(delayed state execution)과 동기적 샤드간 거래(Synchronous Cross Shard Transfers)에 대해 논의하도록 하겠습니다.

Reference

1. Train and Hotel Problem https://github.com/ethereum/wiki/wiki/Sharding-FAQ#what-is-the-train-and-hotel-problem
2. Contract Yanking
   https://ethresear.ch/t/cross-shard-contract-yanking/1450

3. Eth 2.0 Phase 2 pre spec
https://ethresear.ch/t/phase-2-pre-spec-cross-shard-mechanics/4970

4. Fast Asynchronous Cross Shard Transactions
https://ethresear.ch/t/fast-cross-shard-transfers-via-optimistic-receipt-roots/5337