Date: Sun, 17 Jul 2022 22:34:24 +0000
To: Ruben Somsen <rsomsen@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <l8iSmPDtMssCoGR0b4twwHMB551xnJBL1wK1jDZcvA8ipKlnBOdZw8ZFVBc4vZzLUlOC3qKB0aEoF6XT7tyFKr6OPThemVD2SiIliCj3-P8=@protonmail.com>
In-Reply-To: <CAPv7TjadLN0X31vdo6ATy_aYepbcykZ8Vp8ghQA9W-GEV4axmg@mail.gmail.com>
References: <OPZNUXvYVkB6kyu7Xvw5-lLIwwwftN_pz0iavHInWvQtQaxIzJhYQrx3dkITo9Yge02emrXY3obveywkH04dyAJdETIeeq9-zcH3DA7OxKs=@protonmail.com>
 <CAPv7TjadLN0X31vdo6ATy_aYepbcykZ8Vp8ghQA9W-GEV4axmg@mail.gmail.com>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] How to do Proof of Micro-Burn?
Precedence: list

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 wan=
t 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 pr=
oof contains the values. E.g. the rightmost leaf is 40 and has 30 as its ne=
ighbor, and moves up to a node of 70 which has 30 (=3D10+20) as its neighbo=
r, totalling 100.
>
>
> The leaf hash needs to commit to the intent/recipient of the burn, so tha=
t way you can't "double spend" the burn by reusing it for more than one pur=
pose.
>
>
> 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 pay=
ment 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 ens=
ure 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 t=
he commitment.
* Aggregator provides the corresponding `R` of each signature to each custo=
mer.
* Customer computes `S =3D s * G` for their own signature that opens the co=
mmitment.
* Customer offers a PTLC (i.e. pay for signature scheme) that pays in excha=
nge 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