← Back to team overview

mimblewimble team mailing list archive

Re: Relative Locktimes in Grin

 

Mimblewimblers,

I'd like to propose a modification to NSKR locks that may eliminate the need to explicitly reference a prior kernel.

Assumptions -
* Grin/MW allows duplicate kernels to exist on-chain.
* A duplicate kernel can be reused across different transactions, with compensating adjustments to the kernel excess via the kernel offset.

Instead of kernel B referencing kernel A with a relative lockheight between them, we can instead have two instances of the same kernel A and A' with a relative lockheight between them.

A sort of self-referential negative trigger.
Each instance of the kernel would delay the next instance for at least the specified lockheight number of blocks.

John Tromp wasted no time in naming this "No Recent Duplicate" or NRD locks.

An NSKR kernel explicitly references a prior kernel and this reference would need to be stored on-chain.
An NRD kernel would simply not be valid within n blocks (say 1440 blocks for 1 day) of any prior instance of itself.
Note the first instance of an NRD kernel would trivially meet the conditions of the lock, with no prior instance existing to lock it.

The same "moving window" concept of recent history would still apply, allowing kernel history to be efficiently verified.
For a relative lock height of 1440 we need only look back over 1440 blocks of history as the lock "fails open" beyond that.

One downside to this is the later referencing kernel and the prior referenced kernel would both be flagged as NRD.
In the case of NSKR only the later referencing kernel need be flagged as such.

This would make lookups easier and cheaper though as we would not need to maintain a full index of recent kernel history.
We would only care about recent NRD kernels.

NRD locks may solve the problem of how to reference a prior kernel without requiring any additional on-chain data beyond the relative lockheight itself.


Feedback appreciated.

- Antioch



‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Friday, March 6, 2020 1:08 PM, John Tromp <john.tromp@xxxxxxxxx> wrote:

> 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).
>
> --
>
> Mailing list: https://launchpad.net/~mimblewimble
> Post to : mimblewimble@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~mimblewimble
> More help : https://help.launchpad.net/ListHelp




References