27
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 ...
- 1,337
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 ...
- 8,822
19
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 ...
- 77k
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 ...
- 1,337
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 ...
- 108k
13
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 ...
- 71.5k
11
votes
Merkle tree structure for 9 transactions
That's not exactly right. It's more like this:
ROOT
/ \
/ \
/ \
...
- 14.2k
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
...
- 1,864
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 ...
- 17.2k
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 ...
- 17.2k
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 ...
- 108k
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 ...
- 5,174
8
votes
What are MATT opcodes?
Disclosure: I'm the author of the proposal called MATT.
MATT is an acronym for Merkleize All The Things, and is a research project for an approach to bitcoin smart contracts that only require ...
- 166
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 ...
- 108k
7
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 ...
- 29.5k
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 ...
- 108k
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 ...
- 23.1k
6
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:
...
- 11.9k
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 ...
- 71.5k
5
votes
Accepted
How particular node is searched in Merkle tree?
A Merkle tree is just a particular way of hashing a list of elements. In this application, the elements are transactions.
Finding something in a Merkle tree is just looking through the list. The ...
- 108k
5
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 ...
- 71.5k
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 ...
- 7,727
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 ...
- 108k
5
votes
Accepted
Are all transactions, whether SegWit or non-SegWit, part of the commitment in a coinbase transaction?
The wtxids of all transactions are committed to by the witness commitment tree in the coinbase transaction (except the coinbase wtxid itself, as that would be a cyclic dependency). This includes non-...
- 108k
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 ...
- 108k
4
votes
Accepted
What is the difference between Root Hash and Block Hash?
First, all transactions are hashed along a Merkle tree. The root of that tree is the Merkle root.
Then the block header is created with 6 fields: version number, the hash of the previous block, the ...
- 108k
4
votes
Is the hash of the coinbase transaction needed for the merkle root?
You make your list of transaction hashes(without the coinbase transaction, as you haven't mined the block),
This is where the problem in your understanding lies. The coinbase transaction is ...
- 11.9k
4
votes
Accepted
Are hashes of Merkle tree roots unique throughout whole blockchain?
The merkle root is a 32 byte hash.
As the hashing operation is sha256, it is exceedingly unlikely that you will find duplicates, but it is not, strictly speaking, impossible.
- 17.2k
4
votes
Accepted
Does the Merkle Root get constantly updated inside the block or does it only get added once the block is completed?
Once the mining pool has the list of all of the transactions they are including in that block, they calculate the merkle root for this list of transactions, then they distribute the block header, that ...
- 2,068
4
votes
Accepted
Proof-of-inclusion: Merkle Tress, derivation paths
My assumption is that when transaction proof of inclusion occurs
Which proofs of inclusions are you talking about? The only ones I'm aware of in the Bitcoin P2P protocol are those in BIP37 (server ...
- 108k
Only top scored, non community-wiki answers of a minimum length are eligible