Transaction Cut Through

Transaction Cut-Through, or Merging Transactions Across Blocks, is one of the excellent features of Mimblewimble protocol, it contributes to a compressed blockchain history. To quote the original here:

Now, we have used Dr. Maxwell's Confidential Transactions to create a noninteractive version of Dr. Maxwell's CoinJoin, but we have not seen the last of marvelous Dr. Maxwell! We need another idea, transaction cut-through, he described in [8]. Again, we create a noninteractive version of this, and to show how it is used with several blocks.

We can imagine now each block as one large transaction. To validate it, we add all the output commitments together, then subtracts all input commitments, k*G values, and all explicit input amounts times H. We find that we could combine transactions from two blocks, as we combined transactions to form a single block, and the result is again a valid transaction. Except now, some output commitments have an input commitment exactly equal to it, where the first block's output was spent in the second block. We could remove both commitments and still have a valid transaction. In fact, there is not even need to check the rangeproof of the deleted output.

The extension of this idea all the way from the genesis block to the latest block, we see that EVERY nonexplicit input is deleted along with its referenced output. What remains are only the unspent outputs, explicit input amounts and every k*G value. And this whole mess can be validated as if it were one transaction: add all unspent commitments output, subtract the values k*G, validate explicit input amounts (if there is anything to validate) then subtract them times H. If the sum is 0, the entire chain is good.

Both the scheme and solution are very straightforward, almost same as Transaction Aggregation, so we will not give a new demo for it, just some Questions and Answers to be discussed here.

1st Question: Cut-through all the way! then Block data will be modified, How to validate the received historical block is a valid block?

Answer:

• There's no way to validate such kind of cut-throughed historical block. Instead of validate a single block, we can validate the whole chain state, as Mimblewimble protocol said: "If the sum is 0, the entire chain is good."

• There's a denial-of-service option when a user downloads the chain, the peer can give gigabytes of data and list the wrong unspent outputs. The user will see that the result do not add up to 0, but cannot tell where the problem is. -- as listed at the last part of Mimblewimble paper.

• This denial-of-service happen only for some new installed nodes which have been hacked somehow, there's no impact on the well running nodes. A way to detect this fraud chain data is to be be discussed. (TODO).

2nd Question: After cut-through all the way, why we still need keep signature part of the transaction kernel?

Answer:

• After across blocks cut-through all the way, all the intermediate inputs and outputs commitments in this chain are removed (spent outputs and their related inputs which spent them). Then, to validate the chain correct state, we need check:
  • sum(remaining outputs) + sum(fee) - sum(remaining inputs) = sum(mining reward amount)*H + sum(_excess) + sum(k2)*G
  • If considering the Grin project (the classic implementation of Mimblewimble protocol), the fee component of above equation is included in the transaction kernel, as part of the signed message.
  • To keep the fee for the chain state validation, current Grin implementation must keep transaction kernel which include both the fee and the signature. There's possibility to give optimized solution on this structure. TODO.