Difference between revisions of "M of 2 DRAFT"

From Bitcoin Wiki
Jump to: navigation, search
(Created page with "<pre> BIP: 18 (Unofficial) Title: M-of-2 scriptPubKey Author: Ben Reeves <support@pi.uk.com> Status: Draft Type: Standards Track Created: 15-01-2012 </pre> ==Abst...")
 
(Added to category BIP)
 
(80 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
<pre>
 
<pre>
   BIP: 18 (Unofficial)
+
   BIP: Unassigned
 
   Title: M-of-2 scriptPubKey
 
   Title: M-of-2 scriptPubKey
 
   Author: Ben Reeves <support@pi.uk.com>
 
   Author: Ben Reeves <support@pi.uk.com>
 
   Status: Draft
 
   Status: Draft
   Type: Standards Track
+
   Type: Unassigned
 
   Created: 15-01-2012
 
   Created: 15-01-2012
 
</pre>
 
</pre>
Line 10: Line 10:
 
==Abstract==
 
==Abstract==
  
This BIP describes a new standard type of ScriptPubKey designed to allow immediate use of split key wallets.
+
This BIP describes a new standard type of scriptPubKey designed to allow immediate use of split key wallets.
  
 
==Motivation==
 
==Motivation==
Line 20: Line 20:
 
A new standard scriptPubKey will be defined:
 
A new standard scriptPubKey will be defined:
  
   OP_2OVER OP_2OVER OP_ADD OP_ADD OP_ADD <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
   OP_2OVER OP_2OVER OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
  
 
Redeemed by a new standard scriptSig
 
Redeemed by a new standard scriptSig
Line 32: Line 32:
 
* Split key wallets
 
* Split key wallets
  
* Escrow Services - The author does not believe that (A + B) or C scripts are required for escrow transactions. Both parties must trust the holder of C anyway so that can party can instead hold A and B. The holders of A and B can either reach an agreement themselves or party C can act as the final arbitrator using A and B together.
+
* Escrow Services - The author does not believe that (A + B) or C scripts are required for escrow transactions. Both parties must trust the holder of C anyway so that party can instead hold both A and B. The holders of A and B can either reach an agreement themselves or party C can act as the final arbitrator using A and B together.
  
 
==Example Execution==
 
==Example Execution==
Line 40: Line 40:
 
! Stack !! Code
 
! Stack !! Code
 
|-
 
|-
| || <sig> 1 [pubkey] [pubkey] 2 OP_2OVER OP_2OVER OP_ADD OP_ADD OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| || <sig> 1 [pubkey1] [pubkey2] 2 OP_2OVER OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 || OP_2OVER OP_2OVER OP_ADD OP_ADD OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 || OP_2OVER OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 1 [pubkey] || OP_2OVER OP_ADD OP_ADD OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] || OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 1 [pubkey] [pubkey] 2 || OP_ADD OP_ADD OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] [pubkey2] 2 || OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 1 [pubkey] <sumA> || OP_ADD OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] <sumA> || OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 1 <sumB> || OP_ADD OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] <hashA> || OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 <sumC> || OP_HASH160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 <sumB> || OP_HASH256 OP_ADD  OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 <scriptHashA> <scriptHash> || OP_EQUALVERIFY OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 <HashB> || OP_ADD  OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 
|-
 
|-
| <sig> 1 [pubkey] [pubkey] 2 || OP_CHECKMULTISIG
+
| <sig> 1 [pubkey1] [pubkey2] 2 <sumC> || OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 +
|-
 +
| <sig> 1 [pubkey1] [pubkey2] 2 <scriptHashA> <scriptHash> || OP_EQUALVERIFY OP_CHECKMULTISIG
 +
|-
 +
| <sig> 1 [pubkey1] [pubkey2] 2 || OP_CHECKMULTISIG
 
|-
 
|-
 
| 1 ||
 
| 1 ||
 
|}
 
|}
  
Where scriptHash must be constructed in the following manor.
+
Where scriptHash must be constructed in the following manor:
 +
 
 +
scriptHash = RIPMED160(M + SH256(SHA256(pubKey2 + 2) + pubKey1));
 +
 
 +
(+ means addition not concatenation)
 +
 
 +
==Security==
 +
 
 +
Although it may appear insecure totalling the sum of the public keys the author does not believe this to be the case.
  
scriptHash = HASH160(1 + BIGNUM(pubKey1) + BIGNUM(pubKey2) + 2);
+
You could deduce the target value by looking at the the sum of M + pubKey1 + pubKey2 + N  from a previous transaction.
 +
 
 +
<pre>
 +
uint256 target = Previously Redeemed M+P1+P2+N
 +
uint256 myKeyA = SHA256();
 +
uint256 myBogusKeyB = 0;
 +
int n = 2;
 +
int m = 1;
 +
</pre>
 +
 
 +
Initially it might seem that you could use an A or B where B is a invalid key:
 +
 +
<pre>
 +
while(m + myKeyA + myBogusKeyB + n != target) {
 +
  ++myBogusKeyB;
 +
}</pre>
 +
 
 +
However the additional SHA256 operations prevent you from doing this:
 +
 
 +
<pre>
 +
myKeyA = SHA256(myKeyA);
 +
while(m + myKeyA + SHA256(myBogusKeyB + n) != target) {
 +
  ++myBogusKeyB;
 +
}</pre>
 +
 
 +
Resulting in equal brute force time.
 +
 
 +
What does affect security is ability to adjust M (either 1 or 2) without needing to generate a new SHA256 pair. This effectively halves the key space to 2^255 keys however it is still far far out of the realm of brute force possibility. Regardless use of a 20 byte hash limits the key space to 2^160 so it actually has no effect on security at all.
  
 
==Rationale==
 
==Rationale==
  
This BIP replaces BIP 12 ("OP_EVAL") and BIP 16, ("/P2SH/").
+
This BIP replaces BIP 16, ("/P2SH/").
  
The rationale for"pay to script" functionality has been discussed in the other proposals, the general consensus is this functionality is desired and should be implemented ASAP.
+
There is a general consensus that multi signature transactions need to be implemented ASAP without requiring the use extremely long "script addresses". A number of potential issues have been found with the proposals thus far:
 
 
A number of potential issues have been found with the proposals thus far:
 
  
 
* CHV requires the scriptPubKey interacts with data from scriptSig which has not been push onto the stack
 
* CHV requires the scriptPubKey interacts with data from scriptSig which has not been push onto the stack
Line 77: Line 114:
 
* P2SH requires that standard templates become a mandatory part of the scripting language, meaning they can never be fully depreciated in future.
 
* P2SH requires that standard templates become a mandatory part of the scripting language, meaning they can never be fully depreciated in future.
  
All of the these solutions risk a fork in the blockchain and require at least 50% miners approval. This proposal requires no changes to the block validation rules and can be implemented immediately. However it only allows for the most common use cases of pay to script transactions and has limited flexibility. Additionally the resulting scriptPubKey is 3 bytes larger than the standard "pay to address" scriptPubKey in common use, the author does not believe this will significantly effect transaction fees.  
+
All of the these solutions risk a fork in the blockchain and require at least 50% miners approval. This proposal requires no changes to the block validation rules and can be implemented immediately. However it only allows for the most common use cases of pay to script transactions and has limited flexibility. Additionally the resulting scriptPubKey is 6 bytes larger than the standard "pay to address" scriptPubKey in common use.
  
 
==Backwards Compatibility==
 
==Backwards Compatibility==
  
This proposal is fully backward compatible.
+
Old clients will not relay transactions using the new template, however they will preform the same validation as new clients.
 +
 
 +
== M-of-3 ==
 +
 
 +
The following is not part of the specification for this proposal but it is worth mentioning that using the same technique you can support both M-of-2 and M-of-3 transactions.
 +
 
 +
  OP_2OVER OP_2OVER OP_DUP 3 OP_EQUAL OP_IF 8 OP_PICK OP_ADD OP_HASH256 OP_ENDIF OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
 +
 
 +
However this requires 14 bytes of additional op codes.
  
 
==See Also==
 
==See Also==
  
* https://bitcointalk.org/index.php?topic=46538
 
 
* The [[BIP 0013|Address format for Pay to Script Hash BIP]]
 
* The [[BIP 0013|Address format for Pay to Script Hash BIP]]
 
* M-of-N Multisignature Transactions [[BIP 0011|BIP 11]]
 
* M-of-N Multisignature Transactions [[BIP 0011|BIP 11]]
 +
 +
[[Category:BIP|D]]

Latest revision as of 18:22, 29 January 2012

  BIP: Unassigned
  Title: M-of-2 scriptPubKey
  Author: Ben Reeves <support@pi.uk.com>
  Status: Draft
  Type: Unassigned
  Created: 15-01-2012

Abstract

This BIP describes a new standard type of scriptPubKey designed to allow immediate use of split key wallets.

Motivation

The purpose of this proposal is to provide split key wallet functionality without requiring changes to block validation rules or risking a fork in the blockchain.

Specification

A new standard scriptPubKey will be defined:

  OP_2OVER OP_2OVER OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG

Redeemed by a new standard scriptSig

  OP_0  <sig> 1 [pubkey] [pubkey] 2

This proposal only supports A + B or A or B split key transactions.

Use Cases

  • Split key wallets
  • Escrow Services - The author does not believe that (A + B) or C scripts are required for escrow transactions. Both parties must trust the holder of C anyway so that party can instead hold both A and B. The holders of A and B can either reach an agreement themselves or party C can act as the final arbitrator using A and B together.

Example Execution

Stack Code
<sig> 1 [pubkey1] [pubkey2] 2 OP_2OVER OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 OP_2OVER OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] OP_2OVER OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] [pubkey2] 2 OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] <sumA> OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 [pubkey1] <hashA> OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 <sumB> OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 1 <HashB> OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 <sumC> OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 <scriptHashA> <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG
<sig> 1 [pubkey1] [pubkey2] 2 OP_CHECKMULTISIG
1

Where scriptHash must be constructed in the following manor:

scriptHash = RIPMED160(M + SH256(SHA256(pubKey2 + 2) + pubKey1));

(+ means addition not concatenation)

Security

Although it may appear insecure totalling the sum of the public keys the author does not believe this to be the case.

You could deduce the target value by looking at the the sum of M + pubKey1 + pubKey2 + N from a previous transaction.

uint256 target = Previously Redeemed M+P1+P2+N 
uint256 myKeyA = SHA256();
uint256 myBogusKeyB = 0;
int n = 2;
int m = 1;

Initially it might seem that you could use an A or B where B is a invalid key:

while(m + myKeyA + myBogusKeyB + n != target) {
  ++myBogusKeyB;
}

However the additional SHA256 operations prevent you from doing this:

myKeyA = SHA256(myKeyA);
while(m + myKeyA + SHA256(myBogusKeyB + n) != target) {
  ++myBogusKeyB;
}

Resulting in equal brute force time.

What does affect security is ability to adjust M (either 1 or 2) without needing to generate a new SHA256 pair. This effectively halves the key space to 2^255 keys however it is still far far out of the realm of brute force possibility. Regardless use of a 20 byte hash limits the key space to 2^160 so it actually has no effect on security at all.

Rationale

This BIP replaces BIP 16, ("/P2SH/").

There is a general consensus that multi signature transactions need to be implemented ASAP without requiring the use extremely long "script addresses". A number of potential issues have been found with the proposals thus far:

  • CHV requires the scriptPubKey interacts with data from scriptSig which has not been push onto the stack
  • OP_EVAL essentially makes the scripting language turing complete, something which Satoshi deliberately avoided during its design.
  • P2SH requires that standard templates become a mandatory part of the scripting language, meaning they can never be fully depreciated in future.

All of the these solutions risk a fork in the blockchain and require at least 50% miners approval. This proposal requires no changes to the block validation rules and can be implemented immediately. However it only allows for the most common use cases of pay to script transactions and has limited flexibility. Additionally the resulting scriptPubKey is 6 bytes larger than the standard "pay to address" scriptPubKey in common use.

Backwards Compatibility

Old clients will not relay transactions using the new template, however they will preform the same validation as new clients.

M-of-3

The following is not part of the specification for this proposal but it is worth mentioning that using the same technique you can support both M-of-2 and M-of-3 transactions.

  OP_2OVER OP_2OVER OP_DUP 3 OP_EQUAL OP_IF 8 OP_PICK OP_ADD OP_HASH256 OP_ENDIF OP_ADD OP_HASH256 OP_ADD OP_HASH256 OP_ADD OP_RIPEMD160 <scriptHash> OP_EQUALVERIFY OP_CHECKMULTISIG

However this requires 14 bytes of additional op codes.

See Also