DECO科普周：深度研究系列三（解析响应）

作者：Chainlink Labs研究团队

作者：Siam Hussain

贡献者：Lorenz Breidenbach、Dahlia Malkhi、Alexandru Topliceanu、Xiao Wang, Chenkai Weng和Fan Zhang

在上一篇文章中，我们讲到了如何验证TLS响应的真实性。而今天，我们要来讨论如何高效、可靠地解析响应，以及如何在对响应创建主张（claim）时保护敏感数据隐私。

上一篇文章最后提到，证明者和验证者都持有对验证过的TLS响应做出的承诺[R]。响应R是一个包含字节或字符串的数组。然后，证明者可以用DECO向验证者证明关于R的主张是真实的，并同时保护R的隐私。比如在下方示例中，R是关于证明者财务报告的JSON文件，那么她（证明者）就可以声称她银行余额超过100万美元，并且不用透露具体的数字。

{
    "balance": 2000000,
    "account_id": 156461324651,
}

由于验证者看不到R的明文，因此就存在一个安全隐患，即：如何证明这个主张是正确的？具体而言，验证者如何能确保证明是对应着“balance”这个字段，而不是“account_id”字段？这个问题可能乍一看没什么，因为JSON可以非常明确地被解析出来。然而，真正地问题是，在零知识证明中解析JSON的成本非常高。

本文将分享如何高效地解析主张并证明解析的有效性。其中，我们会引出一个协议，该协议会从对某一字符串做出的承诺中提取对某些字段做出的承诺。我们之所以主要以JSON为例，是因为它是API响应中最常用的格式。不过本文中提到的概念也同样适用于XML或YAML等格式。

解析零知识证明JSON所面临的挑战

虽然解析明文JSON的过程很直接了当，但是解析零知识证明JSON却成本极高，因为JSON的数据结构是验证者看不到的。要说明白这一点，我们得先举一个更简单的例子。请看下面关于私密布尔值b的if-else代码示例。

if (b)
    y = f1(x)
else
   y = f2(x)

如果b是不公开的，那么验证者就不知道该选择哪个分支。因此，f1()和f2()都需要通过ZKP协议来计算，然后用多路复用器电路（multiplexer circuit）来选择y值。

上面是解析JSON文件的流程图。从灰色的节点开始，每个节点都有许多可能的分支。由于验证者无法看到JSON文件明文，因此他不知道应该选择哪个分支。因此，解析器需要尝试每一条可能的分支。这样一来，字符串中每多一个字符，可能的分支数量都会大幅增长。也就是说，解析JSON文件的ZKP电路会大到无法承受。

选择性地打开

不过在实践中，JSON的数据结构很少会包含隐私数据。Web API返回给不同用户的响应都拥有相似的数据结构，而与某个用户相关的隐私数据通常是标量JSON值（scalar JSON values）。在DECO中，证明者可以打开一部分发给验证者的响应，让他能够看到数据结构但看不到标量值，以此帮助验证者来解析JSON。这样一来，验证者就可以在本地解析响应，而不用通过ZKP解析。

• 在F(eval(R,q))表单里用一次JSON查询请求q表示一个主张，其中eval(R,q)指对R提出的查询请求q所返回的结果，而F则是一个返回true或者false的函数。 

• 证明者计算：1)格式化后（redacted）的JSON响应R’，R’完全保留了JSON的数据格式，但是把所有标量值都隐去了；2)一个包含所有JSON标量值的数组Z。然后，她将R’以及对数组Z做出的承诺[Z]都发给验证者。

• 双方都在本地计算Z中的索引数组J，Z[J]=eval(R,q)。因为R’完全保留了JSON的数据结构，所以验证者可以用它来计算Z中任何标量值的索引。最后，他们会通过ZKP来计算F(Z[J])，验证对数组Z做出的承诺。

我们将用下面这个示例JSON来展示整个流程。证明者声称其任何账户中都没有负余额。使用jq 语法(一种JSON查询语言) ，q=“.accounts[].balance” andF(x) is min(x)>0。

    "accounts":[
        {
        "balance": 12345,
        "account_id": 156461324651,
        },
        {
            "balance": 1000000,
            "account_id": 213612867132,
        },
        {
            "balance": 2000000,
            "account_id": 371823713701,
        }
    ]
}

诚实的证明者将下方格式化过的JSON R’发给验证者。

{
    "accounts":[
        {
            "balance": "",
            "account_id": "",
        },
        {
            "balance": "",
            "account_id": "",
        },
        {
            "balance": "",
            "account_id": "",
        }
    ]
}

并对下方标量值数组Z做出承诺。

[
    "12345",
    "156461324651",
    "1000000",
    "213612867132",
    "2000000",
    "371823713701"
]

证明者和验证者在本地计算索引数组，其中J=[0,2,4]。然后，他们通过ZKP来计算函数min(Z[J]>0返回为ture，因为Z[[0,2,4]]=[12345,1000000,2000000]，其最小值为12345，是一个正数。

完整性检查

由于验证者需要靠证明者来打开响应，因此也需要确保证明者正确地打开响应。验证者会通过以下方式展开四轮检查。

第一轮检查

首先，验证者会检查R’是否为一个有效的JSON。通过使用现成的JSON 解析器解析 R' 来做到这一点。请注意，这里验证者依靠的是解析器的正确实现。

第二轮检查

下一步，验证者会查看数组中的值是否真的来自响应。双方都会在本地计算一组字符串P，切分格式化过的JSON R’，将标量值剔除。

在上述例子中，P如下：

[
    "{\n    \"accounts\":[\n        {\n            \"balance\": ",
    ",\n            \"account_id\": ",
    ",\n        },\n        {\n            \"balance\": ",
    ",\n            \"account_id\": ",
    ",\n        },\n        {\n            \"balance\": ",
    ",\n            \"account_id\": ",
    ",\n        }\n    ]\n}"
]

这里需要注意的是，双方已经持有了对真实响应做出的承诺[R]。他们使用承诺[R]和[Z]对重建声明(reconstruction statement)进行zk计算。这里的m代表标量值的数量，‖代表字符串拼接（bit-wise concatenation）。 

[R]=?[P[0]∥Z[0]∥P[1]∥Z[1]∥⋯∥P[m−1]∥Z[m−1]∥P[m]]

DECO中采用一个承诺机制对R和Z[i];i=0,⋯,m−1中的所有信息做出承诺。因此可以直接用‖将承诺的信息全都串联起来。这一步唯一的ZKP操作就是一点一点进行左右对比。如果证明者篡改了Z中的任何值，那么这个等式都无法成立。

第三轮检查

在这一轮中，验证者会检查格式化过的响应R’是否完全保留了响应R的数据结构。在具体展示检查过程之前，我们先来看一个例子，其中不诚实的证明者可能会为了作弊而隐藏一部分数据结构。

让我们考虑一个场景，第二个账户的余额实际上是负数，既收到JSON响应如下：

{
    "accounts": [
        {
            "balance": 12345,
            "account_id": 156461324651,
        },
        {
            "balance": -1000000,
            "account_id": 213612867132,
        },
        {
            "balance": 2000000,
            "account_id": 371823713701,
        }
    ]
}

不诚实的证明者可能会向验证者发送以下格式化过的响应以及标量值数组。

{
    "accounts":[
        {
            "balance": "",
            "account_id": "",
        },
        {
            "balance": "",
            "account_id": "",
        }
    ]
}

[
    "12345",
    "156461324651,\n        },\n        {\n            \"balance\": -1000000,\n            \"account_id\": 213612867132",
    "2000000",
    "371823713701"
]

这里要注意到，证明者并没有修改R中的任何值。而是重新排列了R’的数据结构以及Z的值，使得在验证者看来第一个值“aountid”是下图中标记文本而不仅仅是 156461324651。

因此R’和Z仍会通过第二轮检查（注：可以对新的R’计算P，并且与新的Z进行交叉，以验证真实性）。然而，现在J[[0,2]]和Z[[0,2]]，是[12345,2000000]，其中最小值大于0，因此ZKP计算会返回false的结果。 

为了保证R’完全保留了R的数据结构，验证者需要确保证明者没有隐藏Z中的任何JSON数据结构。他可以使用ZKP，将Z中的所有元素都作为标量值来解析。JSON支持四类标量值，即：数字、布尔值、字符串以及null。如果[Z]中的任何元素作为标量值解析失败，验证者都可以拒绝这个主张。在上述例子中，将Z中的第一个元素作为标量值解析就会失败。要注意到，将元素作为标量值解析不会遇到前文提到的分支问题，因为任何一个分支都会导致无效的标量值。

第四轮检查

最后一轮检查为的是保证R’中所有标量值都被格式化了。同样，我们通过举例来论证如果没有第三轮检查，证明者将可以用何种方式作弊。不诚实的证明者可能会向验证者发送以下格式化过的响应以及标量值数组。

{
    "accounts":[
        {
            "balance": "",
            "account_id": "",
        },
        {
            "balance": -1000000,
            "account_id": "",
        },
        {
            "balance": "",
            "account_id": "",
        }
    ]
}

[
    "12345",
    "156461324651",
    "213612867132",
    "2000000",
    "371823713701"
]

这里J=[0,2,4]。证明者揭示了其中一个标量值，因此Z[[0,2,4]]=[12345,213612867132,371823713701]，最小值大于0。要注意，这会导致第二轮检查中数组P的值不正确，因此检查也不会通过。然而，验证者可以在ZKP协议开始前就可以发现这个漏洞。他将R’中的标量值格式化，计算出R’v。如果证明者确实将R’中的所有标量值都格式化了，那么R’和R’v就会是一样的。否则，它们就会是不同的，而验证者就可以在开始ZKP计算之前就拒绝主张。 

总而言之，证明者向验证者发送一个格式化的JSON响应R’以及对所有标量值数组Z做出的承诺[Z]，其中R’完全保留了原本响应R的所有数据结构。然后，验证者会进行如下验证：

1. 用已经验证过的响应R中的结果Z中的相应数值来代替R’中所有被格式化的数值。

2. 证明者除了R’中的标量值以外没有隐藏任何其他信息。

3. 证明者没有在R’中遗留任何未格式化过的标量值。 

第二轮检查验证了承诺标量值的真实性；第三和第四轮检查确保R’完全保留了R的数据结构，因此保障JSON查询可以正确计算。 

这是Chainlink Labs研究团队发布的DECO深度研究系列的第三篇文章。请欢迎查看本系列的其他文章：

• 《DECO科普周：深度研究系列文章一（开篇）》

• 《DECO科普周：深度研究系列二（数据溯源和真实性）》