Re: [viff-devel] Say hello to viff.boost

[Marcel Keller]

Hi friends of VIFF,

my repository now also features a C implementation of viff.field. It 
uses GMP in GFElement. The benchmarks show a speed up between 100 and 
over 200 percent (the latter in multiplication triple generation with 
hyperinvertible matrices). The instructions to use it are the same.


Best regards,
Marcel


Marcel Keller wrote:

Hi friends of VIFF,

I've implemented Share and ShareList in C, based on a C implementation
of Deferred. Using the C extension, benchmark.py and aes.py show a speed
up between 50 and 100 percent.

The code is in my repository: http://hg.viff.dk/mkeller

To use the extension, first compile and install it:
$ python setup.py install [--prefix PREFIX]

Then, add the following lines two to your program before importing
anything from viff or twisted:

import viff.boost
viff.boost.install(with_viff_reactor=)

If the parameter is True, the VIFF reactor is also installed, so this
doesn't have to be done separately.

There is a notable difference to the standard implementation of
Deferred: Errbacks are disabled and exceptions raised in callbacks are
not caught. This is for the following reasons:
- The implementation was inefficient (too many isinstance() calls).
- Errbacks are only used for error reporting in VIFF. However, I prefer
VIFF to crash (and print a traceback) immediately if there is an
exception instead of wrapping the exception and reporting it later,
which makes debugging harder.

I'm open for comments on this issue. It shouldn't be hard to reimplement
errbacks or to implement something different like a global errback. For
compatibility, all Deferred methods are still present.

If trial is modified to load the C extension, all tests succeed except a
few doctests.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Say hello to viff.boost

[Marcel Keller]

Hi friends of VIFF,

I've implemented Share and ShareList in C, based on a C implementation
of Deferred. Using the C extension, benchmark.py and aes.py show a speed
up between 50 and 100 percent.

The code is in my repository: http://hg.viff.dk/mkeller

To use the extension, first compile and install it:
$ python setup.py install [--prefix PREFIX]

Then, add the following lines two to your program before importing
anything from viff or twisted:

import viff.boost
viff.boost.install(with_viff_reactor=)

If the parameter is True, the VIFF reactor is also installed, so this
doesn't have to be done separately.

There is a notable difference to the standard implementation of
Deferred: Errbacks are disabled and exceptions raised in callbacks are
not caught. This is for the following reasons:
- The implementation was inefficient (too many isinstance() calls).
- Errbacks are only used for error reporting in VIFF. However, I prefer
VIFF to crash (and print a traceback) immediately if there is an
exception instead of wrapping the exception and reporting it later,
which makes debugging harder.

I'm open for comments on this issue. It shouldn't be hard to reimplement
errbacks or to implement something different like a global errback. For
compatibility, all Deferred methods are still present.

If trial is modified to load the C extension, all tests succeed except a
few doctests.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and random numbers

[Marcel Keller]

Thomas P Jakobsen wrote:

The urandom is os-specific:

"This function returns random bytes from an OS-specific randomness
source. The returned data should be unpredictable enough for
cryptographic applications, though its exact quality depends on the OS
implementation. On a UNIX-like system this will query /dev/urandom,
and on Windows it will use CryptGenRandom."

I don't know whether this will be good enough.


There is a paper describing various flaws:
http://www.pinkas.net/PAPERS/gpr06.pdf


If not, I guess we'll
have to use some external package (openssl?)  or implement our own
algorithm.


viff.util.rand is used to make all randomness replayable, which already
helped me to find bugs triggered by certain randomness. I would like to
have this feature also in the future, therefore I would vote against a
random number generator using noise not only to generate a seed.

If the environment variable VIFF_SEED is set to the empty string, VIFF
already uses /dev/urandom by using random.SystemRandom for random number
generation. This possibility is not documented however.

Best regards,
Marcel



On Tue, Jul 6, 2010 at 15:40, Ivan Bjerre Damgård  wrote:

It is not good to use the wrong kind of PRG, it should
be fixed as soon as possible. But do we know that
os.urandom will be OK on any platform, or is this
OS -dependent at the end of the day?

- Ivan

On 06/07/2010, at 15.22, Thomas P Jakobsen wrote:


VIFF itself as well as most protocols implemented in VIFF uses the
viff.util package for random number generation. This package in turn
uses the random package in the Python standard library. This means
that random numbers are generated using a Mersenne twister.

As far as I can see, this is a problem, since Mersenne twister PRNGs
are generally not suited for cryptographic usage. E.g. it is not known
to pass the "next-bit test" and withstand the "state compromise
extensions", see
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator.

One solution would be to use the os.urandom() function instead. This
has specifically been designed to produce cryptographically secure
random numbers.

(We should probably keep the old random generator, too. It is probably
faster and not all random numbers used in VIFF and VIFF programs need
to be cryptographically secure.)


Let me know what you think about this.

Kind regards,
Thomas
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk



___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Value overflow in Toft07

[Marcel Keller]

Dear Lars,

thanks for pointing it out. It is now fixed in the official repository.

Best regards,
Marcel


Lars Krapf wrote:

Hello VIFF-team

I would like to suggest the following patch to viff/comparison.py:
159c159
< l = int(self.options.security_parameter + 
math.log(dst_field.modulus, 2))

---
 > l = self.options.security_parameter + 
math.log(dst_field.modulus, 2)


otherwise the l in the next line:
 this_mask = rand.randint(0, (2**l) -1)

is a float, and we get "34, Value out of Range" exceptions for big l.

Best greetings
Lars Krapf

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF reactor

[Marcel Keller]

Hi Joel,


Is it still necessary to run `viff.reactor.install()` as described in
 in
order to utilize the VIFF reactor?

 - If so, would it be possible to "fix" that?


I don't see a good way to that, for the following reasons:
- To change the default reactor properly, it would be necessary to 
change the Twisted source code. That is not an elegant way.
- The VIFF reactor could be installed in the runtime module. However, if 
it would be done that way, viff.runtime would have to be imported before 
importing the reactor, which is a possible source of errors. 
Furthermore, that would prevent other reactors like the GtkReactor from 
being used.



 - If not, then the example apps would need to be updated accordingly.


As far as I can see, all example apps are updated in VIFF 1.0.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] A potential bug in the Shamir Module

[Marcel Keller]

Hi,


The bug is this line:
cur_point = secret.field(i)

If the number of player exceed the size of the field then the function 
returns the wrong id (cur_point)?


Shamir secret sharing only works if the field is strictly bigger than
the number of players. Otherwise, there would not be enough points to
evaluate the polynomial in to get the shares.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Equality protocol : error

[Marcel Keller]

Hi Jonathan,

thanks for sending the config files. I could reproduce the error using
them. It turned out that the equality module doesn't handle the case of
the masked value c being zero. The latest code on viff.dk is now fixed.

Best regards,
Marcel


Jonathan Van den Schrieck wrote:


Dear Mr. Keller,

Here are the files compressed in a .zip files. It should be ok with the filter.

Best regards,

Jonathan

Le 15 avr. 2010 à 13:36, Marcel Keller a écrit :


Hi Jonathan,

The spam filter of the university removed the attached config files. Were they 
in some ASCII format? Names like ARRAY(0x8eaac50) suggest that they actually 
contain serialized Python data structures, which also would explain why the 
spam filter removed them.

Best regards,
Marcel


Jonathan Van den Schrieck wrote:

Dear Mr. Keller,
Here are my config files I used. They are the basic ones used for the 
millionaires problem. I generated new ones and the problem seems fixed, but I 
would be interested to know where the error came from.
Thank you for your help !
Jonathan
Le 8 avr. 2010 à 23:34, Marcel Keller a écrit :

Hi Jonathan,

I can't reproduce the error here. Can you send me your config files? The   
error might be triggered by certain random numbers, which depend on the PRSS 
keys. By the way, the error message is about the same every time something goes 
wrong in a callback. This is because VIFF does not define errbacks. To get a 
little bit more meaningful output, you can use the --deferred-debug parameter.

Best regards,
Marcel





___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Equality protocol : error

[Marcel Keller]

Hi Jonathan,

I can't reproduce the error here. Can you send me your config files? The 
  error might be triggered by certain random numbers, which depend on 
the PRSS keys. By the way, the error message is about the same every 
time something goes wrong in a callback. This is because VIFF does not 
define errbacks. To get a little bit more meaningful output, you can use 
the --deferred-debug parameter.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] OrlandiRuntime implementation

[Marcel Keller]

Claudio Orlandi schrieb:

On Wed, Nov 4, 2009 at 10:15 AM, Marcel Keller  wrote:

Claudio Orlandi wrote:

On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller  wrote:

Hi Claudio and Jesper,

In the code review of the OrlandiRuntime we found two points, we want to
discuss with you.

Step 3 of the triple generation protocol says: Coin-flip a subset
\fancy_T
\subset \fancy_M of size \lambda(2d + 1)M. The current implementation
loops
over the elements in \fancy_M and decides fifty-fifty for every element
whether it should by in \fancy_T until there are enough elements in
\fancy_T. I however think that this choice should be biased according to
the
size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be
put
in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M =
\lambda / (1 + \lambda). Furthermore, I think the probability should be
updated whenever \fancy_M is processed completely and \fancy_T still is
not
big enough. Maybe it would be easier to choose \lambda(2d + 1)M  times a
random element of the remaining ones in \fancy_M instead.

So you could loop the elements of M and include them in T with
probability \lambda/(1+\lambda), but then you're not guaranteed that
you have enough triplets left in M.

Exactly, that's why I suggested the solution which in that case would
restart with an adapted probability.


Choosing the right number of

random elements from M and include them in T is the right choice (or
any solution that guarantees the size of M \ T to be 2(2d+1)M --- I
don't know if the typo is in your email or in Step 3, but the size of
the set M should be (1+\lambda)2(2d+1)M --- you miss a 2.

I think the 2 is missing in your report and the code.



Wow. Then it really shouldn't work!
The factors are:
1+lambda : because in the test we check a fraction lambda/1+lambda of
the triplets
2 : because there is a test to check the correctness of the triplets
that burns one triplet to ensure the other one is good
2d+1: because we do the shamir secret sharing multiplication


Isn't the burning already done in TripleTest, so you really have just 
(lambda+1)(2d+1)M triples when doing coin-flipping for the test set?



I guess at some point I should also give a look at the code...


In step 6, the implementation generates a distributed random number in
Z_p
to determine a partition where one element should be put if there is
still
space there. I suggest to use the randomness more efficiently to save
communication. E.g., if a random number in Z_p is smaller than M^l with l
\le log_M(p), one can extract l random numbers in Z_M. The same method
probably could be used in step 3 as well.

Right. Actually if you want to save communication here you can also
use a PRG using the distributed random number as the seed.


Best regards,
Marcel


If you have time, there are a lot of things that need to be done here.
I already told Janus knows some of them, but said he can't work on
them. Here is something nice we should do to reduce the online time of
a factor (at least) 3:

In the protocol there are Pedersen commitemnts with three base element
g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes
g^xh_1^r_1h_2^r_2. The protocol now does it in the following way:
1) compute a=g^x
2) compute b=h_1^r_1
3) compute c=h_2^r_2
4) compute d=a*b*c

The complexity is dominated by the three exponentiation, that one
implements using some ladder (square and multiply)

There is no need to do three exponentiation if one does something a bit
smarter:
- precompute
g001=g^0h_1^0h_2^1
g010=g^0h_1^1h_2^0
...
g010=g^1h_1^1h_2^1

Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking
comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this
is just one ladder, so virtually the same as just one of the above
exponentiation.

One can go further and precompute more elements, for instance
g000
...
g333
And now you look at 2 bits of x,r_1,r_2 for every square in the
square-and-multiply. This saves another factor 2 in time but you need
to store a bigger table of size 8^2.

What is the best strategy given our architecture? How many powers
should we precompute?

The commitments are computed by an external elliptic curve library, so I
can't answer anything here. Janus should know more about it.



Actually i think that the elliptic curve library offers method for
square, multiply, and a multiplication, not for the commitments as an
object... I seem to remember that Janus implemented them.


In any case, the commitments are completely implemented in C and I 
didn't have a look at that code.


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] OrlandiRuntime implementation

[Marcel Keller]

Claudio Orlandi wrote:

On Wed, Nov 4, 2009 at 5:46 AM, Marcel Keller  wrote:

Hi Claudio and Jesper,

In the code review of the OrlandiRuntime we found two points, we want to
discuss with you.

Step 3 of the triple generation protocol says: Coin-flip a subset \fancy_T
\subset \fancy_M of size \lambda(2d + 1)M. The current implementation loops
over the elements in \fancy_M and decides fifty-fifty for every element
whether it should by in \fancy_T until there are enough elements in
\fancy_T. I however think that this choice should be biased according to the
size of \fancy_M and \fancy_T, i.e. every element of \fancy_M should be put
in \fancy_T with probability \lambda(2d + 1)M / (1 + \lambda)(2d + 1)M =
\lambda / (1 + \lambda). Furthermore, I think the probability should be
updated whenever \fancy_M is processed completely and \fancy_T still is not
big enough. Maybe it would be easier to choose \lambda(2d + 1)M  times a
random element of the remaining ones in \fancy_M instead.


So you could loop the elements of M and include them in T with
probability \lambda/(1+\lambda), but then you're not guaranteed that
you have enough triplets left in M.


Exactly, that's why I suggested the solution which in that case would 
restart with an adapted probability.


> Choosing the right number of

random elements from M and include them in T is the right choice (or
any solution that guarantees the size of M \ T to be 2(2d+1)M --- I
don't know if the typo is in your email or in Step 3, but the size of
the set M should be (1+\lambda)2(2d+1)M --- you miss a 2.


I think the 2 is missing in your report and the code.


In step 6, the implementation generates a distributed random number in Z_p
to determine a partition where one element should be put if there is still
space there. I suggest to use the randomness more efficiently to save
communication. E.g., if a random number in Z_p is smaller than M^l with l
\le log_M(p), one can extract l random numbers in Z_M. The same method
probably could be used in step 3 as well.


Right. Actually if you want to save communication here you can also
use a PRG using the distributed random number as the seed.


Best regards,
Marcel



If you have time, there are a lot of things that need to be done here.
I already told Janus knows some of them, but said he can't work on
them. Here is something nice we should do to reduce the online time of
a factor (at least) 3:

In the protocol there are Pedersen commitemnts with three base element
g,h_1,h_2. To commit to x using randomness r_1,r_2 one computes
g^xh_1^r_1h_2^r_2. The protocol now does it in the following way:
1) compute a=g^x
2) compute b=h_1^r_1
3) compute c=h_2^r_2
4) compute d=a*b*c

The complexity is dominated by the three exponentiation, that one
implements using some ladder (square and multiply)

There is no need to do three exponentiation if one does something a bit smarter:
- precompute
g001=g^0h_1^0h_2^1
g010=g^0h_1^1h_2^0
...
g010=g^1h_1^1h_2^1

Now, to compute g^xh_1^r_1h_2^r_2 one does the ladder by looking
comtemporarily at the i-th bit of x, r_1, r_2. The complexity of this
is just one ladder, so virtually the same as just one of the above
exponentiation.

One can go further and precompute more elements, for instance
g000
...
g333
And now you look at 2 bits of x,r_1,r_2 for every square in the
square-and-multiply. This saves another factor 2 in time but you need
to store a bigger table of size 8^2.

What is the best strategy given our architecture? How many powers
should we precompute?


The commitments are computed by an external elliptic curve library, so I 
can't answer anything here. Janus should know more about it.


Regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] OrlandiRuntime implementation

[Marcel Keller]

Hi Claudio and Jesper,

In the code review of the OrlandiRuntime we found two points, we want to 
discuss with you.


Step 3 of the triple generation protocol says: Coin-flip a subset 
\fancy_T \subset \fancy_M of size \lambda(2d + 1)M. The current 
implementation loops over the elements in \fancy_M and decides 
fifty-fifty for every element whether it should by in \fancy_T until 
there are enough elements in \fancy_T. I however think that this choice 
should be biased according to the size of \fancy_M and \fancy_T, i.e. 
every element of \fancy_M should be put in \fancy_T with probability 
\lambda(2d + 1)M / (1 + \lambda)(2d + 1)M = \lambda / (1 + \lambda). 
Furthermore, I think the probability should be updated whenever \fancy_M 
is processed completely and \fancy_T still is not big enough. Maybe it 
would be easier to choose \lambda(2d + 1)M  times a random element of 
the remaining ones in \fancy_M instead.


In step 6, the implementation generates a distributed random number in 
Z_p to determine a partition where one element should be put if there is 
still space there. I suggest to use the randomness more efficiently to 
save communication. E.g., if a random number in Z_p is smaller than M^l 
with l \le log_M(p), one can extract l random numbers in Z_M. The same 
method probably could be used in step 3 as well.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Noisy preprocessing

[Marcel Keller]

Actually, I meant the update method in runtime.py, line 807, which 
doesn't output program counters.


Janus Dam Nielsen schrieb:

Hi Marcel,

Occasionally I need to see which program counters are needed, so I can 
save them and use the NeededDataBenchmark strategy. This suggests that 
we should make it an option.


On 28/10/2009, at 20.01, Marcel Keller wrote:


Hi Janus,

do you still need the timing output in the update callback in
Runtime.preprocess()? It makes benchmarking the usual runtimes very
noisy because the update callback is called many times there.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk <mailto:viff-devel@viff.dk>
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk


**
*
*
*Janus Dam Nielsen*
*
*
Research and Innovationspecialist, PhD.
CENTRE FOR IT-SECURITY

THE ALEXANDRA INSTITUTE LTD.

T +45 42 22 93 56
E janus.niel...@alexandra.dk <mailto:janus.niel...@alexandra.dk>
W alexandra.dk




___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Noisy preprocessing

[Marcel Keller]

Hi Janus,

do you still need the timing output in the update callback in
Runtime.preprocess()? It makes benchmarking the usual runtimes very
noisy because the update callback is called many times there.

Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Orlandi preprocessing

[Marcel Keller]

Hi Janus,

I remember you saying today that the preprocessing in the OrlandiRuntime 
is more efficient per item the more items are requested. Is that 
correct? I ask because in my optimizations, I limited the items being 
preprocessed per call in order to save memory. I would of course drop 
that because it doesn't really affect the other cases.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Optimizing preprocessing

[Marcel Keller]

Janus Dam Nielsen wrote:


On 21/10/2009, at 20.28, Marcel Keller wrote:

Martin Geisler wrote:
Janus Dam Nielsen <mailto:janus.niel...@alexandra.dk>> writes:

Hi Marcel,

I am not opposed to your suggestion. However I would like to point out
that in VIFF you compute on shares and not field elements!

Well, we've actually made the outer runtime interfaces in such a way
that add, mul, xor, etc... accept both integers, FieldElements and
Shares. The methods then wrap their input as needed -- or they *dont*
wrap it if that leads to a short cut (e.g., constant multiplication)


I agree (see also my answer).
I would still like to stress that Shares are the basic values in VIFF. 
The interface is then designed in such a way, so that we can do various 
optimizations, but computing on field elements (a particular 
representation of a share) is an optimization, which I am very happy 
that the interface allows us to do. But it is still an optimization. 


I agree that the design maybe is not optimal semantically, IMHO because 
Shares are Deferreds. This leads to the situation that whenever a 
callback returns a Share, the Deferred code converts it into the result 
carried by the Share. However, a list of Shares returned by a callback 
is not converted.



Computing directly on the field elements is hacking the abstractions
of VIFF. Computation on field elements or rather the representation of
a Share can be useful as an optimization, however this optimization
should be confined within applications or runtimes, and should not
progress over interface boundaries as I fear you are suggesting.

I think we are in agreement: public methods on the runtimes will keep
returning Shares. Methods used internally in runtimes can return other
things as needed. To me it sounds like a better API to require
preprocessing functions to return a list of Deferreds:
 [D(?), D(?), ...],
instead of a Deferred list of tuples containing Deferreds :-)
I think it will simplify the interface nicely, at least for consumers.
Using simpler types also leads to less memory usage which has a positive
effect on performance, as Marcel notes. So let's go for it.


So this makes 2 votes in favour of it and 1 against it. Maybe we 
should have a meeting to discuss it. What do you think?
I can agree on this as well, as long as we don't make field elements 
canonical.


You mean that the preprocessing infrastructure should not be restricted 
to FieldElements but can handle other items such as the tuples used by 
the Orlandi runtime. Is that correct? It was never my plan to introduce 
this restriction. I just want to get rid of the Deferreds in the 
preprocessing pool because I think that they are unnecessary there.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Optimizing preprocessing

[Marcel Keller]

Martin Geisler wrote:

Janus Dam Nielsen  writes:


Hi Marcel,

I am not opposed to your suggestion. However I would like to point out
that in VIFF you compute on shares and not field elements!


Well, we've actually made the outer runtime interfaces in such a way
that add, mul, xor, etc... accept both integers, FieldElements and
Shares. The methods then wrap their input as needed -- or they *dont*
wrap it if that leads to a short cut (e.g., constant multiplication)


I agree (see also my answer).


Computing directly on the field elements is hacking the abstractions
of VIFF. Computation on field elements or rather the representation of
a Share can be useful as an optimization, however this optimization
should be confined within applications or runtimes, and should not
progress over interface boundaries as I fear you are suggesting.


I think we are in agreement: public methods on the runtimes will keep
returning Shares. Methods used internally in runtimes can return other
things as needed. To me it sounds like a better API to require
preprocessing functions to return a list of Deferreds:

  [D(?), D(?), ...],

instead of a Deferred list of tuples containing Deferreds :-)

I think it will simplify the interface nicely, at least for consumers.
Using simpler types also leads to less memory usage which has a positive
effect on performance, as Marcel notes. So let's go for it.


So this makes 2 votes in favour of it and 1 against it. Maybe we should 
have a meeting to discuss it. What do you think?


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] AES slides from SPEED-CC

[Marcel Keller]

Hi,


There are two talks about how to implement AES efficiently, this one

  http://www.hyperelliptic.org/SPEED/slides09/kasper-aes_speedcc09_slides.pdf

describes on slide 9 how one will typically combine SubBytes, ShiftRows,
and MixColumns into one operation operating on diagonals. I don't know
if that will matter for us?


I don't think so because lookup tables are not efficient in MPC.

Regards,
Marcel


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Optimizing preprocessing

[Marcel Keller]

Hi Janus,

I am not opposed to your suggestion. However I would like to point out 
that in VIFF you compute on shares and not field elements!. Computing 
directly on the field elements is hacking the abstractions of VIFF.


I don't think so. Since I work with VIFF, it treats field elements as 
they would be shares with threshold 0. You can multiply and add field 
elements and shares. Furthermore, if you open to shares and multiply 
them, VIFF doesn't multiply locally, but executes the multiplication for 
shares of higher threshold. You have to do the following to achieve 
local multiplication:


a = open(share_a)
b = open(share_b)
c = gather_shares([a, b])
c.addCallback(lambda (a, b): a * b)

Therefore, I think that VIFF computes on field elements as well as on 
shares almost equally.


Computation on field elements or rather the representation of a Share 
can be useful as an optimization, however this optimization should be 
confined within applications or runtimes, and should not progress over 
interface boundaries as I fear you are suggesting.


I believe that if you would implement an OrlandiTuple class and overload 
operators there with the current _plus, _minus, and _const_mul 
functions, the OrlandiRuntime could reuse the add, sub, and lin_comb 
functions from PassiveRuntime and maybe even the mul function from 
BasicActiveRuntime. The OrlandiTuple would then be something equivalent 
to a FieldElement in the older runtimes.


Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Optimizing preprocessing

[Marcel Keller]

Dear friends of VIFF,

I have a proprosal to optimize preprocessing in VIFF, which I would like 
to put up for discussion.


Notation:
- D(x): a Deferred object whose callback function will be called with x
- S(x): same for a Share object
- F: a FieldElement object
- [x, ...]: a Python list
- (x, ...): a Python tuple

Current situation:
The two generate_triples() functions in the active runtimes return
n, D([(S(F), S(F), S(F)), ...]),
where n denotes the length of the list. Runtime.preprocess() puts one 
D(S(F), S(F), S(F)) per program counter in the preprocessing pool and 
uses util.deep_wait() to return a Deferred whose callback is called when 
all field elements are available.


The get_triple() functions return
D(S(F), S(F), S(F)),
either taken from the preprocessing pool, or by calling 
generate_triples() and adding an extra callback to extract the first triple.


My proposal:
The generate_triples() functions return
[D([F, F, F]), ...],
and Runtime.preprocess() puts one [F, F, F] per program counter in the 
preprocessing pool. There is no need for deep_wait, we can just use 
gatherResults on the Deferreds return by the generator functions. The 
generator functions can use gatherResults to get D([F, F, F]) from 
[S(F), S(F), S(F)].


The get_triple() functions return
[F, F, F], True  if there is a triple in the pool, and
[S(F), S(F), S(F)], Falseotherwise.
For the multiplication in BasicActiveRuntime it doesn't make a 
difference whether FieldElements or Shares are returned. Future 
applications which require Shares can wrap the FieldElements in Shares 
if the Boolean is True.


Benchmarks:
- 1 multiplications in parallel with active security using PRSS
  - 4% faster preprocessing
  - 5% faster online operation
  - 50 MB less memory used
- 10 AES blocks in parallel using masked exponentiation with active 
security using PRSS

  - 10% faster preprocessing
  - 10% faster online operation
  - 140 MB less memory used

Further considerations:
- I don't see any problem for replacing FieldElement with anything that 
does not contain Deferreds in any form.
- Probably, it would also be possible to leave the generator functions 
as they are and use something similar to deep_wait(). However, I 
consider it as an overhead.
- One could also always wrap the FieldElements in Shares, but this would 
again be an overhead.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Broken unit tests

[Marcel Keller]

Martin Geisler wrote:

I'm very confused about what exactly

  for x in xs[i:] + xs[:i]:
...
i = (i + 1) % len(xs)

is supposed to do? After x has run through all xs (rotated i steps),
then i will have been incremented by len(xs). But you do it mod
len(xs) and so i comes out of the loop unchanged.

This solution is indeed not very elegant. The problem that has to be
solved here is the following: In a normal run every player (i.e. every
runtime) has its own reactor and this reactor runs
process_deferred_queue() of one runtime. In the unit tests however,
there is one reactor for n runtimes. Therefore the reactor has to call
process_deferred_queue() of every runtime. Now, if we just would
iterate as usual over the runtimes this would lead to very unbalanced
and therefore slower execution, because the loop call is called
recursively. So this construct is to ensure that every time
loop_call() is called, another runtime has first priority.


Is all this even necessary when the code calls self.activate_reactor
once in a while?


Yes because activate_reactor() lets the reactor call the loop call.


I sort of had the impression that it was not necessary
to activate the reactor explicitly -- do things no longer work correctly
without it?


The loop call is something different than activating the reactor. If 
reactor is a ViffReactor a proper loop call is mandatory, but not the 
reactor activation. In the case of a SelectReactor activate_reactor() 
shouldn't do anything, this is a mistake, which I will correct. I'll 
also make a patch to make the unit tests also run with a SelectReactor.



Also, the sending of messages is already delayed by a random amount, so
perhaps the unbalanced execution will be handled that way?


I don't think so.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Broken unit tests

[Marcel Keller]

Hi Martin,

Martin Geisler wrote:

All the tests in the buildbot are currently broken:

  http://buildbot.viff.dk/waterfall

It is because of this change of yours:

@@ -164,6 +166,18 @@
 # the Runtime, since we want everybody to wait until all
 # runtimes are ready.
 self.runtimes.append(result)
+self.real_runtimes.append(runtime)
+self.i = 0
+
+# This loop call should ensure the queues of the parties are
+# processed in a more or less fair manner. This is necessary
+# because we have only one reactor for all parties here.
+def loop_call():
+for runtime in self.real_runtimes[self.i:] + 
self.real_runtimes[:self.i]:
+runtime.process_deferred_queue()
+self.i = (self.i + 1) % len(self.real_runtimes)
+
+reactor.setLoopCall(loop_call)


I think the problem is that after this change the unit tests need the 
reactor to be a ViffReactor, but it seems that the reactor is a 
SelectReactor. And this seems to be the case since your changeset "Make 
the VIFF reactor available to trial".



I'm very confused about what exactly

  for x in xs[i:] + xs[:i]:
...
i = (i + 1) % len(xs)

is supposed to do? After x has run through all xs (rotated i steps),
then i will have been incremented by len(xs). But you do it mod len(xs)
and so i comes out of the loop unchanged.


This solution is indeed not very elegant. The problem that has to be 
solved here is the following: In a normal run every player (i.e. every 
runtime) has its own reactor and this reactor runs 
process_deferred_queue() of one runtime. In the unit tests however, 
there is one reactor for n runtimes. Therefore the reactor has to call 
process_deferred_queue() of every runtime. Now, if we just would iterate 
as usual over the runtimes this would lead to very unbalanced and 
therefore slower execution, because the loop call is called recursively. 
So this construct is to ensure that every time loop_call() is called, 
another runtime has first priority.



The xs[i:] + xs[:i] construct is at best uncommon and at worst wasted
work. Instead of rotating the list, it should be enough to start at an
offset (i) and work your way through the list with proper wrapping at
the end.


You're right.


Also, the fact that you have both self.runtimes and self.real_runtimes
smells funny :-) It's as if you're circumventing the natural scopes of
the Deferreds by storing a reference to the runtimes "on the side".

The list of Deferreds in self.runtimes ought to be enough -- can you not
add callbacks to that list if you need something to happen when the
runtimes are ready?


Yes, it just was too lazy.

Best reagards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Say hello to viff.reactor

[Marcel Keller]

Hi friends of VIFF,

I've now implemented a special reactor for VIFF, based on the standard 
SelectReactor. The new reactor should make non-trivial programs 
considerably faster, e.g. computation of 10 AES-blocks in parallel from 
over 6 seconds to 2.3 seconds per block (3 players, passive security).


The code is in my repository: http://hg.viff.dk/mkeller
To use the new reactor, simply install it before importing the reactor:

import viff.reactor
viff.reactor.install()
from twisted.internet import reactor

If you use other reactors such as Gtk2Reactor or WxReactor, VIFF still 
will work but without any speed improvements.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Non-default reactors

[Marcel Keller]

Hi friends of VIFF,

Who is working with non-default reactors, such as gtk2reactor? How do 
you deal with the fact that VIFF might block the reactor for a long time 
which might render the GUI non-responsive?


I'm currently working on a special reactor for VIFF to get more control 
over the scheduling.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] How to avoid the boring math

[Marcel Keller]

Hi friends of VIFF,

I've now played a little bit with artificial bandwidth limits and 
artificial delays in order to be able to better analyze protocols. 
(Actually, my motivation was to get the running time for AES matching my 
analysis. It worked.)


I found out that setting a delay of 1 second for every packet gives a 
running time matching the number of rounds quite well. On the other 
hand, limiting the bandwidth gives at least a qualitative impression of 
the number of elementary operations. Another observation is that one 
could also have a look at the TCP sequence numbers to get an impression 
of the number of elementary operations.


I've included to shell scripts for Linux: One delays the network traffic 
to a given address space by 1 second, the other limits the traffic to 
15kbit/s.  They must be run as root.


If adding a delay, one should also apply the attached patch to avoid 
strange results (longer running times for less traffic).


Best regards,
Marcel

Disclaimer: Hereby I reject to encourage anyone to replace serious 
protocol analysis by heuristics.



diff -r 5feebdfcc759 viff/runtime.py
--- a/viff/runtime.py	Fri Apr 24 14:04:45 2009 +0200
+++ b/viff/runtime.py	Fri Apr 24 14:11:54 2009 +0200
@@ -272,6 +272,7 @@
 self.incoming_data = {}
 
 def connectionMade(self):
+self.transport.setTcpNoDelay(True)
 self.sendString(str(self.factory.runtime.id))
 
 def connectionLost(self, reason):


delay.sh
Description: application/shellscript


limit.sh
Description: application/shellscript
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Two-threaded VIFF

[Marcel Keller]

Hi friends of VIFF,

I've finally completed the patch for a two-threaded VIFF where most of 
the VIFF code runs in a separate thread. The patch is against the tip of 
my repository: http://hg.viff.dk/mkeller


It turned out be not so straight-forward as I thought. I had to use a 
recursion, as in the hack, but I refined it to ensure that the recursion 
limit isn't exceeded.


Benchmarks:
Unfortunately, this solution is slower than the hack, e.g. one AES block 
encryption takes 4 seconds compared to 3 seconds with the hack. On the 
other hand, the preprocessing time in the actively secure multiplication 
is linear and not quadratic, whereas the online time is significantly 
larger:


two-threadedhackoriginal
(n,t)   online  preprocessing   online  preprocessing   online  preproc.
(4,1)   6   22  4   17  4   20
(7,2)   10  37  6   29  6   42
(10,3)  13  53  8   42  8   82
(13,4)  17  68  10  56  10  136
(16,5)  20  84  12  68  12  208
(19,6)  23  106 13  83  14  287
(22,7)  26  120 15  98  17  377

I did some profiling and didn't find an obvious reason why the 
two-thread is slower. Therefore, I guess that the reason is the 
multi-threading implementation of Python (which could be better, as 
mentioned in the discussion about the hack). The guess is also supported 
by the fact that having an own thread for every callback, which I also 
tried, turned out to be really slow.


Unit tests:
All unit test get passed, even the previosly skipped 
test_multiple_callbacks. This because I added the @increment_pc 
decorator to schedule_callback(). This of course changes the program 
counters heavily but I didn't experience any problems.


Best regards,
Marcel
diff -r e2759515f57f apps/aes.py
--- a/apps/aes.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/apps/aes.py	Tue Apr 21 17:25:45 2009 +0200
@@ -82,7 +82,7 @@
 rt.shutdown()
 
 g = gather_shares(opened_ciphertext)
-g.addCallback(fin)
+rt.schedule_callback(g, fin)
 
 def share_key(rt):
 key =  []
diff -r e2759515f57f apps/benchmark.py
--- a/apps/benchmark.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/apps/benchmark.py	Tue Apr 21 17:25:45 2009 +0200
@@ -91,6 +91,7 @@
 print "Total time used: %.3f sec" % (stop-start)
 print "Time per %s operation: %.0f ms" % (what, 1000*(stop-start) / count)
 print "*" * 6
+sys.stdout.flush()
 
 
 operations = ["mul", "compToft05", "compToft07", "eq"]
@@ -174,7 +175,7 @@
 # run with no preprocessing. So they are quite brittle.
 if self.operation == operator.mul:
 key = ("generate_triples", (Zp,))
-desc = [(i, 1, 0) for i in range(2, 2 + count)]
+desc = [(2, 2, 2 * count + 1, 2, i, 1, 0) for i in range(1, count + 1)]
 program_desc.setdefault(key, []).extend(desc)
 elif isinstance(self.rt, ComparisonToft05Mixin):
 key = ("generate_triples", (GF256,))
@@ -228,7 +229,8 @@
 if seconds > 0:
 print "Starting test in %d" % seconds
 sys.stdout.flush()
-reactor.callLater(1, self.countdown, None, seconds - 1)
+time.sleep(1)
+self.countdown(None, seconds - 1)
 else:
 print "Starting test now"
 sys.stdout.flush()
@@ -255,6 +257,7 @@
 def run_test(self, _):
 c_shares = []
 record_start("parallel test")
+sys.stdout.flush()
 while self.a_shares and self.b_shares:
 a = self.a_shares.pop()
 b = self.b_shares.pop()
diff -r e2759515f57f apps/millionaires.py
--- a/apps/millionaires.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/apps/millionaires.py	Tue Apr 21 17:25:45 2009 +0200
@@ -97,10 +97,10 @@
 # the argument (which is None since self.results_ready does
 # not return anything), so we throw it away using a lambda
 # expressions which ignores its first argument.
-results.addCallback(lambda _: runtime.synchronize())
+runtime.schedule_callback(results, lambda _: runtime.synchronize())
 # The next callback shuts the runtime down, killing the
 # connections between the players.
-results.addCallback(lambda _: runtime.shutdown())
+runtime.schedule_callback(results, lambda _: runtime.shutdown())
 
 def results_ready(self, results):
 # Since this method is called as a callback above, the results
diff -r e2759515f57f viff/active.py
--- a/viff/active.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/active.py	Tue Apr 21 17:25:45 2009 +0200
@@ -501,6 +501,7 @@
 result = Share(self, share_x.field)
 # This is the Deferred we will do processing on.
 triple = self.get_triple(share_x.field)
+

Re: [viff-devel] Confusing behaviour?

[Marcel Keller]

I think the problem is the following: Every players sends its id on a 
new connection, and the connection is considered to be set up when this 
id arrives. So it may occur that a player has received the ids from all 
other players and wants to send its id to other player(s). But nothing 
is sent before all callbacks are executed. Since the player considers 
all connections to made, also the main callback, which blocks, is 
executed. Therefore, the problem is somehow related to what I'm working 
on because in a two-threaded solution the Twisted reactor is (nearly) 
never blocked. However, your problem probably could be fixed by 
synchronizing before blocking:


sync = runtime.synchronize()
sync.schedule_callback(blocking_code())

Thomas P Jakobsen wrote:

Hi all,

When I execute the attached VIFF protocol on three servers I would
expect all three to ask me to press enter. When all three servers have
done that, I would expect the computation of c to start and that the
servers will eventually finish.

I've run the protocol several times on Linux and Windows. What happens is this:

Sometimes it works out as expected, but at other times only two of the
servers will ask the user to press enter. In some cases, the third
server will ask its user to press enter as soon as one of the two
other servers presses enter. At other times, the third server will
first wake up and ask its user to press enter when both of the two
first servers have pressed enter.

I find this behaviour confusing (..twisted?) and wonder whether it is
a bug or a feature? If it's a bug, could it be related to the issue
discussed in the thread "Mystery of the quadratic running time
solved?". I must admit that I haven't followed that thread in
detail...

By the way, the same thing seem sto happen if the protocol, insted of
asking the user to press enter, does some local computations like
quering a database, sleeping, computing primes or the like. Sometimes,
one of the servers will sit still until one or both of the other
servers have finished their local jobs. This was how I initially
stumbled across the problem.

Best regards,
Thomas

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

Hi Ivan,

I just wanted to say that I think it would be great if you would 
implement a version of your proposed two-threaded solution. I do not 
have a firm grasp of all the programming details, but it does seem that 
the overall idea is converging, and that some time soon the best way to 
judge the idea is to go ahead and do it.


OK, i will start doing it next Monday.

Note that Alexandra is committed to using a non-trivial amount of 
resources on developing VIFF and related software. Although this may not 
mean that lots of man-hours are available just now, it might be possible 
that they could help you.
It may also be more efficient that one guy does it in the first 
iteration, I'll leave this up to you.


Since it doesn't seem that complicated to me, I will try it on my own 
first. But I keep that in mind for the case that I'm wrong.


Note that myself, Martin and Jakob will not be at the meeting Thursday. 
Maybe we should postpone the meeting until next week?


Me neither, I'm on holidays until the weekend. Therefore, I would agree 
to postpone the meeting.


Best regards,
Marcel

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

I think we would get the same result if we started a LoopingCall that
executes process_deferred_queue with an interval of, say, 100 ms:

  
http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.task.LoopingCall.html

This should work since the runUntilCurrent method runs through the
waiting calls and will trigger our process_deferred_queue method.

And voilá -- no hacking of the Twisted source needed.

I'm not sure but LoopingCall._reschedule() looks more like it
schedules the calls at certain tick, not as soon as possible after the
interval is elapsed. This might not cost too much time but still
doesn't feel very elegant. Furthermore, setting the interval very low
leads to high CPU usage when waiting. Again, this is not too bad but
not elegant either. The same applies if using reactor.callLater()
directly.


A looping call is just a higher level wraper for doing

  def reschedule(func):
func()
reactor.callLater(interval, reschedule, func)

  reschedule(func)

It will execute the function when the (now + interval) time has been
reached and when the control flow returns to the reactor's event loop.
We probably wont need the extra logic in a looping call, so we can just
let the function reschedule itself like above.


That's what I meant with calling reactor.callLater() directly.


If we do this with an interval of 0, then the function will be called on
each iteration through the reactor's event loop -- just like your
loopCall I believe?


Not exactly because it also sets the timeout of the select call to 0
leading to 100% CPU usage while when we are waiting.


diff -r e2759515f57f viff/runtime.py
--- a/viff/runtime.py   Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/runtime.py   Fri Mar 06 13:43:14 2009 +0100
@@ -306,6 +306,8 @@
 deferred = deq.popleft()
 if not deq:
 del self.incoming_data[key]
+# just queue
+self.factory.runtime.queue_deferred(deferred)

Why is this done?

At this time, we shouldn't call the callbacks because we might recurse
into selectreactor.doSelect(). However, we want to know which
deferreds are ready so we can call deferred.callback() later.


Uhh, this sounds a bit dangerous -- do we know exactly which Deferreds
we can invoke callback on and which we cannot? As I remember, we invoke
callback in a couple of other locations, is that safe?


Yes, it is safe because the callback is called only once. When the data 
arrives, the Deferreds are paused, appended to the queue, and the 
callback is called. The Deferres in the queue are unpaused and removed 
in process_deferred_queue(). As far as I know you can pause and unpause 
Deferreds as you like.



If that doesn't matter, then I think this would be faster:

  queue, self.deferred_queue = self.deferred_queue, []
  map(Deferred.unpause, queue)

My idea is that looping over the list with map is faster than
repeatedly popping items from the beginning (an O(n) operation).

But map() still would need O(n) time because that is the nature of
calling a function n times, isn't it? Maybe the function calls are
optimized but the code in the function still is called n times.


Each pop(0) call is an O(n) operation, so we get O(n^2) here -- it is an
expensive way to loop through a list. And now that I look at it, using
map will still unpause the Deferreds in the order as you added them.


OK, I wasn't aware that pop(0) is O(n), but I still think that the
complexities should be added resulting in running time O(n) again. Using 
a linked list would be more reasonable, of course.



The difference is then that anything added to the queue as a result of
the unpause calls will be processed the next time the code is called.


Yes, and the Deferreds in the queue previously would wait. I considered 
it to be more safe if the Deferreds are processed in the order they arrive.



A question springs to my mind: calling

  reactor.runUntilCurrent()
  reactor.doIteration(0)

is the same as calling

  reactor.iterate(0)

and the documentation for that method says:

  [...] This method is not re-entrant: you must not call it recursively;
  in particular, you must not call it while the reactor is running.

How does your code ensure that we only call myIteration when we're
not in a call made by the reactor? And could we simply call
reactor.iterate instead?

We actually call it recursively but it should be reentrant if it's not
called from doIteration(). doIteration() is a the same as
select.doSelect(), which certainly is not reentrant. We however call
it from the loop call (process_deferred_queue()) after doIterate().

Calling reactor.iterate() is not enough because it doesn't call
process_deferred_queue().


So if we call reactor.iterate and then runtime.process_deferred_queue as

  reactor.callLater(0, reactor.iterate)
  reactor.callLater(0, runtime.process_deferred_queue)

we should be fine? They would then both run one after another just as
soon as the event loop is rea

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

You're talking about this two-threaded solution as if it is something
that exists and will solve all our problems...


No, for now, it's just an imagination in my mind, a proposal for the 
next meeting, and a strong feeling that it's the right way to do it.



But I still haven't seen it, and I would like to see how you can cleanly
seperate the work of the two threads. I'm afraid that the threads will
be alternating between working and waiting on the other thread in such a
way that we could just as well use one thread.


My idea is that the Twisted main loop runs in one thread and most of the 
VIFF code in the other. The Twisted thread only waits for I/O and the 
VIFF thread only waits if there is no work to be done.


If the group decides to give this idea a try, I would be happy to 
implement it. I would claim that it can be done in one or two weeks.



Also, threading in Python is unfortunately not optimal :-( The Python VM
will use a single thread to execute the bytecode, even when using
multiple thread in Python. It is only if the threads do things blocking
for I/O that you will see a performance increase by using multiple
threads.


I'm aware that Python only runs on one CPU, a friend pointed that out to 
me today. However, the Twisted thread mentioned above would block on I/O.


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Multiparty AES in less than 3 seconds per block thanks to Twisted hack

[Marcel Keller]

For those who are not on the Twisted mailing list, the reply is here:

  http://twistedmatrix.com/pipermail/twisted-python/2009-February/019252.html

There Jean-Paul Calderone says that he doesn't believe in a re-entrent
reactor, but he does not explain in detail why that it so.


I think there are good reasons not to believe in a re-entrant reactor.


My guess is that a generally re-entrent reactor could end up doing a lot
of recursion where each recursion step holds unto a local scope and
thereby keeps local variables from being reclaimed by the garbage
collector. A simple loop does not have that problem, so I can understand
why the Twisted guys will want to keep the design as simple as possible.


Me too, I think I mentioned at some time that I didn't expect them to 
accept my hack.



I'll try and write a mail to them to explain our problem in more detail.
Maybe your short patch didn't provide enough information when taken out
of context.


That may be true. I just thought that I don't want to bother him with 
VIFF code.



- It breaks some unit tests. I'm not sure whether it really breaks
functionality or just the unit testing tool of Twisted.


Are these VIFF (trial viff) or Twisted (trial twisted) unit tests? In
any case, we have to fix this if there in order to keep our sanity :-)


The VIFF unit tests. Though I didn't execute the Twisted unit tests, I 
think that they would success since there no changes to Twisted if the 
loop call is not used.



As I said at the meeting, a possibility would be to go multi-threaded.
The Twisted maintainer suggested another way but I don't think that
that way works for us.


Do you mean the inlineCallbacks or the coiterate? And why it not work?


As far as I understood it, inlineCallbacks would stop the VIFF code, 
which would make it not asynchronous anymore. Coiterate needs generator 
functions. Maybe I'm wrong but I just consider the VIFF code to be too 
complex to be put in generator functions.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

Indeed we did not know (well I didn't) back then that the data was
not sent immediately by Twisted, and I was starting to think
yesterday whether the hack would make a difference. Lucky for us, it
apparently does :)

That is not the only problem. To free the memory of the shares and to
send out further shares, also the incoming shares must be processed as
soon as possible. This is even trickier because incoming shares might
trigger code that calls functions sending out data, which activates
the Twisted reactor again and therefore leads to a possibly too deep
recursion. I think I have a solution for that, it just wasn't
necessary to implement it for now because the hack worked anyway.


I guess we could simply not recurse if the recursion depth is too big?

At some point we have to let the recursive calls finish in order to let
the local variables and stack frames be garbage collected.


Yes, but If we just stop recursing at a certain level, we might just 
stay at that level for a longer time. That is also not optimal. In my 
opinion, another point for the two-threaded solution.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

Wow, this is nice! I had sort of given up finding the cause of this :-(
Thank you for looking at this, and just in time for my presentation at
PKC in 10 days :-)


You're welcome. :-)


--- /usr/lib/python2.5/site-packages/twisted/internet/base.py   2008-07-29 
22:13:54.0 +0200
+++ internet/base.py2009-02-20 12:27:42.0 +0100
@@ -1127,17 +1127,32 @@
 self.startRunning(installSignalHandlers=installSignalHandlers)
 self.mainLoop()
 
+
+def setLoopCall(self, f, *args, **kw):

+self.loopCall = (f, args, kw)
+
+
+def myIteration(self, t):
+# Advance simulation time in delayed event
+# processors.
+self.runUntilCurrent()
+
+if (t is None):
+t2 = self.timeout()
+t = self.running and t2
+
+self.doIteration(t)
+
+if ("loopCall" in dir(self)):
+f, args, kw = self.loopCall
+f(*args, **kw)
+
 
 def mainLoop(self):

 while self._started:
 try:
 while self._started:
-# Advance simulation time in delayed event
-# processors.
-self.runUntilCurrent()
-t2 = self.timeout()
-t = self.running and t2
-self.doIteration(t)
+self.myIteration(None)
 except:
 log.msg("Unexpected error in main loop.")
 log.err()


The changes above basically insert a call to self.loopCall after each
doIteration invocation, right?

When the loopCall is process_deferred_queue the main loop becomes:

  self.runUntilCurrent()
  self.doIteration(t)
  runtime.process_deferred_queue

  self.runUntilCurrent()
  self.doIteration(t)
  runtime.process_deferred_queue

  ...


Yes, exactly.


I think we would get the same result if we started a LoopingCall that
executes process_deferred_queue with an interval of, say, 100 ms:

  
http://twistedmatrix.com/documents/8.2.0/api/twisted.internet.task.LoopingCall.html

This should work since the runUntilCurrent method runs through the
waiting calls and will trigger our process_deferred_queue method.

And voilá -- no hacking of the Twisted source needed.


I'm not sure but LoopingCall._reschedule() looks more like it schedules 
the calls at certain tick, not as soon as possible after the interval is 
elapsed. This might not cost too much time but still doesn't feel very 
elegant. Furthermore, setting the interval very low leads to high CPU 
usage when waiting. Again, this is not too bad but not elegant either. 
The same applies if using reactor.callLater() directly.


Of course, we can avoid hacking the Twisted code by extending it within 
VIFF. Still, I'm in favor of the two-threaded solution because it's more 
elegant, doesn't have the danger of recursing too deep, and, in my 
opinion, it should be feasible.



diff -r e2759515f57f viff/runtime.py
--- a/viff/runtime.py   Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/runtime.py   Fri Mar 06 13:43:14 2009 +0100
@@ -306,6 +306,8 @@
 deferred = deq.popleft()
 if not deq:
 del self.incoming_data[key]
+# just queue
+self.factory.runtime.queue_deferred(deferred)


Why is this done?


At this time, we shouldn't call the callbacks because we might recurse 
into selectreactor.doSelect(). However, we want to know which deferreds 
are ready so we can call deferred.callback() later.



+#: Activation depth counter
+self.depth_counter = 0


This is for keeping track of the recursion depth in the future?


Yes. It was used in some debug output earlier but I removed it to 
simplify the patch.



+def queue_deferred(self, deferred):
+deferred.pause()
+self.deferred_queue.append(deferred)
+
+def process_deferred_queue(self):
+while(self.deferred_queue):
+deferred = self.deferred_queue.pop(0)
+deferred.unpause()


Are you doing it this way to ensure that the Deferreds are unpaused in
the same order as they were added to the list?


Yes. I'm not sure whether this is really necessary but it seems just 
cleaner because the callback of the some deferred might do a lot of 
computations and recurse, which unnecessarily extends the lifetime of 
the remaining deferreds.



If that doesn't matter, then I think this would be faster:

  queue, self.deferred_queue = self.deferred_queue, []
  map(Deferred.unpause, queue)

My idea is that looping over the list with map is faster than repeatedly
popping items from the beginning (an O(n) operation).


But map() still would need O(n) time because that is the nature of 
calling a function n times, isn't it? Maybe the function calls are 
optimized but the code in the function still is called n times.



+def activate_reactor(self):
+self.activation_counter += 1
+
+# setting the number to n makes the reactor called

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

That is not the only problem. To free the memory of the shares and to 
send out further shares, also the incoming shares must be processed as 
soon as possible. This is even trickier because incoming shares might 
trigger code that calls functions sending out data, which activates 
the Twisted reactor again and therefore leads to a possibly too deep 
recursion. I think I have a solution for that, it just wasn't 
necessary to implement it for now because the hack worked anyway.


Ah, but the numbers I had been shown did not indicate we were anywhere 
near running out of memory. That's not to say memory isn't important (it 
certainly will be in cases with huge amounts of operations), I just 
didn't think it had anything to do with our specific test cases for the 
paper.


Sorry, maybe I expressed myself not clear enough: We are not running out 
of memory, we are too slow because there are delays due to the control 
flow. I think that higher memory usage is just a side effect.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

Indeed we did not know 
(well I didn't) back then that the data was not sent immediately by 
Twisted, and I was starting to think yesterday whether the hack would 
make a difference. Lucky for us, it apparently does :)


That is not the only problem. To free the memory of the shares and to 
send out further shares, also the incoming shares must be processed as 
soon as possible. This is even trickier because incoming shares might 
trigger code that calls functions sending out data, which activates the 
Twisted reactor again and therefore leads to a possibly too deep 
recursion. I think I have a solution for that, it just wasn't necessary 
to implement it for now because the hack worked anyway.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Mystery of the quadratic running time solved?

[Marcel Keller]

Hello friends of VIFF,

I've now run the benchmark of actively secure multiplications with 
hyperinvertible matrices together with my hack. Here are my results 
(column 1 and 2) compared to the results in the paper "Asynchronous 
Multiparty Computation: Theory and Implementation" (column 3 and 4):


(n,t)   online  preprocessing   online  preprocessing
(4,1)   5   18  4   20
(7,2)   7   30  6   42
(10,3)  9   43  8   82
(13,4)  12  56  10  136

The preprocessing time now seems to be linear whereas the online time is 
slightly increased. I didn't benchmark bigger thresholds because it's 
difficult enough find 13 camels which are not hard ridden yet. I think I 
 also fixed the increased online time, but I couldn't test the fix 
thoroughly because the active adversaries continuously change the 
corrupted camels.


Again, there are two patches in the attachement, and again, the patch 
for VIFF is against the current tip of my repository: 
http://hg.viff.dk/mkeller/rev/e2759515f57f


Best regards,
Marcel

--- /usr/lib/python2.5/site-packages/twisted/internet/base.py	2008-07-29 22:13:54.0 +0200
+++ internet/base.py	2009-02-20 12:27:42.0 +0100
@@ -1127,17 +1127,32 @@
 self.startRunning(installSignalHandlers=installSignalHandlers)
 self.mainLoop()
 
+
+def setLoopCall(self, f, *args, **kw):
+self.loopCall = (f, args, kw)
+
+
+def myIteration(self, t):
+# Advance simulation time in delayed event
+# processors.
+self.runUntilCurrent()
+
+if (t is None):
+t2 = self.timeout()
+t = self.running and t2
+
+self.doIteration(t)
+
+if ("loopCall" in dir(self)):
+f, args, kw = self.loopCall
+f(*args, **kw)
+
 
 def mainLoop(self):
 while self._started:
 try:
 while self._started:
-# Advance simulation time in delayed event
-# processors.
-self.runUntilCurrent()
-t2 = self.timeout()
-t = self.running and t2
-self.doIteration(t)
+self.myIteration(None)
 except:
 log.msg("Unexpected error in main loop.")
 log.err()
diff -r e2759515f57f viff/active.py
--- a/viff/active.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/active.py	Fri Mar 06 13:43:14 2009 +0100
@@ -69,6 +69,9 @@
 for protocol in self.protocols.itervalues():
 protocol.sendData(pc, data_type, message)
 
+# do actual communication
+self.activate_reactor()
+
 def echo_received(message, peer_id):
 # This is called when we receive an echo message. It
 # updates the echo count for the message and enters the
@@ -132,6 +135,8 @@
 d_send = Deferred().addCallback(send_received)
 self._expect_data(sender, "send", d_send)
 
+# do actual communication
+self.activate_reactor()
 
 return result
 
@@ -260,6 +265,9 @@
 # first T shares.
 return rvec[:T]
 
+# do actual communication
+self.activate_reactor()
+
 result = gather_shares(svec[T:])
 self.schedule_callback(result, exchange)
 return result
@@ -360,6 +368,9 @@
 # first T shares.
 return (rvec1[:T], rvec2[:T])
 
+# do actual communication
+self.activate_reactor()
+
 result = gather_shares([gather_shares(svec1[T:]), gather_shares(svec2[T:])])
 self.schedule_callback(result, exchange)
 return result
diff -r e2759515f57f viff/passive.py
--- a/viff/passive.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/passive.py	Fri Mar 06 13:43:14 2009 +0100
@@ -104,6 +104,10 @@
 
 result = share.clone()
 self.schedule_callback(result, exchange)
+
+# do actual communication
+self.activate_reactor()
+
 if self.id in receivers:
 return result
 
@@ -209,6 +213,10 @@
 result = gather_shares([share_a, share_b])
 result.addCallback(lambda (a, b): a * b)
 self.schedule_callback(result, share_recombine)
+
+# do actual communication
+self.activate_reactor()
+
 return result
 
 def pow(self, share, exponent):
@@ -484,6 +492,9 @@
 else:
 results.append(self._expect_share(peer_id, field))
 
+# do actual communication
+self.activate_reactor()
+
 # Unpack a singleton list.
 if len(results) == 1:
 return results[0]
diff -r e2759515f57f viff/runtime.py
--- a/viff/runtime.py	Thu Mar 05 21:02:57 2009 +0100
+++ b/viff/runtime.py	Fri Mar 06 13:43:14 2009 +0100
@@ -306,6 +306,8 @@
 deferred = deq.popleft()
 if not deq:
   

Re: [viff-devel] Multiparty AES in less than 3 seconds per block thanks to Twisted hack

[Marcel Keller]

Hi Ivan,

> For instance, you call what you did a hack - is there a more

"official" way to do it?


I call it a hack because of two reasons:
- The maintainer of Twisted doesn't want to implement something similar 
upstream.
- It breaks some unit tests. I'm not sure whether it really breaks 
functionality or just the unit testing tool of Twisted.


As I said at the meeting, a possibility would be to go multi-threaded. 
The Twisted maintainer suggested another way but I don't think that that 
way works for us. If we manage to solve the problem with the unit tests, 
we could of course somehow modify the relevant part of Twisted from 
within VIFF.


Best regards,
Marcel


I've now implemented the hack I mentioned at the last SIMAP/CACE 
meeting. The quintessence of the hack is that we do network 
communication every time a multiplication or open operation is 
scheduled, not only after returning the control back to Twisted.


___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Multi-party AES encryption

[Marcel Keller]

Hi,

VIFF now supports AES encryption (but not decryption). You find it in 
the repository http://hg.viff.dk/mkeller. There is an example 
application in the apps directory.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] VIFF and large scale programs -- is VIFF really asynchronous?

[Marcel Keller]

> A really unpleasant thought has occurred to me: Is VIFF really properly
> asynchronous? (Yes, this question is intended to provoke you into thinking
> about the issue below. Of course VIFF is asynchronous in the sense that
> there are no rounds.)
>
>
>
> If I understand/remember correctly, VIFF is 100% single threaded. This
> means that if we have a small program:
>
> x, y = runtime.shamir_share([1, 2], Zp, input)
> z = x*y
> for i in xrange(100):
>   z=z*z
>
> 1) We first share two values (returning immediately).

There's a pitfall here: What do you mean with "share"? At this point, the 
shares are only scheduled to be sent, the real communication doesn't occur 
until step 3. The FAQ of Twisted says so: 
http://twistedmatrix.com/trac/wiki/FrequentlyAskedQuestions#WhydoesittakealongtimefordataIsendwithtransport.writetoarriveattheothersideoftheconnection
Since I discussed this issue last week with Martin, I also looked at the 
source of Twisted 8.1.0 to confirm it.

> 2) We start doing a lot of multiplications. However, as we don't have
> the actual shares yet, we just get deferreds.
>
> 3) Once the for-loop terminates, we return control to the
> surroundings. At this point we notice that the shares of x and y are
> there and start the actual multiplication protocols.
>
>
>
> Is my interpretation above correct? Because if it is, then this really
> explains the memory issues I've been seeing. And more importantly, it
> tells us how to actually use VIFF for large-scale computation: put in
> explicit "stops".

As Mikkel wrote, I had the same issues and I solved them by calling parts of 
my code (one AES round at a time) as a callback of some trigger shares.
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] ComparisonToft07Mixin

[Marcel Keller]

Hi

Does anyone know of a documentation explaining the code in the 
ComparisonToft07Mixin class in comparison.py? I've read the relevant 
part of Tomas' dissertation but it seems that the algorithm there is 
different.


Best regards,
Marcel
___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

Re: [viff-devel] Viff installation on Gentoo

[Marcel Keller]

Martin Geisler schrieb:

Marcel Keller <[EMAIL PROTECTED]> writes:


As requested, here is the command to install the dependencies on Gentoo:

$ emerge -av twisted gmpy

Make sure to have the crypt use flag enabled, otherwise SSL might not
be available.


Thank you very much! I have included this in the online installation
guide:

  http://viff.dk/doc/install.html#gnu-linux

The Debian instructions include pyOpenSSL too, should the Gentoo
instructions not have that as well?


If the crypt use flag is enabled, pyOpenSSL is a dependency of twisted. 
One could also install pyOpenSSL directly (emerge pyopenssl), but that 
will be broken if twisted changes its SSL library. On the other hand, 
the use flag could also change.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk

[viff-devel] Viff installation on Gentoo

[Marcel Keller]

As requested, here is the command to install the dependencies on Gentoo:

$ emerge -av twisted gmpy

Make sure to have the crypt use flag enabled, otherwise SSL might not be 
available.

___
viff-devel mailing list (http://viff.dk/)
viff-devel@viff.dk
http://lists.viff.dk/listinfo.cgi/viff-devel-viff.dk