From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 23 Oct 2024 19:07:06 -0700 Received: from mail-yb1-f187.google.com ([209.85.219.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1t3nFh-00023X-Rp for bitcoindev@gnusha.org; Wed, 23 Oct 2024 19:07:06 -0700 Received: by mail-yb1-f187.google.com with SMTP id 3f1490d57ef6-e0b8fa94718sf990357276.0 for ; Wed, 23 Oct 2024 19:07:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1729735619; x=1730340419; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:sender:from:to:cc:subject:date :message-id:reply-to; bh=AUAp6IzeH4d2W9fDj3Lix4bhOZrQEeG0/Oq1k5rT5Ys=; b=aTbaqH1D8P/+O8q0RuqvpUVYtCj5ULLddRxKETGdXL9qyrH0ACqcgG7+wAvn2SxcQK Oyqr8HESJCElcGvddcNjJr/fzMakgcj0rfNnqhLhSxV8XJpbfjOCJcyq0pOnba+OftGU qSYdnLX2nJVSIMH1NO7NIcU8XOA6WjzfT+i6cAWhmZ6znsVlAxhcsrto4ATiG9gkMJtu uttSrBGipSGJ+/jN26ZSCIiX9zXxiAuXRGBpNV0NheOqiMkNyS9aTDHqMq7Bx5To0fy9 hG0iJ8p7WRhlCzngqRopxZ+nSsuh8yvfydwSbTEgZj/bVim+JWX4VXuxQ6vM/kGqEa1v qncg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729735619; x=1730340419; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:from:to:cc:subject:date:message-id :reply-to; bh=AUAp6IzeH4d2W9fDj3Lix4bhOZrQEeG0/Oq1k5rT5Ys=; b=XIaTACXmkHqBeMIxTsgwllwTBp3L3JTrslsO2Fp8y/vtctxOklf4ZIGcqlGXmGy5id SAoBSFQkBGFC8vlXy+X3Eqr8VVrCUq1BbI4oaNZAWENNLusBbw8H66eIdYEMgswag1mT XP+MMDCX8tvycPHvssUnVYnOXahA5xsboJF/mc6mWo04wMZ4DYYmULvrFEchN7ftUqBb fUffheaTmWjXsOcwWviI7WCockq9/sYCR+i8qQJqOSnpVZkYnCeM2ZXRXk2e01lN7XuJ iSBOP0oJb3vPJzFY8YqKtpejt+5D9seFoe0cg1DJxioir1Hy/OftDLv3wQdYDkoEORmv +E5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729735619; x=1730340419; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=AUAp6IzeH4d2W9fDj3Lix4bhOZrQEeG0/Oq1k5rT5Ys=; b=HYLOJNMgU0xpfn0VCoiZZ1HLSe+xnHI8839T04LP4QCfDiyXx2NjNsQdfrNFnKb4gx rBNyrmhUkuhziWCdSUr0SYa6X0zUlArQT16J7cpgDr09AaS1crwvaCS4XtG+zKP6mghA y2HZ6WuAmoFan9/Q+3CezuHc45QcTnpCjniDSBD+R1fhlPHY23rx+CUCLrxD3yzS1Gbs D6d80NQIjOJG9QsQ/B5/Cnhj+ac/GsugaMsAPeeKSETxoOWbbobGH+rREFYtqdZ1FD8N BC9gLIipL3jOPxgkleQqJAo93i6dFtwVyD/h3JxnFiDsqF7kHJnc9lvCVzRSXAYYTrr5 Qrdg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWioiusECZx+k0jGSvt0oDEVMz5MV93PX4qJXRXtWyWAa8+t/6CHeI2h4+j0lfYU1zBMILLyogiMOb4@gnusha.org X-Gm-Message-State: AOJu0YzJjdebgVW3UB8z2y1grwJxJ1KzzknGJ6mEVon5YHa8sKlGtcqP nTjbm3O1CMALScdAu3p4L94a16senKPAwfOijJ5Y77dvxu6+qGl4 X-Google-Smtp-Source: AGHT+IGy+lfdaLaiqlXsWimQ1csXgm8TrepP8mC0NDtC639uIHr5ajLgYT2kf85S3pbbo2UkyPXz/Q== X-Received: by 2002:a05:6902:1b0c:b0:e28:ecf0:f880 with SMTP id 3f1490d57ef6-e2e3a65071cmr4625823276.23.1729735619268; Wed, 23 Oct 2024 19:06:59 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:188c:b0:e1c:eeec:3175 with SMTP id 3f1490d57ef6-e2e4a77e8fals697764276.1.-pod-prod-02-us; Wed, 23 Oct 2024 19:06:57 -0700 (PDT) X-Received: by 2002:a05:690c:4087:b0:6e5:bca9:cb8f with SMTP id 00721157ae682-6e7f0fcc42emr38450437b3.38.1729735616907; Wed, 23 Oct 2024 19:06:56 -0700 (PDT) Received: by 2002:a05:690c:f8b:b0:6e2:1e5e:a1e1 with SMTP id 00721157ae682-6e7ef02e532ms7b3; Wed, 23 Oct 2024 18:51:59 -0700 (PDT) X-Received: by 2002:a05:690c:dc4:b0:6e2:11b7:f681 with SMTP id 00721157ae682-6e85814c19emr5758027b3.6.1729734718298; Wed, 23 Oct 2024 18:51:58 -0700 (PDT) Date: Wed, 23 Oct 2024 18:51:57 -0700 (PDT) From: Andrew Toth To: Bitcoin Development Mailing List Message-Id: Subject: [bitcoindev] BIP: DLEQ MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_22384_485612025.1729734717967" X-Original-Sender: andrewstoth@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_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 
  BIP: ?
  Title: Discrete Log Equality Proofs over secp256k1
  Author: Andrew Toth 
          Ruben Somsen 
  Comments-URI: TBD
  Status: Draft
  Type: Standards Track
  License: BSD-2-Clause
  Created: 2024-06-29
  Post-History: TBD
=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 ≥ 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 ''hashBIP?/aux(r)''. * Let ''rand =3D hashDLEQ(t || cbytes(A) || cytes(C))''. * Let ''k =3D int(rand) mod n''. * Fail if ''k =3D 0''. * Let ''R1 =3D k=E2=8B=85G''. * Let ''R2 =3D k=E2=8B=85B''. * Let ''e =3D int(hashDLEQ(cbytes(A) || cbytes(B) || cbytes(C) |= |=20 cbytes(R1) || cbytes(R2)))''. * 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 ≥ n''. * Let ''R1 =3D s=E2=8B=85G - e=E2=8B=85A''. * Fail if ''is_infinite(R1)''. * Fail if ''not has_even_y(R1)''. * Let ''R2 =3D s=E2=8B=85B - e=E2=8B=85C''. * Fail if ''is_infinite(R2)''. * Fail if ''not has_even_y(R2)''. * Fail if ''e =E2=89=A0 int(hashBIP?/DLEQ(cbytes(A) || cbytes(B)= ||=20 cbytes(C) || cbytes(R1) || cbytes(R2)))''. * 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 =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
=20

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.

This is inspired by https://github.com/discreetlogcontracts/dlcspecs/blob/master/E= CDSA-adaptor.md#proof-of-discrete-logarithm-equality, but is a little m= ore 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 c= ompatible with.

Pull request here https://github.com/bit= coin/bips/pull/1689


<pre>
=C2=A0 BI= P: ?
=C2=A0 Title: Discrete Log Equality Proofs over secp256k1
= =C2=A0 Author: Andrew Toth <andrewstoth@gmail.com>
=C2=A0 =C2=A0= =C2=A0 =C2=A0 =C2=A0 Ruben Somsen <rsomsen@gmail.com>
=C2=A0 Co= mments-URI: TBD
=C2=A0 Status: Draft
=C2=A0 Type: Standards Track=
=C2=A0 License: BSD-2-Clause
=C2=A0 Created: 2024-06-29
=C2= =A0 Post-History: TBD
</pre>

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

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

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''.

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

This docum= ent is licensed under the 2-clause BSD license.

=3D=3D=3D Motiva= tion =3D=3D=3D

[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.
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.

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

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].

=3D=3D=3D DLEQ Proof Genera= tion =3D=3D=3D

Input:
* The secret key ''a'': a 256-bit uns= igned integer
* The public key ''B'': a point on the curve
* Auxi= liary 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''.
* L= et ''C =3D a=E2=8B=85B''.
* Let ''t'' be the byte-wise xor of ''bytes(= 32, a)'' and ''hash<sub>BIP?/aux</sub>(r)''.
* Let ''rand = =3D hash<sub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.
* L= et ''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&= gt;(cbytes(A) || cbytes(B) || cbytes(C) || 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''.<= br />
=3D=3D=3D DLEQ Proof Verification =3D=3D=3D

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 pub= lic 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 =3D int(proof[0:32])''.
*= Let ''s =3D int(proof[32:64])''; fail if ''s &ge; n''.
* Let ''R&= lt;sub>1</sub> =3D s=E2=8B=85G - e=E2=8B=85A''.
* Fail if ''i= s_infinite(R<sub>1</sub>)''.
* Fail if ''not has_even_y(R&= lt;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) || cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R= <sub>2</sub>)))''.
* Return success iff no failure occurre= d before reaching this point.

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

TBD

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

TB= D

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

<references />
<= br />=3D=3D Acknowledgements =3D=3D

TBD
 =20

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/b0f40eab-42f3-4153-8083-b455fbd17e19n%40googlegroups.com.
------=_Part_22385_1372994977.1729734717967-- ------=_Part_22384_485612025.1729734717967--