path: root/25/4c123a0c938f7ecae2fbba3e9d4cfc80e33460

Return-Path: <rsomsen@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 26E7FC002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 19 Jul 2022 22:23:55 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id F2BA3418F0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 19 Jul 2022 22:23:54 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org F2BA3418F0
Authentication-Results: smtp4.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=OGgIp6kE
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id or9rYtoZq4ju
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 19 Jul 2022 22:23:53 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 9625B418EE
Received: from mail-oi1-x236.google.com (mail-oi1-x236.google.com
 [IPv6:2607:f8b0:4864:20::236])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 9625B418EE
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 19 Jul 2022 22:23:53 +0000 (UTC)
Received: by mail-oi1-x236.google.com with SMTP id i126so8764863oih.4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 19 Jul 2022 15:23:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=ymthe+IFw8x5AiPJEiKf3DB7hT6oS6Hq5EVWM8Ax4O4=;
 b=OGgIp6kE5DCAt5CDcypkiR5YVP7zlsJxoBR0sLrldleVFRendHDUf3HRX9NrzWIRM2
 emh23PAv4rsr3+42SYcqi4JNa5Gd/eFBUEe9WTB3qLPyhvfXGoS5TFGHroEAljAggMEu
 +VMHYshB57w4eJfN5nVwlTghKNAinhajXsVsSA3p5q8p7TnGkPLwfY5q7+oLM/iH5jXQ
 V8fenDgSCP8akgMxyfzmT/86EICqWyaIjau6z6ecVrfwmqQaEPu6immTWgieJs7AKvOB
 KArLsnL7/dSy4+6MFKAzmlYnO9eHKX3NfdvO9k5P8S1hQBSwWx7aiMufxNB7W62iJE2U
 c29g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=ymthe+IFw8x5AiPJEiKf3DB7hT6oS6Hq5EVWM8Ax4O4=;
 b=crwHnGAv/Q/gdjfUzyRfB5bJX/7uHugugInxRtYGCCWSMJEsxBWdKJsptSnfsd+GwK
 r+O8/ZKNNGIs8+qfPq+HtmvbA/yi7Vr3xYj2cZFjF+s8QZBpXIo340PvRbj36J2p9Oed
 +S7oUKFrBLvmCSPB+ZsXZ29IEWoeKJPrw0gYxWTd2VmAhKv/K/IhMHZ3c1UpSk3umjQc
 LpCqYpJVgC0FsVu8kCSKG0EaiDU1zol7k8pt/dtGKJuAYkWcpty7bczbJSZ/H7FxVsX4
 vfg8uc0FB4XRjjmHDf1aS7IKdyR+0lIpTQmkUY+rhPz7pmJmlpIVcG3mC8pCqy2qFuQb
 7XMA==
X-Gm-Message-State: AJIora9lmZvxNquNi4rbAyHdDUGqnfJVI0djQuyT1DT6flQhHvLjOu6R
 459U/bRCiJounXRca3oNyKCcwZcuHUYBdyVJlnA=
X-Google-Smtp-Source: AGRyM1s6aN1r1SudBS6bkWmY/UuWCQCtMZLRs6mCqhDZ+R2VAy6O8tHoSZmgPnq1mZno3c0DwYOMNaOcz7XuFdsn6Sk=
X-Received: by 2002:a05:6808:300b:b0:337:b697:b077 with SMTP id
 ay11-20020a056808300b00b00337b697b077mr905384oib.126.1658269432493; Tue, 19
 Jul 2022 15:23:52 -0700 (PDT)
MIME-Version: 1.0
References: <OPZNUXvYVkB6kyu7Xvw5-lLIwwwftN_pz0iavHInWvQtQaxIzJhYQrx3dkITo9Yge02emrXY3obveywkH04dyAJdETIeeq9-zcH3DA7OxKs=@protonmail.com>
 <CAPv7TjadLN0X31vdo6ATy_aYepbcykZ8Vp8ghQA9W-GEV4axmg@mail.gmail.com>
 <l8iSmPDtMssCoGR0b4twwHMB551xnJBL1wK1jDZcvA8ipKlnBOdZw8ZFVBc4vZzLUlOC3qKB0aEoF6XT7tyFKr6OPThemVD2SiIliCj3-P8=@protonmail.com>
 <CAPv7TjaFW8oOjrJGjUCkMLy2nfSOkjsR0Dg3Rbzq7__WOVir7Q@mail.gmail.com>
 <2RqMBHD1F81zChgG5I40iCbuAriXQARjeDcMWuFDiPFh3cegBC-GDfsj6rr7pzU2myZLWf65DatR9eHpBSZOmWDP0XHRycg8Y3T-Y85H8vI=@protonmail.com>
In-Reply-To: <2RqMBHD1F81zChgG5I40iCbuAriXQARjeDcMWuFDiPFh3cegBC-GDfsj6rr7pzU2myZLWf65DatR9eHpBSZOmWDP0XHRycg8Y3T-Y85H8vI=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Wed, 20 Jul 2022 00:23:40 +0200
Message-ID: <CAPv7Tja_E5e=3J_XSxchFoFbz0jiXqn5b4FnjBYb8d44QKAB+g@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000773aa105e42ff0af"
X-Mailman-Approved-At: Tue, 19 Jul 2022 22:24:35 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] How to do Proof of Micro-Burn?
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Tue, 19 Jul 2022 22:23:55 -0000

--000000000000773aa105e42ff0af
Content-Type: text/plain; charset="UTF-8"

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 <ZmnSCPxj@protonmail.com> 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
>

--000000000000773aa105e42ff0af
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Good evening ZmnSCPxj,<div><br></div><div>&gt;I suppose th=
at means that the knower of `k` is a trusted party; it is trusted to only i=
ssue commitments and not generate fake ones</div><div><br></div><div>Then y=
ou can reduce the scheme to just committing to K and having that key sign w=
hatever the burn was intended for. I doubt this is useful in practice.</div=
><div><br></div><div>&gt;can you please explain</div><div><br></div><div>Th=
e 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.<br><br><font face=3D"monospace"=
>(1a) =C2=A0100 =C2=A0 =C2=A0 =C2=A0(1b) =C2=A0ABCD =C2=A0 =C2=A0 =C2=A0 (2=
a) =C2=A0100 =C2=A0 =C2=A0 (2b) =C2=A0ABCD<br>=C2=A0 =C2=A0 / =C2=A0 =C2=A0=
\ =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0/ =C2=A0 =C2=A0\ =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0/ =C2=A0 =C2=A0\ =C2=A0 =C2=A0 =C2=A0 =C2=A0 / =C2=A0 =C2=A0\<=
br>=C2=A0 30 =C2=A0 =C2=A0 =C2=A070 =C2=A0 =C2=A0 =C2=A0AB =C2=A0 =C2=A0 =
=C2=A0CD =C2=A0 =C2=A0 =C2=A030 =C2=A0 =C2=A0 =C2=A070 =C2=A0 =C2=A0 AB =C2=
=A0 =C2=A0 =C2=A0CD<br>=C2=A0/ =C2=A0\ =C2=A0 =C2=A0/ =C2=A0\ =C2=A0 =C2=A0=
/ =C2=A0\ =C2=A0 =C2=A0/ =C2=A0\ =C2=A0 =C2=A0/ =C2=A0\ =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 / =C2=A0\<br>10 =C2=A020 =C2=A030 =C2=A040 =C2=A0 A =C2=
=A0B =C2=A0 =C2=A0C =C2=A0D =C2=A0 10 =C2=A020 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0A =C2=A0B</font><br><br>(view as monospace font, e.g. via bitcoin-dev=
 archive)<br><br>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.<br><br=
>When you verify the full merkle sum proof (2a + 2b, combined in a single t=
ree), 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&#39;t match.<br><br>This e=
nsures that you can&#39;t create a valid tree with=C2=A0commitments that ad=
d=C2=A0up to more than the burned amount (essentially a &quot;double spend&=
quot;).<br></div><div><br></div><div>&gt;the buyer has every incentive to a=
ctually pay</div><div><br></div><div>Not if you never had any intention of =
buying it and are just trying to run them out of business.</div><div><br></=
div><div>Hope this helps!</div><div><br></div><div>Cheers,</div><div>Ruben<=
/div><div><br></div><div><br></div></div><br><div class=3D"gmail_quote"><di=
v dir=3D"ltr" class=3D"gmail_attr">On Tue, Jul 19, 2022 at 4:48 PM ZmnSCPxj=
 &lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>=
&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
Good morning Ruben,<br>
<br>
&gt; Good evening ZmnSCPxj,<br>
&gt; Interesting attempt.<br>
&gt;<br>
&gt; &gt;a * G + b * G + k * G<br>
&gt;<br>
&gt; Unfortunately I don&#39;t think this qualifies as a commitment, since =
one could trivially open the &quot;commitment&quot; to some uncommitted val=
ue 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)?<br>
<br>
I believe this is only possible for somebody who knows `k`?<br>
As mentioned, an opening here includes a signature using `b + k` as the pri=
vate key, so the signature can only be generated with knowledge of both `b`=
 and `k`.<br>
<br>
I suppose that means that the knower of `k` is a trusted party; it is trust=
ed to only issue commitments and not generate fake ones.<br>
<br>
&gt; Even if we fixed the above with some clever cryptography, the crucial =
merkle sum tree property is missing, so &quot;double spending&quot; a burn =
becomes possible.<br>
<br>
I do not understand what this property is and how it is relevant, can you p=
lease explain this to a non-mathematician?<br>
<br>
&gt; You also still run into the same atomicity issue, except the risk is m=
oved 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 wor=
se, since generally only the seller has a reputation to lose, not the buyer=
.<br>
<br>
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`.<=
br>
Assuming the opening of the commitment is actually what has value (since th=
e lack of such an opening means the buyer cannot prove the commitment) then=
 the buyer has every incentive to actually pay for the opening.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--000000000000773aa105e42ff0af--