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
+ 732
− 0
Compare changes
  • Side-by-side
  • Inline
rfc/0005 Duniter Protocol Rework.md 0 → 100644
+ 732
− 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
 
1. 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 values
 
 
> To simplify explanations, we'll work with Ğ1 currency as an example. The currency symbol be
 
> replaced by any other currency made with Duniter.
 
 
The smallest **unit** that can be stored is 1 mĞ1, or 0.001 Ğ1. To avoid any floating part, all
 
storage and calculations are made in mĞ1, and are displayed with other prefixes for
 
user-friendliness.
 
 
- 1 Ğ1 = 1 000 mĞ1 = 1 000 units
 
- 1 kĞ1 = 1 000 Ğ1 = 1 000 000 units
 
- 1 MĞ1 = 1 000 000 Ğ1 = 1 000 000 000 units
 
- 1 GĞ1 = 1 000 000 000 Ğ1 = 1 000 000 000 000 units
 
 
Currency values are stored as :
 
 
| Size | Data |
 
|:----:|:-----|
 
| *1 byte* | Base
 
| *7 bytes* | Signed value in units
 
 
> Value need to be signed to allow operations on them within scripts.
 
 
The real value is calculated as :
 
 
```txt
 
RealValue = Value * 10^Base
 
```
 
 
Since the base will grow forever, it needs to cycle. We can compare values 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 `2^16` units, we increment the base.
 
 
We also need to update the displayed value, as it will be impractical to display them as very large
 
numbers. A suggested solution is to talk about *Dunes* or *Ď1* as a *Dividend Ğ1*, since *Ď1* are
 
not going to grow exponentialy.
 
 
### 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.
 
 
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 | `0x10` |
 
| Membership / Leaving | `0x11`/`0x12` |
 
| Certification | `0x13` |
 
| Revocation | `0x14` |
 
| V10Document | `0xf0` |
 
 
`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 in Name64 (such as `g1_` or `gt_`)
 
| 1 | Data type (determine `size` of payload without encoding) (in hexadecimal)
 
| `size` | Encoded payload (displayed in Base58)
 
 
| Data type | Payload size | Description
 
|:---------:|:------------:|:------
 
| 0/`00` | 32 | account
 
| 2/`02` | 32/64 | [ed25519] public/private key
 
| 3/`03` | 64 | [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. In the blockchain only
 
public keys are registers, but private keys can be provided this way to take adventage of error
 
detection.
 
 
The payload is encoded as followed :
 
 
- Cut payload in 6 bytes chucks, and for each produce `(2 first bytes of SHA256(Chunck)) ++ Chunck`.
 
- Take the `SHA256` of this new value and put its 2 first bytes at the begining.
 
 
TODO : Provide step by step examples.
 
 
> Thanks to hashes and Base58, any small change in the payload will change drasticly its appearence.
 
> 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 `Joiner` 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 `Membership` 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 a `Joiner` document
 
 
These certifications are linked to the `Joiner` document. If not enough certifications are made
 
before it expires, a new `Joiner` document and new certifications must be made. The number of
 
certifications necessary is defined in the parameters of the currency as `SigQuantity`.
 
 
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 `SigPeriod` time interval.
 
 
Finally, a member can't have more than `SigStock` active certifications in the blockchain. A
 
certification expires after a `SigValidity` 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 `MembershipWindow` 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 a `IdentityWindow`
 
period to enters again the *WoT*, otherwise the identity is revoked and will never be able to join
 
again.
 
 
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 entity don't want it, 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 value taken from this account
 
| ... | *Unlock parameters (with alignement padding with `Nop` opcodes)*
 
|
 
| | **For each output** :
 
| 8 | Currency value to send to this account
 
| 1 | `0` for merge/account mode, `1` for non-merge/UTXO mode
 
| ... | *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 consome 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 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 marks the output as **invalid** and can't be inserted in the blockchain since it would be **unusable and will lock founds indefinitly**. They also **must not** appear in Merklized script but this **CAN'T BE DETECTED before spending. Be sure your transaction is in non-merge mode before publishing an `Eval`+`FetchSourceBlockTime` script**.
 
| `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 of timestamp and blockid between the block in which the spending transaction document appears and the spending transaction. One of the 2 durations can be discarded with `Drop` or `Nip` opcodes. It can be used to prevent using a source based on the duration before spending. If the output is in merge-mode, this opcode marks the output as **invalid** and can't be inserted in the blockchain since it would be **unusable and will lock founds indefinitly**. They also **must not** appear in Merklized script but this **CAN'T BE DETECTED before spending. Be sure your transaction is in non-merge mode before publishing an `Eval`+`FetchSourceBlockTime` script**.
 
| `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.
 
 
> 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)` | `<pubkey> <pubkeyhash> CheckSig` | `SIG(sig_index)` | `<sig_index> FetchSig`
 
| `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.