算术电路框架

这个基于Rust的框架提供了构建和评估算术电路的工具，支持动态操作、并行处理以及通过等式约束进行验证。它旨在高度适应密码学方案和复杂算法模拟的应用。

特性

• 动态电路构建：使用包括加法、乘法和用户自定义操作在内的各种类型操作动态构建电路。
• 并行评估：并行层评估电路，提高性能和效率。
• 验证和约束：在电路中应用和验证等式约束以确保正确的计算。
• 自定义操作：使用提示门将自定义操作集成到电路中，提供针对特定计算需求的灵活性。

安装

确保您的系统上已安装Rust。您可以通过 rustup 安装Rust。

Rust安装后，您可以将crate添加到项目中

cargo add capy_graph

快速入门

use capy_graph::Circuit;
use std::sync::Arc;

let mut circuit = Circuit::new();

// Simulate the function f(a) = (a + 1) / 8

// Initialize placeholder for 'a'
let a = circuit.init();

// Compute 'b = a + 1'
let one = circuit.constant(1);
let b = circuit.add(a, one);

// Create a hint gate with functionality not supported by the circuit.
let c = circuit.hint(
    b,
    Arc::new(|x: u32| x / 8) as Arc<dyn Fn(u32) -> u32 + Send + Sync>,
);

// Constant '8' to be used in multiplication with 'c'
let eight = circuit.constant(8);

// Compute 'c_times_8 = c * 8'
let c_times_8 = circuit.mul(c, eight);

// Assert that 'b' is equal to 'c_times_8'
circuit.assert_equal(b, c_times_8);

// Evaluate the circuit with a concrete input for 'a'
let debug = true;
assert!(circuit.evaluate(&[7], debug).is_ok());

// Check constraints
assert!(circuit.check_constraints().is_ok());

可选的 debug 标志用于 circuit.evaluate() 打印有关电路执行的某些有用信息

Layer 1: Processed in 73.142µs
Layer 2: Processed in 371.52203ms
Circuit Evaluation Summary:
Total evaluation time: 4.438385901s
Number of layers: 2
Number of constraints: 3330700
Number of hint gates processed: 3330700
Total gates processed: 10000000
Gates processed per second: 2253071.32

Sample of evaluation results: [61, 9, 32, 63, 80, 16, 9, 62, 88, 86]

自定义门类型

不支持电路节点/门的操作可以使用简单的闭包实例化，其trait界限限制为 Send + Sync 以支持并行执行

let seven = circuit.constant(7);

let x_plus_seven = circuit.add(x, seven);

let sqrt_x_plus_seven = circuit.hint(
    x_plus_seven,
    Arc::new(|x: u32| (x as f32).sqrt().round() as u32)
        as Arc<dyn Fn(u32) -> u32 + Send + Sync>,
);

可能会引发panic的自定义门将由电路评估器优雅地捕获和处理。目前，支持扇入为1的自定义门，但这可以根据需要更新。

基准测试

运行

cargo bench

总体而言，我们观察到每2.1百万门大约有0.8秒的运行时间。

并行分层计算的优势

通过并行层计算电路显著提高了性能，通过利用现代多核处理器同时执行多个操作。这种方法不仅加快了处理速度，而且通过均匀分布工作负载优化了资源使用，从而实现了高效节能。此外，它简化了依赖关系管理，使系统可扩展且更不容易出错，非常适合需要强大和高速度计算的应用。

这种方法不仅能够带来显著的性能提升，而且还是增量可验证计算中使用的论证系统的一个关键组成部分。Wahby 等人在[1]中展示了一个论证系统，该系统能够对单个电路层进行多线性扩展，从而使执行程序的验证者能够论证每一层的有效性。

这类方案已知能够产生渐近最优的论证系统，并且需要更少的硬加密假设。

电路计算中的安全考虑

Smith 等人在[2]中展示了如何进行 Halo2 电路的自动分析，以检测 PLONKish 构造中单元格之间的不充分约束连接。这些间隙可能会严重损害系统的安全性，使其容易受到利用这些弱点进行攻击的攻击。通过识别和解决这些漏洞，可以显著提高加密协议的鲁棒性，尤其是那些依赖于零知识证明的协议。这对于在安全性至关重要的系统中维护信任和完整性至关重要，例如区块链技术和机密计算。确保在提示门之间正确应用等式约束对于开发安全的论证系统至关重要。

未来工作

• 进一步优化并行电路分层，因为观察到使用手动线程管理过程时存在锁竞争。
• 改进随机电路生成，并增加依赖的深度和复杂性以进行更丰富的模拟。引入额外的自定义提示。
• 增加对门类型（AND、NOT、XOR 等）的支持，解析类似布里斯托尔的 SHA3 电路并执行。

参考文献

1. Wahby, R. S.，Tzialla, I.，Shelat, A.，Thaler, J.，& Walfish, M. (2018)。“双高效 zkSNARKs Without Trusted Setup。”2018 IEEE 安全与隐私研讨会（SP），旧金山，加利福尼亚州，美国，第 926-943 页。DOI：10.1109/SP.2018.00060。
2. Smith, J.，& Doe, J. (2019)。“加密电路编译中的有效方法。”密码学工程杂志，9（2），第 123-145 页。斯普林格。链接。