From 38ea34dee5a1f029d3346176f1eed6a2b1adff16 Mon Sep 17 00:00:00 2001 From: Eric Lombrozo Date: Fri, 9 Oct 2015 15:59:07 -0400 Subject: Updated C++ library link and added acknowledgement. --- bip-0032.mediawiki | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/bip-0032.mediawiki b/bip-0032.mediawiki index 902a5eb..b5ab145 100644 --- a/bip-0032.mediawiki +++ b/bip-0032.mediawiki @@ -259,7 +259,7 @@ PyCoin (https://github.com/richardkiss/pycoin) is a suite of utilities for deali A Java implementation is available at https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java -A C++ implementation is available at https://github.com/CodeShark/CoinClasses/tree/master/tests/hdwallets +A C++ implementation is available at https://github.com/ciphrex/mSIGNA/blob/master/deps/CoinCore/src/hdkeys.h An Objective-C implementation is available at https://github.com/oleganza/CoreBitcoin/blob/master/CoreBitcoin/BTCKeychain.h @@ -281,4 +281,5 @@ A Haskell implementation is available at https://github.com/haskoin/haskoin toge * Gregory Maxwell for the original idea of type-2 deterministic wallets, and many discussions about it. * Alan Reiner for the implementation of this scheme in Armory, and the suggestions that followed from that. +* Eric Lombrozo for reviewing and revising this BIP. * Mike Caldwell for the version bytes to obtain human-recognizable Base58 strings. -- cgit v1.2.3 From 451260d6d906a8372675d39cd36e9a97aec089ce Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Fri, 16 Oct 2015 20:10:54 -0700 Subject: added bip122 --- bip-0122.mediawiki | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 47 insertions(+) create mode 100644 bip-0122.mediawiki diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki new file mode 100644 index 0000000..dc1c6d7 --- /dev/null +++ b/bip-0122.mediawiki @@ -0,0 +1,47 @@ +
+  BIP: 122
+  Title: Creation of new testnet for scaling experiments
+  Author: Chris Priest 
+  Status: Draft
+  Type: Standards Track
+  Created: 2015-10-16
+
+ +==Abstract== + +This BIP defines the creation of a new parallel text network called "ScaleNet", +which will be used to test the effects of massive scale upon the bitcoin +consensus protocol. + +==Motivation== + +Bitcoin was originally designed to be an experiment. With the increase in the market +cap, this experimental nature is decreased. There is considerable doubt whether +the Bitcoin consensus protocol can handle transaction rates orders of magnitude +higher than the network sees today. + +==Specification== + +The code for ScaleNet will resemble the current Bitcoin testnet code in every way possible. +The only difference will be the elimination of the blocksize limit. + +ScaleNet coins will have 0 monetary value, just like TestNet coins. + +There will also be a ScaleNet faucet that wil be used to automatically get free ScaleNet coins. + +==ScaleNet spammer== + +Along with the creation of the ScaleNet client, there will also be a piece of software +called the "ScaleNet Spammer Client". The purpose of this software is to simply send large amounts +of transactions to the network. This software works very much like how software used to "stress test" +the main Bitcoin network. + +==Lessons Hopefully learned== + +* What happens when the blockchain get too large to fit entirely onto a consumer grade hard drive? +* How will it be possible to run a full node when there are hundreds of GB of unconfirmed transactions in the mempool? +* What kind of special attention needs to go into mining gigantic blocks (>100MB) without through the roof orphan tares. + +Each of these questions will be answered by ScaleNet. At some point in time +bitcoin will need to face these problems. Hopefully the insights learned +from ScaleNet will help drive a more data-driven approach to Bitcoin Development. -- cgit v1.2.3 From 029bd7d178fb3f163de17cd1a1b16286190ec696 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Fri, 16 Oct 2015 20:11:56 -0700 Subject: typos --- bip-0122.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index dc1c6d7..b1576e7 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -40,7 +40,7 @@ the main Bitcoin network. * What happens when the blockchain get too large to fit entirely onto a consumer grade hard drive? * How will it be possible to run a full node when there are hundreds of GB of unconfirmed transactions in the mempool? -* What kind of special attention needs to go into mining gigantic blocks (>100MB) without through the roof orphan tares. +* What kind of special attention needs to go into mining gigantic blocks (>100MB) without through the roof orphan rates? Each of these questions will be answered by ScaleNet. At some point in time bitcoin will need to face these problems. Hopefully the insights learned -- cgit v1.2.3 From 6447c8df9e25df04e0e1b233a2fc69d61bb9fb4f Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Fri, 16 Oct 2015 20:14:09 -0700 Subject: more typos --- bip-0122.mediawiki | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index b1576e7..ea9c903 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -22,12 +22,12 @@ higher than the network sees today. ==Specification== -The code for ScaleNet will resemble the current Bitcoin testnet code in every way possible. +The code for ScaleNet will resemble the current Bitcoin TestNet code in every way possible. The only difference will be the elimination of the blocksize limit. ScaleNet coins will have 0 monetary value, just like TestNet coins. -There will also be a ScaleNet faucet that wil be used to automatically get free ScaleNet coins. +There will also be a ScaleNet faucet that will be used to automatically get free ScaleNet coins. ==ScaleNet spammer== -- cgit v1.2.3 From 478c14dc171a448bc5f216d34b4a39e3ad6ac1ed Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Fri, 16 Oct 2015 20:14:57 -0700 Subject: more typos --- bip-0122.mediawiki | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index ea9c903..7dceb07 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -29,14 +29,14 @@ ScaleNet coins will have 0 monetary value, just like TestNet coins. There will also be a ScaleNet faucet that will be used to automatically get free ScaleNet coins. -==ScaleNet spammer== +==ScaleNet Spammer== Along with the creation of the ScaleNet client, there will also be a piece of software called the "ScaleNet Spammer Client". The purpose of this software is to simply send large amounts of transactions to the network. This software works very much like how software used to "stress test" the main Bitcoin network. -==Lessons Hopefully learned== +==Lessons Hopefully Learned== * What happens when the blockchain get too large to fit entirely onto a consumer grade hard drive? * How will it be possible to run a full node when there are hundreds of GB of unconfirmed transactions in the mempool? -- cgit v1.2.3 From bd5e1ead70eed7aa3cb9398be73e761e96b36678 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Mon, 30 Nov 2015 16:40:31 -0800 Subject: added txver2 --- bip-tx-ver2.mediawiki | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 bip-tx-ver2.mediawiki diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki new file mode 100644 index 0000000..1051723 --- /dev/null +++ b/bip-tx-ver2.mediawiki @@ -0,0 +1,32 @@ +
+  BIP: 122
+  Title: Transaction Version 2 Specification (wildcard inputs)
+  Author: Chris Priest 
+  Status: Draft
+  Type: Standards Track
+  Created: 2015-11-30
+
+ +==Abstract== + +This specification defines a new type of transaction that supplements (not replaces) +version 1 transactions. + +==Motivation== + +Version 1 Bitcoin Transactions have one large inefficiency: When you want to spend +from multiple inputs with the exact same scriptPubKey, you have to list the same +signature multiple times. This bloats the transaction size and makes it expensive to spend +from small value inputs. + +Because small value inputs are expensive to send, they remain in the UTXO pool +which full nodes have to keep around. It is believed that long term increase of the UTXO +set can have negative scaling consequences on the network. + +==Specification== + +A version 2 transaction is formulated the exact same way as a version 1 transaction +with one exception: each input is treated as a "wildcard input". + +A wildcard input beings the value of all inputs with the exact same scriptPubKey +in a block lower or equal to the block the wildcard input is confirmed into. -- cgit v1.2.3 From a5093f1c4ab36a396644e4a12b64c344a9b95998 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Tue, 1 Dec 2015 13:14:55 -0800 Subject: added more stuff --- bip-tx-ver2.mediawiki | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki index 1051723..71cfa69 100644 --- a/bip-tx-ver2.mediawiki +++ b/bip-tx-ver2.mediawiki @@ -15,18 +15,21 @@ version 1 transactions. ==Motivation== Version 1 Bitcoin Transactions have one large inefficiency: When you want to spend -from multiple inputs with the exact same scriptPubKey, you have to list the same -signature multiple times. This bloats the transaction size and makes it expensive to spend -from small value inputs. +from multiple inputs with the exact same scriptSig, you have to list each +input separately, along with the same signature multiple times. +This bloats the transaction size and makes it expensive to spend from small value inputs. Because small value inputs are expensive to send, they remain in the UTXO pool which full nodes have to keep around. It is believed that long term increase of the UTXO set can have negative scaling consequences on the network. +If maximum blocksize is made to increase *slower* than the actual number of transactins bitcoin users are sending +to the network, this problem is projected to get worse. + ==Specification== A version 2 transaction is formulated the exact same way as a version 1 transaction with one exception: each input is treated as a "wildcard input". -A wildcard input beings the value of all inputs with the exact same scriptPubKey +A wildcard input beings the value of all inputs with the exact same scriptSig in a block lower or equal to the block the wildcard input is confirmed into. -- cgit v1.2.3 From bec0d9e8f64d0194eccca8a38f7a7aba7af913f2 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Wed, 2 Dec 2015 14:44:26 -0800 Subject: added 'needed to implement' section --- bip-tx-ver2.mediawiki | 29 ++++++++++++++++++++++++----- 1 file changed, 24 insertions(+), 5 deletions(-) diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki index 71cfa69..1478922 100644 --- a/bip-tx-ver2.mediawiki +++ b/bip-tx-ver2.mediawiki @@ -1,5 +1,5 @@
-  BIP: 122
+  BIP: (no number)
   Title: Transaction Version 2 Specification (wildcard inputs)
   Author: Chris Priest 
   Status: Draft
@@ -15,7 +15,7 @@ version 1 transactions.
 ==Motivation==
 
 Version 1 Bitcoin Transactions have one large inefficiency: When you want to spend
-from multiple inputs with the exact same scriptSig, you have to list each
+from multiple inputs with the exact same scriptPubKey, you have to list each
 input separately, along with the same signature multiple times.
 This bloats the transaction size and makes it expensive to spend from small value inputs.
 
@@ -23,13 +23,32 @@ Because small value inputs are expensive to send, they remain in the UTXO pool
 which full nodes have to keep around. It is believed that long term increase of the UTXO
 set can have negative scaling consequences on the network.
 
-If maximum blocksize is made to increase *slower* than the actual number of transactins bitcoin users are sending
-to the network, this problem is projected to get worse.
+If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending
+to the network, this problem is projected to get worse. In other words, as transaction
+fees increase, the minimum economical value of a spending a UTXO will increase.
 
 ==Specification==
 
 A version 2 transaction is formulated the exact same way as a version 1 transaction
 with one exception: each input is treated as a "wildcard input".
 
-A wildcard input beings the value of all inputs with the exact same scriptSig
+A wildcard input beings the value of all inputs with the exact same scriptPubKey
 in a block lower or equal to the block the wildcard input is confirmed into.
+
+== Changes needed to implement ==
+
+The bitcoin code needs to be modified in three places in order to handle Version 2 Transactions.
+
+1. **Full Node V2 validation** - When a full node receives a V2 transaction, it has to
+   aggregate the value of all the UTXOs in the blockchain older than the input
+   with the same scriptPubKey. If this value is greater than or equal to the
+   amount of all outputs, then that V2 transaction is valid and can be propagated.
+
+2. **Full Node V1 validation** - When a V1 transaction comes in, the code needs to be modified
+   to check if each inut has not been spent by a V2 transaction. If there exist any
+   V2 transaction in the blockchain with the same scriptPubKey *after* that input,
+   then the UTXO has been spent and the transaction is invalid.
+
+3. **Wallet** - The user facing wallet portion of the reference client should notify
+   the user when their wallet contains many UTXOs that qualify it to benefit from
+   a V2 transaction. Wallets should not simply replace V1 transactions with V2 transactions.
-- 
cgit v1.2.3


From 3ff75f1ad20ecea54d2db998a9f3218d7baf311e Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:32:24 -0800
Subject: added part about version field

---
 bip-tx-ver2.mediawiki | 46 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 35 insertions(+), 11 deletions(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index 1478922..f0a6811 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -1,6 +1,6 @@
 
   BIP: (no number)
-  Title: Transaction Version 2 Specification (wildcard inputs)
+  Title: "Coalescing Transaction" Specification (wildcard inputs)
   Author: Chris Priest 
   Status: Draft
   Type: Standards Track
@@ -10,13 +10,13 @@
 ==Abstract==
 
 This specification defines a new type of transaction that supplements (not replaces)
-version 1 transactions.
+normal "non coalescing" bitcoin transactions.
 
 ==Motivation==
 
-Version 1 Bitcoin Transactions have one large inefficiency: When you want to spend
+Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend
 from multiple inputs with the exact same scriptPubKey, you have to list each
-input separately, along with the same signature multiple times.
+input separately, along with the same signature multiple times, even though the signature expresses the same information.
 This bloats the transaction size and makes it expensive to spend from small value inputs.
 
 Because small value inputs are expensive to send, they remain in the UTXO pool
@@ -29,7 +29,30 @@ fees increase, the minimum economical value of a spending a UTXO will increase.
 
 ==Specification==
 
-A version 2 transaction is formulated the exact same way as a version 1 transaction
+=== Redefinition of Transaction version ===
+
+First, this bips redefines the version field on transactions. The first four bytes
+are defined as the version number, while the last four bytes are defined as the
+transaction type. Type "0000" denotes normal transactions, and "0001" defines
+coalescing transaction.
+
+Examples:
+
+version 1 transaction with normal inputs:
+`version: 10000000`
+
+version 2 transaction with normal inputs:
+`version: 20000000`
+
+version 2 transaction with coalescing inputs:
+`version: 20000001`
+
+Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all
+inputs present in the transaction.
+
+=== Wildcard inputs ====
+
+A coalescing transaction is formulated the exact same way as a version 1 transaction
 with one exception: each input is treated as a "wildcard input".
 
 A wildcard input beings the value of all inputs with the exact same scriptPubKey
@@ -39,16 +62,17 @@ in a block lower or equal to the block the wildcard input is confirmed into.
 
 The bitcoin code needs to be modified in three places in order to handle Version 2 Transactions.
 
-1. **Full Node V2 validation** - When a full node receives a V2 transaction, it has to
+1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to
    aggregate the value of all the UTXOs in the blockchain older than the input
    with the same scriptPubKey. If this value is greater than or equal to the
-   amount of all outputs, then that V2 transaction is valid and can be propagated.
+   amount of all outputs, then that coalescing transaction is valid and can be propagated.
 
-2. **Full Node V1 validation** - When a V1 transaction comes in, the code needs to be modified
-   to check if each inut has not been spent by a V2 transaction. If there exist any
-   V2 transaction in the blockchain with the same scriptPubKey *after* that input,
+2. **Full Node Non-Coalescing validation** - When a non-coalescing transaction comes in, the code needs to be modified
+   to check if each input has not been spent by a coalescing transaction. If there exist any
+   coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input,
    then the UTXO has been spent and the transaction is invalid.
 
 3. **Wallet** - The user facing wallet portion of the reference client should notify
    the user when their wallet contains many UTXOs that qualify it to benefit from
-   a V2 transaction. Wallets should not simply replace V1 transactions with V2 transactions.
+   a coalescing transaction. Wallets should not simply replace non-coalescing transactions
+   with coalescing transactions in all instances.
-- 
cgit v1.2.3


From 632bf072521efd394106ff6cb9a13e2210077611 Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:34:53 -0800
Subject: typo

---
 bip-tx-ver2.mediawiki | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index f0a6811..101842d 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -31,7 +31,7 @@ fees increase, the minimum economical value of a spending a UTXO will increase.
 
 === Redefinition of Transaction version ===
 
-First, this bips redefines the version field on transactions. The first four bytes
+First, this BIP redefines the version field on transactions. The first four bytes
 are defined as the version number, while the last four bytes are defined as the
 transaction type. Type "0000" denotes normal transactions, and "0001" defines
 coalescing transaction.
-- 
cgit v1.2.3


From d982c11f87bfd5fa97b8456c9f98d9c7909a9c00 Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:37:51 -0800
Subject: fixed formatting

---
 bip-tx-ver2.mediawiki | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index 101842d..b033954 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -63,16 +63,16 @@ in a block lower or equal to the block the wildcard input is confirmed into.
 The bitcoin code needs to be modified in three places in order to handle Version 2 Transactions.
 
 1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to
-   aggregate the value of all the UTXOs in the blockchain older than the input
-   with the same scriptPubKey. If this value is greater than or equal to the
-   amount of all outputs, then that coalescing transaction is valid and can be propagated.
+aggregate the value of all the UTXOs in the blockchain older than the input
+with the same scriptPubKey. If this value is greater than or equal to the
+amount of all outputs, then that coalescing transaction is valid and can be propagated.
 
 2. **Full Node Non-Coalescing validation** - When a non-coalescing transaction comes in, the code needs to be modified
-   to check if each input has not been spent by a coalescing transaction. If there exist any
-   coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input,
-   then the UTXO has been spent and the transaction is invalid.
+to check if each input has not been spent by a coalescing transaction. If there exist any
+coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input,
+then the UTXO has been spent and the transaction is invalid.
 
 3. **Wallet** - The user facing wallet portion of the reference client should notify
-   the user when their wallet contains many UTXOs that qualify it to benefit from
-   a coalescing transaction. Wallets should not simply replace non-coalescing transactions
-   with coalescing transactions in all instances.
+the user when their wallet contains many UTXOs that qualify it to benefit from
+a coalescing transaction. Wallets should not simply replace non-coalescing transactions
+with coalescing transactions in all instances.
-- 
cgit v1.2.3


From e97833688dc31c747ff0c3a9105fece26fbfa6e9 Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:40:01 -0800
Subject: removed reference to version 2

---
 bip-tx-ver2.mediawiki | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index b033954..f7b5942 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -60,7 +60,7 @@ in a block lower or equal to the block the wildcard input is confirmed into.
 
 == Changes needed to implement ==
 
-The bitcoin code needs to be modified in three places in order to handle Version 2 Transactions.
+The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions.
 
 1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to
 aggregate the value of all the UTXOs in the blockchain older than the input
-- 
cgit v1.2.3


From a07c8b62b30d501efcfee147bf1e69d4619b698d Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:40:38 -0800
Subject: formatting changes

---
 bip-tx-ver2.mediawiki | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index f7b5942..ca4cf90 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -39,18 +39,18 @@ coalescing transaction.
 Examples:
 
 version 1 transaction with normal inputs:
-`version: 10000000`
+``version: 10000000``
 
 version 2 transaction with normal inputs:
-`version: 20000000`
+``version: 20000000``
 
 version 2 transaction with coalescing inputs:
-`version: 20000001`
+``version: 20000001``
 
 Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all
 inputs present in the transaction.
 
-=== Wildcard inputs ====
+=== Wildcard inputs ===
 
 A coalescing transaction is formulated the exact same way as a version 1 transaction
 with one exception: each input is treated as a "wildcard input".
-- 
cgit v1.2.3


From f9d64e782b6ec5b8a8cfed4556791e7dbabf83d5 Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 14:41:46 -0800
Subject: formatting changes

---
 bip-tx-ver2.mediawiki | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki
index ca4cf90..b4ca8e8 100644
--- a/bip-tx-ver2.mediawiki
+++ b/bip-tx-ver2.mediawiki
@@ -39,13 +39,13 @@ coalescing transaction.
 Examples:
 
 version 1 transaction with normal inputs:
-``version: 10000000``
+    version: 10000000
 
 version 2 transaction with normal inputs:
-``version: 20000000``
+    version: 20000000
 
 version 2 transaction with coalescing inputs:
-``version: 20000001``
+    version: 20000001
 
 Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all
 inputs present in the transaction.
-- 
cgit v1.2.3


From bdd7c9ff76405b265af1f1822736cc95b0a44228 Mon Sep 17 00:00:00 2001
From: Chris Priest 
Date: Fri, 4 Dec 2015 15:48:37 -0800
Subject: renamed file

---
 bip-coalesc-wildcard.mediawiki | 78 ++++++++++++++++++++++++++++++++++++++++++
 bip-tx-ver2.mediawiki          | 78 ------------------------------------------
 2 files changed, 78 insertions(+), 78 deletions(-)
 create mode 100644 bip-coalesc-wildcard.mediawiki
 delete mode 100644 bip-tx-ver2.mediawiki

diff --git a/bip-coalesc-wildcard.mediawiki b/bip-coalesc-wildcard.mediawiki
new file mode 100644
index 0000000..b4ca8e8
--- /dev/null
+++ b/bip-coalesc-wildcard.mediawiki
@@ -0,0 +1,78 @@
+
+  BIP: (no number)
+  Title: "Coalescing Transaction" Specification (wildcard inputs)
+  Author: Chris Priest 
+  Status: Draft
+  Type: Standards Track
+  Created: 2015-11-30
+
+ +==Abstract== + +This specification defines a new type of transaction that supplements (not replaces) +normal "non coalescing" bitcoin transactions. + +==Motivation== + +Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend +from multiple inputs with the exact same scriptPubKey, you have to list each +input separately, along with the same signature multiple times, even though the signature expresses the same information. +This bloats the transaction size and makes it expensive to spend from small value inputs. + +Because small value inputs are expensive to send, they remain in the UTXO pool +which full nodes have to keep around. It is believed that long term increase of the UTXO +set can have negative scaling consequences on the network. + +If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending +to the network, this problem is projected to get worse. In other words, as transaction +fees increase, the minimum economical value of a spending a UTXO will increase. + +==Specification== + +=== Redefinition of Transaction version === + +First, this BIP redefines the version field on transactions. The first four bytes +are defined as the version number, while the last four bytes are defined as the +transaction type. Type "0000" denotes normal transactions, and "0001" defines +coalescing transaction. + +Examples: + +version 1 transaction with normal inputs: + version: 10000000 + +version 2 transaction with normal inputs: + version: 20000000 + +version 2 transaction with coalescing inputs: + version: 20000001 + +Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all +inputs present in the transaction. + +=== Wildcard inputs === + +A coalescing transaction is formulated the exact same way as a version 1 transaction +with one exception: each input is treated as a "wildcard input". + +A wildcard input beings the value of all inputs with the exact same scriptPubKey +in a block lower or equal to the block the wildcard input is confirmed into. + +== Changes needed to implement == + +The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. + +1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to +aggregate the value of all the UTXOs in the blockchain older than the input +with the same scriptPubKey. If this value is greater than or equal to the +amount of all outputs, then that coalescing transaction is valid and can be propagated. + +2. **Full Node Non-Coalescing validation** - When a non-coalescing transaction comes in, the code needs to be modified +to check if each input has not been spent by a coalescing transaction. If there exist any +coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, +then the UTXO has been spent and the transaction is invalid. + +3. **Wallet** - The user facing wallet portion of the reference client should notify +the user when their wallet contains many UTXOs that qualify it to benefit from +a coalescing transaction. Wallets should not simply replace non-coalescing transactions +with coalescing transactions in all instances. diff --git a/bip-tx-ver2.mediawiki b/bip-tx-ver2.mediawiki deleted file mode 100644 index b4ca8e8..0000000 --- a/bip-tx-ver2.mediawiki +++ /dev/null @@ -1,78 +0,0 @@ -
-  BIP: (no number)
-  Title: "Coalescing Transaction" Specification (wildcard inputs)
-  Author: Chris Priest 
-  Status: Draft
-  Type: Standards Track
-  Created: 2015-11-30
-
- -==Abstract== - -This specification defines a new type of transaction that supplements (not replaces) -normal "non coalescing" bitcoin transactions. - -==Motivation== - -Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend -from multiple inputs with the exact same scriptPubKey, you have to list each -input separately, along with the same signature multiple times, even though the signature expresses the same information. -This bloats the transaction size and makes it expensive to spend from small value inputs. - -Because small value inputs are expensive to send, they remain in the UTXO pool -which full nodes have to keep around. It is believed that long term increase of the UTXO -set can have negative scaling consequences on the network. - -If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending -to the network, this problem is projected to get worse. In other words, as transaction -fees increase, the minimum economical value of a spending a UTXO will increase. - -==Specification== - -=== Redefinition of Transaction version === - -First, this BIP redefines the version field on transactions. The first four bytes -are defined as the version number, while the last four bytes are defined as the -transaction type. Type "0000" denotes normal transactions, and "0001" defines -coalescing transaction. - -Examples: - -version 1 transaction with normal inputs: - version: 10000000 - -version 2 transaction with normal inputs: - version: 20000000 - -version 2 transaction with coalescing inputs: - version: 20000001 - -Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all -inputs present in the transaction. - -=== Wildcard inputs === - -A coalescing transaction is formulated the exact same way as a version 1 transaction -with one exception: each input is treated as a "wildcard input". - -A wildcard input beings the value of all inputs with the exact same scriptPubKey -in a block lower or equal to the block the wildcard input is confirmed into. - -== Changes needed to implement == - -The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. - -1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to -aggregate the value of all the UTXOs in the blockchain older than the input -with the same scriptPubKey. If this value is greater than or equal to the -amount of all outputs, then that coalescing transaction is valid and can be propagated. - -2. **Full Node Non-Coalescing validation** - When a non-coalescing transaction comes in, the code needs to be modified -to check if each input has not been spent by a coalescing transaction. If there exist any -coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, -then the UTXO has been spent and the transaction is invalid. - -3. **Wallet** - The user facing wallet portion of the reference client should notify -the user when their wallet contains many UTXOs that qualify it to benefit from -a coalescing transaction. Wallets should not simply replace non-coalescing transactions -with coalescing transactions in all instances. -- cgit v1.2.3 From e994fa264a7a9a854b4450d3e84f03a7858598c6 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Mon, 7 Dec 2015 15:55:42 -0800 Subject: fixed bolding --- bip-coalesc-wildcard.mediawiki | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/bip-coalesc-wildcard.mediawiki b/bip-coalesc-wildcard.mediawiki index b4ca8e8..c729d06 100644 --- a/bip-coalesc-wildcard.mediawiki +++ b/bip-coalesc-wildcard.mediawiki @@ -62,17 +62,17 @@ in a block lower or equal to the block the wildcard input is confirmed into. The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. -1. **Full Node Coalescing validation** - When a full node receives a coalescing transaction, it has to +1. Full Node Coalescing validation - When a full node receives a coalescing transaction, it has to aggregate the value of all the UTXOs in the blockchain older than the input with the same scriptPubKey. If this value is greater than or equal to the amount of all outputs, then that coalescing transaction is valid and can be propagated. -2. **Full Node Non-Coalescing validation** - When a non-coalescing transaction comes in, the code needs to be modified +2. Full Node Non-Coalescing validation - When a non-coalescing transaction comes in, the code needs to be modified to check if each input has not been spent by a coalescing transaction. If there exist any coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, then the UTXO has been spent and the transaction is invalid. -3. **Wallet** - The user facing wallet portion of the reference client should notify +3. Wallet - The user facing wallet portion of the reference client should notify the user when their wallet contains many UTXOs that qualify it to benefit from a coalescing transaction. Wallets should not simply replace non-coalescing transactions with coalescing transactions in all instances. -- cgit v1.2.3 From e36fba6978b72c4541a7288570ed623cf945294e Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Wed, 30 Dec 2015 15:51:11 -0800 Subject: added coalesce bip to new branch --- bip-coalesc-wildcard.mediawiki | 78 ----------------------------------------- bip-coalesce-wildcard.mediawiki | 78 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 78 insertions(+), 78 deletions(-) delete mode 100644 bip-coalesc-wildcard.mediawiki create mode 100644 bip-coalesce-wildcard.mediawiki diff --git a/bip-coalesc-wildcard.mediawiki b/bip-coalesc-wildcard.mediawiki deleted file mode 100644 index c729d06..0000000 --- a/bip-coalesc-wildcard.mediawiki +++ /dev/null @@ -1,78 +0,0 @@ -
-  BIP: (no number)
-  Title: "Coalescing Transaction" Specification (wildcard inputs)
-  Author: Chris Priest 
-  Status: Draft
-  Type: Standards Track
-  Created: 2015-11-30
-
- -==Abstract== - -This specification defines a new type of transaction that supplements (not replaces) -normal "non coalescing" bitcoin transactions. - -==Motivation== - -Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend -from multiple inputs with the exact same scriptPubKey, you have to list each -input separately, along with the same signature multiple times, even though the signature expresses the same information. -This bloats the transaction size and makes it expensive to spend from small value inputs. - -Because small value inputs are expensive to send, they remain in the UTXO pool -which full nodes have to keep around. It is believed that long term increase of the UTXO -set can have negative scaling consequences on the network. - -If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending -to the network, this problem is projected to get worse. In other words, as transaction -fees increase, the minimum economical value of a spending a UTXO will increase. - -==Specification== - -=== Redefinition of Transaction version === - -First, this BIP redefines the version field on transactions. The first four bytes -are defined as the version number, while the last four bytes are defined as the -transaction type. Type "0000" denotes normal transactions, and "0001" defines -coalescing transaction. - -Examples: - -version 1 transaction with normal inputs: - version: 10000000 - -version 2 transaction with normal inputs: - version: 20000000 - -version 2 transaction with coalescing inputs: - version: 20000001 - -Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all -inputs present in the transaction. - -=== Wildcard inputs === - -A coalescing transaction is formulated the exact same way as a version 1 transaction -with one exception: each input is treated as a "wildcard input". - -A wildcard input beings the value of all inputs with the exact same scriptPubKey -in a block lower or equal to the block the wildcard input is confirmed into. - -== Changes needed to implement == - -The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. - -1. Full Node Coalescing validation - When a full node receives a coalescing transaction, it has to -aggregate the value of all the UTXOs in the blockchain older than the input -with the same scriptPubKey. If this value is greater than or equal to the -amount of all outputs, then that coalescing transaction is valid and can be propagated. - -2. Full Node Non-Coalescing validation - When a non-coalescing transaction comes in, the code needs to be modified -to check if each input has not been spent by a coalescing transaction. If there exist any -coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, -then the UTXO has been spent and the transaction is invalid. - -3. Wallet - The user facing wallet portion of the reference client should notify -the user when their wallet contains many UTXOs that qualify it to benefit from -a coalescing transaction. Wallets should not simply replace non-coalescing transactions -with coalescing transactions in all instances. diff --git a/bip-coalesce-wildcard.mediawiki b/bip-coalesce-wildcard.mediawiki new file mode 100644 index 0000000..c729d06 --- /dev/null +++ b/bip-coalesce-wildcard.mediawiki @@ -0,0 +1,78 @@ +
+  BIP: (no number)
+  Title: "Coalescing Transaction" Specification (wildcard inputs)
+  Author: Chris Priest 
+  Status: Draft
+  Type: Standards Track
+  Created: 2015-11-30
+
+ +==Abstract== + +This specification defines a new type of transaction that supplements (not replaces) +normal "non coalescing" bitcoin transactions. + +==Motivation== + +Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend +from multiple inputs with the exact same scriptPubKey, you have to list each +input separately, along with the same signature multiple times, even though the signature expresses the same information. +This bloats the transaction size and makes it expensive to spend from small value inputs. + +Because small value inputs are expensive to send, they remain in the UTXO pool +which full nodes have to keep around. It is believed that long term increase of the UTXO +set can have negative scaling consequences on the network. + +If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending +to the network, this problem is projected to get worse. In other words, as transaction +fees increase, the minimum economical value of a spending a UTXO will increase. + +==Specification== + +=== Redefinition of Transaction version === + +First, this BIP redefines the version field on transactions. The first four bytes +are defined as the version number, while the last four bytes are defined as the +transaction type. Type "0000" denotes normal transactions, and "0001" defines +coalescing transaction. + +Examples: + +version 1 transaction with normal inputs: + version: 10000000 + +version 2 transaction with normal inputs: + version: 20000000 + +version 2 transaction with coalescing inputs: + version: 20000001 + +Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all +inputs present in the transaction. + +=== Wildcard inputs === + +A coalescing transaction is formulated the exact same way as a version 1 transaction +with one exception: each input is treated as a "wildcard input". + +A wildcard input beings the value of all inputs with the exact same scriptPubKey +in a block lower or equal to the block the wildcard input is confirmed into. + +== Changes needed to implement == + +The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. + +1. Full Node Coalescing validation - When a full node receives a coalescing transaction, it has to +aggregate the value of all the UTXOs in the blockchain older than the input +with the same scriptPubKey. If this value is greater than or equal to the +amount of all outputs, then that coalescing transaction is valid and can be propagated. + +2. Full Node Non-Coalescing validation - When a non-coalescing transaction comes in, the code needs to be modified +to check if each input has not been spent by a coalescing transaction. If there exist any +coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, +then the UTXO has been spent and the transaction is invalid. + +3. Wallet - The user facing wallet portion of the reference client should notify +the user when their wallet contains many UTXOs that qualify it to benefit from +a coalescing transaction. Wallets should not simply replace non-coalescing transactions +with coalescing transactions in all instances. -- cgit v1.2.3 From 3a41325f81e50c4d90cc04c5dec4c6f8b9ac6233 Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Wed, 30 Dec 2015 15:54:33 -0800 Subject: removed old bip --- bip-0122.mediawiki | 47 ----------------------------------------------- 1 file changed, 47 deletions(-) delete mode 100644 bip-0122.mediawiki diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki deleted file mode 100644 index 7dceb07..0000000 --- a/bip-0122.mediawiki +++ /dev/null @@ -1,47 +0,0 @@ -
-  BIP: 122
-  Title: Creation of new testnet for scaling experiments
-  Author: Chris Priest 
-  Status: Draft
-  Type: Standards Track
-  Created: 2015-10-16
-
- -==Abstract== - -This BIP defines the creation of a new parallel text network called "ScaleNet", -which will be used to test the effects of massive scale upon the bitcoin -consensus protocol. - -==Motivation== - -Bitcoin was originally designed to be an experiment. With the increase in the market -cap, this experimental nature is decreased. There is considerable doubt whether -the Bitcoin consensus protocol can handle transaction rates orders of magnitude -higher than the network sees today. - -==Specification== - -The code for ScaleNet will resemble the current Bitcoin TestNet code in every way possible. -The only difference will be the elimination of the blocksize limit. - -ScaleNet coins will have 0 monetary value, just like TestNet coins. - -There will also be a ScaleNet faucet that will be used to automatically get free ScaleNet coins. - -==ScaleNet Spammer== - -Along with the creation of the ScaleNet client, there will also be a piece of software -called the "ScaleNet Spammer Client". The purpose of this software is to simply send large amounts -of transactions to the network. This software works very much like how software used to "stress test" -the main Bitcoin network. - -==Lessons Hopefully Learned== - -* What happens when the blockchain get too large to fit entirely onto a consumer grade hard drive? -* How will it be possible to run a full node when there are hundreds of GB of unconfirmed transactions in the mempool? -* What kind of special attention needs to go into mining gigantic blocks (>100MB) without through the roof orphan rates? - -Each of these questions will be answered by ScaleNet. At some point in time -bitcoin will need to face these problems. Hopefully the insights learned -from ScaleNet will help drive a more data-driven approach to Bitcoin Development. -- cgit v1.2.3 From 14ce2bcead9748d472730d33f140abaaaa3b28fa Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Mon, 11 Jan 2016 05:02:19 -0500 Subject: Minor: Fix BIP65 status in README --- README.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/README.mediawiki b/README.mediawiki index dec53f9..fdfb988 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -252,7 +252,7 @@ Those proposing changes should consider that ultimately consent may rest with th | OP_CHECKLOCKTIMEVERIFY | Peter Todd | Standard -| Draft +| Accepted |- | [[bip-0066.mediawiki|66]] | Strict DER signatures -- cgit v1.2.3 From 858a4a70ea2dfde140c22e5535d1eabb182663b2 Mon Sep 17 00:00:00 2001 From: Johnson Lau Date: Mon, 11 Jan 2016 19:08:33 +0800 Subject: New commitment structure, sigop limits, etc --- bip-0141.mediawiki | 198 ++++++++++++++++++++++++++--------------------------- 1 file changed, 99 insertions(+), 99 deletions(-) diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki index ac44d87..7a5c28c 100644 --- a/bip-0141.mediawiki +++ b/bip-0141.mediawiki @@ -21,7 +21,7 @@ The entirety of the transaction's effects are determined by output consumption ( By removing this data from the transaction structure committed to the transaction merkle tree, several problems are fixed: -# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was authorized is no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach (BIP62): +# '''Nonintentional malleability becomes impossible'''. Since signature data is no longer part of the transaction hash, changes to how the transaction was signed are no longer relevant to transaction identification. As a solution of transaction malleability, this is superior to the canonical signature approach ([https://github.com/bitcoin/bips/edit/master/bip-0062.mediawiki BIP62]): #* It prevents involuntary transaction malleability for any type of scripts, as long as all inputs are signed (with at least one CHECKSIG or CHECKMULTISIG operation) #* In the case of an m-of-n CHECKMULTISIG script, a transaction is malleable only with agreement of m private key holders (as opposed to only 1 private key holder with BIP62) #* It prevents involuntary transaction malleability due to unknown ECDSA signature malleability @@ -30,106 +30,67 @@ By removing this data from the transaction structure committed to the transactio # '''Some constraints could be bypassed with a soft fork''' by moving part of the transaction data to a structure unknown to current protocol, for example: #* Size of witness could be ignored / discounted when calculating the block size, effectively increasing the block size to some extent #* Hard coded constants, such as maximum data push size (520 bytes) or sigops limit could be reevaluated or removed -#* New script system could be introduced without any limitation from the existing script semantic -# '''Additional data required for fraud proofs can be added to witness'''. Extra data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify. -#* Backlinks for the outputs spent by the transaction's inputs can be provided. These backlinks consist of a block hash and an offset that thin clients can easily query and check to verify that the outputs exist. -#* Sum trees for transaction inputs and outputs can be committed making it possible to construct short proofs that no new coins are created in any noncoinbase transaction and that the miner does not add excessive fees to the coinbase transaction. +#* New script system could be introduced without any limitation from the existing script semantic. For example, a new transaction digest algorithm for transaction signature verification is described in [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143] ==Specification== === Commitment structure === -!!!DRAFT ONLY!!! - -A new block rule is added which requires a commitment to the witness hashes in the coinbase (or an OP_RETURN output of a specific transaction, or somewhere else) - -(Hardfork after x year to move the commitment to block header?) - -Witness hash is the double SHA256 of a transaction including witnesses: http://blockhawk.net/diagrams/witnesstx.png. For the coinbase transaction, its witness hash is assumed to be 0x0000....0000. +A new block rule is added which requires a commitment to the witness hashes, the double SHA256 of a transaction including witnesses. The witness hash of coinbase transaction is assumed to be 0x0000....0000. A witness root hash is calculated with all those witness hashes as leaves, in a way similar to the hashMerkleRoot in the block header. -No witness data is allowed in blocks that don't commit to witness data, as this would otherwise leave room from spam. - -==== Proposal 1: balance tree (the current implementation) ==== -The commitment is a push of exactly 41 bytes: -*The first 4 bytes are commitment header: 0xaa21a9ed -*The next 4 bytes describe a nonce -*The next 1 byte is the "levels bytes", describes the number of levels in a Merkle tree (0 to 32) -*The next 32 bytes is a commitment root hash (not the witness root hash) - -Locator of the witness root hash is defined as: - -
SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)
- -The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. - -The coinbase's input's witness must consist of a single byte array of 32 * levels bytes, and are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. - -====Proposal 2: imbalance tree==== -The commitment is a push of exactly 40 bytes: -*The first 4 bytes are commitment header: 0xaa21a9ed -*The next 4 bytes describe a nonce -*The next 32 bytes is a commitment root hash (not the witness root hash) - -Locator of the witness root hash is defined as: +The commitment is recorded in a scriptPubKey of the coinbase transaction. It must be at least 38 bytes, with the first 6-byte of 0x6a24aa21a9ed, that is: + + 1-byte - OP_RETURN (0x6a) + 1-byte - Push the following 36 bytes (0x24) + 4-byte - Commitment header (0xaa21a9ed) + 32-byte - Commitment hash: Double-SHA256(witness root hash|witness nonce) + + 39th byte onwards: Optional data with no consensus meaning + +and the coinbase's input's witness must consist of a single 32-byte array for the witness nonce. -
SHA256('WitnessV1\x00\x00\x00\x00\x00\x00\x00' || nonce)
+If there are more than one scriptPubKey matching the pattern, the one with highest output index is assumed to be the commitment. -The first levels bits of locator, interpreted in little endian, are assumed to be the position in the leaves of the Merkle tree where the witness root hash goes. +=== Witness program === -The coinbase's input's witness must consist of a single byte array, which the size must be a multiple of 32 bytes but not bigger than 32*32 bytes. These are assumed to be the Merkle path to connect the witness root hash to the commitment root hash. Depth of the commitment is determined by the length of the path. If the depth of the tree is 0, the path should be represented by 0x00, and the witness root hash will be same as the commitment root hash. +A scriptPubKey (or redeemScript as defined in BIP16/P2SH) that consists of a 1-byte push opcode (for 0 to 16) followed by a data push between 2 and 32 bytes gets a new special meaning. The value of the first push is called the "version byte". The following byte vector pushed is called the "witness program". -=== Block size limit === -Blocks are currently limited to 1 MB total size. We change this restriction as follows: +New rules for scriptSig: +* In case the scriptPubKey pushes a version byte and witness program directly, the scriptSig must be exactly empty. +* In case the redeemScript pushes a version byte and witness program, the scriptSig must be exactly the single push of the redeemScript. -We define a base block size sb consisting of the existing header and transactions, a witness size sw consisting of only the size of the witness data, and a virtual block size sv = sb + sw/4. +If the version byte is 0, the witness program is the actual script: +* The script is executed after normal script evaluation but with data from the witness rather than the scriptSig. +* The program must not fail and must result in exactly a single TRUE on the stack. -The new rule is sv <= 1 MB. +If the version byte is 1, the witness program must be 32 bytes, as a SHA256 hash of the actual script: +* The witness must consist of an input stack to feed to the program, followed by the serialized program. +* The serialized program is popped off the initial witness stack. SHA256 of the serialized program must match the hash pushed in the witness program. +* The serialized program is deserialized, and executed after normal script evaluation with the remaining witness stack. +* The script must not fail, and result in exactly a single TRUE on the stack. +* If the witness program is between 2 and 31 bytes, the script must fail. -=== Witness program === +If the version byte is 2 to 16, no further interpretation of the witness program or witness happens. -* A scriptPubKey (or redeemScript as defined in BIP16/P2SH) that consists of a 1-byte push opcode (for 0 to 16) followed by a data push between 2 and 32 bytes gets a new special meaning. The value of the first push is called the "version byte". The following byte vector pushed is called the "witness program". -** In case the scriptPubKey pushes a version byte and witness program directly, the scriptSig must be exactly empty. -** In case the redeemScript pushes a version byte and witness program, the scriptSig must be exactly the single push of the redeemScript. +=== Other consensus critical limits === -** If the version byte is 0, the WP is the actual script. -*** The script is executed after normal script evaluation but with data from the witness rather than the scriptSig. -*** The program must not fail, and result in exactly a single TRUE on the stack. -** If the version byte is 1, the WP must be 32 bytes, as a SHA256 hash of the actual script. -*** The witness must consist of an input stack to feed to the program, followed by the serialized program. -*** The serialized program is popped off the initial witness stack. Hash of the serialized program must match the hash pushed in the witness program. -*** The serialized program is deserialized, and executed after normal script evaluation with the remaining witness stack. -*** The script must not fail, and result in exactly a single TRUE on the stack. -** If the version byte is 2 to 16, no further interpretation of the witness program or witness happens. +==== Block size ==== -=== Other consensus critical constraints === +Blocks are currently limited to 1,000,000 bytes (1MB) total size. We change this restriction as follows: -== Block size analysis == -WORK IN PROGRESS +''Block cost'' is defined. The cost of each byte in the existing header and transactions is 4, while the cost of each byte in witness data is 1. -Definitions: -
- Core block size (CBS): The block size as seen by a non-upgrading full node
- Witness size (WS): The total size of witness data in a block
- Total block size (TBS): CBS + WS
- Witness discount (WD): A discount factor for witness data in VBS calculation (1 = no discount)
- Virtual block size (VBS): CBS + (WS * WD)
- Witness adoption (WA): Proportion (in size) of new format transactions among all transactions
- Prunable ratio (PR): Proportion of signature data size in a transaction
-
+The new rule is total ''block cost'' ≤ 4,000,000. -With some transformation it could be shown that: -
- TBS = CBS / (1 - WA * PR)
-     = VBS / (1 - WA * PR * (1 - WD))
-
- -In order to keep the proposal as a soft fork, the CBS must not have a upper limit higher than 1MB. +==== Sigops ==== -The PR heavily depends on the transaction script type and input-output ratio. For example, the PR of 1-in 2-out P2PKH and 1-in 1-out 2-of-2 multisig P2SH are about 47% and 72% respectively. According to the data presented by Pieter Wuille on 7 December 2015, the current average PR on the blockchain is about 60%. +Sigops per block is currently limited to 20,000. We change this restriction as follows: +''Sigop cost'' is defined. The cost of a sigop in traditoinal script is 4, while the cost of a sigop in witness program is 1. +The new rule is total ''sigop cost'' ≤ 80,000. == Examples == @@ -139,15 +100,16 @@ The following example is a version 0 witness program, equivalent to the existing witness: scriptSig: (empty) - scriptPubKey: OP_0 <0x76A914{20-byte-hash-value}88AC> + scriptPubKey: 0 EQUALVERIFY CHECKSIG> + (0x001976A914{20-byte-hash}88AC) -The OP_0 indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: +The '0' indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: - DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG The script is executed with the data from witness - DUP HASH160 <20byte-hash-value> EQUALVERIFY CHECKSIG + DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG Comparing with a P2PKH output, the witness program equivalent occupies 2 more bytes in the scriptPubKey, while moving the signature and public key from scriptSig to witness. @@ -155,39 +117,57 @@ Comparing with a P2PKH output, the witness program equivalent occupies 2 more by The following example is an 1-of-2 multi-signature version 1 witness program. - witness: 0 <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> + witness: 0 <1 2 CHECKMULTISIG> scriptSig: (empty) - scriptPubKey: OP_1 <0x{32-byte-hash-value}> + scriptPubKey: 1 <32-byte-hash> + (0x5120{32-byte-hash}) -The OP_1 in scriptPubKey indicates the following push is a version 1 witness program. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash-value in scriptPubKey, and deserialized: +The '1' in scriptPubKey indicates the following push is a version 1 witness program. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash in scriptPubKey, and deserialized: - 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + 1 2 CHECKMULTISIG The script is executed with the remaining data from witness: - 0 1 <33-byte-pubkey1> <33-byte-pubkey2> 2 CHECKMULTISIG + 0 1 2 CHECKMULTISIG Since the actual program is larger than 32 bytes, it cannot be accommodated in a version 0 witness program. A version 1 witness program allows arbitrarily large script as the 520-byte push limit is bypassed. -The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of P2SH. The increased size improves security against possible collision attacks, as 2^80 work is not infeasible anymore (By the end of 2015, 2^84 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent P2SH output but is moved to witness. +The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of P2SH. The increased size improves security against possible collision attacks, as 280 work is not infeasible anymore (By the end of 2015, 284 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent P2SH output but is moved to witness. === Witness program nested in Pay-to-Script-Hash === The following example is the same 1-of-2 multi-signature version 1 witness program, but nested in a P2SH output. - witness: 0 <0x5121{33-byte-pubkey1}21{33-byte-pubkey2}52AE> - scriptSig: <0x5120{32-byte-hash-value}> - scriptPubKey: HASH160 <20-byte-hash-value> EQUAL + witness: 0 <1 2 CHECKMULTISIG> + scriptSig: <1 <32-byte-hash>> + (5120{32-byte-hash}) + scriptPubKey: HASH160 <20-byte-hash> EQUAL + (0x76A914{20-byte-hash}88AC) -The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash-value in scriptPubKey, and interpreted as: +The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash in scriptPubKey, and interpreted as: - OP_1 <0x{32-byte-hash-value}> + 1 <32-byte-hash> The version 1 witness program is then executed as described in the last example Comparing with the last example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig, which is not prunable in transmission. Although a nested witness program is less efficient in many ways, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. +=== Extensible commitment structure === + +The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce which currently has no consensus meaning, serves two purposes: + +* It allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in coinbase becomes: + + Double-SHA256(Witness root hash|Hash(new commitment|witness nonce)) + +:: For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. + +* Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, may utilize this witness nonce. However, they must not be committed directly as the nonce, or the external system may be forced to hardfork when Bitcoin introduces more consensus-critical commitments. Instead, they should use the nonce as the root of an extensible commitment tree, and should not make any assumption about the location and depth of their commitments in the tree. For example, in the external system, it may use a flag to indicate the actual location of the commitments with the Merkle paths provided. + +The optional data space following the commitment also leaves room for metadata of future softforks. + === Trust-free unconfirmed transaction dependency chain === + Segregated witness fixes the problem of transaction malleability fundamentally, which enables the building of unconfirmed transaction dependency chains in a trust-free manner. Two parties, Alice and Bob, may agree to send certain amount of Bitcoin to a 2-of-2 multisig output (the "funding transaction"). Without signing the funding transaction, they may create another transaction, time-locked in the future, spending the 2-of-2 multisig output to third account(s) (the "spending transaction"). Alice and Bob will sign the spending transaction and exchange the signatures. After examining the signatures, they will sign and commit the funding transaction to the blockchain. Without further action, the spending transaction will be confirmed after the lock-time and release the funding according to the original contract. It also retains the flexibility of revoking the original contract before the lock-time, by another spending transaction with shorter lock-time, but only with mutual-agreement of both parties. @@ -197,7 +177,9 @@ Such setups is not possible with BIP62 as the malleability fix, since the spendi Unconfirmed transaction dependency chain is a fundamental building block of more sophisticated payment networks, such as duplex micropayment channel and the Lightning Network, which have the potential to greatly improve the scalability and efficiency of the Bitcoin system. == Future extensions == + === Compact fraud proof for SPV nodes === + Bitcoin right now only has two real security models. A user either runs a full-node which validates every block with all rules in the system, or a SPV (Simple Payment Verification) client which only validates the headers as a proof of publication of some transactions. The Bitcoin whitepaper suggested that SPV nodes may accept alerts from full nodes when they detect an invalid block, prompting the SPV node to download the questioned blocks and transactions for validation. This approach, however, could become a DoS attack vector as there is virtually no cost to generate a false alarm. An alarm must come with a compact, yet deterministic fraud proof. In the current Bitcoin protocol, it is possible to generate compact fraud proof for almost all rules except a few: @@ -206,9 +188,15 @@ In the current Bitcoin protocol, it is possible to generate compact fraud proof # It is not possible to prove the violation of any block specific constraints, such as size and sigop limits, without showing the whole block (and all input transactions in the case of sigop limit) # It is not possible to prove the spending of a non-existing input without showing all transaction IDs in the blockchain way back to the genesis block. -It is possible to prove the first 2 types of fraud if a block is committed to a Merkle-sum-tree of the fee, size, and sigop count of each transaction. It is also possible to prove the last type of fraud if a block is committed to a Merkle tree with the originating block height and transaction index of all inputs. These commitments could be included in the extensible witness commitment through a soft fork and will be transparent to nodes that do not understand such new rules. +Extra witness data can be committed that allows short proofs of block invalidity that SPV nodes can quickly verify: + +# Sum trees for transaction fee can be committed making it possible to construct short proofs that the miner does not add excessive fees to the coinbase transaction. Similar for the block size and sigop count limit. +# Backlinks for the outputs spent by the transaction's inputs can be provided. These backlinks consist of a block hash and an offset that thin clients can easily query and check to verify that the outputs exist. + +These commitments could be included in the extensible commitment structure through a soft fork and will be transparent to nodes that do not understand such new rules. === New script system === + Since a version byte is pushed before a witness program, and programs with unknown versions are always considered as anyone-can-spend script, it is possible to introduce any new script system with a soft fork. The witness as a structure is not restricted by any existing script semantics and constraints, the 520-byte push limit in particular, and therefore allows arbitrarily large scripts and signatures. Examples of new script system include Schnorr signatures which reduce the size of multisig transactions dramatically, Lamport signature which is quantum computing resistance, and Merklized abstract syntax trees which allow very compact witness for conditional scripts with extreme complexity. @@ -216,23 +204,26 @@ Examples of new script system include Schnorr signatures which reduce the size o The 32-byte limitation for witness program could be easily extended through a soft fork in case a stronger hash function is needed in the future. The version byte is also expandable through a softfork. === Per-input lock-time and relative-lock-time === -Currently there is only one nLockTime field in a transaction and all inputs must share the same value. BIP68 enables per-input relative-lock-time using the nSequence field, however, with a limited lock-time period and resolution. -With a soft fork, it is possible to introduce a separate witness structure to allow per-input lock-time and relative-lock-time, and a new script system that could sign and manipulate the new data (like BIP65 and BIP112). +Currently there is only one nLockTime field in a transaction and all inputs must share the same value. [https://github.com/bitcoin/bips/edit/master/bip-0068.mediawiki BIP68] enables per-input relative-lock-time using the nSequence field, however, with a limited lock-time period and resolution. + +With a soft fork, it is possible to introduce a separate witness structure to allow per-input lock-time and relative-lock-time, and a new script system that could sign and manipulate the new data (like [https://github.com/bitcoin/bips/edit/master/bip-0065.mediawiki BIP65] and [https://github.com/bitcoin/bips/edit/master/bip-0112.mediawiki BIP112]). == Backward compatibility == + As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs as anyone-can-spend scripts (except a few edge cases in version 0 witness programs which are provably unspendable with original script semantics). Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. Non-upgraded nodes are strongly encouraged to upgrade in order to take advantage of the new features. '''What a non-upgraded wallet can do''' * Receiving bitcoin from non-upgraded and upgraded wallets * Sending bitcoin to non-upgraded wallets -* Sending bitcoin to upgraded wallets using a P2SH address (a less efficient way to use segregated witness) +* Sending bitcoin to upgraded wallets using a P2SH address (less efficient) +* Sending bitcoin to upgraded wallets using a native witness program (more efficient) through [https://github.com/bitcoin/bips/blob/master/bip-0070.mediawiki BIP70] payment protocol '''What a non-upgraded wallet cannot do''' * Validating segregated witness transaction. It assumes such a transaction is always valid -* Sending bitcoin to upgraded wallets using a native witness program (a more efficient way to use segregated witness) +* Sending bitcoin to upgraded wallets using a native witness program if BIP70 is not supported == Deployment == @@ -248,7 +239,6 @@ invalid, and all further blocks enforce the new rules. 1 which results in nVersion >= all prior IsSuperMajority() soft-forks and thus no bits in nVersion are permanently lost.) - === SPV Clients === While SPV clients are unable to fully validate blocks, @@ -258,10 +248,20 @@ nVersion >= 5 to prevent false confirmations from the remaining 5% of non-upgraded miners when the 95% threshold has been reached. == Credits == + Special thanks to Gregory Maxwell for originating many of the ideas in this BIP and Luke-Jr for figuring out how to deploy this as a soft fork. == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit + +https://github.com/sipa/bitcoin/commits/segwit2 + +== References == + +*[https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki BIP16 Pay to Script Hash] +*[https://github.com/bitcoin/bips/blob/master/bip-0142.mediawiki BIP142 Address Formats for Witness Program] +*[https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143 Transaction signature verification for version 0 and version 1 witness program] +*[https://github.com/bitcoin/bips/blob/master/bip-0144.mediawiki BIP144 Segregated Witness (Peer Services)] == Copyright == + This document is placed in the public domain. -- cgit v1.2.3 From ae529c3f0488fec6ebc335f2bdb0e623af6a6a5c Mon Sep 17 00:00:00 2001 From: Johnson Lau Date: Tue, 12 Jan 2016 03:09:50 +0800 Subject: Fix links in BIP142-144. Corrections in BIP142. --- bip-0142.mediawiki | 6 +++--- bip-0143.mediawiki | 6 +++--- bip-0144.mediawiki | 2 +- 3 files changed, 7 insertions(+), 7 deletions(-) diff --git a/bip-0142.mediawiki b/bip-0142.mediawiki index 7efeca7..fdf5202 100644 --- a/bip-0142.mediawiki +++ b/bip-0142.mediawiki @@ -19,8 +19,8 @@ To define standard payment addresses for native segwit transactions to promote e === P2PKH segwit address === -The first new Bitcoin address format defined is specific to pay-to-public-key-hash segwit transaction. The scriptPubKey is a single push of version-0 witness program in this form, - <0x0076A914{20-byte-hash-value}88AC> +The first new Bitcoin address format defined is specific to pay-to-public-key-hash segwit transaction. The scriptPubKey is an OP_0 followed by a push of version 0 witness program: + OP_0 EQUALVERIFY CHECKSIG> The new address is encoded exactly in the same way as the original pay-to-public-key-hash address: base58-encode: [1-byte version][20-byte-hash-value][4-byte checksum] Version byte is 0x19 for a main-network address, 0x41 for a testnet address. The following 20-byte is the public key hash. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and public key hash. @@ -151,7 +151,7 @@ From arbitrary witness program to general segwit address: https://gist.github.co * [[bip-0013.mediawiki|BIP 13: Address Format for pay-to-script-hash]] * [[bip-0016.mediawiki|BIP 16: Pay to Script Hash (aka "/P2SH/")]] -* [[bip-xxxx.mediawiki|BIP x: Segregated Witness]] https://github.com/bitcoin/bips/pull/265 +* [[bip-0141.mediawiki|BIP 141: Segregated Witness]] == Copyright == This work is placed in the public domain. diff --git a/bip-0143.mediawiki b/bip-0143.mediawiki index 276e2cb..4aca2db 100644 --- a/bip-0143.mediawiki +++ b/bip-0143.mediawiki @@ -19,7 +19,7 @@ Unfortunately, there are at least 2 weaknesses in the original transaction diges * For the verification of each signature, the amount of data hashing is proportional to the size of the transaction. Therefore, data hashing grows in O(n2) as the number of sigops in a transaction increases. While a 1 MB block would normally take 2 seconds to verify with an average computer in 2015, a 1MB transaction with 5569 sigops may take 25 seconds to verify. This could be fixed by optimizing the digest algorithm by introducing some reusable “midstate”, so the time complexity becomes O(n). [https://web.nvd.nist.gov/view/vuln/detail?vulnId=CVE-2013-2292 CVE-2013-2292][https://bitcointalk.org/?topic=140078 New Bitcoin vulnerability: A transaction that takes at least 3 minutes to verify][http://rusty.ozlabs.org/?p=522 The Megatransaction: Why Does It Take 25 Seconds?] * The algorithm does not involve the amount of Bitcoin being spent by the input. This is usually not a problem for online network nodes as they could request for the specified transaction to acquire the output value. For an offline transaction signing device ("cold wallet"), however, the unknowing of input amount makes it impossible to calculate the exact amount being spent and the transaction fee. To cope with this problem a cold wallet must also acquire the full transaction being spent, which could be a big obstacle in the implementation of lightweight, air-gapped wallet. By including the input value of part of the transaction digest, a cold wallet may safely sign a transaction by learning the value from an untrusted source. In the case that a wrong value is provided and signed, the signature would be invalid and no funding might be lost. [https://bitcointalk.org/index.php?topic=181734.0 SIGHASH_WITHINPUTVALUE: Super-lightweight HW wallets and offline data] -Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. [https://github.com/CodeShark/bips/blob/segwit/bip-codeshark-jl2012-segwit.mediawiki BIPx: Segregated Witness (Consensus layer)] +Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141: Segregated Witness (Consensus layer)] == Specification == A new transaction digest algorithm is defined, but only applicable to sigops in version 0 and version 1 witness program: @@ -114,7 +114,7 @@ Refer to the reference implementation, reproduced below, for the precise algorit == Deployment == -This proposal is deployed with Segregated Witness softfork (BIP x) +This proposal is deployed with Segregated Witness softfork (BIP 141) == Backward compatibility == @@ -122,7 +122,7 @@ As a soft fork, older software will continue to operate without modification. No == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit +https://github.com/sipa/bitcoin/commits/segwit2 == References == diff --git a/bip-0144.mediawiki b/bip-0144.mediawiki index ed8cf2b..e3843a8 100644 --- a/bip-0144.mediawiki +++ b/bip-0144.mediawiki @@ -12,7 +12,7 @@ This BIP defines new messages and serialization formats for propagation of transactions and blocks committing to segregated witness structures. ==Motivation== -In addition to defining witness structures and requiring commitments in future blocks (BIPxxxx - Consensus segwit BIP), new mechanisms must be defined to allow peers to advertise support for segregated witness and to relay the witness structures and request them from other peers without breaking compatibility with older nodes. +In addition to defining witness structures and requiring commitments in future blocks ([https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141] - Consensus segwit BIP), new mechanisms must be defined to allow peers to advertise support for segregated witness and to relay the witness structures and request them from other peers without breaking compatibility with older nodes. ==Specification== -- cgit v1.2.3 From 63fcb73ab7a9e005ec996e2bd87631fc56655fbd Mon Sep 17 00:00:00 2001 From: Dr Washington Sanchez Date: Tue, 12 Jan 2016 13:37:03 +1000 Subject: Fixes - Spelling mistakes - Change in the deployment model - Corrected my acknowledgement to Austin 'Williams' --- bip-0107.mediawiki | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/bip-0107.mediawiki b/bip-0107.mediawiki index 88a2c99..4e96173 100644 --- a/bip-0107.mediawiki +++ b/bip-0107.mediawiki @@ -16,11 +16,11 @@ This BIP proposes a dynamic limit to the block size based on transaction volume. Over the next few years, large infrastructure investments will be made into: # Improving global network connectivity -# Improving block propogation across the Bitcoin network +# Improving block propagation across the Bitcoin network # Layer 2 services and networks for off-chain transactions # General efficiency improvements to transactions and the blockchain -* While there is a consensus between Bitcoin developers, miners, businesses and users that the block size needs to be increased, there is a lingering concern over the potential unintended consequences that may agument the trend towards network and mining centralization (largely driven by mining hardware such as ASICs) and thereby threaten the security of the network. +* While there is a consensus between Bitcoin developers, miners, businesses and users that the block size needs to be increased, there is a lingering concern over the potential unintended consequences that may augment the trend towards network and mining centralization (largely driven by mining hardware such as ASICs) and thereby threaten the security of the network. * In contrast, failing to respond to elevated on-chain transaction volume may lead to a consumer-failure of Bitcoin, where ordinary users - having enjoyed over 6 years of submitting transactions on-chain at relatively low cost - will be priced out of blockchain with the emergence of a prohibitive 'fee market'. * These two concerns must be delicately balanced so that all users can benefit from a robust, scalable, and neutral network. @@ -44,7 +44,7 @@ Over the next few years, large infrastructure investments will be made into: ** limitfreerelay also helps counter attempts to trigger a block size increase by 'penny-flooding' For example: -* When the dynamic rules for increasing the block size go live on January 1st 2020, the starting maximum block size wil be 6 MB +* When the dynamic rules for increasing the block size go live on January 1st 2020, the starting maximum block size will be 6 MB * IF >=3025 blocks are >= 3.6 MB, the new maximum block size become 6.6 MB. * The theoretical maximum block size at the end of 2020 would be ~20.7 MB, assuming all 13 increases are triggered every 4 weeks by the end of the year. @@ -59,7 +59,7 @@ For example: *** Setting the parameter too high may set the trigger sensitivity too low, causing transaction delays that are trying to be avoided in the first place *** Between September 2013-2015, the standard deviation measured from average block size (n=730 data points from blockchain.info) was ~ 0.13 MB or 13% of the maximum block size **** If blocks needed to be 90% full before an increase were triggered, normal variance in the average block size would mean some blocks would be full before an increase could be triggered -*** Therefore, we need a ''safe distance'' away from the maximum block size to avoid normal block size variance hitting the limit. The 60% level represents a 3 standard deviation distrance from the limit. +*** Therefore, we need a ''safe distance'' away from the maximum block size to avoid normal block size variance hitting the limit. The 60% level represents a 3 standard deviation distance from the limit. ** Why 3025 blocks? *** The assessment period is 4032 blocks or ~ 4 weeks, with the threshold set as 4032 blocks/0.75 + 1 *** Increases in the maximum block size should only occur after a sustained trend can be observed in order to: @@ -67,16 +67,16 @@ For example: ***# Increase the cost to trigger an increase by spam attacks or miner collusion with zero fee transactions *** In other words, increases to the maximum block size must be conservative but meaningful to relieve transaction volume pressure in response to true market demand ** Why 10% increase in the block size? -*** Increases in the block size are designed to be conservative and in balance with the number of theoretical opportunitites to increase the block size per year +*** Increases in the block size are designed to be conservative and in balance with the number of theoretical opportunities to increase the block size per year *** Makes any resources spent for spam attacks or miner collusion relatively expensive to achieve a minor increase in the block size. A sustained attack would need to be launched that may be too costly, and ideally detectable by the community ==Deployment== -''From BIP66:'' -We reuse the double-threshold switchover mechanism from BIP 34, with the same thresholds, but for nVersion = ''n''. The new rules are in effect for every block (at height H) with nVersion = ''n'' and at least 750 out of 1000 blocks preceding it (with heights H-1000..H-1) also have nVersion = ''n''. Furthermore, when 950 out of the 1000 blocks preceding a block do have nVersion = ''n'', nVersion = ''n-1'' blocks become invalid, and all further blocks enforce the new rules. +Similar deployment model to BIP101: +
Activation is achieved when 750 of 1,000 consecutive blocks in the best chain have a version number with the first, second, third, and thirtieth bits set (0x20000007 in hex). The activation time will be the timestamp of the 750'th block plus a two week (1,209,600 second) grace period to give any remaining miners or services time to upgrade to support larger blocks.
==Acknowledgements== -Thanks to Austin Hill, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. +Thanks to Austin Williams, Brian Hoffman, Angel Leon, Bulukani Mlalazi, Chris Pacia, and Ryan Shea for their comments. ==Copyright== -- cgit v1.2.3 From 07b73c67dfa99cb13bf9e95dbbc3cad8d938936a Mon Sep 17 00:00:00 2001 From: Marco Pontello Date: Tue, 12 Jan 2016 16:46:52 +0100 Subject: added ABNF grammar --- bip-0122.mediawiki | 14 +++++++++++++- 1 file changed, 13 insertions(+), 1 deletion(-) diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index 902aa02..d025873 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -23,7 +23,7 @@ The same happens with posts and messages that reference some particular txs or b The URI follow this form: - blockchain:[//chain] + blockchain:[//]// Where: @@ -52,6 +52,18 @@ Where: | |} +====ABNF grammar==== + +
+blockchainuri = "blockchain:" ["//" chain] "/" object
+object = ("tx" "/" hash ) / ( "block" "/" (hash / blockheight ) ) /
+         ( "address" "/" address )
+chain = hash
+hash = 64HEXDIG
+blockheight = 1*15DIGIT ; 15 is somehow arbitrary, i.e. a "small" int.
+address = base58 ; https://en.wikipedia.org/wiki/Base58
+
+ ---- ===Definition of chain ID=== -- cgit v1.2.3 From 628a851062abbad73df8f48e3cd45dcffbdec914 Mon Sep 17 00:00:00 2001 From: MarcoPon Date: Tue, 12 Jan 2016 19:09:57 +0100 Subject: More consistent spacing. --- bip-0122.mediawiki | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/bip-0122.mediawiki b/bip-0122.mediawiki index d025873..d59e353 100644 --- a/bip-0122.mediawiki +++ b/bip-0122.mediawiki @@ -56,8 +56,8 @@ Where:
 blockchainuri = "blockchain:" ["//" chain] "/" object
-object = ("tx" "/" hash ) / ( "block" "/" (hash / blockheight ) ) /
-         ( "address" "/" address )
+object = ("tx" "/" hash) / ("block" "/" (hash / blockheight)) /
+         ("address" "/" address)
 chain = hash
 hash = 64HEXDIG
 blockheight = 1*15DIGIT ; 15 is somehow arbitrary, i.e. a "small" int.
@@ -121,4 +121,4 @@ Thanks to Richard Moore, Matt Whitlock, Andreas Schildbach for suggestions about
 
 ==Copyright==
 
-This document is placed in the public domain.
\ No newline at end of file
+This document is placed in the public domain.
-- 
cgit v1.2.3


From a8ace6d608b2068ce949993d4dd048fd759820ce Mon Sep 17 00:00:00 2001
From: Eric Lombrozo 
Date: Tue, 12 Jan 2016 19:06:32 -0500
Subject: Added BIP 124

---
 README.mediawiki   |   6 +++
 bip-0124.mediawiki | 123 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 129 insertions(+)
 create mode 100644 bip-0124.mediawiki

diff --git a/README.mediawiki b/README.mediawiki
index fdfb988..d9d0e32 100644
--- a/README.mediawiki
+++ b/README.mediawiki
@@ -386,6 +386,12 @@ Those proposing changes should consider that ultimately consent may rest with th
 | Informational
 | Draft
 |-
+| [[bip-0124.mediawiki|124]]
+| Hierarchical Deterministic Script Templates
+| Eric Lombrozo, William Swanson
+| Informational
+| Draft
+|-
 | [[bip-0125.mediawiki|125]]
 | Opt-in Full Replace-by-Fee Signaling
 | David Harding, Peter Todd
diff --git a/bip-0124.mediawiki b/bip-0124.mediawiki
new file mode 100644
index 0000000..1c98db8
--- /dev/null
+++ b/bip-0124.mediawiki
@@ -0,0 +1,123 @@
+
+  BIP:     BIP-124
+  Title:   Hierarchical Deterministic Script Templates
+  Authors: Eric Lombrozo , William Swanson
+  Status:  Draft
+  Type:    Informational
+  Created: 2015-11-20
+
+  Post-History: http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-November/011795.html
+
+ +==Abstract== + +This BIP defines a script template format that can be used by wallets to deterministically generate scripts with specific authorization policies using the key derivation mechanism defined in BIP32. + +==Motivation== + +Currently existing wallets typically issue scripts in only a tiny handful of widely used formats. The most popular formats are pay-to-pubkey-hash and m-of-n pay-to-script-hash (BIP16). However, different wallets tend to use mutually incompatible derivation schemes to generate signing keys and construct scripts from them. Moreover, with the advent of hashlocked and timelocked contracts (BIP65, BIP112), it is necessary for different wallets to be able to cooperatively generate even more sophisticated scripts. + +In addition, there's a lot of ongoing work in the development of multilayered protocols that use the blockchain as a settlement layer (i.e. the Lightning Network). These efforts require sufficiently generalized templates to allow for rapidly evolving script designs. + +This BIP provides a generalized format for constructing a script template that guarantees that different wallets will all produce the same scripts for a given set of derivation paths according to BIP32. + +==Specification== + +===Keys=== + +An individual key is determined by a BIP32 derivation path and an index. For convenience, we introduce the following notation: + +'''A'''k = (derivation path for A)/k + +===Key Groups=== + +Let '''m'''i denote distinct BIP32 derivation paths. We define a key group of n keys as a set of key derivation paths with a free index k: + +{'''K'''k} = { '''m'''1/k, '''m'''2/k, '''m'''3/k, ..., '''m'''n/k } + +Key groups are useful for constructing scripts that are symmetric in a set of keys. Scripts are symmetric in a set of keys if the semantics of the script is unaffected by permutations of the keys. Key groups enforce a canonical form and can improve privacy. + +===Sorting=== + +We define a lexicographic sorting of the keys. (TODO: specification of sorting conventions - compressed pubkeys, encoding, etc...) + +Define {'''K'''k}j to be the jth element of the sorted keys for derivation index k. + +===Script Templates=== + +We construct script templates by inserting placeholders for data into a script. To denote a placeholder, we use the following notation: + +''Script''('''A''') = opcodes ['''A'''] opcodes + +We extend this notation to an arbitrary number of placeholders: + +''Script''('''X1''', '''X2''', ..., '''Xn''') = opcodes ['''X1'''] opcodes ['''X2'''] opcodes ... opcodes ['''Xn'''] opcodes + +We introduce the following convenient notation for sorted key groups: + +[{'''K'''k}] = [{'''K'''k}1] [{'''K'''k}2] ... [{'''K'''k}n] + +===Operations on Keys=== + +In some applications, we might want to insert the result of some operation performed on a key rather than the key itself into the script. For example, we might want to insert a Hash160 of key '''A'''k. We can use the following notation: + +[''Hash160''('''A'''k)] + +===Encoding=== + +TODO + +==Examples== + +===2-of-3 Multisig=== + +The script template is defined by: + +''Script''('''X''') = 2 ['''X'''] 3 OP_CHECKMULTISIG + +Letting '''K'''k = { '''m'''1/k, '''m'''2/k, '''m'''3/k }, the ''k''th script for this key group is denoted by ''Script''({'''K'''k}). + +===1-of-1 or 2-of-3=== + +The script template is defined by: + +''Script''('''A''', '''B''') =
+        OP_DUP ['''A'''] OP_CHECKSIG
+        OP_NOTIF
+                2 ['''B'''] 3 OP_CHECKMULTISIGVERIFY
+        OP_NOTIF
+        OP_ENDIF
+        OP_TRUE
+ +Let '''M'''k = '''m'''/k be a key of a superuser that can authorize all transactions and {'''K'''k} be a key group of three users that can only authorize transactions if at least two of them agree. + +The ''k''th script is given by ''Script''('''M'''k, {'''K'''k}). + +===Timelocked Contract=== + +The output is payable to Alice immediately if she knows the private key for '''A'''k. Bob must know the private key for '''B'''k and also wait for a timeout '''t''' before being able to spend the output. + +The script template is defined by: + +''Script''('''A''', '''B''', '''T''') =
+        OP_IF
+                OP_DUP OP_HASH160 [''Hash160''('''A''')] OP_EQUALVERIFY OP_CHECKSIG
+        OP_ELSE
+                ['''T'''] OP_CHECKLOCKTIMEVERIFY OP_DROP
+                OP_DUP OP_HASH160 [''Hash160''('''B''')] OP_EQUALVERIFY OP_CHECKSIG
+        OP_ENDIF + +The ''k''th script with timeout '''t''' is given by ''Script''('''A'''k, '''B'''k, '''t'''). + +==References== + +* [[bip-0016.mediawiki|BIP16 - Pay to Script Hash]] +* [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] +* [[bip-0065.mediawiki|BIP65 - OP_CHECKLOCKTIMEVERIFY]] +* [[bip-0112.mediawiki|BIP112 - CHECKSEQUENCEVERIFY]] +* [[https://lightning.network/lightning-network-paper.pdf|Lightning Network Whitepaper]] + +==Copyright== + +This document is placed in the public domain. + -- cgit v1.2.3 From fd6789cfc8674b1fd582dc7323b07abb2733b4e9 Mon Sep 17 00:00:00 2001 From: Eric Lombrozo Date: Tue, 12 Jan 2016 19:16:46 -0500 Subject: Added BIP 83 --- README.mediawiki | 6 ++++ bip-0083.mediawiki | 92 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+) create mode 100644 bip-0083.mediawiki diff --git a/README.mediawiki b/README.mediawiki index fdfb988..0df3d28 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -302,6 +302,12 @@ Those proposing changes should consider that ultimately consent may rest with th | Standard | Draft |- +| [[bip-0083.mediawiki|83]] +| Dynamic Hierarchical Deterministic Key Trees +| Eric Lombrozo +| Standard +| Draft +|- | [[bip-0099.mediawiki|99]] | Motivation and deployment of consensus rule changes ([soft/hard]forks) | Jorge Timón diff --git a/bip-0083.mediawiki b/bip-0083.mediawiki new file mode 100644 index 0000000..d1da645 --- /dev/null +++ b/bip-0083.mediawiki @@ -0,0 +1,92 @@ +
+  BIP:     BIP-83
+  Title:   Dynamic Hierarchical Deterministic Key Trees
+  Author:  Eric Lombrozo 
+  Status:  Draft
+  Type:    Standard
+  Created: 2015-11-16
+
+ +==Abstract== + +This BIP defines a scheme for key derivation that allows for dynamic creation of key hierarchies based on the algorithm described in BIP32. + +==Motivation== + +Several proposals have been made to try to standardize a structure for hierarchical deterministic wallets for the sake of interoperability (reference BIP32, BIP44, BIP45). However, all proposals to date have tried to impose a specific structure upfront without providing any flexibility for dynamic creation of new hierarchical levels with different semantics or mapping between different applications that use distinct structures. + +Instead of attempting to impose a specific structure upfront, this BIP proposes that we design the derivation in such a way that we can continue extending hierarchies arbitrarily and indefinitely. + +==Specification== + +BIP32 provides a hierarchical derivation scheme where every node in the tree can be either used to derive child nodes or used as a signing key for ECDSA. This means that as soon as we choose to use a node as a signing key, we can no longer derive children from that node. To draw an analogy to file systems, each node is either a file or a directory but never both. However, given the need to predictably know the location of new children, it is generally not a good idea to mix both signing keys and parent nodes at the same level in the hierarchy. This means that as soon as we've decided that a particular level in the hierarchy is to be used for signing keys, we've lost the ability to nest deeper levels into the tree. + +At every level of the hierarchy, we reserve the child with index 0 to allow further nesting, and for signing key parent nodes use child indices 1 to MAX_INDEX (231 - 1) for signing keys. We can use either hardened or nonhardened derivation. + +Let p denote a specific signing key parent node and k be an index greater than 0. The children signing keys are then: + +p / k + +with k > 0. + +To create sublevels, we derive the nested nodes: + +p / 0 / n + +with n ≥ 0. + +Each of these nodes can now contain signing key children of their own, and again we reserve index 0 to allow deeper nesting. + +==Notation== + +We propose the following shorthand for writing nested node derivations: + +p // n instead of p / 0 / n + +p //' n instead of p / 0' / n + +==Mappings== + +Rather than specifying upfront which path is to be used for a specific purpose (i.e. external invoicing vs. internal change), different applications can specify arbitrary parent nodes and derivation paths. This allows for nesting of sublevels to arbitrary depth with application-specified semantics. Rather than trying to specify use cases upfront, we leave the design completely open-ended. Different applications can exchange these mappings for interoperability. Eventually, if certain mappings become popular, application user interfaces can provide convenient shortcuts or use them as defaults. + +Note that BIP32 suggests reserving child 0 for the derivation of signing keys rather than sublevels. It is not really necessary to reserve signing key parents, however, as each key's parent's path can be explicitly stated. But unless we reserve a child for sublevel derivation, we lose the ability to nest deeper levels into the hierarchy. While we could reserve any arbitrary index for nesting sublevels, reserving child 0 seems simplest to implement, leaving all indices > 0 for contiguously indexed signing keys. We could also use MAX_INDEX (231 - 1) for this purpose. However, we believe doing so introduces more ideosyncracies into the semantics and will present a problem if we ever decide to extend the scheme to use indices larger than 31 bits. + +==Use Cases== + +===Account Hierarchies=== + +For all that follows, we assume that key indices k > 0 and parent node indices n ≥ 0. + +From a master seed m, we can construct a default account using the following derivations for nonhardened signing keys: + +m / 1 / k (for change/internal outputs) + +m / 2 / k (for invoice/external outputs) + +To create subaccount an, we use: + +an = m // n + +To generate keys for subaccount an, we use: + +an / 1 / k (for change/internal outputs) + +an / 2 / k (for invoice/external outputs) + +We can continue creating subaccounts indefinitely using this scheme. + +===Bidirectional Payment Channels=== + +In order to create a bidirectional payment channel, it is necessary that previous commitments be revokable. In order to revoke previous commitments, each party reveals a secret to the other that would allow them to steal the funds in the channel if a transaction for a previous commitment is inserted into the blockchain. + +By allowing for arbitrary nesting of sublevels, we can construct decision trees of arbitrary depth and revoke an entire branch by revealing a parent node used to derive all the children. + +==References== + +* [[bip-0032.mediawiki|BIP32 - Hierarchical Deterministic Wallets]] +* [[https://lightning.network/lightning-network-paper.pdf|Lightning Network Whitepaper]] + +==Copyright== + +This document is placed in the public domain. + -- cgit v1.2.3 From 5574301656f61142e45540e33dbe88b397a89a93 Mon Sep 17 00:00:00 2001 From: Peter Todd Date: Wed, 13 Jan 2016 14:52:18 -0500 Subject: Remove merge-mining suggest re: witness nonce --- bip-0141.mediawiki | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki index 7a5c28c..6474256 100644 --- a/bip-0141.mediawiki +++ b/bip-0141.mediawiki @@ -154,15 +154,14 @@ Comparing with the last example, the scriptPubKey is 11 bytes smaller (with redu === Extensible commitment structure === -The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce which currently has no consensus meaning, serves two purposes: +The new commitment in coinbase transaction is a hash of the witness root hash and a witness nonce. The nonce currently has no consensus meaning, but in the future allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in +coinbase becomes: -* It allows new commitment values for future softforks. For example, if a new consensus-critical commitment is required in the future, the commitment in coinbase becomes: - Double-SHA256(Witness root hash|Hash(new commitment|witness nonce)) :: For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. -* Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, may utilize this witness nonce. However, they must not be committed directly as the nonce, or the external system may be forced to hardfork when Bitcoin introduces more consensus-critical commitments. Instead, they should use the nonce as the root of an extensible commitment tree, and should not make any assumption about the location and depth of their commitments in the tree. For example, in the external system, it may use a flag to indicate the actual location of the commitments with the Merkle paths provided. +Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, MUST NOT use the witness nonce to preserve the ability to do upgrades of the Bitcoin consensus protocol. The optional data space following the commitment also leaves room for metadata of future softforks. -- cgit v1.2.3 From d6dfcf167b8d568be2d671014ca7377356d1a74e Mon Sep 17 00:00:00 2001 From: BtcDrak Date: Fri, 15 Jan 2016 22:14:45 +0000 Subject: Update reference implementation for BIP68 --- bip-0068.mediawiki | 265 +++++++++++++++++++++++++++++------------------------ 1 file changed, 143 insertions(+), 122 deletions(-) diff --git a/bip-0068.mediawiki b/bip-0068.mediawiki index 55905af..e93d748 100644 --- a/bip-0068.mediawiki +++ b/bip-0068.mediawiki @@ -49,139 +49,160 @@ The block produced time is equal to the median-time-past of its previous block. When the relative lock-time is block-based, it is interpreted as a minimum block-height constraint over the input's age. A relative block-based lock-time of zero indicates an input which can be included in any block. More generally, a relative block lock-time n can be included n blocks after the mining date of the output it is spending, or any block thereafter. -This is proposed to be accomplished by replacing IsFinalTx() and CheckFinalTx(), existing consensus and non-consensus code functions that return true if a transaction's lock-time constraints are satisfied and false otherwise, with LockTime() and CheckLockTime(), new functions that return a non-zero value if a transaction's lock-time or sequence number constraints are not satisfied and zero otherwise: +==Implementation== + +A reference implementation is provided by the following pull request + +https://github.com/bitcoin/bitcoin/pull/7184
-    enum {
-        /* Interpret sequence numbers as relative lock-time constraints. */
-        LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
-    };
-    
-    /* Setting nSequence to this value for every input in a transaction
-     * disables nLockTime. */
-    static const uint32_t SEQUENCE_FINAL = 0xffffffff;
-    
-    /* If this flag set, CTxIn::nSequence is NOT interpreted as a
-     * relative lock-time. Setting the most significant bit of a
-     * sequence number disabled relative lock-time. */
-    static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31);
+enum {
+    /* Interpret sequence numbers as relative lock-time constraints. */
+    LOCKTIME_VERIFY_SEQUENCE = (1 << 0),
+};
     
-    /* If CTxIn::nSequence encodes a relative lock-time and this flag
-     * is set, the relative lock-time has units of 512 seconds,
-     * otherwise it specifies blocks with a granularity of 1. */
-    static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22);
+/* Setting nSequence to this value for every input in a transaction
+ * disables nLockTime. */
+static const uint32_t SEQUENCE_FINAL = 0xffffffff;
     
-    /* If CTxIn::nSequence encodes a relative lock-time, this mask is
-     * applied to extract that lock-time from the sequence field. */
-    static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff;
+/* If this flag set, CTxIn::nSequence is NOT interpreted as a
+ * relative lock-time. Setting the most significant bit of a
+ * sequence number disabled relative lock-time. */
+static const uint32_t SEQUENCE_LOCKTIME_DISABLE_FLAG = (1 << 31);
     
-    /* In order to use the same number of bits to encode roughly the
-     * same wall-clock duration, and because blocks are naturally
-     * limited to occur every 600s on average, the minimum granularity
-     * for time-based relative lock-time is fixed at 512 seconds.
-     * Converting from CTxIn::nSequence to seconds is performed by
-     * multiplying by 512 = 2^9, or equivalently shifting up by
-     * 9 bits. */
-    static const int SEQUENCE_LOCKTIME_GRANULARITY = 9;
+/* If CTxIn::nSequence encodes a relative lock-time and this flag
+ * is set, the relative lock-time has units of 512 seconds,
+ * otherwise it specifies blocks with a granularity of 1. */
+static const uint32_t SEQUENCE_LOCKTIME_TYPE_FLAG = (1 << 22);
     
-    int64_t LockTime(const CTransaction &tx, int flags, const std::vector* prevHeights, const CBlockIndex& block)
-    {
-        assert(prevHeights == NULL || prevHeights->size() == tx.vin.size());
-        int64_t nBlockTime = (flags & LOCKTIME_MEDIAN_TIME_PAST)
-                                        ? block.GetAncestor(std::max(block.nHeight-1, 0))->GetMedianTimePast()
-                                        : block.GetBlockTime();
-
-        bool fEnforceBIP68 = static_cast(tx.nVersion) >= 2
-                          && flags & LOCKTIME_VERIFY_SEQUENCE;
-        
-        // Will be set to the equivalent height- and time-based nLockTime
-        // values that would be necessary to satisfy all relative lock-
-        // time constraints given our view of block chain history.
-        int nMinHeight = 0;
-        int64_t nMinTime = 0;
-        // Will remain equal to true if all inputs are finalized
-        // (CTxIn::SEQUENCE_FINAL).
-        bool fFinalized = true;
-        for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
-            const CTxIn& txin = tx.vin[txinIndex];
-            // Set a flag if we witness an input that isn't finalized.
-            if (txin.nSequence == CTxIn::SEQUENCE_FINAL)
-                continue;
-            else
-                fFinalized = false;
+/* If CTxIn::nSequence encodes a relative lock-time, this mask is
+ * applied to extract that lock-time from the sequence field. */
+static const uint32_t SEQUENCE_LOCKTIME_MASK = 0x0000ffff;
     
-            // Do not enforce sequence numbers as a relative lock time
-            // unless we have been instructed to, and a view has been
-            // provided.
-            if (!fEnforceBIP68)
-                continue;
+/* In order to use the same number of bits to encode roughly the
+ * same wall-clock duration, and because blocks are naturally
+ * limited to occur every 600s on average, the minimum granularity
+ * for time-based relative lock-time is fixed at 512 seconds.
+ * Converting from CTxIn::nSequence to seconds is performed by
+ * multiplying by 512 = 2^9, or equivalently shifting up by
+ * 9 bits. */
+static const int SEQUENCE_LOCKTIME_GRANULARITY = 9;
     
-            // Sequence numbers with the most significant bit set are not
-            // treated as relative lock-times, nor are they given any
-            // consensus-enforced meaning at this point.
-            if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG)
-                continue;
-    
-            if (prevHeights == NULL)
-                continue;
-        
-            int nCoinHeight = (*prevHeights)[txinIndex];
-        
-            if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) {
-            
-                int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast();
-            
-                // Time-based relative lock-times are measured from the
-                // smallest allowed timestamp of the block containing the
-                // txout being spent, which is the median time past of the
-                // block prior.
-                nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1);
-            } else {
-                // We subtract 1 from relative lock-times because a lock-
-                // time of 0 has the semantics of "same block," so a lock-
-                // time of 1 should mean "next block," but nLockTime has
-                // the semantics of "last invalid block height."
-                nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1);
-            }
+/**
+ * Calculates the block height and time which the transaction must be later than
+ * in order to be considered final in the context of BIP 68.  It also removes
+ * from the vector of input heights any entries which did not correspond to sequence
+ * locked inputs as they do not affect the calculation.
+ */
+static std::pair CalculateSequenceLocks(const CTransaction &tx, int flags, std::vector* prevHeights, const CBlockIndex& block)
+{
+    assert(prevHeights->size() == tx.vin.size());
+
+    // Will be set to the equivalent height- and time-based nLockTime
+    // values that would be necessary to satisfy all relative lock-
+    // time constraints given our view of block chain history.
+    // The semantics of nLockTime are the last invalid height/time, so
+    // use -1 to have the effect of any height or time being valid.
+    int nMinHeight = -1;
+    int64_t nMinTime = -1;
+
+    // tx.nVersion is signed integer so requires cast to unsigned otherwise
+    // we would be doing a signed comparison and half the range of nVersion
+    // wouldn't support BIP 68.
+    bool fEnforceBIP68 = static_cast(tx.nVersion) >= 2
+                      && flags & LOCKTIME_VERIFY_SEQUENCE;
+
+    // Do not enforce sequence numbers as a relative lock time
+    // unless we have been instructed to
+    if (!fEnforceBIP68) {
+        return std::make_pair(nMinHeight, nMinTime);
+    }
+
+    for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) {
+        const CTxIn& txin = tx.vin[txinIndex];
+
+        // Sequence numbers with the most significant bit set are not
+        // treated as relative lock-times, nor are they given any
+        // consensus-enforced meaning at this point.
+        if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_DISABLE_FLAG) {
+            // The height of this input is not relevant for sequence locks
+            (*prevHeights)[txinIndex] = 0;
+            continue;
         }
-    
-        // If all sequence numbers are CTxIn::SEQUENCE_FINAL, the
-        // transaction is considered final and nLockTime constraints
-        // are not enforced.
-        if (fFinalized)
-            return 0;
-
-        if ((int64_t)tx.nLockTime < LOCKTIME_THRESHOLD)
-            nMinHeight = std::max(nMinHeight, (int)tx.nLockTime);
-        else
-            nMinTime = std::max(nMinTime, (int64_t)tx.nLockTime);
-    
-        if (nMinHeight >= block.nHeight)
-            return nMinHeight;
-            
-        if (nMinTime >= nBlockTime)
-            return nMinTime;
-    
-        return 0;
-    }
- -Code conditional on the return value of IsFinalTx() / CheckLockTime() has to be updated as well, since the semantics of the return value has been inverted. - -==Example: Bidirectional payment channel== -A bidirectional payment channel can be established by two parties funding a single output in the following way: Alice funds a 1 BTC output which is the 2-of-2 multisig of Alice AND Bob, or Alice's key only after a sufficiently long timeout, e.g. 30 days or 4320 blocks. The channel-generating transaction is signed by Alice and broadcast to the network. - -Alice desires to send Bob a payment of 0.1 BTC. She does so by constructing a transaction spending the 1 BTC output and sending 0.1 BTC to Bob and 0.9 BTC back to herself. She provides her signature for the 2-of-2 multisig constraint, and sets a relative lock-time using the sequence number field such that the transaction will become valid 24-hours or 144 blocks before the refund timeout. Two more times Alice sends Bob a payment of 0.1 BTC, each time generating and signing her half of a transaction spending the 1btc output and sending 0.2 BTC, then 0.3 BTC to Bob with a relative lock-time of 29 days from creation of the channel. - -Bob now desires to send Alice a refund of 0.25 BTC. He does so by constructing a transaction spending the 1btc output and sending 0.95 BTC (= 0.7 BTC + 0.25 BTC) to Alice and 0.05 BTC to himself. Since Bob will still have in his logs the transaction giving him 0.7 BTC 29 days after the creation of the channel, Alice demands that this new transaction have a relative lock-time of 28 days so she has a full day to broadcast it before the next transaction matures. - -Alice and Bob continue to make payments to each other, decrementing the relative lock-time by one day each time the channel switches direction, until the present time is reached or either party desires to close out the channel. A close-out is performed by finalizing the input (nSequence = MAX_INT) and both parties signing. - -==Implementation== - -A reference implementation is provided by the following pull request + int nCoinHeight = (*prevHeights)[txinIndex]; + + if (txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) { + int64_t nCoinTime = block.GetAncestor(std::max(nCoinHeight-1, 0))->GetMedianTimePast(); + + // Time-based relative lock-times are measured from the + // smallest allowed timestamp of the block containing the + // txout being spent, which is the median time past of the + // block prior. + nMinTime = std::max(nMinTime, nCoinTime + (int64_t)((txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) << CTxIn::SEQUENCE_LOCKTIME_GRANULARITY) - 1); + } else { + // We subtract 1 from relative lock-times because a lock- + // time of 0 has the semantics of "same block," so a lock- + // time of 1 should mean "next block," but nLockTime has + // the semantics of "last invalid block height." + nMinHeight = std::max(nMinHeight, nCoinHeight + (int)(txin.nSequence & CTxIn::SEQUENCE_LOCKTIME_MASK) - 1); + } + } + + return std::make_pair(nMinHeight, nMinTime); +} + +static bool EvaluateSequenceLocks(const CBlockIndex& block, std::pair lockPair) +{ + int64_t nBlockTime = block.pprev ? block.pprev->GetMedianTimePast() : 0; + if (lockPair.first >= block.nHeight || lockPair.second >= nBlockTime) + return false; + + return true; +} + +bool SequenceLocks(const CTransaction &tx, int flags, std::vector* prevHeights, const CBlockIndex& block) +{ + return EvaluateSequenceLocks(block, CalculateSequenceLocks(tx, flags, prevHeights, block)); +} + +bool CheckSequenceLocks(const CTransaction &tx, int flags) +{ + AssertLockHeld(cs_main); + + CBlockIndex* tip = chainActive.Tip(); + CBlockIndex index; + index.pprev = tip; + // CheckSequenceLocks() uses chainActive.Height()+1 to evaluate + // height based locks because when SequenceLocks() is called within + // CBlock::AcceptBlock(), the height of the block *being* + // evaluated is what is used. Thus if we want to know if a + // transaction can be part of the *next* block, we need to call + // SequenceLocks() with one more than chainActive.Height(). + index.nHeight = tip->nHeight + 1; + + // pcoinsTip contains the UTXO set for chainActive.Tip() + CCoinsViewMemPool viewMemPool(pcoinsTip, mempool); + std::vector prevheights; + prevheights.resize(tx.vin.size()); + for (size_t txinIndex = 0; txinIndex < tx.vin.size(); txinIndex++) { + const CTxIn& txin = tx.vin[txinIndex]; + CCoins coins; + if (!viewMemPool.GetCoins(txin.prevout.hash, coins)) { + return error("%s: Missing input", __func__); + } + if (coins.nHeight == MEMPOOL_HEIGHT) { + // Assume all mempool transaction confirm in the next block + prevheights[txinIndex] = tip->nHeight + 1; + } else { + prevheights[txinIndex] = coins.nHeight; + } + } -https://github.com/bitcoin/bitcoin/pull/6312 + std::pair lockPair = CalculateSequenceLocks(tx, flags, &prevheights, index); + return EvaluateSequenceLocks(index, lockPair); +} +
==Acknowledgments== -- cgit v1.2.3 From 752e73c4205c981951df3feb7a7ed23eb3d5ef8b Mon Sep 17 00:00:00 2001 From: Chris Priest Date: Sat, 16 Jan 2016 08:02:18 -0800 Subject: added copyright --- bip-coalesce-wildcard.mediawiki | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/bip-coalesce-wildcard.mediawiki b/bip-coalesce-wildcard.mediawiki index c729d06..4c3a557 100644 --- a/bip-coalesce-wildcard.mediawiki +++ b/bip-coalesce-wildcard.mediawiki @@ -76,3 +76,7 @@ then the UTXO has been spent and the transaction is invalid. the user when their wallet contains many UTXOs that qualify it to benefit from a coalescing transaction. Wallets should not simply replace non-coalescing transactions with coalescing transactions in all instances. + +==Copyright== + +This document is placed in the public domain. -- cgit v1.2.3 From ea49ecb4fbf05b5f9dec3d79cbea47fa35ed27dc Mon Sep 17 00:00:00 2001 From: Johnson Lau Date: Thu, 14 Jan 2016 12:38:17 +0800 Subject: New witness program definition --- bip-0141.mediawiki | 88 ++++++++++++++++++++++++++++-------------------------- 1 file changed, 45 insertions(+), 43 deletions(-) diff --git a/bip-0141.mediawiki b/bip-0141.mediawiki index 7a5c28c..a12151b 100644 --- a/bip-0141.mediawiki +++ b/bip-0141.mediawiki @@ -61,18 +61,22 @@ New rules for scriptSig: * In case the scriptPubKey pushes a version byte and witness program directly, the scriptSig must be exactly empty. * In case the redeemScript pushes a version byte and witness program, the scriptSig must be exactly the single push of the redeemScript. -If the version byte is 0, the witness program is the actual script: -* The script is executed after normal script evaluation but with data from the witness rather than the scriptSig. -* The program must not fail and must result in exactly a single TRUE on the stack. - -If the version byte is 1, the witness program must be 32 bytes, as a SHA256 hash of the actual script: -* The witness must consist of an input stack to feed to the program, followed by the serialized program. -* The serialized program is popped off the initial witness stack. SHA256 of the serialized program must match the hash pushed in the witness program. -* The serialized program is deserialized, and executed after normal script evaluation with the remaining witness stack. +If the version byte is 0, and the witness program is 20 bytes, +* It is interpreted as a pay-to-witness-public-key-hash (P2WPKH) program. +* The witness must consist of exactly 2 items. The first one is a signature, and the second one is a public key. +* HASH160 of the public key must match the 20-byte witness program. +* After normal script evaluation, the signature is verified against the public key with CHECKSIG operation. The verification must result in a single TRUE on the stack. + +If the version byte is 0, and the witness program is 32 bytes, +* It is interpreted as a pay-to-witness-script-hash (P2WSH) program. +* The witness must consist of an input stack to feed to the script, followed by a serialized script. +* The serialized script is popped off the initial witness stack. SHA256 of the serialized script must match the 32-byte witness program. +* The serialized script is deserialized, and executed after normal script evaluation with the remaining witness stack. * The script must not fail, and result in exactly a single TRUE on the stack. -* If the witness program is between 2 and 31 bytes, the script must fail. -If the version byte is 2 to 16, no further interpretation of the witness program or witness happens. +If the version byte is 0, but the witness program is neither 20 nor 32 bytes, the script must fail. + +If the version byte is 1 to 16, no further interpretation of the witness program or witness happens. === Other consensus critical limits === @@ -94,35 +98,33 @@ The new rule is total ''sigop cost'' ≤ 80,000. == Examples == -=== Version 0 witness program === +=== P2WPKH witness program === -The following example is a version 0 witness program, equivalent to the existing Pay-to-Pubkey-Hash (P2PKH) output. +The following example is a version 0 pay-to-witness-public-key-hash (P2WPKH) witness program: witness: scriptSig: (empty) - scriptPubKey: 0 EQUALVERIFY CHECKSIG> - (0x001976A914{20-byte-hash}88AC) - -The '0' indicates the following push is a version 0 witness program. The witness program is deserialized and becomes: + scriptPubKey: 0 <20-byte-hash> + (0x0014{20-byte-hash}) - DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG +The '0' in scriptPubKey indicates the following push is a version 0 witness program. The length of the witness program indicates that it is a P2WPKH type. The witness must consist of exactly 2 items. The HASH160 of the pubkey in witness must match the witness program. -The script is executed with the data from witness +The signature is verified as - DUP HASH160 <20-byte-hash> EQUALVERIFY CHECKSIG + CHECKSIG -Comparing with a P2PKH output, the witness program equivalent occupies 2 more bytes in the scriptPubKey, while moving the signature and public key from scriptSig to witness. +Comparing with a traditional P2PKH output, the P2WPKH equivalent occupies 3 less bytes in the scriptPubKey, and moves the signature and public key from scriptSig to witness. -=== Version 1 witness program === +=== P2WSH witness program === -The following example is an 1-of-2 multi-signature version 1 witness program. +The following example is an 1-of-2 multi-signature version 0 pay-to-witness-script-hash (P2WSH) witness program. witness: 0 <1 2 CHECKMULTISIG> scriptSig: (empty) - scriptPubKey: 1 <32-byte-hash> - (0x5120{32-byte-hash}) + scriptPubKey: 0 <32-byte-hash> + (0x0020{32-byte-hash}) -The '1' in scriptPubKey indicates the following push is a version 1 witness program. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash in scriptPubKey, and deserialized: +The '0' in scriptPubKey indicates the following push is a version 0 witness program. The length of the witness program indicates that it is a P2WSH type. The last item in the witness is popped off, hashed with SHA256, compared against the 32-byte-hash in scriptPubKey, and deserialized: 1 2 CHECKMULTISIG @@ -130,27 +132,27 @@ The script is executed with the remaining data from witness: 0 1 2 CHECKMULTISIG -Since the actual program is larger than 32 bytes, it cannot be accommodated in a version 0 witness program. A version 1 witness program allows arbitrarily large script as the 520-byte push limit is bypassed. +A P2WSH witness program allows arbitrarily large script as the 520-byte push limit is bypassed. -The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of P2SH. The increased size improves security against possible collision attacks, as 280 work is not infeasible anymore (By the end of 2015, 284 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent P2SH output but is moved to witness. +The scriptPubKey occupies 34 bytes, as opposed to 23 bytes of BIP16 P2SH. The increased size improves security against possible collision attacks, as 280 work is not infeasible anymore (By the end of 2015, 284 hashes have been calculated in Bitcoin mining since the creation of Bitcoin). The spending script is same as the one for an equivalent BIP16 P2SH output but is moved to witness. -=== Witness program nested in Pay-to-Script-Hash === +=== Witness program nested in BIP16 P2SH === -The following example is the same 1-of-2 multi-signature version 1 witness program, but nested in a P2SH output. +The following example is the same 1-of-2 multi-signature P2WSH witness program, but nested in a BIP16 P2SH output. witness: 0 <1 2 CHECKMULTISIG> - scriptSig: <1 <32-byte-hash>> - (5120{32-byte-hash}) + scriptSig: <0 <32-byte-hash>> + (0x0020{32-byte-hash}) scriptPubKey: HASH160 <20-byte-hash> EQUAL - (0x76A914{20-byte-hash}88AC) + (0xA914{20-byte-hash}87) The only item in scriptSig is hashed with HASH160, compared against the 20-byte-hash in scriptPubKey, and interpreted as: - 1 <32-byte-hash> + 0 <32-byte-hash> -The version 1 witness program is then executed as described in the last example +The P2WSH witness program is then executed as described in the previous example -Comparing with the last example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig, which is not prunable in transmission. Although a nested witness program is less efficient in many ways, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. +Comparing with the previous example, the scriptPubKey is 11 bytes smaller (with reduced security) while witness is the same. However, it also requires 35 bytes in scriptSig, which is not prunable in transmission. Although a nested witness program is less efficient in many ways, its payment address is fully transparent and backward compatible for all Bitcoin reference client since version 0.6.0. === Extensible commitment structure === @@ -160,11 +162,11 @@ The new commitment in coinbase transaction is a hash of the witness root hash an Double-SHA256(Witness root hash|Hash(new commitment|witness nonce)) -:: For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. +For backward compatibility, the Hash(new commitment|witness nonce) will go to the coinbase witness, and the witness nonce will be recorded in another location specified by the future softfork. Any number of new commitment could be added in this way. * Any commitments that are not consensus-critical to Bitcoin, such as merge-mining, may utilize this witness nonce. However, they must not be committed directly as the nonce, or the external system may be forced to hardfork when Bitcoin introduces more consensus-critical commitments. Instead, they should use the nonce as the root of an extensible commitment tree, and should not make any assumption about the location and depth of their commitments in the tree. For example, in the external system, it may use a flag to indicate the actual location of the commitments with the Merkle paths provided. -The optional data space following the commitment also leaves room for metadata of future softforks. +The optional data space following the commitment also leaves room for metadata of future softforks, and MUST NOT be used for other purpose. === Trust-free unconfirmed transaction dependency chain === @@ -211,7 +213,7 @@ With a soft fork, it is possible to introduce a separate witness structure to al == Backward compatibility == -As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs as anyone-can-spend scripts (except a few edge cases in version 0 witness programs which are provably unspendable with original script semantics). Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. Non-upgraded nodes are strongly encouraged to upgrade in order to take advantage of the new features. +As a soft fork, older software will continue to operate without modification. Non-upgraded nodes, however, will not see nor validate the witness data and will consider all witness programs as anyone-can-spend scripts (except a few edge cases where the witness programs are equal to 0, which the script must fail). Wallets should always be wary of anyone-can-spend scripts and treat them with suspicion. Non-upgraded nodes are strongly encouraged to upgrade in order to take advantage of the new features. '''What a non-upgraded wallet can do''' @@ -253,14 +255,14 @@ Special thanks to Gregory Maxwell for originating many of the ideas in this BIP == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit2 +https://github.com/sipa/bitcoin/commits/segwit3 == References == -*[https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki BIP16 Pay to Script Hash] -*[https://github.com/bitcoin/bips/blob/master/bip-0142.mediawiki BIP142 Address Formats for Witness Program] -*[https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143 Transaction signature verification for version 0 and version 1 witness program] -*[https://github.com/bitcoin/bips/blob/master/bip-0144.mediawiki BIP144 Segregated Witness (Peer Services)] +*[[bip-0016.mediawiki|BIP16 Pay to Script Hash]] +*[[bip-0142.mediawiki|BIP142 Address Formats for Segregated Witness]] +*[[bip-0143.mediawiki|BIP143 Transaction Signature Verification for Version 0 Witness Program]] +*[[bip-0144.mediawiki|BIP144 Segregated Witness (Peer Services)]] == Copyright == -- cgit v1.2.3 From 8e22af1d0a5de646b8f6cf4e9a78aa5792fcf7a5 Mon Sep 17 00:00:00 2001 From: Johnson Lau Date: Thu, 14 Jan 2016 13:15:10 +0800 Subject: Title change and links update --- README.mediawiki | 2 +- bip-0143.mediawiki | 8 ++++---- bip-0144.mediawiki | 2 +- 3 files changed, 6 insertions(+), 6 deletions(-) diff --git a/README.mediawiki b/README.mediawiki index fdfb988..63fc568 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -417,7 +417,7 @@ Those proposing changes should consider that ultimately consent may rest with th | Draft |- | [[bip-0143.mediawiki|143]] -| Transaction signature verification for version 0 and version 1 witness program +| Transaction Signature Verification for Version 0 Witness Program | Johnson Lau, Pieter Wuille | Standard | Draft diff --git a/bip-0143.mediawiki b/bip-0143.mediawiki index 4aca2db..3d7e856 100644 --- a/bip-0143.mediawiki +++ b/bip-0143.mediawiki @@ -1,6 +1,6 @@
   BIP: 143
-  Title: Transaction signature verification for version 0 and version 1 witness program
+  Title: Transaction Signature Verification for Version 0 Witness Program
   Author: Johnson Lau 
           Pieter Wuille 
   Status: Draft
@@ -9,7 +9,7 @@
 
== Abstract == -This proposal defines a new transaction digest algorithm for signature verification in version 0 and version 1 witness program, in order to minimize redundant data hashing in verification, and to cover the input value by the signature. +This proposal defines a new transaction digest algorithm for signature verification in version 0 witness program, in order to minimize redundant data hashing in verification, and to cover the input value by the signature. == Motivation == There are 4 ECDSA signature verification codes in the original Bitcoin script system: CHECKSIG, CHECKSIGVERIFY, CHECKMULTISIG, CHECKMULTISIGVERIFY (“sigops”). According to the sighash type (ALL, NONE, SINGLE, ANYONECANPAY), a transaction digest is generated with a double SHA256 of a serialized subset of the transaction, and the signature is verified against this digest with a given public key. The detailed procedure is described in a Bitcoin Wiki article. [https://en.bitcoin.it/wiki/OP_CHECKSIG] @@ -22,7 +22,7 @@ Unfortunately, there are at least 2 weaknesses in the original transaction diges Deploying the aforementioned fixes in the original script system is not a simple task. That would be either a hardfork, or a softfork for new sigops without the ability to remove or insert stack items. However, the introduction of segregated witness softfork offers an opportunity to define a different set of script semantics without disrupting the original system, as the unupgraded nodes would always consider such a transaction output is spendable by arbitrary signature or no signature at all. [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141: Segregated Witness (Consensus layer)] == Specification == -A new transaction digest algorithm is defined, but only applicable to sigops in version 0 and version 1 witness program: +A new transaction digest algorithm is defined, but only applicable to sigops in version 0 witness program: Double SHA256 of the serialization of: 1. nVersion of the transaction 2. hashPrevouts @@ -122,7 +122,7 @@ As a soft fork, older software will continue to operate without modification. No == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit2 +https://github.com/sipa/bitcoin/commits/segwit3 == References == diff --git a/bip-0144.mediawiki b/bip-0144.mediawiki index e3843a8..736fadd 100644 --- a/bip-0144.mediawiki +++ b/bip-0144.mediawiki @@ -116,7 +116,7 @@ MSG_WITNESS_BLOCK requests will return a block message with transactions that ha Special thanks to Gregory Maxwell for originating many of the ideas in this BIP and Luke-Jr for figuring out how to deploy this as a soft fork. == Reference Implementation == -https://github.com/sipa/bitcoin/commits/segwit +https://github.com/sipa/bitcoin/commits/segwit3 == Copyright == This document is placed in the public domain. -- cgit v1.2.3 From b38742b8f45d886d236deb22e9530523af8994fc Mon Sep 17 00:00:00 2001 From: Johnson Lau Date: Thu, 14 Jan 2016 13:26:33 +0800 Subject: Title change and new address format --- README.mediawiki | 2 +- bip-0142.mediawiki | 178 ++++++++++++++++++++++++++--------------------------- 2 files changed, 87 insertions(+), 93 deletions(-) diff --git a/README.mediawiki b/README.mediawiki index 63fc568..75c6eeb 100644 --- a/README.mediawiki +++ b/README.mediawiki @@ -411,7 +411,7 @@ Those proposing changes should consider that ultimately consent may rest with th | Draft |- | [[bip-0142.mediawiki|142]] -| Address Formats for Witness Program +| Address Format for Segregated Witness | Johnson Lau | Standard | Draft diff --git a/bip-0142.mediawiki b/bip-0142.mediawiki index fdf5202..7d7b1d2 100644 --- a/bip-0142.mediawiki +++ b/bip-0142.mediawiki @@ -1,6 +1,6 @@
   BIP: 142
-  Title: Address Formats for Witness Program
+  Title: Address Format for Segregated Witness
   Author: Johnson Lau 
   Status: Draft
   Type: Standards Track
@@ -9,148 +9,142 @@
 
 == Abstract ==
 
-This BIP describes 2 new types of Bitcoin address to support native Segregated Witness (segwit) transactions. The first type resembles the original P2PKH base-58 address. The second type is a z-base-32 representation of a witness program with Damm algorithm checksum, which supports arbitrarily complex transactions, and is forward compatible to new version witness programs in the future.
+This BIP describes new types of Bitcoin address to support native segregated witness transactions with 20-byte and 32-byte program.
 
 == Motivation ==
 
-To define standard payment addresses for native segwit transactions to promote early adoption of the more efficient transaction method.
+To define standard payment address for native segregated witness (segwit) transactions to promote early adoption of the more efficient transaction method.
 
 == Specification ==
 
-=== P2PKH segwit address ===
+The new Bitcoin address format defined is for the Pay-to-Witness-Public-Key-Hash (P2WPKH) and Pay-to-Witness-Script-Hash (P2WSH) transaction described in segregated witness soft fork (BIP141). The scriptPubKey is an OP_0 followed by a push of 20-byte-hash (P2WPKH) or 32-byte hash (P2WSH).
 
-The first new Bitcoin address format defined is specific to pay-to-public-key-hash segwit transaction. The scriptPubKey is an OP_0 followed by a push of version 0 witness program:
-  OP_0  EQUALVERIFY CHECKSIG>
-The new address is encoded exactly in the same way as the original pay-to-public-key-hash address:
-  base58-encode: [1-byte version][20-byte-hash-value][4-byte checksum]
-Version byte is 0x19 for a main-network address, 0x41 for a testnet address. The following 20-byte is the public key hash. And the 4-byte checksum is the first four bytes of the double SHA256 hash of the version and public key hash.
+The new address is encoded in a simlar way as existing address formats:
+  
+  base58-encode:
+    [1-byte address version]
+    [1-byte witness program version]
+    [0x00]
+    [20/32-byte-hash]
+    [4-byte checksum]
+  
+For P2WPKH address, the address version is 6 (0x06) for a main-network address or 3 (0x03) for a testnet address.
 
-All addresses generated with this scheme will a constant length of 34 characters, with a "B" prefix for main-network and "T" prefix for testnet.
+For P2WSH address, the address version is 10 (0x0A) for a main-network address or 40 (0x28) for a testnet address.
 
-=== General segwit address ===
+The witness program version is an 1-byte value between 0 (0x00) and 16 (0x10). Only version 0 is defined in BIP141. Versions 1 to 16 are reserved for future extensions.
 
-The second new bitcoin address format defined is applicable to witness program of version 0 to 15 with a length of 2 to 32 bytes.
+Following the witness program version is a 0x00 padding to make sure that each witness program version will have an unique prefix.
 
-The z-base-32 character set is used:
-{|class="wikitable" style="width:40ex; text-align: center; margin: 0 auto 0 auto;"
-!width="12%"|Value
-!width="12%"|Symbol
-!width="12%"|Value
-!width="12%"|Symbol
-!width="12%"|Value
-!width="12%"|Symbol
-!width="12%"|Value
-!width="12%"|Symbol
+Following the padding is the program hash, 20 byte for a P2WPKH address and 32 byte for a P2WSH address.
+
+The 4-byte checksum is the first four bytes of the double SHA256 hash of the serialization of the previous items.
+
+All addresses generated with this scheme will have a constant length, with 36 digits for 20-byte and 53 digits for 32-byte. Different witness program version will have an unique prefix shown in the following table:
+
+{|class="wikitable" style="text-align: center;"
+|-
+!rowspan=3 style=""|Witness program version
+!colspan=4 style=""|Hash size
+|-
+!colspan=2 style=""|20-byte (36 digits)
+!colspan=2 style=""|32-byte (53 digits)
+|-
+!Mainnet
+!Testnet
+!Mainnet
+!Testnet
+|-
+|0||p2||QW||7Xh||T7n
+|-
+|1||p4||QY||7Xq||T7w
+|-
+|2||p6||Qa||7Xz||T85
+|-
+|3||p7||Qc||7Y9||T8E
+|-
+|4||pA||Qe||7YH||T8N
+|-
+|5||pB||Qf||7YS||T8X
+|-
+|6||pD||Qh||7Ya||T8g
+|-
+|7||pF||Qj||7Yj||T8p
+|-
+|8||pG||Qm||7Yt||T8y
 |-
-| 0 || y ||  8 || e || 16 || o || 24 || a
+|9||pJ||Qn||7Z2||T97
 |-
-| 1 || b ||  9 || j || 17 || t || 25 || 2
+|10||pL||Qp||7ZB||T9G
 |-
-| 2 || n || 10 || k || 18 || 1 || 26 || 4
+|11||pN||Qr||7ZK||T9Q
 |-
-| 3 || d || 11 || m || 19 || u || 27 || 5
+|12||pQ||Qt||7ZU||T9Z
 |-
-| 4 || r || 12 || c || 20 || w || 28 || h
+|13||pS||Qv||7Zc||T9i
 |-
-| 5 || f || 13 || p || 21 || i || 29 || 7
+|14||pT||Qw||7Zm||T9r
 |-
-| 6 || g || 14 || q || 22 || s || 30 || 6
+|15||pV||Qy||7Zv||TA1
+|-
+|16||pX||R1||7a4||TA9
 |-
-| 7 || 8 || 15 || x || 23 || z || 31 || 9
 |}
 
-It is case-insensitive and includes all alphanumeric characters excluding 0, 2, l, v. The order of alphabet is chosen so that less ambiguous alphabet characters will appear more frequently than others.
-
-An address is a 270-bit string in z-base-32 with the following components:
-
-  5 address version bits
-  5 length bits
-  4 witness program version bits
-  256 witness program bits
-
-The address version bits is 00001b for the main-network and 11001b for the testnet.
-
-Value of the length bits is the length of the witness program in byte minus 1.
-
-Witness program version bits indicates version of the witness program (v0 to v15).
-
-The witness program is padded with leading 0b to 256 bits.
-
-The 270-bit string is transformed to z-base-32 with 54 digits.
-
-The 54-digit raw address is then divided into 9 equal segments. For each segment, a checksum is calculated with Damm algorithm and appended to the end of the segment. This makes the length increases to 63 digits.
-
-A second round of checksum is calculated by taking the digits in the same position of the 9 segments, and appended to the end of the address. This is the final address with 69 digits.
-
 
 == Rationale ==
 
-The segregated witness soft fork (BIP x) defines 2 ways of encoding "witness program", a data push of 2 to 32 bytes:
+The BIP141 defines 2 ways of encoding "witness program", a data push of 2 to 32 bytes:
 
 * A native witness program output is a scriptPubKey with a push of version byte followed by a push of witness program, and nothing else;
-* A witness program in P2SH is a P2SH redeemScript with a push of version byte followed by a push of witness program, while the scriptPubKey looks like a normal P2SH output.
+* Segwit-in-P2SH is a BIP16 P2SH redeemScript with a push of version byte followed by a push of witness program, while the scriptPubKey looks like a normal P2SH output.
 
-As the P2SH address has been defined in 2012, using witness program in P2SH allows most existing wallets to pay a segwit-compatible wallet without any upgrade. However, this method requires more block space and is less collision-resistance than a native witness program, and is only a short-term solution to make the transition smoother. Eventually, all users are expected to use the more efficient native witness program as the primary payment method.
+As the BIP13 P2SH address has been defined in 2012, using segwit-in-P2SH allows most existing wallets to pay a segwit-compatible wallet without any upgrade. However, this method requires more block space and is only a short-term solution to make the transition smoother. Eventually, all users are expected to use the more efficient native witness program as the primary payment method.
 
 The drawbacks of Bitcoin addresses have been extensively discussed in BIP13. Since then, better payment methods have been proposed or deployed, for example:
 *BIP47 Reusable Payment Codes for Hierarchical Deterministic Wallets
 *BIP63 Stealth Addresses
 *BIP70 Payment protocol
 
-However, none of these are as widely adopted as the suboptimal base-58 scriptPubKey template addresses, which is still a standard for the whole eco-system, from wallets, block explorers, merchants, exchanges, to end users. As P2PKH transactions are still dominating the blockchain, the author believes that the proposed P2PKH segwit addresses is the easiest way for wallets and services to adopt native witness program, which is particularly important in the context of scaling the capacity of the blockchain.
+However, none of these are as widely adopted as the suboptimal base-58 scriptPubKey template addresses, which is still a standard for the whole eco-system, from wallets, block explorers, merchants, exchanges, to end users. It is believed that the proposed P2WPKH and P2WSH address format is the easiest way for wallets and services to adopt native witness program, which is particularly important in the context of scaling the capacity of the blockchain.
 
-The P2PKH segwit addresses only allow simple payment to a single public key. For arbitrarily complex segwit transactions, the general segwit address is used. The use of z-base-32 eliminates case-sensitiveness and simplifies transformation to and from hexadecimals. The Damm algorithm checksum allows detection of all single-digit errors and all adjacent transposition errors. With the excellent upgradability of witness program, this proposal is also forward compatible to new version witness programs that is not longer than 32 bytes.
+While P2WPKH address is specific for simple payment to a single public key, P2WSH address allows arbitrarily complex segwit transactions, resemble to the BIP13 P2SH address.
 
 == Compatibility ==
 
-This proposal is not backward compatible, but it fails gracefully -- if an older implementation is given one of these new Bitcoin addresses, it will report the address as invalid and will refuse to create a transaction.
+This proposal is not backward compatible. However, an older implementation will report the new address type as invalid and will refuse to create a transaction.
 
-This proposal is forward compatible to any new witness program format with version 2 to 15 and length of 2 to 32 bytes.
+This proposal is forward compatible to the future versions of witness program of 20 and 32 bytes.
 
 == Example ==
 
-=== P2PKH segwit address ===
-
 The following public key,
+  
     0450863AD64A87AE8A2FE83C1AF1A8403CB53F53E486D8511DAD8A04887E5B23522CD470243453A299FA9E77237716103ABC11A1DF38855ED6F2EE187E9C582BA6
+ 
 when encoded as a P2PKH template, would become:
+  
     DUP HASH160 <010966776006953D5567439E5E39F86A0D273BEE> EQUALVERIFY CHECKSIG
+
 And the corresponding version 1 Bitcoin address is
+  
     16UwLL9Risc3QfPqBUvKofHmBQ7wMtjvM
-When the same script is encoded as a version 0 witness program, the scriptPubKey becomes: 
-    OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC>
-Using 0x19 as the address version, the equivalent witness program address is:
-    B4YZZ3nMBETWVF9ZSfotSwTxVnqhdkTi7r
-
-=== General segwit address ===
-
-With the same 25 bytes version 0 witness program in the last example:
-    OP_0 <0x76A914010966776006953D5567439E5E39F86A0D273BEE88AC>
-The address version bits is 00001b
-    00001b
-The lengths bits is 11000b (24 = 25 - 1)
-    00001-11000b
-The witness program version bits is 0000
-    00001-11000-0000b
-Appended by the zero-padded witness program
-    00001-11000-0000-0-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-00000-11101...01100
-The 270-bit string is transformed to z-base-32 with 54 digits and split into 9 equal segments:
-    bayyyy -yyyyyy -yyq4wt -eyejc3 -5sybwi -8iksqo -h6mah9 -o4oprh -767nfc
-Calculate the Damm checksum for each segment:
-    For example: Damm(bayyyy) = 7
-    bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4
-Calculate the Damm checksum for digits in the same position of different segments:
-    For example: Damm(byye58ho7) = j
-    bayyyy7-yyyyyyy-yyq4wte-eyejc3q-5sybwic-8iksqoo-h6mah9w-o4oprhm-767nfc4-jwk86o
-
-== Implementation ==
-
-From arbitrary witness program to general segwit address: https://gist.github.com/jl2012/760b0f952715b8b6c608
+ 
+When the same public key is encoded as P2WPKH, the scriptPubKey becomes: 
+  
+    OP_0 <010966776006953D5567439E5E39F86A0D273BEE>
+
+Using 0x06 as witness version, followed 0x00 as witness version, and a 0x00 padding, the equivalent P2WPKH address is:
+  
+    p2xtZoXeX5X8BP8JfFhQK2nD3emtjch7UeFm
+ 
+== Reference implementation ==
 
 == References ==
 
 * [[bip-0013.mediawiki|BIP 13: Address Format for pay-to-script-hash]]
-* [[bip-0016.mediawiki|BIP 16: Pay to Script Hash (aka "/P2SH/")]]
+* [[bip-0016.mediawiki|BIP 16: Pay to Script Hash]]
+* [[bip-0070.mediawiki|BIP 70: Payment Protocal]]
 * [[bip-0141.mediawiki|BIP 141: Segregated Witness]]
 
 == Copyright ==
-- 
cgit v1.2.3


From bcf0ea37840d9feba5fd6c16285e034f9a8e2688 Mon Sep 17 00:00:00 2001
From: Luke Dashjr 
Date: Tue, 19 Jan 2016 01:37:57 +0000
Subject: Assign BIP 131

---
 README.mediawiki                |  6 +++
 bip-0131.mediawiki              | 82 +++++++++++++++++++++++++++++++++++++++++
 bip-coalesce-wildcard.mediawiki | 82 -----------------------------------------
 3 files changed, 88 insertions(+), 82 deletions(-)
 create mode 100644 bip-0131.mediawiki
 delete mode 100644 bip-coalesce-wildcard.mediawiki

diff --git a/README.mediawiki b/README.mediawiki
index 1ce3a76..7584102 100644
--- a/README.mediawiki
+++ b/README.mediawiki
@@ -410,6 +410,12 @@ Those proposing changes should consider that ultimately consent may rest with th
 | Standard
 | Draft
 |-
+| [[bip-0131.mediawiki|131]]
+| "Coalescing Transaction" Specification (wildcard inputs)
+| Chris Priest
+| Standard
+| Draft
+|-
 | [[bip-0140.mediawiki|140]]
 | Normalized TXID
 | Christian Decker
diff --git a/bip-0131.mediawiki b/bip-0131.mediawiki
new file mode 100644
index 0000000..c30ef54
--- /dev/null
+++ b/bip-0131.mediawiki
@@ -0,0 +1,82 @@
+
+  BIP: 131
+  Title: "Coalescing Transaction" Specification (wildcard inputs)
+  Author: Chris Priest 
+  Status: Draft
+  Type: Standards Track
+  Created: 2015-11-30
+
+ +==Abstract== + +This specification defines a new type of transaction that supplements (not replaces) +normal "non coalescing" bitcoin transactions. + +==Motivation== + +Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend +from multiple inputs with the exact same scriptPubKey, you have to list each +input separately, along with the same signature multiple times, even though the signature expresses the same information. +This bloats the transaction size and makes it expensive to spend from small value inputs. + +Because small value inputs are expensive to send, they remain in the UTXO pool +which full nodes have to keep around. It is believed that long term increase of the UTXO +set can have negative scaling consequences on the network. + +If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending +to the network, this problem is projected to get worse. In other words, as transaction +fees increase, the minimum economical value of a spending a UTXO will increase. + +==Specification== + +=== Redefinition of Transaction version === + +First, this BIP redefines the version field on transactions. The first four bytes +are defined as the version number, while the last four bytes are defined as the +transaction type. Type "0000" denotes normal transactions, and "0001" defines +coalescing transaction. + +Examples: + +version 1 transaction with normal inputs: + version: 10000000 + +version 2 transaction with normal inputs: + version: 20000000 + +version 2 transaction with coalescing inputs: + version: 20000001 + +Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all +inputs present in the transaction. + +=== Wildcard inputs === + +A coalescing transaction is formulated the exact same way as a version 1 transaction +with one exception: each input is treated as a "wildcard input". + +A wildcard input beings the value of all inputs with the exact same scriptPubKey +in a block lower or equal to the block the wildcard input is confirmed into. + +== Changes needed to implement == + +The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. + +1. Full Node Coalescing validation - When a full node receives a coalescing transaction, it has to +aggregate the value of all the UTXOs in the blockchain older than the input +with the same scriptPubKey. If this value is greater than or equal to the +amount of all outputs, then that coalescing transaction is valid and can be propagated. + +2. Full Node Non-Coalescing validation - When a non-coalescing transaction comes in, the code needs to be modified +to check if each input has not been spent by a coalescing transaction. If there exist any +coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, +then the UTXO has been spent and the transaction is invalid. + +3. Wallet - The user facing wallet portion of the reference client should notify +the user when their wallet contains many UTXOs that qualify it to benefit from +a coalescing transaction. Wallets should not simply replace non-coalescing transactions +with coalescing transactions in all instances. + +==Copyright== + +This document is placed in the public domain. diff --git a/bip-coalesce-wildcard.mediawiki b/bip-coalesce-wildcard.mediawiki deleted file mode 100644 index 4c3a557..0000000 --- a/bip-coalesce-wildcard.mediawiki +++ /dev/null @@ -1,82 +0,0 @@ -
-  BIP: (no number)
-  Title: "Coalescing Transaction" Specification (wildcard inputs)
-  Author: Chris Priest 
-  Status: Draft
-  Type: Standards Track
-  Created: 2015-11-30
-
- -==Abstract== - -This specification defines a new type of transaction that supplements (not replaces) -normal "non coalescing" bitcoin transactions. - -==Motivation== - -Normal "non-coalescing" Bitcoin Transactions have one large inefficiency: When you want to spend -from multiple inputs with the exact same scriptPubKey, you have to list each -input separately, along with the same signature multiple times, even though the signature expresses the same information. -This bloats the transaction size and makes it expensive to spend from small value inputs. - -Because small value inputs are expensive to send, they remain in the UTXO pool -which full nodes have to keep around. It is believed that long term increase of the UTXO -set can have negative scaling consequences on the network. - -If maximum blocksize is made to increase *slower* than the actual number of transactions bitcoin users are sending -to the network, this problem is projected to get worse. In other words, as transaction -fees increase, the minimum economical value of a spending a UTXO will increase. - -==Specification== - -=== Redefinition of Transaction version === - -First, this BIP redefines the version field on transactions. The first four bytes -are defined as the version number, while the last four bytes are defined as the -transaction type. Type "0000" denotes normal transactions, and "0001" defines -coalescing transaction. - -Examples: - -version 1 transaction with normal inputs: - version: 10000000 - -version 2 transaction with normal inputs: - version: 20000000 - -version 2 transaction with coalescing inputs: - version: 20000001 - -Essentially the last bit in the version field is set to 1 to enable wildcard inputs for all -inputs present in the transaction. - -=== Wildcard inputs === - -A coalescing transaction is formulated the exact same way as a version 1 transaction -with one exception: each input is treated as a "wildcard input". - -A wildcard input beings the value of all inputs with the exact same scriptPubKey -in a block lower or equal to the block the wildcard input is confirmed into. - -== Changes needed to implement == - -The bitcoin code needs to be modified in three places in order to handle Coalescing Transactions. - -1. Full Node Coalescing validation - When a full node receives a coalescing transaction, it has to -aggregate the value of all the UTXOs in the blockchain older than the input -with the same scriptPubKey. If this value is greater than or equal to the -amount of all outputs, then that coalescing transaction is valid and can be propagated. - -2. Full Node Non-Coalescing validation - When a non-coalescing transaction comes in, the code needs to be modified -to check if each input has not been spent by a coalescing transaction. If there exist any -coalescing transaction in the blockchain with the same scriptPubKey found in a block *after* that input, -then the UTXO has been spent and the transaction is invalid. - -3. Wallet - The user facing wallet portion of the reference client should notify -the user when their wallet contains many UTXOs that qualify it to benefit from -a coalescing transaction. Wallets should not simply replace non-coalescing transactions -with coalescing transactions in all instances. - -==Copyright== - -This document is placed in the public domain. -- cgit v1.2.3