Relative locks with FCMP++

[tevador]

The legacy unlock_time field in Monero is being deprecated. It's planned that the next hard fork will enforce a value of 0 in all transactions.

The arguments against unlock_time are:

1. It's not actually useful for any decentralized protocol (payment channels, atomic swaps).
2. It's a DoS vector on the FCMP++ tree.
3. It creates anonymity puddles.
4. There have been issues with merchants receiving maliciously locked payments.

Relative locks

Relative locks are useful for a variety of decentralized protocols. Notably, payment channels are notoriously hard to design for Monero. The simplest payment channel protocol only requires adaptor signatures and relative locks. Adaptor signatures are already possible with FCMP++ (and the separate membership proof further facilitates pre-signed transactions). The only missing feature is a simple relative lock.

Note that Monero already enforces a relative 10-block lock. For FCMP++, it means the tree root R used for the membership proof must be at least 10 blocks old. This proposal adds the option to make the lock longer than 10 blocks.

Let Rh be the FCMP tree root at height h and ref be the explicit transaction reference height (the earliest height the transaction is mineable), which is specified in the membership proof.

This proposal completely changes the way locked transactions work after the FCMP++ hard fork. The lock is not applied to the transaction outputs. It's applied to transaction inclusion in the blockchain. Locked transactions cannot even enter the mempool until they unlock.

Simple "leaky" locks

The simplest way to implement a relative lock with virtually zero cost would be to disable the original Monero lock mechanism but allow unlock_time to have a value of 0 or 1. The relative lock would be enforced by the consensus layer by forcing a specific value for the FCMP tree root R:

unlock_time	R	Approx. lock duration
0	Rref-10	20 minutes
1	Rref-720	24 hours

Transactions with unlock_time = 0 enforce only the default 10-block lock, while transactions with unlock_time = 1 enforce a 720-block lock, which corresponds to a lock time of 24 hours, which is sufficient for the dispute mechanism in decentralized payment channel protocols.

Because the unlock_time field is public, I'm proposing only 2 values for the lock time to limit the impact of the resulting anonymity puddles. Time-locked transactions would be easily identifiable in the blockchain. To avoid leaking the fact that the transaction was time-locked, wallets could randomly set unlock_time to 1 when spending an output older than the lock time with a small probability. The leakage would be limited to the fact that the age of the spent output was at least 24 hours.

Hiding locks with a ring signature

@UkoeHB suggested a more private solution based on a ring signature on the root hash comitment.

The protocol will support a few possible lock times, for example:

i	Ri	Approx. lock duration
0	Rref-10	20 minutes
1	Rref-90	3 hours
2	Rref-720	1 day
3	Rref-5040	1 week
4	Rref-40320	8 weeks
5	Rref-262800	1 year
6	Rref-2102400	8 years

Each transaction will include an additional commitment L = j H + x G with j equal to one of the i values from the table above (i.e. 0 <= j <= 6). The value j = 0 corresponds to the default 10-block lock. The commitment L is signed by the spend authorization proof.

The FCMP++ proof outputs a tree root commitment R = Rj + y G where Rj is one of the Ri values from the table.

We then define the ring (L - i H, R - Ri) for each i = 0..6. Note that the prover will know the opening of exactly the j-th pair from the ring. This can be proven with a standard ring signature. The approximate size of a 7-ring signature is 256 bytes, which is relatively small compared to the size of the FCMP++ proof.

The purpose of this construction is for the pre-signed commitment L to force a relative lock without publicly revealing that the transaction was pre-signed and time-locked.

Payment channel protocol sketch

Here is a sketch of a trustless payment channel protocol that required a relative lock on a pre-signed transaction. The payment channel is bidirectional between Alice and Bob. Transactions fees are ignored for clarity.

Opening the channel

The channel is opened by Alice and Bob jointly signing 4 transactions: Fund, CloseA, CloseB and Recover. The Fund transaction is immediately submitted to the network. Alice keeps CloseA and Recover as her offline transactions and Bob keeps CloseB and Recover as his offline transactions.

The channel opening process is:

1. Alice and Bob agree on the initial channel balances.
2. Alice and Bob agree on a 2-of-2 stealth address Kfund.
3. Alice and Bob agree on a 2-of-2 stealth address Kclose0.
4. Alice and Bob jointly sign the initial Recover transaction, which spends from Kclose0 to Alice's and Bob's private addresses according to the correct channel balances. The Recover transaction is time-locked relative to the preceding Close transaction.
5. Alice generates a key pair and shares the public key TA0 with Bob.
6. Bob generates a key pair and shares the public key TB0 with Alice.
7. Alice signs her half of the CloseB transaction, which spends the entire channel balance from Kfund to Kclose0. Alice uses R + TB0 as the signature nonce. This creates an adaptor signature only Bob can complete.
8. Bob signs his half of the CloseA transaction, which spends the entire channel balance from Kfund to Kclose0. Bob uses R + TA0 as the signature nonce. This creates an adaptor signature only Alice can complete.
9. Finally, Alice and Bob jointly sign the Fund transaction, which spends their private inputs into the stealth address Kfund.

The channel opening is complete when the Fund transaction is confirmed on the Monero network.

              [Fund]
                |
     ___________|_____________
     |                       |
     v                       V
[CloseA(0)]             [CloseB(0)]
     |                       |
     |_______________________|
                |
                v
     [Recover(0)(time-locked)]

Channel state update

The channel transitions from state N-1 to state N (with new channel balances for Alice and Bob) as follows:

1. Alice and Bob agree on new channel balances.
2. Alice and Bob agree on a 2-of-2 stealth address KcloseN.
3. Alice and Bob jointly sign the N-state Recover transaction, which spends from KcloseN to Alice's and Bob's private address according to the correct channel balances. The Recover transaction is time-locked relative to the preceding Close transaction.
4. Alice generates a key pair and shares the public key TAN with Bob.
5. Bob generates a key pair and shares the public key TBN with Alice.
6. Alice signs her half of the N-state CloseB transaction, which spends the entire channel balance from Kfund to KcloseN. Alice uses R + TBN as the signature nonce. This creates an adaptor signature only Bob can complete.
7. Bob signs his half of the CloseA transaction, which spends the entire channel balance from Kfund to KcloseN. Bob uses R + TAN as the signature nonce. This creates an adaptor signature only Alice can complete.
8. Alice signs her half of the N-state PunishA transaction, which spends the entire channel balance from KcloseN-1 to Bob's private address. Alice uses R + TAN-1 as the signature nonce, but omits tAN-1 from the signature response, which makes the signature invalid.
9. Bob signs his half of the N-state PunishB transaction, which spends the entire channel balance from KcloseN-1 to Alice's private address. Bob uses R + TBN-1 as the signature nonce, but omits tBN-1 from the signature response, which makes the signature invalid.

The new transaction graph looks like this:

               [Fund]
                 |
      ___________|_____________
      |                       |
      v                       V
[CloseA(N-1)]           [CloseB(N-1)]
     |                       |
     |_______________________|
                |
                |
                -> [Recover(N-1)(time-locked)]
                |
                |
                -> [PunishA(N)]
                |
                |
                -> [PunishB(N)]


              [Fund]
                |
     ___________|_____________
     |                       |
     v                       V
[CloseA(N)]             [CloseB(N)]
     |                       |
     |_______________________|
                |
                v
     [Recover(N)(time-locked)]

Closing the channel

Type	Description	On-chain transactions
collaborative close	Alice and Bob jointly close the channel	Fund, Withdraw
undisputed force close	one party forces the channel to close	Fund, Close, Recover (time-locked)
disputed force close	one party forces the channel to close with incorrect state	Fund, Close, Punish

Collaborative close

The happy path is if Alice and Bob both agree to close the channel. In that case, they jointly sign a new Withdraw transaction, which spends from Kfund to Alice's and Bob's private addresses according to the final channel balances.

Undisputed force close

If Bob is unresponsive, Alice can force the channel to close by publishing the CloseA(N) transaction. She then has to wait for 24 hours and then publish the Recover(N) transaction, which will distribute the funds in the channel according to the final state.

Note that this is the only case when a time-locked transaction with appears on the chain.

Disputed force close

Alice can try to maliciously close the channel with an old state by publishing CloseA(i) with i < N.

When CloseA(i) appears on the chain, Bob can recover tAi from the valid transaction signature (using the adaptor saved in step i+1). This allows Bob to complete the signature of the PunishA(i+1) transaction. Since the Punish transaction is not locked, Bob can front-run Alice's Recover transaction and punish Alice by taking the entire channel balance.

[UkoeHB]

To avoid leaking the fact that the transaction was time-locked, wallets could randomly set unlock_time to 1 when spending an output older than the lock time with a small probability. The leakage would be limited to the fact that the age of the spent output was at least 24 hours.

unlock_time applies to new enotes, not spending old ones. Wallets can't be randomly locking funds on send.

[tevador]

@UkoeHB I think you misunderstood. The repurposed lock is only applied to off-chain transactions. Locked transactions cannot be submitted to the mempool.

The wallet knows the age of the inputs it's spending. If that age is >720 blocks, setting unlock_time = 1 is easy, the wallet will only use a different FCMP root hash for the membership proof.

[tevador]

I added a payment channel protocol sketch that uses the proposed relative lock mechanism.

[UkoeHB]

Re: privacy

Setting aside perf, would it be possible to sign a ring signature on the FCMP++ root hash? Where it's a dual-layer ring, one layer is the commitments to zero of root hashes and the other is commitments to zero of multiples m of H. The relative lock L is a commitment to one multiple of H, and you sign in the ring sig on L - mH = xG (and include L in the SAL proof message). The root hash ring members are selected from pre-defined block depths (10 blocks, 1 day of blocks, 1 week of blocks, etc.) relative to the indicated signing block (at >= 10 block depth).

The question in my mind is whether FCMP++ proofs could be constructed relative to a commitment to the root hash, rather than the root hash directly.

[UkoeHB]

When CloseA(i) appears on the chain, Bob can recover tAi from the valid transaction signature (using the adaptor saved in step i+1). This allows Bob to complete the signature of the PunishA(i+1) transaction. Since the Punish transaction is not locked, Bob can front-run Alice's Recover transaction and punish Alice by taking the entire channel balance.

This is the interesting bit.

We were discussing in MRL whether unlock_time could achieve this. My idea that almost works (but you are right, does not):

• Pair Close variants with DummyLock. DummyLock spends a tiny amount from K^fund, has a timelock, and outputs a zero-amount enote.
• Write Recover txs so they spend from DummyLock's output. This way DummyLock must be submitted along with Close variants if you want to recover.

The problem is current timelocks are based on a specific blockheight, not relative (as in this proposal), so if the channel is old enough Recover can always be submitted immediately after an old Close.

[tevador]

Setting aside perf, would it be possible to sign a ring signature on the FCMP++ root hash? Where it's a dual-layer ring, one layer is the commitments to zero of root hashes and the other is commitments to zero of multiples m of H. The relative lock L is a commitment to one multiple of H, and you sign in the ring sig on L - mH = xG (and include L in the SAL proof message). The root hash ring members are selected from pre-defined block depths (10 blocks, 1 day of blocks, 1 week of blocks, etc.) relative to the indicated signing block (at >= 10 block depth).

I think that would work and would completely hide the fact that a transaction was time-locked. However, it would require significant changes to the FCMP circuit, which is not something we'd want to do at this stage (code already written, audits in progress etc.).

The FCMP proof could use an artificial root R' = a R10 + b R720 + c R5040 + x1 G, where a, b, c are 0 or 1 and a + b + c = 1. The pre-signed lock commitment would be L = a H1 + b H2 + c H3 + x2 G for some generators H1, H2, H3. The circuit would prove the knowledge of a, b, c, x1, x2 with the public witnesses R', L, R10, R720, R5040, where Rx is the tree root x blocks ago.

CC @kayabaNerve

[kayabaNerve]

Having yet to read the issue in its entirety,

The FCMP as-is already outputs a Pedersen commitment to the tree root. It's outside of the circuit that we unblind it and reveal the underlying root. By modifying the library, but not the circuit, it should be fine to then pipe into a ring signature.

One may also allow the user to declare the tree roots (subject to the standard validity criteria), where these become the top layer of the tree proven against. This wouldn't require modifying any of the FCMP code at all, with caveat the trees would be expected to have consistent length. There also wouldn't be a need to require only one root has a non-zero coefficient so long as we're fine publicly declaring the candidate roots.

I'll try to read the issue in full and give a more specific response later.

[tevador]

The FCMP as-is already outputs a Pedersen commitment to the tree root.

Thanks, I wasn't aware. The solution proposed by @UkoeHB with a two-layer ring signature should work without changes then. If we allow 5-6 possible lock times, which should be plenty, I'm estimating that the transaction size would increase by about 300 bytes. I think the cost of this change would be quite low, which makes for a strong case in support of implementing relative locks this way on top of FCMP++.

[UkoeHB]

Wanted to point out that side-effects from state changes (e.g. a real-world exchange) must not occur until after a state change is fully finalized and validated. Otherwise there are race conditions that let one participant close the previous state without penalty (e.g. initialize a payment, receive the good, then back out without completing the payment state change by submitting close on the previous state but without threat of punishment).

[UkoeHB]

I think you can hostage a channel by receiving a punish but refusing to send your own punish. If the partner tries to close + recover with the previous state, the attacker can just punish and take the funds. The partner may not want to close with the current state e.g. because the current state is a transfer of funds from them to the attacker but they did not receive the goods of an exchange yet. If favorable, the attacker can close + recover the current state. This is a pretty standard problem for 2-of-2 with no arbitrator, solvable with a reputation system (implicit or constructed) or using 2-of-3 with current-state punish txs signable by arbitrator and built before participant punish txs are made.

It's likely that 2-of-3 would be mandatory for high value[+] transactions (mainchain has the same issue/solution and maybe 'take it there' for high value; but that would make channels more limited). No idea how LN/etc. handle this.

The current state update design favors the recipient of money transfers. An alternate arrangement that favors the recipient of goods (which may be less desirable, since vendors are more sensitive to reputation):

• LONG timeline Recover that pays out previous state but ties to current state Close
• Close
• Punish
• ...transaction...
• Recover

[tevador]

The partner may not want to close with the current state e.g. because the current state is a transfer of funds from them to the attacker but they did not receive the goods of an exchange yet.

The party receiving funds should sign Punish first. If the other party then refuses to sign, closing with the new state is favorable.

[UkoeHB]

Don't think punish order matters.

• Fund-receiver misbehaves: ignore punish step entirely, just close-recover with the new favorable state before it's time to complete their side of the bargain.
• Fund-sender misbehaves: this guy wants to close the previous state after receiving goods, but can't because good-sending is always after they send a Punish (regardless of order).