rescue_poseidon 0.32.11

Sponge construction based Algebraic Hash Functions
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

use franklin_crypto::bellman::{Engine, SynthesisError};
use franklin_crypto::plonk::circuit::linear_combination::LinearCombination;
// Computes matrix vector product and assigns result into same vector.
pub(crate) fn matrix_vector_product<E: Engine, const DIM: usize>(matrix: &[[E::Fr; DIM]; DIM], vector: &mut [LinearCombination<E>; DIM]) -> Result<(), SynthesisError> {
    let vec_cloned = vector.clone();

    for (idx, row) in matrix.iter().enumerate() {
        // [fr, fr, fr] * [lc, lc, lc]
        vector[idx] = LinearCombination::zero();
        for (factor, lc) in row.iter().zip(&vec_cloned) {
            vector[idx].add_assign_scaled(lc, *factor)
        }
    }

    Ok(())
}

// Computes sparse matrix - vector by exploiting sparsity of optimized matrixes.
pub(crate) fn mul_by_sparse_matrix<E: Engine, const DIM: usize>(matrix: &[[E::Fr; DIM]; DIM], vector: &mut [LinearCombination<E>; DIM]) {
    assert_eq!(DIM, 3, "valid only for 3x3 matrix");

    let vec_cloned = vector.clone();

    // we will assign result into input vector so set each to zero
    for lc in vector.iter_mut() {
        *lc = LinearCombination::zero();
    }

    for (a, b) in vec_cloned.iter().zip(matrix[0].iter()) {
        vector[0].add_assign_scaled(a, *b);
    }

    vector[1].add_assign_scaled(&vec_cloned[0], matrix[1][0]);
    vector[1].add_assign(&vec_cloned[1]);

    vector[2].add_assign_scaled(&vec_cloned[0], matrix[2][0]);
    vector[2].add_assign(&vec_cloned[2]);
}

#[cfg(test)]
mod test {
    use crate::rand::Rand;
    use crate::tests::{init_cs, init_rng};
    use franklin_crypto::bellman::Field;
    use franklin_crypto::{
        bellman::pairing::bn256::{Bn256, Fr},
        plonk::circuit::{allocated_num::AllocatedNum, linear_combination::LinearCombination},
    };
    use std::convert::TryInto;

    #[test]
    fn test_matrix_product() {
        let cs = &mut init_cs::<Bn256>();
        let rng = &mut init_rng();

        const DIM: usize = 3;

        let mut vector_fe: [Fr; DIM] = [Fr::rand(rng); DIM];

        let mut vector_lc: [LinearCombination<_>; DIM] = (0..DIM).map(|_| LinearCombination::zero()).collect::<Vec<LinearCombination<_>>>().try_into().expect("vector of lc");
        vector_fe
            .iter()
            .zip(vector_lc.iter_mut())
            .for_each(|(src, dst)| *dst = LinearCombination::from(AllocatedNum::alloc(cs, || Ok(*src)).unwrap()));

        let mut matrix = [[Fr::zero(); DIM]; DIM];
        (0..9)
            .map(|_| Fr::rand(rng))
            .collect::<Vec<Fr>>()
            .chunks_exact(3)
            .zip(matrix.iter_mut())
            .for_each(|(src, dst)| *dst = src.try_into().expect("static vector"));

        matrix[1][1] = Fr::one();
        matrix[1][2] = Fr::zero();
        matrix[2][1] = Fr::zero();
        matrix[2][2] = Fr::one();

        crate::common::matrix::mmul_assign::<Bn256, DIM>(&matrix, &mut vector_fe);
        super::mul_by_sparse_matrix(&matrix, &mut vector_lc);

        vector_fe.iter().zip(vector_lc.iter()).for_each(|(fe, lc)| {
            let actual = lc.clone().into_num(cs).unwrap().get_value().unwrap();
            assert_eq!(*fe, actual);
        });
    }
}