每晚八点,我们在社区分享知识,等你。
NervosFans 微信公号:Nervosfans
入群请加乐乐微信:sensus113 美果大冰微信:xj73226
备注入群,谢谢!
以太坊当前使用的累加器(就是Patricia-Merkle trie)是为状态专门设计的。累加器的另个替代方案,能够高度匹配状态客户端模型,仅用于历史。分离历史和状态并鼓励对历史的使用,能够使得无状态客户模型更为实用、扩展性更高。
以太坊1.0中的历史记录
文章中的“历史”指与以太坊有关的任何仅添加数据结构,包括交易历史、区块历史、收据历史。合约代码也是一种形式的历史,原因是合约代码不可变更。另外,应用程序也可以展示历史,比方说,维护存储中的历史分笔数据的合约。
以太坊1.0中的历史属于二等公民,原因是交易、区块和收据信息不能从交易本身读取(除了区块哈希,但仅限于最近的256个块)。BV几年前曾写道使得历史无法访问能够“提高许多节点的效率及代码简洁性”,还有“状态才是最重要的”。理由大概是不应该让节点获取非常旧的历史数据来处理交易。时至今日,依旧是“不断增长的区块链历史无法扩展”的默认。
无状态模型中的历史记录
无状态模型中,节点是完全不用挖掘数据的,无论该数据是历史、状态还是其他什么。提供数据的重任由(比方说)交易发送人在链下完成。所以从这个意义上讲,在无状态模型中,处理历史不会比处理状态更困难。或者书,事实证明,无状态模型中,处理历史可能比处理无状态容易得多。
这里的关键是Leonid Reyzin和Sophia Yakoubov最近一项名为异步累加器的创新。说白了就是Merkle树的升级版(VB下边说这就是MMR的概念)。这个异步累加器有个“低更新频率”的属性,意思是支持累积历史(不是状态那种固有的动态属性),使得单个事件证人的更新(次数)与事件数量呈对数关系(相对于线性关系)。最重要的是,更新不需要知识的累积集,无状态模型就表示非常中意了。
异步累加器挺有用处的。原因是:首先,大大降低了证人持有者的证人维护费用。其次,极大地增加了无状态模型使用提供的(相同)证人数据执行交易的可能性,这一点还蛮重要的。换言之,低更新频率或许为无状态客户端模型提供了实现的可能。
以太坊2.0:双重累加器
因此,对于以太坊2.0,可能需要尝试给“状态第一,历史第二”的理念掉个个,变成 “历史第一,状态第二”,借此撬动低频累加器证人更新。除现有的读/写存储累加器外,给每个合约都配个自己的历史累加器。可以考虑下面这个“混合累加器”VM:
1. 一个历史累加器,用来追踪“不可改变的过去”:仅添加(非动态);高带宽;证人更新频率低;便宜;超大型追踪集(比方说包含数万亿元素);使用异步累加器实现
2. 一个状态累加器。用来追踪“变化的现在”:动态;中等带宽;证人更新频率高;昂贵;相对小的追踪集(比方说包含数百万元素);实施与目前的Patricia-Merkle trie类似
我真觉得很多以太坊应用都能调整,把80%~99%+的存储负载推给历史。相较于存储累加器推送数据,历史累加器推送数据的gas少很多呢,也就意味着鼓励开发者能不用存储就别用。
编写历史驱动的应用
而且,确实有些通用的办法能够以历史最大化存储最小化存储的方式编写应用。比方说:
1. 借助SNARKs(或STARKs),任何应用都能以256位存储,剩下的都到历史中。256位存储中保存从被推送到历史的“交易”中导出的(隐式)状态哈希,通过SNARK大法证明自己有效。每笔交易都会更新该256位存储。说状态为隐式,是因为状态是在链下从“交易”中导出的(跟比特币余额是在链下从UTXO中隐式导出的道理类似)。注意,隐式状态的数据可用性在执行时通过绯闻传播历史交易的处理。
2. 作为上述SNARKs/STARKs的替代方案,还可使用TrueBit/欺诈证明模型。该模型中的交易为(推送到历史的)可能无效担保交易,能在一定时间内“确认”,而此期间(确认前)无挑战成功。应用程序使用存储作为隐式状态临时未确认的过渡状态缓冲区。
总结一下使用MMR维护历史对象证人数据时,特别neat的地方就是:
1. 低频率更新:证人从每插入一次更新一次变成更新日志(#{插入后更新})
2. 仅扩展更新:证人(Merkle路径)从trie中不相关对象更新修改内部节点变成只能扩展(并行友好)
3. 边际内存开销:Trie中证人维护开销从#{对象}变成log(#{对象})。
4. 缩短平均证人大小:Trie中证人大小从log(#{对象})变成log(#{插入后更新})
5. 缩短最坏情况证人大小:Trie中证人大小从#{对象}变成log(#{插入后更新})
对于历史对象,MMR确实证人友好,但BV也指出了一些问题:
在系统中使用显式数据结构以使‘低证人更新频率’历史对象易于使用的想法,真挺有趣。会虽如此,依旧存在些限制:允许从历史记录中引用对象的应用一般也需要有某种状态机制来有效地证明这些对象是否已被使用。
在系统中使用显式数据结构以使‘低证人更新频率’历史对象易于使用的想法,真挺有趣。会虽如此,依旧存在些限制:允许从历史记录中引用对象的应用一般也需要有某种状态机制来有效地证明这些对象是否已被使用。
累加器的语境下,MMR非动态,因此需要有动态累加器(Patricia-Merkle trie)来处理一般状态。因此,也有了这个问题:合约状态最小化能到什么程度,如此能够最大限度地限制trie的使用并使得MMR价值最大化。有两种方法可以最大限度地减少trie使用:
1. 存储在trie中的数据量最小化
2. 对trie的更新次数最小化
上边有建议使用SNARKs/STARK将需要上树的数据大小减少到32个字节(一个哈希的大小)。但是这个方法有个问题,说随每笔交易还是会有一次trie更新,因此trie更新次数与交易数量对齐(线性)。然后,也还是有种方法能够实现次线性数量的trie更新,具体而言就是MMR-trie混合方案。
加密经济累加器
我们来了解一个证人友好的动态‘加密经济累积器’。
给定对象o,通过将add或del位元数据包装到o(就是说整个[add, o]和[del, o]),相当于建出累加器添加与删除的模型。然后将包装好的对象添加到MMR,规定只有已发布抵押物的用户才能进行此操作。规则执行中由Trie记录抵押物发布人。
[del, o]事件与之前的[add, o]事件配对时,出现动态累加器,且相同o不会出现两次[del, o]事件(两次重复删除事件视为“违规”。)可以通过加密经济手段对违规行为干预:用户违规时,任何举报人都可以在一段时间内有效证明违规行为,后销毁一半的抵押物并将剩余抵押物发送至举报人。
注意,加密经济累加器添加和删除操作的“确认”需要时间,并且需要有相应的方案(比方说检查点),支持违规情况下的回滚。抵押物设置仅需一次,设置完成后用户可在不影响(变动)trie的情况下对加密经济累加器做任意数量的删除操作,从而实现次线性。
结论
无状态客户跟MMR真的很搭。有鉴于MMR的证人友好属性可随时为历史对象所用,并且能被扩展至处理状态、模运算亚次线性数量的trie更新。
https://ethresear.ch/t/history-state-and-asynchronous-accumulators-in-the-stateless-model/287
https://ethresear.ch/t/a-cryptoeconomic-accumulator-for-state-minimised-contracts/385
网友评论