[IMPACT]
Blockchain scalability solution: A region-based sharded network
Terms Definitions
Home shard: The autonomous region where a particular address is created in the sharded model. Usually, the address is used as a TxIn address within its home shard region.
Visited shard: When users travel long distances, they can make transactions using their TxIn addresses away from their home shard regions. The transaction request that occurs in the visited shard region is delivered to the node of the home shard region of the TxIn address of the transaction. Therefore, all transactions are processed only in Home Shard, regardless of where they occur.
State: a set of information representing the "current state" of a system; determining whether or not a transaction is valid and the effect should depend only on the state. Examples of state data include the UTXO set.
History: an ordered list of all transactions that have taken place since genesis. In a simple model, the present state should be a deterministic function of the genesis state and the history. Historical data include the cross-Shard-Chain (CSC) and the shard chains.
Transaction: a transaction represents an operation that some user wants to make and is cryptographically signed. In some systems, transactions are called blobs to emphasize that these objects may mean an attempt to operate between the TxIn address and TxOut address.
State transition function: a function that takes a state, applies a transaction and outputs a new state. The computation involved may involve adding and subtracting balances from accounts specified by the transaction, verifying digital signatures, and running contract code.
Merkle tree: a cryptographic hash tree structure that can store a massive amount of data, where authenticating each piece of data only takes O(log(n)) space and time. The transaction set of each Block and the state are kept in a Merkle tree, where the roots of the trees are committed to in a block.
Top-level node: processes cross-shard chain. It does not download all data in the shard chains.
Shard Node (regional node): Processes the shard chain for a specific shard region. Shard Nodes fully download the cross-shard chain to stay in sync.
What is the basic idea of the proposed sharding to start?
Divide the state and history into K = O(n/c) partitions called "shards," where c is the average number of nodes per shard and n is the total number of nodes. So it means there are K total shards. However, defining a shard is different from the existing sharding method. It uses the Region-based Sharding method, which divides the world into regions and allows one shard to take charge of the area, rather than the existing database partitioning method. Nodes in the same region belong to the same shard. For example, if the world is divided into 64 shard regions, the proposed sharding scheme puts all addresses starting with 0x000000 into the first shard (shard 1) and all addresses starting 0x000001 into the second shard (shard 2). Finally, all addresses starting with 0x111111 are assigned to the last shard (shard 64). Therefore, in this proposal, a transaction is processed in either Home-Shard or Visited-Shrad. Assuming that a user initially created a wallet within the Shard 4 region, all addresses created in this wallet starting with 0x000011. When this user moves to the Shard 5 region and tries to issue a transaction, the node in that shard region considers the transaction' Visited-Shard.'
.
Every transaction belongs to a specific shard region based on the transaction's input address (TxIn Addr).
The home shard region is defined as the shard region where a certain TxIn Addr is created.
If the address is used as an input address by moving to another shard region, the moving area becomes the visited shard region.
Mobility must be ensured to visit other shard regions with freedom. That is shard roaming in the use of cryptocurrency.
Therefore, by TxIn address, the home shard region is tracked when a transaction arrives at an L1 node. Accordingly, the transaction issued in the foreign shard region is relayed to its home shard region.
The address mapping table describes the transport addresses of all the regional nodes in the corresponding shard region.
(See Figure 1)
Division of roles for 'Parallel Writes'
If a user tries to make a transaction by visiting a foreign shard region, the transaction should be passed to one of the L1 nodes in its Home shard region. Therefore, as the user's mobility increases, roaming transaction traffic increases.
Since all transactions are processed in the Home Shard area based on the TxIn address, 'Parallel Writes' for each node is possible.
The second important concept in the sharding structure is that when a node processes a transaction, it classifies the transaction into an intra-shard transaction and a cross-shard transaction and processes it.
Therefore, when a node of the Home Shard region starts to process a transaction with TxIn and TxOut addresses, it determines whether the TxOut address is within the same shard of the TxIn address or not.
If the TxIn and TxOut addresses exist in the same shard region, this transaction is considered intra-shard.
On the other hand, if the TxIn and TxOut addresses exist in different shard regions, this transaction is considered an inter-shard transaction. Intra-shard transactions are directed to Intra UTMP (Unconfirmed Transaction Memory Pool), and inter-shard transactions are directed to Inter UTMP.
(See Figure 2)
Fork-less Proof of Stake (FLPoS)
Confirmation of validator registration process and new Collation of shard chain
All constituent nodes within the same shard will have intra-shard transactions sent from the L1 nodes of that shard region. Then, each shard node will have a full copy of collected intra-shard transactions.
Next, as a volunteer of the validator, each local node broadcasts a message consisting of [Node ID, Merkle Hash, Staking Permit, Nonce] to confirm the intent of all regional nodes to participate in collation creation. Merkle Hash is the hashed value for the collected intra-shard transactions in a Merkle tree. Confirmation is that if the number of participating nodes with the same Merkle hash value exceeds 60% of the total number of volunteer nodes, the local node with the same Merkle Hash becomes a validator node allowed to participate in collation creation. Each validator node with the same Merkle Hash consumes identical amounts of computing power to find solutions to the soft mathematical puzzle.
Let's assume that validator node allowed to participate in collation creation are Node1, Node 2, …, Node k, and their Nonce values are Nonce (Node1), Nonce (Node 2), …, Nonce(Node k). After applying the hash function while changing from Nonce(Node 1) to Nonce(Node k ), each validator node computes CollationHash(Node 1), CollationHash(Node 2), …, CollationHash(Node k). The validator node with the smallest hash value becomes the final collation creation node, the leader node. Suppose CollationHash(Node 3) is the smallest hash value, the Collation with Nonce(Node 3). created by Node 3 is confirmed as a new Collation of the shard chain.
This idea removes the latency of collation propagation times and allows rapid collation synchronization. As a result, each regional node can update its shard chain quickly.
(See Figure 3)
Confirmation of validator registration process and new Block of Cross-shard chain
First, each TL node will have a full copy of collected cross-shard transactions.
Next, as a volunteer to become a validator node for the Cross-Shard chain, each TL node broadcasts a message of [Node ID, Merkle Hash, Staking Permit, Nonce] to confirm participating in new block creation. Merkle Hash is the hashed value for the collected cross-shard transactions in a Merkle tree. The process of validator confirmation is that if the number of participating TL nodes with the same Merkle hash value exceeds 60% of the total number of volunteer TL nodes, the volunteer TL node with the same Merkle becomes a validator node allowed to participate in block creation.
Let's assume that validator node allowed to participate in collation creation are Node1, Node 2, …, Node n, and their Nonce values are Nonce (Node1), Nonce (Node 2), …, Nonce(Node n). After applying the hash function while changing from Nonce(Node 1) to Nonce(Node n ), each validator TL node computes BlockHash(Node 1), BlockHash(Node 2), …, BlockHash(Node n). The node with the smallest hash value becomes the final block creator node. If BlockHash(Node 5) is the smallest hash value, the Block with Nonce(Node 5 ) created by TL node five is confirmed as a new block of the Cross-shard chain.
The Fork-less PoS eliminates the process of new block synchronization because each validator TL node comes to determine a newly created block by itself. As a result, each TL node can update the cross-shard chain quickly.
(See Figure 4)
Unspent transaction outputs cache (UTXO)
L1 node checks that the previous outputs referenced by the transaction exist and have not been spent.
The regional node maintains an unspent transaction outputs cache (UTXO) updated every time slot.
The UTXO is a database containing only the unspent transaction outputs.
The UTXO is very useful as it can quickly check if new transactions are valid before entering them into the UTMP.
When a new transaction arrives, its inputs are looked up in the UTXO. If the input is found there, the input corresponds to valid previous output, and the transaction continues to be evaluated.
If the input is not found in the UTXO, the transaction is invalid and can be discarded.
For example, suppose Tx[TxIn = zzz] arrives at node A in the shard p region. Node A knows that the TxIn address belongs to the Shard k region. After looking up the Shard/Address Mapping Table and selecting one node in the shard k region to deliver this Tx, the Tx is passed to the node. The node in the Shard k region that has received the Tx judges the validity of the Tx by referring to the UTXO.
(See Figure 5)
How do nodes in the home shard region process transactions?
First, let's take the case of an Intra shard transaction as an example.
Addresses zzz and ooo both belong to the same shard k.
When Tx[zzz, ooo] arrives at the node, the node first checks the validity of this transaction by referring to the UTXO and double-spending for the zzz address. If validation is confirmed, Tx[zzz, ooo] is entered into Intra UTMP.
Second, let's take the case of the cross-shard transaction as an example.
Addresses xxx, and eee belong to the different shard k and shard p, respectively.
When Tx[zzz, eee] arrives at the node, the node first checks the validity of the zzz address by referring to the UTXO and double-spending for the zzz address. If validation is confirmed, Tx[zzz, eee] is entered into Inter UTMP.
(See Figure 6)
How are transactions between peers with the same home shard region recorded in the shard chain and reflected in the UTXO?
Assume that a transaction that remits 55 from the sss address belonging to the shard k region to the xxx address arrives at node A during time slot i.
When this transaction request arrives, node A refers to the UTXO to complete the checking process of the double-spending problem and transaction validation. Transactions that pass this validity check enter the Intra UTMP. And, the transactions collected in Intra UTMP are sent to L2 all at once. L2 nodes share UTMP data sent by all nodes within the shard region. Then, Collation is created through the Fork-less PoS process. Based on this newly created Collation, the UTXO of the shard p region is updated. The updated UTXO is sent to the L1 nodes, using the updated UTXO during time slot i+1.
(See Figure 7)
How are transactions between peers with the different shard regions recorded in the Cross-shard chain and reflected in the UTXO?
Assume that a transaction that remits 55 from the sss address belonging to the shard p region to the yyy address, which belongs to the shard k region, arrives at node A during time slot i.
When this transaction request arrives, node A refers to the UTXO to complete the checking process of the double-spending problem and transaction validation. The transaction that passes this validity check enters the Inter UTMP. And, the transactions collected in Inter UTMP are sent to the TL nodes all at once. The TL nodes share UTMP data sent by all nodes over the whole network. Then, the new Block of the Cross-Shard chain is created through the Fork-less PoS process. Based on this newly created Block in the Cross-Shard chain, the UTXOs of all the corresponding shard regions are updated at the next time slot. This means that 2-time slots are required to complete a Cross-Shard transaction while it takes one time slot period for an Intra-shard transaction to be completed.
(See Figure 8)
How about a blockchain network in which Cardano takes the lead?
A Top-level node can process a cross-shard chain. It does not download all data in the shard chains.
Shard Node (regional node) can process the shard chain for a specific shard region. Shard Nodes fully download the cross-shard chain in the Top-level node to stay in sync.
Increasing the scalability that Cardano has approached so far, such as increasing the block size or speeding up the time slot, is inevitably limited to improving the scalability.
We plan to apply the processing concept as a fundamental solution to the scalability problem. INTRA-AS traffic and INTER-AS traffic differ from those currently interconnected in Autonomous Systems (AS to blockchain). The sharding realm of a blockchain network can be autonomous for INTRA-Shard transactions. Thus, 'parallel writes' can dramatically improve transaction processing speed. In addition, INTER-Shard transactions are processed by having Top-Level nodes operate the INTER-Shards chain. We plan to design a prototype system capable of processing 3,000 000 transactions per second over six months. If Cardano accepts the proposal, detailed designs will be completed by August 2022, and the Cardano system will be able to process 3,000 000 transactions per second as early as 2023.
How about a blockchain network in which Cardano takes the lead?
A Top-level node can process a cross-shard chain. It does not download all data in the shard chains.
Shard Node (regional node) can process the shard chain for a specific shard region. Shard Nodes fully download the cross-shard chain in the Top-level node to stay in sync.
The role of top-level nodes is vital. However, as the rate of processing inter-shard transactions is high, the performance of 'Parallel Writes' increases, which is a factor that can increase scalability. The problem is that incentives can be reduced for operating top-level nodes. Therefore, you will have to pay a higher fee for inter-shard transactions.
In addition, the inter-shard transaction is completed after the one-time slot has passed compared to the shared transaction. In the process, the shard node must check the block of the cross-shard chain in the previous time slot and update the UTXO, so the synchronization problem between the cross-shard chain and the local shard chain must be resolved.
[FEASIBILITY]
We plan to design a prototype system capable of processing 3,000 000 transactions per second over six months. If Cardano accepts the proposal, detailed designs will be completed by August 2022, and the Cardano system will be able to process 3,000 000 transactions per second as early as 2023.
Researcher labor cost: $10,000
Buy computer equipment: $10,000
Lab and research environment maintenance costs: $8,000
S/W purchase cost: $2,000
1. Younchan Jung
The Catholic University of Korea
- Network Architecture
- Network Security
- Blockchain
- Crypto
2. Marnel Peradilla
Associate Professor, Advanced Research Institute for Informatics, Computing, and Networking, DLSU
- Mobile Ad-hoc Networks
- IP-based Protocols
- Mobility Management
- Software-Defined Networking
- Network Functions Virtualization
- Blockchain
3. Ronnel
Ph. D candidate in The Catholic University of Korea
-
- Software engineer specializing in augmented reality platforms
-
- Metaverse Designer
-
- NFT Strategist
-
- Blockchain Developer
-
- Product manager
[AUDITABILITY]
It is only necessary to check whether the region-based sharding network presented as a result of the study satisfies the processing speed of 3,000 000 transactions per second.
In addition, it will be necessary to check whether the cross-shard chain and the local shard chain are designed to operate in close cooperation.
This project will present a vision for the Cardano leading network, which guarantees the world's best performance, surpassing the Ethereum, Polkadot, and Solana main networks in terms of processing speed.
An entirely new one