text:
\chapter{Digital signature schemes}
\label{chpr:dss}

In this chapter we will present the general idea behind digital signatures: what they are and why they are used. Then we will discuss the Elliptic Curve Digital Signature Algorithm (ECDSA), the one actually used in Bitcoin. After having delved into its problems, we will present the adaptation of the Schnorr signature algorithm to elliptic curve cryptography (there is currently a discussion about its adoption in Bitcoin). The comparison will turn out to be pitiless.
\\
For a detailed explanation of how signatures are actually used in Bitcoin we refer to Appendix \ref{app:A}.
\\
\\
To understand what a digital signature scheme is, we start considering the situation in which Alice wants to sign a document that she aims sending to Bob, who wants assurance that the document comes from Alice and has not been tampered with. As for real life signatures, the aim of a proper digital signature scheme should be to prove the authenticity of a message or document, in the digital realm. Thus, we can list some properties that a signature scheme should provide:
\begin{itemize}
	\item Authentication: the recipient is confident that the message comes from the alleged sender;
	\item Non repudiation: the sender cannot deny having sent the message;
	\item Integrity: ensures that the message has not been altered during transmission.
\end{itemize}
A naive approach to this problem would be to digitalize Alice's signature: but in this case it would be too easy for an eavesdropper to simply copy her signature and append it to any other document.
\\
In order to achieve the listed properties, as first thing we should tie the signature to the document, so that it could not be used again: this would also solve the problem of integrity. If the message changes, the signature is not valid anymore.  Moreover, it should be possible for parties other than Bob to verify that the signature is valid, and it should be possible to show that Alice must have been the person who signed the document: this would ensure the non repudiation and authentication properties.
\\
In cryptography usually some security models are introduced for the so called unforgeability, the property that prevents adversaries from being able to forge a signature on behalf of Alice. In the following we consider the security model known as existentially unforgeability under chosen message attack (UF-CMA), where forgery means winning at the following game:
\begin{enumerate}
	\item The signer (Alice) gives her public key to the adversary (also known as forger or attacker);
	\item The adversary sends messages $m_i$ to the challenger (Alice) and receives valid signature $\sigma$ on the message $m_i$ for the given public key. He may do this as many times as he likes;
	\item The adversary produces a message $m \neq m_i, \ \forall i$ (i.e. the message has not been queried before) along with a valid signature on it.
\end{enumerate}
In this model, unforgeability means that no computationally bounded adversary is able to forge a signature except with negligible probability: in this setting a forgery consists in a signature for a message/public key pair never queried. This hypothesis can be relaxed, excluding from the winning conditions only the triplets message/public key/signature obtained from a query, leading to the concept of strong unforgeability under chosen message attack (SUF-CMA).

\bigskip
\noindent
Now that we have presented the security model, we can look more formally at the scheme: a signature scheme is a triplet of algorithms $(KeyGen, Sign, Ver)$, where the first two are randomized algorithms, while the third one is deterministic. To sign a document or message, the signer proceeds as follows:
\begin{itemize}
	\item He runs the key generation algorithm with no inputs\footnote{Some authors consider as input a security parameter, but we take it as given.} to generate a key pair: $\{q, Q\} = KeyGen()$;
	\item He runs the signing algorithm on message $m$ and private key $q$, resulting in a signature $\sigma$: $\sigma = Sign(m, q)$;
	\item A verifier can check the validity of the signature running the verification algorithm as follows: $Ver(\sigma, m, Q) \in \{0, 1\}$. If $Ver(\sigma, m, Q) = 1$ then the signature is valid, otherwise it is not.
\end{itemize}
A proper signature scheme should satisfy the following consistency equation: $Ver(Sign(m,q), m, Q) = 1, \ \forall \{q, Q\}$ returned from the key generation algorithm.
\\
A possibility to construct signature schemes relies on the difficulty of discrete logarithms on elliptic curves. In the next sections we will analyse deeply merits and flaws of two schemes constructed on this hypothesis.

\bigskip

\section{Elliptic curve digital signature algorithm (ECDSA)}
\label{ecdsa}
Assume that Alice wants to sign a message $M$ and send it to Bob. The first thing to do for the parties involved is to agree on an elliptic curve determined by the set of parameters $T = (p, a, b, G, n, h)$ and on a cryptographically secure hash function. This function is used to get a digest from $M$: usually, a digital signature can only sign small amounts of data. Applying a proper hash function to a message produces a digest which is small but still can act as digital fingerprint if the output space is large enough. After the setup phase, Alice chooses a secret integer $q_A \in [1, ..., n - 1]$ (the private key) and computes her public key $Q_A = q_AG$, that sends to Bob who has to validate it (Alice should not be able to repudiate the signature due to the use of an invalid public key).
\\
The public key can be made public thanks to the difficulty of the ECDLP; moreover, the fact that it is public allows anyone to verify Alice's signature, enforcing the non repudiation property.
\\
The signing and verification algorithms are displayed in Algorithms \ref{alg:ecdsa_sig} and \ref{alg:ecdsa_ver} ($L_n$ represents the length in bits of the group order $n$).

\bigskip

\begin{algorithm}
	\caption{ECDSA: signing algorithm}
	\label{alg:ecdsa_sig}
	\begin{algorithmic}[1]
		\Procedure{ecdsa\_sig}{$M, \ q$}
		\State $m \gets \text{hash}(M)$
		\State Let $z$ be the $L_n$ leftmost bits of $m$: $z \gets \text{int}(z)$
		\State $k \xleftarrow{\text{\$}} \{1, ..., n - 1\}$
		\State $K \gets kG$
		\State $r \gets x_K \ (\text{mod} \ n)$
		\If {$r = 0$}
		\State \textbf{go to} step 4
		\EndIf
		\State $s \gets k^{-1}(z + rq) \ (\text{mod} \ n)$
		\If {$s = 0$}
		\State \textbf{go to} step 4
		\EndIf
		\State \textbf{return} $(\text{bytes}(r), \text{bytes}(s))$
		\EndProcedure
	\end{algorithmic}
\end{algorithm}

\bigskip

\begin{algorithm}
	\caption{ECDSA: verification algorithm}
	\label{alg:ecdsa_ver}
	\begin{algorithmic}[1]
		\Procedure{ecdsa\_ver}{$(r, s), M, Q\ $}
		\State $r \gets \text{int}(r)$, $s \gets \text{int}(s)$
		\If {$r \notin \{1, ..., n - 1\}$ \textbf{or} $s \notin \{1, ..., n - 1\}$}
		\State \textbf{return} {\bf False}
		\EndIf
		\State $m \gets \text{hash}(M)$
		\State Let $z$ be the $L_n$ leftmost bits of $m$: $z \gets \text{int}(z)$
		\State $u_1 \gets zs^{-1} \ (\text{mod} \ n)$, $u_2 \gets rs^{-1} \ (\text{mod} \ n)$
		\State $K \gets u_1G + u_2Q$
		\If {$K = \infty$}
		\State \textbf{return False}
		\EndIf
		\State \textbf{return $r = x_K \ (\text{mod} \ n)$}
		\EndProcedure
	\end{algorithmic}
\end{algorithm}

\bigskip
\noindent
In the signing algorithm it is drawn at random an integer $k$ at step 4: this value has not only to be secret, it has to be selected differently each time\footnote{Loosely speaking, the security of the signature derives from the fact that we have one equation, the one defining $s$, in two unknowns, $k$ and $q$. If we use the same $k$ for another signature, we give the adversary an additional equation, allowing him to solve the system.}. Otherwise the secret key would be recoverable. Indeed, let's consider two signatures on different messages $(r, s)$ and $(r, s')$ derived using the same $k$. After having converted $r, s$ and $s'$ to integers, we have:
$$s = k^{-1}(z + rq_A) \ (\text{mod} \ n), \ s' = k^{-1}(z' + rq_A) \ (\text{mod} \ n) \ \Longrightarrow $$ $$\Longrightarrow s - s' = k^{-1}(z - z') \ (\text{mod} \ n) \ \Longrightarrow \ k = (z - z')(s - s')^{-1} \ (\text{mod} \ n).$$
From just two signatures we were able to recover the common $k$ and now we can derive the private key from the definition of $s$ or from the definition of $s'$:
$$q_A = r^{-1}(ks - z) \ (\text{mod} \ n).$$
\\
To ensure that $k$ is unique for each message one may bypass random number generation completely, since it is one of the main sources of problems in cryptosystems, and generate deterministic signatures by deriving $k$ from both the message and the private key as: $k = \text{hash}(q \ || \ m)$. This approach ensures both a different $k$ every time the message changes and unpredictability.
\\
Moreover there are some ways to speed up the verification procedure: through the Straus's algorithm (also known as Shamir's trick), the sum of two scalar multiplication can be calculated faster than the two isolated scalar multiplication at point 9. A further speed up occurs when making $K$ efficiently recoverable from $r$. In this case one may verify that $sK = zG + rQ_A$, avoiding modular inversion. This can be done by including the point $K$ itself in the signature, either in compressed or uncompressed form: the gain in this case would come at expenses of the signature's size.

\bigskip
\noindent
Let's give a look at the correctness' proof of the procedure:
\\
{\bf Proof}: We have to prove that $kG = K = u_1G + u_2Q_A$.
\begin{itemize}
	\item From the definition of $Q_A$: $u_1G + u_2Q_A = u_1G + u_2q_AG$;
	\item From the definition of $u_1$ and $u_2$: $u_1G + u_2Q_A = s^{-1}(z + rq_A)G$;
	\item From the definition of $s$: $u_1G + u_2Q_A = (k^{-1}(z + rq_A))^{-1}(z + rq_A)G = k(z + rq_A)^{-1}(z + rq_A)G = kG = K$.
\end{itemize}
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\square$
At the beginning of the chapter we have said that the comparison between ECDSA and Schnorr will be pitiless, so it is clear that ECDSA is far from being perfect. Let's discuss some of its problems:
\begin{itemize}
	\item Malleability: the signature $(r, s)$ may be replaced with $(r, -s \ (\text{mod} \ n))$\footnote{With the malleated signature we would have: $u_1G + u_2Q_A = u_1G + u_2q_AG = -s^{-1}(z + rq_A)G = -(k^{-1}(z + rq_A))^{-1}(z + rq_A)G = -k(z + rq_A)^{-1}(z + rq_A)G = -kG = -K$. The verification procedure would then check whether the $x$ coordinate of $-K$ would equal $r$; this would be the case since $K$ and $-K$ share the same $x$ coordinate.}, because this is an equivalent signature. This means that a third party, without access to the private key, can alter an existing valid signature for a given public key and message into another signature that is valid for the same key and message. However this is not regarded as a forgery on the scheme since the message is the original one, but this possibility prevented the deployment of layer 2 solutions for the Bitcoin scalability problem (e.g. the Lightning Network described in \cite{RefWork:18} or the eltoo protocol discussed in \cite{RefWork:19}): recently this problem has been circumvented through the soft fork SegWit.
	\\
	Another solution would be to augment the verification equation with the check $s \leq (n - 1) / 2$;
	\item The signing and verification operations need the calculation of modular inverses and, as we have already pointed out, it is a slow operation. Moreover this computation can be done only if $n$ is a prime number. Indeed we have a theorem stating that $x \in \mathbb{Z}_n$ is invertible if and only if the greatest common divisor of $x$ and $n$ is one\footnote{\url{https://www.coursera.org/learn/crypto/lecture/2YWK8/notation}, from minute 7.39.}. This obviously holds true for every $x \in \mathbb{Z}_n$ if and only if n is a prime number. However this is not at all a problem, but just a remark: $n$ has to be a huge prime number for the ECDLP to be hard;
	\item In order for ECDSA to be secure, it can be shown that we need a small cofactor $h$. This is due to the presence of attacks on the conversion function used in the sixth step of the signing operation, the one that entails taking the $x$ coordinate of $K$ and reducing it modulo $n$. It is told in \cite{RefWork:2} that this function has to be almost bijective for ECDSA to be secure, which means that an attacker cannot find an $r$ for which a random $K$ has non negligible probability of satisfying $r = x_K \ (\text{mod} \ n)$. Indeed we have that the integers $x_K = r + jn$ for $j \in \{0, 1, 2, ..., h\}$, if $h = 1$ or 2 as recommended in \cite{RefWork:3}, are linked usually to one valid candidate $x$ coordinate.
\end{itemize}

\bigskip

\subsection{ECDSA: multi-signature}
Multi-signature schemes allow a group of users to cooperate (interactively or not) to sign a single message or document, usually producing a joint signature that is more compact than a collection of distinct signatures from all users. Verification usually requires the message $m$ and the set of public keys of the signers.
\\
Before we analyse ECDSA multi-signature, let's see formally what these schemes are.

\bigskip
\noindent
A multi-signature algorithm is a triplet of algorithms $(KeyGen, Sign, Ver)$. To sign jointly a document or message $m$, each participant $i$ of the scheme should proceed as follows:
\begin{itemize}
	\item She generates a public key pair through the key generation algorithm: $\{q_i, Q_i\} = KeyGen()$;
	\item She sends her public key to all participants, so that every user can gather the same multiset $L$ of public keys: $L = \{Q_1, Q_2, ..., Q_n\}$;
	\item She runs the signing algorithm on message $m$, secret key $q_i$ and multiset of public key $L$: $\sigma = Sign(m, q_i, L)$;
	\item A verifier can check the validity of the signature through the verification algorithm: $Ver(\sigma, m, L) \in \{0, 1\}$. If it returns 1 then the signature is valid, otherwise it is not.
\end{itemize}
A proper multi-signature scheme should output to every signer the same signature $\sigma$ that satisfies the following consistency equation:
$$Ver(Sign(m, q_i, L), m, L) = 1, \ \forall q_i \ \text{s.t.} \ q_iG = Q_i \in L.$$
It is easy, given a signature scheme, to extend it to the multi-user setting in a naive way: each signer signs the message with its own private key, the final signature being the concatenation of the partial signatures. This is the approach used today in Bitcoin with ECDSA: the problem is that the signature size increase linearly in the number of participants, leading to higher fees for the users and a bloat of the blockchain size that affects every participant in the network. Ideally, the size of the signature should be independent of the number of participants. Recently there have been proposed more efficient multi-signature protocols in \cite{ECDSA1} and \cite{ECDSA2}: however they still need review by the community and lack an actual implementation. Moreover the underlying signature scheme is the \textit{far from being perfect} ECDSA, so we refer the interested reader to the original papers without delving into the technicalities of these works.

\bigskip
\noindent
ECDSA naive multi-signatures require multiple public keys in order to validate multiple signatures, i.e. despite the name, multi-signature in Bitcoin is just a tuple of distinct users' signatures.
\\
In literature, the name multi-signature is associated to schemes that, given $n$ participants, require the collaboration of everybody to produce a valid signature. In Bitcoin this notion is extended to the so called threshold schemes: if before we talked about $m$-of-$m$ schemes, these can be though of as $t$-of-$m$, where at least $t \leq m$ participants have to collaborate to sign.

\bigskip

\subsection{ECDSA: public key recovery}
Given an ECDSA signature $(r, s)$ and linked EC parameters $T$, it is possible to determine the public key $Q$ associated with the private key used to generate the signature: this tool is called public key recovery and turns out to be particularly useful in bandwidth constrained environments. Potentially, many candidate public keys can be recovered from a signature, their number depending on the cofactor $h$. The algorithm for public key recovery is presented in Algorithm \ref{alg:key_recovery}, where the function EC\_point() recovers an elliptic curve point given the $x$ coordinate (it returns \textbf{False} in case no point with that $x$ coordinate exists).

\bigskip

\begin{algorithm}
	\caption{ECDSA: public key recovery}
	\label{alg:key_recovery}
	\begin{algorithmic}[1]
		\Procedure{ecdsa\_recovery}{$(r, s), M$}
		\State $keys \gets \{\}$
		\State $r \gets \text{int}(r), \ s \gets \text{int}(s)$
		\For {$j \gets 0, h - 1$}
		\State $x \gets r + jn$
		\State $K \gets \text{EC\_point}(x)$
		\If {$K = {\bf False}$ \textbf{or} $nK \neq \infty$}
		\State \textbf{go to} step 4
		\EndIf
		\State $m \gets \text{hash}(M)$
		\State Let $z$ be the $L_n$ leftmost bits of $m$: $z \gets \text{int}(z)$
		\For {$k \gets 1,2$}
		\State $Q \gets r^{-1}(sK - zG)$
		\State $keys \gets keys + Q$
		\State $K \gets -K$
		\EndFor
		\EndFor
		\State \textbf{return} $keys$
		\EndProcedure
	\end{algorithmic}
\end{algorithm}
\noindent
In the set $keys$ there is the correct key. Authenticity could be checked against a public key in some certificate or directory.
\\
Through public key recovery, the verification of a signature becomes implicit: you first recover $Q$ from $(r, s)$, then the signature is deemed valid once the public key $Q$ has been authenticated. This step is necessary since, in general, from every signature we can extract a public key.

\bigskip

\bigskip

\section{Schnorr signature algorithm}
\label{schnorr}
In this section we finally pass to analyse the core of the present work, following closely the recent Bitcoin Improvement Proposal (BIP) by Pieter Wuille and others \cite{RefWork:5} about Schnorr's standardization for the Bitcoin protocol.
\\
As stated in the BIP, ECDSA is standardized, while the Schnorr signature, due to the presence of a patent in past years, is not. As we will see this lack hides some possibilities; on top of that, Schnorr itself is better than ECDSA in several aspects:
\begin{itemize}
	\item Security proof: the security of Schnorr signature is proved in the random oracle model\footnote{In the Random Oracle Model (ROM) hash functions are modelled as truly random functions whose outputs are uniformly random and can be computed by querying a public oracle.} assuming that the ECDLP is hard. Such a proof does not exist for ECDSA, since its security proof requires the generic group model. The two proofs can be found in \cite{RefWork:8} and \cite{RefWork:9}, respectively. The provably secure construction offered by Schnorr is important since it could prevent future attacks on ECDSA\footnote{This is a major achievement since Schnorr provides better security based on the same hypothesis: we do not need to introduce stronger conditions to improve the security.};
	\item Non-malleability: ECDSA, as already showed, is malleable. On the other hand, Schnorr signatures are provably non-malleable\footnote{Segregated witness (SegWit) solves the known malleability problem of ECDSA, but we do not know if others exist. On the other hand, Schnorr is strongly unforgeable under chosen message attacks (SUF-CMA), a property that prevents malleability.};
	\item Linearity: if multiple users sign the same message, the sum of these signatures is a valid signature over the starting message for the sum of the public keys used: although such a construction is completely insecure, it is the basis for several higher level protocols with interesting properties, some of which will be studied in Chapter \ref{chpr:application}.
\end{itemize}
Thanks to these characteristics, the introduction of Schnorr in Bitcoin would result in privacy and efficiency improvements, implying better fungibility and scalability. Moreover, thanks to the version system introduced by SegWit, Schnorr can be deployed ``easily'' through a soft fork. Schnorr signature could moreover enable easier implementations of some protocols that take advantage of the Bitcoin blockchain, such as atomic swaps and payment channels.

\bigskip
\noindent
The fact that Schnorr is not standardized, allows us to make design choices in order to implement other features in addition to the native ones:
\begin{itemize}
	\item Batch validation: the formulation of ECDSA that is standardized cannot be validated more efficiently in batch compared to individually. Switching to Schnorr offers the opportunity to choose a formulation that allows batch validation. This can be an important feature in Bitcoin since when validating a block we need to verify multiple signatures; moreover, we are interested that all of them are valid: if the verification fails, we do not care about which signature caused the failure. We simply reject the whole block;
	\item Fixed size: the proposed Schnorr standardization is of fixed size, 64 bytes. This is in contrast with the 70-72 bytes long ECDSA (caused by the DER encoding). This would lead to a reduction of on-chain transactions' size.
\end{itemize}
When signing with Schnorr there are two possible shapes for the signature. EC Schnorr signatures for the message $m$ and public key $Q$ involve a point $K$ and integers $e$ and $s$ which satisfy $e = \text{hash}(K \ || \ m)$ and $sG = K + eQ$. The two different verification equations depend on whether we decide to include $e$ or $K$ in the signature.
\begin{itemize}
	\item The signature is $(e, s)$ with $e = \text{hash}(sG - eQ \ || \ m)$. This choice avoids the difficulty of encoding an EC point in the signature;
	\item The signature is $(K, s)$ with $sG = K + \text{hash}(K \ || \ m)Q$. This formulation supports batch validation since there are no elliptic curve operations inside the hashes.
\end{itemize}
In the cited BIP the choice falls on the second option, since it supports batch validation. Batch validation is important also because it would speed up considerably the syncing of new Bitcoin nodes that have to download the entire blockchain and validate every transaction (this would be true from the hypothetical block in which batch validation would be introduced; obviously it is not a retroactive property).
\\
However, using the second validation rule directly comes with a downside: it is possible for a third party to convert a signature $(K, s)$ for key $Q$ into a signature $(K, s + a*\text{hash}(K \ || \ m))$ for key $Q + aG$ and the same message, for any integer $a$. Indeed, the signature $(K, s)$ is verified checking that:
$$sG = K + \text{hash}(K \ || \ m)Q \ \Longrightarrow$$
$$\Longrightarrow \ (s + a*\text{hash}(K \ || \ m))G = sG + a*\text{hash}(K \ || \ m)G =$$
$$= K + \text{hash}(K \ || \ m)Q + a*\text{hash}(K \ || \ m)G = K + \text{hash}(K \ || \ m)(Q + aG).$$
This is not a concern for the Bitcoin protocol itself, due to the difficulty of the ECDLP\footnote{An adversary could convert the signature for a public key of his choice only knowing the secret key of the signer: in this way he would be able to compute $Q_{adv} = (q + a)G$, choosing properly the integer $a$.}. However it may be better to avoid this problem, since in some cases it could become a concern: an example is unhardened derivation in BIP32. For this reason, the BIP suggests to use key prefixed Schnorr, changing the verification equation to $sG = K + \text{hash}(K \ || \ Q \ || \ m)Q$. Because any change in the public key would produce unpredictable changes in the hash, an adversary cannot use an existing signature to do anything but verify it. Notice that this choice prevents the possibility for public key recovery, a construction that is typically incompatible with batch validation\footnote{\url{https://bitcoin.stackexchange.com/questions/77234/schnorr-vs-ecdsa}.}.
\\
Let's give a deeper look at how the formulation without key prefixing can be exploited in case of unhardened derivation using BIP32. Without entering in the details, in BIP32 it is specified how to derive key pairs from a unique master key pair, easing incredibly the backup procedure: the major achievement is that the whole tree of key pairs is recoverable from a special number called seed, that can be safely stored in efficient ways. We label the parent key pair as $\{q_P, Q_P\}$ and the child key pair as $\{q_C, Q_C\}$. The scheme for unhardened derivation is represented in Figure \ref{fig:bip32} and works as follows: we use the hash function HMAC, that outputs in the space of 512 bits, fed with the parent public key, the parent chain code (for our purposes the only thing that matters is that it is derived as half of the output of the HMAC function, i.e. it is a 256 bits string) and the child index. The result is divided in two halves, an offset and the child chaincode (that is needed for further derivations). The offset is added to the parent private key (modulo the order of the curve) to obtain the child private key. Thus, denoting the offset as $f$, we have the following relation: $q_C = f + q_P \ (\text{mod} \ n) \ \Longrightarrow \ Q_C = fG + Q_P$.

\begin{figure}
	\noindent
	\makebox[\textwidth]{\includegraphics[width=15cm, height=7cm]{Images/bip32.png}}
	\captionof{figure}{BIP32's unhardened derivation.}
	\label{fig:bip32}
	\source{\cite{RefWork:7}}
\end{figure}
\noindent
Now, imagine an attacker is given a valid signature $(K, s)$ for public key $Q_P$ and message $m$. Relying on the previous relation, he is able to forge a valid signature for public key $Q_C$ on the same message $m$ as $(K, s + \text{hash}(K \ || \ m)f)$. Indeed we have:
$$(s + \text{hash}(K \ || \ m)f)G = sG + \text{hash}(K \ || \ m)fG = $$
$$= K + \text{hash}(K \ || \ m)Q_P + \text{hash}(K \ || \ m)fG = K + \text{hash}(K \ || \ m)(Q_P + fG) = $$
$$ = K + \text{hash}(K \ || \ m)Q_C.$$
When substituting $sG$ with $K + \text{hash}(K \ || \ m)Q_P$ we relied on the fact that $(K, s)$ is a valid signature for public key $Q_P$ and message $m$. Notice that the attacker only needs a valid signature for the parent public key, the related public key and message, the parent chaincode and the child index.
\\
This is a particular case of the previously presented weakness, that now can be exploited since the relation between the two public keys is known. Also the hardened derivation would prevent the forgery since, in place of the parent public key, the parent secret key is given as input to the hash function. To learn the relation between the two public keys, i.e. the offset, the forger would need to know also the parent private key. But this would mean that the attacker has direct access to all the funds secured by the subtree generated by the compromised parent node: the simple forgery is not anymore a concern.

\bigskip
\noindent
Getting back to the signature specification, the first problem we have to face is how to encode efficiently the EC point in the signature. Several possibilities exist:
\begin{enumerate}
	\item Encoding the full point through $x$ and $y$ coordinates, resulting in a 96 bytes signature (32 for each coordinate and another 32 for the integer $s$);
	\item Encoding the $x$ coordinate and use an additional byte to encode whether $y$ is odd or even, like for compressed public keys: this would result in a 65 bytes signature;
	\item Encoding only the $x$ coordinate making the point implicit, leading to a 64 bytes signature.
\end{enumerate}
In the BIP, the choice falls on the third option, since compactness is prioritized. However we cannot have ambiguity about the $y$ coordinate, so we need to break the symmetry, i.e. we need to make the whole point $K$ implicit in its $x$ coordinate. Again, we have multiple possibilities:
\begin{enumerate}
	\item Select the $y$ coordinate in the lower half of the plane;
	\item Select the $y$ coordinate that is even;
	\item Select the $y$ coordinate that is a quadratic residue\footnote{It can be proved that the product of two numbers is a quadratic residue when either both or none of the factors are quadratic residues. Since we have that the two $y$ coordinates are one the negation of the other, and since -1 is not a quadratic residue when $p = 3 \ (\text{mod} \ 4)$ (as for secp256k1), we conclude that exactly one of the two roots is a quadratic residue. Notice that this choice for symmetry breaking prevents a real standardization: this formulation of Schnorr signature would not work for curves in which $p = 1 \ (\text{mod} \ 4)$.}.
\end{enumerate}
As directly stated in the BIP ``the third option is slower at signing time but a bit faster to verify, as the quadratic residue of the $y$ coordinate can be computed directly for points represented in Jacobian coordinates. The two other options require a possibly expensive conversion to affine coordinates first. This would even be the case if the sign or oddness were explicitly coded". This is the statement with which the choice of the third option is justified.

\bigskip
\noindent
Hereinafter hash will denote the SHA-256 function and the elliptic curve on which everything is worked out is intended to be secp256k1. Now we present the signing and verification algorithms\footnote{The validation procedure of the public key is incorporated in the verification algorithm to be compliant with the BIP, although in the case of ECDSA it was implicit.}, exemplified by Algorithms \ref{alg:schnorr_sig} and \ref{alg:schnorr_ver}, where the function is\_on\_curve($Q$) returns \textbf{True} or \textbf{False} depending on whether $Q$ is on the curve or not.

\bigskip

\begin{algorithm}
	\caption{Schnorr: signing algorithm}
	\label{alg:schnorr_sig}
	\begin{algorithmic}[1]
		\Procedure{schnorr\_sig}{$M, \ q$}
		\State $m \gets \text{hash}(M)$
		\State $k \gets \text{int}(\text{hash}(\text{bytes}(q) \ || \ m)) \ (\text{mod} \ n)$
		\State $K \gets kG$
		\If {$\text{jacobi}(y_K) \neq 1$}
		\State $k \gets n - k$
		\EndIf
		\State $e \gets \text{int}(\text{hash}(\text{bytes}(x_K) \ || \ \text{bytes}(qG) \ || \ m)) \ (\text{mod} \ n)$
		\State $s \gets k + eq \ (\text{mod} \ n)$
		\State \textbf{return} $(\text{bytes}(x_K), \text{bytes}(s))$
		\EndProcedure
	\end{algorithmic}
\end{algorithm}

\noindent
We chose $k$ in such a way that it changes each time the signature algorithm is applied to a different message; indeed even with Schnorr the predictability of this secret value can be used to recover the private key. Given $(r_0, s_0)$ and $(r_1, s_1)$ we have, by definition of $s_i$:
$$k = s_0 - e_0q = s_1 - e_1q\ (\text{mod} \ n) \ \Longrightarrow \ q = (s_0 - s_1)(e_0 - e_1)^{-1} \ (\text{mod} \ n).$$

\bigskip

\begin{algorithm}
	\caption{Schnorr: verification algorithm}
	\label{alg:schnorr_ver}
	\begin{algorithmic}[1]
		\Procedure{schnorr\_ver}{$(r, s), M, Q$}
		\If {\textbf{not} $\text{is\_on\_curve}(Q)$ \textbf{or} $Q = \infty$}
		\State \textbf{return False}
		\EndIf
		\State $r \gets \text{int}(r)$, $s \gets \text{int}(s)$
		\If {$r \notin \{1, ..., p - 1\}$ or $s \notin \{1, ..., n - 1\}$}
		\State \textbf{return False}
		\EndIf
		\State $m \gets \text{hash}(M)$
		\State $e \gets \text{int}(\text{hash}(\text{bytes}(r) \ || \ \text{bytes}(Q) \ || \ m)) \ (\text{mod} \ n)$
		\State $K \gets sG - eQ$
		\If {$K = \infty$ \textbf{or} $\text{jacobi}(y_K) \neq 1$ \textbf{or} $x_K \neq r$}
		\State \textbf{return False}
		\EndIf
		\State \textbf{return True}
		\EndProcedure
	\end{algorithmic}
\end{algorithm}

\bigskip
\noindent
Again, it can be of interest to give a look to the correctness' proof.
\\
{\bf Proof}: Given the signature $(r, s)$, we need to prove that the elliptic curve point $K$, recoverable from the integer $r$, equals $sG - eQ$. But by definition of $s$ and by definition of public key, we have:
$$sG - eQ = (k + eq)G - eqG = kG = K.$$
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\square$

\bigskip
\noindent
We conclude the section on Schnorr analysing the batch verification algorithm. It is pretty common for a system to verify a large number of signatures, particularly nowadays with crypto-currency widespread adoption. Thus, faster validation for a batch of signatures traduces in efficiency enhancements.
\\
When validating a signature in the formulation that we chose, the most expensive operations are the two elliptic curve scalar multiplications involved. Using directly the $(K, s)$ representation, we can verify the signature doing the hash operation first, and then performing elliptic curve operations. This is the key ingredient that allows to introduce batch validation.

\bigskip
\noindent
We established that a signature $(K, s)$ is valid if $K = sG - \text{hash}(x_K \ || \ Q \ || \ m)Q$.
Therefore, a couple of valid signatures $(K_0, s_0)$ and $(K_1, s_1)$ will verify:
$$K_0 + K_1 = s_0G - \text{hash}(x_{K_0} \ || \ Q_0 \ || \ m_0)Q_0 + s_1G - \text{hash}(x_{K_1} \ || \ Q_1 \ || \ m_1)Q_1 \Longrightarrow
$$
$$K_0 + K_1 = (s_0 + s_1)G - \text{hash}(x_{K_0} \ || \ Q_0 \ || \ m_0)Q_0 - \text{hash}(x_{K_1} \ || \ Q_1 \ || \ m_1)Q_1.$$
We are able to aggregate the $s$ values prior multiplication: this approach reduces the number of scalar multiplication to one per signature, plus one for the aggregated $s$. Sadly, this is not secure at all: an attacker can produce a set of signatures that cancel each others. This could be a problem if the signatures are invalid. The attacker would convince the network that they are valid thanks to the batch validation that would succeed. There is also a simpler example that could help clarifying why this construction is not secure: imagine we have a set $(K_i, s_i), \ i \in \{1, ..., m\}$ of valid signatures. Obviously the naive batch validation would succeed. However it would be possible to switch the terms between the signatures, invalidating them all: nonetheless, the batch validation would still succeed. To work around this, we will introduce a random factor $a_i$ per signature. Not knowing the random factor for each of his signatures, the attacker is now unable to have them cancel each others:
$$a_0K_0 + a_1K_1 = $$
$$= (a_0s_0 + a_1s_1)G - a_0\text{hash}(x_{K_0} \ || \ Q_0 \ || \ m_0)Q_0 - a_1\text{hash}(x_{K_1} \ || \ Q_1 \ || \ m_1)Q_1.$$
Unfortunately in this way we introduce a new scalar multiplication per signature, killing the batch speed up. However at this point we can rely on some other algorithms: we will study Bos-Coster's algorithm\footnote{\url{https://bitcoin.stackexchange.com/questions/80698/schnorrs-batch-validation}.}, but others exist (e.g. Pippenger algorithm). The core idea is to rewrite:
$$a_0K_0 + a_1K_1 = (a_0 - a_1)K_0 + a_1(K_0 + K_1).$$
For $m$ signatures we would have $m$ couples $(a_i, K_i), \ i = 0, ..., m - 1$ and the algorithm to compute $a_0K_0 + ... + a_{m - 1}K_{m - 1}$ would work as follows:
\begin{itemize}
	\item Sort the tuples according to the value of $a_i$ (rename consequently the values, so that $a_0$ is the greatest value associated to the point $K_0$);
	\item While the list has length larger than one:
	\begin{itemize}
		\item Substitute the top two elements $(a_0, K_0)$ and $(a_1, K_1)$ with the transformed values $(a_0 - a_1, K_0)$ and $(a_1, K_0 + K_1)$. If $a_0 - a_1 = 0$ you can remove one element;
		\item Sort the list again.
	\end{itemize}
\item When only one element remains, with very large probability it will be of the form $(1, K)$, otherwise it will be of the form $(a, K)$\footnote{The final value of the multiplier is the greatest common divisor of all the starting random factors: for this reason, when $m$ is sufficiently large, with high probability it will be 1 or small.}: the output is $K$ or $aK$, respectively.
\end{itemize}
The intuition is that, if we have $m$ signatures, we would have $m$ multiplications of the kind $a_iK_i$. Each time we do the above transformation, the difference $a_0 - a_1$ is, on average, $m$ orders of magnitude lower of the starting values ($a_0$ is the greatest value and $a_1$ is the closest to it): at each iteration we reduce the order of one multiplier by a factor of $m$ at the expenses of an EC addition. This scales much better than the double and add algorithm used to implement scalar multiplication: indeed in this case we have an EC point addition for every bit of the multiplier.

\bigskip
\noindent
Algorithm \ref{alg:schnorr_batch} presents the batch verification for a number $u$ of signatures $(r_1, s_1), ..., (r_u, s_u)$, associated to the messages $M_1, ..., M_u$ and to public keys $Q_1, ..., Q_u$: the optimization procedure for the calculation of $RHS$ that occurs at step 26 is not represented, but we relied exactly on the Bos-Coster's algorithm presented above.
\\
We highlight again the fact that the algorithm, taken from the BIP, is constructed to work on secp256k1, as clearly shown by step 14, where we can see the defining equation. However it can be easily extended to other curves satisfying the relation $p = 3 \ (\text{mod} \ 4)$: this property is used in step 15, that we try here to clarify. Referring to the algorithm, we have that the $y$ coordinates are the square roots of $c$ and can be computed as $y = \pm c^{\frac{p + 1}{4}}$, if they exist, due to a lemma by Lagrange\footnote{\url{https://en.wikipedia.org/wiki/Quadratic\_residue\#Prime\_or\_prime\_power\_modulus}.}, applicable when $p \equiv 3 \ (\text{mod} \ 4)$. Euler's criterion tells us that, given an odd prime $p$ and an integer $d$ coprime to $p$, we have $d^{\frac{p - 1}{2}} = \pm 1 \ (\text{mod} \ p)$, depending on whether $d$ is a quadratic residue ($d^{\frac{p - 1}{2}} = 1 \ (\text{mod} \ p)$) or not ($d^{\frac{p - 1}{2}} = - 1 \ (\text{mod} \ p)$). The same criterion applied to $y$ yields to $y^{\frac{p - 1}{2}} \ (\text{mod} \ p) = \pm c^{\frac{p + 1}{4}\frac{p - 1}{2}} \ (\text{mod} \ p) = \pm (c^{\frac{p - 1}{2}})^{\frac{p + 1}{4}} \ (\text{mod} \ p) = \pm 1^{\frac{p + 1}{4}} \ (\text{mod} \ p) = \pm 1 \ (\text{mod} \ p)$. Therefore, $y = c^{\frac{p + 1}{4}} \ (\text{mod} \ p)$ is a quadratic residue, while $y = - c^{\frac{p + 1}{4}} \ (\text{mod} \ p)$ is not: this approach is thus used to comply with the chosen symmetry breaking method.
\begin{figure}
	\makebox[\textwidth]{\includegraphics[scale=0.45]{Images/speedup.eps}}
	\captionof{figure}{Batch validation speed up.}
	\label{fig:figure6}
\end{figure}

\bigskip
\noindent
Figure \ref{fig:figure6} represents the speed up: the red line is obtained through a logarithmic fit. The $x$-axis represents the number of signatures $n$, while along the $y$-axis we find the ratio between the time required to validate $n$ signatures one by one and the time required to verify the batch. We got back the results presented in \cite{RefWork:5}, where it is shown that the time to verify $n$ signatures grows with $O\left(\frac{n}{log(n)}\right)$.

\begin{algorithm}
	\caption{Schnorr: batch verification algorithm}
	\label{alg:schnorr_batch}
	\begin{algorithmic}[1]
		\Procedure{schnorr\_batch}{$u, \{(r_1, s_1), ..., (r_u, s_u)\}, \{M_1, ..., M_u\}, \{Q_1, ..., Q_u\}$}
		\State $RHS \gets \infty$
		\State $mult \gets 0$
		\For {$i \gets 1,u$}
		\If {\textbf{not} is\_on\_curve$(Q_i)$ \textbf{or} $Q_i = \infty$}
		\State \textbf{return False}
		\EndIf
		\State $r_i \gets \text{int}(r_i)$, $s_i \gets \text{int}(s_i)$
		\If {$r_i \notin \{1, ..., p - 1\}$ \textbf{or} $s_i \notin \{1, ..., n - 1\}$}
		\State \textbf{return False}
		\EndIf
		\State $m_i \gets \text{hash}(M_i)$
		\State $e_i \gets \text{int}(\text{hash}(\text{bytes}(r_i) \ || \ \text{bytes}(Q_i) \ || \ m_i)) \ (\text{mod} \ n)$
		\State $c \gets r^3 + 7 \ (\text{mod} \ p)$
		\State $y \gets c^{\frac{p + 1}{4}}$
		\If {$y^2 \neq c$}
		\State \textbf{return False}
		\EndIf
		\State $K_i \gets (r_i, y)$
		\If {$i \neq 1$}
		\State  $a_i \xleftarrow{\text{\$}} \{1, ..., n - 1\}$
		\Else
		\State $a_i \gets 1$
		\EndIf
		\State $mult \gets mult + a_is_i$
		\State $RHS \gets a_iK_i + (a_ie_i)Q_i$
		\EndFor
		\If {$multG \neq RHS$}
		\State \textbf{return False}
		\EndIf
		\State \textbf{return True}
		\EndProcedure
	\end{algorithmic}
\end{algorithm}

max_stars_repo_name: gionasoldati/thesis

max_issues_repo_name: gionasoldati/thesis

max_forks_repo_name: gionasoldati/thesis


text:
\chapter{Probability and statistics}

\section{Binomial coefficients}
\begin{tabular}{ l l l }
$ \displaystyle \binom{n}{k} = \frac{n!}{k!(n-k)!} $  &
$ \displaystyle \binom{n}{k} = \binom{n}{n-k} $  &
$ \displaystyle \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} $  \\
$ \displaystyle \binom{n}{0} = \binom{n}{n} = 1  $  &
$ \displaystyle \binom{n}{1} = \binom{n}{n-1} = n  $  &
$ \displaystyle \sum_{k=0}^{n}\sum_{h=0}^{k}\binom{n}{k}\binom{k}{h} = 3^n  $  \\
$ \displaystyle \sum_{k=0}^{n}\sum_{h=0}^{k}\sum_{i=0}^{h}\binom{n}{k}\binom{k}{h}\binom{h}{i} = 4^n  $
\end{tabular}

\section{Permutations}
\textbf{Permutation}: set of ordered things (e.g. $(1,2,3)\ne(3,2,1)$).
Example of permutation: "How many ways can we award a 1st, 2nd and 3rd place prize among eight contestants?"

The number of {\it permutations} of $n$ elements is given by $$n!$$

The number of {\it permutations} of $p$ from $n$ is given by
\[
\frac{n!}{(n-p)!}=p!{n\choose p}
\]

The number of {\it permutations} of $p$ from $n$ with repetition is given by
\[
n^p
\]

\section{Combinations}
\textbf{Combination}: set of things whose order is not important (e.g. $(1,2,3)=(3,2,1)$).
Example of combination: "How many ways can I give 3 tin cans to 8 people?"

The number of possible {\it combinations} of $k$ elements from $n$ elements is given by
\[
{n\choose k}=\frac{n!}{k!(n-k)!}
\]

The number of possible {\it combinations} of $k$ elements from $n$ elements with repetition is given by
\[
{n+(k-1)\choose k}={n+(k-1)\choose n-1}=\frac{(n+(k-1))!}{k!(n-1)!}
\]

The number of different ways to classify $n_i$ elements in $i$ groups, when
the total number of elements is $N$, is
\[
\frac{N!}{\prod\limits_i n_i!}
\]

ext: tex


text:
\section{Volunteer Trials} \label{sec:develop_trials}
    This works’ field research is composed of, as determined before, user trials in a controlled environment with the goal of finding and collecting insight in regard to the usage of Cultural Awareness as the primary solution for the issue of user spontaneity and adaptability, and the hypotheses stated within the Goals section\ref{sec:intro_goals}.\\
    The planning surrounding the user trials was carried out with the intent of facilitating the forms of techniques employed in data collection useful for evaluation, those being observation data and user opinion data. These are performed concurrently to differing degrees of focus in accordance to different parts of each trial. These parts of a trial roughly follow the directions of the outline provided earlier in the section on HCI Evaluation\ref{sec:hci_definition_goals}, however, they will be detailed further in the following sections and an overview provided is provided in image \ref{fig:FigureTrialSections}.

    \begin{figure}[ht]
        \hspace*{-1cm}
        \centering
        \includegraphics[width=.9\paperwidth]{figures/TrialSections.png}
        \caption{\label{fig:FigureTrialSections}Overview of User Trial's Sections.}
    \end{figure}

    \subsection{Pre-Test} \label{sec:develop_trials_pre}
    The pre-test is the initial part of the trial, and it matches up roughly to the Introduction and Warm-Up phases of a field study plan. Users are introduced to the controlled environments, the room and equipment, and are initially asked for their demographic data and some first impressions and some very basic questions, such as, if they have knowledge of the apparatus used in gesture detection presented, the Leap Motion. They are also allowed to test out the Leap Motion’s diagnostic visualizer for up to 30 seconds just to get a rough idea of its function.\\
    However, there’s two bigger main components to the Pre-test after the initial introduction. A Cultural Survey and a Game Explanation.\\
    The Cultural Survey is done before any information about the game is given to the volunteer. They are presented with a simple black text on white background slide show containing several snippets indicating a different message. Each message represents one of the game’s task, and the volunteer is tasked with performing the gestures they feel best describe that action or message. The main objective of this exercise is checking if the user performs a majority of the same moves as the ones the Cultural Group uses during the game. This is a requirement of this work as a counter-measure against certain potentially erroneous assumptions made during development, such as, most directly, the choice of gestures the tasks use. Should the majority of users name the same gestures as the Cultural Group, this helps pre-emptively validate the game as a cultural experience. Should the majority name a specific different gesture, that should, conversely, invalidate that task for result-checking.\\
    The Game Explanation happens right afterwards. Here, the volunteers are shown a depiction of the in-game tasks they’ll have to perform, in the same order as the messages they just read through, both in the slide show and with a separate physical document. There are different explanations for the cultural and non-cultural group, however, those difference are never stated. The volunteers are given instructions on how to perform the tasks, as well as the differences between the Interaction Spaces and the method by which the game progresses. Finally, they’re asked if they understand the purpose of the gesture used in the task. Their comments and understanding are written down and recorded. Here the non-cultural users are implicitly given an opportunity to name their preference for one of the tasks they performed previously.\\

    \subsection{Game Observation} \label{sec:develop_trials_game}
    Following the explanation of the game, the volunteers are ready to play the game proper. Here, they are asked to perform the game fully. The volunteers are given a few more pointers to aid them on the way, mainly with getting used with movement, but are never outright given the actual gestures required for a task. They are also prompted for help if they appear to have difficulties at certain steps but are only given it if they accept or request it.\\
    Any special observation is recorded, priority given to unexpected displays of frustration or amusement. But some aspects of observing the user are most important for this segment. The Time Elapsed, the Number of User Errors, if Help was Required, and if the Correct Gesture was actually performed. These are likely to provide the most qualitative insight and are discernible enough to make an immersion scoring out of, and as such, the protocol developed for the trial is to document these values for every single task and every single volunteer, with both help from recordings (when permitted) and the game’s own logging of each task.\\

    \subsection{Post-Test} \label{sec:develop_trials_post}
    After the game is completed, the volunteer is given a moment to rest and then they’re asked to go over a questionnaire and answer it. This is closely related to the Cool-Off period of a field research and is the adequate time to investigate questions in the form of a survey. Volunteers aren’t asked to answer on their own, but rather, all of the questions are read out to the users and they’re made clearly aware of what each question is asking, slowing down the pace between questions if they’re answering too fast, and prodding for certainties in responses when a bout of indecision arises.\\
    There are three parts to the post-test questionnaire. The first part is a usability survey. Since the game was rewritten from scratch, it stands that its usability is still unproven and must be evaluated, however, the real reasoning behind making this investigation is that many aspects of usability have crossover with immersion and satisfaction signifiers. Thus, this is an insightful exercise towards the goals of this work and helps frame the way by which further questioning will be administered. The questions presented in the first part are adapted from the System Usability Scale. All scores of the scale are present and answers are scaled such as a 0-100 usability score is possible. Some other satisfaction-related questions were dropped here, particularly, that of the least enjoyable or most concerning aspect of the game, to ensure users don’t leave out details about their frustrations.\\
    The second part of the questionnaire goes over every Task and asks two questions on a scale for each of the gestures. The two aspects are surveyed are the ease of the gesture, and the natural fit of the gesture for the task. Since the users may find different interpretations for the scale, this one is meant to be taken as a comparative measure between each of the gestures, scoring them in terms of ‘below than ideal’. This should provide some final insights into the choice of gestures and their applicability for the task, but moreover, should provide a focal point of comparison between the Cultural and Non-Cultural groups.\\
    The third part is short, and merely looks into the volunteer’s experience with computers on their daily lives and their interest and pre-existing capabilities using other natural systems. This was a concern that could arise if groups of volunteers appeared to have vastly different expectations and performances between one another.\\

    \subsection{Second Trial} \label{sec:develop_trials_second}
    After performing the trial, the users are thanked and allowed to depart. However, their contribution isn’t over at this point. Given that one aspect of the proposed benefits to the shamanic interface approach has a large emphasis on memorization of commands, these have to be tested after a delay of time with no exposure to the system. All participants are therefore asked to come back and fulfil a second follow-up trial after a period of 14 days minimum. The goal here is to assess if their memory of the content still matches the actual experience. The second trial has two parts, first the volunteers perform the game again, and then they’re given a new post-game questionnaire.\\
    Absolutely nothing is changed with the game builds themselves, as the experience must remain consistent with the previous. Also, the same indicators have primary focus during observation, those being Number of User Error and so on. However, a small difference is with the protocol is that time, the users are not given any of the previous helpful pointers and are not prompted on their need of help if they’re seen struggling. The players must request help themselves if they appear to struggle and are allowed to proceed with failure if they don’t remember the task gesture but are certain of an erroneous one. This compels users to rely only on their own recollection of the solutions and in taking their time, rather than rely on communication with the researcher. The benefit of taking this approach is that it highlights their confidence on the gestures given without it needing to be taken in survey. To that end, the users are also not corrected on gestures until the second trial is over and they’re no longer under observation.\\
    The second post-game questionnaire is different from the first trials. This questionnaire has two parts. The first goes over every task and surveys users on their ease remembering each gesture. This is, again, meant to highlight a difference between each of the two Cultural groups, as the Non-cultural is predicted to mention greater barrier against the Cultural group. Additionally, there may also be a significant disparity between self-confidence and erroneous resolution of gestures in this aspect between the two groups, which may be of interest to record. As for the second part of the questionnaire, instead of focusing mostly on usability like the previous, this time, users are prompted over categories of experiential quality indicators. They’re asked about the impact, agreement and value of several aspects of the experience which they may rate on a 5-point scale between Strong Disagreement and Strong Agreement, although the majority just kept to simple a binary dimension between Yes and No or Good and Not Good answers. Listing the categories, their affective expectations, their feelings, their self-consciousness, the repeatability and their willingness to share with and recommend to others, their thoughts on the applicability and usability of the type of experience among different groups of people, the technological quality of the experience, and sense making and meaningful feedback.\\


text:
\documentclass{article}
\usepackage[pdftex]{graphicx}
\bibliographystyle{plain}
\begin{document}
%
%  Some useful definitions.
%
%\newcommand{\dzhat}{{\Delta \hat{Z}}}
%\newcommand{\dxhat}{{\Delta \hat{X}}}
%\newcommand{\dyhat}{{\Delta \hat{y}}}
%\newcommand{\dthat}{{\Delta \hat{t}}}
%
%\newcommand{\dzbar}{{\Delta \bar{Z}}}
%\newcommand{\dxbar}{{\Delta \bar{X}}}
%\newcommand{\dybar}{{\Delta \bar{y}}}
%\newcommand{\dtbar}{{\Delta \bar{t}}}
%
%\newcommand{\dz}{{\Delta Z}}
%\newcommand{\dx}{{\Delta X}}
%\newcommand{\dy}{{\Delta y}}
%\newcommand{\dt}{{\Delta t}}

\newcommand{\elprod}{\circ}

\title{CSDP User's Guide}
\date{December 29, 2009}
\author{Brian Borchers}
\maketitle
\section*{Introduction}
CSDP is a software package for solving semidefinite programming
problems.  The algorithm is a predictor--corrector version of the
primal--dual barrier method of Helmberg, Rendl, Vanderbei, and
Wolkowicz \cite{HelmbergC:Anims}.  A more detailed, but now somewhat
outdated description of the algorithms in CSDP can be found in
\cite{BorchersB:CSDCls}.  CSDP is written in C for efficiency and
portability.  On systems with multiple processors and shared memory,
CSDP can run in parallel.  CSDP uses OpenMP directives in the C source
code to tell the compiler how to parallelize various loops.  The code
is designed to make use of highly optimized linear algebra routines
from the LAPACK and BLAS libraries.

CSDP also has a number of features that make it very flexible.  CSDP
can work with general symmetric matrices or with matrices that have
defined block diagonal structure.  CSDP is designed to handle
constraint matrices with general sparse structure.  The code takes
advantage of this structure in efficiently constructing the system of
equations that is solved at each iteration of the algorithm.

In addition to its default termination criteria, CSDP includes a
feature that allows the user to terminate the solution process after
any iteration.  For example, this feature has been used within a
branch and bound code for maximum independent set problems to
terminate the bounding calculations as soon as a bound has been
obtained that is good enough to fathom the current note.  The library
also contains routines for writing SDP problems and solutions to files
and reading problems and solutions from files.

A stand alone solver program is included for solving SDP problems that
have been written in the SDPA sparse format \cite{SDPA}.  An interface
to MATLAB and the open source MATLAB clone Octave is also provided.
This interface can be used to solve problems that are in the format
used by the SeDuMi \cite{SturmJF:UsiS1M}.

This document describes how to use the stand alone solver, MATLAB and
Octave interface, and library routines.  For detailed instructions on
how to compile and install CSDP see the INSTALL file in the main
directory.

\clearpage
\section*{The SDP Problem}
CSDP solves semidefinite programming problems of the form
\begin{equation}
\begin{array}{rrcl}
\max  & \mbox{tr}\; (CX) & & \\
      & A(X) & = & a \\
      & X                   & \succeq & 0 \\
\end{array}
\end{equation}
where
\begin{equation}
A(X)=\left[
\begin{array}{c}
\mbox{tr} \; (A_{1} X) \\
\mbox{tr} \; (A_{2} X) \\
\ldots \\
\mbox{tr} \; (A_{m} X) \\
\end{array}
\right].
\end{equation}
Here $X \succeq 0$ means that $X$ is positive semidefinite.  All of
the matrices $A_{i}$, $X$, and $C$ are assumed to be
real and symmetric.

The dual of this SDP is
\begin{equation}
\begin{array}{rrcl}
\min  & a^{T}y  & & \\
      & A^{T}(y)-C & = & Z \\
      & Z                   & \succeq & 0 \\
\end{array}
\end{equation}
where
\begin{equation}
A^{T}(y)=\sum_{i=1}^{m} y_{i}A_{i}.
\end{equation}

Other semidefinite programming packages use slight variations on this
primal--dual pair.  For example, the primal--dual pair used in SDPA
interchanges the primal and dual problems.

Users of CSDP can specify their own termination criteria.  However, the
default criteria are that
\begin{equation}
\begin{array}{rcl}
   \frac{\mbox{tr}(XZ)}{1+ | a^{T}y| } &  <  & 1.0 \times 10^{-8} \\
   \frac{\| A(x)- a\|_{2}}{1 + \| a \|_{2}} & < &  1.0 \times 10^{-8} \\
   \frac{\| A^{T}(y) -C -Z \|_{F}}{1 + \|C\|_{F}} & < & 1.0 \times 10^{-8} \\
   X,Z & \succeq & 0. \\
\end{array}
\end{equation}

Note that for feasible primal and dual solutions,
$a^Ty-\mbox{tr}(CX)=\mbox{tr}(XZ)$.  Thus the first of these criteria insures
that the relative duality gap is small.  In practice, there are
sometimes solutions which satisfy our primal and dual feasibility
tolerances but have duality gaps which are not close to
$\mbox{tr}(XZ)$.  In some cases, the duality gap may even become
negative.  Because of this ambiguity, we use the $\mbox{tr}(XZ)$ gap
instead of the difference between the objective functions.  An option
in the param.csdp file allows CSDP to use the difference of the primal
objective functions instead of the $\mbox{tr}(XZ)$ gap.

The matrices $X$ and $Z$ are considered to be positive definite when
their Cholesky factorizations can be computed.  In practice, this is
somewhat more conservative than simply requiring all eigenvalues to be
nonnegative.

The Seventh DIMACS Implementation Challenge used a slightly different
set of error measures \cite{MittelmannHD:AnibS}.  For convenience in
benchmarking, CSDP includes these DIMACS error measures in its
output.

To test for primal infeasibility, CSDP checks the inequality
\begin{equation}
\frac{-a^{T}y}{\| A^{T}(y)-Z \|_{F}} > 1.0 \times 10^8.
\end{equation}
If CSDP detects that a problem is primal infeasible, then it will announce
this in its output and return a dual solution with $a^{T}y=-1$, and
$\| A^{T}(y)-Z \|$ very small.  This acts as a certificate of primal
infeasibility.

Similarly, CSDP tests for dual infeasibility by checking
\begin{equation}
  \frac{\mbox{tr}(CX)}{\| A(X) \|_{2}} > 1.0 \times 10^8.
\end{equation}
If CSDP detects that a problem is dual
infeasible, it announces this in its output and returns a primal
solution with $\mbox{tr}(CX)=1$, and $\| A(X)\|$ small.  This acts
as a certificate of the dual infeasibility.

The tolerances for primal and dual feasibility and the relative duality
gap can be changed by editing CSDP's parameter file.  See the
following section on using the stand alone solver for a description of
this parameter file.

\section*{Using the stand alone solver}
CSDP includes a program which can be used to solve SDP's that have
been written in the SDPA sparse format.   Usage is
\begin{verbatim}
  csdp <problem file> [<final solution>] [<initial solution>]
\end{verbatim}
where {\tt <problem file>} is the name of a file containing the SDP
problem in SDPA sparse format, {\tt final solution} is the optional
name of a file in which to save the final solution, and {\tt initial
solution} is the optional name of a file from which to take the
initial solution.

The following example shows how CSDP would be used to solve a test problem.
\begin{verbatim}
>csdp theta1.dat-s
Iter:  5 Ap: 1.00e+00 Pobj:  7.5846337e+00 Ad: 1.00e+00 Dobj:  4.2853659e+01
Iter:  6 Ap: 1.00e+00 Pobj:  1.5893126e+01 Ad: 1.00e+00 Dobj:  3.0778169e+01
Iter:  7 Ap: 1.00e+00 Pobj:  1.9887401e+01 Ad: 1.00e+00 Dobj:  2.4588662e+01
Iter:  8 Ap: 1.00e+00 Pobj:  2.1623330e+01 Ad: 1.00e+00 Dobj:  2.3465172e+01
Iter:  9 Ap: 1.00e+00 Pobj:  2.2611983e+01 Ad: 1.00e+00 Dobj:  2.3097049e+01
Iter: 10 Ap: 1.00e+00 Pobj:  2.2939498e+01 Ad: 1.00e+00 Dobj:  2.3010908e+01
Iter: 11 Ap: 1.00e+00 Pobj:  2.2996259e+01 Ad: 1.00e+00 Dobj:  2.3000637e+01
Iter: 12 Ap: 1.00e-00 Pobj:  2.2999835e+01 Ad: 1.00e+00 Dobj:  2.3000020e+01
Iter: 13 Ap: 1.00e+00 Pobj:  2.2999993e+01 Ad: 1.00e+00 Dobj:  2.2999999e+01
Iter: 14 Ap: 1.00e+00 Pobj:  2.3000000e+01 Ad: 1.00e+00 Dobj:  2.3000000e+01
Success: SDP solved
Primal objective value: 2.3000000e+01
Dual objective value: 2.3000000e+01
Relative primal infeasibility: 1.11e-16
Relative dual infeasibility: 3.93e-09
Real Relative Gap: 7.21e-09
XZ Relative Gap: 7.82e-09
DIMACS error measures: 1.11e-16 0.00e+00 1.00e-07 0.00e+00 7.21e-09 7.82e-09
Elements time: 0.008845
Factor time: 0.008865
Other time: 0.198949
Total time: 0.216659
\end{verbatim}

One line of output appears for each iteration of the algorithm, giving
the iteration number, primal step size (Ap), primal objective value
(Pobj), dual step size (Ad), and dual objective value (Dobj).  The
last eight lines of output show the primal and dual optimal objective
values, the XZ duality gap, the actual duality gap, the relative
primal and dual infeasibility in the optimal solution.

The last four lines give the time in seconds used by various steps in
the algorithm.  The first line, ``Elements'' shows the time spent in
constructing the Schur complement matrix.  The second line, ``Factor''
shows the time spent in factoring the Schur complement matrix.  The
third line, ``Other'' shows the time spent in all other operations.
The fourth line gives the total time used in solving the problem.
Note that the times given here are ``wall clock'' times, not CPU time.
On a system that is running other programs, the wall clock time may be
considerably larger than the CPU time.  On multiprocessor systems, the
wall clock time will not include all of the CPU time used by the
different processors.  The reported time will typically vary on
repeated runs of CSDP, particularly for samll problems like the one
solved here.

CSDP searches for a file named ``param.csdp'' in the current directory.
If no such file exists, then default values for all of CSDP's parameters
are used.  If there is a parameter file, then CSDP reads the parameter
values from this file.  A sample file containing the default parameter
values is given below.

\begin{verbatim}
axtol=1.0e-8
atytol=1.0e-8
objtol=1.0e-8
pinftol=1.0e8
dinftol=1.0e8
maxiter=100
minstepfrac=0.90
maxstepfrac=0.97
minstepp=1.0e-8
minstepd=1.0e-8
usexzgap=1
tweakgap=0
affine=0
printlevel=1
perturbobj=1
fastmode=0
\end{verbatim}

The first three parameters, axtol, atytol, and objtol are the
tolerances for primal feasibility, dual feasibility, and relative
duality gap.  The parameters pinftol and dinftol are tolerances used
in determining primal and dual infeasibility.  The maxiter parameter
is used to limit the total number of iterations that CSDP may use.
The minstepfrac and maxstepfrac parameters determine how close to the
edge of the feasible region CSDP will step.  If the primal or dual
step is shorter than minstepp or minstepd, then CSDP declares a line
search failure.  If parameter usexzgap is 0, then CSDP will use the
objective function duality gap instead of the
$\mbox{tr}(XZ)$ gap.
If tweakgap is
set to 1, and usexzgap is set to 0, then CSDP will attempt to ``fix'' negative duality gaps.
If parameter affine is set to 1, then CSDP will take only primal--dual
affine steps and not make use of the barrier term.  This can be useful
for some problems that do not have feasible solutions that are strictly in the
interior of the cone of semidefinite matrices.
The printlevel parameter determines how much debugging information is
output.  Use printlevel=0 for no output and printlevel=1 for normal
output. Higher values of printlevel will generate more debugging
output.  The perturbobj parameter determines whether the objective
function will be perturbed to help deal with problems that have unbounded
optimal solution sets.  If perturbobj is 0, then the objective will not
be perturbed.  If perturbobj=1, then the objective function will be perturbed
by a default amount.  Larger values of perturbobj (e.g. 100.0) increase the
size of the perturbation.  This can be helpful in solving some difficult
problems. The fastmode parameter determines whether or not
CSDP will skip certain time consuming operations that slightly improve
the accuracy of the solutions.  If fastmode is set to
1, then CSDP may be somewhat faster, but also somewhat less accurate.

\section*{Calling CSDP from MATLAB or Octave}
An interface to the stand alone solver from MATLAB or Octave is
included in CSDP.  This requires MATLAB 6.5 or later) or Octave 2.9.5
or later.  The interface accepts problems in the format used by the
MATLAB package SeDuMi 1.05.  The usage is

\begin{verbatim}
%
% [x,y,z,info]=csdp(At,b,c,K,pars,x0,y0,z0)
%
% Uses CSDP to solve a problem in SeDuMi format.
%
% Input:
%        At, b, c, K      SDP problem in SeDuMi format.
%        pars             CSDP parameters (optional parameter.)
%        x0,y0,z0         Optional starting point.
%
% Output:
%
%        x, y, z          solution.
%        info             CSDP return code.
%                         info=100 indicates a failure in the MATLAB
%                         interface, such as inability to write to
%                         a temporary file.
%
% Note: This interface makes use of temporary files with names given by the
% tempname function.  This will fail if there is no working temporary
% directory or there isn't enough space available in this directory.
%
% Note: This code writes its own param.csdp file in the current working
% directory.  Any param.csdp file already in the directory will be deleted.
%
% Note: It is assumed that csdp is the search path made available through
% the ``system'' or ``dos'' command.  Typically, having the csdp executable in
% current working directory will work, although some paranoid system
% administrators keep . out of the path.  In that case, you'll need to
% install csdp in one of the directories that is in the search path.
% A simple test is to run csdp from a command line prompt.
\end{verbatim}

The following example shows the solution of a sample problem using this
interface.  To make the example more interesting, we've asked CSDP to
find a solution with a relative duality gap smaller than 1.0e-9 instead
of the usual 1.0e-8.

\begin{verbatim}
>> load control1.mat
>> whos
  Name      Size                   Bytes  Class

  At      125x21                    8488  double array (sparse)
  K         1x1                      140  struct array
  ans       2x1                       16  double array
  b        21x1                      168  double array
  c       125x1                       80  double array (sparse)

Grand total is 732 elements using 8892 bytes

>> pars.objtol=1.0e-9

pars =

    objtol: 1.0000e-09

>> [x,y,z,info]=csdp(At,b,c,K,pars);
Transposing A to match b
Number of constraints: 21
Number of SDP blocks: 2
Number of LP vars: 0
Iter:  0 Ap: 0.00e+00 Pobj:  3.6037961e+02 Ad: 0.00e+00 Dobj:  0.0000000e+00
Iter:  1 Ap: 9.56e-01 Pobj:  3.7527534e+02 Ad: 9.60e-01 Dobj:  6.4836002e+04
Iter:  2 Ap: 8.55e-01 Pobj:  4.0344779e+02 Ad: 9.67e-01 Dobj:  6.9001508e+04
Iter:  3 Ap: 8.77e-01 Pobj:  1.4924982e+02 Ad: 1.00e+00 Dobj:  6.0425319e+04
Iter:  4 Ap: 7.14e-01 Pobj:  8.2819408e+01 Ad: 1.00e+00 Dobj:  1.2926534e+04
Iter:  5 Ap: 8.23e-01 Pobj:  4.7411688e+01 Ad: 1.00e+00 Dobj:  4.9040115e+03
Iter:  6 Ap: 7.97e-01 Pobj:  2.6300212e+01 Ad: 1.00e+00 Dobj:  1.4672743e+03
Iter:  7 Ap: 7.12e-01 Pobj:  1.5215577e+01 Ad: 1.00e+00 Dobj:  4.0561826e+02
Iter:  8 Ap: 8.73e-01 Pobj:  7.5119215e+00 Ad: 1.00e+00 Dobj:  1.7418715e+02
Iter:  9 Ap: 9.87e-01 Pobj:  5.3076518e+00 Ad: 1.00e+00 Dobj:  5.2097312e+01
Iter: 10 Ap: 1.00e+00 Pobj:  7.8594672e+00 Ad: 1.00e+00 Dobj:  2.2172435e+01
Iter: 11 Ap: 8.33e-01 Pobj:  1.5671237e+01 Ad: 1.00e+00 Dobj:  2.1475840e+01
Iter: 12 Ap: 1.00e+00 Pobj:  1.7250217e+01 Ad: 1.00e+00 Dobj:  1.8082715e+01
Iter: 13 Ap: 1.00e+00 Pobj:  1.7710018e+01 Ad: 1.00e+00 Dobj:  1.7814069e+01
Iter: 14 Ap: 9.99e-01 Pobj:  1.7779600e+01 Ad: 1.00e+00 Dobj:  1.7787170e+01
Iter: 15 Ap: 1.00e+00 Pobj:  1.7783579e+01 Ad: 1.00e+00 Dobj:  1.7785175e+01
Iter: 16 Ap: 1.00e+00 Pobj:  1.7784494e+01 Ad: 1.00e+00 Dobj:  1.7784708e+01
Iter: 17 Ap: 1.00e+00 Pobj:  1.7784610e+01 Ad: 1.00e+00 Dobj:  1.7784627e+01
Iter: 18 Ap: 1.00e+00 Pobj:  1.7784626e+01 Ad: 1.00e+00 Dobj:  1.7784620e+01
Iter: 19 Ap: 1.00e-00 Pobj:  1.7784627e+01 Ad: 1.00e+00 Dobj:  1.7784627e+01
Iter: 20 Ap: 9.60e-01 Pobj:  1.7784627e+01 Ad: 9.60e-01 Dobj:  1.7784627e+01
Success: SDP solved
Primal objective value: 1.7784627e+01
Dual objective value: 1.7784627e+01
Relative primal infeasibility: 1.08e-09
Relative dual infeasibility: 3.12e-10
Real Relative Gap: -3.50e-10
XZ Relative Gap: 6.05e-11
DIMACS error measures: 1.08e-09 0.00e+00 7.02e-10 0.00e+00 -3.50e-10 6.05e-11
Elements time: 0.003162
Factor time: 0.000430
Other time: 0.013774
Total time: 0.017366
0.012u 0.004s 0:00.02 50.0%     0+0k 0+0io 0pf+0w
>> info

info =

     0

\end{verbatim}

The {\bf writesdpa} function can be used to write out a problem in SDPA
sparse format.

\begin{verbatim}
%  This function takes a problem in SeDuMi MATLAB format and writes it out
%  in SDPA sparse format.
%
%  Usage:
%
%  ret=writesdpa(fname,A,b,c,K,pars)
%
%      fname           Name of SDPpack file, in quotes
%      A,b,c,K         Problem in SeDuMi form
%      pars            Optional parameters.
%                      pars.printlevel=0           No printed output
%                      pars.prinlevel=1 (default)  Some printed output.
%                      pars.check=0 (default)      Do not check problem data
%                                                  for symmetry.
%                      pars.check=1                Check problem data for
%                                                  symmetry.
%
%      ret             ret=0 on success, ret=1 on failure.
%
\end{verbatim}

Problems in the SeDuMi format may involve ``free'' variables.  A free variable
can be converted into the difference of two non--negative variables using the
{\bf convertf} function.

\begin{verbatim}
%
%  [A,b,c,K]=convertf(A,b,c,K)
%
%  converts free variables in a SeDuMi problem into nonnegative LP variables.
%
\end{verbatim}
\section*{Using the subroutine interface to CSDP}
\subsection*{Storage Conventions}
The matrices $C$, $X$, and $Z$ are treated as block diagonal matrices.
The declarations in the file blockmat.h describe the block matrix
data structure.  The {\tt blockmatrix} structure contains a count of
the number of blocks and a pointer to an array of records that
describe individual blocks.  The individual blocks can be matrices
of size {\tt blocksize} or diagonal matrices in which only a vector
of diagonal entries is stored.

Individual matrices within a block matrix are stored in column major
order as in Fortran.  The ijtok() macro defined in index.h can be used
to convert Fortran style indices into an index into a C vector.  For
example, if A is stored as a Fortran array with leading dimension
n, element (i,j) of A can be accessed within a C program as
A[ijtok(i,j,n)].

The following table  demonstrates how a 3 by 2 matrix would
be stored under this system.
\\
\\
\begin{tabular}{|l|l|} \hline
C index & Fortran index \\ \hline
A[0] & A(1,1) \\ \hline
A[1] & A(2,1) \\ \hline
A[2] & A(3,1) \\ \hline
A[3] & A(1,2) \\ \hline
A[4] & A(2,2) \\ \hline
A[5] & A(3,2) \\ \hline
\end{tabular}

Vectors are stored as conventional C vectors.  However, indexing
always starts with 1, so the [0] element of every vector is wasted.
Most arguments are described as being of size {\tt n} or {\tt
m}.  Since the zeroth element of the vector is wasted, these
vectors must actually be of size {\tt n+1} or {\tt m+1}.

The constraint matrices $A_{i}$ are stored in a sparse form.  The array
{\bf constraints} contains pointers which point to linked lists of
structures, with one structure for each block of the sparse matrix.
The {\bf sparseblock} data structures contain pointers to arrays which
contain the entries and their {\bf i} and {\bf j} indices.

For an example of how to setup these data structures, refer to the
example directory in the CSDP distribution.
This directory contains a program that solves the very
small SDP

\begin{equation}
\begin{array}{rrcl}
\max  & \mbox{tr}\; (CX)  & & \\
      & \mbox{tr}\;A_{1}X & = & 1 \\
      & \mbox{tr}\;A_{2}X & = & 2 \\
      & X                   & \succeq & 0 \\
\end{array}
\end{equation}
where
\begin{equation}
C=\left[
\begin{array}{rrrrrrr}
 2 &  1 &   &   &   &   &    \\
 1 &  2 &   &   &   &   &    \\
   &    & 3 & 0 & 1 &   &    \\
   &    & 0 & 2 & 0 &   &    \\
   &    & 1 & 0 & 3 &   &    \\
   &    &   &   &   & 0 &    \\
   &    &   &   &   &   & 0  \\
\end{array}
\right]
\end{equation}
\begin{equation}
A_{1}=\left[
\begin{array}{rrrrrrr}
 3 &  1 &   &   &   &   &    \\
 1 &  3 &   &   &   &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    &   &   &   & 1 &    \\
   &    &   &   &   &   & 0  \\
\end{array}
\right]
\end{equation}
\begin{equation}
A_{2}=\left[
\begin{array}{rrrrrrr}
 0 &  0 &   &   &   &   &    \\
 0 &  0 &   &   &   &   &    \\
   &    & 3 & 0 & 1 &   &    \\
   &    & 0 & 4 & 0 &   &    \\
   &    & 1 & 0 & 5 &   &    \\
   &    &   &   &   & 0 &    \\
   &    &   &   &   &   & 1  \\
\end{array}
\right].
\end{equation}

In this problem, the $X$, $Z$, $A_{1}$, $A_{2}$ and $C$ matrices have
three blocks.  The first block is a 2 by 2 matrix.  The second block
is a 3 by 3 matrix.  The third block is a diagonal block with 2
entries.

In addition to setting up and solving this problem, the example
program calls the write\_prob() routine to produce a file containing
the SDP problem in SDPA sparse format.  This is stored in the file
prob.dat-s.

\begin{verbatim}
2
3
2 3 -2
1.000000000000000000e+00 2.000000000000000000e+00
0 1 1 1 2.000000000000000000e+00
0 1 1 2 1.000000000000000000e+00
0 1 2 2 2.000000000000000000e+00
0 2 1 1 3.000000000000000000e+00
0 2 1 3 1.000000000000000000e+00
0 2 2 2 2.000000000000000000e+00
0 2 3 3 3.000000000000000000e+00
1 1 1 1 3.000000000000000000e+00
1 1 1 2 1.000000000000000000e+00
1 1 2 2 3.000000000000000000e+00
1 3 1 1 1.000000000000000000e+00
2 2 1 1 3.000000000000000000e+00
2 2 2 2 4.000000000000000000e+00
2 2 3 3 5.000000000000000000e+00
2 2 1 3 1.000000000000000000e+00
2 3 2 2 1.000000000000000000e+00
\end{verbatim}
The 2 in the first line indicates that this problem has two constraints.
The 3 in the second line indicates that there are three blocks in the $X$
and $Z$ matrices.  The third line gives the sizes of the three blocks.  Note
that the third block's size is given as -2.  The minus sign indicates that
this is a diagonal block.  The fourth line gives the values of the right
hand sides of the two constraints.

The remaining lines in the file describe the entries in the $C$,
$A_{1}$, and $A_{2}$ matrices.  The first number in each line is the
number of the matrix, with $0$ for the $C$ matrix.  The second number
specifies a block within the matrix.  The third and fourth numbers give
the row and column of a nonzero entry within this block.  The fifth number
gives the actual value at that position within the block.
Comparing this file to the problem statement above
can be helpful in understanding the SDPA sparse file format.

Figure \ref{cmat} shows a graphical representation of the
data structure that holds the C matrix.  Notice that individual matrix
blocks of the C matrix are stored as Fortran arrays and that the
diagonal block is stored as a vector, with the 0 entry unused.  The data
structures for $X$ and $Z$ are similar.

\begin{figure}
\begin{center}
\scalebox{0.5}{\includegraphics{cmat}}
\caption{The C matrix.}
\label{cmat}
\end{center}
\end{figure}

Figure \ref{constraints} shows the overall structure of the constraints.  There
is a vector of pointers to linked lists of constraint blocks.  The 0th entry
in this array is ignored.  Blocks that contain only zero entries are not
stored in the linked lists.  Figure \ref{a1block1} shows the detail
of the data structure for block 1 of the constraint matrix $A_{1}$.

\begin{figure}
\begin{center}
\scalebox{0.5}{\includegraphics{constraints}}
\caption{The constraints.}
\label{constraints}
\end{center}
\end{figure}

\begin{figure}
\begin{center}
\scalebox{0.5}{\includegraphics{a1block1}}
\caption{Block 1 of $A_{1}$.}
\label{a1block1}
\end{center}
\end{figure}

\clearpage

After solving the problem, the example program outputs the solution to
prob.sol using the write\_sol() routine.  The output produced on
different computers might vary because of floating point round--off
differences.  However, the following output is typical.

\begin{verbatim}
7.499999999674811235e-01 9.999999995736339464e-01
1 1 1 1 2.500000018710683558e-01
1 1 1 2 -2.500000000325189320e-01
1 1 2 2 2.500000018710683558e-01
1 2 1 1 6.895272851149165827e-10
1 2 1 3 -4.263660251297748376e-10
1 2 2 2 2.000000000263161049e+00
1 2 3 3 1.999999999836795217e+00
1 3 1 1 7.500000019361059422e-01
1 3 2 2 1.000000001542258765e+00
2 1 1 1 1.250000001467082567e-01
2 1 1 2 1.249999992664581755e-01
2 1 2 2 1.250000001467082567e-01
2 2 1 1 6.666669670820890570e-01
2 2 1 3 -4.518334811445142147e-07
2 2 2 2 2.200629338637236883e-10
2 2 3 3 2.200635108933231998e-10
2 3 1 1 5.868341556035494699e-10
2 3 2 2 4.401258478508541047e-10
\end{verbatim}

The first line of the file gives the optimal y values.  The lines that
start with "1 " give the nonzero entries in the optimal Z matrix.  As in
the SDPA input file there are five numbers per line.  The first number
is the number of the matrix, where 1 is used for $Z$ and 2 is used
for $X$.  The second number specifies a block within the matrix.
The third and fourth numbers are the row and column within the block.
The final number is the actual value at the position in the block.
For example,
\begin{verbatim}
2 2 1 3 -4.518334811445142147e-07
\end{verbatim}
means that in the 1st row, third column of block 2 of the $X$ matrix, the
entry is $-4.518334811445142147\times 10^{-7}$.
Since the matrices are symmetric, we only record
the entries in the upper triangle of the matrix.   The same entry will
also appear in row 3, column 1.

So, the optimal solution to the example problem is (rounding the
numbers off to two or three digits)

\begin{equation}
y=\left[
\begin{array}{rr}
0.75 & 1.00
\end{array}
\right]
\end{equation}

\begin{equation}
Z=\left[
\begin{array}{rrrrrrr}
 0.25 & -0.25 &   &   &   &   &    \\
 -0.25 & 0.25 &   &   &   &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    & 0 & 2.00 & 0 &   &    \\
   &    & 0 & 0 & 2.00 &   &    \\
   &    &   &   &   & 0.75 &    \\
   &    &   &   &   &   & 1.00  \\
\end{array}
\right]
\end{equation}

\begin{equation}
X=\left[
\begin{array}{rrrrrrr}
 0.125 &  0.125 &   &   &   &   &    \\
 0.125 &  0.125 &   &   &   &   &    \\
   &    & 0.667 & 0 & 0 &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    & 0 & 0 & 0 &   &    \\
   &    &   &   &   & 0 &    \\
   &    &   &   &   &   & 0  \\
\end{array}
\right]
\end{equation}

\subsection*{Storage Requirements}
CSDP requires storage for a number of block diagonal matrices of the same
form as $X$ and $Z$, as well as storage for the Schur complement system that
is Cholesky factored in each iteration.  For a problem with $m$ constraints
and block diagonal matrices with blocks of size $n_{1}$, $n_{2}$, $\dots$,
$n_{s}$, CSDP requires approximately
\begin{equation}
\mbox{Storage}=8(m^{2}+11(n_{1}^{2}+n_{2}^{2}+\ldots+n_{s}^{2}))
\end{equation}
bytes of storage.  This formula includes all of the two dimensional
arrays but leaves out the one dimensional vectors.  This formula also
excludes the storage required to store the constraint matrices, which
are assumed to be sparse.  In practice it is wise to allow for about
10\% to 20\% more storage to account for the excluded factors.

The parallel version of CSDP requires additional storage for work
matrices used by the routine that computes the Schur complement
matrix.  If the OpenMP maximum number of threads (typically the number
of processors on the system) is $p$, and $p>1$, then CSDP will
allocate an additional $16(p-1)n_{\mbox{max}}^{2}$
bytes of storage for workspace.

\subsection*{Calling The SDP Routine}
The routine has 11 parameters which include the problem data and an
initial solution.  The calling sequence for the sdp subroutine is:

\begin{verbatim}
int easy_sdp(n,k,C,a,constraints,constant_offset,pX,py,pZ,ppobj,pdobj)
   int n;                                 /* Dimension of X */
   int k;                                 /* # of constraints */
   struct blockmatrix C;                  /* C matrix */
   double *a;                             /* right hand side vector */
   struct constraintmatrix *constraints;  /* Constraints */
   double constant_offset;                /* added to objective */
   struct blockmatrix *pX;                /* X matrix */
   double **py;                           /* y vector */
   struct blockmatrix *pZ;                /* Z matrix */
   double *ppobj;                         /* Primal objective */
   double *pdobj;                         /* Dual objective */
\end{verbatim}
\subsection*{Input Parameters}
\begin{enumerate}
\item {\tt n}. This parameter gives the dimension of the X, C, and Z matrices.
\item {\tt k}. This parameter gives the number of constraints.
\item {\tt C}.  This parameter gives the $C$ matrix and implicitly defines
the block structure of the block diagonal matrices.
\item {\tt a}.  This parameter gives the right hand side vector $a$.
\item {\tt constraints}.  This parameter specifies the problem constraints.
\item {\tt constant\_offset}.  This scalar is added to the primal and dual
objective values.
\item {\tt pX}.  On input, this parameter gives the initial primal solution $X$.
\item {\tt py}.  On input, this parameter gives the initial dual solution $y$.
\item {\tt pZ}.  On input, this parameter gives the initial dual solution $Z$.
\end{enumerate}
\subsection*{Output Parameters}
\begin{enumerate}
\item {\tt pX}.  On output this parameter gives the optimal primal solution $X$.
\item {\tt py}.  On output, this parameter gives the optimal dual solution $y$.
\item {\tt pZ}.  On output, this parameter gives the optimal dual solution $Z$.
\item {\tt ppobj}.  On output, this parameter gives the optimal primal objective value.
\item {\tt pdobj}.  On output, this parameter gives the optimal dual objective value.
\end{enumerate}
\subsection*{Return Codes}
If CSDP succeeds in solving the problem to full accuracy,
the {\tt easy\_sdp} routine will return 0.
Otherwise, the {\tt easy\_sdp} routine will return a nonzero
return code.  In many cases, CSDP will have actually found a good
solution that doesn't quite satisfy one of the termination criteria.
In particular, return code 3 is usually indicative of such a solution.
Whenever there is a nonzero return code, you should examine the return
and the solution to see what happened.

The nonzero return codes are
\begin{enumerate}
\item Success.  The problem is primal infeasible.
\item Success.  The problem is dual infeasible.
\item Partial Success.  A solution has been found, but full accuracy was
not achieved.  One or more of primal infeasibility, dual infeasibility,
or relative duality gap are larger than their tolerances, but by a factor
of less than 1000.
\item Failure.  Maximum iterations reached.
\item Failure.  Stuck at edge of primal feasibility.
\item Failure.  Stuck at edge of dual infeasibility.
\item Failure.  Lack of progress.
\item Failure.  X, Z, or O was singular.
\item Failure.  Detected NaN or Inf values.
\end{enumerate}
\subsection*{The User Exit Routine}

By default, the {\tt easy\_sdp} routine stops when it has obtained a
solution in which the relative primal and dual infeasibilities and the
relative gap between the primal and dual objective values is less than
$1.0 \times 10^{-8}$.  There are situations in which you might want to
terminate the solution process before an optimal solution has been
found.  For example, in a cutting plane routine, you might want to
terminate the solution process as soon as a cutting plane has been
found.  If you would like to specify your own stopping criteria, you
can implement these in a user exit routine.

At each iteration of its algorithm, CSDP calls a routine named {\tt
user\_exit}.  CSDP passes the problem data and current solution to
this subroutine.  If {\tt user\_exit} returns 0, then CSDP continues.
However, if {\tt user\_exit} returns 1, then CSDP returns immediately
to the calling program.  The default routine supplied in the CSDP
library simply returns 0.  If CSDP is compiled
with the ``-DUSESIGTERM'' flag, then default routine will also stop
the solution process whenever the process receives a TERM signal.
You can write your own routine and link it
with your program in place of the default user exit routine.

The calling sequence for the user exit routine is
\begin{verbatim}
int user_exit(n,k,C,a,dobj,pobj,constant_offset,constraints,X,y,Z,params)
   int n;                                 /* Dimension of X */
   int k;                                 /* # of constraints */
   struct blockmatrix C;                  /* C matrix */
   double *a;                             /* right hand side */
   double dobj;                           /* dual objective  */
   double pobj;                           /* primal objective */
   double constant_offset;                /* added to objective */
   struct constraintmatrix *constraints;  /* Constraints */
   struct blockmatrix X;                  /* primal solution */
   double *y;                             /* dual solution */
   struct blockmatrix Z;                  /* dual solution */
   struct paramstruc params;              /* parameters sdp called with */
\end{verbatim}
\subsection*{Finding an Initial Solution}
The CSDP library contains a routine for finding an initial solution to the
SDP problem.  Note that this routine allocates all storage required for the
initial solution.  The calling sequence for this routine is:

\begin{verbatim}
void initsoln(n,k,C,a,constraints,pX0,py0,pZ0)
   int n;                                  /* dimension of X */
   int k;                                  /* # of constraints */
   struct blockmatrix C;                   /* C matrix */
   double *a;                              /* right hand side vector */
   struct constraintmatrix *constraints;   /* constraints */
   struct blockmatrix *pX0;                /* Initial primal solution */
   double **py0;                           /* Initial dual solution */
   struct blockmatrix *pZ0;                /* Initial dual solution */
\end{verbatim}

\subsection*{Reading and Writing Problem Data}
The CSDP library contains routines for reading and writing SDP
problems and solutions in SDPA format. The routine {\tt write\_prob}
is used to write out an SDP problem in SDPA sparse format.  The
routine {\tt read\_prob} is used to read an SDP problem in from a
file.  The routine {\tt write\_sol} is used to write an SDP solution
to a file.  The routine {\tt read\_sol} is used to read a solution
from a file.

The calling sequence for {\tt write\_prob} is

\begin{verbatim}
int write_prob(fname,n,k,C,a,constraints)
   char *fname;                          /* file to write */
   int n;                                /* Dimension of X */
   int k;                                /* # of constraints */
   struct blockmatrix C;                 /* The C matrix */
   double *a;                            /* The a vector */
   struct constraintmatrix *constraints; /* the constraints */
\end{verbatim}

The calling sequence for {\tt read\_prob} is:

\begin{verbatim}
int read_prob(fname,pn,pk,pC,pa,pconstraints,printlevel)
   char *fname;                /* file to read  */
   int *pn;                    /* Dimension of X */
   int *pk;                    /* # of constraints */
   struct blockmatrix *pC;     /* The C matrix */
   double **pa;                /* The a vector */
   struct constraintmatrix **pconstraints;  /* The constraints */
   int printlevel;             /* =0 for no output, =1 for normal
                                  output, >1 for debugging */
\end{verbatim}
Note that the {\tt read\_prob} routine allocates all storage required
by the problem.

The calling sequence for {\tt write\_sol} is

\begin{verbatim}
int write_sol(fname,n,k,X,y,Z)
   char *fname;                     /* Name of the file to write to */
   int n;                           /* Dimension of X */
   int k;                           /* # of constraints */
   struct blockmatrix X;            /* Primal solution X */
   double *y;                       /* Dual vector y */
   struct blockmatrix Z;            /* Dual matrix Z */
\end{verbatim}
This routine returns 0 if successful and exits if it is unable to write
the solution file.

The calling sequence for {\tt read\_sol} is

\begin{verbatim}
int read_sol(fname,n,k,C,pX,py,pZ)
   char *fname;                     /* file to read */
   int n;                           /* dimension of X */
   int k;                           /* # of constraints */
   struct blockmatrix C;            /* The C matrix */
   struct blockmatrix *pX;          /* The X matrix */
   double **py;                     /* The y vector */
   struct blockmatrix *pZ;          /* The Z matrix */
\end{verbatim}
Note that {\tt read\_sol} allocates storage for $X$, $y$, and $Z$.  This
routine returns 0 when successful, and exits if it is unable to read
the solution file.

\subsection*{Freeing Problem Memory}
The routine {\tt free\_prob} can be used to automatically
free the memory allocated for a problem.  The calling sequence
for {\tt free\_prob} is

\begin{verbatim}
void free_prob(n,k,C,a,constraints,X,y,Z)
    int n;                                /* Dimension of X */
    int k;                                /* # of constraints */
    struct blockmatrix C;                 /* The C matrix */
    double *a;                            /* The a vector */
    struct constraintmatrix *constraints; /* the constraints */
    struct blockmatrix X;                 /* X matrix. */
    double *y;                            /* the y vector. */
    struct blockmatrix Z;                 /* Z matrix. */
\end{verbatim}

\bibliography{sdp}

\end{document}

max_stars_repo_name: RedFantom/limbo

max_issues_repo_name: RedFantom/limbo

max_forks_repo_name: RedFantom/limbo


text:
\chapter{Recognition of Abstractions}

   Figure~\ref{Tutorial:exampleRecognitionOfAbstractions} shows the low level
construction of a more complex AST fragment (a function declaration) and its insertion
into the AST at the top of each block.  Note that the code does not handle
symbol table issues.

   Building a function in global scope.

\begin{figure}[!h]
{\indent
{\mySmallFontSize

\label{Tutorial:exampleRecognitionOfAbstractions}

% Do this when processing latex to generate non-html (not using latex2html)
\begin{latexonly}
   \lstinputlisting{\TutorialExampleDirectory/addVariableDeclaration.C}
\end{latexonly}

% Do this when processing latex to build html (using latex2html)
\begin{htmlonly}
   \verbatiminput{\TutorialExampleDirectory/addVariableDeclaration.C}
\end{htmlonly}

% end of scope in font size
}
% End of scope in indentation
}
\caption{Example source code showing automated recognition of high-level abstractions
    within AST (as support for complex domain-specific transformations).}
\end{figure}

max_stars_repo_name: maurizioabba/rose

max_issues_repo_name: sujankh/rose-matlab

max_forks_repo_name: sujankh/rose-matlab


text:
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CS624: Analysis of Algorithms
% Copyright 2015 Pejman Ghorbanzade <pejman@ghorbanzade.com>
% Creative Commons Attribution-ShareAlike 4.0 International License
% More info: https://github.com/ghorbanzade/beacon
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Question 2}

For each of the following undirected graphs either show that there is a Hamiltonian cycle or prove that none can exist.

\begin{figure}[H]\centering
\tikzstyle{every node}=[circle, draw, fill=gray!20]
\begin{subfigure}{0.32\textwidth}\centering
  \begin{tikzpicture}[scale=0.75, transform shape]
    \node (n1) at (0,0) {D};
    \node (n2) at (4,0) {C};
    \node (n3) at (1,-1) {H};
    \node (n4) at (3,-1) {G};
    \node (n5) at (3,-3) {F};
    \node (n6) at (1,-3) {E};
    \node (n7) at (0,-4) {A};
    \node (n8) at (4,-4) {B};
    \path[draw,thick]
    (n1) edge (n2)
    (n1) edge (n3)
    (n1) edge (n7)
    (n2) edge (n4)
    (n2) edge (n8)
    (n3) edge (n4)
    (n3) edge (n6)
    (n4) edge (n5)
    (n5) edge (n6)
    (n6) edge (n7)
    (n5) edge (n8)
    (n7) edge (n8)
	;
  \end{tikzpicture}
\caption{Graph $F$}
\label{fig:sfig1}
\end{subfigure}
\begin{subfigure}{0.32\textwidth}\centering
  \begin{tikzpicture}[scale=0.75, transform shape]
    \node (n1) at (0,0) {A};
    \node (n2) at (2,0) {B};
    \node (n3) at (4,0) {C};
    \node (n4) at (0,4) {G};
    \node (n5) at (2,4) {H};
    \node (n6) at (4,4) {I};
    \path[draw,thick]
    (n1) edge (n2)
    (n2) edge (n3)
    (n4) edge (n5)
    (n5) edge (n6)
    (n1) edge (n4)
    (n2) edge (n5)
    (n3) edge (n6)
	;
  \end{tikzpicture}
\caption{Graph $G$}
\label{fig:sfig2}
\end{subfigure}
\begin{subfigure}{0.32\textwidth}\centering
  \begin{tikzpicture}[scale=0.75, transform shape]
    \node (n1) at (0,0) {A};
    \node (n2) at (2,0) {B};
    \node (n3) at (4,0) {C};
    \node (n4) at (0,2) {D};
    \node (n5) at (2,2) {E};
    \node (n6) at (4,2) {F};
    \node (n7) at (0,4) {G};
    \node (n8) at (2,4) {H};
    \node (n9) at (4,4) {I};
    \path[draw,thick]
    (n1) edge (n2)
    (n2) edge (n3)
    (n4) edge (n5)
    (n5) edge (n6)
    (n7) edge (n8)
    (n8) edge (n9)
    (n1) edge (n4)
    (n2) edge (n5)
    (n3) edge (n6)
    (n4) edge (n7)
    (n5) edge (n8)
    (n6) edge (n9)
	;
  \end{tikzpicture}
\caption{Graph $H$}
\label{fig:sfig3}
\end{subfigure}
\caption{Connected Undirected Graphs for Question 2}\label{fig21}
\end{figure}

\subsection*{Solution}

For a graph $G = (V,E)$ to have a Hamiltonian Cycle, there should be a cycle that contains every vertex in $V$ exactly once.
Therefore, to show a graph $G$ has a Hamiltonian Cycle, it suffices to propose a cycle that begins with $u \in V$, passes every $v \in V-\{u\}$ and ends in $u \in V$.

We can also prove by contradiction that $G$ has a Hamiltonian Cycle $c$ if any vertex $u \in V$ is an endpoint of exactly $2$ edges in $c$.
If $u$ is an endpoint of less than 2 edges, then $u$ is either not connected to $c$ or $c$ is not a cycle; both cases leading to contradiction.
If $u$ is an endpoint of more than two edges, starting from $u$, we can follow $u$ to $v$, using one edge, then return to $u$ using another edge and then visit the third connected vertex.
However, since $c$ is a cycle, we should end our path with $u$, thus visiting $u$ more than twice which contradicts definition of Hamiltonian Cycle.
Therefore, to show that a graph $G$ does not have any Hamiltonian Cycle $c$, we show that there is a vertex $v \in V$ which is an endpoint of more than 2 edges in $c$.
\begin{enumerate}[label=(\alph*)]
\item There is a cycle $c$ of the form $A \rightarrow B \rightarrow C \rightarrow D \rightarrow H \rightarrow G \rightarrow F \rightarrow E \rightarrow A$, that passes through all vertices in $V$ and ends in $A$.
Therefore, Graph $F$ has a Hamiltonian Cycle.
\item There is a cycle $c$ of the form $A \rightarrow B \rightarrow C \rightarrow I \rightarrow H \rightarrow G \rightarrow A$, that passes through all vertices in $V$ and ends in $A$.
Therefore, Graph $G$ has a Hamiltonian Cycle.
\item Vertex $E$ in graph $H$ is connected to $H$ via 4 edges.
Since we proved any Hamiltonian cycle $c$ should pass vertex $E$ with 2 edges, $E$ will be connected to exactly 2 vertices from the set $S = \{B, D, F, H\}$.
Regardless of our choice, choosing any two-element subset of $S$ will immediately divide yet-unvisited vertices into two islands and after visiting one of them, we are unable to visit the other without passing again from an already-visited node.
Therefore, graph $H$ does not have any Hamiltonian Cycle.
\end{enumerate}

max_stars_repo_name: ghorbanzade/beacon

max_issues_repo_name: ghorbanzade/beacon

max_forks_repo_name: ghorbanzade/beacon