|
Title: Counting the number of tx in a block without downloading the whole block? Post by: jl2012 on March 04, 2015, 05:54:04 AM Is it possible to count the number of tx in a block without downloading the whole block? (e.g. only using the Merkle tree)
Title: Re: Counting the number of tx in a block without downloading the whole block? Post by: gmaxwell on March 04, 2015, 06:19:46 AM 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.Title: Re: Counting the number of tx in a block without downloading the whole block? Post by: hhanh00 on March 04, 2015, 10:16:45 AM 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.
Title: Re: Counting the number of tx in a block without downloading the whole block? Post by: jl2012 on March 04, 2015, 10:58:27 AM 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? Title: Re: Counting the number of tx in a block without downloading the whole block? Post by: TierNolan on March 04, 2015, 11:52:51 AM 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. Quote 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. |