• 简体版 | 繁體版
  • 联系我们
  • 加入我们
  • 关于我们
  •  
  • 首页
  • 快讯
  • 价值号
  • 视频
  • 专题
  • 深度
  • 入驻价值号
  • 碳链APP
    微信公众号

    扫码下载App

  • 登录
  • 微信公众号

    微信公众号

导航
  • 首页
  • 快讯
  • 区块链+
  • 价值号
  • 视频
  • 专题
  • DeFi优选
碳链价值APP
专注服务于金融科技和区块链
立即打开

Txilm Protocol (中文版)

王嘉平王嘉平  •  2019-05-19
Txilm协议 中文版 Monoxide公链系统中的加盐短哈希有损区块压缩算法

Txilm协议在设计迭代中得到了原比特大陆 区块链团队 王逵 的指导和非常有意义的探讨。同时得到了孙毅老师主持的中科院计算所区块链实验室的大力支持。感谢 实验室中王鑫和姜鑫两位同学帮助完成了算法的初步模拟验证和近似误差的确认。

本文翻译自Monoxide团队的Medium博文,感谢 猎豹移动 区块链团队 王海龙 完成翻译和校对。

1 背景

假设新创建的区块中大多数交易TXes已经存储在大多数全节点的内存池中,致密区块(compact block)只携带TXIDs。这是在比特币改进提案BIP152中提出的。更多细节参见bitcoincore.org/en/2016。

总的来说,致密区块用32字节的TXID(例如,交易TX的SHA256值)替代每个交易TX(大约300-400字节)。这可以节省近10倍的带宽。

我们旨在进一步将致密区块中每个TX表示的大小减小到约40比特。我们可以在致密区块最初的提案(6.4=32字节/40比特)上做到6.4倍压缩。新的提案没有使用诸如布隆过滤器或IBLT这些额外的数据结构。此外,新提案不依赖各个全节点之间有高度一致的内存池(Mempool)。

通过结合规范的交易排序规则(canonical transaction ordering rule, CTOR),短哈希可以被进一步降低到32比特,这在致密区块最初的提案上产生了8倍压缩。做到了总的数据量减小80倍。

2 基本原理

我们通过基于TXID的小尺寸哈希值在区块中显示每个TX。

TXID-HASH = h(TXID)

其中h是一个小尺寸的哈希函数,它可以产生32比特到64比特的哈希值。该函数可以仅是CRC32,CRC40或CRC64。所提新的致密区块方案只包括一个TXID-HASH列表,按交易TX的初始列表排序。

这种k比特的小尺寸哈希可能会产生二义性(ambiguity),这需要每个全节点解决。一旦从发送方接收到包括TXID-HASH列表的新区块,接收方就在其内存池中的哈希列表中搜索每个接收到的TXID-HASH。对于每个TXID-HASH,可能发生三种情况,分别如下:

1. 未找到:内存池中没有交易TX可以匹配上接收到的TXID-HASH。接收方将向发送方或其他peer节点索要该TXID。

2. 找到一个匹配的TX:解析TXID成功。

3. 找到多个匹配的TX:接收方将收集所有匹配的TXIDs作为第二阶段解析的候选集。

在第二阶段,迭代多个TXID-HASH的候选者的所有组合来重新计算Merkle树。其正确的组合将产生一个与区块头携带的Merkle根相匹配的值。

如果情况(3)中的任一组合或情况(2)中被解析的TXID列表没能匹配区块头中的Merkle根,那么接收方将回退到要求发收方传输该区块的完整TXID列表,具体协议在最初的致密区块提案中有描述。出现这种情况的原因是在接收方的内存池中至少有一个TXID在接收的TXID-HASH列表中有相同的TXID-HASH,而不是包括在区块中的TXID-HASH。

对第二阶段搜索的一个可选优化是,在实际重新计算Merkle根之前,添加轻量级的预检查。我们提出了一种轻量级的Merkle树,CRC32-Merkle树,即用CRC32取代SHA256,4字节的Merkle树节点和根。当创建一个新区块,4字节的CRC32-Merkle根将预置到编码的TXID-HASH数据。在搜索正确的组合时,这产生了40倍的加速。(在16字节上算SHA256 对比 在8字节上算CRC32)

解决二义性可能引发额外的延迟。对很多有二义性的TXID-HASH的组合进行迭代也可能消耗大量的CPU时间。本提案的可行性高度依赖哈希碰撞的概率,这一概率同哈希值的长度(k比特)以及内存池的大小是相关的。

3 单个碰撞的概率

单个碰撞被定义为情况1或3至少发生1次。这种碰撞可以在接收到的TXID-HASH之间,或者处于接收到的列表和内存池之间。

给定k比特大小的的TXID-HASH,碰撞率是1/2^k。因此在一个新区块中发生单个碰撞的概率可以被建模为广义生日问题(Generalized Birthday problem)。比如,在内存池中,我们平均有m个TX,而新区块有n个TX。单个碰撞的概率可近似为:

PSC = 1 - (1 - 1/2^k) ^ (m * n + n * n/2)

例如,我们取m=60000,n=10000:k = 32, PSC = 0.14k = 40, PSC = 0.00059k = 64, PSC = 0.00000035

我们建议把k=40作为一个合理值,具备良好的压缩比和相当低的碰撞率。足够大的k约与log(m * n +n * n/2)成比例。

例如,我们放大100倍:m = 6000000,n = 1000000:k = 48, PSC = 0.023k = 56, PSC = 0.000090k = 64, PSC = 0.00000035

或者,我们把m,n的值取小一点,m = 3000,n=200k = 24, PSC =0.036k = 32, PSC = 0.00014k = 40, PSC = 0.00000056

4 结合CTOR 技术

规范交易排序规则(CTOR)是一种排序方案,它根据交易的哈希对一个区块和内存池中的交易进行排序,该方案已经被部署在BCH网络中。基于CTOR方案,所提的方案将实现更低的碰撞率和更高的压缩率。

因为交易在区块和内存池中都是有序的,任何有二义性的TXID-HASH的候选空间将被缩小到由其前一个TXID和下一个TXID限定的范围,并且具有被解析的TXID-HASH,而不是整个内存池。假设新确认的TXID均匀分布在已排序的内存池中,则可能的碰撞空间的大小将从m降低到m/n。在排序后,有二义性的TXID-HASH只有在相邻时才会发生区块内的碰撞。这显著降低了碰撞概率和解决二义性的成本,从而允许更短的哈希和更高的压缩比。

按CTOR技术对交易排序,碰撞概率可以被近似为:

PSC = 1 - (1 - 1/2^k) ^ (m + n/2)

对小尺寸的区块:m = 3000,n =200:K = 16, PSC = 0.046K = 24, PSC = 0.00018K = 32, PSC = 0.00000072

对中等尺寸的区块:m = 60000,,n = 10000:k = 16, PSC = 0.63k = 24, PSC = 0.0039k = 32, PSC = 0.000015

对大尺寸的区块: m = 6000000,n = 1000000:k = 24, PSC = 0.32k = 32, PSC = 0.0015k = 40, PSC = 0.0000059

5 恶意碰撞攻击

攻击者很容易构造一个新交易,其TXID-HASH和已有的交易相匹配。大量创建这种恶意交易可能使上述的碰撞概率分析无效并且使新区块的验证成本不菲,这最终导致更高的分叉率。我们提出了两个简单的策略来应对该攻击模型。

加盐哈希一个简单的防护策略是在计算TXID-HASH时引入一个盐(Salt):

TXID-HASH = h( Salt + TXID )

该盐值该特定于携带那些TXID-HASHes的区块并被包括在编码的数据中。例如,直接将CRC32-Merkle的根作为盐,或引入另一个4字节字段,随机生成。

即便已有的交易对所有人是已知的,攻击者在一个区块被矿工广播之前是无法构造恶意的交易。恶意交易很难比接收并验证新区块更早之前到达全节点。这使得攻击者可能发起攻击的时间窗口极度受限。同时,这要求攻击者可以快速地将恶意交易泛洪到整个网络。理论上讲,这有可能(例如,控制大型的僵尸网络),尤其是当主链底层的P2P网络很小的时候。该策略使得恶意交易只能针对单个特定区块,因此先前传播的恶意交易将无法攻击未来的区块从而使得该攻击在经济上很低效。如果想要持续攻击网络,需要持续构造恶意交易,隔了一个块之后,之前的攻击交易就失效了。但是这些交易的交易费用依旧背会后续区块获取,使得攻击成本相当高昂。

受到攻击时降级到老算法引入加盐哈希显著地提升了碰撞攻击的成本和失败率。倘若在极端情况,不计成本,大规模的碰撞攻击仍然是可能的。当整个网络受到攻击时,我们要求矿工回退到TXID列表。矿工会愿意在这个时候退到老算法,因为创建孤块是在浪费哈希算力,矿工会尽可能避免。

在验证进来的新区块时,包括矿工在内的所有全节点都可以察觉到此类攻击。它可以通过简单地计算每个区块中带二义性的TXID-HASH的数量来做到。如果数量显明显高于预期值并且观察到分叉。下一个区块应该回退到TXID列表算法。

参考文献

[1] Compact Blocks FAQ: bitcoincore.org/en/2016

[2 ]BIP152: Compact Blocks: github.com/bitcoin/bips

[3] Canonical Transaction Ordering for Bitcoin

https://blog.vermorel.com/pdf/canonical-tx-ordering-2018-06-12.pdf

[4] Wiki: Birthday problem

en.wikipedia.org/wiki/B

[5] Big Number Calculation:ttmath.org/online_calcu

原文链接:

medium.com/breaking-the

展开全文
打开碳链价值APP  查看更多精彩资讯
声明:本文内容为作者独立观点,不代表碳链价值立场,且不构成任何投资理财建议。
0 0

扫一扫,分享到微信

相关推荐

马斯克发布Cybertruck背后的故事 深度

马斯克发布Cybertruck背后的故事

碳链价值 2023-12-01 深度
Cybertruck
这个炫酷皮卡在公众面前最早出现可以追溯到2019年,马斯克在洛杉矶一个活动上面介绍了Cybertruck。
元宇宙的潜在困境 深度

元宇宙的潜在困境

碳链一线 2023-12-01 深度
元宇宙
元宇宙是人类在经典互联网时代陷入「存量残杀」情形时的破局之法,也是人类对未来虚拟世界的美好畅想。
NFT & ERC-6551:新星再度闪耀 价值号

NFT & ERC-6551:新星再度闪耀

Bing Ventures 2023-11-17 价值号
NFT
2023年交易量大幅度下滑。NFT流动性下降因缺乏创新性和可玩性。ERC-6551、Blend 借贷和 Opensea 的 Deals 可能是NFT市场回暖的关键。NFT市场的低迷程度很大程度上取决于更广泛的加密货币市场的表现。

碳链快讯更多 ›

2023-11-30

MicroStrategy 再次购买 16130 枚BTC

2023-11-28

李家超:打击无牌加密平台

2023-11-28

港媒:HOUNAX或为香港本地公司玖币

2023-11-28

Spartan Group管理合伙人:做空头寸信息遭某大型加密交易所泄露

2023-11-28

WSJ:美SEC仍在寻找 Binance.US 存在潜在欺诈的证据

2023-11-28

Vitalik 最新博文阐述对技术乐观主义、AI 风险、区块链和密码学等的看法

2023-11-28

美法官:赵长鹏必须暂时留在美国

2023-11-26

Arthur Hayes:美元流动性增长预示比特币将迎来上行趋势

2023-11-25

Web3 数字银行 iPeakoin 完成近千万美元 A 轮融资,真格基金领投

2023-11-24

盈透证券已获香港零售客户虚拟资产交易的许可

2023-11-23

新加坡拟于2024年中禁止加密货币保证金或杠杆交易,以遏制散户投机

2023-11-22

Mt. Gox 受托人:将很快开始向债权人偿还债务

2023-11-22

Sam Altman 将回归 OpenAI 担任 CEO

2023-11-21

武汉市公安局破获10亿元虚拟币洗钱案

2023-11-20

连线杂志:OpenAI 近 500 名员工威胁辞职,除非董事会辞职并重新任命 Sam Altman

2023-11-20

Tether 自愿冻结与国际犯罪集团有关的 2.25 亿枚被盗 USDT

2023-11-20

OKX已向香港证监会递交虚拟资产交易平台牌照申请

2023-11-20

华尔街日报:Bullish 已收购 CoinDesk 100% 的股权

2023-11-20

彭博:现货比特币 ETF 市场规模有望达 1000 亿美元

2023-11-20

微软 CEO:OpenAI 创始人 Sam Altman 和 Brockman 将加入微软

2023-11-20

Sam Altman回归失败 OpenAI董事会聘请Emmett Shear担任CEO

2023-11-20

彭博社:OpenAI 临时 CEO Mira Murati 计划重新聘请前 CEO Sam Altman 和前总裁 Greg Brockman

2023-11-20

知情人士:在被 OpenAI 罢免前,Altman 正寻求为新的人工智能芯片公司筹集资金

2023-11-19

OpenAI董事会:原则上同意Sam Altman回归

2023-11-19

彭博社:OpenAI 投资者正向公司董事会施压,要求恢复 Sam Altman 的 CEO 职务

2023-11-18

京港互联网 3.0 产业中心暨青年人才基地揭牌

2023-11-18

美 SEC 已推迟对 Global X 与富兰克林邓普顿的现货比特币 ETF 做出决定的日期

2023-11-18

OpenAI 罢免 Sam Altman 的 CEO 与董事会职务

2023-11-18

富达已向美 SEC 提交以太坊现货 ETF 申请

2023-11-17

BitGo 首席执行官:美 SEC 很有可能拒绝一系列现货比特币ETF申请

2023-11-17

日本金融厅批准推出ODX数字证券交易所START

2023-11-17

资产管理公司 WisdomTree 再次提交现货比特币 ETF 的 S-1 招股说明书

2023-11-17

德国联邦议员支持比特币作为该国法定货币

2023-11-16

贝莱德向 SEC 提交以太坊现货 ETF 的 S-1 招股说明书,任命 Coinbase 为托管人

2023-11-16

NYDFS 更新加密货币上市和退市指导方针,要求更为严格

2023-11-16

Arthur Hayes:随着美元流动性上升,比特币等风险资产将继续飙升

2023-11-15

新加坡金管局宣布扩大资产代币化计划

2023-11-15

蚂蚁集团首次披露海外发展数据 营收规模同比增长300%

2023-11-15

马来西亚砂拉越州与蚂蚁数科达成合作 发展数字政务服务应用

2023-11-15

彭博分析师:美 SEC 将在 21 日前对 3 个比特币现货 ETF 申请作出决策

2023-11-15

Cathie Wood:Gary Gensler的政治野心是现货比特币ETF受阻的原因

2023-11-15

Blockchain.com完成1.1亿美元E轮融资,估值较去年3月下跌超50%

2023-11-15

港股上市公司博雅互动拟斥资 9000 万美元购买比特币和以太坊

2023-11-14

加密货币集团 BGX 战略投资 OSL 母公司 BC 科技集团,认购约 7.1 亿港元新股

2023-11-14

渣打银行推出区块链部门 Libeara,拟代币化新加坡元政府债券基金

2023-11-14

韩国金管局成立虚拟资产上币工作组,并开始规划加密货币上市和退市指南

2023-11-14

港股上市公司博雅互动寻求股东授权以在一年内购买至多 1 亿美元加密货币

2023-11-14

BC科技集团出售上海憬威90%股权,并继续短暂停牌以待新股份发行

2023-11-14

传统金融资产代币化公司Fnality完成9500万美元B轮融资,高盛和法国巴黎银行领投

2023-11-13

香港立法会议员邱达根:可将比特币列为金融产品纳入「资本投资者入境计划」资产范围

推荐文章

  • 马斯克发布Cybertruck背后的故事

    2023-12-01

  • 元宇宙的潜在困境

    2023-12-01

  • 渣打银行预测:ETH有望在三年内狂飙五倍

    2023-10-12

  • ​香港应该成为未来RWA生态的引领者

    2023-10-11

  • 花旗银行为机构客户推出「全年无休」的数字通证平台

    2023-09-19

价值号更多 ›

深潮TechFlow
深潮TechFlow
文章: 305
  • 金融巨头PayPal入局,稳定币战事迎来转折点?
  • Apple 的 Vision Pro 问世, Web3 元宇宙面临复苏还是毁灭?
  • a16z 安德森:为什么 AI 会拯救世界
区块链骑士
区块链骑士
文章: 1435
  • 分析师:BTC ETF获批或将带来超160亿美元资金流入
  • Uniswap v4的Hooks功能引发争议,这是走向审查的开始吗?
  • 为什么人们不再谈论区块链技术,这是好事吗?丨BK Weekly#10
TinTinLand
TinTinLand
文章: 93
  • 智能合约新势力何以吸引开发者和用户?第三周 Web3 开发者集结精彩回顾
  • Hacker 资讯|12 月上旬区块链黑客松活动汇总
  • 如果 OpenAI 是个 DAO ,能否避免这场闹剧
换一批

热门标签

新基建 比特币 以太坊 DeFi 共识对话 区块链+ 美联储 央行数字货币 加密衍生品 AI 云计算 大数据 5G 政策 交易所 稳定币 电子支付 Libra 算力产业 联盟链 公链 区块链 加密货币 Nervos Cosmos EOS BCH STO 数字货币 去中心化

邮件订阅

及时、全面、专业、准确的资讯与数据,致力于为区块链爱好者以及数字货币投资者提供最好的服务。

App内打开

邮件订阅

及时、全面、专业、准确的资讯与数据,致力于为区块链爱好者以及数字货币投资者提供最好的服务。

Moshou

碳链价值是集资讯、行情、数据于一身的区块链信息服务平台,我们追求及时、全面、专业、精确的资讯与数据,致力于为区块链创新者和数字货币投资者提供优质的服务。

关于我们 加入我们 联系我们 隐私条款
微信公众号

扫一扫关注微信公众号

Copyright © 2018-2020 碳链价值 京ICP备18046423号
下载碳链App

下载碳链App

微信公众号

微信公众号

微信公众号

微信公众号

打赏文章作者

支付宝打赏二维码 支付宝扫一扫打赏
微信打赏二维码 微信扫一扫打赏

# 热门搜索 #

CBDC 比特币 DeFi 以太坊 区块链