penumbra
penumbra copied to clipboard
Add FMD `Clue`s to transactions
Is your feature request related to a problem? Please describe.
Currently, we include FMD keys in the key hierarchy and in addresses, but don't include Clue
s in transactions, so it's not possible to use FMD to detect them.
At this stage, supporting FMD as an accelerated scanning mechanism doesn't help us, because we don't have enough transaction volume that the scanning is actually a bottleneck, and this will continue to be the case for some time.
However, we want to be forward-compatible enough to be able to implement detection later, when it's useful to do so. Including detection keys in addresses is the first step. The next step is to include Clue
s in transactions.
The original idea was to attach an FMD Clue
to each OutputBody
, since each OutputBody
contains a new NotePayload
to be scanned, and to thereby filter the scanning to be done. But actually, this doesn't work, and would wreck privacy.
The problem is that each transaction contains a group of outputs, but the FMD detection false positives are all independent, occurring with probability $p$. This gives a distinguisher between true and false positives that isn't part of the original FMD game. Consider a transaction with two change outputs: if a detector uses the correct detection key, they'll detect both with probability 1, but if a detector uses the wrong detection key, they'll detect both with probability $p^2$. So now, instead of having cover traffic occurring at false positive rate $p$, the false positive rate drops to $p^2 \ll p$, just by an accident of transaction construction.
To fix this, we should to attach the clues to the transaction, rather than the output, so that there is one clue per recipient clue key per transaction. This adds a new problem -- we don't want to leak the number of distinct recipients -- but we can fix that by requiring that there are always as many clues as there are outputs, and padding the list of clues with clues addressed to dummy clue keys.
Describe the solution you'd like
- [x] https://github.com/penumbra-zone/penumbra/issues/1226
- [ ] Add a
fmd_clues: Vec<Clue>
toTransactionBody
: https://github.com/penumbra-zone/penumbra/pull/1270 - [ ] Add a consensus rule to the shielded pool component enforcing that
tx.fmd_clues.len() == tx.outputs.len()
- [ ] Figure out how to have dummy clue keys in the
TransactionPlan
- [ ] Add clue creation to the transaction
build
method.
There are still some open questions about how exactly we want to include clues in the transaction plan. We probably want the signer to be able to see who will get clues, and consider them authorizing data, but they may not be able to derive the clues deterministically, or they might have difficulty doing so.
After a bit of reflection, I think the original suggestion I made to put the FMD bits in the ChainParams
was a mistake: https://github.com/penumbra-zone/penumbra/pull/1217#issuecomment-1197377796
Currently, we don't have any chain parameters that are set by the chain, the chain parameters are all high-level config options. Since the idea is for the FMD precision to be auto-adjusted according to transaction volume, it's likely that we'll have some parameterization, e.g., length and decay for an EWMA of message volume, target anonymity set, etc., and those parameters might need to be adjusted. I think it would make more sense to put those parameters (whatever we decide them to be) into the ChainParams, and then have the bit sizes actually used for FMD be derived from them. Otherwise, we'll end up having the chain parameters be a mix of configuration options and configuration-derived data.
Instead, we should put the FMD parameters in a separate payload (also in the CompactBlock
):
https://github.com/penumbra-zone/penumbra/issues/1226