SV21

[SV21 ISIT]Private Data Access in Blockchain Systems Employing Coded Sharding

面向编码分片的区块链（PolyShard），数据采用RS码编码后保存，采用PIR保护余额查询

Introduction

区块链的共识主要包含两方面：

• 谁拥有出块的权利
• 谁对链的视图将被所有人认可

在比特币中分别为PoW和最长链原则

区块链系统的三个性能指标：

• security threshold：区块链系统能容忍的恶意节点数量，取决于共识算法
• 吞吐量：每个时间单元的交易量，区块大小固定时，可以根据验证通过的区块数量衡量
• 存储效率：每个节点存储完整区块链数据的比例

比特币和以太坊采用完整复制的思想，导致存储效率为最低值1

水平扩展（horizontal scaling）：随着网络规模线性地增加吞吐量、降低存储效率

编码分片（coded sharding）被认为是解决不可能三角的方案之一

区块链的分片是指将将网络划分为小的子网，每个子网掌握不相交的交易集合和不相交的账户

编码的分片中，区块链是一个编码的块形成的链，是对跨分片的块进行编码得到的

Privacy in Blockchain

假名（pseudonym）：公钥

钱包：与发送方和接收方相关联的一对假名

交易的隐私包含：

• 被记录到区块里的过程
• 上链后从区块里读：如果客户端下载了完整的账本，敌手无法发现与客户端相关的账户
  • 但是随着区块链规模增加，会影响客户端的存储
  • 采用SPV，只需要存储区块头，但是只能验证支付，无法验证

目前保护余额查询 这一过程隐私的方法：

• 钱包假名机制是暂时的，即可以更换公钥
• 公钥无法追踪到用户身份

It is not difficult to realize that transaction-privacy based on ephemeral nature of wallets is an illusion. （好有哲理）

因此有了中心化的混币机构（可能作恶，可能滥用财产，容易受到去匿名攻击）

如果采用PIR，可以实现余额查询的隐私保护

Private Information Retrieval

$n$个服务器，每个服务器都有完整的$k$个比特的字符串$(x_1,x_2,\dots,x_k)$，获取$x_i$，但是任何服务器都不知道哪个比特被查询了

评价PIR的标准之一是rate，是指取回的符号/下载的符号，类似有效率

Contribution

• 形式化了使用PIR在编码分片区块链上进行交易隐私保护
• 构造了从RS码存储的数据中进行查询的PIR
• 容忍最多$n-k$半诚实服务器合谋

Transaction Privacy with Coded Sharding

Private Data Access: System model

节点个数为$n$，分片个数为$k$，每个分片内账户总数为$m$

同步网络，网络可以是动态的，但是假设网络规模永远为$n$个节点

主要考虑$T$个epoch，$B_j(t)$表示第$j$个分片内的区块，$j\in[k],t\in[T]$，假设没有跨片交易，$X_j(t)$为$B_j(t)$包含的交易

$X_j(t)=(X_j^{send}(t),X_j^{receive}(t))$

$X_j^{send}(t),X_j^{receive}(t)$每个元素都属于$\mathbb{F}_q^m$，即$(1\times m)$向量，$q$的值取决于单个交易的最大单元

账户$p$向账户$q$发送b个单位密码货币，记为

$$X_j^{send}(t,p)=-b,X_j^{receive}(t,q)=b$$

$X_j^{send}(t,p)$是$X_j^{send}$的第$p$个分量

只考虑线性码，第$i$个节点在epoch $t$存储$Y_i(t)$的是$\{X_j(t),j\in[k]\}$的线性组合

$$Y_i(t)=\sum^k_{j=1}g_{ij}X_j(t),i\in[n]$$

$g_i=[g_{i1},\dots,g_{ik}]^T$是第$i$个节点的生成向量，$X_j(t)$为$1\times 2m$向量，考虑$T$个epoch后节点$i$的内容$Z_i(T)$

$$Z_i = \left[ \begin{matrix} Y_i(1)\\ Y_i(2)\\ \vdots\\ Y_i(T) \end{matrix} \right] = \left[ \begin{matrix} X_1(1) &\dots & X_k(1) \\ X_1(2) &\dots &X_k(2) \\ \vdots &\ddots &\vdots \\ X_1(T) & \dots & X_k(T) \end{matrix}\right] \left[\begin{matrix} g_{i1}\mathbb{1}_{2m} \\ g_{i2}\mathbb{1}_{2m} \\ \vdots \\ g_{ik}\mathbb{1}_{2m} \end{matrix}\right]=U \cdot(g_i \otimes\mathbb{1}_{2m}) \\$$

$\mathbb{1}_{2m}$是$2m\times1$维的全1向量，$U:(T\times 2km)$包含了$T$个epoch内所有分片，涉及总用户$km$的交易历史

考虑$j$个分片内的用户$p$，会想知道自己付的钱是否被打包，即$X_j(t),U(t,2(j-1)m)$

每一行为一个epoch，出块$k$个，第$j$个块的范围为$[2(j-1)m,2mj]$，则$p$对应的send位置为$2(j-1)m+p$;

同理，可以查询receive位置$2(j-1)m+p+m=2j+p-m$

如果服务器对send位置和receiver位置（即p）不知情（oblivious），能够防御恶意服务器将假名和用户的真实网络地址联系起来

统计账户可以记作$\sum_{t=1}^T U(t,2(j-1)m+p)+U(t,2j-m+p)$

服务器可以分为：

• curious-but-honest：想要猜出$p$，但是会正确响应
• stragglers：拖延很久争取时间猜出$p$，之后正确响应
• malicious：尝试猜出$p$，可能返回错误结果

当用户$p$想要读取$X_j(t,p)=U(t,2(j-1)m+p)$时，生成$n$个随机的$1\times 2m$向量$\{q_i(j,p)\in\mathbb{F}_q^{2m}|i=1,2,\dots,n \}$，向第$i$个节点发送$(t,q_i(j,p))$

每个节点返回$\mathcal{A}(Y_i(t),q_i(j,p)):=a_i=q_i(j,p)^TY_i(t)$，扩张n倍

收到所有$a_i$后，计算$\hat{X}_j(t,p)=\sum^n_{i=1} a_i$

协议需要满足：

• 正确性：$\hat{X}_j(t,p)=X_j(t,p)$对所有$j,p$均成立
• 隐私性：信息论安全 对在$\{1,\dots,2m\}$均匀随机的$P$和curious-but-honest的服务器集合$\mathcal{D}$，满足 $I(P:\cup_{i\in\mathcal{D}}q_i(j,p))=0$

Overiew of Reed-Solomon Codes

假设采用广义RS码 (generalized Reed-Solomon code, GRS) 对区块进行编码

复习信息论

$(n,k)$ 线性码：n是码长，k是线性空间维数

生成矩阵：$G:k\times n$，每一行是生成向量

校验矩阵：$H: (n-k)\times n$，每一行是一个n元线性方程组的系数，$n-k$ 行确定了一个n维线性空间

若c为码字，有$Hc^T=0$

$C_{GRS}$是MDS码，最小距离$n-k+1$

$H_{(n-k)\times A},A\leq n-k$ 列满秩，说明$H$内 存在$A\times A$可逆矩阵

Private Data Access with Curious-but-honest Servers

如果敌手是malicious，可以通过固定查询检测出，所有回复$q^TY_1(t)\dots q^TY_n(t)$是一个码字，则$q^TY_1(t)\in \mathbb{F}_q$

因此从敌手的角度来说保持curious but honest是更加明智的选择

假设curious but honest服务器的数量 $d\leq n-k$

PIR protocol

构造查询向量的思想：混合

• $\mathcal{C}_{GRS}$的奇偶校验向量（思想来自于[TIT18]）
• 半随机向量(q)
• 生成矩阵的逆矩阵的行向量

最终用户$p$构造的查询向量为$\{q_i(j,p)\in \mathbb{F}^{2m}_q|i=1,\dots,n\}$

分别向每个服务器$i$发送查询$q_i(j,p),t$

收到回复$\mathcal{A}(Y_i(t),q_i(j,p))=a_i=q_i(j,p)^TY_i(t)$后，客户端计算$X_j(t,p)=\sum^n_{i=1} a_i$

以下给出查询向量$q_i(j,p)$的构造方式：

分别记GRS码的校验矩阵和生成矩阵为：

$$H_{GRS}= \left [ \begin{matrix} h_1^T\\ h_2^T\\ \vdots \\ h^T_{n-k} \end{matrix} \right ]_{(n-k) \times n} G_{GRS}= \left [ \begin{matrix} G_1 \ G_2 \end{matrix} \right ]_{k \times n}$$

其中$G_1:k\times k,G_2:k\times(n-k)$，$G_1$是$G_{GRS}$可逆的子矩阵，$h^T_l=[h_{l1},h_{l2},\dots,h_{ln}],1\leq l\leq(n-k)$

$G_1^{-1}=[\tilde\phi_1,\dots,\tilde\phi_k],\tilde\phi_i:k\times 1,\phi_j^T=[\tilde\phi_j \ 0]_{1\times n}$，即$\tilde\phi_j$后面补$n-k$ 个$0$

假设curious but honest服务器的数量为$d$

均匀随机选择$d$个向量$r_1,\dots,r_d \in \mathbb{F}^{2m}_q$，计算$r_{d+1}=(\sum^d_{i=1} r_i)+e_p$，其中$e_p=[0\ 0\ \dots\ 1_p\ \dots\ 0]_{2m \times 1}$

$$R_p=[r_1 \ r_2\ \dots \ r_{d+1}]_{2m \times (d+1)}\\ \Psi_j= \left [ \begin{matrix} h_1^T + \phi_j^T\\ h_2^T+\phi_j^T \\ \vdots\\ h_d^T+\phi_j^T\\ \phi_j^T \end{matrix} \right ]_{(1+d)\times n}\\ Q=R_p\Psi _j:2m\times n$$

此时矩阵$Q$的每一列分别为$q_i(j,p)$，令$\varphi_{i}=\phi^T_{ji},i\in[n]$

$$q_1(j,p)= \left[ \begin{matrix} \sum^{d}_{k=1} r_{k,1}(h_{k,1}+\varphi_1 )+r_{d+1,1}\varphi_{1}\\ \sum^{d}_{k=1} r_{k,2}(h_{k,1}+\varphi_1 )+r_{d+1,2}\varphi_{1}\\ \vdots \\ \sum^{d}_{k=1} r_{k,2m}(h_{k,1}+\varphi_1 )+r_{d+1,2m}\varphi_{1} \end{matrix} \right ]\\ q_i(j,p)= \left[ \begin{matrix} \sum^{d}_{k=1} r_{k,1}(h_{k,i}+\varphi_i )+r_{d+1,1}\varphi_{i}\\ \sum^{d}_{k=1} r_{k,2}(h_{k,i}+\varphi_i )+r_{d+1,2}\varphi_{i}\\ \vdots \\ \sum^{d}_{k=1} r_{k,2m}(h_{k,i}+\varphi_i )+r_{d+1,2m}\varphi_{i} \end{matrix} \right ],i\in[n]$$

接下来证明这种构造满足正确性和隐私性

Privacy

设作恶的服务器为$d\leq n-k,\mathcal{D}={i_1,\dots,i_d}$，则发送给所有作恶节点的查询向量组成$2m\times d$的矩阵$Q_D$

对$R=[r_1 \ r_2 \cdots \ r_d ]_{2m\times d},E_p=[e_p \ \cdots \ e_p]_{2m\times d},rank-one,\Phi=[h_1 \ h_2 \ \cdots \ h_d]_{d\times d}$

$$\Delta_D=\left[ \begin{matrix} \hat\phi_{j1} \\ & \hat\phi_{j2} \\ & & \ddots\\ & & & \hat\phi_{jd} \end{matrix} \right ]_{d\times d}$$

有$Q_D=R_p \cdot\Psi_{j,D}=R\Phi+ E_p\Delta _D$

Correctness

根据$a_i=q_i(j,p)^TY_i(t),Y_i(t)=\sum^k_{j=1}g_{ij}X_j(t),i\in[n]$

$$\begin{align} X_j(t,p) &=\sum^n_{i=1} a_i \\ & = \sum_{i=1}^n q_i(j,p)^TY_i(t) \\ & = (\sum_{l=1}^dr_l^T\sum^n_{i=1}(h_{l_i}+\phi_{ji})Y_i(t))+r_{d+1}\sum^n_{i=1}\phi_{ji}Y_i(t) \end{align}$$