mimblewimble team mailing list archive

[Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx>]

After further thoughts, this clearly doesn't provide that much when all S(x_i) have to be known and starts breaking apart with summing. I clearly have to keep in mind that any idea I haven't slept on isn't worth sending.

My apologies for the noise.

- Igno

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Tuesday, September 18, 2018 3:58 PM, Ignotus Peverell <igno.peverell@xxxxxxxxxxxxxx> wrote:

> 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