The 'Sigma Language'#
The sigmastate-interpreter repository contains implementations of ErgoScript compiler and ErgoTree Interpreter for a family of Sigma-protocol based authentication languages (or simply Sigma language).
Sigma Language Background#
Every coin in Bitcoin is protected by a program in the stack-based Script language. An interpreter for the language evaluates the program against a context (a few variables containing information about a spending transaction and the blockchain), producing a single boolean value. While Bitcoin Script allows some contracts to be programmed, its abilities are limited. Also, a hard fork would be required to add new cryptographic primitives, such as ring signatures.
Generalizing the Bitcoin Script, ErgoScript compiler and ErgoTree interpreter implement an authentication language which allows developers to specify coin spending conditions. The ErgoScript Compiler compiles the source code into ErgoTree byte code, which can be saved in UTXO coins to protect their spending (same as in Bitcoin).
ErgoTree, in turn, is a bytecode language and memory representation that can be deterministically interpreted in the given blockchain context.
ErgoTree defines guarding proposition for a coin as a logic formula which combines predicates over a context and cryptographic statements provable via Σ-protocols with AND, OR, k-out-of-n connectives.
An interacting party willing to spend the coin first constructs a prover with a set of secrets, it knows and then the prover is executed in two steps:
- Reduction - the prover uses the ErgoTree interpreter which deterministically reduces the ErgoTree proposition to a compound cryptographic statement (aka sigma proposition, Σ-protocol) by evaluating ErgoTree over known shared context (state of the blockchain system and a spending transaction). This step produces a value of the SigmaBoolean type.
- Signing - the prover is turning the obtained (and possibly complex) Σ-proposition into a signature with the help of a Fiat-Shamir transformation. This step produces a proof that the party knows the secrets such that the knowledge can be verified before the spending transaction is added to the blockchain.
To allow valid coin spending a verifier is running the ErgoTree interpreter with the following three inputs:
- A guarding proposition given by an ErgoTree
- A blockchain context of the transaction being verified
- A proof (aka transaction signature) generated by a prover
The verifier is executed as part of transaction validation for each input and is executed in three steps:
Same as prover, the verifier uses the ErgoTree interpreter and deterministically produces a value of the SigmaBoolean type. However, this step must finish the evaluation for any possible inputs within concrete fixed time limit (aka maximum cost), which the interpreter checks.
The verifier estimates the complexity of the cryptographic Sigma proposition (based on the size and the concrete nodes of the SigmaBoolean tree). The spending fails if the estimated cost exceeds the maximum limit.
The signature checker, takes;
- The proof
- The SigmaBoolean (aka sigma protocol proposition)
- The signed message (e.g. transaction bytes).
The checker then verifies the proof, which means it verifies that all the necessary secrets have been known and used to construct the proof (i.e. sign the transaction).