path: root/71/7e7ad380870e43e5116b78d0cb462ac1de611e

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 <bitcoindev+bncBD5ZD7PQ5YPRBMOT7G2AMGQEXIN3BDY@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <weiji.g@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
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: <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.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







<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't heard about this idea, here is the link to the ear=
lier email=C2=A0</p>
<p>thread: <a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-d=
ev/2023-April/021592.html">https://lists.linuxfoundation.org/pipermail/bitc=
oin-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's why I took a det=
our 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-">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's consider IPA-based solutions. IPA has a transparent setup, re=
quires=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's skip it for now). This is how we could use I=
PA 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's commitment to the witnesses.=
 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't have too many existing bl=
ocks 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">https:=
//youtu.be/i-uap69_1uw?t=3D4044</a> and <a href=3D"https://eprint.iacr.org/=
">https://eprint.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'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>

<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/93611162-6029-4308-98b5-3c95b30a2ac9n%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/93611162-6029-4308-98b5-3c95b30a2ac9n%40googlegroups.com</a>.=
<br />

------=_Part_421959_1141452221.1721657152014--

------=_Part_421958_116489523.1721657152014--