Which clients fully support P2SH and/or multisig ?

[Peter Todd]

How can the counter-party vanishing affect this?  You get the refund (Tx2) signed by the payee before you (payor) sign the funding transaction (Tx1).   That essentially makes the whole operation atomic:  either all parties get their money into an escrow that automatically returns to the payor if one of the parties disappears... or nothing happens.

It's not possible to sign tx2 until tx1 is fully signed; tx2 refers to tx1 by it's hash, which includes the signatures. (the original micropayments channel writeup on the wiki had this mistake too)

[Peter Todd]

I was browsing the forums while ignoring a boring presentation.  I didn't read the whole exchange in detail, just enough to confirm my guess at the function of the script presented.

As you may have noticed from my post, I'm not as willing to handwave over adding state to transactions.  I follow the argument about checking history as well as confirmations.  I think that it might be too complicated to make reasonably accurate estimates of security once branching is added.

When you say "state" what exactly are you referring too?

[jl2012]

How can the counter-party vanishing affect this?  You get the refund (Tx2) signed by the payee before you (payor) sign the funding transaction (Tx1).   That essentially makes the whole operation atomic:  either all parties get their money into an escrow that automatically returns to the payor if one of the parties disappears... or nothing happens.

It's not possible to sign tx2 until tx1 is fully signed; tx2 refers to tx1 by it's hash, which includes the signatures. (the original micropayments channel writeup on the wiki had this mistake too)

The merchant doesn't need to see the full tx1 before he signs tx2. He just needs the hash of tx1 and the corresponding output index. If the merchant uses a brand new private key, he can blindly sign the tx2:

1. Merchant sends a new public key (Pu-M) to user

2. User creates a transaction (tx1) to send bitcoin to 2-of-2 multisig of Pu-M and Public key of user (Pu-U). DO NOT BROADCAST

3. User creates a timelock transaction (tx2) to send the multisig output of tx1 back to himself; sign it; pass it to merchant

4. Merchant signs tx2 WITHOUT KNOWING tx1

5. User sees the fully signed tx2. Broadcast tx1

6. Merchant acknowledge the tx1 after several confirmations

[etotheipi]

How can the counter-party vanishing affect this?  You get the refund (Tx2) signed by the payee before you (payor) sign the funding transaction (Tx1).   That essentially makes the whole operation atomic:  either all parties get their money into an escrow that automatically returns to the payor if one of the parties disappears... or nothing happens.

It's not possible to sign tx2 until tx1 is fully signed; tx2 refers to tx1 by it's hash, which includes the signatures. (the original micropayments channel writeup on the wiki had this mistake too)

The merchant doesn't need to see the full tx1 before he signs tx2. He just needs the hash of tx1 and the corresponding output index. If the merchant uses a brand new private key, he can blindly sign the tx2.

Yeah that's what I actually meant.   Tx1 has to be signed, but doesn't have to be broadcast until tx2 is signed.   If Tx2 is never signed, then the signed tx1 is discarded and the channel is effectively canceled.

Though there is a question of whether there is a subtle security issue with someone signing to spend a tx they haven't seen (or know for sure that what they saw corresponds to the hash).

On the other hand, they have to include the prevTxOutScript in the signature which means that the sig is not valid if the payor gives them a fake tx1 hash.   In fact this alone finally makes me realize the value of having to copy the prevTxOutScript into the TxIn before signing

[Mike Hearn]

Yes. We puzzled over that choice for a long time. I wonder if it is deliberate or just fortunate co-incidence. However we keep discovering interesting quirks of the protocol that turn out to be useful much later on, so I suspect deliberate.

It'd be even better if the entire output structure was serialized, as you suggested.

[jl2012]

But anyway, I always love the idea of OP_PUSHBLOCKHEIGHT. This has been discussed many times here. It simplifies the process a lot and could be wrapped as P2SH. User can keep sending bitcoin to the same P2SH address without those timelock txs.

I am just not sure how it could be done as a soft-fork. I think a soft-fork new OP code could only be "nothing or fail". Unless you wrap it as a serialized script and run it with a re-defined OP_NOP, and make it looks like send-to-anyone to old clients, i.e.

Code:

<serialized script> OP_RUN OP_DROP OP_TRUE 

[jl2012]

Though there is a question of whether there is a subtle security issue with someone signing a TX spending a TX they haven't seen (or know for sure that what they saw corresponds to the hash).

On the other hand, they have to include the prevTxOutScript in the signature which means that the sig is not valid if the payor gives them a fake tx1 hash.   In fact this alone finally makes me realize the value of having to copy the prevTxOutScript into the thin before signing

If the key is never used, I can't see any risk with this. The merchant will eventually see tx1. If the merchant is not satisfied with tx1 or tx2, they will not acknowledge tx1 and not use the key again

[etotheipi]

Yes. We puzzled over that choice for a long time. I wonder if it is deliberate or just fortunate co-incidence. However we keep discovering interesting quirks of the protocol that turn out to be useful much later on, so I suspect deliberate.

It'd be even better if the entire output structure was serialized, as you suggested.

Given the complexity around OP_CODESEPARATORs in the OP_CHECKSIG procedure, I would guess that Satoshi had a reason for not just copying the whole TxOut, but instead allowing signatures to only include pieces of the previous-TxOut-script.  My understanding is that no one has yet determined the usefulness of OP_CODESEPARATOR besides possibly being a potential source of protocol bugs/vulnerabilities.  But I would suspect he had a concrete use case for it that we haven't figured out yet.

[Peter Todd]

The merchant doesn't need to see the full tx1 before he signs tx2. He just needs the hash of tx1 and the corresponding output index. If the merchant uses a brand new private key, he can blindly sign the tx2:

1. Merchant sends a new public key (Pu-M) to user

2. User creates a transaction (tx1) to send bitcoin to 2-of-2 multisig of Pu-M and Public key of user (Pu-U). DO NOT BROADCAST

3. User creates a timelock transaction (tx2) to send the multisig output of tx1 back to himself; sign it; pass it to merchant

4. Merchant signs tx2 WITHOUT KNOWING tx1

5. User sees the fully signed tx2. Broadcast tx1

6. Merchant acknowledge the tx1 after several confirmations

Yup, you're absolutely right, which means jspilman's micropayment system is completely secure for both parties once tx1 confirms, and until then simply has zero-conf security.

It's also still compatible with replace-by-fee scorched-earth: if the user double-spends the unconfirmed tx1 paying into the multisig output, and has signed a non-timelocked tx2, sign tx2 spending the amount that doesn't get refunded back to the user 100% to fees and they'll still pay for whatever they owe. Exactly the same as scorched-earth for a non-micropayment-channel transaction.

Heh, the confusion we've all had in examining this stuff makes me think when it comes to OP_CODESEPARATOR we should always consider the possibility that Satoshi simply made a mistake in the design.

But anyway, I always love the idea of OP_PUSHBLOCKHEIGHT. This has been discussed many times here. It simplifies the process a lot and could be wrapped as P2SH. User can keep sending bitcoin to the same P2SH address without those timelock txs.

I am just not sure how it could be done as a soft-fork. I think a soft-fork new OP code could only be "nothing or fail". Unless you wrap it as a serialized script and run it with a re-defined OP_NOP, and make it looks like send-to-anyone to old clients, i.e.

Code:

<serialized script> OP_RUN OP_DROP OP_TRUE 

Basically the best way to do it is to make script-v2 based on merklized abstract syntax trees and push it all into one opcode:

<MAST-top-level-hash> OP_NOP1/OP_MAST_EVAL

For pre-soft-fork nodes the OP_NOP1 does nothing, and the top-level-hash will make the script evaluate as true. (the hash would never be == 0 for a valid script)

The scriptSig is then the fragments of the abstract syntax tree of the part of the script that is actually executed. For instance, lets say all the script is executed:

scriptPubKey: <hash> OP_MAST_EVAL
scriptSig: <sig> (<pubkey> OP_CHECKSIG)

Basically this looks just like P2SH. But lets suppose a more complex scriptPubKey:

IF <pubkey1> OP_CHECKSIG
ELSE <pubkey2> OP_CHECKSIG
ENDIF

You spend it with either:

scriptSig: <sig1> 1
scriptSig: <sig2> 0

But with MAST you only have to reveal the branch actually being executed, so your scriptSig now looks like this:

<sig1> 1
(IF <pubkey1> OP_CHECKSIG
 ELSE Hash(<pubkey2> OP_CHECKSIG)
 ENDIF)

For two branches, it's not a big savings, but I could have embedded a hundred possible pubkeys into that script with nested if statements, yet to spend the script I only have to provide the data required to execute one short path. I also don't have to reveal any parts of the script that weren't executed if I don't want to.

edit: Credit goes to Russell O’Connor and Pieter Wuille for this idea.

[jl2012]

OP_MAST_EVAL sounds like an extension to BIP17 or BIP12. Isn't it? Very interesting

[Mike Hearn]

The point of OP_CODESEPARATOR is not a mystery. It is dead code left over from a time when Bitcoin did not execute scriptSig+scriptPubKey by running them separately with a shared stack but actually concatenated the programs together. This was a major security hole as you could just set scriptSig to OP_RETURN and make it satisfy any output. It is by far the worst security problem Bitcoin ever had. When he fixed it, Satoshi didn't bother to clean up all the code that supported the old method and thus we are left with OP_CODESEPARATOR. It has no utility today.

(in other words Peter is right - it's leftovers from a design mistake).

[jl2012]

The point of OP_CODESEPARATOR is not a mystery. It is dead code left over from a time when Bitcoin did not execute scriptSig+scriptPubKey by running them separately with a shared stack but actually concatenated the programs together. This was a major security hole as you could just set scriptSig to OP_RETURN and make it satisfy any output. It is by far the worst security problem Bitcoin ever had. When he fixed it, Satoshi didn't bother to clean up all the code that supported the old method and thus we are left with OP_CODESEPARATOR. It has no utility today.

(in other words Peter is right - it's leftovers from a design mistake).

What happened to OP_RETURN? In bitcoin wiki it just says "Marks transaction as invalid." How could it satisfy any output? Has the definition changed?

[jgarzik]

What happened to OP_RETURN? In bitcoin wiki it just says "Marks transaction as invalid." How could it satisfy any output? Has the definition changed?

wiki wording does not precisely match actual function.

[Peter Todd]

What happened to OP_RETURN? In bitcoin wiki it just says "Marks transaction as invalid." How could it satisfy any output? Has the definition changed?

wiki wording does not precisely match actual function.

Heh.

OP_RETURN used to cause script processing to exit immediately, leaving the stack untouched. If the top stack item evaluated true, the script would succeed, false, the script would fail. This was changed in a75560d828464c3f1138f52cf247e956fc8f937d - notice how Satoshi didn't mention the changes at all. That's pretty much the last time the scripting code has seen any major changes FWIW. Also note how at the same time Satoshi also added some other hard-fork changes, like adding a 20KB size limit on scripts. (later reduced to 10KB in 73aa262647ff9948eaf95e83236ec323347e95d0 along with more hard-fork changes, this time with a commit message mentioning security)

Here's another fun one: OP_DOUBLEBYTE_BEGIN. Never implemented, but looks like the idea was to add some two byte opcodes eventually. Also OP_NOTEQUAL, an opcode that was disabled in v0.1

[Peter Todd]

The point of OP_CODESEPARATOR is not a mystery. It is dead code left over from a time when Bitcoin did not execute scriptSig+scriptPubKey by running them separately with a shared stack but actually concatenated the programs together. This was a major security hole as you could just set scriptSig to OP_RETURN and make it satisfy any output. It is by far the worst security problem Bitcoin ever had. When he fixed it, Satoshi didn't bother to clean up all the code that supported the old method and thus we are left with OP_CODESEPARATOR. It has no utility today.

(in other words Peter is right - it's leftovers from a design mistake).

Actually I was thinking that even when Bitcoin worked that way OP_CODESEPARATOR would have served no purpose. However I was thinking about it more, and realized that if you didn't insert OP_CODESEPARATOR between the scriptSig and scriptPubKey before calling EvalScript() you could do some interesting things.

Basically I would be able to write a scriptPubKey like this:

<pubkey1> OP_CHECKSIG OP_VERIFY <pubkey2> OP_CHECKSIG

This is spendable by the following scriptSig:

<sig2> <sig1> OP_CODESEPARATOR

sig1 is a signature made by pubkey1 and what sig1 signs is the transaction; nothing exciting yet. But because the scriptSig and scriptPubkey are combined, and Bitcoin happily executes op's in scriptSigs, pubkey1 can also sign new opcodes that have to be present in the scriptSig for the signature to be valid. For instance pubkey1 could make a signature only spendable if the scriptSig includes this:

<pubkey3> OP_CHECKSIG OP_VERIFY

Essentially pubkey1 has delegated the ability to sign the transaction to pubkey3 after the fact. Now if pubkey2 wants to spend the transaction they create a signature of their own over the transaction including those new opcodes, and create the following scriptSig:

<sig2> <sig1> <sig3> OP_CODESEPARATOR <pubkey3> OP_CHECKSIG OP_VERIFY

sig3, sig1 and then sig2 are all checked, and they are all hash a transaction including the following combined scriptSig+scriptPubkey:

<pubkey3> OP_CHECKSIG OP_VERIFY <pubkey1> OP_CHECKSIG OP_VERIFY <pubkey2> OP_CHECKSIG

These days the scriptSig and scriptPubKey evaluated separately, and critically that means that when the scriptPubKey is evaluated pbegincodehash is set to the beginning of the scriptPubKey - there is no way to have a signature check any part of the scriptSig. Secondly there is no way for the scriptPubKey to determine what is in the scriptSig other than the contents of the data stack - there's no way to access the scripts themselves. Even though opcodes can be executed in the scriptSig there is no way that the scriptPubKey can make sure the right ones are executed.

Interestingly Luke's CHECKHASHVERIFY BIP is really proposing something very similar to what I'm talking about above, except in how it relies on a strict hash verification rather than signatures; Luke's implementation may have even enabled the above, although I can't seem to find the code to check. (it'd be bad if it did though because it's a hard-fork) The right design would probably be something like OP_GETCODE to put the serialized code on the stack, followed by OP_HASH/OP_EQUAL/OP_VERIFY for the P2SH case, and OP_HASH/OP_SIGCHECK/OP_VERIFY. Add in some more opcodes to be able to get the other parts of a transaction, and match that against templates, and you'd have a lot of interesting capabilities.

Really Satoshi's one mistake was allowing OP_RETURN to return true in the scriptSig; if he hadn't put in OP_RETURN, or had the current behavior where OP_RETURN can only make the script fail, we could have kept combined scriptSig and scriptPubKey processing. Worth thinking about for the future if a script v2.0 ever happens.

edit: Note how all of the above works even better if there is some kind of OP_CODESEPARATOR "stack", or if OP_CHECKSIG can accept a number for how many OP_CODESEPARATORS "back" it counts; consider what happens when you try to do the delegation a second time.

[Luke-Jr]

Interestingly Luke's CHECKHASHVERIFY BIP is really proposing something very similar to what I'm talking about above, except in how it relies on a strict hash verification rather than signatures; Luke's implementation may have even enabled the above, although I can't seem to find the code to check. (it'd be bad if it did though because it's a hard-fork) The right design would probably be something like OP_GETCODE to put the serialized code on the stack, followed by OP_HASH/OP_EQUAL/OP_VERIFY for the P2SH case, and OP_HASH/OP_SIGCHECK/OP_VERIFY. Add in some more opcodes to be able to get the other parts of a transaction, and match that against templates, and you'd have a lot of interesting capabilities.

Was proposing. BIP 17 is withdrawn.
For historical review/reference, I've pushed WITHDRAWN_checkhashverify to my gitorious and github repositories.

[jl2012]

The merchant doesn't need to see the full tx1 before he signs tx2. He just needs the hash of tx1 and the corresponding output index. If the merchant uses a brand new private key, he can blindly sign the tx2:

1. Merchant sends a new public key (Pu-M) to user

2. User creates a transaction (tx1) to send bitcoin to 2-of-2 multisig of Pu-M and Public key of user (Pu-U). DO NOT BROADCAST

3. User creates a timelock transaction (tx2) to send the multisig output of tx1 back to himself; sign it; pass it to merchant

4. Merchant signs tx2 WITHOUT KNOWING tx1

5. User sees the fully signed tx2. Broadcast tx1

6. Merchant acknowledge the tx1 after several confirmations

Yup, you're absolutely right, which means jspilman's micropayment system is completely secure for both parties once tx1 confirms, and until then simply has zero-conf security.

It's also still compatible with replace-by-fee scorched-earth: if the user double-spends the unconfirmed tx1 paying into the multisig output, and has signed a non-timelocked tx2, sign tx2 spending the amount that doesn't get refunded back to the user 100% to fees and they'll still pay for whatever they owe. Exactly the same as scorched-earth for a non-micropayment-channel transaction.

Heh, the confusion we've all had in examining this stuff makes me think when it comes to OP_CODESEPARATOR we should always consider the possibility that Satoshi simply made a mistake in the design.

But anyway, I always love the idea of OP_PUSHBLOCKHEIGHT. This has been discussed many times here. It simplifies the process a lot and could be wrapped as P2SH. User can keep sending bitcoin to the same P2SH address without those timelock txs.

I am just not sure how it could be done as a soft-fork. I think a soft-fork new OP code could only be "nothing or fail". Unless you wrap it as a serialized script and run it with a re-defined OP_NOP, and make it looks like send-to-anyone to old clients, i.e.

Code:

<serialized script> OP_RUN OP_DROP OP_TRUE 

Basically the best way to do it is to make script-v2 based on merklized abstract syntax trees and push it all into one opcode:

<MAST-top-level-hash> OP_NOP1/OP_MAST_EVAL

For pre-soft-fork nodes the OP_NOP1 does nothing, and the top-level-hash will make the script evaluate as true. (the hash would never be == 0 for a valid script)

The scriptSig is then the fragments of the abstract syntax tree of the part of the script that is actually executed. For instance, lets say all the script is executed:

scriptPubKey: <hash> OP_MAST_EVAL
scriptSig: <sig> (<pubkey> OP_CHECKSIG)

Basically this looks just like P2SH. But lets suppose a more complex scriptPubKey:

IF <pubkey1> OP_CHECKSIG
ELSE <pubkey2> OP_CHECKSIG
ENDIF

You spend it with either:

scriptSig: <sig1> 1
scriptSig: <sig2> 0

But with MAST you only have to reveal the branch actually being executed, so your scriptSig now looks like this:

<sig1> 1
(IF <pubkey1> OP_CHECKSIG
 ELSE Hash(<pubkey2> OP_CHECKSIG)
 ENDIF)

For two branches, it's not a big savings, but I could have embedded a hundred possible pubkeys into that script with nested if statements, yet to spend the script I only have to provide the data required to execute one short path. I also don't have to reveal any parts of the script that weren't executed if I don't want to.

Can we do this way:

• 1. Redefine OP_NOP1 as OP_MAST_EVAL
• 2. Format of scriptPubKey: <20 bytes script merkle root hash> OP_MAST_EVAL. (Any other data /OP codes in the script are invalid)
• 3. scriptSig: Pushing a single serialized script including all signature(s), hash(es) and script(s). Any other data / OP codes are invalid. This makes sure the script can't be edited after hash check (ref: P2SH)
• 4. There could be many sub-scripts for OP_MAST_EVAL. For example, if we want a 3-of-8 multi-sig. There will be 9 sub-scriptPubKey (sspk), numbered from 1-9.
  
  • The sspk2 to sspk9 are normal pay-to-public key scripts with different public keys:<pubKey-n> OP_CHECKSIG
  • The sspk1 is the main script, which will call the other sspk. To avoid looping (e.g. sspk2 calling sspk3 and sspk3 calling sspk2), only sspk1 may call other sspk.
  • Calling of sspk is done by OP_SSPK. It pops the top stake (the sspk-ID) and runs the sspk. Each sspk has its own sub-stake. No matter what is left in the sub-stake, OP_SSPK will only return either 0 (if the sspk failed) or 1 (if the sspk succeed) as top stake.(*)
  • For a 3-of-8 multi-sig, the sspk1 will be: <2> OP_SSPK <3> OP_SSPK OP_ADD <4> OP_SSPK OP_ADD <5> OP_SSPK OP_ADD <6> OP_SSPK OP_ADD <7> OP_SSPK OP_ADD <8> OP_SSPK OP_ADD <9> OP_SSPK OP_ADD <3> <OP_EQUAL>

• 5. Calculation of script merkle root is same as transaction merkle root, but done by hash160.
• 6. For example, we want use pubKey-2, 4, 5 to redeem the bitcoin. We need to provide these information:
  
  • Total number of sub-scripts (i.e. 9)
  • Full sspk1, sspk2, sspk4, sspk5
  • hash(sspk3), hash(sspk6), hash(sspk9), and hash(hash(sspk7) concat hash (sspk8))
  • sub-scriptSigs (sss) for sspk1, sspk2, sspk4, sspk5 (the sss1 is empty in this example)
  Concatenate all these things in a format without any ambiguity and push as the only item of the main scriptSig
  

• 7. OP_MAST_EVAL will
  
  • a. match the merkle root
  • b. run sss1 (which is empty here) with sspk1 (the whole transaction fails if sspk1 is not provided)
  • c. hit the first OP_SSPK, call sspk2, and run it with sss2, return a 1 when succeed
  • d. hit the second OP_SSPK, try to call sspk3. Since sspk3 is not available, a 0 is returned
  • e. keep running sspk1. The result of sspk1 is the final result

• 8. Failing of a individual sspk will not fail the whole transaction. It just pushes a 0 to the main stake.
• 9. All sspk must be called at least once in sspk1.

(* We may allow it to push the items in sub-stakes back to the main-stake. This allows greater flexibility but makes the system more complicated and may introduced unexpected behavior. I don't think it's necessary)[/list]

[TierNolan]

Basically the best way to do it is to make script-v2 based on merklized abstract syntax trees and push it all into one opcode:

<MAST-top-level-hash> OP_NOP1/OP_MAST_EVAL


For pre-soft-fork nodes the OP_NOP1 does nothing, and the top-level-hash will make the script evaluate as true. (the hash would never be == 0 for a valid script)

Ensuring miner acceptance would be critical .

However, that is true for P2SH anyway.

So, you need to define "holder" opcodes/structures.  Each one needs a full() and hash() method.

The basic one is <sequence>.

Sequence

This is an implied holder.

Full(): concat(OP_A, OP_B, ... OP_Z)
Hash(): Hash(concat(OP_A, OP_B, ... OP_Z))

IF

OP_IF <holder> OP_ENDIF

Full()
if (true):   concat(OP_IF, full(holder), OP_ENDIF)
if (false): concat(OP_IF, hash(holder), OP_ENDIF)

Hash()
hash(concat(OP_IF, hash(holder), OP_ENDIF))

IF-ELSE

OP_IF <holder1> OP_ELSE <holder2> OP_ENDIF

Full()
if (true):   concat(OP_IF, full(holder1), OP_ELSE, hash(holder2), OP_ENDIF)
if (false): concat(OP_IF, hash(holder1), OP_ELSE, full(holder2), OP_ENDIF)

Hash()
hash(concat(OP_IF, hash(holder1), OP_ELSE, hash(holder2), OP_ENDIF))

WHILE

OP_WHILE <holder1> OP_DO <holder2> OP_ENDDO

Full()
if no-loops: concat(OP_WHILE, full(holder1), OP_DO, hash(holder2), OP_ENDDO)
if loops: concat(OP_WHILE, full(holder1), OP_DO, full(holder2), OP_ENDDO)

hash()
hash(concat(OP_WHILE, hash(holder1), OP_DO, hash(holder2), OP_ENDDO))

This one actually is a bit of a problem.  The full(holder2) branch need to include any part of holder 2 that is actually pinged by any of the loops.

With loops, the number of opcodes would be harder to verify.  Loops with a fixed number of iterations could be checked without having to run the entire script.

The really nice feature is that unspent transactions all have a fixed sized scriptPubKey.  You have to actually spend the transaction rather than forcing nodes to include complex scriptPubKeys, since they don't know if they are spendable.

[mmeijeri]

Essentially pubkey1 has delegated the ability to sign the transaction to pubkey3 after the fact.

I'm having trouble understanding this. In what way has pubkey1 done this, and of what use is that? I don't understand why the current design requires the public key script (or a subscript of it) to be signed at all, but I understand from another thread that no one really knows the answer to that.