1. 引言

Private market，借助zk-SNARKs和以太坊来 隐私且trustlessly selling：

• 1）以太坊地址的私钥（ECDSA keypair）
• 2）EdDSA签名
• 3）Groth16 proof：借助递归性来匿名交易Groth16 proofs。

开源代码实现见：

• https://github.com/dmpierre/eth-private-market（Circom、TypeScript、Solidity）
• https://github.com/nulven/EthDataMarketplace（TypeScript、Solidity）

Private market定位为permissionless P2P时长，支持任意用户bid/ask私钥、签名和Groth16 proof。

数据交易需同时解决2大问题：

• 数据仅对buyer可用。
• 数据具有可验证的属性。

相关示例有：

• 1）zkML：基于proven accuracy来交易机器学习模型。
  • https://github.com/zk-ml/linear-regression-demo（Solidity&Javascript）
• 2）Yi Protocol：Down-sampled versions of images for private NFT transfer。
• 3）Nightmarket：Dark Forest Coordinate交易市场
  • https://github.com/0xSage/nightmarket（Solidity&Javascript）
• 4）Image blurring：
  

2. 三大基石

本协议基于以下3大基石来构建：

• 1）Assertion proof：$f(data,property)=true$
• 2）Encryption proof：$enc(data,key)$
• 3）Commitment proof：$h(data)$

3. 案例一：卖某个奇数

假设Alice向Bob出售某个奇数，基本流程为：

• 1）Alice知道某个秘密奇数，希望能卖1Ether：
  • Alice对该奇数进行commit，并将相应哈希结果推送到某合约中。
  • Alice发布其公钥，任何人都可用于计算共享密钥。
• 2）Bob想要知道Alice卖的奇数：
  • Bob根据Alice发布的公钥计算二者的共享密钥。
  • Bob发布 其计算共享密钥时的公钥。
  • Bob对其私钥进行commit。
  • Bob托管1Ether。
• 3）Alice现在可向Bob出售其奇数了。Alice会计算包含如下信息的single proof：
  • 展示其数字无法被2整除——即assertion proof。
  • 展示其对该奇数进行了正确加密——即encryption proof。该加密数据会提交上链。
  • 展示其使用了与Bob相同的共享密钥，且所售奇数与早前commit的一致——即Commitment proof。

一旦合约验证Alice的proof通过，则将释放Bob托管的1Ether给Alice。至此，Alice获利1ETH，Bob使用共享密钥解密链上数据，可获得相应的奇数。

4. 案例二：卖私钥

有趣的是，有一个围绕以太坊流动性最强的资产之一创建市场的计划。私钥起着访问账户和发起交易的作用，我们可能想知道这样的设置能起到什么作用。
首先，能够不信任地出价或索要私钥可能会成为将股份委托给未知方的威慑机制。如果一把钥匙从具有委托金额的赌注者那里泄露，任何拥有它的人都可以使用这种设置匿名、不信任地出售它。因此，这种设置可以发出私人和有价值信息泄露的信号。
它还提出了有关治理协议和投票机制的问题。来自私人钥匙被提议出售或出售的地址的选票应该被计算在内吗？在市场上出售私钥可能不是操纵选票的最直接方式。事实上，购买私钥并不能以任何方式保证买家出价的地址会以特定的方式投票。然而，治理协议可能容易受到恶意实体以一定ETH金额出售或购买一组地址的攻击，从而使对特定决定的投票可能无效。一旦参与地址的私钥在私人市场上播出，这些地址是否仍应该在治理决策中有发言权？
最后，私钥市场设置的某些部分可能与帐户抽象的上下文相关。钱包可能会采用旋转密钥对方案来对其交易进行签名。对于账户借贷等用例来说，能够使用这种设置出售对钱包的临时访问可能特别有趣。
我们的建设在任何方面都不是决定性的。相反，它指向了一个方向，可以使以太坊钱包这一非流动性资产具有流动性。

secp256k1 keypair为以太坊和比特币的基石，卖以太坊私钥 分为2种情况：

• 1）ask
• 2）bid

4.1 Placing an ask on an ethereum address

Placing an ask on an ethereum address的流程为：

• 1）seller对其地址进行commit，表示其愿意出售相应的私钥，并标价。
• 2）buyer在合约内托管相应数量的ETH，并提交其公钥。buyer会计算：
  • 使用seller的公钥来计算出共享密钥ECDH value
  • 对该共享密钥进行commit。
• 3）为获利，seller向链上提交的proof需满足：
  • Assertion correctness：即地址派生自所提供的私钥。
  • Encryption correctness：即私钥已被正确加密。
  • Commitment correctness：即：
    • 加密秘钥对应 Bob提交的committed shared key。
    • 派生地址对应之前commit的地址。

由于proof data中包含了encrypted data，因此现在buyer可访问链上的encrypted private key。

相应的电路为：

/*
     This circuit is used within the ask setup. It does not require to check
     the validity of an ECDH shared key, since it is not used. The shared key
     has been committed onchain, we make the hash of this shared key public 
     and check against this commmitment when posting the proof.
*/

template SellETHAddressNoECDH(n, k) {

     signal input sharedKey[2]; // private
     signal input sharedKeyHash; // public

     signal input poseidonNonce; // public
     signal input encryptedPrivECDSAKey[7]; // public
     
     signal input privECDSAKey[4]; // private

     signal output address;

     var i;

     /* 
          1. Hash the shared key 
          Ensure that it corresponds to the committed one. 
     */

     component poseidonSharedKey = Poseidon(2);
     poseidonSharedKey.inputs[0] 

4.2 Placing a bid on an ethereum address

bid与ask流程不同。bid是buyer先表达购买某地址的意图，因此是buyer在seller之前发布其公钥。从seller的角度来看，具有与ask流程不同的proof。

Placing a bid on an ethereum address的流程为：

• 1）buyer对某以太坊地址出价，并在market合约中托管相应数量的ETH。
• 2）seller提交上链的proof中需包含：
  • Assertion correctness：即地址派生自所提供的私钥。
  • Encryption correctness：即私钥已被正确加密。
  • Commitment correctness：即：
    • seller使用了buyer的committed公钥。
    • 派生地址对应当前所bid的地址。
  • Key exchange correctness：seller的communicated公钥，对应于，用于计算共享加密密钥的公钥。

bid流程具有更少的步骤。但seller需要添加一个key exchange correctness proof。否则，seller could communicate a different public key from the one he derived using the private key used to compute the shared encryption key.

相应的电路为：

/*
     This circuit is used within the bid setup. We check here that 
     the ECDH value has been correctly computed. We make the public key of the seller
     public so that the buyer - bidder - can compute the shared key value after the
     sale has been made. 
*/

template SellETHAddressECDH(n, k) {
     
     signal input sellerPubJubJub[2]; // public
     signal input sellerPrivJubJub; // private

     signal input buyerPubJubJub[2]; // public

     signal input sharedKey[2]; // private

     signal input poseidonNonce; // public
     signal input encryptedPrivECDSAKey[7]; // public
     
     signal input privECDSAKey[4]; // private

     signal output address;

     /*
          1. Check that the shared key is correctly computed
     */
     component sharedKeyCheck = SharedJubJubKeyCheck();
     
     sharedKeyCheck.pubA[0] 

5. 案例三：卖EdDSA签名

在我们的应用程序中，签名的购买者要求签名其公钥的哈希。利用一些公钥注册表，这种设置可以成为构建web3本地订阅平台的一种令人信服的方式。在市场上购买的签名是PCD（Proof-Carrying Data），表明买方知道“由特定服务的公钥签名的签名”。因此，签名的购买者可以不受信任地获得感兴趣的服务。

买家也可以将这些签名收集在钱包中，选择我们希望完全或部分泄露给服务提供商的签名。例如，提交了一个PR，将该jubjub-signature-pcd添加到Zupass repo中，允许将此类签名存储在Zuzalu护照中。

让我们看一个具体的例子。比特币杂志建议使用这种设置订阅其内容。Alice 支付0.01 ETH访问该报一年。报纸服务从发布在链上的内容中获取Alice的公钥，对其进行哈希签名，并在链上发布加密签名。Alice可以解密签名，现在可以将其添加到PCD钱包中。登录后，Alice将被要求证明：

• （1）她知道由报纸的密钥对签名的签名，该密钥对的消息是她的公钥的散列，
• （2）她知道该公钥的私钥。公钥将保持隐藏状态，Alice只需提供proof即可。因此，她将不信任地私下登录并阅读比特币杂志文章。

在我们的设置中，我们要求买家发布卖家需要签名的哈希预图像。尽管这会产生额外的调用数据，但卖家知道要签名的消息。

EdDSA签名的ask流程与ECDSA keypair的ask流程没有太大区别。签名的买方可以要求由卖方提交的公钥对任意公共消息进行签名，具体流程为：

• 1）seller对其public keypair进行commit，声称只要给特定价格，可对消息进行签名。
• 2）buyer托管相应数量的ETH到market合约并提交其公钥，以下单要求签名。buyer会在链下计算：
  • 使用seller的公钥来计算ECDH value（即“shared key”）
  • 对shared key进行commit
  • 待签名消息，包含了buyer的公钥哈希。
• 3）seller提交上链的proof中需包含：
  • assertion correctness：签名是对特定的哈希进行签署。
  • encryption correctness：签名解密正确
  • commitment correctness：
    • 加密密钥对应committed shared key。
    • 签名消息对应buyer的链上committed hash。

本方案中，卖家可能对签署任意数据感到不舒服。作为补救措施，买家还发布了正在签名的哈希的pre-image。卖家现在必须检查正在签名的哈希是否与所传递的pre-image相对应，并做出相应的决定。

相应的电路见：

/*
     A seller has placed an ask order for a signature over a public message
     A buyer has escrowed some value for it, along with a public preimage
     The seller makes a proof that:
          1. The signature has been encrypted with the committed shared key
          2. The signature signs a hash whose preimage is the publicly committed one
          3. The signature is correct
          4. The encryption is correct
*/

template SellSigPublicMessageEdDSA() {

     signal input pubKeyJubJubSeller[2]; // public
     signal input messagePreImage[2]; // public

     signal input message; // public h( messagePreImage )

     signal input sharedKey[2]; // private
     signal input sharedKeyHash; // public
     signal input signaturePoseidonNonce; // public
     
     signal input eddsaSigR8[2]; // private
     signal input eddsaSigS; // private
     signal input poseidonEncryptedSig[4]; // public 

     var i;

     /* 
          1. Hash the shared key 
          Ensures that it corresponds to the committed one
     */

     component poseidonSharedKey = Poseidon(2);
     poseidonSharedKey.inputs[0] 

6. 案例四：卖Groth16 proof

当我们开始这个项目时，我们首先想知道如何让proof-gated服务的用户能够完全拥有他们所拥有的访问权限。

最近，Personae Labs发布了heyanoun，这是一个专门为名词所有者设计的工具，可以匿名地在网上构思和讨论DAO道具。这对名词群体来说是相当有力量的。虽然是公开的，但该应用程序的验证性确保了只有名词持有者才能参与，从而起到过滤机制的作用，提高了讨论质量。
然而，假设非名词持有者也可能有有趣的观点可能并不太牵强。如果一个非名词持有服务器托管网者想匿名为一个道具团队背书，该怎么办？或者，如果一个道具有一个损坏的启动器，只有非名词持有者（可能希望保持匿名）才能报告恶意，该怎么办？另外，名词持有者自己呢？他们利用自己的访问权限，让匿名者能够在自己的平台上表达自己，这不是很有趣吗？这可能会为他们持有的NFT增加一些价值。
这就是销售groth16 proofs所能做到的。举个例子，我最近发现了一个访问heyanon群组的请求命令。当我的订单被一位匿名群成员填写后，我在相应的heyanon群中发布了一条消息，甚至没有将我的地址包含在这个群中！太酷了。填写我订单的地址认为我的信息很有趣，并有机会利用它不再使用的访问权限做一些事情。在我这边，我有幸发布了一条厚脸皮的信息，并为一个我一直想成为其中一员的团体做出了贡献。
这是一个非常激动人心的成就。我们相信，它可以为proof-gated应用程序开辟另一个设计空间。
首先，由于递归性允许选择性的输入公开，dapps制造商可以根据公开信号的公开来设计不同的访问策略。这将导致不同的证明可能具有不同的值，遵循它们提供的访问类型。
例如，在heyanoun上，“匿名访问”证明的购买者可以使用通用的“假名”发布消息。但也有可能购买稍微贵一点的“冒充”证明，从而可以用一个随着时间的推移而积累声誉的“假名”发布消息，在社区中具有更大的影响力和影响力。
对于能够访问此类应用程序的NFT持有者来说，这也是令人兴奋的。他们现在可以不信任地从他们的NFT中提取价值，这与围绕他们资产的投机动态不同。围绕其公用事业的市场可能会在NFT社区内形成动态生态系统。结合PCD钱包，可以设想一套全新的应用程序和用户体验。
在链上游戏的背景下，出售证明而不是输入证明可以被视为设计“作弊代码”的一种方式。在darkforest，Nightmarket的设置是出售行星坐标。但如果proof被出售，proof买家可能会让其他玩家相信他正在探索某个特定区域，四处传播虚假信息。他还可以让其他玩家或nft兑换服务机构相信他赢得了一轮比赛或进入了排行榜前5名。
我们很高兴听到您对如何使用此设置的想法。实现这一点的一个途径是开发一个递归电路库，该库适用于之前（或未）引用的每个dapp。

我们在这里详细介绍了如何可靠地销售groth16 proof。通过利用递归，我们可以私下出售groth16 proof，然后买家可以使用该proof访问相应的proof-gated服务。

6.1 Placing an ask for a groth16 proof

heyanoun app中一样的groth16 proof为例。

为访问这些服务，用户需提供 a proof that he knows a valid signature

s

s

s over a message

m

m

m emanating from a public key

p

k

i

pk_i

pki​ stored in a tree

t

t

t with root

r

r

r and leaves

p

k

0

,

⋯
 

,

p

k

i

,

⋯
 

,

p

k

n

pk_0,cdots,pk_i,cdots,pk_n

pk0​,⋯,pki​,⋯,pkn​。

我们首先开始设想，heyanon用户可以直接将merkle路径和签名出售给感兴趣的买家。问题是，这将打破卖家的匿名性。merkle路径和签名都会向买家透露merkle树中的哪个公钥已经出售了他的访问权限。
相反，我们将利用递归性。这使我们获得了选择性的隐私，只泄露我们想要的输入——消息和群根。卖方必须生成一个证明，表明他知道消息m（公共）上的有效签名s（私有）和解析为根r（公共）的merkle路径p（私有）的证明。
出售proof本身不会打破卖家的匿名性，同时授予买家相同的访问级别。具体流程为：

• 1）seller对group root $r$
• 2）在链下，buyer使用seller的公钥计算shared key，然后托管相应数量的ETH到market，提交公钥，并对其希望发送到该group的消息进行commit，来下单proof。【注意在本步骤中，若buyer使用所计算的shared key来机密message的话，则buyer和seller都将对所交易的message获得匿名性。】
• 3）seller提交上链的proof需包含：
  • assertion correctness：所售groth16 proof是正确的——为recursive part。
  • encryption correctness：该proof经正确加密
  • commitment correctness：
    • 加密密钥和verification密钥的哈希正确
    • 所售proof的group root和message哈希，与初始committed值对应。

相应的电路见：

/*
     This circuit:
          1. verifies a proof
          2. encrypts the proof's content
          3. hashes the verification key
          4. hashes the shared key
*/

template verifyAndEncryptSigMerkleProof(publicInputCount, l, nPoseidonHash, nHashInputs) {
     /*
          In our setup, we werify a proof of a proof of:
               1. a valid signature over a message m 
               2. a merkle path resolving to root r
     */
     var k = 6;
     var m;
     var i;
     var j;
     var encryptedProofLength = l + 1;

     // verification key
     signal input negalfa1xbeta2[6][2][k]; // private
     signal input gamma2[2][2][k]; // private
     signal input delta2[2][2][k]; // private
     signal input IC[publicInputCount+1][2][k]; // private
     signal input vkHash; // public

     // proof
     signal input negpa[2][k]; // private
     signal input pb[2][2][k]; // private
     signal input pc[2][k]; // private
     signal input pubInput[publicInputCount]; // public

     // encryption
     signal input encryptedProof[encryptedProofLength]; // public
     signal input poseidonNonce; // public
     signal input sharedKey[2]; // private
     signal input sharedKeyHash; // public

     component verify = verifyProof(publicInputCount);
     component encrypt = EncryptGroth16Proof(l);
     component hash = HashGroth16Vkey(nPoseidonHash, nHashInputs);
     component poseidonSharedKey = Poseidon(2);

     var startIdxHashGamma2 = (k * 2 * k); // offset 
     var startIdxHashDelta2 = startIdxHashGamma2 + (k * 4);
     var startIdxHashIC = startIdxHashDelta2 + (k * 4);

     for (i = 0; i 

7. 案例五：卖以太坊交易

还有一种设置，出售的是在以太坊上执行交易。这可以以一种有趣的方式实现隐形交易。具体流程为：

• 1）Alice发布ask，表明其想要执行一笔交易的意图。该交易将提供一定数量的ETH托管在market中。
• 2）Bob想要Alice将一定数量的ETH发送到其持有私钥的地址中。Bob在market中为Alice托管一定数量的ETH。Bob会计算：
  • 使用Alice的公钥计算shared key
  • 对shared key进行commit
  • 其想要Alice执行的加密交易数据，其中包含了转账地址和数量。
  • 对交易数据进行commit，可包含$h(address,amount)$
• 3）Alice对交易数据解密。Alice将相应数量发送到特定地址。通过提供包含如下信息的proof，Alice可获得Bob给的相应托管：
  • assertion correctness：使用merkle path来对应交易trie root，Alice展示了存在与交易收据trie中的某交易收据，其满足Bob初始请求的交易参数。
  • encryption correctness：Alice使用shared key对交易收据加密。
  • commitment correctness：
    • 所执行交易参数的哈希，等于之前bob提交的承诺值。
    • 加密的交易收据使用了正确的shared key。

需要注意的是，Bob可以托管与他要求Alice执行的不同数量的ETH。如果他托管了更多的ETH，他将在某种程度上为执行的交易向Alice“小费”。他还将进一步将智能合约上托管的金额与Alice交易的金额脱钩。

这种设置可以通过将交易收据trie的连续根存储在市场的合同上来实现。

然而，由于时间和技术限制，我们在此不提供实施。除其他困难外，我们无法找到方法轻松获得证明在交易收据trie中包含交易收据的merkle路径-在geth上使用类似于eth_getProof的API。我们必须同时实现这个API和一种有效的方式来生成包含交易收据的证据——类似于Axiom对以太坊的state trie所做的。

我们感到惊讶的是，以太坊的黄皮书明确提到，生成与交易收据相关的零知识证明可能很有趣。事实上，这种设置可以很容易地从证明简单事务的执行推广到更复杂的合同交互，也就是隐形交互。

8. 改进点

我们的构建承担着某角色向市场发送他知道自己无法完成的询价单的风险。有三种机制可以用来防止这种情况：通过提供proof证明买家知道解决该房产的数据来启动询问，大幅削减询问者只有提供相应proof才能取消询问的规则，并最终在市场上建立声誉协议。
我们还详细介绍了买方-卖方序列，最多需要三个不同的步骤：询问、订单和填写。然而，我们不应该局限于这种特定的流动。可以想象，增加一个步骤，使买家和卖家能够私下交流和/或承诺提供一些额外的数据。

除此之外，我们今天的设置仅适用于escrowing ether。然而，可以允许将NFT或ERC-20等各种资产用作托管。也可以有一个集体托管设置，买家将ETH集中在一起。例如，一个链上游戏DAO团队可以将他们的ETH集中起来购买一个昂贵的作弊代码，从而获得不公平的决定性战略优势。
我们也没有讨论证明无效的问题。然而，启用此类方案的proof-gated应用程序可能需要想办法避免proof在其协议中被“双重使用”。

待改进技术点：
groth16 proof的卖家将不得不从calldata中承担不可忽略的成本。我们没有致力于实现压缩证明表示，这可能有助于我们降低此类成本。这也指出，如果以太坊的普通日常用户采用这种设置，加密数据将发布在链上，那么这种设置将要求简洁。

我们不得不得到强大的服务器来生成zkeys和proofs4。一般来说，groth16递归证明成本在今天的日常机器上运行是令人望而却步的。我们很高兴看到团队使用Nova的证明方案，正在努力实现在移动设备上递归生成证明的能力。

参考资料

[1] 2023年8月PSE视频 Private markets on Ethereum – 0xPARC Pierre
[2] Private Market
[3] 2022年6月 Applied ZK, Devconnect AMS’22视频 ZK Data Marketplace, Applied ZK – Day 1

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: USACO section 2.2 Subset Sums(DP,背包)

Subset Sums For many sets of consecutive integers from 1 through N (1 For example, if N=3, one can partition the set {1, 2, 3} in …