732 lines
44 KiB
TeX
732 lines
44 KiB
TeX
\documentclass[11pt]{report}
|
|
\usepackage{listings,cite,amsmath,amsfonts,amssymb,fullpage,url}
|
|
\usepackage{underscore,dsfont,vhistory}
|
|
\usepackage[bookmarks=true]{hyperref}
|
|
\usepackage{fancyvrb}
|
|
\hypersetup{
|
|
bookmarks=false, % show bookmarks bar
|
|
pdftitle={BOLT}, % title
|
|
pdfauthor={Joseph Ayo Akinyele}, % author
|
|
pdfsubject={TeX and LaTeX}, % subject of the document
|
|
pdfkeywords={TeX, LaTeX, graphics, images}, % list of keywords
|
|
colorlinks=true, % false: boxed links; true: colored links
|
|
linkcolor=blue, % color of internal links
|
|
citecolor=black, % color of links to bibliography
|
|
filecolor=black, % color of file links
|
|
urlcolor=blue, % color of external links
|
|
linktoc=page % only page is linked
|
|
}%
|
|
\def\myversion{1.0} % keep in sync with the revision history
|
|
|
|
\title{%
|
|
\vspace{-1in}
|
|
\center
|
|
%\includegraphics[scale=0.7]{yeletech-logo}
|
|
\vspace{1in}
|
|
\center
|
|
\textcolor{black}{
|
|
{\selectfont{\huge{Blind Off-Chain\\Lightweight Transactions\\(BOLT)}}}}
|
|
\center
|
|
\textcolor{black}{
|
|
{\selectfont{\huge{Version \myversion}}}}
|
|
\vspace{1in}
|
|
\\
|
|
{{\bf Authors}\\ Matthew D. Green (mgreen@cs.jhu.edu) \\ Ian Miers (imiers@cs.jhu.edu)\\J. Ayo Akinyele (ayo@boltlabs.io)}
|
|
\\
|
|
\vspace{2in}
|
|
\textcolor{black}{
|
|
{{\small{MIT License\\Copyright {\textcopyright} 2018}}}}
|
|
}
|
|
%\newpage
|
|
%\pagenumbering{arabic}
|
|
%\\
|
|
%\vspace{0.2in}
|
|
%\rule{16cm}{1pt}\vskip1cm
|
|
|
|
\date{}
|
|
\usepackage{hyperref}
|
|
\usepackage{fancyhdr}
|
|
%\pagestyle{fancy}
|
|
\fancypagestyle{myfancypage}{
|
|
\fancyhf{}
|
|
%\lhead{\large{\textbf{\textit{xxx}}}}
|
|
%\chead{\vpsace{1in}}
|
|
%\rhead{\large\textbf{\textit{xxx}}}
|
|
%\lfoot{\small{YeleTech Security, Inc}}
|
|
%\cfoot{\small\textit{xxx}}
|
|
\rfoot{\small{ \thepage{} }}
|
|
}
|
|
\renewcommand{\headrulewidth}{0.3pt}
|
|
\renewcommand{\footrulewidth}{0.4pt}
|
|
\newcommand{\company}{YeleTech Security, Inc}
|
|
\newcommand{\BC}{B^{\text{\sf cust}}_{\text{0}}}
|
|
\newcommand{\BM}{B^{\text{\sf merch}}_{\text{0}}}
|
|
|
|
\pagestyle{myfancypage}
|
|
\setlength{\headsep}{0.2in}
|
|
|
|
\input{myheader}
|
|
|
|
\begin{document}
|
|
\maketitle
|
|
\tableofcontents
|
|
\thispagestyle{myfancypage}
|
|
|
|
\newpage
|
|
\chapter*{Abstract}
|
|
\label{ch:abstract}
|
|
\thispagestyle{myfancypage}
|
|
|
|
This document describes the design and implementation of the Blind Off-chain Lightweight Transactions (BOLT) library. The BOLT protocol comprises a number of techniques for enabling privacy-preserving unlinkable payment channels for decentralized crypto-currencies between pairs of individual parties. BOLT is designed to provide a ``Layer 2'' payment protocol for privacy-preserving crypto-currencies such as Zerocash (or Zcash)~\cite{Zerocash}, by allowing individuals to establish and use payment channels for rapid or instantaneous payments that do not require an on-chain transaction. This document describes the cryptographic instantiations of the BOLT protocol according to the published paper by Matthew Green and Ian Miers~\cite{BoltCCS}.
|
|
|
|
The intended use of this document is for understanding BOLT and the associated software implementation in the Rust programming language.
|
|
This document is hereby released to the public domain free of charge.
|
|
|
|
\thispagestyle{myfancypage}
|
|
\chapter{Introduction}
|
|
\label{sec:introduction}
|
|
\thispagestyle{myfancypage}
|
|
\rhead{\small\textit{Introduction}}
|
|
|
|
BOLT is a system for conducting privacy-preserving off chain payments between pairs of individual parties. We refer to these parties as ``customers'', ``merchants'' and ``hubs'', with definitions provided below. BOLT is designed to provide a ``Layer 2'' payment protocol for privacy-preserving cryptocurrencies such as Zcash, by allowing individuals to establish and use payment channels for rapid/instantaneous payments that do not require an on-chain transaction.
|
|
|
|
\paragraph{Parties and Terminology.} Financial transactions in the BOLT system are conducted between two parties, possibly with the assistance of an intermediate third party. Each party runs the BOLT software. These parties fall into three categories, which we describe below:
|
|
\begin{itemize}
|
|
\item {\bf Customers.} Customers are users who establish payment channels and initiate payment transactions to a merchant, possibly via an intermediate party known as a ``hub''. These payments may have positive or negative value, provided there are sufficient funds in the payment channel to allow the transaction.
|
|
\item {\bf Merchants.} Merchants are users who cooperate in the establishment of payment channels (with customers and hubs), and receive payments from customers or hubs.
|
|
\item {\bf Hubs.} In some settings, customers may pay merchants directly. In other settings, a customer may pay a merchant via an intermediate party known as a ``hub''. Hubs establish channels with both customer and merchant, and relay transactions (of positive or negative value) between two such parties.
|
|
\end{itemize}
|
|
|
|
BOLT can be deployed in one of two settings, called ``Pairwise'' and ``Hub'' mode, as illustrated in Figure~\ref{fig:bolt}.
|
|
|
|
\begin{figure}
|
|
\caption{Pairwise and Hub modes for BOLT protocol}
|
|
\centering
|
|
\includegraphics[width=0.7\textwidth]{bolt-diagram}
|
|
\label{fig:bolt}
|
|
\end{figure}
|
|
|
|
Note that these diagrams represent only one set of channel(s) between the parties. In practice, every party may have many relationships with different customers, merchants, or hubs.
|
|
|
|
\noindent
|
|
{\bf Software components.} Each BOLT participant requires must run the BOLT software, which consists of up to three pieces. These are:
|
|
|
|
\begin{itemize}
|
|
\item A full node for a BOLT-compatible cryptocurrency, {\em e.g.}, zcashd. This node is connected to the currency P2P network, and must support commands via an ({\em e.g.}, RPC) interface.
|
|
\item A BOLT library ({\bf libbolt}) that constructs and parses the messages required for interactive off-chain transactions with (one or more) remote BOLT participant(s), and interfaces with the cryptocurrency node via its interface.
|
|
\end{itemize}
|
|
|
|
The actual BOLT data transfer may be implemented by an application designer, via a channel such as HTTP or some alternative data transfer mechanism. Alternatively, parties can receive inbound connections using a dedicated daemon:
|
|
|
|
\begin{itemize}
|
|
\item A dedicated daemon ({\bf boltd}) that implements BOLT communications with remote parties. This daemon uses HTTPS/JSON communications, incorporates libbolt and interfaces directly with the cryptocurrency node.
|
|
\end{itemize}
|
|
|
|
\section{BOLT Privacy Guarantees}
|
|
\label{sec:privacy}
|
|
|
|
BOLT provides a more limited set of privacy guarantees than a standard payment network. This is inherent in the fact that BOLT uses payment channels, which are pairwise relationships that must be established between a Customer and Merchant before payment can take place.
|
|
|
|
The BOLT privacy guarantees can be summarized as follows:
|
|
\begin{itemize}
|
|
\item The Merchant will be aware of the number of channels she has open at any given time, and the total funding amount of each channel. We assuming an anonymous underlying currency network, so the Merchant does not know the identity of the Customer that opens each channel (this information should be protected by the underlying currency network).
|
|
\item The Customer (who initiates transactions) always knows the identity of the Merchant she is paying, and the instantaneous balance of each of her open channels.
|
|
\item The Merchant (who responds to transactions) does not learn the identity of the Customer, or which channel a payment is associated with. She knows only that the payment is associated with one of her current active payment channels.
|
|
\item The sole exception to rule (3) is when a payment interaction fails or is disputed. In this case, the Merchant learns which channel is associated with the final (failed) payment, but cannot link this channel to any previous payments.
|
|
\end{itemize}
|
|
|
|
In practice this guarantee is sufficient to protect customer identities. Channels are not linked to customer identities (due to the anonymous payment network), and the merchant cannot link any previous payments to the failed payment or channel.
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%% BOLT Design
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
|
|
\chapter{BOLT Library}
|
|
\label{ch:bolt}
|
|
\thispagestyle{myfancypage}
|
|
\rhead{\small\textit{libbolt}}
|
|
|
|
\section{Overview}
|
|
|
|
In this section, we describe the implementation of the BOLT library for an anonymous payment channel (APC). An APC is a construct established between two parties that interact via a payment network. An APC must be used in combination with a payment network capable of {\em conditionally} escrowing funds and {\em binding} these escrow transactions funds to some data. We assume the existence of such a payment network ({\em e.g.}, Zcash) and leave the details of the payment network outside the scope of this document.
|
|
|
|
\section{Core Cryptographic Building Blocks}
|
|
\label{sec:core}
|
|
|
|
In this section, we describe the core cryptographic primitives required to implement the BOLT protocol. They include the following:
|
|
|
|
\begin{itemize}
|
|
\item Commitment Scheme
|
|
\item Digital Signatures with efficient protocols
|
|
\item Symmetric Key Encryption
|
|
\item Pseudo-random Functions
|
|
\item One-time Encryption
|
|
\item Non-Interactive Zero-Knowledge Proofs of Knowledge
|
|
%\item Interactive protocols for generating blind or partially blind signatures
|
|
\end{itemize}
|
|
|
|
%%%%%%%%%%%% Crypto Tools %%%%%%%%%%%%
|
|
|
|
\subsection{Commitment Scheme}
|
|
\label{sec:commit}
|
|
|
|
BOLT instantiates a commitment primitive using the Pedersen commitment scheme~\cite{PedersenCommits}. The scheme has the following interface:
|
|
|
|
\medskip \noindent
|
|
${\sf CSetup}() \rightarrow PP$: the algorithm generates public parameters and outputs the $PP$.
|
|
|
|
\medskip \noindent
|
|
${\sf Commit}(PP, M; r) \rightarrow C$: On input parameters $PP$, a message $M \in \G$, and optional random coins $r$, the algorithm outputs a commitment $C$.
|
|
|
|
\medskip \noindent
|
|
${\sf Decommit}(PP, C, M) = \{0, 1\}$: On input parameters $PP$, and a tuple $(C, M, r)$ outputs 1 if $C$ is a valid commitment to the message or 0 otherwise.
|
|
|
|
\subsubsection{Pedersen Commitments}
|
|
\label{sec:ped92}
|
|
|
|
We define Pedersen commitments over a vector of $n$ messages as follows:
|
|
|
|
\medskip \noindent
|
|
${\sf CSetup}() \rightarrow PP$: the algorithm generates public parameters and outputs the $PP = (g_1, g_2, ..., g_{n}, h)$.
|
|
|
|
\medskip \noindent
|
|
${\sf Commit}(PP, M; r) \rightarrow C$: On input parameters $PP$, a message tuple $M = (m_1, m_2, ... m_n)$, and optional random coins $r$, the algorithm outputs a commitment $C = {g_1}^{m_1} \cdot {g_2}^{m_2} \dots {g_n}^{m_n} \cdot h^r$ and $r$.
|
|
|
|
\medskip \noindent
|
|
${\sf Decommit}(PP, C, M) = \{0, 1\}$: On input parameters $PP$, and a tuple $(C, M, r)$. Check if $C \stackrel{?}{=} {g_1}^{m_1} \cdot {g_2}^{m_2} \dots {g_n}^{m_n} \cdot h^r$. Outputs 1 if $C$ is a valid commitment to the message or 0 otherwise.
|
|
|
|
|
|
\subsection{Symmetric-Key Encryption}
|
|
\label{sec:authenc}
|
|
|
|
BOLT includes an symmetric-key encryption (SymEnc) primitive (via XSalsa20-Poly1305) for providing confidentiality and integrity.
|
|
|
|
\medskip \noindent
|
|
${\sf Encrypt}(K, M, N) \rightarrow C$. The encryption algorithm takes as input a symmetric-key, a message $M \in \{0,1\}^\ell$ and the associated nonce $N \in \{0,1\}^k$. The algorithm outputs the ciphertext $C$.
|
|
|
|
\medskip \noindent
|
|
${\sf Decrypt}(K, C, N) = M \cup \bot$. The decryption algorithm takes as input a symmetric-key, the ciphertext $C$ and the associated nonce $N$. The algorithm outputs the message $M$ or returns $\bot$.
|
|
|
|
\subsection{Digital Signatures with Efficient Protocols} % CL sigs
|
|
\label{sec:signatures}
|
|
|
|
BOLT includes signatures due to Camenisch and Lysyanskaya (CL)~\cite{CL04} which features: (1) a protocol for a user to obtain a signature on the value(s) in a commitment without the signer learning anything about the message(s), and (2) a non-interactive protocol for proving knowledge of a signature. We will first provide the definition of a signature scheme then provide the details of the signature and the associated protocols.
|
|
|
|
\medskip \noindent
|
|
${\sf SigKeygen}(\PP) \rightarrow (\PK, \SK)$. The key generation algorithm takes as input a security parameter $\tau$, runs the ${\sf ECSetup}(1^\tau)$ to select the elliptic curve parameters and outputs the public and secret key.
|
|
|
|
\medskip \noindent
|
|
${\sf Sign}(\PP, \SK, M) \rightarrow \sigma$. The signing algorithm takes as input public parameters, a secret key $\SK$ and message $m \in \{0,1\}^*$ and outputs a signature $\sigma$.
|
|
|
|
\medskip \noindent
|
|
${\sf Verify}(\PK, M, \sigma) = \{true, false\}$. The verification algorithm takes as input a public key $\PK$, the message $m$ and the signature $\sigma$. The algorithm outputs $true$ if the signatures is valid with respect to $M$ and $\PK$. Otherwise, it outputs $false$.
|
|
|
|
\subsubsection{CL Signature~\cite{CL04}}
|
|
\label{sec:clsigs}
|
|
|
|
Run the {\sf Setup} algorithm to generate public parameters $\PP = (q, \G_1, \G_2, g_1, g_2, e)$.
|
|
|
|
\medskip \noindent
|
|
${\sf SigKeygen}(\PP) \rightarrow (\PK, \SK)$. The key generation algorithm chooses $x \leftarrow \Z_q$, $y \leftarrow \Z_q$ and for $1 \le i \le \ell$, choose $z_i \leftarrow \Z_q$. Let $X = g_1^x$, $Y = g_1^y$, for $1 \le i \le \ell$, set $Z_i = g_1^{z_i}$ and $W_i = Y^{z_i}$. Set $\SK = (x, y, {z_1, \dots, z_\ell})$ and $\PK = (X, Y, \{Z_i\}, \{W_i\})$.
|
|
|
|
\medskip \noindent
|
|
${\sf Sign}(\PP, \SK, M) \rightarrow \sigma$. On input message $M = (m^{(0)}, m^{(1)}, \dots, m^{(\ell)})$, and secret key $SK = (x, y, z_1, \dots, z_\ell)$ and public parameters $\PP = (q, \G_1, \G_2, g_1, g_2, e)$, and computes the following:
|
|
\begin{enumerate}
|
|
\item choose a random $a \in \G_2$
|
|
\item Let $A_i = a^{z_i}$ for $1 \le i \le \ell$
|
|
\item Let $b = a^y$, $B_i = (A_i)^{y}$
|
|
\item Let $c = a^{x + xym^{(0)}} \cdot \prod_{i=1}^{\ell} A_i ^ {xym^{(i)}}$
|
|
\item Output signature $\sigma = (a, \{A_i\}, b, \{B_i\}, c)$
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
${\sf Verify}(\PK, M, \sigma) = \{true, false\}$. On input $\PK = (X, Y, \{Z_i\}, \{W_i\})$, message $M = (m^{(0)}, m^{(1)}, \dots, m^{(\ell)})$ and signature $\sigma = (a, \{A_i\}, b, \{B_i\}, c)$, check the following:
|
|
\begin{enumerate}
|
|
\item $\{A_i\}$ were formed correctly: $e(Z_i, a) = e(g_1, A_i)$
|
|
\item $b$ and $\{B_i\}$ were formed correctly: $e(Y, a) = e(g_1, b)$ and $e(Y, A_i) = e(g_1, B_i)$
|
|
\item $c$ was formed correctly: $e(X, a) \cdot e(X, b)^{m^{(0)}} \cdot \prod_{i=1}^{\ell} e(X, B_i)^{m^{(i)}} = e(g_1, c)$
|
|
|
|
% $e(a, Y) = e(g, b)$ and $e(X, a) \cdot e(X, b)^m = e(g, c)$. If both conditions hold, then output $true$. Otherwise, $false$.
|
|
\end{enumerate}
|
|
|
|
% include protocol for proving knowledge of a valid signature
|
|
\subsubsection{(1) Protocol for obtaining a signature on a committed value}
|
|
\label{sec:sigoncommit}
|
|
|
|
Suppose $M = g_1 ^ {m^{(0)}} \prod_{i=1}^{\ell} {Z_i}^{m^{(i)}}$ is a commitment to a vector of messages $(m^{(0)}, m^{(1)}, \dots, m^{(\ell)})$ whose signature the user wishes to obtain. Then, the user and the signer execute the following protocol:
|
|
\begin{itemize}
|
|
\item The common input is the $\PP = (q, \G_1, \G_2, g_1, g_2, e)$, $\PK = (X, Y, \{Z_i\}, \{W_i\})$ and a commitment $M$.
|
|
\item The user's input is the messages $m^{(0)}, m^{(1)}, \dots, m^{(\ell)}$ that open to the commitment such that $M = g_1 ^ {m^{(0)}} \prod_{i=1}^{\ell} {Z_i}^{m^{(i)}}$.
|
|
\item The signer's input is the secret key $\SK = (x, y, {z_1, \dots, z_\ell})$.
|
|
\item The user and signer engage in a zero-knowledge proof of knowledge of the opening to the commitment as follows:
|
|
\begin{enumerate}
|
|
\item $PK \{ (u^{(0)}, \cdots, u^{(\ell)}): M = g_1 ^ {m^{(0)}} \prod_{i=1}^{\ell} {Z_i}^{m^{(i)}}$
|
|
\end{enumerate}
|
|
\item The signer computes $\sigma = (a, \{A_i\}, b, \{B_i\}, c)$ as follows (using $\SK$):
|
|
\begin{enumerate}
|
|
\item Choose $\alpha \leftarrow \Z_q$,
|
|
\item Set $a = g^\alpha$
|
|
\item For $1 \le i \le \ell$, let $A_i = a^{z_i}$
|
|
\item Set $b = a^y$
|
|
\item For $1 \le i \le \ell$, let $B_i = {A_i}^y$
|
|
\item Set $c = a^x M^{\alpha xy}$
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
|
|
\subsubsection{(2) Protocol for proving knowledge of a signature}
|
|
\label{sec:blindsigs}
|
|
|
|
\begin{itemize}
|
|
\item The common input is the public parameters $\PP = (q, \G_1, \G_2, g_1, g_2, e)$ and public key $\PK = (X, Y, \{Z_i\}, \{W_i\})$
|
|
\item The prover's input is the vector of messages $m^{(0)}, m^{(1)}, \dots, m^{(\ell)}$ and signature $\sigma = (a, \{A_i\}, b, \{B_i\}, c)$
|
|
\item The protocol is in three parts:
|
|
\begin{enumerate}
|
|
\item The prover computes a blinded version of the signature $\sigma$ as follows:
|
|
\begin{itemize}
|
|
\item Chose random $r, r' \in \Z_q$
|
|
\item Compute $\hat{\sigma} = (\tilde{a}, \{\tilde{A_i}\}, \tilde{b}, \{ \tilde{B_i} \}, \hat{c})$ as follows: $\tilde{a} = a^r$, $\tilde{b} = b^r$, $\hat{c} = ({c^r})^{r'}$, $\tilde{A} = {A_i}^r$ and $\tilde{B_i}= {B_i}^r$ for $1 \le i \le \ell$
|
|
\item Send $\hat{\sigma}$ to verifier
|
|
\end{itemize}
|
|
|
|
\item Both the prover and verifier compute ${\sf v}_x$, ${\sf v}_{xy}$, ${\sf v}_{\{xy,i\}}$ where $i = 1, \dots, \ell$ and ${\sf v}_s$ as follows:
|
|
\begin{enumerate}
|
|
\item Compute ${\sf v}_x = e(X, \tilde{a})$
|
|
\item Compute ${\sf v}_{xy} = e(X, \tilde{b})$
|
|
\item Compute ${\sf v}_{\{xy,i\}} = e(X, \tilde{B_i})$
|
|
\item Compute ${\sf v}_s = e(g_1, \hat{c})$
|
|
\end{enumerate}
|
|
|
|
\item The prover and verifier execute the following protocol:
|
|
\begin{enumerate}
|
|
\item Verify proof $\pi = PK\{(\mu^0, \dots, \mu^\ell, \rho) : ({{\sf v}_s})^\rho = {{\sf v}_x} {{\sf v}_{xy}}^{\mu^0} \prod_{i=1}^\ell ({\sf v}_{(xy,i)})^{\mu_i}\}$.
|
|
\item Check if $e(Z_i, \tilde{a}) \stackrel{?}{=} e(g_1, \tilde{A_i})$ and $e(Y, \tilde{a}) \stackrel{?}{=} e(g_1, \tilde{b})$ and $e(Y, \tilde{A_i}) \stackrel{?}{=} e(g_1, \tilde{B_i})$.
|
|
\end{enumerate}
|
|
|
|
\end{enumerate}
|
|
\end{itemize}
|
|
|
|
\subsection{Pseudo-random Functions (PRF)}
|
|
\label{sec:prf}
|
|
|
|
For the unidirectional construction, BOLT includes a pseudo-random function $F$ that supports efficient proofs of knowledge. $F$ is instantiated using the Dodis-Yampolskiy PRF~\cite{DY05}, the public parameters are a group $\G_1$ of prime order $q$ with generator $g$. The seed is a random value $s \in \Z_q$ and the function is computed as $F_{s}(x) = g^{1/(s+x)}$.
|
|
|
|
\subsection{One-Time Encryption}
|
|
\label{sec:ote}
|
|
|
|
For the bidirectional construction, BOLT includes a IND-CPA secure one-time encryption scheme with a keyspace that is also the range of the pseudo-random function (PRF) described in Section~\ref{sec:prf}. In addition, the message space is the domain of the public key for the CL signature scheme instantiated in Section~\ref{sec:signatures}.
|
|
|
|
\medskip \noindent
|
|
${\sf OTKeyGen}(\tau) \rightarrow K$. On input parameters, the algorithm outputs a random key, $K \in \G_1$.
|
|
|
|
\medskip \noindent
|
|
${\sf OTEnc}(K, M) \rightarrow C$. The algorithm takes as input a one-time key $K$ and a message tuple $(M_1, M_2) \in \G_1$ and outputs a ciphertext $C$.
|
|
|
|
\medskip \noindent
|
|
${\sf OTDec}(K, C) = M$ or $\bot$. The algorithm takes as input a key $K$ and the ciphertext $C$ and outputs the message tuple as $M$ or $\bot$.
|
|
|
|
\subsection{Non-Interactive Zero Knowledge Proofs (NIZKP)}
|
|
\label{sec:nizkp}
|
|
|
|
BOLT features non-interactive zero-knowledge proofs of knowledge for the purposes of proving statements about committed values:
|
|
\begin{enumerate}
|
|
\item a proof of knowledge of a committed value
|
|
\item a proof that a committed value is in a range
|
|
\end{enumerate}
|
|
%%%%%%%%%%%% Crypto Tools %%%%%%%%%%%%
|
|
|
|
%\subsection{Proving Knowledge of a Signature for a Single Message~\cite{CL04}}
|
|
%\label{sec:blindsigs}
|
|
%
|
|
%\noindent
|
|
%{\bf How to compute a blind signature.} Given public key $pk = (q, G, {\sf G}, g, {\sf g}, e, X, Y)$. Prover takes as input the message $m \in \Z_q$ and CL signature (see Section~\ref{sec:clsigs}) $\sigma = (a, b, c)$.
|
|
%Prover does the following to compute a blinded version of signature $\sigma \leftarrow (a, b, c)$ from CL signature.
|
|
%\begin{enumerate}
|
|
%\item Chose random $r, r' \in \Z_q$.
|
|
%\item Compute $\tilde{\sigma} := (a^{r'}, b^{r'}, c^{r' r}) = (\tilde{a}, \tilde{b}, \tilde{c}^r) = (\tilde{a}, \tilde{b}, \hat{c})$.
|
|
%\item Send $(\tilde{a}, \tilde{b}, \hat{c})$ to the verifier.
|
|
%\end{enumerate}
|
|
%
|
|
%\noindent
|
|
%{\bf How to prove knowledge of a signature.} Given $\tilde{\sigma} = (\tilde{a}, \tilde{b}, \hat{c})$, both prover and verifier compute the following values locally:
|
|
%\begin{enumerate}
|
|
%\item Compute ${\sf v}_x = e(X, \tilde{a})$
|
|
%\item Compute ${\sf v}_{xy} = e(X, \tilde{b})$
|
|
%\item Compute ${\sf v}_s = e(g, \hat{c})$
|
|
%\end{enumerate}
|
|
%
|
|
%\noindent
|
|
%The prover and verifier execute the following zero-knowledge proof protocol:
|
|
%\begin{enumerate}
|
|
%\item Verify proof $\pi = PK\{(u, p) : ({{\sf v}_s}^p = {{\sf v}_x} {{\sf v}_{xy}}^u)\}$.
|
|
%\item Check if $e(\tilde{a}, Y) = e(g, \tilde{b})$ holds.
|
|
%\end{enumerate}
|
|
|
|
|
|
\section{Constructions}
|
|
\label{sec:constructs}
|
|
|
|
\subsection{Unidirectional Scheme}
|
|
\label{sec:unidirectional}
|
|
|
|
The unidirectional payment construction only supports payments from a customer to a merchant and only supports transfer of fixed-value coins. It consists of a tuple of possibly probabilistic algorithms ({\sf Setup}, {\sf KeyGen}, ${\sf Init}_{\sf C}, {\sf Init}_{\sf M}$, {\sf Refund}, {\sf Refute}, {\sf Resolve}) and two interactive protocols ({\sf Establish}, {\sf Pay}).
|
|
|
|
\begin{enumerate}
|
|
|
|
% Setup description
|
|
\item ${\sf Setup}(1^\lambda) \rightarrow {\sf PP}$. On input $\lambda$, optionally generate CRS parameters for (1) a secure commitment scheme (see Section~\ref{sec:commit}), (2) a non-interactive zero knowledge proof system (see Section~\ref{sec:nizkp}). Output all of these as ${\sf PP}$.
|
|
|
|
% Key generation description
|
|
\item ${\sf KeyGen}({\sf PP}) \rightarrow (pk, sk)$.
|
|
\begin{itemize}
|
|
\item Compute $(pk, sk) \leftarrow \prod_{\sf sig}.{\sf SigKeygen}(1^\lambda)$. %Note that $pk$ can be derived from the $sk$.
|
|
\end{itemize}
|
|
|
|
\medskip \noindent
|
|
\item ${\sf Init_{C}}({\sf PP}, \BC, \BM, pk_c, sk_c) \rightarrow ({\sf T}_c, csk_c)$. On input a keypair $(pk_c, sk_c)$, perform the following:
|
|
|
|
\begin{itemize}
|
|
\item Uniformly sample two distinct PRF seeds $k_1, k_2$ and random coins $r$ for the commitment scheme.
|
|
\item Compute ${\sf wCom} = {\sf Commit}(sk_c, k_1, k_2, \BC; r)$
|
|
\item For $i = 1$ to $\BC$, sample $ck_i \rightarrow {\sf SymKeyGen}(1^\lambda)$ to form the vector $\vec{ck}$.
|
|
\item Output ${\sf T}_c = ({\sf wCom}, pk_c)$ and $csk_c = (sk_c, k_1, k_2, r, \BC, \vec{ck})$.
|
|
\end{itemize}
|
|
|
|
% Init algorithm description
|
|
\item ${\sf Init_{M}}({\sf PP}, \BC, \BM, pk_m, sk_m) \rightarrow {\sf T}_m, csk_m$. On input a keypair $(pk_m, sk_m)$, perform the following:
|
|
|
|
\begin{itemize}
|
|
\item Output ${\sf T}_m = pk_m$ and $csk_m = (sk_m, \BM)$.
|
|
\end{itemize}
|
|
|
|
% Establish protocol description
|
|
\item ${\sf Establish}( C\{{\sf PP}, {\sf T}_m, csk_c)\}, \{M({\sf PP}, {\sf T}_c, csk_{m})\})$. On input public parameters and each of the initial
|
|
channel tokens, the {\sf Establish} protocol activates a channel between customer and merchant who have previously
|
|
escrowed funds. If the interaction succeeds, the merchant receives {\sf established} message and the customer
|
|
receives a wallet $w$. Either party may receive an error denoted by $\bot$.
|
|
|
|
\medskip \noindent
|
|
The customer executes the following algorithm:
|
|
\begin{itemize}
|
|
\item Parse $csk_c$ as $(pk_c, sk_c, k_1, k_2, r, \BC)$.
|
|
\item Sample $sk_0 \in \{0,1\}^\ell$.
|
|
\item Generate $\pi_1 = PK\{ (sk_c, k_1, k_2, r) : {\sf wCom} = {\sf Commit}(sk_c, k_1, k_2; r) \wedge (pk_c, sk_c) \in {\sf KeyGen}(1^\lambda)\}$
|
|
% breakdown Proof of knowledge statement
|
|
\begin{itemize}
|
|
\item {\sf NIZK} statement: ${\sf wCom} = {g_1}^{x_c} \cdot {g_2}^{y_c} \cdot {g_3}^{k_1} \cdot {g_4}^{k_2} \cdot h^r \wedge X_c = {g_1}^{x_c} \wedge Y_c = {g_2}^{y_c}$ where $sk_c = (x_c, y_c)$.
|
|
\end{itemize}
|
|
\item For $j = 1$ to $B$:
|
|
\begin{enumerate}
|
|
\item Compute $s_j \leftarrow F_{k_1}(j), u_j \leftarrow F_{k_2}(j)$.
|
|
\item $\pi_{j}^r = PK\{ (sk_c, k_1, k_2, r) : s_j \leftarrow F_{k_1}(j) \wedge u_j \leftarrow F_{k_2}(j) \\ \wedge {\sf wCom} = {\sf Commit}(sk_c, k_1, k_2; r) \\ \wedge (pk_c, sk_c) \in {\sf KeyGen}(1^\lambda)\}$
|
|
\item Compute internal signature $\hat{\sigma_j} = {\sf Sign}(sk_c, {\sf spend}||j||s_j||u_j||\pi_{j}^r||ck_{j+1})$.
|
|
\item Compute $C_j = {\sf SymEnc}(ck_j, j||s_j||u_j||\pi_{j}^r||\hat{\sigma_j}||ck_{j+1})$
|
|
\item Compute external signature $\sigma_j = {\sf Sign}(sk_c, {\sf coin}||j||C_j)$.
|
|
\end{enumerate}
|
|
\item Customer sends ${\sf wCom}, \pi, (C_1, \sigma_1,\dots,C_B,\sigma_B)$ to the merchant.
|
|
\end{itemize}
|
|
|
|
\noindent
|
|
The merchant executes the following algorithm in response:
|
|
\begin{enumerate}
|
|
\item Verify the signature on ${\sf T}_c$
|
|
\item Check that $\BC = B$
|
|
\item Verify $\pi_1$
|
|
\item For $j = 1$ to $B$, verify the signature $\sigma_j$ on $C_j$
|
|
\item If any of the above conditions (1-4) do not hold, abort and output $\bot$
|
|
\item Return a blind signature $\sigma_w$ on the contents of {\sf wCom}
|
|
\end{enumerate}
|
|
|
|
\noindent
|
|
The merchant sets state to {\sf established} and the customer obtains $w = (sk_0, sk_c, k_1, k_2, r, B, \sigma_w, 1)$.
|
|
|
|
% Pay protocol description
|
|
\item ${\sf Pay}( C\{{\sf PP}, \epsilon, w_{\sf old})\}, \{M({\sf PP}, \epsilon, {\bf S}_{\sf old})\})$. On input parameters, a payment amount $\epsilon$, and a wallet $w_{\sf old}$ from a customer, and the merchant's current state ${\bf S}_{\sf old}$ (initially set to $0$) from the merchant: the customer receives a payment success bit $R_{\sf C}$ and the new wallet $w_{\sf new}$ on success. The merchant receives a payment success bit $R_{\sf M}$ and an updated ${\bf S}_{\sf new}$ on success.
|
|
|
|
\medskip \noindent
|
|
The customer executes the following algorithm:
|
|
\begin{itemize}
|
|
\item Parse $w_{\sf old}$ as $(sk_0, sk_c, k_1, k_2, r, B, \sigma_w, i)$. Return $\bot$ if $i \geq B$.
|
|
\item Compute $s \leftarrow F_{k_1}(i)$
|
|
\item Compute $t \rightarrow {\sf OTEnc}(F_{k_2}(i), pk_c)$
|
|
\item Compute $\pi = PK\{ (pk_c, sk_c, k_1, k_2, r, i, \sigma_w): s = F_{k_1}(i) \wedge 0 < i \leq B\\ \wedge t = {\sf OTEnc}(F_{k_2}(i), pk_c) \\ \wedge {\sf Verify}(pk_m, (k_1, k_2, sk_c), \sigma_w) \\ \wedge (pk_c, sk_c) \in {\sf KeyGen}(1^\lambda) \}$
|
|
%\todo{Expand}
|
|
|
|
\item Return $(s, t, \pi)$
|
|
\end{itemize}
|
|
|
|
\medskip \noindent
|
|
The merchant executes the following:
|
|
\begin{itemize}
|
|
\item Verify $\pi$ and $(s,\cdot, \cdot) \notin {\bf S}$.
|
|
\item If this holds, then set ${\bf S} \leftarrow {\bf S} \cup (s, t, \pi)$ and $R_{M} \leftarrow 1$.
|
|
\item Otherwise, set $R_{M} \leftarrow \bot$.
|
|
\end{itemize}
|
|
|
|
\medskip \noindent
|
|
The customer obtains a new wallet $w_{new} := (sk_0, sk_c, k_1, k_2, r, B, \sigma_w, i+1)$.
|
|
|
|
% Refund algorithm description
|
|
\item ${\sf Refund}({\sf PP}, {\sf T}_{M} csk_c, \sigma)$. On input wallet $w$, output a customer channel closure message $rc_c$. This algorithm is executed by the customer.
|
|
\begin{itemize}
|
|
\item Parse $w$ to obtain $\vec{ck}$ and the current coin index $i$.
|
|
\item Compute $\sigma \leftarrow {\sf Sign}(sk_c, {\sf refund}||{\sf cID}||i||ck_i)$.
|
|
\\ {\bf NOTE}: {\sf cID} uniquely identifies the channel being closed
|
|
\item Output ${\sf rc}_{C} := ({\sf cID}, i, ck_i, \sigma)$.
|
|
\end{itemize}
|
|
|
|
% Refute algorithm description
|
|
\item ${\sf Refute}({\sf PP}, {\sf T}_{C}, {\bf S}, {\sf rc}_{C})$. On input the merchant's current state ${\bf S}_{\sf old}$ and a customer channel closure message, output a merchant channel closure message ${\sf rc}_{M}$ and an updated merchant state ${\bf S}_{new}$. This algorithm is executed by the merchant.
|
|
|
|
\begin{enumerate}
|
|
\item Parse the customer's channel closure message ${\sf rc}_{C}$ as $({\sf cID}, i, ck_i, \sigma)$.
|
|
\item Verify ${\sf cID}$ and the signature $\sigma$.
|
|
\item If signature is valid, obtain the ciphertexts $C_i, \dots, C_{B}$ (from the {\sf Establish} protocol)
|
|
\item For $j = i$ to $B$, compute $(j||s_j||u_j || \pi_{j}^r || ck_j || \hat{\sigma_j}) \leftarrow {\sf SymDec}(ck_j, C_j)$ and verify the signature $\hat{\sigma_j}$ and proof ${\pi_j^r}$.
|
|
\item Failure conditions: (1) fail to verify $\hat{\sigma_j}$ and proof ${\pi_j^r}$, or (2) decryption of any ciphertext $C_j$ results in $\bot$, or (3) decrypted values $(s_j, u_j) \in {\bf S}$ where ${\sf OTDec}(u_j, t_j) = pk_c$.
|
|
\item If failure, then record invalid result ${\sf rc}_{M} = ({\sf fail}, {\sf cID})$
|
|
\item If success, then record valid result ${\sf rc}_{M} = ({\sf accept})$
|
|
\item Sign result using $sk_m$ (verified by payment network)
|
|
\item For each valid $C_j$, set ${\bf S} \leftarrow {\bf S} \cup (s_j, t_b, \pi)$
|
|
\item Output {\bf S} as new merchant state
|
|
\end{enumerate}
|
|
|
|
% Resolve algorithm description
|
|
\item ${\sf Resolve}({\sf PP}, {\sf T}_{C}, {\sf T}_{M}, {\sf rc}_{C}, {\sf rc}_{M})$. On input the customer and merchant channel tokens ${\sf T}_{C}$ and ${\sf T}_{M}$, along with closure messages ${\sf rc}_{C}, {\sf rc}_{M}$ (where either message may be {\sf null}), this algorithm outputs the final channel balance ${B_{\sf final}^{\sf merch}}$, ${B_{\sf final}^{\sf cust}}$.
|
|
\begin{enumerate}
|
|
\item Parse the customer and merchant closure messages and verify all signatures
|
|
\item If there are any invalid signatures, grant the balance of the channel to the opposing party.
|
|
\item If ${\sf rc}_{C} = (N, sk_{N}, \sigma)$ and ${\sf rc}_{M} = {\sf accept}$, then set ${B_{\sf final}^{\sf cust}} = ({B_{0}^{\sf cust}} - N) + 1$.
|
|
\item Evaluate the merchant closure message to determine whether the customer misbehaved. %\todo{expand on this, if possible}
|
|
\item If so, assign the merchant the full balance of the channel.
|
|
\end{enumerate}
|
|
|
|
\end{enumerate}
|
|
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%%%%%%%%%% BIDIRECTIONAL SCHEME DESCRIPTION HERE %%%%%%%%%%
|
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
\subsection{Bidirectional Scheme}
|
|
|
|
The bidirectional payment construction enables compact closure and compact wallets in addition to a single run of the {\sf Pay} protocol to transfer arbitrary values (constrained by a maximum payment amount). It consists of a tuple of possibly probabilistic algorithms ({\sf Setup}, {\sf KeyGen}, ${\sf Init}_{\sf C}, {\sf Init}_{\sf M}$, {\sf Refund}, {\sf Refute}, {\sf Resolve}) and two interactive protocols ({\sf Establish}, {\sf Pay}).
|
|
|
|
\begin{enumerate}
|
|
|
|
% Setup description
|
|
\item ${\sf Setup}(1^\lambda) \rightarrow {\sf PP}$. On input $\lambda$, optionally generate CRS parameters for (1) a secure commitment scheme (see Section~\ref{sec:commit}), (2) a non-interactive zero knowledge proof system (see Section~\ref{sec:nizkp}). Output all of these as ${\sf PP}$.
|
|
|
|
% Key generation description
|
|
\item ${\sf KeyGen}({\sf PP}) \rightarrow (pk, sk)$.
|
|
%\begin{itemize}
|
|
%\item
|
|
Compute $(pk, sk) \leftarrow \prod_{\sf sig}.{\sf SigKeygen}(1^\lambda)$. %Note that $pk$ can be derived from the $sk$.
|
|
%\end{itemize}
|
|
|
|
% Init algorithm for customer
|
|
\medskip \noindent
|
|
\item ${\sf Init_{C}}({\sf PP}, {\sf cID}, \BC, \BM, pk_c, sk_c) \rightarrow ({\sf T}_{\sf c}, csk_{\sf c})$. On input a keypair $(pk_c, sk_c)$, perform the following:
|
|
|
|
\begin{enumerate}
|
|
\item Customer generates wallet commitment by sampling random coins $r$.
|
|
\item Compute ephemeral keypair $(wpk, wsk) \leftarrow {\sf KeyGen}({\sf PP})$.
|
|
\item Compute ${\sf wCom} = {\sf Commit}({\sf cID}, wpk, \BC; r)$.
|
|
\item Output ${\sf T}_{\sf c} = (pk_c, {\sf wCom})$ and retains secret $csk_{\sf c} = (sk_c, {\sf cID}, wpk, wsk, r, \BC)$.
|
|
\end{enumerate}
|
|
|
|
% Init algorithm description for merchant
|
|
\item ${\sf Init_{M}}({\sf PP}, \BC, \BM, pk_m, sk_m) \rightarrow {\sf T}_m, csk_m$. On input a keypair $(pk_m, sk_m)$, perform the following:
|
|
|
|
\begin{itemize}
|
|
\item Output ${\sf T}_{\sf m} = pk_m$ and $csk_{\sf m} = (sk_m, \BM)$.
|
|
\end{itemize}
|
|
|
|
% Establish protocol description
|
|
\item ${\sf Establish}( C\{{\sf PP}, {\sf T}_m, csk_c)\}, \{M({\sf PP}, {\sf T}_c, csk_{m})\})$. On input public parameters and each of the initial
|
|
channel tokens, the {\sf Establish} protocol activates a channel between the two parties who have previously
|
|
escrowed funds. If the interaction succeeds, the merchant receives {\sf established} message and the customer
|
|
receives a wallet $w$. Either party may receive an error denoted by $\bot$.
|
|
|
|
\medskip \noindent
|
|
The customer does the following:
|
|
\begin{enumerate}
|
|
\item Parse $csk_c$ to obtain $({\sf cID}, {\sf wCom}, wpk, wsk, r, \BC)$
|
|
\item Generate a proof $\pi_1$ of the following statement: \\
|
|
$\pi_1 = PK\{ (wpk, wsk, r) : {\sf wCom} = {\sf Commit}({\sf cID}, wpk, \BC; r) \wedge (wpk, wsk) \in {\sf KeyGen}(1^\lambda)\}$
|
|
%\todo{Expand}
|
|
\item Send proof $\pi_1$ to the merchant.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
The merchant does the following:
|
|
\begin{enumerate}
|
|
\item Parse ${\sf T}_{C}$ to obtain $\BC, {\sf wCom}$.
|
|
\item Verify proof $\pi_1$ is valid. If not, output $\bot$
|
|
\item Execute interactive protocol to compute {\bf a blind signature} $\sigma_w$ under $sk_m$ on contents of ${\sf wCom}$.
|
|
\item Customer obtains $\sigma_w$.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
The customer obtains a wallet $w := (\BC, wpk, wsk, r, \sigma_w)$ and the merchant sets its state to {\sf established} for the channel.
|
|
|
|
|
|
% Pay protocol description
|
|
\item ${\sf Pay}( C\{{\sf PP}, \epsilon, w_{\sf old})\}, \{M({\sf PP}, \epsilon, {\bf S}_{\sf old})\})$. On input parameters, a payment amount $\epsilon$, and a wallet $w_{\sf old}$ from a customer, and the merchant's current state ${\bf S}_{\sf old}$ (initially set to $0$) from the merchant: the customer receives a payment success bit $R_{\sf C}$ and the new wallet $w_{\sf new}$ on success. The merchant receives a payment success bit $R_{\sf M}$ and an updated ${\bf S}_{\sf new}$ on success.
|
|
|
|
\medskip \noindent
|
|
In the first phase, the customer does the following:
|
|
\begin{enumerate}
|
|
\item Parse $w_{old}$ as $({\sf cID}, B, wpk, wsk, r, \sigma_w)$.
|
|
\item Sample $(wpk', wsk') \leftarrow {\sf KeyGen}(\PP)$.
|
|
\item Sample random coins $r'$.
|
|
\item Generate ${\sf wCom'} \leftarrow {\sf Commit}({\sf cID}, wpk', B - \epsilon; r')$
|
|
\item Generate proof $\pi_2$ as follows:
|
|
\\ $\pi_2 = PK\{ (wpk', B, r', \sigma_w) : {\sf wCom'} = {\sf Commit}({\sf cID}, wpk', B - \epsilon; r')
|
|
\\ \wedge {\sf Verify}(pk_m, (wpk, B), \sigma_w) = 1
|
|
\\ \wedge 0 \leq (B - \epsilon) \leq {\sf val}_{\sf max} \}$
|
|
|
|
\begin{itemize}
|
|
\item Compute $C_1 = g^B \cdot h^{r_1}$
|
|
\item Compute $C_2 = C_1 / g^\epsilon$
|
|
\item Compute $C_3 = g_1^{x_1} \cdot g_2^{x_2} \cdot h^{r_3}$
|
|
\item Compute ${\sf wCom''} = C_2 \cdot C_3$. Keep ${\sf wCom'}$ private.
|
|
%\item Prove commitment ${\sf wCom'}$ in zero knowledge (via {\sf NIZK}).
|
|
%\item Prove knowledge of valid signature $\sigma_w$ on $(x_1, x_2, B)$ in $C_1 \cdot C_3$.
|
|
%\item Prove that $i$ is in the range $0 < i \leq B$.
|
|
\end{itemize}
|
|
\item Send $(\epsilon, {\sf wCom'}, wpk, \pi_2)$ to the merchant.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
In response, the merchant does the following for the first phase:
|
|
\begin{enumerate}
|
|
\item Verify $\pi_2$, ensure that $(wpk, \cdot) \notin {\bf S}$ and $\epsilon_{\sf min} \leq \epsilon \leq \epsilon_{\sf max}$
|
|
\item If these conditions do not hold, abort and output $\bot$
|
|
\item Set ${\bf S}_{\sf new} := {\bf S}_{\sf old} \cup \{(wpk, \bot)\}$.
|
|
\item If $\epsilon < 0$, then $R_{M} \leftarrow 1$ otherwise $R_{M} \leftarrow \bot$.
|
|
\item Execute interactive protocol to generate a {\bf partially blind signature} $rt_{w'}$ under $sk_m$ on the message $({\sf refund}||wpk'||B - \epsilon)$.
|
|
\\ {\bf NOTE}: $wpk'$ and $B - \epsilon$ are the contents of ${\sf wCom'}$.
|
|
%\\ \todo{Expand}
|
|
\item The customer obtains $rt_{w'}$ at the end of this phase.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
In the second phase, the customer does the following:
|
|
\begin{enumerate}
|
|
\item Check that ${\sf Verify}(pk_m, ({\sf refund}||wpk'||B - \epsilon), rt_{w'}) = 1$
|
|
\item If verification failure or message does not arrive, abort and output $rt_{w'}$.
|
|
\item Otherwise, compute $\sigma_{rev} = {\sf Sign}(wsk, {\sf revoke}||wpk)$.
|
|
\item Send $\sigma_{rev}$ to the merchant.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
In the second phase, the merchant does the following:
|
|
\begin{enumerate}
|
|
\item Ensure ${\sf Verify}(wpk, ({\sf revoke}||wpk), \sigma_{rev}) = 1$.
|
|
\item If so, set ${\bf S}_{\sf new} := {\bf S}_{\sf old} \cup \{(wpk, \sigma_{rev}\}$ and $R_{M} \leftarrow 1$.
|
|
\item Execute interactive protocol to generate a {\bf blind signature} $\sigma_{w'}$ on the contents of ${\sf wCom'}$ using $sk_m$.
|
|
\item If this completes, set $R_{M} \leftarrow 2$.
|
|
\item Send $\sigma_{w'}$ back to the customer.
|
|
\end{enumerate}
|
|
|
|
\medskip \noindent
|
|
The customer obtains a new wallet $w_{\sf new} := (B - \epsilon, wpk', wsk', r', \sigma_{w'})$ and the merchant keeps ${\bf S}_{\sf new}, R_{M}$.
|
|
|
|
|
|
% Refund algorithm description
|
|
\item ${\sf Refund}({\sf PP}, {\sf T}_{M}, csk_{C}, w) \rightarrow (m, \sigma)$.
|
|
\begin{enumerate}
|
|
\item If the customer has not invoked the {\sf Pay} protocol, then $m := ({\sf refundUnsigned}, (wpk, B), r)$.
|
|
\item Otherwise, set $m := ({\sf refundToken}, (wpk, B), rt_w)$.
|
|
\item Compute $\sigma = {\sf Sign}(sk_c, m)$.
|
|
\item Output ${\sf rc}_{C} = (m, \sigma)$.
|
|
\end{enumerate}
|
|
|
|
% Refute algorithm description
|
|
\item ${\sf Refute}({\sf PP}, {\sf T}_{C}, {\bf S}, {\sf rc}_{C})$.
|
|
\begin{enumerate}
|
|
\item If a merchant sees a channel closure message, it first parses ${\sf T}_{C}$ to obtain $pk_c$.
|
|
\item Parse tuple $(m, \sigma) \leftarrow {\sf rc}_{C}$
|
|
\item ${\sf Verify}(pk_c, m, \sigma) = 1$ or $\bot$
|
|
\item If signature $\sigma$ verifies, then parse tuple $({\sf cID}, wpk, B) \leftarrow m$.
|
|
\item Verify that {\sf cID} matches the channel.
|
|
\item If previous record of $(wpk, \sigma_{rev}) \in {\bf S}$, then output ${\sf rc}_{M} = (({\sf revoked}, \sigma_{rev}), \sigma)$.
|
|
\\ {\bf NOTE}: $\sigma$ is a valid signature over $({\sf revoked}, \sigma_{rev})$
|
|
\item Otherwise, add new key ${\bf S} = {\bf S} \cup wpk$.
|
|
\end{enumerate}
|
|
|
|
% Resolve algorithm description
|
|
\item ${\sf Resolve}({\sf PP}, {\sf T}_{C}, {\sf T}_{M}, {\sf rc}_{C}, {\sf rc}_{M})$.
|
|
\begin{enumerate}
|
|
|
|
\item Verify that both tokens ${\sf rc}_{C}, {\sf rc}_{M}$ are signed by the customer and merchant keys $pk_c$ and $pk_{m}$ respectively.
|
|
\item Verify that both tokens contain the same channel identifier ${\sf cID}$ and matches the one from ${\sf T}_{C}$ and ${\sf T}_{M}$.
|
|
\item If either of the tokens fail this test, then replace with $\bot$. Let $B_{\sf total} = \BC + \BM$.
|
|
\item If ${\sf rc}_{C}$ is $\bot$, output all the funds to the merchant.
|
|
\item Parse $(pk_c, {\sf wCom}) = {\sf T}_{C}$.
|
|
\item $m$ should have the following structure $({\sf type}, ({\sf cID}, wpk, B), {\sf Token})$
|
|
\item Parse $({\sf revoked}, wpk, \sigma_{rev}) = m$
|
|
\item Ensure that ${\sf Verify}(wpk, ({\sf revoked}||{\sf cID}||wpk), \sigma) = 1$.
|
|
\item If verification check fails, then output ${B_{\sf final}^{\sf cust}} = B_{\sf total}$ and ${B_{\sf final}^{\sf merch}} = 0$.
|
|
\item Check the refund validity:
|
|
\begin{enumerate}
|
|
\item[a.] If ${\sf type} = {\sf refundUnsigned}$, check ${\sf wCom} = {\sf Commit}(wpk, B; {\sf Token})$ and that merchant's token contains $\sigma_{rev}$.
|
|
\item[b.] If ${\sf type} = {\sf refundToken}$, check ${\sf Token}$ is a valid refund token on $(wpk, B)$.
|
|
\item[c.] If either {\bf (a)} or {\bf (b)} fails, abort and output ${B_{\sf final}^{\sf cust}} = 0$ and ${B_{\sf final}^{\sf merch}} = B_{\sf total}$.
|
|
\end{enumerate}
|
|
\item Check the refutation's validity by checking that ${\sf Verify}(wpk, {\sf revoke}||wpk, \sigma_{rev}) = 1$.
|
|
\begin{enumerate}
|
|
\item[a.] If valid, abort and output ${B_{\sf final}^{\sf cust}} = 0$ and ${B_{\sf final}^{\sf merch}} = B_{\sf total}$.
|
|
\item[b.] If invalid, pay the claimed balance to the customer (${B_{\sf final}^{\sf cust}} = B$) and the remainder to Merchant (${B_{\sf final}^{\sf merch}} = B_{\sf total} - B$).
|
|
\end{enumerate}
|
|
|
|
\end{enumerate}
|
|
|
|
|
|
\end{enumerate}
|
|
|
|
\chapter{BOLT Usage}
|
|
\label{ch:usage}
|
|
|
|
\section{Overview}
|
|
|
|
BOLT is a payment channel protocol. In order to use BOLT, a Customer and Merchant must establish and fund a payment channel on the network of a compatible cryptocurrency. Customer and Merchant represent defined roles in the BOLT system.
|
|
|
|
\paragraph{Pairwise channels.} A standard pairwise BOLT interaction consists of five phases. At a high level they are as follows:
|
|
|
|
\begin{enumerate}
|
|
\item {\bf Channel negotiation.} To initiate an interaction, Customer and Merchant agree on the initial balances of the channel, which we denote by A (customer initial balance) and B (merchant initial balance) respectively. The Merchant provides a public key and signed channel opening transaction to the Customer.
|
|
|
|
%{\bf Note}: this may or may not be a formal BOLT protocol step, and can be done in various ways. One approach is to have both parties sign a transaction for the underlying currency network. The other is to have both parties do separate transactions on the currency network. We need to figure this out BUT it will be currency specific, so it is the hardest part.
|
|
|
|
\item {\bf Channel funding.} Customer transmits the channel opening transaction to the currency network, which causes the Customer and Merchant to fund the channel with ({\bf A}, {\bf B}) units of currency respectively. This funding is conducted {\em on-chain}, and should be conducted using a privacy-preserving currency like Zcash so as to protect the customer's identity.
|
|
|
|
\item {\bf Channel activation.} Once the channel has been funded and the transaction confirmed on the network, the parties now interact directly to activate the channel and prepare it for online payments.
|
|
|
|
\item {\bf Payment.} This step may occur many times. To initiate a payment, the customer initiates an off-chain payment of {\bf D} units of currency (of positive or negative value) to the merchant. This payment maintains the total channel balance, but updates the Customer and Merchant's ownership of the balances. The merchant does not learn which Customer or Channel was involved in the payment. This produces updated state at each party.
|
|
|
|
\item {\bf Channel closure.} At the conclusion of a channel interaction, the customer or merchant may initiate the closure of the channel. If the parties dispute the balance of the channel, each party transmits a ``closure token'' to the currency network. The payment network must include logic to evaluate the tokens to determine the correct balances {\bf (A, B)} to pay out to the Customer and Merchant respectively. The parties may now withdraw their shares of the resulting channel.
|
|
|
|
\end{enumerate}
|
|
|
|
A key design consideration of BOLT is that no party should ever be at risk of losing their funds because the other party has become unresponsive or has submitted invalid information. At each of the above steps, either party may abort and close the channel using the most recent balance information. The cryptocurrency network must enforce a {\em time-delay before releasing funds}, in order to ensure that both parties have the opportunity to dispute closure.
|
|
|
|
We include a discussion of the precise requirements for the cryptocurrency network further below.
|
|
|
|
\paragraph{Hub channels.} BOLT also supports a ``Hub'' mode in which a Customer and Merchant interact via a payment hub. The use of a payment hub significantly increases the flexibility of BOLT, by enabling a hub and spoke model without the need for direct payment channel relationships between each individual Customer and Merchant. More significantly, the Hub does not learn the identity of the Customer or Merchant, nor does it see the payment amount.
|
|
|
|
The use of a Hub between a given Customer and Merchant requires the creation of two separate channels, one Customer $\longleftrightarrow$ Hub (``CH'') channel, and one Hub $\longleftrightarrow$ Merchant (``HM'') channel. The steps in opening and closing each channel are similar to steps (1), (2), (3) and (5) in the description above. However, the payment step (4) differs as follows:
|
|
|
|
\begin{itemize}
|
|
\item {\bf (Hub-based) Payment.} The Customer initiates an off-chain payment of D units of currency (of positive or negative value) to the Merchant, via the Hub. This payment atomically updates the CH and HM channels such that the Hub's balance on the CH channel is increased by D units, and the Merchant's balance on the HM channel is increased by D units. If either channel update fails, the entire transaction fails and both channels fall back to the previous channel balances.
|
|
\end{itemize}
|
|
|
|
The Hub learns only that a transaction took place, but not the amount or the identities of the Customer or Merchant.
|
|
|
|
% add bibliography
|
|
\bibliographystyle{plain}
|
|
{\normalsize
|
|
\bibliography{bib}
|
|
}
|
|
\rhead{}
|
|
|
|
\end{document}
|