Grin Transaction Aggregation

I was asked by @mably to repost my ML answer here so that more people can read it. This is the answer to Azure’s question about a P2P protocol that can handle transaction merging. Here it is:

I am happy to say that the protocol has already been implemented into Grin as of 2 days ago; https://github.com/mimblewimble/grin/pull/1067. I’m going to explain here the details for the ML.

We started with Dandelion [1], a privacy-preserving transaction propagation protocol. Basically, instead of broadcasting transactions to a subset of your peers, you broadcast it to only one peer: the Dandelion relay, a randomly chosen outgoing peer. This peer will do a coin flip to determine if it should send the transaction to everyone (fluff it), or only its own Dandelion relay (stem it). So basically, transactions are propagated in two phases: the stem phases (only to one peer) and the fluff phase (to all the peers). This was implemented in #719 [2]. Still no aggregation at this point.

Then we found that we can leverage this protocol to aggregate transactions during the stem phase. But in that case, we need to allow transactions with multiples kernels [3] and be resilient to the Denial of Service attack that Andrew talked about where a random peer can just perform a weird aggregation (which can possibly invalidate transactions). In the last case, we developed a way to de-aggregate aggregated transactions [4].

Finally, in order to aggregate transactions with the Dandelion protocol, we implemented the following protocol. When you send a transaction that you want to be aggregated with other transactions (we use the term stem transaction here), we will broadcast this transaction to our Dandelion relay. The Dandelion relay will then wait a period of time (the patience timer), in order to get more stem transactions to aggregate. At the end of the timer, the relay does a coin flip for each new stem transaction and determines if it will stem it (send to the next Dandelion relay) or fluff it (broadcast normally). Then the node will take all the transactions to stem, aggregate them, and broadcast them to the next Dandelion relay. It will do the same for the transactions to fluff, except that it will broadcast the aggregated transactions “normally” (to a random subset of the peers).
This gives us a P2P protocol that can handle transaction merging. Antioch did an amazing job, the code is well written and well commented [5].

Finally, it is still possible to broadcast a transaction normally (bypass this protocol and then send it to all your peers) if you are in hurry and cannot wait for the aggregation with others transactions.

I understand that some may find this explanation slightly complicated, considering all of the new vocabulary. You can read more about Dandelion in the Grin docs [6], and I also created some slides (which are not up to date but should give you a good understanding of Grin & Dandelion) that you can review[7].

Cheers,

~ Quentin

[1] Dandelion BIP https://github.com/gfanti/bips/blob/master/bip-dandelion.mediawiki
[2] Dandelion PR https://github.com/mimblewimble/grin/pull/719
[3] Allowing multi-kernels transaction https://github.com/mimblewimble/grin/pull/681
[4] Anti-aggregation mechanism https://github.com/mimblewimble/grin/pull/984
[5] Dandelion monitor code https://github.com/mimblewimble/grin/blob/master/servers/src/grin/dandelion_monitor.rs
[6] Grin Dandelion docs https://github.com/mimblewimble/grin/tree/master/doc/dandelion
[7] Grin & Dandelion slides http://lesceller.com/doc/dandelion.pdf

Link to the original email: https://lists.launchpad.net/mimblewimble/msg00492.html

2 Likes