path: root/10/e9517b3318d61a592001e48f664be794eb336f

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 <bitcoindev+bncBCTP33FZ3YMBBI6Z7K2AMGQELLURVUQ@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <weikeng.chen@l2iterative.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
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: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
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

<div><div><div>I need to point out that Dory requires pairing, and therefor=
e it cannot work with secp256k1?</div><div>Please circle back.</div></div><=
/div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On M=
onday, July 22, 2024 at 9:16:18=E2=80=AFAM UTC-5 Weiji Guo wrote:<br/></div=
><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-lef=
t: 1px solid rgb(204, 204, 204); padding-left: 1ex;">





<p>Greetings, bitcoin developers. I am writing to update you about the OP_Z=
KP=C2=A0<br></p>
<p>proposal I initiated last year. This time, it concerns which ZKP scheme =
to use in=C2=A0</p>
<p>the underlying proving system. This email will contain the following fou=
r parts:</p>
<p><br></p>
<p>1, background, mainly about the initial proposal. You may skip it if you=
 already=C2=A0</p>
<p>know about it.</p>
<p>2, high-level requirements for the ZKP scheme and the current priority r=
egarding=C2=A0</p>
<p>selection. Also, a brief explanation of precluding trusted setup and FRI=
-based=C2=A0</p>
<p>schemes.=C2=A0</p>
<p>3, ideas and open issues regarding Inner Product Argument.</p>
<p>4, what-ifs</p>
<p><br></p>
<p>I should have studied all these further before sending this email, but I=
 also want to=C2=A0</p>
<p>have something to talk about during Bitcoin Nashville. During the conf, =
you may=C2=A0</p>
<p>find me in the K14 booth for f2f talks.</p><p><br></p>
<p>=E2=80=94=E2=80=94=E2=80=94Background=E2=80=94=E2=80=94=E2=80=94</p>
<p><br></p>
<p>For those who haven&#39;t heard about this idea, here is the link to the=
 earlier email=C2=A0</p>
<p>thread: <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-d=
ev/2023-April/021592.html" target=3D"_blank" rel=3D"nofollow" data-saferedi=
recturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://lists.linuxfo=
undation.org/pipermail/bitcoin-dev/2023-April/021592.html&amp;source=3Dgmai=
l&amp;ust=3D1721759122708000&amp;usg=3DAOvVaw0E5ekCauPdmICOtmJxikV3">https:=
//lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021592.html</a=
></p>
<p><br></p>
<p>Before proposing any BIP, we must explore existing ZKP schemes and discu=
ss=C2=A0</p>
<p>how to use them with OP_ZKP within applications. That&#39;s why I took a=
 detour to=C2=A0</p>
<p>develop potential applications to understand further how OP_ZKP could wo=
rk in=C2=A0</p>
<p>real-world applications. That work concluded about two months ago; since=
 then, I=C2=A0</p>
<p>have been working on OP_ZKP.</p>
<p><br></p>
<p>=E2=80=94=E2=80=94=E2=80=94High level requirements=E2=80=94=E2=80=94=E2=
=80=94</p>
<p><br></p>
<p>1, Security. The security assumptions should be minimal. Ideally, only t=
he ECDLP=C2=A0</p>
<p>assumption is taken, leading directly to the Inner Product Argument over=
=C2=A0</p>
<p>secp256k1. However, an open issue still blocks IPA from working in OP_ZK=
P=C2=A0</p>
<p>(details will follow soon). We might consider pairing in a transparent s=
etup setting,=C2=A0</p>
<p>but no trusted setup.</p>
<p><br></p>
<p>2, Small block size consumption. The proof should be both succinct and=
=C2=A0</p>
<p>concretely small. Being concretely small allows individual or small numb=
ers of=C2=A0</p>
<p>proofs to be posted on-chain without incurring too many costs. Otherwise=
, they=C2=A0</p>
<p>will have to wait to be verified in a batch, should the scheme allow suc=
h. Arguably,=C2=A0</p>
<p>waiting for batching is not a good idea, as the transactions will have t=
o be put on=C2=A0</p>
<p>hold, and there is no guarantee more will come. That said, we might revi=
sit this=C2=A0</p>
<p>choice should we run out of candidate schemes.=C2=A0</p>
<p><br></p>
<p>FRI-based proofs are considered too big for 100- to 128-bit provable sec=
urity. The=C2=A0</p>
<p>size is a few hundred kilobytes for a circuit of 2^20 size. Besides, it =
does not allow=C2=A0</p>
<p>batched verification (see the following requirement).=C2=A0</p>
<p><br></p>
<p>3, Batched verification is mandatory due to block size considerations. S=
hould the=C2=A0</p>
<p>situation allow, we could replace the proof data (as transaction witness=
es) of=C2=A0</p>
<p>thousands of OP_ZKP transactions with a single argument to save block sp=
ace=C2=A0</p>
<p>(and transaction costs).=C2=A0</p>
<p><br></p>
<p>It also saves verification time, even without the benefits of saving blo=
ck space.=C2=A0</p>
<p><br></p>
<p>4, Small verification key for deployment. It seems natural but is not th=
e default=C2=A0</p>
<p>case for some schemes.=C2=A0</p>
<p><br></p>
<p>5, Aggregated proving. This is optional as it happens off-chain. However=
, it=C2=A0</p>
<p>effectively reduces proof size and verification time requirements for so=
me non-</p>
<p>constant size proof schemes (we precluded trusted setup). Consider aggre=
gating=C2=A0</p>
<p>many sub-circuits together with a constant or log-sized argument.=C2=A0<=
/p>
<p><br></p>
<p>2^16 is a reasonable upper bound for a sub-circuit. Computing a block ha=
sh=C2=A0</p>
<p>takes about 60k constraints (Sha256 applied twice against an 80-byte blo=
ck=C2=A0</p>
<p>header).</p>
<p><br></p>
<p>But 2^16 is still too large for FRI-based proof. Each FRI-query should c=
ost 16^2=C2=A0</p>
<p>hashes, which is 8 kilobytes. There are dozens of queries to run to meet=
 the target=C2=A0</p>
<p>security (preferably 128-bit, without further security conjectures). Int=
erested=C2=A0</p>
<p>readers may refer to <a href=3D"https://a16zcrypto.com/posts/article/17-=
misconceptions-" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D=
"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://a16zcrypto.com/posts/ar=
ticle/17-misconceptions-&amp;source=3Dgmail&amp;ust=3D1721759122709000&amp;=
usg=3DAOvVaw2-6Njs-PW7TKh39f_R4FaZ">https://a16zcrypto.com/posts/article/17=
-misconceptions-</a></p>
<p>about-snarks/#section--11.=C2=A0</p>
<p><br></p>
<p>=E2=80=94=E2=80=94=E2=80=94Inner Product Argument=E2=80=94=E2=80=94=E2=
=80=94</p>
<p><br></p>
<p>Now, let&#39;s consider IPA-based solutions. IPA has a transparent setup=
, requires=C2=A0</p>
<p>only ECDLP assumption, can work on the secp256k1 curve, has a relatively=
 small=C2=A0</p>
<p>proof size, and is capable of both batched verification and aggregated p=
roving.=C2=A0</p>
<p>We can use the aggregated proving technique to address the issue of line=
ar time=C2=A0</p>
<p>verification. The remaining open issue with IPA is that the size of the =
verification=C2=A0</p>
<p>key is linear to the circuit size.=C2=A0</p>
<p><br></p>
<p>Let me expand on the last two issues.=C2=A0</p>
<p><br></p>
<p>The linear verification time of IPA comes from the need to recompute the=
=C2=A0</p>
<p>Pedersen commitment base in each round of reduction (could be postponed =
but=C2=A0</p>
<p>still O(N)). We could adopt the aggregated proving technique to address =
this=C2=A0</p>
<p>issue and effectively reduce the complexity of the actual verification t=
ime.=C2=A0</p>
<p>Suppose there are M sub-circuits; each has a size bound of N (assuming N=
 =3D=C2=A0</p>
<p>2^16). We could have an argument to combine the M inner products into on=
e. This=C2=A0</p>
<p>argument is also made of IPA, thus having O(log(M)) size and O(M) verifi=
cation=C2=A0</p>
<p>time. Then the total proof size is O(log(M) + log(N)), and verification =
time=C2=A0</p>
<p>becomes O(M)+O(N) rather than O(M*N) (there will be some extra costs per=
=C2=A0</p>
<p>aggregated proof, but let&#39;s skip it for now). This is how we could u=
se IPA to=C2=A0</p>
<p>achieve succinctness and to deal with huge circuits (we need this as we =
might=C2=A0</p>
<p>recursively verify proofs of other schemes).=C2=A0</p>
<p><br></p>
<p>Linear verification key comes from the need for the verifier to use all =
the circuit=C2=A0</p>
<p>constants. It is at least accurate for BP, BP+, and even Halo, and it us=
ed to be=C2=A0</p>
<p>acceptable as the multi-scalar multiplication dominates the verification=
 costs.=C2=A0</p>
<p>However, it becomes an issue with aggregated proving in terms of both=C2=
=A0</p>
<p>deployment size and verification time. When M is large enough, the aggre=
gated=C2=A0</p>
<p>verification time to compute with these constants is non-trivial, even c=
ompared to=C2=A0</p>
<p>the MSM costs. The more significant issue is with the circuit deployment=
. We have=C2=A0</p>
<p>to save all these parameters on-chain.=C2=A0</p>
<p><br></p>
<p>To further expand on this, let me re-iterate the Sonic Arithmetization p=
rocess. It is=C2=A0</p>
<p>R1CS-based with some pre-processing. Suppose there are N multiplication =
gates=C2=A0</p>
<p>such that:</p>
<p>		=C2=A0 =C2=A0 =C2=A0 A_i * B_i =3D C_i=C2=A0</p>
<p>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</p>
<p>witnesses of N-element vectors.=C2=A0</p>
<p><br></p>
<p>There are also Q linear constraints to capture the addition gates, circu=
it wiring,=C2=A0</p>
<p>and multiplied-by-constant constraints:</p>
<p>		=C2=A0 =C2=A0 =C2=A0 WL*A + WR*B + WO*C =3D K</p>
<p>where WL, WR, and WO are Q*N matrixes of field elements, and K is a Q-el=
ement=C2=A0</p>
<p>vector of field elements. WL, WR, WO, and K are circuit constants.=C2=A0=
</p>
<p><br></p>
<p>Although WL, WR, and WO are vastly sparse, they are at least O(N) size. =
The=C2=A0</p>
<p>verifier will have to compute on them during verification after generati=
ng a=C2=A0</p>
<p>challenge value in response to the prover&#39;s commitment to the witnes=
ses. This=C2=A0</p>
<p>O(N) size prevents us from deploying verification keys on-chain.=C2=A0</=
p>
<p><br></p>
<p>The natural idea is to commit to those constants somehow and to offload =
the=C2=A0</p>
<p>commitment opening to the prover. Although the verifier still pays O(N) =
time to=C2=A0</p>
<p>verify, the deployment size is constant, and the opening size is only O(=
log(N))=C2=A0</p>
<p>instead of O(N), assuming an IPA opening. However, this no longer holds =
with=C2=A0</p>
<p>aggregated proving, as there is no guarantee that the aggregated constan=
ts=C2=A0</p>
<p>aWL, aWR, and aWO will be sparse. The complexity could become O(N^2).=C2=
=A0</p>
<p><br></p>
<p>The open issue here is to find a way to commit to WL, WR, and WO such th=
at 1)=C2=A0</p>
<p>the verification key could be tiny, 2) the proof size to open the commit=
ment is=C2=A0</p>
<p>acceptable, and 3) the commitments could be aggregated. If necessary, mo=
dify=C2=A0</p>
<p>the arithmetization further, ideally without introducing new security as=
sumptions.=C2=A0</p>
<p>-- If we do, for example, introduce SXDH, then we can consider schemes l=
ike=C2=A0</p>
<p>Dory, which has a transparent setup and O(log(N)) verifier time.=C2=A0</=
p>
<p><br></p>
<p>=E2=80=94=E2=80=94=E2=80=94What-ifs=E2=80=94=E2=80=94=E2=80=94</p>
<p><br></p>
<p>What if the above open issue could be resolved? The resulting proving sy=
stem=C2=A0</p>
<p>should work even for a Raspberry Pi 4 node. I ran some benchmarks on Ras=
pberry=C2=A0</p>
<p>Pi 4 for some elliptical curve operations. The general conclusion is tha=
t it is about=C2=A0</p>
<p>ten times slower than my Mac Book Pro for a single thread. For a circuit=
 of 2^16=C2=A0</p>
<p>size, the verification time with MBP is doubt 200~300 ms (inferred by=C2=
=A0</p>
<p>benchmarking MSM of this size); therefore, it would be about 2~3 seconds=
 for=C2=A0</p>
<p>RP4. The aggregation might double or triple the time cost.=C2=A0</p>
<p><br></p>
<p>Now, for block verification, counted in batched verification, it should =
be=C2=A0</p>
<p>acceptable for RP4 to spend around 10 seconds verifying ALL OP_ZKP=C2=A0=
</p>
<p>transactions in a new block. Luckily, we won&#39;t have too many existin=
g blocks full=C2=A0</p>
<p>of OP_ZKP transactions any time soon.=C2=A0</p>
<p><br></p>
<p>For transaction forwarding, a simple technique of pool-then-batched veri=
fication=C2=A0</p>
<p>could work for RP4. As its name suggests, an RP4 node could simply pool =
any=C2=A0</p>
<p>incoming OP_ZKP transactions in memory when it is already busy verifying=
 some.=C2=A0</p>
<p>When it is done, the node retrieves all the pooled OP_ZKP transactions a=
nd=C2=A0</p>
<p>verifies them in a batch. This way, it only adds a few seconds of latenc=
y to=C2=A0</p>
<p>forwarding any OP_ZKP transactions.=C2=A0</p>
<p><br></p>
<p>What if the open issue cannot be resolved? We might consider Dory. It is=
=C2=A0</p>
<p>transparent, requires pairing, and has logarithmic proof size but concre=
tely larger=C2=A0</p>
<p>than Bulletproofs (but Torus-based optimization might help here by a fac=
tor of 3;=C2=A0</p>
<p>check out here: <a href=3D"https://youtu.be/i-uap69_1uw?t=3D4044" target=
=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com=
/url?hl=3Den&amp;q=3Dhttps://youtu.be/i-uap69_1uw?t%3D4044&amp;source=3Dgma=
il&amp;ust=3D1721759122709000&amp;usg=3DAOvVaw3FdEuuUgG7upoG1ZWhbiy_">https=
://youtu.be/i-uap69_1uw?t=3D4044</a> and <a href=3D"https://eprint.iacr.org=
/" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.g=
oogle.com/url?hl=3Den&amp;q=3Dhttps://eprint.iacr.org/&amp;source=3Dgmail&a=
mp;ust=3D1721759122709000&amp;usg=3DAOvVaw3rTdyBbS2UlaC4sFrYALAJ">https://e=
print.iacr.org/</a></p>
<p>2007/429.pdf ). It also has logarithmic verification time, and batched v=
erification=C2=A0</p>
<p>allows for saving block space and verification time. The community might=
 need to=C2=A0</p>
<p>accept the SXDH assumption.</p>
<p><br></p>
<p>That&#39;s it. Thanks for reading. Any comments are welcome.=C2=A0</p>
<p>And again, see you in the K14 booth, Nashville.</p>
<p><br></p>
<p>Regards,</p>
<p>Weiji</p>
<p><br></p></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/22162f02-9362-4d1c-b0ce-3cf8dd01bd93n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/22162f02-9362-4d1c-b0ce-3cf8dd01bd93n%40googlegroups.com</a>.=
<br />

------=_Part_77317_1003527765.1721673950701--

------=_Part_77316_761588001.1721673950701--