How to do Proof of Micro-Burn?

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 is 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 scalability 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 with 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-commitments 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 the 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 cheap to verify. Is something like this possible?

Kind Regards,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).

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 =
P + hash(Q||mast)*G, you'd commit the root in P such that P = 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#spacechains

On Sun, Jul 17, 2022 at 9:41 PM Велеслав 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 is
> 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 scalability
> 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 with
> 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-commitments
> 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 the
> 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 cheap
> 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
>

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

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
>

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

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
>

On Wed, Jul 20, 2022 at 12:23:40AM +0200, Ruben Somsen via bitcoin-dev wrote:

> 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

From a practical point of view, note that the merkle-sum-tree is only useful in cases where you're burning significantly less than a transaction fee. For the forseeable future, that's <~$50, probably less.

Trusting a well-known third-party with $50 really isn't a big problem. So I think adding more clever cryptography to avoid trusting the third party to complete the burn isn't really necessary.