Code Monkey home page Code Monkey logo

sigmastate-interpreter's Introduction

CI codecov

ErgoScript compiler and ErgoTree interpreter

This repository contains implementations of ErgoScript compiler and ErgoTree Interpreter for a family of Sigma-protocol based authentication languages (or simply Sigma language).

This library is used internally in Ergo Node and ergo-wallet, the public interfaces are subject to change.

For development of Ergo applications using JVM languages (Java/Scala/Kotlin/etc) a better alternative is to use Appkit.

Sigma Language Background

Every coin in Bitcoin is protected by a program in the stack-based Script language. An interpreter for the language is evaluating the program against a context (few variables containing information about a spending transaction and the blockchain), producing a single boolean value as a result. While Bitcoin Script allows for some contracts to be programmed, its abilities are limited. Also, to add new cryptographic primitives, for example, ring signatures, a hard-fork is required.

Generalizing the Bitcoin Script, ErgoScript compiler and ErgoTree interpreter implement an authentication language which allows to express 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 which 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 and 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 quarding 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 tree steps:

  • Reduction - same as prover, the verifier uses the ErgoTree interpreter and deterministically produces a value of the SigmaBoolean type. However, this step must finish evaluation for any possible inputs within concrete fixed time limit (aka maximum cost), which is checked by the interpreter.

  • Cost estimation - the verifier estimates the complexity of cryptographic Sigma proposition (based in the size and the concrete nodes of SigmaBoolean tree). The spending fails if the estimated cost exceeds the maximum limit.

  • Signature verification - the signature checker takes 1) the proof, 2) the SigmaBoolean (aka sigma protocol proposition) and 3) the signed message (e.g. transaction bytes). The checker than verifies the proof, which means it verifies that all the necessary secrets has been known and used to construct the proof (i.e. sign the transaction).

Getting Started

This library is publishied on Maven repository and can be added to the SBT configuration of Scala project.

libraryDependencies += "org.scorexfoundation" %% "sigma-state" % "4.0.3"

Repository Organization

sub-module description
common Used in all other submodules and contain basic utility classes
core Implementation of graph-based intermediate representation of ErgoTree, which is used in cost estimation and interpretation
docs Collection of documents
library Implementation of graph IR nodes for Coll, Size and other types
library-api Declarations of interfaces
library-impl Implementation of interfaces
sigma-api Declarations of runtime interfaces which are used in ErgoTree interpreter
sigma-impl Implementation of sigma-api interfaces
sigma-library Implementation of graph IR nodes for Sigma types
sigmastate Implementation ErgoTree, Interpreter and cost estimation

Acknowledgments

We thank JetBrains for supporting this project since 2021 by providing All Products Pack subscription.

We thank YourKit for support of open source projects with its full-featured Java Profiler. YourKit, LLC is the creator of YourKit Java Profiler and YourKit .NET Profiler, innovative and intelligent tools for profiling Java and .NET applications.

References

sigmastate-interpreter's People

Contributors

andyceo avatar aslesarenko avatar catena2w avatar dmdv avatar ergomorphic avatar gagarin55 avatar greenhat avatar jozanek avatar knizhnik avatar kushti avatar mike-aksarin avatar oskin1 avatar pragmaxim avatar reyzin avatar robkorn avatar scalahub avatar terjokhin avatar thub1271 avatar tolsi avatar victormikheev avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.