NOTE: This document is an unfinished work in progress, working toward v0.1.0!
Title: Active local state reconcilation using Avalanche Author: Tyler Smith (tcrypt) Status: Draft Created: 2019-10-01 License: MIT
- Abstract
- Motivation
- Goals
- Protocol Overview
- Specification
- Future Improvements
- Implementations
- Acknowledgments
- References
- Copyright
This document specifies a protocol for nodes of a Nakamoto Consensus network to actively work to reconcile their local states with those of their peers. It enables nodes to sample each others' state in order to determine which item of a conflict set is currently chosen by the most nodes, and to work toward a super majority of nodes chosing the same item. An Avalanche-based consensus algorithm is used for this processing affording the protocol asyncrony, metastability, and quiescent finality.
This document will not go into the details of the Avalanche algorithms and knowledge of them is assumed of the reader.
Nakamoto Concensus has the proptery of objectivity which is required for nodes wishing to join the consensus trustlessly. This is acheived using proof of work to give every state a real-world weight. Unfortunately this imposes some non-ideal requirements on the system such syncrony, artificial latency, and indefinite continued maintance of the consensus, i.e. a state change is never 100% finalized.
By recognizing that the vast majority of nodes making up the mining and large payment infrastructures are always online and very rarely need to join consensus more than once, we can design a protocol that allows them to very quickly come to aggrement on the state of the network from their viewpoints. The miners of the network continue their task of solidifying their local states into the canonical global state which enables new aganets to join the consensus trustlessly.
We want our protocol to be:
fast robust byzantine fault tolerant permissionless
We consider every block and transaction to be a member of conflict set of 1 or more items and use the Avalanche algorithm to resolve each set into exactly 1 item. The set of all items chosen for their respective conflict sets is used by participants as their local states which greatly minimizes the information entropy across these nodes.
Each peer keeps a list as many other participants as it can and for as long as there are unresolved conflict sets a peer will pick a random other peer and send them a query for all unresolved conflict sets. Responses are fed into a vote accumulator based on the Snowball algorithm and once the confidence reaches a threshold that conflict set is resolved. This process continues any time there are unresolved conflicts sets and works constantly until there are no more sets to resolve.
Sybil resistances is added by requiring peers to commit to a set of UTXOs that contain a sufficient coins age, and by weighting the random selection of peers by the committed coin ages.
Sybil resistance is provided by requiring peers offering the Query service to commit to a set of UTXOs that have a sufficient coin amount times block age, which we denote with the unit "Coin Blocks", or CB. If a Join message received by a Query peer does not meet the sufficient Coin Blocks threshold that peer must not be added to the Snowglobe Pool and should be banned.
The initial temporary amount required is 1440 Coin Blocks.
The heart of Avalanche's efficiency is in the DAG that allows us to accept or reject entire chains of states with a single Snowball instance. The more connected the graph is the fewer Snowball instances need to be performed to finalize all states, however if forming the graph is too complex much or all of these gains will be used up constructing graph edges.
The solution is to use all naturally forming, objective edges already present in the chain already and no more. We define the edges of the graph recursively by defining the incoming edges for a given vertex. The edges for a vertex depends on its type and are as follows:
- Transactions: A transaction has incoming edges from each parent transaction.
These are:
- The flow of UTXOS, i.e. When transaction B spends a UTXO created by transaction A then there is a single edge going from A to B.
- The chain of blocks, i.e. There is edge going from a blocks' parent to the block.
The follow serivce bit should be used by clients to signal to that they understand the protocol:
NODE_SNOWGLOBE = (1 << 26)When a node wants to advertise to a protocol-aware client that it is offering its local state for sampling, it should send them a Join message built as follows:
| Size | Name | Type | Description |
|---|---|---|---|
| 1 | version | uint8 | The version of the protocol supported by this peer. |
| 8 | sequence | uint16 | The sequence of this Join message. Used to invalidate pervious Join messages. |
| 33 | identityPubkey | [33]uint8 | The identity key of this peer. |
| []36 | outpoints | [][36]uint8 | A list of outpoints for sybil resistance. |
| 32 | identitySignature | uint8 | A signature for this message, without signatures, signed by identityPubkey. |
| []32 | outpoints | [][32]uint8 | A list of signatures for this message, without signatures, signed by the pubkey with control over the outpoint at the same index of outpoints. |
When a client wants to sample a node for a set of vertices it should send them a Query message build as follows:
| Size | Name | Type | Description |
|---|---|---|---|
| 8 | queryID | uint64 | An identifier for the sender to use to relate answers to queries. |
| []36 | invs | [][36]uint8 | A list of inventory vectors for the vertices being queried about. |
When a client wants to sample a node for a set of vertices it should send them a Query message build as follows:
| Size | Name | Type | Description |
|---|---|---|---|
| 8 | queryID | uint64 | An identifier for the sender to use to relate answers to queries. |
| []36 | invs | [][36]uint8 | A list of inventory vectors for the vertices being queried about. |
When a client first starts up it should refresh its pool of nodes available for sampling. It can do this with a combination of checking nodes they know with the appropriate service bit set, a domain-specific DNS seed, and other standard techniques for finding peers on a p2p network.
Next a client must sync to the tip block; the one with the most proof of work visible to the client. From here the client should begin iteratively checking blocks backwards, from tip to Genesis, until it finds a block that has been accepted by the client's queriable peers. They now know that block, all of its ancestors, and every transaction contained within those blocks, have been finalized by the network.
The following items are things that would improve the protocol but have been omitted for now to keep the protocol simple.
Currently ever UTXO in a Join message must have a matching signature, however each signature covers the same data and many UTXOs may be controlled by a single pubkey. In this case it would be acceptable to have only one signature for all of these UTXOs.
Query requests currently use full 32 byte transaction and block identifiers but this can be reduced significantly using various "short ID" mechanisms. This is a clear improvement to be made on memory and bandwidth consumption.
The current protocol requires signing every query response to validate its authenticity which is likely to become a bottleneck at scale. We can improve this situation by having peers connect using an authenticated communication tunnel.
Using a protocol conforming to the Noise[?] framework using QUIC for transport is under development by Bitcoin ABC.
There is a WIP implementation in Go based on the bchd full node: https://github.com/gcash/bchd/tree/snowglobe/
Bitcoin ABC's WIP implementation that this protocol was largely developed around is available here:
Team Rocket, deadalnix, Chris, Emin, Colin
TODO: Links and reference markers in text
- Snowflake to Avalanche
- Preconensus and Markets
- Chris' Avalanche article
- Noise Protocol
This document is placed in the public domain.