26

"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 example, that with hash HK—is a valid transaction (i.e., part of a list of, in this example, 16 transactions with hashes HA, HB, … HP), one need only perform ...


23

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 single detail in any of the transactions changes, so does the Merkle root. It also means that if the exact same transactions are listed in a different order, ...


20

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 and is not usually explained clearly. Here's my two cents. To understand the efficiency aspect of Merkle trees, consider the two parties that are actually ...


18

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 only store block headers and not block contents. It is misleading to say that "Without the Merkle root in the block header, we would have no cryptographic ...


16

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 the leaves. Clearly when a commutative operation is used, [A,B,C,D] and [D,C,A,B] will hash to the same thing. This is not a problem if the Merkle root is ...


15

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 the Merkle root (which is in the block header) and get told about A. The intermediate levels of the Merkle tree are not provided, therefore, to calculate them, ...


13

To see how it simplifies verification, consider that in order to verify a transaction T is part of the blockchain, the verifier has to get from the transaction hash to the merkle root. If there are n transaction, there are log_2(n) levels to climb in the merkle tree, so to speak. To climb from the transaction T's hash to its parent P, we only need its ...


11

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 (Hash01234444) / \ Hash0123 Hash4444 / \ / \ Hash01 ...


10

Say a block consisting of these 10 transactions, noted by their txids at indexes 0 to 9: E1AF205960AE338A37174B407EE71067C3CD7F04D48A5CEC7E13F6ECCB61DCBC A314970CD7C647D1CC0A477E1A2122B98205B6924B73001B8DAB20EE81C2F4F7 B08EB9DCE0452A1B1970C4D29E88BDEE07669A2A5D1B08586D7FFA17B2E3F6B5 958B9E94AEA9A485BA494C50FB3192558057F7CAED9705D4B11369F071F10642 ...


9

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 header, each block contains a list of serialized transactions in the order they appear in the merkle tree. A complete block is a block header + list of ...


9

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 a full justification behind them, and were simply made because it worked at the time without any major, obvious shortcomings. This is one such scenario, as far ...


8

That's not exactly right. It's more like this: ROOT / \ / \ / \ / \ z1 z2 / \ / \ / \ ...


8

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 Merkke root computation is just a dozen or so hashes every 232. It's so little because not the entire Merkle tree needs recomputation; just the coinbase transaction ...


8

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 the only mitigation really is to connect to more peers (you only need one "honest" peer). This problem is also somewhat addressed by BIP157 aka "...


7

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 changed. It is important that it be this way. What if I could broadcast a solved block but leave out the transaction where I sent coins to someone else, ...


6

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 of pruning. It was built on the assumption that you download and validate all blocks. Because of this, it operates in one of two modes: No pruning (the ...


6

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 identifiers.


6

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 of the elements equals the root of the merkle tree. (If not, this is not the correct merkle tree.) Check if the element is in the array. This takes O(n) time ...


6

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 header is regenerated, and hashing continues with the new block header. It's misleading to call this a "restart", since that implies there was some progress that ...


6

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 your set, and they hash to: A: 011 B: 101 C: 111 D: 001 E: 010 Now you arrange them in a tree, by using the bits of the key hash as split conditions: root 0 0 ...


6

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 are the transactions themselves. Merkle trees are used to prove that a transaction is part of a block as the merkle root is placed in the block header for the ...


5

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 Documentation "From these txids, the merkle tree is constructed by pairing each txid with one other txid and then hashing them together." –Developer ...


5

The Stratum server is delivering a partially hashed merkle branch in the response… for which the miner needs to provide, ‘A’ (the generation/coinbase transaction) concatenated with the ‘first’ transaction (B). The remaining elements of the array are ‘pre-computed’ portions of the merkle tree. As indicated on slush’s bitcoin.cz site (http://mining.bitcoin.cz/...


5

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 to have a hash tree which is ordered by the key you're looking to prove non-membership on. The proof is just the two neighbors that are greater and lesser than ...


5

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 primes, and then throw those individual primes away). Bitcoin is generally designed to avoid trusted parties. For a 128-bit security level, you need at least 3000 ...


4

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 effort has been expended to make it satisfy the proof-of-work, the block cannot be changed without redoing the work. As later blocks are chained after it, the work ...


4

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 chronologically, not by txid, so you need a linear search. If you want to find a transaction in a block quickly, you'll need an external index data structure. ...


4

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 transactions that did not make it into the block go into the next block (assuming sufficient fees) Otherwise, calculate a new merkle root every so often (varies per miner,...


4

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 their proof of work, and make the assumption it has seen the longest chain. It is now convinced it has seen the chain the network accept. This is different from a ...


4

Let's take a look at this block, because it only has one transaction (the coinbase): 000000000000000000eb2d0ed97a7b2cff7f1408417dca83908004beb6fd9b95 Let's grab the raw hex data: ...


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