AtHeartEngineer/halo2
1
0
Fork 0
mirror of https://github.com/AtHeartEngineer/halo2.git synced 2026-01-09 20:48:02 -05:00
Code Issues Packages Projects Releases Wiki Activity
2,307 Commits 31 Branches 4 Tags
main
Commit Graph

2307 Commits

This Branch
This Branch
All Branches
Author SHA1 Message Date
therealyingtong
75b5c1e923 halo2_gadgets 0.1.0-beta.3 2022-04-06 12:28:36 +08:00
therealyingtong
a11cb9796e halo2_proofs 0.1.0-beta.4 2022-04-06 12:24:28 +08:00
str4d
95df0af86d Merge pull request #537 from zcash/fix-stack-overflow 
Reduce depth of AST by special casing the application of Horner's rule
 2022-04-04 23:13:30 +01:00
Sean Bowe
6a31a0e6a1 Apply @str4d's review suggestions. 2022-04-04 14:07:31 -06:00
Sean Bowe
fa069a7455 Use unwrap_or_default() instead of unwrap_or(HashMap::new()) 2022-04-03 10:06:19 -06:00
Sean Bowe
fd7e9ddbb0 rustfmt 2022-04-02 15:38:46 -06:00
Sean Bowe
4163b8765a Reduce depth of AST by special casing the application of Horner's rule. 
The existing code will fold together a very deep AST that applies Horner's
rule to each gate in a proof -- which could include multiple circuits and
so for some applications will quickly grow such that when we recursively
descend later during evaluation the stack will easily overflow.

This change special cases the application of Horner's rule to a
"DistributePowers" AST node to keep the tree depth from exploding in size.
 2022-04-02 13:13:46 -06:00
Jack Grigg
0946bdb455 dev: Enable VerifyFailure::Permutation to point to region offsets 2022-03-30 01:39:50 +00:00
therealyingtong
51d34c12a2 Bench heavily padded lookup in MockProver. 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2022-03-24 22:02:29 +08:00
str4d
406f622e33 Merge pull request #531 from zcash/release-0.1.0-beta.3 
Release `halo2_proofs 0.1.0-beta.3`
 2022-03-22 20:29:09 +00:00
Jack Grigg
11dcfb88ba halo2_gadgets 0.1.0-beta.2 2022-03-22 20:04:14 +00:00
Jack Grigg
8acd4abfb3 halo2_proofs 0.1.0-beta.3 2022-03-22 19:59:10 +00:00
Jack Grigg
e39c8e94d2 Update changelogs 2022-03-22 19:55:53 +00:00
str4d
8abd7b74db Merge pull request #417 from zcash/fix-assigned-usage 
Expand `Assigned<F>` APIs
 2022-03-22 19:46:51 +00:00
ying tong
084ecf185a Merge pull request #523 from zcash/therealyingtong-patch-1 
[book] Correct typo in Q_0 of protocol description.
 2022-03-18 12:56:36 +08:00
str4d
642efc1536 Merge pull request #521 from zcash/reconstruct-selectors 
Remove selector_map from pinned verification key and remove VerificationKey serialization
 2022-03-18 00:14:36 +00:00
str4d
31b68fab25 Merge pull request #524 from zcash/fix-docs-rs-build 
Fix docs.rs build
 2022-03-17 19:34:52 +00:00
Jack Grigg
c6b4fcaf34 Fix docs.rs build 
The published source code for each package needs to include the required
header file, and the path to that header file needs to be relative to
the package source (not the repository source). We therefore need to
have the header file present in each workspace package.

Closes zcash/halo2#506.
 2022-03-17 19:14:11 +00:00
Jack Grigg
d3f2980349 Remove VerifyingKey serialization from sha256 gadget benchmark 2022-03-17 18:58:53 +00:00
ying tong
2194973aa8 [book] Correct typo in protocol description. 
Co-authored-by: Daira Hopwood <daira@jacaranda.org>
 2022-03-17 21:35:06 +08:00
Sean Bowe
f46d77763e Remove logic for reading and writing VerificationKey to/from buffers. 2022-03-16 14:19:33 -06:00
Sean Bowe
819bc3c2f5 Stop placing the selector_map (which is an internal API detail) in the pinned verification key. 2022-03-16 14:19:13 -06:00
Sean Bowe
e10f4e1d0e Add mechanism for generating a new proof in test. 2022-03-16 12:53:04 -06:00
Daira Hopwood
b48b032041 Minor simplification 2022-02-16 17:14:41 +00:00
Jack Grigg
57596cab36 dev: Add a custom VerifyFailure::CellNotAssigned emitter 
The `dev::tests::unassigned_cell` test case, shown via `assert_eq!(err, Ok(()))`:
```
  left: `Err([CellNotAssigned { gate: Gate { index: 0, name: "Equality check" }, region: Region { index: 0, name: "Faulty synthesis" }, gate_offset: 1, column: Column { index: 1, column_type: Advice }, offset: 1 }])`,
 right: `Ok(())`',
```

Via `impl Display for VerifyFailure`:
```
Region 0 ('Faulty synthesis') uses Gate 0 ('Equality check') at offset 1, which requires cell in column Column { index: 1, column_type: Advice } at offset 1 to be assigned.
```

Via `VerifyFailure::emit`:
```
error: cell not assigned
  Cell layout in region 'Faulty synthesis':
    | Offset | A0 | A1 |
    +--------+----+----+
    |    0   | x0 |    |
    |    1   |    |  X | <--{ X marks the spot! 🦜

  Gate 'Equality check' (applied at offset 1) queries these cells.
```
 2022-02-16 13:57:53 +00:00
Jack Grigg
369ff521d3 dev: Store gate offset in VerifyFailure::CellNotAssigned 2022-02-16 13:57:53 +00:00
Jack Grigg
c19a1ade2a dev: Add a custom VerifyFailure::Lookup emitter 
The `dev::tests::bad_lookup` test case, shown via `assert_eq!(err, Ok(()))`:
```
  left: `Err([Lookup { lookup_index: 0, location: InRegion { region: Region { index: 2, name: "Faulty synthesis" }, offset: 1 } }])`,
 right: `Ok(())`',
```

Via `impl Display for VerifyFailure`:
```
Lookup 0 is not satisfied in Region 2 ('Faulty synthesis') at offset 1
```

Via `VerifyFailure::emit`:
```
error: lookup input does not exist in table
  (L0) ∉ (F0)

  Lookup inputs:
    L0 = x1 * x0 + (1 - x1) * 0x2
    ^
    | Cell layout in region 'Faulty synthesis':
    |   | Offset | A0 | F1 |
    |   +--------+----+----+
    |   |    1   | x0 | x1 | <--{ Lookup inputs queried here
    |
    | Assigned cell values:
    |   x0 = 0x5
    |   x1 = 1
```
 2022-02-16 13:56:17 +00:00
Jack Grigg
62eea4c457 dev: Move cell loaders into dev::util 2022-02-16 13:56:17 +00:00
Jack Grigg
44e3cf8c61 dev: Move expression stringifier into dev::failure::emitter 2022-02-16 13:56:17 +00:00
Jack Grigg
212e3d07ce dev: Move cell layout emitter into a submodule 2022-02-16 13:56:17 +00:00
Jack Grigg
8e1fb87a33 dev: Add a custom VerifyFailure::ConstraintNotSatisfied emitter 
An example failure, shown via `assert_eq!(err, Ok(()))`:
```
  left: `Err([ConstraintNotSatisfied { constraint: Constraint { gate: Gate { index: 0, name: "R1CS constraint" }, index: 0, name: "buggy R1CS" }, location: InRegion { region: Region { index: 0, name: "Example region" }, offset: 1 }, cell_values: [(VirtualCell { name: "", column: Column { column_type: Advice, index: 0 }, rotation: 0 }, "0x2"), (VirtualCell { name: "", column: Column { column_type: Advice, index: 1 }, rotation: -1 }, "0x4"), (VirtualCell { name: "", column: Column { column_type: Advice, index: 2 }, rotation: 1 }, "0x8")] }])`,
 right: `Ok(())`',
```

Via `impl Display for VerifyFailure`:
```
Constraint 0 ('buggy R1CS') in gate 0 ('R1CS constraint') is not satisfied in Region 0 ('Example region') at offset 1
- Column('Advice', 0)@0 = 0x2
- Column('Advice', 1)@-1 = 0x4
- Column('Advice', 2)@1 = 0x8
```

Via `VerifyFailure::emit`:
```
error: constraint not satisfied
  Cell layout in region 'Example region':
    | Offset | A0 | A1 | A2 |
    +--------+----+----+----+
    |    0   |    | x1 |    |
    |    1   | x0 |    |    | <--{ Gate 'R1CS constraint' applied here
    |    2   |    |    | x2 |

  Constraint 'buggy R1CS':
    S0 * (x0 * x1 + x2) = 0

  Assigned cell values:
    x0 = 0x2
    x1 = 0x4
    x2 = 0x8
```
 2022-02-16 13:56:17 +00:00
Jack Grigg
5cdc029bb4 dev: Add MockProver::assert_satisfied 
This is equivalent to `assert_eq!(mock_prover.verify(), Ok(()))`, but
pretty-prints the verification failures instead of debug-printing them.
In its initial state, it just prints the `Display` impl.
 2022-02-16 13:56:17 +00:00
Jack Grigg
0e08903669 dev: Move VerifyFailure and FailureLocation into submodule 2022-02-16 13:55:29 +00:00
str4d
c12620c598 Merge pull request #505 from zcash/ci-updates 
CI updates
 2022-02-16 13:54:19 +00:00
Jack Grigg
82bb4e6141 CI: Test against Windows and macOS in addition to Ubuntu 2022-02-15 23:35:11 +00:00
Jack Grigg
e2932427ed CI: Update codecov/codecov-action to v2.1.0 2022-02-15 23:34:43 +00:00
str4d
c63828b51a Merge pull request #504 from zcash/release-0.1.0-beta.2 
`halo2 0.1.0-beta.2` etc.
 2022-02-15 01:57:34 +00:00
Daira Hopwood
c5cdea1eb0 Merge pull request #487 from daira/book-improve-incomplete-addition 
Improve the explanation of incomplete addition
 2022-02-15 01:05:00 +00:00
Daira Hopwood
e7ffefdbe2 MockProver: Optimize repetitions of the last usable row, not the zero row. 
Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2022-02-15 00:30:54 +00:00
Daira Hopwood
7107b8353a MockProver: Use a sorted scan to check that lookup inputs 
are contained in the table, fixing a performance regression.
This includes an optimization for "fill rows", which are
assumed in this commit to be all-zeros.

closes #398

Signed-off-by: Daira Hopwood <daira@jacaranda.org>
 2022-02-14 23:54:06 +00:00
Jack Grigg
80953d02c2 halo2 0.1.0-beta.2 2022-02-14 22:03:40 +00:00
Jack Grigg
c9852c61ec halo2_gadgets 0.1.0-beta.1 2022-02-14 21:58:20 +00:00
Jack Grigg
f642727e51 halo2_proofs 0.1.0-beta.2 2022-02-14 21:58:20 +00:00
Jack Grigg
1d2f698aca Update license dates and links 2022-02-14 21:58:20 +00:00
Jack Grigg
e0cc7b39d3 Update changelogs 2022-02-14 21:29:42 +00:00
ebfull
247cd620ee Merge pull request #502 from zcash/simplify-ipa-equation 
halo2_proofs: change IPA check equation to match the book
 2022-02-14 11:17:11 -07:00
Sean Bowe
0b73c74f72 Address comments brought up by @str4d. 2022-02-14 10:44:14 -07:00
Sean Bowe
f2daf91315 halo2_proofs: change IPA check equation to match the book 
The verifier's check in the inner product argument used to assume that the
G'_0 value had an additional (trivial) blinding factor term, which makes
it slightly easier to reason that it never is the point at infinity.
However, we never sample challenges that are zeroes (both for security
and completeness reasons) so this element would never be the point at
infinity anyway. Thus, we can simplify the check with the added benefit of
matching the book's description of the protocol.
 2022-02-14 09:37:57 -07:00
ebfull
8c0deb10aa Merge pull request #495 from zcash/book-consistency 
halo2_proofs: rename variables for consistency
 2022-02-14 09:24:20 -07:00
str4d
552c5beb23 Merge pull request #501 from zcash/hardcoded-proof 
Add hardcoded proof to plonk_api test
 2022-02-14 16:07:52 +00:00