paper.tex

\documentclass{article}
%\documentclass[twocolumn]{article}%
\usepackage[utf8]{inputenc}%
\usepackage{standalone}%
\usepackage{amsmath}%
\usepackage{amsthm}%
\usepackage{amssymb}%
\usepackage{hyperref}%
\usepackage{xcolor}%
\usepackage{tabularx}%
\usepackage{listings}%
\usepackage{colortbl}
\usepackage{enumitem}

\usepackage{listings, xcolor}

\definecolor{verylightgray}{rgb}{.97,.97,.97}

\lstdefinelanguage{Solidity}{
	keywords=[1]{anonymous, assembly, assert, balance, break, call, callcode, case, catch, class, constant, continue, constructor, contract, debugger, default, delegatecall, delete, do, else, emit, event, experimental, export, external, false, finally, for, function, gas, if, implements, import, in, indexed, instanceof, interface, internal, is, length, library, log0, log1, log2, log3, log4, memory, modifier, new, payable, pragma, private, protected, public, pure, push, require, return, returns, revert, selfdestruct, send, solidity, storage, struct, suicide, super, switch, then, this, throw, transfer, true, try, typeof, using, value, view, while, with, addmod, ecrecover, keccak256, mulmod, ripemd160, sha256, sha3}, % generic keywords including crypto operations
	keywordstyle=[1]\color{blue}\bfseries,
	keywords=[2]{address, bool, byte, bytes, bytes1, bytes2, bytes3, bytes4, bytes5, bytes6, bytes7, bytes8, bytes9, bytes10, bytes11, bytes12, bytes13, bytes14, bytes15, bytes16, bytes17, bytes18, bytes19, bytes20, bytes21, bytes22, bytes23, bytes24, bytes25, bytes26, bytes27, bytes28, bytes29, bytes30, bytes31, bytes32, enum, int, int8, int16, int24, int32, int40, int48, int56, int64, int72, int80, int88, int96, int104, int112, int120, int128, int136, int144, int152, int160, int168, int176, int184, int192, int200, int208, int216, int224, int232, int240, int248, int256, mapping, string, uint, uint8, uint16, uint24, uint32, uint40, uint48, uint56, uint64, uint72, uint80, uint88, uint96, uint104, uint112, uint120, uint128, uint136, uint144, uint152, uint160, uint168, uint176, uint184, uint192, uint200, uint208, uint216, uint224, uint232, uint240, uint248, uint256, var, void, ether, finney, szabo, wei, days, hours, minutes, seconds, weeks, years},	% types; money and time units
	keywordstyle=[2]\color{teal}\bfseries,
	keywords=[3]{block, blockhash, coinbase, difficulty, gaslimit, number, timestamp, msg, data, gas, sender, sig, value, now, tx, gasprice, origin},	% environment variables
	keywordstyle=[3]\color{violet}\bfseries,
	identifierstyle=\color{black},
	sensitive=false,
	comment=[l]{//},
	morecomment=[s]{/*}{*/},
	commentstyle=\color{gray}\ttfamily,
	stringstyle=\color{red}\ttfamily,
	morestring=[b]',
	morestring=[b]"
}

\lstset{
	language=Solidity,
	backgroundcolor=\color{verylightgray},
	extendedchars=true,
	basicstyle=\footnotesize\ttfamily,
	showstringspaces=false,
	showspaces=false,
	numbers=left,
	numberstyle=\footnotesize,
	numbersep=9pt,
	tabsize=2,
	breaklines=true,
	showtabs=false,
	captionpos=b
}

\lstdefinelanguage{circom}{
	keywords=[1]{signal, input, output, public, template, component, var, function, return, if, else, for, while,
		do, log, assert, include, pragma, circom}, % generic keywords including crypto operations
	keywordstyle=[1]\color{blue}\bfseries,
	keywords=[2]{},	% types; money and time units
	keywordstyle=[2]\color{teal}\bfseries,
	keywords=[3]{},	% environment variables
	keywordstyle=[3]\color{violet}\bfseries,
	identifierstyle=\color{black},
	sensitive=false,
	comment=[l]{//},
	morecomment=[s]{/*}{*/},
	commentstyle=\color{gray}\ttfamily,
	stringstyle=\color{red}\ttfamily,
	morestring=[b]',
	morestring=[b]"
}

\lstset{
	language=circom,
	backgroundcolor=\color{verylightgray},
	extendedchars=true,
	basicstyle=\footnotesize\ttfamily,
	showstringspaces=false,
	showspaces=false,
	numbers=left,
	numberstyle=\footnotesize,
	numbersep=9pt,
	tabsize=2,
	breaklines=true,
	showtabs=false,
	captionpos=b
}

\newcommand{\khk}{K_{H}}
\newcommand{\khkp}{$K^{-1}[\text{HK}]$}
\newcommand{\kid}{K_{ID}}
%\newcommand{\kid}{$K$}
\newcommand{\todo}[1]{\fbox{\parbox{\linewidth}{\textcolor{red}{#1}}}}
\newcommand{\iv}{$IV(\text{\identity})$}
\newcommand{\sigid}{$K^{-1}[CA](K[Identity])$}
\newtheorem{problem}{Problem}
\newenvironment{solution}
  {\emph{Solution:}}
  {\hfill $\square$}
\newcommand{\pbc}{\textit{Identity Blockchain}}

\title{Identity Blockchain - Proof of Identity}
\author{
Albert Vučinović, University North\\
Miroslav Jerković, University of Zagreb}
\begin{document}
\maketitle

\begin{abstract}
$\pbc$ uses state-certified electronic identities (eIDs) to create blockchain identities and a consensus protocol called Proof of Identity (PoI). PoI is "green" and enables many applications that are impossible to implement without verified identity on the blockchain, e.g., direct democracy and universal basic income, encrypted messaging, etc. $\pbc$ preserves identity anonymity by using zk-SNARKs and an anonymization protocol for identity onboarding.
\end{abstract}

\section{Introduction}
TODO

\section{Notation}
\vspace{10px}
 \arrayrulecolor{gray}
\begin{tabular}{p{0.16\linewidth}| p{0.81\linewidth}}
  $(K, K^{-1})$ & \ \ Pair of public key $K$ and the corresponding private key $K^{-1}$ \\[3px]
	$K(value)$ & \ \ String $value$ encrypted with a public key $K$ \\[3px]
	$K^{-1}(value)$ & \ \ String $value$ encrypted with a private key $K^{-1}$ \\[3px]
  $H$ & \ \ zk-SNARK-friendly hash function \\[5px]
 \hline \\
   $Nin$ & \ \ Unique state-issued personal \textit{National Identification Number}\\[3px]
   $CA$ & \ \ Certificate Authority \\[3px]
   $eID$ & \ \ Electronic identification document \\[3px]
	$\kid$ & \ \ CA-certified public key of eID\\[3px]
  $\khk$ & \ \ Human key, unique public key to access \pbc{}

\end{tabular}

\vspace{15px}

Sometimes we write $K$ for $(K, K^{-1})$.

\newpage
\section{Registering $\kid$}
Register $\kid$ on \pbc{} by calling $$register\kid(H(Nin), \kid^{-1}("register\kid"), invalidate\kid, verifyProofArguments).$$
\begin{enumerate}[leftmargin=0cm]

	\item[] \underline{Pseudo-solidity code}

	\hfill\begin{minipage}{\dimexpr\textwidth-20px}
	\begin{lstlisting}[language=Solidity]
	pragma solidity ^0.8.0;
		
	mapping(uint => uint) public ninKidUsed;
	mapping(uint => bool) public kidInvalid;
	
	function registerKid(
		uint hNin, // hNin = H(Nin)
		uint vKid, // vKid = KidPrivate("registerKid")
		bool invalidateKid,
		uint[2] memory proofPointA,
		uint[2][2] memory proofPointB,
		uint[2] memory proofPointC
	) public {
		// Setting public arguments
		uint[] memory inputValues = new uint[](2);
		inputValues[0] = hNin;
		inputValues[1] = vKid;
	
		require(
			verifyProof(proofPointA, proofPointB, proofPointC, inputValues)
		);
	
		uint previousVKid = ninKidUsed[hNin];
		if (previousVKid == vKid) return; // already registered
		if (previousVKid != vKid && invalidateKid == true) {
			// If they are different, invalidate old Kid
			kidInvalid[previousVKid] = true;
		}
		require(!kidInvalid[vKid]);
	
		ninKidUsed[hNin] = vKid;
	}
	\end{lstlisting}
	\xdef\tpd{\the\prevdepth}
	\end{minipage}

	\item[] Features
    \begin{itemize}
      \item[] \textbf{Sybil resistance} \\ A Person is prevented from registering more than one $\khk$, e.g. by using different eIDs issued for the same $Nin$.
          \vspace{5px}
      \item[] \textbf{Fix for the loss of eID} \\ A Person who has lost a previously registered $\kid$, e.g. due to loss of eID, can overwrite it by registering a new $\kid$.
          \vspace{5px}
      \item[] \textbf{Identity theft damage control} \\ If a Person overwrites the previous $\kid$ with a new one, the identity Thief loses access to services that verify the entire identity chain.
    \end{itemize}

\item[] Remarks
\begin{itemize}
\item[i)] An entity that knows $\kid$, e.g. the CA who certified the corresponding eID, can know that the Person has registered $\kid$ on \pbc{}.
\item[ii)] Reasoning for the choice of arguments $H(Nin)$ and $\kid^{-1}("register\kid")$: 
\begin{itemize}
	\item[-] if $H(Nin, \kid^{-1}("register\kid"))$ was instead used, then if someone tried to register with two different eIDs, we couldn't tell if $Nin$ was already used. 
	\item[-] the choice of arguments $Nin$ and $\kid^{-1}("register\kid")$ would be almost the same as $H(Nin)$ and $\kid^{-1}("register\kid")$, because you can brute force all the possible $Nin$s and find the corresponding $H(Nin)$s.
\end{itemize}
\end{itemize}

\item[] \underline{Pseudo-circom code}

Statements we need to check:
\begin{itemize}
	\item[1)] CA is accepted by \pbc{} (assumption: the set representations of \textit{CA-public-keys} and \textit{revoked-CA-public-keys} lists exist on \pbc{}):
		\begin{itemize}
			\item[i)] inclusion of the CA in cert in \textit{CA-public-keys}.
			\item[ii)] exclusion of the CA in cert from \textit{revoked-CA-public-keys}.
		\end{itemize}
		Verify CA validity with respect to time (maybe on \pbc{})!
	\item[2)] Cert CA signed: 
		\begin{itemize}
			\item[i)] $\kid$
			\item[ii)] x509 Subject that contains $Nin$ in the right place in the subject
		\end{itemize}
		Verify validity of x509 certificate with respect to time!
		\item[3)] $\kid$ is not revoked by CA (\pbc{} hosted list)
	\item[4)] $\kid$ decrypts $\kid^{-1}("register\kid")$ into clear text "registerKid".
\end{itemize}

For now, we're using the MIT-licensed \href{https://github.com/zkp-application/circom-rsa-verify}{Circom RSA signature verify}, which probably doesn't work - we should check (sha256?). \\

The next line is used on a file of shape:\\
-----BEGIN PUBLIC KEY-----\\
...\\
-----END PUBLIC KEY-----\\
-----BEGIN CERTIFICATE-----\\
...\\
-----END CERTIFICATE-----\\

We assume: \\
	modulus = Subject Modulus\\
	exp = Subject Exponent\\
openssl x509 -in Identification.pem -text -noout\\

\begin{lstlisting}[language=circom]
pragma circom 2.0.0;

include "./utils/rsa_verify.circom"
include "./circomlib/circuits/sha256/sha256.circom"
include "./circomlib/bitify.circom"

//hashNumberOfWords = 4 for sha256
//rsaNumberOfWords = 32 for 2048 rsa
//we use words of 64 bits
template NinOwnsKid(
		rsaNumberOfWords, 
		hashNumberOfWords, 
		lengthInBitsOfSignedMessage,
		lengthOfNinInBits,
		bitsInAWord
){
	//TODO: What happens to uint256 when converted to signal

	//public:
	signal input hNin;
	signal input vKid;

	//private:
	signal input Nin;
	//Kid, CA signature
	signal input exp[rsaNumberOfWords];
	signal input sign[rsaNumberOfWords];
	signal input modulus[rsaNumberOfWords];

	//we need some inputs to verify what is signed
	//and that Nin in the right place in the signed message
  signal input messageToBeSigned[lengthInBitsOfSignedMessage];
	signal input Nin[lengthOfNinInBits];

	//TODO: Insert Nin into messageToBeSigned in the right place
	//or create constraint on the corresponding bits

	component sha = Sha256(lengthInBitsOfSignedMessage);
	for (int i = 0; i<lengthInBitsOfSignedMessage; i++) {
		sha.in[i] <== messageToBeSigned[i]
	}

	var hashed[hashNumberOfWords];//4x64 bit
	var hashedBits[hashNumberOfWords*bitsInAWord];
	for (int i=0; i<hashNumberOfWords*bitsInAWord;i++){
		hashedBits[i] <== sha.out[i];
	}
	component b2n = Bits2Num(64);
	//TODO:Can we use a component multiple times?
	//Will all the constraints be generated
	for (int i=0;i<hashNumberOfWords;i++){
		for (int j=0;j<bitsInAWord;j++){
			b2n.in[j] <== hashedBits[i*64+j];
		}
	  hashed[i] <== b2n.out;
	}

	//lets assume sha256WithRSAEncryption
	//verify CA signature of Kid
	component rsa = RsaVerifyPkcs1v15(bitsInAWord, rsaNumberOfWords, 17, 4);
	for (var i = 0; i < rsaNumberOfWords; i++){
		rsa.exp[i] <== exp[i];
		rsa.sign[i] <== sign[i];
		rsa.modulus[i] <== modulus[i];
	}
	for (var i = 0; i<hashNumberOfWords; i++){
		rsa.hashed[i] <== hashed[i];
	}

	//TODO: verify Kid(vKid)=="registerKid"

	//Check CA on CA approved list
	//On blockchain mapping (uint256 => bool) public CAValid
	
	//Take Kid
	//Take CA
	
}
component main { public [hNin,vKid]} = NinOwnsKid();
\end{lstlisting}
\xdef\tpd{\the\prevdepth}

\end{enumerate}

\newpage
\section{Registering $\khk$}
Register $\khk$ on \pbc{} by calling $$register\khk(HNin\kid, HNin\kid\khk, \khk, verifyProofArguments),$$
  where:
    \begin{enumerate}
      \item[] $HNin\kid=H(Nin,\kid^{-1}("register\khk"))$
      \item[] $HNin\kid\khk=H(Nin, \kid^{-1}("register\khk"), \khk^{-1}("register\khk"))$.
    \end{enumerate}
\begin{enumerate}[leftmargin=0cm]
	\item[] \underline{Pseudo-solidity code}

	\hfill\begin{minipage}{\dimexpr\textwidth-20px}
	\begin{lstlisting}[language=Solidity]
	mapping(uint => uint) public ninKidKhUsed;
	mapping(uint => bool) public isPerson;
	
	function registerKh(
		uint hNinKid,
		uint hNinKidKh,
		uint Kh,
		uint[2] memory proofPointA,
		uint[2][2] memory proofPointsB,
		uint[2] memory proofPointC
	) public {
		//Setting public arguments
		uint[] memory inputValues = new uint[](3);
		inputValues[0] = hNinKid;
		inputValues[1] = hNinKidKh;
		inputValues[2] = Kh;
	
		require(
			verifyProof(proofPointA, proofPointsB, proofPointC, inputValues)
		);
	
		ninKidKhUsed[hNinKid] = hNinKidKh;
		isPerson[Kh] = true;
	}
	\end{lstlisting}
	\xdef\tpd{\the\prevdepth}
	\end{minipage}

	\item[] Features
	\begin{itemize}
		  \item[] \textbf{Sybil resistance} \\ $\khk$ is a unique public key bound to the Person on the \pbc{}. By design, the Person cannot have two valid $\khk$ keys at the same time.
	
		  TODO: Explanation/proof.
		  \vspace{5px}
		\item[] \textbf{Anonimity} \\ No one who has a database with all public keys $\kid$ or/and public keys $\khk$ can tell, from the function call, which $Nin$, $\kid$ or $\khk$ was used. This is true under the assumption that CA, which certified the eID, does not have access to $\kid^{-1}$, i.e. that $\kid$ was securely generated on the eID.
	
		TODO: Explanation/proof.
	\end{itemize}
	
	\item[] Remarks
	\begin{itemize}
	\item[i)] Reasoning behind the choice of arguments:
	We want to connect $Nin$ with $\khk$ in a unique, but untraceable way.
	If we only used $HNin\kid\khk$ then if someone used multiple $\khk$s we wouldn't be able to prove the connection to $Nin$ (i.e. they could register a lot of $\khk$s).
	Hashing connects arguments, and makes them opaque without the knowledge of arguments (which in this case include private keys), so the arguments are opaque without the knowledge of private keys.
	\end{itemize}

\item[] \underline{Pseudo-circom code}

Statements we need to check:
\begin{itemize}
	\item[1)] $register\kid$ is still valid
	\item[2)] $HNin\kid$ is valid
	\item[3)] $HNin\kid\khk$ is valid
	\item[4)] $\khk$ is valid
	\item[5)] TODO: $\khk$ invalidation!?
\end{itemize}

\begin{lstlisting}[language=circom]
	pragma circom 2.0.0;
\end{lstlisting}

\end{enumerate}

\newpage
\section{Problems}
\begin{enumerate}[label=\textbf{P\arabic*}]
\item The rate of addition of identities, the problems of frequent changes of Merkle Tree Roots, and how long it takes to generate zkp proof, and block generation time.
\item \label{bigsteal} The Thief stole $\kid^{-1}$ before we registered on \pbc{} and then registered $\kid$ and $\khk$.
\item The Thief stole $\kid^{-1}$ after we registered on \pbc.
\item Trying to use unregistered Key.
\item Trying to register the same $Nin$ with multiple Keys (e.g. two physical ids).
\item \label{chain} Using $\khk$ without checking the whole $CA\rightarrow \kid \rightarrow \khk$ chain.
  \begin{itemize}
    \item[i)] Using $\khk$ to register as a mining key.
    \item[ii)] Invalidating $\khk$.
    \item[iii)] Using new $\khk$ as a mining key.
  \end{itemize}
  \underline{Solution}

  Look at the solution to \ref{miningKey}.

  The Mining Registry can accept new $\khk$ after an expiration period (which can be e.g. one day).
\item \label{miningKey} A combination of \ref{bigsteal} and \ref{chain}. The Thief steals $\kid$, registers $\khk$ and registers $\khk$ for mining. The problem is bigger, because we can't invalidate $\khk$ if we don't know which $\khk$ it is.

  \underline{Solution}

  We make $\khk$ renewable. We write the last block number it was renewed on to the \pbc.
  Mining Registry can choose to accept $\khk$ that is not older than some time period (for the Registry a good period would seem to be one day).
  When paying the miners, the Registry also requires proof of $\khk$.
\item Only $\khk$ is compromised.
\end{enumerate}
\end{document}