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：任意碎片之间的传递
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