mina_tree/proofs/
transition_chain.rs

1use mina_curves::pasta::Fp;
2
3use crate::scan_state::protocol_state::hashes_abstract;
4
5/// <https://github.com/MinaProtocol/mina/blob/aebd4e552b8b4bcd78d1e24523169e8778794857/src/lib/merkle_list_verifier/merkle_list_verifier.ml#L36>
6fn verify_impl<'a, T>(
7    init_state_hash: Fp,
8    target_hash: Fp,
9    merkle_list_len: usize,
10    merkle_list_iter: T,
11) -> Option<Vec<Fp>>
12where
13    T: Iterator<Item = &'a Fp>,
14{
15    let mut hashes = Vec::with_capacity(merkle_list_len + 1);
16    hashes.push(init_state_hash);
17
18    for proof_elem in merkle_list_iter {
19        let last = hashes.last().unwrap();
20        hashes.push(hashes_abstract(*last, *proof_elem));
21    }
22
23    if hashes.last().unwrap() == &target_hash {
24        hashes.reverse();
25        Some(hashes)
26    } else {
27        None
28    }
29}
30
31pub fn verify(target_hash: Fp, transition_chain_proof: (Fp, Vec<Fp>)) -> Option<Vec<Fp>> {
32    let init_state_hash = transition_chain_proof.0;
33    let merkle_list = transition_chain_proof.1;
34
35    verify_impl(
36        init_state_hash,
37        target_hash,
38        merkle_list.len(),
39        merkle_list.iter(),
40    )
41}
42
43pub fn verify_right(target_hash: Fp, transition_chain_proof: (Fp, Vec<Fp>)) -> Option<Vec<Fp>> {
44    let init_state_hash = transition_chain_proof.0;
45    let merkle_list = transition_chain_proof.1;
46
47    verify_impl(
48        init_state_hash,
49        target_hash,
50        merkle_list.len(),
51        merkle_list.iter().rev(),
52    )
53}
54
55#[cfg(test)]
56mod tests {
57    use std::str::FromStr;
58
59    use crate::util::FpExt;
60
61    use super::*;
62
63    #[cfg(target_family = "wasm")]
64    use wasm_bindgen_test::wasm_bindgen_test as test;
65
66    #[test]
67    fn test_verify_empty_list() {
68        let f = |s| Fp::from_str(s).unwrap();
69
70        let target_hash =
71            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
72        let init_state =
73            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
74        let merkle_list = vec![];
75        let transition_chain_proof = (init_state, merkle_list);
76
77        let result = verify(target_hash, transition_chain_proof);
78
79        let fields = result.unwrap();
80        let fields_str = fields.iter().map(|f| f.to_decimal()).collect::<Vec<_>>();
81
82        const OCAML_RESULT: &[&str] =
83            &["13961539055339866639536775340930523333525643277685972296197275513682073214917"];
84
85        assert_eq!(fields_str, OCAML_RESULT);
86    }
87
88    #[test]
89    fn test_verify_fail() {
90        let f = |s| Fp::from_str(s).unwrap();
91
92        let target_hash =
93            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
94        let init_state =
95            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
96        let merkle_list = vec![
97            f("13961539055339866639536775340930523333525643277685972296197275513682073214918"),
98            f("13961539055339866639536775340930523333525643277685972296197275513682073214919"),
99            f("13961539055339866639536775340930523333525643277685972296197275513682073214920"),
100        ];
101        let transition_chain_proof = (init_state, merkle_list);
102
103        let result = verify(target_hash, transition_chain_proof);
104        assert!(result.is_none());
105    }
106
107    #[test]
108    fn test_verify_pass() {
109        let f = |s| Fp::from_str(s).unwrap();
110
111        let target_hash =
112            f("800582919435166641451934253876519891456057321474706167207963223632227256531");
113        let init_state =
114            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
115        let merkle_list = vec![
116            f("13961539055339866639536775340930523333525643277685972296197275513682073214918"),
117            f("13961539055339866639536775340930523333525643277685972296197275513682073214919"),
118            f("13961539055339866639536775340930523333525643277685972296197275513682073214920"),
119        ];
120        let transition_chain_proof = (init_state, merkle_list);
121
122        let result = verify(target_hash, transition_chain_proof);
123
124        let fields = result.unwrap();
125        let fields_str = fields.iter().map(|f| f.to_decimal()).collect::<Vec<_>>();
126
127        const OCAML_RESULT: &[&str] = &[
128            "800582919435166641451934253876519891456057321474706167207963223632227256531",
129            "10598046929389065722730858200397844581724575694137702641700814979483247066836",
130            "16081440258805529661738981264264797691385178952734852216885856078447011038998",
131            "13961539055339866639536775340930523333525643277685972296197275513682073214917",
132        ];
133
134        assert_eq!(fields_str, OCAML_RESULT);
135    }
136
137    #[test]
138    fn test_verify_right_empty_list() {
139        let f = |s| Fp::from_str(s).unwrap();
140
141        let target_hash =
142            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
143        let init_state =
144            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
145        let merkle_list = vec![];
146        let transition_chain_proof = (init_state, merkle_list);
147
148        let result = verify_right(target_hash, transition_chain_proof);
149
150        let fields = result.unwrap();
151        let fields_str = fields.iter().map(|f| f.to_decimal()).collect::<Vec<_>>();
152
153        const OCAML_RESULT: &[&str] =
154            &["13961539055339866639536775340930523333525643277685972296197275513682073214917"];
155
156        assert_eq!(fields_str, OCAML_RESULT);
157    }
158
159    #[test]
160    fn test_verify_right_fail() {
161        let f = |s| Fp::from_str(s).unwrap();
162
163        let target_hash =
164            f("800582919435166641451934253876519891456057321474706167207963223632227256531");
165        let init_state =
166            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
167        let merkle_list = vec![
168            f("13961539055339866639536775340930523333525643277685972296197275513682073214918"),
169            f("13961539055339866639536775340930523333525643277685972296197275513682073214919"),
170            f("13961539055339866639536775340930523333525643277685972296197275513682073214920"),
171        ];
172        let transition_chain_proof = (init_state, merkle_list);
173
174        let result = verify_right(target_hash, transition_chain_proof);
175        assert!(result.is_none());
176    }
177
178    #[test]
179    fn test_verify_right_pass() {
180        let f = |s| Fp::from_str(s).unwrap();
181
182        let target_hash =
183            f("20637333162962631765110035680315905889290315150614944427035244260128010405493");
184        let init_state =
185            f("13961539055339866639536775340930523333525643277685972296197275513682073214917");
186        let merkle_list = vec![
187            f("13961539055339866639536775340930523333525643277685972296197275513682073214918"),
188            f("13961539055339866639536775340930523333525643277685972296197275513682073214919"),
189            f("13961539055339866639536775340930523333525643277685972296197275513682073214920"),
190        ];
191        let transition_chain_proof = (init_state, merkle_list);
192
193        let result = verify_right(target_hash, transition_chain_proof);
194
195        let fields = result.unwrap();
196        let fields_str = fields.iter().map(|f| f.to_decimal()).collect::<Vec<_>>();
197
198        const OCAML_RESULT: &[&str] = &[
199            "20637333162962631765110035680315905889290315150614944427035244260128010405493",
200            "8316842580468002558804570525036141813716506343242763169790486373222346781790",
201            "15085839017587781134699581518615528888092289271567746845604070331351347632343",
202            "13961539055339866639536775340930523333525643277685972296197275513682073214917",
203        ];
204
205        assert_eq!(fields_str, OCAML_RESULT);
206    }
207}
mina_tree/proofs/transition_chain.rs

mina_tree/proofs/
transition_chain.rs
