https://github.com/arkworks-rs/nonnative
R1CS constraints for non-native field arithmetic
Science Score: 10.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
○codemeta.json file
-
○.zenodo.json file
-
○DOI references
-
○Academic publication links
-
✓Committers with academic emails
4 of 7 committers (57.1%) from academic institutions -
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (11.3%) to scientific vocabulary
Keywords
Keywords from Contributors
Repository
R1CS constraints for non-native field arithmetic
Basic Info
Statistics
- Stars: 21
- Watchers: 9
- Forks: 11
- Open Issues: 2
- Releases: 0
Topics
Metadata Files
README.md
Non-Native Field Gadgets
The nonnative library provides R1CS constraints for checking computations over a non-native field in a proof system.
The library is based on the constraint-writing framework arkworks-rs and is released under the MIT License and the Apache v2 License (see License).
WARNING: This is an academic proof-of-concept prototype; in particular, it has not received careful code review. This implementation is NOT ready for production use.
Overview
This library implements a field gadget for a prime field Fp over another prime field Fq where p != q.
When writing constraint systems for many cryptographic proofs, we are restricted to a native field (e.g., the scalar field of the pairing-friendly curve). This can be inconvenient; for example, the recursive composition of proofs via cycles of curves requires the verifier to compute over a non-native field.
The library makes it possible to write computations over a non-native field in the same way one would write computations over the native field. This naturally introduces additional overhead, which we minimize using a variety of optimizations.
Usage
Because the non-native field implements the FieldVar trait in arkworks, we can treat it like a native field variable (FpVar).
We can do the standard field operations, such as +, -, and *. See the following example:
```rust
let a = NonNativeFieldVar::
// add let aplusb = &a + &b;
// sub let aminusb = &a - &b;
// multiply let atimesb = &a * $b;
// enforce equality a.enforce_equal(&b)?; ```
Advanced optimization
After each multiplication, our library internally performs a reduce operation, which reduces an intermediate type NonNativeFieldMulResultVar to the normalized type NonNativeFieldVar.
This enables a user to seamlessly perform a sequence of operations without worrying about the underlying details.
However, this operation is expensive and is sometimes avoidable. We can reduce the number of constraints by using this intermediate type, which only supports additions. To multiply, it must be reduced back to NonNativeFieldVar. See below for a skeleton example.
To compute a * b + c * d, the straightforward (but more expensive) implementation is as follows:
let a_times_b = &a * &b;
let c_times_d = &c * &d;
let res = &a_times_b + &c_times_d;
This performs two reduce operations in total, one for each multiplication.
We can save one reduction by using the NonNativeFieldMulResultGadget, as follows:
let a_times_b = a.mul_without_reduce(&b)?;
let c_times_d = c.mul_without_reduce(&d)?;
let res = (&a_times_b + &c_times_d)?.reduce()?;
It performs only one reduce operation and is roughly 2x faster than the first implementation.
Inspiration and basic design
The library employs the standard idea of using multiple limbs to represent an element of the target field. For example, an element in the TargetField may be represented by three BaseField elements (i.e., the limbs).
TargetField -> limb 1, limb 2, and limb 3 (each is a BaseField element)
After some computation, the limbs become overwhelmed and need to be reduced, in order to engage in more computation.
We heavily use the optimization techniques in [KPS18] and [OWWB20]. Both works have their own open-source libraries: xJsnark and bellman-bignat. Compared with them, this library works with the arkworks environment and is also optimized for density instead of number of constraints, which is useful for holographic zero-knowledge proofs like Marlin.
License
The library is licensed under either of the following licenses, at your discretion.
- Apache License Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
Unless you explicitly state otherwise, any contribution submitted for inclusion in this library by you shall be dual licensed as above (as defined in the Apache v2 License), without any additional terms or conditions.
References
[KPS18]: A. E. Kosba, C. Papamanthou, and E. Shi. "xJsnark: a framework for efficient verifiable computation," in Proceedings of the 39th Symposium on Security and Privacy, ser. S&P ’18, 2018, pp. 944–961.
[OWWB20]: A. Ozdemir, R. S. Wahby, B. Whitehat, and D. Boneh. "Scaling verifiable computation using efficient set accumulators," in Proceedings of the 29th USENIX Security Symposium, ser. Security ’20, 2020.
Owner
- Name: arkworks
- Login: arkworks-rs
- Kind: organization
- Website: arkworks.rs
- Twitter: arkworks_rs
- Repositories: 25
- Profile: https://github.com/arkworks-rs
An ecosystem for developing and programming with zkSNARKs
GitHub Events
Total
- Fork event: 1
Last Year
- Fork event: 1
Committers
Last synced: about 3 years ago
Top Committers
| Name | Commits | |
|---|---|---|
| Weikeng Chen | w****k@b****u | 21 |
| Pratyush Mishra | p****a@b****u | 9 |
| Nicholas Ward | n****d@b****u | 2 |
| dependabot-preview[bot] | 2****]@u****m | 2 |
| Dev Ojha | V****n@u****m | 1 |
| William Lin | 3****4@u****m | 1 |
| Alex Ozdemir | a****r@h****u | 1 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 10 months ago
All Time
- Total issues: 10
- Total pull requests: 35
- Average time to close issues: 7 days
- Average time to close pull requests: 2 days
- Total issue authors: 6
- Total pull request authors: 7
- Average comments per issue: 1.8
- Average comments per pull request: 0.43
- Merged pull requests: 33
- Bot issues: 1
- Bot pull requests: 6
Past Year
- Issues: 0
- Pull requests: 0
- Average time to close issues: N/A
- Average time to close pull requests: N/A
- Issue authors: 0
- Pull request authors: 0
- Average comments per issue: 0
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- weikengchen (5)
- DanieleDiBenedetto (1)
- Will-Lin4 (1)
- Pratyush (1)
- jon-chuang (1)
- dependabot-preview[bot] (1)
Pull Request Authors
- weikengchen (20)
- dependabot-preview[bot] (6)
- Pratyush (5)
- ValarDragon (1)
- alex-ozdemir (1)
- npwardberkeley (1)
- Will-Lin4 (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- cargo 417,874 total
- Total docker downloads: 41
- Total dependent packages: 6
- Total dependent repositories: 39
- Total versions: 2
- Total maintainers: 1
crates.io: ark-nonnative-field
Constraints for nonnative field gadgets
- Homepage: https://arkworks.rs
- Documentation: https://docs.rs/ark-nonnative-field/
- License: MIT/Apache-2.0
-
Latest release: 0.3.0
published about 5 years ago
Rankings
Maintainers (1)
Dependencies
- ark-bls12-377 ^0.3.0 development
- ark-bls12-381 ^0.3.0 development
- ark-mnt4-298 ^0.3.0 development
- ark-mnt4-753 ^0.3.0 development
- ark-mnt6-298 ^0.3.0 development
- ark-mnt6-753 ^0.3.0 development
- ark-pallas ^0.3.0 development
- paste 1.0 development
- ark-ec ^0.3.0
- ark-ff ^0.3.0
- ark-r1cs-std ^0.3.0
- ark-relations ^0.3.0
- ark-std ^0.3.0
- derivative 2
- num-bigint 0.4.0
- num-integer 0.1.44
- num-traits 0.2
- tracing 0.1