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
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.
This document is licensed under the 2-clause BSD license.
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.
All conventions and notation are used as defined in BIP340.
Input:
- The secret key a: a 256-bit unsigned integer
- The public key B: a point on the curve
- Fail if a = 0 or a ≥ n.
- Fail if is_infinite(B).
- Return bytes(a⋅B).
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
- 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 hashBIP0TBD/aux(r).
- Let rand = hashBIP0TBD/nonce(t || bytes(A) || Bytes(C)).
- Let k' = int(rand) mod n.
- Fail if k' = 0.
- Let R1 = k'⋅G.
- Let R2 = k'⋅B.
- Let k = k' if has_even_y(R1), otherwise let k = n - k' .
- Let e = int(hashBIP0TBD/proof(bytes(R1) || bytes(R2) || 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.
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
- 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 R1 = s⋅G - e⋅A.
- Fail if is_infinite(R1).
- Fail if not has_even_y(R1).
- Let R2 = s⋅B - e⋅C.
- Fail if is_infinite(R2).
- Fail if not has_even_y(R2).
- Fail if e ≠ int(hashBIP0TBD/proof(bytes(R1) || bytes(R2) || bytes(A) || bytes(C))) mod n.
- Return success iff no failure occurred before reaching this point.
TBD
TBD
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.