path: root/d9/bd5ad9b320eb8b6fe26f4ca6978b9f5b49eb8f

Return-Path: <rsomsen@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 9C690C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 17 Jul 2022 20:40:47 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 5E855605EA
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 17 Jul 2022 20:40:47 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 5E855605EA
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20210112 header.b=XJOd3sHd
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 smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id lzI_sSHGdMAC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 17 Jul 2022 20:40:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 0619C605E8
Received: from mail-oa1-x31.google.com (mail-oa1-x31.google.com
 [IPv6:2001:4860:4864:20::31])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 0619C605E8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 17 Jul 2022 20:40:45 +0000 (UTC)
Received: by mail-oa1-x31.google.com with SMTP id
 586e51a60fabf-f2a4c51c45so19350627fac.9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sun, 17 Jul 2022 13:40:45 -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;
 bh=aD10yuiHRivGDiw8TXKAjRNQ/w3TqgRy7rrk4qPtFMs=;
 b=XJOd3sHd3layWLbbLQi7pTFzhdHmHCt6tOFcDF21phoOlKmwlcdR8TqYQ9X0bLgB90
 wTq6F5WGM+ZGsOV/72b7Z9Mxkdi3MXOPWIFFQNfmXAPuKz1dMeLkX3h2Bt5pd2+MjIDq
 lVjVwxZ8x4dMMJJTXahTyKv1MfKaNs+FFvFq7V7qcUuzUmmHV2UQlVQ/mdh6/NeAm3hw
 /a8QlJD7BwEb8q1jghe8b/p5aV8ROIH+cXmoEFi1hajx9y/EXbRAeIcl0eOJRqfscFLl
 gJZNzlCBQdpfXgs0x0cumRSj0+bwz6KLuS0kWO48wSamQ3VyrxTq779dIbbBhMIP/qWa
 UgIQ==
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;
 bh=aD10yuiHRivGDiw8TXKAjRNQ/w3TqgRy7rrk4qPtFMs=;
 b=JUZ3LyG8a+6cxx8fBLU9RcuBJ9jb0EI8h2w4KwyyMEDwoyj1UupdodE2WmoRqkid0h
 3rZkdjoPvCf/6LEQvPtJSTozZ+dEDTYf7VcI0hU3ocREWaaeks/YeFZ9GbDOg/lIQpuf
 5YP5X4lGaFFx4Sl4iSGRICU/hcDnjxdz2urLr0jDH5/KYHFlRRewUhfSBhcnXx4eVNe+
 jDN9pfSrRwasfiQSiX8x6Jd67nmu2Yb/5INuB2tgbZsf8dpyXd2Z/c8eVj32rJz3NXxB
 XvhkuUbfCCbdC/iFKcrd7QJA6daL+Grc1qFYj1M+1Sjy+wa8UP6hG3kO9HKqVI0wpr9B
 yjtA==
X-Gm-Message-State: AJIora+Bv6eTlGyXUD7v299fTzTqpWDCZK6fXpjiVYFynOJGcdP0II3V
 evrod9zEQefQTZMUtFJDb0xZ1KKOl6bXL1Mi3/U=
X-Google-Smtp-Source: AGRyM1svb89XxLup6MoBtLeJRevgP0eIHHYFNuHNjBVkfz9ydTmraCfXgmSfltjEdn2yxQvb2yPLYSfwUFgfM721l6Y=
X-Received: by 2002:a05:6870:5b91:b0:108:374a:96b0 with SMTP id
 em17-20020a0568705b9100b00108374a96b0mr13264161oab.126.1658090444779; Sun, 17
 Jul 2022 13:40:44 -0700 (PDT)
MIME-Version: 1.0
References: <OPZNUXvYVkB6kyu7Xvw5-lLIwwwftN_pz0iavHInWvQtQaxIzJhYQrx3dkITo9Yge02emrXY3obveywkH04dyAJdETIeeq9-zcH3DA7OxKs=@protonmail.com>
In-Reply-To: <OPZNUXvYVkB6kyu7Xvw5-lLIwwwftN_pz0iavHInWvQtQaxIzJhYQrx3dkITo9Yge02emrXY3obveywkH04dyAJdETIeeq9-zcH3DA7OxKs=@protonmail.com>
From: Ruben Somsen <rsomsen@gmail.com>
Date: Sun, 17 Jul 2022 22:40:33 +0200
Message-ID: <CAPv7TjadLN0X31vdo6ATy_aYepbcykZ8Vp8ghQA9W-GEV4axmg@mail.gmail.com>
To: =?UTF-8?B?0JLQtdC70LXRgdC70LDQsg==?= <veleslav.bips@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000f7745e05e40643cb"
X-Mailman-Approved-At: Sun, 17 Jul 2022 20:41:08 +0000
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: Sun, 17 Jul 2022 20:40:47 -0000

--000000000000f7745e05e40643cb
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 (=3D10+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).

As I believe you already realized, while an op_return is needed (or rather,
preferred) to burn, you don't necessarily have to put the hash there and
can thus save some bytes. One possible place to commit the root hash is in
a double taproot commitment in the change output. So while taproot is Q =3D
P + hash(Q||mast)*G, you'd commit the root in P such that P =3D N +
hash(N||burn_tree_root)*G. What's important is that the location is fully
deterministic, in order to ensure there isn't more than one tree (which
would be yet another way to "double spend").

Finally, you can perform the burn on a spacechain[0] (basically a
"sidechain" that has burned BTC as its native token) in order to pretty
much avoid using mainchain block space altogether, so it should scale much
better. It's worth noting that this fully supports SPV proofs, so the third
party you're proving the burn to doesn't have to run a full node (though
SPV may not be safe enough for big amounts).

To me this seems like a possible way to revitalize the original hashcash
use case, e.g. by only accepting emails which have an SPV proof of some
burned sats attached, or any other place where spam is an issue.

Cheers,
Ruben


[0] Spacechains:
https://gist.github.com/RubenSomsen/c9f0a92493e06b0e29acced61ca9f49a#spacec=
hains



On Sun, Jul 17, 2022 at 9:41 PM =D0=92=D0=B5=D0=BB=D0=B5=D1=81=D0=BB=D0=B0=
=D0=B2 via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hello List,
>
> I have been pondering this problem for some time and have not yet come up
> with an elegant solution, so I am asking here to get more perspective.
>
> There are many usecases for proof of burn. The current working solution i=
s
> to use OP_RETURN with some application specific data.
>
> However, this is limited because block space is finite, and although the
> use of block space itself is an implicit form of burn and can be used in
> the economic calculation of the burn, it is still a fundamental scalabili=
ty
> constraint.
>
> It would be great to have some sort of second layer protocol where
> micro-burns could be instantly exchanged and public proofs generated.
> Something like the Lightning Network, but with public evidence of burns.
>
> I was thinking of pre-committing a larger OP_RETURN burn in the
> blockchain, with an additional output that would include a merkel tree wi=
th
> sparse summation (see Taro), but I haven't found a solution to the
> double-spend problem. I see that the space in this tree can be oversold
> before it is committed to the blockchain.
>
> This makes me wonder if there really is no solution other than to use a
> blockchain. For example, a liquid type sidechain, where the pre-commitmen=
ts
> being burned are a kind of pledge, and the resulting merkel tree is built
> and fixed via a bail-out sidechain mechanism.
>
> Burns can be performed on the side chain at a very high frequency, and th=
e
> side chain can end up fixing these burns back into the main chain within
> some effective merkel tree proof structure.
>
> All in all, I would like some kind of solution that would be similar to
> buying a micro-burn using the Lightning network milisatoshis, and then
> quickly and reliably obtaining a unique and valid burn proof that is chea=
p
> to verify. Is something like this possible?
>
> Kind Regards,
> Veleslav
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr">Hi=C2=A0<span style=3D"font-family:Arial;font-size:14px">V=
eleslav,</span><div><font face=3D"Arial"><span style=3D"font-size:14px"><br=
></span></font></div><div><font face=3D"Arial"><span style=3D"font-size:14p=
x">This is something I&#39;ve been interested in.<br></span></font><div><sp=
an style=3D"font-family:Arial;font-size:14px"><br></span></div><div><font f=
ace=3D"Arial"><span style=3D"font-size:14px">What you need is a basic merkl=
e 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. th=
e rightmost leaf is 40 and has 30 as its neighbor, and moves up to a node o=
f 70 which has 30 (=3D10+20) as its neighbor, totalling 100.</span></font><=
/div><div><font face=3D"Arial"><span style=3D"font-size:14px"><br></span></=
font></div><div><font face=3D"Arial"><span style=3D"font-size:14px">The lea=
f 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 on=
e purpose.</span></font></div><div><font face=3D"Arial"><span style=3D"font=
-size:14px"><br></span></font></div><div><font face=3D"Arial"><span style=
=3D"font-size:14px">You could outsource the burn to an aggregating third pa=
rty by paying them e.g. over LN but it won&#39;t be atomic, so they could w=
alk away with your payment=C2=A0</span></font><span style=3D"font-family:Ar=
ial;font-size:14px">without actually following through</span><span style=3D=
"font-size:14px;font-family:Arial">=C2=A0with the burn (but presumably take=
 a reputational hit).</span></div><div><span style=3D"font-size:14px;font-f=
amily:Arial"><br></span></div><div><font face=3D"Arial"><span style=3D"font=
-size:14px">As I believe you already realized, while an op_return is needed=
 (or rather, preferred) to burn, you don&#39;t necessarily have to put the =
hash there and can thus save some bytes. One possible place to commit the=
=C2=A0root hash is in a double taproot commitment in the change output. So =
while taproot is Q =3D P=C2=A0+ hash(Q||mast)*G, you&#39;d commit the root =
in P such that P =3D N=C2=A0+ hash(N||burn_tree_root)*G. What&#39;s importa=
nt is that the location is fully deterministic, in order to ensure there is=
n&#39;t more than one tree (which would be yet another way to &quot;double =
spend&quot;).</span></font></div><div><span style=3D"font-size:14px;font-fa=
mily:Arial"><br></span></div><div><font face=3D"Arial"><span style=3D"font-=
size:14px">Finally, you can perform the burn on a spacechain[0] (basically =
a &quot;sidechain&quot; that has burned BTC as its native token) in order t=
o pretty much avoid using mainchain block space altogether, so it should sc=
ale much better. It&#39;s worth noting that this fully supports SPV proofs,=
 so the third party you&#39;re proving the burn to doesn&#39;t have to run =
a full node (though SPV may not be safe enough for big amounts).</span></fo=
nt></div><div><font face=3D"Arial"><span style=3D"font-size:14px"><br></spa=
n></font></div><div><font face=3D"Arial"><span style=3D"font-size:14px">To =
me this seems like a possible way to revitalize the original hashcash use c=
ase, e.g. by only accepting emails which have an SPV proof of some burned s=
ats attached, or any other place where spam is an issue.</span></font></div=
><div><font face=3D"Arial"><span style=3D"font-size:14px"><br></span></font=
></div><div><font face=3D"Arial"><span style=3D"font-size:14px">Cheers,</sp=
an></font></div><div><font face=3D"Arial"><span style=3D"font-size:14px">Ru=
ben</span></font></div><div><font face=3D"Arial"><span style=3D"font-size:1=
4px"><br></span></font></div><div><font face=3D"Arial"><span style=3D"font-=
size:14px"><br></span></font></div><div><font face=3D"Arial"><span style=3D=
"font-size:14px">[0] Spacechains:=C2=A0</span></font><a href=3D"https://gis=
t.github.com/RubenSomsen/c9f0a92493e06b0e29acced61ca9f49a#spacechains">http=
s://gist.github.com/RubenSomsen/c9f0a92493e06b0e29acced61ca9f49a#spacechain=
s</a></div><div><font face=3D"Arial"><span style=3D"font-size:14px"><br></s=
pan></font></div><div><font face=3D"Arial"><span style=3D"font-size:14px"><=
br></span></font></div></div></div><br><div class=3D"gmail_quote"><div dir=
=3D"ltr" class=3D"gmail_attr">On Sun, Jul 17, 2022 at 9:41 PM =D0=92=D0=B5=
=D0=BB=D0=B5=D1=81=D0=BB=D0=B0=D0=B2 via bitcoin-dev &lt;<a href=3D"mailto:=
bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.or=
g</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"=
><div style=3D"font-family:Arial;font-size:14px"><span><span>Hello List,</s=
pan></span><div><div><div><div><br></div><div><span></span></div><span>I ha=
ve been pondering this problem for some time and have not yet come up with =
an elegant solution, so I am asking here to get more perspective.</span><di=
v><br></div><div><span>There are many usecases for proof of burn. The curre=
nt working solution is to use OP_RETURN with some application specific data=
.</span></div><div><br></div><div><span>However, this is limited because bl=
ock space is finite, and although the use of block space itself is an impli=
cit form of burn and can be used in the economic calculation of the burn, i=
t is still a fundamental scalability constraint.</span><span><br></span></d=
iv><div><br></div><div><span>It would be great to have some sort of second =
layer protocol where micro-burns could be instantly exchanged and public pr=
oofs generated. Something like the Lightning Network, but with public evide=
nce of burns.</span></div><div><br></div><div><span>I was thinking of pre-c=
ommitting a larger OP_RETURN burn in the blockchain, with an additional out=
put that would include a merkel tree with sparse summation (see Taro), but =
I haven&#39;t found a solution to the double-spend problem. I see that the =
space in this tree can be oversold before it is committed to the blockchain=
.</span></div><div><br></div><div><span>This makes me wonder if there reall=
y is no solution other than to use a blockchain. For example, a liquid type=
 sidechain, where the pre-commitments being burned are a kind of pledge, an=
d the resulting merkel tree is built and fixed via a bail-out sidechain mec=
hanism.</span></div><div><br></div><div><span>Burns can be performed on the=
 side chain at a very high frequency, and the side chain can end up fixing =
these burns back into the main chain within some effective merkel tree proo=
f structure.</span><span><br></span></div><div><br></div><span>All in all, =
I would like some kind of solution that would be similar to buying a micro-=
burn using the Lightning network milisatoshis, and then quickly and reliabl=
y obtaining a unique and valid burn proof that is cheap to verify. Is somet=
hing like this possible?</span><div><span><br></span></div><div><span>Kind =
Regards,</span></div><span>Veleslav</span></div></div></div></div><div>

            </div>

_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000f7745e05e40643cb--