Change the Directory Semantics to Support Multiparty Payjoin

[nothingmuch]

In the context of #362 multiparty transactions & cut-through, we can better support multiple writers and readers to the same subdirectory by making changes to the directory interface.

Currently POSTing (or PUTing) a v2 request or response repeatedly to the same subdirectory will overwrite the value. With #364 Implicit Session Initialization, requests (original PSBT payloads in pjv2) and responses (proposal PSBT payloads in pjv2) are no longer distinguished, but the same behavior would apply to the subdirectory value.

Trivial: Last writer wins (no changes to current behavior)

For multiparty transactions, a shared tree of extensible buffers of arbitrary length can be constructed with an initial subdirectory as the 1st message slot. Once a value is written, the key-value pair is hashed to derive the shared secret for the next message's slot.

Races result in overwrites, which is why this is a buffer of trees. The i-th message's subdirectory ID is a merkle root of a transcript (linear sequence of messages). For a subtree to be successfully broadcast all parties need to be able to read the slot before it's overwritten (though it could be overwritten to a previous value).

No liveness guarantees. Clients need to poll message slots after writing. Something like a turn based approach or randomized timing might reduce write contention enough to be practical for the semi-honest setting assumed in #362.

In order to hide the number of participants from the directory, cover GET requests can be sent (e.g. each client samples a random number from an exponential distribution of extra clients to simulate, and consistently makes that many additional requests).

Unfortunately write contention can degrade this, so it's not just a liveness and efficiency but also a privacy concern. The number of participants is a relevant quantity since it can significantly aid the adversary to constrain or adjust credence of different sub-transaction mappings.

Write once

Instead of overwriting, simply make values immutable after being written, so the directory can be used to serialize writes turning the tree into an append only linked list of messages.

Write contention still wastes bandwidth for rejected writes, and leaks the same information about the number of participants to the directory.

Append Only Log

Instead of rejecting POSTs to the same directory, the values could simply be concatenated. Due to the padding, each subdirectory would take the form of an append only array of fixed sized messages, whereas in the previous approaches the shared buffer spans multiple subdirectories.

Since subdirectories are now variable sized, this can leaks information about the number of participants, and also the size of the transaction. Both of these can be addressed padding, but how much and how to randomize it requires further consideration. In this approach it may make sense to lower the padding size (e.g. 8x 896 would make each message less than standard MTU, and with HTTP 1.1 pipelining, HTTP/2 or HTTP/3 between both client and OHTTP relay and relay and directory would have the the same IP overhead as 1x 7168 byte write over a single TCP connection).

With this approach a turn based protocol would also be possible alongside or as an alternative to the two subdirectory approaches of #364, with the first non-padding message being the original PSBT and the second being the payjoin PSBT (and perhaps an optional third message being the broadcast tx, allowing post-dated payjoins to be broadcast by the receiver?).

By adding support range headers on a GET request, individual messages can be polled instead of requiring the log to be re-read. Subdirectories could have no explicit EOF, and a ranged GET past the end of the current value could block before returning an empty response, supporting long polling.

I'm not sure if this should be specified or just a matter of policy, but a size limit on subdirectories seems prudent, above which POSTs are rejected.

Mailbox / Queue

Same as an append only log, but earlier messages expire after some time. Before these are dropped, writes can be temporarily rejected if size limit exceeded.

This change would also make possible longer lived subdirectories, which for privacy reasons should be discouraged for privacy reasons.

More interestingly, it would also make it possible to do sender initiated payjoins inspired by SNICKER. With full RBF being increasingly viable, RBF cut through is a lot less complex to implement (BIP 125 rules in a multiparty setting are tricky), which suggests more potential incentive for adoption.

Naively this is very censorable and problematic for privacy because this would be associated with specific spent inputs (or potentially unspent outputs in p2tr case).

However, in conjunction with a BIP 352 silent payment, both sender and receiver learn a shared secret input_hash·a·b_scan·G, the DH exchange which is hashed to obtain the payment key tweak. In other words, the receiver of a silent payments could optimistically reply with a payjoin PSBT to the the sender over the payjoin directory with an unlinkable subdirectory ID, and if the sender supports payjoins they could poll that subdirectory and RBF the silent payment with a payjoin transaction.

Because the silent payment would still leak a payment value, it would be cool if we could come up with some approach to sharing a secret that doesn't create a tradeoff, but perhaps the simplest approach of sending multiple low feerate silent payment transactions in order to incentivize the receiver to consolidate them all in a payjoin would be enough. In the case of donations, the donor might be inclined to donate more in a payjoin than in a unilateral transaction.

Edit: I vaguely remember at least two papers that proposed on chain notification mechanisms for multiparty tx initiation, and I believe one of them was covert. Perhaps they are applicable to the RBF cut through setting, i will try to find them and share here.

Prunable mailbox / circular buffer

Probably a bad idea: Optionally or even alternatively to time based expiry, explicit client side pruning could be supported (or even required), which makes sense for a single receiver with a long lived subdirectory ID.

In the semi-honest multiparty setting more or less makes sense if writers include a Lamport clock in protocol messages so they can all agree on a lower bound of messages they've all seen, and also randomize who will do the pruning to avoid contention. Explicit pruning could be temporarily rejected i done too fast/early, which would allow an honest directory to have a discretionary policy of rate limiting writes to ensure all clients can read all data.

[DanGould]

It seems like an Append Only Log is straightforward to implement while #364 Payjoin Directory changes is open and making the change. I suppose GET range headers and padding could even be added to pjv2 after #364 is merged by making a default behavior to return a pre-defined number of bytes.

Since subdirectories are now variable sized, this can leaks information about the number of participants, and also the size of the transaction. Both of these can be addressed padding, but how much and how to randomize it requires further consideration.

This leaps out at me as the next milestone consideration. We're at a brief pause where we can make a decision to change pjv2 padding if it will help new protocols blend in. The padding question needs to be considered immediately

It also appears that Append Only Log could be upgraded to Mailbox / Queue without breaking v2 semantics. Assuming such a change is (relatively) backwards compatible with an Append Only Log of V2, I want to start by implementing that. Before committing to a Mailbox / Queue upgrade I want to validate this new Silent Payjoin™️ idea.

To hide the payment value, a Silent Payjoin sender could broadcast a transaction to the receiver at the minimum fee rate with a trivial output amount as a notification, posting an Original PSBT to the tweaked subdirectory with the actual payment value. The notification wouldn't even need to spend (all of) the same input(s) as the Original PSBT. As long as the silent payments receiver scanned for these notifications, they would be able to respond to the sender with a Payjoin PSBT at the tweaked subdirectory. While potentially censorable (my understanding of the issue is that an ~input * silent payments tweak = subdirectory id can be identified by a directory with knowledge of the silent payments address), I'm not sure all privacy value is lost, since all a malicious directory would discover is that an input is potentially spent in a Silent Payjoin. A resulting transaction could still be either a payjoin or not, even if such subdirectory is POSTed and GETed.

I'm realizing at the end of my post that I may have misunderstood, since my hide-the-payment value paragraph assumes the subdirectory id for Silent Payjoins is obtained with a mutual tweak rather than a long-lived static one. If in fact I have misunderstood, please elaborate on how Append Only Log gets us what the existing Directory doesn't w.r.t. silent payments sender-initiated payjoin.

Immediate action

1. Address the padding question
2. Implement Append Only Log

[nothingmuch]

I suppose GET range headers and padding could even be added to pjv2 after #364 is merged by making a default behavior to return a pre-defined number of bytes.

👍

The padding question needs to be considered immediately

Agreed, see below

It also appears that Append Only Log could be upgraded to Mailbox / Queue without breaking v2 semantics.
...
Before committing to a Mailbox / Queue upgrade I want to validate this new Silent Payjoin™️ idea.

Yes, the main thing to consider there is whether or not long lived mailboxes associated with UTXOs are even desirable.

This silent payments based idea IMO needs to be evaluated in relation to some potential alternatives/complementary approaches to deriving a shared secret between a sender and receiver. Xim, or something that leans on BIP 353/BOLT 12 more heavily, or uses a separate directory to resolve outpoints to bip-322 authenticated pubkeys, or perhaps something like riposte to send SP style notifications that aren't on chain transactions.

I am trying to get a better sense of the design space there and reviewing some of the older papers whose details I forgot, I will write this up once I've refreshed my memory and can characterize the tradeoffs a bit better.

To hide the payment value, a Silent Payjoin sender could broadcast a transaction to the receiver at the minimum fee rate with a trivial output amount as a notification, posting an Original PSBT to the tweaked subdirectory with the actual payment value. The notification wouldn't even need to spend (all of) the same input(s) as the Original PSBT.

👍

While potentially censorable (my understanding of the issue is that an ~input * silent payments tweak = subdirectory id can be identified by a directory with knowledge of the silent payments address)

In BIP 352 the receiver's on chain keys are derived as P_i = B + hash(input_hash·a·B || i)·G, which the receiver can detect by scanning all transactions. input_hash·a·B is the sender's way of deriving the shared secret, input_hash·b·A is the receiver's.

Once such a key is detected by the receiver in a transaction, then the same shared secret should be used to derive a different tweak for the receiver key / subdirectory ID. This might be derived as Q = B + hash(hash("payjoin domain separator") || input_hash·a·B)·G.

Because the underlying secret is not known to the directory, Q and P should not be linkable (decisional DH assumption).

I'm realizing at the end of my post that I may have misunderstood, since my hide-the-payment value paragraph assumes the subdirectory id for Silent Payjoins is obtained with a mutual tweak rather than a long-lived static one.

Correct, each notification transaction derives a different tweak that depends on the inputs the sender has chosen.

If in fact I have misunderstood, please elaborate on how Append Only Log gets us what the existing Directory doesn't w.r.t. silent payments sender-initiated payjoin.

My description which was a bit confused & confusing. The POST semantics are orthogonal to this, append only semantics are only necessary for SNICKER type messaging, where no shared secret between sender & receiver is derived, and therefore all senders would derive the same receiver key. This is of course bad for censorship and bad for privacy.

Using SP to notify is really only about deriving ephemeral in lieu of a BIP 21 URL with pj param, where per payment receiver public keys from a static silent payments address.

Therefore this alternative way of establishing a shared secret would work just as well with any of last writer wins, write once, append only semantics, since they fix the main downside of a naive SNICKER inspired approach.

The only situation in which append only semantics help is that in write once semantics only the first sender can message the receiver, in last writer wins there's a race condition where two payments arrive in between receiver polls and the first one is missed.

So tl;dr - append only semantics only help multiparty setting where there's a shared subdirectory with multiple writers and nothing like a turn based approach to keep their writes separate, or the sub-optimal scenario where there is no out of band derivation of shared secrets and therefore receiver public keys are reused.

Padding

With regards to padding, I think the way to do this is to specify that padding should have a minimum value (this is the most important), and an expected value of somewhat higher than that with the padding amount sampled from an exponential distribution so that it's always a bit higher, and occasionally it's significantly higher.

However, if such multiparty protocols still split/shard their transcript over multiple subdirectories (a hybrid of the write once semantics and append semantics), each subdirectory would have a limited but random size, and write contention would still be reduced to avoid leaking the number of participants, so I don't think that's a serious issue.

Picking the minimum values is a consideration for how wasteful in bandwidth do we want to be right now in order to make any alternative protocols' traffic to blend in. I think the current value of ~8KiB is already a sensible balance?

To estimate the size of a complete transcript, there would also be some overhead in messages. For a tx output size upper bound of around 400KiB-4MiB, this can probably be bounded by some linear factor that might be substantial. For example if uncompressed range proofs are used, that's ~8kb per homomorphic value used, and there would O(n log n) commitments per tx for WabiSabi style DoS protection. If silent payments tweaking is mandatory for stateless address reuse avoidance, i believe that's O(n^2) overhead in total since each input must provide a tweak for every output, but maybe only O(n) if input_hash·a·G is shared in the protocol, which might be enough (still trying to figure this out sorry) (edit: the overhead has to be quadratic because the entity adding the output might not know b_scan, blinded tweak values must be published based on the public scanning key, and each input owner must multiply those by a to allow the input adder to derive the output address without revealing the relationship between the tweaked key and the SP address). At any rate, a protocol transcript would likely end up being on the order of megabytes or tens of megabytes in total, substantially more than the ~8KiB currently specified, but so long as it's split into to roughly fixed size chunks, that shouldn't be a problem.