DLEQ.mediawiki

  BIP: ?
  Title: Discrete Log Equality Proofs over secp256k1
  Author: Andrew Toth <andrewstoth@gmail.com>
          josibake <josibake@protonmail.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 DLEQ Proof Generation DLEQ Proof Verification Test Vectors and Reference Code Changelog Footnotes Acknowledgements

Introduction

Abstract

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.

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.

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 t be the byte-wise xor of bytes(a) and hash_BIP?/aux(r).
• Let rand = hash_BIP?/DLEQ(t || bytes(A) || Bytes(C)).
• Let k = int(rand) mod n.
• Fail if k = 0.
• Let R₁ = k⋅G.
• Let R₂ = k⋅B.
• Let e = int(hash_BIP?/DLEQ(bytes(A) || bytes(B) || bytes(C) || bytes(R₁) || bytes(R₂))).
• 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 proof generation A: a point on the curve
• The public key used in the proof generation B: a point on the curve
• The X coordinate of the result of multiplying the secret and public keys used in the proof generation 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]).
• 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_BIP?/DLEQ(bytes(A) || bytes(B) || bytes(C) || bytes(R₁) || bytes(R₂))).
• 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.

I was pointed to https://github.com/discreetlogcontracts/dlcspecs/blob/master/ECDSA-adaptor.md#proof-of-discrete-logarithm-equality, a DLEQ spec as part of Discreet Log Contracts. It's even implemented in https://github.com/BlockstreamResearch/secp256k1-zkp/blob/6152622613fdf1c5af6f31f74c427c4e9ee120ce/src/modules/ecdsa_adaptor/dleq_impl.h... Sorry, I don't know why I didn't recall this.

The other spec is a bit less precise because it doesn't talk about parsing etc.... In the implementation, parsing is done in https://github.com/BlockstreamResearch/secp256k1-zkp/blob/6152622613fdf1c5af6f31f74c427c4e9ee120ce/src/modules/ecdsa_adaptor/main_impl.h#L30 as part of the adaptor sig. Interestingly, overflow of e is ignored, though that shouldn't make a difference in practice because one shouldn't be able to find an e-overflowing but otherwise valid proof. So this may just be compatible to your draft if you adopt the other hash tag, and we could even change the e overflow in the code to make the implementation fully compliant with it.

I'm not sure what this means for this document here. The possibility to refer to an existing spec is also attractive. But I also don't think it makes this document useless, and I still think having this as a standalone BIP has non-zero benefit.

@real-or-random thank you for the links! I was just implementing this in secp256k1, this would have saved me some time 😅. But it was a good learning experience.

I will think about how to proceed.

I successfully made a DLEQ proof and verification for a silent payment using the dleq_impl.h implementation of secp256k1-zkp. That implementation seems to fit very well.

@real-or-random I quickly exposed the internal dleq_impl.h functions in BitBoxSwiss/secp256k1-zkp@a361bdc for our use. I guess it would be best if they could be ported to a new module in https://github.com/bitcoin-core/secp256k1/ (cc @josibake), or expose them in secp256k1-zkp like I did.

About compatibility of dleq_impl.h with the above draft:

• The dleq_impl.h implementation uses a slightly different hash to construct e apart from the tag: different order of the pubkeys, and the other base is also included.
• No negation in dleq_impl.h to make the Y coordinate even. @andrewtoth what's the reason for the negations in your draft?

I removed overflow of e, and added the other base in the proof hash. But, I don't think I can make it exactly the same as the zkp implementation, since they're hashing the 33 byte points and mine does the bip340 bytes(P) which does bytes(x(P)). I also will add the BIP number to the tags.

No negation in dleq_impl.h to make the Y coordinate even. @andrewtoth what's the reason for the negations in your draft?

@benma thanks for noticing, I'm not sure so I removed it.

I removed overflow of e, and added the other base in the proof hash. But, I don't think I can make it exactly the same as the zkp implementation, since they're hashing the 33 byte points and mine does the bip340 bytes(P) which does bytes(x(P)).

Serializing all points as x-only seems strange, is there a good reason for that? If not, could e.g. use the cbytes(P) function from BIP327 (https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#user-content-Notation) to serialize points as 33 bytes, and, if really needed xbytes(P) for 32-byte serialization (I strongly suspect that there is no need for the latter though, not even in the context of Silent Payments; the shared secret is an intermediate value that doesn't directly correspond to a taproot output yet, IIUC). Then the BIP should pretty much match the DLEQ implementation in secp256k1-zkp.

I'd also suggest to use the bytes(n, x) function (also defined in BIP327) for serializing scalars for better clarity. The proof serialization line would then look like:

• Let proof = bytes(32, e) || bytes(32, (k + ea) mod n).

The X coordinate of the result of multiplying the secret and public keys used in the proof generation c: a 32-byte array

This could also just be a "point on the curve", i.e. uppercase C? Then the lift_x step can be dropped, and it's less confusing, as lowercase c implies that this is the scalar (the discrete log of C).

@andrewtoth I was gonna ask the same - why not just use the 33 byte serialization?

@andrewtoth Looking good!

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.

Could be worded more clearly (and replaced "invalid" with "incorrect", as technically it could still result in a valid albeit unintended output). Maybe something like this:

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.

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.

I'm not sure this makes practical sense. Generally the private keys are only stored on one device, so there is no practical scenario where a device might verify the result with a private key. Leaving this sentence out seems better.

All conventions and notation are

notations

Let rand = hashBIP?/DLEQ(t || bytes(A) || Bytes(C))

Wondering if defining this deterministically isn't too restrictive since deterministic randomness isn't secure in multi-party signing (except with something like MuSig-DN), though perhaps a footnote is sufficient as multi-party signing is already a departure from what is described in this BIP

@theStack thanks for pointing me to BIP327 notations and conventions, those will work better here I think.

The X coordinate of the result of multiplying the secret and public keys used in the proof generation c: a 32-byte array

This could also just be a "point on the curve", i.e. uppercase C? Then the lift_x step can be dropped, and it's less confusing, as lowercase c implies that this is the scalar (the discrete log of C).

I see, yes. I believe in the silent payments PSBT BIP I specified the ECDH share to be only 32 bytes, but it seems that it must also be 33 bytes there as well.

Thanks for all your feedback! I've made a PR to the BIPs repo so we can continue discussion there bitcoin/bips#1689.