How does IBLT_diff reveal the transactions that needs to be retrieved?

Question

I understand IBLT (Invertible Bloom Lookup Tables) and as far as I know it is used to increase propagation speed by only sending the transactions to a full node that its missing instead of sending all transactions. In Gavin's specification it is mentioned that we do:

IBLT_diff = IBLT_new - IBLT_us

What I understand from this is that the full node checks and after comparing its IBLT with the miner's IBLT, the full node figures out which transactions are missing.
Then full node requests the transactions missing from the miner. Is this correct?
In the middle of the specification, it says that they are not using the full transaction hash and then it says that in order to prevent brute forcing it adds a salt to it. May I know why they are doing this and if so then how does full node know the transaction hash to request from if its truncated.

Answer 1

Then full node requests the transactions missing from the miner. Is this correct?

No. All transactions (including the missing ones) are already encoded into the IBLT (that the miner sent).

It's a little like a Sudoku puzzle. The miner sends you an empty sudoku with only the totals filled in. You throw in the transactions that you already know. And then you can work out all the remaining empty spots on your own.

And the main benefit is exactly to prevent having to ask the miner anything, because that adds round-trips around the internet and thus latency.

not using the full transaction hash

Probably because the hashes are large and the chance of a hash collision is not very high and not really a problem if it happens once a year (that's a number I just made up). So to save some space and/or make the calculations faster.

and then it says that in order to prevent brute forcing it adds a salt to it.

That's so an attacker can not generate 2 transactions on purpose that cause such a (trimmed) hash collision. If an attacker could do that, you would be unable to solve the Sudoku and you would be forced to get the transactions or block in a different manner (adding round trips and latency).

Note that there are other situations that would cause you to get stuck with an unsolved Sudoku. For example if you have just restarted your node, your mempool would be near empty so you don't have any transactions to start with.

Note that Rusty Russel also made a few blog posts on IBLT, those are more recent than Gavin's and might give you another perspective.