Kurt PanzkREPL：一个zkSNARKs 在线开发环境
作者：Kevin Kwok 译者：Kurt Pan 原文链接：https://0xparc.org/blog/zkrepl在计算的旧石器时代，计算机曾是机电的巨兽，每秒只可以执行几十次操作，但每年的成本却高达数百万美元。程序是通过细致的思考、在接线板中插入电线以及给卡片打孔来开发的。那个时候，bug就是是字面意义上的虫子，它们会啃咬电线，偶尔会导致短路，这可能会烧毁所有东西。 那时，对计算机进行编程是一项充满仪式感的艰苦的活动。但在 1950 年代后期，一种名为 LISP 的新编程系统被发明出来，它能够对其自己的实现进行推理——通过一个名为eval的结构，程序可以要求它们自己的制造者来产生新的程序。基于此，研究者提出了一个简单的程序，该程序将从键盘读取一些输入，将其发送到eval 结构，打印结果，然后循环回到起点以等待进一步的输入。 这个巧妙的技巧 ，REPL（译者注：读取﹣求值﹣输出循环）， 引发了编程的民主化进程——把编程从一个仅由民族国家用来操控火箭的东西，变成了一个青少年用来制作游戏的东西。零知识近年来，我们见证了一个计算的新时代的兴起。我们有像以太坊和比特币这样的区块链...
Kurt Pan公链隐私探索
原文：https://wdai.us/posts/navigating-privacy/ 作者：Wei Dai 翻译：Kurt Pan此文是对公链（又名去中心化账本、Crypto和 Web3）场景下隐私方面的阐述。第一部分会涉及为什么隐私是大规模采用的关键障碍以及隐私有哪些不同方面。第二部分综述了达成隐私的三种不同方法：通过零知识证明，通过仅以匿名为目标，以及通过一种新的称为 MOCCA 抽象。第一部分：什么是公链隐私以及为什么隐私——大规模采用的最后障碍现代金融系统运行良好，我们不必担心日常交易的安全性或隐私性。当你在杂货店购物、通过支票支付租金或在银行获取短期贷款时，你不必担心你的交易会受到非相关方的公开审查。在现代银行和信用卡网络中，大部分交易细节保留在相关金融中介和机构内部。理想情况下，用户不必担心他们的敏感信息会被泄露给大众，同时当局也几乎可以追踪那些非法活动。 不幸的是，目前在流行的区块链上进行的交易并非可以做到如此程度。尽管区块链技术允诺使当前的金融生态去中心化和民主化，但大多数系统甚至无法达到我们所期望的最基本的隐私级别。你买的披萨🍕会被永久记录，你所有的交易都...
Kurt Pan什么是ZEXE ？
原文：Anthony Matlala 翻译：Kurt Pan自加密货币出现，分布式账本系统变得流行起来。典型的分布式账本方案建立在区块链技术上，其特点是特定的数据结构，以区块的形式保存交易信息的记录。这些数据块通过称为哈希的密码学计算数“链接”或连在一起，并且该哈希值唯一地标识给定块。 尽管越来越受欢迎，分布式账本系统方案通常只提供有限的隐私。此外，确实提供隐私的方案通常在其支持的程序的表达能力方面受到限制。 正是这个问题促使隐私研究人员（包括几位 ZCash 创始科学家）提出了一个他们称为 ZEXE或零知识执行的方案。ZEXE 是第一个基于账本的方案，在该方案中应用程序可以在无信任、私密和可扩展的情况下执行。 虽然 Aleo 是由 ZEXE 的几位作者创立的，并且该研究是其计算模型的关键部分，但 Aleo 不仅仅是 ZEXE，其额外提供了用于编写私有应用程序的完整系列方法。 尽管如此，ZEXE 是 Aleo 中的核心组件。然而在研究圈之外，它仍然相对不为人知。本系列文章的目的是提供 ZEXE 设计策略背后的额外背景、它支持的功能以及可以使用它构建的真实世界应用的描述。预...
Kurt PanzkREPL：一个zkSNARKs 在线开发环境
作者：Kevin Kwok 译者：Kurt Pan 原文链接：https://0xparc.org/blog/zkrepl在计算的旧石器时代，计算机曾是机电的巨兽，每秒只可以执行几十次操作，但每年的成本却高达数百万美元。程序是通过细致的思考、在接线板中插入电线以及给卡片打孔来开发的。那个时候，bug就是是字面意义上的虫子，它们会啃咬电线，偶尔会导致短路，这可能会烧毁所有东西。 那时，对计算机进行编程是一项充满仪式感的艰苦的活动。但在 1950 年代后期，一种名为 LISP 的新编程系统被发明出来，它能够对其自己的实现进行推理——通过一个名为eval的结构，程序可以要求它们自己的制造者来产生新的程序。基于此，研究者提出了一个简单的程序，该程序将从键盘读取一些输入，将其发送到eval 结构，打印结果，然后循环回到起点以等待进一步的输入。 这个巧妙的技巧 ，REPL（译者注：读取﹣求值﹣输出循环）， 引发了编程的民主化进程——把编程从一个仅由民族国家用来操控火箭的东西，变成了一个青少年用来制作游戏的东西。零知识近年来，我们见证了一个计算的新时代的兴起。我们有像以太坊和比特币这样的区块链...
Kurt Pan公链隐私探索
原文：https://wdai.us/posts/navigating-privacy/ 作者：Wei Dai 翻译：Kurt Pan此文是对公链（又名去中心化账本、Crypto和 Web3）场景下隐私方面的阐述。第一部分会涉及为什么隐私是大规模采用的关键障碍以及隐私有哪些不同方面。第二部分综述了达成隐私的三种不同方法：通过零知识证明，通过仅以匿名为目标，以及通过一种新的称为 MOCCA 抽象。第一部分：什么是公链隐私以及为什么隐私——大规模采用的最后障碍现代金融系统运行良好，我们不必担心日常交易的安全性或隐私性。当你在杂货店购物、通过支票支付租金或在银行获取短期贷款时，你不必担心你的交易会受到非相关方的公开审查。在现代银行和信用卡网络中，大部分交易细节保留在相关金融中介和机构内部。理想情况下，用户不必担心他们的敏感信息会被泄露给大众，同时当局也几乎可以追踪那些非法活动。 不幸的是，目前在流行的区块链上进行的交易并非可以做到如此程度。尽管区块链技术允诺使当前的金融生态去中心化和民主化，但大多数系统甚至无法达到我们所期望的最基本的隐私级别。你买的披萨🍕会被永久记录，你所有的交易都...
Kurt Pan什么是ZEXE ？
原文：Anthony Matlala 翻译：Kurt Pan自加密货币出现，分布式账本系统变得流行起来。典型的分布式账本方案建立在区块链技术上，其特点是特定的数据结构，以区块的形式保存交易信息的记录。这些数据块通过称为哈希的密码学计算数“链接”或连在一起，并且该哈希值唯一地标识给定块。 尽管越来越受欢迎，分布式账本系统方案通常只提供有限的隐私。此外，确实提供隐私的方案通常在其支持的程序的表达能力方面受到限制。 正是这个问题促使隐私研究人员（包括几位 ZCash 创始科学家）提出了一个他们称为 ZEXE或零知识执行的方案。ZEXE 是第一个基于账本的方案，在该方案中应用程序可以在无信任、私密和可扩展的情况下执行。 虽然 Aleo 是由 ZEXE 的几位作者创立的，并且该研究是其计算模型的关键部分，但 Aleo 不仅仅是 ZEXE，其额外提供了用于编写私有应用程序的完整系列方法。 尽管如此，ZEXE 是 Aleo 中的核心组件。然而在研究圈之外，它仍然相对不为人知。本系列文章的目的是提供 ZEXE 设计策略背后的额外背景、它支持的功能以及可以使用它构建的真实世界应用的描述。预...
Subscribe to Kurt Pan
Subscribe to Kurt Pan
Share Dialog
Share Dialog
<100 subscribers
<100 subscribers
王垠写于2019年7月的这篇博文的背景是在网上闹得沸沸扬扬的阿里巴巴赵海平面试王垠导致的论战。回过头看看这个时间点（2019年7到12月），这不就是划时代的COVID-19在武汉隐匿传播的时间嘛，王垠在文中的核心论点在于"P vs NP问题没有实际意义“。从时间点的魔幻性看待这篇文章，那王垠说的是对的，全世界在19年下半年最重要的事应该是正视这个病毒，而不是关心P vs NP问题，否则就是Don't Look Up的鸵鸟。但时过境迁，"the world has changed."，女王和“昨日世界”一起彻底的逝去了。但是P vs NP问题，一个来自半个世纪前的“可能是位居理论计算机核心的未解决问题”，却依然是一个深刻的迷，还没有看到任何被满意解决的进展。
王垠为了得出”P vs NP无用“这个结论给出了三个论点，这也是任何严肃看待P vs NP问题的人都值得去认真思考的几个点。我们一个一个来看：
“多项式时间”这个概念太宽泛太笼统。
这是对复杂性类P本身现实意义的常见质疑，在所有的计算复杂性理论的教材中都会有专门的一节来对此进行讨论。这个质疑出现于对于整个算法分析理论的质疑的方方面面，包括对于大O表示法的质疑，对于渐进分析忽略了典型的输入规模的质疑等等。
如果你问，有多少问题可以在一百万步内或者可以借助32GB内存计算出来？无疑你没有问对问题。基于此你提出的关于计算的理论将受制于所选的模型。不同的CPU架构，不同代际不同型号的产品都会影响最终的结论。换句话说，你根本不是在做理论计算机科学研究，而是在做系统架构设计。
如果你问一个更宽泛的问题“有多少问题可以在随问题规模f(n)增长的时间内算出来？”，那么你已经从具体分析进展到了渐进分析(asymptotic analysis) 的领域了。基于此，很明显至少常数因子你可以忽略不计了，你不用再关心具体计算机的型号了。
更进一步，当我们想要定义简单的、可行的、实用的、高效的计算这一大类时，如果再去区分O(n^2)和O(n^3)显然是不合适的，难道存在二次方算法就高效三次方算法就不高效吗？（这里是一般讨论，不是在说矩阵乘法这种特定问题。）从模型健壮性的方面考虑，我们采取更粗放的观点进行抽象，只区分多项式时间和指数时间，任何多项式时间的上界都是“快的”，任何指数上界都是“慢的”。根据这个区分，一个问题是简单的还是困难的，只要是用和图灵机差不多的计算模型，比如串行的确定性的经典的计算机，而非量子计算机或其他类似的东西，其分类是稳定的不会变化的。这就是抽象化带来的模型的健壮性。模型如果不够健壮，必然会削弱使用这个模型的可靠性和泛用性。
其实对于“多项式时间”这个概念以及相对应的复杂性类P的提出，是有一个专门的名词的，叫Cobham-Edmonds论题：就是说用P来定义高效计算是正确合理的抽象。
你可能还会说：“那万一一个问题能在多项式时间内解决，但是这个多项式是n^999999;一个问题需要指数时间解决，但是这个指数是1.00000001^n。高效性能这么分类吗？“
针对这点质疑，我想指出：在目前的实践中，从未出现过这样的情况。对于在多项式时间内可解的自然问题（匹配、线性规划、素数判定等），都确实存在高效的算法，几乎没有任何一个自然的问题算法的多项式上面的次数会大于3或4。而对于我们认为需要指数时间解决的自然问题（定理证明、电路最小化等），它们大多数真的没有实用的算法。因此，实践经验支撑了我们的抽象划分。
我们看第二个论点：
“P vs NP” 这个问题的定义，是基于一个完全假想的机器——非确定性图灵机。 NP 这个概念其实是在故弄玄虚。
在新一点的教材中，介绍NP问题多数会采用如下多项式时间可验证的定义：
NP是这样一类问题：如果其输出为“Yes”，那么存在一个多项式大小的证明，证明你可以在多项式时间内对此加以验证。
只用确定性图灵机定义NP问题，而把涉及非确定性图灵机的定义作为一个等价的历史定义。这说明非确定性图灵机这个计算模型并非该定义的核心本质。故而非确定性图灵机的“假想性”并非可以成为NP这个概念“故弄玄虚”的理由。
数理逻辑和理论计算机学术界从来没有将问题“现实无用”作为问题低价值从而不去研究的理由，你根本无法据此对之进行质疑，其固有价值是抵抗此类质疑的攻击的。就好比你无法去责备林黛玉搬不动砖一样，林黛玉的价值并不在此。这是NP并非“故弄玄虚”的另一个理由。类似的是密码学中的Random Oracle模型，这个东西现实中一定是不存在的，因为全宇宙作为内存都不够用，但是其不存在性依然不影响ROM成为密码方案的构造和安全性分析中的重要启发式模型。
王垠本人属于“尊邱贬图”派，在计算模型上推崇更符号化的lambda演算而非更机械化的图灵机，这是可以理解的。但是哪怕是lambda演算的计算模型上，计算的高效可验证性依然是重要的性质，这是计算模型独立的。
再来看最后一个论点：
“P vs NP”关心的只是“最坏情况”，而最坏情况也许非常罕见。
这个点我认为是最有讨论意义的，和密码学有着深刻的关联，同时也是当前计算复杂性理论研究的核心，涉及平均情况困难性，细粒度复杂度等研究方向。（去追寻青年华人理论计算机科学家陈立杰老师的光吧少年！）
有一个关于密码学的常见问题是：“基于最弱的P不等于NP假设，能否构造出安全的加密方案？”答案是不可能，如果“安全”是遵从标准严格的定义的话。假设我构造出了一个密码系统，我说这个系统会存在一条很难破译的消息。仅仅依赖P不等于NP假设就会构造出这样的加密系统，这必然是不可用的，因为谁知道其他消息用这个加密难不难呢，如果是只存在一条很难破译的，其他都很简单破译的，这就尴尬了。所以在密码学中，一个NP问题在最坏情况下很难是不够的，我们需要的是平均情况下很难的NP问题。（背包密码的攻破和此有关。）事实上，哪怕是假设存在平均情况下困难的问题对于密码学依然是不够的，单向函数（OWF）的存在性是必要的。
考虑最短向量（SVP）问题，即将格L中的最短非零向量的长度近似到某个乘法因子k内。SVP问题是少数几个我们能证明其最坏情况和平均情况等价的问题，即平均情况下与在最坏情况下一样难。基于这一等价性，Ajtai/Dwork/Regev等人构造出了安全性完全依赖于SVP在最坏情况下的困难性的格密码系统，往“基于NPC问题构造加密算法“这个目标前进了一大步。（依然没有完成，因为近似因子k的不匹配。）
以上就是我对这几个论点的简要讨论，有很多值得展开的，我们后续再聊。
王垠写于2019年7月的这篇博文的背景是在网上闹得沸沸扬扬的阿里巴巴赵海平面试王垠导致的论战。回过头看看这个时间点（2019年7到12月），这不就是划时代的COVID-19在武汉隐匿传播的时间嘛，王垠在文中的核心论点在于"P vs NP问题没有实际意义“。从时间点的魔幻性看待这篇文章，那王垠说的是对的，全世界在19年下半年最重要的事应该是正视这个病毒，而不是关心P vs NP问题，否则就是Don't Look Up的鸵鸟。但时过境迁，"the world has changed."，女王和“昨日世界”一起彻底的逝去了。但是P vs NP问题，一个来自半个世纪前的“可能是位居理论计算机核心的未解决问题”，却依然是一个深刻的迷，还没有看到任何被满意解决的进展。
王垠为了得出”P vs NP无用“这个结论给出了三个论点，这也是任何严肃看待P vs NP问题的人都值得去认真思考的几个点。我们一个一个来看：
“多项式时间”这个概念太宽泛太笼统。
这是对复杂性类P本身现实意义的常见质疑，在所有的计算复杂性理论的教材中都会有专门的一节来对此进行讨论。这个质疑出现于对于整个算法分析理论的质疑的方方面面，包括对于大O表示法的质疑，对于渐进分析忽略了典型的输入规模的质疑等等。
如果你问，有多少问题可以在一百万步内或者可以借助32GB内存计算出来？无疑你没有问对问题。基于此你提出的关于计算的理论将受制于所选的模型。不同的CPU架构，不同代际不同型号的产品都会影响最终的结论。换句话说，你根本不是在做理论计算机科学研究，而是在做系统架构设计。
如果你问一个更宽泛的问题“有多少问题可以在随问题规模f(n)增长的时间内算出来？”，那么你已经从具体分析进展到了渐进分析(asymptotic analysis) 的领域了。基于此，很明显至少常数因子你可以忽略不计了，你不用再关心具体计算机的型号了。
更进一步，当我们想要定义简单的、可行的、实用的、高效的计算这一大类时，如果再去区分O(n^2)和O(n^3)显然是不合适的，难道存在二次方算法就高效三次方算法就不高效吗？（这里是一般讨论，不是在说矩阵乘法这种特定问题。）从模型健壮性的方面考虑，我们采取更粗放的观点进行抽象，只区分多项式时间和指数时间，任何多项式时间的上界都是“快的”，任何指数上界都是“慢的”。根据这个区分，一个问题是简单的还是困难的，只要是用和图灵机差不多的计算模型，比如串行的确定性的经典的计算机，而非量子计算机或其他类似的东西，其分类是稳定的不会变化的。这就是抽象化带来的模型的健壮性。模型如果不够健壮，必然会削弱使用这个模型的可靠性和泛用性。
其实对于“多项式时间”这个概念以及相对应的复杂性类P的提出，是有一个专门的名词的，叫Cobham-Edmonds论题：就是说用P来定义高效计算是正确合理的抽象。
你可能还会说：“那万一一个问题能在多项式时间内解决，但是这个多项式是n^999999;一个问题需要指数时间解决，但是这个指数是1.00000001^n。高效性能这么分类吗？“
针对这点质疑，我想指出：在目前的实践中，从未出现过这样的情况。对于在多项式时间内可解的自然问题（匹配、线性规划、素数判定等），都确实存在高效的算法，几乎没有任何一个自然的问题算法的多项式上面的次数会大于3或4。而对于我们认为需要指数时间解决的自然问题（定理证明、电路最小化等），它们大多数真的没有实用的算法。因此，实践经验支撑了我们的抽象划分。
我们看第二个论点：
“P vs NP” 这个问题的定义，是基于一个完全假想的机器——非确定性图灵机。 NP 这个概念其实是在故弄玄虚。
在新一点的教材中，介绍NP问题多数会采用如下多项式时间可验证的定义：
NP是这样一类问题：如果其输出为“Yes”，那么存在一个多项式大小的证明，证明你可以在多项式时间内对此加以验证。
只用确定性图灵机定义NP问题，而把涉及非确定性图灵机的定义作为一个等价的历史定义。这说明非确定性图灵机这个计算模型并非该定义的核心本质。故而非确定性图灵机的“假想性”并非可以成为NP这个概念“故弄玄虚”的理由。
数理逻辑和理论计算机学术界从来没有将问题“现实无用”作为问题低价值从而不去研究的理由，你根本无法据此对之进行质疑，其固有价值是抵抗此类质疑的攻击的。就好比你无法去责备林黛玉搬不动砖一样，林黛玉的价值并不在此。这是NP并非“故弄玄虚”的另一个理由。类似的是密码学中的Random Oracle模型，这个东西现实中一定是不存在的，因为全宇宙作为内存都不够用，但是其不存在性依然不影响ROM成为密码方案的构造和安全性分析中的重要启发式模型。
王垠本人属于“尊邱贬图”派，在计算模型上推崇更符号化的lambda演算而非更机械化的图灵机，这是可以理解的。但是哪怕是lambda演算的计算模型上，计算的高效可验证性依然是重要的性质，这是计算模型独立的。
再来看最后一个论点：
“P vs NP”关心的只是“最坏情况”，而最坏情况也许非常罕见。
这个点我认为是最有讨论意义的，和密码学有着深刻的关联，同时也是当前计算复杂性理论研究的核心，涉及平均情况困难性，细粒度复杂度等研究方向。（去追寻青年华人理论计算机科学家陈立杰老师的光吧少年！）
有一个关于密码学的常见问题是：“基于最弱的P不等于NP假设，能否构造出安全的加密方案？”答案是不可能，如果“安全”是遵从标准严格的定义的话。假设我构造出了一个密码系统，我说这个系统会存在一条很难破译的消息。仅仅依赖P不等于NP假设就会构造出这样的加密系统，这必然是不可用的，因为谁知道其他消息用这个加密难不难呢，如果是只存在一条很难破译的，其他都很简单破译的，这就尴尬了。所以在密码学中，一个NP问题在最坏情况下很难是不够的，我们需要的是平均情况下很难的NP问题。（背包密码的攻破和此有关。）事实上，哪怕是假设存在平均情况下困难的问题对于密码学依然是不够的，单向函数（OWF）的存在性是必要的。
考虑最短向量（SVP）问题，即将格L中的最短非零向量的长度近似到某个乘法因子k内。SVP问题是少数几个我们能证明其最坏情况和平均情况等价的问题，即平均情况下与在最坏情况下一样难。基于这一等价性，Ajtai/Dwork/Regev等人构造出了安全性完全依赖于SVP在最坏情况下的困难性的格密码系统，往“基于NPC问题构造加密算法“这个目标前进了一大步。（依然没有完成，因为近似因子k的不匹配。）
以上就是我对这几个论点的简要讨论，有很多值得展开的，我们后续再聊。
No activity yet