Title: Proposal to modify OP_CHECKSIG Post by: casascius on September 22, 2011, 02:21:17 AM 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.
And let me describe how all of these wonderful benefits could be achieved.
And now let me describe what the change is.
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 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 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. Title: Re: Proposal to modify OP_CHECKSIG Post by: casascius on September 22, 2011, 02:40:22 AM 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 Title: Re: Proposal to modify OP_CHECKSIG Post by: Luke-Jr on September 22, 2011, 07:10:56 AM This would fork the blockchain. More useful changes have been kept-out-until-later for that reason. ;)
Title: Re: Proposal to modify OP_CHECKSIG Post by: Pieter Wuille on September 22, 2011, 08:36:55 AM 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 (https://github.com/bitcoin/bitcoin/pull/319) Title: Re: Proposal to modify OP_CHECKSIG Post by: theymos on September 22, 2011, 08:44:30 AM 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. Title: Re: Proposal to modify OP_CHECKSIG Post by: casascius on September 22, 2011, 01:29:43 PM 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 (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. Title: Re: Proposal to modify OP_CHECKSIG Post by: Pieter Wuille on September 22, 2011, 01:36:14 PM 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. Title: Re: Proposal to modify OP_CHECKSIG Post by: casascius on September 22, 2011, 02:44:10 PM 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 Title: Re: Proposal to modify OP_CHECKSIG Post by: Gavin Andresen on October 02, 2011, 12:26:42 AM 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: <sig1> <sig2> ... <sign> 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. Title: Re: Proposal to modify OP_CHECKSIG Post by: casascius on October 02, 2011, 12:46:51 AM 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. Title: Re: Proposal to modify OP_CHECKSIG Post by: Gavin Andresen on October 02, 2011, 03:48:38 PM I split ByteCoin's OP_EVAL post and followups into it's own thread (https://bitcointalk.org/index.php?topic=46538.0).
Title: Re: Proposal to modify OP_CHECKSIG Post by: Simon Barber on October 03, 2011, 04:10:10 AM Threshold cryptography allows this 'n of m' functionality to be implemented purely in the clients - no script changes needed, no address format changes needed.
Title: Re: Proposal to modify OP_CHECKSIG Post by: gmaxwell on October 03, 2011, 03:20:06 PM 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. |