6

SPV clients, like Electrum, ask for cryptographic proof that a transaction is contained in a block. This is done by including each merkle branch necessary to get a hash that's equal to the merkle root of the block. This takes log(2, N) * 32 bytes, where N is the number of transactions in the block.

Is there a more space-efficient way to cryptographically prove that a transaction is contained within a block?

For the sake of argument, let's assume that you're allowed to change how the block header and merkle tree is calculated, or replace it altogether.

An example of a possible improvement would be to change the hash function used for building merkle trees from SHA256d to RIPEMD-160 (or another 160 bit hash function, like SHA512/160). This would only take log(2, N) * 20 bytes.

Improve this question
1
  • Very interesting question. At first I thought all you needed was the Merkle root to verify whether transactions were contained in such block. However, as you point out, you also need the entire branch, which as you say, could get kinda large. In the original paper Satoshi calculated in section "Reclaiming Disk Space" only the space required for headers, but not for actual branches, which are needed for this process to work. It also hurts decentralization because you still need full nodes to give you the branches.
    – Luca Matteis
    Jun 7, 2015 at 9:52

1 Answer 1

Reset to default
2

Other than shortening the hash used, there is no way of making the proof take less space.

On a side note, the hash can be made shorter by just using the first n bits. The checksum of a bitcoin address (first 4 bytes of sha256(body))is made in this way. I don't know why ripe160 is used instead of a truncated form of sha256 for the main body of the address.

Improve this answer
1

Your Answer

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

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