mithril-stm 0.10.5

A Rust implementation of Mithril Stake-based Threshold Multisignatures (STMs).
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

use anyhow::anyhow;
use ff::{Field, PrimeField};
use midnight_circuits::instructions::{
    ArithInstructions, AssertionInstructions, AssignmentInstructions, DecompositionInstructions,
};
use midnight_circuits::types::AssignedNative;
use midnight_proofs::circuit::Layouter;
use midnight_proofs::plonk::Error;
use midnight_zk_stdlib::ZkStdLib;
use num_bigint::BigUint;
use num_traits::{Num, One};

use crate::StmResult;
use crate::circuits::halo2::errors::StmCircuitError;
use crate::circuits::halo2::errors::to_synthesis_error;
use crate::circuits::halo2::types::CircuitBase;

/// Splits a field element into `(lower, upper)` limbs at `num_bits` using LE encoding.
pub(super) fn split_field_element_into_le_limbs<Fp: PrimeField>(
    value: &Fp,
    num_bits: u32,
) -> StmResult<(Fp, Fp)> {
    let field_bits = Fp::NUM_BITS;
    if num_bits >= field_bits {
        return Err(anyhow!(StmCircuitError::InvalidBitDecompositionRange {
            num_bits,
            field_bits,
        }));
    }

    let value_big = BigUint::from_bytes_le(value.to_repr().as_ref());
    let lower_mask = (BigUint::one() << num_bits) - BigUint::one();
    let lower_big = value_big.clone() & &lower_mask;
    let upper_big = value_big >> num_bits;
    let lower = big_unsigned_integer_to_field_element::<Fp>(lower_big)?;
    let upper = big_unsigned_integer_to_field_element::<Fp>(upper_big)?;
    Ok((lower, upper))
}

/// Parses the prime-field modulus into a `BigUint` for limb splitting and reduction helpers.
fn field_modulus_as_biguint<Fp: PrimeField>() -> StmResult<BigUint> {
    BigUint::from_str_radix(&Fp::MODULUS[2..], 16)
        .map_err(|_| anyhow!(StmCircuitError::FieldModulusParseFailed))
}

/// Reduces a non-negative integer modulo the field modulus and converts it into a field element.
fn big_unsigned_integer_to_field_element<Fp: PrimeField>(e: BigUint) -> StmResult<Fp> {
    let modulus = field_modulus_as_biguint::<Fp>()?;
    let e = e % modulus;
    Fp::from_str_vartime(&e.to_str_radix(10)[..])
        .ok_or_else(|| anyhow!(StmCircuitError::FieldElementConversionFailed))
}

/// Constrains two assigned field elements to share the same least-significant-bit parity.
pub(super) fn assert_equal_parity(
    std_lib: &ZkStdLib,
    layouter: &mut impl Layouter<CircuitBase>,
    x: &AssignedNative<CircuitBase>,
    y: &AssignedNative<CircuitBase>,
) -> Result<(), Error> {
    let sgn0 = std_lib.sgn0(layouter, x)?;
    let sgn1 = std_lib.sgn0(layouter, y)?;
    std_lib.assert_equal(layouter, &sgn0, &sgn1)
}

/// Decomposes a 255-bit assigned value into `(low_127_bits, high_128_bits)` and constrains
/// the reconstruction to match the original witness.
pub(super) fn decompose_unsafe(
    std_lib: &ZkStdLib,
    layouter: &mut impl Layouter<CircuitBase>,
    x: &AssignedNative<CircuitBase>,
) -> Result<(AssignedNative<CircuitBase>, AssignedNative<CircuitBase>), Error> {
    let x_value = x.value();
    let base127 = CircuitBase::from_u128(1_u128 << 127);
    let (x_low, x_high) = x_value
        .map_with_result(|v| split_field_element_into_le_limbs(v, 127))
        .map_err(to_synthesis_error)?
        .unzip();

    let x_low_assigned: AssignedNative<_> = std_lib.assign(layouter, x_low)?;
    let x_high_assigned: AssignedNative<_> = std_lib.assign(layouter, x_high)?;

    let x_combined: AssignedNative<_> = std_lib.linear_combination(
        layouter,
        &[
            (CircuitBase::ONE, x_low_assigned.clone()),
            (base127, x_high_assigned.clone()),
        ],
        CircuitBase::ZERO,
    )?;
    std_lib.assert_equal(layouter, x, &x_combined)?;

    assert_equal_parity(std_lib, layouter, x, &x_low_assigned)?;

    Ok((x_low_assigned, x_high_assigned))
}