Struct LinearRelation

pub struct LinearRelation<G>
where
    G: Group + GroupEncoding,
{
    pub linear_map: LinearMap<G>,
    pub image: Vec<GroupVar<G>>,
}

A wrapper struct coupling a LinearMap with the corresponding expected output (image) elements.

This structure represents the preimage problem for a group linear map: given a set of scalar inputs, determine whether their image under the linear map matches a target set of group elements.

Internally, the constraint system is defined through:

• A list of group elements and linear equations (held in the LinearMap field),
• A list of GroupVar indices (image) that specify the expected output for each constraint.

Fields

linear_map: LinearMap<G>

The underlying linear map describing the structure of the statement.

image: Vec<GroupVar<G>>

Indices pointing to elements representing the “target” images for each constraint.

Implementations

impl<G> LinearRelation<G>

where G: Group + GroupEncoding,

pub fn new() -> Self

Create a new empty LinearRelation.

pub fn append_equation( &mut self, lhs: GroupVar<G>, rhs: impl Into<LinearCombination<G>>, )

Adds a new equation to the statement of the form: lhs = Σ weight_i * (scalar_i * point_i).

Parameters

• lhs: The image group element variable (left-hand side of the equation).
• rhs: An instance of LinearCombination representing the linear combination on the right-hand side.

pub fn allocate_eq( &mut self, rhs: impl Into<LinearCombination<G>>, ) -> GroupVar<G>

Adds a new equation to the statement of the form: lhs = Σ weight_i * (scalar_i * point_i) without allocating lhs.

Parameters

• rhs: An instance of LinearCombination representing the linear combination on the right-hand side.

pub fn allocate_scalar(&mut self) -> ScalarVar<G>

Allocates a scalar variable for use in the linear map.

pub fn allocate_scalars<const N: usize>(&mut self) -> [ScalarVar<G>; N]

Allocates space for N new scalar variables.

Returns

An array of ScalarVar representing the newly allocated scalar indices.

Example

use curve25519_dalek::RistrettoPoint as G;

let mut relation = LinearRelation::<G>::new();
let [var_x, var_y] = relation.allocate_scalars();
let vars = relation.allocate_scalars::<10>();

pub fn allocate_element(&mut self) -> GroupVar<G>

Allocates a point variable (group element) for use in the linear map.

pub fn allocate_elements<const N: usize>(&mut self) -> [GroupVar<G>; N]

Allocates N point variables (group elements) for use in the linear map.

Returns

An array of GroupVar representing the newly allocated group element indices.

Example

use curve25519_dalek::RistrettoPoint as G;

let mut relation = LinearRelation::<G>::new();
let [var_g, var_h] = relation.allocate_elements();
let vars = relation.allocate_elements::<10>();

pub fn set_element(&mut self, var: GroupVar<G>, element: G)

Assign a group element value to a point variable.

Parameters

• var: The variable to assign.
• element: The value to assign to the variable.

Panics

Panics if the given assignment conflicts with the existing assignment.

pub fn set_elements( &mut self, assignments: impl IntoIterator<Item = (GroupVar<G>, G)>, )

Assigns specific group elements to point variables (indices).

Parameters

• assignments: A collection of (GroupVar, GroupElement) pairs that can be iterated over.

Panics

Panics if the collection contains two conflicting assignments for the same variable.

pub fn compute_image( &mut self, scalars: &[<G as Group>::Scalar], ) -> Result<(), Error>

Evaluates all linear combinations in the linear map with the provided scalars, computing the left-hand side of this constraints (i.e. the image).

After calling this function, all point variables will be assigned.

Parameters

• scalars: A slice of scalar values corresponding to the scalar variables.

Returns

Return Ok on success, and an error if unassigned elements prevent the image from being computed. Modifies the group elements assigned in the LinearRelation.

pub fn image(&self) -> Result<Vec<G>, Error>

Returns the current group elements corresponding to the image variables.

Returns

A vector of group elements (Vec<G>) representing the linear map’s image.

pub fn label(&self) -> Vec<u8>

Returns a binary label describing the linear map.

The format is:

• [Ne: u32] number of equations
• For each equation:
  • [output_point_index: u32]
  • [Nt: u32] number of terms
  • Nt × [scalar_index: u32, point_index: u32] term entries

pub fn into_nizk( self, session_identifier: &[u8], ) -> NISigmaProtocol<SchnorrProof<G>, ShakeCodec<G>>

where G: GroupEncoding,

Convert this LinearRelation into a non-interactive zero-knowledge protocol using the ShakeCodec and a specified context/domain separator.

Parameters

• context: Domain separator bytes for the Fiat-Shamir transform

Returns

A NISigmaProtocol instance ready for proving and verification

Example

let mut relation = LinearRelation::<G>::new();
let x_var = relation.allocate_scalar();
let g_var = relation.allocate_element();
let p_var = relation.allocate_eq(x_var * g_var);

relation.set_element(g_var, G::generator());
let x = Scalar::random(&mut OsRng);
relation.compute_image(&[x]).unwrap();

// Convert to NIZK with custom context
let nizk = relation.into_nizk(b"my-protocol-v1");
let proof = nizk.prove_batchable(&vec![x], &mut OsRng).unwrap();
assert!(nizk.verify_batchable(&proof).is_ok());

Trait Implementations

impl<G> Clone for LinearRelation<G>

where G: Group + GroupEncoding + Clone,

fn clone(&self) -> LinearRelation<G>

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<G> Debug for LinearRelation<G>

where G: Group + GroupEncoding + Debug,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<G> Default for LinearRelation<G>

where G: Group + GroupEncoding + Default,

fn default() -> LinearRelation<G>

Returns the “default value” for a type.

impl<G> From<LinearRelation<G>> for Protocol<G>

where G: Group + GroupEncoding,

fn from(value: LinearRelation<G>) -> Self

Converts to this type from the input type.

impl<G> From<LinearRelation<G>> for SchnorrProof<G>

where G: Group + GroupEncoding,

fn from(value: LinearRelation<G>) -> Self

Converts to this type from the input type.