使用Merklix 树对UTXO集做检查点

区块链技术巴比特2017-11-25 06:57:01  阅读 -评论 0

在之前的一篇文章中,我介绍了Merklix树((译者注:Merklix 树和Merkle树的解释可以查阅原文作者的另一篇博文《Introducing Merklix tree as an unordered Merkle tree on steroid》)作为一种加密方法来描述无序集或无序图。这可以证明一个元素包含或者不存在于 o(ln(n))的数据结构中,并使用这些证明来改变结构,即使不知道它的全部内容。

我现在将解释如何使用它来帮助处理像比特币这样的区块链技术中的UTXO集。

Merklix证明存在与否

在进入UTXO部分之前,让我们演示如何使用一个Merklix树来证明集合中元素的存在或不存在。

在这个例子中,我们试图证明Item1是在集合中的。我们通过提供Item1或其散列,6eec,来说明,由于我们不想显示Item1或只是希望使证明更简洁,它们在图中用红色标示。

然后我们在树中提供一个通向根的路径。此路径在图中用黄色标示。要验证证明,一个散列6eec与3738得到bf1b,它自己散列与d9fe得到2812,树的根。我们证明了元素确实在树中。

现在让我们假设我们想证明Item5不在树中。 它的散列是cd5a,其中c = 1100。

相同的,证明是由黄色的元素得到。通过将bf1b和d9fe一起进行散列,可以验证它们都是树的一部分,并且它们是同层级。 bf1b作为从0开始的所有元素作为其子项,d9fe是从111开始的元素。因此,Item5不可能是这些子树中的任何一个。然而,如果它在树中,它将在这两个节点之间。因为这两个节点是同层级,我们都知道两者之间没有什么,因此可以断定Item5不在该集合中。

使用Merklix 证明来更新树

因为树中的路径是证明提供的,所以它也可以用于修改树本身。再次说明,这项工作并不需要通往根节点路径的先验知识(译者注:这句话我不能保证译的准确,原文是:this work without prior knowledge of the tree past its root.)。现在我们证明了Item5 不在树中,但也许我们想添加它呢?

树中的新节点用红色表示。图中黄色部分表示的是证明中的区块。正如你所看到的,一旦插入Item5 ,树的根节点可以仅使用证明中散列们来计算。

我们还有一个证明,Item1是在集合中,让我们删除它。

再一次,需要计算删除结果的唯一散列要么包含在证明中,要么在插入Item5时被计算。

从这一点,我们可以得出结论::如果k << n,我们可以在o(k * ln(n))中的n个元素的Merklix树中保持一组k个变化,并且当k变大时,趋向于o(k)。变化集在图中用红色表示。

使用Merklix tree 来生成关于UTXO 集的证明

可以通过使用txid 作为关键(译者注:这里的“关键”原文是“key”,我不太确认这样译是否很好)和一些未使用输出的序列化的作为值在 Merklix tree 表示UTXO集。为了简单说明,在上面的插图中,我一直使用散列的值作为关键(key),但是没有这样的义务。我不会继续深入到未使用的输出如何被序列化,知道这些已经足以了解这个概念。

当通过网络发送交易的时候,也有可能发送一个在UTXO 集输入的证明。这将允许接受交易和证明的节点避免查询它们的UTXO 集, 这可能是一个缓慢的过程,特别是如果集很大并且需要在磁盘上。

此外,这使节点可以修剪UTXO集的一部分。他们可以使用存在的证明来更新他们的UTXO集,包括修剪的部分。假使一个交易没有证明,可以向没有修剪的UTXO 集的该部分的另一节点请求证明。如果证明显示输入在UTXO集中,那么可以在其他方面进行检验,并且如果这是有效的,交易可以转发到其他节点。如果证明显示不存在,则交易因无效而被拒绝。

一般认为,网络上的节点不应相互信任。在不能构成证明的情况下,这将不是问题。节点不能说谎。更糟的是,节点可以拒绝回答,在这种情况下,请求可以被转发到另一个节点。

因此,实际上只有非常少的节点需要查询它们的UTXO 集,并且工作量可以分布在许多节点上。这将是比特币区块链中横向扩展(horizontal scaling)的第一个例子。通过这样的措施,UTXO 集可以通过只用一个节点的子集来处理每个它的每个分片就可以疯狂地增长到很大的规模。子集中的节点负责它自己请求分片的子集。

例如,使用大约5000个节点,可以分割UTXO 64路,每个分片大约有78个节点。

即使我们认为这些节点的一半不可信,并且不会回答请求,每个分片留下39个节点。

它可以有效地将每个节点的存储需求减少64个,其UTXO检查工作量减少2500个。在绝对数量上,一个1.5Gb的UTXO 集,一个节点需要大约24Mb的内存,一个区块只需要检验一小部分的UTXO,网络就可以处理当前的工作量。

如果节点采用智能策略,例如保持记忆高速的货币周转率(译者注:暂时未能理解这句的意义,原文是:such as keeping in memory high velocity money and committing to disk and pruning from memory asynchronously savings,),提交磁盘并从不同步的记忆保存中裁剪,网络作为一个整体可以实现极高吞吐量的UTXO请求,例如没有形成一个显著的问题下,允许UTXO 集几个数量级的增长。

 在区块中UTXO 集的检查点

虽然节点可以通过遍历整个区块链的历史来重构UTXO 集,但是这个意味着一个新节点的自我启动时间是 o(n*t),其中n是交易量和t 时间。这只会随着时间变得越来越糟糕。如果节点可以获得根散列的UTXO 集,那么节点就可以快速变得有效。

这可以通过将它放到coinbase 交易中作为软分叉来实现,但是最好将它放到区块头部中作为硬分叉来实现。这样,一个节点只要连接了就可以在网络上开始验证,并反向对已知有效区块开始验证以及作为网络进程转发。

声明:链世界登载此文仅出于分享区块链知识,并不意味着赞同其观点或证实其描述。文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。此文如侵犯到您的合法权益,请联系我们100@7234.cn

    参与讨论 (0 人参与讨论)

    相关推荐

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    区块链投资趋势报告:巨头入场布局行业趋于成熟

    来自:https://mp.weixin.qq.com/s?__biz=MzI4NzIxOTY1NA==&amp;mid=2650632639&amp;idx=1&amp;sn=e6d1c29731d992a80410aaee82ec3ea6&amp;chksm=f3d8db16c4af520097e4a64a71b1d4743ac326b9f027

    重新发明货币

    重新发明货币

    一、货币的演化过程 先简单回顾一下人类货币的演化过程,大概有以下阶段: a. 1.0版本:自然货币(贝壳、牲口、金银……) 这个阶段,货币基于一般等价物的稀有性或者实用性,货币不可能出现人为操纵的超发。 b. 2.0版本:早期纸币、银票到本位纸币 当贸易量越来越大,实物货币太不方便了,而且大家发现其实并不在意货币本身有什么价值,在意的只是这么多的货币能不能交换到足够的物品,于是纸币这种信用货

    从比特币交易看欧洲央行虚拟货币分类

    从比特币交易看欧洲央行虚拟货币分类

      互联网对传统社会的颠覆从未停止,在其完成对信息流、商流、物流、资金流的初步改造之后,或将以虚拟货币的形式打破现有货币体系   4月18日,在中国极客张沈鹏创办的比特币交易平台(42BTC.com)上,比特币对人民币的平均交易价为576元。当天,该平台完成了100个比特币的交易量。仅仅过去一周,4月25日上午,比特币对人民币的平均交易价已达到906元。据42BTC网站统计:在过去的32个月

    欧洲央行-比特币报告

    3.1 比特币 3.1.1 基本特征          比特币可能是最成功的,也可能是最有争议的虚拟货币方案,由日本程序员中本聪(译者注:事实上,中本聪是不是日本人,甚至是不是单个人无从考证)在2009年设计并实现。该计划基于一个类似于BitTorrent的P2P网络。BitTorrent是互联网上著名的共享文件协议,应用在电影,游戏和音乐领域。比特币在全球层面上运作,可用于各类货币交易(虚

    彻底玩转比特币地址和私匙

    彻底玩转比特币地址和私匙

    比特币地址和私匙是所有比特币初学者面对的一大难题,再加上那一串超长的字符串,让人更是摸不到头脑。 现在编者以问答的形式,带你一步步的揭开比特币地址和私匙的面纱。 还不知道什么是比特币地址和私匙的同学请点这里 问题一、比特币钱包由什么组成? 答 我们知道,比特币地址和私匙组成了比特币钱包,而私匙则决定了比特币地址上比特币的归属。 地址和私匙 问题二、如果只记得私匙我们还能还原比特币地址么? 答

    用GO语言实现比特币算法

    用GO语言实现比特币算法

    本节的这个例子展示一点点高精度数学包math/big、一点点散列包hash、一点点加密包crypto,还有一点点测试包testing的知识。这里不介绍bitcoin协议和算法——尽管它们很有趣,而是试图指出,Go对多种操作系统的支持,是实现这种跨平台应用的理想语言。 位钱(bitcoin)是一种使用加密手段制作的分布式电子货币。它最初于1998年由Wei Dai提出,并由中本聪(Satoshi

    详解比特币的找零机制

    详解比特币的找零机制

    比特币的找零机制一直让人有些迷惑,明明只向一个地址发送了比特币为什么 blockchain 上面的显示的有时是1个地址对多个地址,有时是多个地址对1个地址,有时又显示多个地址对多个地址? 为什么比特币资深用户要提醒大家当比特币钱包交易100次以上时再次交易后要重新备份钱包,恢复以前的钱包备份有可能会遭遇损失? 是的,这一切都是因为比特币的找零(Change)机制。本文参考 Bitcoin的维

    玩转比特币客户端之一:C盘转移和加速下载

    玩转比特币客户端之一:C盘转移和加速下载

    C盘空间不足?交易数据下载速度太慢?别着急,乐享比特币教你轻松玩转比特币官方客户端。 所有新人开始接触比特币时做的第一件事情大多数是安装比特币的官方客户端。 安全起见大家最好直接访问官方发布渠道sourceforge的地址进行下载:http://sourceforge.net/projects/bitcoin/files/Bitcoin/ 该网页列出了各版本的官方比特币客户端,目前

    麦妖榜
    更新日期 2019-01-16
    排名用户贡献值
    1等待的宿命23695
    2BitettFan23632
    3六叶树20309
    4天下无双16192
    5lizhen00214782
    6区块大康14461
    7让时间淡忘14188
    8冷风大q11188
    9momo11174
    10linjm122710562
    返回顶部 ↑