Move Prover 多态与单态化编码基准测试基于 prover-lab 的后端验证性能对比实验指南【免费下载链接】aptos-coreAptos is a layer 1 blockchain built to support the widespread use of blockchain through better technology and user experience.项目地址: https://gitcode.com/GitHub_Trending/ap/aptos-core本篇文章围绕 Move Prover 实验套件 prover-lab 中的mono实验见 README系统讲解 Move Prover 两种 Boogie 后端的编码策略——传统多态polymorphic编码与单态化monomorphic编码的核心差异、基准测试的完整复现流程、数据文件与图表解读方法并结合当前仓库源码说明单态化分析的实际实现位置。读完本文你将能够理解 Move Prover 的编码方案如何影响验证性能并掌握使用prover-lab的bench与plot子命令进行模块级、函数级验证耗时对比的完整实战方法。实验背景为什么需要对比两种编码后端Move Prover 是一条将 Move 语言规范specification转换为可验证形式的验证工具链Move 源码首先被编译为字节码经过字节码管线bytecode pipeline的各类变换后最终翻译为 Boogie 程序交由 Boogie SMT 求解器如 Z3证明属性。整个工具链位于仓库的 third_party/move/move-prover 目录而 prover-lab 则是一个专门用于分析 Move Prover 性能的实验 crate见 lab/README.md。data目录下存放着多个实验会话lab session每个会话包含脚本与持久化的基准数据其中mono会话的主题是Benchmarking polymorphic vs monomorphic encoding——即对比两种不同后端backend对同一组 Move 源码的验证性能。之所以要做这个对比是因为如何把 Move 程序编码为 Boogie 类型系统直接决定了最终交给求解器的约束复杂度。泛型的编码方式、结构体的表示形式、内存全局状态的建模方式都会显著影响 SMT 求解时间。这个实验正是为了量化两种编码策略的差距。传统多态后端基于$Value通用域的编码文档首先描述了传统polymorphic后端的编码方式其核心思想是使用一个通用域$Value来统一表示所有可能的 Move 值$Value是全集union它是所有可能值的联合类型任何 Move 值都可以装箱boxed为$Value结构体表示为向量结构体在 Boogie 层被表示成Vec $Value即字段列表就是一个$Value向量字段的选取/更新等价于向量索引索引操作需要伴随 unbox/box 转换泛型值装箱非泛型值拆箱对于泛型值一律使用$Value装箱表示而对于非泛型的参数与局部变量只要可能就使用未装箱unboxed的表示以降低开销相等性依赖分层stratification$Value上提供了相等性判断但由于$Value可以递归地包含自身例如嵌套的Vec $Value相等性比较需要借助分层stratification机制来约束递归深度防止比较过程无限递归。这种设计的优点是编码统一、实现简单代价是大量的装箱/拆箱操作、向量索引以及带深度限制的递归相等性会给求解器带来额外负担。在 struct-as-adt 实验 的 README 中对这种用$Value向量表示结构体的方式也有类似描述可作为对照阅读。单态化后端五大关键编码差异单态化monomorphic后端与多态后端的差异文档归纳为以下五点这也是整个实验最核心的技术内容1. 结构体表示为 ADT并按类型实例特化单态化后端将结构体表示为抽象数据类型ADT字段不再装箱为$Value而是以未装箱形式存放。更重要的是结构体和向量会针对程序中出现的所有类型实例化instantiation进行特化specialize。这意味着相等性也随之特化**不再需要分层stratification**来限制递归深度规范函数specification functions同样会被特化每个具体实例都有对应的 Boogie 版本。特化消除了运行时类型分支让每个实例的 Boogie 表示都尽可能精简。2. 内存全局状态特化编译掉类型索引Move 的全局内存memory是按(类型, 地址)键访问的。在多态后端中内存访问需要同时携带类型索引而单态化后端将内存特化后只需通过单一的地址索引address index即可访问——因为类型索引已经被编译掉了。这大幅简化了全局状态的 Boogie 建模。3. 变更强类型化为$Mutation T对内存的变更mutation被强类型化为$Mutation T其中T是具体的值类型。文档特别指出这假设了 write-back写回存在强边strong edges即写回操作的类型信息是精确、可靠的。4. 泛型函数的参数化多态验证单态化后端验证一个泛型函数及其使用的内存的方式是将类型参数声明为全局的 given 类型given types然后对函数进行验证。其背后的猜想是如果带符号类型参数的验证能够成功那么对任意具体实例化的验证也都能成功即参数化多态。文档也诚实指出这一猜想很可能在将来需要更正式化的证明probably likely needs a more formal proof down the road属于当前实现的一个理论假设。5. 调用点特化内联与 opaque 函数对于内联inlined函数在调用点call site为具体实例化生成特化版本对于opaque不透明函数在调用方一侧特化其前置条件pre conditions与后置条件post conditions并插入到调用位置。这样单态化后端对每个调用点都能拿到类型完全确定的特化代码而不是统一走$Value的通用路径。基准测试实战用prover-lab bench复现实验mono实验目录third_party/move/move-prover/lab/data/mono中提供了完整的实验脚本与数据文件文件作用run.sh对目录下所有.toml配置分别跑按函数与按模块两轮基准plot.sh读取两个后端的基准数据生成 SVG 对比图poly_backend.toml/mono_backend.toml两个后端的 prover 配置当前内容为空/几乎为空说明实验复现时使用的是默认选项poly_backend.fun_data/mono_backend.fun_data按函数维度的基准结果poly_backend.mod_data/mono_backend.mod_data按模块维度的基准结果mod_by_mod.svg/fun_by_fun.svg模块级与函数级验证耗时对比图run.sh的核心命令如下源码见 run.shfor config in *.toml ; do # 按函数基准 cargo run -q --release -p prover-lab -- \ bench -f -c $config -d $STDLIB -d $FRAMEWORK $FRAMEWORK/*.move # 按模块基准 cargo run -q --release -p prover-lab -- \ bench -c $config -d $STDLIB -d $FRAMEWORK $FRAMEWORK/*.move done其中$STDLIB与$FRAMEWORK分别指向 move 标准库与 Diem framework 的 sources 目录即被测对象是整套框架源码依赖目录用-d传入只作依赖、不参与验证源码文件作为位置参数传给bench。bench子命令的参数定义位于 benchmark.rs参数说明-c, --config CONFIG_PATHprover 的 toml 配置文件路径可重复传入以对同一组模块跑多个配置基准输出保存在CONFIG_PATH同名的数据文件中-f, --func是否按函数维度基准默认按模块维度-a, --aptos是否包含 aptos-natives自定义 native 模板见 benchmark.rs-d, --dependency PATHMove 依赖文件或目录不会被验证PATH_TO_SOURCE_FILE...待验证的源码文件输出文件的命名规则按函数基准时扩展名为fun_data按模块基准时为mod_data见 benchmark.rs这就是目录中poly_backend.fun_data、mono_backend.mod_data等文件名的由来。另外bench在运行时会对所有目标施加统一约束见 benchmark.rs保证实验口径一致hard_timeout_secs 60任何单个基准任务最多运行 60 秒超时通常意味着 Boogie 或求解器存在 bugvc_timeout 400验证条件verification condition的超时上限proc_cores 1强制单核保证不同后端之间耗时可比。基准数据格式与结果解读.fun_data/.mod_data文件是纯文本表格每一行包含三项目标函数或模块名、耗时毫秒、结果。以mono_backend.fun_data为例文件头注释# config: mono_backend.toml、# time: 2021-04-22 ...记录了配置与运行时间CoreAddresses::CORE_CODE_ADDRESS 402 ok DiemTimestamp::set_time_has_started 1107 ok SlidingNonce::try_record_nonce 497 errors Signature::ed25519_verify 310 ok其中ok表示该函数验证成功errors表示验证出错出现反例或超时。与poly_backend.fun_data中同一批目标对比同样运行于 2021-04-22DiemTimestamp::set_time_has_started 1147 ok SlidingNonce::try_record_nonce 752 errors Signature::ed25519_verify 386 ok可以看出在这批 Diem framework 函数上单态化后端多数目标的验证耗时低于多态后端例如Signature::ed25519_verify从 386ms 降至 310msDiemTimestamp::set_time_has_started从 1147ms 降至 1107msSlidingNonce::try_record_nonce从 752ms 降至 497ms两者均为errors说明该函数在两个后端下都存在验证失败项但其耗时同样被记录用于对比。需要说明的是这些数字是仓库中持久化的历史基准数据反映的是当时的 Diem framework 与工具链版本不能直接外推为当前 aptos 代码库的通用性能结论。可视化prover-lab plot与 SVG 图表plot.sh使用prover-lab的plot子命令把数据画成 SVGcargo run -q --release -p prover-lab -- \ plot --out fun_by_fun.svg --sort poly_backend.fun_data mono_backend.fun_data cargo run -q --release -p prover-lab -- \ plot --out mod_by_mod.svg --sort poly_backend.mod_data mono_backend.mod_dataplot子命令的参数定义位于 plot.rs参数说明--out FILE输出 SVG 文件路径默认plot.svg-s, --sort是否按第一个数据文件的顺序对全部数据排序--top NUMBER只绘制前 N 个条目绘图逻辑以第一个数据文件的条目顺序为基准只有第一个基准中出现的标签才会被绘制见 plot.rs并使用plotters的SVGBackend输出矢量图。文档中嵌入的两张结果图如下这两张图分别从模块粒度与函数粒度展示了两种后端对整套框架验证耗时的差异是理解单态化收益最直观的入口。可复现性说明本实验无法在 head 上直接运行需要特别提醒run.sh脚本的开头就明确退出exit 1并提示This lab cannot be run at head because the poly backend has been removed!即多态后端在当前仓库的 head 版本中已经被移除因此该实验无法在最新代码上直接复现。若要运行此实验需要回到 Diem 仓库的提交2b248773729ef75c805e94982cce7c941b11cbfb脚本注释中给出的 commit hash。这意味着mono实验属于历史性、结论性的实验记录数据与图表用于说明当时两种后端的性能对比而当前仓库已演进为单态化后端。类似的不可复现实验还有 struct-as-adt对比 ADT 与向量表示结构体其 README 同样给出了可复现的 commit hash222ef5b779c8b10c2575467541c1ff6139609a06。从实验到生产当前仓库中的单态化实现虽然实验本身停留在历史版本但单态化思想已经在当前仓库的 Move Prover 中落地。核心实现位于 bytecode-pipeline/src/mono_analysis.rsMonoAnalysisProcessor实现了FunctionTargetProcessor接口处理器名称为mono_analysis且标记为is_single_run单次运行见 mono_analysis.rs它负责计算单态化信息MonoInfo包括结构体的所有类型实例化、函数的语义实例、可到达的验证根等分析结果会作为GlobalEnv的扩展信息存储Boogie 后端据此生成特化后的编码dump_result还支持把struct 实例化、fun 实例化的分析结果打印出来见 mono_analysis.rs方便开发者在调试时检视特化结果。从源码结构可以推断mono实验所验证的结构体/向量特化、内存特化、调用点特化等核心思路最终被吸收进了正式的单态化分析管线成为 Move Prover 默认后端编码的一部分。这也解释了为什么文档中称该实验对比的是两个不同后端版本——实验记录的是演进过程中的关键决策点。小结本文完整还原了mono实验的技术内容多态后端的$Value通用域编码装箱、向量化结构体、分层相等性与单态化后端的五大差异ADT 表示与特化、内存特化、强类型$Mutation T、泛型函数参数化多态验证、调用点特化。同时给出了通过prover-lab bench/plot复现实验的完整命令与参数表、基准数据文件的格式与解读方法并厘清了实验的可复现性边界——多态后端已被移除实验属于历史记录而单态化思想已在当前仓库的mono_analysis管线和 Boogie 后端中落地。对于希望深入 Move Prover 编码层性能优化的读者建议按文档链接继续阅读 lab/README.md、struct-as-adt 等实验并结合 benchmark.rs、plot.rs 与 mono_analysis.rs 自行验证与扩展。【免费下载链接】aptos-coreAptos is a layer 1 blockchain built to support the widespread use of blockchain through better technology and user experience.项目地址: https://gitcode.com/GitHub_Trending/ap/aptos-core创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
Move Prover 多态与单态化编码基准测试：基于 prover-lab 的后端验证性能对比实验指南
Move Prover 多态与单态化编码基准测试基于 prover-lab 的后端验证性能对比实验指南【免费下载链接】aptos-coreAptos is a layer 1 blockchain built to support the widespread use of blockchain through better technology and user experience.项目地址: https://gitcode.com/GitHub_Trending/ap/aptos-core本篇文章围绕 Move Prover 实验套件 prover-lab 中的mono实验见 README系统讲解 Move Prover 两种 Boogie 后端的编码策略——传统多态polymorphic编码与单态化monomorphic编码的核心差异、基准测试的完整复现流程、数据文件与图表解读方法并结合当前仓库源码说明单态化分析的实际实现位置。读完本文你将能够理解 Move Prover 的编码方案如何影响验证性能并掌握使用prover-lab的bench与plot子命令进行模块级、函数级验证耗时对比的完整实战方法。实验背景为什么需要对比两种编码后端Move Prover 是一条将 Move 语言规范specification转换为可验证形式的验证工具链Move 源码首先被编译为字节码经过字节码管线bytecode pipeline的各类变换后最终翻译为 Boogie 程序交由 Boogie SMT 求解器如 Z3证明属性。整个工具链位于仓库的 third_party/move/move-prover 目录而 prover-lab 则是一个专门用于分析 Move Prover 性能的实验 crate见 lab/README.md。data目录下存放着多个实验会话lab session每个会话包含脚本与持久化的基准数据其中mono会话的主题是Benchmarking polymorphic vs monomorphic encoding——即对比两种不同后端backend对同一组 Move 源码的验证性能。之所以要做这个对比是因为如何把 Move 程序编码为 Boogie 类型系统直接决定了最终交给求解器的约束复杂度。泛型的编码方式、结构体的表示形式、内存全局状态的建模方式都会显著影响 SMT 求解时间。这个实验正是为了量化两种编码策略的差距。传统多态后端基于$Value通用域的编码文档首先描述了传统polymorphic后端的编码方式其核心思想是使用一个通用域$Value来统一表示所有可能的 Move 值$Value是全集union它是所有可能值的联合类型任何 Move 值都可以装箱boxed为$Value结构体表示为向量结构体在 Boogie 层被表示成Vec $Value即字段列表就是一个$Value向量字段的选取/更新等价于向量索引索引操作需要伴随 unbox/box 转换泛型值装箱非泛型值拆箱对于泛型值一律使用$Value装箱表示而对于非泛型的参数与局部变量只要可能就使用未装箱unboxed的表示以降低开销相等性依赖分层stratification$Value上提供了相等性判断但由于$Value可以递归地包含自身例如嵌套的Vec $Value相等性比较需要借助分层stratification机制来约束递归深度防止比较过程无限递归。这种设计的优点是编码统一、实现简单代价是大量的装箱/拆箱操作、向量索引以及带深度限制的递归相等性会给求解器带来额外负担。在 struct-as-adt 实验 的 README 中对这种用$Value向量表示结构体的方式也有类似描述可作为对照阅读。单态化后端五大关键编码差异单态化monomorphic后端与多态后端的差异文档归纳为以下五点这也是整个实验最核心的技术内容1. 结构体表示为 ADT并按类型实例特化单态化后端将结构体表示为抽象数据类型ADT字段不再装箱为$Value而是以未装箱形式存放。更重要的是结构体和向量会针对程序中出现的所有类型实例化instantiation进行特化specialize。这意味着相等性也随之特化**不再需要分层stratification**来限制递归深度规范函数specification functions同样会被特化每个具体实例都有对应的 Boogie 版本。特化消除了运行时类型分支让每个实例的 Boogie 表示都尽可能精简。2. 内存全局状态特化编译掉类型索引Move 的全局内存memory是按(类型, 地址)键访问的。在多态后端中内存访问需要同时携带类型索引而单态化后端将内存特化后只需通过单一的地址索引address index即可访问——因为类型索引已经被编译掉了。这大幅简化了全局状态的 Boogie 建模。3. 变更强类型化为$Mutation T对内存的变更mutation被强类型化为$Mutation T其中T是具体的值类型。文档特别指出这假设了 write-back写回存在强边strong edges即写回操作的类型信息是精确、可靠的。4. 泛型函数的参数化多态验证单态化后端验证一个泛型函数及其使用的内存的方式是将类型参数声明为全局的 given 类型given types然后对函数进行验证。其背后的猜想是如果带符号类型参数的验证能够成功那么对任意具体实例化的验证也都能成功即参数化多态。文档也诚实指出这一猜想很可能在将来需要更正式化的证明probably likely needs a more formal proof down the road属于当前实现的一个理论假设。5. 调用点特化内联与 opaque 函数对于内联inlined函数在调用点call site为具体实例化生成特化版本对于opaque不透明函数在调用方一侧特化其前置条件pre conditions与后置条件post conditions并插入到调用位置。这样单态化后端对每个调用点都能拿到类型完全确定的特化代码而不是统一走$Value的通用路径。基准测试实战用prover-lab bench复现实验mono实验目录third_party/move/move-prover/lab/data/mono中提供了完整的实验脚本与数据文件文件作用run.sh对目录下所有.toml配置分别跑按函数与按模块两轮基准plot.sh读取两个后端的基准数据生成 SVG 对比图poly_backend.toml/mono_backend.toml两个后端的 prover 配置当前内容为空/几乎为空说明实验复现时使用的是默认选项poly_backend.fun_data/mono_backend.fun_data按函数维度的基准结果poly_backend.mod_data/mono_backend.mod_data按模块维度的基准结果mod_by_mod.svg/fun_by_fun.svg模块级与函数级验证耗时对比图run.sh的核心命令如下源码见 run.shfor config in *.toml ; do # 按函数基准 cargo run -q --release -p prover-lab -- \ bench -f -c $config -d $STDLIB -d $FRAMEWORK $FRAMEWORK/*.move # 按模块基准 cargo run -q --release -p prover-lab -- \ bench -c $config -d $STDLIB -d $FRAMEWORK $FRAMEWORK/*.move done其中$STDLIB与$FRAMEWORK分别指向 move 标准库与 Diem framework 的 sources 目录即被测对象是整套框架源码依赖目录用-d传入只作依赖、不参与验证源码文件作为位置参数传给bench。bench子命令的参数定义位于 benchmark.rs参数说明-c, --config CONFIG_PATHprover 的 toml 配置文件路径可重复传入以对同一组模块跑多个配置基准输出保存在CONFIG_PATH同名的数据文件中-f, --func是否按函数维度基准默认按模块维度-a, --aptos是否包含 aptos-natives自定义 native 模板见 benchmark.rs-d, --dependency PATHMove 依赖文件或目录不会被验证PATH_TO_SOURCE_FILE...待验证的源码文件输出文件的命名规则按函数基准时扩展名为fun_data按模块基准时为mod_data见 benchmark.rs这就是目录中poly_backend.fun_data、mono_backend.mod_data等文件名的由来。另外bench在运行时会对所有目标施加统一约束见 benchmark.rs保证实验口径一致hard_timeout_secs 60任何单个基准任务最多运行 60 秒超时通常意味着 Boogie 或求解器存在 bugvc_timeout 400验证条件verification condition的超时上限proc_cores 1强制单核保证不同后端之间耗时可比。基准数据格式与结果解读.fun_data/.mod_data文件是纯文本表格每一行包含三项目标函数或模块名、耗时毫秒、结果。以mono_backend.fun_data为例文件头注释# config: mono_backend.toml、# time: 2021-04-22 ...记录了配置与运行时间CoreAddresses::CORE_CODE_ADDRESS 402 ok DiemTimestamp::set_time_has_started 1107 ok SlidingNonce::try_record_nonce 497 errors Signature::ed25519_verify 310 ok其中ok表示该函数验证成功errors表示验证出错出现反例或超时。与poly_backend.fun_data中同一批目标对比同样运行于 2021-04-22DiemTimestamp::set_time_has_started 1147 ok SlidingNonce::try_record_nonce 752 errors Signature::ed25519_verify 386 ok可以看出在这批 Diem framework 函数上单态化后端多数目标的验证耗时低于多态后端例如Signature::ed25519_verify从 386ms 降至 310msDiemTimestamp::set_time_has_started从 1147ms 降至 1107msSlidingNonce::try_record_nonce从 752ms 降至 497ms两者均为errors说明该函数在两个后端下都存在验证失败项但其耗时同样被记录用于对比。需要说明的是这些数字是仓库中持久化的历史基准数据反映的是当时的 Diem framework 与工具链版本不能直接外推为当前 aptos 代码库的通用性能结论。可视化prover-lab plot与 SVG 图表plot.sh使用prover-lab的plot子命令把数据画成 SVGcargo run -q --release -p prover-lab -- \ plot --out fun_by_fun.svg --sort poly_backend.fun_data mono_backend.fun_data cargo run -q --release -p prover-lab -- \ plot --out mod_by_mod.svg --sort poly_backend.mod_data mono_backend.mod_dataplot子命令的参数定义位于 plot.rs参数说明--out FILE输出 SVG 文件路径默认plot.svg-s, --sort是否按第一个数据文件的顺序对全部数据排序--top NUMBER只绘制前 N 个条目绘图逻辑以第一个数据文件的条目顺序为基准只有第一个基准中出现的标签才会被绘制见 plot.rs并使用plotters的SVGBackend输出矢量图。文档中嵌入的两张结果图如下这两张图分别从模块粒度与函数粒度展示了两种后端对整套框架验证耗时的差异是理解单态化收益最直观的入口。可复现性说明本实验无法在 head 上直接运行需要特别提醒run.sh脚本的开头就明确退出exit 1并提示This lab cannot be run at head because the poly backend has been removed!即多态后端在当前仓库的 head 版本中已经被移除因此该实验无法在最新代码上直接复现。若要运行此实验需要回到 Diem 仓库的提交2b248773729ef75c805e94982cce7c941b11cbfb脚本注释中给出的 commit hash。这意味着mono实验属于历史性、结论性的实验记录数据与图表用于说明当时两种后端的性能对比而当前仓库已演进为单态化后端。类似的不可复现实验还有 struct-as-adt对比 ADT 与向量表示结构体其 README 同样给出了可复现的 commit hash222ef5b779c8b10c2575467541c1ff6139609a06。从实验到生产当前仓库中的单态化实现虽然实验本身停留在历史版本但单态化思想已经在当前仓库的 Move Prover 中落地。核心实现位于 bytecode-pipeline/src/mono_analysis.rsMonoAnalysisProcessor实现了FunctionTargetProcessor接口处理器名称为mono_analysis且标记为is_single_run单次运行见 mono_analysis.rs它负责计算单态化信息MonoInfo包括结构体的所有类型实例化、函数的语义实例、可到达的验证根等分析结果会作为GlobalEnv的扩展信息存储Boogie 后端据此生成特化后的编码dump_result还支持把struct 实例化、fun 实例化的分析结果打印出来见 mono_analysis.rs方便开发者在调试时检视特化结果。从源码结构可以推断mono实验所验证的结构体/向量特化、内存特化、调用点特化等核心思路最终被吸收进了正式的单态化分析管线成为 Move Prover 默认后端编码的一部分。这也解释了为什么文档中称该实验对比的是两个不同后端版本——实验记录的是演进过程中的关键决策点。小结本文完整还原了mono实验的技术内容多态后端的$Value通用域编码装箱、向量化结构体、分层相等性与单态化后端的五大差异ADT 表示与特化、内存特化、强类型$Mutation T、泛型函数参数化多态验证、调用点特化。同时给出了通过prover-lab bench/plot复现实验的完整命令与参数表、基准数据文件的格式与解读方法并厘清了实验的可复现性边界——多态后端已被移除实验属于历史记录而单态化思想已在当前仓库的mono_analysis管线和 Boogie 后端中落地。对于希望深入 Move Prover 编码层性能优化的读者建议按文档链接继续阅读 lab/README.md、struct-as-adt 等实验并结合 benchmark.rs、plot.rs 与 mono_analysis.rs 自行验证与扩展。【免费下载链接】aptos-coreAptos is a layer 1 blockchain built to support the widespread use of blockchain through better technology and user experience.项目地址: https://gitcode.com/GitHub_Trending/ap/aptos-core创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
