Pre-paying the coordinator fee

[MaxHillebrand]

This might be too early to bring up, but I have a couple ideas on the coordinator fee, and am curious if the crypto magic of the current protocol would hold up for it.

tl;dr

unlinkable pre-payment of the coordinator fee across rounds.

Why?

avoid creating small value coins

In a self-spend, say the user has inputs worth 1.01 btc, and the fee is 0.005 btc, then the user would receive 1 btc anonset output, no on-chain change, but instead a fee pre-payment worth 0.005 btc, which can be used for the next round.

I have an intuition that this would make subset sum analysis on non-equal-value outputs even more difficult.

getting rid of small value coins

If a user has a small value coin, say 0.01 btc, then for most real payments he would have to consolidate it with another coin, thus revealing common ownership. Instead, he can register this small coin in the input of a CoinJoin, without receiving any output, the value goes directly to the coordinator fee output. In exchange he gets 0.01 btc fee pre-payment that can be used in a subsequent round to pay for the fee.

gift CoinJoin to others

The coordinator could gift fee pre-payment to users, as a reward for contributions, or as marketing, or for whatever reason. If the pre-payment can be transferred between users, then this could be a further opportunity to gift rounds to others.

Privacy benefits

I think this would mess with assumptions of the CoinJoin quite a bit. The details of course depend on how ever we are going to structure the tx. But in general...

• some users have inputs, but no outputs
• some users have value inputs = outputs
• some users have value inputs > outputs

Legal aspect

I spoke with Balint, and in general, having a fee pre-paid giftcard is not of legal concern, this is not a custodianship. Rather, it is debt on the companies balance sheet, denominated in bitcoin, and it is settled in the providing of the coordination service. There is no payout of pre-paid giftcards to bitcoin directly. [that would be the users has no inputs, but has outputs, and provides the giftcards off-chain.]

Crypto magic

Here I need Your help with clarification if something like this is possible. The idea is that the coordinator can give out a token with a certain value. This token can be used in input registration to prove that the fee is paid. If possible, without the coordinator finding out that such a gift card was used. Or at least, that he does not know which gift card was used.

[nothingmuch]

with the more interesting building blocks we've been exploring it should be possible to realize this similar to or more simply than what i suggested in my first original draft: i think a reasonable way is to just have output registration require a pair of amounts, user output, and fees, and have long lived fee tokens only count towards the latter, whereas input credit tokens can count towards both

i suspect it'll be a while until we get there but i'm definitely already thinking about it

[nopara73]

I think the coordinator fee should not be part of this research at all. That should be a concern for implementations.

[MaxHillebrand]

yes @nothingmuch this seems to be what I'm talking about.

I agree with both of you that it is not pressing and part of the current priorities - however, I do think that we should keep the fees in mind, because they have to be in the implementation, and if the crypto magic does not work for them, then the protocol fails.

I just had a couple ideas that I wanted to note down here, it is more for future reference.

[nopara73]

How do you know the implementor will want to charge fees?

[nothingmuch]

Some notes following today's call:

• Fee amount and output registration amounts must be accounted separately in order to ensure that conversion is one way. This means there are both per-round fee credentials and long term fee credentials (lasting more than a just the duration of a round). Long term fee credentials and input amount credentials are convertible to per-round fee credentials, used to pay for the. Per-round fee credentials can be converted to long term fee credential claims (this is required so that the coordinator can know when the transaction is balanced and output registration has concluded).
• To avoid fingerprinting of users of fee credentials, per-round fee credential presentation and requests should be made mandatory, and null per-round fee credentials issued during connection confirmation similar to input amount credentials. All the coordinator will know is that either no users used fee credentials or some users used fee credentials, which it can infer based on the collected fees anyway, so long term fee credential presentation does not need to be mandatory.
• Long term fee credentials are issued after round termination. After tx confirmation of a successful round claims can be converted to long term fee credentials. After a failed round, long fee credentials need to be refunded. By including an input and signing last or waiting for a confirmed spend of one of the inputs the coordinator can be sure that the last user can't broadcast the transaction for a failed round after the fact after claiming a refund.
• Fee credentials could either be opt-out with a preconfigured total limit that is roughly the same as the current dust limit (where dust change outputs are omitted and distributed among base denomination outputs) or opt-in given the trust requirement.
• The coordinator can provide an additional discount on mining fees for users of fee credentials in order to incentivize rounder amounts and less UTXO set bloat.
• Clients may require multiple per-round fee credentials in order to make parallel requests, but generally need only one long term fee credential.
• Server state for long term fee credentials can be kept bounded by having several epochs, each with its own key, and pruning the nullifiers sets of expired epochs. Note that this requires credentials to be reissued into a new epoch before expiring. To avoid denial of service fee credential reissuance can incur a small cost (balance proof requiring a a small negative number of sats).
• Fee credentials can be made recoverable from the wallet seed if the t scalar in the MAC is given as a hash of an arbitrary preimage provided by the client, and this as well as the the randomness in the credential attribute (and hence serial number) are both deterministically generated from the wallet seed. Clients can obtain the last valid credential when recovering from seed by retrieving a bloom filter or Golomb coded set of used serial numbers, searching backwards from the first positive result (which may be a false positive). The server would need to save copies of previously issued MACs for all unexpired credential epochs. The client must then brute force the amount in order to find out the outstanding balance. Only non-zero fee credentials require deterministic randomness in the serial number commitments, since there is no point in discovering.
• If the coordinator sets a hard limit on the total amount per fee credential custodial risk can be limited and smaller range proofs required (primarily reducing the computational overhead, bandwidth difference is negligible).

[nothingmuch]

For this to be viable, we might need stronger security proofs for the unfogeability of MACs (perhaps we could consider Anonymous Credentials Light scheme as a drop in replacement, where if I'm not mistaken unforgeability is the same as regular Abe-Ohkubo-Suzuki ring signatures), see #96

When unforgeability only underpins denial of service protection, a break can be detected immediately and the consequences are not very serious. With long term credentials for prepaid fees, this is a much bigger risk for the coordinator, and the only way to detect a successful forgery is when the coordinator realizes it is insolvent, and the attacker already had their fees paid for by other users, which would be catastrophic.

[nothingmuch]

In order for the coordinator to know the total outstanding prepaid fee token amounts, conversions between different long lived credential epochs need to have cleartext amounts. This matters both for pruning nullifier sets, and for being able to validate/prove solvency.

However, it's noteworthy that the same need not apply for conversions between long lived fee credentials (only those of the most recent epoch) and per round fee credentials - if those balances are proven in zero knowledge and such a conversion is always done as part of obtaining null credentials (possibly with a 0) the coordinator only learns the total fee amount that was paid by redeeming prepaid fee credentials at the end of the round, which is beneficial for privacy. Note that this requires inputs to signal readyness to sign in order to transition to the signing phase, as the termination can't be inferred based on the outstanding credential balance in the round.