Constantine

Constantine：用于证明系统和区块链协议的高性能密码学

"一个密码系统应该是安全的，即使除了密钥之外的所有系统信息都是公开的。"
— Auguste Kerckhoffs

这个库提供了加密原语的恒定时间实现，特别关注于区块链和零知识证明系统中使用的密码学。

<!-- TOC -->

• Constantine
  • 公共API：曲线和协议
    • 协议
    • 椭圆曲线
    • 通用密码学
    • 线程池
  • 安装
    • 从Rust
    • 从Go
    • 从C
    • 从Nim
  • 依赖和要求
  • 性能
  • 汇编和硬件加速
  • 安全性
    • 免责声明
    • 安全披露
  • 为什么选择Nim
  • 许可证

<!-- /TOC -->

该库旨在成为一个快速、紧凑和强化的椭圆曲线密码学库，特别适用于区块链协议和零知识证明系统。

该库重点关注以下特性：

• 恒定时间（不通过侧信道泄露秘密数据）
• 性能
• 生成的代码大小、数据类型大小和栈使用

按此顺序排列。

公共API：曲线和协议

协议是为特定目标或其组合而设计的一组例程：

• 机密性：只有消息的预期接收者可以阅读
• 身份验证：通信中的另一方是预期的一方
• 完整性：收到的消息未被篡改
• 不可否认性：消息发送者不能否认发送过该消息

图例

• :white_check_mark:：完全支持
• :building_construction:：部分支持：
  • 在C中，某些API未提供。
  • 在Rust中，仅提供低级constantine-sys API，但没有高级封装。
• :see_no_evil:：缺少支持

协议

Constantine在其公共API中支持以下协议。

	Nim	C	Rust	Go
以太坊BLS签名	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
以太坊KZG承诺（用于EIP-4844）	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
以太坊IPA承诺（用于Verkle树）	:building_construction:	:see_no_evil:	:see_no_evil:	:see_no_evil:
以太坊虚拟机BN254预编译ECADD、ECMUL、ECPAIRING	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
EVM BLS12-381预编译（EIP-2537）	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
EVM其他：SHA256、modexp	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
Halo2证明系统的Zk加速层（实验性）	不适用	不适用	:white_check_mark:	不适用

椭圆曲线

Constantine在其公共API中支持以下曲线。

	Nim	C	Rust	Go
BN254-Snarks	:white_check_mark:	:white_check_mark:	:white_check_mark:	:see_no_evil:
BLS12-381	:white_check_mark:	:white_check_mark:	:white_check_mark:	:see_no_evil:
Pasta曲线（Pallas和Vesta）	:white_check_mark:	:white_check_mark:	:white_check_mark:	:see_no_evil:

对于所有椭圆曲线，支持以下算术运算：

• 域算术
  • 在Fr上（即模255位曲线阶）
  • 在Fp上（即模381位素数模数）
• 椭圆曲线算术：
  • 在Fp上的椭圆曲线（EC 𝔾₁）上，使用仿射、雅可比和齐次射影坐标
  • 在Fp2上的椭圆曲线（EC 𝔾₂）上，使用仿射、雅可比和齐次射影坐标
  • 包括标量乘法、多标量乘法（MSM）和并行MSM

除非明确提到 vartime，否则所有操作都是恒定时间的。

对于支持配对的曲线，Fp2算术也被公开。
:building_construction: 配对和多重配对已实现但尚未公开。

通用密码学

Constantine在其公共API中支持以下哈希函数和CSPRNGs。

	Nim	C	Rust	Go
SHA256	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:
从操作系统获取加密安全的随机数生成器（sysrand）	:white_check_mark:	:white_check_mark:	:white_check_mark:	:white_check_mark:

线程池

Constantine 还为 Nim 提供了一个高性能线程池，其性能和 API 继承自：

• 任务并行 API RFC：https://github.com/nim-lang/RFCs/issues/347

  • Weave 数据并行 API：
    • spawn 和 sync
    • parallelFor 和 syncScope
      • parallelFor 支持任意复杂的归约。 Constantine 广泛使用它进行并行椭圆曲线求和归约。
    • isSpawned 和 isReady

• CPU 拓扑 - 查询操作系统/虚拟机级别可用于运行计算的线程数：

  • C 中的 ctt_cpu_get_num_threads_os
  • Nim 中的 getNumThreadsOS
  • Rust 中的 constantine_core::hardware::get_num_threads_os

• https://github.com/mratsim/weave

• https://github.com/status-im/nim-taskpools

该线程池支持嵌套并行以充分利用高核心数，并且不受 OpenMP 嵌套并行循环限制的影响。对于批量 KZG 验证，Constantine 并行发出 3 个多标量乘法，每个使用至少 3 个嵌套并行循环。

有关线程池性能详情、设计和研究的更多信息，请参阅以下文档：

• ./README-PERFORMANCE.md#parallelism
• ./docs/threadpool-design.md
• https://github.com/mratsim/weave/tree/7682784/research

安装

[!重要] Constantine 可以由 Nim v1.6.x、v2.0.2 和 v2.0.4 编译，但不能由 Nim v2.0.0 编译（由于编译时评估崩溃）

从 Rust 安装

1. 安装 clang 编译器，例如：

   • Debian/Ubuntu：sudo apt update && sudo apt install build-essential clang

   • Archlinux：pacman -S base-devel clang

   [!提示] 我们需要 Clang，因为它在加密代码方面的性能明显优于 GCC，特别是对于 Constantine 没有汇编优化的 ARM 架构。Rust 和 Clang 都依赖于 LLVM。<br />通过删除这一行，可以更改为任何 C 编译器。

2. 安装 nim，它在大多数 Linux 发行版的包管理器中可用，MacOS 可通过 Homebrew 安装 Windows 二进制文件可在官方网站获取：https://nim-lang.org/install_unix.html

   • Debian/Ubuntu：sudo apt install nim
   • Archlinux：pacman -S nim

3. 测试以下两项：

   • 用于 Halo2-KZG 的实验性 ZK 加速 API（ZAL）
   • Ethereum EIP4844 KZG 多项式承诺

   git clone https://github.com/mratsim/constantine
   cd constantine
   cargo test
   cargo bench
   

4. 在 Cargo.toml 中添加 Constantine 作为依赖

   • 对于 Halo2-KZG Zk 加速层

     [dependencies]
     constantine-halo2-zal = { git = 'https://github.com/mratsim/constantine' }

   • 对于 Ethereum EIP-4844 KZG 多项式承诺

     [dependencies]
     constantine-ethereum-kzg = { git = 'https://github.com/mratsim/constantine' }

可选地，可以使用 Nim 和 Rust 之间的跨语言 LTO，参见 https://doc.rust-lang.org/rustc/linker-plugin-lto.html：

在项目中添加一个 .cargo/config.toml 文件，内容如下：

# .cargo/config.toml

[build]
rustflags="-Clinker-plugin-lto -Clinker=clang -Clink-arg=-fuse-ld=lld"

并修改 Constantine 的 build.rs 以传递 CTT_LTO=1

    Command::new("nimble")
        .env("CC", "clang")
        .env("CTT_LTO", "1") // <--
        .arg("make_lib_rust")
        .current_dir(root_dir)
        .stdout(Stdio::inherit())
        .stderr(Stdio::inherit())
        .status()
        .expect("failed to execute process");

从 Go 安装

1. 安装任意 C 编译器，推荐使用 clang，例如：

   • Debian/Ubuntu：sudo apt update && sudo apt install build-essential clang
   • Archlinux：pacman -S base-devel clang

2. 安装 nim，它在大多数 Linux 发行版的包管理器中可用，MacOS 可通过 Homebrew 安装 Windows 二进制文件可在官方网站获取：https://nim-lang.org/install_unix.html

   • Debian/Ubuntu：sudo apt install nim
   • Archlinux：pacman -S nim

3. 在 ./include 中编译 Constantine 为静态（和共享）库

   cd constantine
   CC=clang nimble make_lib
   

4. 测试 Go API。

   cd constantine-go
   go test -modfile=../go_test.mod
   

   [!重要] Constantine 使用单独的 modfile 进行测试。<br />除测试外，它没有任何依赖（这对避免供应链攻击至关重要）。

从 C 安装

1. 安装 C 编译器，推荐使用 clang，例如：

   • Debian/Ubuntu：sudo apt update && sudo apt install build-essential clang
   • Archlinux：pacman -S base-devel clang

2. 安装 nim，它在大多数 Linux 发行版的包管理器中可用，MacOS 可通过 Homebrew 安装 Windows 二进制文件可在官方网站获取：https://nim-lang.org/install_unix.html

   • Debian/Ubuntu：sudo apt install nim
   • Archlinux：pacman -S nim

3. 编译动态和静态库。

   • 推荐：
     CC=clang nimble make_lib
   • 或 CTT_ASM=0 nimble make_lib
     以不使用汇编编译（否则它会自动检测支持）
   • 或使用默认编译器
     nimble make_lib

4. 确保库正常工作

   • nimble test_lib

5. 库的位置

   • 库文件位于 ./lib/ 文件夹中
   • 头文件位于 ./include/ 中，例如 Ethereum BLS 签名

6. 阅读examples-c中的示例：

   • 使用C语言的以太坊BLS签名绑定
   • 对比测试Constantine BLS12-381与GMP ./examples-c/t_libctt_bls12_381.c

从Nim开始

您可以通过以下nimble命令安装库的开发版本

nimble install https://github.com/mratsim/constantine@#master

依赖项和要求

为了提高速度，建议使用Clang（参见编译器注意事项）。 特别是GCC生成的进位加法代码效率较低。

Constantine至少需要：

• GCC 7
  之前的版本生成了不正确的进位加法代码。
• Clang 14
  在x86-64上，使用内联汇编来解决编译器在优化大整数算术时遇到的问题， 并确保恒定时间代码。
  Constantine使用Intel汇编语法来解决默认AT&T语法和Clang中传播常量的问题。
  Clang 14增加了对-masm=intel的支持。
  
  在MacOS上，Apple Clang不支持Intel汇编语法，请使用Homebrew Clang或在不使用汇编的情况下编译。
  注意，Apple正在其整个产品线中停止使用Intel CPU，因此这只会影响旧型号和Mac Pro

在Windows上，Constantine使用MinGW进行测试。Microsoft Visual C++编译器尚未配置。

除了编译器外，Constantine没有C、Nim、Rust、Go依赖，甚至Nim标准库也没有，除了：

• 用于测试和基准测试
  • 被测试语言的json和yaml解析器，用于测试向量
  • 被测试语言的标准库，用于测试、计时和消息格式化
  • GMP，用于与GMP进行对比测试
• 对于Nvidia GPU后端：
  • LLVM运行时（不需要带有头文件的"dev"版本）
  • CUDA运行时（不需要带有头文件的"dev"版本）
• 在编译时
  • 我们需要std/macros库来生成Nim代码。

性能

这一部分内容太长，已单独成文。
请参见./README-PERFORMANCE.md

汇编和硬件加速

• 在x86和x86-64上使用汇编，除非传递了CTT_ASM=0。
• 计划为ARM提供汇编。
• 计划提供GPU加速。

汇编解决了两个问题：

• 安全性：与编译器争取恒定时间代码
• 性能：编译器注意事项

安全性

针对所有现有和即将出现的攻击向量来强化实现是一项极其复杂的任务。 在以下情况之前，该库按原样提供，不提供任何保证：

• 经过审计
• 产生正确性的形式化证明
• 可以对恒定时间实现进行形式化验证

针对常见攻击向量的防御是基于最大努力提供的。 请注意，Constantine没有外部包依赖，因此不容易受到 供应链攻击（除非它们影响编译器或操作系统）。

攻击者可能会不遗余力地检索秘密数据，包括：

• 计时椭圆曲线上的乘法所需时间
• 分析嵌入式设备的功耗
• 使用查找表时检测缓存未命中
• 内存攻击，如页面错误、分配器、内存保留攻击

如果不提到硬件、操作系统和编译器 主动阻碍你的以下方面，这将是不完整的：

• 硬件：有时不以恒定时间实现乘法。
• 操作系统：不提供防止内存分页到磁盘、核心转储、调试器附加到你的进程或上下文切换（协程）泄漏寄存器数据的方法。
• 编译器：优化掉你精心设计的无分支代码并泄露服务器机密，或优化掉你的安全擦除例程，因为在函数结束时数据不再使用而被认为是"无用的"。

越来越多的攻击向量正在被收集，供你欣赏 在 https://github.com/mratsim/constantine/wiki/Constant-time-arithmetics

免责声明

Constantine的作者尽最大努力实现一个安全的加密库， 特别是针对远程攻击向量，如定时攻击。

请注意，Constantine按原样提供，不提供任何保证。 使用风险自负。

在将数据置于风险之中之前，强烈建议彻底评估你的威胁模型、 你正在考虑的任何加密库的安全性以及你所冒险的机密。 作者希望提醒用户，最好的代码只能减轻 但不能防止人为失误，这是今天被利用的最薄弱环节和最大的 机密后门。

安全披露

你可以通过"安全"选项卡私下报告安全漏洞。

安全 > 报告漏洞

为什么选择Nim

Nim语言为加密提供以下优势：

• 通过C或C++编译成机器代码，或者编译成Javascript。轻松与这些语言进行FFI。
  • 可以针对具有专有C编译器的晦涩嵌入式设备。
  • 可以针对WASM。
• 可以在Nim中轻松达到C语言可达到的性能。
• 丰富的类型系统：泛型、依赖类型、可变性跟踪和副作用分析、借用检查、编译器强制的不同类型（Miles != Meters，SecretBool != bool和SecretWord != uint64）。
• 编译时求值，包括解析十六进制字符串，将它们转换为BigInt或有限域元素，并进行大整数运算。
• 支持汇编，可以内联或简单地使用{.compile: "myasm.S".}
• 如果不使用GC类型，则不使用GC（自动内存管理设置在类型级别，默认针对延迟/软实时进行优化，可以完全停用）。
• 过程宏直接在AST上工作，用于
  • 创建通用曲线配置，
  • 派生常量
  • 编写大小无关的内联汇编代码生成器
• 即将推出的通过Z3进行形式化验证的证明系统（DrNim，正确性构造RFC）

许可证

根据以下任一许可证授权和分发

• MIT许可证：LICENSE-MIT或http://opensource.org/licenses/MIT

或者

• Apache License，Version 2.0，（LICENSE-APACHEv2或http://www.apache.org/licenses/LICENSE-2.0）

由你选择。除非符合这些条款，否则不得复制、修改或分发本文件。

本库没有外部依赖。 特别是GMP仅用于测试和差分模糊测试， 并未链接到库中。