Skip to content

Latest commit

 

History

History
715 lines (398 loc) · 23.3 KB

StarcoinVerifier.md

File metadata and controls

715 lines (398 loc) · 23.3 KB
Raw

Module 0x1::StarcoinVerifier

use 0x1::BCS;
use 0x1::Hash;
use 0x1::Option;
use 0x1::StructuredHash;

Struct AccountState

struct AccountState has copy, drop, store
Fields
storage_roots: vector<Option::Option<vector<u8>>>

Struct StateProof

struct StateProof has copy, drop, store
Fields
account_proof: StarcoinVerifier::SparseMerkleProof 
    * Account state's proof for global state root.
account_state: vector<u8> 
     * Account state including storage roots.
proof: StarcoinVerifier::SparseMerkleProof 
     * State's proof for account storage root.

Struct SparseMerkleProof

struct SparseMerkleProof has copy, drop, store
Fields
siblings: vector<vector<u8>>
leaf: StarcoinVerifier::SMTNode

Struct SMTNode

struct SMTNode has copy, drop, store
Fields
hash1: vector<u8>
hash2: vector<u8>

Constants

const ACCOUNT_STORAGE_INDEX_RESOURCE: u64 = 1;


const BLOB_HASH_PREFIX: vector<u8> = [66, 108, 111, 98];


const DEFAULT_VALUE: vector<u8> = [];


const ERROR_ACCOUNT_STORAGE_ROOTS: u64 = 101;


const ERROR_LITERAL_HASH_WRONG_LENGTH: u64 = 102;


const HASH_LEN_IN_BITS: u64 = 256;


const SPARSE_MERKLE_INTERNAL_NODE: vector<u8> = [83, 112, 97, 114, 115, 101, 77, 101, 114, 107, 108, 101, 73, 110, 116, 101, 114, 110, 97, 108, 78, 111, 100, 101];


const SPARSE_MERKLE_LEAF_NODE: vector<u8> = [83, 112, 97, 114, 115, 101, 77, 101, 114, 107, 108, 101, 76, 101, 97, 102, 78, 111, 100, 101];


const SPARSE_MERKLE_PLACEHOLDER_HASH_LITERAL: vector<u8> = [83, 80, 65, 82, 83, 69, 95, 77, 69, 82, 75, 76, 69, 95, 80, 76, 65, 67, 69, 72, 79, 76, 68, 69, 82, 95, 72, 65, 83, 72];

Function bcs_deserialize_account_state

public fun bcs_deserialize_account_state(data: &vector<u8>): StarcoinVerifier::AccountState
Implementation 
public fun bcs_deserialize_account_state(data: &vector<u8>): AccountState {
    let (vec, _) = BCS::deserialize_option_bytes_vector(data, 0);
    AccountState{
        storage_roots: vec
    }
}

Function new_state_proof

public fun new_state_proof(account_proof: StarcoinVerifier::SparseMerkleProof, account_state: vector<u8>, proof: StarcoinVerifier::SparseMerkleProof): StarcoinVerifier::StateProof
Implementation 
public fun new_state_proof(account_proof: SparseMerkleProof, account_state: vector<u8>, proof: SparseMerkleProof): StateProof {
    StateProof{
        account_proof,
        account_state,
        proof,
    }
}

Function new_sparse_merkle_proof

public fun new_sparse_merkle_proof(siblings: vector<vector<u8>>, leaf: StarcoinVerifier::SMTNode): StarcoinVerifier::SparseMerkleProof
Implementation 
public fun new_sparse_merkle_proof(siblings: vector<vector<u8>>, leaf: SMTNode): SparseMerkleProof {
    SparseMerkleProof{
        siblings,
        leaf,
    }
}

Function new_smt_node

public fun new_smt_node(hash1: vector<u8>, hash2: vector<u8>): StarcoinVerifier::SMTNode
Implementation 
public fun new_smt_node(hash1: vector<u8>, hash2: vector<u8>): SMTNode {
    SMTNode{
        hash1,
        hash2,
    }
}

Function empty_smt_node

public fun empty_smt_node(): StarcoinVerifier::SMTNode
Implementation 
public fun empty_smt_node(): SMTNode {
    SMTNode{
        hash1: Vector::empty(),
        hash2: Vector::empty(),
    }
}

Function verify_state_proof

public fun verify_state_proof(state_proof: &StarcoinVerifier::StateProof, state_root: &vector<u8>, account_address: address, resource_struct_tag: &vector<u8>, state: &vector<u8>): bool
Implementation 
public fun verify_state_proof(state_proof: &StateProof, state_root: &vector<u8>,
                                       account_address: address, resource_struct_tag: &vector<u8>,
                                       state: &vector<u8>): bool {
    let accountState: AccountState = bcs_deserialize_account_state(&state_proof.account_state);
    assert!(Vector::length(&accountState.storage_roots) > ACCOUNT_STORAGE_INDEX_RESOURCE, ERROR_ACCOUNT_STORAGE_ROOTS);

    // First, verify state for storage root.
    let storageRoot = Option::borrow(Vector::borrow(&accountState.storage_roots, ACCOUNT_STORAGE_INDEX_RESOURCE));
    let ok: bool = verify_smp(&state_proof.proof.siblings,
        &state_proof.proof.leaf,
        storageRoot,
        resource_struct_tag, // resource struct tag BCS serialized as key
        state);
    if (!ok) {
        return false
    };

    // Then, verify account state for global state root.
    ok = verify_smp(&state_proof.account_proof.siblings,
        &state_proof.account_proof.leaf,
        state_root,
        &BCS::to_bytes<address>(&account_address), // account address as key
        &state_proof.account_state,
    );
    ok
}

Function verify_smp

Verify sparse merkle proof by key and value.

public fun verify_smp(sibling_nodes: &vector<vector<u8>>, leaf_data: &StarcoinVerifier::SMTNode, expected_root: &vector<u8>, key: &vector<u8>, value: &vector<u8>): bool
Implementation 
public fun verify_smp(sibling_nodes: &vector<vector<u8>>, leaf_data: &SMTNode, expected_root: &vector<u8>, key: &vector<u8>, value: &vector<u8>): bool {
    let path = hash_key(key);
    let current_hash: vector<u8>;
    if (*value == DEFAULT_VALUE) {
        // Non-membership proof.
        if (empty_smt_node() == *leaf_data) {
            current_hash = placeholder();
        } else {
            if (*&leaf_data.hash1 == *&path) {
                return false
            };
            if (!(count_common_prefix(&leaf_data.hash1, &path) >= Vector::length(sibling_nodes))) {
                return false
            };
            current_hash = StructuredHash::hash(SPARSE_MERKLE_LEAF_NODE, leaf_data);
        };
    } else {
        // Membership proof.
        if (empty_smt_node() == *leaf_data) {
            return false
        };
        if (*&leaf_data.hash1 != *&path) {
            return false
        };
        let value_hash = hash_value(value);
        if (*&leaf_data.hash2 != value_hash) {
            return false
        };
        current_hash = StructuredHash::hash(SPARSE_MERKLE_LEAF_NODE, leaf_data);
    };

    current_hash = compute_smp_root_by_path_and_node_hash(sibling_nodes, &path, ¤t_hash);
    current_hash == *expected_root
}

Function compute_smp_root_by_path_and_node_hash

public fun compute_smp_root_by_path_and_node_hash(sibling_nodes: &vector<vector<u8>>, path: &vector<u8>, node_hash: &vector<u8>): vector<u8>
Implementation 
public fun compute_smp_root_by_path_and_node_hash(sibling_nodes: &vector<vector<u8>>, path: &vector<u8>, node_hash: &vector<u8>): vector<u8> {
    let current_hash = *node_hash;
    let i = 0;
    let proof_length = Vector::length(sibling_nodes);
    while (i < proof_length) {
        let sibling = *Vector::borrow(sibling_nodes, i);
        let bit = get_bit_at_from_msb(path, proof_length - i - 1);
        let internal_node = if (bit) {
            SMTNode{ hash1: sibling, hash2: current_hash }
        } else {
            SMTNode{ hash1: current_hash, hash2: sibling }
        };
        current_hash = StructuredHash::hash(SPARSE_MERKLE_INTERNAL_NODE, &internal_node);
        i = i + 1;
    };
    current_hash
}

Function placeholder

public fun placeholder(): vector<u8>
Implementation 
public fun placeholder(): vector<u8> {
    create_literal_hash(&SPARSE_MERKLE_PLACEHOLDER_HASH_LITERAL)
}

Function create_literal_hash

public fun create_literal_hash(word: &vector<u8>): vector<u8>
Implementation 
public fun create_literal_hash(word: &vector<u8>): vector<u8> {
    if (Vector::length(word)  <= 32) {
        let lenZero = 32 - Vector::length(word);
        let i = 0;
        let r = *word;
        while (i < lenZero) {
            Vector::push_back(&mut r, 0);
            i = i + 1;
        };
        return r
    };
    abort ERROR_LITERAL_HASH_WRONG_LENGTH
}

Function hash_key

fun hash_key(key: &vector<u8>): vector<u8>
Implementation 
fun hash_key(key: &vector<u8>): vector<u8> {
    Hash::sha3_256(*key)
}

Function hash_value

fun hash_value(value: &vector<u8>): vector<u8>
Implementation 
fun hash_value(value: &vector<u8>): vector<u8> {
    StructuredHash::hash(BLOB_HASH_PREFIX, value)
}

Function count_common_prefix

fun count_common_prefix(data1: &vector<u8>, data2: &vector<u8>): u64
Implementation 
fun count_common_prefix(data1: &vector<u8>, data2: &vector<u8>): u64 {
    let count = 0;
    let i = 0;
    while ( i < Vector::length(data1) * 8) {
        if (get_bit_at_from_msb(data1, i) == get_bit_at_from_msb(data2, i)) {
            count = count + 1;
        } else {
            break
        };
        i = i + 1;
    };
    count
}

Function get_bit_at_from_msb

fun get_bit_at_from_msb(data: &vector<u8>, index: u64): bool
Implementation 
fun get_bit_at_from_msb(data: &vector<u8>, index: u64): bool {
    let pos = index / 8;
    let bit = (7 - index % 8);
    (*Vector::borrow(data, pos) >> (bit as u8)) & 1u8 != 0
}
Specification 
pragma verify = false;
pragma opaque;