Bip Draft: 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.

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?

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

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.

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

Bip Draft: Discrete Log Equality Proofs (DLEQ) #1689