# Zero-Knowledge Key-Statement Proof

nChain white paper #0488 titled ** Zero-knowledge key-statement proofs** introduces a zero-knowledge proof (ZKP) that proves a private key, corresponding to a given public key, satisfies certain requirements, while keeping the private key confidential. We have implemented it and applied it to purchasing bitcoin vanity address trustlessly. It can be generalized to a wide range of applications, where secret information can be purchased between mutually distrusting parties without a trusted third party.

# Zero-Knowledge Key-Statement Proof

As we have introduced before, a zero-knowledge proof lets one party convince another party that he knows a secret validating a statement, whilst not revealing the secret.

A zero-knowledge key-statement proof (ZKKSP) is a special type of ZKP where the secret is a private key corresponding to a known public key. The private key satisfies additional constraints, such as hashing to a given value.

The nChain white paper introduces an efficient approach for ZKKSP. Compared with zero-knowledge proofs for general statements such as zk-SNARKS, ZKKSP enjoys several salient advantages:

- ZKKSP does not require a trusted setup, an issue that some (e.g. pairing based) zk-SNARKS suffers from.
- Key-statement proof in zk-SNARKS requires an elliptic curve multiplication circuit, resulting in extremely computationally demanding proof generation and excessively large proof size on the prover side. By contrast, ZKKSP removes the circuit by:

- Working in the same ECDSA elliptic curve than the public key is in
- Checking consistency between the public key and the generated zk-proof; specifically, checking consistency against commitments embedded in the zk-proof¹.

In ZKP, a statement/computation is usually encoded in an arithmetic circuit, consisting of addition and multiplication gates. As Figure 1 shows, zk-SNARKS contains sub-circuits for both a hash function and elliptic curve multiplication. The later circuit checks consistency against the known ECDSA public key. ZKKSP only employs the hash circuit and removes the other circuit, which is at least an order of magnitude larger than the former. Interested readers can refer to the white paper for more details, which we omit here due to space limit.

# Implementation

We fork an existing library called ZoKrates to generate the arithmetic circuit for SHA256. After modifying the circuit format, we implement the rest of key-statement proof as laid out in the white paper.

## ZoKrates

ZoKrates⁴ is a toolbox for zkSNARKs on Ethereum. It consists of a domain-specific language, a compiler, and generators for proofs and verification smart contracts. Below is a source program written in ZoKrates that checks ** sha256(preimage) == h**⁵.

## Workflow

The prover runs the following commands sequentially to generate a proof.

The prover sends the generated proof in ** proof.json** to the verifier. The verifier runs the following command to check if the public key matches the hash value. Note this proof is non-interactive and does not require interaction between the prover and verifier, thanks to the Fiat-Shamir heuristic.

You can find the complete code at our Github.

# Application: Outsourced Vanity Address Generation

This section describes applying ZKKSP to outsourcing bitcoin vanity address generation.

Since searching for a vanity address can be computationally expensive, it is common for the search to be outsourced. Traditionally, either the buyer gets the required value before the seller gets paid, or the seller gets paid before releasing the required value, or they must both trust an escrow service. By employing ZKKSP, the sale of a vanity address can be made trustless.

The protocol for this is detailed as follows.

1. The Buyer and Seller agree on the required vanity pattern and the price (in BSV), and establish a communication channel (which does not need to be secure).

2. The buyer generates a secure random secret key ** sk_B** and corresponding elliptic curve public key

*pk_B = sk_B * G*3. The buyer sends ** pk_B **to the seller.

4. The seller then performs a search for the required pattern in the Base58 encoded address derived from ** pk = pk_B + i * G** by changing

**.**

*i*5. When an address with the required pattern is found, the seller saves the value , signals to the buyer and sends them ** pk_S = i * G** and the SHA256 hash .

6. The seller also provides a ZKKSP to the buyer that the pre-image to is the private key corresponding to ** pk_S**.

7. The buyer verifies the proof, and also confirms that the address ** pk = pk_B + pk_S** corresponding to matches the agreed pattern. At this point (by virtue of the proof), the buyer

*knows*that learning the value

**will enable him derive the full private key for the vanity address (**

*i***), and that particular value hashes to**

*sk_B + i***.**

*h = H(i)*8. The buyer then constructs a hash-time-locked contract (HTLC) transaction ** Tx_1** which contains an output that contains the agreed fee. This output can be unlocked in in two ways:

i. With a signature from the seller and the hash pre-image, ** i**, at any time.

ii. With a signature from the buyer after a specified time (OP_CLTV⁶)

9. The buyer then signs and broadcasts this transaction to the blockchain, where it is mined into a block.

10. Once confirmed, the seller can claim the fee in the output of ** Tx_1 **by providing a transaction

**supplying their signature and the value**

*Tx_2***to unlock the hash-lock, which is then revealed on the blockchain.**

*i*11. The buyer calculates the final vanity address private key ** sk = sk_B + i**, where

*pk = sk * G*12. If the seller fails to supply the value ** i** before a specified OP_CLTV time, then the buyer can provide their signature to re-claim the fee (to prevent the fee being lost due to an uncooperative buyer).

The exchange is fully atomic and trustless, meaning the buyer only gets paid if he provides a valid secret value ** 𝑖** which is revealed publicly on the blockchain. Furthermore, the full private key is not known even to the seller, due to the splitting of the private key.

# Summary

We have shown how to prove key statement, in which the secret private key hashes to a given value. While primitive at first glance, ZKKSP is extremely powerful to enable many atomic fair exchanges in two general steps:

- Seller proves to buyer using ZKKSP that he knows a secret the latter needs and it hashes to a given value;
- The buyer sets up a smart contract that only pays out if the hash preimage is given.

Note step 1 is done **off chain** and can be computationally intensive, while step 2 is **on chain** and extremely light weight.

The same technique can be applied to demand the private key satisfies other requirements (i.e., circuits), such as starting or ending with a given pattern.

# Acknowledgements

This is a joint work between nChain Limited and sCrypt Inc.

[1] These can be achieved either with a non-succinct proof system for circuit satisfiability or with a discrete-log based SNARK. We have implemented the former.

[2] Internal gates are for illustrative purposes only — the real circuits would have 1000s of gates.

[3] The circuit checks that the output of the hash is equal to the EC public key: the values highlighted in blue are revealed to the verifier, all other values are encrypted.

[4] ZoKrates — Scalable Privacy-Preserving Off-Chain Computations, 2018

[5] Both ** preimage** and

**h**are divided into two parts, since basic type

**field**cannot accommodate 256 bits.

[6] “OP_CLTV” on BSV