FGT Algorithm

Types

LEB128 Little Endian Base 128 encoding for unsigned integers typically used to specify length prefixes for arrays and strings. Values in range [0, 127] are encoded in one byte. Larger values use two or more bytes.

Integer

A LEB128 integer with a maximum allowed value of 0x7fffffffffffffff (2 – 1) and a minimum of 0. A varint63 its into a signed 64-bit integer.

String

A binary string with a LEB128 prefix specifying its length in bytes. The maximum allowed length of the underlying string is 0x7fffffff (2 – 1). The empty string is encoded as a single byte 0x00, a one-byte string is encoded with two bytes 0x01 0xNN, a two-byte string is 0x02 0xNN 0xMM, etc

String32

A fixed-length 32-byte string typically used to encode hashes.

SHA3

SHA3 refers to the SHA3-256 function as defined in FIPS202 with a fixed-length 32-byte output.

This hash function is used throughout all data structures and algorithms in this spec, with the exception of SHA-512 (see FIPS180) used internally as function H inside Ed25519 (see RFC8032).

List

A List is encoded as a Integer-prefixed list of serialized items, one by one, as defined by the schema. The length prefix indicates the number of items that follow.

Pointer

A Pointer is encoded as a String32, and identifies another entry by its ID. Pointer restricts the possible acceptable types: Pointer<x> must refer to an entry of type X. A Pointer can be nil (not pointing to any entry), in which case it is represented by the all-zero 32-byte hash:

0x0000000000000000000000000000000000000000000000000000000000000000

Program

Program encapsulates the version of the FGT and the bytecode that should be executed by that FGT

FIELD	TYPE	DESCRIPTION
VM Version	Integer	The FGT version to be used when evaluating the program.
Bytecode	String	The program code to be executed.

Program encapsulates the version of the FGT and the bytecode that should be executed by that FGT

Inputs:

1. program,

2. arguments (list of strings),

3. transaction version (integer).

FIELD	TYPE	DESCRIPTION
Ref	Pointer<issuance1|Spend1|Mux1>	Previous entry referenced by this ValueSource
Value	AssetAmount1	Amount and Asset ID contained in the referenced entry.
Position	String32	If this source refers to a Mux entry, then the Position is the index of an output. If this source refers to an Issuance or Spend entry, then the Position must be 0.

Value Source 1 Validation

Verify that Ref is present and valid. Define RefDestination as follows: If Ref is an Issuance or Spend: Verify that Position is 0. Define RefDestination as Ref.Destination. If Ref is a Mux: Verify that Mux.Destinations contains at least Position + 1 ValueDestinations. Define RefDestination as Mux.Destinations[Position]. Verify that RefDestination.Ref is equal to the ID of the current entry. Verify that RefDestination.Position is equal to SourcePosition, where SourcePosition is defined as follows: If the current entry being validated is an Output1 or Retirement1, SourcePosition is 0. If the current entry being validated is a Mux, SourcePosition is the index of this ValueSource in the current entry’s Sources. Verify that RefDestination.Value is equal to Value.

Value Destination 1

An Entry uses a ValueDestination to refer to other entries that receive value from the current Entry.

FIELD	TYPE	DESCRIPTION
Ref	Pointer<issuance1|Spend1|Mux1>	Pointer<issuance1|Spend1|Mux1>
Value	AssetAmount1	Amount and Asset ID contained in the referenced entry
Position	String32	If this source refers to a Mux entry, then the Position is the index of an output. If this source refers to an Issuance or Spend entry, then the Position must be 0.

Merkle Root

A top hash of a merkle tree (binary or patricia). Merkle roots are used within blocks to commit to a set of transactions and complete state of the blockchain. They are also used in merkleized programs and may also be used for structured reference data commitments.

Merkle Binary Tree

The protocol uses a binary merkle hash tree for efficient proofs of validity. The construction is from RFC 6962 Section 2.1, but using SHA3–256 instead of SHA2–256. It is reproduced here, edited to update the hashing algorithm.

The input to the merkle binary tree hash (MBTH) is a list of data entries; these entries will be hashed to form the leaves of the merkle hash tree. The output is a single 32-byte hash value. Given an ordered list of n inputs, D[n] = {d(0), d(1), ..., d(n-1)}, the MBTH is thus defined as follows:

The hash of an empty list is the hash of an empty string:

MBTH({}) = SHA3-256("")

The hash of a list with one entry (also known as a leaf hash) is:

MBTH({d(0)}) = SHA3-256(0x00 || d(0))

For n > 1, let k be the largest power of two smaller than n (i.e., k < n ≤ 2k). The merkle binary tree hash of an n-element list D[n] is then defined recursively as

MBTH(D[n]) = SHA3-256(0x01 || MBTH(D[0:k]) || MBTH(D[k:n]))

where || is concatenation and D[k1:k2] denotes the list {d(k1), d(k1+1),..., d(k2-1)} of length (k2 - k1). (Note that the hash calculations for leaves and nodes differ. This domain separation is required to give second preimage resistance.)

Note that we do not require the length of the input list to be a power of two. The resulting merkle binary tree may thus not be balanced; however, its shape is uniquely determined by the number of leaves

Merkle Patricia Tree

The protocol uses a binary radix tree with variable-length branches to implement a merkle patricia tree. This tree structure is used for efficient concurrent updates of the assets merkle root and compact recency proofs for unspent outputs. The input to the merkle patricia tree hash (MPTH) is a list of key-value pairs of binary strings of arbitrary length ordered lexicographically by keys. Keys are unique bitstrings of a fixed length (length specified for each instance of the tree). Values are bitstrings of arbitrary length and are not required to be unique. Given a list of sorted key-value pairs, the MPTH is thus defined as follows: The hash of an empty list is a 32-byte all-zero string:

MPTH({}) = 0x0000000000000000000000000000000000000000000000000000000000000000