DLEQ.mediawiki

  BIP: TBD
  Title: Discrete Log Equality Proofs for ECDH shared secrets over secp256k1
  Author: Andrew Toth <andrewstoth@gmail.com>
          Ruben Somsen <rsomsen@gmail.com>
  Comments-URI: TBD
  Status: Draft
  Type: Standards Track
  License: BSD-2-Clause
  Created: 2024-06-29
  Post-History: TBD

Table of Contents Introduction Abstract Copyright Motivation Specification ECDH Shared Secret Generation DLEQ Proof Generation DLEQ Proof Verification Test Vectors and Reference Code Changelog Footnotes Acknowledgements

Introduction

Abstract

This document proposes a standard for 64-byte proofs for ECDH shared secrets over the elliptic curve secp256k1. For given public keys B and A, where A = a⋅G, and an ECDH shared secret C where C = a⋅B, the proof proves that the same secret key a is used for generating both A and C without revealing a.

Copyright

This document is licensed under the 2-clause BSD license.

Motivation

BIP352 requires senders to compute output scripts using ECDH shared secrets from the same secret keys used to sign the inputs. While generating an invalid signature will produce an invalid transaction, generating an invalid output script will produce a valid transaction but sending funds to the wrong output scripts. The entity responsible for broadcasting a signed transaction might not have access to the secret keys, and therefore won't be able to verify that the output scripts are generated correctly. By producing a DLEQ proof for the generated ECDH shared secrets, the signing entity can prove to other entities that the output scripts have been generated correctly without revealing the private keys.

Specification

All conventions and notation are used as defined in BIP340.

ECDH Shared Secret Generation

Input:

• The secret key a: a 256-bit unsigned integer
• The public key B: a point on the curve

The algorithm ECDHSharedSecret(a, B) is defined as:

• Fail if a = 0 or a ≥ n.
• Fail if is_infinite(B).
• Return bytes(a⋅B).

DLEQ Proof Generation

Input:

• The secret key a: a 256-bit unsigned integer
• The public key B: a point on the curve
• Auxiliary random data r: a 32-byte array

The algorithm Prove(a, B, r) is defined as:

• Fail if a = 0 or a ≥ n.
• Fail if is_infinite(B).
• Let A = a⋅G.
• Let C = a⋅B.
• Let a' = a if has_even_y(A), otherwise let a' = n - a.
• Let t be the byte-wise xor of bytes(a') and hash_BIP0TBD/aux(r).
• Let rand = hash_{BIP0TBD/nonce}(t || bytes(A) || Bytes(C)).
• Let k' = int(rand) mod n.
• Fail if k' = 0.
• Let R₁ = k'⋅G.
• Let R₂ = k'⋅B.
• Let k = k' if has_even_y(R₁), otherwise let k = n - k' .
• Let e = int(hash_{BIP0TBD/proof}(bytes(R₁) || bytes(R₂) || bytes(A) || bytes(C))) mod n.
• Let proof = e || bytes((k + ea') mod n).
• If VerifyProof(A, B, bytes(C), proof) (see below) returns failure, abort.
• Return the proof proof.

DLEQ Proof Verification

Input:

• The public key of the secret key used in the shared secret derivation A: a point on the curve
• The public key used in the shared secret derivation B: a point on the curve
• The shared secret c: a 32-byte array
• A proof proof: a 64-byte array

The algorithm VerifyProof(A, B, c, proof) is defined as:

• Let C = lift_x(int(c)); fail if that fails.
• Let e = int(proof[0:32]); fail if e ≥ n.
• Let s = int(proof[32:64]); fail if s ≥ n.
• Let R₁ = s⋅G - e⋅A.
• Fail if is_infinite(R₁).
• Fail if not has_even_y(R₁).
• Let R₂ = s⋅B - e⋅C.
• Fail if is_infinite(R₂).
• Fail if not has_even_y(R₂).
• Fail if e ≠ int(hash_{BIP0TBD/proof}(bytes(R₁) || bytes(R₂) || bytes(A) || bytes(C))) mod n.
• Return success iff no failure occurred before reaching this point.

Test Vectors and Reference Code

TBD

Changelog

TBD

Footnotes

Acknowledgements

TBD

nit: I wouldn't even mention ECDH in the abstract and the title. At least the way I think about this is that it proves just a multiplication of a scalar with a point. So it's at the EC math layer, and not at the "cryptographic primitive" layer. ECDH (as a key exchange!) is one primitive you can build from multiplication, but there are many others. (Of course, this is more of a philosophical difference.) "ECDH Shared Secret Generation" could just go away then.

Here's a suggestion along these lines, feel free to use it/change it/steal from it:

This document proposes a standard for 64-byte zero-knowledge discrete logarithm equality proofs (DLEQ proofs) over the elliptic curve secp256k1. For given elliptic curve points A, B, and C, the prover proves knowledge of a scalar a such that A = a⋅G and C = a⋅B without revealing anything about a. This can, for instance, be useful in ECDH: if A and B are ECDH public keys, and C is their ECDH shared secret computed as C = a⋅B, the proof establishes that the same secret key a is used for generating both A and C without revealing a.