\section{Discussion}
\label{sec:discussion}
\newcommand{\ec}[0]{\emph{ec}\xspace}

\newcommand{\mg}[0]{\emph{mg}\xspace}

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.

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.

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.

\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}.

\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.

\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. 

\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}
	
\subsection{Realtime precomputation}

Here is a large time saver, namely \ec is $81.90$ times faster. Additionally it is a time saver in the realtime portion of the protocol. This will massively impact perceived latency by the clients. So if that is your goal then \ec seems to be the way to go.

Why \ec is so much faster is uncertain. This step consist of removing the shared key the user and node agreed upon during initialization, and adding the $r$ value of the node for this client slot, see section \ref{sec:realpre}. It could be related to the fact that no encryption is applied at this stage of the protocol. And maybe because the elliptic curve is in comparison so much smaller that it saves exponentially more time than the \mg algorithm.

\subsection{Realtime mix and realtime postcomputation}
The problem with these 2 phases is that the duration of these phases are relatively short and therefore are more unreliable to derive any information from. For instance the Realtime mix operation seems to be slower in \ec. This could be the case and could be again explained by the serialization choices made for elliptic curve points. However the difference is so small with respect to the clock resolution that it is risky to claim this. It could be that these phases are calling more functions and we are just measuring the indirection overhead of the \cmix library implementation.

It could also be due to memory fragmentation. The \ec implementation is uses smaller elements, allocating an element size buffer has a bigger chance to succeed within just cleared memory, but subsequent buffers might not find free bytes in the neighborhood. I try to minimize this by allocating all the elements I need at a time. However I don't have much control over for instance the protobuf library. I use the arena allocator from libprotobuf\cite{protobuf-arena} but have no idea how large these arenas are and how the cache locality is for the \cmix network messages.

In short there is not many conclusions we can derive from these results. However these phases seem to be similar between the 2 implementations. One interesting thing here is the Realtime phase in node 3 of both \ec and \mg. It takes quite some more time to remove the R and S than I expected that being said it seems to take about 3 times as long for \mg than \ec and that gives us some insight how long it takes to invert an element in both implementations.

\subsection{Precomputation phase}

The complete precomputation phase on average takes $22.98$ seconds for \ec versus $175.49$ seconds for \mg. So for elliptic curve to be  worth it we would need to make it a bit faster than it now is. But I fully believe it is possible. Again removing the unnecessary inversions would help. Using a different cryptographic library as backend for the ed25519 cryptography would have a much greater impact. How useful libgcrypt may have been for experimenting and debugging certain aspects of the application, it's cryptographic routines might not be as optimized as say an ed25519-donna. That being said ed25519-donna does not implement all the primitives I need to implement all the \cmix primitives. But creating a custom ed25519 library or using one that does support all the primitives \cmix needs would make a huge impact on the performance.

This also holds for the multiplicative group implementation of libgcrypt but I expect that both algorithms would have the same level optimization within the library, because both implementation use the underlying big integer library and operations.

\subsection{Realtime phase}

The complete realtime phase on average takes $2.06$ seconds for \ec versus $75.81$ seconds for \mg. So in the Realtime phase using ed25519 is really worth it.



