RChain的跨分片交易算法

跨分片交易是一个难题，但是遗憾的是业界已经有一个项目RChain解决了这个问题。

分片方式有很多种，最难的是状态分片，什么是状态分片呢？把以太坊比作银行的话，状态指的是银行账户的当前余额。那状态分片就是，按照账户的不同区分开来，就像6222开头的是工商银行，6214开头的招商银行的账户。

在以太坊的第一期的分片计划当中是没有跨分片交易的，交易只能存在于同一个分片的账户之间，也就是不能跨行转账。

那如何实现跨行转账呢？

1、架构

分区是一个树形结构

依赖关系是子分片依赖父分片

子分片的validators可以作为父分片的客户端

token在父分片和子分片的转义是通过智能合约去实现的

在父分片中的智能合约叫做Depository，它代表存储在子分片中token的余额数

当余额从子分片转到父分片当中的时候，它是从Depository提款

当余额从父分片转到子分片当中的时候，它是从Depository存款

在子分片中的智能合约叫Mint

当余额进入子分片的时候，Mint创建相应的代币

当余额离开子分片的时候，Mint销毁相应的代币

Mint和Depository一起建立起父分片和子分片的代币之间的汇率

1.1、跨分片消息传递

1.1.1 组织

每个实体都有一个URN，结构是 : <protocol_id>:<shard_path>/<public_key_fingerprint>.

每个实习都有一个通过公钥来识别身份的邮箱. RChain分片是通过channel实现的.

每个分片都运行着一个Mailman合约来路由消息.

每条消息都包含这三个字段: destination, signature & payload

描述

同一个分片的消息传递

Mailman从消息中提取到destination，然后发送到目标邮箱

准备跨分片消息

在消息发送到其他分片前要经过共识，发送消息的意图将存储在块链中，并且只有在块完成后才发送。

子分片到父分片交易

向父分片发送消息的总结如下：

1、就发送消息到父分片的决定达成共识

2、validators签名然后把消息发送给父分片

3、消息需要至少k个validators的签名

4、获得k个签名之后，消息存储在区块链中

5、共识达成之后，进行下一步

父分片向子分片交易

传输过程如下:

1、就发送消息的决定达成共识

2、子分片的validators作为父分片的客户端，收到了这条消息

3、子分片的validators在子分片的区块链上存储这条消息

4、共识达成之后进行下一步动作

1.2 散列锁托管转移（Hash-locked escrow transfer）

爱丽丝和鲍勃要通过代币P来交易货物，他们需要以下的一个交易机制来保证：

1、爱丽丝拥有代币P有效

2、在交易过程当中，代币P在爱丽丝的账户金额当中锁定，并且不能被其他交易使用

3、当得到了K次确认之后，交易执行成功

4、交易被取消的话，如果时间少于T，则代币会归还到爱丽丝的账户当中

Hash-locked escrow API

以下是对上图中的一些概念的解释:

Methods

initialize(key-hash : Hash, from : LocalAddress, to : LocalAddress, deadline: TimeInterval)

初始化转账的参数

execute(key : Key)

提供一个合法的key来触发交易的执行

通知事件

outgoing-transfer-ready

给发送方的事件。通知发送方这个交易已经正确的建立了

incoming-transfer(keyHash : Hash)

通过接受方它有一笔收款。这个通知还包括了执行这个交易需要的key

transaction-finalised(key=K)

当这笔交易已经完成之后通知双方。 这也是发送方接受交易的key的通道，这个key是用于触发链中的下一个传输

1.3 原子交叉碎片单向值传递（Atomic cross-shard one-way value transfer）

父分片中的代币要转换成子分片中的代币

爱丽丝拥有一个在父分片当中的钱包。鲍勃用户一个在子分片中的钱包

整个转账过程需要是原子性操作

一个单项的值传递需要使用到以上的两种操作：散列锁托管转移和跨分片消息

多步骤的跨分片转账通过它们的最小公共祖先的分片来完成。

在上述的例子当中，从"/a/b"转账给"/d"需要通过图中红色的分片

算法如下：

爱丽丝和鲍伯在不同的任意碎片之间的转移将执行以下算法:

Let LCA-A be the depository of Alice's branch in the least common ancestor

Let LCA-B be the depository of Bob's branch in their least common ancestor.

The algorithm for cross-shard transfers is described below:

transfer(Key, Source, Destination) =
    setup upward-tree-transfer with key-hash=hash(Key), from=Source, to=LCA-A
    setup hash-locked-escrow-transfer with key-hash=hash(Key), from=LCA-A, to=LCA-B
    setup downward-tree-transfer with key-hash=hash(Key), from=LCA-B, to=B
    Destination publish Key
    propagate K from B towards A

 1.3.1 例子

例子1：父分片到子分片

例子2：子分片到父分片

例子3：任意碎片之间的传递

Tips：图片上的字看着有点小，右键选择“在新标签页面中打开图片”看着就比较大了

2、相关名词解释

Shard (aka locale) - 有自己的一组验证人的独立网络

Shard tree - 分片的结构

Neighbour shards - 相邻的分片

Mailman - 发送消息给别的分片的智能合约

Mailbox - 存储消息. 也是分片的客户端

Address - 多分片的环境里的实体的唯一标识. 包括分片id和公钥

Mint - 在分片当中创建和销毁代币的智能合约

Depository - 存储子分片当中的代币余额的智能合约

3、Useful links

https://blockstream.com/sidechains.pdf

https://en.bitcoin.it/wiki/Atomic_cross-chain_trading

https://en.bitcoin.it/wiki/Hashed_Timelock_Contracts