区块链研究实验室|以太坊Patricia树的Merkle证明验证

  • 时间:
  • 浏览:38
  • 来源:区块链技术网

以太坊区块链使用修改后的Merkle Patricia树进行状态认证。这使区块链节点在每个区块的整个区块链状态上达成共识,并使轻客户端可以为任何状态信息创建Merkle证明。

但是自以太坊初期以来就可以进行状态Merkle证明验证,但直到最近才将其添加到JSON RPC API中,因此很高兴看到更多应用程序利用此功能。

存储Merkle证明仅对特定的trie root(即特定状态)有效。因此用户或轻客户端应用程序应该通过运行轻客户端或信任由多个证明方进行多重签名的状态根来信任该状态根:更安全。

账户和合约变量查询

在本例中,我们将使用web3.py构建一个merkle证明,证明指定的状态根中包含键的某些值。

Web3.py尚不支持eth_getProof,因为在撰写本文时并未合并PR。因此可以改用web3.py的这个fork:https://github.com/paouvrard/web3.py/tree/EIP-1186-eth_getProof

编辑(2019年10月):eth_getProof现在在web3.py和web3.js中可用,但在Metamask提供程序中不可用。

Web3.py连接到以太坊节点,并通过JSON RPC或IPC API eth_getProof进行状态查询并提供证明。

合约状态变量查询

简单的Solidity合约,我们要在其中证明映射键的价值:

contract Proof {
        string public greeting;
        mapping (address => uintpublic my_map;
        constructor() public {
                greeting = 'Hello';
                my_map[msg.sender] = 33333;
        }
}

验证“ greeting”和“ my_map”的存储证明:

from web3 import Web3, IPCProvider
from web3.middleware import geth_poa_middleware
from web3._utils.proof import verify_eth_getProof, storage_position


w3 = Web3(IPCProvider(...))
w3.middleware_stack.inject(geth_poa_middleware, layer=0)
w3.eth.defaultAccount = Web3.toChecksumAddress('0x...')


block = w3.eth.getBlock('latest')
greeting = "0x0"
my_map_sender = storage_position(w3.eth.defaultAccount, "0x1")
proof = w3.eth.getProof(contract_addr, [greeting, my_map_sender], block.number)
is_valid_proof = verify_eth_getProof(proof, block.stateRoot)

通过上面的脚本,我们现在可以构建和验证帐户和合约变量的状态Merkle证明。 请注意,verify_eth_getProof(…)仅验证包含证明,并且如果包含排除证明,则将返回False。 可以通过eth.getProof(...)返回的“proof”对象来验证排除情况。

 合约变量如何存储在Patricia trie中?

为了存储变量,EVM根据合约中定义变量的位置使用key:keccack(LeftPad32(key,0),LeftPad32(map position,0))。 此处有更多详细信息:https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_getstorageat。

web3.py分叉提供了方便的storage_position(),它返回所请求的映射密钥的Patricia树存储密钥。

作为比较,Aergo Lua VM在trie中使用key存储变量状态信息:hash(bytes(“ __ sv __” + variable_name + [“-”,var_index],'utf-8')),其中var_u index是可选的,用于映射的键或数组的索引。

证明验证码

这是一个很好的图表,解释了patricia树中不同类型的节点:

来源:https://ethereum.stackexchange.com/questions/6415/eli5-how-does-a-merkle-patricia-trie-tree-work

![](http://bitoken.world/wp-content/uploads/2019/10/11.png)

python

下面的代码通过迭代验证节点(上图中的extension、branch、leaf…)来验证key值和expected_value。 如果Expected_value等于证明中包含的值,则返回true。

def _verify(expected_root, key, proof, key_index, proof_index, expected_value):
    ''' Iterate the proof following the key.
        Return True if the value at the leaf is equal to the expected value.
        @param expected_root is the expected root of the current proof node.
        @param key is the key for which we are proving the value.
        @param proof is the proof the key nibbles as path.
        @param key_index keeps track of the index while stepping through
            the key nibbles.
        @param proof_index keeps track of the index while stepping through
            the proof nodes.
        @param expected_value is the key's value expected to be stored in
            the last node (leaf node) of the proof.
    '''
    node = proof[proof_index]
    dec = rlp.decode(node)

    if key_index == 0:
        # trie root is always a hash
        assert keccak(node) == expected_root
    elif len(node) < 32:
        if rlp < 32 bytes, then it is not hashed
        assert dec == expected_root
    else:
        assert keccak(node) == expected_root

    if len(dec) == 17:
        # branch node
        if key_index >= len(key):
            if dec[-1] == expected_value:
                # value stored in the branch
                return True
        else:
            new_expected_root = dec[nibble_to_number[key[key_index]]]
            if new_expected_root != b'':
                return _verify(new_expected_root, key, proof, key_index + 1, proof_index + 1,
                               expected_value)
    elif len(dec) == 2:
        # leaf or extension node
        # get prefix and optional nibble from the first byte
        (prefix, nibble) = dec[0][:1].hex()
        if prefix == '2':
            # even leaf node
            key_end = dec[0][1:].hex()
            if key_end == key[key_index:] and expected_value == dec[1]:
                return True
        elif prefix == '3':
            # odd leaf node
            key_end = nibble + dec[0][1:].hex()
            if key_end == key[key_index:] and expected_value == dec[1]:
                return True
        elif prefix == '0':
            # even extension node
            shared_nibbles = dec[0][1:].hex()
            extension_length = len(shared_nibbles)
            if shared_nibbles == key[key_index:key_index + extension_length]:
                new_expected_root = dec[1]
                return _verify(new_expected_root, key, proof,
                               key_index + extension_length, proof_index + 1,
                               expected_value)
        elif prefix == '1':
            # odd extension node
            shared_nibbles = nibble + dec[0][1:].hex()
            extension_length = len(shared_nibbles)
            if shared_nibbles == key[key_index:key_index + extension_length]:
                new_expected_root = dec[1]
                return _verify(new_expected_root, key, proof,
                               key_index + extension_length, proof_index + 1,
                               expected_value)
        else:
            # This should not be reached if the proof has the correct format
            assert False
    return True if expected_value == b'' else False

Solidity:TODO

结论

这是一个关于如何使用包含/排除证明(inclusion/exclusion)来查询Solidity合约变量的快速概述。 eth_getStorageAt和eth_getProof实际上消除了在合约代码中定义getter的需要,因为getProof API直接查询了trie状态数据库(获取另一个合约变量的合约仍然需要getter)。在以后的文章中,我们将介绍如何将这些状态证明与侧链的链上状态验证一起用于区块链间通信。

猜你喜欢

区块链红利吃饱后,这个巨头又想"征服"元宇宙?

据12月26日消息,百度与英伟达(NVIDIA)已达成协议,双方合作共建AI元宇宙。另外,在今日举行的百度AI开发者大会上,英伟达全球副总裁暨亚太区总裁 Raymond Teh将受邀出席,并发表主题演讲。

2021-12-27

2021年,区块链股权融资发生了怎么样的演变

过去一年,区块链行业融资井喷,在科技领域中独树一帜,A16z、红杉、老虎基金等等这些顶级机构在 2021 年的区块链行业肆意驰骋,在 DeFi、NFT、Metaverse 等领域扶持了一众创业项目。

2021-12-23

两个元宇宙的世界观,以及和区块链的关系

“元宇宙”这个名词音好听但义很难传达准确,想要更准确地理解义,取名为平行宇宙、竞争宇宙、山寨宇宙,更好。对应的,我们现在肉身所处的宇宙,我们称之为“肉身宇宙”。

2021-12-22

Alien Worlds(外星世界)区块链打金挖矿指南

Alien Worlds(外星世界)是一款4月就开始的游戏,10月27日又上线了全新的任务(Missions)游戏模式; 在WAX用户量排名中Alien Worlds(外星世界)一直排在前三,说明现在存量工作室还有很多;

2021-12-17

DeHorizon(地平线)区块链打金教程

今天我们就解析在一款社交主题游戏 — DeHorizon

2021-12-17