零知识证明 - zkHack V Puzzle 3 - Shadow

zkHack V的第三题是用Nior语言实现的电路。

1. 题目

一个网站想避免使用私钥作为认证数据，给每个用户额外分配了随机数据（pepper）。这个随机数据只有用户自己知道。在使用认证之前，用户需要计算{公钥}_{pepper}的hash值提交到网站。使用认证的过程，用户需要生成零知识证明，证明某个用户知道确定的pepper。题目给出了10个hash值，alice的公钥和pepper，以及bob的公钥，在alice提供诚实的hash的情况下，提供证明她是bob。

2. Nior编写电路

src/main.nr代码实现了电路逻辑：

fn main(identifier: BoundedVec<u8, 128>, pub_key: pub [u8; 32], whitelist: pub [[u8; 32]; 10]) {```  

identifier是长度为128的字节数组，代表{公钥}_{pepper}。pub_key是需要认证的公钥信息。whitelist是白名单，代表所有已经注册过的hash信息。  

let digest = std::hash::sha256_var(identifier.storage(), identifier.len() as u64); ... assert(present);```

电路先计算identifier的sha256 hash信息，并且检查这个digest信息是否包括在白名单中。

let id_haystack: StringBody128 = StringBody::new(identifier.storage(), 128);
let pk_needle: SubString32 = SubString::new(pub_key, 32);
let (result, _): (bool, u32) = id_haystack.substring_match(pk_needle);
assert(result);```  

接着，检查是否identifier包含公钥信息。  

这个电路逻辑不够严谨。电路只是检查了，需要检查的公钥信息是否包含在identifier信息中。事实上需要证明的是，需要检查的公要信息是不是identifier开头的信息。  

### 3. Witness信息  

Prover.toml中提供了main函数的所有输入信息。题目要求只修改identifier信息（长度以及数据）。很明显，identifier中需要包括三个信息：1/ Alice的pub key 2/ Alice的pepper 3/ Bob的pub key。  

经过一些简单的组合测试外，发现hash对不上。仔细查看电路的hash计算逻辑：  

let digest = std::hash::sha256_var(identifier.storage(), identifier.len() as u64);```

sha256计算时数据的长度(identifier.len())，也是由witness信息指定。那也就是说，有一种可能，计算sha256的时候用指定的数据长度，而在identifier中查找公钥信息采用完整的数据。

identifier完整的数据信息如下：

{alice's pub key}_{alice's pepper}{bob's pub key}{其他数据}

4. 解决方案

解决方案相对简单， Prover.toml修改如下：

对题目感兴趣的小伙伴，可以进一步查看zkHack V网站上的详细分析。