changeset 790:5525b9b98415

Imported documentation from viff.dk repository. The exact order and placement of the files in the document tree is very much up for debate -- I just wanted to include them somewhere. Feel free to edit and rearrange things in better ways.
author Martin Geisler <mg@daimi.au.dk>
date Mon, 26 May 2008 22:16:45 +0200
parents 2f1b9576d413
children c7afb6fcc418
files doc/bibliography.txt doc/coding-style.txt doc/development.txt doc/implementation.txt doc/index.txt doc/presentations.txt doc/unit-testing.txt
diffstat 7 files changed, 605 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/bibliography.txt	Mon May 26 22:16:45 2008 +0200
@@ -0,0 +1,56 @@
+.. -*- coding: utf-8 -*-
+
+==============
+ Bibliography
+==============
+
+.. note::
+
+   This list is far from complete. If you find more relevant
+   references then please `send us a mail`__ with the information.
+
+   .. __: mailto:viff-devel@viff.dk
+
+The algorighms used by VIFF are published in various academic papers.
+Here we will try to point out which parts of the code uses which
+papers.
+
+* The ``viff.shamir`` module is obviously based on [Shamir79]_.
+
+*  ``apps/millionaires.py``: Inspired by [Yao82]_.
+
+* The default comparison operation (``Runtime.greater_than_equal``) is
+  based on the comparison protocol from [Toft05]_.
+
+* Broadcast (``Runtime.broadcast``) is based on the original paper by
+  [Bracha84]_ and on the explanation by [Cachin05]_.
+
+* The pseudo-random secret sharing (PRSS) in ``viff.prss`` is
+  described in [CDI05]_.
+
+
+.. [Bracha84] G. Bracha, *An asynchronous [(n-1)/3]-resilient
+   consensus protocol*, Proc 3rd ACM Symposium on Principles of
+   Distributed Computing (PODC), 1984, 154-162.
+
+.. [Cachin05] Christian Cachin, *Security and Fault-tolerance in
+   Distributed Systems*, ETHZ, 2005, PDF__.
+
+   .. __: http://www.zurich.ibm.com/~cca/sft05/agreement.pdf
+
+.. [CDI05] Ronald Cramer, Ivan Damgård, and Yuval Ishai, *Share
+   Conversion, Pseudorandom Secret-Sharing and Applications to Secure
+   Computation*, Proc of TCC 2005, LNCS 3378, PS__.
+
+   .. __:  http://www.cs.technion.ac.il/~yuvali/pubs/CDI05.ps
+
+.. [Shamir79] Adi Shamir, *How to share a secret*, Communications of
+   the ACM, 22 (11): 612-613.
+
+.. [Toft05] Tomas Toft, *Secure Integer Computation with Applications
+   in Economics*, PhD Progress Report, July 2005, PDF__.
+
+   .. __: http://www.daimi.au.dk/~tomas/publications/progress.pdf
+
+.. [Yao82] Andrew Chi-Chih Yao, *Protocols for Secure Computations*,
+   FOCS 1982, 160-164.
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/coding-style.txt	Mon May 26 22:16:45 2008 +0200
@@ -0,0 +1,62 @@
+.. -*- coding: utf-8 -*-
+
+===================
+ VIFF Coding Style
+===================
+
+The VIFF code tries to follow the coding style laid out in `PEP 8`_,
+which you should read or at least skim over. You can check your code
+against by running the pep8.py_ checker.
+
+.. TODO: change PEP 8 link into using the :PEP:`8` role when Sphinx
+.. doesn't crash on it anymore. See
+..
+..   http://groups.google.com/group/sphinx-dev/msg/bc99090aa52b87af
+..
+.. for the bug report.
+
+.. _PEP 8: http://www.python.org/dev/peps/pep-0008
+.. _pep8.py: http://svn.browsershots.org/trunk/devtools/pep8/pep8.py
+
+
+The VIFF Coding Style in Short
+------------------------------
+
+A summary of the rules:
+
+* Use four spaces for indention, never tabs.
+
+* Use a single space around binary operators.
+
+* Name classes using ``CamelCase``.
+
+* Name variables, function, and methods using lowercase words like
+  ``foo_bar``.
+
+* Write docstrings for your functions and methods. Include test for
+  doctest_ if possible.
+
+  .. _doctest: http://docs.python.org/lib/module-doctest.html
+
+* Try to be consistent.
+
+These rules are there to make the source code more readable for both
+old and new people.
+
+The Twisted Coding Style
+------------------------
+
+VIFF uses Twisted_ and their code follows a slightly different coding
+style. Their style is closer to the style used in Java where functions
+and methods are named ``fooBar`` instead of ``foo_bar``.
+
+When writing code which is close to Twisted code, you might want to
+follow that style too. If you subclass a Twisted class to override
+some behavior, you might be forced to follow their style.
+
+If you have a choice, then you should only use the Twisted style if
+you expect people to call both your code and the Twisted code — if
+people will only call your code, then please follow the standard VIFF
+coding style.
+
+.. _Twisted: http://twistedmatrix.com/
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/development.txt	Mon May 26 22:16:45 2008 +0200
@@ -0,0 +1,160 @@
+.. -*- coding: utf-8 -*-
+
+==================
+ VIFF Development
+==================
+
+This page explains what you need to know if you want to start hacking
+on VIFF. In addition to these instructions you will want to read up on
+the `coding style`_ used by VIFF (it is the normal Python style,
+nothing fancy there).
+
+.. _coding style: coding-style.html
+
+
+Getting the Source Code
+-----------------------
+
+VIFF is developed using Mercurial_ (also known as ``hg`` after its
+command line program). This is a distributed revision control system
+which allows you to participate fully in the development even if you
+do not have what is traditionally known as "commit access". You can
+also work offline and take advantage of the many fast operations
+offered by Mercurial.
+
+.. _Mercurial: http://www.selenic.com/mercurial/
+
+After installing Mercurial you can checkout a copy of the source using
+this command line::
+
+   hg clone http://hg.viff.dk/viff/
+
+This will create a directory called ``viff/`` where you will find the
+source code. Please test that VIFF works as expected on your computer
+by following the instructions on `unit testing`_.
+
+.. _unit testing: unit-testing.html
+
+
+Contributing Changes
+--------------------
+
+When you have created a new feature or fixed a bug, then you need to
+send your changes to one of the VIFF developers. If you share a file
+system with one of the developers, then the easiest way to get your
+changes back into VIFF is to ensure that one of the developers has
+read access on the repository files. He can then simply pull the
+changesets over and eventually push them out to the VIFF repository.
+
+Alternatively, you can setup a Mercurial repository where one of the
+developers can ``hg pull`` from. You can do this by uploading your
+clone on some public web server (any webserver works for this since
+the developers can pull using ``hg pull static-http://...``) or by
+running::
+
+   hg serve -p 8000
+
+which creates a web server on port 8000 just like the one running at
+http://hg.viff.dk/viff/. The default port number is 8000, so you can
+leave that out.
+
+A final option is the patchbomb_ extension for Mercurial, which will
+allow you to use::
+
+   hg email -t viff-devel@viff.dk -o
+
+to send the changesets not present in the VIFF repository (``-o``) to
+the VIFF development list (``-t viff-devel@viff.dk``). You will
+probably want to test using a ``-n`` flag or by sending the patches to
+your own address first to make sure everything looks okay. You can get
+the full list of options using ``hg help email``.
+
+.. _patchbomb: http://www.selenic.com/mercurial/
+                      wiki/index.cgi/PatchbombExtension
+
+The advantage of using patchbomb is that allows everybody to go over
+the code and comment on it before the changesets are pulled into the
+repository. The mails sent out by patchbomb contain all the metadata
+needed (name of committer, date, parent changeset, etc.) for importing
+the changes into the repository, just as if the changesets had been
+pulled using ``hg pull``.
+
+
+Revising Changes
+----------------
+
+When developing your changes you will probably make many commits
+representing contained steps. Even though you have made a commit, you
+can still change it *as long as you have not shared it with anybody*.
+The idea is that you are allowed to rewrite history as you see fit in
+your own private repository, but if your changes have been pulled to
+the outside, then you can no longer change them.
+
+Also, you can only change commits in a linear history back from your
+repository tip. This means that if you pull in changes from the main
+VIFF repository and merge them periodically, then you can no longer
+edit changesets past the last merge. We therefore recommend that you
+develop your feature until you are satisfied with it and only merges
+with whatever new changesets there might be in the VIFF repository
+when the feature is done and debugged.
+
+Now, to change a past commit you use the `Mercurial Queues extension`_
+also known as MQ. It gives you a powerful set of tools to work with
+the past history. The basic concept is that changesets can be
+converted into patches, which depend on each other and form a stack.
+Like any good stack, you can push and pop elements from it. In this
+case you push and pop patches.
+
+To get started you will want to import the normal changesets into MQ.
+Let us suppose you found an error in revision 430 (use ``hg view`` or
+``hg log`` to find the revision numbers). You then want to import
+revision 430 and the following changesets into MQ with this command::
+
+   hg qimport -r 430:tip
+
+Nothing much happened — your working directory is left unchanged. To
+see that the command did something you can check the current patch
+series with ``hg qseries``. When importing changesets revision N is
+called ``N.diff`` in the patch series.
+
+What we want is to pop off the other patches so that ``430.diff`` is
+the topmost patch. This is done with::
+
+   hg qgoto 430.diff
+
+This updates your working directory to look exactly like it did when
+you originally committed revision 430! You can now edit the files to
+correct the error you found, and when you are done you run::
+
+   hg qrefresh
+
+to refresh the patch in ``430.diff``. You can use ``hg qrefresh -e``
+to edit the commit message too. Now comes the fun part — you must now
+push the the other patches back on the stack with::
+
+   hg qpush -a
+
+If this goes well with no complaints, then you can delete the patches
+again with::
+
+   hg qdelete -r qbase:qtip
+
+The end result is a completely normal repository with no sign of this
+surgery. You can repeat this as many times as needed to slowly develop
+your patches until you are satisfied with the results.
+
+
+If the changes you made to the patch are conflicting with other
+patches in your stack, then the pushing will stop where the error was
+encountered, and the conflicting patch hunk is stored in a ``.rej``
+file. There is no need to panic if this happens — all you need to do
+is to determine how the hunk in the ``.rej`` file(s) should be applied
+(if at all) and then run ``hg qrefresh`` to indicate that the current
+patch is okay. Now continue applying patches with ``hg qpush -a`` and
+fix any remaining conflicts.
+
+
+.. _Mercurial Queues extension: http://www.selenic.com/mercurial/
+                                       wiki/index.cgi/MqExtension
+
+.. LocalWords:  changeset changesets
--- a/doc/implementation.txt	Mon May 26 21:44:29 2008 +0200
+++ b/doc/implementation.txt	Mon May 26 22:16:45 2008 +0200
@@ -16,3 +16,6 @@
    prss
    config
    program-counters
+   coding-style
+   development
+   unit-testing
--- a/doc/index.txt	Mon May 26 21:44:29 2008 +0200
+++ b/doc/index.txt	Mon May 26 22:16:45 2008 +0200
@@ -13,7 +13,9 @@
 
    overview
    install
+   presentations
    implementation
+   bibliography
    glossary
 
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/presentations.txt	Mon May 26 22:16:45 2008 +0200
@@ -0,0 +1,33 @@
+
+Presentations
+=============
+
+The following VIFF-related presentations are available:
+
+February 21st, 2008:
+  Slides used at a PhD Qualification Exam by Martin Geisler. Like the
+  report they accompany, the second part of the slides are about VIFF
+  and includes benchmark results.
+
+  Available as PDF__.
+
+  .. __: http://viff.dk/files/mg-progress-report-talk.pdf
+
+January 15th, 2008:
+  PhD Progress Report by Martin Geisler. The second part of the report
+  describes the design of VIFF and proves it secure in the Universally
+  Composability security framework by Canetti.
+
+  Available as PDF__.
+
+  .. __: http://viff.dk/files/mg-progress-report.pdf
+
+September 20th, 2007:
+  VIFF Design Talk given by Martin Geisler at a SIMAP_ meeting. The
+  talk describes some of the goals of the VIFF design. It is current
+  to version 0.2 of VIFF.
+
+  Available as PDF__.
+
+  .. _SIMAP: http://simap.dk/
+  .. __: http://viff.dk/files/design-talk.pdf
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc/unit-testing.txt	Mon May 26 22:16:45 2008 +0200
@@ -0,0 +1,289 @@
+.. -*- coding: utf-8 -*-
+
+==============
+ Unit Testing
+==============
+
+VIFF employs a set of unit tests to help developers catch regressions
+and to ensure the correctness of the implementation. The code is
+continuously tested using a BuildBot_ and the results are available
+online_. If you see warnings or errors from the unit tests on the
+`BuildBot waterfall page`_, then please take it as an invitation to
+fix them!
+
+.. _BuildBot: http://buildbot.net/
+.. _online: http://buildbot.viff.dk/
+.. _BuildBot waterfall page: http://buildbot.viff.dk/waterfall
+
+When using Twisted it is natural to use its unit testing framework
+called Trial_. Trial has the big advantage over normal testing
+frameworks that it understands Twisted's Deferreds_ — if a unit test
+returns a Deferred, Trial waits for it to trigger before it declares
+the test a success or failure. Please refer to this tutorial_ for more
+information.
+
+.. _Trial: http://twistedmatrix.com/trac/wiki/TwistedTrial
+.. _Deferreds: http://twistedmatrix.com/projects/core/
+               documentation/howto/defer.html
+.. _tutorial: http://twistedmatrix.com/trac/browser/branches/
+              trial-tutorial-2443/doc/core/howto/trial.xhtml?format=raw
+
+Running the Unit Tests
+----------------------
+
+To run the VIFF unit tests you must make sure that ``import viff``
+works correctly in Python. In other words, you must make sure that
+VIFF is installed or that the root of your source tree is in
+``PYTHONPATH``. You can test this by changing to some unrelated
+directory, starting an interactive Python session and run:
+
+.. sourcecode:: pycon
+
+  >>> import viff
+  >>> print viff.__version__
+  0.3
+
+If it fails with an ImportError, then please double-check that your
+``PYTHONPATH`` is setup correctly.
+
+Now simply execute ``trial viff`` to run the unit tests. You should
+get output similar to this::
+
+  % trial viff
+  Seeding random generator with random seed 4658
+  Running 65 tests.
+  viff.test.test_active_runtime
+    ActiveRuntimeTest
+      test_broadcast ...                                           [OK]
+  viff.test.test_basic_runtime
+    ProgramCounterTest
+      test_callback ...                                            [OK]
+      test_complex_operation ...                                   [OK]
+      test_initial_value ...                                       [OK]
+      test_multiple_callbacks ...                             [SKIPPED]
+      test_nested_calls ...                                        [OK]
+      test_simple_operation ...                                    [OK]
+  viff.test.test_field
+    GF256TestCase
+      test_add ...                                                 [OK]
+      test_construct ...                                           [OK]
+      test_div ...                                                 [OK]
+      test_field ...                                               [OK]
+      test_invert ...                                              [OK]
+      test_mul ...                                                 [OK]
+      test_neg ...                                                 [OK]
+      test_pow ...                                                 [OK]
+      test_str ...                                                 [OK]
+      test_sub ...                                                 [OK]
+      test_xor ...                                                 [OK]
+    GFpElementTestCase
+      test_add ...                                                 [OK]
+      test_bit ...                                                 [OK]
+      test_div ...                                                 [OK]
+      test_field ...                                               [OK]
+      test_invert ...                                              [OK]
+      test_mul ...                                                 [OK]
+      test_neg ...                                                 [OK]
+      test_sqrt ...                                                [OK]
+      test_str ...                                                 [OK]
+      test_sub ...                                                 [OK]
+  doctest
+    DocTestCase
+      field ...                                                    [OK]
+      GF ...                                                       [OK]
+      __eq__ ...                                                   [OK]
+      __init__ ...                                                 [OK]
+      __nonzero__ ...                                              [OK]
+      __radd__ ...                                                 [OK]
+      __rmul__ ...                                                 [OK]
+  viff.test.test_prss
+    PRSSTestCase
+      test_generate_subsets ...                                    [OK]
+  doctest
+    DocTestCase
+      PRF ...                                                      [OK]
+      __call__ ...                                                 [OK]
+      __init__ ...                                                 [OK]
+      generate_subsets ...                                         [OK]
+      prss ...                                                     [OK]
+  viff.test.test_runtime
+    RuntimeTest
+      test_add ...                                                 [OK]
+      test_add_coerce ...                                          [OK]
+      test_convert_bit_share ...                                   [OK]
+      test_greater_than ...                                        [OK]
+      test_greater_than_equal ...                                  [OK]
+      test_greater_than_equalII ...                                [OK]
+      test_less_than ...                                           [OK]
+      test_less_than_equal ...                                     [OK]
+      test_mul ...                                                 [OK]
+      test_open ...                                                [OK]
+      test_open_no_mutate ...                                      [OK]
+      test_prss_share_bit ...                                      [OK]
+      test_prss_share_int ...                                      [OK]
+      test_prss_share_random_bit ...                               [OK]
+      test_prss_share_random_int ...                               [OK]
+      test_shamir_share ...                                        [OK]
+      test_shamir_share_asymmetric ...                             [OK]
+      test_sub ...                                                 [OK]
+      test_sub_coerce ...                                          [OK]
+      test_xor ...                                                 [OK]
+  doctest
+    DocTestCase
+      share ...                                                    [OK]
+      clone_deferred ...                                           [OK]
+      dlift ...                                                    [OK]
+      find_prime ...                                               [OK]
+
+  =====================================================================
+  [SKIPPED]: viff.test.test_basic_runtime.ProgramCounterTest.
+  test_multiple_callbacks
+
+  TODO: Scheduling callbacks fails to increment program counter!
+  ---------------------------------------------------------------------
+  Ran 65 tests in 18.305s
+
+  PASSED (skips=1, successes=64)
+
+Lots of success! But one of the tests was skipped — we do this when we
+have a test which represents a known problem. Otherwise every test run
+would be cluttered with long of traceback messages, making it
+difficult to notice new *unexpected* failures.
+
+
+Writing Unit Tests
+------------------
+
+The unit tests live in the ``viff.test`` package. There you will find
+a number of modules, which in turn contain classes inheriting from
+``twisted.trial.unittest.TestCase``. Trial recognizes these classes
+and will execute methods starting with ``test``.
+
+Simple Tests
+~~~~~~~~~~~~
+
+Adding a new unit test can be as simple as defining a new method in a
+suitable class. The method will want to assert certain things during
+the test, and for that Trial offers a large number of convenient
+methods such as ``assertEqual``, ``assertTrue``, and so on. The full
+reference is available `online`__. Notice that they describe the
+methods under names like ``failUnlessSomething`` which is aliased to
+``assertSomething``. So far all the VIFF unit tests use the
+``assertSomething`` style, but you are welcome to use the other if you
+prefer.
+
+.. __: http://twistedmatrix.com/documents/current/api/
+       twisted.trial.unittest._Assertions.html
+
+A simple example of a unit test is ``viff.test.test_field`` which
+looks like this (heavily abbreviated):
+
+.. sourcecode:: python
+
+  """Tests for viff.field."""
+
+  from viff.field import GF, GF256
+  from twisted.trial.unittest import TestCase
+
+  #: Declare doctests for Trial.
+  __doctests__ = ['viff.field']
+
+  class GFpElementTestCase(TestCase):
+      """Tests for elements from a Zp field."""
+
+      def setUp(self):
+          """Initialize Zp to Z31."""
+          self.field = GF(31)
+
+      def test_invert(self):
+          """Test inverse operation, including inverting zero."""
+          self.assertRaises(ZeroDivisionError, lambda: ~self.field(0))
+          self.assertEquals(~self.field(1), self.field(1))
+
+      def test_sqrt(self):
+          """Test extraction of square roots."""
+          square = self.field(4)**2
+          root = square.sqrt()
+          self.assertEquals(root**2, square)
+
+This demonstrates the most important features in a simple unit test:
+
+* First the needed definitions are imported as normal.
+
+* Setting the ``__doctest__`` field makes Trial run the doctests_ in
+  the named module.
+
+* A class is defined which inherit from ``TestCase``.
+
+* A ``setUp`` method is used to collect preperations that are needed
+  for every test.
+
+* Several test methods are defined. They make use of the assertions
+  offered by Trial.
+
+.. _doctests: http://docs.python.org/lib/module-doctest.html
+
+
+Tests Involving a VIFF Runtime
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Trial really shines when it comes to testing that involves networking.
+First, it allows us to forget about the networking — the network
+connections are replaced by direct method calls on the receiver's
+transport. This makes the test repeatable unlike if real network
+connections were used since they may fail if they cannot bind to the
+wanted port number.
+
+In VIFF the ``util.py`` file contains the logic needed to connect a
+number of Runtime instances in this way. All you need to do is to
+create a subclass of RuntimeTestCase and decorate the test methods
+with ``protocol`` like this example (abbreviated from
+``viff.test.test_active_runtime``):
+
+.. sourcecode:: python
+
+  from viff.test.util import RuntimeTestCase, protocol
+
+  class ActiveRuntimeTest(RuntimeTestCase):
+      """Test for active security."""
+
+      #: Number of players.
+      num_players = 4
+
+      @protocol
+      def test_broadcast(self, runtime):
+          """Test Bracha broadcast."""
+          if runtime.id == 1:
+              x = runtime.broadcast([1], "Hello world!")
+          else:
+              x = runtime.broadcast([1])
+          x.addCallback(self.assertEquals, "Hello world!")
+          return x
+
+By decorating ``test_broadcast`` with ``protocol`` we ensure that the
+method will be called with a Runtime instance. Furthermore, the method
+will be called ``num_player`` times, each time with another Runtime
+instance. The net result is that the test behaves just like if four
+players had started four programs containing the method body.
+
+In the method you can branch on ``runtime.id``. This is needed in the
+typical case where you want only one of the parties to input something
+to a calculation.
+
+In this example all four parties get an ``x`` which will eventually
+contain the string "Hello World". Using Trial we can return ``x`` and
+Trial will then wait for ``x`` to trigger before declaring the test a
+success or failure. We have attached ``self.assertEquals`` as a
+callback on ``x`` with an extra argument of "Hello World". This means
+that when ``x`` eventually triggers, the assertion is run and the test
+finishes.
+
+This is the real power of Trial. You can do some calculations and
+finish by returning a Deferred (and remember that Shares are Deferreds
+in VIFF). The value of this Deferred is not important, it is only
+important that it triggers when the test is done. You will often need
+to use ``twisted.internet.defer.gatherResults`` to combine several
+Deferreds into one that you can return to Trial. Just make sure that
+your final Deferred depends on all other Deferreds so that you do not
+leave lingering Deferreds behind. Trial will complain loudly if you
+do, so it should be easy to spot.