Fast Merkle-Patricia Trie (MPT) state root calculator and proof generator for prefix-sorted nibbles
License: Apache License 2.0
If trie consists of a single leaf node, no proofs would be collected if only non-existent prefixes are passed into proof retainer.
Example:
let mut builder =
HashBuilder::default().with_proof_retainer(vec![Nibbles::from_nibbles(&[0x01])]);
builder.add_leaf(Nibbles::from_nibbles(&[0x00]), &[0x00]);
let _ = builder.root();
// Empty but should include root node
assert!(builder.take_proofs().is_empty());It looks like both #7 and #9 reveal an issue that this library isn't properly handling small nodes (len < 32) that get encoded in place. This issue happens both in hash building and proof verification. I'm submitting this issue specifically to target the verification side, as an Optimism block exists that generates a proof which cannot be verified by this library.
Run this command against an Optimism RPC:
cast proof 0xeB585163DEbB1E637c6D617de3bEF99347cd75c8 0x28f4302150b722752b95a0c2ec6426520f38afc8ec7bb291f3069bed49a511db --block 123955996To retrieve this proof:
{
"address": "0xeb585163debb1e637c6d617de3bef99347cd75c8",
"balance": "0x0",
"codeHash": "0x67c5a59e6d9b3aa748ea52f017726687b9cdd03e1df16608b0dcc071e466e7d6",
"nonce": "0x1",
"storageHash": "0xff7bbbfa0b8ed072fbe6c16290daf12ec721fcb24b61aef9681d532c6ce4feb5",
"accountProof": [
"0xf90211a08036d28fbcd94241f56e39e8a2cfc3e4f0b919c74cbb57eff4c59c653fd5db00a012f46a84ff3ad601bd353b2f3e31945e46f44460c30c6020e608b593c0617fe5a0a602d9d32b128856a4f31c536746db7903ad84b11f52585929f7dfa3e78e6d5da04269f3d5e6055a800cd7d5400944f6ef9d95a6b4e527027041b65d80c27c4befa0910aba2d14d3c2a45d2e7a36d834b3b3ba1e0bdf637a226fe2a8f5154387c8dba065c1949b2ccc7502444d3474e5b960499fb2c16059df3fdde4858f2a1c44e89ba076f5e7f068dfbb80065a9355cee2182e7c3dc6aec8d820a157cfe60ed63cfac8a01697b2d8651556d8d4d3cdc1a16f08de3ebd2b3616149c5b1bddcdaae8f41308a0aa3809e9fb97abe1af73acd06bb28a17f64f7b9651301e361d11107fe4821592a08b56d28d8aa71363efe67bf44e4c4d317de3f886e610b57038ddcbb51adebf89a0fd1b10e1bc203613823587649ba2736aab094e4bc5acb1539f553ed31632e800a03694e9610942219bf0abbc7df4b87678ae3df56676d44d3e2843bdc98c576367a0f0b3f1fd27a825b26f68bb6ba0577ecf6036ba0ba5092a664b31a04269d9dcfaa0e70667416a66a70ac60e24fcb573c4864f51631cf5de0ed89e28e23a118211bda0633da42a9d2f55dc705af446550ee7593950937085060992c6348ed2ec013fa1a00584fd9e77880db4249cdd88c09a585bcd960f097ac036bdae08af52a467423180",
"0xf90211a09ed1e684c63c73767c9684b4120d51965f4cbbf8f9c7b583618120c48df84d5fa0d1f358a69d76e7d53ae1e036e8fa37d65e1f7cafb65e4a68e7d4a60c284c1cd3a063da56cec43b963a318f3d307564ef54611262b58b996f753cc75ebfc48e8f7ba053c939f645855304b620b5ff0002e10f3c0ce183f7d479b10e8500626d772f17a0e998117cd632299e078c3a18611160e7f97c388d0d5a7bba381be1ad2b76468ea007a95b0c4cd25c456604a0f013e22acc26855eacaeb5b1fe2de1515b96f0af29a002a920c2211b8ecb90b0fcecd7a6f895be6df16ec7309534071e8209c6bbe815a0d52f9203c13119d32f8aeb55e2419b58cd1c56be4ada96abfec66e5d660972baa01cf2e5928f761e70d6e76d48c4a43b2a1747ab01110fcfefdd7e0814a48a2c3aa0a17967403d46adb8487c01741e22452274d7920986058c0dbfc160e7bafee2c8a06e03b086bb80a53d8f7f285a9f66869c977ced5c4c007b661db0f9703abe5eb2a09c2da38767d792403967188037a67b486efe823431c0fb1615628c9dd50809f2a02a048b4878872670952efe970c6007cae28f2f6cbaab6ce84844deb9dfe97caea06928113ac8312d69ba88738063e80ca0f96c4f92acd7491c2464320d561e1b2ea09e209dc550525127b858237244b230c0b37f4990e6930b20613893d719d0cf76a030f24f3b27038831c77c18d701d7e899b56473d089463ef635bc96952248e15f80",
"0xf90211a038140540e50aa8ac4bb639a25fffd724a1e5ba64bad2be7e524b8446b8cca09ba02b94061bc33e0c10bb257264c21f24b8ae6bee03c3bc44ff615e35a4887bb153a05571a6357470f8e3b5c16a9297e2d050f33e3c873ad49fa35114819cdc2b8ce2a0e6e8b62c7e02dfa9e55666bcfc0c71712de9ba65a24310f910b1d7dd0b06a41aa0b901cd07e9745acc055497229b6ca6b121e5beb3caa53bffc543d1b416f5a7c1a013b2690a327739cf68533bdeb325a295404df721223c52f1e333b4e2a6a6949ca078e9cc49e2e416aeb4e05985046f05a5292920cf024160396396c71590a0eee8a08e3d6868cd9339de361884900578f42ff17dbb3b47695400f73bb6e4ee6fe4a4a049c57da843c7be063255a12c114d7c817829929cc3505eed1fe9eab4335bda1ca05c00981323194c790d7165ae5926311ecf7d53e38c4d0850f95900b0902ece20a05da08ae83b66ead228dfb4db8dd163625fb3a7c9aabacd49f32c094f59d0b7e3a0e6c94ed320f60af13b05a74853aec2f1ae6fcad71a6c421a4139a08db3211f15a0cbae2af7302bee7261fe93b4b9d750000befeb14fff3d894e4a89d830f2d65eaa05bc279f8280ee215ba790569e7948cee5c5e10798baafffae389869c6cb7ff81a0f8f97d785aa5dae6801a3e35273bcfd61a5437b1a8e062d2eb3cdc5531b994a9a032655f79bfe7ed2576b2e368fb92d560e904216ea42578fc2b89b76a3e2206a680",
"0xf90211a0ee6de933dd5b15d4dc74df4253e900c6c8860ade18ab40076495b28cd82a4120a082bf0dffe385e58fa738d46420a463e135255c13ea0bb991d5e567d0588c9048a045861b8b8e78f8319b22b074574be0ecbd24f01afae8e895243a2506b83f3936a0d4d7d4c41a7396c87b84ffb8cf830d0f56b319e555d78ed57cbc8f0278a2bec1a070e89367a3dee1518d7d0a4208dc14a2576482821b7eb1a52cb912ce7604c30ba0b805c950ffe370296238804f9a506ee5bb0582263f0c5980a5203a91229b2d14a024de6748149e190b456d14abdd21c513417b067ddd4d4028185ade63ea781e22a04316f59386b9cd9d97c0f3b9d14fc85966c7f28a60b984ad5e68d298a58539efa0d550fc0d7ecdaa69f37adb82e5b30c72438a2f430afeb1ba7290075681677e40a0363fd495435e73bfc7b39ed18a2f938556b95dac66ee57d4ae31789411fac03ea00ee00f37011a2910ee377df39018e219140ff91b57f3e1b83dd8220c86f89cf3a08dcf8eaeeb55d8292f5b1d90d9d1675fe8fd38a74029654de92956f55e72aa90a00a92db3d61e49cf786bb3e2ab572f34a78641854f153b6207bed96d519e8e44ea0cad3c8266b246f46f6a4b3822ea94c41289c3cbed8f9eb0547f1718bdbf10bd5a0a4cf0b67884636146e6fc8af48d04369bbc82d544aa39f9586f53f1783c9eeeca07980e782d3562d7d5e8f9dd780833392aa7bd6550cb3c9c146a69bcceae9844580",
"0xf90211a040650d1c7817ccf9ae40df6c7c76fd724ac7ef885da4886c404910b8228ef2d9a0a815fb152f4ddb9cdd8f559cdef19c28af09556663c1ffe02aff2f07b0ce671ca0ef776c369c85eb13151229edca8e24df2ee7933445b48b20e31eb98cd8f8ba68a00dc703950e7f3ddd03afa9a085579ba56e64c14892f2b4fa00c25f7cd275bed7a0c16a777329e347eb35a2569d05cd150ac4aad1cb5e73d06d87f6415505d66bc0a00f4b2391c3e1568146107cace35c822a633ca635bf3da360240441d140c9bdaaa0a364d21e6071090744cacfd9ac4e7695d5c9076588dbe4adb1592236453252bba073948fc38643fdc2b50e986f39dfeb3768197729c61f25a1db4235da18cdaee3a0762fbeb2993085e347a841480ae059ea8f86a1ae177acba4e8b621c666828207a0f3786533ba84126cf2615500de061d1130c684fa24a6648ccc16295033d28213a0f48e2994d1e8000538aa11153801828283accf211bbc6790b5bbdcc398e17bc6a0b0e27bcacffbf87e18560e604a785f0a46586236b7bf819cb941ba8c25e371e5a0d00928f5961b89c36428e5f023975ff697c5fe0b49702891e3c1866f9f833483a0ab7add26e4203737acde733d3e581efad485e7d58d348c9f86842d62d33fb055a0453609eae782d7abbabcb0f5daf675ee62521cfa33b1caf6fd64a842888d42a9a0618db39d111818e096a3bd13f393ef0d0d6a51cb2743d249ca5c8edc4dd4c5fa80",
"0xf90211a0e66c796f585dd24921d8018a9cf7823c20eab815499cba19eb5721aa85a2eb08a0f15f53cc7e68ae86dc554ee8562f78f0186e36fef103fd58b84dc3bc5b7b5716a0b0caeb177dd3105f22fb463fd861785b102f8da1375aa11ddc33580e2b024d2ea049ae9a659e9ed0c18864c53722efce2e576e59992309c226e251b1c778d84a17a08af83e5c14734a98c643c8f0720145b6a3285c075af87301ded9f0ed94e29234a0fb0883e00af318d49c276697a989c37d764e347923336e211da015b4337ded1da0c50bf8f1349f0b3ec295f6538e7608d4d128a2f99765ffbfe4d47cdfa3e50739a059344ebbd6bfd3a16e410af6ab148daa9c9e4ada29011048e1460e7ed1d654d8a0faf13ad6ebc94b61c02f724906c0975dd2ddd0e77e97ed5d75d6859582899eeda0dd894ab88a81703570402bc2e11ad6d0833ca28fd3c79ebe21853604878b42b5a066429670ea488bede5fa6fa32e1b950233d2b32d499117363a360e5241a71c53a06152a9a77e320bfa7ad5fcceaa7acffd83180ee7ea7878b787ab30ad5aa00dcfa036df8cd8535e6017d29c7794c6c5ebc3c39f9b2a158d29662c68f34488303f78a081a7d4fb6021a44bbcf7b30468c986a65a7d48542e56aed868c86caa21bb1a43a0de232030f2a04a8999a18d10b46d6635a25bf7b2ddd7e5896fd5d94ac7100af8a0113b43dead05d843090582869e9b920b9df8042cb40378e5eb2dd798ae30d19c80",
"0xf8f180808080a039187a5ae26e7e18e792d7afe00a56b98e45a2b869c97eba25d912ab3b452325a0d01b5b169170576bad6d7d9cefc0adebadd394e3ca8563c4a5de0445ce4d7f6680a0ef281d23bf2635ca9f447c7db3f237f51f841b12a247c281c95c732e99d37b80a02547644c89d2d59301b7b1f68eca935f89744c8e049b2d943871e723738e922fa0d6af7c6655ef88355b31906b4e6850becb48d0cfce66fe71c835c8e72d695bec808080a01f4829e8f4eff0ba47badbb086adb33b48c908dc4c52cbef3123bd84ff0fc21880a0929ae0d7bee0e1f903118e6a23d1a2accbe155f6722234d2ef44ee2d595b9c4c80",
"0xf8669d34fc5d4b0e7a0f2d2bbd0e8e1485f77deeb29c8ef9b392af50698f04e1b846f8440180a0ff7bbbfa0b8ed072fbe6c16290daf12ec721fcb24b61aef9681d532c6ce4feb5a067c5a59e6d9b3aa748ea52f017726687b9cdd03e1df16608b0dcc071e466e7d6"
],
"storageProof": [
{
"key": "0x28f4302150b722752b95a0c2ec6426520f38afc8ec7bb291f3069bed49a511db",
"value": "0x64",
"proof": [
"0xf90211a03a6276995eb5d1fff9bd16b1c11f8485b162b4bf509f900e7152e79f016e1fd9a05d6782d3e6d8e80edafa4012152fb56bf963bca93dcbbbaf8fd3bf8ba28295eda03d84919d213e30959999a7351331ce2948888570981d9ad64808a67cba9417fba0a0a0ccda0d90bb0e316a657d31fc4b621997237b2018edee3ce831bf85ed876da098365b5f4f15aa28628974dc10040bdfd141aa3d844a44ffd5467d0cfdb83783a0ddab6813f08383b2ccf0f9423a6a33ab9eb359be3c278ee207ae6a5ed137299aa0d192425b22bd98dc8093c4fc265722eb75741d8ba0c4ef962e854d989228c41ca0960e41efa1ed2b424154e352aee64d65a53a16a9a00b64a5cf42718f94958c71a0e834762f9dd9c98f6f6a38243ffd0c9e7d20a9195a873c4f5baacf8cd1ae96aca03fe1eef75ffa73e75aacd56dd249424150869a90dc64e547e8856a072ced443ca08fafd81136beb6f75dcdea84acae59776c6fa3490cf8f894a93956764e51fb07a067318d29e0eac99230f90c0ab0825f13a8d3664bd42047d56a7022fafeb3c9dba0a26569ea91dbf46a1fecafc047a8ae24934a0c62fc424b898b43c94eb5c3d372a0b1fc8022c5ab3c71ec5ccdf606d6195eeb296fd9308010e73f1880c60eb226d6a0618adf141773582331777280e2ec78958f86c71b9978b7d9af124497f3840d43a0b141457f48df415def78506e6e064231b8b1d2147d44b55a38ee06b6e9124b8180",
"0xf90211a07168eea1d730ed9f1cf70a38902ed33a1f0cc9190cd38cfb68e91325320b5750a088b5bcbe087bea7778ea3ef688e1a2c0aa2d6f353b005e329acc9445fe3cce5aa060dc4526d664a91fc2fed626439eba7131e70c8438d5462c0710f37ab230f32da00a72be7dd2836340564ef542a6b09d464dedc9d8b3e5fd5cbeb3798e0d34b5d8a0731649c6f397b6b0603907482939a4b4c70b53f74e31adf68bc06eeabb49784ba061a679e5f45af1a3fe95aabed6e0fa2fd7ee13a927e8ab82a76f35ed9f059e38a0082b162d7c29aa275bcfbe6f9cbf580bf853e3607dafdeadb39f7e9e3b111375a0638726eb586b62a08c65816cbae8b5247db6076a2767aa640907cb4c75d6cacda0a2100f38821facd3fc8679d2bf43f459f5994a8c33f973d633260ed9afc3ccf9a05d4d448d533cb687c1bb5364d5e67ff90683d630b2d067b0065aae4b7019ac26a06232e9a0eefe21605b7839be4dcc00722a69d3658cefb890335cc710608ba5bea0b7a8f7cf5340a6c8a6a36503ec3f0d5d70e3f260dbdef479171b2e2d29c94a77a067a487a714fb8e36f08989b0a119010bcc860021fea11cc118a5bab1675c1ab8a0d693fae220718ad64c3b67fcfde6368cd85b088d2f140f202ee6903f1caf9f68a010547743ab18eb17ff66a4e000e107012d8a2d90af87ce70c9acf325f9c03ee6a0578a2e8429d88ac8439ce23fa53e56eae0a92f1de3c51f9c658ae31aa3cb795680",
"0xf90211a05a7d214557b3e4472543d120c70db7bc3755f414e89f0cc07cd46532c8c64106a0670d3d63dd5118edac19bf69c8f88556b3cb8c9856c57cc921d2655397ab206ea0864750b8004b867b2fb2acc9d7f18479bc894b15287b1d9f40e3b530aa3615dfa0aaed3727bb48773973be6d4335350ef28ccd1146523ec4bdb2c39b98d646b92fa06a714e2e31a89ee75e601ac711147ef0fe0ab7c4a36473a920e16f2c6b41b10ea02e0bc17148b579270dfe9c5fc040902666e4fbc78ef02817062eb5c921072c24a0f4aee87bb20dfc451986710b071bb7a5d7bd7003a656d3fc1de70e32515f2351a051de4ddd598509289966b7dfbc9f3e9bbdfa171cd2cd327a1f2396519cbf7512a0a2d97fe4fa7ed56639cd6fdfccc5b1feb00a76c30eec1e253d3fceee94a4dc9fa08c8274654579455ead172a4fbcc029fca0b79f93c5dfde63712c32db443debb6a09a804862a0d2eeb6b7e9b45eda74e9640d7d3f3555c16eb97e9e7dab365f68fea07deb877adf5588efe64de75a007d0697f7366d8c845e03dee9a955c20b9c0a5ca0ed13b7f02e243ec6c6a6b70c874a248b312cd1aa73d9a7c7fb9e7f78727f6ef6a0444fdaeda66d7a8a7028498423de12694290894c40f8834ea84e93dda1bb1a3ea0e9375a137de60208ba75c8b1c36bff40d4d2eb8526daad20061abb0d250b8922a05cd55c183b85439fd437676697936ca8fb62c4fd84ffa81091c3f7668eda822180",
"0xf90211a0c4bd07594c4580e0819a2b9000792afdce92aada7e5be9918581a9e621737329a07b0e259d9bcde5d4f8fb548b0b35978d68f9241a13910aaf70bbaba1531b18f5a04914617e152bbe18c1c67ec09b3f7eaea81467cb2c5838f9c4ebf173bb0c03b2a0f10be4ec4181209ac1fd7ee5eaa7b22af18bc58417d1577c6422dd12fe253595a02448a42b0b1800ce54da762d83883004f4ef91fb4a12942c0f847d74da39a792a013c8b3cc15d7842fb9c79a9a71f4523f50ed4b37d95557f4303203777a445472a08dfd1e525b4e56f2c003a4a8bbbdd47d7cfeaf1d501bfe41adac9adb0d186f75a0ca5950413b457388de78a19960db2ef78d31ed579d08786d6c92cc1309398572a08e78281cb4d27b20f6577c4df64f04824246f0884d3c85f5dd892a3911e00f81a05aab4fa83de83686d5f4252ab7deac30a3c7194871cd57785afedd9662321b2fa01f1a261f1f101f1322481e5d3bcddac47724f04b950f97a6b20dbb5571a5e8cca0c28d0d7c6eafe4514b3f11cd0af8f54bc063565c99dbffc843c61097c7510b82a00261d2596c1b3c7e71466944456f981b26da324be94c96406195e10baeef6f7ba0c1f4b2f7287df6238c90b21c2e3c2c718998bebe911296d8003676aa74ab7356a09e2a7f1e6609cdf12fff72b30e383aae9cc7737c387c3136ac67d71a8d0e32d0a0d670dee18f2e8aac1cefc42b9f4abea90e8bfbf76f68510ce40f1e6d48f619c580",
"0xf90211a0023acb0a1899e0dcd6542eb6f0cde82adc39ec5db85782420e259375bb801e2ca04d478e778795d730dbad0e70fd2e0ed99f70e881671b50bfa1f6b97010ea6320a0bac36113dbd9edcec87bef7057c82278b4b0b28edb99a9fbe4fc5bc081eb2815a09ea7780a9d6456aa29afcfe103a1afca3cb8f01466be4edb8dd7609f9b530ad7a0226a486fa9f8bcb3e58095e2051ad8672136c6937e8f02b4b3779ee41ee48189a0ad20673b23a08a04f80212b28573af10122b9d7dedd538c97b928f56d2fae471a0bd5267255873578a05206baaa252a7dfb0102f9951b0d2aa08f00d3491311ce2a0adbecfb5195af6eefc35a5d98f12351aced8f80c7e5d60355c08ffdd816e1f57a0199d248969b16aa6fc0078b4b3afb5b3e6d9746087db0a6ef022b47f56962220a0479d2794f682c1c7b38b3b7b0449d0e47d8604613ebbcfa15201edeb27c0183fa019ad2c70a00c2af7f56ff51377f785184519daf5488ac40644c57d17011ee7a7a0ae52372142f050345101f2c0d96a103a4cdaa567822ef6612762225c697f67f3a05906a6ac109ad03a7b78cb59cf801e570279eff04e12d81216e62c234e7b1b17a0eac10df9e05bbb9a0e3b47222648aa17c378c6f9c307666e6fff21ffc7fcf65da03da582bdf69f449c422fa6da13867d1f890ba8f6b4bef9982acfb1b378f97d6ba0a71905dc9427ef645488bfa67a0a4d7e82579d88eb6f1b0bda76ed96d48ae54680",
"0xf90211a0f125e49f87b46684d330e6ed4d635f6ab95e833b59fe2aad0eacce9115b89fbba08ad2ad42eab8c25efd0be4bbc05c41c990447d13f47dacccd0a7da6245a6e1eca015703da424739d0f797aa1d5167813f3f723a1476a2b08b76e562ef7d0cc7904a08fe5a481d2be3a8ff825b6949502c783edb9635bb475238f5bce813084ebdf16a01ded3d7b69c79ea0fa3c0066ef3be567395473e5101568fb5d348956a3f75805a011a2a4b913699c616ace57dbb1b843ed0c555067858d1257f6c6fc32d8663616a0e596c95af6f9794ff3cac4e141d910a5298865901cd0a51640b8ef1aeb2260a7a09ccc97ccb960d3d8fe7dfec8ad53ce94238f4ec693f565fa992bda4f85914eb4a04cf3465e41bbfb3f3710fcb9d713de65cde02369e8518e1637d75f3873e35a3da06ca40820034a4be3e1808a8f0435958b9572514ec53ccbef389e41cbedc3da7aa0476022836c5a9d409fac5f914c303c8f36dd31525a53ecdd17e15ca510d31323a04cf25c8f64339c66169dd4b20e5000299f2a854fe28e7b07b00881ab44b687c0a03e47316bcf8b3088e43f2f98d6c4cfef2428484d1ec126c980060cef9c069272a0abd91eb25120ffd1307055fde1e25aec30ef181319b388eb9f7edac4f7afd494a035f9ee3dbc7012ea4c1590e01f545f5d5f902c746ceb8f60ae7f839401df025ea093aafd9a5316aa553ce40f497c071f1288e874ff9f098e80c328d86fbec0bb8f80",
"0xf8f1a00ddf241f3e1356bd811241563e098b7e0c725c157a232a0cf562e1fa197adcc3a06b2969699975b8caa88032ca6d3ac34bacd4225477afa2255ed1b8150511849da0950026f59bf0f56d980235b4d3a35193901ec65077580220664c1714d60856cd8080808080808080a05c4fa4328578abed6556351808c859945a597040f67045ceb69ce90f5219d947a0fab984dff9a576f3e92dda0e2bda4d32b2f1449fdd7828b97671b77c28c46c27a0a01b91e87e2c1c3cf0ee045e9a616fa41d6a394d0b0e27e3e43da2af47add8dea0c4058bbcd397e4d5c0ac16e715b94923149a535b6598b65e46ea4af86b7a90ba8080",
"0xf87180808080a040f3530d721d081953510dff02d5381decd0cca6fa0692cd86e3921cb4cd2f8d808080a00be0bc890fb8de760431211e77de62bc70f433bcc89a8622b52c9241fb85bb6e808080808080a079297ca4ba33facf2f25f235f445a74268ae9505498858e9577ec7882ac7c7cb80",
"0xf84f8080808080808080808080808080de9c31471a99929945141e551b37cad7fa4462254ea552671a511f3a362564a0c90e7d6af3c13969b075bd0576e3c8f721ee84306327b3c86abc2bca159f52a380"
]
}
]
}Verifying this proof results in failure, with an error saying that 0x64 (the storage slot value) is expected but got None. This is caused by the verification code not digging into in-place encoded nodes when it encounters one. This proof happens to have a branch node that encodes child nodes in-place.
Proof in Merkle Patricia Trie must include the first divergent node. Currently we only include the nodes that share common prefix with the target key.
I am trying to replace triehash::ordered_trie_root with an equivalent function based on alloy-trie. Even if it works pretty well, sometimes alloy-trie panics with a cannot convert a slice of length 29 to FixedBytes<32> error. Here is a complete reproducer for the issue:
use std::collections::BTreeMap;
use alloy_primitives::{keccak256, B256};
use alloy_rlp::Encodable;
use alloy_trie::HashBuilder;
use nybbles::Nibbles;
fn triehash_ordered_trie_root<I>(iter: I) -> B256
where
I: IntoIterator,
I::Item: AsRef<[u8]>,
{
struct Keccak256Hasher;
impl hash_db::Hasher for Keccak256Hasher {
type Out = B256;
type StdHasher = plain_hasher::PlainHasher;
const LENGTH: usize = 32;
fn hash(x: &[u8]) -> Self::Out {
keccak256(x)
}
}
triehash::ordered_trie_root::<Keccak256Hasher, _>(iter)
}
fn alloy_ordered_trie_root<I>(iter: I) -> B256
where
I: IntoIterator,
I::Item: AsRef<[u8]>,
{
let hashed = iter
.into_iter()
.enumerate()
.map(|(i, v)| {
let mut buf = Vec::new();
i.encode(&mut buf);
(buf, v)
})
.collect::<BTreeMap<_, _>>();
let mut hb = HashBuilder::default();
hashed.iter().for_each(|(key, val)| {
let nibbles = Nibbles::unpack(key);
hb.add_leaf(nibbles, val.as_ref());
});
hb.root()
}
// This fails with error:
// cannot convert a slice of length 29 to FixedBytes<32>
#[test]
fn small_data() {
let data = &["cake", "pie", "candy"];
assert_eq!(triehash_ordered_trie_root(data), alloy_ordered_trie_root(data));
}
// This succeeds.
#[test]
fn big_data() {
let data = &["a_very_big_cake", "a_very_big_pie", "a_lots_of_candies"];
assert_eq!(triehash_ordered_trie_root(data), alloy_ordered_trie_root(data));
}
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.