Timelocked Proof of Work via signature length

sig_pow.md

The following script allows everyone to spend; the shorter your signature the earlier you can spend.

OP_SIZE
OP_CHECKSEQUENCEVERIFY OP_DROP

OP_CHECKSIGVERIFY

The point R = 1/2 G has the smallest known x coordinate -- x = 0x3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63. If the public key is chosen P = 1 G then the ECDSA signature becomes s=2(H(m)+x). So, the smaller H(m) the smaller s (as long as it is bigger than x ~ 2^165). Thus, the above output is spendable by the miner mining the lowest TX hash.

This blog post calculates the exact probability distribution for bitcoin ecdsa signature lengths (disclaimer: calculations not verified, but they seem reasonable). Such a probability distribution could be used as a means to calibrate for a targeted minimum amount of work.

If Alice creates an output like what is contemplated here, she can set the work target.

An interesting idea is that Alice could actually timelock the output in a variable manner by making the timelock a function of the signature length of the spending transaction. Longer signature length implies less work, which could be counter-balanced with a longer timelock.

As a step towards understanding this in a more concrete fashion, I think the originally proposed script of

OP_SIZE
OP_CHECKSEQUENCEVERIFY OP_DROP
OP_CHECKSIGVERIFY

is going to always put the relative locktime somewhere between 60-73 blocks because a "typical" ecdsa signature in bitcoin will be 71-73 bytes in length, and an extremely non-typical one (which consequently took a lot of work) might be down in the ~65 byte length.

So, as it is currently written, Alice would fund an output, and if, after 73 blocks, nobody has claimed it, then somebody (which could be Alice herself) could claim it with nearly zero work. Any signature will pass the CSV test after that point.

Of course, irrespective of any timelock, it is easy to enforce a minimum amount of work. For example, I think the following would unlock for any valid signature smaller than 67 bytes in length.

OP_SIZE 67 OP_LESSTHAN OP_DROP
OP_CHECKSIGVERIFY

OP_CSV allows for a maximum relative time lock of 65535 blocks[1] which is approximately 455 days. Doing some arithmetic on the return value of OP_SIZE, such as adding a constant, might have the effect of moving the earliest outcome of the "sig-pow mining" contest into the future. Something like this:

OP_SIZE
65462 OP_ADD        //note: 65462 = 65535 - 73 
OP_CHECKSEQUENCEVERIFY OP_DROP
OP_CHECKSIGVERIFY

This might be good because then there is more time for participants to join the sig-mining race. There are probably better ways to do this too, with more complicated arithmetic, stack juggling, and hence a larger transaction.

Some other scattered thoughts:

• A sig-pow miner, similar to a mainchain miner, naturally wants to maximize the likelihood of earning the reward while minimizing its costs (in work). Say a sig-pow miner has created a valid signature of sufficient shortness, but that the transaction is still timelocked in the sense that it cannot yet be broadcast nor mined in the mainchain yet, then the sig-pow miner might stop sig-mining and instead promise mainchain miners a larger fee in exchange for not including a competitors transaction, despite the competitors transaction having more sig-work. Naturally, the competitor can do the same, so mainchain miners, rationally, should just choose the one which pays the highest fee. Maybe this is not a problem, but it does seem to indicate that the transaction with the most work may not always "win," since mainchain miners can still essentially censor.

• It is interesting to consider the sig-pow miner to mainchain miner economic transaction when/if a sig-pow miner offers a larger fee to mainchain miners instead of doing more sig-mining work in an effort to secure an earlier unlock time.

[1] according to this wiki https://en.bitcoin.it/wiki/Timelock

Not very far along yet, but I started working on a (very naive) proof of concept.