From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 22 Jul 2024 07:16:26 -0700 Received: from mail-yb1-f191.google.com ([209.85.219.191]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sVtpx-0002tG-BI for bitcoindev@gnusha.org; Mon, 22 Jul 2024 07:16:26 -0700 Received: by mail-yb1-f191.google.com with SMTP id 3f1490d57ef6-e05e410d310sf9367714276.2 for ; Mon, 22 Jul 2024 07:16:24 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1721657779; x=1722262579; 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=hXR2r/GaqwvkJGbgbMmetnL3ZfWKUw1BhrvHphQC7Mk=; b=RsUJjp3otVN34MpHqsHHb6th2pv23d/OLdkDPN3nBo3tI8xcVKpJNwe/x4eV3m1WBt Qgih4MtGBCz637TRe0OnKOTlqPtsjf3UBB9Pxk4+AAIS5qFpvn9Hac5sda7s1u6RLpXX OClo/1SFdFM33DHN4kxyZ4gkdGlAriP9D0o48hMT/1bro2Gipl/mw0VJYSeWNz779VsQ 7EbDxNUMRHYT0LqahFvZk5bAIgX0jy+HlC4jqjlM//0IO2ICNA1htILkhLda5u4wu3zR AQgxkBICmW849IWxwbAZNvx7l7nux/265+E6RpDlQwRERSdYyV7wBvjMHAPBLGuxICv9 eAnA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1721657779; x=1722262579; 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=hXR2r/GaqwvkJGbgbMmetnL3ZfWKUw1BhrvHphQC7Mk=; b=bCrRY3wvjfFn0fdnoEN+SC1einJiHSplMuVAeIcGYOAV8uOyB6CNbPvVv65VS61Ab/ WfTMYsR+jfwgbFbkWaMvwaKPA/vOvv/n92JQnHxvgRmBsqQE1GDuP40p+hmhm/AjBl0N CYFTYAf/OXdqkhgBbmd8kZuq35jDFj98crHOdw5oV7mmHuhmQ+Sa3zMuSTcOimg8tJYx 7gHe00qJ6VxlxQM1r0+rvT41NLI5mcb45GaUMtEDaY7BdjBUA6r7FDB9vK511LOht9EN lC93ireTjE5m0XyMaPekktgW+TA/qUWw9IRO6MoZFdcL5eFs0Apx9w14BZnpV1LAY48I untw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721657779; x=1722262579; 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=hXR2r/GaqwvkJGbgbMmetnL3ZfWKUw1BhrvHphQC7Mk=; b=VdV3qeK5v5+fI+RN1rmqI5SyLEAHlLLIS/XWfheJ+Ii+foWKoNDr+fLV3s7g1uLGi/ GuhozuI43kiH3tHwrdcfGFlIg7wHV3upeNN1Uv4vAjMPm/n/inJyc6I9bOLA+soC4F6e gr3vRrL8RKNnwm9bn5DNmafAmHnN9zX+cdpomoIDhPG3keIUt3UEYLfwF5tRRgULuE/N B765KTQnM2AQC9McLg0Cip8rbJ7qNW+7lH1Wtn3BVTASh6QisrHgMrsTrAL3Ws24MBUV U5xGB41JaaScFTuxOExKH6+0mwLK82hY4+K+g0zQtAIHyytgfCMdq20bqqDbEhHHb7fB M2Bg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCV3XyvyARPSSft38ZnYq8Z0nw54Fne6I140F8aKKitNK9xu1MMuoTnOTvSEgyBWSlRwZz+UC4l1DOMAVTRAF6vuVwPRqFk= X-Gm-Message-State: AOJu0YykEksM668F4GuauOFoEj4DRd83+THv3ML1RSwR8GstBokdAKSM BCe61qjDmdYSjYPwfOpy+7pij6Aj86tQgA8RbvhHJNWS5OjG/9H0 X-Google-Smtp-Source: AGHT+IFwLsNPlZ/j1X0ZIwaSiLf3s8LtZo5NvPR4p1hpuYi8InHMmdzT0xBMbxMtZx6oLvt/TFihWQ== X-Received: by 2002:a05:6902:1547:b0:e05:fdbe:bbdf with SMTP id 3f1490d57ef6-e087b33cf2amr7010775276.20.1721657778447; Mon, 22 Jul 2024 07:16:18 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a25:2e52:0:b0:e05:a1df:563f with SMTP id 3f1490d57ef6-e05fd8e155cls7512328276.0.-pod-prod-05-us; Mon, 22 Jul 2024 07:16:16 -0700 (PDT) X-Received: by 2002:a05:690c:2883:b0:65c:2536:be7f with SMTP id 00721157ae682-66a69640faemr2533107b3.7.1721657776869; Mon, 22 Jul 2024 07:16:16 -0700 (PDT) Received: by 2002:a05:690c:2d11:b0:66a:8967:a513 with SMTP id 00721157ae682-66a8967cffams7b3; Mon, 22 Jul 2024 07:05:53 -0700 (PDT) X-Received: by 2002:a05:690c:d87:b0:615:32e1:d82c with SMTP id 00721157ae682-66a66254672mr5470957b3.6.1721657152276; Mon, 22 Jul 2024 07:05:52 -0700 (PDT) Date: Mon, 22 Jul 2024 07:05:52 -0700 (PDT) From: Weiji Guo To: Bitcoin Development Mailing List Message-Id: <93611162-6029-4308-98b5-3c95b30a2ac9n@googlegroups.com> Subject: [bitcoindev] OP_ZKP updates MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_421958_116489523.1721657152014" X-Original-Sender: weiji.g@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_421958_116489523.1721657152014 Content-Type: multipart/alternative; boundary="----=_Part_421959_1141452221.1721657152014" ------=_Part_421959_1141452221.1721657152014 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable =20 Greetings, bitcoin developers. I am writing to update you about the OP_ZKP= =20 proposal I initiated last year. This time, it concerns which ZKP scheme to= =20 use in=20 the underlying proving system. This email will contain the following four= =20 parts: 1, background, mainly about the initial proposal. You may skip it if you=20 already=20 know about it. 2, high-level requirements for the ZKP scheme and the current priority=20 regarding=20 selection. Also, a brief explanation of precluding trusted setup and=20 FRI-based=20 schemes.=20 3, ideas and open issues regarding Inner Product Argument. 4, what-ifs I should have studied all these further before sending this email, but I=20 also want to=20 have something to talk about during Bitcoin Nashville. During the conf, you= =20 may=20 find me in the K14 booth for f2f talks. =E2=80=94=E2=80=94=E2=80=94Background=E2=80=94=E2=80=94=E2=80=94 For those who haven't heard about this idea, here is the link to the=20 earlier email=20 thread:=20 https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021592.h= tml Before proposing any BIP, we must explore existing ZKP schemes and discuss= =20 how to use them with OP_ZKP within applications. That's why I took a detour= =20 to=20 develop potential applications to understand further how OP_ZKP could work= =20 in=20 real-world applications. That work concluded about two months ago; since=20 then, I=20 have been working on OP_ZKP. =E2=80=94=E2=80=94=E2=80=94High level requirements=E2=80=94=E2=80=94=E2=80= =94 1, Security. The security assumptions should be minimal. Ideally, only the= =20 ECDLP=20 assumption is taken, leading directly to the Inner Product Argument over=20 secp256k1. However, an open issue still blocks IPA from working in OP_ZKP= =20 (details will follow soon). We might consider pairing in a transparent=20 setup setting,=20 but no trusted setup. 2, Small block size consumption. The proof should be both succinct and=20 concretely small. Being concretely small allows individual or small numbers= =20 of=20 proofs to be posted on-chain without incurring too many costs. Otherwise,= =20 they=20 will have to wait to be verified in a batch, should the scheme allow such.= =20 Arguably,=20 waiting for batching is not a good idea, as the transactions will have to= =20 be put on=20 hold, and there is no guarantee more will come. That said, we might revisit= =20 this=20 choice should we run out of candidate schemes.=20 FRI-based proofs are considered too big for 100- to 128-bit provable=20 security. The=20 size is a few hundred kilobytes for a circuit of 2^20 size. Besides, it=20 does not allow=20 batched verification (see the following requirement).=20 3, Batched verification is mandatory due to block size considerations.=20 Should the=20 situation allow, we could replace the proof data (as transaction witnesses)= =20 of=20 thousands of OP_ZKP transactions with a single argument to save block space= =20 (and transaction costs).=20 It also saves verification time, even without the benefits of saving block= =20 space.=20 4, Small verification key for deployment. It seems natural but is not the= =20 default=20 case for some schemes.=20 5, Aggregated proving. This is optional as it happens off-chain. However,= =20 it=20 effectively reduces proof size and verification time requirements for some= =20 non- constant size proof schemes (we precluded trusted setup). Consider=20 aggregating=20 many sub-circuits together with a constant or log-sized argument.=20 2^16 is a reasonable upper bound for a sub-circuit. Computing a block hash= =20 takes about 60k constraints (Sha256 applied twice against an 80-byte block= =20 header). But 2^16 is still too large for FRI-based proof. Each FRI-query should cost= =20 16^2=20 hashes, which is 8 kilobytes. There are dozens of queries to run to meet=20 the target=20 security (preferably 128-bit, without further security conjectures).=20 Interested=20 readers may refer to https://a16zcrypto.com/posts/article/17-misconceptions= - about-snarks/#section--11.=20 =E2=80=94=E2=80=94=E2=80=94Inner Product Argument=E2=80=94=E2=80=94=E2=80= =94 Now, let's consider IPA-based solutions. IPA has a transparent setup,=20 requires=20 only ECDLP assumption, can work on the secp256k1 curve, has a relatively=20 small=20 proof size, and is capable of both batched verification and aggregated=20 proving.=20 We can use the aggregated proving technique to address the issue of linear= =20 time=20 verification. The remaining open issue with IPA is that the size of the=20 verification=20 key is linear to the circuit size.=20 Let me expand on the last two issues.=20 The linear verification time of IPA comes from the need to recompute the=20 Pedersen commitment base in each round of reduction (could be postponed but= =20 still O(N)). We could adopt the aggregated proving technique to address=20 this=20 issue and effectively reduce the complexity of the actual verification=20 time.=20 Suppose there are M sub-circuits; each has a size bound of N (assuming N = =3D=20 2^16). We could have an argument to combine the M inner products into one.= =20 This=20 argument is also made of IPA, thus having O(log(M)) size and O(M)=20 verification=20 time. Then the total proof size is O(log(M) + log(N)), and verification=20 time=20 becomes O(M)+O(N) rather than O(M*N) (there will be some extra costs per=20 aggregated proof, but let's skip it for now). This is how we could use IPA= =20 to=20 achieve succinctness and to deal with huge circuits (we need this as we=20 might=20 recursively verify proofs of other schemes).=20 Linear verification key comes from the need for the verifier to use all the= =20 circuit=20 constants. It is at least accurate for BP, BP+, and even Halo, and it used= =20 to be=20 acceptable as the multi-scalar multiplication dominates the verification=20 costs.=20 However, it becomes an issue with aggregated proving in terms of both=20 deployment size and verification time. When M is large enough, the=20 aggregated=20 verification time to compute with these constants is non-trivial, even=20 compared to=20 the MSM costs. The more significant issue is with the circuit deployment.= =20 We have=20 to save all these parameters on-chain.=20 To further expand on this, let me re-iterate the Sonic Arithmetization=20 process. It is=20 R1CS-based with some pre-processing. Suppose there are N multiplication=20 gates=20 such that: A_i * B_i =3D C_i=20 for i in [0 - N-1], A_i, B_i, and C_i as field elements, and A, B, and C=20 are circuit=20 witnesses of N-element vectors.=20 There are also Q linear constraints to capture the addition gates, circuit= =20 wiring,=20 and multiplied-by-constant constraints: WL*A + WR*B + WO*C =3D K where WL, WR, and WO are Q*N matrixes of field elements, and K is a=20 Q-element=20 vector of field elements. WL, WR, WO, and K are circuit constants.=20 Although WL, WR, and WO are vastly sparse, they are at least O(N) size. The= =20 verifier will have to compute on them during verification after generating= =20 a=20 challenge value in response to the prover's commitment to the witnesses.=20 This=20 O(N) size prevents us from deploying verification keys on-chain.=20 The natural idea is to commit to those constants somehow and to offload the= =20 commitment opening to the prover. Although the verifier still pays O(N)=20 time to=20 verify, the deployment size is constant, and the opening size is only=20 O(log(N))=20 instead of O(N), assuming an IPA opening. However, this no longer holds=20 with=20 aggregated proving, as there is no guarantee that the aggregated constants= =20 aWL, aWR, and aWO will be sparse. The complexity could become O(N^2).=20 The open issue here is to find a way to commit to WL, WR, and WO such that= =20 1)=20 the verification key could be tiny, 2) the proof size to open the=20 commitment is=20 acceptable, and 3) the commitments could be aggregated. If necessary,=20 modify=20 the arithmetization further, ideally without introducing new security=20 assumptions.=20 -- If we do, for example, introduce SXDH, then we can consider schemes like= =20 Dory, which has a transparent setup and O(log(N)) verifier time.=20 =E2=80=94=E2=80=94=E2=80=94What-ifs=E2=80=94=E2=80=94=E2=80=94 What if the above open issue could be resolved? The resulting proving=20 system=20 should work even for a Raspberry Pi 4 node. I ran some benchmarks on=20 Raspberry=20 Pi 4 for some elliptical curve operations. The general conclusion is that= =20 it is about=20 ten times slower than my Mac Book Pro for a single thread. For a circuit of= =20 2^16=20 size, the verification time with MBP is doubt 200~300 ms (inferred by=20 benchmarking MSM of this size); therefore, it would be about 2~3 seconds=20 for=20 RP4. The aggregation might double or triple the time cost.=20 Now, for block verification, counted in batched verification, it should be= =20 acceptable for RP4 to spend around 10 seconds verifying ALL OP_ZKP=20 transactions in a new block. Luckily, we won't have too many existing=20 blocks full=20 of OP_ZKP transactions any time soon.=20 For transaction forwarding, a simple technique of pool-then-batched=20 verification=20 could work for RP4. As its name suggests, an RP4 node could simply pool any= =20 incoming OP_ZKP transactions in memory when it is already busy verifying=20 some.=20 When it is done, the node retrieves all the pooled OP_ZKP transactions and= =20 verifies them in a batch. This way, it only adds a few seconds of latency= =20 to=20 forwarding any OP_ZKP transactions.=20 What if the open issue cannot be resolved? We might consider Dory. It is=20 transparent, requires pairing, and has logarithmic proof size but=20 concretely larger=20 than Bulletproofs (but Torus-based optimization might help here by a factor= =20 of 3;=20 check out here: https://youtu.be/i-uap69_1uw?t=3D4044 and=20 https://eprint.iacr.org/ 2007/429.pdf ). It also has logarithmic verification time, and batched=20 verification=20 allows for saving block space and verification time. The community might=20 need to=20 accept the SXDH assumption. That's it. Thanks for reading. Any comments are welcome.=20 And again, see you in the K14 booth, Nashville. Regards, Weiji --=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 on the web visit https://groups.google.com/d/msgid/= bitcoindev/93611162-6029-4308-98b5-3c95b30a2ac9n%40googlegroups.com. ------=_Part_421959_1141452221.1721657152014 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Greetings, bitcoin developers. I am writing to update you about the OP_Z= KP=C2=A0

proposal I initiated last year. This time, it concerns which ZKP scheme = to use in=C2=A0

the underlying proving system. This email will contain the following fou= r parts:


1, background, mainly about the initial proposal. You may skip it if you= already=C2=A0

know about it.

2, high-level requirements for the ZKP scheme and the current priority r= egarding=C2=A0

selection. Also, a brief explanation of precluding trusted setup and FRI= -based=C2=A0

schemes.=C2=A0

3, ideas and open issues regarding Inner Product Argument.

4, what-ifs


I should have studied all these further before sending this email, but I= also want to=C2=A0

have something to talk about during Bitcoin Nashville. During the conf, = you may=C2=A0

find me in the K14 booth for f2f talks.


=E2=80=94=E2=80=94=E2=80=94Background=E2=80=94=E2=80=94=E2=80=94


For those who haven't heard about this idea, here is the link to the ear= lier email=C2=A0

thread: https://lists.linuxfoundation.org/pipermail/bitc= oin-dev/2023-April/021592.html


Before proposing any BIP, we must explore existing ZKP schemes and discu= ss=C2=A0

how to use them with OP_ZKP within applications. That's why I took a det= our to=C2=A0

develop potential applications to understand further how OP_ZKP could wo= rk in=C2=A0

real-world applications. That work concluded about two months ago; since= then, I=C2=A0

have been working on OP_ZKP.


=E2=80=94=E2=80=94=E2=80=94High level requirements=E2=80=94=E2=80=94=E2= =80=94


1, Security. The security assumptions should be minimal. Ideally, only t= he ECDLP=C2=A0

assumption is taken, leading directly to the Inner Product Argument over= =C2=A0

secp256k1. However, an open issue still blocks IPA from working in OP_ZK= P=C2=A0

(details will follow soon). We might consider pairing in a transparent s= etup setting,=C2=A0

but no trusted setup.


2, Small block size consumption. The proof should be both succinct and= =C2=A0

concretely small. Being concretely small allows individual or small numb= ers of=C2=A0

proofs to be posted on-chain without incurring too many costs. Otherwise= , they=C2=A0

will have to wait to be verified in a batch, should the scheme allow suc= h. Arguably,=C2=A0

waiting for batching is not a good idea, as the transactions will have t= o be put on=C2=A0

hold, and there is no guarantee more will come. That said, we might revi= sit this=C2=A0

choice should we run out of candidate schemes.=C2=A0


FRI-based proofs are considered too big for 100- to 128-bit provable sec= urity. The=C2=A0

size is a few hundred kilobytes for a circuit of 2^20 size. Besides, it = does not allow=C2=A0

batched verification (see the following requirement).=C2=A0


3, Batched verification is mandatory due to block size considerations. S= hould the=C2=A0

situation allow, we could replace the proof data (as transaction witness= es) of=C2=A0

thousands of OP_ZKP transactions with a single argument to save block sp= ace=C2=A0

(and transaction costs).=C2=A0


It also saves verification time, even without the benefits of saving blo= ck space.=C2=A0


4, Small verification key for deployment. It seems natural but is not th= e default=C2=A0

case for some schemes.=C2=A0


5, Aggregated proving. This is optional as it happens off-chain. However= , it=C2=A0

effectively reduces proof size and verification time requirements for so= me non-

constant size proof schemes (we precluded trusted setup). Consider aggre= gating=C2=A0

many sub-circuits together with a constant or log-sized argument.=C2=A0<= /p>


2^16 is a reasonable upper bound for a sub-circuit. Computing a block ha= sh=C2=A0

takes about 60k constraints (Sha256 applied twice against an 80-byte blo= ck=C2=A0

header).


But 2^16 is still too large for FRI-based proof. Each FRI-query should c= ost 16^2=C2=A0

hashes, which is 8 kilobytes. There are dozens of queries to run to meet= the target=C2=A0

security (preferably 128-bit, without further security conjectures). Int= erested=C2=A0

readers may refer to https://a16zcrypto.com/posts/article/17-misconceptions-

about-snarks/#section--11.=C2=A0


=E2=80=94=E2=80=94=E2=80=94Inner Product Argument=E2=80=94=E2=80=94=E2= =80=94


Now, let's consider IPA-based solutions. IPA has a transparent setup, re= quires=C2=A0

only ECDLP assumption, can work on the secp256k1 curve, has a relatively= small=C2=A0

proof size, and is capable of both batched verification and aggregated p= roving.=C2=A0

We can use the aggregated proving technique to address the issue of line= ar time=C2=A0

verification. The remaining open issue with IPA is that the size of the = verification=C2=A0

key is linear to the circuit size.=C2=A0


Let me expand on the last two issues.=C2=A0


The linear verification time of IPA comes from the need to recompute the= =C2=A0

Pedersen commitment base in each round of reduction (could be postponed = but=C2=A0

still O(N)). We could adopt the aggregated proving technique to address = this=C2=A0

issue and effectively reduce the complexity of the actual verification t= ime.=C2=A0

Suppose there are M sub-circuits; each has a size bound of N (assuming N= =3D=C2=A0

2^16). We could have an argument to combine the M inner products into on= e. This=C2=A0

argument is also made of IPA, thus having O(log(M)) size and O(M) verifi= cation=C2=A0

time. Then the total proof size is O(log(M) + log(N)), and verification = time=C2=A0

becomes O(M)+O(N) rather than O(M*N) (there will be some extra costs per= =C2=A0

aggregated proof, but let's skip it for now). This is how we could use I= PA to=C2=A0

achieve succinctness and to deal with huge circuits (we need this as we = might=C2=A0

recursively verify proofs of other schemes).=C2=A0


Linear verification key comes from the need for the verifier to use all = the circuit=C2=A0

constants. It is at least accurate for BP, BP+, and even Halo, and it us= ed to be=C2=A0

acceptable as the multi-scalar multiplication dominates the verification= costs.=C2=A0

However, it becomes an issue with aggregated proving in terms of both=C2= =A0

deployment size and verification time. When M is large enough, the aggre= gated=C2=A0

verification time to compute with these constants is non-trivial, even c= ompared to=C2=A0

the MSM costs. The more significant issue is with the circuit deployment= . We have=C2=A0

to save all these parameters on-chain.=C2=A0


To further expand on this, let me re-iterate the Sonic Arithmetization p= rocess. It is=C2=A0

R1CS-based with some pre-processing. Suppose there are N multiplication = gates=C2=A0

such that:

=C2=A0 =C2=A0 =C2=A0 A_i * B_i =3D C_i=C2=A0

for i in [0 - N-1], A_i, B_i, and C_i as field elements, and A, B, and C= are circuit=C2=A0

witnesses of N-element vectors.=C2=A0


There are also Q linear constraints to capture the addition gates, circu= it wiring,=C2=A0

and multiplied-by-constant constraints:

=C2=A0 =C2=A0 =C2=A0 WL*A + WR*B + WO*C =3D K

where WL, WR, and WO are Q*N matrixes of field elements, and K is a Q-el= ement=C2=A0

vector of field elements. WL, WR, WO, and K are circuit constants.=C2=A0=


Although WL, WR, and WO are vastly sparse, they are at least O(N) size. = The=C2=A0

verifier will have to compute on them during verification after generati= ng a=C2=A0

challenge value in response to the prover's commitment to the witnesses.= This=C2=A0

O(N) size prevents us from deploying verification keys on-chain.=C2=A0


The natural idea is to commit to those constants somehow and to offload = the=C2=A0

commitment opening to the prover. Although the verifier still pays O(N) = time to=C2=A0

verify, the deployment size is constant, and the opening size is only O(= log(N))=C2=A0

instead of O(N), assuming an IPA opening. However, this no longer holds = with=C2=A0

aggregated proving, as there is no guarantee that the aggregated constan= ts=C2=A0

aWL, aWR, and aWO will be sparse. The complexity could become O(N^2).=C2= =A0


The open issue here is to find a way to commit to WL, WR, and WO such th= at 1)=C2=A0

the verification key could be tiny, 2) the proof size to open the commit= ment is=C2=A0

acceptable, and 3) the commitments could be aggregated. If necessary, mo= dify=C2=A0

the arithmetization further, ideally without introducing new security as= sumptions.=C2=A0

-- If we do, for example, introduce SXDH, then we can consider schemes l= ike=C2=A0

Dory, which has a transparent setup and O(log(N)) verifier time.=C2=A0


=E2=80=94=E2=80=94=E2=80=94What-ifs=E2=80=94=E2=80=94=E2=80=94


What if the above open issue could be resolved? The resulting proving sy= stem=C2=A0

should work even for a Raspberry Pi 4 node. I ran some benchmarks on Ras= pberry=C2=A0

Pi 4 for some elliptical curve operations. The general conclusion is tha= t it is about=C2=A0

ten times slower than my Mac Book Pro for a single thread. For a circuit= of 2^16=C2=A0

size, the verification time with MBP is doubt 200~300 ms (inferred by=C2= =A0

benchmarking MSM of this size); therefore, it would be about 2~3 seconds= for=C2=A0

RP4. The aggregation might double or triple the time cost.=C2=A0


Now, for block verification, counted in batched verification, it should = be=C2=A0

acceptable for RP4 to spend around 10 seconds verifying ALL OP_ZKP=C2=A0=

transactions in a new block. Luckily, we won't have too many existing bl= ocks full=C2=A0

of OP_ZKP transactions any time soon.=C2=A0


For transaction forwarding, a simple technique of pool-then-batched veri= fication=C2=A0

could work for RP4. As its name suggests, an RP4 node could simply pool = any=C2=A0

incoming OP_ZKP transactions in memory when it is already busy verifying= some.=C2=A0

When it is done, the node retrieves all the pooled OP_ZKP transactions a= nd=C2=A0

verifies them in a batch. This way, it only adds a few seconds of latenc= y to=C2=A0

forwarding any OP_ZKP transactions.=C2=A0


What if the open issue cannot be resolved? We might consider Dory. It is= =C2=A0

transparent, requires pairing, and has logarithmic proof size but concre= tely larger=C2=A0

than Bulletproofs (but Torus-based optimization might help here by a fac= tor of 3;=C2=A0

check out here: https:= //youtu.be/i-uap69_1uw?t=3D4044 and https://eprint.iacr.org/

2007/429.pdf ). It also has logarithmic verification time, and batched v= erification=C2=A0

allows for saving block space and verification time. The community might= need to=C2=A0

accept the SXDH assumption.


That's it. Thanks for reading. Any comments are welcome.=C2=A0

And again, see you in the K14 booth, Nashville.


Regards,

Weiji


--
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 on the web visit https://groups.google.com/d/msg= id/bitcoindev/93611162-6029-4308-98b5-3c95b30a2ac9n%40googlegroups.com.=
------=_Part_421959_1141452221.1721657152014-- ------=_Part_421958_116489523.1721657152014--