Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3A576C002A for ; Mon, 1 May 2023 12:46:45 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 155CE81FD3 for ; Mon, 1 May 2023 12:46:45 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 155CE81FD3 Authentication-Results: smtp1.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20221208 header.b=W51dxUGJ X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id RQqsn0J1CBkE for ; Mon, 1 May 2023 12:46:44 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 0217881FCE Received: from mail-ua1-x92c.google.com (mail-ua1-x92c.google.com [IPv6:2607:f8b0:4864:20::92c]) by smtp1.osuosl.org (Postfix) with ESMTPS id 0217881FCE for ; Mon, 1 May 2023 12:46:43 +0000 (UTC) Received: by mail-ua1-x92c.google.com with SMTP id a1e0cc1a2514c-77d049b9040so7784738241.1 for ; Mon, 01 May 2023 05:46:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20221208; t=1682945203; x=1685537203; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=6lMHuJzjjq7nZkAdPY/6u9IJyfRSVWgM4eKe9mgf+Es=; b=W51dxUGJcnlyr0dGEKY0KQNW+tcBiBvt+pPRUA/AkrZdopsQgebgDXqlk8kMd4zp7D 1EMiV+qqvJtHYlSoGqU65yMG6UdFdSKi61wu4Iblk8QQunwZkCWPT0WlrkTpUh7FbtEl VVsf+4KIwOykWagVTE/EhT946AV8Plnux3ot4r6s/7eXFxptvLJCSBEaxy6mP4yFcEI6 jZoIN/VTCsS9qhg7q7bcbfP6Raart49AD4edPNmQVf8c2a+HyuNJwSPXrYrOmuKsRPJE iZCgCGmlmiNET97AgRR0attr6av+g6dxHI3km+6BQow/DxQxk6a0/8ldbye+oytA+m/d OVrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1682945203; x=1685537203; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=6lMHuJzjjq7nZkAdPY/6u9IJyfRSVWgM4eKe9mgf+Es=; b=enxNYOh0W6EyfV03XvDhK4TvIwuL7F6qwkoGgjXdpuTmZOg23N6MCcBVq/X4gAAosV f6j4nyd9EJWmf7qRL28EfvBNZNRsxPMe6kxody9+I06t8i139A7ZzQ3TNfQs9GXq84rd wgAIpBlrC2v7x+UZ0j64nhoo+Bk48ZcA8nG/x50tmxmtoEHTl9CW1K1LpUcrrHiJNxXb oEZjyAg8GBO9SIE81ccUVIANsVXupAzpx9LZNqnHOQG0XXrrc4XrMmO+5oXkQ9gBsJRC svxXF+Hbldj+Pj4ru8bfFakhSICxxK+nBWS42QyuMGyXllOBqeLUt7T4tdU3yW5pISNC Ckeg== X-Gm-Message-State: AC+VfDwEl0zOazlXLZAj9lb3ZLd/JyTqrQVMAloSLxuqDTHQQLfeveC5 H1Fghzq80LsxJfoS3lVMe047W0Rm1Hw3Pw1dEYkXOfcYQ2qsQ33j X-Google-Smtp-Source: ACHHUZ6GYdlUZjkTp/BMrZDollRPuBCJUPVYRIn1j2/Bu8jRLUgdYuZ3Rxjo5sYU4uVy4TBr0oxPzs/70M6LtU3GSl4= X-Received: by 2002:a1f:c642:0:b0:401:6b30:5eef with SMTP id w63-20020a1fc642000000b004016b305eefmr4562039vkf.8.1682945202644; Mon, 01 May 2023 05:46:42 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Weiji Guo Date: Mon, 1 May 2023 20:46:30 +0800 Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="000000000000faec7c05faa136d9" X-Mailman-Approved-At: Mon, 01 May 2023 12:52:09 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] proposal: new opcode OP_ZKP to enable ZKP-based spending authorization X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 01 May 2023 12:46:45 -0000 --000000000000faec7c05faa136d9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi ZmnSCPxj, Thank you very much for your insights. You are definitely right about making the verification keys consensus-critical and about how the weight units. I totally agree that the weighting of ZKP the witness should be higher. We will carry out some benchmarking to recommend a reasonable weight when we start to develop a GitHub PR. Meanwhile, as we can potentially aggregate many proofs or recursively verify even more, the average cost might still be manageable. Regards, Weiji On Sun, Apr 30, 2023 at 10:16=E2=80=AFAM ZmnSCPxj = wrote: > Good morning Weiji, > > Have not completed reading, but this jumped out to me: > > > > > 3. Dealing with system limitation: verification keys could be very lon= g > and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be put int= o > configurations and only use their hash in the scriptPubKey. The > configuration information such as new verification keys could be propagat= ed > through P2P messages (we might need a separate BIP for this); > > `scriptPubKey` is consensus-critical, and these new P2P messages would > have to be consensus-critical. > > As all nodes need to learn the new verification keys, we should consider > how much resources are spent on each node just to maintain and forever > remember verification keys. > > Currently our resource-tracking methodology is via the synthetic "weight > units" computation. > This reflects resources spent on acquiring block data, as well as > maintaining the UTXO database. > For instance, the "witness discount" where witness data (i.e. modern > equivalent of `scriptSig`) is charged 1/4 the weight units of other data, > exists because spending a UTXO reduces the resources spent in the UTXO > database, although still consumes resources in downloading block data > (hence only a discount, not free or negative/rebate). > > Similarly, any propagation of verification keys would need a similar > adjustment for weight units. > > As verification keys MUST be seen by all nodes before they can validate a= n > `OP_ZKP`, I would suggest that it is best included in block data (which > similarly needs to be seen by all nodes), together with some weight unit > adjustment for that data, depending on how much resources verification ke= ys > would consume. > This is similar to how `scriptPubKey`s and amounts are included in block > data, as those data are kept in the UTXO database, which nodes must > maintain in order to validate the blockchain. > > If verification keys are permanent, they should probably be weighted > heavier than `scriptPubKey`s and amounts --- UTXOs can theoretically be > deleted later by spending the UTXO (which reduces UTXO database size), > while any data that must be permanently stored in a database must > correspondingly be weighted higher. > > Similarly, my understanding is that the CPU resources needed by validatio= n > of generic ZKPs is higher than that required for validation of ECC > signatures. > Much of the current weight calculation assumes that witness data is > primarily ECC signatures, so if ZKP witnesses translate to higher resourc= e > consumption, the weighting of ZKP witnesses should also be higher (i.e. > greater than the 1/4 witness-discounted weight of current witness data). > > Regards, > ZmnSCPxj > --000000000000faec7c05faa136d9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi ZmnSCPxj,

Thank you very much for yo= ur insights. You are definitely right about making the verification keys co= nsensus-critical and about how the weight units. I totally agree that the w= eighting of ZKP the witness should be higher. We will carry out some benchm= arking to recommend a reasonable weight when we start to develop a GitHub P= R.

Meanwhile, as we can potentially aggregate many= proofs or recursively verify even more, the average cost might still be ma= nageable.

Regards,
Weiji

=
On Sun, Ap= r 30, 2023 at 10:16=E2=80=AFAM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
Good morning Weiji,

Have not completed reading, but this jumped out to me:



> 3.=C2=A0 Dealing with system limitation: verification keys could be ve= ry long and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be p= ut into configurations and only use their hash in the scriptPubKey. The con= figuration information such as new verification keys could be propagated th= rough P2P messages (we might need a separate BIP for this);

`scriptPubKey` is consensus-critical, and these new P2P messages would have= to be consensus-critical.

As all nodes need to learn the new verification keys, we should consider ho= w much resources are spent on each node just to maintain and forever rememb= er verification keys.

Currently our resource-tracking methodology is via the synthetic "weig= ht units" computation.
This reflects resources spent on acquiring block data, as well as maintaini= ng the UTXO database.
For instance, the "witness discount" where witness data (i.e. mod= ern equivalent of `scriptSig`) is charged 1/4 the weight units of other dat= a, exists because spending a UTXO reduces the resources spent in the UTXO d= atabase, although still consumes resources in downloading block data (hence= only a discount, not free or negative/rebate).

Similarly, any propagation of verification keys would need a similar adjust= ment for weight units.

As verification keys MUST be seen by all nodes before they can validate an = `OP_ZKP`, I would suggest that it is best included in block data (which sim= ilarly needs to be seen by all nodes), together with some weight unit adjus= tment for that data, depending on how much resources verification keys woul= d consume.
This is similar to how `scriptPubKey`s and amounts are included in block da= ta, as those data are kept in the UTXO database, which nodes must maintain = in order to validate the blockchain.

If verification keys are permanent, they should probably be weighted heavie= r than `scriptPubKey`s and amounts --- UTXOs can theoretically be deleted l= ater by spending the UTXO (which reduces UTXO database size), while any dat= a that must be permanently stored in a database must correspondingly be wei= ghted higher.

Similarly, my understanding is that the CPU resources needed by validation = of generic ZKPs is higher than that required for validation of ECC signatur= es.
Much of the current weight calculation assumes that witness data is primari= ly ECC signatures, so if ZKP witnesses translate to higher resource consump= tion, the weighting of ZKP witnesses should also be higher (i.e. greater th= an the 1/4 witness-discounted weight of current witness data).

Regards,
ZmnSCPxj
--000000000000faec7c05faa136d9--