path: root/40/b67acd42c3001c87aaeb8a73a247b13592a425

Return-Path: <weiji.g@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id C3672C002A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:29:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id 8B59160AB7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:29:26 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 8B59160AB7
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20221208 header.b=EoNXtSLs
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.698
X-Spam-Level: 
X-Spam-Status: No, score=-0.698 tagged_above=-999 required=5
 tests=[BAYES_05=-0.5, 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 smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id wkQh972eMe-m
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:29:24 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 2EF7460A97
Received: from mail-vk1-xa30.google.com (mail-vk1-xa30.google.com
 [IPv6:2607:f8b0:4864:20::a30])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 2EF7460A97
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 08:29:24 +0000 (UTC)
Received: by mail-vk1-xa30.google.com with SMTP id
 71dfb90a1353d-4404923f23eso3496236e0c.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 28 Apr 2023 01:29:24 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20221208; t=1682670562; x=1685262562;
 h=to:subject:message-id:date:from:mime-version:from:to:cc:subject
 :date:message-id:reply-to;
 bh=N4Vl5C9qyB1XK8XUyg+T7WgVp+HkbEXO3+LwKBGaQmM=;
 b=EoNXtSLsq15Ba77mIT6Ej+2/YvSfkpJ+R1ZdWbozovUo6gyGvufd4tfe6wbgkoFPWy
 urEoR3F4NuxLTX98jplQ0nzsGNbFWR7rzKYZrweSUsrnCYrnOBo3wRF/aXZkXBIkST4X
 53mWPnz6IQuuP9KVQ3of0+Z5/+DCxWjD+LJyn9b5xVV0HC3WexdS3/TmKUwVPRn5bPN4
 ngIDuSjCncRQfigSIRK0IjzCs1pUpBnDyIvbHQcT6snS/YX3hXPrBAExpYXnIUBeindh
 +GwwENW1CVPqtVd3uyS2abiVLaEcMZ3YZWPbeb5XqX++C9MJ2iIdT0E8WKuvxF3BhYb6
 RyfA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20221208; t=1682670562; x=1685262562;
 h=to:subject:message-id:date:from:mime-version:x-gm-message-state
 :from:to:cc:subject:date:message-id:reply-to;
 bh=N4Vl5C9qyB1XK8XUyg+T7WgVp+HkbEXO3+LwKBGaQmM=;
 b=AivD30OHSclXVk0F8HTuSQG2V42VFXFGMs+pd0BkjCJ+952GN8Kc3FMKIbNfz1MF51
 nQvRLoxhcbUZi4rlEiM4LeTM71py5C7uw53GDI1KbsazjL8yPzO8oNqU4+L7+Bioe47R
 39VAlBGwNcQBgeccMZ6q8dYgv/kt9/egAGveIk3o5LGZbRiXaG6AUh9HgbkWnTOq9Frh
 bOKFRiwnOJ+WL6xT6sVY1QGErroL1TvuuxDdQuEYbIpX/xgiZIclGerMK3rrukMcJ5Jq
 8ZUdSUtJb/j+RBFCgPED2mVxSyUoLnpwX61T+CL66q37074qkDeImFpvhs87mrX4HvND
 k6Yg==
X-Gm-Message-State: AC+VfDyH9tM1eQhr7IlltKu0rc+1PtBOxw2Co7/OcS3Wm0ZTm94oFyqM
 WZPvPqcbXKn+0XWIn/H6wFHgCBensdFezhulKg2JLT+k0rE=
X-Google-Smtp-Source: ACHHUZ7WYBYwk44nU9/4DrVIaFD1CgeJSZ7LIy1hbwZvBs/Dm9Ixe/dr6KO8KPIUpgo0rTVcBhfCOUxAERttoajDtZM=
X-Received: by 2002:a1f:5744:0:b0:436:1ead:e50e with SMTP id
 l65-20020a1f5744000000b004361eade50emr1698274vkb.1.1682670562255; Fri, 28 Apr
 2023 01:29:22 -0700 (PDT)
MIME-Version: 1.0
From: Weiji Guo <weiji.g@gmail.com>
Date: Fri, 28 Apr 2023 16:29:10 +0800
Message-ID: <CA+ydi=LtskFh89TW75=CBwbdZzWR-ZjWS77TnrF4G+xUfm8z+Q@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="00000000000023278505fa6145f9"
X-Mailman-Approved-At: Sat, 29 Apr 2023 16:19:45 +0000
Subject: [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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 28 Apr 2023 08:29:26 -0000

--00000000000023278505fa6145f9
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hey everyone,


I am writing this email to propose a new opcode to enable zero knowledge
based spending authorization for Bitcoin. This new opcode OP_ZKP will
enable the Bitcoin network to authorize spending based on off-chain
computation, provided acceptable proof is supplied. This will not only
equip the Bitcoin script with Turing completeness, but also enable the
building of payment channels more flexible, stablecoin, decentralized
exchange, DeFi, etc. directly over the Bitcoin network, or even a layer 2.
All these could be accomplished with a soft fork (and follow-up building).


Before any BIP could be requested, I=E2=80=99d like to discuss all the aspe=
cts in
more detail, to cover as many corners as possible, and hopefully to build
consensus among developers and the community.


*### 0. Overview*

Here are what I am currently considering, listed as starting points for
discussion. I hope that I have covered all major issues, but please do feel
free to add more.



   1. How it works: we add OP_ZKP and OP_ZKPVERIFY using some unused OP_NOP
   codes. OP_ZKP works similarly to OP_MULTISIG, with a number parameter to
   indicate how many public inputs are to be read;
   2. Security: to bind the spending conditions to certain UTXO set,
   amount, and recipients, the hash of all this information shall be used a=
s
   public input to the proof;
   3. Dealing with system limitation: verification keys could be very long
   and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be put in=
to
   configurations and only use their hash in the scriptPubKey. The
   configuration information such as new verification keys could be propaga=
ted
   through P2P messages (we might need a separate BIP for this);
   4. Scalability: arrangement for miners or computing power vendors to
   aggregate some proofs for scalability and fee reduction. Alternatively,
   this could be accomplished with recursive proof.
   5. ZKP scheme and curve choices.
   6. Potential uses are unlimited, although there is no apparent secret
   key (private key or seed) in play.
   7. Ecology implications. Impacts on wallets, etc.


Below, I will introduce/discuss the above-listed item one by one. Mostly I
have to keep the discussion minimal and brief. It is still a bit lengthy,
please bear with me.


*### 1. How it works*

Consider below script:


scriptPubKey: <hash of the verification key> <Groth16_BN254> OP_ZKP

scriptSig: <pubInput_1> <pubInput_2> =E2=80=A6 <pubInput_n> <n> <proof>


<Groth16_BN254> is only an example in place of an indicator for the ZKP
scheme and curve parameters. Other combinations are possible. Further
discussion is provided in section 5.


<hash of the verification key> - the node implementation should look up a
verification key that hashed to this value. Verification keys tend to be
long and exceed the limitation imposed by MAX_SCRIPT_ELEMENT_SIZE (520
bytes). And for various schemes/circuits, the size might be different. So a
hash is used here. Further discussion is covered in section 3.


<proof> refers to the proof data to be verified. Its size is also subject
to MAX_SCRIPT_ELEMENT_SIZE. This might limit our choices of the ZKP scheme,
although proof data could be split into several parts.


<n> refers to how many public inputs are to be read. It should depend on
the circuit in use. However, this is *not* the actual number. There is also
an implicit public input, which is the hash of the transaction, calculated
according to the script context.


The evaluation is pretty straightforward. The implementation of OP_ZKP
reads in (and removes) all its parameters from the stack, calculates the
implicit public input from the transaction (UTXO inputs, amount,
recipients, etc.), and then leave a true or false in the stack after ZKP
verification. The security reason behind this implicit public input design
is discussed in the next section.


OP_ZKPVERIFY works the same except for the last step, where it leaves
nothing or fails the verification.


*### 2. Security: replay protection*

Proof should not be replayed to authorize spending of another set of UTXO.
Therefore it is critical to bind the proof to the transaction. This is
similar to OP_CHECKSIG: the transaction hash is needed to verify the proof
for OP_ZKP. To calculate the hash, just follow what the context requires.
For a SegWit transaction, BIP 0143 seems natural. And most of the time this
will be the case. But if those opcodes are indeed used outside of SegWit,
then the hashing algorithm before SegWit should be fine.


Binding proof to the transaction, especially the UTXO entries, also
protects from proof malleability, since once spent, the UTXO entries will
be removed from the available UTXO set.


On the other hand, since proof could be calculated by anybody given the
witness, circuit developers must take this into account. The private inputs
should be kept confidential. In some other uses, there might not be any
private inputs but only an authoritative signature, then it is the
authority=E2=80=99s responsibility to only sign valid information, and circ=
uit
developers=E2=80=99 responsibility to ensure proper protection. Further dis=
cussion
is deferred for now.


*### 3. Dealing with system limitations: verification key*

The size of proof data or verification key could exceed the limitation
imposed by MAX_SCRIPT_ELEMENT_SIZE, which is 520 (bytes). In this section,
we discuss its implications for the verification key.


The size of a verification key varies with different schemes and circuits.
However, the number of total different circuits will be rather limited, at
least at the Bitcoin network level. Therefore, using the hash of the
verification key instead of the key itself renders fixed-size data, and
flexibility without worrying if the verification key gets too long.


Further, it is not advisable to hard code the verification key in the code
base of nodes, as new verification keys arise every few days or months.
Rather, P2P messaging seems a suitable way to propagate new verification
keys. Once received, a node could save it to a configuration file, and also
forward it to other nodes. If an unknown hash is encountered, the node
could also request it from its connected peers. If the node cannot gather a
new verification key in time, then it has to fail the transaction
verification. If too many nodes cannot get the new verification key in
time, the new block containing the offending transaction will not be
accepted by the Bitcoin network. It is suggested that a separate BIP be
requested to address these issues.


*### 4. Scalability*

ZKP verification usually costs at least tens of milli-seconds, and might
also cost more data size. So, it should be fine to have a few dozen ZKP
transactions in a block. But a few thousand will cost too much time to
verify and too much block space. In this section, we discuss how this could
be mitigated.


There are two options: proof aggregation (batching), and recursive
verification.


Some ZKP proofs are known to be capable of aggregation, however, with
certain limitations. For example, aggregating Groth16 proofs seems to
require that all proofs are of the same circuit, so that the value of =CE=
=B3 and
=CE=B4 remain the same across different proofs, as both parameters are from
phase 2 setup, thus circuit specific. We can also aggregate KZG polynomial
commitment scheme-based proofs. Still, the aggregator needs to ensure that
the hash of each transaction has been verified as well.


On the other hand, recursive verification can handle these transaction hash
verification, along with verifying the correctness of each proof. It might
be very computationally intensive to generate a recursive proof for a few
thousand proofs but there are lots of room for further optimization.


It is also possible to develop a hybrid strategy, that some proofs are
aggregated, with additional verification being proved, then both the
aggregation and additional proof could be verified by a recursive proof.


We might need a new SegWit version so that transactions can refer to its
proper proof once aggregated or recursively verified.


Replay protection: once aggregated or proved via recursion to the network,
a transaction cannot be played to the Bitcoin network again, as the UTXO
entries have been spent.


*### 5. ZKP scheme and curve choice*

A major concern is the size of the script, proof, cost of verification, and
the feasibility to aggregate/batching many proofs.


Groth16 checks out here with short proof size, cheap verification, and
feasibility to aggregate. For example, the standard draft here ([1]) shows
an implementation that can aggregate 1024 proofs in 2s and verifies them in
23ms. Although it seems to require that all proofs belong to the same
circuit ( due to =CE=B3 and =CE=B4, which are circuit-specific). Still, the=
 short
proof size and cheap verification cost make Groth16 suitable to verify
other proofs recursively. And when the upper layer proving schemes (and
setup) is the same, so are the verification circuits, therefore those
proofs could be aggregated.


On the other hand, KZG commitment supports batching. So the zkSnarks based
on KZG should support as well. Further, this paper by Boneh, etc. ([2])
enhances KZG commitment to allow one or two group element opening for
multiple polynomials each evaluated at a different set of points.


This is not an exhaustive list, not even a list. Overall, if we can
aggregate/batch many proofs together, then proof size is of smaller
concern. In this case, Plonk might be a better scheme than Groth16, if we
can implement a batching technique to batch proofs from different circuits
together. But still, in the beginning, there might not be many proofs to be
batched/aggregated at all.


We shall designate a parameter to OP_ZKP and OP_ZKPVERIFY to indicate which
scheme (and curve) to use.


For curve, BN254 is a natural choice as it has been adopted by many
blockchain projects. However, this is largely an open issue.


All being said, as a proposal, it is my opinion that we should support
Groth16-BN254 at the beginning. Based on that we could build recursive
verification circuits for other scheme, which does not require a soft fork.
Other schemes and curves, if much desired by the community, could be
included as well. Maybe we can designate a separate BIP for each
scheme-curve pair for direct support (instead of recursive verification).


*### 6. Potential uses*

The potential uses are unlimited: payment aggregation for a fee reduction
or anonymity, stablecoin, DeFi, decentralized exchange, DAO, NFT, etc.,
just to name a few. But still, we could take as an example some uses to
check if any issues arise and discuss how to address them.


A. ZKP-based smart contract. We could reasonably assume ZKP-based smart
contracts to be rather different from consensus-based smart contracts
(although OP_ZKP is part of a script). A notable difference is that with
Bitcoin=E2=80=99s UTXO model instead of account-model, account-balance type=
 of
contracts are hard to build without involving external storage or state
management. And even with external storage involved to manage the states,
the security of the external storage is also a concern. Data might be lost
or corrupted. Bitcoin=E2=80=99s security does not extend to those contracts
automatically. It takes innovations to address these issues.


On the other hand, there could be smart contracts without a need for
explicit state management. This could be gaming or decentralized identity,
that a ZKP proof is used to prove =E2=80=9Dsomething happens or exists acco=
rding to
designated algorithm or criteria=E2=80=9C.


B. Payment aggregation, or Bitcoin Layer 2. Every address can participate
in such a protocol by sending certain Bitcoin to the designated address
(the fund-holding address). Once signed up, participants can send Bitcoin
to each other with very little fee or pays a higher fee to send to Layer 1.
Bookkeeping each participant=E2=80=99s =E2=80=9Cbalance=E2=80=9D is a chall=
enge, but might be
achievable via some complex circuits proving the ownership of certain UTXO
entries. Once proven, the fund-holding address can send Bitcoins to the
address as requested by the participant. It is another challenge to
maintain those UTXO entries off the Bitcoin network with high security. We
might also need to segregate those UXTOs from the Bitcoin network so that
no transaction can be replayed to the Bitcoin network or another Layer 2
protocol.


*### 7. Ecology implications*

Proof generation, computing power services/vendors. Some proof might be
very computationally intensive to generate, for example, recursive
verification of thousands of OP_ZKP transactions. In that case, computation
power services or vendors can work with miners to speed up the generation,
or simply propose a bundle of transactions to be included in a block. By
paying a higher fee miners are motivated to include the bundle, while the
service or vendor can still profit a lot. The immediate reward could
incentivize lots of efforts to further optimize the implementation,
engineering, algorithms, or even ZKP schemes.


Contract composability. We need to figure out a systematic way for one
smart contract to call another, either on-chain or assisted-off-chain. For
ZKP-based smart contracts, proof will have to be generated off-chain and
then used later to call the target contract. Off-chain vendors could
monitor closely related signals, generate the proof, and submit it to the
Bitcoin network. There should be incentives to ensure the proper running of
the system. It is still an open issue about how to define a cross-contract
API, how to signal the call, and how to incentivize computation power
vendors.


Impact on wallet applications. Generating proof to authorize spending seems
a heavy-duty computation task, and does not seem to fit into mobile
applications or hardware wallets, especially those with SoC and powered by
a small battery. However, we argue that this is not the case. If no secret
(private key or seed) is involved, there is no need to involve a wallet
that is tasked with safekeeping secrets. In such cases, the ZKP proof could
be proof that something has indeed happened or exists (including a
signature issued from a wallet), which makes up spending conditions.




That's it for now. I hope you are interested in this idea. I look forward
to your comments.


Thanks,

Weiji


[1] -
https://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-aggreg=
ation.pdf

[2] - https://eprint.iacr.org/2020/081.pdf

--00000000000023278505fa6145f9
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">





<p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&qu=
ot;;min-height:15px">Hey everyone,<br></p><p class=3D"gmail-p1" style=3D"ma=
rgin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p c=
lass=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;"=
>I am writing this email to propose a new opcode to enable zero knowledge b=
ased spending authorization for Bitcoin. This new opcode OP_ZKP will enable=
 the Bitcoin network to authorize spending based on off-chain computation, =
provided acceptable proof is supplied. This will not only equip the Bitcoin=
 script with Turing completeness, but also enable the building of payment c=
hannels more flexible, stablecoin, decentralized exchange, DeFi, etc. direc=
tly over the Bitcoin network, or even a layer 2. All these could be accompl=
ished with a soft fork (and follow-up building).</p><p class=3D"gmail-p1" s=
tyle=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><b=
r></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica N=
eue&quot;">Before any BIP could be requested, I=E2=80=99d like to discuss a=
ll the aspects in more detail, to cover as many corners as possible, and ho=
pefully to build consensus among developers and the community.=C2=A0</p><p =
class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;=
;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13=
px &quot;Helvetica Neue&quot;"><b>### 0. Overview</b></p><p class=3D"gmail-=
p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Here are what=
 I am currently considering, listed as starting points for discussion. I ho=
pe that I have covered all major issues, but please do feel free to add mor=
e.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica N=
eue&quot;;min-height:15px"><br></p><ol class=3D"gmail-ol1" style=3D"list-st=
yle-type:decimal">
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">How it works: we add OP_ZKP and OP_ZKPVERIFY using some unused OP_NO=
P codes. OP_ZKP works similarly to OP_MULTISIG, with a number parameter to =
indicate how many public inputs are to be read;</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">Security: to bind the spending conditions to certain UTXO set, amoun=
t, and recipients, the hash of all this information shall be used as public=
 input to the proof;</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">Dealing with system limitation: verification keys could be very long=
 and exceed the MAX_SCRIPT_ELEMENT_SIZE (520 bytes). They could be put into=
 configurations and only use their hash in the scriptPubKey. The configurat=
ion information such as new verification keys could be propagated through P=
2P messages (we might need a separate BIP for this);</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">Scalability: arrangement for miners or computing power vendors to ag=
gregate some proofs for scalability and fee reduction. Alternatively, this =
could be accomplished with recursive proof.=C2=A0</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">ZKP scheme and curve choices.=C2=A0</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">Potential uses are unlimited, although there is no apparent secret k=
ey (private key or seed) in play.=C2=A0</li>
<li class=3D"gmail-li3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&=
quot;">Ecology implications. Impacts on wallets, etc.</li>
</ol><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Ne=
ue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px=
;font:13px &quot;Helvetica Neue&quot;">Below, I will introduce/discuss the =
above-listed item one by one. Mostly I have to keep the discussion minimal =
and brief. It is still a bit lengthy, please bear with me.=C2=A0</p><p clas=
s=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min=
-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &=
quot;Helvetica Neue&quot;"><b>### 1. How it works</b></p><p class=3D"gmail-=
p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Consider belo=
w script:</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helv=
etica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"ma=
rgin:0px;font:13px &quot;Helvetica Neue&quot;">scriptPubKey: &lt;hash of th=
e verification key&gt; &lt;Groth16_BN254&gt; OP_ZKP</p><p class=3D"gmail-p3=
" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">scriptSig: &lt;=
pubInput_1&gt; &lt;pubInput_2&gt; =E2=80=A6 &lt;pubInput_n&gt; &lt;n&gt; &l=
t;proof&gt;</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;He=
lvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"=
margin:0px;font:13px &quot;Helvetica Neue&quot;">&lt;Groth16_BN254&gt; is o=
nly an example in place of an indicator for the ZKP scheme and curve parame=
ters. Other combinations are possible. Further discussion is provided in se=
ction 5.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helve=
tica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"mar=
gin:0px;font:13px &quot;Helvetica Neue&quot;">&lt;hash of the verification =
key&gt; - the node implementation should look up a verification key that ha=
shed to this value. Verification keys tend to be long and exceed the limita=
tion imposed by MAX_SCRIPT_ELEMENT_SIZE (520 bytes). And for various scheme=
s/circuits, the size might be different. So a hash is used here. Further di=
scussion is covered in section 3.=C2=A0</p><p class=3D"gmail-p1" style=3D"m=
argin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p =
class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;=
">&lt;proof&gt; refers to the proof data to be verified. Its size is also s=
ubject to MAX_SCRIPT_ELEMENT_SIZE. This might limit our choices of the ZKP =
scheme, although proof data could be split into several parts.</p><p class=
=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-=
height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &q=
uot;Helvetica Neue&quot;">&lt;n&gt; refers to how many public inputs are to=
 be read. It should depend on the circuit in use. However, this is *not* th=
e actual number. There is also an implicit public input, which is the hash =
of the transaction, calculated according to the script context.=C2=A0</p><p=
 class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot=
;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:1=
3px &quot;Helvetica Neue&quot;">The evaluation is pretty straightforward. T=
he implementation of OP_ZKP reads in (and removes) all its parameters from =
the stack, calculates the implicit public input from the transaction (UTXO =
inputs, amount, recipients, etc.), and then leave a true or false in the st=
ack after ZKP verification. The security reason behind this implicit public=
 input design is discussed in the next section.</p><p class=3D"gmail-p1" st=
yle=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br=
></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Ne=
ue&quot;">OP_ZKPVERIFY works the same except for the last step, where it le=
aves nothing or fails the verification.</p><p class=3D"gmail-p1" style=3D"m=
argin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p =
class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;=
"><b>### 2. Security: replay protection</b></p><p class=3D"gmail-p3" style=
=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Proof should not be re=
played to authorize spending of another set of UTXO. Therefore it is critic=
al to bind the proof to the transaction. This is similar to OP_CHECKSIG: th=
e transaction hash is needed to verify the proof for OP_ZKP. To calculate t=
he hash, just follow what the context requires. For a SegWit transaction, B=
IP 0143 seems natural. And most of the time this will be the case. But if t=
hose opcodes are indeed used outside of SegWit, then the hashing algorithm =
before SegWit should be fine.</p><p class=3D"gmail-p1" style=3D"margin:0px;=
font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"g=
mail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Binding =
proof to the transaction, especially the UTXO entries, also protects from p=
roof malleability, since once spent, the UTXO entries will be removed from =
the available UTXO set.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:1=
3px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p=
3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">On the other h=
and, since proof could be calculated by anybody given the witness, circuit =
developers must take this into account. The private inputs should be kept c=
onfidential. In some other uses, there might not be any private inputs but =
only an authoritative signature, then it is the authority=E2=80=99s respons=
ibility to only sign valid information, and circuit developers=E2=80=99 res=
ponsibility to ensure proper protection. Further discussion is deferred for=
 now.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetic=
a Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin=
:0px;font:13px &quot;Helvetica Neue&quot;"><b>### 3. Dealing with system li=
mitations: verification key</b></p><p class=3D"gmail-p3" style=3D"margin:0p=
x;font:13px &quot;Helvetica Neue&quot;">The size of proof data or verificat=
ion key could exceed the limitation imposed by MAX_SCRIPT_ELEMENT_SIZE, whi=
ch is 520 (bytes). In this section, we discuss its implications for the ver=
ification key.=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px=
 &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" =
style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">The size of a ver=
ification key varies with different schemes and circuits. However, the numb=
er of total different circuits will be rather limited, at least at the Bitc=
oin network level. Therefore, using the hash of the verification key instea=
d of the key itself renders fixed-size data, and flexibility without worryi=
ng if the verification key gets too long.=C2=A0</p><p class=3D"gmail-p1" st=
yle=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br=
></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Ne=
ue&quot;">Further, it is not advisable to hard code the verification key in=
 the code base of nodes, as new verification keys arise every few days or m=
onths. Rather, P2P messaging seems a suitable way to propagate new verifica=
tion keys. Once received, a node could save it to a configuration file, and=
 also forward it to other nodes. If an unknown hash is encountered, the nod=
e could also request it from its connected peers. If the node cannot gather=
 a new verification key in time, then it has to fail the transaction verifi=
cation. If too many nodes cannot get the new verification key in time, the =
new block containing the offending transaction will not be accepted by the =
Bitcoin network. It is suggested that a separate BIP be requested to addres=
s these issues.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quo=
t;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=
=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;"><b>### 4. Scalability<=
/b></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica =
Neue&quot;">ZKP verification usually costs at least tens of milli-seconds, =
and might also cost more data size. So, it should be fine to have a few doz=
en ZKP transactions in a block. But a few thousand will cost too much time =
to verify and too much block space. In this section, we discuss how this co=
uld be mitigated.=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:1=
3px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p=
3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">There are two =
options: proof aggregation (batching), and recursive verification.</p><p cl=
ass=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;m=
in-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px=
 &quot;Helvetica Neue&quot;">Some ZKP proofs are known to be capable of agg=
regation, however, with certain limitations. For example, aggregating Groth=
16 proofs seems to require that all proofs are of the same circuit, so that=
 the value of =CE=B3 and =CE=B4 remain the same across different proofs, as=
 both parameters are from phase 2 setup, thus circuit specific. We can also=
 aggregate KZG polynomial commitment scheme-based proofs. Still, the aggreg=
ator needs to ensure that the hash of each transaction has been verified as=
 well.=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;H=
elvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D=
"margin:0px;font:13px &quot;Helvetica Neue&quot;">On the other hand, recurs=
ive verification can handle these transaction hash verification, along with=
 verifying the correctness of each proof. It might be very computationally =
intensive to generate a recursive proof for a few thousand proofs but there=
 are lots of room for further optimization.=C2=A0</p><p class=3D"gmail-p1" =
style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><=
br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica =
Neue&quot;">It is also possible to develop a hybrid strategy, that some pro=
ofs are aggregated, with additional verification being proved, then both th=
e aggregation and additional proof could be verified by a recursive proof.<=
/p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue=
&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;f=
ont:13px &quot;Helvetica Neue&quot;">We might need a new SegWit version so =
that transactions can refer to its proper proof once aggregated or recursiv=
ely verified.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;=
Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=
=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Replay protection: onc=
e aggregated or proved via recursion to the network, a transaction cannot b=
e played to the Bitcoin network again, as the UTXO entries have been spent.=
=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helveti=
ca Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margi=
n:0px;font:13px &quot;Helvetica Neue&quot;"><b>### 5. ZKP scheme and curve =
choice</b></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Hel=
vetica Neue&quot;">A major concern is the size of the script, proof, cost o=
f verification, and the feasibility to aggregate/batching many proofs.=C2=
=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica =
Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0=
px;font:13px &quot;Helvetica Neue&quot;">Groth16 checks out here with short=
 proof size, cheap verification, and feasibility to aggregate. For example,=
 the standard draft here ([1])=C2=A0shows an implementation that can aggreg=
ate 1024 proofs in 2s and verifies them in 23ms. Although it seems to requi=
re that all proofs belong to the same circuit ( due to =CE=B3 and =CE=B4, w=
hich are circuit-specific). Still, the short proof size and cheap verificat=
ion cost make Groth16 suitable to verify other proofs recursively. And when=
 the upper layer proving schemes (and setup) is the same, so are the verifi=
cation circuits, therefore those proofs could be aggregated.</p><p class=3D=
"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-hei=
ght:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot=
;Helvetica Neue&quot;">On the other hand, KZG commitment supports batching.=
 So the zkSnarks based on KZG should support as well. Further, this paper b=
y Boneh, etc. ([2]) enhances KZG commitment to allow one or two group eleme=
nt opening for multiple polynomials each evaluated at a different set of po=
ints.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetic=
a Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin=
:0px;font:13px &quot;Helvetica Neue&quot;">This is not an exhaustive list, =
not even a list. Overall, if we can aggregate/batch many proofs together, t=
hen proof size is of smaller concern. In this case, Plonk might be a better=
 scheme than Groth16, if we can implement a batching technique to batch pro=
ofs from different circuits together. But still, in the beginning, there mi=
ght not be many proofs to be batched/aggregated at all.</p><p class=3D"gmai=
l-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:1=
5px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helv=
etica Neue&quot;">We shall designate a parameter to OP_ZKP and OP_ZKPVERIFY=
 to indicate which scheme (and curve) to use.</p><p class=3D"gmail-p1" styl=
e=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br><=
/p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue=
&quot;">For curve, BN254 is a natural choice as it has been adopted by many=
 blockchain projects. However, this is largely an open issue.=C2=A0</p><p c=
lass=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;=
min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13p=
x &quot;Helvetica Neue&quot;">All being said, as a proposal, it is my opini=
on that we should support Groth16-BN254 at the beginning. Based on that we =
could build recursive verification circuits for other scheme, which does no=
t require a soft fork. Other schemes and curves, if much desired by the com=
munity, could be included as well. Maybe we can designate a separate BIP fo=
r each scheme-curve pair for direct support (instead of recursive verificat=
ion).=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;He=
lvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"=
margin:0px;font:13px &quot;Helvetica Neue&quot;"><b>### 6. Potential uses</=
b></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica N=
eue&quot;">The potential uses are unlimited: payment aggregation for a fee =
reduction or anonymity, stablecoin, DeFi, decentralized exchange, DAO, NFT,=
 etc., just to name a few. But still, we could take as an example some uses=
 to check if any issues arise and discuss how to address them.</p><p class=
=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-=
height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &q=
uot;Helvetica Neue&quot;">A. ZKP-based smart contract. We could reasonably =
assume ZKP-based smart contracts to be rather different from consensus-base=
d smart contracts (although OP_ZKP is part of a script). A notable differen=
ce is that with Bitcoin=E2=80=99s UTXO model instead of account-model, acco=
unt-balance type of contracts are hard to build without involving external =
storage or state management. And even with external storage involved to man=
age the states, the security of the external storage is also a concern. Dat=
a might be lost or corrupted. Bitcoin=E2=80=99s security does not extend to=
 those contracts automatically. It takes innovations to address these issue=
s.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica N=
eue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0p=
x;font:13px &quot;Helvetica Neue&quot;">On the other hand, there could be s=
mart contracts without a need for explicit state management. This could be =
gaming or decentralized identity, that a ZKP proof is used to prove =E2=80=
=9Dsomething happens or exists according to designated algorithm or criteri=
a=E2=80=9C.</p><p class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;He=
lvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"=
margin:0px;font:13px &quot;Helvetica Neue&quot;">B. Payment aggregation, or=
 Bitcoin Layer 2. Every address can participate in such a protocol by sendi=
ng certain Bitcoin to the designated address (the fund-holding address). On=
ce signed up, participants can send Bitcoin to each other with very little =
fee or pays a higher fee to send to Layer 1. Bookkeeping each participant=
=E2=80=99s =E2=80=9Cbalance=E2=80=9D is a challenge, but might be achievabl=
e via some complex circuits proving the ownership of certain UTXO entries. =
Once proven, the fund-holding address can send Bitcoins to the address as r=
equested by the participant. It is another challenge to maintain those UTXO=
 entries off the Bitcoin network with high security. We might also need to =
segregate those UXTOs from the Bitcoin network so that no transaction can b=
e replayed to the Bitcoin network or another Layer 2 protocol.=C2=A0</p><p =
class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;=
;min-height:15px"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13=
px &quot;Helvetica Neue&quot;"><b>### 7. Ecology implications</b></p><p cla=
ss=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">P=
roof generation, computing power services/vendors. Some proof might be very=
 computationally intensive to generate, for example, recursive verification=
 of thousands of OP_ZKP transactions. In that case, computation power servi=
ces or vendors can work with miners to speed up the generation, or simply p=
ropose a bundle of transactions to be included in a block. By paying a high=
er fee miners are motivated to include the bundle, while the service or ven=
dor can still profit a lot. The immediate reward could incentivize lots of =
efforts to further optimize the implementation, engineering, algorithms, or=
 even ZKP schemes.=C2=A0</p><p class=3D"gmail-p1" style=3D"margin:0px;font:=
13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-=
p3" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Contract comp=
osability. We need to figure out a systematic way for one smart contract to=
 call another, either on-chain or assisted-off-chain. For ZKP-based smart c=
ontracts, proof will have to be generated off-chain and then used later to =
call the target contract. Off-chain vendors could monitor closely related s=
ignals, generate the proof, and submit it to the Bitcoin network. There sho=
uld be incentives to ensure the proper running of the system. It is still a=
n open issue about how to define a cross-contract API, how to signal the ca=
ll, and how to incentivize computation power vendors.</p><p class=3D"gmail-=
p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15p=
x"><br></p><p class=3D"gmail-p3" style=3D"margin:0px;font:13px &quot;Helvet=
ica Neue&quot;">Impact on wallet applications. Generating proof to authoriz=
e spending seems a heavy-duty computation task, and does not seem to fit in=
to mobile applications or hardware wallets, especially those with SoC and p=
owered by a small battery. However, we argue that this is not the case. If =
no secret (private key or seed) is involved, there is no need to involve a =
wallet that is tasked with safekeeping secrets. In such cases, the ZKP proo=
f could be proof that something has indeed happened or exists (including a =
signature issued from a wallet), which makes up spending conditions.</p><p =
class=3D"gmail-p1" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;=
;min-height:15px"><br></p><p class=3D"gmail-p1" style=3D"margin:0px;font:13=
px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=3D"gmail-p1=
" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"=
><br></p><p class=3D"gmail-p2" style=3D"margin:0px;font:13px &quot;Helvetic=
a Neue&quot;">That&#39;s it for now. I hope you are interested in this idea=
. I look forward to your comments.</p><p class=3D"gmail-p1" style=3D"margin=
:0px;font:13px &quot;Helvetica Neue&quot;;min-height:15px"><br></p><p class=
=3D"gmail-p2" style=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;">Tha=
nks,</p><p class=3D"gmail-p2" style=3D"margin:0px;font-variant-numeric:norm=
al;font-variant-east-asian:normal;font-variant-alternates:normal;font-kerni=
ng:auto;font-feature-settings:normal;font-stretch:normal;font-size:13px;lin=
e-height:normal;font-family:&quot;Helvetica Neue&quot;">Weiji</p><p class=
=3D"gmail-p2" style=3D"margin:0px;font-variant-numeric:normal;font-variant-=
east-asian:normal;font-variant-alternates:normal;font-kerning:auto;font-fea=
ture-settings:normal;font-stretch:normal;font-size:13px;line-height:normal;=
font-family:&quot;Helvetica Neue&quot;"><br></p><p class=3D"gmail-p4" style=
=3D"margin:0px;font:13px &quot;Helvetica Neue&quot;;color:rgb(220,161,13)">=
<span class=3D"gmail-s1" style=3D"color:rgb(0,0,0)">[1] -=C2=A0<a href=3D"h=
ttps://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-aggrega=
tion.pdf"><span class=3D"gmail-s2" style=3D"text-decoration:underline">http=
s://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-aggregatio=
n.pdf</span></a></span></p><p class=3D"gmail-p4" style=3D"margin:0px;font-v=
ariant-numeric:normal;font-variant-east-asian:normal;font-variant-alternate=
s:normal;font-kerning:auto;font-feature-settings:normal;font-stretch:normal=
;font-size:13px;line-height:normal;font-family:&quot;Helvetica Neue&quot;;c=
olor:rgb(220,161,13)"><span class=3D"gmail-s3" style=3D"text-decoration-lin=
e:underline;color:rgb(0,0,0)">[2] -=C2=A0<a href=3D"https://eprint.iacr.org=
/2020/081.pdf"><span class=3D"gmail-s2">https://eprint.iacr.org/2020/081.pd=
f</span></a></span></p><p class=3D"gmail-p4" style=3D"margin:0px;font-varia=
nt-numeric:normal;font-variant-east-asian:normal;font-variant-alternates:no=
rmal;font-kerning:auto;font-feature-settings:normal;font-stretch:normal;fon=
t-size:13px;line-height:normal;font-family:&quot;Helvetica Neue&quot;;color=
:rgb(220,161,13)"><br></p></div>

--00000000000023278505fa6145f9--