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

From: Ruben Somsen <[email-masked]>
Date: Wed, 20 Jul 2022 00:23:40 +0200

Good evening ZmnSCPxj,

>I suppose that means that the knower of `k` is a trusted party; it is
trusted to only issue commitments and not generate fake ones

Then you can reduce the scheme to just committing to K and having that key
sign whatever the burn was intended for. I doubt this is useful in practice.

>can you please explain

The goal is to burn multiple amounts (10, 20, 30, 40) in a single OP_RETURN
(100) and specifically indicating how much of the total is intended for
what use case. A merkle sum tree achieves this.

(1a)  100      (1b)  ABCD       (2a)  100     (2b)  ABCD
    /    \          /    \          /    \         /    \
  30      70      AB      CD      30      70     AB      CD
 /  \    /  \    /  \    /  \    /  \           /  \
10  20  30  40   A  B    C  D   10  20          A  B

(view as monospace font, e.g. via bitcoin-dev archive)

So while in a normal merkle tree (1a) you hash e.g. A and B to get AB, with
a sum tree (1b) you also hash 10 and 20 to get 30.

When you verify the full merkle sum proof (2a + 2b, combined in a single
tree), you verify that 10 (A) + 20 (B) add up to 30 (AB), and 30 (AB) + 70
(CD) add up to 100 (ABCD), else the root hash won't match.

This ensures that you can't create a valid tree with commitments that
add up to more than the burned amount (essentially a "double spend").

>the buyer has every incentive to actually pay

Not if you never had any intention of buying it and are just trying to run
them out of business.

Hope this helps!

Cheers,
Ruben

On Tue, Jul 19, 2022 at 4:48 PM ZmnSCPxj <[email-masked]> wrote:

>
> Good morning Ruben,
>
> > 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)?
>
> I believe this is only possible for somebody who knows `k`?
> As mentioned, an opening here includes a signature using `b + k` as the
> private key, so the signature can only be generated with knowledge of both
> `b` and `k`.
>
> I suppose that means that the knower of `k` is a trusted party; it is
> trusted to only issue commitments and not generate fake ones.
>
> > 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.
>
> I do not understand what this property is and how it is relevant, can you
> please explain this to a non-mathematician?
>
> > 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.
>
> A buyer can indeed impose this cost on the seller, though the buyer then
> is unable to get a valid opening of its commitment, as it does not know `k`.
> Assuming the opening of the commitment is actually what has value (since
> the lack of such an opening means the buyer cannot prove the commitment)
> then the buyer has every incentive to actually pay for the opening.
>
> Regards,
> ZmnSCPxj
>