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<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 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:
program,
arguments (list of strings),
transaction version (integer).
Asset Definition
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<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 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
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))
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<String> | 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<Pointer<Output1|Retirement 1>> | 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.
Last updated