Tip5：代数哈希

提示5：代数哈希

大多数网络安全专业人士会告诉你，密码学哈希涉及对数据进行挤压 (squeezing)，以形成固定长度的输出。当然，我们可以使用 XOF 函数获得可变长度的输出，但这仍然涉及多个轮次的挤压 (squeezing)过程。但这个过程不遵循代数方法，因此缺乏数学基础。在零知识证明 (zero-knowledge proof)的世界中——例如使用 STARKs——我们常用的哈希方法，如 SHA-256 和 Blake2，实现起来很复杂，而且运行速度通常很慢，特别是因为我们无法在有限域中计算它们。

MiMC

为了集成代数哈希，我们需要一种可以在有限域上实现的哈希方法。三种典型的方法是 Pedersen 哈希 [ 这里], Posiden 哈希 [ 这里] 和 MiMC (最小乘法复杂度) 哈希 [1][ 这里]:

MiMC 的一个重要特征是具有较低的乘法复杂度，这在多方计算 (MPC)、全同态加密 (FHE) 和 ZKP 等领域中都有应用。Dan Bohen 等人[2]还提出了将其用于 VDF（可验证延迟函数），因为 MiMC 的复杂度仅为 AES 的 1.6％。

在原始论文中，有一个映射:

F(x) = x³

但 MiMC-7 使用：

F(x) = x⁷

总而言之，我们有一个具有 q 个元素的有限域 (F_q)，并使用 轮函数 (round function) 迭代 r 次——其中 q 是一个素数。在每一轮中，我们添加一个密钥 (k) 值和一个 轮常量 (round constant) (c_i) ——除了第一轮之外——以及 F(x) = x⁷ 的非线性函数。这是一个演示:

MiMC-7 哈希和 Golang

提示5

Tip5 是一个面向代数的 (AO) 哈希函数 [ 这里]，并使用一个有限域 (F_𝑝)，其中 𝑝 = 2⁶⁴ − 2³² + 1——一个“小的” Goldilocks 素数域。这具有 128 位的安全性。一个关键特性是它具有较低的乘法深度，因为乘法在零知识证明中具有较高的开销。总的来说，Tip5 有三个主要元素：

• 一个 S-Box 层。这作为一个基本的查找表运行。
• 一个 MDS 层。这涉及使用 16 × 16 MDS 矩阵对内部状态进行矩阵-向量乘法。
• 一个 ARK (加法轮常量 (Additive Round Constants)) 层。这涉及将一个采样的常量添加到每个状态元素。

我们可以使用代码[ 这里][ 演示]：

/**
 *
 * Copyright (c) 2025 Maxim [maxirmx] Samsonov
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 *
 * This file is a part of tip5xx library
 *
 */

use clap::{Parser, ValueEnum};
use std::error::Error;
use twenty_first::{math::tip5::Tip5, prelude::{Digest, BFieldElement}};
##[derive(Debug, Copy, Clone, PartialEq, Eq, ValueEnum)]
enum Mode {
    Pair,
    Varlen,
}
##[derive(Parser)]
##[command(author, version, about = "TIP5 Hash Calculator")]
struct Args {
    /// Hash mode: 'pair' or 'varlen'
    #[arg(short, long, value_enum, default_value_t = Mode::Pair)]
    mode: Mode,
    /// Input digests in format (n1,n2,n3,n4,n5) for each digest
    #[arg(required = true, help = "Input digests in format (n1,n2,n3,n4,n5).\nFor pair mode: provide exactly 2 digests\nFor varlen mode: provide 2 or more digests\nEach number can be in formats:\n- Hexadecimal: 0x01020304 (must use 0x prefix)\n- Decimal: 16909060 (numbers starting with 0 like 0123 are treated as decimal)")]
    inputs: Vec,
}
fn parse_number(input: &str) -> Result<BFieldElement, Box<dyn Error>> {
    let trimmed = input.trim();
    let value = if trimmed.starts_with("0x") || trimmed.starts_with("0X") {
        // Handle hex format
        let hex_str = &trimmed[2..];
        u64::from_str_radix(hex_str, 16)?
    } else {
        // Handle decimal
        trimmed.parse::()?
    };
    Ok(BFieldElement::new(value))
}
fn parse_digest(input: &str) -> Result<Digest, Box<dyn Error>> {
    // Remove outer parentheses and split by comma
    // 移除外面的括号并用逗号分割
    let content = input.trim()
        .strip_prefix('(')
        .ok_or("Missing opening parenthesis")?
        .strip_suffix(')')
        .ok_or("Missing closing parenthesis")?;
    let numbers: Vec<&str> = content.split(',').collect();
    if numbers.len() != 5 {
        return Err("Each digest must contain exactly 5 numbers".into());
    }
    let elements: Result, _> = numbers
        .iter()
        .map(|n| parse_number(n))
        .collect();
    let elements = elements?;
    Ok(Digest::new([\
        elements[0],\
        elements[1],\
        elements[2],\
        elements[3],\
        elements[4],\
    ]))
}
fn main() -> Result<(), Box<dyn Error>> {
    let args = Args::parse();
    match args.mode {
        Mode::Pair => {
            if args.inputs.len() != 2 {
                return Err("pair mode requires exactly 2 digests".into());
            }
            let digest1 = parse_digest(&args.inputs[0])?;
            let digest2 = parse_digest(&args.inputs[1])?;
            println!("Hash pair mode Digest{}, Digest{}", args.inputs[0], args.inputs[1]);
            let result = Tip5::hash_pair(digest1, digest2);
            print!("Result: ");
            println!("Digest({})", result.to_string());
        }
        Mode::Varlen => {
            if args.inputs.len() < 2 {
                return Err("varlen mode requires at least 2 digests".into());
            }
            let mut digests = Vec::new();
            for input in &args.inputs {
                let digest = parse_digest(input)?;
                digests.extend_from_slice(&digest.values());
            }
            print!("Hash varlen mode Digest");
            for (i, input) in args.inputs.iter().enumerate() {
                if i > 0 {
                    print!(", ");
                }
                print!("{}", input);
            }
            println!("");
            let result = Tip5::hash_varlen(&digests);
            print!("Result: ");
            println!("Digest({})", result.to_string());
        }
    }
    Ok(())
}

一个示例运行是[ 演示]:

Hash pair mode Digest(06635923243246478901,08947438058482825410,01316460179998954120,11985665471998192029,14569756628708636130), Digest(06635923243246478902,08947438058482825410,01316460179998954127,11985665471998192023,14569756628708636139)
Result: Digest(16064912558447642910,09028968064102432957,17557561715502144571,18410287472055724668,16895367727029851698)

你可以在这里找到其他的低 MC 方法:

Baby Jubjub 曲线

• 原文链接： billatnapier.medium.com/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～