10

Do the current Bitcoin opcodes and transaction size limit allow constructing a UTXO which is only spendable if a specified amount of work has been performed?

So the spender, would provide a nonce as input to the script. Then the script would essentially perform a highly simplified version of how bitcoin's block headers are verified (the nonce is combined with some other data, hashed, and the hash is compared with a "target.").

Without OP_CAT and with arithmetic limited to 4 byte inputs, do I understand correctly that the above would be impossible? Or is there some workaround?

Improve this question
6
  • 4
    You could add an op return to your tx with the first 200 bits of the private key. A spender would have to grind the last 56 bits until they find the right private key to sign with. Combine with multisig or Schnorr tweak to target a single recipient!
    – pinhead
    Commented Oct 18, 2019 at 3:50
  • @pinhead thanks! That's a clever way to do it. Indeed it would require proof of work to uncover the key. However, in this case everyone would be guaranteed to ultimately end up with essentially the same "nonce" (which is just the full private key), so wouldn't a mainchain miner just be able to steal the reward? Or, put another way, can you clarify what you mean about using, for example, multisig so that it targets a single recipient? Namely whoever put in the work but also in a manner that the original UTXO didn't need to know who the set of potential workers is. Is this making sense?
    – philbw4
    Commented Oct 18, 2019 at 4:03
  • 2
    Hm that's hard. Miners can steal anything that's not signed. My thought was you could send to a 2of2 multisig where one key is a known recipient and the other key must be brute forced (by that recipient) A miner wouldn't be able to steal that.
    – pinhead
    Commented Oct 18, 2019 at 4:07
  • Again, thank you very much for your answer. This is extremely helpful. So the challenge have with that construction (the 2of2 method you proposed) is that I would need to know the key of the recipient ahead of time which is not what I want. Is there a way we can sort of chain a series of these types of transactions together to accomplish that?
    – philbw4
    Commented Oct 18, 2019 at 4:16
  • What is the application of this? I’m curious to know what you’re trying to accomplish
    – chytrik
    Commented Oct 18, 2019 at 22:12

1 Answer 1

Reset to default
1

The answer depends on what you are trying to accomplish with this construction. I have three guesses in this regard:

  • a set of determined recipients can spend if they perform the PoW: you can have a transaction that can be spent if someone provides: a value whose hash is less than a specified amount (that determines difficulty) AND a signature that describes the set of allowed entities (potentially any multisig).
  • anybody that performs the proof of work can spend (AND you can spend without PoW): this is trickier since a simple hash based PoW would not work, a miner can just change the destination address of the spending transaction to one under his control. You need to prove that you know a secret (the result of the PoW) without actually including it in the tx so that miners are not able to take the money without repeating the PoW: this is what digital signatures accomplish. As suggested in the comments you can contsruct a utxo that can be spent by signing with a certain private key known by you alone and that contains part of it under an op_return. So one has to try any private key in the set of the allowed ones until he can produce a valid signature. This does not leak the private key itself so the miner cannot sign the same tx with a different destination address.
  • anybody that performs the proof of work can spend (AND you can NOT spend without PoW): I thought about this a while and I can't find an easy construction for this, it might be hard even with stronger scripting capabilities than bitcoin's. My best guess is that you have a provably random public key (for instance using a VDF on the nonce of the last block) and everybody has to brute-force the private key to spend. I see two major issues: miners can have some advantage in selecting nonces to influence the randomness of the PK and it's hard to tune the difficulty, you need a custom signature scheme that has the security level you want and that's not trivial with bitcoin script.

This is NOT a complete list, it's just the first ideas that came to my mind. Especially the second case, which looks the most likely to me, can be constructed in several different ways: for instance you could also publish the hash of the private key in an op_return (so the private key doesn't have to be included in the transaction) and you would turn it into a hash-based PoW since hashing is a lot faster than signing.

Improve this answer
15
  • thanks for your answer. For the first bullet point, you mention comparing if the hash is less than a certain value. However, the hash is a 256 bit number, yet the numerical comparison operations in bitcoin script are limited to 32 bits. So I am not sure that this option would work at all? Of your scenarios though, the third one is the one I am trying to do -- anybody performs the work AND I cannot spend without also performing work. So far I am stumped on it.
    – philbw4
    Commented Sep 19, 2020 at 2:48
  • I had imagined the desirable case is the third one. Not an easy task at all. You get me unprepared as for the numerical comparison matter, but at the cost of writing an insanely convoluted script I guess you can workaround it. If you have enough of 32 security bits then you can just take the last 4 bytes of the hash and compare them to the target. Otherwise you can take the last two 4 bytes blocks and combine two checks.
    – St3p
    Commented Sep 22, 2020 at 18:01
  • This is an interesting approach (though, as you suggested, it sounds like the script may end up quite bloated/convoluted). However, I think the "take the last 4 bytes of the hash" is where it may break down. Pushing 32 bytes (the hash) on to the stack seems possible. However, pulling 4 bytes off at a time and comparing them seems not possible, unless I am mistaken? Again, thank you for your thoughts on it.
    – philbw4
    Commented Sep 23, 2020 at 22:04
  • I'm definitely no bitcoin script expert, but from a quick look it actually seems not possible, I don't think I can help further. It might become easier with something like scriptless script, but I really know too little about it.
    – St3p
    Commented Oct 2, 2020 at 14:59
  • Yes, with the coming (eventual) upgrades, something like this may be possible it seems. Until then, I am not sure either. Thank you for your thoughts so far on it!
    – philbw4
    Commented Oct 6, 2020 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.