<p>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.</p>

<p>There is however also no need for that in normal operation of a Bitcoin node or wallet.</p>

<p>For verification, a set (which is internal to the operations of a node, and not part of the block chain) of unspent transaction outputs is maintained, indexed by txid (the so-called UTXO set). This set represents the 'state' of the ledger at a given point in the block chain, and blocks can be seen as 'patches' to the UTXO set: transaction inputs remove ("spend") entries from the UTXO set, and transaction outputs create new ones.</p>

<p>Wallets maintain their own set of transactions relevant to the user's balances. These are typically indexed, but much smaller than the set of all transactions in the blockchain, and often just kept in memory.</p>

CC BY-SA 3.0
2016-01-28T17:07:51.477Z
So, Might I say that the algorithmic efficiency of a transaction lookup is `O(k*log2(n))`, where `k` is the blockchain length and `n` is the number of nodes in the tree?
Henrique Barcelos
CC BY-SA 3.0
2016-01-28T17:36:13.623Z
@HenriqueBarcelos I think it's O(n) where N is ALL transactions ever. You may want to look at the -txindex option to bitcoind. I think that should create an index on all transactions making it (I assume) O(log n) or better.
Jannes
CC BY-SA 3.0
2016-01-28T17:42:10.150Z
For example: _given a transaction id, starting from the head of the chain, I'd lookup for the transaction by traversing the Merkle tree. If I don't find it, then move to the previous block and so on..._ Would this be possible?
Henrique Barcelos
CC BY-SA 3.0
2016-01-28T18:07:38.473Z
There is no Merkle tree for you to traverse. The Merkle tree is not in the block chain, it's just how some of its hashes are computed.
Pieter Wuille
CC BY-SA 3.0
2016-01-28T18:08:20.367Z
The time is O(n), with n the number of all transactiins ever, if all you have is the block chain.
Pieter Wuille
CC BY-SA 3.0
2016-01-28T18:38:45.880Z
@HenriqueBarcelos: To put it in another phrasing: The transactions are not ordered in any specific way in the blocks, they are just a linear list. If you don't know where to find the transaction, and only have the id, you'd have to look at all transactions until you find it.
Murch
CC BY-SA 3.0
2016-01-28T15:31:18.273Z
2016-01-28T15:49:02.940Z
2016-01-28T15:49:02.940Z
Pieter Wuille
<p>Since bitcoin uses binary Merkle trees (<a href="https://bitcoin.stackexchange.com/questions/42624/are-bitcoin-merkle-trees-always-binary/42625#42625">just learned that</a>), I want to know what would be the algorithmic efficiency for transaction lookup in the blockchain.</p>

<p>I don't know exactly how the data structure underneath the blockchain is organized.</p>

<p>AFAIK, each block contain a single Merkle tree, which can be related to the previous block tree by the <code>prevId</code> field in its own block header.</p>

<p>Given all that, I was wondering if, given a <code>TXID</code>, I would be able to locate that transaction in the blockchain in logarithmic time (<code>O(log2 n)</code>) as just a simple tree traversing, or if there are some hidden details I'm not considering.</p>

CC BY-SA 3.0
2016-01-28T15:30:10.500Z
Just to clarify: Are we talking about transaction lookup or UTXO lookup?
Murch
CC BY-SA 3.0
2016-01-28T16:59:43.263Z
@Murch I meant transaction lookup
Henrique Barcelos
CC BY-SA 3.0
2016-01-28T17:38:50.067Z
Just to clarify a possible misunderstanding: "binary Merkle trees" (in Bitcoin blocks) are not used for looking up transactions. They're used to construct proofs that a transaction is contained within a block, in as few bytes as possible.
Jannes
<algorithms><merkle-tree>
Algorithmic efficiency for transaction lookup in blockchain
Henrique Barcelos
# Algorithmic efficiency for transaction lookup in blockchain

(Asked by: username_0 on 2016-01-28)

Since bitcoin uses binary Merkle trees ([just learned that](https://bitcoin.stackexchange.com/questions/42624/are-bitcoin-merkle-trees-always-binary/42625#42625)), I want to know what would be the algorithmic efficiency for transaction lookup in the blockchain.

I don't know exactly how the data structure underneath the blockchain is organized.

AFAIK, each block contain a single Merkle tree, which can be related to the previous block tree by the `prevId` field in its own block header.

Given all that, I was wondering if, given a `TXID`, I would be able to locate that transaction in the blockchain in logarithmic time (`O(log2 n)`) as just a simple tree traversing, or if there are some hidden details I'm not considering.

**Tags:** algorithms, merkle-tree

> **Comments:**
> **username_1**: Just to clarify: Are we talking about transaction lookup or UTXO lookup?  
> **username_0**: @username_1 I meant transaction lookup  
> **username_2**: Just to clarify a possible misunderstanding: "binary Merkle trees" (in Bitcoin blocks) are not used for looking up transactions. They're used to construct proofs that a transaction is contained within a block, in as few bytes as possible.  

---

## 1 answers

### Answer by username_3 on 2016-01-28. Score: 4 | Accepted answer

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.

There is however also no need for that in normal operation of a Bitcoin node or wallet.

For verification, a set (which is internal to the operations of a node, and not part of the block chain) of unspent transaction outputs is maintained, indexed by txid (the so-called UTXO set). This set represents the 'state' of the ledger at a given point in the block chain, and blocks can be seen as 'patches' to the UTXO set: transaction inputs remove ("spend") entries from the UTXO set, and transaction outputs create new ones.

Wallets maintain their own set of transactions relevant to the user's balances. These are typically indexed, but much smaller than the set of all transactions in the blockchain, and often just kept in memory.

> **Comments:**
> **username_0**: So, Might I say that the algorithmic efficiency of a transaction lookup is `O(k*log2(n))`, where `k` is the blockchain length and `n` is the number of nodes in the tree?  
> **username_2**: @username_0 I think it's O(n) where N is ALL transactions ever. You may want to look at the -txindex option to bitcoind. I think that should create an index on all transactions making it (I assume) O(log n) or better.  
> **username_0**: For example: _given a transaction id, starting from the head of the chain, I'd lookup for the transaction by traversing the Merkle tree. If I don't find it, then move to the previous block and so on..._ Would this be possible?  
> **username_3**: There is no Merkle tree for you to traverse. The Merkle tree is not in the block chain, it's just how some of its hashes are computed.  
> **username_3**: The time is O(n), with n the number of all transactiins ever, if all you have is the block chain.  
> **username_1**: @username_0: To put it in another phrasing: The transactions are not ordered in any specific way in the blocks, they are just a linear list. If you don't know where to find the transaction, and only have the id, you'd have to look at all transactions until you find it.  

---

