risc0_zkp/core/hash/sha/
mod.rs

1// Copyright 2024 RISC Zero, Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15//! Simple SHA-256 wrappers.
16
17pub mod cpu;
18pub mod guest;
19mod rng;
20pub mod rust_crypto;
21
22// Pick the appropriate implementation of SHA-256 depending on whether we are
23// in the zkVM guest.
24cfg_if::cfg_if! {
25    if #[cfg(target_os = "zkvm")] {
26        pub use crate::core::hash::sha::guest::Impl;
27    } else {
28        pub use crate::core::hash::sha::cpu::Impl;
29    }
30}
31use alloc::boxed::Box;
32use alloc::{format, vec::Vec};
33use core::{
34    fmt::{Debug, Display, Formatter},
35    marker::PhantomData,
36    ops::DerefMut,
37};
38
39use bytemuck::{Pod, PodCastError, Zeroable};
40use hex::{FromHex, FromHexError};
41use risc0_core::field::Field;
42pub use risc0_zkvm_platform::WORD_SIZE;
43use serde::{Deserialize, Serialize};
44
45use crate::core::digest::{Digest, DIGEST_BYTES, DIGEST_WORDS};
46
47/// The number of words in the representation of a [Block].
48///
49/// Note that for SHA-256 the block is twice the size of the [Digest].
50pub const BLOCK_WORDS: usize = DIGEST_WORDS * 2;
51
52/// Size of the [Block] representation in bytes.
53///
54/// Note that blocks are stored in memory as words instead of bytes, and that a
55/// [Block] is twice the size of a [Digest].
56pub const BLOCK_BYTES: usize = DIGEST_BYTES * 2;
57
58/// Standard SHA-256 initialization vector.
59pub const SHA256_INIT: Digest = Digest::new([
60    0x6a09e667_u32.to_be(),
61    0xbb67ae85_u32.to_be(),
62    0x3c6ef372_u32.to_be(),
63    0xa54ff53a_u32.to_be(),
64    0x510e527f_u32.to_be(),
65    0x9b05688c_u32.to_be(),
66    0x1f83d9ab_u32.to_be(),
67    0x5be0cd19_u32.to_be(),
68]);
69
70/// An implementation of the SHA-256 hashing algorithm of [FIPS 180-4].
71///
72/// [FIPS 180-4]: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
73pub trait Sha256 {
74    /// A pointer to the digest created as the result of a hashing operation.
75    ///
76    /// This may either be a `Box<Digest>` or some other pointer in case the
77    /// implementation wants to manage its own memory. Semantically, holding the
78    /// `DigestPtr` denotes ownership of the underlying value. (e.g. `DigestPtr`
79    /// does not implement `Copy` and the owner of `DigestPtr` can create a
80    /// mutable reference to the underlying digest).
81    type DigestPtr: DerefMut<Target = Digest> + Debug;
82
83    /// Generate a SHA-256 hash from a slice of bytes, padding to block size
84    /// and adding the SHA-256 hash trailer, as specified in FIPS 180-4.
85    fn hash_bytes(bytes: &[u8]) -> Self::DigestPtr;
86
87    /// Generate a SHA-256 hash from a slice of words, padding to block size
88    /// and adding the SHA-256 hash trailer, as specified in FIPS 180-4.
89    fn hash_words(words: &[u32]) -> Self::DigestPtr {
90        Self::hash_bytes(bytemuck::cast_slice(words))
91    }
92
93    /// Generate a hash from a pair of [Digest] using the SHA-256 compression
94    /// function. Note that the result is not a standard-compliant hash of any
95    /// known preimage.
96    fn hash_pair(a: &Digest, b: &Digest) -> Self::DigestPtr {
97        Self::compress(&SHA256_INIT, a, b)
98    }
99
100    /// Execute the SHA-256 compression function on a single block given as
101    /// two half-blocks and return a pointer to the result.
102    ///
103    /// NOTE: The half blocks do not need to be adjacent.
104    ///
105    /// DANGER: This is the low-level SHA-256 compression function. It is a
106    /// primitive used to construct SHA-256, but it is NOT the full
107    /// algorithm and should be used directly only with extreme caution.
108    fn compress(state: &Digest, block_half1: &Digest, block_half2: &Digest) -> Self::DigestPtr;
109
110    /// Execute the SHA-256 compression function on a slice of blocks following
111    /// the [Merkle–Damgård] construction and return a pointer to the result.
112    ///
113    /// DANGER: This is the low-level SHA-256 compression function. It is a
114    /// primitive used to construct SHA-256, but it is NOT the full
115    /// algorithm and should be used directly only with extreme caution.
116    ///
117    /// [Merkle–Damgård]: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction
118    fn compress_slice(state: &Digest, blocks: &[Block]) -> Self::DigestPtr;
119
120    /// Generate a hash from a slice of anything that can be represented as
121    /// a slice of bytes. Pads up to the SHA-256 block boundary, but does not
122    /// add the standard SHA-256 trailer and so is not a standards compliant
123    /// hash.
124    fn hash_raw_data_slice<T: bytemuck::NoUninit>(data: &[T]) -> Self::DigestPtr;
125}
126
127/// Input block to the SHA-256 hashing algorithm. SHA-256 consumes blocks in
128/// 512-bit (64-byte) chunks in a [Merkle–Damgård] construction.
129///
130/// [Merkle–Damgård]: https://en.wikipedia.org/wiki/Merkle%E2%80%93Damg%C3%A5rd_construction
131#[derive(Copy, Clone, Eq, PartialEq, Hash, Pod, Zeroable, Serialize, Deserialize)]
132#[repr(transparent)]
133pub struct Block([u32; BLOCK_WORDS]);
134
135impl Block {
136    /// Returns a reference to the [Block] as a slice of words.
137    pub fn as_words(&self) -> &[u32] {
138        &self.0
139    }
140
141    /// Returns a reference to the [Block] as a slice of bytes.
142    pub fn as_bytes(&self) -> &[u8] {
143        bytemuck::cast_slice(&self.0)
144    }
145
146    /// Returns a mutable slice of words.
147    pub fn as_mut_words(&mut self) -> &mut [u32] {
148        &mut self.0
149    }
150
151    /// Returns the [Block] as references to two half-blocks, with the same size
152    /// are a SHA-256 digest.
153    pub fn as_half_blocks(&self) -> (&Digest, &Digest) {
154        match bytemuck::cast_slice::<_, Digest>(self.as_words()) {
155            [half_block1, half_block2] => (half_block1, half_block2),
156            _ => unreachable!("a block can always be decomposed into two digests"),
157        }
158    }
159
160    /// Returns a mutable slice of bytes.
161    pub fn as_mut_bytes(&mut self) -> &mut [u8] {
162        bytemuck::cast_slice_mut(&mut self.0)
163    }
164}
165
166impl Default for Block {
167    fn default() -> Block {
168        Block([0; BLOCK_WORDS])
169    }
170}
171
172/// Create a new [Block] from an array of words.
173impl From<[u32; BLOCK_WORDS]> for Block {
174    fn from(data: [u32; BLOCK_WORDS]) -> Self {
175        Self(data)
176    }
177}
178
179/// Create a new [Block] from an array of bytes.
180impl From<[u8; BLOCK_BYTES]> for Block {
181    fn from(data: [u8; BLOCK_BYTES]) -> Self {
182        match bytemuck::try_cast(data) {
183            Ok(block) => block,
184            Err(PodCastError::TargetAlignmentGreaterAndInputNotAligned) => {
185                // Bytes are not aligned. Copy the byte array into a new block.
186                bytemuck::pod_read_unaligned(&data)
187            }
188            Err(e) => unreachable!("failed to cast [u8; BLOCK_BYTES] to Block: {}", e),
189        }
190    }
191}
192
193impl<'a> From<&'a [u32; BLOCK_WORDS]> for &'a Block {
194    fn from(data: &'a [u32; BLOCK_WORDS]) -> Self {
195        bytemuck::cast_ref(data)
196    }
197}
198
199impl FromHex for Block {
200    type Error = FromHexError;
201
202    fn from_hex<T: AsRef<[u8]>>(hex: T) -> Result<Self, Self::Error> {
203        Ok(<[u8; BLOCK_BYTES]>::from_hex(hex)?.into())
204    }
205}
206
207impl TryFrom<&[u8]> for Block {
208    type Error = core::array::TryFromSliceError;
209
210    fn try_from(data: &[u8]) -> Result<Self, Self::Error> {
211        Ok(<[u8; BLOCK_BYTES]>::try_from(data)?.into())
212    }
213}
214
215impl TryFrom<&[u32]> for Block {
216    type Error = core::array::TryFromSliceError;
217
218    fn try_from(data: &[u32]) -> Result<Self, Self::Error> {
219        Ok(<[u32; BLOCK_WORDS]>::try_from(data)?.into())
220    }
221}
222
223impl TryFrom<Vec<u8>> for Block {
224    type Error = Vec<u8>;
225
226    fn try_from(data: Vec<u8>) -> Result<Self, Self::Error> {
227        Ok(<[u8; BLOCK_BYTES]>::try_from(data)?.into())
228    }
229}
230
231impl TryFrom<Vec<u32>> for Block {
232    type Error = Vec<u32>;
233
234    fn try_from(data: Vec<u32>) -> Result<Self, Self::Error> {
235        Ok(<[u32; BLOCK_WORDS]>::try_from(data)?.into())
236    }
237}
238
239impl From<Block> for [u8; BLOCK_BYTES] {
240    fn from(digest: Block) -> Self {
241        bytemuck::cast(digest)
242    }
243}
244
245impl From<Block> for [u32; BLOCK_WORDS] {
246    fn from(digest: Block) -> Self {
247        digest.0
248    }
249}
250
251impl AsRef<[u8; BLOCK_BYTES]> for Block {
252    fn as_ref(&self) -> &[u8; BLOCK_BYTES] {
253        bytemuck::cast_ref(&self.0)
254    }
255}
256
257impl AsMut<[u8; BLOCK_BYTES]> for Block {
258    fn as_mut(&mut self) -> &mut [u8; BLOCK_BYTES] {
259        bytemuck::cast_mut(&mut self.0)
260    }
261}
262
263impl AsRef<[u32; BLOCK_WORDS]> for Block {
264    fn as_ref(&self) -> &[u32; BLOCK_WORDS] {
265        &self.0
266    }
267}
268
269impl AsMut<[u32; BLOCK_WORDS]> for Block {
270    fn as_mut(&mut self) -> &mut [u32; BLOCK_WORDS] {
271        &mut self.0
272    }
273}
274
275impl AsRef<[u8]> for Block {
276    fn as_ref(&self) -> &[u8] {
277        self.as_bytes()
278    }
279}
280
281impl AsMut<[u8]> for Block {
282    fn as_mut(&mut self) -> &mut [u8] {
283        self.as_mut_bytes()
284    }
285}
286
287impl AsRef<[u32]> for Block {
288    fn as_ref(&self) -> &[u32] {
289        self.as_words()
290    }
291}
292
293impl AsMut<[u32]> for Block {
294    fn as_mut(&mut self) -> &mut [u32] {
295        self.as_mut_words()
296    }
297}
298
299impl Display for Block {
300    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
301        f.write_str(&hex::encode(self))
302    }
303}
304
305impl Debug for Block {
306    fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
307        f.write_str(&format!("Block({})", &hex::encode(self)))
308    }
309}
310
311/// Wrap a Sha256 trait as a HashFn trait
312struct Sha256HashFn;
313
314impl<F: Field> super::HashFn<F> for Sha256HashFn {
315    fn hash_pair(&self, a: &Digest, b: &Digest) -> Box<Digest> {
316        (*Impl::hash_pair(a, b)).into()
317    }
318
319    fn hash_elem_slice(&self, slice: &[F::Elem]) -> Box<Digest> {
320        (*Impl::hash_raw_data_slice(slice)).into()
321    }
322
323    fn hash_ext_elem_slice(&self, slice: &[F::ExtElem]) -> Box<Digest> {
324        (*Impl::hash_raw_data_slice(slice)).into()
325    }
326}
327
328struct Sha256RngFactory;
329
330impl<F: Field> super::RngFactory<F> for Sha256RngFactory {
331    fn new_rng(&self) -> Box<dyn super::Rng<F>> {
332        Box::new(rng::ShaRng::new())
333    }
334}
335
336/// Make a hash suite from a Sha256 trait
337pub struct Sha256HashSuite<F: Field> {
338    phantom: PhantomData<F>,
339}
340
341impl<F: Field> Sha256HashSuite<F> {
342    /// Construct a Sha256HashSuite
343    pub fn new_suite() -> super::HashSuite<F> {
344        use alloc::rc::Rc;
345        super::HashSuite {
346            name: "sha-256".into(),
347            hashfn: Rc::new(Sha256HashFn {}),
348            rng: Rc::new(Sha256RngFactory {}),
349        }
350    }
351}
352
353#[allow(missing_docs)]
354pub mod testutil {
355    use alloc::vec::Vec;
356    use core::ops::Deref;
357
358    use hex::FromHex;
359    use risc0_core::field::baby_bear::{BabyBearElem, BabyBearExtElem};
360
361    use super::{
362        rust_crypto::{self, Digest as _},
363        Sha256,
364    };
365    use crate::core::digest::Digest;
366
367    // Runs conformance test on a SHA-256 implementation to make sure it properly
368    // behaves.
369    pub fn test_sha_impl<S: Sha256>() {
370        test_hash_pair::<S>();
371        test_rust_crypto_wrapper::<S>();
372        test_hash_raw_data_slice::<S>();
373        test_sha_basics::<S>();
374        test_elems::<S>();
375        test_extelems::<S>();
376    }
377
378    fn test_sha_basics<S: Sha256>() {
379        // Standard test vectors
380        assert_eq!(
381            hex::encode(S::hash_bytes("abc".as_bytes()).deref()),
382            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
383        );
384        assert_eq!(
385            hex::encode(S::hash_bytes("".as_bytes()).deref()),
386            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
387        );
388        assert_eq!(
389            hex::encode(
390                S::hash_bytes(
391                    "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq".as_bytes()
392                )
393                .deref()
394            ),
395            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1"
396        );
397        assert_eq!(hex::encode(S::hash_bytes(
398            "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu" .as_bytes()).deref()),
399            "cf5b16a778af8380036ce59e7b0492370b249b11e8f07a51afac45037afee9d1");
400        // Test also the 'hexDigest' bit.
401        // Python says:
402        // >>> hashlib.sha256("Byzantium").hexdigest()
403        // 'f75c763b4a52709ac294fc7bd7cf14dd45718c3d50b36f4732b05b8c6017492a'
404        assert_eq!(
405            hex::encode(S::hash_bytes("Byzantium".as_bytes()).deref()),
406            "f75c763b4a52709ac294fc7bd7cf14dd45718c3d50b36f4732b05b8c6017492a"
407        );
408    }
409
410    fn test_rust_crypto_wrapper<S: Sha256>() {
411        // Standard test vectors
412        assert_eq!(
413            hex::encode(rust_crypto::Sha256::<S>::digest("abc".as_bytes())),
414            "ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad"
415        );
416        assert_eq!(
417            hex::encode(rust_crypto::Sha256::<S>::digest("".as_bytes())),
418            "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
419        );
420        assert_eq!(
421            hex::encode(rust_crypto::Sha256::<S>::digest(
422                "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq".as_bytes()
423            )),
424            "248d6a61d20638b8e5c026930c3e6039a33ce45964ff2167f6ecedd419db06c1"
425        );
426        assert_eq!(hex::encode(rust_crypto::Sha256::<S>::digest(
427            "abcdefghbcdefghicdefghijdefghijkefghijklfghijklmghijklmnhijklmnoijklmnopjklmnopqklmnopqrlmnopqrsmnopqrstnopqrstu" .as_bytes())),
428            "cf5b16a778af8380036ce59e7b0492370b249b11e8f07a51afac45037afee9d1");
429        // Test also the 'hexDigest' bit.
430        // Python says:
431        // >>> hashlib.sha256("Byzantium").hexdigest()
432        // 'f75c763b4a52709ac294fc7bd7cf14dd45718c3d50b36f4732b05b8c6017492a'
433        assert_eq!(
434            hex::encode(rust_crypto::Sha256::<S>::digest("Byzantium".as_bytes())),
435            "f75c763b4a52709ac294fc7bd7cf14dd45718c3d50b36f4732b05b8c6017492a"
436        );
437    }
438
439    fn hash_elems<S: Sha256>(len: usize) -> Digest {
440        let items: Vec<BabyBearElem> = (0..len as u32).map(BabyBearElem::new).collect();
441        *S::hash_raw_data_slice(items.as_slice())
442    }
443
444    fn hash_extelems<S: Sha256>(len: usize) -> Digest {
445        let items: Vec<BabyBearExtElem> = (0..len as u32)
446            .map(|x| {
447                BabyBearExtElem::new(
448                    BabyBearElem::new(x * 4),
449                    BabyBearElem::new(x * 4 + 1),
450                    BabyBearElem::new(x * 4 + 2),
451                    BabyBearElem::new(x * 4 + 3),
452                )
453            })
454            .collect();
455        *S::hash_raw_data_slice(items.as_slice())
456    }
457
458    fn test_elems<S: Sha256>() {
459        const LENS: &[usize] = &[0, 1, 7, 8, 9];
460        // It doesn't matter what elems hash to, as long as they're consistent.
461        const EXPECTED_STRS: &[&str] = &[
462            "6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19",
463            "da5698be17b9b46962335799779fbeca8ce5d491c0d26243bafef9ea1837a9d8",
464            "643f71dab15c4f6a6e8820dee5f59cc07818b9c4473b47bba9516cc3be992f1c",
465            "3dae53575097f63d0a461048813cc9ab870f0ddbcf9e4aea8dcddecc0aea736d",
466            "903fe671a0971f6dea6e8a1180dcd1ce87b56d0b42ee3861212e86428a983a5b",
467        ];
468
469        let expected: Vec<Digest> = EXPECTED_STRS
470            .iter()
471            .map(|x| Digest::from_hex(x).unwrap())
472            .collect();
473        let actual: Vec<Digest> = LENS.iter().map(|x| hash_elems::<S>(*x)).collect();
474        assert_eq!(expected, actual);
475    }
476
477    fn test_extelems<S: Sha256>() {
478        const LENS: &[usize] = &[0, 1, 7, 8, 9];
479        // It doesn't matter what extelems hash to, as long as they're consistent.
480        const EXPECTED_STRS: &[&str] = &[
481            "6a09e667bb67ae853c6ef372a54ff53a510e527f9b05688c1f83d9ab5be0cd19",
482            "6343c9ca9260f2d6cf190c2d2bbff0bf928789e4d2c1a24654137a5d48f254bc",
483            "07d3bfa65009530790a51cca21b83dd492c60ade96ee1d2c5b25c4c5cfe257b0",
484            "60a53ad42dfe03c7c0d1d46790a832356d09b52c6812eada27622476d6180392",
485            "5af62d0303208f4573656ac707d7447f0303fd76a134a775f329104d03c37985",
486        ];
487
488        let expected: Vec<Digest> = EXPECTED_STRS
489            .iter()
490            .map(|x| Digest::from_hex(x).unwrap())
491            .collect();
492        let actual: Vec<Digest> = LENS.iter().map(|x| hash_extelems::<S>(*x)).collect();
493        assert_eq!(expected, actual);
494    }
495
496    fn test_hash_raw_data_slice<S: Sha256>() {
497        {
498            let items: &[u32] = &[1];
499            assert_eq!(
500                *S::hash_raw_data_slice(items),
501                Digest::from_hex(
502                    "e3050856aac389661ae490656ad0ea57df6aff0ff6eef306f8cc2eed4f240249"
503                )
504                .unwrap()
505            );
506        }
507        {
508            let items: &[u32] = &[1, 2];
509            assert_eq!(
510                *S::hash_raw_data_slice(items),
511                Digest::from_hex(
512                    "4138ebae12299733cc677d1150c2a0139454662fc76ec95da75d2bf9efddc57a"
513                )
514                .unwrap()
515            );
516        }
517        {
518            let items: &[u32] = &[0xffffffff];
519            assert_eq!(
520                *S::hash_raw_data_slice(items),
521                Digest::from_hex(
522                    "a3dba037d56175209dfd4191f727e91c5feb67e65a6ab5ed4daf0893c89598c8"
523                )
524                .unwrap()
525            );
526        }
527    }
528
529    fn test_hash_pair<S: Sha256>() {
530        assert_eq!(
531            *S::hash_pair(
532                &Digest::from_hex(
533                    "67e6096a85ae67bb72f36e3c3af54fa57f520e518c68059babd9831f19cde05b"
534                )
535                .unwrap(),
536                &Digest::from_hex(
537                    "ad5c37ed90bb53c604e9ce787f6feeac7674bff229c92dc97ce2ba1115c0eb41"
538                )
539                .unwrap()
540            ),
541            Digest::from_hex("3aa2c47c47cd9e5c5259fd1c3428c30b9608201f5e163061deea8d2d7c65f2c3")
542                .unwrap()
543        );
544        assert_eq!(
545            *S::hash_pair(
546                &Digest::from_hex(
547                    "0000000000000000000000000000000000000000000000000000000000000000"
548                )
549                .unwrap(),
550                &Digest::from_hex(
551                    "0000000000000000000000000000000000000000000000000000000000000000"
552                )
553                .unwrap()
554            ),
555            Digest::from_hex("da5698be17b9b46962335799779fbeca8ce5d491c0d26243bafef9ea1837a9d8")
556                .unwrap()
557        );
558    }
559}
risc0_zkp/core/hash/sha/mod.rs

risc0_zkp/core/hash/sha/
mod.rs
