mimblewimble team mailing list archive

[Antioch <apeverell@xxxxxxxxxxxxxx>]

Hey all!

The Grin team is doing some brainstorming around how best to implement "relative locktimes" and we wanted to open this up to the wider community to see if anyone has additional thoughts and ideas around this.

To clarify - this discussion is about "transaction locktimes" and not "output locktimes".
This is a minimum block height (relative or absolute) that a tx will be accepted after (and invalid prior to this height).
This is not a way to lock an output on-chain and make it unspendable before a certain height (although these concepts may be closely related).

Grin currently has "absolute locktimes".
Each tx kernel includes a lock_height that specifies the earliest height this tx can be included.
We sign the lock_height alongside the fee in each tx kernel. This lock_height can be thought of as roughly analogous to the concept of nLockTime in Bitcoin.

What we want is a way to add "relative locktimes". Presumably by referring to some prior piece of data on-chain. Bitcoin does this with nSequence field on inputs (a relative number of blocks since the output being spent).

The problem with this in Grin is we don't really have inputs. They are not stored in the blockchain. An input in Grin is literally just a reference to a prior unspent output.
Once these txs are included in a block the inputs are effectively thrown away (along with the now spent outputs). All we maintain is the UTXO set and the tx kernels themselves.

Which suggests that if we want to refer to some prior piece of data then we refer to either -
  * a prior (unspent) output, or
  * a prior tx kernel

Note: We cannot simply refer to a prior block because we need to refer to something that may _not yet_ exist on-chain. We want to be able to create and sign two txs, one with a lockheight relative to the other before either has been broadcast and confirmed in a block.

Prior (Uspent) outputs:
The benefit of referring to a prior output is we enforce uniqueness across the UTXO set
so we can be confident we are referring to the correct prior one, avoiding any ambiguity around the "relative to x at height h".

The problem with outputs though is nodes only maintain data relating to _unspent_ outputs (the UTXO set).
Spent outputs are removed and effectively act as if they never existed. This is a core tenet of the scalability (and privacy) of MW.
So if we refer to an output we appear to be limited to only referring to an _unspent_ output.
Which is fine initially, you create two txs, one with a kernel referencing an output in the earlier tx. But then things get complicated if the referenced output gets spent during (or even before) the timelocked period.

Prior kernels:
Kernels live forever (at least today in Grin).
Referencing a kernel from another kernel is "cleaner" (same MMR) than having a kernel reference an output (across two MMRs).
The problem though is that kernels live forever.
If we need to enforce uniqueness we need to do it across the global set of all kernels.
We would need to maintain an unpruneable index of all kernels on all nodes.
And the kernel set is only going to grow ever larger.

So we would like to be able to implement this without relying on an index of all kernels.

We are currently thinking through a couple of variations of this - allow non-unique kernels and refer to a prior kernel using either "first seen" or "last seen" semantics to resolve ambiguity.

"Last seen" would appear to introduce a vector for denial-of-service.
A mischievous actor could easily craft txs repeatedly (re-)adding a duplicate kernel, forcing the relative locktime to block indefinitely.

"First seen" avoids this problem, we have more control (but not complete control) over when the first instance of a given kernel is added. We would need to handle the case of it being added prematurely but we have the ability to actively monitor for and observe this on-chain.

This is basically where we are at right now with "relative locktimes" -
  * We (think) we need to refer to some prior piece of data on chain
    * n blocks after some x appearing at block height h
  * We want the flexibility to reference something _not yet_ on chain
    * This rules out simply referencing a prior block header
  * All we have to play with are UTXOs and kernels
  * We enforce uniqueness across the UTXO set
  * We would like to avoid needing to enforce uniqueness across the full kernel set
  * We would like to avoid all nodes needing to maintain an index over all kernels

What are we missing here? Is there some subtle thing we can do to allow for a simple "relative locktime" imnplementation?
Is there a way to do this avoiding a reference to either a kernel or an output?

Thoughts and feedback please!
I want to encourage anyone with _any_ ideas (maybe even the particularly crazy ones) to chime in here.
We can move it to the forum if we need to.

— Antioch (and the rest of the Grin team).