Previously, the traversal stack held (node, children queued) pairs.
When visiting a node without it's children queued, we would queue them
all. They take a lot of memory!
Now, the stack holds children iterators.
Also: this patch fixes many bugs introduced by the prior one.
For memories with constant values that have sorts which are linear
groups, there is a way to optimize linear-scan memory-checking.
This patch implements that optimization.
This started as an optimization patch, but my first optimization
revealed a bug. In chasing the bug, I found more optimization.
Changes:
1. Eliminate tuples in preprocessing. (opt)
2. Handle CStore in tuple elimination pass. (bugfix)
3. Use tuples instead of arrays in a few more extension ops: (opt)
* GCD for vanishing polynomials and their derivatives
* sorting in transcript checking
4. A few logging revisions
This allows folks to use the RAM machinery while sticking with (non-interactive) R1CS output.
We're going to need this anyway when we benchmark our new approach.
* r1cs: fix boolean majority
for m = majority(a,b,c),
we were lowering
(-ab + bc + ac - 2abc)
instead of
(ab + bc + ac - 2abc)
Whoops! This is a functional correctness bug: we were lowering
soundly and completely, for the wrong specification.
Credit to Anna for raising the issue!
* add test_sha256 (commented out b/c it is slow)
* fmt + lint
To reduce CI build time:
- Replaced ABY dependency with corresponding binary.
- Removed dependencies on KaHIP and KaHyPar for now because these dependencies aren't used upstream.
Minor updates:
- Updated ABY source to Public branch
Note:
- The aby_interpreter binary will only work on Linux. We can rebuild the binary from this repo.
A basic implementation of committed witnesses & volatile RAM extraction in the Z# front-end.
The passes in question are still a bit brittle, so I left them behind a flag.
- Upgraded ci pipeline to [v3](https://github.com/actions/cache/blob/main/README.md)
- Included installation and build scripts for KaHIP and kahypar in driver.py
- Used absolute paths for caching in ci pipeline (relative paths don't work).
Average ci time brought down from 15 minutes to 8 minutes!
Adds:
an implementation of the Mirage proof system
generalized to multiple round of interaction
a notion of rounds for variables
a notion of randomness for variables
to the R1CS layer:
committed witnesses
rounds
new witness computation machinery (to support multiple rounds)
The first bug is a disagreement between our bellman circuit and our bellman
verify function. The circuit omit unused variables (public or private). The
verify function includes unused public variables.
Now, the circuit includes unused public variables.
The second bug is related to large BV comparisons. The fix is to emit a
bitwise comparator. We could optimize further in the future.
closes#125
* Configuration system. Kill DFL_T
* add circ::cfg::CircCfg that holds cfg info
* it's constructible from circ_opt::CircOpt
* implements clap::Args, so you can set it from your compiler's
CLI/envvars
* defined in external crate to keep clap out of our main build
* organized by circ module, but not feature gated
* no point: the build wouldn't meaningfully change
* includes a way to set the default field
* added circ::cfg::set and circ::cfg::cfg
* also circ::cfg::set_default and circ::cfg::set_cfg
* access a sync::once_cell, static configuration
* killed DFL_T
* workflows
* unit-tested component probably need to not read circ::cfg::cfg.
* compilers need to call circ::cfg::set or circ::cfg::set_default.
* rm dead features
Updated MPC unit tests to use function abstractions. Most of these updates are made to the C frontend and MPC lowering pass. Additional optimization and ILP solving passes need to be updated.
The assignment and cost model passes now need to factor in Array and Tuple semantics. This requires changes to the CostModel assignments. This also requires the the def-use-graph implementation for constant-index propagation.
Work-around:
- disabled HyCC benchmark tests
- disabled tests that use Op::Select / Op::Store
We received a benchmark from Lef which essentially checked the
following:
(cond ? A*B : A*C)[i] == v
where A, B, C are 4 by 4 matrices, cond is a bool, i is an index, and v
a value.
The expected number of constraints is n^3: order 64 , but compile time
and constraint count were in the thousands.
I investigated finding a number of things:
* the Z# front-end entered a conditional branch for the ternary, causing
the MM to happen in a conditional context
* while the MM has an oblivious access pattern, since `i` is variable,
the oblivious pass wasn't really helping
* there were some weird non-constant indices floating around like
(ite cond 0 0)
The three optimizations fix these problems:
* If the Z# frontend isn't in assertion isolation mode, don't enter a
conditional branch for an ITE
* Constant folding: add the rewrite (ite cond a a) -> a
* Linear-scan array eliminator: for each operation, check if the index
is constant. If so, skip the scan (for that access only)
* update TODO
* add quiet mode to zxc
* Drop and garbage collection
This commit adds Drop instances and related functionality that force
garbage collection at life cycle end of various structs that contain
Terms.
I didn't implement Drop for Computation because its Terms are generally
moved into a converter. This means that back-ends are responsible for
garbage collecting (see new functionality in ILP, R1cs, and ABY).
* collect the cfold table, too
* prevent double-panic as a result of garbage_collect()
* z# parser: zx is a default extension too
* update Cargo.lock
* strictness un-op #()
also added err messages for asserts and ?: ternary support from ZoK upstream
* for assignments, strict rhs => strict lhs
* zsharp: type definitions WIP
Still missing monomorphization.
* type defns: generic inference
* struct monomorphization for type aliased structs
* different approach: no monomorphization, just canonicalize aliases
* canonicalize struct names
* typedef tests
things work except that importing an alias and not its referent breaks typechecking
* add error message about needing to import referent structs
* update hashconsing pointer in Cargo.toml
* maybe_garbage_collect should also return early when panicking
Co-authored-by: Alex Ozdemir <aozdemir@hmc.edu>
This PR does two things:
- Fixes some scoping issues in Z# having to do with the context in which function and struct definitions are interpreted.
- Improves speed and reduces TermTable memory consumption by 2x (by keying on Arc<TermData> rather than TermData)
- Improves speed for Z# array handling with a BTreeMap -> HashMap swap
- Adds intrinsic widening casts in Z#. These were previously handled by bit-splitting, which is wasteful.
On array-heavy Z# programs, this PR improves speed by about 5x and memory consumption by roughly the same.
---
* zsharp::term::ir_array should use HashMap (faster, less memory)
* perf improvements
constant folding: get rid of redundant clones
bitvector: impl arith for refs
TermTable: don't store redundant term as key
* EMBED widening casts
* generic inf: need to push fn defn context onto filestack
* canonicalize path in err msg
* need struct defn on filestack, too
* no need to warn about U32 indexing in zsharp
* fix warning
* macos deps script (broken on M1 for now)
* arch dep should be coin-or-cbc
* ZoK 0.7.6 support megat status-commit
- bring in ZoK 0.7.6 libraries
- port in diffs from old thirdparty
- first-cut const and literal support
- add toposort for includes so that we can resolve const values in next pass
- statement handling, include-walking fix
- type should cover u64 case, too
- structs: store for now
- const handling
- flatten import map up-front to make later derefs easier to handle
- stash note
- need array consts, too
- rough in const array support, I think
- error message
- small cleanups: change type of ZGen::constants and make comments more meaningful
- generics in fn calls
- small: better error message
- need to resolve exprs as const in const_type_
- wip simple typing pass
- ast visitor wip
- zokrates ast visitor 1st cut
- double check that we cover all product types
- const typing visitor ; visitor error handling
- reorg visit_files ; unification infra wip
- unification infra wip
- need to walk accesses for an assignment
- walk_accesses wip
- small q
- refactor: data structs should be Hash(Hash), not flat
- walk_accesses wip
- monomorphize structs on LHS of declarations
- check identifiers when monomorphizing structs
- unification wip
- unification wip
- inline struct members must declare all fields
- unification for array_initializer
- unify postfix
- unify fdef with call
- ZExpressionTyper wip
- ZExpressionTyper wip
- ZExpressionTyper first cut
- type equality first cut
- type equality improved
- update struct handling
- stash note
- zok_fe trivial
- error msg fix
- params in scope during stmt visiting
- stash note
- and_then rather than unwrap in flatten_import_map
- handle special names (e.g. EMBED) in toposort
- types for EMBED
- EMBED is now a valid file in stdlib
- rewriter should handle Types, too
- need to rewrite literals on LHS of def stmts
- iteration: fix type of iter var
- for now, allow indexing with both Field and u*
- add warning for indexing with Field
- impl pow
- don't add ITE when unconditionally assigning
- oops, Uint takes bv_lit not pf_lit
- simplify
- fix arg order to bv_lit, improve new_<integral> functions
- use constant folding for term::const_int
- EMBED rework wip
- EMBED rework wip
- EMBED rework wip
- EMBED rework wip
- EMBED rework wip
- prep for generic inf push
- generic inf wip
- generic inf wip
- generic inf wip
- struct generic inference
- struct array inference wip
- make const_expr_ return Result<> rather than blowing up
- finish first-cut generic inf for Array
- turn on fn generic inf
- rework struct monomorphization code
- add support for const asserts
- process declarations lexically
previously we'd processed all consts, then structs, then fns.
now we want to add const initialization via function call,
which is easiest to implement if we simply process declarations
in-order as they appear in the file and require that all uses
follow defs lexically.
This seems to rule out mutual recursion, so we may want to revisit.
- add const initialization via ternary
- const fn call wip
- ZGen interior mutability
this lets us call expr, const_expr_ without mut ref.
this seems to be the right way to go here.
- small touches after rebase
- reorganize zvisit code
- generic lookup: should go through whole stack! (and not panic if stack is empty)
- wip bugfixes
- const_identifier_ should consult generics ; generic_lookup shouldn't traverse the whole stack
- expr type inf for array accesses
- small
- const_stmt_ infra
- const_stmt_ most var infra in place
- cvar_assign handles AssigneeAccesses now
- split type_ and const_type_ using const generics
- cvar_assign: build up list of accesses before resolving them, so that we don't try to double-borrow cvars_stack
- interpreter intf
- zoki --- zok interpreter front-end
- const_expr direct access vs through term impl
- very quick zsharp readme
- feature gate ILP back-end
this makes it easier to build CirC on M1 macs (otherwise,
need to build coin-or from source, which is not hard but
is annoying)
- rename zokrates to zsharp
- heavy hitting stuff here
- update z# readme
- turn off ci for zsharp branch
- small
- add cfg to switch to bn254 curve
- zsharp readme quick
- struct consts
- handle literals on LHS of const decls
- typechecker: ! can take U*, too
- refactor typechecking in InlineStructExpression handling, const_eexpr_ (this is going to move, though)
- support inline structs in ZConstLiteralRewriter
- really turn of ci this time, don't just induce a failure
- don't build circ or opa_bench examples when 'lp' option is off ; fix example builds given renamed zokrates module
- unify_inline_array: respect array dims!
- better InlineArray len handling
- check fn return type
- small, plus a few tiny test cases
- redefinition is an error
- update thinking / status on uglinesses
- explicit generic literals are U32
- remove redundant typechecking in InlineStruct const expr handling
- array and struct equality
- generic-in-generic const test
- inline array and struct generic tests
- small
- sticky notes
- stash note
- small cleanup in zstmtwalker
- support ZSHARP_STDLIB_PATH envvar in ZStdLib
- get_field_size in EMBED ; field comparisons
- test runner
- hex literal fix
- inconsistent array test
- literals test
- TODO quick update
* generic inf refactor wip
* generic inf refactor
- keep plugging away at revamped generic inference
- generic inf refactor wip
- generic inf rework wip
- stash note about divrem
- generic inf wip
- build up one term rather than a vec; walk struct members; remove old crap
- small
- generic inf rework wip
- generic inf refactor wip
- partially hook up new generic inf
- zgenericinf: invoke solver, return result
- ZGenericInf hooked up
- stash a note
- find_unique_model function
- enable incremental mode for find_unique_model
- hook up find_unique_model in zgenericinf
* go over TODOs and small cleanup
* field %
- field to bv should use full width
- need to make sure MSB is 0 when lowering to R1CS\!
* update todos
* unify const and non-const code paths
- unify function_call and const_function_call
- unify stmt and const_stmt
- type_impl_ returns Result<>
- unify expr and const_expr
* update TODO
* rework after rebase
* fix circ example and clippies
* constant folding for array select and store
* cfold: Tuple and extend Eq
* more informative generic params error message in function call
* array accesses should be Field if not otherwise typed
* support Uxx array indexing (automatic type coercion) ; check array index and value for consistency
* tuple const folding
* stash note about array construction
* todos
* more todos
* IR tuple repr: use boxed slices rather than vecs
this enforces the invariant that tuple lengths cannot be changed
closes#39
* IR tuple typing checks
the value in a given tuple slot has a fixed type.
this invariant isn't fully captured right now---it's
up to front- and back-ends to enforce this.
[ EDIT: I think the above is wrong. `ir::term::ty::rec_check_raw`
appears to enforce this. ]
I've added a couple extra safety checks for this.
* todo update
* const fold bvconcat and booltobv
* IR array key_sort and bounds checks
* array oob todos / tests
* ZGenericInf early exit for monomorphized calls
* self.unwrap cleanup
* cache generic inference results
* small debug/assert
* array construction optimization
when constructing an array, push leaf terms directly into the array
rather than building up a huge term. This reduces memory pressure and
reduces constant folding cost in the (common) case of large const
arrays
* todos
* clippy
* bit order consistency fix / tests
to_bits and from_bits functions use msb0 ordering
(i.e., index 0 of the bool array is the MSB)
* clippy small
* update TODOs
* clippy for zsharp frontend
* cargo fmt ; pretty-printing T
* add span for error context in expr and stmt
* update TODOs
* add s_divisible and s_remainder in 'field' in stdlib
* comment on signed field fns
* superfluous front-end example
* zxi unused imports
* zxc first cut
* zxc: in count mode, dump out constraints
* sidestep stack blowup in ir::term::ty::check_raw
* add option to skip linearity reduction in zxc with -L
* debug messages... darn
* lru caching for cfold
* unbounded/bounded cache
unbounded during a single fold_cache call, bounded between
* rebase fixes
feature gate aby back-end with lp
changes in zxi/zxc, and some clippies
* don't check-in non-top-level Cargo.lock
* increase LRU cache size for cfold to avoid n^2 behavior
* heuristic term/type cache collector
* tidy
* fmt
* small bugfix
* small fixes ; move zx_tests
* re-enable ci
* fmt
* tentative obliv-fix
* more obliv-fix
* clippy (for tests)
* Polish the obliv fix a bit. Document
* Addressing my unsolicited comment
* fix build
* typo
* stash Alex's idea about modeling RAM transformations
* back to upstream hashconsing
Co-authored-by: Alex Ozdemir <aozdemir@hmc.edu>
Co-authored-by: Riad S. Wahby <rsw@jfet.org>
Co-authored-by: Alex Ozdemir <aozdemir@hmc.edu>
