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.

[1715438150]

1715438150

[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.

[ertil]

Well, if we are going to do it in some interactive way, then maybe it is possible to just use RBF for that. So, if we have two transactions: A->B->C and both of them are using RBF, then it may be done at mempool level, just by creating A->C transaction and not treating it as double-spending attempt if A->B and B->C transactions are present in mempool. All that is needed is accepting such RBF transactions by miners, nothing else needed.

[spartacusrex]

Wouldn't the RBF need to pay more than the combined total from the separate transactions though ?

If the miner could make make more by adding the 2 separate transactions than the single cut through ?

When there is only one transaction rbf works, since miner makes more. When you are replacing multiple transactions the rbf would need to override the sum of all of them.

Only publishing the final cut-through txn removes any tricky decisions.

[ertil]

Wouldn't the RBF need to pay more than the combined total from the separate transactions though ?

Yes, according to the current rules it need more coins. But one joined transaction will pay more than each of those two transactions are paying separately if we take satoshi per byte ratio. Imagine you have two transactions, each paying 1000 satoshi fee and each having 1000 bytes in size. Then, after doing cut-through on them, you can for example have one transaction paying 2000 satoshi fee and having 1500 bytes in size (because of cut-through). Then, from miner's perspective, including this one transaction is more profitable than including two separate transactions. Miner have nothing to lose, fees remain the same. However, as there is less space needed, such miner can fit more other transactions in the same block and receive more fees from that block.

If miners are mining for profit, they should quickly see that cut-through is working in favor of them and should activate such rules, because they will get the same amount of coins and they will need less space to include them in their blocks. Also, as they are RBF transactions, they don't have to be kept forever, finally only transactions included in blocks will be kept and the rest will be rejected forever as "provably never confirming transaction". Sooner or later, each miner by default will throw such transactions out of its mempool.

If the miner could make make more by adding the 2 separate transactions than the single cut through ?

No. Fees should remain at least the same to make sure that miner don't have to pay for having more space in a block. Miners shouldn't have a dilemma between transaction sizes and their fees, they should have an incentive to activate it (having the same fees occupying less disk space should be enough to convince them).

When there is only one transaction rbf works, since miner makes more.

When N transactions are joined into one, miner also makes more, because satoshi per byte ratio will be higher.

Only publishing the final cut-through txn removes any tricky decisions.

Yes. If transaction is confirmed, other transactions can be safely removed, as they are needed only to show other nodes that some replacement is not some double-spending attempt, but is honestly joined by cut-through.

[vjudeu]

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.

I think that at least some implementation is needed. Is allowing RBF cut-through transactions with higher or equal fees in Core a good idea or not? I mean: if Alice sent some transaction to Bob and it is marked as RBF transaction and if Bob also sent some RBF transaction to Charlie (by using coins from Alice), should it be possible for Alice to create cut-through RBF transaction by joining both transactions and signing it? Optionally, it should be possible to add more inputs and outputs to increase fees, as it is possible in other RBF transactions.

Doing it privately is always possible. But I think that having such option for all RBF transactions that are already in mempool should be also possible. Thoughts?

[ertil]

Is allowing RBF cut-through transactions with higher or equal fees in Core a good idea or not?

Since full-RBF, batching can be done for all unconfirmed transactions, no matter if they should be cut-through or not. Unconfirmed means unconfirmed. And I think wallets should start implementing cut-through for unconfirmed transactions, because that could help unclogging mempools. Then, if you have "Alice -> Bob -> Charlie" transaction, Alice's wallet could allow signing "Alice -> Charlie" as a replacement, while keeping the same fees for a smaller transaction (that would increase satoshis per virtual byte rate).

[tromp]

Is allowing RBF cut-through transactions with higher or equal fees in Core a good idea or not?

No; that's not a good idea. If Alice can have tx1 A -> A1 relayed to all mempools for fee f,
and then have tx2 A -> A1 -> A2 relayed to all mempools, and so on until
txn A -> A1 -> A2 -> ... -> An for the same fee, then this one time fee f was used to generate
an arbitrary amount of network traffic, which amounts to a DOS attack.

That's why you want replacement txs to have enough fees to cover both the cost of their own relay,
as well as the relay of the tx they're replacing.