mina_tree/staged_ledger/
hash.rs

1use ark_ff::{PrimeField, ToBytes};
2use mina_curves::pasta::Fp;
3use poseidon::hash::Inputs;
4use sha2::{Digest, Sha256};
5
6use crate::{
7    proofs::field::FieldWitness, scan_state::pending_coinbase::PendingCoinbase,
8    AppendToInputs as _, ToInputs,
9};
10
11/// Convert to/from OCaml strings, such as
12/// "u~\218kzX\228$\027qG\239\135\255:\143\171\186\011\200P\243\163\135\223T>\017\172\254\1906"
13pub trait OCamlString {
14    fn to_ocaml_str(&self) -> String;
15    fn from_ocaml_str(s: &str) -> Self;
16}
17
18impl<const N: usize> OCamlString for [u8; N] {
19    fn to_ocaml_str(&self) -> String {
20        to_ocaml_str(self)
21    }
22
23    fn from_ocaml_str(s: &str) -> Self {
24        from_ocaml_str(s)
25    }
26}
27
28pub fn to_ocaml_str(bytes: &[u8]) -> String {
29    let mut s = String::with_capacity(256);
30
31    for b in bytes {
32        let c = char::from(*b);
33        if c == '\\' {
34            s.push_str("\\\\");
35        } else if c.is_ascii() && !c.is_ascii_control() {
36            s.push(c);
37        } else {
38            match b {
39                7 => s.push_str(r"\a"),
40                8 => s.push_str(r"\b"),
41                9 => s.push_str(r"\t"),
42                10 => s.push_str(r"\n"),
43                // 11 => s.push_str(r"\v"),
44                12 => s.push_str(r"\f"),
45                13 => s.push_str(r"\r"),
46                _ => s.push_str(&format!("\\{:<03}", b)),
47            }
48        }
49    }
50
51    s
52}
53
54pub fn from_ocaml_str<const N: usize>(s: &str) -> [u8; N] {
55    let mut bytes = [0; N];
56    let mut b_index = 0;
57
58    let mut index = 0;
59    let s = s.as_bytes();
60    while index < s.len() {
61        if s[index] == b'\\' {
62            if s.get(index + 1).map(|next| *next == b'\\').unwrap_or(false) {
63                bytes[b_index] = b'\\';
64                index += 2;
65            } else if s
66                .get(index + 1)
67                .map(|next| "abtnfr".contains(char::from(*next)))
68                // .map(|next| "abtnvfr".contains(char::from(*next)))
69                .unwrap_or(false)
70            {
71                bytes[b_index] = match s[index + 1] {
72                    b'a' => 7,
73                    b'b' => 8,
74                    b't' => 9,
75                    b'n' => 10,
76                    // b'v' => 11,
77                    b'f' => 12,
78                    b'r' => 13,
79                    _ => unreachable!(),
80                };
81                index += 2;
82            } else {
83                let n1 = s[index + 1] - b'0';
84                let n2 = s[index + 2] - b'0';
85                let n3 = s[index + 3] - b'0';
86                bytes[b_index] = (n1 * 100) + (n2 * 10) + n3;
87                index += 4;
88            }
89        } else {
90            bytes[b_index] = s[index];
91            index += 1;
92        }
93
94        b_index += 1;
95    }
96
97    bytes
98}
99
100/// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L27>
101#[derive(Clone, PartialEq, Eq)]
102pub struct AuxHash(pub [u8; 32]);
103
104impl std::fmt::Debug for AuxHash {
105    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
106        f.write_fmt(format_args!("AuxHash({})", self.to_ocaml_str()))
107    }
108}
109
110impl AuxHash {
111    fn to_ocaml_str(&self) -> String {
112        to_ocaml_str(&self.0)
113    }
114
115    fn from_ocaml_str(s: &str) -> Self {
116        Self(from_ocaml_str(s))
117    }
118}
119
120/// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L110>
121#[derive(Clone, PartialEq, Eq)]
122pub struct PendingCoinbaseAux(pub [u8; 32]);
123
124impl std::fmt::Debug for PendingCoinbaseAux {
125    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
126        f.write_fmt(format_args!("PendingCoinbaseAux({})", self.to_ocaml_str()))
127    }
128}
129
130impl PendingCoinbaseAux {
131    fn to_ocaml_str(&self) -> String {
132        to_ocaml_str(&self.0)
133    }
134
135    fn from_ocaml_str(s: &str) -> Self {
136        Self(from_ocaml_str(s))
137    }
138}
139
140/// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L152>
141#[derive(Clone, Debug, PartialEq, Eq)]
142pub struct NonStark {
143    pub ledger_hash: Fp,
144    pub aux_hash: AuxHash,
145    pub pending_coinbase_aux: PendingCoinbaseAux,
146}
147
148impl NonStark {
149    /// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L182>
150    pub fn digest(&self) -> [u8; 32] {
151        let Self {
152            ledger_hash,
153            aux_hash,
154            pending_coinbase_aux,
155        } = self;
156
157        let mut sha: Sha256 = Sha256::new();
158
159        let mut ledger_hash_bytes: [u8; 32] = <[u8; 32]>::default();
160
161        let ledger_hash = ledger_hash.into_repr();
162        ledger_hash.write(ledger_hash_bytes.as_mut_slice()).unwrap();
163        ledger_hash_bytes.reverse();
164
165        sha.update(ledger_hash_bytes.as_slice());
166        sha.update(aux_hash.0.as_slice());
167        sha.update(pending_coinbase_aux.0.as_slice());
168
169        sha.finalize().into()
170    }
171}
172
173impl ToInputs for NonStark {
174    /// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L193>
175    fn to_inputs(&self, inputs: &mut Inputs) {
176        let digest = self.digest();
177        inputs.append_bytes(digest.as_slice());
178    }
179}
180
181/// Staged ledger hash has two parts
182///
183/// 1) merkle root of the pending coinbases
184/// 2) ledger hash, aux hash, and the FIFO order of the coinbase stacks(Non snark).
185///
186/// Only part 1 is required for blockchain snark computation and therefore the
187/// remaining fields of the staged ledger are grouped together as "Non_snark"
188///
189/// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L259>
190#[derive(Clone, Debug, PartialEq, Eq)]
191pub struct StagedLedgerHash<F: FieldWitness> {
192    pub non_snark: NonStark,
193    pub pending_coinbase_hash: F,
194}
195
196impl StagedLedgerHash<Fp> {
197    /// <https://github.com/MinaProtocol/mina/blob/3fe924c80a4d01f418b69f27398f5f93eb652514/src/lib/mina_base/staged_ledger_hash.ml#L290>
198    pub fn of_aux_ledger_and_coinbase_hash(
199        aux_hash: AuxHash,
200        ledger_hash: Fp,
201        pending_coinbase: &mut PendingCoinbase,
202    ) -> Self {
203        Self {
204            non_snark: NonStark {
205                ledger_hash,
206                aux_hash,
207                pending_coinbase_aux: pending_coinbase.hash_extra(),
208            },
209            pending_coinbase_hash: pending_coinbase.merkle_root(),
210        }
211    }
212
213    /// Used for tests only
214    #[cfg(test)]
215    pub fn from_ocaml_strings(
216        ledger_hash: &str,
217        aux_hash: &str,
218        pending_coinbase_aux: &str,
219        pending_coinbase_hash: &str,
220    ) -> Self {
221        use std::str::FromStr;
222
223        Self {
224            non_snark: NonStark {
225                ledger_hash: Fp::from_str(ledger_hash).unwrap(),
226                aux_hash: AuxHash::from_ocaml_str(aux_hash),
227                pending_coinbase_aux: PendingCoinbaseAux::from_ocaml_str(pending_coinbase_aux),
228            },
229            pending_coinbase_hash: Fp::from_str(pending_coinbase_hash).unwrap(),
230        }
231    }
232}
233
234impl ToInputs for StagedLedgerHash<Fp> {
235    fn to_inputs(&self, inputs: &mut Inputs) {
236        let Self {
237            non_snark,
238            pending_coinbase_hash,
239        } = self;
240
241        inputs.append(non_snark);
242        inputs.append(pending_coinbase_hash);
243    }
244}
245
246#[cfg(test)]
247mod tests {
248    use std::str::FromStr;
249
250    #[cfg(target_family = "wasm")]
251    use wasm_bindgen_test::wasm_bindgen_test as test;
252
253    use super::*;
254
255    #[test]
256    fn test_convert() {
257        // stage_ledger_hash=StagedLedgerHash {
258        //     non_snark: NonStark {
259        //         ledger_hash: Fp(7213023165825031994332898585791275635753820608093286100176380057570051468967),
260        //         aux_hash: AuxHash(\\\249\245k\176]TJ\216\183\001\204\177\131\030\244o\178\188\191US\156\192Hi\194P\223\004\000\003),
261        //         pending_coinbase_aux: PendingCoinbaseAux(\\\236\235f\255\200o8\217Rxlmily\194\219\1949\221N\145\180g)\215:'\251W\233),
262        //     },
263        //     pending_coinbase_hash: Fp(25504365445533103805898245102289650498571312278321176071043666991586378788150),
264        // }
265
266        let s = r"\\\236\235f\255\200o8\217Rxlmily\194\219\1949\221N\145\180g)\215:'\251W\233";
267        let pending_coinbase_aux = PendingCoinbaseAux::from_ocaml_str(s);
268        assert_eq!(s, pending_coinbase_aux.to_ocaml_str());
269
270        let s = r"\\\249\245k\176]TJ\216\183\001\204\177\131\030\244o\178\188\191US\156\192Hi\194P\223\004\000\003";
271        let aux_hash = AuxHash::from_ocaml_str(s);
272        assert_eq!(s, aux_hash.to_ocaml_str());
273
274        // non_snark digest="\t\204S\160F\227\022\142\146\172\220.R'\222L&b\191\138;\022\235\137\190>\205.\031\195-\231"
275        // digest=9,204,83,160,70,227,22,142,146,172,220,46,82,39,222,76,38,98,191,138,59,22,235,137,190,62,205,46,31,195,45,231
276
277        let a = AuxHash([
278            9, 204, 83, 160, 70, 227, 22, 142, 146, 172, 220, 46, 82, 39, 222, 76, 38, 98, 191,
279            138, 59, 22, 235, 137, 190, 62, 205, 46, 31, 195, 45, 231,
280        ]);
281
282        println!("a={}", a.to_ocaml_str());
283
284        let s = r"\t\204S\160F\227\022\142\146\172\220.R'\222L&b\191\138;\022\235\137\190>\205.\031\195-\231";
285        assert_eq!(s, a.to_ocaml_str());
286        let aux_hash = AuxHash::from_ocaml_str(s);
287        assert_eq!(s, aux_hash.to_ocaml_str());
288
289        let s = r"\000 \014WQ\192&\229C\178\232\171.\176`\153\218\161\209\229\223Gw\143w\135\250\171E\205\241/\227\168";
290        let memo = <[u8; 34]>::from_ocaml_str(s);
291        assert_eq!(s, memo.to_ocaml_str());
292
293        // let bytes = [10,220,211,153,14,65,191,6,19,231,47,244,155,5,212,131,48,124,227,133,176,79,196,131,23,116,152,178,130,63,206,85];
294
295        // let s = bytes.to_ocaml_str();
296        // println!("s='{}'", s);
297
298        let s = r"\n\220\211\153\014A\191\006\019\231/\244\155\005\212\1310|\227\133\176O\196\131\023t\152\178\130?\206U";
299        let pending_coinbase_aux = PendingCoinbaseAux::from_ocaml_str(s);
300        assert_eq!(s, pending_coinbase_aux.to_ocaml_str());
301    }
302
303    #[test]
304    fn test_non_snark_digest() {
305        // ((non_snark
306        //   ((ledger_hash
307        //     7213023165825031994332898585791275635753820608093286100176380057570051468967)
308        //    (aux_hash
309        //     "T\249\245k\176]TJ\216\183\001\204\177\131\030\244o\178\188\191US\156\192Hi\194P\223\004\000\003")
310        //    (pending_coinbase_aux
311        //     "_\236\235f\255\200o8\217Rxlmily\194\219\1949\221N\145\180g)\215:'\251W\233")))
312
313        let non_snark = NonStark {
314            ledger_hash: Fp::from_str(
315                "7213023165825031994332898585791275635753820608093286100176380057570051468967",
316            )
317            .unwrap(),
318            aux_hash: AuxHash::from_ocaml_str(
319                r"T\249\245k\176]TJ\216\183\001\204\177\131\030\244o\178\188\191US\156\192Hi\194P\223\004\000\003",
320            ),
321            pending_coinbase_aux: PendingCoinbaseAux::from_ocaml_str(
322                r"_\236\235f\255\200o8\217Rxlmily\194\219\1949\221N\145\180g)\215:'\251W\233",
323            ),
324        };
325
326        assert_eq!(
327            non_snark.digest().to_ocaml_str(),
328            r"\t\204S\160F\227\022\142\146\172\220.R'\222L&b\191\138;\022\235\137\190>\205.\031\195-\231"
329        );
330
331        // non_snark=((ledger_hash
332        //   18582860218764414485081234471609377222894570081548691702645303871998665679024)
333        //  (aux_hash
334        //   "0\136Wg\182DbX\203kLi\212%\199\206\142#\213`L\160bpCB\1413\240\193\171K")
335        //  (pending_coinbase_aux
336        //    "\
337        //   \n\220\211\153\014A\191\006\019\231/\244\155\005\212\1310|\227\133\176O\196\131\023t\152\178\130?\206U"))
338
339        let non_snark = NonStark {
340            ledger_hash: Fp::from_str(
341                "18582860218764414485081234471609377222894570081548691702645303871998665679024",
342            )
343            .unwrap(),
344            aux_hash: AuxHash::from_ocaml_str(
345                r"0\136Wg\182DbX\203kLi\212%\199\206\142#\213`L\160bpCB\1413\240\193\171K",
346            ),
347            pending_coinbase_aux: PendingCoinbaseAux::from_ocaml_str(
348                r"\n\220\211\153\014A\191\006\019\231/\244\155\005\212\1310|\227\133\176O\196\131\023t\152\178\130?\206U",
349            ),
350        };
351
352        assert_eq!(
353            non_snark.digest().to_ocaml_str(),
354            r"u~\218kzX\228$\027qG\239\135\255:\143\171\186\011\200P\243\163\135\223T>\017\172\254\1906",
355        );
356    }
357}
mina_tree/staged_ledger/hash.rs

mina_tree/staged_ledger/
hash.rs
