Subject: Re: [bitcoin-dev] How to do Proof of Micro-Burn?

From: Ruben Somsen <[email-masked]>
Date: Tue, 19 Jul 2022 00:32:37 +0200

Good evening ZmnSCPxj,

Interesting attempt.

 >a * G + b * G + k * G

Unfortunately I don't think this qualifies as a commitment, since one could
trivially open the "commitment" to some uncommitted value x (e.g. a is set
to x and b is set to a+b-x). Perhaps you were thinking of Pedersen
commitments (a * G + b * H + k * J)?

Even if we fixed the above with some clever cryptography, the crucial
merkle sum tree property is missing, so "double spending" a burn becomes
possible. You also still run into the same atomicity issue, except the risk
is moved to the seller side, as the buyer could refuse to finalize the
purchase after the on-chain commitment was made by the seller. Arguably
this is worse, since generally only the seller has a reputation to lose,
not the buyer.

Cheers,
Ruben

On Mon, Jul 18, 2022 at 12:34 AM ZmnSCPxj <[email-masked]> wrote:

> Good morning Ruben and Veleslav,
>
> > Hi Veleslav,
> >
> > This is something I've been interested in.
> >
> >
> > What you need is a basic merkle sum tree (not sparse), so if e.g. you
> want to burn 10, 20, 30 and 40 sats for separate use cases, in a single tx
> you can burn 100 sats and commit to a tree with four leaves, and the merkle
> proof contains the values. E.g. the rightmost leaf is 40 and has 30 as its
> neighbor, and moves up to a node of 70 which has 30 (=10+20) as its
> neighbor, totalling 100.
> >
> >
> > The leaf hash needs to commit to the intent/recipient of the burn, so
> that way you can't "double spend" the burn by reusing it for more than one
> purpose.
> >
> >
> > You could outsource the burn to an aggregating third party by paying
> them e.g. over LN but it won't be atomic, so they could walk away with your
> payment without actually following through with the burn (but presumably
> take a reputational hit).
>
> If LN switches to PTLCs (payment points/scalars), it may be possible to
> ensure that you only pay if they release an opening of the commitment.
>
> WARNING: THIS IS ROLL-YOUR-OWN-CRYPTO.
>
> Rather than commit using a Merkle tree, you can do a trick similar to what
> I came up with in `OP_EVICT`.
>
> Suppose there are two customers who want to commit scalars `a` and `b`,
> and the aggregating third party has a private key `k`.
> The sum commitment is then:
>
>    a * G + b * G + k * G
>
> The opening to show that this commits to `a` is then:
>
>    a, b * G + k * G, sign(b + k, a)
>
> ...where `sign(k, m)` means sign message `m` with the private key `k`.
> Similarly the opening for `b` is:
>
>    b, a * G + k *G, sign(a + k, b)
>
> The ritual to purchase a proof goes this way:
>
> * Customer provides the scalar they want committed.
> * Aggregator service aggregates the scalars to get `a + b + ....` and adds
> their private key `k`.
> * Aggregator service reveals `(a + b + ... + k) * G` to customer.
> * Aggregator creates an onchain proof-of-burn to `(a + b + ... + k) * G`.
> * Everyone waits until the onchain proof-of-burn is confirmed deeply
> enough.
> * Aggregator creates the signatures for each opening for `a`, `b`,.... of
> the commitment.
> * Aggregator provides the corresponding `R` of each signature to each
> customer.
> * Customer computes `S = s * G` for their own signature that opens the
> commitment.
> * Customer offers a PTLC (i.e. pay for signature scheme) that pays in
> exchange for `s`.
> * Aggregator claims the PTLC, revealing the `s` for the signature.
> * Customer now has an opening of the commitment that is for their specific
> scalar.
>
> WARNING: I am not a cryptographer, I only portray one on bitcoin-dev.
> There may be cryptographic failures in the above scheme.
>
> Regards,
> ZmnSCPxj
>