a hack implementation of CCS generic arithmetization, won a prize at Zuzalu hackathon 2023 despite incompleteness

Last update: Jun 1, 2023

Related tags

Overview

ccs-hack

CCS (Customized Constraint System) is a generic constraints representation system can simultaneously capture R1CS, Plonkish, and AIR:

$$\sum_{i=0}^{q-1} c_i \bigcirc_{j\in S_i} M_j \cdot z = 0 $$

You can easily convert CCS to R1CS, Plonkish, Air and vice versa. You can also build proof systems that directly using CCS as the constraints system, such as HyperNova, SuperSpartan.

CCS can save (or add) the fragmentation of arithmetisations!

Comments

Waylon/bugs

It changes the following: Added generic params for r1cs in a spot they were missing. Also remove the local finite field implementation (arkworks probably better)

opened by 0xJepsen 0
⬆️ Update num-bigint requirement from 0.3.2 to 0.4.3
⚠️ Dependabot is rebasing this PR ⚠️

Rebasing might not happen immediately, so don't worry if this takes some time.

Note: if you make any changes to this PR yourself, they will take precedence over the rebase.

Updates the requirements on num-bigint to permit the latest version.

Changelog

Sourced from num-bigint's changelog.

Release 0.4.3 (2021-11-02)

GHSA-v935-pqmr-g8v9: Fix unexpected panics in multiplication.

Contributors: @arvidn, @cuviper, @guidovranken

Release 0.4.2 (2021-09-03)

Use explicit Integer::div_ceil to avoid the new unstable method.

Contributors: @catenacyber, @cuviper

Release 0.4.1 (2021-08-27)

Fixed scalar divide-by-zero panics.

Implemented DoubleEndedIterator for U32Digits and U64Digits.

Optimized multiplication to avoid unnecessary allocations.

Optimized string formatting for very large values.

Contributors: @cuviper, @PatrickNorton

Release 0.4.0 (2021-03-05)

Breaking Changes

Updated public dependences on arbitrary, quickcheck, and rand:

arbitrary support has been updated to 1.0, requiring Rust 1.40.

quickcheck support has been updated to 1.0, requiring Rust 1.46.

rand support has been updated to 0.8, requiring Rust 1.36.

Debug now shows plain numeric values for BigInt and BigUint, rather than the raw list of internal digits.

Contributors: @cuviper, @Gelbpunkt

Release 0.3.3 (2021-09-03)

... (truncated)

Commits

e77ffac Merge #228

056e0d4 Release 0.4.3

8008707 Fix an undersized buffer panic in multiplication

0940e50 Fix a mac3 panic when an operand is all-zero

1fc2537 Add 0.3.3 release notes

8ee0b9a Merge #219

1469ed6 Fix div_ceil with rand and serde too

22940ca Release 0.4.2

de57106 Adjust shadowed names around div_ceil

a8fc78c rust: use explicitily Integer::div_ceil

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 0
Update rstest requirement from 0.16 to 0.17
Updates the requirements on rstest to permit the latest version.

Release notes

Sourced from rstest's releases.

0.17.0

Introduce #[awt] and #[future(awt)] feature.

Changelog

Sourced from rstest's changelog.

[0.17.0] 2023/3/19

Add

Add #[awt] and #[future(awt)] to .await future input

Fixed

Fixed wrong message when timeout tests panic before timeout expire (See #171)

[0.16.0] 2022/11/27

Changed

Show TEST START banner only when trace some argument: See #158 for details.

Add values to test name: See #160 for details.

Fixed

Updated test fixtures to 1.64.0 compiler's error messages.

[0.15.0] 2022/06/27

Fixed

Timeout not compile if one of its test arguments il not a copy type [see #154]

[0.14.0] 2022/06/19

Changed

Feature gated async timeout via async-timeout feature [see #148]

Fixed

Removed async-std build dependency [see #148]

[0.13.0] 2022/05/15

Add

#[timeout(duration)] test implementation for both sync and async tests (See #136)

Changed

Split rstest in separated crates for macro and libs (See #32)

[0.12.0] 2021/12/12

Add

Add #[once] fixture attribute to create static fixtures (See #119)

... (truncated)

Commits

7ac624c update readme version

ad67a4d Updated rstest_test version

1584894 Release rstest_test

1960f05 Apply clippy suggestions and prepare

91c60bd Auto await feature (#186)

23b5311 Update unindent requirement from 0.1.9 to 0.2.1 (#181)

b12f16c Fix #175 and release the new version 0.5.0

eeb9b51 Update rstest_test dependencies and publish new version 0.10.0

9ece1be Refactor to introduce a project local path dependency

478baa1 Fix #176

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 0
Update criterion requirement from 0.4 to 0.5
Updates the requirements on criterion to permit the latest version.

Changelog

Sourced from criterion's changelog.

[0.5.0] - 2023-05-23

Changed

Replaced lazy_static dependency with once_cell

Improved documentation of the html_reports feature

Replaced atty dependency with is-terminal

MSRV bumped to 1.64

Upgraded clap dependency to v4

Upgraded tempfile dependency to v3.5.0

Fixed

Quick mode (--quick) no longer outputs 1ms for measured times over 5 seconds

Documentation updates

[0.4.0] - 2022-09-10

Removed

The Criterion::can_plot function has been removed.

The Criterion::bench_function_over_inputs function has been removed.

The Criterion::bench_functions function has been removed.

The Criterion::bench function has been removed.

Changed

HTML report hidden behind non-default feature flag: 'html_reports'

Standalone support (ie without cargo-criterion) feature flag: 'cargo_bench_support'

MSRV bumped to 1.57

rayon and plotters are optional (and default) dependencies.

Status messages ('warming up', 'analyzing', etc) are printed to stderr, benchmark results are printed to stdout.

Accept subsecond durations for --warm-up-time, --measurement-time and --profile-time.

Replaced serde_cbor with ciborium because the former is no longer maintained.

Upgrade clap to v3 and regex to v1.5.

Added

A --discard-baseline flag for discarding rather than saving benchmark results.

Formal support for benchmarking code compiled to web-assembly.

A --quiet flag for printing just a single line per benchmark.

A Throughput::BytesDecimal option for measuring throughput in bytes but printing them using decimal units like kilobytes instead of binary units like kibibytes.

Fixed

When using bench_with_input, the input parameter will now be passed through black_box before passing it to the benchmark.

[0.3.6] - 2022-07-06

Changed

MSRV bumped to 1.49

Symbol for microseconds changed from ASCII 'us' to unicode 'µs'

... (truncated)

Commits

4a560cb release version 0.5 (#683)

3e2849e Post v0.4 CHANGELOG updates (#680)

637010e Bump clap to version 4 (#679)

39d7e2f Update to tempfile 3.5 (#675)

8ab2752 Fix typo in known_limitations.md (#674)

a211230 chore: replace atty with is-terminal (#628)

a844eb2 Bump MSRV to 1.60 for csv dependency (#665)

2f53607 Use OR operator to specify multiple licenses (#643)

86dcd7d Fix bug where time over the maximum would be reported as 1ms in quick mode. (...

2942aee Remove unnecessary pub from example code (#657)

Additional commits viewable in compare view

Dependabot will resolve any conflicts with this PR as long as you don't alter it yourself. You can also trigger a rebase manually by commenting @dependabot rebase.

Dependabot commands and options

You can trigger Dependabot actions by commenting on this PR:

@dependabot rebase will rebase this PR

@dependabot recreate will recreate this PR, overwriting any edits that have been made to it

@dependabot merge will merge this PR after your CI passes on it

@dependabot squash and merge will squash and merge this PR after your CI passes on it

@dependabot cancel merge will cancel a previously requested merge and block automerging

@dependabot reopen will reopen this PR if it is closed

@dependabot close will close this PR and stop Dependabot recreating it. You can achieve the same result by closing it manually

@dependabot ignore this major version will close this PR and stop Dependabot creating any more for this major version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this minor version will close this PR and stop Dependabot creating any more for this minor version (unless you reopen the PR or upgrade to it yourself)

@dependabot ignore this dependency will close this PR and stop Dependabot creating any more for this dependency (unless you reopen the PR or upgrade to it yourself)

dependencies
opened by dependabot[bot] 0
Test for Custome Constrain Systems
[ ] test_ccs_invalid_c_length(): This test should check that is_satisfied_by returns an error when c does not have length q.

[ ] test_ccs_invalid_M_length(): This test should check that is_satisfied_by returns an error when M does not have length t.

[ ] test_ccs_invalid_x_length(): This test should check that is_satisfied_by returns an error when x does not have length l.

[ ] test_ccs_invalid_w_length(): This test should check that is_satisfied_by returns an error when w does not have length n - l - 1.

[ ] test_ccs_invalid_s_cardinality(): This test should check that is_satisfied_by returns an error when any Si in S has a cardinality greater than d.

[ ] test_ccs_invalid_s_value(): This test should check that is_satisfied_by returns an error when any Si in S contains a value not in the domain {0, ..., t-1}.

test
opened by 0xJepsen 0
Tests for plonkish structure
We should test the satisfiability for the plonkish structure in a number of ways

[ ] Check constraints are satisfied with small poly

[ ] Check constraints are not satisfied when they shouldn't be

[ ] Test higher degree polynomials

test
opened by 0xJepsen 0
Benchmarks on overhead

One thing I know the community to be quite interested in is the performance of these maps and schemes. If we are able to benchmark some examples to measure how these hold up in practice it would be a good value add.
documentation enhancement

opened by 0xJepsen 0
Tests for R1CS check constraints
Right now this is a hacked together implementation which has been a really wonderful learning tool. However to move towards production implementations it would be nice to build confidence in our implementation with a variety of tests. These would be a good place to start.

[ ] Test for R1CS satisfaction: This should check that the is_satisfied_by method correctly determines whether a given instance and witness satisfy the R1CS. This should include tests with both satisfying and non-satisfying instances and witnesses.

[ ] Test for R1CS creation: This should check that the R1CS is created correctly given valid inputs and that it correctly rejects invalid inputs. It should test the new method and verify that the assert! statements correctly enforce the constraints on the inputs.

[ ] Test for conversion to CCS: This should check that the to_ccs method correctly converts the R1CS to a CCS. It should test that the properties of the CCS (like its size and the properties of its multisets and constants) match what's expected based on the original R1CS.

test
opened by 0xJepsen 0

Owner

Thor

zk wink

GitHub

Following "ZK HACK III - Building On-chain Apps Off-chain Using RISC Zero"

RISC Zero Rust Starter Template Welcome to the RISC Zero Rust Starter Template! This template is intended to give you a starting point for building a

3 Dec 22, 2022

Burrow is a tool for burrowing through firewalls, built by teenagers at Hack Club.

Burrow Burrow is a tool for burrowing through firewalls, built by teenagers at Hack Club. At its core, burrow is a command line utility written in Rus