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

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.

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¹.

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:

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.

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.

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 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.

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.

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 PCD2 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.

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:

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.

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.

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³. Indeed, this setup would easily generalize from proving the execution of simple transactions to more complex contract interactions, aka stealth interactions.

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.

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⁴. 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.

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.

Footnotes

1. (1) See Nick Ulven's talk here. ↩

2. (2) Here, PCD is meant in a broader, dev-deformed way - rather than its academic definition. ↩

3. (3) Berlin version, p.6 ↩

4. (4): Read: "I blew up my AWS bills lol" ↩