26 votes

What is the Merkle root?

"Figure 7-2. Calculating the nodes in a merkle tree" from Mastering Bitcoin shows the Merkle Root (HABCD) of a list of four transactions: Tx A, Tx B, Tx C, and Tx D: To verify that a transaction—for ...
user avatar
  • 4,307
24 votes
Accepted

Merkle Root and Merkle Proofs

Reading your question, I suspect the cause for your confusion is around the setting in which Merkle trees are used. I think you are right that in the Bitcoin world, the setting is taken for granted ...
user avatar
  • 1,297
23 votes

Why does each block store a Merkle root?

Merkle roots do not verify transactions, they verify a set of transactions. Transaction ID's are hashes of the transaction, and the Merkle tree is constructed from these hashes. It means that if a ...
user avatar
  • 8,724
18 votes

Why does each block store a Merkle root?

Merkle roots are stored in Bitcoin block headers so as to enable efficient membership proofs for transactions in a block, which are necessary for Simple Verified Payment verification (SPV) nodes that ...
user avatar
  • 1,297
18 votes

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

If you have A, HB and HAB you can obviously check whether A fits. As Jestin noted this is essentially a full Merkle tree with two leaves. However, as a thin client, you only have readily available ...
user avatar
  • 63.4k
18 votes
Accepted

Adding instead of concatenating hashes in Merkle trees

There are a number of issues here, with different answers. Can Merkle trees use a commutative operation in general to combine hashes? Yes, but only if they aren't intended to commit to the order of ...
user avatar
11 votes
Accepted

Are number of transactions in Merkle Tree always "even"?

If there are an odd number of nodes on any level of the merkle tree, the last node is duplicated and hashed with itself.n If there were a Tx4, the diagram would look like this Root ...
user avatar
  • 61.4k
10 votes

Merkle Root and Merkle Proofs

Say a block consisting of these 10 transactions, noted by their txids at indexes 0 to 9: E1AF205960AE338A37174B407EE71067C3CD7F04D48A5CEC7E13F6ECCB61DCBC ...
user avatar
  • 1,804
9 votes

Merkle tree structure for 9 transactions

That's not exactly right. It's more like this: ROOT / \ / \ / \ ...
user avatar
  • 13.7k
9 votes
Accepted

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

You cannot obtain a list of transactions from the merkle tree. The merkle tree root is part of the block header, which as you said, allows quick verification of the proof-of-work. After the block ...
user avatar
  • 16.5k
9 votes
Accepted

Why was an insecure merkle tree implementation chosen?

As with many things in Bitcoin, it is likely simply because it worked well enough, and such an attack was not immediately obvious. Several of the choices made in the early days of Bitcoin don't have ...
user avatar
  • 16.5k
8 votes
Accepted

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

You are correct that effectively Bitcoin PoW involves computing the Merkle root every now and then in addition to the hash grinding. However, this is negligable. Even ignoring nTime rolling, the ...
user avatar
8 votes
Accepted

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

Your instinct is correct: a full node can lie-by-omission to a light client and deny them proof that a transaction was included in a block. This is a well-documented vulnerability of SPV wallets and ...
user avatar
  • 4,676
7 votes
Accepted

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? It is impossible. The solved block depends on every byte of transaction data, nothing can be ...
user avatar
  • 13.7k
7 votes
Accepted

Where is the Merkle tree located?

The Merkle tree is not stored anywhere. It is implicitly defined by the transactions in a block. Whenever needed, the portion of it that is needed is computed on the fly using the transaction ...
user avatar
6 votes

Pruning the branches in Merkle Tree

Sure: A leaf (transaction) can be pruned when all of its outputs have been spent. A node can be pruned when both of its children have been pruned. However, Bitcoin Core doesn't implement this kind ...
user avatar
  • 28.7k
6 votes
Accepted

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. Put the entire contents of the merkle tree in an array. Check that the result of hashing all ...
user avatar
  • 28.7k
6 votes
Accepted

When do miners stop waiting for new transactions?

They were never "waiting" in the first place. A miner is incrementing nonces and computing hashes continuously. As soon as a new transaction a2 arrives, it is added to the Merkle tree, the block ...
user avatar
6 votes
Accepted

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

You can use a Merkleized binary trie. You first hash all the elements of your set individually. In this example, I use a 3-bit hash function rather than 256-bit. Let's say you have 5 elements in ...
user avatar
6 votes
Accepted

How is the Leaf node weakness in Merkle Trees exploitable?

In Bitcoin, inner nodes of the merkle tree are constructed by concatenating two 32 byte SHA256d hashes together. The resulting 64 byte value is hashed to get the next node in the tree. The leaf nodes ...
user avatar
  • 61.4k
5 votes
Accepted

Are bitcoin Merkle trees always binary?

Merkle trees in general can have more child nodes, but the Merkle tree for transactional data in Bitcoin is a binary tree. "Merkle trees are binary trees of hashes." –Bitcoin-Wiki Protocol ...
user avatar
  • 63.4k
5 votes
Accepted

Mining Block header bit reversing

Let's take a look at this block, because it only has one transaction (the coinbase): 000000000000000000eb2d0ed97a7b2cff7f1408417dca83908004beb6fd9b95 Let's grab the raw hex data: ...
user avatar
  • 11.3k
5 votes
Accepted

Can SPV clients offer "proof of absence" of a transaction?

There is no known way to do this with the current consensus rules nor does it seem likely except via computationally expensive general ZKP. The normal way to make compact proofs of non-membership is ...
user avatar
  • 7,479
5 votes
Accepted

RSA accumulator vs Merkle Proofs

RSA accumulators are far harder to implement correctly RSA accumulators need a trusted setup (someone, or multiple someones, must come up with a sufficiently large integer that is the product of 2 ...
user avatar
4 votes

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

There are indeed many new transactions every second. The way miners deal with it is two-fold: If an appropriate proof-of-work is found on any merkle root, simply publish that block and any ...
user avatar
  • 7,629
4 votes
Accepted

Pairing pattern of txids in merkle tree

Transaction order in the block Currently, there are only two requirements for the order of transactions: The coinbase transaction is always first. Intra block dependencies must preceed, i.e. if ...
user avatar
  • 63.4k
4 votes
Accepted

Algorithmic efficiency for transaction lookup in blockchain

No, you can't. The block chain is a linked list of blocks, and each block contains an array of transactions. Block headers commit to a Merkle tree of the transactions in them, but they are sorted ...
user avatar
4 votes

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

From the original Bitcoin paper: ... we implement the proof-of-work by incrementing a nonce in the block until a value is found that gives the block's hash the required zero bits. Once the CPU ...
user avatar
  • 28.7k
4 votes

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

Forget about the Merkle tree. Assume that instead, the block header would just contain a hash of the concatenation of all transactions. A lightweight node could then download all headers, verify ...
user avatar
4 votes
Accepted

Merkle Root for 1-transaction block!

The merkle root of a block is the hash of all of the transactions. If there is one transaction, then the hash of all of the transactions is the hash of that one transaction. So the merkle root and the ...
user avatar
  • 61.4k

Only top scored, non community-wiki answers of a minimum length are eligible