Glossary

The following terms and their definitions clarify specialized or technical aspects of Topos technology.

AIR Program

The algebraic representation of a statement/relation one wants to prove validity of using a STARK proving system. It can be seen as the translation of a high level relation to a language understandable by the prover/verifier.

Asymmetric Key Cryptography

The use of different (but mathematically related) keys for encrypting and decrypting data. See also Public Key Cryptography.

Atomic Broadcast

A distributed computing principle ensuring that all participants in a system consistently deliver messages in a specific order. Drawing from the Chandra and Toueg protocol, a consensus-based solution, it operates in synchronized rounds, where each party sends endorsed messages to others. The system collectively decides on the order and validity of these messages, even if some are from malicious sources. By requiring consensus and valid digital endorsements, atomic broadcast guarantees that messages from honest parties are delivered promptly and in a uniform sequence across the network, despite potential interference from adversaries.

Atomic Snapshot

A shared object utilized by NN processes, each of which has a unique location within the object. This location contains records of all successful transfer operations executed by the respective process. Considering each account is controlled by only one process, all transfers from a specific account will be found at its designated location in the atomic snapshot, linked to its owner process.

In simpler terms, imagine the Atomic Snapshot as a shared list of NN compartments, where each compartment belongs to a specific process.

See also Atomic Snapshot memory, Shared-memory model.

Atomic Snapshot Memory, Shared-memory model

Atomic snapshot memory refers to a communal data storage system. It allows various concurrent processes to save data in a group of shared locations. Unique to this system is the ability to read the entire group's contents in one swift action, known as an atomic scan operation.

BAR Fault Tolerance

A concept in the world of distributed systems that seeks to address the challenges of having nodes with various behaviors. Byzantine fault tolerance (BFT) deals with just two types of nodes: faulty (Byzantine) and correct. The BAR model expands on this by introducing three types of nodes: Byzantine, Altruistic, and Rational.

The BAR Fault Tolerance model acknowledges that, in real-world distributed systems, not all nodes can be categorized as "faulty" or "correct." Some nodes might act out of self-interest (rational), while others might consistently do what is expected (altruistic). The BAR model seeks to develop protocols and strategies that ensure system reliability and functionality even when faced with such a diverse set of node behaviors.

Byzantine Fault Tolerance (BFT)

A protocol in distributed systems designed to handle nodes that behave unpredictably or maliciously, known as Byzantine nodes. BFT ensures system reliability and consensus even when a subset of nodes behaves maliciously.

Blockchain

A distributed ledger that records totally ordered transactions, linking the records together via cryptographic hashes. Each block contains the transaction data, a timestamp, and a cryptographic hash of the previous block. The inclusion of the hash of the previous block forms a continuous chain, since the data stored in any given block is affected by the data that came before it. Functionally, this makes each block in a blockchain immutable once written, since a block can not be altered without also altering all subsequent blocks.

Certificate

A data structure created by the Sequencer of subnets, including the Topos Subnet, that certifies subnet state transitions. The certificate encapsulates:

  1. Metadata to verify the proof of the correct state transition of the source subnet.
  2. The target subnet list, identifying the intended recipients.

Collision-Resistant Hash

A cryptographic function that makes it computationally infeasible to find two distinct inputs that produce the same hash output, ensuring data integrity and preventing unauthorized alterations. It is conjectured that collision-resistant hash functions are resistant to quantum computing attacks.

Consensus Number k

In distributed systems, the consensus number (denoted as k) refers to the maximum number of processes that can achieve consensus using a specific synchronization primitive. A primitive with a consensus number of k can solve the consensus problem for up to k processes but no more. This metric establishes a hierarchy for the power of synchronization primitives, with higher values indicating greater capability to coordinate among multiple processes.

Consistency Levels

Describes the behavior of a distributed system regarding the visibility and order of updates to a single data item, ensuring that all participants in the system have a coherent view of the data. Also known as a consistency model, it provides guarantees on how and when changes made by one participant become visible to others, often balancing between system performance and the predictability of data accesses.

Cross-Subnet Message

A message that is sent between two subnets.

Delivery

One certificate is referred to as "delivered" from the point of view of one TCE process.

DevNet

A mostly operational product network for active development and testing of TCE, the Topos Network and the Subnet SDK. Low stability is assumed for this environment. There may be more than one DevNet, such as for fit-for-purpose testing.

Double Echo

Academic name of the core component of the broadcast implemented by the TCE. In the context of distributed systems, a Double Echo protocol refers to a fault-tolerant broadcasting algorithm designed to handle Byzantine failures and ensure message delivery across all correct processes in the system.

Echo

Payload on the TCE that is submitted upon starting the broadcast of one certificate. Participants count the number of Echoes that they receive until reaching a threshold in order to switch to the second round with the Ready payload.

Elliptic Curve Cryptography (ECC)

A modern form of asymmetric cryptography that utilizes the mathematics of elliptic curves to generate key pairs: a private key and a corresponding public key. One advantage of ECC is that it provides the same level of security as traditional methods like RSA but with much shorter key lengths, which makes ECC systems more efficient in terms of speed and the amount of data transmission required. Elliptic Curve Cryptography is known to be susceptible to quantum attacks.

Epoch

In Topos, an epoch refers to a continuous sequence of rr blocks, denoted as Ep=bl1,bl2,...,blrEp = {bl_1, bl_2, ... , bl_r}. The specific number rr is a system parameter. Typically, an epoch corresponds to approximately 24 hours.

Event

An "event" represents a specific action in a process.

Executor Service

An HTTP REST API that accepts requests for transaction executions on any subnets.

The Fischer-Lynch-Paterson (FLP) Result

Also known as the FLP Impossibility, this theorem establishes that, in an asynchronous system, reaching consensus (ensuring all correct processes converge to the same value) is unattainable if even a single node fails, whether due to a crash or byzantine fault.

While the FLP impossibility theorem establishes fundamental limitations for consensus in asynchronous systems with crash failures, practical systems often navigate around these limitations.

FROST

A threshold Schnorr signature scheme, which allows multiple participants of a set to collectively sign a payload, while the signature generated is identical to a regular 1-person Schnorr signature, and this is for any set size and any threshold parameter. See also ICE-FROST.

Harvest and Yield

Yield denotes the probability of a system successfully completing a request, often equated with system availability, such as "four-nines availability" signifying a 99.99% success rate. On the other hand, Harvest evaluates the completeness of returned data in comparison to the ideal dataset. A system that doesn’t deliver all the data, possibly due to issues like an unavailable node, results in a harvest of less than 100%. These metrics allow for nuanced discussions about the trade-offs in system availability and data completeness.

Represents the last certificate entry on a certificate stream (certificate stream for both source and target subnets).

History

In the context of operations, a history (denoted as HH) is a sequence that defines a specific order in which operations occurred.

This sequence introduces an irreflexive partial order, represented by H\prec_H. In this order, one operation e0e_0 is considered to precede another operation e1e_1 if the result of e0e_0 (denoted as res(e0)res(e_0)) comes before the invocation of e1e_1 (denoted as inv(e1)inv(e_1)) within the history HH.

Formally, e0He1e_0 \prec_H e_1, if res(e0)res(e_0) precedes inv(e1)inv(e_1) in HH.

The history represents the observed order of these operations.

ICE-FROST

Upgrade to the FROST protocol to support cheating participant identifiability (during the key generation, key resharing or signature phase); key generation/resharing robustness (that is, the protocol can continue even with malicious participants); and static keys (permitting a single public key that does not change when the individual secret keys are reshared to another set of participants).

Interoperability

The capability of different blockchain systems to effectively communicate and work together. Each of these systems maintains its own unique distributed ledger. Transactions can be initiated on one blockchain and continue or be verified on another. Moreover, data stored on one blockchain can be accessed, verified and referenced by a different blockchain in a way that ensures both ledgers understand and agree on the meaning of the shared data.

Linearization

Ensures that operations in a concurrent system appear as if they were executed sequentially, even if they occur simultaneously. It provides an illusion that every operation acts instantaneously between its start and finish, allowing concurrent object operations to be described by pre and post conditions. A system is linearizable when each of its individual objects is linearizable, distinguishing it from properties like sequential consistency. The concept is fundamental to the "C" (consistency) in the CAP Theorem. For a given operation, the linearization point, or the moment it seems to occur atomically, is its critical section. Contrastingly, Serializability* concerns transactions involving multiple operations over various objects, ensuring they align with a particular serial order.

Merkle Tree

A cryptographic data structure that enables efficient commitment and membership verification of large datasets by organizing them into a hierarchical tree-like structure, with each node's value derived from the cryptographic hash of its child nodes. It ensures data integrity and facilitates quick identification of any changes or discrepancies in the dataset.

Merkle Patricia Trie

A data structure that is used to store a map between arbitrary-length data (keys) and fixed-length values. It is essentially a kind of search tree, and it's used extensively in certain systems (like Ethereum) where a large amount of data needs to be stored, searchable and provable (the Merkle part of the name indicates that each node in the trie is labeled with the hash of the labels or values of its child nodes).

Message Delivery

Pertains to the rules and guarantees about how messages are delivered among different processes in a distributed system. The three main types of message delivery that you should know about are:

  • Reliable Delivery: This guarantees that if a message mm is successfully delivered to one correct process, it will eventually be delivered by all other correct processes.
  • Total Order Delivery: This ensures a consistent global order in which messages are delivered. If one correct process delivers message aa before message bb, then all correct processes will deliver aa before bb. That is, there's a universally agreed order: either aa comes before bb or bb comes before aa.
  • Causal Order Delivery: The order preserves the sequence of messages based on their cause-and-effect relationship. If a message "aa" is delivered before message "bb" is sent, then "aa" will always precede "bb". Likewise, if a sender sends message "bb" before dispatching message "cc", "cc" will always come after "bb".

plonky2

The proving/verifying backend for the zk-EVM STARK proof, in Rust.

Polygon Edge

Blockchain framework used as the blockchain component of subnets.

Poseidon

A hash function tailored for efficient execution within a proving system. Currently used in plonky2 when computing proofs of computational integrity.

Position

Refers to the certificate's location within a stream, irrespective of whether it is in a SourceStream or a TargetStream. Its position can be Zero, Head, or any positive integer.

Process

A series of operations or tasks that a system undertakes. While some may refer to it as a "node," the term "process" provides a more precise description.

  • Benign process: A process is termed benign when it faithfully adheres to the designated algorithm and can only malfunction by crashing.
  • Correct process: This is a process that operates as intended, akin to what is termed an "honest node."

Process Subhistory

A process subhistory, denoted as HpH|p, refers to the specific series of events in a larger history, HH, that are associated with the process named pp.

Two histories, HH and HH’, are considered equivalent if their respective subhistories for every process pp are identical, meaning Hp=HpH|p = H’|p.

A history HH is deemed well-formed when every process subhistory HpH|p within it follows a sequential order.

Prover

The party that generates the proof. They claim to know a secret or a piece of information, and their goal is to convince the verifier of this knowledge without revealing the information itself.

Public input

A public variable given to a verifier, which is passed to the verification function along with a zero-knowledge proof. Depending on the underlying statement in which correctness is being proven, public inputs may vary.

Public Key Cryptography

An asymmetric cryptographic technique that involves a pair of mathematically related keys: a public key and a private key. The public key, freely shareable, is used to encrypt data, while the corresponding private key is employed for decryption. This approach enables secure communication over unsecured channels, eliminating the need for a pre-shared secret between sender and recipient. Common internet communication protocols like HTTPS and SSL utilize public key encryption through algorithms such as RSA and AES, while blockchains often rely on Elliptic Curve Cryptography.

Quantum Computing

A field of computation that utilizes the principles of quantum mechanics to perform complex calculations exponentially faster than classical computers, enabling potential breakthroughs in cryptography, optimization and simulation.

Quantum Resistance

Refers to cryptographic algorithms and protocols designed to withstand attacks from quantum computers, ensuring long-term security for sensitive data and communications even in the presence of powerful quantum adversaries. Also known as post-quantum cryptography.

Quorum

In a crash-fault system, a quorum consists of more than N2\frac{N}{2} processes. It ensures that any two quorums will have at least one process in common. For more complex systems with arbitrary faults (Byzantine systems), a Byzantine quorum, designed to tolerate f faults, includes over (N+f)2\frac{(N+f)}{2} processes. Two Byzantine quorums will always overlap with at least one correct process. Notably, to ensure reliability in algorithms that tolerate Byzantine faults, fewer than f<N3f<\frac{N}{3} processes should fail.

Range Proof

A zero-knowledge range proof is a cryptographic protocol that enables a prover to demonstrate knowledge of a value within a specific range to a verifier without revealing the exact value itself.

Sequencer

Refers to the actor(s) orchestrating the streams between the inside and the outside of subnets. They create, fetch and propagate certificates from and to the TCE.

Serializability

Serializability refers to the property of a transaction schedule in which the outcome of transactions, when executed concurrently, is the same as if they had been executed one after another without any overlap in time.

In simpler terms, it ensures that even when multiple transactions are executed simultaneously, the end result is as if they were executed in a specific order, one at a time.

See also Linearizability.

Site Autonomy

Site autonomy means that each server participating in a distributed database is administered independently from all other databases. Although several databases can work together, each database is a separate repository of data that is managed individually.

Source order

In a secure transfer system, a correct process should not accept a transfer, TT, before accepting all transfers that TT depends on. Specifically, transfers originating from the same process, pp, do not commute. As a result, all correct processes must deliver them in the same order. This property is referred to as the source order.

Source Subnet

Subnet emitting a certificate.

State

A "state" denotes a snapshot of all the information contained within a system at a specific moment.

For the TCE, its state is defined by the collection of certificates delivered by its participants.

In terms of a subnet, the state is a comprehensive structure that does more than just record account details and balances. It also has a machine state capable of executing any machine code. This state evolves from one block to another following a set of pre-defined rules. The Ethereum Virtual Machine (EVM) determines these rules for transitioning between blocks.

Subnet

A network that is sovereign in execution and performs certificate submissions in order to settle its state and interoperate with other subnets.

Sybil Attack

A type of security threat in which a single adversary creates multiple fake identities or nodes in a network to subvert the system's functionality or gain a disproportionate influence. Countermeasures, like proof-of-work mining in blockchain systems, require participants to demonstrate resource commitment (e.g., computational power) to verify their legitimacy, thereby deterring the proliferation of fraudulent entities.

Symmetric Key Cryptography

Encryption scheme where the same key is used to encrypt and decrypt a message. For the same level of security, symmetric key encryption typically requires significantly shorter keys than asymmetric key cryptography.

Target Subnet

A subnet that is designated to receive cross-subnet messages from a source subnet's certificate field target_subnet_list.

Testnet

An operational product network for subnet blockchain builders, dApp developers, TCE node operators, etc, to build and gain experience for growing the ecosystem. Topos releases that are fully qualified with limited exceptions. This environment is assumed to have good stability and limited development-related changes; however, issues may be found in this environment to be addressed before MainNet.

Threshold Signature

A type of cryptographic scheme that allows a group of parties (for example validators) to collectively generate a single signature for a given message, under the condition that a minimum number of them, a "threshold", agree to sign.

Topos Cross-Subnet Messaging Protocol

Protocol by which target subnets can trustlessly and securely interpret cross-subnet messages from source subnets and execute requested transactions locally. Subnets are free to implement other specific cross-subnet messaging protocols that are built on top of the UCI and the TCE.

Topos Subnet

A blockchain network designed primarily to manage the registration of subnets and TCE participants in the ecosystem. Additionally, it is responsible for the management of TOPOS, the native asset of the ecosystem. An integral part of its design is to facilitate on-chain voting, enabling TOPOS token holders to contribute to the development and enhancement of the protocol.

Topos Subnet Validator

A participant tasked with the generation of blocks on the Topos Subnet. Provided they pledge TOPOS as stake and actively engage in the network operations honestly, validators are rewarded for their contribution.

topos-sequencer

Software containing the Topos logic of the subnet. Each validator runs this process on the same host machine alongside the blockchain process.

Transmission Control Engine (TCE)

The TCE is a permissionless network that implements a primitive of reliable broadcast leveraged to order and settle certificates in a more optimal way than under consensus.

Trie

A tree-like data structure used to efficiently store and retrieve dynamic sets of key-value pairs, where keys are usually strings. It optimizes search operations by sharing common prefixes among keys. In the Topos context, this will typically refer to a Merkle Patricia Trie.

Trusted Setup Ceremony

A procedure to generate public parameters, known as Common Reference String (CRS), for a cryptographic protocol in such a way that no single party gains enough information to cheat the system. These parameters are usually generated jointly by multiple participants, and each participant contributes some randomness to the process. This is meant to ensure that even if some of the participants are dishonest or compromised, the overall system remains secure as long as at least one participant acts honestly. Once the CRS has been created, the prover and the verifier will both use it to, respectively, generate and verify proofs.

Note

A trusted setup is often seen as a drawback in cryptographic protocols that require it because any flaw in the setup could compromise the security or privacy of the entire system. If the initial setup isn't done correctly or securely, or if it's performed by a single trusted entity that later becomes compromised, the integrity of the system can be undermined.

Verifier

The party that checks a proof. Their goal is to be convinced that the prover knows a secret or piece of information without learning what the information is.

Wait-free

In the context of shared memory algorithms, an algorithm is described as wait-free if every correct process is guaranteed to complete its operation in a finite number of its own steps, irrespective of the actions or failures of other processes.

In simpler terms, if process FF starts an operation, it will finish it within a predictable number of its own atomic steps, no matter what other processes are doing. This assumes that local operations of any process, say P1P_1, and actions on shared objects complete within a known timeframe.

World State Trie

The Trie in charge of keeping track of the state of all Accounts.

Zero-knowledge Ethereum Virtual Machine (zkEVM)

A type of virtual machine designed to run smart contract transactions in a manner that is compatible with both the computations of zero-knowledge proofs and the current infrastructure of Ethereum. The zkEVM mirrors the Ethereum setting, effectively integrating the established Ethereum development experience and existing utilities into highly scalable and secure subnets.

zk-SNARK

Stands for "Zero-Knowledge Succinct Non-Interactive Argument of Knowledge." A non-interactive cryptographic protocol that enables one party (the prover) to prove the validity of a statement to another party (the verifier) without revealing any information other than that the proof is true. The mathematical basis for zk-SNARK is elliptic curve cryptography, and zk-SNARK requires a [trusted setup(./glossary.html#trusted-setup)].

zk-STARK

Stands for "Zero-Knowledge Scalable Transparent Argument of Knowledge." Similar to the zk-SNARK, it is a non-interactive cryptographic protocol that enables one party (the prover) to prove the validity of a statement to another party (the verifier) without revealing any information other than that the proof is true. The mathematical basis for a zk-STARK is collision-resistant hash functions, and zk-STARK does not require a trusted setup. zk-STARK proofs are larger than zk-SNARK proofs, but it is less computationally demanding to verify them, making them more scalable.