I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a Merkle tree containing all of the items.
2. Give the client the Merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the Merkle root.
4. The client hashes the item, then hashes each Merkle branch, starting at the bottom.
5. If the hash at the end equals the Merkle root, the item is in the set.

The problem with this is that it takes $2*32*log(2, N)$ bytes of bandwidth (where N is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a Merkle tree containing all of the items.
2. Give the client the Merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the Merkle root.
4. The client hashes the item, then hashes each Merkle branch, starting at the bottom.
5. If the hash at the end equals the Merkle root, the item is in the set.

The problem with this is that it takes $2\cdot 32 \cdot \log_2{N}$ bytes of bandwidth (where $N$ is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a merkle tree containing all of the items.
2. Give the client the merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the merkle root.
4. The client hashes the item, then hashes each merkle branch, starting at the bottom.
5. If the hash at the end equals the merkle root, the item is in the set.

The problem with this is that it takes $2*32*log(2, N)$ bytes of bandwidth (where N is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a Merkle tree containing all of the items.
2. Give the client the Merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the Merkle root.
4. The client hashes the item, then hashes each Merkle branch, starting at the bottom.
5. If the hash at the end equals the Merkle root, the item is in the set.

The problem with this is that it takes $2*32*log(2, N)$ bytes of bandwidth (where N is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a merkle tree containing all of the items.
2. Give the client the merkle root, (32 bytes) out of band.
3. Give the client the item, then each branch leading to the merkle root.
4. The client hashes the item, then hashes each merkle branch, starting at the bottom.
5. If the hash at the end equals the merkle root, the item is in the set.

The problem with this is that it takes $2*32*log(2, N)$ bytes of bandwidth (where N is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.

I have an unchanging set of unique items, and I want my server to show one of those items to a client, then cryptographically prove that the item is part of the set.

How I do this currently:

1. Generate a merkle tree containing all of the items.
2. Give the client the merkle root, (32 bytes) out of band.
3. Give the client the item, then the branch leading to the merkle root.
4. The client hashes the item, then hashes each merkle branch, starting at the bottom.
5. If the hash at the end equals the merkle root, the item is in the set.

The problem with this is that it takes $2*32*log(2, N)$ bytes of bandwidth (where N is the number of items in the set.) Is it possible to do this is in a smaller space?

The scheme needs one additional property, which is that once you have all of the items, it must be possible to determine that you have all of the items in the set.

Other factors:

• The set isn't private - it's okay if the scheme reveals information about other members of the set.