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

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

CC BY-SA 3.0
2015-06-07T08:57:38.240Z
[This question](http://bitcoin.stackexchange.com/questions/9202/why-does-bitcoin-use-two-hash-functions-sha-256-and-ripemd-160-to-create-an-ad) touches on why RIPEMD was used.
Bardi Harborow
CC BY-SA 3.0
2015-06-07T04:07:50.810Z
2015-06-07T04:07:50.810Z
Backspace
<p>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 <code>log(2, N) * 32 bytes</code>, where N is the number of transactions in the block.</p>

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

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

<p>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, <a href="https://crypto.stackexchange.com/questions/9435/is-truncating-a-sha512-hash-to-the-first-160-bits-as-secure-as-using-sha1">like SHA512/160</a>). This would only take <code>log(2, N) * 20 bytes</code>.</p>

CC BY-SA 3.0
2015-06-07T09:52:30.387Z
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
<development><merkle-tree>
Is there a more space-efficient way to prove that a transaction is contained within a block?
Nick ODell
# Is there a more space-efficient way to prove that a transaction is contained within a block?

(Asked by: username_0 on 2015-04-08)

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](https://crypto.stackexchange.com/questions/9435/is-truncating-a-sha512-hash-to-the-first-160-bits-as-secure-as-using-sha1)). This would only take `log(2, N) * 20 bytes`.

**Tags:** development, merkle-tree

> **Comments:**
> **username_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.  

---

## 1 answers

### Answer by username_2 on 2015-06-07. Score: 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.

> **Comments:**
> **username_3**: [This question](http://bitcoin.stackexchange.com/questions/9202/why-does-bitcoin-use-two-hash-functions-sha-256-and-ripemd-160-to-create-an-ad) touches on why RIPEMD was used.  

---

