Polygon zkEVM zkASM编译器——zkasmcom

1. 引言

Polygon zkEVM采用zkASM（zero-knowledge Assembly language）语言来解析EVM bytecode。

zkASM编译器代码见：

• https://github.com/0xPolygonHermez/zkasmcom：负责将.zkasm编译为json文件供zkExecutor使用。
• https://github.com/0xPolygonHermez/zkevm-storage-rom：为storage二级状态机的zkASM编译器。负责将storage zkasm文件编译为json文件。
• https://github.com/0xPolygonHermez/zkevm-rom：包含了zkEVM中的zkasm源代码。

本文重点关注zkasm代码，其主要依赖3个库：

• yargs：交互式命令行工具，负责参数解析。
• ffjavascript：Finite Field Library in Javascript。
• jison：一个用JavaScript语言实现的一个语法分析器生成器。

"build_parser_zkasm": "mkdir -p build; ./node_modules/.bin/jison src/zkasm_parser.jison -o build/zkasm_parser.js",
"build_parser_command": "mkdir -p build; ./node_modules/.bin/jison src/command_parser.jison -o build/command_parser.js",
"build": "npm run build_parser_zkasm && npm run build_parser_command"

npm run build会生成2个解析器文件：

• 1）zkasm_parser.js：compile.js中调用const lines = zkasm_parser.parse(src); 对 *.zkasm文件进行编译。
• 2）command_parser.js：当为main入口时，调用cmdList[i] = command_parser.parse(cmdList[i]); 对command进行解析。

zkasm中的常量参数有：【STEP和ROTL_C为只读寄存器。】

const maxConst = (1n  A，将a的索引赋值给A。
  "type": "step",
  "assignment": {
   "in": {
    "type": "reference",
    "identifier": "a"
   },
   "out": [
    "A"
   ]
  },
  "ops": [],
  "line": 14
 },
 { # @b => A，将b的索引赋值给A。
  "type": "step",
  "assignment": {
   "in": {
    "type": "reference",
    "identifier": "b"
   },
   "out": [
    "A"
   ]
  },
  "ops": [],
  "line": 15
 },
 { # @c => A，将c的索引赋值给A。
  "type": "step",
  "assignment": {
   "in": {
    "type": "reference",
    "identifier": "c"
   },
   "out": [
    "A"
   ]
  },
  "ops": [],
  "line": 16
 },
 { # @d => A，将d的索引赋值给A。
  "type": "step",
  "assignment": {
   "in": {
    "type": "reference",
    "identifier": "d"
   },
   "out": [
    "A"
   ]
  },
  "ops": [],
  "line": 17
 },
 { # end:
  "type": "label",
  "identifier": "end",
  "line": 19
 },
 { # 0 => A,B,C,D,E,CTX, SP, PC, GAS, MAXMEM, SR，将这些寄存器清零。
  "type": "step",
  "assignment": {
   "in": {
    "type": "CONST",
    "const": 0
   },
   "out": [
    "A",
    "B",
    "C",
    "D",
    "E",
    "CTX",
    "SP",
    "PC",
    "GAS",
    "MAXMEM",
    "SR"
   ]
  },
  "ops": [],
  "line": 20
 },
 { # finalWait:
  "type": "label",
  "identifier": "finalWait",
  "line": 22
 },
 { # ${beforeLast()}  : JMPN(finalWait)
  "type": "step",
  "assignment": {
   "in": {
    "type": "TAG",
    "tag": "beforeLast()" # 为标签。
   },
   "out": []
  },
  "ops": [
   {
    "JMPC": 0,
    "JMPN": 1,
    "offset": "finalWait"
   }
  ],
  "line": 23
 },
 { # : JMP(start)
  "type": "step",
  "assignment": null,
  "ops": [
   {
    "JMP": 1,
    "JMPC": 0,
    "JMPN": 0,
    "offset": "start"
   }
  ],
  "line": 25
 },
 { # opINVALID:
  "type": "label",
  "identifier": "opINVALID",
  "line": 26
 }
]

然后对以上内容逐行处理：

	for (let i=0; i0) error(l, "command not allowed before include");
            lastLineAllowsCommand = false;
        } else if (l.type == "var") {
            if (typeof ctx.vars[l.name] !== "undefined") error(l, `Variable ${l.name} already defined`);
            if (l.scope == "GLOBAL") { // 给全局变量根据名称分配，不允许有重名情况。
                ctx.vars[l.name] = {
                    scope: "GLOBAL",
                    offset: ctx.lastGlobalVarAssigned + 1
                }
                ctx.lastGlobalVarAssigned += l.count; // 适于按数组分配。
            } else if (l.scope == "CTX") {
                ctx.vars[l.name] = {
                    scope: "CTX",
                    offset: ctx.lastLocalVarCtxAssigned + 1
                }
                ctx.lastLocalVarCtxAssigned += l.count;
            } else {
                throw error(l, `Invalid scope ${l.scope}`);
            }
            if (pendingCommands.length>0) error(l, "command not allowed before var");
            lastLineAllowsCommand = false;
        } else if (l.type == 'constdef' || l.type == 'constldef' ) {
            const value = evaluateExpression(ctx, l.value);
            let ctype = l.type == 'constldef' ? 'CONSTL':'CONST';
            defineConstant(ctx, l.name, ctype, value);
        } else if (l.type == "step") { // start/end等标签下的实际执行语句
            const traceStep = { // traceStep内map：step[key]=op[key]
                // type: "step"
            };
            try {
                for (let j=0; j0) error(l, "command not allowed before label")
            lastLineAllowsCommand = false;
        } else if (l.type == "command") {
            if (lastLineAllowsCommand) {
                if (typeof ctx.out[ctx.out.length-1].cmdAfter === "undefined")
                    ctx.out[ctx.out.length-1].cmdAfter = [];
                ctx.out[ctx.out.length-1].cmdAfter.push(l.cmd);
            } else {
                pendingCommands.push(l.cmd);
            }
        } else {
            error(l, `Invalid line type: ${l.type}`);
        }
    }

assignment中的in内容的处理规则为：

function processAssignmentIn(ctx, input, currentLine) {
    const res = {};
    let E1, E2;
    if (input.type == "TAG") { # ${beforeLast()}  : JMPN(finalWait)，会调用command_parser。
        res.freeInTag = input.tag ? command_parser.parse(input.tag) : { op: ""};
        res.inFREE = 1n;
        return res;
    }
    if (input.type == "REG") {
        if (input.reg == "zkPC") {
            res.CONST = BigInt(currentLine);
        }
        else {
            res["in"+ input.reg] = 1n;
        }
        return res;
    }
    if (input.type == "COUNTER") {
        let res = {};
        res["in" + input.counter.charAt(0).toUpperCase() + input.counter.slice(1)] = 1n;
        return res;
    }
    if (input.type == "CONST") {
        res.CONST = BigInt(input.const);
        return res;
    }
    if (input.type == "CONSTL") {
        res.CONSTL = BigInt(input.const);
        return res;
    }
    if (input.type == 'CONSTID') {
        const [value, ctype] = getConstant(ctx, input.identifier);
        res[ctype] = value;
        return res;
    }

    if (input.type == "exp") {
        res.CONST = BigInt(input.values[0])**BigInt(input.values[1]);
        return res;
    }
    if ((input.type == "add") || (input.type == "sub") || (input.type == "neg") || (input.type == "mul")) {
        E1 = processAssignmentIn(ctx, input.values[0], currentLine);
    }
    if ((input.type == "add") || (input.type == "sub") || (input.type == "mul")) {
        E2 = processAssignmentIn(ctx, input.values[1], currentLine);
    }
    if (input.type == "mul") {
        if (isConstant(E1)) {
            if (typeof E2.CONSTL !== 'undefined') {
                throw new Error("Not allowed CONST and CONSTL in same operation");
            }
            Object.keys(E2).forEach(function(key) {
                E2[key] *= E1.CONST;
            });
            return E2;
        } else if (isConstant(E2)) {
            if (typeof E1.CONSTL !== 'undefined') {
                throw new Error("Not allowed CONST and CONSTL in same operation");
            }
            Object.keys(E1).forEach(function(key) {
                E1[key] *= E2.CONST;
            });
            return E1;
        } else {
            throw new Error("Multiplication not allowed in input");
        }
    }
    if (input.type == "neg") {
        Object.keys(E1).forEach(function(key) {
            E1[key] = -E1[key];
        });
        return E1;
    }
    if (input.type == "sub") {
        Object.keys(E2).forEach(function(key) {
            if (key != "freeInTag") {
                E2[key] = -E2[key];
            }
        });
        input.type = "add";
    }
    if (input.type == "add") {
        if (E1.freeInTag && E2.freeInTag) throw new Error("Only one tag allowed");
        Object.keys(E2).forEach(function(key) {
            if (E1[key]) {
                E1[key] += E2[key];
            } else {
                E1[key] = E2[key];
            }
        });
        if (typeof E1.CONST !== 'undefined' && typeof E1.CONSTL !== 'undefined') {
            throw new Error("Not allowed CONST and CONSTL in same operation");
        }
        return E1;
    }
    if (input.type == 'reference') {
        res.labelCONST = input.identifier;
        if (typeof ctx.definedLabels[input.identifier] !== 'undefined') {
            res.CONST = BigInt(ctx.definedLabels[input.identifier]);
        }
        else if (typeof ctx.vars[input.identifier] !== 'undefined') {
            res.CONST = BigInt(ctx.vars[input.identifier].offset);
        }
        else {
            throw new Error(`Not found label/variable ${input.identifier}`)
        }
        return res;
    }
    throw new Error( `Invalid type: ${input.type}`);


    function isConstant(o) {
        let res = true;
        Object.keys(o).forEach(function(key) {
            if (key != "CONST") res = false;
        });
        return res;
    }
}

assignment中out内容的处理规则为：

function processAssignmentOut(ctx, outputs) {
    const res = {};
    for (let i=0; i