Lookup Singularity
1. 引言
Lookup Singularity概念 由Barry WhiteHat在2022年11月在zkResearch论坛 Lookup Singularity中首次提出:
- 其主要目的是:让SNARK前端生成仅需做lookup的电路。
- Barry预测这样有很多好处,特别是对于可审计性 以及 形式化验证:
- 更易于审计单个lookup argument和各种lookup tables,不再需要数千行的硬编码电路。
- 承认现有的lookup argument方案具有性能瓶颈 但 预测将得到改进:
- 强调可能需要支持巨大table,如size为 2 128 2^{128} 2128的table。
- Lasso/Jolt可能可实现该愿景?
多年来,ZKP的核心元素为check:
- A ∗ B + D = = C A*B+D==C A∗B+D==C
在构建整个电路过程中,重复运用该check。将这种表示的电路称为R1CS。
但是,对于某些任务,R1CS昂贵得令人望而却步,为此,引入了lookup arguments的大量使用。当前,很多ZKP使用lookup argument + R1CS变种多项式承诺 来构建电路。
仅使用R1CS来构建电路存在一些障碍。为此,人们创建了一些hand tuned circuits,在这些hand tuned circuits中,同时包含了多项式约束和lookup arguments。这些hand tuned circuits是特定的,并不是很容易扩展。
1.1 多项式约束
多项式约束是复杂的。电路实现人员构建大量多项式方程式,整个电路定义为由多项式方程式组成的系统。
对这个“由多项式方程式组成的系统” 的solution,构成了a valid proof。很难对方程组的结果进行推理。目前的形式化验证工具无法求解素数域中的多项式方程。
1.2 Lookup argument
lookup argument为set membership check。lookup argument:
- 首次用于做高效的big integer arithmetic。
- 目前还用作VM的控制流
- 做某些不是snark-friendly的运算
- 并不是对所有运算都是更高效的
- 每个lookup会引入一定的prover开销
- 目前控制使用lookup argument的次数 的原因在于,其对Prover来说是昂贵的。
2. 为何Lookup arguments很好?
2.1 语言
当前的snark friendly语言对于新程序员来说是难学的。其使用了不同于之前范式的素数域和多项式约束。而仅使用lookup arguments的语言可能会更简单。当前的语言擅长做snarks定向计算,但当用于传统计算时要昂贵很多。
而仅有lookup的语言,将:
- 既擅长做snarks定向计算
- 也擅长做传统计算
2.2 安全审查
审计人员不再需要取对一组多项式方程式求解。lookup arguments推理起来要简单得多。
如:某电路具有一个ANDgate,有2个输入bit 变量,输出为这2个输入的AND运算结果。
多项式方案为:
(x)(x-1) = 0
y(y-1) = 0
x*y = out
return(out)
Lookup方案为:
out = get x,y from AND table
return(out)
其中AND lookup table为:
由此可知,Lookup方案要简单得多。因此,对于仅有lookup的电路,要更容易找出bug。
2.3 形式化验证
形式化验证工具需对一组多项式方程式求解。现有的形式化验证工具不擅长求解素数域中的多项式方程——这样会引入大量额外工作。
而仅使用lookup argument的话,则可使用现有的形式化验证工具,同时可能可探索一些其它方案。
lookup argument限制了电路中任意point的有限变量集合,使得可能的变量集合由 2 254 2^{254} 2254 限制为了 2 2 2或 2 16 2^{16} 216。这样甚至可支持做state space enumeration 来确认 “电路是正确的”。
2.4 信息论对比
为高效将程序描述为电路,需构建一个电路来将“某输入”映射为“正确的输出”。可将“电路”看成是“每个prover time second编码的信息”。这似乎是对比“实现电路的不同方式”的一种好角度。
多项式约束具有有限的degree:
- 因为degree会影响Prover time。
- degree会限制可编码的信息。
如degree为5的多项式可将5个输入值 映射为 5个输出值。除非增加degree,否则无法在该多项式中包含更多的值。
很多情况下,这样是ok的,因为是使用多项式约束的structure来做计算。因此,乘法运算对应为多项式运算 A ∗ B = = C A*B==C A∗B==C,而XOR运算不是,需要编码为keys to values。
Lookup argument可包含更多的信息。之前已限制lookup table size为 2 28 2^{28} 228个元素。但近期研究成果表明,circuit size仅受限于可灵活完成的最大trusted setup——会限制table_size。
Baloo: Nearly Optimal Lookup Arguments中指出:
- 单个多项式约束中可包含约 5 ∗ 2 254 5*2^{254} 5∗2254位信息。
- Lookup argument可包含 2 254 ∗ table_size 2^{254}*\text{table\_size} 2254∗table_size
当使用多项式约束的structure时,多项式约束是很有用的。但随着更大尺寸的table变得可行,这种优势将消失。
3. 结论
若可仅使用lookup argument来高效定义电路,则将由更简单的工具和电路。
这样,lookup argument 将总是比 多项式约束 效率更高。
未来将关注构建以lookup为中心的ZKP工具。
4. 展望
未来工作:
- 比较现有电路的效率
- 构建仅有lookup的语言示例
- 对不同lookup argument效率做对比,并预测改进空间。
- 寻找lookup argument优于(和劣于)多项式约束的实例:
- 寻找lookup argument 和 多项式约束 的worst case。
- 对现有电路进行benchmark,比对效率:
- lookup argument
- lookup + polynomial constraints
参考资料
[1] Lookup Singularity
[2] The lookup singularity - how zero-knowledge proofs can be made simpler and easier to review.
Justin Thaler系列博客
- SNARK Design
- Rollup项目的SNARK景观
- SNARK原理示例
- SNARK性能及安全——Prover篇
- SNARK性能及安全——Verifier篇
- sum-check protocol in zkproof
- sum-check protocol深入研究
- Lasso、Jolt 以及 Lookup Singularity——Part 1
- Lasso、Jolt 以及 Lookup Singularity——Part 2
lookup系列博客
- PLOOKUP
- PLOOKUP代码解析
- Efficient polynomial commitment schemes for multiple points and polynomials学习笔记
- PLONK + PLOOKUP
- PlonKup: Reconciling PlonK with plookup
- PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge 学习笔记
- Plonk代码解析
- RapidUp: Multi-Domain Permutation Protocol for Lookup Tables学习笔记
- Lookup argument总览
- Halo2 学习笔记——设计之Proving system之Lookup argument(1)
- 多变量lookup argument
- cq:fast lookup argument
- Lookup Argument性能优化——Caulk
- 2023年 ZK Hack以及ZK Summit 亮点记
- Research Day 2023:Succinct ZKP最新进展
- Lasso、Jolt 以及 Lookup Singularity——Part 1
- Lasso、Jolt 以及 Lookup Singularity——Part 2
相关文章:
Lookup Singularity
1. 引言 Lookup Singularity概念 由Barry WhiteHat在2022年11月在zkResearch论坛 Lookup Singularity中首次提出: 其主要目的是:让SNARK前端生成仅需做lookup的电路。Barry预测这样有很多好处,特别是对于可审计性 以及 形式化验证ÿ…...
idea 本地版本控制 local history
idea 本地版本控制 local history 如何打开 1 自定义快捷键 settings->keymap->搜索框输入 show history -》Add Keyboard Shortcut -》设置为 CtrlAltL 2 右键文件-》local history -》show history 新建文件 版本1,creating class com.geekmice…这个是初…...
【Freertos基础入门】深入浅出freertos互斥量
文章目录 前言一、互斥量是什么?二、互斥量的使用场景三、互斥量的使用1.创建 2.删除互斥量3.give和take四、示例代码总结 前言 FreeRTOS是一款开源的实时操作系统,提供了许多基本的内核对象,其中包括互斥锁(Mutex)。…...
皮爷咖啡基于亚马逊云科技的数据架构,加速数据治理进程
皮爷咖啡(Peet’s Coffee)是美国精品咖啡品牌,于2017年进入中国,为中国消费者带来传统经典咖啡饮品,并特别呈现更加丰富的品质咖啡饮品体验。通过深入应用亚马逊云科技云原生数据库产品Amazon Redshift以及Amazon DMS等…...
C++ string类详解
⭐️ string string 是表示字符串的字符串类,该类的接口与常规容器的接口基本一致,还有一些额外的操作 string 的常规操作,在使用 string 类时,需要使用 #include <string> 以及 using namespace std;。 ✨ 帮助文档&…...
深入浅出Pytorch函数——torch.nn.init.ones_
分类目录:《深入浅出Pytorch函数》总目录 相关文章: 深入浅出Pytorch函数——torch.nn.init.calculate_gain 深入浅出Pytorch函数——torch.nn.init.uniform_ 深入浅出Pytorch函数——torch.nn.init.normal_ 深入浅出Pytorch函数——torch.nn.init.c…...
一、docker及mysql基本语法
文章目录 一、docker相关命令二、mysql相关命令 一、docker相关命令 (1)拉取镜像:docker pull <镜像ID/image> (2)查看当前docker中的镜像:docker images (3)删除镜像&#x…...
【计算机网络】13、ARP 包:广播自己的 mac 地址和 ip
机器启动时,会向外广播自己的 mac 地址和 ip 地址,这个即称为 arp 协议。范围是未经过路由器的部分,如下图的蓝色部分,范围内的设备都会在本地记录 mac 和 ip 的绑定信息,若有重复则覆盖更新(例如先收到 ma…...
通过微软Azure调用GPT的接口API-兼容平替OpenAI官方的注意事项
众所周知,我们是访问不通OpenAI官方服务的,但是我们可以自己通过代理或者使用第三方代理访问接口 现在新出台的规定禁止使用境外的AI大模型接口对境内客户使用,所以我们需要使用国内的大模型接口 国内的效果真的很差,现在如果想使…...
回归预测 | MATLAB实现BO-SVM贝叶斯优化支持向量机多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现BO-SVM贝叶斯优化支持向量机多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现BO-SVM贝叶斯优化支持向量机多输入单输出回归预测(多指标,多图)效果一览基本介绍程序设计…...
GAN!生成对抗网络GAN全维度介绍与实战
目录 一、引言1.1 生成对抗网络简介1.2 应用领域概览1.3 GAN的重要性 二、理论基础2.1 生成对抗网络的工作原理2.1.1 生成器生成过程 2.1.2 判别器判别过程 2.1.3 训练过程训练代码示例 2.1.4 平衡与收敛 2.2 数学背景2.2.1 损失函数生成器损失判别器损失 2.2.2 优化方法优化代…...
自动驾驶仿真:基于Carsim开发的加速度请求模型
文章目录 前言一、加速度输出变量问题澄清二、配置Carsim动力学模型三、配置Carsim驾驶员模型四、添加VS Command代码五、Run Control联合仿真六、加速度模型效果验证 前言 1、自动驾驶行业中,算法端对于纵向控制的功能预留接口基本都是加速度,我们需要…...
.netcore grpc客户端工厂及依赖注入使用
一、客户端工厂概述 gRPC 与 HttpClientFactory 的集成提供了一种创建 gRPC 客户端的集中方式。可以通过依赖包Grpc.Net.ClientFactory中的AddGrpcClient进行gRPC客户端依赖注入AddGrpcClient函数提供了许多配置项用于处理一些其他事项;例如AOP、重试策略等 二、案…...
C语言入门_Day7 逻辑运算
目录: 前言 1.逻辑运算 2.优先级 3.易错点 4.思维导图 前言 算术运算用来进行数据的计算和处理;比较运算是用来比较不同的数据,进而来决定下一步怎么做;除此以外还有一种运算叫做逻辑运算,它的应用场景也是用来影…...
什么是Eureka?以及Eureka注册服务的搭建
导包 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 htt…...
Docker安装并配置镜像加速器,镜像、容器的基本操作
目录 1.安装docker服务,配置镜像加速器 (1)安装依赖的软件包 (2)设置yum源,我配置的阿里仓库 (3)选择一个版本安装 (4)启动docker服务,并设置…...
前端 -- 基础 网页、HTML、 WEB标准 扫盲详解
什么是网页 : 网页是构成网站的基本元素,它通常由 图片、链接、文字、声音、视频等元素组成。 通常我们看到的网页 ,常见以 .html 或 .htm 后缀结尾的文件, 因此俗称 HTML 文件 什么是 HTML : HTML 指的是 超文本标记语言,…...
分布式锁实现方式
分布式锁 1 分布式锁介绍 1.1 什么是分布式 一个大型的系统往往被分为几个子系统来做,一个子系统可以部署在一台机器的多个 JVM(java虚拟机) 上,也可以部署在多台机器上。但是每一个系统不是独立的,不是完全独立的。需要相互通信ÿ…...
C语言小练习(一)
🌞 “人生是用来体验的,不是用来绎示完美的,接受迟钝和平庸,允许出错,允许自己偶尔断电,带着遗憾,拼命绽放,这是与自己达成和解的唯一办法。放下焦虑,和不完美的自己和解…...
Flask-flask系统运行后台轮询线程
对于有些flask系统,后台需要启动轮询线程,执行特定的任务,以下是一个简单的例子。 globals/daemon.py import threading from app.executor.ops_service import find_and_run_ops_task_todo_in_redisdef context_run_func(app, func):with …...
jsp本质-servlet
jsp本质-servlet 一、jsp文件 <% page language"java" contentType"text/html; charsetUTF-8" pageEncoding"UTF-8"%> <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>JSP Example…...
回归预测 | MATLAB实现GWO-SVM灰狼优化算法优化支持向量机多输入单输出回归预测(多指标,多图)
回归预测 | MATLAB实现GWO-SVM灰狼优化算法优化支持向量机多输入单输出回归预测(多指标,多图) 目录 回归预测 | MATLAB实现GWO-SVM灰狼优化算法优化支持向量机多输入单输出回归预测(多指标,多图)效果一览基…...
科技资讯|苹果Vision Pro新专利曝光:可调节液态透镜
苹果公司近日申请了名为“带液态镜头的电子设备”,概述了未来可能的头显设计。头显设备中的透镜采用可调节的液态透镜,每个透镜可以具有填充有液体的透镜腔,透镜室可以具有形成光学透镜表面的刚性和 / 或柔性壁。 包括苹果自家的 Vision Pr…...
神经网络基础-神经网络补充概念-38-归一化输入
概念 归一化输入是一种常见的数据预处理技术,旨在将不同特征的取值范围映射到相似的尺度,从而帮助优化机器学习模型的训练过程。归一化可以提高模型的收敛速度、稳定性和泛化能力,减少模型受到不同特征尺度影响的情况。 常见的归一化方法 …...
【Redis】什么是缓存雪崩,如何预防缓存雪崩?
【Redis】什么是缓存雪崩,如何预防缓存雪崩? 如果缓存集中在一段时间内失效,也就是通常所说的热点数据集中失效 (一般都会给缓存设定一个失效时间,过了失效时间后,该数据库会被缓存直接删除,从…...
[国产MCU]-W801开发实例-开发环境搭建
W801开发环境搭建 文章目录 W801开发环境搭建1、W801芯片介绍2、W801芯片特性3、W801芯片结构4、开发环境搭建1、W801芯片介绍 W801芯片是联盛德微电子推出的一款高性价比物联网芯片。 W801 芯片是一款安全 IoT Wi-Fi/蓝牙 双模 SoC芯片。芯片提供丰富的数字功能接口。支持2.…...
区间预测 | MATLAB实现QRGRU门控循环单元分位数回归时间序列区间预测
区间预测 | MATLAB实现QRGRU门控循环单元分位数回归时间序列区间预测 目录 区间预测 | MATLAB实现QRGRU门控循环单元分位数回归时间序列区间预测效果一览基本介绍模型描述程序设计参考资料 效果一览 基本介绍 MATLAB实现QRGRU门控循环单元分位数回归时间序列区间预测。基于分位…...
改善神经网络——优化算法(mini-batch、动量梯度下降法、Adam优化算法)
改善神经网络——优化算法 梯度下降Mini-batch 梯度下降(Mini-batch Gradient Descent)指数加权平均包含动量的梯度下降RMSprop算法Adam算法 优化算法可以使神经网络运行的更快,机器学习的应用是一个高度依赖经验的过程,伴随着大量…...
大数据面试题:Spark的任务执行流程
面试题来源: 《大数据面试题 V4.0》 大数据面试题V3.0,523道题,679页,46w字 可回答:1)Spark的工作流程?2)Spark的调度流程;3)Spark的任务调度原理…...
通过 Amazon SageMaker JumpStart 部署 Llama 2 快速构建专属 LLM 应用
来自 Meta 的 Llama 2 基础模型现已在 Amazon SageMaker JumpStart 中提供。我们可以通过使用 Amazon SageMaker JumpStart 快速部署 Llama 2 模型,并且结合开源 UI 工具 Gradio 打造专属 LLM 应用。 Llama 2 简介 Llama 2 是使用优化的 Transformer 架构的自回归语…...
ansible远程执行命令
一、ansible简介 需要在一台机器上搭建ansible环境,且配置目的ip的密码,通道没有问题即可下发命令 使用的通道是ssh(端口:36000) 二、搭建细节 1、安装ansible yum install -y ansible 2、把目的ip密码写到配置…...
Windows快速恢复丢失的颜色校准
场景 有时开机或启动某个软件后,颜色校准(设置项:校准显示器颜色)会丢失,每次重新设置很麻烦。 文章首发及后续更新:https://mwhls.top/4723.html,无图/无目录/格式错误/更多相关请至首发页查看…...
Vue安装单文件组件
安装 npm npm 全称为 Node Package Manager,是一个基于Node.js的包管理器,也是整个Node.js社区最流行、支持的第三方模块最多的包管理器。 npm -v由于网络原因 安装 cnpm npm install -g cnpm --registryhttps://registry.npm.taobao.org安装 vue-cli…...
小白的Node.js学习笔记大全---不定期更新
Node.js是什么 Node. js 是一个基于 Chrome v8 引擎的服务器端 JavaScript 运行环境Node. js 是一个事件驱动、非阻塞式I/O 的模型,轻量而又高效Node. js 的包管理器 npm 是全球最大的开源库生态系统 特性 单一线程 Node.js 沿用了 JavaScript 单一线程的执行特…...
第二周晨考自测(2.0)
1.冒泡排序 冒泡排序是数组解构中的常见排序算法之一。规则如下:先遍历数组,让相邻的两个数据进行比较,如果前一个比后一个大,那么就把这两个数据交换位置,经过一轮遍历之后,最大的那个数字就排在数组最后…...
计算机视觉之三维重建(三)(单视图测量)
2D变换 等距变换 旋转平移保留形状、面积通常描述刚性物体运动 相似变换 在等距变换的基础增加缩放特点 射影变换 共线性、四共线点的交比保持不变 仿射变换 面积比值、平行关系等不变仿射变换是特殊的射影变换 影消点与影消线 2D无穷远点 两直线的交点可由两直线的…...
docker 批量快速删除容器和镜像
一、批量删除镜像 如果你想要批量删除 Docker 镜像,可以使用各种命令。以下是一些示例: 1. 删除所有镜像: docker rmi $(docker images -q) 2. 删除所有未标记的镜像(即 <none> 镜像): docker rmi $(docker images -f "dangling=true" -q) 请注意…...
【数据分析入门】Matplotlib
目录 零、图形解析与工作流0.1 图形解析0.2 工作流 一、准备数据1.1 一维数据1.2 二维数据或图片 二、绘制图形2.1 画布2.2 坐标轴 三、绘图例程3.1 一维数据3.2 向量场3.3 数据分布3.4 二维数据或图片 四、自定义图形4.1 颜色、色条与色彩表4.2 标记4.3 线型4.4 文本与标注4.5…...
mongodb.使用自带命令工具导出导入数据
在一次数据更新中,同事把老数据进行了清空操作,但是新的逻辑数据由于某种原因(好像是她的电脑中病毒了),一直无法正常连接数据库进行数据插入,然后下午2点左右要给甲方演示,所以要紧急恢复本地的…...
IndexError: tensors used as indices must be long, byte or bool tensors
运行出现报错。修改数据格式 输出sample_ids的值,可以看到数据类型是 torch.int32 解决 需要将sample_ids类型转为long,修改方式: idx idx.type(torch.long)或 idx self.tensor(idx, dtypetorch.long)参考: IndexError: tenso…...
设计模式 : 单例模式笔记
文章目录 一.单例模式二.单例模式的两种实现方式饿汉模式懒汉模式 一.单例模式 一个类只能创建一个对象,这样的类的设计模式就称为单例模式,该模式保证系统中该类只能有一个实例(并且父子进程共享),一个很典型的单例类就是CSTL的内存池C单例模式的基本设计思路: 私有化构造函数…...
深度优先搜索算法
目录 4.1 二叉树的最大深度(简单):深度优先搜索 4.2 对称二叉树(简单):递归 4.3 岛屿数量(中等):深度优先搜索 4.4 岛屿的最大面积(中等)&…...
k8s ----POD控制器详解
目录 一:pod控制器 1、Pod控制器及其功用 2、pod控制器类型 3、Pod与控制器之间的关系 二:Deployment 三:SatefulSet 1、StatefulSet组成 2、为什么要有headless? 3、为什么要有volumeClaimTemplate? 4、实现…...
ReactNative进阶(三十四):ipa Archive 阶段报错error: Multiple commands produce问题修复及思考
文章目录 一、前言二、问题描述三、问题解决四、拓展阅读五、拓展阅读 一、前言 在应用RN开发跨平台APP阶段,从git中拉取项目,应用Jenkins进行组包时,发现最终生成的ipa安装包版本号始终与项目中设置的版本号不一致。 二、问题描述 经过仔…...
MySQL索引ES索引
MySQL MySQL索引的种类 按照索引列值的唯一性:索引可分为唯一索引和非唯一索引; 唯一索引:此索引的每一个索引值只对应唯一的数据记录,对于单列唯一性索引,这保证单列不包含重复的值。对于多列唯一性索引,保证多个值的组合不重复。主键索引是唯一索引的特定类型。该索引…...
webSocket 聊天室 node.js 版
全局安装vue脚手架 npm install vue/cli -g 创建 vue3 ts 脚手架 vue create vue3-chatroom 后端代码 src 同级目录下建 server: const express require(express); const app express(); const http require(http); const server http.createServer(app);const io req…...
iptables防火墙(SNAT与DNAT)
目录 1 SNAT 1.1 SNAT原理与应用 1.2 SNAT工作原理 1.3 SNAT转换前提条件 2 SNAT示例 编辑 2.1 网关服务器配置 2.1.1 网关服务器配置网卡 2.1.2 开启SNAT命令 2.2 内网服务器端配置 2.3 外网服务器端配置 2.4 网卡服务器端添加规则 2.5 SNAT 测试 3 DNAT 3.1 网卡…...
第 359 场 LeetCode 周赛题解
A 判别首字母缩略词 签到题… class Solution { public:bool isAcronym(vector<string> &words, string s) {string pf;for (auto &s: words)pf.push_back(s[0]);return pf s;} };B k-avoiding 数组的最小总和 贪心:从 1 1 1开始升序枚举,…...
【开源项目】Stream-Query的入门使用和原理分析
前言 无意间发现了一个有趣的项目,Stream-Query。了解了一下其基本的功能,可以帮助开发者省去Mapper的编写。在开发中,我们会编写entity和mapper来完成业务代码,但是Stream-Query可以省去mapper,只写entity。 快速入…...
微信小程序picker组件的简单使用 单选
<picker mode"selector" range"{{classData}}" bindchange"bindClassChange" value"{{classIndex}}" range-key"className"><view class"picker">{{classData[classIndex].className || 请选择班级}}…...