Delivery-date: Mon, 14 Oct 2024 02:30:14 -0700
Sender: bitcoindev@googlegroups.com
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"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_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--