Creating and Accepting Payjoin Proposals

[arminsabouri]

The following are my notes on this general problem and how we can tackle in in the simulations and a place for us to have a discussion.

Takers select inputs to satisfy their payment obligations in priority order. For each available strategy, they construct candidate transactions: unilateral payments, batched payments, and combinations that exploit overlapping inputs i.e utxos the taker expects to spend regardless. This produces a weighting over UTXOs.

The taker then evaluates order book utxos, preferring those that produce denser sumsets. This second pass may raise the effective value of UTXOs that ranked lower in the initial weighting. If no order book UTXOs are worth coinjoining with, the taker falls back to a batch payment, decomposing change across a multi-output transaction. A cost function governs all of these paths.

Some order book UTXOs are preferred over others; that preference is reflected in a payoff.

Takers should generate plans and maintain state across timesteps. Currently this statefullness missing entirely. all computation is redone from scratch on each step. As new information arrives, existing plans should be updated incrementally rather than recomputed (statefull ness is probably not a blocker).

Accepting a proposal is relatively cheap. It carries a payoff, and the primary cost is opportunity cost subject to rate-limiting. Accepting an aggregate proposal is a commitment with real cost. Refusing to participate after accepting possible but has consequences.

Selecting specific coins over others leaks information about wallet state and cost function preferences. The intended behavior: announce coins in the order book first, then make proposals using those coins and subsets of coins already posted. From an observer's perspective, it should be impossible to distinguish takers from makers, and wallet state or cost function details should not be inferrable.

Upon receiving an aggregate proposal, the taker has two options: back out or accept. If backing out, the taker may modify the aggregate proposal and rebroadcast it. Acceptance is warranted when, given all available information, the aggregate proposal remains preferable to all other plans.

[nothingmuch]

some corrections for what i was describing yesterday, note all of this is being covered in more detail in the concrete cost function writeup

Takers select inputs to satisfy their payment obligations in priority order.

important: this is selection without replacing the inputs, i.e. first select for the most urgent payment, then out of the remaining coins select for the next one, etc

For each available strategy, they construct candidate transactions: unilateral payments, batched payments

unilateral payments is that baseline, in addition, independently (i.e. with the full available set of coins), also construct a plan for at least one batched payment

in this selection the cost function is tweaked so that various consolidation penalties etc are not included, i.e. this represents the action that makes sense to take within a context that is maximally favorable (dense subset sum, good provenance, etc etc)

this provides two branches in the decision tree, one "big" but shallow branch for the batch payment, and one deeply nested one for the fallback case. there can be multiple alternatives constructed for each various kind of strategy, the point here is to have many plans (paths down the decision tree) that are already prepared ahead of time

and combinations that exploit overlapping inputs i.e utxos the taker expects to spend regardless. This produces a weighting over UTXOs.

more precisely out of the various alternatives in the decision tree, identify the shared elements to these... those are the coins which should be involved in co-spend proposals (announced on the order book, and used to make and accept proposals)

The taker then evaluates order book utxos, preferring those that produce denser sumsets.

here, the cost function terms related to others' coins are reenabled, and the same plans are reevaluated with this more pessimistic evaluation. the best case payoff is computed by disabling all the penalties. the worst case payoff is computed by enabling them and assuming the transactions are unilateral. the goal at this stage is to find combinations of coins from the order book that get closer to the best case, and then construct co-spend proposals that incentivize them to be spent together with wallet's coins, and to be aggregated together with the other proposals made by the wallet but without strongly linking the wallet's coins.

This second pass may raise the effective value of UTXOs that ranked lower in the initial weighting. If no order book UTXOs are worth coinjoining with, the taker falls back to a batch payment, decomposing change across a multi-output transaction. A cost function governs all of these paths.

strictly speaking when the cost function is defined to be monotone, then the only way for multiparty proposals to be evaluated as less valuable than unilateral ones is if the payoff offered in the co-spend proposal exceeds the subjective value obtained. sending such proposals is not rational by definition, but is trivially avoided by sending proposals with zero or even negative payoffs to the counterparty coins' owners, for whom the proposal might still be attractive because of their subjective valuation.

Some order book UTXOs are preferred over others; that preference is reflected in a payoff.

the taker (or perhaps we should say proposer, since taker/maker is about whether or not the payoff is positive or negative, and that can vary from one proposal to the other... it's only in the context of an aggregate proposal that a net-taker or net-maker can be defined based on whether their objective payoff is positive or negative but there is no other qualitative distinction) should choose a payoff offer that is somewhere in the interval between their evaluation being subjectively 0 cost to the maximum payoff they can obtain based on the evaluation with the penalty terms enabled and the other coins included (not the best case scenario where the subjective payoff is maximized, as that contingency may not be realized and would result in overpayment).

Takers should generate plans and maintain state across timesteps.

the decision tree described above is these plans, and it can be continually updated (kind of like a double ended queue, where a new plan can replace and evict a worse plan based on the payoff interval computed by the two variations of the cost function)

Currently this statefullness missing entirely. all computation is redone from scratch on each step. As new information arrives, existing plans should be updated incrementally rather than recomputed (statefull ness is probably not a blocker).

i don't think that's necessarily required, for small wallet states where the entire decision space can be enumerated at every time step, or even with randomized searching through the decision space so long as the randomization is done consistently between timesteps, this is just a computational penalty so we can treat it as an optimization for later

however i do think it's conceptually simple to keep state, especially if we plan to do this kind of optimization more aggressively later

Accepting a proposal is relatively cheap. It carries a payoff, and the primary cost is opportunity cost subject to rate-limiting.

when i said that i neglected to mention that this is only true if the payoff is objectively or the cost function says the subjective payoff is positive, propsals which have a negative payoff to a maker (or shall we say "acceptor"?) and which don't improve the evaluation of their plans in any way should not be accepted, as that reduces the likelyhood that an aggregator will find an aggregation that they are happy with

co-spend proposals' purpose is to reduce coalition formation to iterated bilateral negotiations followed by something like a combinatorial clock auction, since otherwise coalition formation is difficult (i.e. finding stable coalition structures is hard in a complexity theory sense). they are also the direct mechanism through which a transferrable utility is introduced to the coalition formation game, otherwise it'd be a hedonic game and those are much more difficult to find stable equilibria for.

Accepting an aggregate proposal is a commitment with real cost. Refusing to participate after accepting possible but has consequences.

specifically refusing to participate is the same as failing to sign at the end of a session which is considered potentially byzantine behavior and may carry penalties (others will refuse to accept proposals with the coin in question or avoid making offers)

Selecting specific coins over others leaks information about wallet state and cost function preferences. The intended behavior: announce coins in the order book first, then make proposals using those coins and subsets of coins already posted. From an observer's perspective, it should be impossible to distinguish takers from makers, and wallet state or cost function details should not be inferrable

it's not impossible, since the order in which coins are posted in the order book is apparent

if an adversary is knows the wallet state and preferences of a target then they would be able to evaluate whether that target is likely to have made the proposal or not, so working backwards if the adversary deems several proposals to be likely to be complementary, that leaks information about the wallet state that makes them complementary

the main mechanism through which these revealed preference leaks are mitigated is making smaller independent proposals that mostly avoid using more than one of the proposer's coins, and avoid constraining the parameters too narrowly

the space of potential aggregations is exponential in the size of fully accepted proposals being circulated, so partitioning them is computationally difficult the stronger WEAKER the constraints, this is not unlike the sub-transaction model but with additional degrees of freedom

finally, some randomness can be introduced to proposals

of course, not all of the proposer's intended-to-be-spent coins should be named in proposals, rather a minimal set (for example the currently "luckiest" coins according to anti-sybil randomization metric thing are the best to post in the order book) since additional coins can be added after the initial input set is determined... the only constraint here is that the total weight unit allocation per initial input (inputs named in the aggregate proposal) suffice for covering the blockspace of the additional inputs and the outputs, that can be arranged using the transaction parameter lattice (the interval on the allowable allocation can just have a lower bound that will suffice).

if it's not expected that a coin will be offered some positive payoff based on a wallet's best guess of what others' cost functions would say, it's better to post it as a late input and limit the total information revealed in co-spend proposals

Upon receiving an aggregate proposal, the taker has two options: back out or accept. If backing out, the taker may modify the aggregate proposal and rebroadcast it. Acceptance is warranted when, given all available information, the aggregate proposal remains preferable to all other plans.

this applies to both takers and makers, not just takers, and modifying the aggregate proposal like i said is not strictly possible since the party in question would not know the final payoff vector made by the aggregator (which distributes the surplus), but what they can reproduce is the set of aggregated proposals (and of course they are free to modify it, select different transaction parameters from the meet computed from the aggregated proposals, or and distribute the surplus at their discretion)

[nothingmuch]

another notable thing that came up in the convo that seems suitable here, whenever i referred to "the" cost function i mean a function of predicted wallet state that can be used to evaluate transactions as state transitions by comparing the state before, but also incomplete state transitions, i.e. when you only know of some of the pieces of a transaction but still don't know what other parties in it will choose to do. this cost function needs to be monotonically decreasing in new information for the bracketing notions to work and for incentive compatibility, which means that as you learn of the choices made by other parties you should always be indifferent to or happier with this new information, but never negatively surprised, which means another purpose of co-spend proposals is to set things up so that such outcomes are precluded.

this cost function is used to generate a decision tree and ultimately to choose from it, but there are additional constraints such as choosing randomly from a range of acceptable proposals, as opposed to the optimal one. for this reason the more accurate sense of the term would refer to this function, but so far we've been referring to it as the meta cost function, in order to keep the definition of "the" cost function simple and deterministic.

"the" cost function has an explicit form, it is a linear combination of terms, where each term is a function of the transaction data, and is scaled and varies as a function of time independently of the specific term. the objective cost term is just the actual fee cost of a transaction. the utility of transfers out of the wallet depends on time (relative to a deadline, e.g. for a payment) and once this dominates over the reduction in balance (from both objective and the other subjective terms) then that implies sense to execute a transaction. subjective terms concerning privacy can be things like subset sum density, where absence of a dense subset sum in a transaction discounts or penalizes the value of the outputs which result from it, and where a dense subset sum instance (which implies ambiguity in the sub-transaction model) applies no penalty to the resulting outputs, so a state transition that uses funds that do not originate from a transaction which has this property and replaces them with new coins that do represents an increase in this discounted balance, suggesting that this action is desirable (even though objectively the balance will typically decrease due to the blockspace costs). in order to produce the different brackets as discussed in the previous comment, some terms are just set to 0 (i.e. their penalty is not applied).

the meta cost function does not need to be computed explicitly it's just a process for pruning the decision tree and then choosing one of the concrete paths within it, and there is no apparent engineering benefit to describing this mathematically as a function.

better terminology than cost function and meta cost function would be helpful.

[arminsabouri]

@nothingmuch you mentioned "bracketing" a couple times. Can you breifly explain what you mean?

[nothingmuch]

it's an interval of costs, from highest cost / worst case to lowest cost / best case, that can be computed for an action independently of any 3rd party information.

given a plan/action, where for instance more than one coin is spent, if this is a unilateral transaction the consolidation should penalize the value coins that would be created by this transaction, but if it's done as a sub-transaction in a multiparty transaction where the inputs of the other users generate a sufficiently dense sumset, there should be no such penalty.

therefore we can instantiate the cost function twice, once where this penalty is in full effect, and once when this penalty is omitted entirely. due to the monotonicity property, the evaluation according to the second parameterization of the cost function will necessarily be more favorable, representing the best case scenario.

so for every plan we have two scores, the cost of the action in the worst case for privacy (unilateral) and best case. the evaluation of the action that is eventually taken will be somewhere in between, for example if the deadline arrives and no multiparty session has succeeded, then the worst case will be realized, but if it succeeds there's no guarantee that i'll be as good as the best case scenario (though co-spend proposals' parameter lattice is meant to make it so that, contingent on a session succeeding, the upper bound on the cost is much likely to be better than the worst case, potentially arbitrarily close to the best case, and the final ACK on the aggregate proposal can guarantee this upper bound is in effect for a specific session but still contingent on it succeeding)

[bc1cindy]

@arminsabouri I'm open to help if needed