# 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\* 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\* | 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\* | *Pointer\* | | 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 --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://docs.futuregold.us/blockchain-structure/fgt-algorithm.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.