SHA-256

规范

SHA-256 在 NIST FIPS PUB 180-4 有过规范的定义。

和上述规范定义不同的是，这里我们使用 $⊞$ 表示和 $2^{32}$ 的加模运算 ，用 $+$ 表示域上的加法。 $\oplus$ 用于表示异或。

组件（gadget）接口

SHA-256 使用8个32位的变量维护一个内部状态。SHA-256算法使用512比特位为一个区块作为输入，在算法内部将这些区块分解成32位的一些 chunk 。因此我们将SHA-256的组件设计为每次使用32位的 chunk 作为其输入。

芯片（chip）指令

SHA-256 gadget 要求芯片具有如下的指令：

#![allow(unused)]
fn main() {
extern crate halo2;
use halo2::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: Add instruction for computing padding.

这些指令的选择考虑到了可复用性和可优化空间的平衡。我们考虑将 compression 函数分割成几个组成部分，然后提供一个实现了不同轮次逻辑的 compression 组件。但是这会使得芯片无法使用同在一个 compression 轮次的不同部分的相对位置引用。使用一条指令实现所有的 compression 轮次非常类似于 Intel 的 SHA 指令集扩展，后者也是提供了一条指令对应多个 compression 轮次。