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 ...
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 ...
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 ...
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 ...
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
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
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
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.
4
votes
3answers
350 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 ...
1
vote
1answer
3k views

How do I compute merkle root for genesis block?

I wanted to help out the community and create a pure C application independent of the reference client, that given a timestamp and a public key, will produce a merkle root for creation of a genesis ...
0
votes
2answers
865 views

How can I make this PHP merkle root script recursive?

I've been trying to write my own merkle root script in PHP to help with my own understanding, but I've always struggled with recursion. I've managed to write the function that will hash pairs of ...
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 ...
6
votes
1answer
862 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 ...
4
votes
1answer
439 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....
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 ...
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 ...
2
votes
1answer
135 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 ...
1
vote
2answers
227 views

Restarting mining on new transaction

I understood that when a new transaction comes in, the miners have to start over, or at least change their merkle-tree to include the new transaction, essentially starting from scratch again. If I ...
0
votes
2answers
281 views

How Is Block Assembled?

I think I understand mining well enough, but what I don't get is how the blocks of transactions are assembled. According to this post - What exactly is Mining? - the miners assemble the blocks and ...
0
votes
1answer
72 views

How to efficiently find if in-address in transaction is valid and has required amount of data?

A transaction has in-bitcoin address. Transaction tells to transfer that address (in fraction or whole) to another address. Since the source of truth is block-chain, how does miner know that in-...