4

Since bitcoin uses binary Merkle trees (just learned that), 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.

Improve this question
3
  • Just to clarify: Are we talking about transaction lookup or UTXO lookup?
    – Murch ♦
    Commented Jan 28, 2016 at 15:30
  • @Murch I meant transaction lookup
    – Henrique Barcelos
    Commented Jan 28, 2016 at 16:59
  • 4
    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
    Commented Jan 28, 2016 at 17:38

1 Answer 1

Reset to default
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.

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.

Improve this answer
6
  • 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
    Commented Jan 28, 2016 at 17:07
  • @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
    Commented Jan 28, 2016 at 17:36
  • 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
    Commented Jan 28, 2016 at 17:42
  • 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
    Commented Jan 28, 2016 at 18:07
  • 1
    @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 ♦
    Commented Jan 28, 2016 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.