public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
* [bitcoindev] BIP: DLEQ
@ 2024-10-24  1:51 Andrew Toth
  2024-10-25 14:49 ` [bitcoindev] " waxwing/ AdamISZ
  0 siblings, 1 reply; 2+ messages in thread
From: Andrew Toth @ 2024-10-24  1:51 UTC (permalink / raw)
  To: Bitcoin Development Mailing List


[-- Attachment #1.1: Type: text/plain, Size: 5064 bytes --]

 

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.

Pull request here https://github.com/bitcoin/bips/pull/1689


<pre>
  BIP: ?
  Title: Discrete Log Equality Proofs over secp256k1
  Author: Andrew Toth <andrewstoth@gmail•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
</pre>

== 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 ===

[https://github.com/bitcoin/bips/blob/master/bip-0352.mediawiki#specification 
BIP352] requires senders to compute output scripts using ECDH shared 
secrets from the same secret keys used to sign the inputs. 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.
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 notations are used as defined in 
[https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#user-content-Notation 
BIP327].

=== 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 &ge; n''.
* Fail if ''is_infinite(B)''.
* Let ''A = a⋅G''.
* Let ''C = a⋅B''.
* Let ''t'' be the byte-wise xor of ''bytes(32, a)'' and 
''hash<sub>BIP?/aux</sub>(r)''.
* Let ''rand = hash<sub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.
* Let ''k = int(rand) mod n''.
* Fail if ''k = 0''.
* Let ''R<sub>1</sub> = k⋅G''.
* Let ''R<sub>2</sub> = k⋅B''.
* Let ''e = int(hash<sub>DLEQ</sub>(cbytes(A) || cbytes(B) || cbytes(C) || 
cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
* Let ''proof = bytes(32, e) || bytes(32, (k + ea) mod n)''.
* If ''VerifyProof(A, B, 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 result of multiplying the secret and public keys used in the proof 
generation ''C'': a point on the curve
* A proof ''proof'': a 64-byte array

The algorithm ''VerifyProof(A, B, C, proof)'' is defined as:
* Let ''e = int(proof[0:32])''.
* Let ''s = int(proof[32:64])''; fail if ''s &ge; n''.
* Let ''R<sub>1</sub> = s⋅G - e⋅A''.
* Fail if ''is_infinite(R<sub>1</sub>)''.
* Fail if ''not has_even_y(R<sub>1</sub>)''.
* Let ''R<sub>2</sub> = s⋅B - e⋅C''.
* Fail if ''is_infinite(R<sub>2</sub>)''.
* Fail if ''not has_even_y(R<sub>2</sub>)''.
* Fail if ''e ≠ int(hash<sub>BIP?/DLEQ</sub>(cbytes(A) || cbytes(B) || 
cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
* Return success iff no failure occurred before reaching this point.

== Test Vectors and Reference Code ==

TBD

== Changelog ==

TBD

== Footnotes ==

<references />

== Acknowledgements ==

TBD

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/b0f40eab-42f3-4153-8083-b455fbd17e19n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 6280 bytes --]

^ permalink raw reply	[flat|nested] 2+ messages in thread
end of thread, other threads:[~2024-10-26  9:05 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-10-24  1:51 [bitcoindev] BIP: DLEQ Andrew Toth
2024-10-25 14:49 ` [bitcoindev] " waxwing/ AdamISZ

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox