From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Mon, 22 Jul 2024 12:02:07 -0700 Received: from mail-yb1-f188.google.com ([209.85.219.188]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sVyIP-0006Nc-OA for bitcoindev@gnusha.org; Mon, 22 Jul 2024 12:02:07 -0700 Received: by mail-yb1-f188.google.com with SMTP id 3f1490d57ef6-e05ed51f6b0sf10211174276.0 for ; Mon, 22 Jul 2024 12:02:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1721674919; x=1722279719; 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=SDYMhF0UmS/7mIbsROu+1yBM52s+AW8D1tVitxDlCkE=; b=TN5PKVeRDop2He8KErOr3tGjx4FLIwZABHVhNT8Pxl9Yk+X7KPajhh+o9kSVLgitgM 2FM7uO3mXPUcgmIRwTKmfhkL5q2C9wL9wOBzpvdPxBrZdfwIoLPXMj49z+2Zj7N9RMJJ ozaJ7QG6oDq9okFNt8crNxXAf3mPPxhMm0m3Du2ltW9B13aJEg/endr75gSIc+Y59xuT VFL0daK1yBL4V4oB/x6DgwlCDh1PJlg95/2bSvKXlLOzPpuH1LpB6c5MoofTQDoURdqd u98AiBocEwn37QNvarJI5ZJ24Dwkpr6oZY2OqCTnctpunZcb4UUBtFoIGt6uLglW3qhF 2MqA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1721674919; x=1722279719; 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=SDYMhF0UmS/7mIbsROu+1yBM52s+AW8D1tVitxDlCkE=; b=mMF93lfSOhwBotxyhzX5lP5GHOtozstcKSVs2JEqQlkzNymVtUPeKttXgu3WiUoqP6 eH/P8DFzHwHbtpcs9PHRcyu30ndbNkdasAOly0q4aYaAxkDw5jbrY1omnH+4wTEyezb4 CJ9leMIOyTUJOgI2FPKAVliDXIHCEm/3CJLjH1e2jXLio5ouiwR9xkaHw0TiTXFmjalh Avi7HYFsEtRKjVioGt+yG0exM8RBq3zTQ/ICaeU1YPY+0HA1yXCflOnnxz1wxt+Z/yer IHGg0oX2vEzwOh7wyy1QTCqZTfIBkTOi2Ffee9xpS/iTku2QNNfSXoGZpAoTRbwP3Q/X zoMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1721674919; x=1722279719; 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=SDYMhF0UmS/7mIbsROu+1yBM52s+AW8D1tVitxDlCkE=; b=JqNv4/xErq64nKlAtRAItpOClYE4EFeggx4wcc5gaxivVQCauO0DHnPxGPSKXZY7dJ 7kgNI689PbUVvr/pnTXT6RLsBM1sfj/2AvB41b3ALpXHd1Js/K4RAMwmSn5LBLMUgRVH WuA3eRvPJAGGzh0lYEHLLKDkxi5fKoNbm+9/urR1zA34+PyYmqqkam080XHKTEN+2qTQ 3wLdot78Mljf93NTaB4deyaBAFmPvDEt4YdKsRQXACyhGilN3qgoliS7SHMgq70b/8FV svR4epsBsZf2pW2MJXT1ikRj4rpNKeqws+AmgP7sT62vu3XlhHl1SPKf6yaZC/R74pu1 pQMg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXl7Elm6gYkC2L/Rx+Eh0/TKTeEe4PRE8XxOf4X/GKcuV39npvCMvKVRTmPJ4K7xy7eMTcWKgZP/pS12akqpUJnX/lmgQY= X-Gm-Message-State: AOJu0YyYSCC7FPGqRScpOxjhVcpKsmFmEfk5nEX5wRZiLG/QkdsBfV3G p7C8KA9EjD5MxVCQNGI9KtCKEPNE3oAHJC7Yg5lGcYla4ol2HsbF X-Google-Smtp-Source: AGHT+IFT/ClHIi+p+gr4MkRS/zxzHDTBRwSx+Q/9Ujx3IWMaPav2LjmsAZ3DegoZIWxVMgNczP3pkA== X-Received: by 2002:a05:6902:1546:b0:e03:33cf:79f0 with SMTP id 3f1490d57ef6-e0870188ee6mr10679263276.33.1721674919154; Mon, 22 Jul 2024 12:01:59 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a25:e909:0:b0:e05:fd16:c72b with SMTP id 3f1490d57ef6-e05fdb4259dls8773893276.1.-pod-prod-01-us; Mon, 22 Jul 2024 12:01:55 -0700 (PDT) X-Received: by 2002:a05:690c:4:b0:64b:6aaa:2593 with SMTP id 00721157ae682-66a6569d943mr8883807b3.6.1721674915525; Mon, 22 Jul 2024 12:01:55 -0700 (PDT) Received: by 2002:a05:690c:3104:b0:664:87b6:d9e0 with SMTP id 00721157ae682-66918fcc18bms7b3; Mon, 22 Jul 2024 11:45:52 -0700 (PDT) X-Received: by 2002:a05:690c:9d:b0:64b:5cc7:bcb7 with SMTP id 00721157ae682-66a6364e9b6mr5027917b3.1.1721673950966; Mon, 22 Jul 2024 11:45:50 -0700 (PDT) Date: Mon, 22 Jul 2024 11:45:50 -0700 (PDT) From: Weikeng Chen To: Bitcoin Development Mailing List Message-Id: <22162f02-9362-4d1c-b0ce-3cf8dd01bd93n@googlegroups.com> In-Reply-To: <93611162-6029-4308-98b5-3c95b30a2ac9n@googlegroups.com> References: <93611162-6029-4308-98b5-3c95b30a2ac9n@googlegroups.com> Subject: [bitcoindev] Re: OP_ZKP updates MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_77316_761588001.1721673950701" X-Original-Sender: weikeng.chen@l2iterative.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.7 (/) ------=_Part_77316_761588001.1721673950701 Content-Type: multipart/alternative; boundary="----=_Part_77317_1003527765.1721673950701" ------=_Part_77317_1003527765.1721673950701 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I need to point out that Dory requires pairing, and therefore it cannot=20 work with secp256k1? Please circle back. On Monday, July 22, 2024 at 9:16:18=E2=80=AFAM UTC-5 Weiji Guo wrote: > Greetings, bitcoin developers. I am writing to update you about the OP_ZK= P=20 > > proposal I initiated last year. This time, it concerns which ZKP scheme t= o=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,= =20 > you 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= .html > > > Before proposing any BIP, we must explore existing ZKP schemes and discus= s=20 > > how to use them with OP_ZKP within applications. That's why I took a=20 > detour to=20 > > develop potential applications to understand further how OP_ZKP could wor= k=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 th= e=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=20 > numbers 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=20 > revisit 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=20 > witnesses) of=20 > > thousands of OP_ZKP transactions with a single argument to save block=20 > space=20 > > (and transaction costs).=20 > > > It also saves verification time, even without the benefits of saving bloc= k=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 som= e=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 has= h=20 > > takes about 60k constraints (Sha256 applied twice against an 80-byte bloc= k=20 > > header). > > > But 2^16 is still too large for FRI-based proof. Each FRI-query should=20 > cost 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=20 > 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 linea= r=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= =20 > 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 IP= A=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= =20 > the circuit=20 > > constants. It is at least accurate for BP, BP+, and even Halo, and it use= d=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, circui= t=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.= =20 > The=20 > > verifier will have to compute on them during verification after generatin= g=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= =20 > 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 constant= s=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 tha= t=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=20 > 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= =20 > of 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 b= e=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= =20 > 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 an= d=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=20 > factor 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/22162f02-9362-4d1c-b0ce-3cf8dd01bd93n%40googlegroups.com. ------=_Part_77317_1003527765.1721673950701 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I need to point out that Dory requires pairing, and therefor= e it cannot work with secp256k1?
Please circle back.
<= /div>
On M= onday, July 22, 2024 at 9:16:18=E2=80=AFAM UTC-5 Weiji Guo wrote:

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= earlier email=C2=A0

thread: https:= //lists.linuxfoundation.org/pipermail/bitcoin-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= detour 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= , requires=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 u= se IPA 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 witnes= ses. 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 existin= g blocks 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://e= print.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/22162f02-9362-4d1c-b0ce-3cf8dd01bd93n%40googlegroups.com.=
------=_Part_77317_1003527765.1721673950701-- ------=_Part_77316_761588001.1721673950701--