BIP374: Discrete Log Equality Proofs (DLEQ)

andrewtoth commented at 1:47 am on October 24, 2024: contributor

This BIP specifies a standard way to generate and verify DLEQ proofs. This is motivated by sending to silent payments in PSBTs. However, there are also other uses where DLEQs could be useful, so it would be good to have this BIP for others to reference.

This is inspired by https://github.com/discreetlogcontracts/dlcspecs/blob/master/ECDSA-adaptor.md#proof-of-discrete-logarithm-equality, but is a little more specific. There is an implementation of that already at https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master/src/modules/ecdsa_adaptor/dleq_impl.h, which this BIP attempts to be compatible with.

Inital ML post: https://groups.google.com/g/bitcoindev/c/MezoKV5md7s

andrewtoth commented at 4:14 pm on October 24, 2024: contributor

There was some previous discussion on this gist before making this PR https://gist.github.com/andrewtoth/df97c3260cc8d12f09d3855ee61322ea

in bip-DLEQ.mediawiki:46 in 2aab0766e3 outdated

41+* Fail if ''a = 0'' or ''a &ge; n''.
42+* Fail if ''is_infinite(B)''.
43+* Let ''A = a⋅G''.
44+* Let ''C = a⋅B''.
45+* Let ''t'' be the byte-wise xor of ''bytes(32, a)'' and ''hash<sub>BIP?/aux</sub>(r)''.
46+* Let ''rand = hash<sub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.

theStack commented at 5:09 pm on October 24, 2024:

typo

0* Let ''rand = hash<sub>DLEQ</sub>(t || cbytes(A) || cbytes(C))''.

andrewtoth commented at 3:24 am on November 3, 2024:

Fixed.

in bip-DLEQ.mediawiki:69 in 2aab0766e3 outdated

64+The algorithm ''VerifyProof(A, B, C, proof)'' is defined as:
65+* Let ''e = int(proof[0:32])''.
66+* Let ''s = int(proof[32:64])''; fail if ''s &ge; n''.
67+* Let ''R<sub>1</sub> = s⋅G - e⋅A''.
68+* Fail if ''is_infinite(R<sub>1</sub>)''.
69+* Fail if ''not has_even_y(R<sub>1</sub>)''.

theStack commented at 5:17 pm on October 24, 2024:

that seems not necessary and would make roughly every second (valid) proof verification fail (probably a leftover from a previous variant where x-only pubkeys were used?), same as two lines below

andrewtoth commented at 3:24 am on November 3, 2024:

Removed.

jonatack renamed this:
~~Bip Draft: DLEQ~~
Bip Draft: Discrete Log Equality Proofs (DLEQ)
on Oct 24, 2024

jonatack added the label New BIP on Oct 24, 2024

in bip-DLEQ.mediawiki:82 in 2aab0766e3 outdated

75+
76+== Test Vectors and Reference Code ==
77+
78+TBD
79+
80+== Changelog ==

jonatack commented at 8:31 pm on October 24, 2024:

Maybe add a section on backwards compatibility, run git grep -A2 Backward on the repo root for ideas.

andrewtoth commented at 3:28 am on November 3, 2024:

Not sure there’s anything to be backwards compatible with? This would be a new standard? Perhaps it could discuss compatibility with https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master/src/modules/ecdsa_adaptor/dleq_impl.h or any other widely used implementations (Joinmarket)?

jonatack commented at 5:49 pm on November 8, 2024:

Perhaps

0==Backwards Compatibility==
1
2This proposal is compatible with all older clients.

Perhaps it could discuss compatibility with BlockstreamResearch/secp256k1-zkp@master/src/modules/ecdsa_adaptor/dleq_impl.h or any other widely used implementations (Joinmarket)?

Yes, it might be useful to add in a Compatibility section (perhaps somewhat like BIP197) with respect to those.

0==Compatibility==
1
2BIP 197 is compatible with [https://github.com/ethereum/EIPs/pull/1850 ERC 1850] for [https://arxiv.org/pdf/1901.05117.pdf atomic loans] with Ethereum. Can be extended in the future to be compatible with other HTLC and smart contract compatible chains.

andrewtoth commented at 7:01 pm on December 9, 2024:

Added your suggestion.

in bip-DLEQ.mediawiki:3 in 2aab0766e3 outdated

0@@ -0,0 +1,90 @@
1+<pre>
2+  BIP: ?
3+  Title: Discrete Log Equality Proofs over secp256k1

jonatack commented at 8:43 pm on October 24, 2024:

Consider adding Layer: Applications above this line (run git grep -C6 "Layer: Applications" on the repository for info).

andrewtoth commented at 3:24 am on November 3, 2024:

Added.

jonatack added the label PR Author action required on Oct 26, 2024

in bip-DLEQ.mediawiki:52 in 2aab0766e3 outdated

47+* Let ''k = int(rand) mod n''.
48+* Fail if ''k = 0''.
49+* Let ''R<sub>1</sub> = k⋅G''.
50+* Let ''R<sub>2</sub> = k⋅B''.
51+* Let ''e = int(hash<sub>DLEQ</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
52+* Let ''proof = bytes(32, e) || bytes(32, (k + ea) mod n)''.

theStack commented at 11:17 am on October 28, 2024:

pedantic nit: I think the s scalar deserves to be assigned explicitly before serialization, also to be symmetric to the verification part:

0* Let ''s = (k + e⋅a) mod n''.
1* Let ''proof = bytes(32, e) || bytes(32, s)''.

andrewtoth commented at 3:25 am on November 3, 2024:

Done.

in bip-DLEQ.mediawiki:51 in 2aab0766e3 outdated

46+* Let ''rand = hash<sub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.
47+* Let ''k = int(rand) mod n''.
48+* Fail if ''k = 0''.
49+* Let ''R<sub>1</sub> = k⋅G''.
50+* Let ''R<sub>2</sub> = k⋅B''.
51+* Let ''e = int(hash<sub>DLEQ</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.

theStack commented at 11:24 am on October 28, 2024:

for a consistent naming of the tagged hashes, could use the same scheme as in BIP0340, i.e.

“BIP0???/aux” (for calculating t)
“BIP0???/nonce” (for calculating k) and
“BIP0???/challenge” (for calculating e; used both in proof generation and verification).

andrewtoth commented at 3:25 am on November 3, 2024:

Done, although this breaks compatibility with https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master/src/modules/ecdsa_adaptor/dleq_impl.h. I’m not sure it’s feasible to be completely compatible with that implementation though.

in bip-DLEQ.mediawiki:40 in 2aab0766e3 outdated

33+=== DLEQ Proof Generation ===
34+
35+Input:
36+* The secret key ''a'': a 256-bit unsigned integer
37+* The public key ''B'': a point on the curve
38+* Auxiliary random data ''r'': a 32-byte array

stratospher commented at 2:58 pm on October 30, 2024:

is it recommended to use a different r every time? I guess there’s no risk of a being leaked with same r here.

andrewtoth commented at 3:29 am on November 3, 2024:

We could recommend this, perhaps as a footnote?

andrewtoth commented at 9:17 pm on December 21, 2024:

Added as a footnote, also linked to BIP340.

in bip-DLEQ.mediawiki:40 in 2aab0766e3 outdated

35+Input:
36+* The secret key ''a'': a 256-bit unsigned integer
37+* The public key ''B'': a point on the curve
38+* Auxiliary random data ''r'': a 32-byte array
39+
40+The algorithm ''Prove(a, B, r)'' is defined as:

stratospher commented at 3:18 pm on October 31, 2024:

micro-nit: maybe call it GenerateProof. (similar to VerifyProof below)

andrewtoth commented at 3:25 am on November 3, 2024:

Done.

Bip Draft: DLEQ 4f5d87adc8

andrewtoth force-pushed on Nov 3, 2024

andrewtoth commented at 3:30 am on November 3, 2024: contributor

Thanks for your comments @jonatack, @stratospher, @theStack. I’ve also updated the BIP to include the generator G as an input, and so the BIP is no longer specific to secp256k1. This was mentioned on the mailing list as an improvement to make this standard work with other curves as well.

jonatack removed the label PR Author action required on Nov 5, 2024

jonatack requested review from theStack on Nov 8, 2024

jonatack requested review from stratospher on Nov 8, 2024

murchandamus commented at 3:58 pm on November 13, 2024: contributor

From an editorial standpoint this looks good so far. As mentioned by Jon, please include a Backwards Compatibility section, if only to state that there are no concerns.

I did not verify the cryptography of the proof, but after staring at it for a few minutes, I and perhaps other would perhaps benefit from a couple sentences of why/how the proof works e.g. as a footnote. I was also wondering whether you might want to expand on related work, alternate designs, and design decisions in this document. For example you might want to mention some of the things from the opening comment on the PR here, in the footnotes.

theStack commented at 5:50 pm on November 18, 2024: contributor

Fwiw, I’ve written a reference implementation of this BIP for secp256k1 in Python, see: https://github.com/theStack/bips/blob/bip-DLEQ-add_reference_impl/bip-DLEQ/reference.py It’s probably useful to be added to the BIP and also to create test vectors. The unit tests can be executed via

0$ cd bip-DLEQ
1$ python3 -m unittest reference.py

in bip-DLEQ.mediawiki:53 in 4f5d87adc8 outdated

48+* Let ''rand = hash<sub>BIP0???/nonce</sub>(t || cbytes(A) || cbytes(C))''.
49+* Let ''k = int(rand) mod n''.
50+* Fail if ''k = 0''.
51+* Let ''R<sub>1</sub> = k⋅G''.
52+* Let ''R<sub>2</sub> = k⋅B''.
53+* Let ''e = int(hash<sub>BIP0???/challenge</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.

theStack commented at 5:55 pm on November 18, 2024:

nit: I wonder if it is really needed to also include the generator point in the challenge hash? Seems excessive to me as its implicitly included in all other points. Generally I’m not sure what are the best practices here, since this seems to be the first BIP where the generator point can be generic and is not defined as the one in secp256k1.

andrewtoth commented at 4:09 am on December 10, 2024:

Are we sure we can remove this? I added it to reference.py in case.

murchandamus added the label PR Author action required on Nov 25, 2024

BIP-DLEQ: add reference implementation for secp256k1 0c7e54d780

Add optional message to DLEQ cc7bb12b24

Add some more commentary ed98dc7b02

add theStack as co-author b5d47dfef9

in bip-DLEQ.mediawiki:55 in cc7bb12b24 outdated

50@@ -50,7 +51,8 @@ The algorithm ''GenerateProof(a, B, r)'' is defined as:
51 * Fail if ''k = 0''.
52 * Let ''R<sub>1</sub> = k⋅G''.
53 * Let ''R<sub>2</sub> = k⋅B''.
54-* Let ''e = int(hash<sub>BIP0???/challenge</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
55+* Let ''m' = m if m is provided, otherwise an empty byte array''.
56+* Let ''e = int(hash<sub>BIP0???/challenge</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>) || cbytes(m')))''.

theStack commented at 5:14 pm on December 10, 2024:

0* Let ''e = int(hash<sub>BIP0???/challenge</sub>(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(G) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>) || m'))''.

since m' is already a byte-string and not a point

in bip-DLEQ.mediawiki:42 in ed98dc7b02 outdated

39 * The secret key ''a'': a 256-bit unsigned integer
40 * The public key ''B'': a point on the curve
41-* The generator point ''G'': a point on the curve
42 * Auxiliary random data ''r'': a 32-byte array
43-* An optional message ''m'': a 32-byte array
44+* The generator point ''G'': a point on the curve<ref name="why_include_G"> ''' 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.</ref>

theStack commented at 5:16 pm on December 10, 2024:

nit, I think it’s usually written in lowercase

0* The generator point ''G'': a point on the curve<ref name="why_include_G"> ''' 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.</ref>

Lowercase secp

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>

597004acef

Remove cbytes wrapper from m'

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>

e4f1d7bb8e

Remove cbytes wrapper from m' b838696c97

jonatack removed the label PR Author action required on Dec 11, 2024

bugfix: respect message m in DLEQ proof generation/verification dab5571c37

Add test vectors for DLEQ proof generation/verification

Squashed from the following commits:
- Add skeleton for generating DLEQ proof test vectors
- Add run_test_vectors.py counterpart for generated DLEQ proofs
- Add DLEQ test vectors for proof verification

6b16952422

in bip-DLEQ/reference.py:28 in cc7bb12b24 outdated

30-        R1.to_bytes_compressed() + R2.to_bytes_compressed()), 'big')
31-
32-
33-def dleq_generate_proof(a: int, B: GE, r: bytes) -> bytes | None:
34+def dleq_challenge(
35+    A: GE, B: GE, C: GE, R1: GE, R2: GE, G: GE = G, m: bytes | None = None

theStack commented at 11:35 pm on December 20, 2024:

Note that the message is currently not respected, as both the verify and proof functions call dleq_challgenge without passing m, i.e. the default parameter of None is used. I think m should be mandatory in the internal function to avoid this happening (need to change order of parameters though to still use default parameter for G):

0    A: GE, B: GE, C: GE, R1: GE, R2: GE, G: m: bytes | None, GE = G

in bip-DLEQ/reference.py:32 in cc7bb12b24 outdated

34+def dleq_challenge(
35+    A: GE, B: GE, C: GE, R1: GE, R2: GE, G: GE = G, m: bytes | None = None
36+) -> int:
37+    if m is not None:
38+        assert len(m) == 32
39+    m = bytes([]) if m is None else m.to_bytes(32, "big")

theStack commented at 11:35 pm on December 20, 2024:

m is already a byte-string, i.e. the .to_bytes call is not needed

0    m = bytes([]) if m is None else m

in bip-DLEQ.mediawiki:70 in 4f5d87adc8 outdated

65+* The generator point used in the proof generation ''G'': a point on the curve
66+* A proof ''proof'': a 64-byte array
67+
68+The algorithm ''VerifyProof(A, B, C, G, proof)'' is defined as:
69+* Let ''e = int(proof[0:32])''.
70+* Let ''s = int(proof[32:64])''; fail if ''s &ge; n''.

theStack commented at 11:48 pm on December 20, 2024:

Could check that neither of the A, B, C and G inputs are point at infinity here, as otherwise undefined cbytes calls below in the challenge hash calculation are reachable. I initially thought that we would fail earlier in those case anyway due to the is_infinite checks for R1 and R2 below, but those would only hit if both of either G and A (for R1) or B and C (for R2) are point at infinity.

andrewtoth commented at 5:53 pm on December 21, 2024:

Done. Thanks!

theStack commented at 0:28 am on December 21, 2024: contributor

A first draft for DLEQ test vectors is available now (special thanks to @stratospher for discussing the BIP and collecting test ideas together!):

https://github.com/theStack/bips/tree/bip-DLEQ-add_test_vectors (commit https://github.com/theStack/bips/commit/6b169524225e0bc3421f131d930ccb6f715f1068)

They can be generated and ran by:

0$ cd bip-DLEQ
1$ ./gen_test_vectors.py
2$ ./run_test_vectors.py

There are probably more failure and edge cases possible, but they at least already paid off by revealing a bug in the reference implementation (see comments below; the fix is included as a separate commit in the branch). Also, by now only secp256k1’s generator point is exercised. Further test ideas and comments are very welcome! @jonatack @murchandamus: Is there still something to be done for assigning a BIP number? :cowboy_hat_face:

Add note about generating and running test vectors 1f875a3706

Fail if any point is infinity when verifying 687198d72b

Add acknowledgements f5d1c12aa9

andrewtoth force-pushed on Dec 21, 2024

Add description of proof fd60d8eded

Remove changelog 90e7027f19

Add footnote recommending using fresh randomness for each proof 0b590d0d5d

Fix typo a0d8aad1df

andrewtoth commented at 9:19 pm on December 21, 2024: contributor

I did not verify the cryptography of the proof, but after staring at it for a few minutes, I and perhaps other would perhaps benefit from a couple sentences of why/how the proof works e.g. as a footnote. I was also wondering whether you might want to expand on related work, alternate designs, and design decisions in this document. For example you might want to mention some of the things from the opening comment on the PR here, in the footnotes. @murchandamus I added some text on a few design decisions, as well as a description section describing the algebra of the proof.

murchandamus commented at 10:04 pm on December 23, 2024: contributor

Thanks!

@jonatack @murchandamus: Is there still something to be done for assigning a BIP number? 🤠

I was waiting for the review to be addressed, but now it’s back on my review list. I’ll consider that point when I get around to review.

in bip-DLEQ.mediawiki:20 in a0d8aad1df outdated

15+
16+== Introduction ==
17+
18+=== Abstract ===
19+
20+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'', and ''G'', 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''.

murchandamus commented at 4:38 pm on December 26, 2024:

Not sure if this is obvious to other readers, but there doesn’t seem to be any information regarding how ‘‘B’’ is picked in this process. Is it provided per the context of the challenge or picked by the prover? Would there e.g., be an issue if the prover knew ‘‘b’’?

andrewtoth commented at 7:17 pm on December 26, 2024:

‘‘B’’ can be any point on the curve. Whether ‘‘b’’ is known to the prover or verifier does not change the generation or verification. If the prover substitutes ‘‘b’’ for ‘‘a’’ it would invalidate the proof. This is true for ‘‘G’’ as well.

I modified the second sentence slightly to clarify. Let me know if you think it could be worded more clearly.

in bip-DLEQ.mediawiki:2 in a0d8aad1df outdated

0@@ -0,0 +1,127 @@
1+<pre>
2+  BIP: ?

murchandamus commented at 4:42 pm on December 26, 2024:

0  BIP: 374

in bip-DLEQ.mediawiki:12 in a0d8aad1df outdated

 7+          Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
 8+  Comments-URI: TBD
 9+  Status: Draft
10+  Type: Standards Track
11+  License: BSD-2-Clause
12+  Created: 2024-06-29

murchandamus commented at 4:43 pm on December 26, 2024:

BIP2: “The Created header records the date that the BIP was assigned a number”

0  Created: 2024-12-26

murchandamus commented at 4:43 pm on December 26, 2024: contributor

This looks pretty advanced for a first draft. Thanks! I did notice that there was only a little rationale, and wanted to ask whether there were any more notable questions or alternate approaches that should perhaps be mentioned. Other than that, this look great already.

Let’s call this BIP 374. Could you please add the entry to the table in the README?

murchandamus renamed this:
~~Bip Draft: Discrete Log Equality Proofs (DLEQ)~~
BIP374: Discrete Log Equality Proofs (DLEQ)
on Dec 26, 2024

murchandamus commented at 4:46 pm on December 26, 2024: contributor

There was some previous discussion on this gist before making this PR https://gist.github.com/andrewtoth/df97c3260cc8d12f09d3855ee61322ea

Oh, and could you add that gist to the Post-History header, if you think it would be relevant for future readers, or alternatively, document any relevant bits here?

Update bip-DLEQ.mediawiki

Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>

5799659da0

Update bip-DLEQ.mediawiki

Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>

b533b92ed3

BIP374 1350bc423e

Update README table, post-history, and comments-uri 9d6dc6b681

Clarify restraints on given points 1842120907

Move test vectors to bip-0374 directory, add tests for G cb3afee850

andrewtoth commented at 7:18 pm on December 26, 2024: contributor

Oh, and could you add that gist to the Post-History header, if you think it would be relevant for future readers, or alternatively, document any relevant bits here?

I added that and the mailing list link :+1:

fix typo 248540e2ac

murchandamus approved

murchandamus commented at 3:29 pm on December 27, 2024: contributor

Thanks, this looks good to be merged. You can of course continue to iterate on this, at least until you move it to Proposed to designate it ready for implementation; you will just have to make pull requests to change things from now on.

As discussed out of band, gonna merge. Cheers.

murchandamus merged this on Dec 27, 2024

murchandamus closed this on Dec 27, 2024

andrewtoth deleted the branch on Jan 13, 2025

BIP374: Discrete Log Equality Proofs (DLEQ) #1689