search

mimblewimble / grin

Minimal implementation of the Mimblewimble protocol.
https://grin.mw/
Apache License 2.0
5.04k stars 991 forks source link

Dandelion Transaction Aggregation #819

Closed quentinlesceller closed 6 years ago

quentinlesceller commented 6 years ago

This follows from https://github.com/mimblewimble/grin/issues/706 and https://github.com/mimblewimble/grin/pull/719. Now that we have the Dandelion logic in place we can aggregate the transaction during the stem phase. This mechanism will likely need the anti aggregation mechanism mentioned here https://github.com/mimblewimble/grin/issues/799. Relevant documentation https://github.com/mimblewimble/grin/tree/master/doc/dandelion

sesam commented 6 years ago

We talked about it being necessary to prevent too low fee transactions from being aggregated. Otherwise it opens for an attack; by creating heavy transactions with way too low fee, so the aggregate is never mined, in extreme meaning that only non-aggregated transactions are ever mined.

quentinlesceller commented 6 years ago

@antiochp @ignopeverell @yeastplume @tromp I've been thinking a lot about stem transaction aggregation in the past few days and I come up with a new to do it. However, I'm not entirely sure that it makes sense, hence I want your opinion on this. Currently (in #1023), I have a an aggregator that will every 30 seconds (for example) aggregate all the transactions in the stempool and broadcast them as a multi-kernel stem transaction to its Dandelion relay. When a node receives this stem transaction, he will flip a coin and see if he want to "fluff it" or "stem it". This way transactions are aggregated along the way like a snowball. However, I see a lot of problem with this idea:

  1. Low fee transaction getting in the way (mentioned above by @sesam).
  2. Recovering a previous state if a previous node decide to fluff the transaction.
  3. Other reconciliation problems.

Then, I had an idea where the transactions are not aggregated in the stempool but relayed individually just like now. But, when a node flips a coin and fluff it, it will aggregate all the transaction in its stempool and send it to the whole network. This way we can avoid: 1 - Low fee transaction, by checking that the fee is decent. 2 - Problems of recovering a previous state since all the Dandelion relays keeps all the transaction and can just use the previous developed deaggregate function. 3 - One "problem" that I see is it not as efficient for privacy since we do not do cut though along the way but at the end. Also, in that case, we don't need the previous aggregator. Thoughts ?

tromp commented 6 years ago

  1. is not a problem about low fees in particular, but about disparate fees. aggregating one tx with another that pays much higher fees/cost is benefitting the former while punishing the latter. the impact of this can be reduced by adopting a rule that two tx can be aggregated only if their fee/cost ratios are within a factor of 2 for example.

  2. this should never happen; a tx is either fluffed, or relayed to another stem node, but never both.

  3. keeping tx separate until fluffing compromises the unlinking properties of the dandelion network. any chosen next stem node is at some risk of being compromised, so you want them to learn less about input output relations than you know yourself.

antiochp commented 6 years ago

I think the blocker there is in terms of privacy - we're passing all transactions around un-aggregated until the final fluff step. I'm not sure this would be acceptable if users are expecting txs to be aggregated (if possible) at the earliest hop. All it takes is a single node in the stem path to act dishonestly and broadcast all the un-aggregated txs and we lose all privacy benefits. Several nodes doing this on the network and we cannot do any aggregation reliably.

In terms of (1) can we not just reject txs from the stempool if the fee is too low? And in terms of (2) - can each node maintain its own set of un-aggregated txs (those that it itself has aggregated) so it can recover locally? And rely on other nodes doing the right thing locally as well?

quentinlesceller commented 6 years ago

Thanks you for your inputs @tromp and @antiochp! It is much clearer for me now. I'm updating the simulation of Dandelion relay and aggregation accordingly. Will get back to you if I have any question.

quentinlesceller commented 6 years ago

Fixed by https://github.com/mimblewimble/grin/pull/1067.