* [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 ≥ 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 ≥ 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
* [bitcoindev] Re: BIP: DLEQ
2024-10-24 1:51 [bitcoindev] BIP: DLEQ Andrew Toth
@ 2024-10-25 14:49 ` waxwing/ AdamISZ
0 siblings, 0 replies; 2+ messages in thread
From: waxwing/ AdamISZ @ 2024-10-25 14:49 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 7004 bytes --]
First, thanks for doing that; this is a nice thing to standardize!
My enthusiasm really comes from the idea that it may be used in several
protocols in future (well, and currently), so I'd be keen to see it be
sufficiently flexible. Which motivates my reading of it here:
I have a couple of general questions/comments on the design:
Why doesn't the Fiat Shamir challenge (e) include space for a message m?
Just like other ZkPoKs that can be really useful, considering that they are
transferrable.
While it's understandable that you focus on the case of 1 generator being G
(secp default), it seems like an unnecessary restriction. It's easy to
imagine a more complex protocol requiring DLEQs across other pairs of
bases. In this case you'd want to include the other base in the Fiat Shamir
challenge (even if it *is* G). **
I guess no comments on the basic algorithm or the choice of (e,s) vs (R1,
R2,s) proof encoding (as you've chosen exactly the same as what I chose 8
years ago for Joinmarket :) ). The handling of k-generation is obviously a
big step up though.
(**) It's orthogonal to this BIP almost certainly, but it makes me think:
since we have tons of uses for NUMS generator .. generation in various
bitcoin protocols, maybe we should have a BIP just for that? The only
reason I suggest that slightly weird idea is, it's explicitly necessary for
counterparties to be able to reproduce them and it's probably wasteful to
constantly redefine these other NUMS generators that we're going to use.
It's even mentioned in BIP341 for the whole provably unspendable paths
thing.
On Wednesday, October 23, 2024 at 8:06:59 PM UTC-6 Andrew Toth wrote:
> 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 <andre...@gmail•com>
> Ruben Somsen <rso...@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 ≥ 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 ≥ 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/77ad84ed-2ff8-4929-b8da-d940c95d18a7n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 10623 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