`sigma-compiler` by Ian Goldberg, iang@uwaterloo.ca  
Version 0.1.0-rc2, 2025-09-22

This crate provides the `sigma_compiler!` macro as an easy interface
to the [`sigma-proofs`](https://crates.io/crates/sigma-proofs) API
for non-interactive zero-knowledge sigma protocols.

The general form of this macro is:
```
sigma_compiler! { proto_name<Grp>,
   (scalar_list),
   (point_list),
   statement_1,
   statement_2,
   ...
}
```

The pieces are as follows:

  - `proto_name`: The name of the protocol.  A Rust submodule will
     be created with this name, containing all of the data
     structures and code associated with this sigma protocol.
  - `<Grp>`: an optional indication of the mathematical group to use
    (a set of `Point`s and associated `Scalar`s) for this sigma
    protocol.  The group must implement the
    [`PrimeGroup`]
    trait.  If `<Grp>` is omitted, it defaults to assuming there is
    a group called `G` in the current scope.
  - `scalar_list` is a list of variables representing `Scalar`s.
    Each variable can be optionally tagged with one or more of the
    tags `pub`, `rand`, or `vec`.  The tags `pub` and `rand` cannot
    both be used on the same variable.
    - `pub` means that the `Scalar` is public; this can be used for
      public parameters to the protocol, such as the limits of
      ranges, or other constants that can appear in the statements.
      Any `Scalar` not marked as `pub` is assumed to be private to
      the prover, and the verifier will learn nothing about that
      value other than what is implied by the truth of the
      statements.
    - `rand` means that the `Scalar` is a uniform random `Scalar`.
      A `rand` `Scalar` must be used only once in the statements.
      These are typically used as randomizers in Pedersen
      commitments.
    - `vec` means that the variable represents a vector of
      `Scalar`s, as opposed to a single `Scalar`.  The number of
      entries in the vector can be set at runtime, when the sigma
      protocol is executed.
  - `point_list` is a list of variables representing `Point`s.  All
    `Point` variables are considered public.  Each variable can be
    optionally tagged with one or more of the tags `cind`, `const`,
    or `vec`.  All combinations of tags are valid.
    - All `Point`s tagged with `cind` are _computationally
      independent_.  This means that the _prover_ does not know a
      discrete logarithm relationship between any of them.
      Formally, `P1`, `P2`, ..., `Pn` being computationally
      independent `Point`s means that if the prover knows `Scalar`s
      `s1`, `s2`, ..., `sn` such that `s1*P1 + s2*P2 + ... + sn*Pn =
      0` (where `0` is the identity element of the group), then it
      must be the case that each of `s1`, `s2`, ..., `sn` is the
      zero `Scalar` (modulo the order of the group).  Typically,
      these elements would be generators of the group, generated
      with a hash-to-group function, as opposed to multiplying the
      standard generator by a random number (at least not one known
      by the prover).  `Point`s marked `cind` are typically the
      bases used in Pedersen commitments.
    - `const` means that the value of the `Point` will always be the
      same for each invocation of the sigma protocol.  This is
      typical for fixed generators, but possibly other `Point`s as
      well.
    - `vec` means that the variable represents a vector of `Point`s,
      as opposed to a single `Point`.  The number of entries in the
      vector can be set at runtime, when the sigma protocol is
      executed.
   - Each `statement` is a statement that the prover is proving the
     truth of to the verifier.  Each statement can have one of the
     following forms:
     - `C = arith_expr`, where `C` is a variable representing a
       `Point`, and `arith_expr` is an _arithmetic expression_
       evaluating to a `Point`.  This is a _linear combination
       statement_.  An arithmetic expression can consist of:
       - `Scalar` or `Point` variables
       - integer constants
       - the operations `*`, `+`, `-` (binary or unary)
       - the operation `<<` where both operands are expressions with no
         variables
       - the function `sum` that takes a single vector argument and
         returns the sum of its elements
       - parens

       You cannot multiply together two private subexpressions, and
       you cannot multiply together two subexpressions that both
       evaluate to `Point`s.  You cannot add a `Point` to a
       `Scalar`.  Integer constants are considered `Scalar`s, but
       all arithmetic subexpressions involving only constants must
       have values that fit in an [`i128`].

       If any variable in `arith_expr` is marked `vec`, then this is
       a vector expression, and `C` must also be marked `vec`.  The
       statement is considered to hold in 'SIMD' style; that is, the
       lengths of all of the vector variables involved in the
       statement must be the same, and the statement is proven to
       hold component-wise.  Any non-vector variable in the
       statement is considered equivalent to a vector variable, all
       of whose entries have the same value.  Note that you can do a
       dot product between two vectors `x` and `A` with `sum(x*A)`.

       As an extension, you can also use an arithmetic expression
       evaluating to a _public_ `Point` in place of `C` on the left
       side of the `=`.  For example, if `a` is a `Scalar` tagged
       `pub`, and `C` is a `Point`, then the expression `(2*a+1)*C =
       arith_expr` is a valid linear combination statement.
     - `a = arith_expr`, where `a` is a variable representing a
       private `Scalar`.  This is a _substitution statement_.  Its
       meaning is to say that the private `Scalar` `a` has the value
       given by the arithmetic expression, which must evaluate to a
       `Scalar`.  The effect is to substitute `a` anywhere it
       appears in the list of statements (including the right side
       of other substitutions) with the given expression.  The
       expression must not contain the variable `a` itself, either
       directly, or after other substitutions.  For example, the
       statement `a = a + b` is not allowed, nor is the combination
       of substitutions `a = b + 1, b = c + 2, c = 2*a`.
     - `a = arith_expr`, where `a` is a variable representing a
       public `Scalar`.  This is a _public Scalar equality
       statement_.  Its meaning is to say that the public `Scalar`
       `a` has the value given by the arithmetic expression, which
       must evaluate to a public `Scalar`.  The statement is simply
       removed from the list of statements to be proven in the
       zero-knowledge sigma protocol, and code is emitted for the
       prover and verifier to each just check that the statement is
       satisfied.  Currently, there can be no vector variables in
       this kind of statement.
     - `(a..b).contains(x)`, where `a` and `b` are constants or
       _public_ `Scalar`s (or arithmetic expressions evaluating to
       public `Scalar`s), and `x` is a private `Scalar`, possibly
       multiplied by a constant and adding or subtracting an
       expression evaluating to a public `Scalar`.  For example,
       `((a+2)..(3*b-7)).contains(2*x+2*c*c+12)` is allowed, if `a`,
       `b`, and `c` are public `Scalar`s and `x` is a private
       `Scalar`.  `(a..b).contains(x)` is a _range statement_, and
       it means that `x` lies in the range `a..b`.  As usual in
       Rust, the range `a..b` _includes_ `a`, but _excludes_ `b`.
       If you want to include both endpoints, you can also use the
       usual Rust notation `a..=b`.  The size of the range must fit
       in an [`i128`].
     - `x != a`, where `x` is a private `Scalar`, possibly
       multiplied by a constant and adding or subtracting an
       expression evaluating to a public `Scalar`, and `a` is a
       constant or _public_ `Scalar` (or an arithmetic expression
       evaluating to a public `Scalar`).  For example, `2*x+2*c*c+12
       != a*b+17` is allowed, if `a`, `b`, and `c` are public
       `Scalar`s and `x` is a private `Scalar`.  `x != 0` is a more
       typical example.  This is a _not-equals statement_, and it
       means that the value of the expression on the left is not
       equal to the value of the expression on the right.
   - Statements can also be combined with `AND(st1,st2,...,stn)` and
     `OR(st1,st2,...,stn)`.  The list of statements in the macro
     invocation are implicitly put into a top-level `AND`.  `AND`s
     and `OR`s can be arbitrarily nested.  As usual, an `AND`
     statement is true when all of its component statements are
     true; an `OR` statement is true when at least one of its
     component statements is true.
   

The macro creates a submodule with the name specified by
`proto_name`.  This module contains:
  - A struct `Instance` containing all the `Point`s and _public_
    `Scalar`s specified in the macro invocation.  Any public vector
    `Scalar` or `Point` variable will be represented as a
    `Vec<Scalar>` or `Vec<Point>` respectively.
  - A struct `Witness` containing all the _private_ `Scalar`s
    specified in the macro invocation. Any private vector variable
    will be represented as a `Vec<Scalar>`.
  - A function `prove` with the signature
    ```
    pub fn prove(
        instance: &Instance,
        witness: &Witness,
        session_id: &[u8],
        rng: &mut (impl CryptoRng + RngCore),
    ) -> sigma_proofs::errors::Result<Vec<u8>>
    ```
    The parameter `instance` contains the public variables (also
    known to the verifier).  The parameter `witness` contains the
    private variables known only to the prover.  The parameter
    `session_id` can be any byte slice; the proof is bound to this
    byte slice, and the verifier must use the same byte slice in
    order to verify the proof.  The parameter `rng` is a random
    number generator that implements the [`CryptoRng`] and
    [`RngCore`] traits.  The output, if successful, is the proof as
    a byte vector.
  - A function `verify` with the signature
    ```
    pub fn verify(
        instance: &Instance,
        proof: &[u8],
        session_id: &[u8],
    ) -> sigma_proofs::errors::Result<()>
    ```
    The parameter `instance` contains the public variables, and must
    be the same as passed to the `prove` function.  The parameter
    `proof` contains the output of the `prove` function.  The
    parameter `session_id` must be the same as passed to the `prove`
    function.  If `verify` returns `Ok(())`, then the verifier can
    assume that the prover did know a `Witness` struct for which the
    statements (with public values specified by the given
    `Instance` struct) are all true, but the verifier does not learn
    any other information about that `Witness` struct.

[`PrimeGroup`]: https://docs.rs/group/0.13.0/group/prime/trait.PrimeGroup.html
[`CryptoRng`]: https://docs.rs/rand/0.8.5/rand/trait.CryptoRng.html
[`RngCore`]: https://docs.rs/rand/0.8.5/rand/trait.RngCore.html
[`i128`]: https://doc.rust-lang.org/1.78.0/std/primitive.i128.html