译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/sha256.html

SHA-256

规范(Specification)

SHA-256 在 NIST FIPS PUB 180-4 中定义。

与该规范不同,我们用 $⊞$ 表示模 $2^{32}$ 加法,用 $+$ 表示域加法(field addition)。$\oplus$ 用于表示异或(XOR)。

Gadget 接口

SHA-256 在八个 32 比特变量中维护状态。它以 512 比特的块(blocks)为单位处理输入,但在内部把这些块切分成 32 比特的小块(chunks)。因此我们把 SHA-256 gadget 设计成以 32 比特小块为单位消费输入。

芯片指令(Chip instructions)

SHA-256 gadget 需要一个具备以下指令的芯片(chip):

#![allow(unused)]
fn main() {
extern crate halo2_proofs;
use halo2_proofs::plonk::Error;
use std::fmt;

trait Chip: Sized {}
trait Layouter<C: Chip> {}
const BLOCK_SIZE: usize = 16;
const DIGEST_SIZE: usize = 8;

pub trait Sha256Instructions: Chip {
    /// Variable representing the SHA-256 internal state.
    type State: Clone + fmt::Debug;
    /// Variable representing a 32-bit word of the input block to the SHA-256 compression
    /// function.
    type BlockWord: Copy + fmt::Debug;

    /// Places the SHA-256 IV in the circuit, returning the initial state variable.
    fn initialization_vector(layouter: &mut impl Layouter<Self>) -> Result<Self::State, Error>;

    /// Starting from the given initial state, processes a block of input and returns the
    /// final state.
    fn compress(
        layouter: &mut impl Layouter<Self>,
        initial_state: &Self::State,
        input: [Self::BlockWord; BLOCK_SIZE],
    ) -> Result<Self::State, Error>;

    /// Converts the given state into a message digest.
    fn digest(
        layouter: &mut impl Layouter<Self>,
        state: &Self::State,
    ) -> Result<[Self::BlockWord; DIGEST_SIZE], Error>;
}
}

TODO:添加用于计算填充(padding)的指令。

这套指令的选取是为了在指令的可复用性和芯片对其进行内部优化的空间之间取得平衡。具体来说,我们考虑过把压缩函数(compression function)拆分成其组成部分(Ch、Maj 等),并提供一个实现轮逻辑(round logic)的压缩函数 gadget。然而,这会阻止芯片在一轮压缩(round compression)的各个部分之间使用相对引用(relative references)。提供一条实现全部压缩轮的指令,也与 Intel SHA 扩展(extensions)类似——后者提供了一条执行多轮压缩的指令。