Questions tagged [merkle-patricia-tries]

Filter by
Sorted by
Tagged with
0
votes
0answers
12 views

Average case performance of a Modified Merkle Patricia Trie

I recently read this specification of a merkle-patricia Trie by Parity, which states that the performance of the Merkle Patricia Trie used in Ethereum is: [Merkle-Patricia Trees] provide the holy ...
1
vote
1answer
36 views

Compute transactions trie root hash from a BlockBodies message using ethereumjs

Given a decoded BlockBodies message, I want to compute the root hash of the transactions trie, so that I can match it against block headers that my node has downloaded. After reviewing How Ethereum ...
3
votes
0answers
31 views

Why using Merkle Patricia trie for keeping transactions and receipts instead of Merkle trie?

Using Merkle Patricia trie for keeping Ethereum states has the advantage of fewer changes in the data structure during the updates in the states compared to Merkle trie. But what is the advantage of ...
1
vote
1answer
31 views

If we put all 35 million active address into one MPT tree (Merkle Patricia Tree), how many bytes is the MPT?

As we all know, the more address there are, the more bytes the MPT tree (Merkle Patricia Tree) saves and there may be 35 million active address in Ethereum. If we put all 35 million active address ...
0
votes
0answers
13 views

How much compression do Merkle Patricia Trees actually provide?

I like the idea of a MPT but extra information has to be stored to build them.. so I'm wondering how much they actually compress the data. Is there actually data/statistics somewhere for how much ...
2
votes
0answers
31 views

Why does Ethereum have nested trie structure that a storage trie is under a account in state trie?

As I understand it, the leaf node of the state trie has account data. The account data has a storage root, and the variables of the contract are stored in the leaf node of the storage root. But ...
1
vote
1answer
34 views

Why does proof of non-inclusion is useful in Ethereum?

Currently Ethereum uses modified Merkle patricia trie and maybe plan to move to a sparse Merkle tree (SMT), which both support `proof of non-inclusion', i.e. allowing one to proof that some key does ...
0
votes
0answers
42 views

How Merkle Patricia Trie updates the account balance?

This is my understanding of the Merkle Patricia Trees in Ethereum so far: There are three kinds of merkle trees storing diff info - state, transaction and receipt. When a new block is added it ...
0
votes
0answers
35 views

Does it possible to perform Merkle root proof with filters?

I have a centralized e-commerce system with orders table inside. There are few order categories inside this system such as: Pending payment Pending shipping Pending delivery Completed Cancelled I ...
3
votes
0answers
79 views

Get proof that a transaction was included within a block

I see that the web3 api has the getProof method: https://web3js.readthedocs.io/en/1.0/web3-eth.html#getproof My question is - is there a similar way to get (and verify) a proof that a transaction x ...
2
votes
1answer
133 views

Implementing Merkle Patricia Trie

I am currently trying to implement Ethereum's Merkle Patricia Trie using Python 3.6 and I am having some troubles and honestly I am frustrated. I am using the following sources: Ethereum Wiki ...
1
vote
0answers
25 views

How can I recover the path to a specific transaction in the tx patricia merkle tree?

I'm working on a project where a non trusted entity is running an ethereum node (either geth or aleth), and has to pass information along to a non networked party. Namely, the non networked party ...
4
votes
0answers
146 views

How to generate a state root

I am trying to implement a Simplified World State Trie based on Merkle Patricia Tree. Take the following image for example there are four accounts address  value a711355   ...
1
vote
1answer
121 views

what is the role of merkle tree in ethereum? [duplicate]

I know the functionality of merkle tree, it makes a root hash from a group of data.My question is how merkle tree is act in ethereum blockchain,precisesly in the place of transaction hash,block hash,...
1
vote
1answer
42 views

Why do Merckle trees use nibbles

In Appendix D of the yellow paper for Ethereum, it describes the Modified Merkle Patricia Tree, and states: Any series of bytes may also trivially be viewed as a series of nibbles, given an endian-...
0
votes
0answers
19 views

Verify transaction was included in certain block within smart contract

Is there a good resource for proving that a particular transaction was included in block x?
1
vote
2answers
81 views

How are transactions stored in a block?

In State, use Merkle Patricia Trie for storing data. "key value" is account address(hash value). And also, Ethereum block uses MPT for storing transactions. However, Additionally Ethereum Block use ...
2
votes
0answers
628 views

How Merkle trees are implemented in a database exactly

I have just checked out these resources: What is a Merkle Tree? Beginner’s Guide to this Blockchain Component Using Merkle trees to detect inconsistencies in data Exploring the use of Hash Trees for ...
4
votes
2answers
284 views

Why are transaction tries in Ethereum not plain Merkle Tries?

I understand the Ethereum block header contains a Merkle Patricia Trie (MPT) root for the global state, one for receipts (which I don't understand but am not focussed on for now), and one for all the ...
3
votes
1answer
59 views

Ethereum Merkle Patricia Tree Riddle

since I spend some time on diving into the data structures that ethereum is based on, I stumbled upon the following task from a stanford course which i included at the bottom. I am struggling ...
2
votes
1answer
85 views

How do ethereum validate a OLD transaction(say 10k blocks ago) without sync/replay-ing the full node?

When a full node receives a freshly mined new block, it seems straightfoward how we could validate all the transactions contained in the block. As we already the current world state, we could just ...
1
vote
0answers
42 views

Calculating Merkle root on chain

I'd like to calculate a Merkle tree on chain, and then only store the root. The tree will track all balances for an ERC20 token. How many accounts would this be feasible for? If there are 1000 ...
2
votes
1answer
33 views

How to recreate a HexaryTrie from a saved database

I am trying to create a HexaryTrie from the database that the trie writes to. Here is my Code: from trie import ( HexaryTrie, ) db = {} trie1 = HexaryTrie(db) trie1[b'deadbeef'] = b'deadbeef' ....
0
votes
2answers
59 views

Using Python trie to build transactionsTrie. Why is my Transactionsroot wrong?

I am trying to build a TransactionsTrie with python. I am using this [trie][1]-Library. I followed the Instructions. Edit: Removed the original question because it was stupid. @carver Thank you ...
2
votes
1answer
363 views

Are number of transactions in Merkle Tree always “even”?

According to definition and structure of the Merkle Tree, apparently, the number of transactions in a block that inserted in a Merkle Tree structure must be even (and not odd), is not it? Please see ...
2
votes
1answer
71 views

Leaf node with encodedPath containing only Hex-Prefix in Merkle Patricia Trie

A leaf node is defined as the tuple [encodedPath, value], and encodedPath uses the Hex-Prefix encoding. Is it possible we have a leaf node with encodedPath having only the prefix and no partial path ...
1
vote
1answer
169 views

Merkle proof for Smart Contract mapping field data

I'm trying to get merkle proof for Ethereum Smart Contract mapping field data. I created test smart contract and deployed to test network. Smart Contract Code like following code: contract ...
1
vote
1answer
99 views

Which node to use in Merkle Patricia Tree when there are single and shared nibbles at the same point?

If I understood well, extension and leaf nodes should be used when there are shared nibbles, and branch nodes when there are differences. Which type of node should be used when storing a different ...
1
vote
1answer
757 views

How the blocks and tries are stored

Newbie here! I still not sure if I understood how some structures of Ethereum are physically stored (assuming Geth implementation) State Trie: only one off-chain Merkle Patricia Tries stored using ...
2
votes
1answer
164 views

ELI5 sparse Merkle trees on sharding

Lately, there's been some interest in sparse Merkle trees (SMTs). I know Ethereum uses Patricia tries (PTs), but this thread seems to indicate that working with SMTs would yield similar performance, ...
1
vote
0answers
72 views

Custom Merkle Patricia Tree

One of the requirements of building our company's DApp is to maintain a separate, custom Merkle Patricia Tree that contain's data from our company's platform only. The Tree needs all CRUD operations ...
8
votes
2answers
718 views

Why Merkle-Patricia Trie has three types of nodes?

I've been reading about Merkel Patricia Trie and I think that I understand how it works, but it looks a bit overcomplicated to me, which suggests that I do not understand it fully. Here is how Merkle ...
1
vote
0answers
64 views

Why is the transactionsRoot the same hash as “empty patricia merkle trie” root hash?

My setup is as follows: I am Using ganache-cli and metamask to send 1 ETH from account 1 to account 2. When I use JsonRPC to get the Information about Block 1 (the one with the transaction) the ...
1
vote
1answer
62 views

Sound but incorrect change in Merkle-tree

From the whitepaper, The first step in in verifying block validity is: Check if the previous block referenced by the block exists and is valid. With regard to a merkle tree propogating change ...
1
vote
1answer
50 views

Merkeling in Ethereum

I am currently facing the challenge to prove that a transaction is mined into a block. Dose anyone know libraries/tools that do this kind of thing? e.g.: create a proof that can be validated offline ...
3
votes
1answer
137 views

UTXO vs Account scalability paradigms and Merkle proof of ownership

From Ethereum's design rationale: Potential scalability paradigms: UTXOs are more theoretically compatible with certain kinds of scalability paradigms, as we can rely on only the owner of some coins ...
2
votes
1answer
605 views

How to store storage trie in leveldb?

I want to know the structure of storage trie and its data structure in leveldb, and I read solidity storage. I still have questions? In the yellow paper, it says that storage root is a mapping ...
2
votes
1answer
157 views

How to check member in merkle tree

If we want to check that data is member of it or not we will take the root, data block, and all the blocks in path between data and root. According to this picture if i want to check that data block, ...
0
votes
1answer
188 views

Why stateRoot, transactionsRoot and receiptsRoot not included in the blockheader of any etherscan ?

My question may be stupid. I'm trying to understand how ethereum is made and in all articles I read that a block header include a list of things and the stateRoot, the transactionsRoot and the ...
1
vote
1answer
184 views

Trie, Radix Trie, Patricia and Merkle Patricia Trie

Can you explain to me the main differences between these 4 tries? Thank you
1
vote
1answer
84 views

Addresses in paths of State Patricia Trie

Every block header has 3 patricia trees. In State Patricia Trie, the paths are the sha3 of the ethereum addresses, and the value for any particular address is encoded with RLP. But, what addresses ...
1
vote
1answer
98 views

Examples of light-client interactions to extract Merkle proofs?

I'd be grateful for pointers to working examples of interacting with the geth/parity light-client protocols. I'm particularly interested in working code which shows how to extract the Merkle proof ...
3
votes
1answer
502 views

How to calculate the merkle proof for quering the balance of a token holder?

I know this can be done through accessing the full node of Ethereum, but I want to know, how could I do it technically? Suppose I have an ERC20 token contract having address 0xabc.. and Alice is the ...
1
vote
1answer
1k views

What are the storage and state tries?

I have seen that nodes hold a storage trie and state trie. What are those tries and are there these two tries per a contract code (in every copy of the blockchain)?
1
vote
2answers
413 views

How do merkle and patricia trees co-exist

I understand how those tree's work separately, but i can't imagine how to put it in one structure. From ethereum's wiki: All substantial quantities of data in Ethereum are stored in a data ...
3
votes
1answer
193 views

JavaScript merkle-patricia-tree/secure - OutOfMemory when traversing large (~70Gb) state tries

I have the JavaScript code below, which is traversing the state trie from geth's leveldb for Ethereum mainnet Block #5200035. After some time with high cpu usage and having reserved about 6Gb RAM, ...
2
votes
2answers
284 views

Storage trie - are trie nodes reused for two contract instances with the same storage content?

Reading geth code and various posts here, I think I have now a good understanding of how the data is stored in Ethereum (please correct me if I am wrong at some point). At the lowest level we have a ...
1
vote
1answer
48 views

Reference a long-forgoten account

In the Etherem Blog Vitalik says: "but we do not store history older than 5000 blocks.". 1) Is it to be understood that the state Trie does not contain the state of accounts which were not in use ...
3
votes
0answers
28 views

Does any client maintain a mapping of hashes to addresses?

As explained in the Design Rationale wiki: Using sha3(k) as the key in the "secure tree" (used in the state and account storage tries): this makes it much more difficult to DoS the trie by setting ...
4
votes
1answer
290 views

Why are keys hashed in Merkle Patricia Trie?

Account addresses are hashed before they are recorded in the Patricia Merkle Trie, as well as storage slot indexes. This makes it difficult to enumerate all accounts and storage slots by scanning the ...