BIP 374: Discrete Log Equality Proofs

0374 - Draft - Standards - Dec. 26, 2024 (1 year, 6 months ago)

Number
374
Status
Draft
Type
Standards
Created
Dec. 26, 2024
License
BSD-2-Clause

December

26

2024

  BIP: 374
Layer: Applications
Title: Discrete Log Equality Proofs
Author: Andrew Toth <[email protected]>
Ruben Somsen <[email protected]>
Sebastian Falbesoner <[email protected]>
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP 374
Status: Draft
Type: Standards Track
Created: 2024-12-26
License: BSD-2-Clause
Post-History: https://gist.github.com/andrewtoth/df97c3260cc8d12f09d3855ee61322ea
https://groups.google.com/g/bitcoindev/c/MezoKV5md7s

Introduction

Abstract

This document proposes a standard for 64-byte zero-knowledge discrete logarithm equality proofs (DLEQ proofs) over an elliptic curve. For given elliptic curve points A , B , C , G , and a scalar a known only to the prover where A = a⋅G and C = a⋅B , the prover proves knowledge of a 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 .

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

Motivation

BIP 352 requires senders to compute output scripts using ECDH shared secrets from the same secret keys used to sign the inputs. Generating an incorrect signature will produce an invalid transaction that will be rejected by consensus. An incorrectly generated output script can still be consensus-valid, meaning funds may be lost if it gets broadcast. 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 notations are used as defined in BIP 327 .

Description

The basic proof generation uses a random scalar k , the secret a , and the point being proven C = a⋅B .

  • Let R 1 = k⋅G .
  • Let R 2 = k⋅B .
  • Let e = hash(R 1 || R 2 ) .
  • Let s = (k + e⋅a) .

Providing only C , e and s as a proof does not reveal a or k .

Verifying the proof involves recreating R 1 and R 2 with only e and s as follows:

  • Let R 1 = s⋅G - e⋅A .
  • Let R 2 = s⋅B - e⋅C .

This can be verified by substituting s = (k + e⋅a) :

  • s⋅G - e⋅A = (k + e⋅a)⋅G - e⋅A = k⋅G + e⋅(a⋅G) - e⋅A = k⋅G + e⋅A - e⋅A = k⋅G .
  • s⋅B - e⋅C = (k + e⋅a)⋅B - e⋅C = k⋅B + e⋅(a⋅B) - e⋅C = k⋅B + e⋅C - e⋅C = k⋅B .

Thus verifying e = hash(R 1 || R 2 ) proves the discrete logarithm equivalency of A and C .

DLEQ Proof Generation

The following generates a proof that the result of a⋅B and the result of a⋅G are both generated from the same scalar a without having to reveal a .

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 1
  • The generator point G : a point on the curve 2
  • An optional message m : a 32-byte array 3

The algorithm GenerateProof(a, B, r, G, m) is defined as:

  • Fail if a = 0 or a ≥ n .
  • Fail if is_infinite(B) .
  • Let A = a⋅G .
  • Let C = a⋅B .
  • Let t be the byte-wise xor of bytes(32, a) and hash BIP 374/aux (r) .
  • Let m' = m if m is provided, otherwise an empty byte array .
  • Let rand = hash BIP 374/nonce (t || cbytes(A) || cbytes(C) || m') . 4
  • Let k = int(rand) mod n .
  • Fail if k = 0 .
  • Let R 1 = k⋅G .
  • Let R 2 = k⋅B .
  • Let e = int(hash BIP 374/challenge (cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R 1 ) || cbytes(R 2 ) || m')) .
  • Let s = (k + e⋅a) mod n .
  • Let proof = bytes(32, e) || bytes(32, s) .
  • If VerifyProof(A, B, C, proof) (see below) returns failure, abort.
  • Return the proof proof .

DLEQ Proof Verification

The following verifies the proof generated in the previous section. If the following algorithm succeeds, the points A and C were both generated from the same scalar. The former from multiplying by G , and the latter from multiplying by B .

Input:

  • The public key of the secret key used in the proof generation A : a point on the curve
  • The public key used in the proof generation B : a point on the curve
  • The result of multiplying the secret and public keys used in the proof generation C : a point on the curve
  • A proof proof : a 64-byte array
  • The generator point used in the proof generation G : a point on the curve 5
  • An optional message m : a 32-byte array 6

The algorithm VerifyProof(A, B, C, proof, G, m) is defined as:

  • Fail if any of is_infinite(A) , is_infinite(B) , is_infinite(C) , is_infinite(G)
  • Let e = int(proof[0:32]) .
  • Let s = int(proof[32:64]) ; fail if s ≥ n .
  • Let R 1 = s⋅G - e⋅A .
  • Fail if is_infinite(R 1 ) .
  • Let R 2 = s⋅B - e⋅C .
  • Fail if is_infinite(R 2 ) .
  • Let m' = m if m is provided, otherwise an empty byte array .
  • Fail if e ≠ int(hash BIP 374/challenge (cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R 1 ) || cbytes(R 2 ) || m')) .
  • Return success iff no failure occurred before reaching this point.

Backwards Compatibility

This proposal is compatible with all older clients.

Test Vectors and Reference Code

A reference python implementation is included here . Test vectors can be generated by running ./bip-0374/gen_test_vectors.py which will produce a CSV file of random test vectors for both generating and verifying proofs. These can be run against the reference implementation with ./bip-0374/run_test_vectors.py .

Changelog

  • 0.2.0 (2025-02-27):
    • Add the message to the rand computation
  • 0.1.0 (2024-12-26):
    • Initial version

Footnotes

Acknowledgements

Thanks to josibake, Tim Ruffing, benma, stratospher, waxwing, Yuval Kogman and all others who participated in discussions on this topic.

  1. Why include auxiliary random data? The auxiliary random data should be set to fresh randomness for each proof. The same rationale and recommendations from BIP 340 should be applied. ↩︎
  2. Why include the generator point G as an input? While all other BIPs have used the generator point from secp256k1, passing it as an input here lets this algorithm be used for other curves. ↩︎
  3. Why include a message as an input? This could be useful for protocols that want to authorize on a compound statement, not just knowledge of a scalar. This allows the protocol to combine knowledge of the scalar and the statement. ↩︎
  4. Why include the message in the rand computation? Not including the message in the rand computation could leak a if two proofs were constructed for the same a , B , and G but a different message m and an all-zero r . ↩︎
  5. Why include the generator point G as an input? While all other BIPs have used the generator point from Secp256k1, passing it as an input here lets this algorithm be used for other curves. ↩︎
  6. Why include a message as an input? This could be useful for protocols that want to authorize on a compound statement, not just knowledge of a scalar. This allows the protocol to combine knowledge of the scalar and the statement. ↩︎

View on GitHub

Authors

Ruben Somsen

Andrew Toth

Sebastian Falbesoner