Skip to content
Snippets Groups Projects

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

Closed WIP: RFC 1 : Abstract Syntax Tree-based output script locks
dip/0001 into master
Closed nanocryk requested to merge dip/0001 into master
Compare
and
1 file
+ 300
− 0
Compare changes
  • Side-by-side
  • Inline
DIP0001.md 0 → 100644
+ 300
− 0
 
```
 
DIP: 1
 
Title: New transaction output script system using Abstract Syntaxic Trees
 
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.
 
 
# Script AST exemples
 
 
A output script condition can be represented as a tree composed on different operators as branches, and input data as leaves.
 
 
With an operator `ED(pubkey, signature)` we can check if the current document is signed with the provided public key :
 
 
```
 
ED
 
------------
 
| |
 
pubkey signature
 
```
 
 
With a `OR(branches)` we can test 1 out of 2 signatures :
 
 
```
 
OR
 
----------------------
 
ED ED
 
| |
 
------------ ------------
 
| | | |
 
pubkey signature pubkey signature
 
```
 
 
With `SUM(branches)` and `GE(a,b)` operators when can check easely for a 2 out of 3 signatures :
 
 
```
 
GE
 
---------
 
SUM 2
 
|
 
-------------------------------------------
 
ED ED ED
 
| | |
 
------------ ------------ ------------
 
pubkey signature pubkey signature pubkey signature
 
```
 
 
# Binary representation
 
 
As seen in exemples above, we have to manage different types of tree nodes :
 
 
- **Operators** : above some branches and operate on them
 
- **Local values of different types** : leaf nodes with values stored in the script (like pubkeys)
 
- **Extern values** : leaf nodes with values provided as input to the script (like signatures)
 
 
We'll also need a valid way to not provide an ununsed/undefined input, and another one to provide the hash of an AST.
 
 
We can define opcodes to encode this information :
 
 
| Code | Name | Description | Parameters
 
|:------:|:----------:|:-----------------|:-------------
 
| `0x00` | `NOP` | Nothing/void | None
 
| `0x01` | `EXT` | Extern value | `<input index>`
 
| `0x02` | `MASTH` | MAST hash | `<AST>`
 
| `0x03` | `DOCSIG` | Fetch document signature (U64) | `<signature index>`
 
| `0x04` | `APP` | Append other script | `<script index>`
 
| | | |
 
| `0x08` | `U8` | 1 byte value | `<value>`
 
| `0x09` | `U16` | 2 bytes value | `<value>`
 
| `0x0a` | `U32` | 4 bytes value | `<value>`
 
| `0x0b` | `U64` | 8 bytes value | `<value>`
 
| `0x0c` | `U128` | 16 bytes value | `<value>`
 
| `0x0d` | `U256` | 32 bytes value | `<value>`
 
| `0x0e` | `U512` | 64 bytes value | `<value>`
 
| `0x0f` | `U1024` | 128 bytes value | `<value>`
 
 
All other AST opcodes are defined with this syntax :
 
`<opcode> <children count (1 byte)> <children data>`
 
 
To allow as many opcodes as we need, we define opcodes in range `[0x05;0xfe]`. With `0xff`, the next byte is accounted in opcode resolution, and can again be `0xff`. Thus `0xffff14` is a valid opcode.
 
 
Since `children count` is stored in 1 byte, the maximum number of children is 255. For most cases it's not a problem since you can apply your operator on 2 smaller subsets and combine them after.
 
 
```
 
AND 300 <child 1> <child2> ...
 
```
 
 
can be expressed as
 
 
```
 
AND 2
 
AND 150 <child 1> <child2> ...
 
AND 150 <child 151> <child152> ...
 
```
 
 
`APP` operator append at execution another script store aside the main script. This structure will be defined in a document format document (DIP0002).
 
At script execution the whole AST will be builded from the main script and input parameters. Any recursive insertion will fail and make the script invalid.
 
This operator can be usefull to use the same result in multiple places of the script.
 
One optimisation at execution is to execute all script in reverse dependency order (first the one with no dependencies, then ones depending on it) and store the result, so this script is only executed once.
 
 
# List of operators
 
 
| Code | Name | Description | Return type | Children
 
|:------:|:----------:|:------------|:-----------:|:--------
 
| `0x10` | `NOT` | Binary NOT | Boolean (U8)| 1 boolean (U8)
 
| `0x11` | `OR` | Binary OR | Boolean (U8)| Any amount of booleans (U8)
 
| `0x12` | `AND` | Binary AND | Boolean (U8)| Any amount of booleans (U8)
 
| `0x13` | `XOR` | Binary XOR | Boolean (U8)| 2 boolean (U8)
 
| | | | |
 
| `0x20` | `EQ` | == | Boolean (U8)| Any numbers of the same size
 
| `0x21` | `LT` | < | Boolean (U8)| 2 numbers of same size
 
| `0x22` | `GT` | > | Boolean (U8)| 2 numbers of same size
 
| `0x23` | `LE` | <= | Boolean (U8)| 2 numbers of same size
 
| `0x24` | `GE` | >= | Boolean (U8)| 2 numbers of same size
 
| | | | |
 
| `0x30` | `SUM` | Sum | Number (size of inputs) | Any numbers of the same size
 
| | | | |
 
| `0x50` | `ATL`| Verify absolute time lock | Boolean (U8) | Timestamp (UNIX seconds)(U64)
 
| `0x51` | `RTL`| Verify relative time lock | Boolean (U8) | Delay since insertion in blockchain (seconds)(U64)
 
| `0x52` | `SMR` | Run script with merkle root | Boolean (U8) | Hash (U32), AST
 
| | | | |
 
| `0x70` | `PH` | Verify password hash | Boolean (U8) | Hash (U32), password (U32)
 
| `0x71` | `ED` | Verify Ed25519 signature | Boolean (U8) | Public key (U32), signature (U64)
 
| `0x72` | `EDPKH` | Verify Ed25519 signature on pubkey hash | Boolean (U8) | Pubkey hash (U32), Public key (U32), signature (U64)
 
 
 
 
We can now express our previous *visual* trees as combinaisons of opcodes :
 
 
- Simple signature :
 
 
```
 
ED 2
 
U32 <public_key>
 
EXT 0 # Signature in parameter 0
 
```
 
 
- 1 out of 2 signatures :
 
 
```
 
OR 2
 
ED 2
 
U32 <public_key_a>
 
EXT 0 # Signature in parameter 0
 
ED 2
 
U32 <public_key_b>
 
EXT 1 # Signature in parameter 1
 
```
 
 
- 2 out of 3 signatures :
 
 
```
 
GE 2
 
SUM 3
 
ED 2
 
U32 <public_key_a>
 
EXT 0 # Signature in parameter 0
 
ED 2
 
U32 <public_key_b>
 
EXT 1 # Signature in parameter 1
 
ED 2
 
U32 <public_key_c>
 
EXT 2 # Signature in parameter 2
 
U8 2
 
```
 
 
# Input parameters
 
 
Input parameters are provided in a list of AST.
 
 
In the exemple of 2 out of 3 signatures above, the input could be :
 
 
```
 
2
 
0 : DOCSIG 0 # signature a
 
2 : DOCSIG 1 # signature c
 
```
 
 
In the document, they will be expressed as `<parameters count (2 bytes)> <index1> <ast1> <index2> <ast2> ...`.
 
At execution each AST will replace it's invocation in the script tree.
 
 
If a script try to access to an non defined parameter, `NOP` will be used.
 
If an operator get invalid inputs (not the correct size or `NOP`), it will return an *undefined value*.
 
 
In a previous version of the document all parameters had to be provided, with `NOP` when the parameter is not used. It was shorter for scripts using all parameters, but impractical for big conditionnal scripts where only some parameters are required, and the remaining are discarded. In a 1 out of 200 signature script, you now have to provide only 1 parameter instead of 200 (with 199 `NOP`).
 
 
Input parameters must not contain directly signatures and must use `DOCSIG` operator instead to fetch signatures from document end at execution. Since signatures are made from the whole document, it's impractical to store them inside it. For non-Ed25519 signatures, a different setup could be required, or a protocol change to allow non-Ed25519 document signatures.
 
 
With AST parameters can import each other with the `EXT` operator. However no recursion is allowed. Any case creating an infinite script is forbidden.
 
 
# Undefined operators
 
 
Undefined operators returns an *undefined value*. *Undefined values* propagate up when used by all operators expect with `OR` operator if another *defined value* is true.
 
 
## Exemple
 
 
```
 
OR
 
--------------------------------
 
| |
 
ED AND
 
------------ --------------------
 
| | | |
 
pubkey signature ED UNDEFINED
 
------------
 
| |
 
pubkey signature
 
```
 
 
Since the `AND` branch is dependent of all of its children, the **undefined state** propagate up to the `AND`.
 
 
```
 
OR
 
--------------------------------
 
| |
 
ED UNDEFINED
 
------------
 
| |
 
pubkey signature
 
```
 
 
If the left signature verification returns true, the `OR` operator returns true. Otherwise it will propagate the **undefined state**.
 
 
If at the end the returned value is `UNDEFINED`, the execution is concidered invalid and the transaction can't be spent.
 
 
# Merklized trees
 
 
The next step now is to transform our script tree into a Merkle Tree.
 
The hash of each node is :
 
 
- `HASH(node) = value` for `0x02/MASTH` operator
 
- `HASH(node) = SHA256(opcode + value)` for other `[0x00;0x0f]` operators
 
- `HASH(node) = SHA256(opcode + child count + HASH(child1) + HASH(child2) + ...)` for all other operators
 
 
where `+` is a concatenation.
 
 
The hash of the root node is called the Merkle Root. It can be used to store a script in an output condition only with a hash. Then when spending, we rebuild the Merkle Root of the given script tree to check if this is the correct script. We can also replace unused branches in the script (while using an `OR` operator) by their hash, reducing the data size and hiding perhaps secret conditions; while keeping the same Merkle Root.
 
 
## Exemple
 
 
Let's make a 2 out of 3 signatures with a MAST. This script is made of this AST :
 
 
```
 
GE 2
 
SUM 3
 
ED 2
 
U32 <public_key_a>
 
EXT 0 # Signature in parameter 0
 
ED 2
 
U32 <public_key_b>
 
EXT 1 # Signature in parameter 1
 
ED 2
 
U32 <public_key_c>
 
EXT 2 # Signature in parameter 2
 
U8 2
 
```
 
 
We calculate the Merkle Root `<merkle root>`, and then build the final output script condition :
 
 
```
 
SMR 2
 
U32 <merkle_root>
 
EXT 3 # Script AST
 
# We need to use index 3 because 0 to 2
 
# are already used by the hashed script
 
```
 
 
Then when you want to use it, you provide as parameters :
 
 
```
 
3
 
0 : DOCSIG 0 # signature a
 
2 : DOCSIG 1 # signature c
 
3 : GE 2
 
SUM 3
 
ED 2
 
U32 <public_key_a>
 
EXT 0 # Signature in parameter 0
 
MASTH <hash of this unused branch>
 
ED 2
 
U32 <public_key_c>
 
EXT 2 # Signature in parameter 2
 
U8 2
 
```
 
 
# Size limit
 
 
To prevent spam and abuses, script and inputs should have a maximum size. It's not defined yet but could follow the usage, like more transactions are accepted in blocks if the previous block have some.
 
 
A better solution for both situation could be to use average of transaction count/script sizes of `n` past block instead of the last 1 block.
 
\ No newline at end of file