From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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:

1, Combine zkS= tark and aggregated IPA. Application circuits will be developed and proved = in skStark,
while the recursive verifier will be developed in agg= regated IPA. This way 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 m= ay contain at most T OP_ZKP transactions,=C2=A0
otherwise small m= iner such as Raspberry Pi 4 won't be able to verify the block quick enough,= even
as we implement the batched verification for aIPA.

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

We mai= ntain a live doc in GH:=C2=A0https://github.com/opzkp/tea-horse=C2=A0
=
Please let me know if you have any comments.=C2=A0

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 me= ntioned in the earlier email. It is just recursive=C2=A0
verification. = Instead of publishing each application circuit's verification key on-ch= ain, we should have=C2=A0
only one circuit that OP_ZKP will verif= y, which is a recursive verifier.=C2=A0

Interested= readers are welcome to visit the GitHub org dedicated for OP_ZKP:=C2=A0https://github.com/opzkp

So far I have just put up the high level ideas here:=C2=A0https://github.com/opzkp/tea-horse. There = are nothing
else yet. But we will add stuff as we move on.
<= div>
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 ha= ve to work on some pairing-friendly 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 pa= iring, and therefore it cannot 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= =C2=A0

transparent, requires pairing, and has logarithmic proof size but concre= tely larger=C2=A0

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