BlockChain Core - Sharding on Blockchain 8

자료 : SoK: Sharding on Blockchain
지난 포스트 - SoK: Sharding on Blockchain 7

---

6 CROSS-SHARD TRANSACTIONS 본문

To scale blockchain, transactions need to be distributed among multiple committees (or shards), and each shard processes a subset of transactions in parallel. Typically, a transaction may have multiple inputs and outputs. However, due to sharding technology, the inputs and outputs of a transac- tion might be in different shards, and these transactions are called cross-shard (or inter-shard) transactions. Due to random distribution of the transactions in sharding proto- cols, a cross-shard transaction can be considered as a global transaction, which should be executed by different shards. To achieve a global consistency among different shards, we need to carefully handle the cross-shard transactions. Taking Unspent Transaction-Output (UTXO) model as an example, it is expected that the majority of transactions (e.g., more than 90% in [91]) are cross-sharded in a traditional model, where UTXOs are randomly assigned to shards for process- ing [100] [55]. For the Account/Balance transaction model, the cross-shard transactions also can reach up to 90% when the number of shards is more than 64 [137].

To enable value transfer between different shards thereby achieving shard interoperability, supporting for cross-shard transactions is crucial in any sharded-ledger system. In this section, we first describe a general transaction model, Un- spent Transaction-Output (UTXO), and present its poten- tial issues in blockchain sharding protocols. Then we dis- cuss potential techniques (e.g., atomic commit) to deal with cross-shard transactions. Finally, we present the state-of-the- art approaches to cope with the cross-shard transactions in sharding.

6.1 Transaction Model

UTXO model is adopted by most blockchain protocols and distributed applications. It represents each step in the evalu- ation of a data object as a separate atomic state of the ledger. Such a state is created by a transaction and destroyed (or “con- sumed") by another unique transaction occurring later [3]. More specifically, in a typical UTXO model, an input repre- sents the value that is to be spent and output represents the new value that is created in response to the input values’ consumption. We can think of inputs and outputs represent- ing different phases of the state of the same asset (e.g., in asset management), where state includes its ownership (or shares). Clearly, an input can be used only once, and stops being considered in the system.

In a UTXO model, input fields implicitly or explicitly refer output fields of other transactions that have not yet been spent. At the validation time, verifiers need to ensure that the outputs referenced by the inputs of the transactions have not been spent and upon transaction-commitment we see them as spent. However, in a multi-shard system, some transac- tions might involve a coordination between multiple shards. Such transactions might require to access or manipulate the state that is handled by different shards. The inter-shard consensus ensures that this takes place consistently and atomically across all involved shards.

A simple but inadequate strawman approach to a cross- shard transaction, is to concurrently send a transaction to all the corresponding shards for processing. However, for a cross-shard transaction, due to the separated verification processes, some shards might commit this transaction while others might abort it. In such a case the UTXOs at the shard who accepted the transactions are lost as there is no straight- forward way to roll back a half-committed transaction, with- out adding exploitable race conditions. Thus, we require to ensure the consistency of transactions between shards, to prevent double spending and to prevent unspent funds from being locked forever.

6.2 Atomic Commit

In multi-shard blockchain, it requires to guarantee the global transactions with the properties of ACID [134]: Atomicity, Consistency, Isolation, and Durability. Atomic Commitment (AC) protocol was intially proposed to handle the global ACID transactions [78]. To ensure the transaction atomicity in a blockchain sharding, we require the participants to agree on one output for the transaction: either commit or abort, but not both.

One of the earliest and most commonly used protocols for atomic commitment is the two-phase commit (2PC) proto- col [74]. In a 2PC protocol, the global transaction manager (or called coordinator node) sends a “prepare" message to all local transactions. The local transactions try to become ready to commit, i.e., reach the ready state. In this state, a local transaction has successfully finished all its actions. To be able to follow a global commit decision, the changes of the local transactions are written to a stable storage. Differ- ent to the committed state, it is still possible to abort a local transaction in the ready state [77]. In other words, the local transaction is able to follow either a global commit or abort decision.

When it is required that every correct participant even- tually reaches an outcome despite the failure of other par- ticipants, the problem is called Non-Blocking Atomic Com- mitment (NB-AC) [11]. Solving this problem enables correct participants to relinquish resources (e.g., locks) without wait- ing for crashed participants to recover. The 2PC algorithm solves AC but not NB-AC, whereas the three-phase commit (3PC) algorithm [121] [122] solves NB-AC in synchronous systems (when communication delays and process relative speeds as bounded). The 3PC protocol introduces an addi- tional pre-commit state between the ready and commit states, which ensures that there is no direct transaction between the non-committable and committable states. This simple modification makes the 3PC protocol non-blocking under node failure. However, compared to the 2PC protocol, the 3PC protocol acts as the major performance suppressant in the design of efficient distributed systems. It can be easily observed that the addition of the pre-commit state leads to an extra phase of communication among the nodes. Thus, it is necessary to design an efficient commit protocol for geo-scale systems.

However, neither 2PC nor 3PC can be directly applied to the blockchain sharding schemes without modification. For different blockchain sharding schemes, they might have different assumptions among the shards, e.g., the trustwor- thiness among shards. A practical cross-shard commit ap- proach depends on its assumptions and the threat models used. For example, Interledger [130] protocol enables trans- fers between ledgers, and ledger-provided escrow removes the need to trust these connectors (e.g., each connector func- tions as a trusted third party to provide the service to the payment sender [81]). Analogized to the blockchain shard- ing scheme, it assumes that different shards (or alternatively blockchain) that we want to perform atomic transactions across are mutually distrustful, e.g., one might fail to be secure and/or live. The mutual distrusts can further lead to DoS “account lockout" attacks, which is why all these Interledger-type protocols require complex timeout-based recovery mechanisms. In contrast, OmniLedger relies on the fact that all shards can be assumed “by construction" to be both safe and live, which means that the simple 2PC approach works fine in that context, and the NB-AC problem does not need to be solved in that threat model. But in Om- niLedger the shards have to trust each other. If we weaken the security of OmniLedger’s shard selection so that shards no longer fully trust each other, then we need to bring back more complex cross-shard commit protocols.

Thus, for different blockchain sharding schemes, they might have different mechanisms to deal with the the cross- shard transactions. We will discuss these different solutions for specific sharding schemes.

6.3 Methods to Deal with Cross-shard Transactions

Instead of presenting all possible AC protocols, this section presents several state-of-the-art schemes to deal with cross- shard transactions. Some of these schemes do not use the term “shard" but instead using “committee" to deal with the cross-committee transactions, both have the same meaning, i.e., one transaction involving multiple independent entities. However, some sharding protocols, such as Elastico, do not provide a clear or separated process to deal with the cross- shard transactions.

1) RSCoin
RSCoin [55] is a cryptocurrency framework in which central banks maintain complete control over the monetary supply, but rely on a distributed set of authori- ties, or mintettes, to prevent double-spending. The mintettes process the lower-level blocks, which form a potentially cross- referenced chain. The communication between committee members takes place indirectly through the client, and it also relies on the client to ensure completion of the transactions. A client first gets signed “clearance" from the majority of the mintettes that manage the transaction inputs. Next, the client sends the transaction and signed clearance to mintettes cor- responding to transaction outputs. The mintettes check the validity of the transaction and verify signed evidence from input mintettes that the transaction is not double-spending any inputs. If the checks pass, the mintettes append the trans- action to be included in the next block. The system operates in epochs: at the end of each epoch, mintettes send all cleared transactions to the central bank, which collates transactions into blocks that are appended to the blockchain.
However, client/user-driven atomic commit protocols are vulnerable to DoS if the client stops participating and the inputs are locked forever. These systems assume that clients are incentivized to proceed to the unlock phase. Such incen- tives may exist in a cryptocurrency application where an unresponsive client will lose its own coins if the inputs are permanently locked, but do not hold for a general-purpose platform where inputs may have shared ownership. Besides, RSCoin relies on a two-phase commit protocol executed within each shard which, unfortunately, is not Byzantine fault tolerant and can result in double spending attacks by a colluding adversary.

2) Chainspace
Chainspace [2] is a recently proposed, sharded smart contract platform with privacy built in by design. To enable scalability on Chainspace, the nodes are organized into shards that manage the state of objects, keep track of their validity, and record transactions committed or aborted. The nodes ensure that only valid transactions, consisting of encrypted or committed data, along with the zero-knowledge proofs that assert their correctness, end up on their shard of the blockchain. The nodes communicate with the other shards to decide whether to accept or reject a transaction via inter-shard consensus. Instead of a client- driven approach, Chainspace runs an atomic commit proto- col collaboratively between all the concerned committees. This is achieved by making all the committees act as a re- source manager for the transactions they manage. To do this, Chainspace proposes a protocol called Sharded Byzantine Atomic Commit or S-BAC, which combines existing Byzan- tine agreement and atomic commit protocols in a novel way. In S-BAC Byzantine agreement securely keeps a consensus on a shard of 3f + 1 nodes in total, containing up to f ma- licious nodes. Atomic commit runs across all shards that contain objects which the transaction relies on. The transac- tion is rejected unless all of the shards accept to commit the transaction.

3) OmniLedger
OmniLedger [91] uses a Byzantine shard atomic commit (Atomix) protocol to atomically process trans- actions across committees, such that each transaction is ei- ther committed or aborted. Since both deploying atomic commit protocols and running BFT consensus are unnec- essarily complex, atomix uses a lock-then-unlock process. OmniLedger intentionally keeps the shards’ logic simple and makes any direct shard-to-shard communication unneces- sary by tasking the client with the responsibility of driving the unlock process while permitting any other party (e.g., validators or even other clients) to fill in for the client if a spe- cific transaction stalls after being submitted for processing. Atomix takes a three-step (initialize/lock/unlock) protocol to deal with cross-shard UTXO transactions. More specifically, the client first gossips the cross-shard transactions to all their input shards. Then, OmniLedger takes a two-phase ap- proach to handle atomic commit, in which each input shard first locks the corresponding input UTXO(s) and issues a proof-of-acceptance, if the UTXO is valid. The client collects responses from all input committees and issues an “unlock to commit" to the output shard. Interested readers are referred to [91] for the details.
Both OmniLedger and RSCoin heavily rely on the client to proceed with the cross-shard transactions, thus both pro- tocols assume that the client is the honest part. Typically, OmniLedger allows the output committee to verify transac- tions independently; the transactions have to be gossiped to the entire network and one proof needs to be generated for a batch of transactions, potentially incurring some communi- cation overhead. Besides, OmniLedger depends on the client to retrieve the proof which incurs extra burden on typically lightweight client nodes.

4) RapidChain
In RapidChain [141], the user does not attach any proof to transaction. It lets the user commu- nicate with any committee who routes transaction to its output committee via the inter-committee routing protocol. RapaidChain considers a simple UTXO transaction tx =< (I1, I2), O > that spends coins I1, I2 in shard S1 and S2, re- spectively, to create a new coin O belonging to shard S3. The RapidChain engine executes tx by splitting it into three sub-transactions: txa =< I1, I1′ >, txb =< I2, I2′ >, and txc =< (I1′, I2′), O >, where I1′ and I2′ belong to S3. txa and txb essentailly transfer I1 and I2 to the output shard, which are spent by txc to create the final output O. All thress sub- transactions are single-shard. In case of failures, when, for example, txb fails while txa succeeds, RapidChain sidesteps atomicity by informing the owner of I1 to use I1′ for future transactions, which has the same effect as rolling back the failed tx. The cross-shard transaction in RapidChain has largely relied on the inter-committee routing scheme which enables the users and committee leaders to quickly locate to which committees they should send their transaction. To achieve this, RapidChain builds a routing overlay net- work, at the committee level, which is based on a routing algorithm of Kademlia [104]. Specifically, each RapidChain committee maintains a routing table of loд(n) records which point to loд(n) different committees which are distance 2i for 0 ≤ i ≤ loдn − 1 away.
For cross-shard transactions in RapidChain, one drawback is that, for each transaction, it creates three different transac- tions to exchange information among shards. This inherently increases the number of transactions to be proceeded, and the communication by sending the extra transactions back to its input committees also increases. It uses the committee’s leader to produce these transactions without considering the status of a leader (e.g., malicious leader). Also, the input com- mittees include the created new transaction into its leader. This behavior to some extent modifies the originality of trans- actions. Besides, the cross-shard transaction largely depends on the routing algorithm, which is a potential bottleneck.

5) Discussion
Sharding protocols reduce the communi- cation, computation and storage requirements of each node by dividing the blockchain into partitions, each stored by one of the committees. The cross-shard transactions, however, makes the verification more challenging. Thus, an efficient mechanism to deal with the cross-shard transactions is cru- cial in the design of a practical blockchain sharding protocol.
Intuitively, there exist some fallacies about the client (who is a coordinator to handle cross-shard transactions) or the shard consensus leader. Taking OmniLedger and RSCoin as examples, one fallacy is that if the client performs some malicious behaviors, then the protocol could not proceed suc- cessfully. This is not the fact. Both RSCoin and OmniLedger have backup “garbage collection" strategies that enable the ledger (or other clients) to complete or abort cross-shard transactions that failed or malicious clients might leave un- completed. It is not a complicated process, and just a matter of ensuring that the “lock" phase records all the cross-shard transaction information that a future garbage-collector or other interested client needs to complete or abort the trans- action that has an account of interest locked. Another fallacy is that the OmniLedger uses the leader of a shard to issue and indicate acceptance or rejection; this might involve some problems, especially if the leader is a malicious one. This is also not true. An OmniLedger shard’s leader is merely the leader of a PBFT-sytle Byzantine consensus group, and has no power to carry out any (malicious) behaviors itself with- out getting them validated by a majority of honest nodes within the same group. In other words, the “accept" or “re- ject" decision, like all decisions that an OmniLedger shard makes, are products of (and layered on top of) the PBFT state machine, and thus will always be “correct" and “honest” and “non-malicious" because of PBFT, unless the system’s basic security invariants are broken, e.g., leading to fully- compromised with too many corrupted nodes.
How to efficiently handle the cross-shard transactions is a fundamental topic in most blockchain sharding proto- cols. When designing an efficient mechanism to deal with cross-shard transactions, it requires to consider several sig- nificant factors, e.g., the atomic commitment scheme within the shard, the communication complexity among the shards (e.g., the number of message exchanges), and the transac- tion model. Technically, the transaction model affects the cross-shard transaction mechanism significantly. We should notice that for different applications, they might adopt dif- ferent transaction models. Currently, most of the state-of- the-art sharding protocols are still based on the traditional cryptocurrency-based UTXO model. However, for different transaction models, it might result different storage require- ments [135] [136].

Besides the garbage-collection mechanisms, there exist some blockchain protocols, such as SideCoin [92] and Roller- Chain [43], utilizing the distributed state snapshotting mech- anism [40] to record the blockchain’s recent status. And this state snapshotting mechanism can be applied into sharding blockchain, e.g., RapidChain, to check the cross-shard trans- actions much quicker, and it also can be used to reconfigure the committees of next epoch.

6 CROSS-SHARD TRANSACTIONS

블록체인을 확장하려면 트랜잭션을 여러 committee(또는 샤드)에 분산하고, 각 샤드는 병렬로 일부 거래를 처리한다.

일반적으로 트랜잭션에는 입력과 출력이 있는데, 샤딩 기술로 인해 트랜잭션의 입력과 출력이 다른 샤드에 있을 수 있으며, 이러한 트랜잭션을 크로스-샤드(또는 인터-샤드) 트랜잭션이라고 한다.

• 한 샤드에서 발생한 트랜잭션이 다른 샤드의 데이터에 영향을 미치는 트랜잭션

  이 크로스-샤드 트랜잭션의 처리 시간을 줄이고 네트워크 트래픽을 감소시키는 것이 관건.

이 섹션에서는

먼저 일반적인 트랜잭션 모델인 Unspent Transaction-Output (UTXO)를 설명하고,

블록체인 샤딩 프로토콜에서의 잠재적인 문제점을 소개한다.

그런 다음, 크로스-샤드 거래를 처리하기 위한 기술(예: 원자적 커밋)을 논의.

샤딩에서 크로스-샤드 트랜잭션을 처리하기 위한 최신 기술 접근 방식을 제시한다.

6.1 Transaction Model

UTXO 모델은 대부분의 블록체인 프로토콜과 분산 애플리케이션에서 사용되는 모델이다.

UTXO는 데이터 객체의 각 단계를 별개의 상태로 표현한다. 이 상태는 트랜잭션을 통해 생성되고, 나중에 다른 트랜잭션에 의해 소비되거나 사용된다.

• 입력 : 사용될 값
• 출력 : 입력 값의 소비로 생성되는 새로운 값

멀티 샤드 시스템에서 중요한 부분

크로스 샤드 같은 멀티샤드 시스템에서는 샤드 간 일치가 필수적인 요소이다.샤드 간 일치가 없으면, 각 샤드의 상태가 독립적으로 유지될 수 있습니다. 이는 이중 지출과 같은 보안 문제로 이어질 수 있기 때문이다.

따라서 UTXO 모델에서도 트랜잭션이 유효한지 확인하기 위해서는 각 샤드의 상태가 일관되게 유지되어야 한다.

크로스 샤드 트랜잭션은 여러 샤드에 걸쳐 발생하므로, 각 샤드에서 트랜잭션을 검증하고 커밋하는 방식은 일반적인 트랜잭션과 다르다. 따라서, 크로스 샤드 트랜잭션의 일관성을 보장하기 위해서는 컨센서스 메커니즘을 사용하여 각 샤드에서 트랜잭션을 일관되게 검증하고 커밋해야 한다. 이는 이중 지불을 방지하고 미지급 자금이 영원히 잠기지 않도록 하기 위함이다.

---

6.2 Atomic Commit

멀티샤드 블록체인에서는 ACID [134]의 속성을 가진 글로벌 트랜잭션을 보장해야 한다.

ACID는 원자성(Atomicity), 일관성(Consistency), 격리성(Isolation), 지속성(Durability)

원자적 커밋 프로토콜은 글로벌 트랜잭션을 처리할 때 ACID 속성을 보장하는 방법 중 하나이다. 원자적 커밋 프로토콜을 사용하면, 모든 참가자가 트랜잭션을 성공적으로 커밋하거나 모두 실패하도록 보장할 수 있다.

원자적 커밋을 달성하기 위해 가장 일반적으로 사용되는 프로토콜은 ‘2단계 커밋(2PC)’ 프로토콜이다.

2PC 프로토콜

2PC 프로토콜은 원자적 커밋을 달성하기 위한 프로토콜이다.

원자적 커밋의 ‘모든 참가자가 트랜잭션을 성공적으로 커밋하거나 모두 실패하는 것’을 보장하기 위해서 2PC 프로토콜이 사용되는데, 이 프로토콜은 두 단계로 진행된다.

2PC 프로토콜의 두 단계

1. 준비 단계:

   글로벌 트랜잭션 관리자(대장 노드)는 모든 로컬 트랜잭션에 준비 메시지를 보낸다. 로컬 트랜잭션은 커밋할 준비가 되도록 시도한다. 즉, 준비 상태에 도달한다.

   이 상태에서 로컬 트랜잭션이 모든 작업을 성공적으로 완료하게 되면, 글로벌 커밋 결정을 따를 수 있도록 로컬 트랜잭션의 변경 사항은 안정적인 저장소에 기록된다.

2. 커밋/중단 단계:

   로컬 트랜잭션은 커밋 또는 중단 결정을 전달한다.

3PC 프로토콜

3PC는 2PC에 한 단계가 추가된 프로토콜이다.

3PC 프로토콜의 세 단계

1. 준비 단계:

   글로벌 트랜잭션 관리자는 모든 로컬 트랜잭션에 준비 메시지를 보낸다. 로컬 트랜잭션은 커밋할 준비가 되도록 시도한다. 즉, 준비 상태에 도달한다.

   이 상태에서 로컬 트랜잭션이 모든 작업을 성공적으로 완료하게 되면, 글로벌 커밋 결정을 따를 수 있도록 로컬 트랜잭션의 변경 사항은 안정적인 저장소에 기록된다.

2. 커밋/중단 단계:

   로컬 트랜잭션은 커밋 또는 중단 결정을 전달한다.

3. 완료 단계:

   글로벌 트랜잭션 관리자는 모든 로컬 트랜잭션의 결정을 확인한다. 모든 로컬 트랜잭션이 커밋을 선택한 경우 글로벌 트랜잭션 관리자는 커밋을 완료한다. 모든 로컬 트랜잭션이 중단을 선택한 경우 글로벌 트랜잭션 관리자는 중단을 완료한다.

3PC 프로토콜은 2PC 프로토콜에 비해 성능이 향상되지만 구현이 복잡하다. 따라서, 효율적인 3PC 프로토콜을 설계하는 것은 어려운 과제다.

Non-Blocking Atomic Commitment

원자적 커밋 (AC)은 모든 참가자가 트랜잭션을 성공적으로 커밋하거나 모두 실패하는 것을 보장해야 하는데, 트랜잭션을 보내는(or 받는) 사용자가 여러가지의 문제로 실패할 경우가 있다. 그럴 때 문제가 있는 사용자가 해결할 때까지 기다릴 수 없다.이러한 상황(문제)을 Non-Blocking Atomic Commitment(비 블록킹 원자적 커밋)이라고 한다.

NB-AC 예시

• 모든 참가자가 다른 참가자의 실패에도 불구하고 결국 결과에 도달해야 하는 경우
• 올바른 참가자가 중단된 참가자가 복구되기를 기다리지 않고 자원 (예: 잠금)을 포기해야 하는 경우

‼️ 논문(and Bard)에서는 2PC가 NB-AC를 해결하지 못한다고 나오는데, ChatGPT에서는 3PC가 추가적인 메시지 교환과 복잡성을 도입하여 구현이 상대적으로 복잡하고 오버헤드가 증가할 수 있기 때문에 주로 2PC로 Non-Blocking Atomic Commitment(비 블록킹 원자적 커밋)을 해결한다고 나온다.

---

블록체인 샤딩 방식은 여러 개의 샤드로 분산되어 있기 때문에 2PC와 3PC를 블록체인 샤딩 방식에 직접적으로 적용할 수 없다.

2PC와 3PC는 모든 참가자가 트랜잭션을 성공적으로 커밋하거나 모두 실패하는 것을 보장할 수 없다. 즉, 수정해야 함.

따라서, 서로 다른 블록체인 샤딩 방식은 크로스샤드 거래를 처리하기 위해 다른 메커니즘을 가질 수 있다.

6.3 Methods to Deal with Cross-shard Transactions

이 섹션에서는 크로스 샤드 트랜잭션을 처리하기 위한 최신 방식을 몇 가지 제시한다.

1) RSCoin

RSCoin은 중앙 은행이 통화 공급을 완전히 통제하면서도 이중 지출을 방지할 수 있는 암호 화폐 프레임워크이다.

RSCoin은 민트 에이전트라는 분산된 집단의 권한을 사용하여 트랜잭션을 처리한다.

민트 에이전트가 블록에 트랜잭션 추가하는 단계

• 트랜잭션의 유효성을 검사.
• 입력 민트 에이전트로부터 서명된 증거를 확인하여 트랜잭션이 이중 지출되지 않음을 확인.
• 만약 모든 검사가 통과하면, 민트 에이전트는 다음 블록에 포함되도록 트랜잭션을 추가

RSCoin 시스템은 주기(단계별)로 작동하며, 각 주기의 끝에서 민트 에이전트는 모든 승인된 트랜잭션을 중앙 은행으로 보낸다. 중앙 은행은 블록체인에 추가되는 블록으로 트랜잭션을 수집하게 된다.

클라이언트/사용자 주도형 원자적 커밋 프로토콜(client/user-driven atomic commit protocol)

RSCoin은 클라이언트/사용자 주도형 원자적 커밋 프로토콜을 사용한다.

클라이언트/사용자 주도형 원자적 커밋 프로토콜은 클라이언트 또는 사용자가 주도하여 원자적 커밋을 관리하는 방식을 의미하며, 분산 시스템에서 트랜잭션 처리와 커밋 결정을 클라이언트 레벨에서 수행하는 방식이다.

클라이언트는 각 참여자(서버, 데이터베이스 등)와의 상호작용을 통해 트랜잭션을 시작하고 커밋 여부(트랜잭션의 성공 또는 실패)를 결정한다.

• 장점: 클라이언트가 주체적으로 트랜잭션의 처리 및 커밋 여부를 결정하므로, 특정 참여자의 장애나 지연으로 인해 전체 시스템이 블록되는 상황을 방지할 수 있다.
  • 분산 시스템에서 블록킹 현상을 최소화
  • 응답성과 유연성을 향상시킬 수 있다.
• 단점: 클라이언트가 참여를 중단하고 입력이 영원히 잠기면 시스템이 작동하지 않는다.
  • DoS 공격에 취약
  • 비잔틴 내결함성이 아니기 때문에 공모한 공격자에 의해 이중 지출 공격을 받을 수 있다.

2) Chainspace

Chainspace는 분산된 스마트 컨트랙트 플랫폼으로, 높은 처리량과 확장성을 제공하기 위해 설계되었으며, 안전하고 신뢰할 수 있는 스마트 컨트랙트 실행 환경을 제공하는 것을 목표로 한다.

• 여러 개의 노드로 구성된 네트워크에서 동작하며, 각 노드는 분산 저장소에 저장된 블록체인 데이터를 공유
• 스마트 컨트랙트를 프로그래밍하고 실행하는 데 사용되는 특수한 언어를 제공(언어의 이름이 따로 명시되지 않음)
  • 코드 예시

    // 경매(Auction)를 관리하는 컨트랙트
    contract Auction:
        state highestBidder: address
        state highestBid: int
      
        entrypoint initialize(bidder: address, bidAmount: int):
            highestBidder = bidder
            highestBid = bidAmount
      
        entrypoint placeBid(bidder: address, bidAmount: int):
            if bidAmount > highestBid:
                highestBidder = bidder
                highestBid = bidAmount
      
        entrypoint getHighestBid() -> (address, int):
            return (highestBidder, highestBid)
  

• 비교적 낮은 지연 시간과 빠른 트랜잭션 처리 속도를 제공하여 실시간 응용 프로그램 및 대규모 트래픽 처리에 적합
• 데이터의 안전성과 무결성을 유지하기 위해 암호화 및 합의 알고리즘을 사용

Sharded Byzantine Atomic Commit(S-BAC) 프로토콜

Chainspace는 클라이언트 주도형 접근 방식 대신 모든 관련 위원회 간에 공동으로 원자적 커밋 프로토콜을 실행한다.

모든 위원회가 관리하는 트랜잭션의 리소스 관리자 역할을 하도록 함

• S-BAC에서 비잔틴 합의는 총 3f + 1개의 노드로 구성된 샤드에서 안전하게 합의를 유지
• 원자적 커밋은 트랜잭션이 의존하는 객체를 포함하는 모든 샤드에서 실행
• 모든 샤드가 트랜잭션을 커밋하기로 동의하지 않는 한 트랜잭션은 거부

일단 비잔틴 합의를 거친 후 → 모든 샤드가 커밋하기로 동의해야 한다는 것.

3) OmniLedger

OmniLedger는 블록체인을 확장하기 위해 개발된 프로토콜이다.

OmniLedger에서는 비잔틴 샤드 원자적 커밋 프로토콜인 Atomix 프로토콜을 사용한다.

Atomix 프로토콜

Atomix 프로토콜은 크로스 샤드 UTXO 트랜잭션을 원자적으로 처리하기 위해 간단한 두 단계 프로세스를 사용한다.

1. 클라이언트가 모든 입력 샤드에 트랜잭션을 전파

   각 입력 샤드는 유효한 경우 먼저 해당 입력 UTXO(들)를 잠그고 승인 증명을 발급한다.

2. 클라이언트가 모든 입력 위원회의 응답을 수집하고 출력 샤드에 “해제하여 커밋”을 발행

   출력 샤드는 모든 입력 위원회가 트랜잭션을 승인하면 트랜잭션을 커밋한다.

OmniLedger와 RSCoin은 모두 크로스 샤드 트랜잭션을 진행하기 위해 클라이언트에 크게 의존하므로, 두 프로토콜 모두 클라이언트가 정직하다고 가정한다. (Chainspace와는 다름)

4) RapidChain

RapidChain은 블록체인에서의 거래 처리 속도와 확장성을 향상시키기 위한 목적으로 설계된 프로토콜이다.

RapidChain 특징

• 여러 개의 샤드(shard)로 구성

  샤드는 독립적으로 작동하는 하위 체인으로 생각할 수 있다. 각 샤드는 일부 거래를 처리하고, 해당 샤드의 원장에 기록한다. 이를 통해 전체 네트워크의 부하를 분산시키고, 트랜잭션 처리량을 증가시키는 것이 가능하다.

• 크로스-샤드(cross-shard) 거래를 처리하기 위해 인터 위원회 라우팅 메커니즘을 사용

  RapidChain은 크로스-샤드 거래를 효율적으로 처리하기 위해 다양한 기술과 알고리즘을 도입한다. 예를 들어, 거래 정보를 샤드 간에 교환하기 위해 리더(leader) 기반의 메커니즘을 사용하며, 샤드 간의 거래 일관성을 유지하기 위해 라우팅 알고리즘을 활용한다.

• RapidChain의 크로스-샤드 트랜잭션의 단점

  • 각 트랜잭션마다 세 개의 다른 트랜잭션을 생성하여 샤드 간에 정보를 교환한다는 점
    • 이로 인해 처리해야 할 트랜잭션 수가 증가하며, 추가 트랜잭션을 입력 위원회로 다시 보내는 통신도 증가한다.
    • 트랜잭션 생성은 위원회 리더를 사용하여 이루어지며 (악의적인 리더와 같은) 리더의 상태를 고려하지 않는다.

인터 위원회 라우팅(inter-committee routing) 프로토콜

인터 위원회 라우팅 프로토콜은 사용자가 트랜잭션에 증명을 첨부하지 않는 대신 트랜잭션을 출력 위원회로 라우팅하는 위원회와 통신할 수 있다.

• UTXO(미사용 거래 출력) 모델을 사용하여 트랜잭션을 처리

  • 요런 느낌- (입력)기존의 샤드에 속한 동전이 소비되면, (출력)결과로 새로운 동전이 생성된다.

    예를 들어, 하나의 거래에는 S1과 S2라는 두 개의 샤드에 속한 동전(I1, I2)이 소비되고, 그 결과로 S3 샤드에 속하는 새로운 동전 O가 생성된다.

    

  • RapidChain은 이러한 거래를 세 개의 하위 거래로 분할하여 처리.

    • 첫 번째 하위 거래인 txa는 동전 I1을 소비하고 I1’을 생성
    • 두 번째 하위 거래인 txb는 동전 I2를 소비하고 I2’을 생성
    • 세 번째 하위 거래인 txc는 I1’과 I2’를 소비하고 O를 생성
    • 이러한 하위 거래는 각각 단일 샤드에서 실행
• 트랜잭션 실패 시 - 원자성 유지는 어떻게?
  • 만약 txa가 성공하고 txb가 실패하는 경우,
  • RapidChain은 txb가 실패한 거래를 되돌리는 대신, I1의 소유자에게 I1’을 사용하도록 안내
  • 이렇게 함으로써 거래의 원자성을 유지할 수 있습니다.

---

다음에 계속…