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

pull andrewtoth wants to merge 1 commits into bitcoin:master from andrewtoth:dleq changing 1 files +92 −0
  1. 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

  2. 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
  3. in bip-DLEQ.mediawiki:46 in 2aab0766e3 outdated
    41+* Fail if ''a = 0'' or ''a ≥ 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.
  4. 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.
  5. jonatack renamed this:
    Bip Draft: DLEQ
    Bip Draft: Discrete Log Equality Proofs (DLEQ)
    on Oct 24, 2024
  6. jonatack added the label New BIP on Oct 24, 2024
  7. 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.
    
  8. 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.
  9. jonatack added the label PR Author action required on Oct 26, 2024
  10. 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.
  11. 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.
  12. 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?
  13. 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.
  14. Bip Draft: DLEQ 4f5d87adc8
  15. andrewtoth force-pushed on Nov 3, 2024
  16. 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.
  17. jonatack removed the label PR Author action required on Nov 5, 2024
  18. jonatack requested review from theStack on Nov 8, 2024
  19. jonatack requested review from stratospher on Nov 8, 2024
  20. 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.

  21. 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
    
  22. 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.
  23. murchandamus added the label PR Author action required on Nov 25, 2024

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bips. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-06 22:10 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me