Output Cleansing Chain

output_cleansing_chain.md

Output Cleansing Chain

An idea where N parties form a chain in which they aggregate their transactions, but end with nobody knowing anything about the outputs apart from their own. The chain has a property that all outputs change at each transaction aggregation. This means that node at position M+1 aggregates and changes all the outputs, which means that the node at position M would no longer recognize any output apart from its own if it saw the transaction. Transaction that is passed through the chain should always be valid so it does not open a spam vector where one could send invalid transactions and waste others time.

Current p2p aggregation

The current Grin implementation of p2p transaction aggregation is linear where a node aggregates multiple transactions together (assuming they have them) and then passes the transaction forward. This requires a relatively high volume to provide a meaningful obfuscation that Grin currently does not have. The main idea that will be used in this document is the fact that an owner of an output O1 in a transaction T can replace O1 output by another output O2 and adjust the kernel offset to obtain a new transaction T' that is also valid. In theory, if we aggregated M transactions to obtain transaction T1 and afterwards everyone replaced their outputs by new ones, we would break the linkability between the inputs and outputs that were observed during the aggregation phase.

Output Cleansing Chain idea

First, let's redefine what a stem transaction looks like. It is composed of two parts:

1. A transaction that is valid (this is what we have right now)
2. For each output in a transaction, we have a sequence outputSeq of N pairs that include (new_output, kernel_offset_diff)

The sequence outputSeq for an output O1 defines a sequence of pairs where adjacent pairs describe a valid replacement of an output e.g. if we have a valid transaction with an output from outputSeq[3], then we can apply the change described in pair outputSeq[4] to obtain another valid transaction.

The first thing we need to confirm is that it is safe to share outputSeq lists with a node holding our stem transaction. This node will inevitably see our outputs so sharing replacable outputs with them does not hurt any privacy. It can only bring benefits if the nodes performs an output swap. This means that the sender and receiver could just generate their own outputSeq lists for each output (should be long enough lists) and send it to the first node holding their stem transaction.

Suppose we have N nodes that hold a stem transaction. They find each other by communicating, they then pick a random order that forms a chain e.g. a chain of length 5 (how to pick a random order was described in Objective-Dandelion post).

Let's call the fist node in the chain Node1.

Node1 -> Node2 -> Node3 -> Node4 -> Node5

First all nodes generate a one-time private key and broadcast its public key to all other nodes. Nodes verify they all received the same key by each node e.g. confirm hash(sort(public_keys)). Nodes will go in order from Node1 to Node5. Each node does the following:

1. It counts the number of nodes infront of it, let's call that K, and for each output in the stem transaction this node holds, it takes the first K pairs from output's outputSeq and encrypts them with the corresponding public keys based on the reverse order of the chain it sees infront. This forms P different encrypted messages (P is the number of outputs) each having its own onion with K layers where each layer will show a specific participant one output.
2. It decrypts all the onion layers it received to get the new outputs. These new outputs will represent the new output set of a transaction. Now it removes all the outputs from the transaction it received and adds the new output set. Note that because each encrypted output pair was a transition from previous to new output, the transaction should still be valid.
3. It takes this 'cleansed' transaction that has new outputs and aggregates it with its own transaction
4. It sends the aggregated transaction and all the onions (including the onions the node created) to the next node in the chain

Once Node5 finished these steps, the output cleansing chain has been completed.

We can observe two things:

1. the transaction can be validated at every step
2. the outputs that a node at position M saw are no longer there in the next step after the node at position M+1 changes the output set. Each step delinks all the outputs.

Note: Node3 does not encrypt output swap transitions for Node1 and Node2, it only builds onion layer for the nodes that are infront of it.

Objective Dandelion + Output Cleansing Chain

The chain could represent the path from a node that holds a stem transaction to an Objective Dandelion fluff node. We probably would not be able to communicate with all the nodes because the fluff nodes would end up having too many connections. This means we would only ask our max peer node we are connected to, to serve us a sequence of public keys leading to the fluff node so we can build the onions. The peer should be able to provide this by asking its own max peer for the path (note that each peer would only need to ask once per dandelion epoch and then it can cache the path public keys). Once we receive the public keys and build the onions, we simply send the transaction forward to our max peer. At each step, a node can validate the transaction it received, replace the whole output set and pass it forward. In Objective Dandelion, the nodes closer to the fluff node are expected to get more transactions so the close we get to the fluff node, the more likely transaction aggregations will take place.

The general idea is to just have the standard Objective Dandelion where each step is verifiable as in the original proposal, but it also provides new outputs to swap. It is possible that a malicious node would provide false outputs in its onion layering. For instance it could provide a false output for the last fluff node. This would mean the fluff node could not drop all the outputs and replace them with new ones. I think there is a way around this.

How to solve the issues of a malicious node not providing new output or providing an invalid one?

It might be hard to find out which outputs can be replaced and which not if at least one of them is false. Since a malicious node could try to break the fluff/pre-fluff output swaps for everyone, we simply define outputSeq to be a sequence of N triplets that include (previous_output, new_output, kernel_offset_diff). This means that for every encrypted message we get an output state transition that can be verified and apply only those that are possible and keep the transaction valid. A node on the Objective Dandelion path can first validate the transaction it receives, and only then decrypts output transitions and apply those transitions that are valid. This way, a malicious attacker can't break all output swapping.

Note: If the sequence of public keys was of length 1 (our peer was a fluff node), we could ask 2nd max peer (pretend this is our max) to make sure we get some aggregation and output cleansing on the path

Questions

What if a malicious node sees an intermediate transaction and decides to broadcast it?

Yes, a malicious nodes can see intermediate txs that are valid and then broadcast them. But this is already true with current nodes that hold a stem tx :)

Can we identify a malicious node?

I think it should be possible in non Objective Dandelion variant where nodes on the path communicate with each other. If nodes publicly show their starting onions (there is no harm in showing this), they could (if needed) also show the output swap transitions it encrypts. Every participant could verify any onion (if they saw the output swap transitions) by using the public keys that have been shared. I think it should be possible to show which node is lying using this information.

What if a node disconnects?

We ban it. You can't know if it was malicious or not, but not banning it is probably worse. We want to converge towards good nodes.

What if the last chain node never publishes the transaction?

The situation is the same as in the current dandelion phase. In this version we pick the next node either by sending it to a random node or join a cleansing chain in which case, if the chain goes through, we have chosen the next node to be the last node Node5. So if the transaction does not get publishes (if the kernels of the transaction were not broadcasted) then we can broadcast it.

Note: It would be possible to broadcast also the last seen state. For example if a chain was of length 10 and we were the 5th node in the chain and saw a valid transaction, we could decide to broadcast it if the chain does not go through.

Does this impact mempool tx handling?

I'm not sure how the mempool currently handles having a tx T and then receiving T' that had outputs swapped. It is something to think about.

What are the drawbacks?

0. inputs can be linked to the node that had the stem transaction, but that doesn't really matter
1. a node that replaced the outputs can figure out which output maps to the new output by trying combinations of removing one output and then adding the output it found. This could perhaps be mitigated.

Possible improvements

1. Theoretically an output O1 could be replaced by 10 outputs. Similarly, 10 outputs could be replaced by a single output. I'm not sure yet if this brings any improvements, but is something worth thinking about.