Merge pull request #610 from kallewoof/bip-fmt-mbv-tcs

BIPs 98, 116, and 117: Fast Merkle Trees; MERKLEBRANCHVERIFY; Tail Call Execution Semantics

13 files changed, 814 insertions, 0 deletions

diff --git a/README.mediawiki b/README.mediawiki
index c8431d2..9943ca8 100644
--- a/README.mediawiki
+++ b/README.mediawiki
@@ -421,6 +421,13 @@ Those proposing changes should consider that ultimately consent may rest with th
 | Standard
 | Final
 |-
+| [[bip-0098.mediawiki|98]]
+| Consensus (soft fork)
+| Fast Merkle Trees
+| Mark Friedenbach, Kalle Alm, BtcDrak
+| Standard
+| Draft
+|-
 | [[bip-0099.mediawiki|99]]
 |
 | Motivation and deployment of consensus rule changes ([soft/hard]forks)
@@ -519,6 +526,20 @@ Those proposing changes should consider that ultimately consent may rest with th
 | Standard
 | Draft
 |-
+| [[bip-0116.mediawiki|116]]
+| Consensus (soft fork)
+| MERKLEBRANCHVERIFY
+| Mark Friedenbach, Kalle Alm, BtcDrak
+| Standard
+| Draft
+|-
+| [[bip-0117.mediawiki|117]]
+| Consensus (soft fork)
+| Tail Call Execution Semantics
+| Mark Friedenbach, Kalle Alm, BtcDrak
+| Standard
+| Draft
+|-
 | [[bip-0120.mediawiki|120]]
 | Applications
 | Proof of Payment
diff --git a/bip-0098.mediawiki b/bip-0098.mediawiki
new file mode 100644
index 0000000..6bdf784
--- /dev/null
+++ b/bip-0098.mediawiki
@@ -0,0 +1,308 @@
+<pre>
+  BIP: 98
+  Layer: Consensus (soft fork)
+  Title: Fast Merkle Trees
+  Author: Mark Friedenbach <mark@friedenbach.org>
+          Kalle Alm <kalle.alm@gmail.com>
+          BtcDrak <btcdrak@gmail.com>
+  Comments-Summary: No comments yet.
+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0098
+  Status: Draft
+  Type: Standards Track
+  Created: 2017-08-24
+  License: CC-BY-SA-4.0
+  License-Code: MIT
+</pre>
+
+==Abstract==
+
+In many applications it is useful to prove membership of a data element in a set without having to reveal the entire contents of that set.
+The Merkle hash-tree, where inner/non-leaf nodes are labeled with the hash of the labels or values of its children, is a cryptographic tool that achieves this goal.
+Bitcoin uses a Merkle hash-tree construct for committing the transactions of a block into the block header.
+This particular design, created by Satoshi, suffers from a serious flaw related to duplicate entries documented in the National Vulnerability Database as CVE-2012-2459[1], and also suffers from less than optimal performance due to unnecessary double-hashing.
+
+This Bitcoin Improvement Proposal describes a more efficient Merkle hash-tree construct that is not vulnerable to CVE-2012-2459
+and achieves an approximate 55% decrease in hash-tree construction and validation times as compared with fully optimized implementations of the Satoshi Merkle hash-tree construct.
+
+==Copyright==
+
+This BIP is licensed under a Creative Commons Attribution-ShareAlike license. All provided source code is licensed under the MIT license.
+
+==Motivation==
+
+A Merkle hash-tree is a directed acyclic graph data structure where all non-terminal nodes are labeled with the hash of combined labels or values of the node(s) it is connected to.
+Bitcoin uses a unique Merkle hash-tree construct invented by Satoshi for calculating the block header commitment to the list of transactions in a block.
+While it would be convenient for new applications to make use of this same data structure so as to share implementation and maintenance costs, there are three principle drawbacks to reuse.
+
+First, Satoshi's Merkle hash-tree has a serious vulnerability[1] related to duplicate tree entries that can cause bugs in protocols that use it.
+While it is possible to secure protocols and implementations against exploit of this flaw, it requires foresight and it is a bit more tricky to design secure protocols that work around this vulnerability.
+Designers of new protocols ought avoid using the Satoshi Merkle hash-tree construct where at all possible in order to responsibly decrease the likelihood of downstream bugs in naïve implementations.
+
+Second, Satoshi's Merkle hash-tree performs an unnecessary number of cryptographic hash function compression rounds, resulting in construction and validation times that are approximately three (3) times more computation than is strictly necessary in a naïve implementation, or 2.32x more computation in an implementation specialized for this purpose only[2].
+New implementations that do not require backwards compatibility ought to consider hash-tree implementations that do not carry this unnecessary performance hit.
+
+Third, Satoshi's algorithm presumes construction of a tree index from an ordered list, and therefore is designed to support balanced trees with a uniform path length from root to leaf for all elements in the tree.
+Many applications, on the other hand, benefit from having unbalanced trees, particularly if the shorter path is more likely to be used.
+While it is possible to make a few elements of a Satoshi hash-tree have shorter paths than the others, the tricks for doing so are dependent on the size of the tree and not very flexible.
+
+Together these three reasons provide justification for specifying a standard Merkle hash-tree structure for use in new protocols that fixes these issues.
+This BIP describes such a structure, and provides an example implementation.
+
+==Specification==
+
+A Merkle hash-tree as defined by this BIP is an arbitrarily-balanced binary tree whose terminal/leaf nodes are labelled with the double-SHA256 hashes of data, whose format is outside the scope of this BIP, and inner nodes with labels constructed from the fast-SHA256 hash of its children's labels.
+The following image depicts an example unbalanced hash-tree:
+
+:: [[File:bip-0098/unbalanced-hash-tree.png]]
+
+'''A''', '''B''', and '''C''' are leaf labels, 32-byte double-SHA256 hashes of the data associated with the leaf.
+'''Node''' and '''Root''' are inner nodes, whose labels are fast-SHA256 (defined below) hashes of their respective children's labels.
+'''Node''' is labelled with the fast-SHA256 hash of the concatination of '''B''' and '''C'''.
+'''Root''' is labelled with the fast-SHA256 hash of the concatination of '''A''' and '''Node''', and is the ''Merkle root'' of the tree.
+Nodes with single children are not allowed.
+
+The ''double-SHA256'' cryptographic hash function takes an arbitrary-length data as input and produces a 32-byte hash by running the data through the SHA-256 hash function as specified in FIPS 180-4[3], and then running the same hash function again on the 32-byte result, as a protection against length-extension attacks.
+
+The ''fast-SHA256'' cryptographic hash function takes two 32-byte hash values, concatenates these to produce a 64-byte buffer, and applies a single run of the SHA-256 hash function with a custom 'initialization vector' (IV) and without message paddding.
+The result is a 32-byte 'midstate' which is the combined hash value and the label of the inner node.
+The changed IV protects against path-length extension attacks (grinding to interpret a hash as both an inner node and a leaf).
+fast-SHA256 is only defined for two 32-byte inputs.
+The custom IV is the intermediate hash value generated after performing a standard SHA-256 of the following hex-encoded bytes and extracting the midstate:
+
+    cbbb9d5dc1059ed8 e7730eaff25e24a3 f367f2fc266a0373 fe7a4d34486d08ae
+    d41670a136851f32 663914b66b4b3c23 1b9e3d7740a60887 63c11d86d446cb1c
+
+This data is the first 512 fractional bits of the square root of 23, the 9th prime number.
+The resulting midstate is used as IV for the fast-SHA256 cryptographic hash function:
+
+    static unsigned char _MidstateIV[32] =
+        { 0x89, 0xcc, 0x59, 0xc6, 0xf7, 0xce, 0x43, 0xfc,
+          0xf6, 0x12, 0x67, 0x0e, 0x78, 0xe9, 0x36, 0x2e,
+          0x76, 0x8f, 0xd2, 0xc9, 0x18, 0xbd, 0x42, 0xed,
+          0x0e, 0x0b, 0x9f, 0x79, 0xee, 0xf6, 0x8a, 0x24 };
+
+As fast-SHA256 is only defined for two (2) 32-byte hash inputs, there are necessarily two special cases:
+an empty Merkle tree is not allowed, nor is any root hash defined for such a "tree";
+and a Merkle tree with a single value has a root hash label equal to that self-same value of the leaf branch, the only node in the tree (a passthrough operation with no hashing).
+
+===Rationale===
+
+The fast-SHA256 hash function can be calculated 2.32x faster than a specialized double-SHA256 implementation[2], or three (3) times faster than an implementation applying a generic SHA-256 primitive twice,
+as hashing 64 bytes of data with SHA-256 as specified by FIPS 180-4[3] takes two compression runs (because of message padding) and then a third compression run for the double-SHA256 construction.
+Validating a fast-SHA256 Merkle root is therefore more than twice as fast as the double-SHA256 construction used by Satoshi in bitcoin.
+Furthermore the fastest fast-SHA256 implementation ''is'' the generic SHA-256 implementation, enabling generic circuitry and code reuse without a cost to performance.
+
+The application of fast-SHA256 to inner node label updates is safe in this limited domain because the inputs are hash values and fixed in number and in length,
+so the sorts of attacks prevented by message padding and double-hashing do not apply.
+
+The 'initialization vector' for fast-SHA256 is changed in order to prevent a category of attacks on higher level protocols where a partial collision can serve as both a leaf hash and as an inner node commitment to another leaf hash.
+The IV is computed using standard SHA-256 plus midstate extraction so as to preserve compatability with cryptographic library interfaces that do not support custom IVs, at the cost of a 2x performance hit if neither custom IVs nor resuming from midstate are supported.
+The data hashed is a nothing-up-my-sleeve number that is unlikely to have a known hash preimage.
+The prime 23 was chosen as the leading fractional bits of the first eight (8) primes, two (2) through nineteen (19), are constants used in the setup of SHA-256 itself.
+Using the next prime in sequence reduces the likelihood of introducing weakness due to reuse of a constant factor.
+
+The Merkle root hash of a single element tree is a simple pass-through of the leaf hash without modification so as to allow for chained validation of split proofs.
+This is particularly useful when the validation environment constrains proof sizes, such as push limits in Bitcoin script.
+Chained validation allows a verifier to split one proof into two or more, where the leaf is shown to be under an inner node, and that inner node is shown to be under the root.
+Without pass-through hashing in a single-element tree, use of chained validation would unnecessarily introduce a minimum path length requirement equal to the number of chain links.
+Pass-through hashing of single elements allows instead for one or more of the chained validations to use a "NOP" proof consisting of a zero-length path,
+thereby allowing, for example, a fixed series of four (4) chained validations to verify a length three (3) or shorter path.
+
+==Inclusion Proofs==
+
+An important use of Merkle hash-trees is the ability to compactly prove membership with log-sized proofs.
+This section specifies a standard encoding for a multi-element inclusion proof.
+
+To prove that a set of hashes is contained within a Merkle tree with a given root requires four pieces of information:
+
+# The root hash of the Merkle tree;
+# The hash values to be verified, a set usually consisting of the double-SHA256 hash of data elements, but potentially the labels of inner nodes instead, or both;
+# The paths from the root to the nodes containing the values under consideration, expressed as a serialized binary tree structure; and
+# The hash values of branches not taken along those paths.
+
+Typically the last two elements, the paths and the elided branch hashes, are lumped together and referred to as the ''proof''.
+
+Serialization begins with a variable-length integer (VarInt)  used to encode N, the number of internal nodes in the proof.
+Next the structure of the tree is traversed using depth-first, left-to-right, pre-order algorithm to visit each internal nodes, which are serialized using a packed 3-bit representation for the configuration of each node, consuming <code>(3*N + 7) / 8</code> bytes.
+Then the number skipped hashes (those included in the proof, not verified by the proof) is serialized as a variable-length integer (VarInt),
+followed by the hashes themselves in the order previously traversed.
+
+There are eight possible configurations of internal nodes, as given in the following diagram:
+
+:: [[File:bip-0098/node-variants.png]]
+
+In this diagram, DESCEND means the branch links to another internal node, as indicated by the its child graph elements labeled "...";
+SKIP means the branch contains a hash of an elided subtree or element, and the fast-SHA256 root hash of this subtree or double-SHA256 hash of the element is included in the proof structure; and
+VERIFY means the branch contains an externally provided hash that is needed as witness for the verification of the proof.
+In tabular form, these code values are:
+
+{| class="wikitable"
+|-
+| scope="col"| Code
+| scope="col"| Left
+| scope="col"| Right
+|-
+| scope="row"| 000
+| VERIFY
+| SKIP
+|-
+| scope="row"| 001
+| VERIFY
+| VERIFY
+|-
+| scope="row"| 010
+| VERIFY
+| DESCEND
+|-
+| scope="row"| 011
+| DESCEND
+| SKIP
+|-
+| scope="row"| 100
+| DESCEND
+| VERIFY
+|-
+| scope="row"| 101
+| DESCEND
+| DESCEND
+|-
+| scope="row"| 110
+| SKIP
+| VERIFY
+|-
+| scope="row"| 111
+| SKIP
+| DESCEND
+|}
+
+These 3-bit codes are packed into a byte array such that eight (8) codes would fit in every three (3) bytes.
+The order of filling a byte begins with the most significant bit <code>0x80</code> and ends with the lest significant bit <code>0x01</code>.
+Unless the number of inner nodes is a multiple of eight (8), there will be excess low-order bits in the final byte of serialization.
+These excess bits must be zero.
+
+Note that the tree serialization is self-segmenting.
+By tracking tree structure a proof reader will know when the parser has reached the last internal node.
+The number of inner nodes serialized in the proof MUST equal the number of nodes inferred from the tree structure itself.
+Similarly, the number of SKIP hashes can also be inferred from the tree structure as serialized, and MUST equal the number of hashes provided within the proof.
+
+The single-hash proof has N=0 (the number of inner nodes),
+the tree structure is not serialized (as there are no inner nodes),
+and the number of SKIP hashes can be either 0 or 1.
+
+===Example===
+
+Consider the following Merkle tree structure:
+
+:: [[File:bip-0098/traversal-example.png]]
+
+There are six (6) internal nodes.
+The depth-first, left-to-right, pre-order traversal of the tree visits these nodes in the following order: A, B, D, F, C, then E.
+There are three (3) skipped hashes, visited in the following order: 0x00..., 0x66..., and 0x22...
+The remaining four (4) hashes are provided at runtime to be verified by the proof.
+
+{|
+| scope="col"|
+| scope="col"| Byte 1
+| scope="col"| Byte 2
+| scope="col"| Byte 3
+|-
+| scope="row"| Bits
+| 76543210
+| 76543210
+| 76543210
+|-
+| scope="row"| Nodes
+| AAABBBDD
+| DFFFCCCE
+| EE------
+|-
+| scope="row"| Code
+| 10111101
+| 10000100
+| 01000000
+|}
+
+The serialization begins with the VarInt encoded number of inner nodes, <code>0x06</code>, followed by the tree serialization itself, <code>0xbd8440</code>.
+Next the number of SKIP hashes is VarInt encoded, <code>0x03</code>, followed by the three (3) hashes in sequence.
+The resulting 101 byte proof, encoded in base64:.
+
+    Br2EQAMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAGZmZmZmZmZmZmZmZmZmZmZmZmZm
+    ZmZmZmZmZmZmZmZmREREREREREREREREREREREREREREREREREREREREREQ=
+
+===Rationale===
+
+The 3-bit encoding for inner nodes allows encoding all relevant configurations of the nodes where the left and right branches can each be one of {DESCEND, SKIP, VERIFY}.
+The excluded 9th possibility would have both branches as SKIP:
+
+:: [[File:bip-0098/skip-skip.png]]
+
+This possibility is not allowed as for verification purposes it is entirely equivalent to the shorter proof where the branch to that node was SKIP'ed.
+Disallowing a node with two SKIP branches eliminates what would otherwise be a source of proof malleability.
+
+The number of hashing operations required to verify a proof is one less than the number of hashes (SKIP and VERIFY combined),
+and is exactly equal to the number of inner nodes serialized as the beginning of the proof as N.
+The variable-length integer encoding has the property that serialized integers, sorted lexigraphically, will also be sorted numerically.
+Since the first serialized item is the number of inner nodes, sorting proofs lexigraphically has the effect of sorting the proofs by the amount of work required to verify.
+
+The number of hashes required as input for verification of a proof is N+1 minus the number of SKIP hashses,
+and can be quickly calculated without parsing the tree structure.
+
+The coding and packing rules for the serialized tree structure were also chosen to make lexigraphical comparison useful (or at least not meaningless).
+If we consider a fully-expanded tree (no SKIP hashes, all VERIFY) to be encoding a list of elements in the order traversed depth-first from left-to-right,
+then we can extract proofs for subsets of the list by SKIP'ing the hashes of missing values and recursively pruning any resulting SKIP,SKIP nodes.
+Lexigraphically comparing the resulting serialized tree structures is the same as lexigraphically comparing lists of indices from the original list verified by the derived proof.
+
+Because the number of inner nodes and the number of SKIP hashes is extractible from the tree structure,
+both variable-length integers in the proof are redundant and could have been omitted.
+However that would require either construction and storage of the explicit tree in memory at deserialization time,
+or duplication of the relatively complicated tree parsing code in both the serialization and verification methods.
+For that reason (as well as to handle the single-hash edge case) the redundant inner node and SKIP hash counts are made explicit in the serialization,
+and the two values must match what is inferred from the tree structure for a proof to be valid.
+This makes deserialization trivial and defers tree construction until verification time,
+which has the additional benefit of enabling log-space verification algorithms.
+
+==Fast Merkle Lists==
+
+Many applications use a Merkle tree to provide indexing of, or compact membership proofs about the elements in a list.
+This ammendum specifies an algorithm that constructs a canonical balanced tree structure for lists of various lengths.
+It differs in a subtle but important way from the algorithm used by Satoshi so as to structurally prevent the vulnerability described in [1].
+
+# Begin with a list of arbitrary data strings.
+# Pre-process the list by replacing each element with its double-SHA256 hash.
+# If the list is empty, return the zero hash.
+# While the list has 2 or more elements,
+#* Pass through the list combining adjacent entries with the fast-SHA256 hash. If the list has an odd number of elements, leave the last element as-is (this fixes [1]). This step reduces a list of N elements to ceil(N/2) entries.
+# The last remaining item in the list is the Merkle root.
+
+This algorithm differs from Merkle lists used in bitcoin in two ways.
+First, fast-SHA256 is used instead of double-SHA256 for inner node labels.
+Second, final entries on an odd-length list are not duplicated and hashed, which is the mistake that led to CVE-2012-2459[1].
+
+==Implementation==
+
+An implementation of this BIP for extraction of Merkle branches and fast, log-space Merkle branch validation is available at the following Github repository:
+
+[https://github.com/maaku/bitcoin/tree/fast-merkle-tree]
+
+Also included in this repo is a 'merklebranch' RPC for calculating root values and extracting inclusion proofs for both arbitrary trees and trees constructed from lists of values using the algorithm in this BIP,
+and a 'mergemerklebranch' RPC for unifying two or more fast Merkle tree inclusion proofs--replacing SKIP hashes in one proof with a subtree extracted from another.
+
+==Deployment==
+
+This BIP is used by BIP116 (MERKLEBRANCHVERIFY)[4] to add Merkle inclusion proof verification to script by means of a soft-fork NOP expansion opcode.
+Deployment of MERKLEBRANCHVERIFY would make the contents of this BIP consensus critical.
+The deployment plan for BIP116 is covered in the text of that BIP.
+
+==Compatibility==
+
+This BIP on its own does not cause any backwards incompatibility.
+
+==References==
+
+[1] [https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2012-2459 National Vulnerability Database: CVE-2012-2459]
+
+[2] [https://github.com/sipa/bitcoin/tree/201709_dsha256_64 github.com:sipa/bitcoin 201709_dsha256_64] Pieter Wuille, September 2017, personal communication. By making use of knowledge that the inputs at each stage are fixed length, Mr. Wuille was able to achieve a 22.7% reduction in the time it takes to compute the double-SHA256 hash of 64 bytes of data, the hash aggregation function of the Satoshi Merkle tree construction.
+
+[3] [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf Secure Hash Standard]
+
+[4] [https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki BIP 116 MERKLEBRANCHVERIFY]
diff --git a/bip-0098/build.sh b/bip-0098/build.sh
new file mode 100755
index 0000000..a8a3155
--- /dev/null
+++ b/bip-0098/build.sh
@@ -0,0 +1,6 @@
+#!/bin/sh
+
+dot -Tpng -o node-variants.png node-variants.dot
+dot -Tpng -o skip-skip.png skip-skip.dot
+dot -Tpng -o traversal-example.png traversal-example.dot
+dot -Tpng -o unbalanced-hash-tree.png unbalanced-hash-tree.dot
diff --git a/bip-0098/node-variants.dot b/bip-0098/node-variants.dot
new file mode 100644
index 0000000..7171346
--- /dev/null
+++ b/bip-0098/node-variants.dot
@@ -0,0 +1,85 @@
+digraph G {
+  row1 [shape=none, label=""]
+
+  A [label="000"]
+  A -> Al [label="L"]
+  Al [label="VERIFY"]
+  A -> Ar [label="R"]
+  Ar [label="SKIP"]
+
+  B [label="001"]
+  B -> Bl [label="L"]
+  Bl [label="VERIFY"]
+  B -> Br [label="R"]
+  Br [label="VERIFY"]
+
+  { rank = same; row1; A; B; }
+
+  C [label="010"]
+  C -> Cl [label="L"]
+  Cl [label="VERIFY"]
+  C -> Cr [label="R"]
+  Cr [label="DESCEND"]
+  Cr -> Crl
+  Crl [label="..."]
+  Cr -> Crr
+  Crr [label="..."]
+
+  D [label="011"]
+  D -> Dl [label="L"]
+  Dl [label="DESCEND"]
+  Dl -> Dll
+  Dll [label="..."]
+  Dl -> Dlr
+  Dlr [label="..."]
+  D -> Dr [label="R"]
+  Dr [label="SKIP"]
+
+  E [label="100"]
+  E -> El [label="L"]
+  El [label="DESCEND"]
+  El -> Ell
+  Ell [label="..."]
+  El -> Elr
+  Elr [label="..."]
+  E -> Er [label="R"]
+  Er [label="VERIFY"]
+
+  row1 -> invis [style=invis]
+  invis [shape=none, label=""]
+  invis -> C [style=invis]
+  { rank = same; C; D; E; }
+
+  F [label="101"]
+  F -> Fl [label="L"]
+  Fl [label="DESCEND"]
+  Fl -> Fll
+  Fll [label="..."]
+  Fl -> Flr
+  Flr [label="..."]
+  F -> Fr [label="R"]
+  Fr [label="DESCEND"]
+  Fr -> Frl
+  Frl [label="..."]
+  Fr -> Frr
+  Frr [label="..."]
+
+  G [label="110"]
+  G -> Gl [label="L"]
+  Gl [label="SKIP"]
+  G -> Gr [label="R"]
+  Gr [label="VERIFY"]
+
+  H [label="111"]
+  H -> Hl [label="L"]
+  Hl [label="SKIP"]
+  H -> Hr [label="R"]
+  Hr [label="DESCEND"]
+  Hr -> Hrl
+  Hrl [label="..."]
+  Hr -> Hrr
+  Hrr [label="..."]
+
+  Crl -> F [style=invis]
+  { rank = same; F; G; H; }
+}
diff --git a/bip-0098/node-variants.png b/bip-0098/node-variants.png
new file mode 100644
index 0000000..991d7bc
--- /dev/null
+++ b/bip-0098/node-variants.png
diff --git a/bip-0098/skip-skip.dot b/bip-0098/skip-skip.dot
new file mode 100644
index 0000000..5e633d6
--- /dev/null
+++ b/bip-0098/skip-skip.dot
@@ -0,0 +1,7 @@
+digraph G {
+  A [label="???"]
+  A -> Al [label="L"]
+  Al [label="SKIP"]
+  A -> Ar [label="R"]
+  Ar [label="SKIP"]
+}
\ No newline at end of file
diff --git a/bip-0098/skip-skip.png b/bip-0098/skip-skip.png
new file mode 100644
index 0000000..d3e7c45
--- /dev/null
+++ b/bip-0098/skip-skip.png
diff --git a/bip-0098/traversal-example.dot b/bip-0098/traversal-example.dot
new file mode 100644
index 0000000..2993642
--- /dev/null
+++ b/bip-0098/traversal-example.dot
@@ -0,0 +1,32 @@
+digraph G {
+  a [label="A\n101"]
+  a -> b
+  a -> c
+
+  b [label="B\n111"]
+  b -> s0
+  s0 [label="SKIP\n0x00..."]
+  b -> d
+
+  d [label="D\n011"]
+  d -> f
+  d -> s1
+  s1 [label="SKIP\n0x22..."]
+
+  f [label="F\n000"]
+  f -> v1
+  v1 [label="VERIFY\n0x55..."]
+  f -> s2
+  s2 [label="SKIP\n0x66..."]
+
+  c [label="C\n010"]
+  c -> v2
+  v2 [label="VERIFY\n0x11..."]
+  c -> e
+
+  e [label="E\n001"]
+  e -> v3
+  v3 [label="VERIFY\n0x33..."]
+  e -> v4
+  v4 [label="VERIFY\n0x44..."]
+}
diff --git a/bip-0098/traversal-example.png b/bip-0098/traversal-example.png
new file mode 100644
index 0000000..a6a7954
--- /dev/null
+++ b/bip-0098/traversal-example.png
diff --git a/bip-0098/unbalanced-hash-tree.dot b/bip-0098/unbalanced-hash-tree.dot
new file mode 100644
index 0000000..c637652
--- /dev/null
+++ b/bip-0098/unbalanced-hash-tree.dot
@@ -0,0 +1,11 @@
+digraph G {
+  0 [label="Root\nH(A || H(B || C))"]
+  0 -> A
+  A [label="A\nskip"]
+  0 -> 1
+  1 [label="Node\nH(B || C)"]
+  1 -> B
+  B [label="B\nskip"]
+  1 -> C
+  C [label="C\nverify"]
+}
diff --git a/bip-0098/unbalanced-hash-tree.png b/bip-0098/unbalanced-hash-tree.png
new file mode 100644
index 0000000..339bb22
--- /dev/null
+++ b/bip-0098/unbalanced-hash-tree.png
diff --git a/bip-0116.mediawiki b/bip-0116.mediawiki
new file mode 100644
index 0000000..e2a1daf
--- /dev/null
+++ b/bip-0116.mediawiki
@@ -0,0 +1,145 @@
+<pre>
+  BIP: 116
+  Layer: Consensus (soft fork)
+  Title: MERKLEBRANCHVERIFY
+  Author: Mark Friedenbach <mark@friedenbach.org>
+          Kalle Alm <kalle.alm@gmail.com>
+          BtcDrak <btcdrak@gmail.com>
+  Comments-Summary: No comments yet.
+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0116
+  Status: Draft
+  Type: Standards Track
+  Created: 2017-08-25
+  License: CC-BY-SA-4.0
+  License-Code: MIT
+</pre>
+
+==Abstract==
+
+A general approach to bitcoin contracts is to fully enumerate the possible spending conditions and then program verification of these conditions into a single script.
+At redemption, the spending condition used is explicitly selected, e.g. by pushing a value on the witness stack which cascades through a series if if/else constructs.
+
+This approach has significant downsides, such as requiring all program pathways to be visible in the scriptPubKey or redeem script, even those which are not used at validation.
+This wastes space on the block chain, restricts the size of possible scripts due to push limits, and impacts both privacy and fungibility as details of the contract can often be specific to the user.
+
+This BIP proposes a new soft-fork upgradeable opcode, MERKLEBRANCHVERIFY, which allows script writers to commit to a set of data elements and have one or more of these elements be provided at redemption without having to reveal the entire set.
+As these data elements can be used to encode policy, such as public keys or validation subscripts, the MERKLEBRANCHVERIFY opcode can be used to overcome these limitations of existing bitcoin script.
+
+==Copyright==
+
+This BIP is licensed under a Creative Commons Attribution-ShareAlike license. All provided source code is licensed under the MIT license.
+
+==Specification==
+
+MERKLEBRANCHVERIFY redefines the existing NOP4 opcode.
+When executed, if any of the following conditions are true, the script interpreter will terminate with an error:
+
+# the stack contains less than three (3) items;
+# the first item on the stack is more than 2 bytes;
+# the first item on the stack, interpreted as an integer, N, is negative or not minimally encoded;
+# the second item on the stack is not exactly 32 bytes;
+# the third item on the stack is not a serialized Merkle tree inclusion proof as specified by BIP98[1] and requiring exactly <code>floor(N/2)</code> VERIFY hashes; or
+# the remainder of the stack contains less than <code>floor(N/2)</code> additional items, together referred to as the input stack elements.
+
+If the low-order bit of N is clear, <code>N&1 == 0</code>, each input stack element is hashed using double-SHA256.
+Otherwise, each element must be exactly 32 bytes in length and are interpreted as serialized hashes.
+These are the VERIFY hashes.
+
+If the fast Merkle root computed from the Merkle tree inclusion proof, the third item on the stack,
+with the VERIFY hashes in the order as presented on the stack, from top to bottom,
+does not exactly match the second item on the stack,
+the script interpreter will terminate with an error.
+
+Otherwise, script execution will continue as if a NOP had been executed.
+
+==Motivation==
+
+Although BIP16 (Pay to Script Hash)[2] and BIP141 (Segregated Witness)[3] both allow the redeem script to be kept out of the scriptPubKey and therefore out of the UTXO set, the entire spending conditions for a coin must nevertheless be revealed when that coin is spent.
+This includes execution pathways or policy conditions which end up not being needed by the redemption.
+Not only is it inefficient to require this unnecessary information to be present on the blockchain, albeit in the witness, it also impacts privacy and fungibility as some unused script policies may be identifying.
+Using a Merkle hash tree to commit to the policy options, and then only forcing revelation of the policy used at redemption minimizes this information leakage.
+
+Using Merkle hash trees to commit to policy allows for considerably more complex contracts than would would otherwise be possible, due to various built-in script size and runtime limitations.
+With Merkle commitments to policy these size and runtime limitations constrain the complexity of any one policy that can be used rather than the sum of all possible policies.
+
+==Rationale==
+
+The MERKLEBRANCHVERIFY opcode uses fast Merkle hash trees as specified by BIP98[1] rather than the construct used by Satoshi for committing transactions to the block header as the later has a known vulnerability relating to duplicate entries that introduces a source of malleability to downstream protocols[4].
+A source of malleability in Merkle proofs could potentially lead to spend vulnerabilities in protocols that use MERKLEBRANCHVERIFY.
+For example, a compact 2-of-N policy could be written by using MERKLEBRANCHVERIFY to prove that two keys are extracted from the same tree, one at a time, then checking the proofs for bitwise equality to make sure the same entry wasn't used twice.
+With the vulnerable Merkle tree implementation there are privledged positions in unbalanced Merkle trees that allow multiple proofs to be constructed for the same, single entry.
+
+BIP141 (Segregated Witness)[3] provides support for a powerful form of scirpt upgrades called script versioning, which is able to achieve the sort of upgrades which would previously have been hard-forks.
+If script versioning were used for deployment then MERKLEBRANCHVERIFY could be written to consume its inputs, which would provide a small 2-byte savings for many anticipated use cases.
+However the more familiar NOP-expansion soft-fork mechanism used by BIP65 (CHECKLOCKTIMEVERIFY)[5] and BIP112 (CHECKSEQUENCEVERIFY)[6] was chosen over script versioning for the following two reasons:
+
+# '''Infrastructure compatibility.''' Using soft-fork NOP extensions allows MERKLEBRANCHVERIFY to be used by any existing software able to consume custom scripts, and results in standard P2SH or P2WSH-nested-in-P2SH addresses without the need for BIP143[7] signing code. This allows MERKLEBRANCHVERIFY to be used immediately by services that need it rather than wait on support for script versioning and/or BIP-143[7] signatures in tools and libraries.
+# '''Delayed decision on script upgrade protocol.''' There are unresolved issues with respect to how script versioning should be used for future script upgrades. There are only 16 available script versions reserved for future use, and so they should be treated as a scarce resource. Additionally, script feature versioning should arguably be specified in the witness and the BIP141 script versioning only be used to specify the structure of the witness, however no such protocol exists as of yet. Using the NOP-expansion space prevents MERKLEBRANCHVERIFY from being stalled due to waiting on script upgrade procedure to be worked out, while making use of expansion space that is already available.
+
+The MERKLEBRANCHVERIFY opcode allows for VERIFY hashes to be presented directly, or calculated from the leaf values using double-SHA256.
+In most cases the latter approach is expected to be used so that the leaf value(s) can be used for both branch validation and other purposes without any explicit preprocessing.
+However allowing already-calculated hash values as inputs enables using chained MERKLEBRANCHVERIFY opcodes to verify branches of trees with proofs large enough that they would not fit in the 520 byte script push limitation.
+As specified, a 30-branch path can be verified by proving the path from the leaf to the 15th interior node as the 'root', then proving that node's hash to be a child of the actual Merkle tree root hash.
+Validation of a 256-branch path (e.g. a binary prefix tree with a hash value as key) would require 18 chained validations, which would fit within current script limitations.
+
+==Applications==
+
+===1-of-N for large N===
+
+Here is a redeem script that allows a coin to be spent by any key from a large set, without linear scaling in script size:
+
+  redeemScript: <root> 2 MERKLEBRANCHVERIFY 2DROP DROP CHECKSIG
+  witness: <sig> <pubkey> <proof>
+
+The redeem script looks very similar to the standard pay-to-pubkey-hash, except instead of showing that the pubkey's hash is the same as the commitment given, we demonstrate that the pubkey is one of potentially many pubkeys included in the Merkle tree committed to in the redeem script.
+The low-order bit of the first parameter, 2, is clear, meaning that there is one input (<code>(2>>1) == 1</code>), the serialized pubkey, and its VERIFY hash needs to be calculated by MERKLEBRANCHVERIFY using double-SHA256.
+
+===Honeypots===
+
+As described by Pieter Wuille[8] the 1-of-N scheme is particularly useful for constructing honeypots.
+The desire is to put a large bounty on a server, larger than the value of the server itself so that if the server is compromised it is highly likely that the hacker will claim the bitcoin, thereby revealing the intrusion.
+However if there are many servers, e.g. 1,000, it becomes excessively expensive to lock up separate bounties for each server.
+It would be desireable if the same bounty was shared across multiple servers in such a way that the spend would reveal which server was compromised.
+
+This is accomplished by generating 1,000 different keys, building a hash tree of these public keys, and placing each key and associated Merkle path on separate servers.
+When the honeypot is claimed, the (previous) owner of the coins can tell which server was compromised from the key and path used to claim the funds.
+
+==Implementation==
+
+An implementation of this BIP, including both consensus code updates and tests is available at the following Github repository:
+
+[https://github.com/maaku/bitcoin/tree/merkle-branch-verify]
+
+==Deployment==
+
+This BIP will be deployed by BIP8 (Version bits with lock-in by height)[9] with the name "merklebranchverify" and using bit 2.
+
+For Bitcoin mainnet, the BIP8 startheight will be at height M to be determined and BIP8 timeout activation will occur on height M + 50,400 blocks.
+
+For Bitcoin testnet, the BIP8 startheight will be at height T to be determined and BIP8 timeout activation will occur on height T + 50,400 blocks.
+
+We note that DISCOURAGE_UPGRADABLE_NOPS means that transactions which use this feature are already considered non-standard by the rules of the network, making deployment easier than was the case with, for example, with BIP68 (Relative lock-time using consensus-enforced sequence numbers)[9].
+
+==Compatibility==
+
+Old clients will consider the OP_MERKLEBRANCHVERIFY as a NOP and ignore it. Proof will not be verified, but the transaction will be accepted.
+
+==References==
+
+[1] [https://github.com/bitcoin/bips/blog/master/bip-0098.mediawiki BIP98: Fast Merkle Trees (Consensus layer)]
+
+[2] [https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki BIP16: Pay to Script Hash]
+
+[3] [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141: Segregated Witness (Consensus layer)]
+
+[4] [https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2012-2459 National Vulnerability Database: CVE-2012-2459]
+
+[5] [https://github.com/bitcoin/bips/blob/master/bip-0065.mediawiki BIP65: OP_CHECKLOCKTIMEVERIFY]
+
+[6] [https://github.com/bitcoin/bips/blob/master/bip-0112.mediawiki BIP112: CHECKSEQUENCEVERIFY]
+
+[7] [https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki BIP143: Transaction Signature Verification for Version 0 Witness Program]
+
+[8] [https://blockstream.com/2015/08/24/treesignatures.html Multisig on steroids using tree signatures]
+
+[9] [https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP68: Relative lock-time using consensus-enforced sequence numbers]
diff --git a/bip-0117.mediawiki b/bip-0117.mediawiki
new file mode 100644
index 0000000..ab5af61
--- /dev/null
+++ b/bip-0117.mediawiki
@@ -0,0 +1,199 @@
+<pre>
+  BIP: 117
+  Layer: Consensus (soft fork)
+  Title: Tail Call Execution Semantics
+  Author: Mark Friedenbach <mark@friedenbach.org>
+          Kalle Alm <kalle.alm@gmail.com>
+          BtcDrak <btcdrak@gmail.com>
+  Comments-Summary: No comments yet.
+  Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0117
+  Status: Draft
+  Type: Standards Track
+  Created: 2017-08-25
+  License: CC-BY-SA-4.0
+  License-Code: MIT
+</pre>
+
+==Abstract==
+
+BIP16 (Pay to Script Hash)[1] and BIP141 (Segregated Witness)[2] provide mechanisms by which script policy can be revealed at spend time as part of the execution witness.
+In both cases only a single script can be committed to by the construct.
+While useful for achieving the goals of these proposals, they still require that all policies be specified within the confine of a single script, regardless of whether the policies are needed at the time of spend.
+
+This BIP, in conjunction with BIP116 (MERKLEBRANCHVERIFY)[3] allows for a script to commit to a practically unbounded number of code pathways, and then reveal the actual code pathway used at spend time.
+This achieves a form of generalized MAST[4] enabling decomposition of complex branching scripts into a set of non-branching flat execution pathways, committing to the entire set of possible pathways, and then revealing only the path used at spend time.
+
+==Copyright==
+
+This BIP is licensed under a Creative Commons Attribution-ShareAlike license. All provided source code is licensed under the MIT license.
+
+==Specification==
+
+If, at the end of script execution:
+
+* the execution state is non-clean, meaning
+*# the main stack has more than one item on it, or
+*# the main stack has exactly one item and the alt-stack is not empty;
+* the top-most element of the main stack evaluates as true when interpreted as a bool; and
+* the top-most element is not a single byte or is outside the inclusive range of <code>0x51</code> to <code>0x60</code>,
+
+then that top-most element of the main stack is popped and interpreted as a serialized script and executed,
+while the remaining elements of both stacks remain in place as inputs.
+
+If the above conditions hold except for the last one, such that:
+
+* the top-most element ''is'' a single byte within the inclusive range of <code>0x51</code> (<code>OP_1</code>, meaning N=2) to <code>0x60</code> (<code>OP_16</code>, meaning N=17);
+
+and:
+
+* the next N-1 elements on the main stack (continuing on the alt stack if the main stack is exhausted) are 520 byte pushes; and
+* the following Nth element on the main stack (or alt stack, as above) is between 1 and 520 bytes,
+
+then the top-most element of the main stack is dropped,
+and the N=2 (<code>0x51</code>) to 17 (<code>0x60</code>) further elements are popped from the main stack,
+continuing from the alt stack if the main stack is exhausted,
+and concatinated together in reverse order to form a serialized script,
+which is then executed with the remaining elements of both stacks remaining in place as inputs.
+
+The presence of CHECKSIG or CHECKMULTISIG within the subscript do not count towards the global MAX_BLOCK_SIGOPS_COST limit,
+and the number of non-push opcodes executed in the subscript is not limited by MAX_OPS_PER_SCRIPT.
+Execution state, other than the above exceptions, carries over into the subscript,
+and termination of the subscript terminates execution of the script as a whole.
+This is known as execution with tail-call semantics.
+
+Only one such tail-call of a subscript is allowed per script execution context, and only from within a segwit redeem script.
+Alternatively stated, neither evaluation of witness stack nor execution of the scriptPubKey or scriptSig or P2SH redeem script results in tail-call semantics.
+
+==Motivation==
+
+BIP16 (Pay to Script Hash)[1] and BIP141 (Segregated Witness)[2] allow delayed revelation of a script's policy until the time of spend.
+However these approaches are limited in that only a single policy can be committed to in a given transaction output.
+It is not possible to commit to multiple policies and then choose, at spend time, which to reveal.
+
+BIP116 (MERKLEBRANCHVERIFY)[3] allows multiple data elements to be committed to while only revealing those necessary at the time of spend.
+The MERKLEBRANCHVERIFY opcode is only able to provide commitments to a preselected set of data values, and does not by itself allow for executing code.
+
+This BIP generalizes the approach of these prior methods by allowing the redeem script to perform any type of computation necessary to place the policy script on the stack.
+The policy script is then executed from the top of the data stack in a way similar to how BIP16 and BIP141 enable redeem scripts to be executed from the top of the witness stack.
+In particular, using MERKLEBRANCHVERIFY[3] in the scriptPubKey or redeem script allows selection of the policy script that contains only the necessary conditions for validation of the spend.
+This is a form of generalized MAST[4] where a stage of precomputation splits a syntax tree into possible execution pathways, which are then enumerated and hashed into a Merkle tree of policy scripts.
+At spend time membership in this tree of the provided policy script is proven before execution recurses into the policy script.
+
+==Rationale==
+
+This proposal is a soft-fork change to bitcoin's consensus rules because leaving a script that data-wise evaluates as true from its serialized form on the stack as execution terminates would result in the script validation returning true anyway.
+Giving the subscript a chance to terminate execution is only further constraining the validation rules.
+The only scripts which would evaluate as false are the empty script, or a script that does nothing more than push empty/zero values to the stack.
+None of these scripts have any real-world utility, so excluding them to achieve soft-fork compatibility doesn't come with any downsides.
+
+By restricting ourselves to tail-call evaluation instead of a more general EVAL opcode we greatly simplify the implementation.
+Tail-call semantics means that execution never returns to the calling script's context, and therefore no state needs to be saved or later restored.
+The implementation is truly as simple as pulling the subscript off the stack, resetting a few state variables, and performing a jump back to the beginning of the script interpreter.
+
+The restriction to allow only one layer of tail-call recursion is admittedly limiting, however the technical challenges to supporting multi-layer tail-call recursion are significant.
+A new metric would have to be developed to track script resource usage, for which transaction data witness size are only two factors.
+This new weight would have to be relayed with transactions, used as the basis for fee calculation, validated in-line with transaction execution, and policy decided upon for DoS-banning peers that propagate violating transactions.
+
+However should these problems be overcome, dropping the single recursion constraint is itself a soft-fork for the same reason, applied inductively.
+Allowing only one layer of tail-call recursion allows us to receive the primary benefit of multi-policy commitments / generalized MAST,
+while leaving the door open to future generalized tail-call recursion if and when the necessary changes are made to resource accounting and p2p transaction distribution.
+
+The global SIGOP limit and per-script opcode limits do not apply to the policy script
+because dynamic selection of the policy script makes it not possible for static analysis tools to verify these limits in general,
+and because performance improvements to libsecp256k1 and Bitcoin Core have made these limits no longer necessary as they once were.
+The validation costs are still limited by the number of signature operations it is possible to encode within block size limits,
+and the maximum script size per input is still limited to 10,000 bytes.
+
+To allow for this drop of global and per-script limits,
+tail-call evaluation cannot be allowed for direct execution of the scriptPubKey,
+as such scripts are fetched from the UTXO and do not count towards block size limits of the block being validated.
+Likewise tail-call from P2SH redeem scripts is not supported due to quadratic blow-up vulnerabilities that are fixed in segwit.
+
+==Generalized MAST==
+
+When combined with BIP116 (MERKLEBRANCHVERIFY)[3], tail-call semantics allows for generalized MAST capabilities[4].
+The script author starts with a full description of the entire contract they want to validate at the time of spend.
+The possible execution pathways through the script are then enumerated, with conditional branches replaced by a validation of the condition and the branch taken.
+The list of possible execution pathways is then put into a Merkle tree, with the flattened policy scripts as the leaves of this tree.
+The final redeem script which funds are sent to is as follows:
+
+  redeemScript: OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP
+  witness: <nowiki><argN> ... <arg1> <policyScript> <proof></nowiki>
+
+Where <code>policyScript</code> is the flattened execution pathway, <code>proof</code> is the serialized Merkle branch and path that proves the policyScript is drawn from the set used to construct the Merkle tree <code>root</code>, and <code>arg1</code> through <code>argN</code> are the arguments required by <code>policyScript</code>.
+The <code>OVER HASH256</code> copies the subscript and performs the double-SHA256 hash necessary to prepare the leaf hash value for MERKLEBRANCHVERIFY, and the <code>2DROP 2DROP</code> is necessary to remove the arguments to MERKLEBRANCHVERIFY from the stack.
+
+The above example was designed for clarity, but actually violates the CLEANSTACK rule of segwit v0 script execution.
+Unless the CLEANSTACK rule is dropped or modified in a new segwit output version, this would script would have to be modified to use the alt-stack, as follows:
+
+  redeemScript: <nowiki>[TOALTSTACK]*N OVER HASH256 <root> 1 MERKLEBRANCHVERIFY 2DROP 2DROP</nowiki>
+  witness: <nowiki><policyScript> <proof> <arg1> ... <argN></nowiki>
+
+Where <code>[TOALTSTACK]*N</code> is the TOALTSTACK opcode repeated N times.
+This moves <code>arg1</code> through <code>argN</code> to the alt-stack in reverse order, such that <code>arg1</code> is on the top of the alt-stack when execution of <code>policyScript</code> begins.
+The <code>policyScript</code> would also have to be modified to fetch its arguments from the alt-stack, of course.
+
+If the total set of policy scripts includes scripts that take a varying number of parameters, that too can be supported, within reasonable limits.
+The following redeem script allows between 1 and 3 witness arguments in addition to the policy script and Merkle proof:
+
+  witness: <nowiki><policyScript> <proof> <arg1> ... <argN></nowiki> // N is between 1 and 3
+  redeemScript: DEPTH TOALTSTACK                    // Save number of witness elements to alt-stack
+                TOALTSTACK                          // Save 1st element (required) to alt-stack
+                DEPTH 2 SUB                         // Calculate number of optional elements, ignoring policyScript and proof
+                DUP IF SWAP TOALTSTACK 1SUB ENDIF   // Save 2nd element (optional) to alt-stack, if it is present
+                IF TOALTSTACK ENDIF                 // Save 3rd element (optional) to alt-stack, if it is present; consume counter
+                OVER HASH256 <nowiki><root></nowiki> 1 MERKLEBRANCHVERIFY 2DROP 2DROP
+  alt-stack: <nowiki><N+2> <argN> ... <arg1></nowiki>
+
+Because the number of witness elements is pushed onto the alt-stack, this enables policy scripts to verify the number of arguments passed, even though the size of the alt-stack is not usually accessible to script.
+The following policy script for use with the above redeem script will only accept 2 witness elements on the alt-stack, preventing witness malleability:
+
+  policyScript: <nowiki>FROMALTSTACK ...check arg1... FROMALTSTACK ...check&consume arg2/arg1&2... FROMALTSTACK 4 EQUAL
+
+The number 4 is expected as that includes the <code>policyScript</code> and <code>proof</code>.
+
+The verbosity of this example can be prevented by using a uniform number of witness elements as parameters for all policy subscripts, eliminating the conditionals and stack size counts.
+Future script version upgrades should also consider relaxing CLEANSTACK rules to allow direct pass-through of arguments from the witness/redeem script to the policy script on the main stack.
+
+===Comparison with BIP114===
+
+BIP114 (Merkelized Abstract Syntax Tree)[5] specifies an explicit MAST scheme activated by BIP141 script versioning[2].
+Unlike BIP114, the scheme proposed by this BIP in conjunction with BIP116 (MERKLEBRANCHVERIFY)[3] implicitly enables MAST constructs using script itself to validate membership of the policy script in the MAST.
+This has the advantage of requiring vastly fewer consensus code changes, as well as potentially enabling future script-based innovation without requiring any further consensus code changes at all, as the MAST scheme itself is programmable.
+
+Furthermore, by adding MERKLEBRANCHVERIFY and tail-call semantics to all script using the NOP-expansion space, BIP141 style script versioning is not required.
+This removes a potentially significant hurdle to deployment by making this feature not dependent on resolving outstanding issues over address formats, how script version upgrades should be deployed, and consensus over what other features might go into a v1 upgrade.
+
+==Implementation==
+
+An implementation of this BIP, including both consensus code changes and tests are available at the following Github repository:
+
+[https://github.com/maaku/bitcoin/tree/tail-call-semantics]
+
+==Deployment==
+
+This BIP will be deployed by BIP8 (Version bits with lock-in by height)[9] with the name "tailcall" and using bit 3.
+
+For Bitcoin mainnet, the BIP8 startheight will be at height M to be determined and BIP8 timeout activation will occur on height M + 50,400 blocks.
+
+For Bitcoin testnet, the BIP8 startheight will be at height T to be determined and BIP8 timeout activation will occur on height T + 50,400 blocks.
+
+We note that CLEANSTACK means that transactions which use this feature are already considered non-standard by the rules of the network, making deployment easier than was the case with, for example, with BIP68 (Relative lock-time using consensus-enforced sequence numbers)[6].
+
+==Compatibility==
+
+The v0 segwit rules prohibit leaving anything on the stack, so for v0 parameters have to be passed on the alt stack for compatibility reasons.
+
+==References==
+
+[1] [https://github.com/bitcoin/bips/blob/master/bip-0016.mediawiki BIP16: Pay to Script Hash]
+
+[2] [https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki BIP141: Segregated Witness (Consensus Layer)]
+
+[3] [https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki BIP116: MERKLEBRANCHVERIFY]
+
+[4] "[https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-September/015028.html An explanation and justification of the tail-call and MBV approach to MAST]", Mark Friedenbach, Bitcoin Development Mailing List, 20 September 2017.
+
+[5] [https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki BIP114: Merkelized Abstract Syntax Tree]
+
+[6] [https://github.com/bitcoin/bips/blob/master/bip-0068.mediawiki BIP68: Relative lock-time using consensus-enforced sequence numbers]