arkworks-rs / accumulation Goto Github PK

Rust library for accumulation schemes

License: Apache License 2.0

Rust 100.00%

proof-carrying-data accumulation-schemes cryptography elliptic-curves

accumulation's Introduction

Accumulation Schemes

ark-accumulation is a Rust library that provides infrastructure for implementing accumulation schemes. This library was developed as part of the Proof-Carrying Data without Succinct Arguments paper, and is released under the MIT License and the Apache v2 License (see License).

WARNING: This is an academic prototype, and in particular has not received careful code review. This implementation is NOT ready for production use.

Overview

An accumulation scheme for a predicate is a cryptographic primitive that allows an accumulation prover to receive a stream of inputs and accumulate them into an object called an accumulator. Given the inputs and outputs of the prover, an accumulation verifier can verify that the set of inputs was properly accumulated. At any time, an accumulation decider can use a single accumulator to determine whether all the previously accumulated inputs satisfy the predicate.

This library provides the following features that enable specific implementations of accumulation schemes:

hp-as: An accumulation scheme for Hadamard Products
ipa-pc-as: An accumulation scheme for the polynomial commitment scheme based on Inner Product Arguments (as implemented in the poly-commit library)
r1cs-nark-as: An accumulation scheme for a NARK for R1CS (as implemented in this library)
trivial-pc-as: An accumulation scheme for the trivial polynomial commitment scheme (as implemented in the poly-commit library)

Build guide

The library compiles on the stable toolchain of the Rust compiler. To install the latest version of Rust, first install rustup by following the instructions here, or via your platform's package manager. Once rustup is installed, install the Rust toolchain by invoking:

rustup install stable

After that, use cargo (the standard Rust build tool) to build the library:

git clone https://github.com/arkworks-rs/accumulation.git
cd accumulation
cargo build --release

This library comes with some unit and integration tests. Run these tests with:

cargo test

License

This library is licensed under either of the following licenses, at your discretion.

Unless you explicitly state otherwise, any contribution that you submit to this library shall be dual licensed as above (as defined in the Apache v2 License), without any additional terms or conditions.

Reference papers

Proof-Carrying Data from Accumulation Schemes
Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, Nicholas Spooner

Proof-Carrying Data without Succinct Arguments
Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, Nicholas Spooner

accumulation's People

Contributors

Stargazers

Watchers

Forkers

spector-in-london deevashwer 0kml joshbeal rhombus-tech

accumulation's Issues

Dependabot can't resolve your Rust dependency files

Dependabot can't resolve your Rust dependency files.

As a result, Dependabot couldn't update your dependencies.

The error Dependabot encountered was:

Updating git repository `https://github.com/arkworks-rs/algebra`
    Updating git repository `https://github.com/Will-Lin4/poly-commit`
    Updating git repository `https://github.com/arkworks-rs/sponge/`
    Updating git repository `https://github.com/arkworks-rs/utils`
    Updating crates.io index
    Updating git repository `https://github.com/arkworks-rs/curves`
error: no matching package named `ark-sponge` found
location searched: https://github.com/Will-Lin4/poly-commit?branch=accumulation-experimental#0688fc5f
required by package `ark-poly-commit v0.1.0 (https://github.com/Will-Lin4/poly-commit?branch=accumulation-experimental#0688fc5f)`
    ... which is depended on by `ark-accumulation v0.1.0 (/home/dependabot/dependabot-updater/dependabot_tmp_dir)`

If you think the above is an error on Dependabot's side please don't hesitate to get in touch - we'll do whatever we can to fix it.

View the update logs.

Implement specialized HP accumulation for the IVC case

Constraint counts for the accumulation verifier

What is the easiest way to produce data used in Figure 7 here: https://eprint.iacr.org/2020/1618.pdf? Also, how about the number of constraints for the accumulation verifier for the NARK for R1CS in this paper?

It looks like the examples (e.g., scaling-as) report the prover time/verifier time/etc. but not the number of constraints of the accumulation verifier.

Generalize `ASForHP` to any bilinear product, as outlined in the paper.

`Absorbable` implementations that utilize `to_bytes` may not match their `AbsorbableGadget` counterpart

There may be 0 padding in some implementations of native to_bytes, making it differ from the constraints equivalent. It may be worthwhile to consistently take a subset of the bytes (based on the number of bits in the field) to make the outputs consistent between native and constraints to_bytes.

Implement generalization of split accumulation that enables succinct PCD proofs

Use linear combinations for rowcheck

To optimize the NARK and the accumulation verifier, we could use the "open a linear-equation" idea from Marlin, where for row-check instead of providing evaluations for z_a, z_b, z_c, v_h and q, we provide evaluations for z_a and v_H only, and then check that z_a(beta) * z_b - z_c - v_H(beta) * q = 0 at beta

this reduces the accumulator size, and eliminates some non-native work

(above I assume that we're committing to v_H too)