分类目录归档:区块链

Merkle Patricia Trie(翻译)

Published / by sickworm / Leave a Comment

原文:https://github.com/ethereum/wiki/wiki/Patricia-Tree

改良的 Merkle Patricia Trie 规范(又称为 Merkle Patricia Tree)

Merkle Patricia Trie(下简称 MPT 树,Trie 又称前缀树或字典树)尝试提供一种加密认证的数据结构,其可用于存储任意类型的的键值对。本文仅讨论键值对为字符串的情况(对于其他类型,只需要使用某种序列化方式将其转换为字符串即可)。这些键值对是完全确定的,这意味着两颗具有相同键值对的 Patricia 前缀树,它们的数据是保证完全一致的,因此也拥有相同的根哈希(root hash)。MPT 树提供优秀的 O(log(n)) 时间复杂度的插入,查询和删除性能。此外 MPT 树也比一些基于比较的替代方案(如红黑前缀树)更好理解和实现。

主要技术指标:Merkle Patricia Trie

但是,radix 树有一个较大的缺点:存储效率很低。举个例子,如果你只存储一个路径/值对,而这个路径长64个字符(32 字节的半字节(Hex)表示,正如以太坊的状态树一样),你将需要近 1K 的额外空间,一层一个字符地存储这个路径,并在需要删除它的时候花上整整 64 步。本文的 Patricia 树正是用来解决这个问题的。

改进

MPT 树通过提高原本的数据结构的复杂度,来尝试解决效率问题。MPT 树的节点可分为 4 种类型:

  1. NULL 空节点,用于表示空字符串
  2. branch 分支节点,具有 17 个项 [v0 ... v15, vt]
  3. leaf 叶子节点,具有 2 个项 [ encodedPath, value ]
  4. extension 扩展节点,具有 2 个项 [ encodedPath, key ]

在使用长为 64 个字符的路径的情况下,在遍历前缀树的前面几层的节点之后,后面层的节点很大可能都不再是发散的路径,而是一条单一路径。如果此时还按照前面的节点一样配置 index(Hex 字符集,共 16 个),则除了其中 1 个 index 不为空之外(即目标路径的下一个字符),剩余 15 个 index都是空的。这样做显然是不明智的。所以我们使用扩展节点 [ encodedPath, key ] 来快速处理这种单一路径。其中,encodePath 包含要跳过的”局部路径”(partial path,使用了下面提到的紧凑编码),key 用于下一次的数据库查询。

对于用 encodePath 第一个半字节就可以确定的叶子节点,上面提到的情况同样存在,且跳过的”局部路径”即完整路径的剩余部分。此时 value 即目标值。

当遍历半字节路径时,我们可能最终得到一个奇数个半字节的遍历路径。但因为所有的数据是以 bytes 格式存储的,因此不可能区分下面这种情况:半字节 1,和半字节 01 (两者都应该存储为 <01>)。所以如果要指定奇数长度,则在局部路径加上前缀标记。

规范:带可选终结符的十六进制序列的紧凑编码

上面提到,局部路径的首位半字节用于标记一个 2 项节点的属性:奇数剩余路径长度/偶数奇数剩余路径长度叶子节点/扩展节点 。定义如下:

 HEX 值     位值     |     节点局部路径类型           路径长度
----------------------------------------------------------
   0        0000    |        扩展节点                偶数        
   1        0001    |        扩展节点                奇数         
   2        0010    |    终止节点 (叶子节点)         偶数        
   3        0011    |    终止节点 (叶子节点)         奇数         

对于偶数剩余路径长度(02),将始终跟随另一个“填充”的半字节 0

def compact_encode(hexarray):
    term = 1 if hexarray[-1] == 16 else 0 
    if term: hexarray = hexarray[:-1]
    oddlen = len(hexarray) % 2
    flags = 2 * term + oddlen
    if oddlen:
        hexarray = [flags] + hexarray
    else:
        hexarray = [flags] + [0] + hexarray
    // hexarray now has an even length whose first nibble is the flags.
    o = ''
    for i in range(0,len(hexarray),2):
        o += chr(16 * hexarray[i] + hexarray[i+1])
    return o

示例:

> [ 1, 2, 3, 4, 5, ...]
'11 23 45'
> [ 0, 1, 2, 3, 4, 5, ...]
'00 01 23 45'
> [ 0, f, 1, c, b, 8, 10]
'20 0f 1c b8'
> [ f, 1, c, b, 8, 10]
'3f 1c b8'

以下是在 MPT 树中获取节点的扩展代码:

def get_helper(node,path):
    if path == []: return node
    if node = '': return ''
    curnode = rlp.decode(node if len(node) < 32 else db.get(node))
    if len(curnode) == 2:
        (k2, v2) = curnode
        k2 = compact_decode(k2)
        if k2 == path[:len(k2)]:
            return get_helper(v2, path[len(k2):])
        else:
            return ''
    elif len(curnode) == 17:
        return get_helper(curnode[path[0]],path[1:])

def get(node,path):
    path2 = []
    for i in range(len(path)):
        path2.push(int(ord(path[i]) / 16))
        path2.push(ord(path[i]) % 16)
    path2.push(16)
    return get_helper(node,path2)

比特币多种输出脚本(outputScript,scriptPubKey)介绍

Published / by sickworm / Leave a Comment

目前可见outputScript(scriptPubKey)格式:(参考https://bitcoin.stackexchange.com/questions/73758/what-are-the-standard-formats-of-transaction-outputs

p2pk
43 41
data(0x41):04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f ac
23 21 data(0x21):0349f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f ac

example:https://www.blockchain.com/btc/tx/7bdd7de22535770be3e14a4e527aed4431ab8adb3115657ca47df6fb1e89d70d

p2pkh

19 76a914 data(0x14):9bc6f9caddaaab28c2bc0a8bf8531f91109bdd58 88ac

p2sh

17 a914 data(0x14):9bc6f9caddaaab28c2bc0a8bf8531f91109bdd58 87

p2wpkh(bech32)

16 00 14 data(0x14):9bc6f9caddaaab28c2bc0a8bf8531f91109bdd58

p2wsh(bech32)
22 00 20 data(0x20):701a8d401c84fb13e6baf169d59684e17abd9fa216c8cc5b9fc63d622ff8c58d

p2ms
example: 2 of 3 multisig

52 // OP_2
410491bba2510912a5bd37da1fb5b1673010e43d2c6d812c514e91bfa9f2eb129e1c183329db55bd868e209aac2fbc02cb33d98fe74bf23f0c235d6126b1d8334f86
2102359c6e3f04cefbf089cf1d6670dc47c3fb4df68e2bad1fa5a369f9ce4b42bbd1
41048d2455d2403e08708fc1f556002f1b6cd83f992d085097f9974ab08a28838f07896fbab08f39495e15fa6fad6edbfb1e754e35fa1c7844c41f322a1863d46213
0395a9d84d47d524548f79f435758c01faec5da2b7e551d3b8c995b7e06326ae4a
53 // OP_3
ae // OP_CHECKMULTISIG

op_return

OP_RETURN (1 byte) PUSH (1 byte) <0 to 83 bytes of data>

others:
anyscript

说明

  1. 比特币理论上支持任意格式的script;

  2. 最主流的两种支付script为p2pkh,p2sh;隔离见证专用script为p2wpkh,p2wsh,使用新的叫bech32的编码,bech32已有官方实现:BIP173

  3. 隔离见证使用的script为p2wpkh和p2wsh两种,对应经典script的p2pkh和p2sh,但是使用隔离见证script这要求双方的钱包都支持隔离见证,所以在区块上见的不多。参考:
    https://testnet.blockchain.info/tx/f299afe17901f5a8d87f306c13f42c6fbf3d5b5de090973cf0fd34d403ccd2b8(p2wpkh转p2sh,详见4)
    https://www.blockchain.com/btc/tx/a60499338cdedebfd8cb7c379129cad1be5185d92d0db34717e66c1980a139b8(native p2wpkh)

  4. 接收方(使用utxo的一方)必须支持隔离见证,否则无法发送隔离见证交易;发送方可以不支持隔离见证,若不支持,接收方需要提供p2wpkh或p2wsh对应的p2sh脚本。这样虽然报文会稍微大一点,但是可以让不支持隔离见证的钱包发送支持隔离见证的utxo,这也是包括ledger在内主流的做法(接收地址为3开头的p2sh地址,实际使用时使用隔离见证交易)。详见BIP141BIP132

版权所有,转载请注明出处:
https://sickworm.com/?p=423

比特币隔离见证交易格式解析(Segregated witness)

Published / by sickworm / Leave a Comment

如果你还不了解经典交易构成,请看:https://blog.csdn.net/q4878802/article/details/49638457

隔离见证交易相关规范:

BIP141

BIP143

BIP144

BIP173

隔离见证 Segregated witness 交易解析

交易:https://testnet.blockchain.info/tx/f299afe17901f5a8d87f306c13f42c6fbf3d5b5de090973cf0fd34d403ccd2b8

交易报文:

01000000
00 // marker,固定值,旧交易不能txin count为0,此作为隔离见证交易格式的判断位
01 // flag,固定值,this will allow us to easily add more extra non-committed data to transactions (like txouts being spent, …). It can be interpreted as a bitvector.

// intput count
03

6f7f967a3e8c20964758efdc78e267a254b181fc3f4eab9112d885dd10e8a486 // prev tx
01000000 // prev tx index
17 16 001406c3d51e041b64e87a577ffd1a4ff5357cefd015 // scriptSig, P2WPKH nested in BIP16 P2SH <0 <20-byte-key-hash>>
// 当该utxo的前置输出是P2SH的时候就需要这样写,20字节长为对应私钥的地址,也就是witness里的公钥的hash160
ffffff00 // sequence,非ffffffff表示locktime无效

e0080049a6c62fee278ed7e11901f21b7dd9b356eedce0ce4f59c230c1e365ba
00000000
1716001406c3d51e041b64e87a577ffd1a4ff5357cefd015ffffff00

6ce4d6d1c2ee3c259989f50991f4f71c4ca96b6e986b470b9a84fd7e97c5f17d
00000000
1716001406c3d51e041b64e87a577ffd1a4ff5357cefd015ffffff00

// output count
02
00e1f50500000000 // value
17 a914 e5394e8a18db94b5e28b74f094718cab23ef9feb 87 // P2SH
a06e990700000000
17 a914 1ca5105565408eed39cdf021346313447bd99628 87

// witness P2WPKH 02 48 3045022100b6a271084b68c8b203bf708c6e725020d1e2997be2a88aef345303f62c3ce393022058ca1f83180467a3d0263a0183d28758ab797e6924c843cd797daeade984ed23 01 // sign script
21 0217cf57c2b592c9b00931370fd069b910b0b39c9f89f716d09ef614b1a3854b1c // publicKey

02 47 304402202dc1263af4dc28e2643fb5a1ceac2cd5b2d98bad3ae1d223adf809412db45ff602206c712c80be48cf60c8ce52b3757608fb66c6829f7ebcff807583380a1aff6ebd 01
21 0217cf57c2b592c9b00931370fd069b910b0b39c9f89f716d09ef614b1a3854b1c

02 47 30440220730c98896f0a4edd6ddcf5d5f1e5c04831cb1e7e6ad11e66623bc184e7242ffd02201d18e034c6764892d6dcd310488d6e9364e6abf2f7d51d31bc72ed3ac7b304ca 01
21 0217cf57c2b592c9b00931370fd069b910b0b39c9f89f716d09ef614b1a3854b1c

00000000

01000000
00
01
// input
01
b839a180196ce61747b30d2dd98551bed1ca2991377ccbd8bfdede8c339904a6
01000000
00
ffffffff

02
7dba920000000000
17 a914 9bc6f9caddaaab28c2bc0a8bf8531f91109bdd58 87 // P2SH
e31c030000000000
22 0020 701a8d401c84fb13e6baf169d59684e17abd9fa216c8cc5b9fc63d622ff8c58d // P2WSH

// witness P2WSH, 0 <1 2 CHECKMULTISIG>
04 // var_int 00, sig1, sig2,
00 // it’s a bitcoin’s bug and remain to now
47 304402204280e3c1c1edca50fb3c8843c410943937ad72f7e167e1f3fa99ff909a1b7a0502201e15e94ff9ce09cdb4cd0ab5d8bba52c408b900b8e4044a740a41eb3e8d34cff 01
48 3045022100a9b09d4f387e90b2ed2e38ea4bdecd901f611b68032566d08600868ce2b3b6a3022058c4ab2770dcea1adc301ff3f84d26e4d3e7dff3fdee1123c378c7e8d209e744 01

69 // var_int, data_length 1 + 66 + 2 = 69
52 // OP_2
210375e00eb72e29da82b89367947f29ef34afb75e8654f6ea368e0acdfd92976b7c
2103a1b26313f430c4b15bb1fdce663207659d8cac749a0e53d70eff01874496feff
2103c96d495bfdd5ba4145e3e046fee45e84a8a48ad05bd8dbb395c011a32cf9f880
53 // OP_3
ae // OP_CHECKMULTISIG

00000000

0100000000
01
01
36641869ca081e70f394c6948e8af409e18b619df2ed74aa106c1ca29787b96e
01000000
23220020a16b5755f7f6f96dbd65f5f0d6ab9418b89af4b1f14a1bb8a09062c35f0dcb54
ffffffff
02
00e9a43500000000
1976a914389ffce9cd9ae88dcc0631e88a821ffdbe9bfe2688ac
c0832f0500000000
1976a9147480a33f950689af511e6e84c138dbbd3c3ee41588ac

08
00
47304402206ac44d672dac41f9b00e28f4df20c52eeb087207e8d758d76d92c6fab3b73e2b0220367750dbbe19290069cba53d096f44530e4f98acaa594810388cf7409a1870ce01
473044022068c7946a43232757cbdf9176f009a928e1cd9a1a8c212f15c1e11ac9f2925d9002205b75f937ff2f9f3c1246e547e54f62e027f64eefa2695578cc6432cdabce271502
473044022059ebf56d98010a932cf8ecfec54c48e6139ed6adb0728c09cbe1e4fa0915302e022007cd986c8fa870ff5d2b3a89139c9fe7e499259875357e20fcbb15571c76795403
483045022100fbefd94bd0a488d50b79102b5dad4ab6ced30c4069f1eaa69a4b5a763414067e02203156c6a5c9cf88f91265f5a942e96213afae16d83321c8b31bb342142a14d16381
483045022100a5263ea0553ba89221984bd7f0b13613db16e7a70c549a86de0cc0444141a407022005c360ef0ae5a5d4f9f2f87a56c1546cc8268cab08c73501d6b3be2e1e1a8a0882
4730440220525406a1482936d5a21888260dc165497a90a15669636d8edca6b9fe490d309c022032af0c646a34a44d1f4576bf6a4a74b67940f8faa84c7df9abe12a01a11e2b47

83 // OP_INVERT
cf // data_length 1 + cc + 3 = cf
56 // OP_6
210307b8ae49ac90a048e9b53357a2354b3334e9c8bee813ecb98e99a7e07e8c3ba3
2103b28f0c28bfab54554ae8c658ac5c3e0ce6e79ad336331f78c428dd43eea8449b
21034b8113d703413d57761b8b9781957b8c0ac1dfe69f492580ca4195f50376ba4a
21033400f6afecb833092a9a21cfdf1ed1376e58c5d1f47de74683123987e967a8f4
2103a6d48b1131e94ba04d9737d61acdaa1322008af9602b3b14862c07a1789aac16
2102d8b661b0b3302ee2f162b09e07a55ad5dfbe673a9f01d9f0c19617681024306b
56 // OP_6
ae // OP_CHECKMULTISIG
00000000

版权所有,转载请注明出处:
https://sickworm.com/?p=420

实现比特币BTC交易重发(Opt-In Replace-by-Fee,Opt-In RBF)

Published / by sickworm / Leave a Comment

当你的交易因为交易费用过低而迟迟不能被节点确认,而又没有被节点抛弃的时候,你可能需要交易重发这个功能。而交易重发实际上就是,将保存在节点交易内存池中的你的交易(因为还没被确认)替换成新的交易。

BTC交易重发的三种方法:

  1. Opt-In Replace-by-Fee,简称 Opt-In RBF 或 RBF。将更高手续费用的交易提交到节点,也是本文着重介绍的方法。具体规范:BIP125

  2. CPFP,Child Pays for Parent。使用未确认交易的输出,并给予较高手续费。此时节点如果要打包这个子交易,则必须将其低手续费的父交易也一并打包。具体策略应该是一系列交易的平均手续费(未确认)

  3. double pay,制造双花。连接上没有收录你的交易的节点,使用原来交易的输入构建新的交易,并广播出去。由于两笔交易是冲突的,所以节点只会收录其中一笔交易。最后然后祈祷该交易被收录。

各方案比较

Opt-In Replace-by-Fee 比 CPFP 费用消费低,CPFP 需要多消耗一笔交易费用的钱;

CPFP 不需要节点支持 BIP125 也可以使用,Opt-In Replace-by-Fee 需要足够多的节点支持,交易才容易被成功收录(BIP 125 已发布2年多,其实不用担心此问题);

double pay 又麻烦成功率又低,不到万不得已不使用。

Opt-In Replace-by-Fee 实现指南(参考 BIP125

交易需声明为可替换交易,声明方式分两种

  1. 显式声明:至少一个input的nSequence小于0xffffffff-1(不是小于等于)

  2. 继承声明:没有显式声明可替换的交易,但如果他们的前置交易可替换且没有被确认,那该交易也是可替换的

实现细节:(Bitcoin Core 0.12.0)

  1. 交易需要声明为可替换交易

  2. 可替换交易没有包含新的,未曾出现过在内存池中的,未确认inputs(未确认input的意思是其前置output所在的交易未确认)

  3. 新替换交易的交易费用比待替换交易费用高

  4. 新替换交易费用必须比节点的min relay fee高

  5. 待替换交易的子交易(即使用了该交易的任意outputs,该交易替换后它们将被从内存池中移出)数量不可超过100条

测试站点

使用 https://www.blockchain.com/btc/pushtx 测试通过。

测试点:

  1. 降低手续费,不提高手续费(应失败)

  2. 提高一点点手续费(应成功)

  3. 提高手续费到比找零utxo还大的值(此时会引入新utxo)(应成功)

ETH交易重发

相比 BTC,ETH 的交易重发就简单多了。只需要发布同一个 nonce 的交易,旧交易就会被替换掉。当然手续费要比以前高,矿工可不干无用功。

版权所有,转载请注明出处:
http://sickworm.com/?p=409

比特币要解决什么问题?

Published / by sickworm / Leave a Comment

本系列文章标题为码农翻身的小密圈中圈主提出的问题,下面是我跟帖的回答

比特币解决了第三方发放信用货币时可能产生的问题。

首先,人民币是有价值的。为什么这些人民币纸币有价值呢?因为这是国家发行的,而国家说他是有价值,我们人民群众也认可国家。所以,人民币可以在我们之间交易,2元人民币可以买包方便面,10元可以买包巧克力。

然后我们思考一下,人民币会永远有这样的价值吗?不一定。什么情况下人民币会失去价值?亡国了!中央银行为了解决国库空虚,无限制地增发货币!这并不是不可能,世界上某些国家曾经,甚至正在上演这样的事情。人民币有价值,是国家向我们保证人民币是没问题的,你们可以放心使用。当发行方的信任出现问题时,货币的价值也就没办法得到保证了。

往小里说,货币发行方不一定是国家。如果你信任我,你给我100块,我给你在纸上画只鸡,作为我发行的货币。我还有其他朋友也认可我画的鸡,你可以不通过我,直接拿这张纸和他交易。以后等我建立自己的国家,我的国民都会用我画的鸡做交易。
不严格地说,这张有我画的鸡的纸就是我发行的货币。如果哪一天我跑路了,或者有人发现我暗戳戳的画鸡给我的小老婆,让她拿鸡去和别人交易,我这鸡纸恐怕就没人相信了,没人愿意相信这鸡纸的价值。
因为我不再被信任,我的信用货币也不再具有价值。

而比特币是数字货币,它不靠第三方发行,也不需要信任哪个第三方。它的价值由他自身产生运行的机制作保证,任何人可对其原理进行验证。且没有人为的干扰(理论上,现实中还是有硬分叉这种充满争议的情况发生)。我们不再需要依赖那些不靠谱的人(画鸡纸的我)和国家(津巴布韦这样的)的信用,只需要证明比特币背后的机制是符合货币需求的,它就可以得到我们的信任。

版权所有,转载请注明出处:
http://sickworm.com/?p=390