STARKy RGB: making RGB compatible with zk-STARKs

[dr-orlovsky]

I'd like to share with you results of my research I've been doing for the last year, and propose for a discussion a design and a set of changes required to achieve history compression for RGB with zk-STARKs (a project codenamed "zk-RGB") in a future.

zk-STARKs are the most advanced method for computational integrity, which has the following unique properties, making it the best choice among all the alternatives:

• poly-logarithmic verification time;
• no use of elliptic curves, with makes it both fast and quantum-resistant;
• simpler to implement for register-based VMs, like AluVM (takes a computation trace with registers instead of an arithmetic circuit design as SNARKs or Bulletproofs do).

The only drawback of zk-STARKs is the size of the proof, which may span multiple megabytes; however, this is mitigated by the use of a recurcive zk-STARK proofs, meaning that the whole history of any size for a given RGB contract may be always compressed to a constant-sized blob of few MBs.

Change analysis

This part analyses what is required in order to bring zk-STARK compatibility to the RGB consensus, describing the required changes and the proposed implementation approach module-by-module.

Client-side validation

SHA256 is very computational-intense to be implemented in zk-STARK, which will very significantly increase the size of proofs and the time required to generate them. Thus, use of zk-START-friendly hash function is advised.

Thus, a multi-protocol commitments must support different hash functions, and commit to the specific use function value alongside such parameters as entropy and the depth of the tree.

It can be that information about the used hash function should be optional, since it can be deduces from the single-use seal type, which commits to the closing method; and each closing method can be used with just one type of MPC (and its hash function). But anyway, this may significantly simplify validation logic, so consider adding info about the hash to the MPC itself (or use some feature flags to indicate that).

PR: LNP-BP/client_side_validation#186

zk-AluVM

It would take a complete re-write of AluVM to make it zk-STARK-compatible, but the good news is that this task is already complete (see the PR at the end of the section). Specifically, what was needed and was already done:

1. A new reduced RISC ALU128 base instruction set architecture (ISA) which contains only:
   • A8-A128 registers;
   • control flow instructions;
   • EQ instruction (and no LE/LT/GE/GT);
   • data instructions: put a value into a register, clear value, test value, copy move and swap values between registers; all these ops are compatible with values being field elements;
   • no bit logic instructions.
2. Galois finite-field arithmetic GFA128 ISA extension:
   • adds fp read-only register contanining the used field order;
   • adds field_order to the CoreConfig with which AluVM core is initialized;
   • treats all A8-A128 registers as field elements;
   • adds arithmetic ops over finite field; if a register has a value which doesn't fit it the operation sould fail.
3. zk-aluvm feature flag which allows only zk-STARK-compatible ISA and ISA extension: ALU128 and GFA128.

PR: AluVM/rust-aluvm#128

The above can be followed with more functionality, deployed later, which would include:

• 256- and 512-bit finite field arithmetic (ALU256, ALU512, GFA256, GFA512);
• instructions implementing jets for
  • zk-compatible hash functions (POSEIDON/RESCUE);
  • lamport-style signatures (using hashes and not elliptic curves).

NB: These upgrades should be deployed later over the course of time, since they are fully backward-compatible.

NB2: I do not think we need elliptic curve cryptography in zk-AluVM, since the ownership is verified at the level of Bitcoin transactions, and other asymmetric cryptography cases can be done with lamport-style hash-based signatures, which are fast and easy to do in zk-STARKs (and we have no size restrictions due to compression).

RGB

RGB State

With the introduction of zk-STARK history compression, the state data in RGB won't be always seen from the history. Thus, all types of the contract state will be now differentiated into two categories:

• omittable: state which omitted from the compressed history,
• persistent: the state which is preserved and kept forever (increasing the size of history data even when the compression is applied).

Next, two other state categories appear: verifiable state and non-verifiable.

The verifiable state MUST consist (or be representable) of exclusively field elements; and its content may be validated using zk-AluVM for each RGB operation. The state which doesn't satisfy this requirement is non-verifiable.

The proposed design for the state refactoring is the following:

1. Phase 1: state unification and simplification - Tracking: state unification, removal of confidential assets #263
   • remove Pedersen commitments and abandon planned support for bulletproofs ("confidential assets");
   • unify all state types into a single type as opaque data blob;
   • provide AluVM scripts which would calculate state from the user input and present it to user (these scripts do not need to be zk-compatible since they are not used in contract verification and history).
2. Phase 2: make state STARKy - STARKy RGB, phase 2 rgb-core#281
   • owned state should be treated as omittable and verifiable;
   • global state should differentiate (at the schema level for each state type) whether it is verifiable and omittable;
   • all verifiable state (both global and owned) must be refactored into a set (of up to 8) field elements (i.e. structured state with strict types, used currently, should be abandoned for the verifiable state).

RGB Contract Genesis

Contract issuers in the contract genesis must commit to selection hash function (global) for both seals and anchors (MPCs);

It is advised to restrict the contracts to use only one (per blockchain) single-use seal closing method among all operations - a change recommended anyway independently from a zk-STARK RGB epic.

RGB Schema

The schema should include information on:

• used zk-AluVM ISAs;
• configuration for AluVM (used field order, max call stack size etc);
• for each global state type whether it is verifiable and persistent (or not);
• schema for owned state, verifiable global state and metadata instead of semantic type id should contain the number of field elements a state can have.

RGB VM

1. RGB should use only zk-AluVM for the state validation.
2. Old RGB-specific instructions should be removed; a new set of RGB zk-AluVM ISA extension must be created allowing to load field element from the verifiable state to one of the A registers;
3. Future support for bitcoin blockchain introspection and other external oracle information can be added in the same way with a transformation of the oracle data into a (set of) field element(s).

RGB Validation

First, non-verifiable global state must not be checked during the validation and should be seen at the consensus level as just opaque binary blobs. The rest of the state is present in form of field elements and must be validated with zk-AluVM scripts only.

The other parts of verification logic must be ensured to be compatible with zk-STARK. Optimistically, this means re-writing the whole validation (including schema validation) into a zk-AluVM program, however this may be challenging and hard to audit/debug. The alternative proposed approach includes the following components:

1. Ensure that schema validation business logic is as simple as possible and can be represented as an arithmetic circuit operating on field elements.(aside from state validation which is done with zk-AluVM anyway, the main task of schema validation is comparing the number of elements of an operation with a limits specified in the schema, so it can be easily arithmetized);
2. MPC validation (which comes down just to Merkle tree computation) must be written and run as a standard zk-AluVM program;
3. Single-use seal validation can't be zk-STARK compressed without compressing the state of bitcoin blockchain itself, so it may remain as is. However, independently from making RGB STARKy, it is advised that instead of witness resolver API RGB validator must receive a pre-fetched witness information (this will significantly shorten validation time and exclude network errors related to blockchain querying from the validation itself).

Deployment

Project summarizing all the required or proposed changes and the progress of their implementation is available at https://github.com/orgs/RGB-WG/projects/20/views/1

It is proposed to do a STARKy RGB ("STARGB") as a v0.12 release as soon as possible; desirably by the end of 2024, with the first beta with all required consensus changes available by the end of Nov. This is important to prevent people from issuing non-STARK compatible contracts, which can't be compressed later, using current v0.11. The deadlines seems reasonable since the most of work required for such release (like AluVM re-write into zk-AluVM, or phase 1 of RGB state changes) is already implemented.

[dr-orlovsky]

CC @adambor @fedsten