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.

Filter by
Sorted by
Tagged with
60
votes
6answers
63k 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 ...
23
votes
6answers
8k 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 ...
22
votes
3answers
7k 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 ...
17
votes
4answers
17k 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 ...
13
votes
3answers
11k 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 ...
8
votes
1answer
1k views

Adding instead of concatenating hashes in Merkle trees

Why aren't the hashes combined using a commutative operation such as addition instead of concatenating them? Any possible vulnerabilities or security flaws? thanks for your time and efforts.
7
votes
4answers
509 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
1answer
281 views

How do merkle trees ensure credibility to blockchain, when full node wrongly denies a presence of a txn in a block?

How can Merkle Trees ensure that a full node doesn't lie to a thin node that a txn t is not present in a block B if infact B contains t? How can a thin node tell if the full node is lying if the full ...
7
votes
2answers
4k 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 ...
7
votes
1answer
2k 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 ...
7
votes
1answer
1k 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 ...
7
votes
1answer
159 views

CVE-2012-2459 , possible code and performance improvement, is my logic correct?

ok so, in my effort to create a fullnode from scratch both for learning purpose and need (not a topic for discussion, thanks), I was looking at the code that check Merkle Root to not be vulnerable to ...
6
votes
2answers
423 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 ...
6
votes
1answer
2k 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 ...
6
votes
1answer
136 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
756 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 ...
5
votes
1answer
517 views

Is Bitcoin PoW actually SHA256 + Merkle generation? Or have I misunderstood coinbase/append?

Miners can mutate nonce (32 bits) + time (mutates once a second). This allows for 232 (~4 billion) hashes per second. That's not enough anymore for our ASICs as they perform in the TH/s now rather ...
5
votes
1answer
1k 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 ...
5
votes
1answer
645 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 ...
5
votes
2answers
2k 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 + ...
5
votes
1answer
892 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 ...
5
votes
1answer
465 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
390 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
428 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
3answers
69 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?
4
votes
2answers
190 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 ...
4
votes
1answer
2k 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.
4
votes
1answer
600 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
2answers
2k 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 ...
4
votes
1answer
3k 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
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?
4
votes
1answer
304 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 ...
4
votes
1answer
564 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, \"...
4
votes
1answer
159 views

How big would the transaction history be if all spent transactions were pruned?

If the transaction history's Merkle tree were pruned to remove all transactions that have been completely spent, what would be the size of the transaction history in comparison to its current size? (...
4
votes
1answer
785 views

How do I calculate the witness commitment hash for a given block?

From my understanding, every SegWit enabled block has an added output script which is used as a place to store the "Witness commitment" specified in BIP 141. One issue I've stumbled upon was ...
4
votes
1answer
150 views

Is Merkle tree pruning described in the whitepaper feasible/useful? If not, would there be any alternative?

When I was reading bitcoin-paper-errata-and-details.md written by David A. Harding, I realized that there's probably a common misunderstanding or over-simplification about Merkle tree pruning. What ...
3
votes
1answer
1k 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
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
3answers
359 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
2answers
490 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, ...
3
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....
3
votes
2answers
530 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
2answers
440 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 ...
3
votes
1answer
837 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
79 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
2answers
1k 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
2answers
1k views

How could we determine that a particular transaction in which block's Merkle tree?

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/ : If the light client wants to determine the status of a transaction, it can simply ask for a Merkle proof showing that a particular ...
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
1answer
843 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 ...
2
votes
1answer
322 views

RSA accumulator vs Merkle Proofs

For proof of inclusion (used by SPV nodes) Bitcoin relies on Merkle proofs. Why Merkle trees were chosen and not RSA accumulators, as they can be used to provide a shorter proof? What are the ...