Bitcoin Forum
June 23, 2017, 12:10:30 AM *
News: Latest stable version of Bitcoin Core: 0.14.2  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: CHECKSIG 2.0  (Read 1483 times)
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 08:09:06 AM
 #1

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>...........
     to <outputscript-a>:<value-a>, <outputscript-b>:<value-b>, <outputscript-c>:<value-c>........
     given that <tx-hash4>:<vout4>:<value4>, <tx-hash5>:<vout5>:<value5> , <tx-hash6>:<vout6>:<value6>...... are part of this transaction

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:
  • Pop the second-to-top stake (a)
  • Calculate HASH160(a)
  • Pop the top stake (b)
  • If HASH160(a) is not equal to b, the script fails
  • Deserialize a, and run it as script

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:
  • 0x00:
    • The script fails if the remaining string is not empty
    • Returns InputID of the input
  • 0x01:
    • The script fails if the remaining string is not empty
    • Returns InputID of all inputs in a concatenated form by the order of input index, with Input 0 at the beginning.
    • Appends a 0xff at the end of the concatenated string
  • 0x02:
    • Enumerate the number of inputs, divide by 8, round up to the next integer if not an integer.
    • The script fails if the length (in bytes) of the remaining string is larger than the integer.
    • Read the remaining string as a bitmap. Each bit refers the an input, with the least significant bit refers to input 0.
    • If there is any positive bit for an non-existing input, the script fails.
    • For every positive bit, returns the InputID of the corresponding input by the order of input index.
    • Concatenate the results, with the InputID of the lowest index at the beginning.
  • 0x03:
    • Enumerate the number of inputs, take log256, round up to the next integer if not an integer.
    • The script fails if the length (in bytes) of the remaining string is not equal to 2 times the integer.
    • Split the remaining string in half. Call the more significant halve x and the less significant halve y.
    • If x>y, the script fails.
    • If y is greater than the largest input index, the script fails.
    • Return the InputID of all inputs with index from x to y (inclusive) in a concatenated form by the order of input index, the InputID of the lowest index at the beginning.

OP_PUSHOUTPUT: it pops the top stake. From the top stake, it pops the least significant byte. If the least significant byte is:
  • 0x00:
    • The script fails if the remaining string is not empty
    • Returns an empty string
  • 0x01, 0x02, 0x03: Same as OP_PUSHINPUT, just replace inputs with outputs.

OP_PUSHSCRIPTSIG:
  • Pops the top stake, an interger (z >= 0)
  • The script fails if z is greater than the highest input index
  • Return the ScriptSig of the input z

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>
<serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
 

scriptPubKey would be:

Code:
<hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
OP_EVAL2

Running the script
  • 1. stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> <hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 2. OP_EVAL2, stake = <sig> <0x1802> <0x0C02>
  • 3. OP_PUSHINPUT, stake = <sig> <0x1802> <concatenated InputIDs for inputs 2 and 3>
  • 4. OP_SWAP, stake = <sig> <concatenated InputIDs> <0x1802>
  • 5. OP_PUSHOUTPUT, stake = <sig> <concatenated InputIDs> <concatenated OutputIDs for outputs for outputs 3 and 4>
  • 6. OP_CAT, stake =  <sig> <concatenated InputIDs and OutputIDs>
  • 7. OP_HASH256, stake = <sig> <hash of concatenated InputIDs and OutputIDs>
  • 8. stake = <sig> <hash of concatenated InputIDs and OutputIDs> <public key>
  • 9. OP_CHECKSIG2, stake = <1>. Script ends.
-----------------------

To prepare a signature:

  • List the InputID of all required inputs (including inputs to be signed by the key pair, and any required inputs owned by other key pair)
  • Concatenate the InputID, by the desired order
  • Append an 0xff at the end if the exact inputs are required (no more, no less)
  • List the OutputID of all required outputs
  • Concatenate the OutputID, by the desired order
  • Append an 0xff at the end if the exact outputs are required (no more, no less)
  • Concatenate the InputIDs and OutputIDs, take double SHA256, sign with private key

-----------------------

To prepare a transaction:
  • Arrange the order of inputs and outputs to make sure they are coherent with all signatures
  • ScriptSig will be <signature> <command for OP_PUSHOUTPUT> <command for OP_PUSHINPUT> <serialized script>
  • If a key pair is signing for 2 or more outputs, the ScriptSig for the rest of inputs is simply <input index> OP_PUSHSCRIPTSIG

------------------------

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
<sig> <0x1802> <0x0C02>
<serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
 

scriptPubKey would be:

Code:
<hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
OP_EVAL2

Running the script
  • 1. stake = <0>
  • 2. OP_PUSHSCRIPTSIG; stake = <sig> <0x0702> <0x0302> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 3. stake =  <sig> <0x0702> <0x0302> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2><hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 4. OP_EVAL2, stake = <sig> <0x0702> <0x0302>
  • 5. The rest is same as above

If properly optimised, these steps are actually not needed,  saving many hashing and ECDSA operations

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
1498176630
Hero Member
*
Offline Offline

Posts: 1498176630

View Profile Personal Message (Offline)

Ignore
1498176630
Reply with quote  #2

1498176630
Report to moderator
1498176630
Hero Member
*
Offline Offline

Posts: 1498176630

View Profile Personal Message (Offline)

Ignore
1498176630
Reply with quote  #2

1498176630
Report to moderator
POLONIEX TRADING SIGNALS
+50% Profit and more via TELEGRAM
ALTCOINTRADER.CO
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1498176630
Hero Member
*
Offline Offline

Posts: 1498176630

View Profile Personal Message (Offline)

Ignore
1498176630
Reply with quote  #2

1498176630
Report to moderator
TierNolan
Legendary
*
Offline Offline

Activity: 1078


View Profile
July 19, 2013, 09:29:01 AM
 #2

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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 09:34:13 AM
 #3

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.

4bytes = 32bits = 2^32, not 32

I choose 4 bytes because now we use 4bytes to encode vout


Oh I'm sorry. You are right. That's easy, just use a variable length integer (https://en.bitcoin.it/wiki/Protocol_specification#Variable_length_integer ) to encode the number of bytes of the bitmap.

(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.

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
TierNolan
Legendary
*
Offline Offline

Activity: 1078


View Profile
July 19, 2013, 12:17:25 PM
 #4

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?

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 03:09:22 PM
 #5

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.

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1078


View Profile
July 19, 2013, 04:07:39 PM
 #6

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.

jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 04:08:15 PM
 #7

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

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 04:24:48 PM
 #8

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.

Number of inputs/outputsBytes for bitmapBytes for range
1-812
9-1622
17-2432
249-256322
257-264334
65529-6553681924

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 04:56:17 PM
 #9

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?)

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 19, 2013, 05:29:55 PM
 #10

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.

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1078


View Profile
July 20, 2013, 05:50:27 AM
 #11

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.

jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 20, 2013, 03:23:33 PM
 #12

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:
  • 0x00:
    • The script fails if the remaining string is not empty
    • Returns InputID of the input
  • 0x01:
    • The script fails if the remaining string is not empty
    • Returns InputID of all inputs in a concatenated form by the order of input index, with Input 0 at the beginning.
    • Appends a 0xff at the end of the concatenated string
  • 0x02:
    • Enumerate the number of inputs, divide by 8, round up to the next integer if not an integer.
    • The script fails if the length (in bytes) of the remaining string is larger than the integer.
    • Read the remaining string as a bitmap. Each bit refers the an input, with the least significant bit refers to input 0.
    • If there is any positive bit for an non-existing input, the script fails.
    • For every positive bit, returns the InputID of the corresponding input by the order of input index.
    • Concatenate the results, with the InputID of the lowest index at the beginning.
  • 0x03:
    • Enumerate the number of inputs, take log256, round up to the next integer if not an integer.
    • The script fails if the length (in bytes) of the remaining string is not equal to 2 times the integer.
    • Split the remaining string in half. Call the more significant halve x and the less significant halve y.
    • If x>y, the script fails.
    • If y is greater than the largest input index, the script fails.
    • Return the InputID of all inputs with index from x to y (inclusive) in a concatenated form by the order of input index, the InputID of the lowest index at the beginning.
OP_PUSHOUTPUT: it pops the top stake. From the top stake, it pops the least significant byte. If the least significant byte is:
  • 0x00:
    • The script fails if the remaining string is not empty
    • Returns an empty output
  • 0x01, 0x02, 0x03: Same as OP_PUSHINPUT, just replace inputs with outputs.
OP_PUSHSCRIPTSIG:
  • Pops the top stake, an interger (z)
  • The script fails if z is greater than the highest input index
  • Return the ScriptSig of the input z

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>
<serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
 

scriptPubKey would be:

Code:
OP_DUP
OP_HASH160
<hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
OP_EQUALVERIFY
OP_EVAL2

Running the script
  • 1. stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 2. OP_DUP, stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 3. OP_HASH160, stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> <hash1>
  • 4. stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2> <hash1> <hash of serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 5. OP_EQUALVERIFY, stake = <sig> <0x1802> <0x0C02> <serialized OP_PUSHINPUT OP_SWAP OP_PUSHOUTPUT OP_CAT OP_HASH256 <public key> OP_CHECKSIG2>
  • 6. OP_EVAL2, stake = <sig> <0x1802> <0x0C02>
  • 7. OP_PUSHINPUT, stake = <sig> <0x1802> <concatenated InputIDs for inputs 2 and 3>
  • 8. OP_SWAP, stake = <sig> <concatenated InputIDs> <0x1802>
  • 9. OP_PUSHOUTPUT, stake = <sig> <concatenated InputIDs> <concatenated OutputIDs for outputs for outputs 3 and 4>
  • 10. OP_CAT, stake =  <sig> <concatenated InputIDs and OutputIDs>
  • 11. OP_HASH256, stake = <sig> <hash of concatenated InputIDs and OutputIDs>
  • 12. stake = <sig> <hash of concatenated InputIDs and OutputIDs> <public key>
  • 13. OP_CHECKSIG2, stake = <1>. Script ends.
-----------------------

To prepare a signature:

  • List the InputID of all required inputs (including inputs to be signed by the key pair, and any required inputs owned by other key pair)
  • Concatenate the InputID, by the desired order
  • Append an 0xff at the end if the exact inputs are required (no more, no less)
  • List the OutputID of all required outputs
  • Concatenate the OutputID, by the desired order
  • Append an 0xff at the end if the exact outputs are required (no more, no less)
  • Concatenate the InputIDs and OutputIDs, take double SHA256, sign with private key

-----------------------

To prepare a transaction:
  • Arrange the order of inputs and outputs to make sure they are coherent with all signatures
  • ScriptSig will be <signature> <command for OP_PUSHOUTPUT> <command for OP_PUSHINPUT> <serialized script>
  • If a key pair is signing for 2 or more outputs, the ScriptSig for the rest of inputs is simply <input index> OP_PUSHSCRIPTSIG

------------------------

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.

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
jl2012
Legendary
*
Offline Offline

Activity: 1624


View Profile
July 20, 2013, 06:19:37 PM
 #13

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>
<serialized OP_PUSHOUTPUT OP_SWAP OP_PUSHINPUT OP_JOIN OP_HASH256 <public key> OP_CHECKSIG2>
 


scriptPubKey would be:

Code:
Code:
OP_DUP
OP_HASH160
<hash of serialized OP_PUSHOUTPUT OP_SWAP OP_PUSHINPUT OP_JOIN OP_HASH256 <public key> OP_CHECKSIG2>
OP_EQUALVERIFY
OP_EVAL2

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

Donation address: 1CxPk7mhhe2uCDosQraSMeCdgvwWHfLSQx
PGP: D3CC 1772 8600 5BB8 FF67 3294 C524 2A1A B393 6517
Bitcoin Wizards Wiki: https://8333.info/
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!