Zero-knowledge key-statement proof

This post was first published on Medium.

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:

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

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:

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.

***

[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

Acknowledgements

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

Watch: CoinGeek New York presentation, Kensei: the Gateway to the Definitive Blockchain

Source: Read Full Article