← Back to team overview

mimblewimble team mailing list archive

Re: Relative Locktimes in Grin

 

John,

> The real problem seems to be that anyone doing a sync from genesis afterwards,
> lacks the data to verify the relative timelock, since the referenced
> output is obviously
> gone from all later utxo sets.

Yes agreed - this is what we had been discussing in gitter.
"Historical validators" (if that's the right term?) cannot verify these after the fact once these outputs get removed.

> For clarity, is this about how light clients can verify relative
> locktimes without
> having the full kernel history?

> [...] This is where
> Merkle proofs seem to be required to verify the height of the
> referenced kernel.

That is part of it yes - We had discussed Merkle proofs but it adds a significant amount of complexity to any solution right now.
I think we have settled on the assumption (for now at least) that all clients will have the full kernel history.
Knowing that when we decide to relax this assumption we can use Merkle proofs for this.

The bigger issue was around keeping an exhaustive index of kernels. There are some concerns around needing to enforce uniqueness globally across all kernels (at consensus level).
But with "first seen" or "last seen" we can avoid needing an exhaustive index, so maybe maintaining an index is not too controversial in this case.

"First seen" vs "last seen" is more around how to unambiguously identify a kernel if we do not enforce uniqueness. We need a way for everyone to agree on exactly which instance of the referenced kernel we are talking about.
The index gets more complex if we need to handle duplicates in the MMR (particularly when dealing with re-orgs and re-indexing recent blocks).
A Merkle proof would unambiguously do this for us, but maybe we can do this without the added complexity if we take the assumption that we have the full kernel history.


— Antioch


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, September 13, 2018 5:15 PM, John Tromp <john.tromp@xxxxxxxxx> wrote:

> dear Antioch,
>
> > 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.
>
> I don't think that's the problem. An output can't be doublespent,
> and the referenced output should be one of its inputs,
> so if the 2nd tx is to be valid, then the referenced output is still unspent.
> The real problem seems to be that anyone doing a sync from genesis afterwards,
> lacks the data to verify the relative timelock, since the referenced
> output is obviously
> gone from all later utxo sets.
>
> > 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.
>
> It appears that full nodes will need to keep a complete kernel history
> in any case,
> to aid new peers syncing.
> Doesn't that make the cost of maintaining an index relatively
> manageable for full nodes?
>
> > So we would like to be able to implement this without relying on an index of
> > all kernels.
>
> For clarity, is this about how light clients can verify relative
> locktimes without
> having the full kernel history?
> For the initial sync, they could first record the (presumably) short
> list of all referenced kernels,
> then simultaneously verify and use this list while checking all
> historic kernels.
>
> For an extension sync, there is an issue for new kernels referring
> back to old kernels from the initial (or earlier) sync. This is where
> Merkle proofs seem to be required to verify the height of the
> referenced kernel. Is this where your first vs last seen comes in?
>
> regards,
> -John




References