mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

To clarify a little bit, as this came up a couple times and is ambiguous in my email: in this setting the validator is expected to know all the individual S(x_i) in R. She can then easily check that the provided x_i in the proving triplet corresponds to a known S(x_i) in R.

I think this can be generalized so the S(x_i) that will never be checked anymore (say x_i is the commitment of an already spent output) can be kept as a sum. But I'd love to be proven wrong about that too.

- Igno

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Tuesday, September 18, 2018 10:23 AM, Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx> wrote:

> We introduce a sequence of elements x at position i, such that:
>
> S(x_i) = H(x_i | i) * G
>
> With G a generator point on an ECC curve and H a hash function. This sequence has a unique "root":
>
> R(S) = Sum S(x_i) = Sum H(x_i | i) * G = (Sum H(x_i | i)) * G
>
> We posit that membership in R(S) can be proven by just providing the triple <i, x_i, Sum_{j != i} H(x_j | j)>.
>
> Does that seem sound? This seems too simple for someone not to have thought about before, would anyone on this list have a reference?
>
> We're thinking this could be used as a close alternative to our current MMRs, the advantages would be:
>
> * A very succinct membership proof (Merkle proof equivalent).
> * A root that's easy and efficient to compute.
> * Intermediate summing (equivalent to pruning a MMR).
>
> I'd be happy to see someone come up with a reason why this wouldn't work (or why it would).
>
> - Igno