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"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] How to do Proof of Micro-Burn?
Precedence: list

--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--