mimblewimble team mailing list archive

[John Tromp <john.tromp@xxxxxxxxx>]

dear mimblewimblers,

I'd like to propose a potential alternative way to implement relative
time locks. It possibly qualifies as a "crazy idea" as Antioch alluded
to below. It can be thought of as a negative trigger.

I propose to call it a "No Such Kernel Recently" or NSKR lock.
Suppose we have transaction A that might appear on chain at an unknown
height in the future, and a transaction B, spending A's output, that
should only happen at least a day after A. We can refer to kernel A
inside kernel B and require that inclusion of B in a block at height h
is invalid if kernel A appears at any height from h-1440 up to (and
including) h.
Compared to a positive trigger that would require kernel A to have
been included at least 1440 blocks earlier, the obvious difference is
that NSKR doesn't require checking the entire kernel history from
height 0 to height h-1440, which is a big gain in efficiency and
allows kernel history verification to proceed with a small moving
window.

It may appear to have as a downside a seeming violation of the
following principle that Andrew brought up earlier:

> Agreed, I think we want to copy Bitcoin's attitude of "transactions, once valid, never stop being valid" although the reverse is allowable.

However, for B to be valid in the first place, by construction, A must
already be on chain to provide B with valid inputs. So B cannot be
invalidated by the appearance of A.

It thus seems that NSKR provide an efficient means to implement
relative time locks. Feedback welcome.

regards,
-John

> Your email matches the idea of "triggers" that I originally proposed
> for enabling relative timelocks back in Jan 2017:
> https://lists.launchpad.net/mimblewimble/msg00025.html
>
> The conclusion that Andrew Poelstra and I came to back then was the
> same: kernels (previously referred to as "excess values") are the
> logical place for it.
>
> >We would need to maintain an unpruneable index of all kernels on all nodes.
>
> This may not be practical in terms of bandwidth (and maybe adds
> complications for IBD?), but the transaction that depends on the
> inclusion of a kernel could be accompanied by an SPV proof to that
> kernel. It would be in the interest of the sender to reference the
> "first seen" one.
>
> >We would need to handle the case of it being added prematurely
>
> Premature to whom? Triggering the countdown of a relative timelock
> would imply some kind of disagreement that needs to be resolved by the
> blockchain, so it will always be premature to the party that is being
> forced to react.
>
> >we have the ability to actively monitor for and observe this on-chain
>
> Yes, that seems like an absolute prerequisite. If triggering the
> timelock is not detectable, then the other party in the channel cannot
> respond to it.
>
> >I want to encourage anyone with _any_ ideas (maybe even the particularly crazy ones)

> It seems inherent that at least *something* needs to noticeably appear
> or change in order to trigger the countdown. Here's an idea that I
> think is absolutely terrible but fits the 'crazy' bill. You could use
> the relative timelock capabilities of a different blockchain (e.g.
> Bitcoin) to force someone (yes, they'd need to have equivalent value
> locked up in that chain...) to reveal an RSA timelock puzzle,
> triggering the countdown. Based on Ethan Heilman's idea:

> -- Ruben Somsen
> >
> > 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).