Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Circuit oram/adding linearity test #20

Conversation

wjuan-mob
Copy link
Contributor

@wjuan-mob wjuan-mob commented Mar 25, 2022

Adding measure_oram_stash_size_distribution function that returns stash size statistics
Adding tests for stash size independence with respect to oram size
Adding tests for stash size linear growth with respect to time.
Increases the size and timeout of tests in CircleCI to run these since otherwise it times out and runs out of memory.

These tests are generally useful for determining whether our Oram implementations are well behaved, and helps validate changes to our oram.

These tests are mimicking figures 3 and 4 in this paper: https://eprint.iacr.org/2013/280.pdf
The tolerances for the unit tests were increased far above what may appear normal in order to keep the CI runs under an hour. In order to achieve tolerance under .05 percent, it was necessary to increase the number of iterations over 2^25 which takes between 5 and 10 hours depending on the machine etc. Though optimizations could be made to parallelize runs if this is desired.
The choice to use variance instead of using the thresholding scheme used in the paper to test independence against N is because it seemed like a more intuitive metric for the unit test that would be more granular/sensitive to changes.

@wjuan-mob wjuan-mob marked this pull request as draft March 25, 2022 16:16
@wjuan-mob wjuan-mob changed the base branch from master to feature/CircuitOram April 27, 2022 16:01
@wjuan-mob wjuan-mob changed the base branch from feature/CircuitOram to master May 3, 2022 21:33
@wjuan-mob wjuan-mob changed the base branch from master to feature/CircuitOram May 3, 2022 21:33
@wjuan-mob wjuan-mob marked this pull request as ready for review May 4, 2022 19:01
@wjuan-mob wjuan-mob requested review from samdealy and cbeck88 May 4, 2022 19:01
no-asm-tests/src/main.rs Outdated Show resolved Hide resolved
no-asm-tests/src/main.rs Outdated Show resolved Hide resolved
no-asm-tests/src/main.rs Outdated Show resolved Hide resolved
@samdealy
Copy link

samdealy commented May 4, 2022

Nice work, thanks for meeting to go more in depth!

@wjuan-mob wjuan-mob merged commit ba6de90 into mobilecoinfoundation:feature/CircuitOram May 9, 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
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants