Proposal to modify OP_CHECKSIG

[casascius]

I would like to make a serious visit to a proposal I made in some other thread a while back, and that's to propose a modification to OP_CHECKSIG.

First, let me describe the very specific benefits that could be gained from implementing the proposal.

• Users could generate a Bitcoin address that, upon receipt of bitcoins, are automatically encumbered by 2 private keys, or a 2-of-3 key strategy - directly lessening people's risk of getting their coins lost or stolen.
• New Bitcoin addresses could be generated securely in halves by two different machines, where neither machine (nor someone who has rooted it) has enough private key material to spend the funds.
• All Bitcoin addresses generated in the above two schemes would be fully backward compatible and well-formed and nobody would need to modify their interactions with bitcoind to accommodate outgoing payments to these addresses

And let me describe how all of these wonderful benefits could be achieved.

• One simple change to the OP_CHECKSIG command.
• Yes, this would require a fork of the block chain, but this doesn't have to be done now, soon, or ever, just for this purpose alone.
• Just put the code in now and leave it disabled thru block 250000 on the production chain until some other external cause forces us to fork the block chain for some other reason.  By then, the current versions will definitely be extinct dinosaurs, and if a block chain fork were ever to happen sooner, the block number could be conveniently moved, just how namecoin's merged mining went from 25000 to 19200 when the occasion presented itself.

And now let me describe what the change is.

• Change the OP_CHECKSIG command, so where it now takes ONE pubkey and ONE signature, it would optionally take a binary-serialized boolean expression of n pubkeys in place of the one pubkey, and n signatures to sign against the pubkeys, some of which may or may not be present in any given transaction.
• Right now, a bitcoin address encodes a hash of a pubkey.  With this addition, a bitcoin address could encode the hash of the entire binary serialized expression.  (The OP_HASH160 would still work exactly as it did before, it would just be hashing more bytes).
• To spend the funds, the spender would need to provide the entire expression in place of the pubkey.  The entire expression would still be a single blob of bytes on the scripting stack just like a pubkey, but would just be a little larger

So here is an example.  The way it works now, I send bitcoins to address X.  My client emits:

Code:

OP_DUP OP_HASH160 hashofpubkeyofX OP_EQUALVERIFY OP_CHECKSIG

And when X goes to spend them, he emits a scriptsig of:

Code:

signatureforX pubkeyofX

With this modification, address X could be based on the hash of a little script that actually contains three pubkeys arranged in the form (A AND B) OR C.  Since a bitcoin address represents a hash, and a hash is taken on a blob of bytes, nothing says that the blob of bytes couldn't be a script rather than a single public key.  A client would still emit the exact same script:

Code:

OP_DUP OP_HASH160 hashofpubkeyofthewholescript OP_EQUALVERIFY OP_CHECKSIG

And if X wanted to spend them, and he has private keys for A and B, he would emit:

Code:

signatureforA+signatureforB+null    script:(pubkeyforA AND pubkeyforB) OR pubkeyforC

The OP_CHECKSIG would pass because the script can be satisfied with just the two of three signatures.

And if X wanted to spend them and he only has has private key for C, he would emit:

Code:

null+null+signatureforC   script:(pubkeyforA AND pubkeyforB) or pubkeyforC

Now, how secure bitcoin address generation would work:

Joe wants a secure bitcoin address, but is rightly afraid of viruses and keyloggers.  He need not fear, since he will use two virus-infested devices to securely generate an address.

He generates one ECDSA keypair on his virus-infested PC with a keylogger and remote viewing trojan monitored by someone in Romania.

He generates a second ECDSA keypair on his Blackberry that has been rooted by his wireless carrier at the behest of his government, via an online website that secretly keeps a copy of all the private keys it produces.

He writes down both private keys.

With either of these computers, he creates a single Bitcoin address by hashing his two public keys together.  Unless he uses two machines both pwned by the same attacker, or the two attackers have some way to find one another and do a "show you mine if you show me yours", he is pretty much safe from attacks because neither of his adversaries knows the other private key and both are needed to spend the funds.  Heaven forbid he generate one of these keys using a device that has no internet connection, and there's no way he'll be able to get his bitcoins stolen.

[1714797578]

1714797578

[1714797578]

1714797578

[1714797578]

1714797578

[1714797578]

1714797578

[casascius]

And here is how such simple binary scripting could be implemented.

It doesn't have to have the full faith and force of the existing scripting engine.  A very simplified boolean-only one would work, and could be implemented in a little loop and a switch statement.

I note that all pubkeys used in Bitcoin currently start with 0x04.  The 0x04 could be repurposed in OP_CHECKSIG to mean "the next 64 bytes are a pubkey", so that all existing signatures would be well-formed checksig scripts.

And then bytes other than 0x04 could represent a very small subset of boolean operations with a boolean stack:  for example:

0x00 = PUSHfalse
0x01 = PUSHtrue
0x02 = DUP top element
0x03 = XOR
0x04 = pubkey, evaluate it and push true if signature good, false if not
0x05 = AND
0x06 = OR
0x07 = XOR
0x08 = AND3 (pops 3 elements, pushes true if all 3 elements must be true)
0x09 = AND23 (pops 3 elements, pushes true if at least 2 are true)

So (A AND B) OR C would just be represented in bytes as:

04 <pubkeyA> 04 <pubkeyB> 05 04 <pubkeyC> 06

[Luke-Jr]

This would fork the blockchain. More useful changes have been kept-out-until-later for that reason.

[Pieter Wuille]

There's a large discussion around implementing boolean expressions over signature-verifications on github and the mailinglist already, and those work with the existing script languages without modifications. Does your proposal do anything beyond that?

See https://github.com/bitcoin/bitcoin/pull/319

[theymos]

I like the idea.

Instead of reusing OP_CHECKSIG, I think it would be better to use OP_CHECKMULTISIG. OP_CHECKMULTISIG is defective and needs to be changed, anyway. OP_CHECKSIG can remain in use for "normal" transactions, which will keep sizes down. Using a different address version for these scripts will not be much of a burden on senders.

It should not be possible to use a mini-script that contains no public keys, as allowing this would make brute-forcing much easier. Instead of brute-forcing a key-creation operation and some hashing, the attacker would only have to do hashing.

Just put the code in now and leave it disabled thru block 250000 on the production chain until some other external cause forces us to fork the block chain for some other reason.  By then, the current versions will definitely be extinct dinosaurs, and if a block chain fork were ever to happen sooner, the block number could be conveniently moved, just how namecoin's merged mining went from 25000 to 19200 when the occasion presented itself.

Setting some fixed upgrade point and then not following through would be terrible because you'd still have some part of the network using the planned rules.

[casascius]

There's a large discussion around implementing boolean expressions over signature-verifications on github and the mailinglist already, and those work with the existing script languages without modifications. Does your proposal do anything beyond that?

See https://github.com/bitcoin/bitcoin/pull/319

Yes, that's useful, and my proposal does something different that is intrinsically practical.  It allows a normal Bitcoin address to be given out and receive funds, and for those funds to be protected by safer address schemes the moment they are sent, with no burden on the senders.

So I could give out my Bitcoin address like usual, but that Bitcoin address could require more than 1 key to spend my funds. That would enable, for example, a future client that safely supports a 2 of 3 key scheme.  Privkey 1 is held by the client. Privkey 2 is held by my wallet protection service that verifies my spends by SMS before letting them happen, and privkey 3 is locked in my safe just in case provider with key #2 goes belly up. These funds would require (k1 AND k2) OR k3.

For someone to create a 2of3 or other complex transaction right now, they have to create it that way on purpose - which requires them to know the entire spend script and all of the pubkeys in order to emit the script.  Something MtGox is unlikely to add anytime soon to their withdraw page. With this proposal, I can give out normal Bitcoin addresses that encumber the funds in the manner I deem safe for me, the moment they arrive, with no burden on the sender to send the transactions any special way.

[Pieter Wuille]

There will obviously be a need for communicating such outputs (either an address scheme, or out of band protocol, or ...), but that is independent from how those requirements get encoded in the block chain.

It is already possible to encode arbitrary boolean expressions over signature checks in scripts, given that they are allowed to pass the IsStandard() test. That sounds like a much better solution to me than trying to pack everything into the OP_CHECKSIG code: it breaks backward compatibility, and is far less flexible.

[casascius]

There will obviously be a need for communicating such outputs (either an address scheme, or out of band protocol, or ...), but that is independent from how those requirements get encoded in the block chain.

It is already possible to encode arbitrary boolean expressions over signature checks in scripts, given that they are allowed to pass the IsStandard() test. That sounds like a much better solution to me than trying to pack everything into the OP_CHECKSIG code: it breaks backward compatibility, and is far less flexible.

You are absolutely right in that the functionality is already there outside OP_CHECKSIG.  What I want to emphasize is that for it to be useful as a safety feature, it requires expert human action on the part of the developers of every website that offers a withdraw or send bitcoins feature to be of any practical use.  Think about it for a moment... that's never gonna happen, please let me illustrate why not.

Even if arbitrary boolean expressions are possible, how will that safely help me take money out of MtGox or anywhere else?  Does MtGox then need to implement a "boolean expression withdraw" feature in order to take advantage of that?  Are they ever going to?  How will that be explained to the average joe user?  What about people who want to send me money who don't understand a "boolean expression transaction"?  Or those who scoff that they need to now input 3 addresses for me (or one very long one) to send me money.  Forget putting my bitcoin address on my business card, as it now needs to be a QR code the size of a saltine cracker to be of any use! =)

OK, or I could also receive bitcoins at a normal address and either forward them to a boolean expression myself or with a third party service... but I'm back to square one... having bitcoins encumbered by 1 private key for a time, at which point they can be stolen by whoever roots my box, or by the operator of that third party forwarding service.  On the other hand, with my proposal, no single person (but me) or machine ever has simultaneous possession of all the keys necessary to spend my funds at any point in their lifecycle, they are highly unlikely to be stolen.

Yes, I realize a blockchain fork is not something to take lightly, and I'm not proposing one.  I am also one for clean, concise code and for not convoluting the implementation with respect to the abstract design, and I fully appreciate not wanting to "redefine" OP_CHECKSIG (though the opcode could be cleanly renamed OP_CHECKSIGEX, where EX=expression).

But rather, I'm proposing the code be put in and left dormant except on testnet, to be enabled on mainline only on the next occasion that a fork becomes necessary or desirable for some other reason.

The world right now is rejecting us as a project for security problems - besides malware and hackings, people having bitcoins stolen is all you read about when you type "bitcoin" into Google News.  Nobody but computer experts wants to touch them now because they have a reasonable expectation that they will probably wake up one morning to discover they're gone without a trace.

You can hardly keep bitcoins safe on your computer today without either using Linux or dedicating a computer to Bitcoin or both, which just isn't going to work for the majority of the world who uses Windows and Macs.  This proposal would add a practical security benefit to every future joe schmoe Bitcoin user that would not depend on mandatory cooperation from all senders and website operators.

I believe the code burden would be small.  Here is the code for this opcode renamed to OP_CHECKSIGEX with my idea penciled in as pseudo-code (my additions in CAPS): http://pastebin.com/5aR9EGcn

[Gavin Andresen]

I'm going to shoot myself in my foot again thinking about stuff late in the day and week when my brain is tired...

... but here are some half-baked thoughts:

The:   DUP HASH160 <hash> EQUALVERIFY   that we're currently using to hash a 65-byte public key into a 20-byte bitcoin address could be generalized into something like:

n DIGEST160 <hash> EQUALVERIFY  :   create a secure 160-bit hash from the <n> items on the stack, make sure it matches a given hash.

That would be very useful for creating multisignature transactions where <hash> is really some arbitrary combination of public keys.

But it would be really spiffy if the complicated transaction could be in the ScriptSig (specified when the coins are spent) and not the ScriptPubKey (so the sender doesn't need to know what kind of transaction they're funding).  Maybe something like:

ScriptPubKey:  END_DIGEST160 <hash> EQUAL

... and the generic ScriptSig would be:

<sig₁> <sig₂> ... <sig_n> BEGIN_DIGEST160 ... an arbitrary script with public keys and CHECKSIGs and stuff....

BEGIN...END_DIGEST160 would create a secure hash for all the opcodes and data between the begin and end.

I think I can convince myself that would always be secure.  Concrete example of the simplest, one-key transaction would be:

ScriptSig:  <signature>  BEGIN_DIGEST160 <public_key> CHECKSIGVERIFY
ScriptPubKey: END_DIGEST160 <hash> EQUAL

Nobody can put another Script in the ScriptSig, because that would change <hash>.
And the signature must be valid because it is checked in the ScriptSig.

If we're going to schedule a blockchain split to support new stuff, something like this seems like the right thing to do.

[casascius]

ScriptSig:  <signature>  BEGIN_DIGEST160 <public_key> CHECKSIGVERIFY
ScriptPubKey: END_DIGEST160 <hash> EQUAL

I like it.  It would accomplish the same thing without adding undue complexity.

[Gavin Andresen]

I split ByteCoin's OP_EVAL post and followups into it's own thread.

[Simon Barber]

Threshold cryptography allows this 'n of m' functionality to be implemented purely in the clients - no script changes needed, no address format changes needed.

[gmaxwell]

Threshold cryptography allows this 'n of m' functionality to be implemented purely in the clients - no script changes needed, no address format changes needed.

No, not really.   You still have to have a trusted part to hold the resultant derived key.   Meaning you can't use 2 of 3 to address  "one of my machines is compromised but I don't know which" since if you recover the complete key on the compromised machine you're screwed.