qesa代码解析

1. 引言

前序博客 qesa Efficient zero-knowledge arguments in the discrete log setting 学习笔记。

Hoffmann等人 2019年论文 《Efficient zero-knowledge arguments in the discrete log setting 》。

相应的代码实现可参见：

• https://github.com/crate-crypto/qesa （rust）
• https://github.com/emsec/QESA_ZK （C++）

https://github.com/emsec/QESA_ZK 为论文官方实现代码，包含的算法全面，本文主要关注https://github.com/emsec/QESA_ZK 中的代码实现，部分算法会参考https://github.com/crate-crypto/qesa中的代码实现。

1.1 C++17

https://github.com/emsec/QESA_ZK 代码中采用的是C++2017，需要保证编译服务器的C++版本兼容。 安装升级gcc的方法可参见博客 gcc版本编译安装。

1.2 relic toolkit

https://github.com/relic-toolkit/relic 为一个采用C++实现的密码学库，目前实现的内容有：

• Multiple-precision integer arithmetic
• Prime and Binary field arithmetic
• Elliptic curves over prime and binary fields (NIST curves and pairing-friendly curves)
• Bilinear maps and related extension fields
• Cryptographic protocols (RSA, Rabin, ECDSA, ECMQV, ECSS(Schnorr), ECIES, Sakai-Ohgishi-Kasahara ID-based authenticated key aggrement, Boneh-Lynn-Schacham and Boneh-Boyen short signatures, Paillier and Benaloh homomorphic encryption systems)

https://github.com/emsec/QESA_ZK 是基于relic toolkit 来构建的，需要调用relic库。 注意，QESA_ZK与relic master 版本不兼容，需切换到relic-toolkit-0.5.0版本再编译，详细方法为：

git clone https://github.com/relic-toolkit/relic
cd relic
git checkout relic-toolkit-0.5.0

mkdir build
cd build
cmake ../ -DWITH="BC;DV;BN;MD;FP;EP" \
    -DTESTS=0 -DBENCH=0 -DCHECK=off -DCOLOR=off -DDOCUM=off \
    -DFP_PRIME=255 -DFP_PMERS=on -DRAND=UDEV -DARITH=GMP \
    -DCOMP="-O3 -funroll-loops -fomit-frame-pointer -fPIC" -DWSIZE=64 -DSTLIB=on -DSHLIB=off $1

make -j

将编译的结果 lib/librelic_s.a 库文件拷贝至 QESA_ZK/proof_system/lib 目录下。

git clone https://github.com/emsec/QESA_ZK
mkdir QESA_ZK/proof_system/lib
cp lib/librelic_s.a QESA_ZK/proof_system/lib/

编译并运行QESA_ZK proof_system：

cd QESA_ZK/proof_system/
make

1.3 基本结构体

struct ProverContext
    {
        bool first_iteration;

        Matrix A;
        math::vector w;

        u32 n;
        math::vector u_minus_one;
        math::vector u_plus_one;

        u32 state;

        ProverContext() { state = 0; };
    };

    struct VerifierContext
    {
        Matrix A;
        math::vector t;

        u32 n;
        bool result;

        u32 state;

        VerifierContext() { state = 0; result = false; };
    };

2. Matrix-vector multiplication argument + Zero-Knowledge 2.1 L M P A s i m p l e Z K LMPA_{simpleZK} LMPAsimpleZK​协议

∑ s t d \sum_{std} ∑std​协议+ L M P A n o Z K LMPA_{noZK} LMPAnoZK​协议= L M P A s i m p l e Z K LMPA_{simpleZK} LMPAsimpleZK​协议。 // ctx.state = 0 即进行的是 ∑ s t d \sum_{std} ∑std​操作，来对所有witness进行blinding。

bool test_lmpa()
{
    std::cout  bool {
        self.inner.verify(transcript, G_Vec, H_Vec, Q, gamma_i)
    }
}

4.2 Q E S A C o p y QESA_{Copy} QESACopy​协议

参见https://github.com/emsec/QESA_ZK/blob/master/proof_system/src/test/test_qesa_copy.cpp 代码：

bool test_qesa_copy()
{
    std::cout