Utreexo:比特币UTXO merkle tree proof以节约节点存储空间

2024-02-10 07:50

本文主要是介绍Utreexo:比特币UTXO merkle tree proof以节约节点存储空间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 背景介绍(本小节内容摘自区块链数据存储的“密码学黑科技”)

中本聪在设计比特币的时候,通过区块大小和出块时间将比特币的吞吐量限制在一个非常低的水平(1MB/10min),一个重要的考虑就是存储空间的限制。
即便如此,比特币从创始块以来所有交易和区块构成的区块链历史已经超过 200GB,且还在以每个月 4~5GB 的速度增长;比特币网络的未花费交易集合(UTXO)的大小也已接近一亿,占用空间超过 6GB。
作为区块链 2.0 的代表,支持智能合约的以太坊的“世界状态”则更为巨大。
以太坊现在有超过八千万个地址,仅仅是存储这些地址的基本信息(每个地址至少要约 100B 用来保存账户地址、余额、nonce、状态根(state root)等)就已经需要近10GB的空间了,算上智能合约的代码和内部状态则占用的空间还要再多十倍以上。
而上述数据仅仅是在用户数量不多、共识吞吐量不到 20Kbps(以简单转账交易计算,最多不超过 30 TPS —— Conflux 在 20 Mbps 的测试网络条件下可以实现 9.38Mbps 的共识吞吐量 [2])的情况下得出的。
如果想要把区块链的吞吐量提升到数千 TPS (与 Visa 相当)的水平,则存储方面需要承受高两个数量级的压力;如果要支持上亿用户大规模使用智能合约,则地址数量恐怕要超过十亿,相应的状态存储也至少要比现在多几十倍。
因此,区块链历史和状态的存储问题是继共识算法以后又一个挡在区块链扩容之路上的拦路虎。
在传统的分布式计算和分布式数据库场景中,可以通过磁盘阵列(RAID)和云存储技术以较低成本实现高可靠性的大规模数据存储。
但是这些设计的前提是提供服务的各个节点都是可信的,只存在宕机的风险而不会出现拜占庭错误,即没有恶意的攻击。
以比特币为代表的区块链为了在有拜占庭错误的前提下实现高可靠性,采用了每个节点(本文中节点均指参与共识的“全节点” full node——“Light nodes aren’t nodes”)存储一份完整数据的方案(类似 RAID 1)。
因此,区块链网络中的所有交易历史实际上会被存储几千甚至上万份副本,获得极高可靠性的同时也付出了不菲的成本。
此外,新节点加入的时候必须耗费数天时间下载并验证自创始块以来所有的历史数据,变相抬高了新节点加入的门槛,降低了区块链系统的去中心性。

2. Utreexo

由MIT数字货币研究所Thaddeus Dryja于2019年发表的论文《 Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set》,通过在transaction交易中除了所花费的UTXO外,额外再附加utreexo merkle tree proof信息,节点无需存储所有历史和状态信息。

Utreexo相关代码实现参见:

  • https://github.com/mit-dci/utreexo

Utreexo不会改变比特币的安全模式。
其衍化历史为:

  • 2018年10月的Bitcoin Optech Newsletter #17中提出:
    通过使用UTXO Hash Set(UHO),使全节点不再需要存储所有的UTXOs,仅需存储UTXOs的hash值,从而有效减少存储空间且不会对现有共识策略有任何影响。
  • 2019年2月的Bitcoin Optech Newsletter #32中提出:
    比特币的全节点维护了UTXO集合账本,记录的是当前所有可花费的比特币所有权信息。当前该账本有超过5千万个地址信息,需要将近300GB的存储空间。通过该账本,节点可以对确认交易中所花费的比特币确实在UTXO集合中存在,从中获取该比特币的所有权信息,可验证交易中的签名和其它witness信息,保证所花费的比特币是合法的,不存在双花和错花问题。
    如果要求spender在交易中提供所有权信息的同时,提供一份所花费的币在UTXO集合中的密码学证明proof,则verify验证节点不需要存储所有的UTXO集合,仅需存储UTXO集合的commitment即可。采用RSA累加器是一种方案。总之,存储UTXO commitment所需的空间远远小于存储所有状态的空间。但是交易的大小会增加,因为一方面要提供所有权信息,另一方面要提供proof以证明当前花费确实在UTXO集合中。但大小的影响可以接受:每笔交易input仅额外需约70字节的所有权信息+每个block仅额外需约325字节的aggregated proof信息。
    现有的密码学累加器要么需要trusted setup,要么其proof验证时间要远远低于使用merkle tree的方式。
  • 2019年6月的Bitcoin Optech Newsletter #50中提出:
    Utreexo累加器(hash based accumulator):
    1)将UTXO的查找和管理从全节点中移出。
    2)Logarithmic in the size of the full set.
    提出了一种新类型的node(Compact State Node):仅存储an accumulator representation of the state. Compact State Node可逐步添加,并不会影响现有节点软件。全节点仍可按之前的方式运行,相互之间传递交易和区块。Bridge node节点除了承担全节点的功能外,还需存储整个Merkle forest,并为Compact State Node提供proofs。
    在这里插入图片描述
    参考资料:
    [1] https://bitcoinops.org/en/topics/utreexo/
    [2] https://bitcoinops.org/en/newsletters/2019/06/12/#utreexo
    [3] 区块链数据存储的“密码学黑科技”
    [4] 2019年论文《 Utreexo: A dynamic hash-based accumulator optimized for the Bitcoin UTXO set》
    [5] UTXO Hash Set(UHO)
    [6] https://diyhpl.us/wiki/transcripts/bitcoin-core-dev-tech/2019-06-06-utreexo/
    [7] https://bitcoinops.org/en/newsletters/2019/02/05/#accumulators-for-blockchains
    [8] https://bitcoinops.org/en/newsletters/2018/10/16/#using-utxo-accumulators-to-reduce-data-storage-requirements-utreexo

这篇关于Utreexo:比特币UTXO merkle tree proof以节约节点存储空间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/696547

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

JS和jQuery获取节点的兄弟,父级,子级元素

原文转自http://blog.csdn.net/duanshuyong/article/details/7562423 先说一下JS的获取方法,其要比JQUERY的方法麻烦很多,后面以JQUERY的方法作对比。 JS的方法会比JQUERY麻烦很多,主要则是因为FF浏览器,FF浏览器会把你的换行也当最DOM元素。 <div id="test"><div></div><div></div

驱动(RK3588S)第七课时:单节点设备树

目录 需求一、设备树的概念1、设备树的后缀名:2、设备树的语法格式3、设备树的属性(重要)4、设备树格式举例 二、设备树所用函数1、如何在内核层种获取设备树节点:2、从设备树上获取 gpio 口的属性3、获取节点上的属性只针对于字符串属性的4、函数读取 np 结点中的 propname 属性的值,并将读取到的 u32 类型的值保存在 out_value 指向的内存中,函数的返回值表示读取到的

OpenStack离线Train版安装系列—3控制节点-Keystone认证服务组件

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版

OpenStack离线Train版安装系列—2计算节点-环境准备

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版

OpenStack离线Train版安装系列—1控制节点-环境准备

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版

OpenStack离线Train版安装系列—10.控制节点-Heat服务组件

本系列文章包含从OpenStack离线源制作到完成OpenStack安装的全部过程。 在本系列教程中使用的OpenStack的安装版本为第20个版本Train(简称T版本),2020年5月13日,OpenStack社区发布了第21个版本Ussuri(简称U版本)。 OpenStack部署系列文章 OpenStack Victoria版 安装部署系列教程 OpenStack Ussuri版