Proof of Burn Smart Contract

Hi I have a question about the paper and please correct me if I’m wrong. It look like the proof of unspendability, that is no tag can be derived that hashes to the perturbed hash is based in lemma 1, is not fully deterministic. This said something like, given such a perturbation the probability of finding such a corresponding tag is negligible. But I consider this not a closed proof, it is just a hard to calculate problem. Especially since the above always fails contract does ensure with certainty that it is unspendable. I must add to this that the given proof in the paper is blockchain agnostig, in that it assumes only some basic properties a chain which does not include, this such that a proper theory base is build for a bridge between networks.

1 Like

I don’t fully understand the paper yet, but I agree with your characterization of its non-determinism. Is it most accurate to say that the probability of spending from the address (i.e., finding a signing key) is vanishingly small? Is this more vanishingly small than guessing the signing key for the address corresponding to a regular Cardano key pair? Do there exist Cardano addresses that provably (in a deterministic sense) do not correspond to key pairs? In general, I suspect that many proofs involving hashing will be probabilistic and not closed.

In the practical Cardano context, it is interesting to contrast this with “always fails”: To prove that “always fails” does indeed always fail, would you have to prove the correctness of the Plutus implementation in cardano-node? To prove “proof of burn”, would you have to prove the correctness of transaction witnessing (i.e., the cryptographic primitives) in cardano-node? I’m not sure which is harder to prove, or indeed which have been proved already.

1 Like

I think so. I read some more on this topic online and I think that in the computer science literature is common to prove such properties up to a well defined bound. So nothing is completely secure but the degree of how secure it is can be quantified and be reasoned about. The writers of the paper do this for unspendability in definition 5.

I guess they are somewhat equivalent in the cardano way of creating addresses. What interests me the most about this question is that changing one bit of the hash does not guarantee the existence of a associated signing key (or plutus script). I think I read in a number theory book somewhere that hash function are not surjective. And intuitively that should be the case since otherwise this would impy a bijection (hash function are injective and thus would be bijective). This brings one to a proper proof of such a unspendable addresses. What one would like to show is given a hash algorithm (cardano uses blake2b) which points in the image are certainly not reached by the an hashed string.

I agree. As you say such a proof is only relavent up to the fault tolerance of any attack by an advesary on the network. Transaction can be forged on a blockchain if consensus is compromised, which on cardano can happen up to a well defined degree (IOHK actually quantified this in a paper I think).

I think the proof via the surjective property of such a hash function is the way to go. It is more mathematical and deterministic of nature. Besides even if the implementation of cardano is fully correct, the rigidity it is as good as the network/consensus it is run on.

1 Like

I stand corrected, I just found a source that says that any hash function will have collisions in the output. That is, there are multiple strings that hash to the same output (and thus not injective).

“The ideal situation is that every hashed value generated is really unique for each input value, but this is not possible. In the hash functions the possible hash values to be generated are finite, since they have a fixed output size and because the input size is theoretically infinite, by the Pigeonhole principle, there will be collisions with two distinct entries, resulting in the same hash.” 1

This still does not exclude the possibility of a probable unreachable point in the image.

1 Like

Another interesting question about the correspondence of hashes of scripts and their address is whether or not all possible scripts already exist and are “discovered”. And is it possible to create a self referential plutus script? see the Tupper’s Self-Referential Formula for this one.

1 Like

Thanks, @fermat, for the fascinating and very instructive information!

So it might be the case that the proof-of-burn algorithm, for some hash functions (perhaps like that of Cardano), might generate addresses that are not in the image of the hash function? and that a deterministic proof (based on the properties of the particular hash function) of that might be possible?

1 Like

Yes :grinning:, I fleetingly thought it would be cool to include the address of the tag in the tag itself (i.e., “This proof-of-burn tag has the address addr1vyxdw4rlu6krp9fwgwcnld6y84wdahg585vrdy67n5urp9qlryntm.”), but of course this is as difficult as finding a hash collision.

1 Like

To clear up the used hash functions in cardano. I found the following in the appendix of the Shelley ledger specification.

The hashing algorithm for all verification keys and multi-signature scripts is BLAKE2b-224. Ex-
plicitly, this is the payment and stake credentials (Figure 5), the genesis keys and their delegates
(Figure 11), stake pool verification keys (Figure 21), and VRF verification keys (Figure 20).
Everywhere else we use BLAKE2b-256. In the CDDL specification in Appendix D, hash28
refers to BLAKE2b-224 and and hash32 refers to BLAKE2b-256. 1

I tried looking up the haskell code in the Cardano.Api.Hash module but I got no usefull information about it.

Here are the relevant parts of the Cardano codebase:

1 Like

Thank you, I still have not installed Hoogle. I found another interesting question. As computers get better the rate at which one can hash increases, how resilient is the cardano chain in the future against this inevitable process? In the past other hash functions failed as well (like the MD5 hash function which is now considered easily cracked). Now the chain could be upgraded to include newer hash functions but still this especially poses a problem for any chain since addresses and such are immutable by nature. So it may be that in the future the blake2 hash function becomes crack-able due to increased computing power, which will result in a lot of old addresses beeing cracked, even after a hard fork that allows newer methods.

1 Like

I think this is a computer generated spam bot right? Makes no sense at all. Don’t trust the link.

I would love to hear if somebody already has done it already.

Yes, multiple people did create a burn address. See the above discussion for references of these.

I wanted to add another burn address that just came to mind and is really easy. One can create a V2 timelocking multi-sig script that is only permitted to transact before a slot and after a slot that don’t causally intersect (that is, their intersection is the empty set). So for example, given my favorite twin primes 29 and 31 define

{
  "type": "all",
  "scripts":
  [
    {
      "type": "after",
      "slot": 31
    },
    {
      "slot": 29,
      "type": "before"
    }
  ]
}

Which hashes to the address

addr1w8g3nhjk8pn6k5pj6gxc63ny4ch0stw4t39fe3rc7tj26msk9s4lp

And just to be really sure we can go one step further! One can also construct a multi-sig address that needs signing by all of the above mentioned addresses/scripts :slight_smile: I leave that as an exercise for the reader.

1 Like

Aside from the proof being different for burn-via-script vs burn-via-address, a big difference between the techniques is the proof is public on the blockchain for burn-via-script, but private for burn-via-address. I.e., the burning can be kept secret for burn-via-address. Thus, each technique supports some different use cases.

1 Like

Good addition, i agree. If you want a “private” provable burn address one could always do something like this

{
  "type": "all",
  "scripts":
  [
    {
      "type": "after",
      "slot": 31
    },
    {
      "slot": 29,
      "type": "before"
    },
    {
      "type": "sig"
      "KeyHash": Some PubKey for entropy to generate unique address.
    }
  ]
}

But I think you mean something else with the word private. Since all scripts are used as witnesses they are publicly available one the blockchain, thus its is deducible exactly which address is acts as a burn address. While the perturbation of a hash does not raise this property.

1 Like

IAGON has already completed this proof of burn challenge in early October. Still haven´t gotten the lobster NFT that was promised :smiley:

Although we know that ADA is not meant to be burned, we took on this fun challenge.

Article here
Github here

1 Like

Hello and welcome @brownruffryder,

Nice contract but I disagree that IAGON completed the challenge first and thus should not receive any price (@bwbush implemented the ideas in the paper first). The paper explicitly speaks of the perturbation of a Public Key to lock funds (not a smart contract). I like what IAGON made, a smart contract that can lock funds for any period of time. Even indefinitely, which results in effectively “burning” these funds. As shown in the post above there are multiple ways of burning and proving this. I think the value of the IAGON smart contract lies within the proving funds are burned/locked. Is there an website which catalogs the current state of the contract? That would give anyone the opportunity to check whether funds are really locked or burned (not just the techies that can roam the blockchain from the terminal).

But again, kudo’s to IAGON for a neat smart contract and a nice repo that encompasses all things to work with the contract.

Appreciate the feedback. Although I disagree in regards tot who is first to complete it. Theoretical is just theoretical until proven otherwise in practice. Even though we wrote everything on paper beforehand, we think it is important to showcase this is practical sense (coded/repo) in a smart and organised manner.

I hope people find it useful :slight_smile:

1 Like

If you absolutely want to burn your assets you can simply send ada to an address for which you have no private key. Gone for ever!