-3
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Is $B'$ a set or an element? Is $A$ a set of numbers? I think you misread the problem statement: Can you quote it? $\endgroup$
    – greybeard
    Commented Jul 21, 2022 at 7:11
  • $\begingroup$ As the question is stated, $A, x$ play no role at all. Something is wrong. $\endgroup$
    – user16034
    Commented Jul 21, 2022 at 7:49
  • $\begingroup$ I’ve quoted the original problem statement. $\endgroup$
    – Paul Yu
    Commented Jul 21, 2022 at 7:54

1 Answer 1

Reset to default
0
$\begingroup$

I don't undestand what is the difficulty you are having.

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*} $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ The x here is the difference of 2 sets, but I’d like to know the missing number in B. If B’ = B \ {y}, and B = A \ {x}, I’d like to know {y} $\endgroup$
    – Paul Yu
    Commented Jul 21, 2022 at 1:08
  • $\begingroup$ It's difficult to see a solution with two sets $A$&$B$ while convinced there is a more interesting set $B'$. $\endgroup$
    – greybeard
    Commented Jul 22, 2022 at 19:36

Your Answer

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

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