Circuit oram/dependency inject evictor #37
Merged
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Co-authored-by: Nick Santana <nick@mobilecoin.com>
Co-authored-by: Nick Santana <nick@mobilecoin.com>
…ram/DependencyInjectEvictor
…ram/DependencyInjectEvictor
…n-mob/mc-oblivious into CircuitOram/DependencyInjectEvictor
… tree_size, internal_tests, and evict_creator
Co-authored-by: Nick Santana <nick@mobilecoin.com>
…n-mob/mc-oblivious into CircuitOram/DependencyInjectEvictor
Co-authored-by: Nick Santana <nick@mobilecoin.com>
…ranches to evict.
…tOram/DependencyInjectEvictor
nick-mobilecoin
approved these changes
Sep 8, 2022
wjuan-mob
added a commit
that referenced
this pull request
Oct 11, 2022
* Adding stash_size function for diagnostics (#19) * Adding stash_size function for diagnostics * Adding stash_size function for diagnostics * Circuit oram/adding linearity test (#20) * Adding stash_size function for diagnostics * Adding linearity test and analysis test * Adding stash_size function for diagnostics * Adding linearity test and analysis test * Fixing conditional compilation * Catching panic so we get results even when stash overflows * Fixing error in stash size metric. Inverted * Refactor tests to no_asm crate * adjust fudge factor * updating circle ci config to add gsl for no-asm-test * Increasing timeout and decreasing runtime to get test to complete * increasing timeout * Using cfg debug to reduce logging for normal test run, and cargo fmt * reducing the number of stash sizes we test to get ci to pass * reducing the number of runs to get ci to pass * Increasing the size of container and adding oom logging to circleci * Typo in xlarge, remove grep in dmesg * removing debugging lines * remove unintended line removal in lib.rs * Removing unintended comment change * lint * increasing stash sizes tested to see if possible with xlarge * renaming expected_ent to expected_entry for clarity * more precise nomenclature * Refactor commonly used oram access pattern * rename and add const * add underscore to unused variable * Circuit oram/refactor path oram (#24) * Adding stash_size function for diagnostics * Adding linearity test and analysis test * Refactoring path oram * Cargo fmt * Adding stash_size function for diagnostics * Adding linearity test and analysis test * Refactoring path oram * Cargo fmt * Fixing conditional compilation * Catching panic so we get results even when stash overflows * Fixing error in stash size metric. Inverted * Refactor tests to no_asm crate * adjust fudge factor * updating circle ci config to add gsl for no-asm-test * Increasing timeout and decreasing runtime to get test to complete * increasing timeout * Using cfg debug to reduce logging for normal test run, and cargo fmt * reducing the number of stash sizes we test to get ci to pass * reducing the number of runs to get ci to pass * fix lint * fix merge * Remove unintentional changes * whitespace * remove unused cfg attribution * Circuit oram/no asm lint (#35) * Clean up lint in no asm * Adding lint for no-asm in circle ci * Add workspace to no-asm-tests to address missing workspace issue * Move Evictor to its own module (#36) * Move Evictor to its own module * Adding clarifying information for the Evictor module * Fix formatting of use statements * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Switch to newer module file format/naming convention Co-authored-by: Nick Santana <nick@mobilecoin.com> * Circuit oram/dependency inject evictor (#37) * Move Evictor to its own module * Adding clarifying information for the Evictor module * Refactor path_oram to take an evictor creator and add deterministic evictor * Add clarifying comments, Shortcut deterministic get next branch to avoid overflow * Fix formatting of use statements * Add clarification around deterministic get next branch to evict * Remove dead code * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Remove empty spaces from use statements to allow fmt to collapse them properly * Fix accidental delete of imports in previous commit * Clarify comments about reverse lexicographic order * Clarify tree size vs tree depth * Remove size parameter from EvictorCreator and rename num_bits_needed, tree_size, internal_tests, and evict_creator * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Rename evict to evictor * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Format evictor. * Add backticks around input variable names * Add clarifying comment on why path oram does not require additional branches to evict. * Refactor evictor/mod.rs to evictor.r * Update no-asm test for rename of evict-> evictor Co-authored-by: Nick Santana <nick@mobilecoin.com> * Circuit oram/add prepare deepest and target (#38) * Move Evictor to its own module * Adding clarifying information for the Evictor module * Refactor path_oram to take an evictor creator and add deterministic evictor * Add clarifying comments, Shortcut deterministic get next branch to avoid overflow * Add crate level permissions to elements of path_oram to be used by the evictor * Add prepare deepest and prepare target with associated tests * Reformat prepare deepest for clarity * Fix formatting of use statements * Add clarification around deterministic get next branch to evict * Remove dead code * Switch try_from u64 to as 64 * Add a fixed data test for prepare_deepest and prepare_target in addition to the random test * Add clarifying comment for prepare deepest/target fixed test * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Remove empty spaces from use statements to allow fmt to collapse them properly * Fix accidental delete of imports in previous commit * Clarify comments about reverse lexicographic order * Clarify tree size vs tree depth * Remove size parameter from EvictorCreator and rename num_bits_needed, tree_size, internal_tests, and evict_creator * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Rename evict to evictor * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Format evictor. * Add backticks around input variable names * Add clarifying comment on why path oram does not require additional branches to evict. * Refactor evictor/mod.rs to evictor.r * Update no-asm test for rename of evict-> evictor * Apply suggestions from code review Co-authored-by: Nick Santana <nick@mobilecoin.com> * Fix test after suggestions * Remove unneeded type specification. * Remove unneeded mut * Fix error in helper function for test code of prepare deepest * Lint and remove unneeded mut * Update prepare deepest to return a vector instead of taking a mutable slice. * Update prepare target to return a vector instead of updating a mutable slice. * Update test deepest and test target non oblivious code to return vectors instead of modifying slices * Remove redundant run_with_several_seeds in fixed tree test * Add clarifying comment about why we test elements for vacancy, and corresponding test. * Remove erroneous line from test non oblivious prepare target that caused it to unset an intended target. * Refactor test Prepare deepest for additional clarity by moving the iteration over each bucket into a separate function. * Add clarifying comments around height. * Add test from paper, written by Nick * Remove print statements for testing to reduce excessive bloat in logs. * Add test verifying that when 2 elements are going to the same destination, prepare deepest takes the one closer to the root. * Lint * Clean up comments. * Capitalize ORAM in some comments. * Update mc-oblivious-ram/src/evictor.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Apply suggestions from code review Co-authored-by: Nick Santana <nick@mobilecoin.com> Co-authored-by: Nick Santana <nick@mobilecoin.com> * Circuit oram/add oblivious circuit oram v2 (#39) * Move Evictor to its own module * Adding clarifying information for the Evictor module * Refactor path_oram to take an evictor creator and add deterministic evictor * Add clarifying comments, Shortcut deterministic get next branch to avoid overflow * Add crate level permissions to elements of path_oram to be used by the evictor * Add prepare deepest and prepare target with associated tests * Reformat prepare deepest for clarity * Fix formatting of use statements * Add clarification around deterministic get next branch to evict * Remove dead code * Switch try_from u64 to as 64 * Add a fixed data test for prepare_deepest and prepare_target in addition to the random test * Add clarifying comment for prepare deepest/target fixed test * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Remove empty spaces from use statements to allow fmt to collapse them properly * Fix accidental delete of imports in previous commit * Clarify comments about reverse lexicographic order * Clarify tree size vs tree depth * Remove size parameter from EvictorCreator and rename num_bits_needed, tree_size, internal_tests, and evict_creator * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Rename evict to evictor * Update mc-oblivious-ram/src/evictor/mod.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Format evictor. * Add backticks around input variable names * Add clarifying comment on why path oram does not require additional branches to evict. * Refactor evictor/mod.rs to evictor.r * Update no-asm test for rename of evict-> evictor * Apply suggestions from code review Co-authored-by: Nick Santana <nick@mobilecoin.com> * Fix test after suggestions * Remove unneeded type specification. * Remove unneeded mut * Fix error in helper function for test code of prepare deepest * Lint and remove unneeded mut * Update prepare deepest to return a vector instead of taking a mutable slice. * Update prepare target to return a vector instead of updating a mutable slice. * Update test deepest and test target non oblivious code to return vectors instead of modifying slices * Remove redundant run_with_several_seeds in fixed tree test * Add clarifying comment about why we test elements for vacancy, and corresponding test. * Remove erroneous line from test non oblivious prepare target that caused it to unset an intended target. * Refactor test Prepare deepest for additional clarity by moving the iteration over each bucket into a separate function. * Add clarifying comments around height. * Add test from paper, written by Nick * Remove print statements for testing to reduce excessive bloat in logs. * Add test verifying that when 2 elements are going to the same destination, prepare deepest takes the one closer to the root. * Lint * Clean up comments. * Capitalize ORAM in some comments. * Update mc-oblivious-ram/src/evictor.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Apply suggestions from code review Co-authored-by: Nick Santana <nick@mobilecoin.com> * Add circuit ORAM evictors and creators * Add tests for CircuitOram: santity tests, exercise tests, analysis test. * Update rust toolchain to 4-29 for consistency with main repo * Remove std crate from testing. This is actually part of the api and therefore imports std into the mc-traits crate. * Apply suggestions from code review Co-authored-by: Nick Santana <nick@mobilecoin.com> * Remove unneeded mutability. * Rename variable for clarity. * Rename variable for brevity. * Minor optimization of drop held item to no longer vacate held item. * Simplify bucket access. * Minor optimization, move temporary variable allocation outside of loop. * Rename variables to abstract away underlying. * Simplify array access. * Refactor take_block_if_appropriate. * Rename variable for clarity. * Rename index_of_deepest_block_from_bucket and remove unused return. * Update mc-oblivious-ram/src/evictor.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Add test for take block if appropriate. * Refactor index of deepest to use branch and reorder to resolve immutable/mutable issue. * Refactor prepare_branch_from_buckets into duplicated test helper. * Refactor out destination_leaf_for_bucket * Add test for index of deepest from bucket. * Add clarifying comment to test for linearity. * Refactor test per Nick to use Parametrized yare test and better capture the meta_is_vacant case. * Update mc-oblivious-ram/src/evictor.rs Co-authored-by: Nick Santana <nick@mobilecoin.com> * Revert "Merge branch 'UpgradeRustVersion' into CircuitOram/AddObliviousCircuitOramV2" This reverts commit f68e826, reversing changes made to f3744a9. Co-authored-by: Nick Santana <nick@mobilecoin.com> Co-authored-by: Nick Santana <nick@mobilecoin.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The motivation for this PR is to let Path_oram use multiple different kinds of evictors.
This PR:
This PR is part of the following PR chain
This is a clone of wjuan-mob#7 that is pointing at the appropriate base.