Skip to content
\[ \newcommand{\lst}[1]{#1} \newcommand{\Tup}[1]{(#1)} \newcommand{\Apply}[2]{#1\langle#2\rangle} \newcommand{\MSig}[3]{\text{def}~#1(#2): #3} \newcommand{\Ov}[1]{\overline{#1}} \newcommand{\TyLam}[3]{\lambda(\Ov{#1:#2}).#3} \newcommand{\Trait}[2]{\text{trait}~#1~\{ #2 \}} \newcommand{\To}{\mapsto} \newcommand{\Low}[1]{\mathcal{L}{[\![#1]\!]}} \newcommand{\Lam}[2]{\lambda#1.#2} \newcommand{\IfThenElse}[3]{\text{if}~(#1)~#2~\text{else}~#3} \newcommand{\False}{\text{false}} \newcommand{\True}{\text{true}} \newcommand{\langname}{ErgoTree} \newcommand{\corelang}{Core-\lambda} \]

Cryptographic#

This document provides an in-depth look at the cryptographic schemes, protocols, and data structures used in the Ergo blockchain. Ergo’s security model relies heavily on advanced cryptographic protocols that ensure the integrity of transactions, protect user privacy, and enforce complex spending conditions within smart contracts. This document outlines the internal workings of these cryptographic schemes, focusing on their implementation within Ergo, particularly through the sigmastate-interpreter, sigma-rust, and Scrypto repositories.

Overview#

Ergo’s cryptographic toolkit is built around composable Sigma protocols, which allow for flexible, secure, and efficient proofs of knowledge and cryptographic operations within its smart contract framework. These Sigma protocols are the foundation of Ergo’s cryptographic security, and they enable privacy-preserving applications like multi-signature wallets, ring signatures, and threshold signatures.

Cryptographic Toolkit#

  • Hash Functions: SHA-256 & Blake2b are used for generating secure cryptographic digests and ensuring data integrity.
  • Encoding: Base58 encoding is used to represent binary data, such as public keys or hashes, in a more human-readable format.
  • Signing Algorithms: Ergo supports both ECDSA (secp256k1) and Schnorr signatures for secure transaction signing.
  • Primitive Secrets: Schnorr signatures and Diffie-Hellman tuples are primitive secrets used in creating proofs of knowledge.
  • Non-Interactive Proofs: Ergo makes cryptographic proofs non-interactive using the Fiat-Shamir transformation, making them suitable for blockchain environments.

For more details on cryptographic functions in ErgoScript, see ErgoScript Cryptographic Functions.

Sigma Protocols#

Sigma protocols (Σ-protocols) are a subclass of cryptographic proof systems that allow a prover to convince a verifier of knowledge of a secret without revealing the secret itself. They are integral to the privacy and security features in Ergo, enabling advanced cryptographic applications such as zero-knowledge proofs, ring signatures, and threshold signatures.

How Sigma Protocols Work#

At their core, Sigma protocols provide a secure way to prove the following properties:

  1. Proof of Knowledge of Discrete Logarithm: Prove knowledge of the discrete logarithm of a given public key without revealing the secret key.

  2. Proof of Equality of Discrete Logarithms (Diffie-Hellman Tuple): Prove that two discrete logarithms (e.g., over different bases) are equal without revealing the logarithms.

These basic Sigma protocols can be combined using logical operators, such as AND, OR, and THRESHOLD (k-out-of-n), to form complex proofs.

Composability of Sigma Protocols#

One of the key advantages of Sigma protocols is their composability. They can be combined in flexible ways to create sophisticated cryptographic contracts:

  • OR Proofs: Prove knowledge of one secret from a set of secrets (e.g., ring signatures).
  • AND Proofs: Prove knowledge of all secrets in a statement (e.g., multi-signature).
  • Threshold Proofs: Prove knowledge of at least k out of n secrets. This is essential for threshold signatures, where a subset of participants must cooperate to authorize a transaction.

These constructs enable the creation of powerful, privacy-preserving applications on Ergo.

Example: 3-out-of-5 Threshold Signature#

Consider a 3-out-of-5 threshold signature that allows any three participants to sign a transaction. This ErgoScript implements such a scheme:

val ringScript = s"""
{
  atLeast(
    3, 
    Coll(
      PK("9f8ZQt1Sue6W5ACdMSPRzsHj3jjiZkbYy3CEtB4BisxEyk4RsNk"), 
      PK("9hFWPyhCJcw4KQyCGu4yAGfC1ieRAKyFg24FKjLJK2uDgA873uq"), 
      PK("9fdVP2jca1e5nCTT6q9ijZLssGj6v4juY8gEAxUhp7YTuSsLspS"), 
      PK("9gAKeRu1W4Dh6adWXnnYmfqjCTnxnSMtym2LPPMPErCkusCd6F3"),
      PK("9gmNsqrqdSppLUBqg2UzREmmivgqh1r3jmNcLAc53hk3YCvAGWE")
    )
  )
}

This script enables three participants from a group of five to cooperatively sign and authorize a transaction. It leverages the THRESHOLD (k-out-of-n) logic, which is native to Sigma protocols, ensuring that only a subset of participants is required to perform cryptographic operations.

Schnorr Signatures#

Schnorr signatures are a key part of Ergo’s cryptographic foundation, providing an efficient, simple, and secure way to verify the authenticity of transactions. The Schnorr signature scheme is based on the hardness of the discrete logarithm problem and is favored for its performance and security properties over ECDSA.

How Schnorr Signatures Work#

The signing process in Schnorr signatures follows these steps:

  1. Key Generation: Generate a private key \(x\) and compute the corresponding public key \(P = xG\), where \(G\) is the generator of the elliptic curve (SecP256K1).

  2. Signing: To sign a message \(m\), the user:

  3. Picks a random nonce \(k\) and computes \(R = kG\),
  4. Computes \(e = H(R || P || m)\),

  5. Computes the signature as \(s = k + ex\).

  6. Verification: The verifier checks the signature by computing \(R' = sG - eP\) and verifying: [ e = H(R' || P || m) ]

Schnorr signatures are widely used in Ergo for multi-signature schemes, privacy-enhancing protocols, and adaptor signatures.

Use Cases of Schnorr Signatures#

  • Multi-Signature Wallets: Schnorr signatures enable efficient and secure multi-signature wallets, where multiple participants must sign a transaction collaboratively.
  • Adaptor Signatures: Adaptor signatures allow for conditional private swaps, such as atomic swaps between different cryptocurrencies, without revealing sensitive information.

For detailed examples and implementation, see Verifying Schnorr Signatures in ErgoScript.

Diffie-Hellman Protocol#

The Diffie-Hellman (DH) protocol is widely used in cryptography for secure key exchange. In Ergo, the Diffie-Hellman Tuple (DHT) protocol allows provers to demonstrate shared knowledge of a secret without revealing it, enabling privacy-preserving cryptographic proofs.

Diffie-Hellman Tuple (DHT)#

In a Diffie-Hellman Tuple, a prover proves knowledge of a shared secret \(x\) such that:

\[ u = g^x \quad \text{and} \quad v = h^x \]

This protocol can be combined with Sigma protocols to create privacy-preserving smart contracts, such as stealth addresses and mixers. For instance, ErgoMix relies on the security of the Diffie-Hellman protocol to ensure transaction fungibility and user privacy.

Use Cases of Diffie-Hellman#

  • Stealth Addresses: Ensure that each transaction generates a unique address, making it difficult to link transactions to the original public address, protecting user privacy.
  • ZeroJoin Mixers: Enable on-chain privacy-preserving mixing of tokens, ensuring that transactions remain fungible and private without reliance on trusted third parties.

For a deep dive into Diffie-Hellman Tuples, refer to Diffie.

Data Structures in Ergo#

Ergo employs specialized cryptographic data structures to ensure secure and efficient state management within its blockchain:

AVL+ Trees#

Ergo uses AVL+ trees as part of its Authenticated Dynamic Dictionary (ADD) to track UTXO state changes. These trees provide cryptographic proofs of state changes while maintaining logarithmic complexity for inserts, lookups, and deletions. AVL+ trees are essential for the UTXO model’s scalability and efficiency, enabling fast and secure updates across the network.

Merkle Trees#

Merkle trees are used in Ergo to ensure the integrity of large datasets, such as blocks of transactions, without requiring the entire dataset to be transmitted or verified. By storing only the root hash of a Merkle tree, nodes can quickly verify that individual transactions are part of the block, reducing the overhead of verification.

Learn more about Merkle trees here.

Security Considerations#

The cryptographic schemes in Ergo rely on the hardness of the discrete logarithm problem and other well-established cryptographic assumptions. It is critical that developers design smart contracts carefully to avoid vulnerabilities, such as weak randomness or improper use of cryptographic primitives. Ergo provides extensive test coverage for its cryptographic implementations, such as the SigningSpecification.

Conclusion#

Ergo’s cryptographic framework, built on Sigma protocols, Schnorr signatures, and Diffie-Hellman key exchanges, provides robust tools for secure and privacy-preserving decentralized applications. Its composable cryptographic proofs enable developers to create complex spending conditions, privacy-enhancing features, and flexible multi-signature schemes, all while maintaining a high standard of security.

For more information, visit the sigmastate-interpreter repository, sigma-rust repository, and Scrypto repository.