[Bitcoin-development] RFC: empty scriptPubKeys and OP_RETURN for marking unspendable txouts

[Bitcoin-development] RFC: empty scriptPubKeys and OP_RETURN for marking unspendable txouts

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3936 bytes --]

In my fidelity bond protocol (1) I'm proposing the use of two possible
new features:

The first is the use of OP_RETURN at the end of a scriptPubKey to
designate that the txout can be immediately pruned as it is obviously
unspendable. My use-case is the publish part of the two-step
publish-sacrifice protocol. I specifically want to use OP_RETURN rather
than a spendable scriptPubKey like <serialized tx> <pubkey> OP_CHECKSIG
so that implementors can not get lazy and fail to actually write the
code to spend the non-standard outputs created, thus polluting the UTXO
set. Simply using <serialized tx> by itself as the scriptPubKey -
spendable with an empty scriptSig - is another possiblity, but I suspect
no-one will want to spend the tx fees to clean up those txouts; note how
long it took for someone to bother doing that with p2pools share chain
hash txout, and the effort(2) seems to have been a one-time experiment.
Of course, P2Pool itself could use this mechanism too.

OP_RETURN marks the script as invalid upon execution, and since a script
is invalid if an OP_IF or OP_ELSE is not terminated with OP_ENDIF it is
guaranteed to execute. (there is no op-code that marks a script as valid
and returns immediately) OP_FALSE is another possibility too; I don't
see clear advantages for one or the other modulo OP_FALSE's more
intuitive name.

Finally OP_VERIF and OP_VERNOTIF say that "Transaction is invalid even
when occuring in an unexecuted OP_IF branch" on the wiki, although a
look at EvalScript() leaves me less than convinced this is true.  More
to the point, the mechanism should be something that is as unlikely as
possible to have different behavior in alternate implementations.
(remember that often only valid transactions are put in unittests by
lazy implementors)

OP_RETURN doesn't need any special support in the reference client yet
nor am I suggesting to make it a standard transaction type, but I would
like some feedback on if the idea itself is reasonable.


The second idea is the use of an empty scriptPubKey to create trivially
spendable outputs; provide the the scriptKey OP_TRUE or similar. For
fidelity bonds the advantage is to create a mechanism where even
non-miners have a chance at taking the funds sacrificed, and thus
increase the incentive to scan the blockchain for sacrifices and makes
it more likely for the sacrifice to be a true sacrifice of value. An
additional advantage is you avoid having to provide the txin to prove
the value of the mining fee. The advantage over just using a pubkey with
a known secret key is that the transaction size is shorter; remember
that the sacrifice transaction has to be published as serialized data in
a prior transaction.

In the future another use would be as a way of multiple parties to
collectively sign an assurance contract(3) donating to miners. This is
effectively a mining fee because miners who chose to include the
transaction can always chose to include an additional transfer from the
txout to a scriptPubKey only they can spend.

For the purpose of fidelity bonds ideally an empty scriptPubKey spent by
the scriptSig OP_TRUE would be made a standard transaction type to make
collecting the funds as easy as possible until miners start doing so
themselves. Having it a standard transaction type would also make it
easier for miners to implement the code to do this themselves; in
particular this discourages them from just allowing all non-standard
transactions. The main disadvantage I see is that it makes it easier for
people with buggy custom transaction code to accidentally lose their
funds.

Again, thoughts?


1) https://github.com/petertodd/trustbits/blob/master/fidelitybond.md
2) See the transactions associated with 1HfA1KHC7bT1hnPPCjpj9CB4koLM4Hz8Va
3) https://en.bitcoin.it/wiki/Contracts#Example_3:_Assurance_contracts

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] RFC: empty scriptPubKeys and OP_RETURN for marking unspendable txouts

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]

On Tue, Feb 12, 2013 at 10:11 AM, Peter Todd <pete@petertodd.org> wrote:

> .... Again, thoughts?
>

First: I really like the fidelity bond concept, and want to see it happen.

RE: OP_RETURN : I've got a knee-jerk opposition to the OP_RETURN opcode,
because it was the cause of the nastiest bug ever Bitcoin history. So I'd
be more comfortable using either OP_FALSE or OP_INVALIDOPCODE for the
"provably unspendable" transaction.


RE: anyone-can-spend transactions:  Thinking aloud... I wonder if we might
inadvertently cause "spend storms" on the network; if suddenly there are 11
BTC sitting in an anybody-can-spend txout, I could imagine EVERYBODY on the
network trying to race each other to spend it (maybe assuming that there
are a few miners on old versions of the software who are too dumb to claim
it for themselves).


-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 1242 bytes --]

Re: [Bitcoin-development] RFC: empty scriptPubKeys and OP_RETURN for marking unspendable txouts

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5406 bytes --]

On Tue, Feb 12, 2013 at 12:42:37PM -0500, Gavin Andresen wrote:
> On Tue, Feb 12, 2013 at 10:11 AM, Peter Todd <pete@petertodd.org> wrote:
> 
> > .... Again, thoughts?
> >
> 
> First: I really like the fidelity bond concept, and want to see it happen.
> 
> RE: OP_RETURN : I've got a knee-jerk opposition to the OP_RETURN opcode,
> because it was the cause of the nastiest bug ever Bitcoin history. So I'd

So what exactly was the OP_RETURN bug anyway? I know it has something to
do with not executing the scriptSig and scriptPubKey separately
(https://bitcointalk.org/index.php?topic=58579.msg691432#msg691432) but
commit 7f7f07 that you reference isn't in the tree, nor is 0.3.5 tagged.

> be more comfortable using either OP_FALSE or OP_INVALIDOPCODE for the
> "provably unspendable" transaction.

You know, come to think of it, OP_FALSE doesn't get used by standard
transactions either, and it's behavior is a little odd in how it does
push to the stack. So lets make the standard OP_INVALIDOPCODE,
specifically 0xFF, and put it at the start of the scriptPubKey.

> RE: anyone-can-spend transactions:  Thinking aloud... I wonder if we might
> inadvertently cause "spend storms" on the network; if suddenly there are 11
> BTC sitting in an anybody-can-spend txout, I could imagine EVERYBODY on the
> network trying to race each other to spend it (maybe assuming that there
> are a few miners on old versions of the software who are too dumb to claim
> it for themselves).

That's a good point. It would encourage efforts to identify as many
Bitcoin nodes as possible, particularly miners, and I don't think we
really want to incentivise that. It's not a problem unique to this
proposal - compromised private keys and SIGHASH_NONE (1) - but
fidelity bonds will give people incentive to develop the infrastructure
to exploit it.

    1) Speaking of, maybe I'm missing something, but if I have a
    transaction with one or more txin's and sign every signature with
    SIGHASH_SINGLE, what stops an attacker from adding their own txout
    at the end and diverting the mining fee to themselves?

Having said that, if we both make empty scriptPubKeys standard, and add
code so that miners will always try to spend the outputs for themselves
at the same time, we can get rid of this problem by removing the
incentive. It would also still make non-fidelity-bond uses viable as
well.

Of course, if you want to go down that path, we might as well add code
to detect and spend fidelity bonds too, and make the publish
transactions IsStandard(). Basically for every script in a confirmed
block check if any pushdata op happens to be a script that we would be
willing to add to the mempool at nBlockHeight + N. (assuming current
utxo set) If so, add it to the mempool now. N should be at least 100
blocks I think for the same reason that coinbase tx's take 100 blocks to
spend. The limit also means the size of the mempool can't get larger
than MAX_BLOCK_SIZE * N. Meanwhile IsStandard() would allow the
scriptPubKey OP_INVALIDOPCODE <valid serialized tx>

P2SH already treats data as scripts, so treating data as entire tx's
isn't that big of a leap. Also since the txout is unspendable, the
Satoshi criteria that block-reorgs should not make child tx's vanish is
still met. (though tx mutability sort of breaks this anyway)


We would however open quite a few cans of worms:

1) We just made non-final !IsStandard() for a reason.

2) What if there are transactions already in the mempool that spend the
txin's of the sacrifice? If we ignore them, we've just created another
way to double-spend unconfirmed transactions. On the other hand, if we
don't ignore them, we've just created a way to give us a chance to mine
the sacrifice for ourselves.

Personally I'm with you Gavin and think assuming miners are greedy is
best, but lets just say I probably shouldn't write an implementation
with a function named IsTxOutStealable()?

2a) What if multiple sacrifice publications exist spending the same
txin's? We should have deterministic behavior and mine the most valuable
one. If you don't do that, the attackers effective hashpower is
increased. (and thus the true sacrifice value of the bond decreases)

2b) ...but this is actually an annoying optmization problem. You could
create a whole bunch of sacrifices, each spending two or more inputs,
one small, one large. Then create one large sacrifice, that spends all
the *small* inputs. If the value of the large sacrifice is less than the
combined totals of the smaller sacrifices, you should be mining the
small ones rather than the large for maximum return.

3) With the 10KB limit on scripts, a naive IsStandard() could wind up
recursing about 200 times; we probably should say recursive publish
transactions are non-standard.

3b) ...on the other hand, if they are non-standard, implementations that
use fidelity bonds better make sure they don't accept such monsters.

We probably should just define one standard sacrifice tx form with one
txin, one txout, and a standard P2SH scriptPubKey, but miners can still
do their own thing and cause problems in determining the true value
sacrificed if they don't get the optimization problem right.

Fidelity bonds needs a lot more thought, and a testnet implementation...

-- 
'peter'[:-1]@petertodd.org

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] RFC: empty scriptPubKeys and OP_RETURN for marking unspendable txouts

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1782 bytes --]

> So what exactly was the OP_RETURN bug anyway? I know it has something to
> do with not executing the scriptSig and scriptPubKey separately
> (https://bitcointalk.org/index.php?topic=58579.msg691432#msg691432) but
> commit 7f7f07 that you reference isn't in the tree, nor is 0.3.5 tagged.
>

It was fixed by Satoshi long ago, back when we used CVS I think.

The problem was how scripts were executed. They were concatenated together
and then run as a single unit. The now obsolete OP_CODESEPARATOR was put
between them to control what was hashed and what wasn't.

The obvious problem with that arrangement being that scriptSig ran first
(it has to, to push the signatures onto the stack), so nothing stopped you
setting a scriptSig to OP_RETURN and making the script evaluate to true,
always. A pretty amazing oversight given the thought and care that went
into Bitcoin generally, and its robustness since then.

The fix was to move to the current system whereby the two scripts are
executed independently but sharing a stack, and it's only the return value
of the scriptPubKey that matters.

The scripting system always struck me as a rather late addition to the
design. Satoshi admitted as much when he said that he added it after
encountering an explosion of special cases as he designed various types of
contracts. The fact that there's an obvious bug in CHECKMULTISIG is more
evidence of this part being a general rush job, along with Satoshis
willingness to disable much of its functionality later with the IsStandard
checks. Also the design of CHECKSIG is an obvious retrofit, it would have
made far more sense to decompose it, and we never found a use case for 99%
of the opcodes despite having successfully designed (redesigned?) all the
contract types he ever mentioned.

[-- Attachment #2: Type: text/html, Size: 2585 bytes --]