Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [merkle-tree]

A hash-tree used to allow efficient and secure verification of contents of large data structures. Merkle-Trees are employed in Bitcoin to prove existence of transactions in a block.

51
votes
6answers
53k views

What is the Merkle root?

The Bitcoin wiki Vocabulary article explains why the Merkle root exists: Every transaction has a hash associated with it. In a block, all of the transaction hashes in the block are themselves ...
20
votes
3answers
5k views

What is the benefit of using a Merkle Root rather than simply hashing all of the transactions in the block?

I understand what the merkle root is and how it is calculated, but I have not been able to figure out what is the actual purpose behind using this kind of hashing solution? I mean, I know that the ...
16
votes
4answers
15k views

Why does each block store a Merkle root?

I understand how a Merkle root is calculated and stored in the block. But how do miners verify a transaction using the Merkle root? Here are 18 conditions that verify a transaction. None of them uses ...
10
votes
5answers
2k views

Merkle Root and Merkle Proofs

This is one of those questions that everyone seems to write about but the same bad explanations are just plagiarized from site to site. Edit: The heart of my question is why Merkle trees are claimed ...
7
votes
4answers
499 views

How is it possible that transactions can be added to a block currently being mined?

It seems counter-intuitive that the current block can be hashed and transactions can be added to it, however that is what this thread indicates. Can someone help me connect the dots (not necessarily ...
7
votes
3answers
7k views

Why is the full Merkle path needed to verify a transaction?

If I have transaction A and wish to verify that it is in the block, and I also have the hash of transaction B and the hash of the hashes of A and B, then can't I just hash A and then see if what I get ...
7
votes
1answer
1k views

Are bitcoin Merkle trees always binary?

I've been doing a lot of research about bitcoin, trying to understand it at the bit & byte level. I was wondering about the lookup efficiency of the Merkle tree. I haven't found any evidence ...
6
votes
2answers
2k views

How do you create a merkle tree that lets you insert and delete elements without recomputing the whole thing?

I have a merkle tree. The elements of this tree are in sorted order, so that anyone can create a proof that something isn't in the tree. So far, so good. However, I also want to be able to add and ...
6
votes
1answer
120 views

Is there a more space-efficient way to prove that a transaction is contained within a block?

SPV clients, like Electrum, ask for cryptographic proof that a transaction is contained in a block. This is done by including each merkle branch necessary to get a hash that's equal to the merkle root ...
6
votes
2answers
678 views

How do pool operators do their hashing?

For every "getwork" served by the pool, a Merkle root must be calculated for a block. The run time of SHA-256 is proportional to the number of "chunks" of 256 bits, and a typical block will have ...
6
votes
1answer
863 views

What is the canonical way of creating merkle tree branches?

I'm currently looking into creating some compact merkle tree branches to prove that a given hash was included in a given merkle root. My initial thought was to list the leaf, the merkle root and all ...
5
votes
1answer
1k views

What order do transactions appear in a block? Is it up to the miner?

It seems to be random or up to the miner from what I can tell. But to store blocks, one must keep the order of the transactions (in some position column, etc) because regenerating the block for later ...
5
votes
1answer
222 views

How to build Merkle root from merkle branches?

Is there any help/tutorial on how to build the Merkle root from stratum data? The Slushpool's stratum protocol has an example of a mining job but it does not contain any Merkle branches and I don't ...
4
votes
3answers
352 views

How hard is it to alter a block after it was found?

Once a miner has found a block, how easy it is for him to add or remove a tx included in that very block? Would he have to solve the modified block from the scratch or is there a point he can resume ...
4
votes
1answer
376 views

Why was an insecure merkle tree implementation chosen?

At risk of creating a "lets discuss politics" question, let me clarify that what I want to know is whether there is a known benefit to Satoshi's "duplicate the last hash" merkle tree implementation ...
4
votes
2answers
135 views

Does a Block contain the list of transactions? Or only the Merkle Tree?

I was wondering how a block encodes its set of transactions. I know a Merkle Tree is generated, and that it encodes a Hashed version of the transactions. But is the Merkle Tree included in the Block ...
4
votes
1answer
442 views

Where is the Merkle tree located?

I am reading about the Merkle tree, I've read that in a block we store just the root of the tree. To check if a ttransaction is included in the Merkle tree we need to use the transaction's Merkle path....
4
votes
1answer
879 views

Merkle tree structure for 9 transactions

I've been reading the developers documentation, other sources and the good books about Bitcoin. But none of the resources shows a merkle tree with 5 or more leafs. I'm confused, does the bitcoin core ...
4
votes
1answer
2k views

Algorithmic efficiency for transaction lookup in blockchain

Since bitcoin uses binary Merkle trees (just learned that), I want to know what would be the algorithmic efficiency for transaction lookup in the blockchain. I don't know exactly how the data ...
4
votes
2answers
1k views

Mining Block header bit reversing

While trying to understand the mining process and checking in python..... i am puzzled with which info from/to pool are in Little Endian, which one needs reversing in building the block header + ...
3
votes
1answer
213 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 ...
3
votes
1answer
666 views

When do miners stop waiting for new transactions?

I know my question might sound familiar to the question as follow: When does a miner decide to stop collecting transactions and start calculating hashes to try to win? But actually, the reply marked ...
3
votes
3answers
57 views

If SPV clients didn't exist, would Bitcoin still use Merkle trees?

I understand how full nodes use Merkle proofs to convince SPV clients that certain transactions are valid / invalid. Does the Bitcoin software use Merkle trees in any other way?
3
votes
3answers
324 views

Where is the incentive to update the Merkle root

I've just read the following question Does block size effect Miner's Hashing speed? and it appears that the answer is no - since miners only need to hash the Merkle root. However, updating ...
3
votes
1answer
233 views

How is the Leaf node weakness in Merkle Trees exploitable?

Recently a weakness in leaf nodes of merkle trees was disclosed and it is claimed that this issue is exploitable to trick SPV nodes. How does the weakness make SPV nodes vulnerable to attack? What ...
3
votes
1answer
1k views

Algorithm of checking whether an element is present in a merkle tree

I've read and watch about merkle trees but can't figure out how to implement is_present(element) method. Explainations and links are accepted.
3
votes
1answer
1k views

Pruning the branches in Merkle Tree

In Merkle tree, leaves are actual transactions and internal nodes are hash of their childrens. In the Bitcoin paper, Satoshi talks about pruning branches in the Merkle tree to save storage space. ...
3
votes
2answers
916 views

What is the difference between Root Hash and Block Hash?

I was reading about how Bitcoin works from Satoshi's original paper. I had a query while going through the 7th paragraph. What is the difference between Root Hash and Block Hash? Isn't the block hash ...
3
votes
2answers
450 views

How do you know that Block, the Merket Root & the hashes in the path are authentic?

I went through this Q & A on Merkle Root What is the Merkle root? And several others on the Merkle Root & the Merkle Tree. I understand what is a Merkle Tree & how you can take use your ...
3
votes
1answer
640 views

How can I verify my merkle root function is correct?

I've started playing with Bitcoin on a more technical level recently (I'm an experienced software developer but just a user of Bitcoin up until now). I'm trying to implement a function to calculate a ...
3
votes
1answer
2k views

Pairing pattern of txids in merkle tree

For constructing the merkle tree txids are paired and hashed. ¹ But how are these txids paired? Does it happen chronologically or is there a certain pattern of pairing?
3
votes
1answer
740 views

How does a client get the merkle branch of a transaction?

When the Bitcoin client receives a transaction, it checks if the transaction is confirmed. This is done by verifying that the transaction hashes correctly, in the merkle tree, to the merkle root in a ...
3
votes
1answer
38 views

Question about identical txids/merkle tree in Developer guide

I am new to the technical details about Bitcoin and has been reading Developer guide on bitcoin.org. I have a question about below contents mentioning merkle tree, identical txids. I googled and ...
3
votes
1answer
215 views

Mining Process - Transactions Selection

I started reading about Bitcoin a few weeks ago. Reading most the information and watching videos on the web, I though I understood about the mining process. However, I was shocked when I realized ...
3
votes
1answer
430 views

How do I get merkle branches using the Stratum protocol?

I need to get the merkle branch quickly for a known TX. I have connected to various stratum servers, but whenever I send the method below I get "HTTP code 405 - Method not allowed". { \"id\": 1, \"...
3
votes
1answer
523 views

Checking the Merkle Root for Block #100000

The below text is copied from the Bitcoin Developer Reference at bitcoin.org: If a block has three or more transactions, intermediate merkle tree rows are formed. The TXIDs are placed in order and ...
3
votes
1answer
1k views

What is the purpose of Merkle Tree in blocks?

The leaves of the Merkle Tree has the hash of the transactions. How are transactions stored in the block? What is the purpose of Merkle Tree.
2
votes
2answers
388 views

How often do miners recalculate the merkle root they're working on?

I think that I understood most of the things about Bitcoin but there is still a mystery. We can see on https://blockchain.info/ that there are up to 4/5 new transactions every seconds. My question ...
2
votes
2answers
95 views

Example of data that is hashed in the merkle tree for a transaction

So I am reading this (excellent resource) on the Bitcoin merkle tree for a transaction. The merkle tree is constructed bottom-up. In the following example, we start with four transactions, A, B, C, ...
2
votes
2answers
126 views

Can SPV clients offer “proof of absence” of a transaction?

So light SPV clients give the user the ability to obtain merkle proofs (from a full node) that a given transaction is included in a block. Is there some cryptographic mechanism by which an SPV client ...
2
votes
1answer
365 views

Is the hash of the coinbase transaction needed for the merkle root?

first time posting here. I was interested on how mining software works down to the bytes. I came across this well written article right here: http://www.righto.com/2014/02/bitcoin-mining-hard-way-...
2
votes
2answers
153 views

While calculating merkle proof, where are the other hashes being stored?

Consider that I have a merkle root made up of transactions a,b,c,d,e,f,g,h. The root is H( H(H(a)+H(b)) + H(H(b)+H(b)) ) + H( H(H(b)+H(b)) + H(H(b)+H(h)) ). Now, I have to verify whether transaction ...
2
votes
2answers
229 views

Who gives SPV nodes merkle path to do validation for small subset of transaction?

From Mastering bitcoin: Merkle trees are used extensively by SPV nodes. SPV nodes don’t have all transactions and do not download full blocks, just block headers. In order to verify that a transaction ...
2
votes
1answer
993 views

What shape of merkle tree does the Bitcoin client build?

The Bitcoin client builds a merkle tree to represent the transactions, then includes the root of that tree in the block header. But usually, the number of transactions is not a power of two. When ...
2
votes
1answer
261 views

How is the Merkle Tree sequentially propagated, and are the parts addressed?

When downloading the Merkle Tree, are all branches from the root downloaded in order? Are the individual pieces of the tree cataloged in such a way so that the position of each piece is known? In ...
2
votes
1answer
197 views

How do transactions fit into mining? [duplicate]

One question about the inner working of the mining process: I know there isn't such a thing as a block 30% or 99% mined, or a mine is blocked or it isn't, I get it. The thing is: how do the ...
2
votes
1answer
58 views

How come Merkle tree is more efficient when tree branches are not stored in blockchain?

Suppose we have 8 transactions in a block X as follows and we know every node's hash value of the whole Merkle tree (that is, including intermediary nodes such as 45). Then if someone claims ...
2
votes
1answer
216 views

Transactions used to form a block

I've read the Developers Guide ( bitcoin.org/en/developer-guide ), asked a few peers and I still don't understand how the transactions are used to form the block. I did get that the transactions are ...
2
votes
1answer
1k views

Get confused on the merkle tree algorithm

From page https://en.bitcoin.it/wiki/Protocol_specification , I understand the merkle tree works like merkle([a,b,c,d]) = h( h(a,b), h(c,d) ) But when I do the stratum protocol http://mining....
2
votes
1answer
558 views

Is pruning of the merkle tree implemented in the bitcoin android wallet?

I know that satoshi's client doesn't prune, because we need to store all the transactions so that we can send them to other nodes. But does this android bitcoin wallet from de.schildbach prune? ...