What is this?

Private Market is a permissionless p2p marketplace that enables any user to bid/ask private keys, signatures and groth16 proofs.

Summary

We present here our zero-knowledge circuits and contracts used for privately exchanging cryptographic objects on Ethereum.

First, we outline how property, encryption and commitment proofs work in the context of a p2p market. Then, we detail setups of increasing complexity for selling ECDSA keypairs, EdDSA Signatures and groth16 proofs in a trustless and privacy-preserving manner. While selling private keys of ethereum addresses and EdDSA signatures is relatively straightfoward, we have had to leverage recursivity to enable anonymous trades of groth16 proofs.

We conclude by describing a setup where users can trustlessly sell execution of transactions themselves on Ethereum, laying out a potential construction of *stealth transactions*. Interestingly, this setup could be generalized to any kind of contract interactions - aka *stealth interactions*.

Our motivation is twofold. First, it might be of interest to demonstrate how any provable computation can be privately traded on Ethereum. Second, we believe that those kind of zk-powered marketplaces open up design and protocol questions and avenues for proof-gated and ethereum dapps makers and users.

General setup: three building blocks

The initial zk-marketplace protocol proposal laid out the different and complementary proofs necessary for trading objects with provable attributes on Ethereum. Nick Ulven's seminal work described three main components, namely property (denoted "assertion proof" in the rest of this post), commitment and encryption proofs^{1}.

Each of those proofs are carried out using succinct zero-knowledge cryptography, giving both parties of a trade the ability to selectively disclose inputs and be convinced that the data being bought satisfies a property with high probability.

**Assertion proof: $f(data, property) = true$**

The assertion proof consists in proving that an assertion holds true regarding some piece of data being sold. A good example is to prove that the statement that a private key resolves to a particular Ethereum address is true: $f(secretKey, address) = true$. The assertion proof convinces the buyer that the private piece of data being sold indeed possesses some property that he is interested in.

**Encryption proof: $enc(data, key)$**

The encryption proof aims to convince the buyer that the private piece of data has been encrypted using a desired key. This key will most likely be a shared buyer-seller ECDH value.

**Commitment proof: $h(data)$**

A commitment proof can play different roles. Hence, there exists different kinds of commitment proofs. In general, the commitment proof aims at proving that what is being sold and how it is sold verifies some earlier committed value.

For instance, it could ensure that the data being sold at the time of exchange corresponds to the data that has been listed initally - i.e. $h(data_{sold}) == h(data_{listed})$. It could also ensure that when the buyer and the seller share the correct encryption key. The sale will occur only if the shared key resolves to a previously calculated commitment, such as $h(sharedKey)$

Assertion, encryption and commitment proofs might not be exhaustive of what a marketplace construction could look like. However, they do form a set of primitives out of which more or less complex setups can be thought of.

**A trivial sale**

Let's go over how those three different proofs work together. Pretend that Alice is selling Bob an odd number:

Alice has this valuable piece of information, consisting of knowing an odd number. She asks 1 ether for it.

She commits to this number by posting its hash on a smart contract.

She posts her public key, with which anyone can compute a shared key.

Bob wants to know what is this odd number that Alice is proposing.

- He computes his shared key with Alice.
He posts the public key with which he computed his shared key.

He commits to the shared key by posting its hash on the smart contract.

- He escrows 1 ether.

Alice can now sell to Bob her odd number. She will compute a single proof consisting of:

Showing that her number is not divisible by 2 - the assertion proof.

Showing that she correctly encrypted the odd number - the encryption proof. This encrypted data is posted on chain.

Showing that she used the same shared key as Bob and that the odd number being sold is the same as the one committed earlier - the commitment proof.

Upon the smart contract validating the proof, the escrow will be released. Alice can profit from 1 ETH. Using the shared key, Bob will decrypt the onchain posted data and enjoy his odd number.

Selling private keys

We detail here two setups (ask and bid) for selling Ethereum private keys. As secp256k1 keypairs form the backbone of the Ethereum and Bitcoin blockchains, it felt natural to us to explore this avenue.

**Placing an ask on an ethereum address**

Let's go over what an ask process would look like for the private key of an Ethereum address.

A seller commits to an address for which he would be ready to sell the private key and posts a corresponding price.

A buyer escrows the corresponding price amount in ETH on a smart contract and posts his public key . He computes:

- an ECDH value using the seller's public key point.
- a commmitment to the shared key.

To release the escrow, the seller posts on-chain a proof showing:

Assertion correctness: the address can be derived from the provided private key.

Encryption correctness: the private key has been correctly encrypted.

Commitments correctness: the encryption key corresponds to the committed shared key. The derived address corresponds to the earlier asked address.

Since the proof data comprises the encrypted data, the buyer will now have access to the encrypted private key onchain.

We provide a circuit for this setup here.

**Placing a bid on an ethereum address**

Placing a bid differs from placing an ask since the buyer expresses his intent to buy an address first. He will post his public key before the seller. This entails a different proof from the seller's viewpoint:

A buyer places a bid on an Ethereum address and escrows a corresponding amount of ETH on the market contract.

A seller posts on-chain a proof:

Assertion correctness: the address can be derived from the provided private key.

Encryption correctness: the private key has been correctly encrypted

Commitments correctness: the seller used the buyer's committed public key. The derived address corresponds to the address being bid.

Key exchange correctness: the seller's communicated public key corresponds to the one that has been used to compute the shared encryption key.

A bid process hence has a reduced number of steps. However, the seller is required to also add a key exchange correctness proof. If not, a seller could communicate a different public key from the one he derived using the private key used to compute the shared encryption key.

We provide a circuit for this setup here.

**Considerations**

It is interesting to consider that there exists a scheme for creating a market around one of the most illiquid asset of Ethereum. Private keys play the role of accessing accounts and initiating transactions and we may wonder what role such a setup can play.

Firstly, being able to trustlessly bid or ask for a private key could act as a deterring mechanism for delegating a stake to unknown parties. If a key were to leak from a staker with a delegated amount, anyone possessing it could sell it anonymously and trustlessly using this setup. Hence, this setup makes it possible to signal the leak of a private and valuable piece of information.

It also raises questions concerning governance protocols and voting mechanisms. Should votes from addresses whose private keys have been proposed for sale or sold count? Selling private keys on a marketplace might not be the most straightforward way of manipulating votes. Indeed, buying a private key does not guarantee in any way that the address a buyer would bid for would vote in a particular way. However, governance protocol could be vulnerable to a malicious entity selling or buying a bunch of addresses for a certain ETH amount, making a vote on a particular decision potentially non-effective. Once private keys of participating addresses have been broadcasted on a private market, should those still have their voice in governance decisions?

Finally, parts of a private key marketplace setup might be relevant in the context of account abstraction. A wallet might adopt a rotating keypair scheme for signing its transactions. Being able to sell a temporary access to a wallet using this setup might be particularly interesting for a use case such as account lending.

Our construction is not definitive in any way. It rather points in a direction which could make liquid the illiquid asset that is an Ethereum wallet.

Selling EdDSA signatures

The ask flow for an EdDSA signature is not very different from the ask flow of an ECDSA keypair. Our implementation makes it possible for the buyer of a signature to ask for an arbitrary public message to be signed by the public key committed by a seller.

In our setup, we require the buyer to post the hash pre-image that the seller is required to sign. Although it incurs additional calldata, the seller knows what message is being signed.

A seller commits to a public keypair that he claims to be able to sign messages with and posts a price.

Offchain, a buyer orders the signature by escrowing the corresponding price amount in ETH on the market and posts his public key point. He computes:

an ECDH value (the "shared key") using the seller's public key point.

- a commitment to the shared key.
a message to be signed. Here, it consists of the buyer's public key hash.

The seller posts on-chain a proof showing:

assertion correctness: the signature has been correctly signed over the required hash.

encryption correctness: the signature has been encrypted correctly.

commitments correctness: the encryption key corresponds to the committed shared key. The signature's message corresponds to the buyer's on-chain committed hash.

In our setup, a seller might not be comfortable with signing arbitrary data. As a remedy, the buyer also posts the pre-image of the hash being signed. The seller now has to check that the hash being signed corresponds to the communicated pre-image and decide accordingly.

We provide a corresponding circuit for this setup here.

**Considerations**

In our app, the buyer of a signature asks for the hash of its public key to be signed. Leveraging some public key registry, this setup can be a convincing way to build a web3 native subscription platform. The signature that is bought on the market is a PCD^{}2 showing that the buyer knows "a signature that has been signed by the public key of a particular service". The buyer of the signature hence trustlessly gains access to a service of interest.

The buyer could also collect those signatures in a wallet, choosing which ones we wish to entirely or partly divulge to the service provider. As an example, we made a PR to add this PCD to the Zupass repo, allowing for such signatures to be stored in the Zuzalu passport.

Let's go over a concrete example. The Bitcoin magazine proposes to subscribe to its content using this setup. Alice comes and escrows 0.01 ETH to access the newspaper for a year. The newspaper service fetches Alice's public key from what has been posted on-chain, signs a hash of it and posts on-chain the encrypted signature. Alice can decrypt the signature and can now add it to its PCD wallet. Upon login, Alice will be required to show that (1) she knows a signature signed by the newspaper's keypair whose message is the hash of her public key and (2) she knows the private key of this public key. The public key will remain hidden, Alice will only have to provide the proof. Thus, she will trustlessly and privately gain login and read access to the Bitcoin magazine articles.

Selling Groth16 proofs

We detail here how to trustlessly sell groth16 proofs. By leveraging recursion, we make it possible to privately sell a groth16 proof which a buyer can then use to access a corresponding proof-gated service.

**Placing an ask for a groth16 proof**

The groth16 proof that we will place an ask for is the same kind of proof that is used on apps such as heyanon.

To access those services, a user has to provide a proof that he knows a valid signature $s$ over a message $m$ emanating from a public key $pk_i$ stored in a tree $t$ with root $r$ and leafs $pk_0, ... , pk_i, ..., pk_n$.

We first started to imagine that a heyanon user could directly sell the merkle path and the signature to an interested buyer. The problem is that it would break the anonymity of the seller. Both the merkle path and the signature would divulge to the buyer which public key in the merkle tree has sold his access.

Rather, we will leverage recursivity. This makes us gain selective privacy, only divulging the inputs we want - the message and the group root. The seller will have to generate a proof showing that he knows a proof of a valid signature $s$ (private) over a message $m$ (public) and a merkle path $p$ (private) resolving to a root $r$ (public).

Selling the proof itself will not break the anonymity of the seller while granting the same access level to the buyer. Here is how it would go:

A seller commits to a group root $r$ to which he claims to have access to and a verification key hash $v$, associated with the verification key used in the proof-gated service.

Offchain, a buyer computes a shared key using the seller's public key. He then orders a proof by escrowing the corresponding price amount in ETH on the market, posting his public key and committing to a message he wishes to be posted within the group.

The seller posts on-chain a proof showing:

assertion correctness: the groth16 proof being sold is correct - this is the recursive part.

encryption correctness: the proof has been correctly encrypted.

commitments correctness: hashes of the encryption and verification keys are correct. The sold proof's group root and message hash correspond to the initially committed values.

We provide a corresponding circuit for this setup here .

Note that in step 2., if the buyer encrypted the message he wants to be signed using the computed shared key, the buyer and seller would even obtain anonymity of the message being exchanged.

**Considerations**

When we started this project we first wondered how we could make it possible for users of a proof-gated service to have full ownership of the access they have.

Recently, personae labs released heyanoun, a tool specifically designed for nouns owners to anonymously ideate and discuss DAO props online. This is quite empowering for the nouns community. While public, the app's proof-gatedness ensures that only noun holders can participate, thereby acting as a filtering mechanism and enhancing discussion quality.

Yet, it might not be too far-fetched to hypothesize that non-noun holders could also have interesting takes. What if a non-noun holder wanted to anonymously endorse a team regarding a prop? Or what if a prop had a corrupted initiator for which only a non-noun holder - that may wish to remain anonymous - could report malicious intent? Also, what about nouns holders themselves? Wouldn't it be interesting for them to leverage their access and make it possible to offer anons the ability to express themselves on their platform? This could add quite some value to their NFT holding.

This is what selling groth16 proofs enables. To give an example, I recently spotted an ask order to access a heyanon group. When my order got filled - by an anonymous group member -, I posted a message within the corresponding heyanon group, without even having my address included in this group! That's quite cool. The address that filled my order deemed my message interesting and had the opportunity to make something out of the access it was not using anymore. On my side, I had the privilege to post a cheeky message and make a contribution to a group I always wanted to feel a part of.

This is a very exciting achievement. We believe that it could open up another design space for proof-gated apps.

First, because recursivity enables selective input disclosure, dapps makers could design different access policies according to which public signal is divulged. This would entail that different proofs could have different values, following the access type they offer.

For instance, on heyanoun, the buyer of an "anon-access" proof could get the ability to post a message under a generic "nym". But there could also be the possibility to buy a slightly more expensive "impersonate" proof, making it possible to post a message under a "nym" that has accrued reputation over time, with more weight and influence within the community.

It also is exciting for NFT holders that have access to such apps. They can now trustlessly extract value out of their NFT, one that is different from the speculative dynamics that may surround their asset. Markets around their utility could spin up dynamic ecosystems within NFT communities. Combined with a PCD holding wallet, a whole new set of apps and UX could be envisioned.

In the context of on-chain games, selling proofs rather than input to the proofs could be seen as a way to design "cheat codes". In darkforest, the Nightmarket setup was selling planet coordinates. But if the proof was sold instead, the proof-buyer could get other players to believe that he is exploring a specific area, spreading fake information around. He could also make other players or nft-redeeming services believe that he has won a round or placed in the leaderboard's top 5.

We would be excited to hear your ideas on how this setup could be used. One avenue for this could be to develop a library of recursive circuits adapted to each of the previously (or not) cited dapps.

Selling Ethereum transactions

There also exists a setup where what is being sold is the execution of a transaction on Ethereum. This could enable stealth transactions in an interesting way.

Alice signals her intent to execute a transaction by placing an ask. The transaction will be executed provided some ETH amount is placed in escrow on the market.

Bob wants Alice to send some ETH to an address he holds the private key of. He escrows some ETH on the market for Alice. He computes:

- a shared key using Alice's public key point
- a commitment to the shared key
the encrypted transaction data he wants Alice to execute. It consists of an address and an amount to be transferred.

a commitment to the transaction data. It could consist of $h(address, amount)$.

Alice decrypts the transaction data. She sends to the specified address the corresponding amount. She will get the escrow by providing a proof consisting of:

Assertion correctness: using a merkle path resolving to a transaction trie root, Alice shows that there is a transaction receipt within the transaction receipt trie that satifies what Bob initially requested as transaction parameters.

Encryption correctness: Alice encrypted the transaction receipt using the shared key.

Commitment correctness: The hash of the executed transaction parameters is equal to the commitment that has been posted by Bob. The transaction receipt has been encrypted using the correct shared key.

It is to be noted that Bob can escrow an amount of ETH different from what he asked Alice to execute. If he escrows a greater amount of ETH, he will in a way "tip" Alice for the executed transaction. He will also further decorrelate the amount being escrowed on the smart contract from the amount being transacted by Alice.

Such a setup could be possible by storing successive roots of the transaction receipt trie on the market's contract.

However, being time and technically limited we do not provide an implementation here. Among other difficulties, we were not able to find ways to easily obtain merkle paths proving the inclusion of a transaction receipt within the transaction receipt trie - using an API similar to `eth_getProof`

on geth. We would have had to implement both this API and an efficient way to generate proofs of transaction receipt inclusion - similar to what Axiom did with Ethereum's state trie.

We were surprised since Ethereum's yellow paper explicitly mention that it might be interesting to generate zero-knowledge proofs pertaining to transaction receipts^{3}. Indeed, this setup would easily generalize from proving the execution of simple transactions to more complex contract interactions, aka *stealth interactions*.

Improving our setup

Our construction bears the risk of an actor spamming the market with ask orders that he knows he won't be able to fill. Three mechanisms could be used to prevent this: gate the ask with the provision of a proof that the buyer knows the data which resolves to the property, slashing rules where the asker can cancel his ask only by providing a corresponding proof and finally building a reputation protocol on top of the market.

We also detailed buyer-seller sequences requiring at most three different steps: an ask, an order and a fill. We should not however limit ourselves to this particular flow. One could imagine adding a step to enable buyers and sellers to privately communicate and/or commit to some additional piece of data.

In addition to this, our setup works today solely with escrowing ether. However, one could allow for all kinds of assets such as NFTs or ERC-20s to be used as escrow. There could also be a collective escrow setup where buyers pool ETH together. For instance, an on-chain game DAO team could pool together their ETH to buy a pricey cheatcode giving them an unfair decisive strategic advantage.

We also did not tackle the topic of nullyfing proofs. However, proof-gated apps that enable such schemes may need to think of ways to avoid proofs from being "double spent" within their protocol.

Technicalities

A seller of a groth16 proof will have to incur a non-negligible cost from calldata. We did not work on implementing a compressed proof representation which may help us reduce such costs. This also points out that this setup will demand succinctness if it were to be adopted by an average everyday Ethereum user, with the encrypted data being posted on-chain.

We have had to get beefy servers for generating zkeys and proofs^{4}. In general, the groth16 recursive proof cost is today prohibitive to be running on day-to-day machines. We would be excited to see teams working on making it possible to reach for the ability to recursively generate proofs on mobile devices, using proof schemes in the vein of Nova.

Acknowledgements

This work would not have been possible without all the help I received from the 0xPARC team.

Also, this work is heavily indebted to Nalin's work on recursivity.

Finally, I got a lot of ideas thanks to Enrico, Lakshman and Vivek. I thank them for their patience and intelligence, while I was taking them through the weeds of this project.