zebra_chain/orchard/sinsemilla.rs
1//! Sinsemilla hash functions and helpers.
2
3use bitvec::prelude::*;
4use halo2::{
5 arithmetic::{Coordinates, CurveAffine, CurveExt},
6 pasta::pallas,
7};
8use sinsemilla::HashDomain;
9
10/// [Coordinate Extractor for Pallas][concreteextractorpallas]
11///
12/// ExtractP: P → P𝑥 such that ExtractP(𝑃) = 𝑥(𝑃) mod 𝑞P.
13///
14/// ExtractP returns the type P𝑥 which is precise for its range, unlike
15/// ExtractJ(𝑟) which returns a bit sequence.
16///
17/// [concreteextractorpallas]: https://zips.z.cash/protocol/nu5.pdf#concreteextractorpallas
18pub fn extract_p(point: pallas::Point) -> pallas::Base {
19 let option: Option<Coordinates<pallas::Affine>> =
20 pallas::Affine::from(point).coordinates().into();
21
22 match option {
23 // If Some, it's not the identity.
24 Some(coordinates) => *coordinates.x(),
25 _ => pallas::Base::zero(),
26 }
27}
28
29/// GroupHash into Pallas, aka _GroupHash^P_
30///
31/// Produces a random point in the Pallas curve. The first input element acts
32/// as a domain separator to distinguish uses of the group hash for different
33/// purposes; the second input element is the message.
34///
35/// <https://zips.z.cash/protocol/nu5.pdf#concretegrouphashpallasandvesta>
36#[allow(non_snake_case)]
37pub fn pallas_group_hash(D: &[u8], M: &[u8]) -> pallas::Point {
38 let domain_separator = std::str::from_utf8(D).unwrap();
39
40 pallas::Point::hash_to_curve(domain_separator)(M)
41}
42
43/// Sinsemilla Hash Function
44///
45/// "SinsemillaHash is an algebraic hash function with collision resistance (for
46/// fixed input length) derived from assumed hardness of the Discrete Logarithm
47/// Problem. It is designed by Sean Bowe and Daira Hopwood. The motivation for
48/// introducing a new discrete-log-based hash function (rather than using
49/// PedersenHash) is to make efficient use of the lookups available in recent
50/// proof systems including Halo 2."
51///
52/// SinsemillaHash: B^Y^\[N\] × B[{0 .. 𝑘·𝑐}] → P_𝑥 ∪ {⊥}
53///
54/// <https://zips.z.cash/protocol/nu5.pdf#concretesinsemillahash>
55#[allow(non_snake_case)]
56pub fn sinsemilla_hash(D: &[u8], M: &BitVec<u8, Lsb0>) -> Option<pallas::Base> {
57 let domain = std::str::from_utf8(D).expect("must be valid UTF-8");
58 let hash_domain = HashDomain::new(domain);
59
60 hash_domain.hash(M.iter().map(|b| *b.as_ref())).into()
61}
62
63#[cfg(test)]
64mod tests {
65
66 use super::*;
67 use crate::orchard::tests::vectors;
68
69 // Checks Sinsemilla hashes to point and to bytes (aka the x-coordinate
70 // bytes of a point) with:
71 // - One of two domains.
72 // - Random message lengths between 0 and 255 bytes.
73 // - Random message bits.
74 #[test]
75 #[allow(non_snake_case)]
76 fn sinsemilla_hackworks_test_vectors() {
77 use halo2::pasta::group::ff::PrimeField;
78
79 for tv in tests::vectors::SINSEMILLA.iter() {
80 let D = tv.domain.as_slice();
81 let M: &BitVec<u8, Lsb0> = &tv.msg.iter().collect();
82
83 assert_eq!(
84 sinsemilla_hash(D, M).expect("should not fail per Theorem 5.4.4"),
85 pallas::Base::from_repr(tv.hash).unwrap()
86 )
87 }
88 }
89
90 // Checks Pallas group hashes with:
91 // - One of two domains.
92 // - Random message lengths between 0 and 255 bytes.
93 // - Random message contents.
94 #[test]
95 #[allow(non_snake_case)]
96 fn sinsemilla_hackworks_group_hash_test_vectors() {
97 use halo2::pasta::group::GroupEncoding;
98
99 for tv in tests::vectors::GROUP_HASHES.iter() {
100 let D = tv.domain.as_slice();
101 let M = tv.msg.as_slice();
102
103 assert_eq!(
104 pallas_group_hash(D, M),
105 pallas::Point::from_bytes(&tv.point).unwrap()
106 );
107 }
108 }
109}