Skip to content
Snippets Groups Projects

WIP: RFC 5 : New Scalable Blockchain Protocol

Closed WIP: RFC 5 : New Scalable Blockchain Protocol
rfc5-duniter-protocol-rework into master
Closed nanocryk requested to merge rfc5-duniter-protocol-rework into master
Compare
and
1 file
+ 1062
− 0
Compare changes
  • Side-by-side
  • Inline
rfc/0005 Duniter Protocol Rework.md 0 → 100644
+ 1062
− 0
# #5 Duniter Protocol Rework (V11)
```txt
RFC: 5
Title: Duniter Protocol Rework (V11)
Type: Hard-fork
Status: WIP
Author: nanocryk <nanocryk@duniter.org>
Created: 2018-01-29
Last edited: 2018-01-30
License: AGPL-3
```
This document provide specifications of a reworked protocol for the Duniter project.
It aims to provide an efficient and strong base for future developments by taking the actual
protocol (version 10), simplifying it and adding usefull elements to increase performance and
extensibility.
This document is written in a "no previous knowledge" fachion to allow anyone to understand it,
and will allow to directly use it as documentation if changes are accepted and implemented.
> This document is in writing process and may not be complete nor accurate. Reviews and comments
> are welcome.
## Summary
1. [A brief description of Duniter](#1-a-brief-description-of-duniter)
1. [Protocol conventions](#2-protocol-conventions)
1. [Keys, addresses and accounts.](#3-keys-addresses-and-accounts)
1. [Identities and the Web of Trust](#4-identities-and-the-web-of-trust)
1. [Transactions between accounts](#5-transactions-between-accounts)
1. [Usage of V10 documents](#6-usage-of-v10-documents)
1. [In depth block structure](#7-in-depth-block-structure)
1. Deployement plan
## 1. A brief description of Duniter
The **Duniter software** aims to provide a **Universal *Dividend** based crypto-currency based on
*Stephane Laborde's [Relative Theory of Money]*. It aims to provide money creation equality between
all users of the currency in space [of users] and time [users join and leave]. Money is
co-created by all the users and this process is automated by **Duniter**, allowing any user without
any technical skills to take part of the money creation. The name is made of `D + unit + er` as "a
tool to create UD units".
[Relative Theory of Money]: http://en.trm.creationmonetaire.info/
Each *Duniter* currency is built on a consecutive list of **blocks** linked together using
[cryptographic hashes], hense the name **blockchain**. Each block represent a new valid state of the
system and contains data to transform this valid state into a new valid state. This process is
applyed by any nodes in the network to ensure changes meet consensus.
Each block store the *proof of integrity* of the state and transformations as the *root* of a
[Merkle tree] (the Merkle root). This *Merkle root* needs to have specific properties to be
considered valid and computationnal work is needed to satisfy them. This process is called a
**Proof of Work** and allow to randomly pick writer for the next block, preventing an individual or
a group to take control of the currency.
[cryptographic hashes]: https://en.wikipedia.org/wiki/Cryptographic_hash_function
[Merkle tree]: https://en.wikipedia.org/wiki/Merkle_tree
Since we want to provide a *Universal Dividend*, we need to ensure that a real living user can
only have one identity per currency. To avoid computationnal attacks on the blockchain, we also
desire to have a "one user, one vote" *Proof of Work* system. To achieve this we use a
[Web of Trust] between members. Each member can give and receive certifications to allow other
identities to become and stay a member. This *Web of Trust* is stored in the blockchain, and
only *members* are allowed to write blocks. Thus, the *blockchain* is secured from the inside and
can't be easily attacked by external entities. The *Web of Trust* have more rules to resist attacks
which will be discribed later in this document.
As a currency, transactions can be made from *accounts* to others with programmable conditions that
can be used to create smart-contracts. Anyone can use the currency for transactions, not only
members.
[Web of Trust]: https://en.wikipedia.org/wiki/Web_of_trust
## 2. Protocol conventions
### Data format
Documents are structured and stored in binary formats to allow efficient storage, network
transmission and reading. All data is [big-endian] unless otherwise specified and [aligned] in 4
bytes blocks to improve memory speeds. All given sizes are given in *bytes* unless otherwise
specified.
[big-endian]: https://en.wikipedia.org/wiki/Endianness
[aligned]: https://en.wikipedia.org/wiki/Data_structure_alignment
### Hashes
*Cryptographic hashes* are done with the [SHA-256] algorithm unless otherwise specified. They are
stored as raw bytes arrays and should be displayed in hexadecimal format.
[SHA-256]: https://en.wikipedia.org/wiki/SHA-2
### Formating
Some formats are used to improve display or storage of some data :
- **Base58** (display) : Mainly used in addresses.
The alphabet is `123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz`.
- **Base64** (display) : Data format used for non user-friendly data such as signatures.
The alphabet is `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/`.
- **Name64** (storage) : Allow to store names in a more compact way that raw ASCII/UTF-8 text.
Each character is stored on 6bits, and prevent any invalid characters.
The alphabet is `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_-`.
### Block IDs and blockstamps
Each block is indexed by its **block ID** stored as a *4 bytes unsigned integer*.
The ***genesis block*** *ID* is `0`, and each following block have a *block ID* incremented
by `1`.
To refeer a *block*, we use it's **blockstamp** made of its *block ID* and its *Merkle root*.
The *blockstamp* of the genesis block *might be* `0-883228A23F8A75B342E912DF439738450AE94F5D`
and the *blockstamp* of block `433` *might be* `433-FB11681FC1B3E36C9B7A74F4DDE2D07EC2637957`.
Since hashes are stored on 32 bytes, a *blockstamp* is stored on a 36 bytes value.
> Note that is says "might be" because the hash is not known in advence.
### Currency amounts
Currency amounts are stored as integer values of the smallest unit. In clients, this amount is
displayed with a decimal part which is absent from the protocol.
A base is also defined to manage big numbers due to the exponentialy increasing amount on currency
produced with the Universal Dividend.
Currency amounts are stored as :
| Size | Data |
|:----:|:-----|
| *1 byte* | Base
| *7 bytes* | Signed amount in units
> The amount needs to be signed to allow operations on them within scripts.
The real amount is calculated as :
```txt
RealAmount = Amount * 10^Base
```
Since the base will grow forever, it needs to cycle. We can compare amounts in an interval of
`[-128;127]` around the main base.
> TODO : better explain ranges
This base incrementation will be very slow and a full cycle won't append until a long time. When the
UD becomes greater than a fixed value, we increment the base.
### Dates
All dates are stored in [UNIX timestamp format], as the number of seconds
since 00:00:00 UTC on January 1, 1970. They are stored in a 64bit format to
avoid [year 2038 problem]. In this format the counter will overflow
in approximately 293 billion years.
[UNIX timestamp format]: https://en.wikipedia.org/wiki/Unix_time
[year 2038 problem]: https://en.wikipedia.org/wiki/Unix_time#Representing_the_number
Durations are expressed in eleapsed time between 2 *timestamps*.
Another way to provide dates is to reference a *blockstamp*.
Dates in the *blockchain* are calculated as the average time provided in a window of
`MedianTimeBlocks` blocks. It should be preferred to use *blockstamps* since its independent
of any external influences.
> `MedianTimeBlocks = 24` in Ǧ1 currency.
### Documents structure
Most transformations of the state are made through **documents** composed of a **header**, a
**payload** and one or more **signatures**. The pair `(currency code, document type)` is used in
signatures, but is ellided when written into a block since they can be deduced from block data and
context. This prevent documents from other currencies to be compatible or to be used in another
context (joining/leaving documents have the same structure, only a different document type).
An **extention field** is provided to allow future protocol extensions without modifying this
document structure. It can contain any data but should have some sort of standard format to target
specific extensions. This format is not yet defined and will be in a future RFC, for now this
extension field should be empty (size of 0).
The *header* and *payload* are hashed to optain a **document ID**, then *signatures* are made on it.
The header is composed of :
| Size | Data |
|:----:|:-----|
| *2 bytes* | Currency code
| *2 bytes* | Document type
| *2 bytes* | Payload size in bytes
| *2 bytes* | Number of issuers
| ... | List of issuers *generic public keys* with alignement padding for each
| *1 byte* | Extension field size in bytes (0 to 255)
| ... | Extension field with alignement padding
> Payload and each signatures have alignement padding.
> Currency code should be chosen to form a recognizable prefix in addresses.
> Exemple : g1 (todo: code ?), gt (todo: code ?)
Cryptographic systems of signatures are not provided and matching public key types are used. A
document is valid if we can make pairs of well-formed `(public key, signature)` (with 0 bytes left
and no overflows) and each signature is valid for the document content and the public key.
The document types are the following :
| Name | Code |
|:-----|:----:|
| Transaction | `0x00` |
| Identity | `0x01` |
| Membership / Leaving | `0x02`/`0x03` |
| Certification | `0x04` |
| Revocation | `0x05` |
| V10Document | `0x06` |
`V10Document` allow to use V10 non-transaction documents. This will allow a smooth transition
between the 2 protocols, pending documents in pool will be usable on the new blockchain without
needing user intervention.V10 transaction documents can't be used with the new transaction system.
However, unspent transaction outputs in the last v10 block will be converted to v11
*account system*.
## 3. Keys, addresses and accounts
To allow funds to be spent only by authorized users, we make us of [Public-key cryptography].
User can generate `(public key, private key)` pairs, use the **private key** to sign data and get
a **signature**, and **verify** this *signature* with the the associated *public key*.
[Public-key cryptography]: https://en.wikipedia.org/wiki/Public-key_cryptography
Cryptographic data is stored in a special format to allow to :
- provide the type of data it contains
- link a key with a specific currency to avoid cross-blockchain [replay attacks].
- encode checksum to add error detection and close-looking attacks difficult
- human readable format
[replay attacks]: https://en.wikipedia.org/wiki/Replay_attack
This format (called an **address**) is structured as :
| Size | Data |
|:----:|:-----|
| 2 | Currency code
| 2 | Data type (determine `size` of payload)
| 4 | Checksum
| `size` | Payload
| Data type | Payload size | Description
|:---------:|:------------:|:------
| 0 | 32 | account
| 2 | 32/64 | [ed25519] public/private key
| 3 | 32 | [ed25519] public key hash
> More data types will be added in the future.
[ed25519]: https://en.wikipedia.org/wiki/EdDSA
The difference between public and private keys can be infered by the context and size.
The checksum is the first 4 bytes of `SHA256(CurrencyCode ++ DataType ++ Payload)`
> With this format it will be very unlikely someone send to an unwanted address.
## 4. Identities and the Web of Trust
An identity provide the relation between a *public key* and *an arbitrary identity*. This link is
done through an `Identity` document containing :
| Size | Data |
|:----:|:-----|
| 36 | *Time of signature* blockstamp
| 1 | Username length (1 to 127)
| ... | Username in *Name64* format *(with alignement padding)*
This document must have only one issuer and the username must not be
used by any active members or passed members for a defined period of time. We can compute an
**identity hash** (or **Identity UID**, **IUID**) as
`IdentityHash = SHA256(Username ++ KeyHashAddress ++ Blockstamp)`. This *IUID* will be used to
refeer to this identity.
This identity can be revoked using a `Revocation` document containing the *IUID* to revocate. Of
course, this document is only valid if its unique issuer is associated with the provided *IUID*.
Then, a `Membership` document has to be created for a newcomer to *express their will* to integrate
the *Web of Trust*.
| Size | Data |
|:----:|:-----|
| 36 | *Time of signature* blockstamp
| 32 | *IUID*
This document is only valid for a short time outside the blockchain starting at the provided
*blockstamp*.
To allow this document to be inserted in the blockchain, the `Identity` document must receive
certifications from members of the *Web of Trust* as `Certification` documents :
| Size | Data |
|:----:|:-----|
| 36 | *Time of signature* blockstamp
| 32 | *Document ID* if an `Identity` document
If not enough certifications are made before the `Membership` document expires, a new `Membership`
document and new certifications must be made. The number of certifications necessary is defined in
the parameters of the currency as `CertThreshold`.
Other rules impact if this set of documents can be inserted into the blockchain.
First, there is a **distance rule** to avoid [sybil attacks]. When a member have received and gave
at least `Y[N]` certifications each, where `Y[N] = N^(1/5)` and `N` is the number of members of the
*WoT*, he's called a **sentry**. Since certifications are unidirectionnal, the *Web of Trust* is a
directed graph with edges connecting *certifiers* to *certified*. We call the **distance** between A
and B the minimum number of edges we need to use to go from point A to point B in the graph. The
*distance rule* consist in computing the distance between each *sentry* and the newcoming indentity,
and testing that this distance is less than or equal to `StepMax` for at least `XPercent` of the
*sentries*, where `StepMax` and `XPercent` are parameters of the currency.
[sybil attacks]: https://en.wikipedia.org/wiki/Sybil_attack
Also, when a certification of a member reach the blockchain, no other certifications will be valid
in a `CertPeriod` time interval.
Finally, a member can't have more than `CertStock` active certifications in the blockchain. A
certification expires after a `CertValidity` period, allowing the member to certify other identities
(or to renew its previous certification).
When an identity enters the *WoT*, he can co-create the *Universal Dividend* and is allowed to
participate in the writing process of the blockchain. This identity is valid for a
`MembershipValidity` period, but can be renewed sooner after a `MembershipPeriod` period. This
renewing will only be accepted if the above rules are still applying (distance rule, certification
count).
If the `Membership` document expires, the identity leaves the *WoT*, and have another
`MembershipValidity` period to enters again the *WoT*, otherwise the identity is revoked and will
never be able to join again. An identity also leaves the *WoT* if at any time he have less than
the required minimum.
This leaving state can also be acheived manually by issuing a `Leaver` document (having the same
structure as the `Membership` document but with a different *document type*). An identity can
also be manualy revoked by issuing a `Revocation` document (with again the same structure).
It's important for users to precompute and sign a `Revocation` document and store it in a safe
place to be able to use it if their privare key is compromised or lost. It's fine to revocate an
identity and to create a new one, but members won't allow someone to create a new account while
the previous is not revoked, since it still can produce *Universal Divideds* and could allow the
user to produce more than one.
## 5. Transactions between accounts
### Notion of accounts
First, we need to define more precisely what is an **account**. An *account* can be anything that
holds funds.
In the previous protocol, there were only **unspent transactions outputs** (**UTXO**) and **UDs**.
A transaction consisted as a list of outputs, and list of outputs of previous transactions (sources)
and UDs, with each output locked by a condition satisfied by the next transaction. Thus, there
weren't any notion of account, only a set of *UTXOs* someone way able to spend. However for this
system to work it's mandatory to store all history of transactions, and many outputs spendable by
the same entity were in separate record and required more disk space. It also required to list
multiple sources if individual ones didn't hold enough money.
In this new protocol, *UTXOs* sharing the same spending condition are stored together unless
the issuers don't want to, as this merging mecanism is not compatible with some sorts of smart
contracts. However the vast majority of *UTXO* are mergeable and allow many things :
- Take less space on disk, in the blockchain and in network communications
- Make it easier for client to know how much they can spend
- Avoid to provide multiple inputs with the same condition, making simpler transactions documents
and removing duplicated signatures and proofs.
- UD spending condition is the same script as members identity account, so the set of "not yet spent
UDs" can be directly merged into the identity account.
### The Transaction document
A `Transaction` document contains the following :
| Size | Data |
|:----:|:-----|
| 1 | Number of inputs
| 1 | Number of outputs
| 2 | *(padding)*
|
| | **For each source** :
| 32 | Source
| 8 | Currency amount taken from this account
| ... | *Unlock parameters (with alignement padding with `Nop` opcodes)*
|
| | **For each output** :
| 8 | Currency amount to send to this account
| 1 | Output type
| 1 | Script system version
| ... | *Lock script (with alignement padding with `Nop` opcodes)*
The source field can be either :
- A lock script hash : we consume funds from any previous transaction made with this lock script.
```txt
Source = SHA256(ScriptHash ++ Index)
```
The `Index` is used to prevent double spending. The first time an account is a source, this
`Index` must be 0 and each time the account is used, this number must be increased by 1. This
prevent the same transaction document to be used multiple times on the same source to withdraw
more funds that the signer aggreed. With this technique it's also possible to generate in advance
multiple transaction by using consecutive *indexes*, each one becoming valid when the previous
one is included in the blockchain.
> The first time the source will be `SHA256(ScriptHash ++ 0)`, then `SHA256(ScriptHash ++ 1)`,
> then `SHA256(ScriptHash ++ 2)`, etc.
- A transaction id : we consume funds from a specific non-merged transaction
```txt
Source = SHA256(TransactionID ++ Index)
```
The **transaction ID** is the *document ID* of the source transaction, and the *index* allow to
target a specific output of this source transaction. It can only be used once as a source and
the amount needs to be equal to the output amount provided in the source transaction. After it's
used, it can be forgotten.
In each case, this hash, the `ScriptHash`/`TransactionID` and the `Index` are stored in the
blockchain to resolve where are the funds.
The output type can be :
| Type | Description |
|:----:|:-----|
| 0 | Merge/account, complete script
| 1 | Non-merge/UTXO, complete script
### The script system
> This system is heavily inspired by Bitcoin script system discribed
> [here](https://en.bitcoin.it/wiki/Script). It adds to it transaction data fetching (such as
> outputs, amounts); merkelized scripts and multiple cryptographic systems support.
The script system is simple, **stack-based** and processed from left to right. It is intentionnaly
**not Turing-complete, with no loops**.
The stack hold *byte arrays*. When used as numbers, byte arrays are interpreted as
**big-endian variable-length integers** with two's complement for sign handling. 0 can also be
represented by a null-length array. Byte array are interpreted as *booleans* where `false` is
represented by 0 and `true` by any other value.
A **main stack** and **alt stack** are available and empty by default. The executed script is the
concatenation of the *unlock parameters* and the *lock script*. The *unlock parameters* is a
script putting data onto the stack which will be used by the *lock script*.
A *transaction* is valid if nothing in the script triggers a failure, the main stack contains only
one `true` value and the alt stack is empty.
> We'll refeer to the **main stack** as **the stack** and precise **alt stack** when necessary.
#### Opcodes
| Opcode | Hex | Word | Input | Output | Description |
|:------:|:---:|:-----|:------|:-------|:------------|
| | | | | | **Constants**
| `0` | `0x00` | `C0`, `Zero`, `False` | *none* | *empty value* | An empty array is pushed on the stack.
| `1-75` | `0x01-0x4b` | `PushData1-PushData75` | *special* | *data* | The next *opcode* bytes is data to be pushed on the stack.
| `76` | `0x4c` | `PushData1B` | *special* | *data* | The next byte contains the number of bytes to be pushed on the stack.
| `77` | `0x4d` | `PushData2B` | *special* | *data* | The next two bytes contains the number of bytes to be pushed on the stack.
| `78` | `0x4e` | `PushData4B` | *special* | *data* | The next four bytes contains the number of bytes to be pushed on the stack.
| `80` | `0x50` | `CN1`, `NegOne`| *nothing* | `-1` | The number -1 is pushed onto the stack.
| `81` | `0x51` | `C1`, `One`, `True` | *nothing* | `1` | The number 1 is pushed onto the stack.
| `82-96` | `0x52-0x60` | `C2-C16` | *nothing* | `2-16` | The number in the word name (2-16) is pushed onto the stack.
|
| | | | | | **Flow control**
| `97` | `0x61` | `Nop` | *nothing* | *nothing* | Does nothing.
| `98` | `0x62` | `If` | `condition` | *nothing* | If the top stack value (`condition`) is not `false`, opcodes until an `Else` or `Fi` are executed, otherwise they are ignored. The top stack value is always removed.
| `99` | `0x63` | `IfNot` | `condition` | *nothing* | If the top stack value (`condition`) is `false`, opcodes until an `Else` or `Fi` are executed, otherwise they are ignored. The top stack value is always removed.
| `100` | `0x64` | `Else` | *nothing* | *nothing* | If the preceding `If`/`IfNot` was not executed then opcodes until a `Fi` are executed, otherwise they are ignored.
| `101` | `0x65` | `Fi` | *nothing* | *nothing* | Ends an if/else block. All blocks must end, or the transaction is **invalid**. A `Fi` without `If`/`IfNot` earlier is also not valid.
| `102` | `0x66` | `Assert`/`Verify` | `true`/`false` | *nothing* / *panic* | **Marks transaction as invalid** if top stack value in not `true`. The top stack value is removed.
| `103` | `0x67` | `Panic`/`Return` | *nothing* | *panic* | **Marks transaction as invalid.**
|
| | | | | | **Stack**
| `104` | `0x68` | `ToAltStack` | `xn .. x2 x1 x0 <n>` | `(alt) x0 x1 x2 .. xn` | Puts the `n` items on top of the main stack onto the top of the alt stack, one by one. Removes them from the main stack.
| `105` | `0x69` | `FromAltStack` | `(alt) xn .. x2 x1 x0 (main) <n>` | `x0 x1 x2 .. xn` | Puts the `n` items on top of the alt stack onto the top of the main stack, one by one. Removes them from the alt stack.
| `106` | `0x6a` | `Depth` | *nothing* | `<stack size>` | Puts the number of stack items onto the stack.
| `107` | `0x6b` | `IfDup` | `x` | `x`/`x x` | If the stop stack value is not `0`, duplicate it.
| `108` | `0x6c` | `Drop` | `x` | *nothing* | Removes the top stack item.
| `109` | `0x6d` | `Dup` | `x` | `x x` | Duplicate the top stack item.
| `110` | `0x6e` | `Nip` | `x1 x2` | `x2` | Removes the second-to-top stack item.
| `111` | `0x6f` | `Over` | `x1 x2` | `x1 x2 x1` | Copies the second-to-top stack item to the top.
| `112` | `0x70` | `Pick` | `xn ... x2 x1 x0 <n>` | `xn .. x2 x1 x0 xn` | The item `n` back in the stack is copied to the top.
| `113` | `0x71` | `Roll` | `xn ... x2 x1 x0 <n>` | `.. x2 x1 x0 xn` | The item `n` back in the stack is moved to the top.
| `114` | `0x71` | `Rot` | `x1 x2 x3` | `x2 x3 x1` | The top three item on the stack are rotated to the left.
| `115` | `0x72` | `Swap` | `x1 x2` | `x2 x1` | The top two items on the stack are swapped.
| `116` | `0x73` | `Tuck` | `x1 x2` | `x2 x1 x2` | The item at the top of the stack is copied and inserted before the second-to-top item.
| `117` | `0x74` | `Drop2` | `x1 x2` | *nothing* | Removes the top two stack items.
| `118` | `0x75` | `Dup2` | `x1 x2` | `x1 x2 x1 x2` | Duplicates the top two stack items.
| `119` | `0x76` | `Dup3` | `x1 x2 x3` | `x1 x2 x3 x1 x2 x3` | Duplicates the top three stack items.
| `120` | `0x77` | `Over2` | `x1 x2 x3 x4` | `x1 x2 x3 x4 x1 x2` | Copies the pair of items two spaces back in the stack to the front.
| `121` | `0x78` | `Rot2` | `x1 x2 x3 x4 x5 x6` | `x3 x4 x5 x6 x1 x2` | The fifth and sixth items back are moved to the top of the stack.
| `122` | `0x79` | `Swap2` | `x1 x2 x3 x4` | `x3 x4 x1 x2` | Swaps the top two pairs of items.
| `123` | `0x7a` | `IsEmpty` | `in` | `true`/`false` | Returns 1 if the top of the stack in a zero-length vector. It consumes the input, so if it needs to be used it should be duplicated first.
|
| | | | | | **Bitwise Logic**
| `128` | `0x80` | `Invert` | `in` | `out` | Flips all of the bits in the input.
| `129` | `0x81` | `BitAnd` | `x1 x2` | `out` | Bolean *and* between each bit in the inputs.
| `130` | `0x82` | `BitOr` | `x1 x2` | `out` | Bolean *or* between each bit in the inputs.
| `131` | `0x83` | `BitXor` | `x1 x2` | `out` | Bolean *exclusive or* between each bit in the inputs.
| `132` | `0x84` | `BitEqual` | `x1 x2` | `true`/`false` | Return 1 if the inputs are exactly equal, 0 otherwise.
|
| | | | | | **Arithmetic**
| | | | | | *Arithmetic inputs are limited to signed 64-bit integers, but may overflow their output.*
| `144` | `0x90` | `Add1` | `in` | `out` | 1 is added to the input.
| `145` | `0x91` | `Sub1` | `in` | `out` | 1 is subtracted from the input.
| `146` | `0x92` | `Negate` | `in` | `out` | The sign of the input is flipped.
| `147` | `0x93` | `Abs` | `in` | `out` | The input is made positive.
| `148` | `0x94` | `Not` | `in` | `out` | If the input is 0 or 1, it is flipped. Otherwise the output will be 0.
| `149` | `0x95` | `Not0` | `in` | `out` | Returns 0 if the input is 0, 1 otherwise.
| `150` | `0x96` | `Add` | `a b` | `out` | a is added to b.
| `151` | `0x97` | `Sub` | `a b` | `out` | b is subtracted from a.
| `152` | `0x98` | `And` | `a b` | `out` | If both a and b are not 0, the output is 1, otherwise 0.
| `153` | `0x99` | `Or` | `a b` | `out` | If a or b in not 0, the output is 1, otherwise 0.
| `154` | `0x9a` | `NumEqual` | `a b` | `out` | Returns 1 if numbers are equal, otherwise 0.
| `155` | `0x9b` | `NumNotEqual` | `a b` | `out` | Returns 1 if numbers are not equal, otherwise 0.
| `156` | `0x9c` | `NumLessThan` | `a b` | `out` | Returns 1 if a is less than b, 0 otherwise.
| `157` | `0x9d` | `NumGreaterThan` | `a b` | `out` | Returns 1 if a is greater than b, 0 otherwise.
| `158` | `0x9e` | `NumLessThanOrEqual` | `a b` | `out` | Returns 1 if a is less than or equal to b, 0 otherwise.
| `159` | `0x9f` | `NumGreaterThanOrEqual` | `a b` | `out` | Returns 1 if a is greater than or equal to b, 0 otherwise.
| `160` | `0xa0` | `Min` | `a b` | `out` | Returns the smaller of a and b.
| `161` | `0xa1` | `Max` | `a b` | `out` | Returns the larger of a and b.
| `162` | `0xa2` | `Within` | `x min max` | `out` | Returns 1 if x is within the specified range (left-inclusive), 0 otherwise.
| `163` | `0xa3` | `Sum` | `xn .. x2 x1 x0 <n>` | `out` | Returns the sum of the `n` top values from the stack.
| | | | | | ***Arithmetic operations on currency values (takes account of the base) :***
| `164` | `0xa4` | `CurrencyEqual` | `a b` | `out` | Returns 1 if numbers are equal, otherwise 0.
| `165` | `0xa5` | `CurrencyNotEqual` | `a b` | `out` | Returns 1 if numbers are not equal, otherwise 0.
| `166` | `0xa6` | `CurrencyLessThan` | `a b` | `out` | Returns 1 if a is less than b, 0 otherwise.
| `167` | `0xa7` | `CurrencyGreaterThan` | `a b` | `out` | Returns 1 if a is greater than b, 0 otherwise.
| `168` | `0xa8` | `CurrencyLessThanOrEqual` | `a b` | `out` | Returns 1 if a is less than or equal to b, 0 otherwise.
| `169` | `0xa9` | `CurrencyGreaterThanOrEqual` | `a b` | `out` | Returns 1 if a is greater than or equal to b, 0 otherwise.
| `170` | `0xaa` | `CurrencyMin` | `a b` | `out` | Returns the smaller of a and b.
| `171` | `0xab` | `CurrencyMax` | `a b` | `out` | Returns the larger of a and b.
| `172` | `0xac` | `CurrencyWithin` | `x min max` | `out` | Returns 1 if x is within the specified range (left-inclusive), 0 otherwise.
| `173` | `0xad` | `CurrencySum` | `xn .. x2 x1 x0 <n>` | `out` | Returns the sum of the `n` top values from the stack.
|
| | | | | | **Crypto**
| `176` | `0xb0` | `Hash` | `value algo` | `hash` | The input is hashed using `algo` hashing algorithm. The list of algorithms is available below.
| `177` | `0xb1` | `CheckSig` | `sig pubkey pubkeyhash` | `true`/`false` | The signature must be a valid signature of the spending *transaction id* and given *public key* (in key format described before). `pubkeyhash` must also correspond to `pubkey`. If it is, 1 is returned, 0 otherwise. If the `pubkeyhash` indicate an unknown cryptographic system, it returns 1 to allow backward-compatible addition of new ones.
| `178` | `0xb2` | `CheckMultiSig` | `sig1 sig2 ... pub1 pub2 ... pubhash1 pubhash2 <count>` | valid sig count | Verify each group `(sign, pubn, pubhashn)`, return the sum of each internal `CheckSig`.
| `179` | `0xb3` | `Eval` | `script hash` | *special* | Evaluate `script` as if it were in-place. The script must have a Merkle root equal to `hash`. If not, **transaction is invalid**. If the script *panic* (says the transaction is invalid), the **transaction is invalid**. The script hashing algorithm is described later in this document.
| `180` | `0xb4` | `Unused` | *special* | `false` | Returns `false`. The `(opcode ++ hash)` of this instruction are the **next 33 bytes in the script**. It allow to only provide hashes of unused code when using `Eval` opcode. Can only be used in *unlock parameters* and an output having an `Unused` opcode in its lock script is **invalid**.
|
| | | | | | **Data fetching**
| `192` | `0xc0` | `FetchSig` | `index` | `signature`/*empty* | Returns the document signature at this index, or an *empty value* if out of bounds. This allow to segregate signatures outside of the transaction body and prevent transaction malleability. It should never be used in an lock script since the order of signature could not be guaranted with multiple sources. It should only be used in the unlock parameters.
| `193` | `0xc1` | `FetchSourceBlockTime` | *nothing* | `timestamp blockid` | Returns the timestamp and blockid corresponding to the block in which the source transaction document appears. One of the 2 dates can be discarded with `Drop` or `Nip` opcodes. If the output is in merge-mode, this opcode returns the date of the last time this account has been used as input. It can be used to allow spending X times per period, or to define new conditions after a spending is done at a given time.
| `194` | `0xc2` | `FetchTargetBlockTime` | *nothing* | `timestamp blockid` | Returns the timestamp and blockid corresponding to the block in which the spending transaction document appears. One of the 2 dates can be discarded with `Drop` or `Nip` opcodes. It can be used to prevent using a source based on the date of the spending transaction.
| `195` | `0xc3` | `FetchDeltaBlockTime` | *nothing* | `delta_timestamp delta_blockid` | Returns the difference between `FetchTargetBlockTime` and `FetchSourceBlockTime`.
| `196` | `0xc4` | `FetchOutputAmount` | `output_index` | `amount base`/*empty* *empty* | Returns the amount spent by a specific output. Returns an empty value if this index is out of bound.
| `197` | `0xc5` | `FetchOutputAddress` | `output_index` | `address`/*empty* | Returns the script hash (address) of a specific output. Returns an empty value if this index is out of bound. It can be used to force specific conditions for an output.
Any **undefined operators** will prevent the script from running and mark the transaction as
**valid**. They cause an **anyone can spend** behavior. With this construct, giving them a new
meaning can only restrict the set of valid transactions and outdated client will never see new
opcodes as invalid to their rules. It can be used to add new backward-compatible features.
If no backward-compatible features needs to be added, we can add them as part of a new version of
the script system. The current one is version 0, and any unknown script system version makes the
transaction valid without even looking at the script content, allowing to make these changes in
a backward-compatible way.
> Client should show warnings when they see an "anyone-can-spend" script.
Padding is done through `Nop` operators, and any leading `Nop` opcodes will be discarded before any
treatment (hashing, execution).
#### Hashing algorithms list
| Code | Name |
|:----:|:-----|
| `0` | SHA-256
Any other hashing code will return an *empty value*.
> More hashing algorithms will be added later.
#### Script examples
To simplify our scripts examples, we write constants as `<data>` fields, and the stack push
is implied. When a signature is used, the use of `FetchSig` is implied.
- Classic pay-to-pubkey script
```txt
Script : <pubkeyhash> CheckSig
Parameters : <sig> <pubkey>
```
Here is a step by step execution of the script
| Stack | Script | Description |
|:------|:-------|:------------
| | `<sig> <pubkey> <pubkeyhash> CheckSig` | Script and parameters are merged.
| `<sig> <pubkey> <pubkeyhash>` | `CheckSig` | Data is pushed on the stack.
| `true` | | Signature is checked from top two stack items.
There is only `true` in the stack, so this transaction is valid.
- 2-of-3-multisig script
```txt
Script : <pubkeyhash1> <pubkeyhash2> <pubkeyhash3> 3 CheckMultiSig 2 NumGreaterThanEqual
Parameters : <sig1> <empty> <sig3> <pubkey1> <empty> <pubkey3>
```
#### Script hashing
We must find a way to translate a stack-based script into a graph of dependency between
operations. Each operator consumes inputs and produces outputs than can be used to build
a graph. It's not a tree since a value can be used multiple time with a `Dup` opcode, but it
should not cause problems in bluiding a Merkle Tree with duplicated branches.
Each opcode becomes a node of the tree, and each producer of its input is a child, and the
consumers of its outputs are parents.
Let's build a 1-of-2-multisig script with separated checks :
```txt
Script : <pubkeyhash a> CheckSig 1 ToAltStack
<pubkeyhash b> CheckSig 1 FromAltStack
Or
```
We have a first opcode pushing `<compact key a>` on the stack. Then `CheckSig` consume
it and some input parameters, and push the result on the stack. The opcode `<compact key a>`
is a child of `CheckSig`. We can apply this rule to all of the operators to obtain this
tree :
```txt
-------Or--------
| |
---FromAltStack--- |
| | |
---ToAltStack-- 1 |
| | |
CheckSig 1 CheckSig
| |
<pubkeyhash a> <pubkeyhash b>
```
If an operator have multiple children, we add them in a tree in the same order as the inputs.
Here `ToAltStack` take in input `xn ... x2 x1 x0 <n>`, so they are inserted in the tree in
the same order from right to left.
The rules for the hash of an opcode are :
- If it consumes items from stacks, we add `SHA-256(SHA-256(child1) + SHA-256(child2) + ...)`
- If it provide data (`PushDataX` opcodes), we add `SHA-256(data)`
- We then hash all the above with `SHA-256`.
- We prefix the opcode.
The only exception is the `Unused` opcode having the `(opcode, hash)` pair in the 33 following bytes. This is
used to hide the unused branches at spending.
Exemple :
```txt
C4 PushData1B <data on 4 bytes>
```
becomes
```txt
PushData1B
+ SHA-256(
+ SHA-256(C4)
+ SHA-256(<data on 4 bytes>)
)
```
An opcode can be replaced by an `Unused` opcode **only if it always push one boolean value (0 or 1) on the main stack**. `Unused` will push `false` on the stack *as if* the underlying branch returned false.
In the above example only the 2 `CheckSig` and the `Or` can be replaced by their hash.
Note that it's praticaly no possible to replace the `Or`, since it will return `false` and
the transaction will be invalid.
If we consider `<script_hash>` as the Merkle Root of the above script, we can have as a lock script :
```txt
<script_hash> Eval
```
Then at spending we should have as parameters :
```txt
<sig a> <pubkey a>
[
<pubkeyhash a> CheckSigHash 1 ToAltStack
Unused [CheckSig <branch hash>] 1 FromAltStack
Or
] -- this script is pushed in one byte array on top of the stack
```
or
```txt
[
<sig b> <pubkey b>
Unused [CheckSig <branch hash>] 1 ToAltStack
<pubkeyhash b> CheckSig 1 FromAltStack
Or
] -- this script is pushed in one byte array on top of the stack
```
In each case, the `Unused` opcode returns `false` but the other returns `true`, so `Or`
return `true`.
#### Allow usage of V10 outputs
To allow spending of transaction in V10 format, we must translate the old scripts in this new format
and have the exact same behavior.
| V10 script | V11 script | V10 parameters | V11 parameters
|:-----------|:------------|:---------------|:----
| `SIG(pubkey)` | `<pubkeyhash> CheckSig` | `SIG(sig_index)` | `<sig_index> FetchSig <pubkey>`
| `XHX(sha256_hash)` | `1 Hash <sha256_hash> BitEqual` | `XHX(pass)` | `<pass>`
| `CLVT(timestamp)` | `FetchSourceBlockTime Drop <timestamp> NumGreaterThanOrEqual` | *nothing* | *nothing*
| `CSV(delay)` | `FetchDeltaBlockTime Drop <delay> NumGreaterThanOrEqual` | *nothing* | *nothing*
|
| `{X} AND {Y}` | `{X} 1 ToAltStack {Y} 1 FromAltStack And` | `{X} {Y}` | `{Y} {X}`
| `{X} OR {Y}` | `{X} 1 ToAltStack {Y} 1 FromAltStack Or` | `{X} {Y}` | `{Y} {X}`
> TODO : Need peer reviewing since it's a critical part of this protocol change.
## 6. Usage of V10 documents
For any currency running with the v10 Duniter protocol wanting to migrate to this new protocol, it's
necessary to be able to use v10 documents that are still in pools, such as identities or
certifications. Transaction are mostly inserted in the blockchain in the next block, so it's not
usefull to accept them, as it will result in complications to be compatible with the new
*account system*.
To include v10 documents, we can use the `V10Document` document type composed of :
| Size | Data |
|:----:|:-----|
| 2 | Size of the payload
| ... | Payload
with the payload being the text v10 document. This document don't need any issuer or signatures
since these are already in the v10 document.
When inserted into the state, signatures are no longer needed and documents can be converted in the
new format.
## 7. In depth block structure
### State machine logic
Each block tracks the transformation of one valid state to a new one.
```txt
State(t+1) = Transform(t+1, State(t))
```
A transformation is made of a succession of events. The order of these events can't be changed
since an event can use the consequence of a previous event. An event can be a document issued by a
user or a spontaneous event such as UD creation or document expiration.
```txt
State(t+1) = Event3(Event2(Event1(State(t))))
```
To allow forks handling it must be possible to find the previous state based on the new state and
the transformations.
```txt
State(t) = ReverseTransform(t+1, State(t+1))
State(t) = ReverseEvent1(ReverseEvent2(ReverseEvent3(State(t+1))))
```
### Main data structure : binary trees
When we have a set of entries to store in a Merkle tree, we divide them in 2 parts recursively. For
exemple if we have the set of documents `A, B, C, D, E, F`, we'll end up in 2 groups `A, B, C` and
`D, E, F`. Then `A, B, C` will then be decomposed in `A` and `B, C` (we use the Euclidan division,
`3 / 2 = 1`), same for `D, E, F`.
Finally alongside the root we store the hash of the entries list.
```txt
/\
/ \
entries list /\
/ \
/ \
/ \
/ \
/\ /\
/ \ / \
/ /\ / /\
A B C D E F
```
With this list we know that all items are in the tree and can be queried. Each node use the list
`A, B, C, D, E, F` to compute the tree and the list, and verify that the final hash corresponds. No
documents can be added or removed without updating the list.
This list need to have a consensual order to allow nodes to compute the same tree. For most trees
they will be ordered by alphabetic or numeric order, but some lists such as the events list must
not be sorted.
Entries can be documents (issued by users), some internal data of the system or subtrees.
Only documents hashes are stored in the tree, and they must be stored alongside the tree on disk
to be retreived.
By convention, if our root node is named `root`, then `root/A` qualifies the hash of the `A`
entry stored in this binary tree structure and we omit its path in the tree.
### Global structure of the tree
The Merkle tree is made as the following
- `/signature` : signature of the `container` with the issuer public key.
- `/container` : contains data signed by the block issuer.
- `issuer` : issuer public key.
- `nonce` : nonce used in the Proof of Work mechanism.
- `date` : block forging date
- `previous_root` : hash of the previous block `/`
- `transform` : list of events discribing transformations on the previous state
- `final_state` : state after all transformations
`/signature` and `/container` are in this order, and `/container` children are sorted in alphabetic
order.
Other fields are allowed and don't make the block invalid to allow future features to be
backward compatible (soft fork).
### State structure
The `state` is made of 2 parts :
- a `data` tree containing the actual state of the system. It contains only updated data and all
outdated ones are removed.
- a `requests` tree storing common request answers about the system is a `RememberWindow` block
period. This allow clients to make requests on "maybe outdated" data such as identity memberships,
spent UTXOs or emptied accounts.
Since all changes reflects `data` changes or "forgetings" after a defined window, this part can be
computed by each node and verified in a new block. None of the contents need to be propagated on
the network, only its hash `helpers` is needed. However if its invalid and the block is rejected,
a node can query its data to investigate where the problem comes from.
If the request is a "Yes/No" question, the client can compute both `Yes` and `No` answer and ask a
node which is in the tree. It prevent any attack by omission in the `RememberWindow`.
Nodes are only required to answer these requests in the `ForkWindow` blocks to be considered
cooperative. It means a client can request informations on deleted data in a
`ForkWindow + ForgetWindow` time period, and older informations can be discarded unless the node
wants to keep it for archives purposes.
The state contains the following data :
- `data/system/parameters` : stores system parameters
> All delays or periods are expressed in seconds
Contains as entries :
- `UDReevaluationPeriod` : Time period between two UD re-evaluations (v10 `dtReeval`)
- `UDReevaluationGrowth` : The %growth of the UD every `UDReevaluationPeriod` (v10 `c`)
- `UDFirstReevaluation` : Time of the first UD re-evaluation (v10 `udReevalTime0`)
- `UDCreationPeriod` : Time period between two UD creations (v10 `dt`)
- `UDFirstCreation` : Time of the first UD creation (v10 `udTime0`)
- `UDLastCreation` : Time of the last UD creation
- `UDFirstValue` : The first value of a UD (v10 `ud0`)
- `UDCurrentValue` : The current value of a UD
- `CertPeriod` : Minimum delay between 2 certifications of a same issuer (v10 `sigPeriod`)
- `CertStock` : Maxiumum quantity of active certifications made by a member (v10 `sigStock`)
- `CertWindow` : Maximum age a certification can have before being expired for non-writing (v10
`sigWindow`)
- `CertValidity` : Maximum age of an active signature (v10 `sigValidity`)
- `CertThreshold` : Minimim quantty of certifications to be member of the WoT (v10 `sigQty`)
- `MembershipPeriod` : Minimum delay between 2 memberships of a same issuer (v10 `msPeriod`)
- `MembershipWindow` : Maximum age a membership can have before being expired for non-writing (v10
`msWindow`)
- `MembershipValidity` : Maximum age of an active membership (v10 `msValidity`)
- `IdentityWindow`: Maximum age an identity can have before being expired for non-writing (v10
`idtyWindow`)
- `IdentityForgetPeriod` : Time after a revoked identity can be forgoten, allowing the username
and public key to be reused.
- `WoTSentriesPercent` : Minimum percent of sentries to reach to match the distance rule (v10
`xpercent`)
- `WotStepMax` : Maximum distance between each WoT member and a newcomer for the distance rule
(v10 `stepMax`)
- `BlockMedianTimeWindow` : number of blocs used for calculating median time (v10
`medianTimeBlock`)
- `BlockTargetPeriod` : Target time between 2 blocks (v10 `avgGenTime`)
- `PoWMin` : minimum block difficulty for all members
- `PoWReevaluationPeriod` : The number of blocks requiered to evaluate `BlockPoWMin` value
(v10 `dtDiffEval`)
- `PowExcludedCalculators` : The percent of previous issuers to reach for personalized difficulty (v10
`percentRot`)
- `RequestRememberWindow` : Time after an outdated answser can be removed from requests.
- `CurrencyUnitBase` : Applied as a power of 10 to currency amounts. Allow value rotations and
management of big numbers caused by the exponentional growth of units due to UD creation.
- `CurrencyBaseShiftThreshold` : When the UD is greater than this number, the unit base is
increased.
- `data/currency/accounts` : stores account.
Each account is indexed and sorted by its account ID (lock script hash) and contains :
- `script` : complete script (in tree : raw data hash instead of script hash)
- `balance` : amount on this account
- `index` : chaining index
- `last_output_time` : last `(timestamp, blockid)` it was listed as output (receive funds)
- `last_input_time` : last `(timestamp, blockid)` it was listed as input (spent funds,
`(0, -1)` if never spent)
- `data/currency/utxos` : stores UTXOs.
Each UTXO is indexed and sorted by its `(TransactionID, Index)` and contains :
- `script` : complete script (raw data hash in tree)
- `amount` : amount in this UTXO
- `time` : `(timestamp, blockid)` at which the transaction as been inserted in block
- `data/wot/members` : stores active identities.
Each identity is indexed and sorted by its IUID and contains :
- `username`
- `public key hash`
- `created_timestamp`
- `last_renewal_timestamp`
- `data/wot/excluded` : stores excluded identities.
Each identity is indexed and sorted by its IUID and contains :
- `username`
- `public key hash`
- `exclusion_timestamp`
- `data/wot/certifications` : stores active certifications.
Each certification is indexed and sorted by its document ID and contains :
- `certifier`
- `certified`
- `certification_timestamp` : blockstamp contained in the certification document
- `data/wot/revoked` : stores revoked identities.
Each indentity is indexed and sorted by its IUID and contains :
- `username`
- `public_key_hash`
- `revocation_timestamp`
- `requests/wot/username_is_member` : "Is X a member ?" answer for all active members and old
members for a fixed amount of time.
Each answer is indexed and stored by its username. The entry most be the hash of
`<username> is a member` or `<username> is not a member`.
- `requests/username_received_certifications` : store the list of received certifications (document
ids) for each member.
Each answer is indexed and stored by its username.
- `requests/username_emited_certifications` : store the list of emited certifications (document ids)
for each member.
Each answer is indexed and stored by its username.
> For each `requests/wot/username_XXX` request there is a corresponding `requests/wot/iuid_XXX`
> request indexed by the IUID of the member.
> TODO : Maybe add `username_is_outdistanced`. It needs to be done once every block so it's
> maybe not too much computationaly heavy for 5 minutes blocks.
> This tree is not yet complete and is subject to changes.
### Transform structure
The `transform` is made of a list of events applied to the previous state and computing the new
state. These events must not be sorted since their application may not be commutative. They can be
issued by users to use the currency or interact with the WoT or be spontaneous if they issued by the
system. The later can be a UD creation, certification or identity expiration, data deletion, etc.
Everytime a data is destroyed in the forward application, its content is included in the event
data so it can be applied in reverse and restored.
Each event have this data structure :
| Size | Data |
|:----:|:-----|
| 2 | Event type
| 2 | Event payload size in bytes
| ... | Payload
We'll now list all possible events, their validity rules and how they affect the state (in forward
or reverse) :
#### `Transaction` user event : spend funds from sources to outputs.
Payload content :
- Transaction document
- Destroyed accounts data
- Destroyed UTXOs data
Rules :
- Sources must be account with enough funds, or UTXOs.
- All sources script locks must return true.
- All outputs scripts must be well-formed.
- The sum of input amounts must be equal to the sum of output amounts.
Forward application :
- Each account source amount is decreased by the provided amount, and empty accounts are
destroyed.
- Each UTXO source is destroyed.
- Each account output amount is increased by the provided amount, or created if it doesn't exist
yet.
- Each UTXO output is created.
Backward application :
- Each UTXO output is destroyed.
- Each account output amount is decreased by the provided amount, and destroyed if it now equals
0.
- Each UTXO source is created.
- Each account source amount is increased by the provided amount, or created if it was destroyed.
#### `DividendCreation` spontaneous event : create UD for all active members
Payload content :
- Previous UD creation timestamp (0 if first UD creation)
- Current UD creation timestamp
- UD amount
Rules :
- For first UD : the first block having a median timestamp greater than `UDFirstCreation` must
have this event.
- For other UDs : the first block having a median timestamp greater than `UDLastCreation` +
`UDCreationPeriod` must have this event.
- All payload data matches
Forward application :
- Add `UDCurrentValue` to the account of each active member in this block. The account of a member
have a script of `<pubkeyhash> CheckSig`.
- Set `UDLastCreation` to the block median time.
Backward application :
- Set `UDLastCreation` to the previous UD creation timestamp.
- Remove UD amount from the account of each active member in this block.
> TODO : Provide order of event types
\ No newline at end of file