# ACI GOLD Algorithm ## ypes LEB128\ **Little Endian Base 128** encoding for unsigned integers typically used to specify length prefifixes 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 ifts into a signed 64-bit integer. ## String A binary string with a **LEB128** prefifix 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 preiifx indicates the number of items that follow. ## Struct A *Struct* is encoded as a concatenation of all its serialized fifields. ## Public Key In this document, a *public key* is the 32-byte binary encoding of an Ed25519 (EdDSA) public key, as defined in **RFC8032**. ## Signature In this document, a *signature* is the 64-byte binary encoding of an Ed25519 (EdDSA) signature, as defined in **RFC8032** ## Signature Auxiliary data structures are **Structs** that are not **entries** by themselves, but used as fields within the entries. ## 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 ACI GOLD and the bytecode that should be executed by that ACI GOLD | FIELD | TYPE | DESCRIPTION | | ---------- | --------- | ------------------------------------------------------------ | | VM Version | *Integer* | The ACI GOLD version to be used when evaluating the program. | | Bytecode | *String* | The program code to be executed. | Program encapsulates the version of the ACI GOLD and the bytecode that should be executed by that ACI GOLD **Inputs:** 1. program, 2. arguments (list of strings), 3. transaction version (integer). ## Asset De**fi**nition | FIELD | TYPE | DESCRIPTION | | -------------------- | ---------- | ------------------------------------------------------------------------------------ | | Initial Block ID | *String32* | ID of the ACI GOLD block for the blockchain in which this asset is defined. | | Bytecode | *Program* | Program that must be satisfied for this asset to be issued. | | Asset Reference Data | String32 | Hash of the reference data (formerly known as the “asset definition”) for this asset | **Inputs:** Asset ID is a globally unique identifififier of a given asset across all blockchains. Asset ID is defined as the **SHA3-256** of the **Asset Defnition**: > AssetID = SHA3-256(AssetDefinition) ## Asset Amount 1 AssetAmount1 struct encapsulates the number of units of an asset together with its **asset ID**. | FIELD | TYPE | DESCRIPTION | | -------------------- | ---------- | ------------------------------------------------------------------------------------ | | AssetID | *String32* | **Asset ID.** | | Value | *Integer* | Number of units of the referenced asset | | Asset Reference Data | *String32* | Hash of the reference data (formerly known as the “asset definition”) for this asset | ## Asset Amount 1 An **Entry** uses a ValueSource to refer to other **Entries** that provide the value for it. | 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 effifificient 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 ![](broken-reference) The hash of a list with one entry (also known as a leaf hash) is: > The hash of a list with one entry (also known as a leaf hash) is: In case a list contains multiple items, all keys have a common bit-prefifx extracted and the list is split in two lists A and B with elements in each list sharing at least one prefifix bit of their *keys*. This way the top level hash may have an empty common prefix, but nested hashes never have an empty prefix. The hash of multiple items is defined recursively: > MPTH(A + B) = SHA3-256(0x01 || MPTH(A) || MPTH(B)) ![](broken-reference) ## Entries Entries form a directed acyclic graph within a blockchain: *block headers* reference the *transaction headers* (organized in a *merkle tree*) that in turn reference outputs, that are coming from *muxes, issuances* and *spends*. ## Entry Each entry has the following generic structure: | FIELD | TYPE | DESCRIPTION | | ------- | -------- | --------------------------------------------------------- | | Type | *String* | The type of this Entry. E.g. *Issuance1, Retirement1* etc | | Body | *Struct* | Varies by type. | | Witness | *Struct* | Varies by type. | ## Entries An entry’s ID is based on its **type** and **body**. The type is encoded as raw sequence of bytes (without a length prefix). The body is encoded as a *SHA3-256* hash of all the fields of the body struct concatenated. > entryID = SHA3-256("entryid:" || type || ":" || SHA3-256(body)) Block Header | FIELD | TYPE | DESCRIPTION | | ------- | -------- | ---------------------------------------------------------- | | Type | *String* | The type of this Entry. E.g. *Issuance1, Retirement1* etc. | | Body | *Struct* | Varies by type. | | Witness | *Struct* | Varies by type. | | FIELD | TYPE | DESCRIPTION | | ------------------------------- | -------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------- | | Version | *Integer* | The type of this Entry. E.g. Issuance1, Retirement1 etc. | | Height | *Integer* | Block serial number | | Previous Block ID | *String32* | Hash of the previous block or all-zero string. | | Timestamp | *Integer* | Time of the block in milliseconds since 00:00:00 UTC Jan 1, 2018 | | Transactions Merkle Root | *MerkleRoot* | Root hash of the merkle binary hash tree formed by the transaction IDs of all transactions included in the block | | Assets Merkle Root | *PatriciaRoot* | Root hash of the merkle patricia tree of the set of unspent outputs with asset version 1 after applying the block. See Assets Merkle Root for details | | Next Consensus Program Bytecode | *String* | Authentication predicate for adding a new block after this one. | | ExtHash | *ExtStruct* | Extension fields | | WITNESS FIELD | TYPE | DESCRIPTION | | ----------------- | ------------- | ------------------------------------------------------------------------------------- | | Program Arguments | List\ | List of signatures and other data satisfying previous block’s next consensus program. | ## Block Header Validation **Input**\ BlockHeader entry, BlockHeader entry from the previous block, *PrevBlockHeader*. List of transactions included in block **Algorithm:**\ `Verify that the block’s version is greater or equal the block version in the previous block header.` \ `Verify that Height is equal to PrevBlockHeader.Height + 1.` \ `Verify that PreviousBlockID is equal to the entry ID of PrevBlockHeader.` \ `Verify that Timestamp is strictly greater than PrevBlockHeader.Timestamp.` \ `Evaluate the consensus program:` \ `Create a VM 1 with initial state and expansion flag set to false.` \ `Prepare VM with program arguments from the block witness.` \ `Set the VM’s program to the` \ `PrevBlockHeader.NextConsensusProgramBytecode.` \ `Execute Verify Predicate operation. If it fails, halt and return` \ `false.` \ `For each transaction in the block:` \ `Validate transaction with the timestamp and block version of the` \ `input block header.` \ `Compute the transactions merkle root for the block.` \ `Verify that the computed merkle tree hash is equal to TransactionsMerkleRoot.` \ `If the block version is 1:` \ `verify that the ExtHash is the all-zero hash` ## Block ID Block ID is defined as an *Entry ID* of the *block header* structure. ## Transaction Header | FIELD | TYPE | DESCRIPTION | | ------- | -------- | ------------- | | Type | *String* | txheader | | Body | *Struct* | See below. | | Witness | *Struct* | Empty struct. | | BODY FIELD | TYPE | DESCRIPTION | | ---------- | ---------------------------------------- | --------------------------------------------------------------------------------------------------------------- | | Version | *Integer* | Transaction version, equals 1. | | Height | *List\>* | A list of pointers to Outputs or Retirements. This list must contain at least one item. | | Data | *String32* | *Hash* of the reference data for the transaction, or a string of 32 zero-bytes (representing no reference data) | | Maxtime | *Integer* | Must be either zero or a timestamp higher than the timestamp of the *block* that includes the transaction. | | ExtHash | *ExtStruct* | *Hash* of all extension fields. *(See Extstruct.)* If Version is known, this must be *32 zero-bytes.* | ## Transaction ID **Transaction ID is defined as an Entry ID of the transaction header structure.** **Transaction Header Validation** If the **Maxtime** is greater than zero: \ Verify that it is greater than or equal to the **Mintime**. \ Validate each entry in the **Results.** \ If the transaction version is 1: \ Verify that **Results** is not empty. \ Verify that the **ExtHash** is the all-zero hash **Output 1** | FIELD | TYPE | DESCRIPTION | | ------- | -------- | ------------------ | | Type | *String* | **"**output1" | | Body | *Struct* | See below. | | Witness | *Struct* | Struct | | BODY FIELD | TYPE | DESCRIPTION | | ---------- | -------------- | ----------------------------------------------------------------------------------------------------------- | | Source | *ValueSource1* | The source of the units to be included in this output. | | Height | *Program* | The program to control this output. | | Data | *String32* | Hash of the reference data for this entry, or a string of *32 zero-bytes* (representing no reference data). | | ExtHash | *ExtStruct* | If the transaction version is known, this must be *32 zero-bytes* | **Output Validation** *Validate* Source. \ If the transaction version is 1: verify that the ExtHash is the all-zero hash. \ Verify that the program ACI GOLD *version* is not equal to 0. \ If the program ACI GOLD *version* is 1, verify that the program’s *bytecode* does not begin with **FAIL** instruction. **Retirement Validation** *Validate* **Source**. \ If the transaction version is 1: verify that the **ExtHash** \ is the all-zero hash.