mina_tree/port_ocaml/
hash.rs

1//! Implementation of janestreet hash:
2//! <https://github.com/janestreet/base/blob/v0.14/hash_types/src/internalhash_stubs.c>
3
4use std::hash::Hasher;
5
6use ark_ff::{BigInteger, BigInteger256};
7use mina_curves::pasta::Fp;
8
9use crate::AccountId;
10
11#[derive(Debug)]
12pub(super) struct JaneStreetHasher {
13    h: u32,
14}
15
16#[allow(clippy::derivable_impls)]
17impl Default for JaneStreetHasher {
18    fn default() -> Self {
19        // the seed seems to be zero
20        // <https://github.com/janestreet/base/blob/v0.14/src/hash.ml#L165>
21        Self { h: 0 }
22    }
23}
24
25#[allow(clippy::precedence)]
26fn rotl32(x: u32, n: u32) -> u32 {
27    (x) << n | (x) >> (32 - n)
28}
29
30/// <https://github.com/janestreet/base/blob/v0.14/hash_types/src/internalhash_stubs.c#L52>
31fn mix(mut h: u32, mut d: u32) -> u32 {
32    d = d.wrapping_mul(0xcc9e2d51);
33    d = rotl32(d, 15);
34    d = d.wrapping_mul(0x1b873593);
35    h ^= d;
36    h = rotl32(h, 13);
37    h = h.wrapping_mul(5).wrapping_add(0xe6546b64);
38    h
39}
40
41/// <https://github.com/janestreet/base/blob/v0.14/hash_types/src/internalhash_stubs.c#L35>
42fn final_mix(mut h: u32) -> u32 {
43    h ^= h >> 16;
44    h = h.wrapping_mul(0x85ebca6b);
45    h ^= h >> 13;
46    h = h.wrapping_mul(0xc2b2ae35);
47    h ^= h >> 16;
48    h
49}
50
51impl Hasher for JaneStreetHasher {
52    /// <https://github.com/janestreet/base/blob/v0.14/hash_types/src/internalhash_stubs.c#L42C1-L47C2>
53    fn finish(&self) -> u64 {
54        let h = final_mix(self.h);
55        let h: u32 = h & 0x3FFF_FFFF; // 30 bits
56        h as u64
57    }
58
59    /// <https://github.com/janestreet/base/blob/v0.14/hash_types/src/internalhash_stubs.c#L60C1-L90C2>
60    fn write(&mut self, s: &[u8]) {
61        // Little endian implementation only
62        for (chunk, chunk_len) in s.chunks(4).map(|chunk| (chunk, chunk.len())) {
63            let w: u32 = if chunk_len == 4 {
64                u32::from_le_bytes(chunk.try_into().unwrap())
65            } else {
66                // Finish with up to 3 bytes
67                let mut w = [0u8; 4];
68                w[..chunk_len].copy_from_slice(chunk);
69                u32::from_le_bytes(w)
70            };
71            self.h = mix(self.h, w);
72        }
73
74        // Finally, mix in the length. Ignore the upper 32 bits, generally 0.
75        self.h ^= (s.len() & 0xFFFF_FFFF) as u32;
76    }
77
78    fn write_u32(&mut self, i: u32) {
79        self.h = mix(self.h, i);
80    }
81
82    /// This is used for `bool` in OCaml
83    fn write_i64(&mut self, d: i64) {
84        let n = (d >> 32) ^ (d >> 63) ^ d;
85        self.h = mix(self.h, n as u32);
86    }
87}
88
89/// <https://github.com/ocaml/Zarith/blob/6f840fb026ab6920104ea7b43140fdcc3e936914/caml_z.c#L3333-L3358>
90fn hash_field(f: &Fp) -> u32 {
91    let mut acc = 0;
92
93    let bigint: BigInteger256 = (*f).into();
94    let bigint = bigint.to_64x4();
95    let nignore: usize = bigint.iter().rev().take_while(|&b| *b == 0).count();
96
97    for bigint in bigint.iter().take(BigInteger256::NUM_LIMBS - nignore) {
98        acc = mix(acc, (bigint & 0xFFFF_FFFF) as u32);
99        acc = mix(acc, (bigint >> 32) as u32);
100    }
101
102    if bigint.last().unwrap() & 0x8000_0000_0000_0000 != 0 {
103        // TODO: Not sure if that condition is correct
104        acc += 1;
105    }
106
107    acc
108}
109
110pub fn account_id_ocaml_hash(account_id: &AccountId) -> u32 {
111    let mut hasher = JaneStreetHasher::default();
112    hasher.write_u32(hash_field(&account_id.public_key.x));
113    hasher.write_u32(account_id.public_key.is_odd as u32);
114    hasher.write_u32(hash_field(&account_id.token_id.0));
115    hasher.finish() as u32
116}
117
118pub trait OCamlHash {
119    fn ocaml_hash(&self) -> u32;
120}
121
122impl OCamlHash for AccountId {
123    fn ocaml_hash(&self) -> u32 {
124        account_id_ocaml_hash(self)
125    }
126}
127
128#[cfg(test)]
129mod tests {
130    use std::str::FromStr;
131
132    use mina_signer::CompressedPubKey;
133
134    use super::*;
135
136    #[test]
137    fn test_hash_fp() {
138        const TOKEN_ID: &str =
139            "4967745125912355413023996042397960619663294160624364664207862415774117920201";
140        const PK: &str =
141            "9706454913247140231138457869942480497494390376582974522927223806983428482248";
142
143        let fp = Fp::from_str(TOKEN_ID).unwrap();
144        let acc = hash_field(&fp);
145        dbg!(acc as i32);
146        assert_eq!(acc, (-1384641025i32) as u32);
147
148        let fp = Fp::from_str(PK).unwrap();
149        let acc = hash_field(&fp);
150        dbg!(acc as i32);
151        assert_eq!(acc, (-2044176935i32) as u32);
152
153        let fp = Fp::from_str(TOKEN_ID).unwrap();
154        let mut hasher = JaneStreetHasher { h: 1178103103 };
155        hasher.write_u32(hash_field(&fp));
156        assert_eq!(hasher.h, 327258694);
157
158        let fp = Fp::from_str(TOKEN_ID).unwrap();
159        let hash = {
160            let mut hasher = JaneStreetHasher::default();
161            hasher.write_u32(hash_field(&fp));
162            hasher.finish()
163        };
164        assert_eq!(hash, 712332047);
165
166        let pk = CompressedPubKey {
167            x: Fp::from_str(PK).unwrap(),
168            is_odd: true,
169        };
170        let hash = {
171            let mut hasher = JaneStreetHasher::default();
172            hasher.write_u32(hash_field(&pk.x));
173            hasher.write_u32(pk.is_odd as u32);
174            hasher.finish()
175        };
176        assert_eq!(hash, 284693557);
177
178        let account_id = AccountId {
179            public_key: pk,
180            token_id: crate::TokenId(Fp::from_str(TOKEN_ID).unwrap()),
181        };
182        let hash = {
183            let mut hasher = JaneStreetHasher::default();
184            hasher.write_u32(hash_field(&account_id.public_key.x));
185            hasher.write_u32(account_id.public_key.is_odd as u32);
186            hasher.write_u32(hash_field(&account_id.token_id.0));
187            hasher.finish()
188        };
189        assert_eq!(hash, 386994658);
190    }
191}
mina_tree/port_ocaml/hash.rs

mina_tree/port_ocaml/
hash.rs
