Delivery-date: Wed, 23 Oct 2024 19:07:06 -0700
Sender: bitcoindev@googlegroups.com
Date: Wed, 23 Oct 2024 18:51:57 -0700 (PDT)
From: Andrew Toth <andrewstoth@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <b0f40eab-42f3-4153-8083-b455fbd17e19n@googlegroups.com>
Subject: [bitcoindev] BIP: DLEQ
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_22384_485612025.1729734717967"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_22384_485612025.1729734717967
Content-Type: multipart/alternative; 
	boundary="----=_Part_22385_1372994977.1729734717967"

------=_Part_22385_1372994977.1729734717967
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

=20

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

This is inspired by=20
https://github.com/discreetlogcontracts/dlcspecs/blob/master/ECDSA-adaptor.=
md#proof-of-discrete-logarithm-equality,=20
but is a little more specific.
There is an implementation of that already at=20
https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master/src/module=
s/ecdsa_adaptor/dleq_impl.h,=20
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>

=3D=3D Introduction =3D=3D

=3D=3D=3D Abstract =3D=3D=3D

This document proposes a standard for 64-byte zero-knowledge ''discrete=20
logarithm equality proofs'' (DLEQ proofs) over the elliptic curve=20
''secp256k1''. For given elliptic curve points ''A'', ''B'', and ''C'', the=
=20
prover proves knowledge of a scalar ''a'' such that ''A =3D a=E2=8B=85G'' a=
nd ''C =3D=20
a=E2=8B=85B'' without revealing anything about ''a''. This can, for instanc=
e, be=20
useful in ECDH: if ''A'' and ''B'' are ECDH public keys, and ''C'' is their=
=20
ECDH shared secret computed as ''C =3D a=E2=8B=85B'', the proof establishes=
 that the=20
same secret key ''a'' is used for generating both ''A'' and ''C'' without=
=20
revealing ''a''.

=3D=3D=3D Copyright =3D=3D=3D

This document is licensed under the 2-clause BSD license.

=3D=3D=3D Motivation =3D=3D=3D

[https://github.com/bitcoin/bips/blob/master/bip-0352.mediawiki#specificati=
on=20
BIP352] requires senders to compute output scripts using ECDH shared=20
secrets from the same secret keys used to sign the inputs. Generating an=20
incorrect signature will produce an invalid transaction that will be=20
rejected by consensus. An incorrectly generated output script can still be=
=20
consensus-valid, meaning funds may be lost if it gets broadcast.
By producing a DLEQ proof for the generated ECDH shared secrets, the=20
signing entity can prove to other entities that the output scripts have=20
been generated correctly without revealing the private keys.

=3D=3D Specification =3D=3D

All conventions and notations are used as defined in=20
[https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#user-conten=
t-Notation=20
BIP327].

=3D=3D=3D DLEQ Proof Generation =3D=3D=3D

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 =3D 0'' or ''a &ge; n''.
* Fail if ''is_infinite(B)''.
* Let ''A =3D a=E2=8B=85G''.
* Let ''C =3D a=E2=8B=85B''.
* Let ''t'' be the byte-wise xor of ''bytes(32, a)'' and=20
''hash<sub>BIP?/aux</sub>(r)''.
* Let ''rand =3D hash<sub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.
* Let ''k =3D int(rand) mod n''.
* Fail if ''k =3D 0''.
* Let ''R<sub>1</sub> =3D k=E2=8B=85G''.
* Let ''R<sub>2</sub> =3D k=E2=8B=85B''.
* Let ''e =3D int(hash<sub>DLEQ</sub>(cbytes(A) || cbytes(B) || cbytes(C) |=
|=20
cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
* Let ''proof =3D bytes(32, e) || bytes(32, (k + ea) mod n)''.
* If ''VerifyProof(A, B, C, proof)'' (see below) returns failure, abort.
* Return the proof ''proof''.

=3D=3D=3D DLEQ Proof Verification =3D=3D=3D

Input:
* The public key of the secret key used in the proof generation ''A'': a=20
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=20
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 =3D int(proof[0:32])''.
* Let ''s =3D int(proof[32:64])''; fail if ''s &ge; n''.
* Let ''R<sub>1</sub> =3D s=E2=8B=85G - e=E2=8B=85A''.
* Fail if ''is_infinite(R<sub>1</sub>)''.
* Fail if ''not has_even_y(R<sub>1</sub>)''.
* Let ''R<sub>2</sub> =3D s=E2=8B=85B - e=E2=8B=85C''.
* Fail if ''is_infinite(R<sub>2</sub>)''.
* Fail if ''not has_even_y(R<sub>2</sub>)''.
* Fail if ''e =E2=89=A0 int(hash<sub>BIP?/DLEQ</sub>(cbytes(A) || cbytes(B)=
 ||=20
cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R<sub>2</sub>)))''.
* Return success iff no failure occurred before reaching this point.

=3D=3D Test Vectors and Reference Code =3D=3D

TBD

=3D=3D Changelog =3D=3D

TBD

=3D=3D Footnotes =3D=3D

<references />

=3D=3D Acknowledgements =3D=3D

TBD

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
b0f40eab-42f3-4153-8083-b455fbd17e19n%40googlegroups.com.

------=_Part_22385_1372994977.1729734717967
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>
        <div>
 =20
  <span>
    <div>
      <p dir=3D"auto">This BIP specifies a standard way to generate and=20
verify DLEQ proofs. This is motivated by sending to silent payments in=20
PSBTs. However, there are also other uses where DLEQs could be useful,=20
so it would be good to have this BIP for others to reference.</p>
<p dir=3D"auto">This is inspired by <a href=3D"https://github.com/discreetl=
ogcontracts/dlcspecs/blob/master/ECDSA-adaptor.md#proof-of-discrete-logarit=
hm-equality">https://github.com/discreetlogcontracts/dlcspecs/blob/master/E=
CDSA-adaptor.md#proof-of-discrete-logarithm-equality</a>, but is a little m=
ore specific.<br />
There is an implementation of that already at <a href=3D"https://github.com=
/BlockstreamResearch/secp256k1-zkp/blob/master/src/modules/ecdsa_adaptor/dl=
eq_impl.h">https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master=
/src/modules/ecdsa_adaptor/dleq_impl.h</a>, which this BIP attempts to be c=
ompatible with.</p><p dir=3D"auto">Pull request here https://github.com/bit=
coin/bips/pull/1689</p><p dir=3D"auto"><br /></p>&lt;pre&gt;<br />=C2=A0 BI=
P: ?<br />=C2=A0 Title: Discrete Log Equality Proofs over secp256k1<br />=
=C2=A0 Author: Andrew Toth &lt;andrewstoth@gmail.com&gt;<br />=C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 Ruben Somsen &lt;rsomsen@gmail.com&gt;<br />=C2=A0 Co=
mments-URI: TBD<br />=C2=A0 Status: Draft<br />=C2=A0 Type: Standards Track=
<br />=C2=A0 License: BSD-2-Clause<br />=C2=A0 Created: 2024-06-29<br />=C2=
=A0 Post-History: TBD<br />&lt;/pre&gt;<br /><br />=3D=3D Introduction =3D=
=3D<br /><br />=3D=3D=3D Abstract =3D=3D=3D<br /><br />This document propos=
es a standard for 64-byte zero-knowledge ''discrete logarithm equality proo=
fs'' (DLEQ proofs) over the elliptic curve ''secp256k1''. For given ellipti=
c curve points ''A'', ''B'', and ''C'', the prover proves knowledge of a sc=
alar ''a'' such that ''A =3D a=E2=8B=85G'' and ''C =3D a=E2=8B=85B'' withou=
t 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 s=
ecret computed as ''C =3D a=E2=8B=85B'', the proof establishes that the sam=
e secret key ''a'' is used for generating both ''A'' and ''C'' without reve=
aling ''a''.<br /><br />=3D=3D=3D Copyright =3D=3D=3D<br /><br />This docum=
ent is licensed under the 2-clause BSD license.<br /><br />=3D=3D=3D Motiva=
tion =3D=3D=3D<br /><br />[https://github.com/bitcoin/bips/blob/master/bip-=
0352.mediawiki#specification BIP352] requires senders to compute output scr=
ipts using ECDH shared secrets from the same secret keys used to sign the i=
nputs. Generating an incorrect signature will produce an invalid transactio=
n that will be rejected by consensus. An incorrectly generated output scrip=
t can still be consensus-valid, meaning funds may be lost if it gets broadc=
ast.<br />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.<br /><br />=
=3D=3D Specification =3D=3D<br /><br />All conventions and notations are us=
ed as defined in [https://github.com/bitcoin/bips/blob/master/bip-0327.medi=
awiki#user-content-Notation BIP327].<br /><br />=3D=3D=3D DLEQ Proof Genera=
tion =3D=3D=3D<br /><br />Input:<br />* The secret key ''a'': a 256-bit uns=
igned integer<br />* The public key ''B'': a point on the curve<br />* Auxi=
liary random data ''r'': a 32-byte array<br /><br />The algorithm ''Prove(a=
, B, r)'' is defined as:<br />* Fail if ''a =3D 0'' or ''a &amp;ge; n''.<br=
 />* Fail if ''is_infinite(B)''.<br />* Let ''A =3D a=E2=8B=85G''.<br />* L=
et ''C =3D a=E2=8B=85B''.<br />* Let ''t'' be the byte-wise xor of ''bytes(=
32, a)'' and ''hash&lt;sub&gt;BIP?/aux&lt;/sub&gt;(r)''.<br />* Let ''rand =
=3D hash&lt;sub&gt;DLEQ&lt;/sub&gt;(t || cbytes(A) || cytes(C))''.<br />* L=
et ''k =3D int(rand) mod n''.<br />* Fail if ''k =3D 0''.<br />* Let ''R&lt=
;sub&gt;1&lt;/sub&gt; =3D k=E2=8B=85G''.<br />* Let ''R&lt;sub&gt;2&lt;/sub=
&gt; =3D k=E2=8B=85B''.<br />* Let ''e =3D int(hash&lt;sub&gt;DLEQ&lt;/sub&=
gt;(cbytes(A) || cbytes(B) || cbytes(C) || cbytes(R&lt;sub&gt;1&lt;/sub&gt;=
) || cbytes(R&lt;sub&gt;2&lt;/sub&gt;)))''.<br />* Let ''proof =3D bytes(32=
, e) || bytes(32, (k + ea) mod n)''.<br />* If ''VerifyProof(A, B, C, proof=
)'' (see below) returns failure, abort.<br />* Return the proof ''proof''.<=
br /><br />=3D=3D=3D DLEQ Proof Verification =3D=3D=3D<br /><br />Input:<br=
 />* The public key of the secret key used in the proof generation ''A'': a=
 point on the curve<br />* The public key used in the proof generation ''B'=
': a point on the curve<br />* The result of multiplying the secret and pub=
lic keys used in the proof generation ''C'': a point on the curve<br />* A =
proof ''proof'': a 64-byte array<br /><br />The algorithm ''VerifyProof(A, =
B, C, proof)'' is defined as:<br />* Let ''e =3D int(proof[0:32])''.<br />*=
 Let ''s =3D int(proof[32:64])''; fail if ''s &amp;ge; n''.<br />* Let ''R&=
lt;sub&gt;1&lt;/sub&gt; =3D s=E2=8B=85G - e=E2=8B=85A''.<br />* Fail if ''i=
s_infinite(R&lt;sub&gt;1&lt;/sub&gt;)''.<br />* Fail if ''not has_even_y(R&=
lt;sub&gt;1&lt;/sub&gt;)''.<br />* Let ''R&lt;sub&gt;2&lt;/sub&gt; =3D s=E2=
=8B=85B - e=E2=8B=85C''.<br />* Fail if ''is_infinite(R&lt;sub&gt;2&lt;/sub=
&gt;)''.<br />* Fail if ''not has_even_y(R&lt;sub&gt;2&lt;/sub&gt;)''.<br /=
>* Fail if ''e =E2=89=A0 int(hash&lt;sub&gt;BIP?/DLEQ&lt;/sub&gt;(cbytes(A)=
 || cbytes(B) || cbytes(C) || cbytes(R&lt;sub&gt;1&lt;/sub&gt;) || cbytes(R=
&lt;sub&gt;2&lt;/sub&gt;)))''.<br />* Return success iff no failure occurre=
d before reaching this point.<br /><br />=3D=3D Test Vectors and Reference =
Code =3D=3D<br /><br />TBD<br /><br />=3D=3D Changelog =3D=3D<br /><br />TB=
D<br /><br />=3D=3D Footnotes =3D=3D<br /><br />&lt;references /&gt;<br /><=
br />=3D=3D Acknowledgements =3D=3D<br /><br />TBD</div>
  </span>
 =20
</div>

      </div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/b0f40eab-42f3-4153-8083-b455fbd17e19n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/b0f40eab-42f3-4153-8083-b455fbd17e19n%40googlegroups.com</a>.<br />

------=_Part_22385_1372994977.1729734717967--

------=_Part_22384_485612025.1729734717967--