Title: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 08:09:06 AM REVISED:
There are some complaints about the existing CHECKSIG procedures: 1. Choice of SIGHASH types are restricted. It is either all or one or none, but cannot sign some of the outputs. (https://bitcointalk.org/index.php?topic=212555.0) 2. It wastes a lot of blockchain space to sign outputs of the same script, because it requires one sig per input 3. In order to calculate the fee, one needs to see the full transactions which could be a problem for lightweight hardware wallet (https://bitcointalk.org/index.php?topic=181734.0) 4. It has some unexpected behaviors: https://bitcointalk.org/index.php?topic=260595.0 To solve these problems, we need to revolutionize the way of checking signatures. Here I propose the OP_CHECKSIG2 The format of signature is completely different for OP_CHECKSIG2. In human language, the signature will look like: Code: I agree to release the fund of <tx-hash1>:<vout1>:<value1>, <tx-hash2>:<vout2>:<value2> , <tx-hash3>:<vout3>:<value3>........... This structure will supersede all existing sighash types (all/none/single/anyonecanpay), and do a lot more ------------------------------ Some definitions: Input index: order of an input in a final transaction. The first input is index 0 Output index: order of an output in a final transaction. The first output is index 0 OutPoint: <hash of previous tx|output index of previous tx>. A 36 bytes identifier of previous outputs, describe at https://en.bitcoin.it/wiki/Protocol_specification#tx InputID: An unique identifier for an input, in a format of <value of the input|OutPoint> (36+8=44bytes) OutputID: <value of the output|pk_script length|pk_script>, same format as TxOut describe at https://en.bitcoin.it/wiki/Protocol_specification#tx Some new OP codes: OP_EVAL2:
OP_CHECKSIG2: it pops the top 3 stakes <sig> <hash> <public key>, and check the validity of <sig> against <hash> with <public key>. If it is, 1 is returned, 0 otherwise. OP_PUSHINPUT: it pops the top stake. From the top stake, it pops the least significant byte. If the least significant byte is:
OP_PUSHOUTPUT: it pops the top stake. From the top stake, it pops the least significant byte. If the least significant byte is:
OP_PUSHSCRIPTSIG:
To make this a soft-fork, OP_EVAL2 and OP_PUSHSCRIPTSIG will use some of the unused OP_NOP (e.g. OP_NOP3 and OP_NOP4); The other new codes will use currently unspecified codes, and they will fail the script if not called by OP_EVAL2 For example, in a standard transaction, the ScriptSig would look like (in a bitmap mode): Code: <sig> <0x1802> <0x0C02> scriptPubKey would be: Code: <hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> Running the script
To prepare a signature:
----------------------- To prepare a transaction:
------------------------ Example of a full transaction: There are 4 key pairs: Alice, Bob, Carl, David 5 inputs, the InputIDs are: Alice-1, Alice-2, Bob-1, Carl-1, David-1 5 outputs the OutputIDs are: A, B, C, D, E As long as outputs A, B, C are paid, Alice is willing to sign and don't care where other BTC comes from and where the rest of BTC goes As long as outputs D, E are paid, and Carl-1 is involved, Bob is willing to sign and don't care where other BTC comes from and where the rest of BTC goes Carl will sign if Bob-1 is involved. He doesn't care where other BTC comes from and where the BTC goes David will sign if all 5 inputs and 5 outputs are involved. No more, no less. Alice will construct this message: "Alice-1|Alice-2|A|B|C", take double SHA256, sign with her key (Alice-sig)* Bob will construct this message: "Bob-1|Carl-1|D|E", take double SHA256, sign with his key (Bob-sig) Carl will construct this message: "Bob-1|Carl-1", take double SHA256, sign with his key (Carl-sig) David will construct this message: "Alice-1|Alice-2|Bob-1|Carl-1|David-1|0xff|A|B|C|D|E|0xff", take double SHA256, sign with his key (Carl-sig) The raw, unsigned transaction is arranged this way: Input index 0: Alice-1 Input index 1: Alice-2 Input index 2: Bob-1 Input index 3: Carl-1 Input index 4: David-1 Output index 0: A Output index 1: B Output index 2: C Output index 3: D Output index 4: E The ScriptSig for input 0: <Alice-sig><0x0702><0x0302><serialized script> The ScriptSig for input 1: OP_0 OP_PUSHSCRIPTSIG The ScriptSig for input 2: <Bob-sig><0x1802><0x0C02><serialized script> The ScriptSig for input 3: <Carl-sig><0x00><0x0C02><serialized script> The ScriptSig for input 4: <David-sig><0x01><0x01><serialized script> The tx is completed. Broadcast. ------------------------------------- Evaluating inputs with OP_PUSHSCRIPTSIG: Code: OP_0 OP_PUSHSCRIPTSIG scriptPubKey would be: Code: <hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> Running the script
If properly optimised, these steps are actually not needed, saving many hashing and ECDSA operations Title: Re: CHECKSIG 2.0 Post by: TierNolan on July 19, 2013, 09:29:01 AM When you say bitmaps, do you mean that there is a limit of 32 inputs/outputs (one bit per)?
Another option would be to use var_ints and round up to the nearest 8. If there are 15 or fewer inputs/outputs, then that will be smaller. For large transactions, you are adding an extra byte. Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 09:34:13 AM When you say bitmaps, do you mean that there is a limit of 32 inputs/outputs (one bit per)? Another option would be to use var_ints and round up to the nearest 8. If there are 15 or fewer inputs/outputs, then that will be smaller. For large transactions, you are adding an extra byte. I choose 4 bytes because now we use 4bytes to encode vout Oh I'm sorry. You are right. (Don't need an extra byte to encode because the number of inputs/outputs is known by looking at the transaction) For large transaction this could become very big. We may allow people to assign a range instead. Title: Re: CHECKSIG 2.0 Post by: TierNolan on July 19, 2013, 12:17:25 PM For large transaction this could become very big. We may allow people to assign a range instead. We may be talking past each other. I assume the point is to say that the signature must include inputs in certain positions? Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 03:09:22 PM For large transaction this could become very big. We may allow people to assign a range instead. We may be talking past each other. I assume the point is to say that the signature must include inputs in certain positions? Let me explain this way: There are 3 key pairs: Alice, Bob, Carl 4 inputs: Alice-1, Alice-2, Bob-1, Carl-1 5 outputs: A, B, C, D, E As long as outputs A, B, C are paid, Alice is willing to sign and don't care where other BTC comes from and where the rest of BTC goes As long as outputs D, E are paid, and Carl-1 is involved, Bob is willing to sign and don't care where other BTC comes from and where the rest of BTC goes Carl will sign if if Bob-1 is involved. He doesn't care where other BTC comes from and where the BTC goes Alice will construct this message: "Alice-1 Alice-2; <empty> ; A B C", take double SHA256, sign with her key (Alice-sig)* Bob will construct this message: "Bob-1; Carl-1 ; D E", take double SHA256, sign with his key (Bob-sig) Carl will construct this message: "Carl-1; Bob-1 ; <empty>", take double SHA256, sign with his key (Carl-sig) (* This is simplified. The actual message is <Alice-1 hash><Alice-1 vout><Alice-1 value><Alice-2 hash><Alice-2 vout><Alice-2 value><separator><separator><Output A script><Output A value><Output B script><Output B value><Output C script><Output C value>) However, the transaction is not compete yet. The raw, unsigned transaction is arranged this way: Input index 1: Alice-1 Input index 2: Alice-2 Input index 3: Bob-1 Input index 4: Carl-1 Output index 1: A Output index 2: B Output index 3: C Output index 4: D Output index 5: E Alice-sig is appended with this bitmap: 00000011 00000000 00000111. The first byte means she is signing for input 1, 2. The second byte means she doesn't care where the rest of inputs comes from. The third byte means outputs 1, 2, 3 must be paid Bob-sig is appended with this bitmap: 00000100 00001000 00011000 Carl-sig is appended with this bitmap: 00001000 00000100 00000000 <Alice-sig-bitmap> <Alice-public key> OP_CHECKSIG2 is used as the scriptsig of input 1 (just like P2SH) OP_1 OP_PUSHSCRIPTSIG is used as the scriptsig of input 2 (2 bytes only. saved a lot of space!) <Bob-sig-bitmap> <Bob-public key> OP_CHECKSIG2 is used as the scriptsig of input 3 <Carl-sig-bitmap> <Carl-public key> OP_CHECKSIG2 is used as the scriptsig of input 4 The tx is completed. Broadcast. -------- To verify: Input 1: Based on the bitmap of Alice-sig (00000011 00000000 00000111), we can reconstruct this message: "Alice-1 Alice-2; <empty> ; A B C". Take double SHA256, verify the signature against Alice-public key Input 2: Scriptsig of input 1 is used. Repeat the verification. (In an optimized system such repeat is not needed) Input 3 and 4: Similar to input 1 As all signatures are valid, the transaction is valid. Title: Re: CHECKSIG 2.0 Post by: Peter Todd on July 19, 2013, 04:07:39 PM I'd suggest you think about how you could separate CHECKSIG into three steps: generate transaction subset, hash, check pubkey signature. If you can figure out a rational way to split up the "generate tx subset" part, all the better.
We're much more likely to be able to successfully test a new CHECKSIG implementation if it's split into modular parts; we can always have opcode aliases so that really common sequences are compressed into a single alias even if the backend runs a whole bunch of opcodes. Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 04:08:15 PM I think the scheme could be simplified. There is no need to distinguish "sign a input" and "require a input". Signing an input that you own means you agree to release the fund. Signing an input that you do not own means you require that input to participate. It is illogical to say "I want my input to participate, but I don't want to sign it".
Back to my example, Alice will construct this message: "Alice-1 Alice-2; A B C", take double SHA256, sign with her key (Alice-sig)* Bob will construct this message: "Bob-1 Carl-1 ; D E", take double SHA256, sign with his key (Bob-sig) Carl will construct this message: "Bob-1 Carl-1 ; <empty>", take double SHA256, sign with his key (Carl-sig) Alice-sig is appended with this bitmap: 00000011 00000111. The first byte means she is signing for input 1, 2. The second byte means outputs 1, 2, 3 must be paid Bob-sig is appended with this bitmap: 00001100 00011000 Carl-sig is appended with this bitmap: 00001100 00000000 Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 04:24:48 PM here will be 3 ways to indicate the index: none (0x00), all (0x01), bitmap (0x02), and range (0x03)
To indicate inputs, "none" means "signing this input only", "all" means "signing all inputs, no more, no less" To indicate outputs, "none" means "send to anyone", "all" means "all outputs are required, no more, no less" 01 01 is equivalent to the current SIGHASH_ALL 01 00 is equivalent the current SIGHASH_NONE 00 01 is equivalent the current SIGHASH_ALL + SIGHASH_ANYONECANPAY 00 00 is equivalent the current SIGHASH_NONE + SIGHASH_ANYONECANPAY Bitmap and range are used when referring to some of the inputs/outputs The bitmap code (0x02) is followed by some bytes. The length is determined by the number of inputs/outputs. For every 8 inputs or outputs, there is 1 byte. An input/output is indicated by "1" at the corresponding bit The range code (0x03) is followed by 2 integers x and y to indicate the range of required inputs/outputs (x and y included). The integer is 1 byte if there is no more than 256 inputs/outputs, and 2 bytes if there is no more than 65536 inputs/outputs, etc. The range code is less flexible, but more efficient if there is a huge number of inputs/outputs.
Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 04:56:17 PM I'd suggest you think about how you could separate CHECKSIG into three steps: generate transaction subset, hash, check pubkey signature. If you can figure out a rational way to split up the "generate tx subset" part, all the better. We're much more likely to be able to successfully test a new CHECKSIG implementation if it's split into modular parts; we can always have opcode aliases so that really common sequences are compressed into a single alias even if the backend runs a whole bunch of opcodes. It's easy, just a few more OP codes. Generate tx subset (*): OP_PUSHALLINPUTSWITHVALUE will return the concatenated hash, vout, and value of all inputs, by the order in the transaction OP_PUSHTHISINPUTWITHVALUE will return the hash, vout, and value of this input OP_PUSHALLOUTPUTSSWITHVALUE will return the concatenated output script and value of all outputs, by the order in the transaction <bitmap> OP_PUSHINPUTWITHVALUEBYBITMAP will return the concatenated hash, vout, and value of the inputs specified by the bitmap <bitmap> OP_PUSHOUTPUTWITHVALUEBYBITMAP will return the concatenated output script and value of the outputs specified by the bitmap <x> <y> OP_PUSHINPUTWITHVALUEBYRANGE will return the concatenated hash, vout, and value of the inputs x to y inclusive <x> <y> OP_PUSHOUTPUTWITHVALUEBYRANGE will return the concatenated output script and value of the outputs x to y inclusive <z> OP_PUSHINPUTWITHVALUE will return the hash, vout, and value of input z <z> OP_PUSHOUTPUTWITHVALUE will return the output script and value of output z Then, use a new OP_JOIN to concatenate all these things (#) Hash: use the existing OP_HASH256 to do double SHA256 Check sig: the new OP_CHECKSIG will verify the signature (* This part could be further separated to something like OP_PUSHINPUT, OP_PUSHINPUTVALUE, but it will make it looks quite clumsy.) (# By the way, why OP_CAT is considered as a high risk code and get disabled?) Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 19, 2013, 05:29:55 PM I'd suggest you think about how you could separate CHECKSIG into three steps: generate transaction subset, hash, check pubkey signature. If you can figure out a rational way to split up the "generate tx subset" part, all the better. We're much more likely to be able to successfully test a new CHECKSIG implementation if it's split into modular parts; we can always have opcode aliases so that really common sequences are compressed into a single alias even if the backend runs a whole bunch of opcodes. It's easy, just a few more OP codes. Generate tx subset (*): OP_PUSHALLINPUTSWITHVALUE will return the concatenated hash, vout, and value of all inputs, by the order in the transaction OP_PUSHTHISINPUTWITHVALUE will return the hash, vout, and value of this input OP_PUSHALLOUTPUTSSWITHVALUE will return the concatenated output script and value of all outputs, by the order in the transaction <bitmap> OP_PUSHINPUTWITHVALUEBYBITMAP will return the concatenated hash, vout, and value of the inputs specified by the bitmap <bitmap> OP_PUSHOUTPUTWITHVALUEBYBITMAP will return the concatenated output script and value of the outputs specified by the bitmap <x> <y> OP_PUSHINPUTWITHVALUEBYRANGE will return the concatenated hash, vout, and value of the inputs x to y inclusive <x> <y> OP_PUSHOUTPUTWITHVALUEBYRANGE will return the concatenated output script and value of the outputs x to y inclusive <z> OP_PUSHINPUTWITHVALUE will return the hash, vout, and value of input z <z> OP_PUSHOUTPUTWITHVALUE will return the output script and value of output z Then, use a new OP_JOIN to concatenate all these things (#) Hash: use the existing OP_HASH256 to do double SHA256 Check sig: the new OP_CHECKSIG will verify the signature (* This part could be further separated to something like OP_PUSHINPUT, OP_PUSHINPUTVALUE, but it will make it looks quite clumsy.) (# By the way, why OP_CAT is considered as a high risk code and get disabled?) Wait.....there is a big loophole. If subset generation and sig checking are decoupled, an attacker can use a signature for another transaction to redeem any outputs of the same script, because he can bypass those OP_PUSHOUTPUTWITHVALUE codes and feed the CHECKSIG with the subset hash of the previous transaction directly. I think that was the reason why Satoshi made OP_CHECKSIG doing everything. Title: Re: CHECKSIG 2.0 Post by: Peter Todd on July 20, 2013, 05:50:27 AM Wait.....there is a big loophole. If subset generation and sig checking are decoupled, an attacker can use a signature for another transaction to redeem any outputs of the same script, because he can bypass those OP_PUSHOUTPUTWITHVALUE codes and feed the CHECKSIG with the subset hash of the previous transaction directly. I think that was the reason why Satoshi made OP_CHECKSIG doing everything. How would that happen? All the processing would still happen in the scriptPubKey, out of the control of the attacker. Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 20, 2013, 03:23:33 PM Some definitions:
Input index: order of an input in a final transaction. The first input is index 0 Output index: order of an output in a final transaction. The first output is index 0 OutPoint: <hash of previous tx|output index of previous tx>. A 36 bytes identifier of previous outputs, describe at https://en.bitcoin.it/wiki/Protocol_specification#tx InputID: An unique identifier for an input, in a format of <value of the input|OutPoint> (36+8=44bytes) OutputID: <value of the output|pk_script length|pk_script>, same format as TxOut describe at https://en.bitcoin.it/wiki/Protocol_specification#tx Some new OP codes: OP_EVAL2: basically the OP_EVAL of BIP12, but will run the now disabled OP_CAT and support some new OP codes OP_CHECKSIG2: it pops the top 3 stakes <sig> <hash> <public key>, and check the validity of <sig> against <hash> with <public key>. If it is, 1 is returned, 0 otherwise. OP_PUSHINPUT: it pops the top stake. From the top stake, it pops the least significant byte. If the least significant byte is:
To make this a soft-fork, OP_EVAL2 will use one of the unused OP_NOP (e.g. OP_NOP3); The other new codes will use currently unspecified codes, and they will fail the script if not called by OP_EVAL2 For example, in a standard transaction, the ScriptSig would look like (in a bitmap mode): Code: <sig> <0x1802> <0x0C02> scriptPubKey would be: Code: OP_DUP Running the script
To prepare a signature:
----------------------- To prepare a transaction:
------------------------ Example of a full transaction: There are 4 key pairs: Alice, Bob, Carl, David 5 inputs, the InputIDs are: Alice-1, Alice-2, Bob-1, Carl-1, David-1 5 outputs the OutputIDs are: A, B, C, D, E As long as outputs A, B, C are paid, Alice is willing to sign and don't care where other BTC comes from and where the rest of BTC goes As long as outputs D, E are paid, and Carl-1 is involved, Bob is willing to sign and don't care where other BTC comes from and where the rest of BTC goes Carl will sign if Bob-1 is involved. He doesn't care where other BTC comes from and where the BTC goes David will sign if all 5 inputs and 5 outputs are involved. No more, no less. Alice will construct this message: "Alice-1|Alice-2|A|B|C", take double SHA256, sign with her key (Alice-sig)* Bob will construct this message: "Bob-1|Carl-1|D|E", take double SHA256, sign with his key (Bob-sig) Carl will construct this message: "Bob-1|Carl-1", take double SHA256, sign with his key (Carl-sig) David will construct this message: "Alice-1|Alice-2|Bob-1|Carl-1|David-1|0xff|A|B|C|D|E|0xff", take double SHA256, sign with his key (Carl-sig) The raw, unsigned transaction is arranged this way: Input index 0: Alice-1 Input index 1: Alice-2 Input index 2: Bob-1 Input index 3: Carl-1 Input index 4: David-1 Output index 0: A Output index 1: B Output index 2: C Output index 3: D Output index 4: E The ScriptSig for input 0: <Alice-sig><0x0702><0x0302><serialized script> The ScriptSig for input 1: OP_0 OP_PUSHSCRIPTSIG The ScriptSig for input 2: <Bob-sig><0x1802><0x0C02><serialized script> The ScriptSig for input 3: <Carl-sig><0x00><0x0C02><serialized script> The ScriptSig for input 4: <David-sig><0x01><0x01><serialized script> The tx is completed. Broadcast. Title: Re: CHECKSIG 2.0 Post by: jl2012 on July 20, 2013, 06:19:37 PM I find an interesting idea here: https://en.bitcoin.it/wiki/User:Gmaxwell/alt_ideas
Quote Transaction checkpoints. Each transaction (or signature?) should contain a block index and 32 (?) least significant bits of the block hash. The transaction's fees are only valid (or only their full value?) if they are mined in a chain they agree with. This would let people making bitcoin transactions 'vote with their wallets' on the identity of the chain they consider important. This isn't a viable POW replacement, but would greatly reduce the economic benefit of mining moderate depth forks, esp as fees begin to dominate the block reward. "You don't get (all) of my fee payment if you are mining a chain I don't like!" Nodes would typical checkpoint a few blocks in the past from their current height to avoid overstating their opinion unnecessarily. Deep checkpoints could be automatically triggered by observing a critical mass of coins-day-destroyed confirming them— creating a PoS-ish system, though this is subject to the 'nothing at stake' problem of PoS, and is probably very dangerous. (e.g. isolation risk for newly bootsrapping nodes) It could be incorporated into CHECKSIG 2.0. To make it an optional function, I propose 2 new OP codes: OP_JOIN: It keeps popping the stake, until the stake becomes empty or the top stake is -1. In the latter case, the -1 is removed. It returns the concatenated popped items (but not the -1). The first popped stake item is the beginning of the concatenated string. OP_PUSHBLOCKHASH: Giving it a blockheight, it returns the block hash Now the ScriptSig would be: Code: <sig> <-1> <height> OP_BLOCKHASH <0x1802> <0x0C02> scriptPubKey would be: Code: Code: So that the "<height> OP_BLOCKHASH" part is optional. EDIT: It's different from the original idea. My proposal makes a transaction invalid if it is not mined in the designated chain. This seems not very good since it would become a big trouble in case there is network split / major re-org |