晶格、折叠与交响乐——陈彬彬

但现在我们已经习惯了YouTube。

But now we are get get used to YouTube.

对吧？

Right?

是啊。

Yeah.

所以这更像流水线作业，用户体验也好得多。

So it's it's more pipeline and it's much better experience.

有意思。

Interesting.

我认为我最初的问题其实是：递归和折叠对SNARC的哪部分功能有帮助？

I think in my initial question, it was sort of like, there's also this question of like, what part of the SNARC does recursion and folding help with?

那么是证明时间缩短了，还是验证时间受到了影响？

So does the proof time go down, or does the verifying time get affected?

没错。

Yeah.

我只是好奇是否存在某种权衡。

I'm just curious if there's like a trade off at all.

实际上，验证折叠方案会更困难吗？

Is it harder to verify a folded scheme, actually?

是的。

Yes.

我认为主要动机是缩短证明时间。

I think the main motivation is proof time.

好的。

Okay.

我想特别是为了节省内存。

And it's particular for and also memory, I guess.

既节省内存又缩短时间，但尤其适用于那些大规模问题。

Both memory and improved time, but particular for those large problem.

所以如果你的任务并不复杂，比如只是证明单笔交易或验证一个哈希值，就没必要使用折叠方案。

So if your task is not very complex, if you're just proving single transaction or just proving a hash, you don't bother to use folding.

你只需使用简单的sigma协议或SNARC即可。

You just do a simple sigma protocol or SNARC.

这样就足够了。

That's good enough.

只有当面对真正大规模的问题时才有意义，比如CK版本的机器

It makes sense only when it comes to a really large problem, like CK version machine

嗯。

Mhmm.

或者说，像可验证的机器学习这种情况。

Or, like, verifiable machine learning.

这种情况下，使用单一的整体SNARC来高效证明并不那么容易。

In this case, it's not that easy to use a monolithic SNARC to prove efficiently.

因此你必须先将这个大问题拆分成较小的问题，然后再使用SNARCs。

So you had to split this large problem into a smaller problem first and then use SNARCs.

而折叠恰恰是一种非常高效、可扩展且内存利用率高的方法，能将这个庞大的问题分解为较小的问题。

And folding is exactly a very efficient way and a scalable way and as well as memory efficient way to reduce this really large problem into smaller problem.

我记得最初分享时提到过，它特别适合处理某些重复性高的问题。

And I think I remember when it was first shared, it also is really good for certain types of problems which are, like, repetitive.

是的。

Yes.

比如你需要重复执行的步骤。

Like, you want repetitive steps.

你不想要动态电路或大量变化，而是需要相当一致的东西。

You don't want, like, dynamic circuits and lots of different like, you want something quite consistent.

没错。

Exactly.

举例来说，如果你需要一个CPU，你不会想要定制电路。

So for example, you if you want to have a CPU, right, you don't have, like, custom circuit.

你需要的就是CPU。

You want to have CPU.

每次只需运行单一指令，而折叠技术正是为此量身打造的。

Well, each time, just run a single instruction, and folding is perfect for this.

嗯，每个代码块语句只需一条指令。

Well, each chunk statement, just one single instruction.

我想提两点。

And I want to mention two things.

首先，我们选择折叠（folding）是因为它非常适合这种统一计算。

First is that, first, we do this for folding is because folding is perfect for this uniform computation.

如果这种计算具有迭代性质，就完全契合折叠框架。

So if this computation satisfies property, which is kind of iterative, it perfectly fits for the framework folding.

但我想提到最近有篇名为《Mangroove》的论文，它实际上能将任意计算

But I do want to mention that recently there's a paper called Mangroove, which actually can reduce some arbitrary computation

嗯哼。

Uh-huh.

分解为多个统一计算。

Into many uniform computation.

之后你同样可以开始进行折叠处理。

And after that, you can start doing the folding as well.

酷。

Cool.

所以它比那个更通用。

So it's more general than that.

好的。

Okay.

那么现在让我们进入第二部分，关于格点结构。

And then now let's go to that second part, which is like lattices.

所以你正在介绍格点结构。

So you're introducing lattices.

这样是否让审批时间变得更高效了？

Is approving time made even more efficient?

就像，是的。

Like, which yeah.

再问一次，哪些部分会受到影响，引入格点结构时有什么权衡吗？

Again, which part is affected, and is there any trade off when you introduce lattices?

流程中有任何部分会变慢吗？

Does any part of the process get slower?

是的。

Yeah.

非常好的问题。

Very good question.

最初，我们使用格密码的目标不仅是为了后验安全性。

So, initially, our goal for using Lattices is not only for postcon security.

实际上我们是想加速证明者的效率。

It's actually we want to accelerate the prover.

我们想让证明者比基于LipGER的流式方案更快。

We want to make prover even faster than LipGER based flowing schemes.

为什么？

Why?

因为我们在上一场战争中也获得了一些非常不错的承诺。

Because we have some really nice commitment in the last war as well.

我想澄清一下，1992年发明的原始ITI承诺方案其实效率并不高，因为它是基于某些整数格构建的。

I do want to clarify that the original ITI commitments that was invented in 1992 is actually not that efficient because it's based on some integer lattices.

但后来，在环环境下——比如多项式环环境下——它被Vadim、Chris Piker、Alan Rawson和Danielle Lee Michian Show等人进行了优化和改进，我想大概是在2006年左右。

But later, it has been adapted and optimized in the ring setting, like, polynomial ring setting by Vadim, Chris Piker, Alan Rawson, and Danielle Lee Michian Show around, I think, around 2006 or something.

是的。

Yeah.

可能是2006年。

Maybe 2006.

在那之后，这个方案变得更高效了。

So after that, the item becomes more efficient.

基本上，其复杂度从二次方降到了接近线性，速度大幅提升，而且具有高度可并行性。

They basically, the complexity goes from quadratic to cosine linear, and it's much faster than that and also highly paralyzable.

此外，你还可以用小域来实例化它。

And moreover, you can use some small fields to instantiate.

这使得它变得极其快速。

So that makes it extremely fast.

这就是我们采用这类承诺方案的动机之一。

So that's the one of the motivation for using that kind of commitments.

总结来说，我们具有可证后提交安全性，理论上还可能实现更快的证明者。

So in summary, we have plausibly post comm security, but and in theory, we might also guess even fast prover.

这确实很棒。

So that's really nice.

这就是我们研究它的动机所在。

That's why we have some motivation to study it.

是的。

Yeah.

我想补充另一个动机点。

I'll add another piece of motivation, actually.

使用Lipstick曲线承诺时，你的见证和电路都存在于某个域中

With the Lipstick curve commitments, you have your witness, your circuit lives in a field

嗯。

Mhmm.

当你进行承诺时，你需要将它们放在椭圆曲线上。

And then when you do commitments, you put them on an elliptic curve.

对。

Yes.

对吧？

Right?

然后当你想执行验证器的递归检查步骤时，现在你必须用你的域来编写关于椭圆曲线的陈述。

And then when you want to do this recursive step of checking your verifier, you now have to write statements about the elliptic curves with your field.

所以你会遇到这种奇怪的递归现象

So you have this weird recursive thing happening

是的。

Yeah.

这实际上相当麻烦。

And this is actually quite painful to do.

它会让你的电路变得非常大，这就是为什么我们处理这些曲线循环时非常痛苦，还导致了各种错误。

It makes your circuits very big, and that's why we had these cycles of curves that were very painful to deal with, that caused bugs.

所以早在Protosar和Nova问世时，我们就在想，如果能摆脱这些曲线循环该有多好？

And so even back when Protosar and Nova came out, we were all thinking, wouldn't it be nice if we could get rid of these cycles of curves?

我们能否用格密码之类的方法来实现呢？

And can we use things like lattices to do that?

是的。

Yeah.

这个观点非常到位。

That's a very good point.

引入格密码会有什么缺点吗？

Are there any downsides to introducing lattices?

有。

Yes.

确实存在。

Definitely.

有的。

Yes.

就像，每当你引入新事物时，总会有一些权衡。

Like, whenever you introduce something, there are some trade off.

好的。

Okay.

很高兴听到这个。

Good to hear.

天下没有免费的午餐。

No free lunches.

是啊。

Yeah.

完全没有免费的午餐。

No free lunches at all.

特别是在我们第一代晶格折叠简化方案中，虽然它们相当有竞争力，正在变得实用。

And especially in our first generation of lattice folding simps schemes, even though they are pretty competitive, they are becoming practical.

它们仍然没能超越椭圆曲线方案的最先进水平。

They still didn't beat the state of the art of elite of Elliptic curve schemes.

正如我之前提到的，原因在于我们实际上在处理一个更复杂的问题。

The reason is that, as I mentioned before, we actually are dealing with a harder problem.

对吧？

Right?

我们必须处理范数爆炸的问题。

We have to deal with norm blow up.

我们必须证明这些范数是低范数的。

We have to deal with proving that norm are low norm.

这些额外任务使得基于格的音位方案构建更加困难，同时也增加了音位方案的复杂度。

So these are extra tasks make the construction of lattice based phoneme schemes harder, and that also adds complexity of the phoneme schemes.

例如在第一代格折叠方案中，为了证明范数是低或小的，你必须先将原始弱点分解为多个范数更低的弱点向量。

For example, in the first generation of lattice fold, in order to prove that the norm are low or small, you have to first decompose the original weakness into multiple weakness vectors, which are even lower norms.

只有这样你才能运行所谓的拇指检查协议来证明它。

And only then you can run some so called thumb check protocol to prove it.

这意味着证明者的工作量更大，因为他们需要提交更多的向量。

And that means the provers work is more because they need to commit to more vectors.

假设最初你只需要提交一个向量，现在却需要提交比如10或16个向量，这显著增加了证明者的开销。

Suppose initially, you only need to commit to one vector, now you have to commit, say, like, 10 or 16 vectors, which is more prover expensive.

因此尽管基于RIM的临时承诺本身效率更高，但实际需要完成的工作量反而更大。

So even though ad hoc commitment itself or RIM based ad hoc commitment itself is more efficient, the work you have been done is actually more.

所以速度实际上并不比基于椭圆曲线的方案更快。

So the speed is actually not faster than ellipse based falling schemes.

为了真正提高效率，我们确实需要更高效的范围证明方案。

So in order to make it more efficient, we really need to have a more efficient range proofs.

这就是Lattice four和Lattice four plus的核心内容？

And that is the bulk of Lattice four, Lattice four plus?

是的。

Yeah.

我想这就是你在白板会议上讲解的内容。

And I think what you cover in the whiteboard sessions.

对吧？

Right?

是的。

Yes.

没错。

Exactly.

有趣的是，这个

It's funny when and this

这实际上让我想到了白板会议本身，因为在那次会议上，你提到了一些关于范围证明的查找工作，但我有点困惑，你好像说CQ在范围证明方面做了些事情，而我总觉得它们是相当独立的。

is actually bringing me to the whiteboard sessions themselves because in that, you mentioned a few, like, lookup works in that context of, like, range proofs, but I was confused what like, you sort of said, like, yeah, CQ does something with the range proofs, but I I always thought of them as being pretty separate.

查找表、查找参数的工作与范围证明之间是否存在某种联系？

Is there a connection there between, like, the lookup table, lookup argument work, and the range proofs?

如果存在的话，具体是什么联系呢？

And if so, like, what is it?

确实存在。

Definitely.

如果你仔细想想，范围证明实际上是查找参数的一种特例。

So if you think about this, range proof is actually a special case of lookup arguments.

对吧？

Right?

因为在范围证明中，你想要证明的是某个值处于特定范围内。

Because what you want to prove in a range proof is you want to prove that certain value is in certain range.

但这个范围本身也是一张表。

But this range itself is also a table.

只是张特殊的表。

It's just a special table.

哦。

Oh.

这张表包含了该范围内的所有数值。

The table includes the all the values of this range.

这意味着如果你有查找论证，那么你同时也就拥有了范围证明。

So that means if you have a lookup arguments, that you also have a range proof as well.

哦，哇。

Oh, wow.

是的。

Yeah.

不知为何，我感觉节目里从没真正提到过这一点。

For some reason, I feel like that never really came up on the show.

所以当我看着白板时，我就像这样——我举起了手，但你知道这只是视频，我人并不在场。

So that that was also like, as I was watching the whiteboard, I was like, you know, I was putting my hand up, but, you know, it's a video, and I wasn't actually there.

我没有参与录制。

I wasn't part of the recording.

不过，你知道，我

But, like, you know, I

就像那一刻，对，我当时就有这个疑问。

I it's like the moment where I, yeah, I had this question.

我当时有点困惑，但这个解释很有帮助。

I was kinda confused, but this is helpful.

实际上这很合理，你基本上只需要选择特定范围的查找。

And it makes sense, actually, that you just choose, like, the lookup of just a certain range, basically.

是的。

Yes.

对。

Yeah.

范围证明。

Range proof.

当你思考范围证明时，大家会认为它比查找问题更特殊甚至更简单。

When you think about range proof, you all think as a special or even simpler problem than lookup.

还有其他方法可以实现这个范围证明吗？

Are there any other ways to do this range proof?

我知道你们有两轮晶格折叠迭代。

I know that you have two iterations of lattice fold.

还有一篇名为NEO的论文我们应该提到——嗯。

There's also this paper called NEO that we should mention Mhmm.

那篇论文同样基于晶格进行折叠。

That also does folding based on lattices.

我在想，是的，所有这些技术，有的非常不同，有的非常相似，还有很多我想探索的吗？

I was wondering, yeah, all the techniques there, super different, super similar, and is there a lot more I'd like to explore?

是的。

Yes.

我认为基于格（lattice）的环境下，范围证明与其他基于椭圆曲线的环境略有不同。

So I think the lattice based setting, the range proof is slightly different from the other Ellipse curve based setting.

目前，我们主要有两个——或者说三个主要思路。

And currently, we have two main idea or three main ideas, I would say.

首先是做分解，其次是随机投影，这是使用Librato的思路。

First is doing decomposition, and second is to do random projection, which is the idea using Librato.

第三是LASSO plus中提出的单项式编码思路，通过重构PONOM环来证明某些查找关系。

And third is the idea in LASSO plus, which we call the monomial encoding, where you just use some kind of restructure of PONOM ring to prove some lookup relations.

这些方法各有优缺点。

All these are having their pros and cons.

我想特别提到，最近在这篇我想稍后讨论的新论文中，我们还提出了一种新的基于格的折叠方案，其中包含了一种结合投影和单项式编码的新型范围证明。

And I want I want to mention that recently in this new paper I'm I want to discuss later, we have also have a new lattice based following scheme, which has a new range proof, which is kind of combination of projection and nominal encoding.

这使得整个过程更快更简单。

That makes this much faster and much simpler.

所以Neo的主要贡献，我认为并不在于范围证明。

So Neo, I think the main contribution of Neo is, I guess, is not a range proof.

它同样采用了最后折叠分解的模式，但在支持小域和更自然地编码约束方面，具有其他非常出色的风险类特性和贡献。

It uses this paradigm of decomposition of last fold as well, But it has some other really nice, risk like, properties and contributions in terms of supporting small field and encoding the constraints in a more natural way.

嗯。

Mhmm.

所以我认为他们会用分解来做分支证明。

So I think they'll use decomposition to do the branch proof.

使用格结构或结合格结构中的折叠是否存在其他权衡或缺点？

Are there any other trade offs or downsides to using lattices or to combining folding in lattices?

是的。

Yes.

这一点我认为会与我稍后要讲的新工作有所关联。

And this is something that I think will have connection to what I said later in terms of the new work.

除了证明者的开销外，验证者的开销也是个问题。

So beyond this prover overhead, this verifier overhead is also an issue.

好的。

Okay.

尽管它比基于哈希的签名方案要好得多，但实际上仍不如基于椭圆曲线的签名方案。

Even though it's much better than hash based phoneme scheme, it's actually still worse than ELIP curve based phoneme schemes.

啊。

Ah.

原因是需要运行这个Fierce和Mir电路。

So the reason is that you have to run this Fierce and Mir circuit.

对于不熟悉的人来说，Fierce Amir是一种通过使用哈希函数在交互记录上生成这些非常远的挑战，将交互式协议转换为非交互式协议的方法。

For those who are not familiar, Fierce Amir is a way to convert an interactive protocol into a non interactive protocol by generating these very far challenges using a hash function on the transcript.

在最后的设置中，这个记录比椭圆曲线设置要大得多，因为这些ITEC承诺比片段和哈希值更大。

And in the last setting, this transcript is much larger than a ellipse curve setting because these ITEC commitments are larger compared to pieces and hashes.

每个ITEC承诺可能大到四甚至八 kilobytes。

Is each ITEC commitments can be as large as in as four kilobytes or even eight kilobytes.

如果你需要在这个记录中对许多承诺进行哈希处理，那么仅执行Fierce Amir哈希的复杂度就已经相当高了。

And you have if you have many commitments to hash inside this transcript, then this complexity of just doing the Fierce Amir hashing is already pretty expensive.

嗯。

Mhmm.

所以问题之一就是：能否在Variable中移除这个Fierce Amir电路，从而使递归电路变得更小？

So the one of the questions, can you remove this Fierce Amir circuit in the Variable to make the recursive circuit much smaller?

嗯。

Mhmm.

顺便说，作为对比，Pedersen承诺和Pedersen哈希只有几个字节大小。

By the way, for comparison, the Pedersen commitments, Pedersen hashes are, like, a few bytes.

对吧？

Right?

是的。

Yeah.

大概是32字节或48字节左右。

32 bytes or forty forty eight bytes, I guess.

是的。

Yeah.

第一个数量级的差异。

The first one magnitude difference.

对。

Yes.

嗯。

Yeah.

这算是另一个定义问题，但你在白板上提到过，实际上Vadim在他的讲解中也提到了SIS。

This is kind of another definitions question, but you mentioned it in your whiteboard, and actually Vadim mentioned it in his as well, the SIS.

嗯。

Mhmm.

你今天在采访中已经定义过了，但能谈谈它到底是什么吗？

And you you already have defined it today in in the interview, but can you talk about what that actually is?

因为它出现了。是的。

Because it comes up Yeah.

每次你们讨论格理论时都会提到。

Every time you're talking about lattices.

是的。

Yeah.

SIS（最短整数解假设）就像是连接基础格问题与密码学应用的桥梁。

So SIS or shortest integer solution assumption is kind of a bridge between this really fundamental lattice problem and the cryptographic applications.

好的。

Okay.

这是一个密码学假设，意思是给定一个随机生成的矩阵A，很难找到一个短向量X使得A乘以X等于零。

So this is a cryptographic assumptions, which is saying that given a randomly generated matrix a, it's hard to find a small vector x such that when a times x, you get zero.

如果不对这个向量X做任何限制，你其实很容易就能解出这个方程。

So if you don't have any constraints on this vector x, you can actually very easily solve this equation.

对吧？

Right?

本质上这就是一组线性方程组，可以直接求解。

Basically, there's just a bunch of linear equations and then can solve it.

这是个简单问题。

That is the easy problem.

但事实证明，当你添加这些微小约束条件——必须确保x的范数很小，或者说这个向量的每个元素都很小——这就变成了一个非常困难的问题。

But it turns out when you add these small constraints that you have to make sure this x is no norm or, like, every element of this vector is small, this turns out to be a really hard problem.

我们有一个归约证明：如果你能解决这个问题，就能解决高维格中的某些真正困难的格问题。

And we have a reduction that if you can solve this problem, you can solve some really hard lattice problems in the high dimensional lattices.

但在这个情况下，这是不是

But in this case, is this one

那种密码学时刻——你希望它很难？

of these, you know, cryptography moments where you want it to be hard?

确实如此。

We do.

是的。

Yeah.

对。

Yeah.

就是说，你希望它非常困难，因为你不希望它被破解。

Like, you want it to be very difficult because you don't want it to be breakable.

对吧？

Right?

是的。

Yes.

我们希望它真的非常难。

We want it to be really hard.

好的。

Okay.

只是每次提到SIS问题时都觉得有点好笑，听起来像是我们要解决的问题，但其实重点不在这。

It's just funny whenever like, the SIS problem, it sounds like something that we're trying to solve, but that's not the point.

不是。

No.

不是。

No.

不。

No.

我们喜欢这样。

We like it.

我们希望它很难。

We want it to be hard.

是的。

Yeah.

我们绝对希望它很难。

We definitely want it to be hard.

否则，大多数格密码学都会崩溃。

Otherwise, like, most of the lattice cryptography will collapse.

我明白了。

I got it.

嗯。

Mhmm.

是的。

Yeah.

但话说回来，这确实是个问题，我们确实希望人们尝试解决它，因为尝试的人越多，我们就越能确定它的难度。

But by the way, it is a problem, and we do want people to try to solve it because the more people try, the more we know it's hard.

对。

Yes.

所以这

So it's

就像如果SIS问题被解决了，对格密码来说会很糟糕，但也许对整体安全有好处，因为我们会知道

like if the SIS problem was solved, that would be bad for lattices, but maybe good for, like, you know, general safety and security because we would know

没错。

Yes.

这还不够

This wasn't hard

难。

enough.

是的。

Yeah.

那将是一个真正的突破，如果我们能取得这些成果，会是非常重要的。

And that would be a really breakthrough, like, very, very important results if we do have these Mhmm.

成果。

Results.

不过感觉上，量子计算机似乎无法破解它。

And the feeling, though, is that the quant like, quantum computers can't break it.

如果你觉得这不是我们要找的，那么假设就是量子计算机无法破解它。

If you're feeling it's not what we're looking for, the the assumption is that you can't break it with quantum computers.

我的意思是，目前这更多是一种普遍感觉或普遍看法。

I mean, it is, at this point, you know, a general feeling or a general sentiment.

是的。

Yeah.

这就是我们的工作方式。

Like, that that is just how we work.

是的。

Yes.

首先，我无法给出一个很好的解释说明为何它能抵御量子计算攻击。但关键在于，我们已经对这些算法进行了三十多年的密码分析，这是最成熟且经过时间检验的假设之一——至今仍未出现真正有效的攻击手段

First, I don't have a really good explanation on why it will be against quantum computing attacks, But the thing is that we have gone through thirty years or more of cryptanalysis of these words, and this is one of the most mature and time tested assumptions that no really good attacks on top of it

嗯。

Mhmm.

即便是量子计算机也无法破解。

Even for quantum computers.

而且有许多极具天赋的研究人员

And there are many really talented researchers.

他们基本上只专注于格密码分析工作

They are basically just working on cryptanalysis on lattices.

试图破解它们？

Trying to break them?

对。

Yeah.

试图破解它们，但我们目前还没有很好的解决方案。

Trying to break them, and we don't have a really good solution yet.

当你决定开始研究Lattice Fold时，在Protostar项目和我们那次访谈之间，再到Lattice Fold和Lattice Fold Plus期间，格密码领域发生了什么变化，使你们能够开始使用它们？

When you decided to start working on Lattice Fold, in that time between Protostar and that interview we did and Lattice Fold and Lattice Fold Plus, what happened in lattices that changed, that allowed you to start using them?

你在节目前面提到过，大概两年后，你们开始意识到'哦，我们其实可以做到这个'。

You sort of mentioned earlier on in the episode that, like, two years on, you started to see, oh, we can actually do this.

但具体是什么？

But what was it?

是像Labrador那样的工作吗？

Was it like the Labrador work?

是出现了什么新成果，还是发生了什么变化？

Was it something that came out, something that changed?

是的。

Yes.

我想主要是因为当时我们在这方面投入的时间还不够多。

So I think it's just we didn't spend too much time on it at that time.

然后你看了看，心想，嘿。

And then you looked, and you're like, hey.

我们可以做到。

We could do it.

是的。

Yeah.

我想可能这某种程度上是预先想好的。

I think maybe it's come kind of pre thought.

就像，当我们思考这个问题时，当我们思考折叠时，我们总是想着折叠。

Like, when we think about this problem, when we think about folding, we always think about folding.

我们从未考虑过分解。

We never think about decomposition.

这就是为什么我们认为折叠后无法控制规范。

So that's why we think there's no possibility of controlling the norm after folding.

但事实证明，如果你先分解再折叠，实际上就能控制这个规范，这是思维转变带来的第一步突破。

But it turns out if you fold if after folding, you decompose first and then you fold and you actually control this norm, and this is the first step that the change of man mindset makes it possible.

第二点是这个范围证明。

And the second is this range proof.

我认为这个范围证明某种程度上同时受到了Librato和Thumbcheck的启发。

I think that range proof is kind of inspired by both, inspired by Librato as well as Thumbcheck.

好的。

Okay.

因为我之前花了很多时间研究Thumbcheck，结果发现Thumbcheck确实是个很好的协议，能帮助你证明某些关系。

Because I'm previously, I was working a lot on Thumbcheck, and it turns out Thumbcheck is a really nice protocol to help you to prove some relations.

事实证明这种分支证明关系就是其中之一，可以被涵盖。

It turns out this branch proof relation is one of them, can be covered.

所以实际上你可以用SumCheck来为此提供分支证明。

And so you can actually use SumCheck to give a branch proof for that.

更重要的是，这个分支证明具有次线性验证复杂度，这在折叠案例中非常重要。

And moreover, this branch proof has sublinear verify complexity, which is very important in the folding case.

我们无法直接在Labrador中使用的原因，正是因为Labrador的验证复杂度实际上是线性的，这不足以支持折叠应用。

The reason we cannot directly use in Labrador is exactly because the verifier complexity of Labrador is actually linear, which is not enough for folding to be used.

这就像是几种不同研究线索的汇聚，意味着现在正是我们深入探索的好时机。

So it's like a it's sort of a convergence of a few different research threads that meant actually now is a good moment for us to really dive into this.

是的。

Yes.

没错。

Exactly.

这个领域需要来自折叠世界的人去审视所有这些格点工作，并将它们整合起来使其运作。

It's an area that needed someone who was from the folding world to go and look at all these lattice works and put things together and make it work.

而这正是Binya和Dan在Lattice Fold中所做的。

And that's exactly what Binya and Dan did with Lattice Fold.

我...我过去可能说过Lattice Fold像是Labrador之后的延续，但我觉得这个说法也需要修正。

I I I think I, in the past, have sort of talked about, like, Lattice Fold is like a continuation after Labrador, but I I feel like I've been corrected on that too.

我的意思是，它可能受到了一些影响，但本质上并不是同一种格点结构。

I mean, I'm guessing it's taking some influence from it, but it's not really the same kind of lattice.

能否请你描述一下这些研究线索是在哪里分叉的？

Like, maybe can you just describe, like, where those research threads diverge?

这是Labrador Greyhound项目，然后，是的，接着是Lattice Fold相关的工作。

This is Labrador Greyhound, and then, yeah, and then sort of the lattice fold work.

我认为Labrador项目主要是用于论证，比如简洁的论证。

I think the Labrador one is mainly for arguments, like, succinct arguments.

嗯。

Mhmm.

从某种意义上说，他们想要构建一个能直接证明这种关系的小型证明论证系统。

In a sense, they they want to prove argument system that has small proof directly proving this relation.

因此在密码学原语方面，它们与折叠方案略有不同。

So in terms of crypto primitive, they are slightly different from folding.

嗯。

Mhmm.

而后续的Greyhound项目是对Labrador的优化，它将方案的验证复杂度从线性提升到了平方根级别。

And, the follow-up, Greyhound, is kind of a optimization to Labrador, which improved the verified complexity of the scheme from linear to square root

嗯。

Mhmm.

不过它仍然比不上多对数复杂度。

Though it's still worse than polylogarithmic.

另一方面，我想提一下还有另外一些工作，比如'石头剪刀布'，以及最近出现的'摇滚'。

On the other hand, I want to mention there are also some other work called the Rock and Paper and Scissors and also recently Rock and Roll.

哦，是的。

Oh, yeah.

这些是基于格论证的另一条研究路线，不仅证明规模小，验证复杂度也呈符号级缩小。

They are another line of work for lattice based arguments that not only have small proof sizes, but also a symtology small verify complexity.

我认为是多对数级别的验证复杂度。

I think it's polylogarithmic verify complexity.

但与Librato相比，它们的实际效率较低。

However, they are compared to Librato, they are less concretely efficient.

但我确实认为有许多新工作和后续研究正在尝试让它们变得更实用。

But I do think there are many new works, follow ups that try to make them more practical as well.

以上就是论证方向的第一条研究路线。

So that will be the first line in terms of arguments.

真有趣。

It's funny.

摇滚乐。

The rock and roll.

我在ZK Mesh上看到的。

I I saw that for ZK Mesh.

这是最近才发布的。

It came out really recently.

对吧？

Right?

是的。

Yes.

它始于这个石头剪刀布，而摇滚乐是对该工作的优化和后续研究。

So it starts with this rock paper scissors, and the rock and roll is kind of a optimization and a follow-up to that work.

好的。

Okay.

我得把它收录到新版里。

I'll have to include it in a in a new edition.

非常酷。

Very cool.

好的。

Okay.

那真是太棒了。

That was really great.

感谢分享这种区别。

Thanks for sharing that kind of distinction.

这一点我一直不太清楚。

This has been something I wasn't quite clear on.

我原本以为它更像是一种延续。

I really thought of it as, like, a continuation.

但你知道吗，就像晶格作为一个主题越来越受关注，然后我就明白了，哦，原来是这样。

But, you know, it's just like lattices as a theme were becoming more and then I was like, oh, this is why.

那么，宾妮，你之前提到即将开展的新工作涉及折叠技术，以及一种通过组合折叠场景来获取snorkeys的新方法。

So, Binnie, earlier you teased out that you had some new work coming up that also involves folding and a new way to combine folding scenes to get snorkeys.

能否详细谈谈这项工作的动机，以及其中的具体内容？

Can you tell us a bit more about the motivation for this work and, like, what's happening in there?

好的。

Yeah.

当然。

Definitely.

我想他们部分提到过，之前的falling方案，特别是基于last的falling方案，在证明Fierce和Mir电路时存在一些明显缺陷。

So I think they'll also partially mention this, that the previous falling schemes, especially last based falling schemes, they have some discount drawback of proving Fierce and Mir circuits.

从这个角度看，Fierce和Mir电路相当庞大，因为我们的art操作其实很简单，只是环元素的组合。

So Fierce and Mir circuit is pretty large in that sense because our art operation is pretty simple just in a combination of ring elements.

所以这是我想移除这个Fierce Schemer电路的首要原因。

So this is the first reason that I want to remove this Fierce Schemer circuit.

今年早些时候，我读到了Rong、Lev和Dimitri合著的这篇论文。

Early this year, I came across this paper by Rong and Lev and Dimitri.

他们针对基于GKR的证明系统提出了一个非常精妙的攻击方法。

They come up with this really elegant attack towards the GKR based proof system.

嗯。

Mhmm.

简单介绍一下背景，GKR 2008是一个非常优雅的交互式证明系统。

So to give a a little bit background, GKR 2,008 is a very elegant interactive proof system.

最初它们是交互式协议，意味着存在一个在线阶段。

So initially, they are interactive protocols, meaning that's an online phase.

证明者和验证者需要通过通信来确认某种算术电路计算是否正确完成。

The prover and the verifier needs to communicate to check certain kind of arithmetic circuit computation was done correctly.

但事实证明，我们也可以通过使用这种启发式方法使其非交互化，即通过对话记录的哈希计算来生成验证文件变更。

But it turns out we can also make it noninteractive by using this this heuristics that generates the very file changes using the hash computation of the transcript.

我们甚至在理想化模型中为此提供了某种安全性证明，将哈希函数视为随机预言机，即本质上是一个可以黑盒方式调用的随机函数。

And then we even have some kind of security proof for that in an idealized model, where we treat these hash functions as some random oracle, meaning that's that's basically just some random function that it can carry in a black box way.

但这个攻击表明，当你将这个哈希函数实例化为现实世界中的具体函数时，这个方案就不再安全了。

But it turns out what this attack is showing you is that whenever you instantiate this hash function into a real world concrete hash function, it turns out this scheme no longer is no longer secure.

具体而言，他们能够为某些错误陈述生成有效证明，从而破坏了系统的可靠性。

And particularly, they're able to generate a valid proof for some false statements, which break the soundness of the system.

嗯。

Mhmm.

实现这种攻击的核心思路是，它允许证明者为某些包含字段虚假启发式内容的陈述生成证明。

And the main idea of enabling this attack is because it allows the prover to generate a proof for certain statements where these statements is proving some field shammy heuristics inside the statements.

之所以这样做很重要，是因为它能让证明者在电路中预测这个极快的手势操作，凭借其能力，可被利用来为错误陈述生成虚假证明。

And the reason why why it is important to do that is because it allows the prover to generate, to predict this very fast hand inside circuit, which given its power, they can be exploited to generate a fake proof for some false statements.

这个结果其实我们早就知道了。

This is, you know, a result that we knew from back in the day.

就像那些在随机预言模型中安全的协议，当你用哈希函数替换随机预言后，在实际模型中并不总是安全的。

Like, protocols that are secure in the random Oracle model are not always secure in the real model when you change the random Oracle for a hash function.

但在当时，我们只有一些非常古怪协议的例子。

But at the time, we only had, you know, examples for very weird protocols.

是的。

Yes.

就像，你必须真正设计出一个故意要被破坏的协议。

Like, you have to really come up with a protocol that's really designed on purpose to break.

嗯。

Mhmm.

对吧？

Right?

而今年早些时候的这篇新论文，就像是首次出现了一个实际存在、被人们使用且自然产生的协议遭遇了这个问题。

And then this recent paper earlier this year was, like, the first time that there was a natural protocol that was out in the wild that people used that actually suffers this problem.

是的。

Yes.

就像Vinny说的，攻击的一部分是在电路内部进行fiat shimmer操作，我想这就是你要说的。

And like Vinny is saying, it's part of the attack was to do fiat shimmer inside the circuit, and that's, I think, where you're going.

Vinnie说的正是折叠过程中发生的情况。

Vinnie is like, exactly what's happening in folding.

我们在电路内部进行fiat shimmer操作。

We do fiat shimmer inside our circuit.

但这突然意味着所有作品都不够安全了吗？你觉得需要写篇新论文来研究如何增强安全性，还是说你们已经通过其他特性具备了更高的安全性？

But what's did that mean that all of a sudden the works were less secure, and you felt like you needed to do a new paper to, like, figure out how to make it more secure, or were you already more secure because of some other feature?

这确实是对现实世界系统的攻击，但并非对所有递归SNARK系统的中间攻击。

So this is indeed an attack to a real world system, but that's not a mid attack to all the recursive SNARK system.

好的。

Okay.

它仅适用于这种基于GKR的系统，但无法直接作用于其他证明系统如Fry、Stark、Planck、Spartan、Hyperplunk等。

It's only working for this GKR based system, but not immediately working for other poof system like Fry, Stark, Planck, Spartan, Hyperplunk, so on.

不过这仍然令人担忧。

However, it's still worrisome.

对吧？

Right?

是的。

Yeah.

它打开了这扇门。

It opens the door.

嗯

Mhmm.

这说明是有可能的。

It says it's possible.

是的。

Yeah.

这动摇了我们的信心。

It shakes our confidence.

没错。

Yeah.

它改变了人们对它的信心。

It change the confidence of it.

嗯哼。

Uh-huh.

特别是对于递归SNARK来说，因为递归SNARK在他们的攻击中做的正是同样的事情。

And especially for recursive SNARKs because recursive SNARK is exactly doing the same thing in their attack.

他们的攻击恰恰关键利用了这一点：你可以在电路内运行Firschemir验证或Firschemir哈希。

Their attack is exactly crucially exploits this fact that you can run this Firschemir verify or Firschemir hashes inside circuits.

嗯。

Mhmm.

这种能力为你提供了一种攻击该方案的方法。

And that power gives you a way to attack the scheme.

嗯。

Mhmm.

所以我认为这降低了人们对这种递归框架的信心，即通过递归将后续方案转换为IVC或PCD。

So that give I think give less confidence on this kind of framework of doing recursion and convert the following scheme into IVC or PCD using recursion.

那你们修复了吗？

So did you fix it?

我不认为这是修复。

I wouldn't say it's fixes.

我只是尝试消除这个攻击面。

I just, like, try to remove this attack surface.

比如，我们在声明中并不证明任何字段的shammer电路。

Like, we don't we don't prove any field shammer circuits in the in the statements.

如果是这种情况，处理这类攻击会容易得多，因为电路逻辑更容易审计。

If that's the case, it's much easier to handle this kind of attack because circuit logic is much easier to audit.

你只需要确保它永远不会在电路内运行这些Fierce Hammer哈希函数或实例化随机预言机。

You just make sure that it never runs these Fierce Hammer hash functions or run instantial random Oracle inside circuits.

但在之前的框架中，审计要困难得多，因为无论如何你都必须这么做。

But in the in the previous framework, it's much harder to audit because, anyway, you have to do this.

对吧？

Right?

所以你无法判断是否存在某些微小变化会导致其可被攻击。

So you don't know whether there are some kind of really tiny changes that make it techable or not.

嗯。

Mhmm.

这几乎就像是KRS攻击风格的后门，与电路应有的功能无法区分，所以是的。

It's almost like backdoor in the style of the KRS attack is indistinguishable from what the circuit is supposed to do, and so that's Yeah.

超级困难。

Super hard.

是的。

Yes.

好的。

Okay.

所以这项新工作摆脱了虚假镜像。

So this new work gets rid of fiatry mirroring.

你要怎么做呢？

How how do you do that?

是的。

Yeah.

这项新研究被称为Symphony。

So this new work is called Symphony.

在介绍它的成果之前，我想先说说为什么取这些名字？

So maybe before before what it is achieves, I want to mention this, why these names?

嗯。

Mhmm.

这个名字有两个原因。

There are two reasons for this name.

第一个原因是，如果你看Symphony，对吧，这篇论文其实受到了许多先前优秀论文的启发。

The first reason is that if you look at Symphony, right, like, this paper is actually inspired by many previous works, many elegant papers previously.

如果把每篇论文比作乐器，那么我们在这里所做的就是尝试和谐地将它们组合在一起，让所有这些乐器共同演奏出一首交响乐。

If you think about each paper as instruments, then what we do here is try to just harmoniously combine them together and play all this instrument together to get a symphony.

很美。

Beautiful.

是的。

Yeah.

这就是我称之为交响乐的一个原因。

That's one reason why I call it a symphony.

第二个原因是，我尝试倡导一种新的折叠方式，即只折叠一次或两次。

And the the second reason is that I try to advocate a new way to do the folding, which is just folding only once or twice.

所以你只需要单次折叠，就像单次折叠一样，这就是一种交响乐。

So you've you've only fold sing like, fold for single times, so it's a kind of symphony.

这是单次折叠

It's a single folding

嗯。

Mhmm.

时间。

Time.

不错。

Nice.

是的。

Yeah.

所以这篇论文的主要思想或贡献是尝试倡导一个新的框架来进行折叠，并通过两个步骤将折叠转化为证明系统。

So the main idea or main contribution of this paper is try to advocate a new framework to do the folding and convert a folding into a proof system by two steps.

第一步是进行高元折叠而非低元折叠。

The first step is to do high arity folding rather than low arity folding.

这意味着我们希望您只需运行这些折叠步骤一次，甚至两次，但在每一步中，我们都将大量陈述合并为一个。

What does it mean is that we want you just to run these folding steps once or even or just twice, but in each step, we all fold a lot of statements altogether into one.

嗯。

Mhmm.

如果您查看之前的方案，我们只折叠两个或三个输入。

If you look at the previous schemes, we only fold two inputs or three inputs.

我认为通常是将少于10个输入合并为一个输入。

I think usually less than 10 inputs into one input.

在之前的方案中我们只能这样做的原因是验证者复杂度极高。

The reason why we can only do that in the previous scheme is because the verifier complexity is extremely large.

我们不想给验证者电路复杂度增加太多开销。

We don't want to add a lot of overhead on the verifier circuit complexity.

验证者取决于我们正在一起折叠的项目数量吗？

And the verifier depends on the number of things we're folding together?

正是如此。

Exactly.

好的。

Okay.

所以这实际上是一个线性关系。

So it's actually a linear relation.

如果你折叠两个输入，那么复杂度就是两倍的x。

So if you fold two inputs, then the say the complexity is two times x.

嗯。

Mhmm.

那么如果你折叠10个输入，验证复杂度将大约增加10倍。

Then if you fold 10 inputs, then the complexity verify complexity will be approximately 10 x.

所以如果你折叠1000个输入，复杂度会变得极其庞大。

So if you fold 1,000 inputs, would be extremely large.

这就像验证复杂度会爆炸性增长1000倍。

It's like a 1,000 time blow up on the verify complexity.

这就是为什么这类方法之前被认为在实际应用中不切实际的原因。

So that's the reason this kind of approach was deemed impractical in practice before.

但事实证明，我们改变了这一现状，发现只要能将Fierce Chamire电路移出证明声明之外，这实际上是可行的。

But it turns out, we changed this status quo, and we found that, actually, it is possible to do that as long as you can remove the Fierce Chamire circuit outside the proven statements.

这就是第一个贡献。

So that's the first contribution.

我们提出了一种基于层次格的新音素方案，即使对于数千或数万的大规模输入，其验证复杂度（不包括Fierce Chamire电路）也极小。

We come up with a new hierarchy lattice based phonemes for which the verified complexity excluding the Fierce Chamire circuit is extremely small even for really large inputs, like thousands or tens of thousand inputs.

第二步是设计一种方法，将这种层次折叠整合到新的证明系统中，该系统确实不需要将FIAH CHAMMER电路嵌入证明声明。

And the second step is to come up with a way that compile this folding hierarchy folding into a new proof system, which indeed does not need to embed this FIAH CHAMMER circuit into the proven statements.

这解决了两个问题。

And that solves two issues.

对吧？

Right?

首先是效率问题。

The first, efficiency issue.

我们不再需要验证这个庞大的fear chamois电路了。

We don't need to prove this large fear chamois circuit anymore.

其次，是解决了这类安全问题。

And second is solve this kind of security issue.

我们不再拥有这种可被利用或发动类似KRS攻击的攻击面。

We no longer have this attacking surface for exploiting or conducting these KRS like attacks.

所以这基本上就是两个主要成果。

So that's basically the two main results.

那么秘诀是什么呢？

So what's the secret sauce?

你们是怎么做到的？

How do you do that?

如何实现一个基于折叠技术却无需证明递归语句的SNARK？

How do you have a a snark that from folding that doesn't need to prove recursive statements?

实际上，这是个非常简单的思路。

So, actually, this is a very simple idea.

它是基于这种名为'提交并证明SNARK'的技术构建的。

It is built from this commit so called commit and prove SNARK.

我在想是否听说过这个。

I wonder if I have heard about this.

这是一类特殊的SNARK，证明者可以预先提交部分见证数据，然后再在线证明某些内容。

It's a special class of SNARKs for which the prover can commit part of the witness beforehand, before you prove something online.

嗯。

Mhmm.

之后，你可以证明一个同时涉及这些已提交数据和某些在线数据的关系。

And then later, you can prove a relation that involves both this committed data and some online data.

我猜是不需要在电路内部进行承诺操作。

I guess without doing the commitment inside a circuit.

对吧？

Right?

因为这正是我们想要避免的。

Because that's kind of what we're trying to avoid.

完全正确。

Exactly.

不在电路内部进行承诺，这样效率也更高。

Without doing the commitment inside circuits, and that makes it much more efficient as well.

嗯。

Mhmm.

让我举个具体例子说明它在另一篇论文Veritas中的应用，那是我、Tricia和Dan合著的另一篇论文。

So let me give a concrete example on how it is used in another paper called Veritas, which is another paper of me, I, and Tricia, and Dan.

哦，其实我们在节目里经常提到这篇论文。

Oh, we've mentioned it a lot on the show, actually.

是关于证明图片编辑的。

It's about proving edits on pictures.

对吧？

Right?

没错。

Exactly.

噢，是的。

Oh, yeah.

没错。

Exactly.

在那个例子中，如果你通过拍照获得了某张高分辨率原图的数字签名。

So in that example, if you have a digital signature for some original high resolution image by taking a photo.

对吧？

Right?

你有一台带有特殊芯片的特殊相机。

You have some special camera which has a special chip.

每次拍照时，这个芯片会对照片进行标记，以确保之后可以验证这张照片是由人类而非AI拍摄的。

Whenever take a photo, the chip will assign this photo to make sure later you can verify this photo is taken by a human being rather than being by an AI.

但之后，如果你想发布一些编辑过的图片，比如想把图片裁剪得更小

But later, if you want to publish some edited images, like, if you want to crop the image into a smaller one

嗯。

Mhmm.

你如何证明这张裁剪后的照片是来自这张经过签名的原图呢？

How do you prove that this crop photo is coming from this signed original photo?

对吧？

Right?

嗯。

Mhmm.

在这种情况下，提交和ProofSnark就非常有用。

In this case, commit and ProofSnark is really useful to do that.

你只需要证明这个在线见证（即裁剪后的照片）是之前提交的见证（即签名的原始照片）的有效转换。

What you do is just to prove that this online witness, which is this cropped photo, is a valid transformation of the previously committed witness, which is designed original photo.

而且你只需要证明这个转换过程。

And you only need to prove this transformation.

你不需要证明这个承诺的开放关系，而且你还有之前生成的针对该承诺的签名。

You don't have to prove this commitment opening relation, and you also have this signature for the commitment that has been generated previously.

这就是承诺和证明snarks的一个应用案例，我们发现实际上在我们的场景中它还有更多应用。

So this is one application of commitment and prove snarks, and we found that it actually have more application for that in our scenarios.

所以我们提出了一种新方法，利用提交和证明snark将以下方案转化为非交互式论证，而无需嵌入恐惧的shammy启发式算法。

So we come up with a new way to make use of commit and prove snark to turn the following scheme into a non interactive argument without embedding fear shammy heuristics.

是的。

Yeah.

立即就冒出几个问题，你们用的是哪种提交改进的SNARK？

A few questions come up immediately, which is which commit improved snark do you use?

比如，它是否也是后量子安全的？

Like, is that also gonna be post quantum?

接下来的问题是，如果我打算用SNARK来构建论证，那我何不从一开始就直接用SNARK作为论证呢？

And then the next question is, if I'm gonna use a snark to make a argument, you know, can't I just use the snark as my argument from from the beginning?

引入折叠技术后，我是否能获得效率提升？

Like, do I gain deficiency by introducing folding in there?

CP SNARK其实非常通用。

So the CP SNARK is quite general.

你可以选用任何CP SNARK，但只有与后量子安全的提交证明SNARK配合才具有可信度。

You can use any CP SNARK you want, but it is only plausible with Postcon secure commit and proof SNARK.

嗯。

Mhmm.

如果提交和证明SNARK本身不具备后量子安全性，这个编译器也不会具备后量子安全性。

If commit and proof SNARK itself is not postcon secure, this compiler will also not be postcom secure.

但它对于选择何种类型的提交和证明SNARK具有很大的通用性和灵活性。

But it does have a lot of generality and flexibility on what kind of commit and proof SNARK you can choose.

例如，你可以选择基于哈希的方案。

For example, you can choose hash based.

你也可以选择基于KZG、多项式或IOP的SNARK方案。

You can also choose KZG based, polynomial, IOP based SNARKs.

嗯。

Mhmm.

我们能否继续留在格密码领域，使用基于格的方案？

Can we stay in Lattice land and have a Lattice based one?

是的。

Yeah.

这这正是我想问的问题。

That that was gonna be my question.

我其实想问的是，这里是否还涉及到格密码相关的工作？

This I was kind of like, is there still Lattice work involved here?

格密码的工作主要是在折叠这一侧。

So the Lattice work mostly are in the folding side.

这个CP-SNARK，我们基本上是把它当作黑箱处理。

This CP SNARK, we kind of take it as black box.

如果我们有一个非常好的基于格密码的承诺和证明SNARK，我们也可以使用它。

If we have a really nice Lattice based commit and proof SNARK, we can also use that as well.

但目前大多数基于格密码的SNARK，它们的验证复杂度相当高。

But, currently, most of the Lattice based SNARKs, they have pretty expensive verification complexity.

这就是为什么目前我们更倾向于使用基于哈希或KZG的方案。

So that's why for now, we prefer to use hash based or KZG based schemes.

但如果出现更好的基于LAS的SNARK，我们也可以使用。

But if there are even better LAS based SNARC coming up, we can also use that as well.

第二个问题是什么来着？

And the second what is the second question?