跨分片合约拖拽
每晚八点，我们在社区分享知识，等你。
NervosFans 微信公号：Nervosfans
入群请加乐乐微信：sensus113 美果大冰微信：xj73226
备注入群，谢谢！
特别感谢Piper Merriam帮忙一起想出这个点子。
跨分片合约拖拽（Cross-shard Contract Yanking）属于跨分片锁定【1】及类似技术的通用化方案，以实现跨分片活动解决火车和酒店问题。
注：【1】跨分片锁定方案
基本思想是使用读写锁定确保引用多个分片上数据的交易能以原子方式执行。
假设交易T所需的状态/存储集S，规定：
1. 一团数据的地址；
2. 是否需要读或写锁定
3. 保存数据团分片的ID
准备阶段
执行T之前，要求将一组存储S的锁定L添加至区块链。存储s∈S的锁定l∈L类似一笔交易，但是需要由保存s的分片以及T的父分片共同finalize。
提交阶段
执行T之前，需要：
（1）提供L已被添加到S中引用的所有分片状态的Merkle证明
（2）存储S的Merkle分支
T被执行并提交前，需要在T所在分片中提交（1）和（2），否则T所在分片中没有人能够检查T是否已正确执行。
如何避免系统中出现死锁？
1. 简单点的解决方案是锁定时间超时，可以是某个块高度，并防止区块在一段时间内获得锁定。但是这么做可能太慢。
2. 更好的解决方案是让区块链用T的首个预留块高度给交易T加个时间戳。有了该时间戳，就可以使用受伤等待机制（wound-wait mechanism）【2】来预防死锁。
注：【2】受伤-等待机制（wound-wait mechanism）解决死锁
受伤等待机制属于主动预防死锁的技术。交易Ti请求正由Tj持有的数据项时，仅在Ti时间戳大于Tj时间戳时，允许Ti等待，反之Tj被回滚（受伤）。
本方案中，交易请求锁定资源（数据项）时，若该资源已被其他交易冲突锁定，可能出现以下两种情形（之一）：
1. 时间戳（Ti）<时间戳（Tj）时，则Ti强制回滚Tj，即Ti使Tj受伤。稍后Tj随机延迟重启，但有相同时间戳。
2. 时间戳（Ti）>时间戳（Tj）时，则强制Ti等待至资源可用。
区块链实现
假设将任何交易锁定添加至区块链之前，必须添加交易初始化程序指定交易可引用的所有存储及锁定。
交易T的时间戳是其初始化程序的块高。
那么，如何保证条件（1）和（2）是成立的？
例（1）
分片上的验证人发现某些Ti的时间戳小于自己分片上交易Tj的时间戳且Tj阻止Ti访问资源时，分片引用Tj已获取锁定，联系其他分片，证明Tj的其他锁定必须回滚。有数据可用性证明时，Tj所在分片客户端可访问全部信息，因此客户端（出于故障保护的目的）可将信息转发给其他分片。
例（2）
我对例2有些疑虑。交易Ti必须等待另个有较早时间戳的交易Tj执行完毕，若Tj一直不释放自己的锁定，会怎样？交易Tj能否“拥有”数据？这个问题或许能通过锁定的时间限制缓解，锁定可由分片甚至数据团本身指定。
锁定方案的优点：交易以原子方式执行，必要时有可能以原子方式回滚。
不足：带来些开销。
其实，“锁定”分片A上的合约意思是把分片上的合约状态冻结，将状态保存到收据中，将合约导入分片B，在该合约与分片B上的其他对象间执行些操作，然后使用另个收据将合约发送回分片A，让其继续存在。
想要简化并通用化这个机制，把“锁定”改为“拖拽（yanking）”即可。在EVM中添加个YANK（单个堆栈参数：target_shard）操作码，YANK从状态中删除合约并签发包含合约状态及target_shard的收据；随后在target_shard中对收据进行处理，在该分片中实例化相同合约。合约可以自由指定自己被拖拽的条件。
举个例子，酒店预订合约可以通过reserve()函数实现，这个函数可以预订酒店房间，实例化代表酒店房间的合约，且该合约包含move_to_shard(uint256 shard_id)函数，允许任何人将合约拖到另个分片上。那么，人们也可以通过预订酒店房间，拖合约到车票预订合约分片，然后在该分片上以原子方式预订酒店和车票，从而解决车票酒店问题。必要时，酒店房间合约中的book()函数可以自毁酒店房间合约并签发收据，这个收据可用来保存预订记录在酒店预订主合约中。用户在拖拽后原子预订前消失时，任何想要预订酒店房间的人都可以使用这个（相同的）酒店房间合约来执行此操作，甚至是将酒店房间合约拖回到原始分片。
为保证拖拽效率，被拖者的内部状态必须很小，以便可以编码进收据中，且拖拽的gas成本要与被拖者的总大小成正比。一般从可用性层面来说，令对许多用户有意义的合约为可拖拽（yankable）并不是个好主意，原因是拖拽后的合约在target_shard中重新实例化之前，是不可用的。出于这两个原因，最可能的工作流是使合约具有与上述酒店房间（合约）类似的行为，意思是合约将与个别交互相关的状态分离出来，以便可以分别在分片间移动。
注意，跨分片消息和拖拽之间存在很好的并行，现有的CALLs和CREATEs：CALL = 同步分片内消息传递，CREATE = 同步分片内合约创建，CROSS_SHARD_CALL = 异步跨分片消息传递，YANK = 异步跨分片合同创建。YANK操作码不一定必须删除现有合约并创建收据才能在新分片上生成副本。非要这么做时（删除现有合约并创建收据）可能需要调用CROSS_SHARD_CREATE和self-destruct；这么做虽体现出对称性，却也需要个支持在另个分片中创建一个与原始合约地址相同合约的功能。
Q&A
问：如何预防用户相同的拖拽收据用两次，比如在没有任何新YANK调用的情况下在分片之间来回拖拽（状态相同的）合约？
分片是否需要记住每个领取过（claimed）的收据，防止领取两次的情形？（若需要，不就产生了须由分片存储不断增长且不可修剪的状态吗？）
或者还有别的机智法子？
答：有三种比较极端的选项：
1. 分片需要记住领取过的所有拖拽收据
2. 拖拽要求提供该分片中所有先前块的Merkle证明，证明相同合约未在先前块中被拖拽进（该分片）
3. 收据指定一个特定的区块高度，在此期间可以领取，若合约未包含在该特定高度，则永远消失。
但这三个选项都显然有点荒谬，下面是正常点的：
1. 收据须在一年内领取。分片须记住收据一年。
2. 分片记住收据一周。若一周内收据未领取，那么请求人必须每周提供一份Merkle证明，证明该收据不在上一周状态中领取收据列表中。
https://ethresear.ch/t/cross-shard-contract-yanking/1450
https://ethresear.ch/t/cross-shard-locking-scheme-1/1269
https://ethresear.ch/t/cross-shard-locking-resolving-deadlock/1275
