From fffc35ad3c397359b29f30949547e2c767198600 Mon Sep 17 00:00:00 2001
From: Dennis Brentjes <dennis@brentj.es>
Date: Mon, 21 May 2018 17:10:57 +0200
Subject: changed results and conclusion stuff.

---
 content/discussion.tex | 24 ++++++++++++------------
 1 file changed, 12 insertions(+), 12 deletions(-)

(limited to 'content/discussion.tex')

diff --git a/content/discussion.tex b/content/discussion.tex
index ff3a688..23196a9 100644
--- a/content/discussion.tex
+++ b/content/discussion.tex
@@ -6,37 +6,37 @@
 
 In this section \ec and \mg will refer to the 2 different implementations that we compare. They stand for elliptic curve and multiplicative group.
 
-So lets first talk about what our expectations are. The size of the messages being sent are different. The ed25519 implementation can send messages up to $31$ bytes. The 2048 bit multiplicative group can send up to $255$ bytes of data. This implementation uses a prefix to the message data that is the destination id. This takes up $20$ bytes of each message, as it is the SHA1 hash of the public key of the receiver. this means that the ed25519 implementation only sends $11$ bytes of payload versus $235$ bytes of payload for the multiplicative group implementation.
+So lets first talk about what our expectations will be.
+The size of the 2 types of messages, for \mg and \ec, are slightly different.
+We use a 2048 bit multiplicative group so we have 256 byte messages.
+Ed25519 has a little below 255 bit group elements giving us less then 32 byte messages.
+For convenience and because we're using Koblitz's method we only use 31 byte for the message part. But to counter this we do 8 mixes at a time to go up to 248 byte messages. Still 8 bytes short, but this makes the timings more comparable.
 
-However there are ways around this. By doing 8 mixes of the ed25519 implementation in one single \cmix run with the same permutation functions but with different $R$ and $S$, we can significantly boost the effective payload. The effective payload of the ed25519 algorithm would become $228$ bytes versus $235$ bytes of the multiplicative group. This is why I will consider the payload difference between the multiplicative group and the ed25519 implementation to be a factor of $8$.
+Note that these separate runs of the ed25519 protocol can trivially be parallelized, possibly making it even more interesting by comparison. But as we are interested in a straight up comparison this implementation does not use a parallelized implementation of multiple mixes.
 
-Note that these separate runs of the ed25519 protocol can trivially be parallelized, possibly making it even more interesting by comparison.
+This implementation uses a prefix to the message data that is the destination id. This takes up $20$ bytes of each message, as it is the SHA1 hash of the public key of the receiver.So the payload would become $236$ and $228$ bytes for \mg and \ec respectively.
 
-So by the above dissertation, we hope to see that \ec is 8 times faster than \mg in all respects. Just by the virtue of only having to handle $\frac{1}{8}$ of the data. We hope to even be a bit faster than that.
+So by the above dissertation, we hope to see that \ec is faster than \mg in all respects. This would mean it would be beneficial to research parallelism and more optimal implementations in the future.
 
 \subsection{Precomputation precomputation}
 
-First of all this step does not seems to differ between nodes, all \ec nodes spend around $3.67s$ and the \mg nodes spend about $19.19s$. Which is $5.23$ times faster, not the 8 times we would expect.
-
-This can easily be explained by the way one generates random curve points on an elliptic curve. You have to generate a random number and check, in the case of ed25519, if that number is a valid $y$ coordinate. For Ed25519 about half of the possible $y$ values are valid, so the chance that a randomly generated number is valid will be $.5$. Because of this you need to, on average, generate and check twice as many coordinates as the actual number of random curve points you want, see equation \ref{eq:prepre}.
+Right away we can see a large difference between \ec and \mg, with \ec being more than $2$ times slower. Most likely this can be explained by 2 factors. The first being that this step includes generating all the randomness needed for the \cmix run. It generates $R$ and $S$ and the permutation $\pi$. For Ed25519 it tries a $Y$-value and if it doesn't map onto the curve we try a different one. On average only half of the points would be valid.
 
 \begin{equation}
 \label{eq:prepre}
 \sum_{x=0}^{\infty} n \cdot \left( \frac{1}{2}\right)^x =\ 2n
 \end{equation} 
 
-Therefore we only expect to be 4 times faster in that regard we are still slightly faster than the \mg counterpart, but \ec is slower on a fundamental level because of the extra calculations needed to generate random curve points.
+Another slowing factor might be the memory fragmentation. The way that libgcrypt operates is that each object is it's own opaque pointer to an internal data structure. So there is no way to consolidate memory into a single block. This wouldn't be a factor if both algorithms would use the same amount of allocations, but now that we do 8 simultaneous mixes for \ec we have 8 times the amount of the allocations for the \ec algorithm. This impacts the performance quite heavily 
 
 \subsection{Precomputation mixing}
 \label{sec:premix}
 
-The values for the premix step are very close to our ideal 8 times ratio, $6.79$ times faster. There is however no fundamental explanation why it should be slower than expected. There is however one implementation detail that might have had it's influence here.
-
-Like discussed in section \ref{sec:wireformat}, when serializing elliptic curve points, there are several choices you can make about the format. This implementation chose to send both affine coordinates, which adds unnecessary group element inversions. This means There is time to gain if we switch from affine to projected coordinate system within the network format. it would mean sending more data. However the conversions from network to internal format would be faster and it would avoid the inversion of $Z$. This would be a large time saver for many of the steps, even the $prepre$ step we already discussed. My expectation based on some informal testing and the results of the realtime postprocessing phase  is that it would make this step at least 8 times faster than the \mg implementation making it comparable in performance. 
+Another big time loss is attributed to the wire format chosen. because we only send over the Y coordinate, we need to convert the coordinate from projected to affine coordinate systems. This takes up extra time which can be eliminated if we choose. Unfortunately if we want to do this using libgcrypt we need to send over all 3 projected coordinates as there is no way to use only the $Y$ and $Z$ coordinates to reconstruct the curve point in libgcrypt.
 
 \subsection{Precomputation postprocessing}
 
-So here in the precomputation post-computation phase the elliptic curve algorithm pays off. with $1.17s$ vs $20.16s$ a $17.26$ times speed increase. This is probably because the inversions in \mg are much more computational intensive as inversions in \ec. This does not mean that they are free in \ec as discussed in section \ref{sec:premix}
+In this stage we only do a `simple' cryptographic operation on each of the points to determine the node's decryption share. There are no extra allocations and no unneeded inversions, and we can see \ec is *2.5* times faster.
 	
 \subsection{Realtime precomputation}
 
-- 
cgit v1.2.3-70-g09d2

