Add DLEQ proof implementing BIP 374 #1802

This PR adds a DLEQ (Discrete Logarithm Equality) proof module as specified in BIP 374.

Based on [PR #1651](https://github.com/bitcoin-core/secp256k1/pull/1651) by @stratospher and the secp256k1-zkp implementation.

Public API

Exposes two functions for proof generation and verification:

• secp256k1_dleq_prove
• secp256k1_dleq_verify

These are designed to support rust FFI bindings and follow the API patterns established in similar modules.

Questions for Reviewers

• Should this module be optional (current behavior) or enabled by default?
• Are there additional changes needed to support existing Silent Payments PRs?
• Feedback on API design, documentation, and test coverage?

Notes

Addressed outstanding comments from [PR #1651](https://github.com/bitcoin-core/secp256k1/pull/1651#discussion_r2417300085):

• BIP-374 v0.2.0 test vectors
• Proper memory clearing with memclear

Have you talked with @stratospher before opening this PR? I don’t want to draw conclusions prematurely, but opening a parallel PR that implements the same changes without first engaging on the existing one by reviewing it, leaving a comment, or waiting for the author's public response is not how we usually collaborate in open source. The lack of (co)authorship on the commits is also unusual.

If you have contacted stratospher, please ignore this comment. It's just to avoid putting the original author in an unfair or difficult position if still working on the PR.

Have you talked with @stratospher before opening this PR?

Yes, stratospher and I had discussed who should submit this new PR. I drew the short straw :)

sorry for the confusion and thank you @macgyver13 for the PR!

did an initial pass and it looks good! mostly left style nits.

1 API design question I had is whether it would be better for the proof generation API to also accept C as an argument - that is GenerateProof(a, B, r, G, m, C) kind of API instead of GenerateProof(a, B, r, G, m).

When computing silent payment output points, we anyways compute shared secret/C for each output - so there's a possibility to avoid recomputation again if we can pass C. But current approach might be safer since callers could accidentally provide incorrect C and errors could happen.

Did you check other use cases of DLEQ for whether they might prefer passing C or computing C internally in the proof generation function?

I have a question regarding the choice of parameters passed to this API, and I may be missing some design context here — so I’d appreciate clarification. Is there a specific reason why the second generator B is provided directly as an input? @furszy In the original proposal of DLEQ proofs by Chaum and Pedersen [1], the correctness of the protocol relies on the prover not knowing the discrete‑log relation between the two generators. Specifically, if the prover knows a scalar b such that B=b⋅G, then the two equations for the verification are no longer distinct and will be dependent on each other. In the context of silent payments (and the description provided in BIP 374) this makes sense, since B represents another user’s public key — a point for which the prover does not know the corresponding private key. However, as commented by stratospher #1651 (comment) this PR is intended to support more general DLEQ use cases, I am concerned that allowing callers to supply an arbitrary B might introduce risks in scenarios where generator independence is not guaranteed.

Other constructions with two generators on the same curve (e.g., Pedersen commitments, bulletproofs) typically derive the second generator using a hash‑to‑curve procedure, ensuring that no participant knows the discrete‑log ratio between G and B. I was wondering whether a similar approach might help avoid potential misuse here, or whether this falls outside the intended scope of this PR. I would be very interested to hear your thoughts on this. [1] D. Chaum and T. P. Pedersen, Wallet Databases with Observers, 1992.
https://www.hsslb.ch/cryptopapers/other/Chaum_WalletDBswObservers.pdf

In the original proposal of DLEQ proofs by Chaum and Pedersen [1], the correctness of the protocol relies on the prover not knowing the discrete‑log relation between the two generators.

You probably mean soundness instead of correctness? If I'm not mistaken, this is simply not true. See for instance Nigel Smart's Cryptography: An Introduction (3rd Edition), Section 25.3.1, page 377, PDF page 389. This rather accessible write-up shows that the underlying Sigma protocol has correctness, 2-special soundness, and zero-knowledge, all with probability 1 and without any computational assumption. Technically, one doesn't even need the assumption that the discrete logarithm problem is hard in the group. Note in particular that the proof of special soundness extracts the witness and not the discrete logarithm between g and h (or G and B in our notation); the latter doesn't even show up in the proof.

Specifically, if the prover knows a scalar b such that B=b⋅G, then the two equations for the verification are no longer distinct and will be dependent on each other.

Can you elaborate and also explain why you believe that this requires the assumption that the prover doesn't know the discrete logarithm between G and B?

Thank you for the review @stratospher and appreciate the curious questions about the API!

1 API design question I had is whether it would be better for the proof generation API to also accept C as an argument - that is GenerateProof(a, B, r, G, m, C) kind of API instead of GenerateProof(a, B, r, G, m).

When computing silent payment output points, we anyways compute shared secret/C for each output - so there's a possibility to avoid recomputation again if we can pass C. But current approach might be safer since callers could accidentally provide incorrect C and errors could happen.

If we accept C as an input, I would suggest computing C internally to verify correctness before calling secp256k1_dleq_prove_internal. This would counter the optimization benefit. This is the approach I took when testing that variation of the API.

Did you check other use cases of DLEQ for whether they might prefer passing C or computing C internally in the proof generation function?

I am not well versed in other DLEQ use cases outside Silent Payments, so I surveyed related applications of Discrete Log Equivalence starting with Andrew Toth's BIP-374 review on the OpTech Podcast. Below you will find a list of reviewed use cases and my assessment of whether to require output points like C as input parameters to proof generation.

DLEQ implementations reviewed:

• Cashu NUT-12 - computes the blind signature C' internally as C' = a·B'
• JoinMarket PODLE - computes output point P2 internally as P2 = x·J
• Half-Adaptor (DLEQ with adaptors) - computes output points internally as Pₙ = x·Gₙ

Related protocols reviewed (not DLEQ-based):

• Curve Trees - anonymous usage tokens from curve trees
• RIDDLE - ring signatures (LSAG) with key images

I don't see a compelling reason to change the API based on these findings, but I'm open to different perspectives.

Thanks for your response and for the explanation.

You probably mean soundness instead of correctness?

Yes — thanks for the correction.

If I'm not mistaken, this is simply not true. See for instance Nigel Smart's Cryptography: An Introduction (3rd Edition), Section 25.3.1…

Agreed. I’ve encountered DLEQ mostly in other contexts, and in particular in scenarios involving DLEQ across two different curves. In those settings, Pedersen commitments are typically used, which require the independence of the two generators. Writing out the equations explicitly for the single-curve setting makes it clear that this independence assumption is not needed here, as you point out.

Can you elaborate and also explain why you believe that this requires the assumption that the prover doesn't know the discrete logarithm between G and B?

My reasoning was that the second verification equation (the one checking R₂ in this notation) is effectively just the first verification equation multiplied by b, due to how the parameters are constructed. This made me think that knowing the discrete logarithm between G and B might collapse the two checks.

Rebased on latest master and adapted the module to two API changes it introduced, no behavior changes.

• the pluggable SHA256 hash_ctx
• the ecmult_gen → ecmult_gen_ge split

Folded into the affected commits:

• dleq: add module structure and internal implementation
• dleq: add test framework and BIP-374 test vectors
• dleq: add public API wrappers

Thank you for the review @theStack! Your suggestions all made sense and I've applied them.

While I was reviewing your feedback I also made some additional changes based on the findings of several agentic review passes:

• Changed secp256k1_dleq_hash_point to return void. It always returned 1 and went unchecked by callers.
• Constant-time coverage: dleq_prove is now exercised in ctime_tests.c, and A/C are declassified as the proof's public statement. Invalid seckeys return early via secp256k1_scalar_set_b32_seckey + declassify, taking the same "constant-time only for valid inputs" approach as #1919. Re-ordered pubkey_load(B) ahead of the seckey parse in secp256k1_dleq_prove, so an invalid B returns before the secret scalar is loaded, removing the need to clear it on that path.
• Enabled the module by default in dev mode, so the release job's --enable-dev-mode distcheck builds it. Previously nothing in CI validated the module against the tarball.
• Extended the public API tests with message-binding cases in both directions.
• Rounded out failure-path coverage: zero nonces, infinity points, invalid pubkeys, scalar overflow.

Also rebased on master, and folded the earlier "Apply review feedback" commit into the commits it touched; the series is five commits now. If you spot any other improvements, let me know.

My last local rebase missed #1915, which moved these helpers to group.h and renamed them:

• secp256k1_eckey_pubkey_parse -> secp256k1_ge_parse_ext33
• secp256k1_eckey_pubkey_serialize33 -> secp256k1_ge_serialize_ext33

This was discussed in yesterday's IRC meeting:

08:39 < theStack> one topic i wanted to raise is dleq proofs and their scope within libsecp 08:40 < theStack> the main use case now would be users of silentpayments (pr #1651), but there is also an open pr with a dedicated module (pr #1802) 08:43 < real_or_random> hm it ticks the first two boxes here for sure https://github.com/bitcoin-core/secp256k1/blob/master/CONTRIBUTING.md#adding-new-functionality-or-modules 08:44 < real_or_random> relevance: well. it's used within SP but that is not an argument because then internal code would suffice. what are other use cases? 08:44 < real_or_random> I tend to think DLEQ is generic enough to be relevant. It came up in multiple contexts so far 08:45 < real_or_random> it's a middle-layer thing like ECDH. Not as useful as ECDH in terms of number of applications but there are a handful? (...) 08:50 < theStack> other than SP, i'm currently not aware of any concrete applications for DLEQs in the bitcoin ecosystem. i guess my preference is to extend the SP module with a create_outputs_with_proof function and not expose the DLEQ functions unless there are compelling use cases 01:47 < real_or_random> theStack: my thinking was that joinmarket needs DLEQ for example. #1802 has a short list. but sure, they all have their own implementations currently 01:48 < real_or_random> theStack: but agreed. not exposing it for now is the conservative thing. it can always be exposed if there's demand

Thanks for following up! Left some more small findings below, some of them quite pedantic (feel free to ignore if they seem too nit-picky). Seems like a rebase on master is also necessary due to #1908.

A few other notes:

• there is consensus that we prefer directly including the test vector source data from BIPs (the two .csv files in this case) in this repository, see e.g. #1698 (comment) and #1786
• the test vector generation script test_vectors_dleq_generate.py is missing the executable flag
• an entry in the features list of README.md is missing
• adding an example examples/dleq.c would be nice, but could still be done in a follow-up (thinking of how users would multiply with arbitrary points feels a bit "hazmat"-y though, they would need to abuse the pubkey tweaking function...)

As mentioned on IRC earlier today, I don't have a really strong opinion on whether it makes sense to fully expose the public API functions already now or not (curious what others think), but it certainly can't hurt to prepare for it.

Thanks @theStack for the detailed review and @real-or-random for relaying the meeting notes. Both of these are helpful context. I'll work through the review points and push an update to address your suggestions.

On scope: I've been reflecting on this today, and I've come round to thinking the safer and more pragmatic approach for BIP375 is a small set of silent payments functions, ahead of the two DLEQ primitives this PR exposes. They'd give wallet developers a more natural implementation boundary. Using the current two primitives leaves the developer to handle several BIP352 and BIP375 details themselves. That's related to your examples/dleq.c point, since an example can demonstrate the primitives but can't carry these rules for the caller:

• taproot even-Y negation on input keys
• the input_hash construction
• the k-ordering rule: group by scan key, order by spend key within the group, then by output index (the module groups by scan key today; handling the full ordering there would be ideal)

The shape follows from BIP375 having two forms of share/proof, a global one over every eligible input key and a per-input one, plus a verifier holding no key for the inputs it checks and a combiner holding none at all. Listed below in order of how much key material the caller holds, starting with @stratospher's existing function for context:

/* Signer holding EVERY eligible input key, on one device:
 * derive the outputs and the global share/proof together, sharing the single ECDH
 * per unique scan key that both steps need. This is [#1651](/bitcoin-core-secp256k1/1651/)'s existing function,
 * shown with master's parameter naming. Would fill PSBT_GLOBAL_SP_ECDH_SHARE / _DLEQ,
 * from dleq_data, subject to the question below the block. */
int secp256k1_silentpayments_sender_create_outputs_with_proof(
    const secp256k1_context *ctx,
    secp256k1_xonly_pubkey **generated_outputs,
    secp256k1_silentpayments_dleq_data **dleq_data,
    size_t *n_dleq_size,
    const secp256k1_silentpayments_recipient **recipients,
    size_t n_recipients,
    const unsigned char *outpoint_smallest36,
    const secp256k1_keypair * const *keypairs,
    size_t n_keypairs,
    const unsigned char * const *seckeys,
    size_t n_seckeys
);

/* Signer creates the ECDH share and DLEQ proof for ONE scan key. Derives no outputs,
 * so a caller holding only some of the eligible input keys can still contribute its
 * share to a transaction it cannot complete alone.
 *
 * The share is computed over the sum of whatever keys are passed, and that choice
 * decides which PSBT field the result belongs in:
 *   all eligible input keys -> global share  -> PSBT_GLOBAL_SP_ECDH_SHARE / _DLEQ
 *   one input's key         -> that input's  -> PSBT_IN_SP_ECDH_SHARE / _DLEQ
 *
 * Which mode to use is the caller's decision: BIP375 allows a signer holding every key
 * to still choose per-input ("or does not want to create a global ECDH share").
 *
 * Call once per scan key in global mode; once per (input, scan key) pair in per-input
 * mode. Keys passed via keypairs are treated as taproot inputs and even-Y negated
 * before summing as in _sender_create_outputs. */
int secp256k1_silentpayments_sender_create_share_and_proof(
    const secp256k1_context *ctx,
    unsigned char *share33,
    unsigned char *proof64,
    const secp256k1_pubkey *recipient_scan_pubkey,
    const unsigned char *aux_rand32,
    const secp256k1_keypair * const *keypairs,
    size_t n_keypairs,
    const unsigned char * const *seckeys,
    size_t n_seckeys
);

/* Signer verifying shares it did NOT create, holding no key for those inputs:
 * BIP375 assigns this to the party that verifies proofs "for all inputs it does
 * not have the private keys for".
 * One pubkey for the per-input case, all of them for the global case. */
int secp256k1_silentpayments_verify_share_proof(
    const secp256k1_context *ctx,
    const unsigned char *share33,
    const unsigned char *proof64,
    const secp256k1_pubkey *recipient_scan_pubkey,
    const secp256k1_xonly_pubkey * const *xonly_pubkeys,
    size_t n_xonly_pubkeys,
    const secp256k1_pubkey * const *pubkeys,
    size_t n_pubkeys
);

/* Transaction Extractor, holding NO secret keys at all:
 * compute output scripts from shares supplied by others. This is the case
 * _sender_create_outputs_with_proof cannot cover, since it requires the seckeys
 * in order to derive the outputs itself.
 * Takes one already-summed share per scan key, keyed by share_scan_pubkeys, so a
 * caller holding per-input shares combines them first.
 * Input pubkeys for every eligible input are needed, since input_hash commits
 * to their sum. */
int secp256k1_silentpayments_sender_create_outputs_from_shares(
    const secp256k1_context *ctx,
    secp256k1_xonly_pubkey **generated_outputs,
    const secp256k1_silentpayments_recipient **recipients,
    size_t n_recipients,
    const unsigned char *outpoint_smallest36,
    const secp256k1_pubkey * const *share_scan_pubkeys,
    const unsigned char * const *shares33,
    size_t n_shares,
    const secp256k1_xonly_pubkey * const *xonly_pubkeys,
    size_t n_xonly_pubkeys,
    const secp256k1_pubkey * const *pubkeys,
    size_t n_pubkeys
);

A sender holding every key should keep using the first, unchanged in shape, since deriving outputs and proofs together shares the one ECDH per unique scan key that both need. The other three are illustrative. The last one keys each share by its scan pubkey, matching how BIP375 keys the share fields themselves.

One question came out of reading #1651 to work out how the above would fit alongside it. In sender_create_outputs_with_proof, seckey_sum_scalar is multiplied by input_hash before create_shared_secret_with_proof is called, so the value that ends up as the DLEQ secret is input_hash·a_n rather than a_n. The proof is then a statement about input_hash·a_n, and the stored shared_secret is input_hash·a_n·B_scan.

If I'm reading BIP375 correctly, the value it wants in PSBT_GLOBAL_SP_ECDH_SHARE is a_n·B_scan, with the proof over a_n and input_hash applied afterwards during output computation, so a proof made the other way wouldn't verify against A_n. Am I missing a reason it's folded in earlier? I can see why it happens in master's sender_create_outputs, where the comment at main_impl.h:277 notes that multiplying the scalars first saves an elliptic curve multiplication and nothing observable depends on the ordering, so I assume it carried over naturally once proofs were added.

For what it's worth, create_shared_secret_with_proof itself looks agnostic here: handed a_n it would produce C = a_n·B_scan and A = a_n·G directly. So if this does want changing for BIP375, it looks like the caller rather than the proof code. @theStack once you've had a chance to look at these signatures we can work out who's best placed to integrate them into the silent payments module. I can see a future where both the silent payments functions and the DLEQ primitives are useful.

I am still in the exploratory phases of new work that combines MuSig2 and Silent Payments and uses the existing DLEQ API. Of the four above, only the combiner _sender_create_outputs_from_shares carries over to that case; share creation and verification still want the generic DLEQ pair. Once that work is ready for critique I can share it for review.

@macgyver13: Thanks for your thoughts and the API proposal! Since this PR is focusing on the generic DLEQ module and could be useful for non-SP use-cases as well, I've opened a SP-specific issue for further discussion (with emphasis on what I think main use-case for DLEQs in SP nowadays, i.e. verification of created outputs), where I will reply in more detail to your post within the next days: https://github.com/bitcoin-core/secp256k1/issues/1925

Mutation testing report for this PR is available at: https://secp256k1.space/pull/1802

Thanks again @theStack. All of your review points were applied to the original commit series. I did not provide a dleq.c example in this update - still on my todo list.

Additionally, included test_vectors_generate_proof.csv and test_vectors_verify_proof.csv, this required modifying .gitignore to explicitly allow *.csv files from /src/modules/dleq/.

Rebased on master and adapted to #1908 (direct ->hash_ctx access).

Verified generator produced same output after G point check instead of relying on row count (no diff):

./tools/test_vectors_dleq_generate.py src/modules/dleq | git diff --no-index -- - src/modules/dleq/dleq_vectors.h

Left some more smaller findings below, and added the "needs changelog" label.