Counting the number of tx in a block without downloading the whole block?

[jl2012]

Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)

[gmaxwell]

Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)

No, you can get an upper bound on the size by the depth of the tree if you get the coinbase (or any other) txn,  and a lower bound if you get given a transaction late in the block. You can get an exact measure by taking the rightmost branch and observing the duplicated hashes, but nothing more compact than that.

[hhanh00]

On a related note, what's the reason why the tx-count in the block header retrieved by getheaders always 0? It seems it would be as easy to return the actual count.

[jl2012]

Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)

No, you can get an upper bound on the size by the depth of the tree if you get the coinbase (or any other) txn,  and a lower bound if you get given a transaction late in the block. You can get an exact measure by taking the rightmost branch and observing the duplicated hashes, but nothing more compact than that.

Having a upper bound is probably good enough for me. The upper bound is the nearest power of 2, right?

As a related question, in the current protocol, could an SPV node requests for the x-th transaction in the y-th block, without knowing the txid of the transaction?

[TierNolan]

Having a upper bound is probably good enough for me. The upper bound is the nearest power of 2, right?

I think the Merkle path to the last transaction would give you the number of txids.  You could prove that it is the last by making sure that hashes are doubled.

You can work out which levels of the tree have an odd number of entries, and so has to double up the last hash.

As a related question, in the current protocol, could an SPV node requests for the x-th transaction in the y-th block, without knowing the txid of the transaction?

The merkleblock packet could be used as a response.  I don't think there is is a way to request a particular indexed transaction though.

Indexed lookups would be good though.  Parallel download would be easier if you could ask for the 100,000th block rather than having to download the first 99,999 blocks.  In almost all cases all peers would agree, so there is no risk.  Headers first makes this less of an issue though.