dFusion ：可扩展的去中心化链上交易所
为想创建项目的朋友搭建创业平台，请感兴趣的朋友加乐乐微信：sensus113
NervosFans 微信公号：Nervosfans
谢谢！
本规范由Gnosis开发。
为打造一个具有去中心化订单匹配功能的可扩展中心化交易所，本规范采用了SNARK应用（snapp）的链上扩展手段，仅在Merkle根哈希中存储信息并支持SNAKRs在预定义的逻辑门 cp中对其进行操纵。同时，根据 DIZK，还支持数量更大的SNARK限制条件（所以我们也准备按照这个套路来）。批量拍卖中结合Gnosis开发的统一无套利价格清算技能对订单进行匹配。
规范
该交易所（设想）支持户通过N个预定义ERC20通证之间的限价订单进行交易。对于每个ERC20通证，交易人的余额都会被存储于Merkle树根哈希中：balanceTRH_I for 0<I<=N 。此Merkle树中的每片叶子仅包含用户持有的通证数量。
交易所中的帐户地址以及随机数被存储于另个Merkle树的根哈希accountsRH中。
balanceTRH_Token 中第i个叶子的余额对应（属于）accountsRH中第i片叶子的账户。
将所有订单编码成限价订单的形式： (accountLeafIndex,fromTokenIndex, toTokenIndex, limitPrice, amount, nounce, signature)。订单读取应按照以下方式进行：来自指定叶子索引的用户希望以不超过限定的价格卖出指定数量的fromTokenIndex（里的）token并购入toTokenIndex（里的）token。
[accountsRH,balanceRH_1, ..., balanceRH_N] 这些根哈希会被哈希到一起然后存储于stateTRH 这个链上“锚定”智能合约 中。锚定合约用来存储该snapp交易所中全部相关信息。
交易工作流程包括以下连续操作：
1. （带sha哈希的）订单收集
2. 从sha到Pederson哈希的转换函数
3. 查找批量价格：优化批量交易盈余
4. 交易执行后的余额更新
5. 处理未决/挂起退出与存款
6. 回到步骤1重新开始
（带sha哈希的）订单收集
以太坊上的锚定智能合约可以提供以下函数：
此函数更新orderHashSha变量，变量使用有效签名对全部订单进行编码。 函数可被任意方调用。理想情况下，“去中心化的运营商”会接受来自用户的订单，将其捆绑并包含在此函数中。 注意，订单仅作为交易有效负载发送，不会“存储”在EVM中。
从sha到Pederson哈希的转换函数
第一步，使用sha把订单们哈希到一起，这么做是因为EVM上做sha很便宜。但是SNARK里边做sha就很‘贵’了，所以才有了把sha变成Pederson哈希这一步。
我们使用SNARK来完成这项工作：
TransitionHashes＆Validation SNARK进行以下检查：
1. 重新计算所有订单的sha，再将其与公共输入orderHashSha进行比对以验证私有输入。
2. 再次迭代所有订单，后用Pederson 哈希按顺序做哈希。得出的Pederson哈希为输出。
注意，即便这些订单未包含在订单发件人的余额中也无妨，稍后的拍卖清算中会对这些订单进行整理。
锚定合约中有服务此过程的一些功能：
提供所需信息以及significant bond（担保？），任何人可申请变更锚定合约的状态。不需要提供SNARK：
发送的（状态）迁移信息不正确时，任何人可通过提供significant bond并调用以下函数的方式对其进行挑战。
默认下，认为任何针对significant bond的挑战都是合法的，且会在特定时间段（譬如几个小时）后执行，除非第一个状态迁移（请求）的提交人能在此预定义时间范围内提供证明自己请求正确性的SNARK证明。
调用以下函数后，锚定合约将对SNARK做出评估。
查找批量价格：优化批量交易盈余（顺差）
上一步操作完成后，批量（交易）中的订单处理完成。现在，可以计算出一个‘统一清算价格’，这个价格能够最大化所有交易对之间的交易盈余（顺差）。单笔订单的交易顺差指的是统一清算价格与价格上限之间的差额乘以对应通证的订单数量（具体步骤见这里）。计算统一清算价格属于NP困难优化问题，且在预定义的短时间范围内（SolvingTime）很可能找不到一个全局最优解（我们认为3-10分钟属于合理区间）。尽管如此，人们依旧可以提出自己的解决方案，因此程序仍不失公平。锚定合约存储全部提交（清算价格）方案并从中选出能够最大化交易顺差的那个做最终方案。交易顺差指所有统一清算价格与各被触动订单价格上限之间差额的总和乘以订单盈余。
这相当于拍卖的统一清算价格计算以一种去许可、去中心化的方式进行。权利义务不分家，敢提交价格方案至锚定合约，就得承担在下个步骤中提供相应的余额更新信息并且必须响应来自他人的挑战是‘义务’。
交易执行后的余额更新
价格方案提交后，锚定合约会选出能够最大化交易盈余的方案。本方案的提交人需要执行两个步骤：
1. 将完整的解决方案作为有效载荷发布到以太坊区块链中。方案包含价格向量P、账户余额已更新的新balanceRootHash、每笔订单的交易盈余（VV）向量。
P是与参照通证Token_1有关的所有价格的价格向量。 由于价格都是无套利的，我们可以计算出
price Token_i: Token_k = (Token_i:Token_1):(Token_1:Token_k)
不过，并非所有低于限价的订单都能被处理。譬如，发送订单的帐户余额不足因此无法结算卖盘。 那么，对于这种‘未担保订单（uncovered）’要么拒绝接纳要么只能部分处理。 因此，价格方案提交人必须提供每笔订单交易盈余的一部分：
价格方案的VV和P这两个部分被作为数据有效载荷提供给锚定合约，合约对其做sha哈希，形成 hashBatchInfo。
现在，所有人都能检查价格方案的有效性。若方案无效，任何人可挑战方案提交人。 出现挑战时，方案提交人需要提供以下SNARK证明方案的正确性：
本SNARK检查以下内容：
1. priceMatrix 含有hashBatchInfo导出的（带有sha的）值
2. orderVolume VV含有hashBatchInfo导出的（带有sha的）值
3. 对照 balanceRH验证[balanceTRH_i for 0<i<=N]的哈希
4. 验证[VV] 含有hashBatchInfo导出的值
5. 对于[订单们]中的订单:
A. 通过检查stateRH中余额+证明的方式打开接收账户的余额叶子
B. 打开accountIndexLeaf检查叶子是否由发送人所有
C. 检查随机数是否有效并更新
D. 读取订单的部分盈余
E. 减去卖出量，更新余额
F. FollowUpOrderOfAccount == 0时
a. 检查余额是否为正
G. 否则
a. 检查 FollowUpOrderOfAccount 中引用的其他订单的接收人是否相同且订单是否触动余额
H. 添加购买量，更新余额
I. 关闭余额叶子，更新Merkle树哈希
J. 跟踪每个通证的总销售盈余
K. 跟踪每个通证的总购买盈余
L. 跟踪每个通证的总销售量
M. 跟踪每个通证的总购买量
6. 检查所有通证的 selling volume 与buying volume是否相等
7. 检查计算出的总交易盈余与公共输入 tradingWelfare是否相等
处理未决/挂起退出与存款
存取款也需纳入‘balanceRH’处理。为此，我们再次用到了SNARKs与规定挑战期。
向锚定合约存款时，必须将资金发送到锚定合约的以下函数中：
也就是说所有存款信息都存储在一个bytes32的 depositHash中。 每出20个以太坊区块，就把发生的 depositHash存储在一个唯一的哈希中。
调用以下函数，存款可以由任何担保方（significantly bonded party）纳入（incorporated）：
本函数通过纳入 blockNr 到 blockNr+19的存款对stateRH进行更新。
任何人可检查stateRH是否正确更新。更新不正确时，任何人可通过提供担保的方式对此方案的提交人进行挑战。
提交人被挑战时，须提供以下SNARK：
此SNARK 检查：
1. 对 [deposit information]做哈希，得到depositHash
2. 对于 [deposit information]中的存款
A. 打开带有当前余额的叶子，
B. 打开AccountHash的叶子并
C. 检查 deposit.sender == accountLeaf.address
D. 用当前的余额更新叶子，
E. 重新计算stateRH
退出请求的套路类似。 不过有一个地方要注意：退出应当有延迟，否则非法的状态迁移可能还没被挑战就退出来了。
想要退出，首先需要调用锚定合约中的以下函数提出退出请求：
然后，任何担保方可以调用以下函数的方式把这坨（捆绑在一起的）退出请求纳入当前stateRH中：
FunctionincorporateWithdrawals(uintblockNr, bytes32 oldBalanceHash, bytes32 newBalanceHash, bytes32withdrawalAmounts)
登记在区块blockNr与blockNr + 19之间的所有退款请求被处理掉。价格方案提交人必须交出之前的oldBalanceHash，这个哈希记录了提款前的余额。 此外还需发送记录用户新余额的以及withdrawalAmounts的newBalanceHash，这个newBalanceHash是对用户全部合法提款后的余额做哈希得到的。
同样，未能正确提供incorporatedWithdrawals的结果时，可对此提出挑战。挑战时，方案提交人需提供以下SNARK证明：
此SNARK检查：
1. 对[exitRequest informaiton]做哈希，得到 exitRequestHash
2. 对于[exitRequest information]中的提款
A. 打开带有当前余额的叶子
B. 打开accountHash的叶子 withdrawal.sender == accountLeaf.address 且withdrawal.amount <= stateRHToken.amount时，
a. 用当前余额更新叶子
b. 重新计算stateRH
c. 将withdrawal.amount 纳入 withdrawalAmounts
方案未被挑战时，任何用户可在提交1天后触发提款，方法是提供存储在withdrawAmounts [blockNr]中自己余额的Merkle证明
可行性研究
本系统的扩展性存在两个主要的限制因素，分别是：信息作为有效载荷发送到以太坊的相关成本以及SNARK中限制条件的数量。
（信息）作有效负载时的订单成本
按照以下方式构建订单：( accountLeafIndex，fromTokenIndex，toTokenIndex，limitprice，amount，signature）。 加上以下限制条件时：
1. 交易所中只有2^6种不同的通证
2. 只有2^16个不同的leafIndexes
3. 使用浮点以64位精度编码价格（61位指数位，底部3位为尾数位）
4. 使用浮点以64位精度编码数量（61位指数位，底部3位为尾数位）
5. 签名是一对（s，r，v），其中s和r可能与椭圆曲线素数一样大。 就是说（r，s） -> 512位。那么我们可以把任一订单存储在3个bytes32中，且k笔订单序的总gas成本为：
transaction initiation costs（交易发起成本） + k* order as payload costs（订单做有效负载的成本） + k* signature verification cost （签名验证的成本）+ k* hashing costs（哈希成本）+ updatingthe orderHashSha 21000+k*(6+16+16+64+64+512)*68/8+k*3000+k*60+5000
就是花880万gas可以存储1000笔订单的意思。
SNARKs中的限制条件
根据DIZK，计算出限制条件高达几十亿的SNARKs是可行的。 但是此方法中描述的并行仅在基础椭圆曲线的素数-1经常能被2整除时有效。以太坊alt-bn128曲线中的素数-1能被2^ 28整除，因此，限制条件在2 ^ 28（约26亿）以下的SNARK都可以计算。
当然，限制条件最多的时候是SNARK检查交易并更新全部余额时。 下文中，根据做哈希的频率（预估），我们估算出了所需的电路（circuits）数量，由于限制条件的总数主要取决于哈希函数电路，这个估值应该不会差很多。
SNARK-applyAuction中，SNARK电路由以下操作主导：
1. 迭代所有订单 - >限制条件乘以#orders（订单数量）
2. 对于每个订单，需要打开3片叶子：
A. accountLeaf，balanceLeaf_SendingToken，balanceLeaf_ReceivingToken -> 3 * log_2(#balances) * 2 * #pedersonHashConstraints
3. 每个订单都要重新计算Merkle根：
A. accountLeaf, balanceLeaf_SendingToken, balanceLeaf_ReceivingToken -> 2* log_2(#balances) * 2 * #pedersonHashConstraints
那么，限制条件的数量的应该是#orders * log_2（#balances）* 10 * #pedersonHashConstraints这个量级，意思是每个pedersonHash中有1.1k个限制条件时，可以处理大约1M账户的5K笔订单。
所以，目前最大的难点是如何生成有228个限制条件的信任设置。
价格操纵
有人担心盈利市场订单（profitable market order，即售价限制定得很低的订单）提交后，攻击者会占满有限的订单空间，由于其他人无法提交自己的合法订单，这可能影响价格发现的公平进行，导致攻击者通过抄底市场订单的方式从价格优惠中获利。
可通过以下两种方式预防：
1. 订单加密：可以使用分布式密钥生成方案对订单加密，且只有在订单处理完成（finalized）后方可解密。 如此，攻击者无从知晓 “市场订单”的价格。
2. 订单参与期货：98％的订单空间使用一般的费用模型分配。 剩下的2％将专门用于使用了GNO / OWl或其他通证的人。 如此，攻击者无从占据整个订单空间。
