cannot decode branch: cannot decode child hash #3346
Comments
|
Hi @boern I've been investigating and these are my finding Error decoding nodeWe are failing decoding the last node of the proof because it has an error in the 3rd child data length
But I'm sure this is not a gossamer error, I tested it in Substrate and Smoldot and they have similar issues Smoldot test exampleUsing use hex_literal::hex;
use smoldot::trie::{proof_decode::decode_and_verify_proof, proof_node_codec::decode};
pub async fn decode_failing_node_using_smoldot() -> Result<(), smoldot::trie::proof_node_codec::Error> {
let data = hex!("e902116a2811eaaa372fcd8c769b5f433d3995872b21c468dcfc6270e1f9fa07167eaa4c7c00f5f981c0b4dafe3c1029e70fb290294fc21f040197ac00f209dbf659a97bd83f7dc3fc42e985905ea2313b2551b72692510e9744493bd525055e27e295948a110806617572612092d55c08000000000561757261010116fd4fedb8ecd8eba0d907b7bd534b260bc0b86a0e9a1fd8f18cb85e9073f442a6a9f5460bfb2443bce67b8fdba17bbd2927bdad8fc6ae021c03e2c8b3e33e89");
let decoded = decode(&data)?;
println!("Decoded:\n{:?}", decoded);
Ok(())
}It fails with: Substrate test exampleUsing use hex_literal::hex;
use trie_db::{node::OwnedNode, NibbleSlice};
pub async fn decode_failing_node_using_substrate() -> Result<(), Box<dyn std::error::Error>> {
let data = hex!("e902116a2811eaaa372fcd8c769b5f433d3995872b21c468dcfc6270e1f9fa07167eaa4c7c00f5f981c0b4dafe3c1029e70fb290294fc21f040197ac00f209dbf659a97bd83f7dc3fc42e985905ea2313b2551b72692510e9744493bd525055e27e295948a110806617572612092d55c08000000000561757261010116fd4fedb8ecd8eba0d907b7bd534b260bc0b86a0e9a1fd8f18cb85e9073f442a6a9f5460bfb2443bce67b8fdba17bbd2927bdad8fc6ae021c03e2c8b3e33e89");
let node = OwnedNode::new::<NodeCodec<sp_runtime::traits::BlakeTwo256>>(data)?;
println!("Trie:\n{:?}", node);
Ok(())
}Getting this error: So we are consistent with Substrate and Smoldot behavior. Open questions
Regarding the get key value methodIf you change your gossamer test to not validate the nodes it will build the trie and get the key (as substrate does) but the key is different in substrate and gossamer Substrate result: Gossamer result: New test: func TestParachainHeaderStateProof(t *testing.T) {
stateRoot, err := hex.DecodeString("3b903e9947f26c4455f213b648661d0ef9b30018da7fa7be76bb5af2f5f75735")
require.NoError(t, err)
encodeStorageKey, err := hex.DecodeString("cd710b30bd2eab0352ddcc26417aa1941b3c252fcb29d88eff4f3de5de4476c3b6ff6f7d467b87a9e8030000")
require.NoError(t, err)
proof1, err := hex.DecodeString("36ff6f7d467b87a9e803000021590f48b11891aee1f281f856256f37a20f8abc5d027434f89dd2decab922fe")
require.NoError(t, err)
proof2, err := hex.DecodeString("800464801861be085002d2b0498ea992b13cfb1ca6b5e05a7ca54f6180dcc1bcd10a9f0680f6f6801e4b41e2e6d8ec194dba122bfb9eb33feb2545ef5144cea79551f7cc5280f6370779a48f025599265f348f955ee0b12eeb99238950c07f5562091f2186d48043e819b824d89dc6e744b5342c963829d44a93a1bdad2405615856f67945c9e0")
require.NoError(t, err)
proof3, err := hex.DecodeString("80cf93807b212eaf64882b542230cc1fa87d9505181a516c0dfd67ac55d3158cd753f8ad80862c9aecf51563f0b4f54f6d2a325bec9afdf62a66f595e150203fd9a144b1e580c2fb34bc8b88011ab509fd52c25b3469bbc9353f472a05decd83449af1e3677d80ecbe9453c51b405848014efabda8a0cde4b9458e7c26a4d9eeb589c52bdb5eb1809c43b10cb7509edfd059982f30f20ba7368bbd82786184cf0a5be813cd07490a8088d755e63972295bd4772b7322e27adb3358090fc2f16c66e65341de0d9bd22980891eac33e3ee82a64283ab12370710911e866576869040634657bcc78a1385a180a4c9385e359a9977574174c4d31beab6206a569ad15ef435bf784f16623e1d21802e89324e6a5e0be929b37bb44bdbf6619e6af80cbdebc9bd67a44c8aa072ef3980d8eabbfa85a6309a2ff6dac1a06e6a6d214faba34887e6f8e14c0d0d1858711e")
require.NoError(t, err)
proof4, err := hex.DecodeString("80ffff80fe86a6cb12b2233729f7834ff614d56c968207d9ae09266cd3835e32fc7bbdba80ee3fa56aef90d79d5a7c8e5f6e85252288631533a5a8ebf405846bdc3cedcaf38019c7f105c5c4278d8f4b5a67adb644c0d4b056b6affbe8721df8ce54865e8fe8800b223e5d94298635855f517e49a2e925d4e39de3e27ff1af06b658de5a2e8280804165dde7158903211dc880ebc441e6fc3ef9f8a1c5f99fd261178c4e97206805808dcd7a042792b39ad7fcbd97e77273b3d0b250c3203398f7290a7d3e0d7cc20c807c3fac76e1315865f8e8fcda6748711a415fc87187794acba9584b2c151b956080091b6db629efcf3857b17a2df2fa8b296c5aedc80db088f4e6a560053c7ce890803e5026745b944d7fa9a39c6f08292b88efbaec1e1041ccd78348053881c1bf86800451959b47e46ecdb0edd2df37445db0a629898058bae12a73ad88379a130fe080f52d9d5dfa99ec1762f86ca9b229e11e8f7910633e1032ece9c89e28892397a4805e6def858a456048697cbdb9af83fc447c671b0cf283f1409400f3a6c506321f80f8093e29566bd8ebec39521f87c10156d1c424a767aadecd231adf5c55f5f538806075e1c36fcba711bb56da63b85b31fdf481041a0acb93b035a6ebb9987734f4808f0cfeb4e4785d0fcb162883963e55e8cbc49c2398f1f275cfe5d2484bac2f9780b063dd4a5cd6b883c54ff93751d114e20e99e2e05eff766ddcca317b67d4f08a")
require.NoError(t, err)
proof5, err := hex.DecodeString("9e710b30bd2eab0352ddcc26417aa1945fcb801998fc2315e4329c3d3c59ff787fef52f1707abcf997f8114a016594b6716ce8803a5b05f6d48162e04748dce0050d00025c0d51a4845ea2119f66952522b2cd2b80549fd5090d980b3ae9b1b61196d5f617c57b2f4e5eb5f2e51e4c5c857429363180196a38280fc3af7f724552363e4833e604127b44cb46271dd28151765bb91cf0505f0e7b9012096b41c4eb3aaf947f6ea4290800004c5f03c716fb8fff3de61a883bb76adb34a2040080ae1c868ee54941861f121640db72e895211b6748da302cc4ddf39f715c76e7528052e248e38ba2e7f604c09c090bfb8abc6bc68c2f92f34f454606b4a63102e58a8026a2dd112b0ca67351d4abb723dc41978d5865dd4b208b37eed5200bbc0ba0f4807bd51e23ee41e85d99c3985aa8b0f859f70f20fa783b7055b5161adfc69e2d5180a6a96fae992961a174ea36d7e23e69c08d45ecacc82e14fbc3546b8d60ceae48")
require.NoError(t, err)
proof6, err := hex.DecodeString("9f0b3c252fcb29d88eff4f3de5de4476c3ffff8076bed1a9045e1937ab7ad7cff6e667c66351022b28103771310fa09e0a07708f808ff91cb4e274aa25177bbea2d77d5693f3da34820ecb82d6a06529de8bc0beb580b51c90d98a3cc501566107ce9b89e91609de184f72c521efe2e2486beb095dc280af5427f678c5055f4039369c53aaa785a3767ba10cf2e42b5cc9b625d8021bca8044ea5b04397b504579d34a01419b6f0fb0c4f3003b3e6e0b99687cc88f398670803d46b9972edc81cd44df296d227eafde0abd880a53ea37632ddb558e913315e68010a7cfabb7bf234b6efd0fba3d30758e762ec52d14d329e0b9ebd5c84ec7752680c9b8e0f77483284d53f3ccb7ca3a217faa9b50a819cfa557438cfa9813306910809bb471046c73d5edf5683b4e3408714f428ecdf8c447e80f8335b4049e555c2e80fd2a0bea95ba513ddd672bdd9d9fbfd1c9588731d06e9afa5004332250054ea180263061f7d953b0fba1d98b9c6529ce6c1d78af0012180caccb388c4921216de1803543b7e854863de08e6ce77ac171ecec6b64d419e58d6171fe654ee279b5f8c28061cd0a2e641fbce3fd78bad7f2b298918a187aca625491c1a1898763705840fa807aa5071686a8d5d83f8db3531aaaa181ea3843746bfc7917193b1dfcfbb0c49b8065ad311a5eb95c25f400fd199f1005a4ba6f62a7049117e9466dba91c1df949d80aa704996ec32908132b67245030b4d8456c46415837150ef58898df6b9b0ce5e")
require.NoError(t, err)
proof7, err := hex.DecodeString("e902116a2811eaaa372fcd8c769b5f433d3995872b21c468dcfc6270e1f9fa07167eaa4c7c00f5f981c0b4dafe3c1029e70fb290294fc21f040197ac00f209dbf659a97bd83f7dc3fc42e985905ea2313b2551b72692510e9744493bd525055e27e295948a110806617572612092d55c08000000000561757261010116fd4fedb8ecd8eba0d907b7bd534b260bc0b86a0e9a1fd8f18cb85e9073f442a6a9f5460bfb2443bce67b8fdba17bbd2927bdad8fc6ae021c03e2c8b3e33e89")
require.NoError(t, err)
proof := [][]byte{proof1, proof2, proof3, proof4, proof5, proof6, proof7}
trie, err := buildTrie(proof, stateRoot)
require.NoError(t, err)
value := trie.Get(encodeStorageKey)
t.Log("The Key Value:", value)
//Value obtained by running the same test in rust
expected := []uint{233, 2, 17, 106, 40, 17, 234, 170, 55, 47, 205, 140, 118, 155, 95, 67, 61, 57, 149, 135, 43, 33, 196, 104, 220, 252, 98, 112, 225, 249, 250, 7, 22, 126, 170, 76, 124, 0, 245, 249, 129, 192, 180, 218, 254, 60, 16, 41, 231, 15, 178, 144, 41, 79, 194, 31, 4, 1, 151, 172, 0, 242, 9, 219, 246, 89, 169, 123, 216, 63, 125, 195, 252, 66, 233, 133, 144, 94, 162, 49, 59, 37, 81, 183, 38, 146, 81, 14, 151, 68, 73, 59, 213, 37, 5, 94, 39, 226, 149, 148, 138, 17, 8, 6, 97, 117, 114, 97, 32, 146, 213, 92, 8, 0, 0, 0, 0, 5, 97, 117, 114, 97, 1, 1, 22, 253, 79, 237, 184, 236, 216, 235, 160, 217, 7, 183, 189, 83, 75, 38, 11, 192, 184, 106, 14, 154, 31, 216, 241, 140, 184, 94, 144, 115, 244, 66, 166, 169, 245, 70, 11, 251, 36, 67, 188, 230, 123, 143, 219, 161, 123, 189, 41, 39, 189, 173, 143, 198, 174, 2, 28, 3, 226, 200, 179, 227, 62, 137}
require.Equal(t, expected, value)
}Open questions
Next steps:
Let me know if you discover anything else about it |
|
@dimartiro thx for your reply ! Then, by polkadotjs -> rpc calls, get the state proof of the parachain header Finally, use the above proof data to construct a trie db, get the value, and compare whether the value is equal to the encoded head bytes. You can repeat the above steps to get the latest proof data and then construct the test ! Additional Information: |
|
@boern thank you for your reply, and all the details. TL;DR: I've been investigating and the difference between Substrate and our implementation is related with the DB they are building and the way they are retrieving the key for a hashed value. I fixed it in my current PR Overview
https://spec.polkadot.network/chap-state#defn-merkle-value Every node larger than 32 bytes is hashed to reduce the space usage, so given this and reading the substrate implementation I deduced that if you want to retrieve the value for a hashed node you will need to keep a mapping between the hashed nodes and the real values. What is happening?We are returning this value: If you print the substrate trie you will see that this value is the same as what we are returning 
But if you print the value substrate is returning is different let value = trie.get_with(&encode_storage_key, |v: &[u8]| v.to_vec()).unwrap().unwrap();Actually, that value is the byte representation for the last proof: println!("The Key Value:\n{:?}", hex::encode(value));So, why is Substrate returning a different value when you are trying to retrieve that key?The difference is in the way substrate is handling the hashed values. In substrate you have to build a DB to use it later to build the trie let db = StorageProof::new(proof).into_memory_db::<sp_runtime::traits::BlakeTwo256>();This DB is a key value store that has hashed nodes as keys and "real" nodes as value let value = trie.get_with(&encode_storage_key, |v: &[u8]| v.to_vec()).unwrap().unwrap();Internally it executes this lookup fn load_value(
v: Value,
prefix: Prefix,
full_key: &[u8],
db: &dyn HashDBRef<L::Hash, DBValue>,
recorder: &mut Option<&mut dyn TrieRecorder<TrieHash<L>>>,
query: Q,
) -> Result<Q::Item, TrieHash<L>, CError<L>> {
match v {
Value::Inline(value) => Ok(query.decode(&value)),
Value::Node(hash) => {
let mut res = TrieHash::<L>::default();
res.as_mut().copy_from_slice(hash);
if let Some(value) = db.get(&res, prefix) {
if let Some(recorder) = recorder {
recorder.record(TrieAccess::Value {
hash: res,
value: value.as_slice().into(),
full_key,
});
}
Ok(query.decode(&value))
} else {
Err(Box::new(TrieError::IncompleteDatabase(res)))
}
},
}
}Getting the node from the DB using the key (that is the node value) for not inlined nodes ...
Value::Node(hash) => {
let mut res = TrieHash::<L>::default();
res.as_mut().copy_from_slice(hash);
if let Some(value) = db.get(&res, prefix)
...We, on the other hand, are returning the storage value directly from the hashed nodes (so we are returning the hashed value) SolutionI pushed this commit with a similar solution than subtrate in my current PR. Now we are mapping the hashed nodes with their corresponding "real" nodes and we are returning the values from that mapping in case storage value is a hashed value. So the test pass now. 
PS: If you want to verify a proof for a given value you can use the Let me know if it works for you, I'll be adding this issue in that PR to close it when it's merged |
|
@dimartiro thank you, I synced your code and tested it, it works, but the node decoding still has errors, did you find the cause of this problem? n7, err := node.Decode(bytes.NewReader(proof7))
require.NoError(t, err)
_, _ = n7.CalculateMerkleValue()
t.Log("N7:", n7) |
|
@boern thanks for the confirmation. Do you really need to decode it? Did you try with Substrate? Based on my tests in my previous comment, that node failed to be decoded in Gossamer, Substrate and Smoldot because it has an invalid child length. Let me know if you can decode it in substrate and the method you are using. |
#[tokio::test]
pub async fn decode_node_using_substrate() -> Result<(), Box<dyn std::error::Error>> {
let data = hex!("e902116a2811eaaa372fcd8c769b5f433d3995872b21c468dcfc6270e1f9fa07167eaa4c7c00f5f981c0b4dafe3c1029e70fb290294fc21f040197ac00f209dbf659a97bd83f7dc3fc42e985905ea2313b2551b72692510e9744493bd525055e27e295948a110806617572612092d55c08000000000561757261010116fd4fedb8ecd8eba0d907b7bd534b260bc0b86a0e9a1fd8f18cb85e9073f442a6a9f5460bfb2443bce67b8fdba17bbd2927bdad8fc6ae021c03e2c8b3e33e89");
let node = OwnedNode::new::<NodeCodec<sp_runtime::traits::BlakeTwo256>>(data)?;
println!("Trie:\n{:?}", node);
Ok(())
}test reult: Error: Decode(Error { cause: None, desc: "out of range decoding Compact<u32>" })Same result as your test, as I understand it, the last node should also be decoded! |
|
@boern I have the same question, could be related with a bug probably. Glad to see that the change is working for you, please let us know if you have any other issue. |
|
🎉 This issue has been resolved in version 0.8.0 🎉 The release is available on GitHub release Your semantic-release bot 📦🚀 |
Describe the bug
I want to use gossamer trie to verify parachain header proofs that gets from polkadot rococo testnet,the code as follows:
Expected Behavior
Use the proofs from polkadot rococo testnet to build trie tree and get the parachain header value by the storage key
Current Behavior
Error: Received unexpected error:
cannot decode branch: cannot decode child hash: at index 2: unknown prefix for compact uint: 59
I write a sample that uses the substrate trie to verify the same proofs, the result is ok, Isn't gossamer trie unable to verify the proof from polkadot？
The complete test code link as follows:
golang testing code: https://github.com/boern/gossamer/blob/diego/trieV1/new-headers/lib/trie/proof/state_proof_test.go#L75
rust testing code: https://github.com/boern/trie-test/blob/main/rust/src/state_proof_example.rs#L71
The text was updated successfully, but these errors were encountered: