Skip to content

Latest commit

 

History

History
354 lines (273 loc) · 12.4 KB

zkvm-blockchain.md

File metadata and controls

354 lines (273 loc) · 12.4 KB
Raw

ZkVM blockchain specification

This is the specification for the ZkVM blockchain, a blockchain containing ZkVM transactions.

Nodes participating in a ZkVM blockchain network must implement the data types and perform the procedures described in this document. Specifically:

This document does not describe the mechanism for producing blocks from pending transactions, nor for choosing among competing blocks to include in the authoritative chain (a.k.a. consensus).

Data types

Blockchain state

The state of a ZkVM blockchain is given by the blockchain-state structure. Each node maintains a copy of this structure. As each new block arrives, it is applied to the current state to produce a new, updated state.

The blockchain state contains:

  • initialheader: The initial block header (the header with height 1). This never changes.
  • tipheader: The latest block header.
  • utreexo: The Utreexo forest.

Block

A block contains:

The initial block (at height 1) has an empty list of transactions.

Block header

A block header contains:

  • version: Integer version number, set to 1.
  • height: Integer block height. Initial block has height 1. Height increases by 1 with each new block.
  • previd: ID of the preceding block. For the initial block (which has no predecessor), this is an all-zero string of 32 bytes.
  • timestamp_ms: Integer timestamp of the block in milliseconds since the Unix epoch: 00:00:00 UTC Jan 1, 1970. Each new block must have a time strictly later than the block before it.
  • txroot: 32-byte Merkle root hash of the transactions in the block.
  • utxoroot: 32-byte Utreexo forest root of the utxo set after applying all transactions in the block, or all-zero string if the root has not changed since the previous block.
  • ext: Variable-length byte string to contain future extensions. Empty in version 1.

Block ID

A block ID is computed from a block header using the transcript mechanism:

T = Transcript("ZkVM.blockheader")
T.append("version", LE64(version))
T.append("height", LE64(height))
T.append("previd", previd)
T.append("timestamp_ms", LE64(timestamp_ms))
T.append("txroot", txroot)
T.append("utxoroot", utxoroot)
T.append("ext", ext)
blockid = T.challenge_bytes("id")

Transaction encoding

TBD: describe transaction encoding.

Transaction witness hash

Transaction witness hash commits to the raw transaction: the transaction header, utreexo proofs, tx program, signature and a constraint system proof.

T = Transcript("ZkVM.tx_witness_hash")
T.append_message("tx", encoded_tx)
result = T.challenge_bytes("hash")  // 32 bytes

Contract ID merkle leaf

Contract ID is hashed as a merkle leaf hash for the Utreexo as follows:

T.append("contract", contract_id)

Procedures

In the descriptions that follow, the word “verify” means to test whether a condition is true. If it’s false, all pending procedures abort and a failure result is returned.

Start new network

A node starts here when creating a new blockchain network. Its blockchain state is set to the result of the procedure.

Inputs:

  • timestamp_ms, the current time as a number of milliseconds since the Unix epoch: 00:00:00 UTC Jan 1, 1970.
  • utxos, the starting utxo set that allows bootstrapping the anchors.

Output:

  • Blockchain state.

Procedure:

  1. Make an initial block header initialheader from timestamp_ms and utxos.
  2. Return a blockchain state with its fields set as follows:
    • initialheader: initialheader
    • tipheader: initialheader
    • utxos: utxos

Make initial block header

Inputs:

  • timestamp_ms, the current time as a number of milliseconds since the Unix epoch: 00:00:00 UTC Jan 1, 1970.
  • utxos, the initial list of utxo IDs needed to bootstrap ZkVM anchors.

Output:

Procedure:

  1. Compute txroot from an empty list of transaction ids.
  2. Create a new Utreexo from utxos, normalize and compute the Utreexo root utxoroot.
  3. Return a block header with its fields set as follows:
    • version: 1
    • height: 1
    • previd: all-zero string of 32-bytes
    • timestamp_ms: timestamp_ms
    • txroot: txroot
    • utxoroot: utxoroot
    • ext: empty

Join existing network

A new node starts here when joining a running network. It must either:

  • obtain all historical blocks, applying them one by one to reproduce the latest blockchain state; or
  • obtain a recent copy of the blockchain state state from a trusted source (e.g., another node that has already validated the full history of the blockchain) and begin applying blocks beginning at state.tipheader.height+1.

An obtained (as opposed to computed) blockchain state state may be partially validated by computing the Utreexo root from state.utxos and verifying that it equals state.header.utxoroot. Note the Utreexo state can be validated only at the points when it was normalized, which may not happen at every block.

Validate block

Validating a block checks it for correctness outside the context of a particular blockchain state.

Additional correctness checks against a particular blockchain state happen during the apply block procedure, of which this is a subroutine.

Inputs:

  • block, the block to validate, at height 2 or above.
  • prevheader, the previous blockheader.

Output:

Procedure:

  1. Verify block.header.version >= prevheader.version.
  2. If block.header.version == 1, verify block.header.ext is empty.
  3. Verify block.header.height == prevheader.height+1.
  4. Verify block.header.previd equals the block ID of prevheader.
  5. Verify block.header.timestamp_ms > prevheader.timestamp_ms.
  6. Let txlogs and txids be the result of executing the transactions in block.txs with block.header.version and block.header.timestamp_ms.
  7. Compute txroot from txids.
  8. Verify txroot == block.header.txroot.
  9. Return txlogs.

Make block

Inputs:

  • state, a blockchain state.
  • version, a version number for the new block. Note that this must be equal to or greater than state.tipheader.version, the version number of the previous block header.
  • timestamp_ms, a time for the new block as milliseconds since the Unix epoch, 00:00:00 UTC Jan 1, 1970. This must be strictly greater than state.tipheader.timestamp_ms, the timestamp of the previous block header.
  • txs, a list of transactions.
  • ext, the contents of the new block’s “extension” field. Note that at this writing, only block version 1 is defined, which requires ext to be empty.

Output:

  • a new block containing txs.

Procedure:

  1. Let previd be the block ID of state.tipheader.
  2. Let txlogs and txids be the result of executing txs with version and timestamp_ms.
  3. Let state´ be the result of applying txlogs to state.
  4. Let txids be the list of transaction IDs of the transactions in txs, computed from each transaction’s header entry and the corresponding item from txlogs.
  5. Compute txroot from txids to produce txroot.
  6. If state´.utreexo has updates count higher than 65536 (2^16), normalize the Utreexo and compute the Utreexo root uroot. Otherwise, set uroot to all-zero hash.
  7. Let h be a block header with its fields set as follows:
    • version: version
    • height: state.tipheader.height+1
    • previd: previd
    • timestamp_ms: timestamp_ms
    • txroot: txroot
    • utxoroot: uroot
    • ext: ext
  8. Return a block with header h and transactions txs.

Note: the threshold of updates count is not enforced by the verifiers and can be adjusted by the network.

Execute transaction list

Input:

  • txs, a list of transactions.
  • version, a version number for a block.
  • timestamp_ms, a block timestamp as milliseconds since the Unix epoch, 00:00:00 UTC Jan 1, 1970.

Outputs:

Procedure:

  1. Let txresults be an empty list of tuples.
  2. For each transaction tx in txs:
    1. Verify tx.locktime_ms <= timestamp_ms.
    2. If version == 1, verify tx.version == 1.
    3. Execute tx to produce transaction log txlog.
    4. Compute transaction ID txid from the header entry of tx and from txlog.
    5. Add (txid, txlog) to txresults.
  3. Return txresults.

Note that step 2 can be parallelized across txs.

Apply block

Applying a block causes a node to replace its blockchain state with the updated state that results.

Inputs:

  • block, the block to apply.
  • state, the current blockchain state.

Output:

  • New blockchain state state′.

Procedure:

  1. Let txlogs be the result of validating block with prevheader set to state.tipheader.
  2. Let state′ be state.
  3. Let state′′ be the result of applying txlogs to state′.
  4. Set state′ <- state′′.
  5. If block.header.utxoroot is not all-zero:
    1. Normalize the Utreexo and compute the Utreexo root.
    2. Verify block.header.utxoroot == utxoroot.
    3. Update the state′ with the new normalized Utreexo instance.
  6. Set state′.tipheader <- block.header.
  7. Return state′.

Apply transaction list

Inputs:

Output:

  • Updated blockchain state or failure.

Procedure:

  1. Let state′ be state.
  2. For each txlog in txlogs, in order:
    1. Let state′′ be the result of applying the txlog to state′ to produce state′′.
    2. Set state′ <- state′′ if transaction log is not rejected.
  3. Return state′.

Apply transaction log

Inputs:

Output:

  • New blockchain state state′ or failure.

Procedure:

  1. Let state′ be state.
  2. For each input entry or output entry in txlog:
    1. If an input entry, perform the Utreexo delete operation with UTXO ID. If it fails, reject the entire transaction log.
    2. If an output entry, perform the Utreexo insert operation with UTXO ID.
  3. Return state′ if the updates did not fail.

Compute txroot

Input:

  • Ordered list of block transactions.

Output:

Procedure:

  1. Create a transcript T with label ZkVM.txroot.
  2. For each transaction, compute witness hash w.
  3. Return MerkleHash(T, {w}) hashing the witness hash with T.append_message("txwit", w).