Applied Colins feedback.HEADmaster

1 files changed, 40 insertions, 40 deletions

diff --git a/content/implementation.tex b/content/implementation.tex
index abd05aa..98435e7 100644
--- a/content/implementation.tex
+++ b/content/implementation.tex
@@ -1,7 +1,7 @@
 \section{Implementation}
 \label{sec:implementation}
 
-A large portion of research effort was consumed by the implementation of \cmix and benchmark framework. Including setting up the benchmarking infrastructure in such a way that it;
+A large portion of research effort was consumed by the implementation of \cmix{} and benchmark framework. Including setting up the benchmarking infrastructure in such a way that it.
 
 \begin{itemize}
 	\item Supports multiple but subtly different cryptographic back-ends.
@@ -9,94 +9,94 @@ A large portion of research effort was consumed by the implementation of \cmix a
 	\item Allows different back-ends to be comparably benchmarked.
 \end{itemize}
 
-The following section will talk about some implementation specific things, talking about how this framework achieves these goals and where things could be improved. Information on where to find the implementation can be found in appendix \ref{app:impl}
+The following section will talk about some implementation specific details, talking about how this framework achieves these goals and where things could be improved. Information on where to find the implementation can be found in Appendix \autoref{app:impl}
 
 \subsection{Overview of the software}
 
-The software consists of 9 modules, either small libraries or separate binaries. The modules are;
+The software consists of nine modules. The modules are.
 
 \begin{description}
-	\item[libcmix-crypto] Library containing the API definition of both the generic API and the specific API's for both multiplicative group and elliptic curve variants of the API. Supplying the real cryptographic operations to implement \cmix in. This library is responsible for filling the generic API with the corresponding specific API. The specific API can be chosen at project configuration time.
+	\item[libcmix-crypto] Library containing the API definition of both the generic API and the specific API's for both the multiplicative group and elliptic curve variants of the API. These specific implementations supply the real cryptographic operations that facilitate the implementation of \cmix{}. The specific API can be chosen at project configuration time.
 	
-	\item[libcmix] This library contains the implmentation of \cmix using $libcmix{\text -}crypto$. This library only supplies \cmix related data structures and operations. The library operates by passing each call to a library function a so called $CMixContext$ structure, which in turn contains a generic API. 
+	\item[libcmix] Library containing the implementation of \cmix{} using $libcmix{\text -}crypto$. This library only supplies \cmix{} related data structures and operations. The library operates by passing a so called $CMixContext$ structure to each call of the \cmix{} library functions. This context structure contains, amongst other things, a generic API from the $libcmix{\text -}crypto$ library. 
 	
-	\item[libcmix-protobuf] This library contains just the \cmix definitions for the $google protobuf$ protocol. This\cmix implementation uses $protobuf$ to transmit messages between nodes and clients. This makes sure all communication between actors are properly serialized and de-serialized and allows it to inter-operate with different clients and/or nodes.
+	\item[libcmix-protobuf] Library containing just the \cmix{} definitions for the $google protobuf$ protocol. This\cmix{} implementation uses $protobuf$ to transmit messages between nodes and clients. This makes sure all communication between actors are properly serialized. It also allows the current implementation of actors to easily interoperate with different actor implementations.
 	
-	\item[libcmix-network] Small networking library that supplies TCP servers and clients using the $Boost::asio$ library. The library supports both plain TCP and SSL connections.
+	\item[libcmix-network] Networking library that supplies TCP servers and clients using the $Boost$$::$$asio$ library. The library supports both plain TCP and SSL connections.
 	
-	\item[libcmix-common] Small library that contains code that is relevant to both the $client$ and $node$ binaries. It contains abstractions over the $libcmix{\text -}network$ library. This was done because there is a sense of directionality in \cmix node communication, the network forms a ring where the last nodes has a connection to the first node. Therefore the library supplies Senders, Receivers and SenderReceivers. This prevents you from sending messages to the wrong node as you only receive from your previous node and only send to the next node.
+	\item[libcmix-common] Library that contains code that is relevant to both the $client$ and $node$ binaries. It contains abstractions over the $libcmix{\text -}network$ library. This was required because there is a sense of directionality in \cmix{} node communication, the network forms a ring where the last nodes has a connection to the first node. Therefore the library supplies ``Senders'', ``Receivers'' and ``SenderReceivers''. This prevents you from sending messages to the wrong node as you only receive from your previous node and only send to the next node.
 	
-	\item[liblog] Small logging library, this is just an abstraction over $Boost::Log$ and only uses the $trivial\_log$ variant.
+	\item[liblog] Logging library, this is just an abstraction over $Boost$$::$$Log$ and only uses the $trivial\_log$ variant.
 	
-	\item[node] A binary that implements the \cmix node behavior. Nodes can be configured at startup to fulfill certain roles. For full explanation of the configuration please refer to the \emph{-{}-help} output 
+	\item[node] A binary that implements the \cmix{} node behavior. Nodes can be configured at startup to fulfill certain roles. For full explanation of the configuration please refer to the \emph{-{}-help} output.
 	
-	\item[client] A binary that implements a \cmix client. Clients can also be configured as startup. Please refer to the \emph{-{}-help} output for more information.
+	\item[client] A binary that implements a \cmix{} client. Clients can also be configured at startup. Please refer to the \emph{-{}-help} output for more information.
 	
-	\item[statsd] A binary that accepts Performance statistics of the nodes via TCP. Nodes can be configured  to either connect to a stats daemon or perform operation without it.
+	\item[statsd] A binary that accepts Performance statistics of the nodes via TCP. Nodes can be configured  to either connect to a stats daemon or operate normally without one.
 \end{description}
 
 \subsubsection{libcmix-crypto}
 
-One goal of $libcmix{\text -}crypto$ was to be as reusable and accessible as possible. This is why $libcmix{\text -}crypto$ was written in $C$. Another goal was to make it easy to add new cryptographic backends and an easy way to swap between them. This implementation chose to only build and use one implementation based on the configuration of the project. This was done to make sure that no code change was needed to switch between algorithms. One can easily configure the project, and which cryptographic backend to use with $CMake$. In $CMake$ one can choose between either using elliptic curve, or multiplicative group. And choose out of a list of implementations of either the elliptic curve or multiplicative group variants.
+One goal of $libcmix{\text -}crypto$ was to be as reusable and accessible as possible. This is why $libcmix{\text -}crypto$ was written in $C$. Another goal was to make it easy to add new cryptographic backends and an easy way to swap between backends. This implementation chose to only build and use one implementation based on the configuration of the project. This was done to make sure that no code change was needed to switch between algorithms. One can easily configure the project, and which cryptographic backend to use with $CMake$. In $CMake$ one can choose between either using elliptic curve, or multiplicative group. And choose out of a list of implementations of either the elliptic curve or multiplicative group variants.
 
-For each type of encryption (multiplicative group or ed25519) multiple backends can be created and used. By adding a folder with a descriptive chosen $name$ and adding a file to that folder named $name\_algorithm.c$ for instance $gcrypt\_ed25519.c$. After rerunning the $CMake$ configuration step you can choose what backend you want to use. After a build of the project this implementation will be used as the \cmix cryptographic backend.
+For each type of encryption (multiplicative group or $Ed25519$) multiple backends can be created and used. By adding a folder with a descriptive chosen $name$ and adding a file to that folder named $name\_algorithm.c$ for instance $gcrypt\_ed25519.c$. This will make the implementation show up in the $CMake$ configuration after running $CMake$ once. When building the project, the chosen implementation will be used as the \cmix{} cryptographic backend.
 
-This additional backend should initialize all the $extern$ declared variables defined in one of the specific APIs, for example $ed25519.h$ (\autoref{lst:ed25519.h}), with compatible function pointers. There are some convenience macros to help you set up additional backends.
+This additional backend should initialize all the $extern$ declared variables defined in one of the specific APIs, for example $ed25519.h$ (\autoref{lst:ed25519.h} in Appendix \autoref{app:cryptolst}), with compatible function pointers. There are some convenience macros to help you set up additional backends.
 
 \subsubsection{libcmix}
 
 Like $libcmix{\text -}crypto$, $libcmix$ was also implemented in $C$. All $libcmix$ functions operate by taking a $CMixContext$ structure as first parameter.
-The $CMixContext$ contains all the randomness and other information needed for mix network operation. Return values from $libcmix{\text -}crypto$ are passed and stored in the opaque $GroupElement$ type. The specific cryptographic backend will be able to reinterpret objects of this type back to the right representation to do the actual cryptography with. This allows us to use the same functions (and thus function signatures) for all cryptography types and implementations.
+The $CMixContext$ contains all the randomness and other information needed for mix network operation. Return values from $libcmix{\text -}crypto$ are passed and stored in the ``token'' $GroupElement$ type. The specific cryptographic backend will be able to reinterpret objects of this type. This allows us to use the same functions (and thus function signatures) for all cryptography types and implementations.
 
-The downside is that the cryptographic backend library has to implement a kind of serialization. It is responsible for transforming $GroupElement$s to some kind of string representation and back. This representation can be, and in all current cases is, binary. Which also means that the library needs a function to let the caller know how large the serialized output will be. Furthermore the message representation does not have to match the serialized group element representation, in case of ed25519 this is impossible. So we get separate serialization for messages.
+The downside is that the cryptographic backend library has to implement serialization. It is responsible for transforming $GroupElement$s to a string representation and back. This representation can be, and in all current cases is, binary. Which also means that the library needs a function to let the caller know how large the serialized output will be. Furthermore the message representation does not have to match the serialized group element representation. In case of $Ed25519$ serialized group elements are the affine $x$ and $y$ coordinates, but the message format is just a random string, we will discuss this problem in \autoref{sec:mappingcurve}. This means we get separate serialization for messages and intermediate results.
 
-It also moves responsibility of generating randomness to the cryptographic library. As we need to generate random group element vectors R and S and only the cryptographic backend library knows what those are. The library also generates the permutation function which means it needs to generate a uniform int securely, And it also implements the Diffie-Hellman key-exchange functions as it also needs a random group element to perform the key-exchange.
+It also moves responsibility of generating randomness to the cryptographic library. The \cmix{} implementation needs random group element vectors $R$ and $S$ and only the cryptographic backend library knows what those are. The backend library also generates the permutation function which means it needs to able to securely generate an integer value uniformly within a range. It should also implement the Diffie-Hellman key-exchange functions as the key-exchange needs to generate a random group element.
 
-All these extra functionality which needs to be implemented in the backend adds up and makes the API look a bit bloated, but most functions are easily implemented in a couple of lines of code. Unfortunately it is simply impossible to have a higher level library take care of these operations without losing possible abstraction of the underlying cryptographic libraries or data structure used by that library.
+All this extra functionality, which needs to be implemented in the backend, adds up and makes the API look a bit bloated. However most functions are easily implemented in a couple lines of code. Unfortunately it is simply impossible to have a higher level library that takes care of these operations without losing possible abstraction of the underlying cryptographic libraries or data structure used by such library.
 
 
-\subsection{ElGamal in multiplicative Group and Elliptic Curve}
+\subsection{\elgamal{} in multiplicative group and elliptic curve}
 
-The goal of this research is to see how differently these two ways of using ElGamal in this cryptographic scheme effect things like latency and throughput in \cmix. But also doing this in the most reusable way  possible so that the implementation is of use for further research.
+The goal of this research is to see how differently these two ways of using ElGamal in this cryptographic scheme effect things like latency and throughput in \cmix{}. But also doing this in the most reusable way  possible so that the implementation can be used in future research.
 
-This means we will be trying to find cryptographic libraries that do most of the work while we focus on getting a uniform API over different back-ends and the correct implementation of said back-ends. Unfortunately ElGamal is not a very popular encryption algorithm in modern cryptographic libraries. and even if it is supported with a high level interface it is very rigid and wouldn't allow for any secret sharing as needed in \cmix. Because of this we needed access to lower level cryptographic primitives. Which was found in the libgcrypt library. The next step is to create a \cmix library which abstracts the lower level cryptographic primitives for both ``multiplicative group'' and ``elliptic curve'' ElGamal. This makes it easy to switch between implementations and test without changing any of the application code. This library is written in ``C'' to make interfacing with it from other languages used in the application level easier. For the application level code I used ``C++'', but in theory this should be easily swapped for a different application language.
+This means we will be trying to find cryptographic libraries that do most of the work while we focus on getting a uniform API over different back-ends and the correct implementation of those back-ends. Unfortunately ElGamal is not a very popular encryption algorithm in modern cryptographic libraries. and even if it is supported with a high level interface it is very rigid and wouldn't allow for any secret sharing as needed in \cmix{}. Therefore we need access to lower level cryptographic primitives, which are found in the $libgcrypt$ library. The next step is to create a \cmix{} library which abstracts the lower level cryptographic primitives for both ``multiplicative group'' and ``elliptic curve'' ElGamal. This makes it easy to switch between implementations and test without changing any of the application code. This library is written in ``C'' to make interfacing with it easier, for example by a different language used in the application level. For the benchmark C++ was used as the application level language and in theory this should be easily swapped for a different application language.
 
-Although using libgcrypt makes it possible to implement \cmix, it doesn't mean it was an easy task. The library still lacks some convenience functions that needed workarounds in the eventual implementation. This especially is the case for the elliptic curve back-end. Some specific problems will be discussed later.
+Although using $libgcrypt$ makes it possible to implement \cmix{}, it doesn't mean it was an easy task. The library still lacks some convenience functions that required workarounds. Especially for the elliptic curve back-end. Some specific problems will be discussed later.
 
 \subsection{Wire format}
 \label{sec:wireformat}
-For \cmix to work, we need to send group elements of the cryptographic algorithms from one node to the next. For multiplicative group this is easy. They are just big integers with a max size and can be sent as arrays of a fixed length.
+For \cmix{} to work, we need to send group elements of the cryptographic algorithms from one node to the next. For multiplicative group this is easy. They are just big integers with a max size and can be sent as arrays of a fixed length.
 
-When serializing elliptic curve points, there are several options. You can send both affine coordinates. You can send only the y coordinate, in the case of ed25519. This means you need to calculate, one of the, corresponding x'es when de-serializing. Or you can send the projective coordinates. I chose in this implementation to send both affine $x$ and $y$ coordinates. This forces each node to calculate the inverse of the internally used projective $Z$ coordinate. Which is relatively slow. 
+When serializing elliptic curve points, there are several options. You can send both affine coordinates. You can send only the y coordinate, in the case of ed25519. This means you need to calculate, one of the, corresponding x'es when de-serializing. Or you can send the projective coordinates. This benchmarks $Ed25519$ implementation sends both affine $x$ and $y$ coordinates. Mainly due to fact that he length of projected coordinates can vary wildly and some limitations fo the $libgcrypt$ library. Unfortunately this forces each node to calculate the inverse of the internally used projective $Z$ coordinate. Which is relatively slow. 
 
-The main reason for this is that the raw affine $x$ and $y$ coordinate are easier to inspect and debug. On top of that libgcrypt is not very forthcoming on documentation of their internal structure, especially in their elliptic curve library. This means that it was not clear how to properly serialize the projective coordinates of a point. So just for now keep in mind that the overall implementation could be a bit faster when these unnecessary inversions of $Z$ would be eliminated.
+One nice side effect of this decision is that the affine $x$ and $y$ coordinates are easier to inspect and debug. On top of that $libgcrypt$ is not very forthcoming on documentation of their internal structure, especially in their elliptic curve library. This means that it was not clear how to properly serialize the projective coordinates of a point. So  keep in mind that the overall implementation could be a bit faster when these unnecessary inversions of $Z$ would be eliminated.
 
-So as to not worry about any other network serialization, this framework uses Google protobuf to serialize the \cmix messages further. This also means that you could have multiple nodes which are implemented in different languages interact with each other. As long as these languages have protobuf implementations available.
+So as to not worry about any other network serialization, this framework uses $googleprotobuf$ to serialize the \cmix{} messages further. This also means that you could have multiple nodes which are implemented in different languages interact with each other. As long as these languages have protobuf implementations available.
 
-\subsection{Mapping strings to Ed25519 points}
-
-So to use the homomorphic property of ElGamal we need to directly encode user input of the \cmix network into, in this case, valid curve points.
+\subsection{Mapping strings to $Ed25519$ points}
+\label{sec:mappingcurve}
+To use the homomorphic property of ElGamal we need to directly encode user input of the \cmix{} network into, in this case, valid curve points.
 
 \subsubsection{Elligator}
 
-An algorithm that might spring to mind first is the Elligator algorithm\cite{Bernstein:2013:EEP:2541806.2516734} to map curve points to strings indistinguishable from random strings. However this is the exact reverse of the operation I need in \cmix. Elligator works by converting curve points to a representative, a randomly seeming string of bytes. However not every possible string of that size is an representative of a curve point. This makes it impossible to use the Elligator for the reverse mapping in this problem.
+An algorithm that might spring to mind first is the $Elligator$ algorithm\cite{Bernstein:2013:EEP:2541806.2516734} to map curve points to strings indistinguishable from random strings. Unfortunately this is the exact inverse of the operation that \cmix{} needs. $Elligator$ works by converting curve points to a representative, which is a randomly seeming string of bytes. However not every possible string of that size is a representative of a curve point. This makes it impossible to use the Elligator for the reverse mapping in this problem.
 
 \subsubsection{Koblitz's method}
 
-There does exist an algorithm to map arbitrary strings to curve points. It is a probabilistic algorithm called the Koblitz's method\cite{Koblitz}. It starts by choosing a number that will be used as a  ``stride''. The string you want to encode as a point has to be interpreted as a group element and multiplied by the stride. The result of this multiplication must also be a group element. This means your message space is made smaller by a factor ``stride''. Now you can check if your result has a corresponding $x$ coordinate, in the case of Ed25519. If it has one you are done, if it doesn't you add $1$ to your current trial $y$ coordinate and check again. This continues up until your trial $y$ coordinate reaches the value of  $first\_trial\_y\_coordinate + stride$. If you haven't found an $x$ coordinate corresponding to your trial $y$ the mapping algorithm fails.
+There does exist an algorithm to map arbitrary strings to curve points. It is a probabilistic algorithm called the Koblitz's method\cite{Koblitz}. It starts by choosing a number that will be used as a  ``stride''. The string you want to encode as a point has to be interpreted as a group element and multiplied by the stride. The result of this multiplication must also be a group element. This means your message space is made smaller by a factor ``stride''. In the case of $Ed25519$ you can check if your result has a corresponding $x$ coordinate. If it has one you are done, if it doesn't you add $1$ to your current trial $y$ coordinate and check again. This continues up until your trial $y$ coordinate reaches the value of  $first\_trial\_y\_coordinate + stride$. If you haven't found an $x$ coordinate corresponding to your trial $y$ the mapping algorithm fails.
 
-You can map a point back to the original string by dividing the y coordinate with the ``stride''. This works because we only add a value less than the stride to the original number and integer division discards these additions.
+You can map a point back to the original string by dividing the y coordinate with the ``stride.'' This works because we only add a value less than the stride to the original number and integer division discards these additions.
 
-The problem with this probabilistic Koblitz's method is choosing your ``stride''. There is no way of knowing what the max distance between two consecutive suitable y coordinates could be. We do know that about half of the possible group elements would be suitable in Ed25519, but it is impossible to list all the Ed25519 curve points and check. This makes it an unsolvable problem, but we can make an educated guess, and stay on the safe side of that guess.
+The problem with this probabilistic Koblitz's method is choosing your ``stride''. There is no way of knowing what the max distance between two consecutive suitable $y$ coordinates could be. We do know that about half of the possible group elements would be suitable in $Ed25519$, but it is impossible to list all the $Ed25519$ curve points and check. This makes it an unsolvable problem. This is why this paper makes an educated guess on how big the ``stride'' should be and backs up this decision with empirical data.
 
-Now to address the concern that you divide your message space by the stride. This reduction will theoretically effect your throughput, however it only does if you would optimally pack your messages in the 252 bit message space you have available in Ed25519. However if you only use the lower 248 bits, which gives you 31 byte message space. You have 5 bits to use as a stride. Which, anecdotally, seems to be enough. Of course there is no way of knowing if this stride will work for all possible messages. But for the purpose of this benchmark it works well enough. It might be possible to find out how stride influences the chance of not finding a suitable y coordinate. But that is outside of the scope of this research.
+Now to address the concern that you divide your message space by the stride. This reduction will theoretically effect your throughput, however it only does if you would optimally pack your messages in the 252 bit message space you have available in $Ed25519$. However if you only use the lower 248 bits, which gives you 31 byte message space. You have 5 bits to use as a stride. Which, anecdotally, seems to be enough. Of course there is no way of knowing if this stride will work for all possible messages. But for the purpose of this benchmark it works good enough. It might be possible to find out how the stride influences the chance of not finding a suitable $y$ coordinate. But that is outside of the scope of this research.
 
-A small but nice benefit of using $2^5 = 32$ as stride; multiplication and division are bit shifts as $32$ is a power of $2$. For debugging purposes you might want to consider a stride of $16$. This makes any hexadecimal representation of a number just shift up one character. However in actual runs of the algorithm with a stride of $16$ was insufficient. Some of the runs would fail because there was no suitable $y$ coordinate within $16$ value range. This has not happened for a stride of $32$ yet. To reiterate this is no guarantee that it will never happen.
+A small but nice benefit of using $2^5 = 32$ as stride is that multiplication and division are bit shifts as $32$ is a power of $2$. For debugging purposes you might want to consider a stride of $16$, because this makes any hexadecimal representation of a number just shift up one character. In actual runs of the algorithm using a stride of $16$ was insufficient. Some of the runs would fail because there was no suitable $y$ coordinate within the $16$ value range. This has not happened for a stride of $32$ yet. This is no guarantee that it will never happen.
 
-\subsection{Debugging the \cmix operations.}
+\subsection{Debugging the \cmix{} operations.}
 
-Debugging the \cmix operations is hard. Intermediate results produced by the nodes are hard to validate for the real 2048 bit numbers used in the multiplicative group and the 256 bit numbers used in the ElGamal cases. Fortunately it is possible to use smaller multiplicative groups and smaller curves to debug structural issues in the algorithms. For the multiplicative groups this works like a charm, as the operations are pretty easy to do by hand or calculator, The operations for elliptic curve are a lot less intuitive, even for small curves. Especially with no known good library that implements these operations. This makes debugging some of the mix algorithm primitives tedious and time consuming.
+Debugging the \cmix{} operations is hard. Intermediate results produced by the nodes are hard to validate for the real 2048 bit numbers used in the multiplicative group and the 256 bit numbers used in the ElGamal cases. Fortunately it is possible to use smaller multiplicative groups and smaller curves to debug structural issues in the algorithms. For the multiplicative groups this works like a charm, as the operations are pretty easy to do by hand or with a calculator. The operations for elliptic curve are a lot less intuitive, even for small curves. Especially with no known good library that implements these operations. This makes debugging some of the mix algorithm primitives tedious and time consuming.
 
-Some tools that have been a great help in creating the implementation in general are AddressSanitizer\cite{ASan} and the companion leak check tool LeakSanitizer\cite{LSan}. These tools check all the executed code paths for any object or array access outside of the allowed bounds. This is no guarantee the application is completely memory safe. It does ensure that any out of bounds access is detected, even if the access was still technically in valid memory just not part of the object or array.
+Some tools that have been a great help in creating the implementation in general are AddressSanitizer\cite{ASan} and the companion leak check tool LeakSanitizer\cite{LSan}. These tools check all the executed code paths for any object or array access outside of the allowed bounds. This is no guarantee the application is completely memory safe. It does ensure that any out of bounds access is detected, even if the access was still technically in valid memory.
 
-The leak tool also helped to keep an eye on the tokens passed around by the \cmix library. Because the implementation language of the library was $C$ and there are 2 different implementations for the 2 different ElGamal back-ends. There is lots of token passing. These tokens need to be destructed but have no clear overarching owner at times. This makes it harder to keep track of object lifetime. So LeakSanitizer helped out tracking these lost tokens. Which allowed me to eventually eliminate memory leaks. Which in turn allowed me to run the benchmark for a high number of clients on a system with relatively low specs.
+The leak tool also helped to keep an eye on the tokens passed around by the \cmix{} library. Because the implementation language of the library is $C$ and there are two different implementations for the two different ElGamal back-ends, many tokens are being passed around. These tokens need to be destructed but have no clear overarching owner. This makes it harder to keep track of object lifetime. So LeakSanitizer helped out tracking these lost tokens. Which allowed elimination of the memory leaks. Which in turn allowed the execution of the benchmark for a high number of clients on a system with relatively low specs.