path: root/27/a2ab90b5cde06003c78cda567dcc8bfe5305ab

Delivery-date: Mon, 14 Oct 2024 02:30:14 -0700
Received: from mail-yw1-f191.google.com ([209.85.128.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+bncBD5ZD7PQ5YPRBHOJWO4AMGQEVCW3I2Y@googlegroups.com>)
	id 1t0HP3-0008Po-RF
	for bitcoindev@gnusha.org; Mon, 14 Oct 2024 02:30:14 -0700
Received: by mail-yw1-f191.google.com with SMTP id 00721157ae682-6e35865abe9sf25957337b3.0
        for <bitcoindev@gnusha.org>; Mon, 14 Oct 2024 02:30:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1728898207; x=1729503007; 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=8KDK5Jlhn/AB+BjmER8VKAoYck0uhmRdCLmEkawm4YA=;
        b=h5nivwZx+JK5IxyxUNOgrlmDpwBbfzcR2/T9Wx4/a+4W4MQ0TbHEP859Bww7tTkuW4
         1MrT/KV+qiOmM2EXgyB8bTAaSC5sQzahIlWTKcBE6cOZncfNAXngvKobc0Ru9h317vmo
         jVutA8nDqgawfmoMIrwojHMjHkYBy8xRLMW2OKUZS/2481X8xeEaX5QXcNWNZSwCC2Ti
         JooDvYRv4LQmR4+2KM04Y7lpWRLxtF8LEvWyW7OtM0phRf/EobsY+HEUS8egUGBNItj7
         2GyJ8yuHeMbomBW/Jny7lNsT9Fsuh4XiD83Dow4aSbC6KVMDksAI0E4LpIYent4K51RH
         mfpw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1728898207; x=1729503007; 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=8KDK5Jlhn/AB+BjmER8VKAoYck0uhmRdCLmEkawm4YA=;
        b=KT89gfaTl1WZ3DDe3PbqKa/Ehxplrf631y2BYPPxPHaiyjeBG7vCmgFYZIsOfxoiGn
         Mrh06Hfvk1RF3eWIOCVook/9E7yZaL80ZGGZULzTq0h036tZU5shdEANcanQ4lrm/JRO
         HsE7GxXhQk98FSmKeYZpa3T+5+ys1YgVUPxDppDH7WZnRZNILTjr26WPxDGsCwh8tvna
         zyOyZn3ONA9Rcky6hmBAjdsPsfdAytydFZ1M3VWbA47kqsvNrggaGTBX9dtDNLCgPbvE
         T5H5oO2VFLD1o61JPyAObzCPmzrETYbKXxMTxTfX8NYNDz2Zw1fOwHnvlQ2AU1nIwLsQ
         ArVA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1728898207; x=1729503007;
        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=8KDK5Jlhn/AB+BjmER8VKAoYck0uhmRdCLmEkawm4YA=;
        b=IWr5PFDmY9m0O0SI0PmeIm7953qMUGmwXI0JbBmxuM/aY6ld+kdNuLJyBNqmw38CYU
         tviVeEZi0TDDVEzsdsLax1AaDz3CphwcxTqjqklAaB4agTsvWXvl6YYT3TvmxdZBTU/n
         QDi7nSaHYydSg6YWggNZhPg3OUseVwa8OKi2NRhTbBJRzzhXQRgCCf8lV/8004HCUwwT
         arqozQEaVuCXonwsO9TNdCtrffjdIGP38XMyKTIvYfL0c7FhPUPtRlE85fmMHeImH/Lq
         8WNf6xTFMSnnOfjQYDtLS1JoHnWkx1QRTPlMDE79QPlSHdaykuWiA3JIY/pDRSuM1ov9
         s3hw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCUJQnOF5F0BSsk4cV/7+KlCA0WtJFDzrLenjA1x7Q5svYojYo07emj5THX044Ch9EaeJejGFpDH6EKT@gnusha.org
X-Gm-Message-State: AOJu0YyeJkQxOieKo8CXnuMAVDirsrQ80RqKMpaU6wDkhjHpgskk2ReX
	/1LFg+bR2Uvo2+FdDtfbSqG5wK+aSuYvFVzNKeTlvIH5T8TZP8Jr
X-Google-Smtp-Source: AGHT+IFqBCRI4p8+wigu471XXJk4y4GLmMfmMiIgXu8F/vEM4Zr8UkrykPLJLMV0RIbn+/Q3USsnvA==
X-Received: by 2002:a05:6902:1208:b0:e29:335d:5f0e with SMTP id 3f1490d57ef6-e29335d5ff1mr4697416276.18.1728898207340;
        Mon, 14 Oct 2024 02:30:07 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:725:b0:e26:bea:956d with SMTP id
 3f1490d57ef6-e290bb7c459ls350435276.2.-pod-prod-03-us; Mon, 14 Oct 2024
 02:30:05 -0700 (PDT)
X-Received: by 2002:a05:690c:92:b0:6db:d217:895e with SMTP id 00721157ae682-6e347c486b3mr71863077b3.36.1728898205124;
        Mon, 14 Oct 2024 02:30:05 -0700 (PDT)
Received: by 2002:a05:690c:3411:b0:6dd:c9c1:7a16 with SMTP id 00721157ae682-6e31ec95431ms7b3;
        Mon, 14 Oct 2024 02:00:15 -0700 (PDT)
X-Received: by 2002:a05:690c:63c7:b0:6dd:fb99:c220 with SMTP id 00721157ae682-6e3477cb0c8mr74481787b3.11.1728896414469;
        Mon, 14 Oct 2024 02:00:14 -0700 (PDT)
Date: Mon, 14 Oct 2024 02:00:14 -0700 (PDT)
From: Weiji Guo <weiji.g@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <5a7ee837-690b-4e0e-ba7c-a6e344b0589cn@googlegroups.com>
In-Reply-To: <63186352-b441-4548-b7fa-8ff0d5f6fc97n@googlegroups.com>
References: <93611162-6029-4308-98b5-3c95b30a2ac9n@googlegroups.com>
 <22162f02-9362-4d1c-b0ce-3cf8dd01bd93n@googlegroups.com>
 <8d3084bc-aece-48ba-a08d-01b53392b64dn@googlegroups.com>
 <63186352-b441-4548-b7fa-8ff0d5f6fc97n@googlegroups.com>
Subject: [bitcoindev] Re: OP_ZKP updates
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_445450_924296474.1728896414250"
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_445450_924296474.1728896414250
Content-Type: multipart/alternative; 
	boundary="----=_Part_445451_1267342522.1728896414250"

------=_Part_445451_1267342522.1728896414250
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

One more update before implementations:

1, Combine zkStark and aggregated IPA. Application circuits will be=20
developed and proved in skStark,
while the recursive verifier will be developed in aggregated IPA. This way=
=20
we may achieve 6~7 KB proof
size and around 1 second verification time for each OP_ZKP transaction.

2, There will be a threshold value T. That is, any bitcoin block may=20
contain at most T OP_ZKP transactions,=20
otherwise small miner such as Raspberry Pi 4 won't be able to verify the=20
block quick enough, even
as we implement the batched verification for aIPA.

3, Surpassing count T, we may have a block prove to recursively verify the=
=20
proof of all the OP_ZKP=20
transactions, generating a new proof for miners to verify. This time we are=
=20
NOT limited to schemes with
batched verification. Therefore we may consider for example, zkStark again,=
=20
so that the verification
will be very fast and the proof size is still acceptable.

We maintain a live doc in GH: https://github.com/opzkp/tea-horse=20
Please let me know if you have any comments.=20

Regards,
Weiji
On Wednesday, August 28, 2024 at 11:35:55=E2=80=AFPM UTC+8 Weiji Guo wrote:

> I believe I have found the solution to the open issue mentioned in the=20
> earlier email. It is just recursive=20
> verification. Instead of publishing each application circuit's=20
> verification key on-chain, we should have=20
> only one circuit that OP_ZKP will verify, which is a recursive verifier.=
=20
>
> Interested readers are welcome to visit the GitHub org dedicated for=20
> OP_ZKP: https://github.com/opzkp
>
> So far I have just put up the high level ideas here:=20
> https://github.com/opzkp/tea-horse. There are nothing
> else yet. But we will add stuff as we move on.
>
> Regards,
> Weiji
>
> On Tuesday, July 23, 2024 at 8:40:08=E2=80=AFAM UTC+8 Weiji Guo wrote:
>
>> Yes, that's true. With Dory we will have to work on some pairing-friendl=
y=20
>> curve. Not secp256k1.
>>
>> On Tuesday, July 23, 2024 at 3:01:59=E2=80=AFAM UTC+8 Weikeng Chen wrote=
:
>>
>> 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:
>>
>> =E2=80=94=E2=80=94=E2=80=94What-ifs=E2=80=94=E2=80=94=E2=80=94
>>
>> 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
>>
>>

--=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/5a7ee837-690b-4e0e-ba7c-a6e344b0589cn%40googlegroups.com.

------=_Part_445451_1267342522.1728896414250
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

One more update before implementations:<div><br /></div><div>1, Combine zkS=
tark and aggregated IPA. Application circuits will be developed and proved =
in skStark,</div><div>while the recursive verifier will be developed in agg=
regated IPA. This way we may achieve 6~7 KB proof</div><div>size and around=
 1 second verification time for each OP_ZKP transaction.</div><div><br /></=
div><div>2, There will be a threshold value T. That is, any bitcoin block m=
ay contain at most T OP_ZKP transactions,=C2=A0</div><div>otherwise small m=
iner such as Raspberry Pi 4 won't be able to verify the block quick enough,=
 even</div><div>as we implement the batched verification for aIPA.</div><di=
v><br /></div><div>3, Surpassing count T, we may have a block prove to recu=
rsively verify the proof of all the OP_ZKP=C2=A0</div><div>transactions, ge=
nerating a new proof for miners to verify. This time we are NOT limited to =
schemes with</div><div>batched verification. Therefore we may consider for =
example, zkStark again, so that the verification</div><div>will be very fas=
t and the proof size is still acceptable.</div><div><br /></div><div>We mai=
ntain a live doc in GH:=C2=A0https://github.com/opzkp/tea-horse=C2=A0</div>=
<div>Please let me know if you have any comments.=C2=A0</div><div><br /></d=
iv><div>Regards,</div><div>Weiji</div><div class=3D"gmail_quote"><div dir=
=3D"auto" class=3D"gmail_attr">On Wednesday, August 28, 2024 at 11:35:55=E2=
=80=AFPM UTC+8 Weiji Guo wrote:<br/></div><blockquote class=3D"gmail_quote"=
 style=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); p=
adding-left: 1ex;">I believe I have found the solution to the open issue me=
ntioned in the earlier email. It is just recursive=C2=A0<div>verification. =
Instead of publishing each application circuit&#39;s verification key on-ch=
ain, we should have=C2=A0</div><div>only one circuit that OP_ZKP will verif=
y, which is a recursive verifier.=C2=A0</div><div><br></div><div>Interested=
 readers are welcome to visit the GitHub org dedicated for OP_ZKP:=C2=A0<a =
href=3D"https://github.com/opzkp" target=3D"_blank" rel=3D"nofollow" data-s=
aferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://github=
.com/opzkp&amp;source=3Dgmail&amp;ust=3D1728982058288000&amp;usg=3DAOvVaw0w=
Bc72b6Y2BKY4bYEXWo_C">https://github.com/opzkp</a></div><div><br></div><div=
>So far I have just put up the high level ideas here:=C2=A0<a href=3D"https=
://github.com/opzkp/tea-horse" target=3D"_blank" rel=3D"nofollow" data-safe=
redirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://github.co=
m/opzkp/tea-horse&amp;source=3Dgmail&amp;ust=3D1728982058288000&amp;usg=3DA=
OvVaw11T2a7LuyWgVnlEH20FAvz">https://github.com/opzkp/tea-horse</a>. There =
are nothing</div><div>else yet. But we will add stuff as we move on.</div><=
div><br></div><div>Regards,</div><div>Weiji<br><div><br></div></div><div cl=
ass=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On Tuesday, July=
 23, 2024 at 8:40:08=E2=80=AFAM UTC+8 Weiji Guo wrote:<br></div><blockquote=
 class=3D"gmail_quote" style=3D"margin:0 0 0 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">Yes, that&#39;s true. With Dory we will ha=
ve to work on some pairing-friendly curve. Not secp256k1.<div><br><div></di=
v></div><div><div><div dir=3D"auto">On Tuesday, July 23, 2024 at 3:01:59=E2=
=80=AFAM UTC+8 Weikeng Chen wrote:<br></div></div></div><div><div><blockquo=
te style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204)=
;padding-left:1ex"><div><div><div>I need to point out that Dory requires pa=
iring, and therefore it cannot work with secp256k1?</div><div>Please circle=
 back.</div></div></div></blockquote></div></div><div><div><blockquote styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex"><div><div dir=3D"auto">On Monday, July 22, 2024 at 9:16:18=E2=
=80=AFAM UTC-5 Weiji Guo wrote:<br></div></div></blockquote></div></div><di=
v><div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid =
rgb(204,204,204);padding-left:1ex"><div><blockquote style=3D"margin:0px 0px=
 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">





<p>=E2=80=94=E2=80=94=E2=80=94What-ifs=E2=80=94=E2=80=94=E2=80=94<br></p></=
blockquote></div></blockquote></div></div><div><div><blockquote style=3D"ma=
rgin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:=
1ex"><div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px sol=
id rgb(204,204,204);padding-left:1ex">
<p>What if the open issue cannot be resolved? We might consider Dory. It is=
=C2=A0<br></p>
<p>transparent, requires pairing, and has logarithmic proof size but concre=
tely larger=C2=A0</p></blockquote></div></blockquote></div></div></blockquo=
te></div></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/5a7ee837-690b-4e0e-ba7c-a6e344b0589cn%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/5a7ee837-690b-4e0e-ba7c-a6e344b0589cn%40googlegroups.com</a>.=
<br />

------=_Part_445451_1267342522.1728896414250--

------=_Part_445450_924296474.1728896414250--