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@lists.launchpad.net Unsubscribe : https://launchpad.net/~mimblewimble More help : https://help.launchpad.net/ListHelp
