以太坊Patricia树的Merkle证明验证

以太坊区块链使用修改后的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 => uint) public 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)。在以后的文章中,我们将介绍如何将这些状态证明与侧链的链上状态验证一起用于区块链间通信。


关键词: 以太坊  Merkle  

该内容来自于互联网公开内容,非区块链原创内容,如若转载,请注明出处:https://htzkw.com/archives/28390

联系我们

aliyinhang@gmail.com