WIP: RFC 1 : Abstract Syntax Tree-based output script locks

Update 2 : Rewriting with way better format to fix flaws of the first draft.

In the current Duniter protocol input and output conditions are stored in machine-readable BNF text format. This is good for human readability, but it requires parsing and takes place due to its textual format.

To lower blocksize and transactions weights; or to allow more complex conditions, it could be preferable to use a more simple binary format which need little or no parsing, close to memory and that can be converted back to text format. It can also allow to add new features without hard-forking the protocol.

0001-ast-script-lock.md

+```
+DUIP: 1
+Title: "Abstract Syntax Tree"-based output script locks.
+Author: Nanocryk <nanocryk@gmail.com>
+Status: Proposition
+Type: Hard-fork (transaction document)
+Created: 2017-11-22
+License: GPL-3
+```
+
+> This document is currently being written and thus it's not complete. Specifications may change in the future.
+
+# Abstract
+
+In the current Duniter protocol input and output conditions are stored in machine-readable BNF text format. This is good for human readability, but it requires parsing and takes place due to its textual format.
+
+To lower blocksize and transactions weights; or to allow more complex condtions, it could be preferable to use a more simple binary format which need little or no parsing, close to memory and that can be converted back to text format. It can also allow to add new features without hard-forking the protocol.
+
+# Table of Contents
+
+1. [Basic script structure](#1-basic-script-structure)  
+  1.1. [Scripts as ASTs](#11-scripts-as-asts)  
+  1.2. [Signatures (`SIG`)](#12-signatures-sig)  
+  1.3. [Unlock inputs (`INPUT`)](#13-unlock-inputs-input)  
+  1.4. [Avoid redudancies (`INCLUDE`)](#14-avoid-redudancies-include)  
+  1.5. [Avoid providing unused branches (`BRANCH_HASH`/`SCRIPT_HASH`)](#15-avoid-providing-unused-branches-branch_hashscript_hash)  
+
+# 1. Basic script structure
+
+# 1.1. Scripts as ASTs
+
+An output script allow to define conditions on how funds can be spent. The most basic case is to lock funds with a given public key, and requiring a signature (made with the associated private key) to use them as input of a new transaction.
+Since we define a *conditon*, we can express it as a *boolean function*.
+
+We want to be able to have multiple ways of spending an output, such as mutli-signatures or time locks. It means we must have *operators* which combines multiples conditions into one. One ways to store these functions are as *Abstract Syntax Tree*s : Each operator is a tree with its inputs as leaves. This leaves can be primitive values or other operators.
+
+For a classic 1-signature lock, an AST could look like :
+
+```
+           SIG
+            |
+      -------------      
+  PublicKey   Signature
+```
+- `SIG` would be an operator verifying the association between the signature and the public key.
+- `PublicKey` is stored in the script.
+- `Signature` is provided as an input when unlocking funds.
+
+If we want a *1 out of 2 signatures*, we could have :
+
+``` 
+                          OR
+                          |
+             ----------------------------
+            SIG                        SIG
+             |                          |
+      ---------------            --------------
+  PublicKeyA   SignatureA   PublicKeyB   SignatureB
+```
+
+- `OR` would be an operator returning `true` if at least one input is `true`.
+
+For a *2 out of 3 signatures*, we could have :
+
+``` 
+                                                             GREAT_EQ
+                                        -------------------------------------------
+                                       SUM                                        2
+                                        |
+             ----------------------------------------------------
+            SIG                        SIG                      SIG
+             |                          |                        |
+      ---------------            --------------           ---------------
+  PublicKeyA   SignatureA   PublicKeyB   SignatureB   PublicKeyC   SignatureC
+```
+
+- `SUM` would be an operator computing the sum of its leaves.
+- `GREAT_EQ` would be an operator comparing if the *left operande* is *greater or equal* to the *right operande*.
+
+# 1.2. Signatures (`SIG`)
+
+We want our system to cover as many cases as possible. Currently the Duniter protocol use only [Ed25519][ed25519] signatures, but it could in the future use othe schemes such as [Schnorr signatures][schnorr].
+
+[ed25519]: https://en.wikipedia.org/wiki/EdDSA
+[schnorr]: https://en.wikipedia.org/wiki/Schnorr_signature
+
+We also want the impossibility to change a script defined as an unlock condition, so the content of the script must be signed, and this signature required to unlock the funds.
+
+It means multiple things :
+
+- Our `SIG` operator should be usable with multiple cryptographic systems. We must have a parameter provided which system is used.
+- Since keys and signatures lengths may vary from a system to another, it should accept inputs of any length.
+- We'll use document signatures as signature source. We need an operator to fetch this data from the document.
+
+With these requirements we have : 
+
+- `SIG` operator defined as `SIG(System, PublicKey, Signature)`.
+- An operator capable of providing data of any length.
+- An operator capable of fetching data outside of script.
+
+# 1.3 Unlock inputs (`INPUT`)
+
+When a user want to spend an output, it must provide inputs to unlock funds as values making the lock script returns true. To allow complex scripts, the values are *AST*s.
+
+Inputs are stored as list of pairs of indexes and ASTs. To allow complex conditions, these values are stored as ASTs.
+
+A script can use an `INPUT(Index)` operator returning the input.
+
+# 1.4. Avoid redudancies (`INCLUDE`)
+
+Some script may required in multiple places the same computed result. To avoid redudancies, we allow to provide a script with multiple ASTs. Each script is executed in order and only the output of the last is taken as the result. A script can use the result of an above script with an `INCLUDE` operator. With this structure it's not possible to have recursion or cycles which avoid infinite loops and Turing-Completeness.
+
+# 1.5. Avoid providing unused branches (`BRANCH_HASH`/`SCRIPT_HASH`)
+
+It could be bad for privacy to expose a complete script with all of the possibilities of spending an output. With the usage of merkelized scripts, we allow the user to provide only the hash of an unused branch which can be used to prove the script is valid while not provide its complete definition.
+
+We define a hash (on 32 bytes) as `HASH(Branch) = SHA256(OperatorCode + HASH(Child0) + HASH(Child1) + ...)`. Since we want to use provide only the hash of a branch while keeping the script valid, we defined an operator `BRANCH_HASH(Hash)` for which `HASH(BRANCH_HASH(Hash)) = Hash`. To allow only hashes of unused branches, this operator will return an `Undefined` value and should be used with aggregators such as `OR` or `SUM`.
+
+Then we can define a `SCRIPT_HASH` operator taking the AST and it's root hash. It will first verify that the hash is correct, then execute it.
+
+# 2. Script chains
+
+# 3. Binary format
+
+# 3.1. Operators
+
+We store an operator as a **1 byte** value representing its type :
+
+- `0x00` or `VALUE <Size:1> <Value:Size>`  
+  Return given `Value` of given `Size`.  
+  `Value` must have a size of `Size` bytes or the script is unreadable and thus invalid.
+- `0x01` or `INPUT <Index:1>`    
+  Return an input parameters as an *AST*.  
+  It this input don't exist, `Undefined` is returned.
+- `0x02` or `DOCSIG <Index:1>`  
+  Return the signature from the document signatures zone as a `VALUE`.  
+  If this signature don't exist, `Undefined` is returned.  
+- `0x03` or `INCLUDE <Index:1>`  
+  Return the `VALUE` returned by another script.
+- `0x04` or `BRANCH_HASH <Hash:32>`  
+  Return `Undefined`.  
+  It's hash is the provided `Hash`.
+- `0x05` or `SCRIPT_HASH <Hash:32> <Script:AST>`  
+  Return script result `VALUE` is the hash is correct, `Undefined` otherwise.
\ No newline at end of file