Implement MemoSet. (#1004)

* Implement MemoSet. * Add len and cardinality to MultiSet. * Use expect_test. * Refactor. * Rename to format_to_string_simple. * Rebase/fix. * Make comments doc comments. * Handle missing value when synthesizing shape. * Add explanatory comments. * Abstract transcript. * Abstract CircuitTranscript. * Rename. * Remove superflous bound. * Always allocate query when synthesizing. * Remove dbg. * Add r() to Transcript. * Eliminate pesky T. * Add MemoSet module doc. * Move associated type from Query to CircuitQuery. * Be more generic. * One more Q. * Fix typo. * Grammar. * Remove redundant assert_eq. --------- Co-authored-by: porcuquine <[email protected]>
lurk-lab · Jan 11, 2024 · d9a54a6 · d9a54a6 · github-actions · Jan 11, 2024
1 parent 1751b93
commit d9a54a6
Show file tree

Hide file tree

Showing 8 changed files with 1,251 additions and 0 deletions.
diff --git a/.clippy.toml b/.clippy.toml
@@ -5,3 +5,4 @@ disallowed-methods = [
     { path = "pasta_curves::Fp", reason = "use pasta_curves::pallas::Base or pasta_curves::vesta::Scalar instead to communicate your intent" },
     { path = "pasta_curves::Fq", reason = "use pasta_curves::pallas::Scalar or pasta_curves::vesta::Base instead to communicate your intent" },
 ]
+allow-dbg-in-tests = true
diff --git a/src/circuit/gadgets/constraints.rs b/src/circuit/gadgets/constraints.rs
@@ -310,6 +310,28 @@ pub(crate) fn div<F: PrimeField, CS: ConstraintSystem<F>>(
     Ok(res)
 }
 
+pub(crate) fn invert<F: PrimeField, CS: ConstraintSystem<F>>(
+    mut cs: CS,
+    a: &AllocatedNum<F>,
+) -> Result<AllocatedNum<F>, SynthesisError> {
+    let inv = AllocatedNum::alloc(cs.namespace(|| "invert"), || {
+        let inv = (a.get_value().ok_or(SynthesisError::AssignmentMissing)?).invert();
+
+        let inv_opt: Option<_> = inv.into();
+        inv_opt.ok_or(SynthesisError::DivisionByZero)
+    })?;
+
+    // inv * a = 1
+    cs.enforce(
+        || "inversion",
+        |lc| lc + inv.get_variable(),
+        |lc| lc + a.get_variable(),
+        |lc| lc + CS::one(),
+    );
+
+    Ok(inv)
+}
+
 /// Select the nth element of `from`, where `path_bits` represents n, least-significant bit first.
 /// The returned result contains the selected element, and constraints are enforced.
 /// `from.len()` must be a power of two.

diff --git a/src/circuit/gadgets/pointer.rs b/src/circuit/gadgets/pointer.rs
@@ -132,6 +132,14 @@ impl<F: LurkField> AllocatedPtr<F> {
         &self.hash
     }
 
+    pub fn get_value<T: Tag>(&self) -> Option<ZPtr<T, F>> {
+        self.tag.get_value().and_then(|tag| {
+            self.hash
+                .get_value()
+                .map(|hash| ZPtr::from_parts(Tag::from_field(&tag).expect("bad tag"), hash))
+        })
+    }
+
     pub fn enforce_equal<CS: ConstraintSystem<F>>(&self, cs: &mut CS, other: &Self) {
         // debug_assert_eq!(self.tag.get_value(), other.tag.get_value());
         enforce_equal(cs, || "tags equal", &self.tag, &other.tag);
	`fib-ref=1751b93d8b9d22c4860b1183cac6db0967d8f0e8`	`fib-ref=d9a54a6b4d995d71de835a3785c6d7e449cf92af`
`num-100`	`1.73 s` (✅ 1.00x)	`1.73 s` (✅ 1.00x faster)
`num-200`	`3.33 s` (✅ 1.00x)	`3.32 s` (✅ 1.00x faster)
	`fib-ref=1751b93d8b9d22c4860b1183cac6db0967d8f0e8`	`fib-ref=d9a54a6b4d995d71de835a3785c6d7e449cf92af`
`num-100`	`1.95 s` (✅ 1.00x)	`1.94 s` (✅ 1.00x faster)
`num-200`	`3.34 s` (✅ 1.00x)	`3.33 s` (✅ 1.00x faster)