Delivery-date: Sat, 26 Oct 2024 02:05:32 -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 1t4cjj-0005br-0a for bitcoindev@gnusha.org; Sat, 26 Oct 2024 02:05:31 -0700 Received: by mail-yb1-f187.google.com with SMTP id 3f1490d57ef6-e26067b727asf688280276.2 for ; Sat, 26 Oct 2024 02:05:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1729933524; x=1730538324; 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:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=+RyNSCcS5zG75T4Inss7y8dcNBiTC0vXyE80cgniODA=; b=NjEuUgpASzn9X9z8cczx3k0srO/Ll0wMSx+mDza72a4CGsXOIoG7rEl/1P0EtT0RLV JVMhOciNBujA71yp4Qt8nEhAEWoRUKPmM8YLJvBqC4/68sl/wFfJi3CR4CJ8MV4MU0OE 5fzhlV1fQg4/KqUsBwvUVhvDD0zmOKAZ+yCqSGg0+0B2dnecaot4LCQUTBHotovM+qTm Vn5l3eC+EMwm2uzhd4tMgk+Ok3lnF4/YB2uo+Rx+9hbCaKWzXhlN43ynVKwB6Ta/pokw 5RbDnkp9n9QGbMFmgRBjdD2Z2CFlLhl/+eOr3ISGAokJb80DLtKL8wv/S0Wxt43hF5eQ K/HA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729933524; x=1730538324; 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:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=+RyNSCcS5zG75T4Inss7y8dcNBiTC0vXyE80cgniODA=; b=H1k9orvhAtHXbpC+PXznvAl5wG2NcsJ0V6eSj0yex0tIbFqKNe2i9DVHpb9MYQQiFC qz9JMrUIFhA1XX8leFhee16POQXN3REKRJ76tZPPLB70ihjqgCtxP+BprMpdfWRo80Sy cndvQkXcxdtaIagHp8dYbU1+DLUjtyGrc+iIQylCsJ1DVc8WjYNS2FOPlztcg20TRoFy JhydlNDu/Yg+pPq3IVvgrQmZlab9iWEuEOfYocubNiO0+8JpPtq9D7ON3JAvqb8zfdAU 0DQGXZhL4Ny/lD8vvB/WE57bsnpR5YpZGTqKwNsjzDzVXEwH9CCu1NYyMvuBjD6uF7gs wExw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729933524; x=1730538324; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=+RyNSCcS5zG75T4Inss7y8dcNBiTC0vXyE80cgniODA=; b=SU2ElyJqV0tvA9p46V7CedI8m44ZjKOuLNz7PkXbQ/tvst4ISAs00+EstXPlYkLlFi Vi/UdQS07Nb2bSt6ifXHibjFsCueJh/9XQ2bWd4FWNNKIvk88kLdaGsUVZo1LadC69bP c7ILmaPIjkfN+/yYjFGiRTDxAbZE8Db6AQ2zZnc33IkKpRkmQMn/qV8r0mgUqZwz7diL xWjYLC1pP8TQLPWm+J1KZbvZgqh4MV9y+q/lchlxTpUwnKu/FJ/ZX0pjQpj54GOQ2BTZ 39+UZ3TGbP/uy6H1rq6uGnEJFgknHSlgNktnOK5eFoOPSG4LQ0AMKV9hqsGGYdv0r6k7 u7Gg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUQLpTf2XLQQtxF2XdEUCkLRv13ttwjBj3s4GulzdovhrSNSwoF/wuB8sGo2X9gF/cHrHLxDa1aORwa@gnusha.org X-Gm-Message-State: AOJu0Ywbi1NjOBVPyJ7c9CuBt2WLyZyTDkcw7gJPjywku4NOkW5u4RDY LU+ErfCnCCk54gDrEQnpnzjSPGORVC500BSGptJMnEWMnyUrh1TD X-Google-Smtp-Source: AGHT+IG8Kpvq4PmuI/bTLEKgXv7RCfe35JXD+6WrTVLY4Qle9CZUlLDQMhrOULhi3QNo9qNAeMH9vA== X-Received: by 2002:a05:6902:2087:b0:e29:60a0:cd33 with SMTP id 3f1490d57ef6-e3087c35ff9mr730601276.10.1729933524446; Sat, 26 Oct 2024 02:05:24 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:188c:b0:e1c:eeec:3175 with SMTP id 3f1490d57ef6-e2e4a77e8fdls116955276.1.-pod-prod-02-us; Sat, 26 Oct 2024 02:05:22 -0700 (PDT) X-Received: by 2002:a05:690c:c:b0:6e2:4c7b:e379 with SMTP id 00721157ae682-6e9d89abf2bmr24913377b3.19.1729933522386; Sat, 26 Oct 2024 02:05:22 -0700 (PDT) Received: by 2002:a81:fb01:0:b0:6dd:c9c1:7a16 with SMTP id 00721157ae682-6e7eed5a03cms7b3; Fri, 25 Oct 2024 07:49:03 -0700 (PDT) X-Received: by 2002:a05:690c:f96:b0:6e2:ac0a:890e with SMTP id 00721157ae682-6e7f0df6366mr114031317b3.6.1729867742797; Fri, 25 Oct 2024 07:49:02 -0700 (PDT) Date: Fri, 25 Oct 2024 07:49:02 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <77ad84ed-2ff8-4929-b8da-d940c95d18a7n@googlegroups.com> In-Reply-To: References: Subject: [bitcoindev] Re: BIP: DLEQ MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_74722_461499448.1729867742479" X-Original-Sender: ekaggata@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_74722_461499448.1729867742479 Content-Type: multipart/alternative; boundary="----=_Part_74723_787826626.1729867742479" ------=_Part_74723_787826626.1729867742479 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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=20 protocols in future (well, and currently), so I'd be keen to see it be=20 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?=20 Just like other ZkPoKs that can be really useful, considering that they are= =20 transferrable. While it's understandable that you focus on the case of 1 generator being G= =20 (secp default), it seems like an unnecessary restriction. It's easy to=20 imagine a more complex protocol requiring DLEQs across other pairs of=20 bases. In this case you'd want to include the other base in the Fiat Shamir= =20 challenge (even if it *is* G). ** I guess no comments on the basic algorithm or the choice of (e,s) vs (R1,= =20 R2,s) proof encoding (as you've chosen exactly the same as what I chose 8= =20 years ago for Joinmarket :) ). The handling of k-generation is obviously a= =20 big step up though. (**) It's orthogonal to this BIP almost certainly, but it makes me think:= =20 since we have tons of uses for NUMS generator .. generation in various=20 bitcoin protocols, maybe we should have a BIP just for that? The only=20 reason I suggest that slightly weird idea is, it's explicitly necessary for= =20 counterparties to be able to reproduce them and it's probably wasteful to= =20 constantly redefine these other NUMS generators that we're going to use.=20 It's even mentioned in BIP341 for the whole provably unspendable paths=20 thing. On Wednesday, October 23, 2024 at 8:06:59=E2=80=AFPM UTC-6 Andrew Toth wrot= e: > This BIP specifies a standard way to generate and verify DLEQ proofs. Thi= s=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-adapto= r.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/modu= les/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'', t= he=20 > prover proves knowledge of a scalar ''a'' such that ''A =3D a=E2=8B=85G''= and ''C =3D=20 > a=E2=8B=85B'' without revealing anything about ''a''. This can, for insta= nce, be=20 > useful in ECDH: if ''A'' and ''B'' are ECDH public keys, and ''C'' is the= ir=20 > ECDH shared secret computed as ''C =3D a=E2=8B=85B'', the proof establish= es 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#specificat= ion=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 b= e=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 [ > https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki#user-conte= nt-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/= 77ad84ed-2ff8-4929-b8da-d940c95d18a7n%40googlegroups.com. ------=_Part_74723_787826626.1729867742479 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
First, thanks for doing that; this is a nice thing to standardize!

My enthusiasm really comes from the idea that it ma= y be used in several protocols in future (well, and currently), so I'd be k= een to see it be sufficiently flexible. Which motivates my reading of it he= re:

I have a couple of general questions/comment= s on the design:

Why doesn't the Fiat Shamir cha= llenge (e) include space for a message m? Just like other ZkPoKs that can b= e really useful, considering that they are transferrable.

<= /div>
While it's understandable that you focus on the case of 1 generat= or being G (secp default), it seems like an unnecessary restriction. It's e= asy to imagine a more complex protocol requiring DLEQs across other pairs o= f bases. In this case you'd want to include the other base in the Fiat Sham= ir challenge (even if it *is* G). **

I gue= ss 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 a= go for Joinmarket :) ). The handling of k-generation is obviously a big ste= p up though.

(**) It's orthogonal to this BIP al= most 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 generato= rs that we're going to use. It's even mentioned in BIP341 for the whole pro= vably unspendable paths thing.

=
On Wednesday, October 23, 2024 at 8:= 06:59=E2=80=AFPM UTC-6 Andrew Toth wrote:
=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/mas= ter/ECDSA-adaptor.md#proof-of-discrete-logarithm-equality, but is a lit= tle more specific.
There is an implementation of that already at https://github.com/BlockstreamResearch/secp256k1-zkp/blob/master/src/modu= les/ecdsa_adaptor/dleq_impl.h, which this BIP attempts to be compatible= with.

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


<pre>
=C2=A0 BIP: ?
=C2=A0 Title: Dis= crete Log Equality Proofs over secp256k1
=C2=A0 Author: Andrew Toth <= andre...@gmail.com>
= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Ruben Somsen <rso...@gmail.com>
=C2=A0 Comments-URI: TBD=C2=A0 Status: Draft
=C2=A0 Type: Standards Track
=C2=A0 License: BS= D-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 proposes a standard for 64-byte zero-knowledge = ''discrete logarithm equality proofs'' (DLEQ proofs) over t= he elliptic curve ''secp256k1''. For given elliptic curve p= oints ''A'', ''B'', and ''C'= 9;, the prover proves knowledge of a scalar ''a'' such that= ''A =3D a=E2=8B=85G'' and ''C =3D a=E2=8B=85B'= ' 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 =3D a=E2=8B=85B'', the proof establi= shes that the same secret key ''a'' is used for generating = both ''A'' and ''C'' without revealing '= ;'a''.

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

This documen= t 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 BIP352] requires senders to compute output scripts using ECDH shared= secrets from the same secret keys used to sign the inputs. Generating an i= ncorrect signature will produce an invalid transaction that will be rejecte= d by consensus. An incorrectly generated output script can still be consens= us-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 p= rove to other entities that the output scripts have been generated correctl= y without revealing the private keys.

=3D=3D Specification =3D=3D
All conventions and notations are used as defined in [https://github.com/= bitcoin/bips/blob/master/bip-0327.mediawiki#user-content-Notation BIP32= 7].

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

Input:
* The= secret key ''a'': a 256-bit unsigned integer
* The publ= ic key ''B'': a point on the curve
* Auxiliary random da= ta ''r'': a 32-byte array

The algorithm ''Pr= ove(a, B, r)'' is defined as:
* Fail if ''a =3D 0'&#= 39; or ''a &ge; n''.
* Fail if ''is_infinite= (B)''.
* Let ''A =3D a=E2=8B=85G''.
* Let = 9;'C =3D a=E2=8B=85B''.
* Let ''t'' be the b= yte-wise xor of ''bytes(32, a)'' and ''hash<sub&= gt;BIP?/aux</sub>(r)''.
* Let ''rand =3D hash<s= ub>DLEQ</sub>(t || cbytes(A) || cytes(C))''.
* Let '= ;'k =3D int(rand) mod n''.
* Fail if ''k =3D 0'&= #39;.
* Let ''R<sub>1</sub> =3D k=E2=8B=85G''= ;.
* Let ''R<sub>2</sub> =3D k=E2=8B=85B''.<= br>* Let ''e =3D int(hash<sub>DLEQ</sub>(cbytes(A) || c= bytes(B) || cbytes(C) || cbytes(R<sub>1</sub>) || cbytes(R<s= ub>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 p= roof ''proof''.

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

Input:
* The public key of the secret key used in the p= roof generation ''A'': a point on the curve
* The public= key used in the proof generation ''B'': a point on the cur= ve
* The result of multiplying the secret and public keys used in the pr= oof generation ''C'': a point on the curve
* A proof = 9;'proof'': a 64-byte array

The algorithm ''Veri= fyProof(A, B, C, proof)'' is defined as:
* Let ''e =3D i= nt(proof[0:32])''.
* Let ''s =3D int(proof[32:64])'&= #39;; fail if ''s &ge; n''.
* Let ''R<sub= >1</sub> =3D s=E2=8B=85G - e=E2=8B=85A''.
* Fail if = 9;'is_infinite(R<sub>1</sub>)''.
* Fail if '= 'not has_even_y(R<sub>1</sub>)''.
* Let '= 9;R<sub>2</sub> =3D s=E2=8B=85B - e=E2=8B=85C''.
* F= ail if ''is_infinite(R<sub>2</sub>)''.
* Fai= l if ''not has_even_y(R<sub>2</sub>)''.
* Fa= il if ''e =E2=89=A0 int(hash<sub>BIP?/DLEQ</sub>(cbytes= (A) || cbytes(B) || cbytes(C) || cbytes(R<sub>1</sub>) || cbyte= s(R<sub>2</sub>)))''.
* Return success iff no failur= e occurred before reaching this point.

=3D=3D Test Vectors and Refer= ence Code =3D=3D

TBD

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

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

<references />

=3D=3D Acknowl= edgements =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/77ad84ed-2ff8-4929-b8da-d940c95d18a7n%40googlegroups.com.
------=_Part_74723_787826626.1729867742479-- ------=_Part_74722_461499448.1729867742479--