Transaction cut-through

[gmaxwell]

As an aside from the CoinJoin discussion, it occurred to me that another transaction size optimization is possible with CoinJoin like transactions.

Say there is a collection of related unconfirmed transactions:
(u signifies an unconfirmed output)


             / uI     
A -> uB -> uH  - uJ
       /
     C

D -> uE -\
          uK -> uL       
F -> uG -/


The authors of the earliest unconfirmed transactions could write replacements for their transactions:


A->ul/uj
    /   
   C
 D   
  \   
F->uL 


This transformation is lossless with respect to the final coin ownership, but the intermediate transactions were cut-through. This works even if the original coin ending up in the final outputs came from multiple parties, as they can coinjoin to preserve the final outcome.

Because the replacements are atomic and consume the original inputs this transformation is safe, assuming people in the middle can handle any accounting complications that arise. (E.g. figuring out that their payment really was completed). So you'd want to have a way of signaling "I permit you to conflict this transaction with one that pays its children, if you can figure out how".

Nlocktime could be set in the mild future in order to create time for these kinds of arrangements to be found, and if blocks are found to fast— no harm, the cutthrough doesn't have to happen all the time.

Because people don't currently spend unconfirmed inputs I expect this wouldn't get much compression now, but in the future it might have quite an impact.

[TierNolan]

So, something like

A pays W and X
B pays Y and Z

X and Y pays H

You can replace it with a combined transaction of

A and B pays W, H and Z

However, to create that tx, you need A and B to sign.

This can happen in stages

B = Y + Z must be less than H + Z, since H > Y.

This means that the owner of B can broadcast

B pays W, H and Z, ANYONE_CAN_PAY

This is not a valid transaction, since B is less than H + Z (and so less than H + Z + W), but it counts as an offer. 

The relay rules would need to be modified, for it to work.

Nodes could check that the fragment doesn't violate the double spending rules and so forward the fragment.

A could see the transaction and then sign and broadcast the combined tx.  This makes it decentralised.

It would also act to reduce fees paid.  However, if you reduce fees, then miners might just include the original tx.

If block space is limited, then miners might still use the smaller tx, as long as it paid more in tx per kB than the original tx.

[keystroke]

Has anyone done research into simulations to estimate the possible savings which would be fained by using transaction cut-through?

[gmaxwell]

Has anyone done research into simulations to estimate the possible savings which would be fained by using transaction cut-through?

I did back then but it was very low because virtually no wallets spent unconfirmed coins.  Today unconfirmed spends are much higher and there would be actual savings.

Possible is hard to estimate, because if this were available it would call for a change in usage, e.g. intentionally avoiding confirmation for some time to give time to find cut-throughs.

Probably the greatest savings from cut-through is just repeated payments that reuse change; which with Opt-In RBF is much easier to implement than generic multi-part cut-through.

[riplin]

I wrote a post on reddit somewhere back in January about something similar. It wasn't multi-party in, multi-party out, but one party in, multi-party out.

Here's a writeup how it would work:

Most financial relationships between merchants and suppliers, employers and employees, subscriptions, leases, mortgages, rent, etc ,etc, are long standing relationships. The vast majority of payments flow through these channels. And we can do some really smart things with these.

Let’s look at a website.

A customer selects a number of goods on a website and proceeds to checkout. He selects bitcoin as payment option. The web server now contacts the payment router and requests a payment request for $X. The payment router now looks in its local database of creditors and starts to query a number of them for partial amounts. A couple of seconds later they all respond and the payment router now combines these payment requests, signs it, and feeds it back to the web server. The web server presents this payment request to the user, user makes payment and done. For the next customer, a completely different set of creditors could be selected, etc. You get the picture.

We just settled a number of partial debts across multiple creditors with a single transaction. Not only that, but for all we know, those creditors did the same thing and also forwarded the request to one or more of its creditors. So it could very well be that we went several hops deep (depending on the allotted time, I’m sure prefetching could work here as well).

The velocity of those coins just increased significantly.

And there are other advantages too:

- Number of transactions is reduced, reducing pressure on the blockchain;
- Large part of the debt settlement between multiple parties is now extracted out of the transaction chain, increasing privacy amongst all participants;
- No changes needed to user wallets to make this work. BIP 70 support is enough;
- No changes needed to Bitcoin either, it’s all just plain transactions;
- Would still work nicely with multi-party transactions (escrow) - the final payout transactions would contain the routing part;
- Hardly any real protocol development needed, other than the communication between payment routers, which should be minimal;
- Accounting side is simple. The relevant transaction outputs show up on both sides of the balance sheet;
- It’s completely distributed. The relationships are all one to one, but can chain and fan out quite easily and dynamically;
- You could still forward parts to a payment processor for conversion to fiat;
- Since you never take possession of (some) of the payment, there’s no exposure to volatility on the bitcoin that’s forwarded;
- Graceful degradation - the payment router can even collect on a local xpub address if all other options fail.

There’s no way you’d even be able to come close to something like this using traditional payment methods.

It would work for individual users as well. You can either setup your own payment router, add your own creditors, your savings xpub, your spending xpub, etc, and have your local wallet send out payment requests to that router when you request payment from someone. Your employer can hook up to it and trickle your salary in that way or you could use a service setup by some company to handle it for you.

[tromp]

This cut-through mechanism is the modus operandi of the Mimblewimble protocol [1], where it doesn't need interaction with any of the tx signers and can be applied across the entire blockchain history to slim down the Initial Block Download.

[1] https://github.com/mimblewimble/grin/blob/master/doc/intro.md

[aliashraf]

@tromp's mentioning of Mimblewimble aside, I think it is deeply related to fast sync proposals like UTXO commitment which I'm advocating for a while and OP, Gregory Maxwell, has been rejecting continuously! So, I'm totally surprised.

Once this "cut-through" proposal is generalized, eliminating intermediate transactions from the history becomes a challenge for validation, so one needs to provide them as some kind of "temporary witness data", otherwise how could nodes become convinced about the actual target(s) of the spent coin(s)?

Generally speaking, one could consider the whole blockchain history as a (prunable) witness data for validity of the UTXO set in a specific state of the blockchain. I know, there are complications, let's address them later.

[gmaxwell]

You misunderstand what 'prunable' means.  It just means you don't have to keep it around after you verified it. It doesn't mean you don't need to verify it.  This thread has zero interaction with utxo commitment proposals.

[aliashraf]

Gregory, with all due respects, I want to assure you that I know what "prunable" means, and how it is related to verification of transactions. Unlike what you say, this cut-through proposal is deeply related to transaction aggregation and fast sync problem as @tromp has already mentioned before me.
Now, I'm realizing that you are not completely aware of the consequences of your own proposal, especially its implementation requirements.

The cut-through/summary transaction in your proposal either is
1) Generated/signed by the first sender(s)
OR
2) A virtual/derived transaction.

In the first scenario, there is no need for any implementation at all:
Unconfirmed transactions could be sent (even privately) between parties and whenever it is possible they are summarized by the original senders.

But in the second scenario, where the blockchain and bitcoin network has to take a role in cutting through and removing the temporary UTXOs in between, eliminating the need for the original senders to be engaged explicitly, no matter what the details might be, you are exactly where I'm talking about.

In Mimblewimble, transaction aggregation and cut-through is an inherent property of the technology but for bitcoin implementing such ideas without disrupting the whole technology is impossible as long as we are obsessed with the infamous "Do not trust, verify!" slogan.

Let's get rid of this slogan for a moment:
Properly implementing UTXO commitment in bitcoin, we can prove that the UTXO set we are committing to is:

1) Provably immune against illegal inflation (just like Mimblewimble).

2) For any given unspent output (live coins) either there is witness data already available or for a long enough period of time such data has been available and the network has been actively confirming it ever and ever.

In the real world, unlike a hypothetical pure computerized cyberspace where bitcoin is just a protocol and not a socioeconomic phenomenon, we human beings, are doing this all the time in our accounting and bookkeeping procedures, financial transactions are aggregated to balance sheets and after being audited and confirmed by authorized bodies are considered as a base for future transactions in the upcoming fiscal year. Nobody checks the whole history of accounts in a 100 years old company.

In Mimblewimble, unspent outputs are encrypted such that only the final owner can decrypt and spend it, so they don't need any additional witness data and can enjoy scalability advantages more conveniently, but it does not mean that no workaround is possible for bitcoin. Your cut-through idea is an example for such workarounds, however there are requirements and paradigm shifts to be considered as well.

[gmaxwell]

Unconfirmed transactions could be sent (even privately) between parties and whenever it is possible they are summarized by the original senders.

Yes, that is literally what this thread was about.

bitcoin implementing such ideas without disrupting the whole technology is impossible as long as we are obsessed with the infamous "Do not trust, verify!" slogan.

This is an empty inflammatory statement.

Let's get rid of this slogan for a moment:
Properly implementing UTXO commitment in bitcoin, we can prove that the UTXO set we are committing to is:

1) Provably immune against illegal inflation (just like Mimblewimble).

2) For any given unspent output (live coins) either there is witness data already available or for a long enough period of time such data has been available and the network has been actively confirming it ever and ever.

I think you've failed to understand the property being provided there.   Mimble wimble requires a considerable amount of non-prunable data: a kernel for every transaction.  Given these kernels, the current utxo entries and their range proofs (which have a size a hundred times larger than the comparable data in Bitcoin) one can verify for ones self that the utxo set was one authorized by creators of the kernels.  There is no sketchy hand-waving "long enough" assumption breaking the security properties (assuming that all activities were simple spends).

At the time the Mimblewimble concept was published the amount of data required to sync bitcoin without the history if it had used Mimblewimble would have been somewhat more than syncing bitcoin's full history is without it...  it didn't substantially lower the resource costs, but rather had the potential for improved privacy without substantially increasing the resources.  (Asymptotically, MW could be a small constant factor smaller. ... but the constant terms mean the history has to be *very* big before its smaller at all, and even there the difference is just the ratio of kernel size to a full transaction size so like a factor of 5 vs bitcoin transactions)

[aliashraf]

Unconfirmed transactions could be sent (even privately) between parties and whenever it is possible they are summarized by the original senders.

Yes, that is literally what this thread was about.

As I reminded earlier, that makes it a no-technical discussion because it needs zero implementation.

I think you've failed to understand the property being provided there.   Mimble wimble requires a considerable amount of non-prunable data: a kernel for every transaction.  

Thank you for the information, but no, there was no confusion for me as I didn't recommend Mimblewimble for bitcoin, although, unlike what you say, it is more efficient and especially more scalable than the current bitcoin synchronization process. I was just reminding of the built-in zero-sum proof  property used there, proposing a smart implementation of UTXO commitment that proves the expected balance in each state of the machine hence reducing the security risks. It is possible without borrowing any further idea from Mimblewimble.

[gmaxwell]

although, unlike what you say, it is more efficient and especially more scalable than the current bitcoin synchronization process. I was just reminding of the built-in zero-sum proof  property used there, proposing a smart implementation of UTXO commitment that proves the expected balance in each state of the machine hence reducing the security risks. It is possible without borrowing any further idea from Mimblewimble.

Sorry, perhaps you swallowed some altcoin scammers lies but it just isn't so. The "built-in zero-sum proof" isn't just some bolt on property, it's fundamental to the system and it has a substantial cost. To get it you must preserve for every transaction a kernel and for every unspent output you have to preserve a pedersen commitment and a cryptographic range proof.  It has the same asymptotic scaling as Bitcoin.  Bitcoin's communications cost is proportional to N_txn*x while the Mimblewimble zero sum property is proportional to N_txn*y + N_utxo*z,  and x is somewhat larger than y, and z is MUCH larger than x.

The result is that (as of the last time I ran the numbers) the resulting data needed to be transferred to sync (if bitcoin had used this all along) was larger with MW, although eventually once the history was enough larger than the utxo set MW could potentially become smaller, but even with an infinite history to utxo size the ratio between them would just be a small constant.

[aliashraf]

although, unlike what you say, it is more efficient and especially more scalable than the current bitcoin synchronization process. I was just reminding of the built-in zero-sum proof  property used there, proposing a smart implementation of UTXO commitment that proves the expected balance in each state of the machine hence reducing the security risks. It is possible without borrowing any further idea from Mimblewimble.

 Bitcoin's communications cost is proportional to N_txn*x while the Mimblewimble zero sum property is proportional to N_txn*y + N_utxo*z,  and x is somewhat larger than y, and z is MUCH larger than x.

and N_utxo is actually m_UTXO,  MUCH smaller than N_txn.

... although eventually once the history was enough larger than the utxo set MW could potentially become smaller.

And  it is merely the definition of scalability.

Once again, I reimnded of MW because of @tromp's comment above thread, showing my respect for his work on grin. Zero-sum in MW is built-in and securing the system needs extra kernel data, but AFAIK, proving the state being in zero-sum doesn't need kernel data, I used it as an analogy for a hypothetical UTXO commitment scheme in which you don't need the history (or even the actual unspent transaction set) to prove that the commitment is loyal to the inflation rules. An analogy, nothing more.

[tromp]

Bitcoin's communications cost is proportional to N_txn*x while the Mimblewimble zero sum property is proportional to N_txn*y + N_utxo*z,  and x is somewhat larger than y, and z is MUCH larger than x.

It looks like you're discussing Initial Block Download communication costs.
Assuming 2-input, 2-output txs, I get

Bitcoin tx size x ~ 400 bytes (or is it closer to 500?)
MW kernel size y ~ 100 bytes
MW output + rangeproof size z ~ 700 bytes (600 with BP+)

Are you saying that 400 is somewhat larger than 100, and 700 is MUCH larger than 400 ?

Plugging in N_txn=600M and N_utxo=68M, we get IBD sizes of 240 GB for Bitcoin and 60 GB + 48 GB = 108 GB for MW.

[gmaxwell]

Thanks for the figures.

Bitcoin tx size x ~ 400 bytes (or is it closer to 500?)

It's closer to 280 with a more compact serialization, which can be done with no consensus changes (see e.g. the blockstream sat codebase for an example implementation)

MW output + rangeproof size z ~ 700 bytes (600 with BP+)

Ah, my calculations would have been assuming 3kb or so, pre-BP range-proofs.

[tromp]

Bitcoin's communications cost is proportional to N_txn*x while the Mimblewimble zero sum property is proportional to N_txn*y + N_utxo*z,  and x is somewhat larger than y, and z is MUCH larger than x.

Actually, Bitcoin could use a variant of Mimblewimble that foregoes the privacy benefits.

A UTXO could be a triple <v, PK, sig> of an amount v, public key PK,
and a signature sig with PK on v to replace the range proof in MW.

A transaction tx is then a set I of inputs, a set O of outputs, and a signature with public key

    tx.PK = sum_{o in O} o.PK - sum_{i in I} i.PK

which the transacting parties can interactively construct just as in MW.

This preserves MW's ability to trivially aggregate transactions, and also allows for an additional "kernel offset"
to obfuscate original transaction boundaries (adjusting the above equation by offset*G).

This reduces z to about 100 bytes, and the Initial Block Download to 600M * 100B + 68M * 100B ~ 67 GB.

[gmaxwell]

I believe the size of that is roughly the same as using a transaction wide aggregate in the transactions-- or at least extremely close.  (+/- details about how the transaction was serialize)

[spartacusrex]

As @Riplin was saying..

You can coordinate the cut through transactions off-chain using a trustless centralised entity - Layer 2 style.

And a decentralised protocol could work @TierNolan but it's also really easy and secure centralised.

So lets say

A -> B -> C -> D

A pays B who pays C who pays D

Cleary the best outcome is A pays D.

A -> D

A,B,C and D could all be members of this 'CutThrough' website.

They perform their 'desired' transaction to another member of the website - but nothing gets posted onto L1.

The Website crunches the numbers and calculates what the most efficient payments are given the set of transactions it has received over a set amount of time ( hours/days ) and then coordinates with those Users to create the appropriate transactions.

The Users would all have to agree, signing something and sharing so that all parties concerned were happy that everyone agreed and then the 'final' transactions are posted.

The incentive and advantage is fees and semi-better privacy. Reduction of fees as less transactions are broadcast. Privacy as no onchain transaction to show it happened - although the entity knows of course.

These fees would be spread over all the users in the cutthrough - so that ad extremis all the users payed less than they would have done. As well as all the benefits already mentioned above to the chain, and speed etc etc.. Win win. And you don't have prior bigger juicier transactions to tempt the miners with as there aren't any.

One solution could be to have a small Eltoo/Lightning channel open to the central entity. Then it could coordinate splitting the fees, and take small amounts from all the concerned parties off chain, and then pay them itself for every L1 transaction.

( This would be different to having a large Eltoo channel since you could be payed and pay a lot with only a tiny initial sum that only needed to cover fees )

At no stage can anyone take anyones money and the worst that can happen is you are delayed before diving back to L1 yourself and completing the transaction as you would anyway have done.

If you could get a 50% reduction in overall transactions.. that's like a blocksize increase x2.. not bad.

[ertil]

Assuming that MimbleWimble will be used, then no centralized website is needed. As @tromp noticed:

tx.PK = sum_{o in O} o.PK - sum_{i in I} i.PK

As coinbase inputs are ignored, we would have two transactions in our 1 MB standard block: the first would be the coinbase transaction and the second would be one MimbleWimble-Segwit-future-version input and one MimbleWimble-Segwit-future-version output. The rest would be non-upgraded transactions to maintain backward compatibility.

But still, this would have some limitations:
1. It would work only with ECDSA public keys.
2. It would require new Segwit address version.
3. All input public keys should still be included, in other case it would be insecure.
4. All output scripts could be based only on ECDSA public keys (optionally some hash of that key, but still, nothing non-standard), in other case turning some output into some input would be difficult and that's what this cut-through is all about.

So, after all we would get something quite close to just producing that transaction now by some centralized entity, the only difference is that this could be made in non-interactive way.

[spartacusrex]

yes non interactive is obviously way cool 

..but I guess the point about the interactive centralised version is that it is still safe, it works today, and no changes at all required.