path: root/3a/979b0ed5e84e9f7694763baea5689654f60247

Return-Path: <rsomsen@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 3B5AEC002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Jul 2022 22:32:51 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id E46C140528
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Jul 2022 22:32:50 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org E46C140528
Authentication-Results: smtp2.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=SNDjQaK2
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 smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id ufCJxu7HYfac
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Jul 2022 22:32:50 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org D71854014A
Received: from mail-oo1-xc36.google.com (mail-oo1-xc36.google.com
 [IPv6:2607:f8b0:4864:20::c36])
 by smtp2.osuosl.org (Postfix) with ESMTPS id D71854014A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Jul 2022 22:32:49 +0000 (UTC)
Received: by mail-oo1-xc36.google.com with SMTP id
 q207-20020a4a33d8000000b0043572da7bdfso2532511ooq.9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 18 Jul 2022 15:32:49 -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=c0qPpeEzLPkmyiYctx5bzVnuZANujP9XhdvRF/K94Qk=;
 b=SNDjQaK21dxz2rrH5wwVZaipjp3a3XStFL2u4rkN/iw3119mpsCLq/KqO189N5b72t
 CyHbxpph3xzPqRkeZ6fLBF7KShxoZoBhdQ7PiOK9F0FVf3gk0Zr5naFy5Qer5SavibUj
 diXCVhbZzGgzV3ybICPFNECBzEabj3Fn0YHx/I3Q+4EOeIgLYbcbfo4NN/gzg5PLdLPx
 0wV06eD8LZ9K0dYcWDNoq4gcPdLs3tg0GmdGnYSLoUVGvFsYv8WRjD1gmpzN+HmL1iBp
 5KM55W6ZFY4wroJIei2FxhnbSa9jdVgl2DDN4xKEV4OklhO5XEz/AIcp7Abw8vBtuykD
 AKzg==
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=c0qPpeEzLPkmyiYctx5bzVnuZANujP9XhdvRF/K94Qk=;
 b=ZaWPCbY+lgan5i3YAaxAdLe00ZBsxLV4DwHBrYbNJhWM1C/kP16qr2Hh2tg3AKj1to
 PVSSlri8EY4VguoBPIFIkTwvxFS4BzmNH2tpkuXeEJVr1VSEW5fjE7eQpTMFl0huinIg
 RiP7eo0ke4ECD5LeshJ+Hqhk/B01GsHKvltlaatir1vhwIv373B4AfKOafRflKnbETZ+
 uWy+AF6rrCT+0XoZkgjqXtWAoqXqQ8E5td4Av+VIzQKp3REofHOIqOQ/s2RIUWYTfArP
 Qvl5asoN17+0jYusane750DkWd2w1xYg20Pi7NAOAL4YO4cb2KjEW5MWXfsoUs5uXi9e
 tfZg==
X-Gm-Message-State: AJIora9NlfEyNDJ1Kcqx8DoSBYHvVfMuc5x1n7ga0FRG0ryoXMpedi8k
 l/Y/xipjlS9QC2A0ApkY99INAlr8A316nBQbZls=
X-Google-Smtp-Source: AGRyM1uWfdJpWtBdnVVlLpRPvvLvSyRP1t6jBT4d6tjsGFyLEU1Kpa9NyCr+uYX5/kAFInEU2ZO5a+wD64pL4Ri+z5A=
X-Received: by 2002:a05:6820:1786:b0:435:a64e:6749 with SMTP id
 bs6-20020a056820178600b00435a64e6749mr1449983oob.1.1658183568928; Mon, 18 Jul
 2022 15:32:48 -0700 (PDT)
MIME-Version: 1.0
References: <OPZNUXvYVkB6kyu7Xvw5-lLIwwwftN_pz0iavHInWvQtQaxIzJhYQrx3dkITo9Yge02emrXY3obveywkH04dyAJdETIeeq9-zcH3DA7OxKs=@protonmail.com>
 <CAPv7TjadLN0X31vdo6ATy_aYepbcykZ8Vp8ghQA9W-GEV4axmg@mail.gmail.com>
 <l8iSmPDtMssCoGR0b4twwHMB551xnJBL1wK1jDZcvA8ipKlnBOdZw8ZFVBc4vZzLUlOC3qKB0aEoF6XT7tyFKr6OPThemVD2SiIliCj3-P8=@protonmail.com>
In-Reply-To: <l8iSmPDtMssCoGR0b4twwHMB551xnJBL1wK1jDZcvA8ipKlnBOdZw8ZFVBc4vZzLUlOC3qKB0aEoF6XT7tyFKr6OPThemVD2SiIliCj3-P8=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Tue, 19 Jul 2022 00:32:37 +0200
Message-ID: <CAPv7TjaFW8oOjrJGjUCkMLy2nfSOkjsR0Dg3Rbzq7__WOVir7Q@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="00000000000099344d05e41bf283"
X-Mailman-Approved-At: Mon, 18 Jul 2022 22:36:44 +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: Mon, 18 Jul 2022 22:32:51 -0000

--00000000000099344d05e41bf283
Content-Type: text/plain; charset="UTF-8"

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

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

<div dir=3D"ltr">Good evening ZmnSCPxj,<div><br></div><div>Interesting atte=
mpt.<br><div><br></div><div>=C2=A0&gt;a * G + b * G + k * G</div><div><br><=
/div><div>Unfortunately I don&#39;t think this qualifies as a commitment, s=
ince one could trivially open the &quot;commitment&quot; to some uncommitte=
d value x (e.g. a is set to x and b is set to a+b-x). Perhaps you were thin=
king of Pedersen commitments (a * G + b * H + k * J)?</div><div><br></div><=
div>Even if we fixed the above with some clever cryptography, the crucial m=
erkle sum tree property is missing, so &quot;double spending&quot; a burn=
=C2=A0becomes possible. You also still run into the same atomicity issue, e=
xcept the risk is moved to the seller side, as the buyer could refuse to fi=
nalize the purchase after the on-chain commitment was made by the seller. A=
rguably this is worse, since generally only the seller has a reputation to =
lose, not the buyer.</div><div><br></div><div>Cheers,</div><div>Ruben</div>=
</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_=
attr">On Mon, Jul 18, 2022 at 12:34 AM ZmnSCPxj &lt;<a href=3D"mailto:ZmnSC=
Pxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&gt; wrote:<br></div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1p=
x solid rgb(204,204,204);padding-left:1ex">Good morning Ruben and Veleslav,=
<br>
<br>
&gt; Hi Veleslav,<br>
&gt;<br>
&gt; This is something I&#39;ve been interested in.<br>
&gt;<br>
&gt;<br>
&gt; 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 (=3D10+20) as its neig=
hbor, totalling 100.<br>
&gt;<br>
&gt;<br>
&gt; The leaf hash needs to commit to the intent/recipient of the burn, so =
that way you can&#39;t &quot;double spend&quot; the burn by reusing it for =
more than one purpose.<br>
&gt;<br>
&gt;<br>
&gt; You could outsource the burn to an aggregating third party by paying t=
hem e.g. over LN but it won&#39;t be atomic, so they could walk away with y=
our payment without actually following through with the burn (but presumabl=
y take a reputational hit).<br>
<br>
If LN switches to PTLCs (payment points/scalars), it may be possible to ens=
ure that you only pay if they release an opening of the commitment.<br>
<br>
WARNING: THIS IS ROLL-YOUR-OWN-CRYPTO.<br>
<br>
Rather than commit using a Merkle tree, you can do a trick similar to what =
I came up with in `OP_EVICT`.<br>
<br>
Suppose there are two customers who want to commit scalars `a` and `b`, and=
 the aggregating third party has a private key `k`.<br>
The sum commitment is then:<br>
<br>
=C2=A0 =C2=A0a * G + b * G + k * G<br>
<br>
The opening to show that this commits to `a` is then:<br>
<br>
=C2=A0 =C2=A0a, b * G + k * G, sign(b + k, a)<br>
<br>
...where `sign(k, m)` means sign message `m` with the private key `k`.<br>
Similarly the opening for `b` is:<br>
<br>
=C2=A0 =C2=A0b, a * G + k *G, sign(a + k, b)<br>
<br>
The ritual to purchase a proof goes this way:<br>
<br>
* Customer provides the scalar they want committed.<br>
* Aggregator service aggregates the scalars to get `a + b + ....` and adds =
their private key `k`.<br>
* Aggregator service reveals `(a + b + ... + k) * G` to customer.<br>
* Aggregator creates an onchain proof-of-burn to `(a + b + ... + k) * G`.<b=
r>
* Everyone waits until the onchain proof-of-burn is confirmed deeply enough=
.<br>
* Aggregator creates the signatures for each opening for `a`, `b`,.... of t=
he commitment.<br>
* Aggregator provides the corresponding `R` of each signature to each custo=
mer.<br>
* Customer computes `S =3D s * G` for their own signature that opens the co=
mmitment.<br>
* Customer offers a PTLC (i.e. pay for signature scheme) that pays in excha=
nge for `s`.<br>
* Aggregator claims the PTLC, revealing the `s` for the signature.<br>
* Customer now has an opening of the commitment that is for their specific =
scalar.<br>
<br>
WARNING: I am not a cryptographer, I only portray one on bitcoin-dev.<br>
There may be cryptographic failures in the above scheme.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--00000000000099344d05e41bf283--