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

$\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
    Jul 21 at 7:11
  • $\begingroup$ As the question is stated, $A, x$ play no role at all. Something is wrong. $\endgroup$ Jul 21 at 7:49
  • $\begingroup$ I’ve quoted the original problem statement. $\endgroup$
    – Paul Yu
    Jul 21 at 7:54

1 Answer 1

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

$\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
    Jul 21 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
    Jul 22 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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