# Identify the missing number in a set given its superset

Given a set B and B’s superset A, if B is missing 1 number (let’s y) but don’t know which number it is, how to find that number? That is,

B’ = B \ {y}, for some unknown element y
B = A \ {x}, for some unknown elements x
I’d like to know y.

The original context is from Problem6,

Miners A and B each have a set of transac- tions in their mempool. Suppose that miner A’s set is a superset of miner B’s. Miner A wants to send to B the transactions that B is missing. The problem is that A does not know which transactions B is missing.

a. Suppose B is only missing one transaction. Show that A can send a single 32-byte message to B that quickly lets B identify the missing transaction hash. B will send the missing transaction hash to A, and A will send back the transaction data.
Hint: Think of computing the xor of all the transaction hashes in A’s mempool.

So far, my thought is:

xor all numbers in A = C
C xor B = missing number and difference between 2 sets

And I’m stuck at here.

• Is $B'$ a set or an element? Is $A$ a set of numbers? I think you misread the problem statement: Can you quote it? Jul 21 at 7:11
• As the question is stated, $A, x$ play no role at all. Something is wrong. Jul 21 at 7:49
• I’ve quoted the original problem statement. Jul 21 at 7:54

If $$B = A \setminus \{x\}$$ for some element $$x$$, then: \begin{align*} \left( \bigoplus_{b \in B} b \right) \oplus \left( \bigoplus_{a \in A} a \right ) &= \left( \bigoplus_{b \in B} b \right ) \oplus \left( \bigoplus_{a \in A \setminus {x}} a \right) \oplus x \\ & = \left( \bigoplus_{b \in B} b \right ) \oplus \left( \bigoplus_{a \in B} a \right) \oplus x \\ &= 0 \oplus x = x. \end{align*}
• It's difficult to see a solution with two sets $A$&$B$ while convinced there is a more interesting set $B'$. Jul 22 at 19:36