Write an algorithm for state-proof verification

The final step in making a simple zkBridge is the creation of a state-proof verification algorithm.

Prerequisites

Read the following tutorials before proceeding further.

• Primer
• Write a circuit with hashes
• Verify EdDSA signatures
• Create a Merkle tree commitment scheme

Circuit code

Headers and namespaces / crates and modules

C++

#include <nil/crypto3/hash/algorithm/hash.hpp>
#include <nil/crypto3/hash/sha2.hpp>
#include <nil/crypto3/algebra/curves/pallas.hpp>
#include <nil/crypto3/algebra/curves/ed25519.hpp>

using namespace nil::crypto3;
using namespace nil::crypto3::algebra::curves;

Rust

#![no_main]

use std::intrinsics::assigner_sha2_256;
use std::intrinsics::assigner_sha2_512;

use ark_curve25519::{EdwardsAffine, Fr};
use ark_pallas::Fq;
use unroll::unroll_for_loops;

Structs and types

C++

typedef __attribute__((ext_vector_type(4)))
            typename pallas::base_field_type::value_type eddsa_message_block_type;

typedef struct {
    typename ed25519::template g1_type<>::value_type R;
    typename ed25519::scalar_field_type::value_type s;
} eddsa_signature_type;

typedef struct {
    typename hashes::sha2<256>::block_type prev_block_hash;
    typename hashes::sha2<256>::block_type data;
    std::array<eddsa_signature_type, 4> validators_signatures;
    std::array<typename ed25519::template g1_type<>::value_type, 4> validators_keys;
} block_data_type;

Rust

type BlockType = [Fq; 2];
type EdDSAMessageBlockType = [Fq; 4];

#[repr(C)]
pub struct BlockDataType {
    prev_block_hash: BlockType,
    data: BlockType,
    validators_signatures: [EdDSASignatureType; 4],
    validators_keys: [EdwardsAffine; 4],
}

#[repr(C)]
pub struct EdDSASignatureType {
    r: EdwardsAffine,
    s: Fr,
}

Rust directives

To learn more about the #[derive(C)] directive, click here.

Additional functions

C++

bool is_same(typename hashes::sha2<256>::block_type block0,
typename hashes::sha2<256>::block_type block1) {
    return block0[0] == block1[0] && block0[1] == block1[1];
}

bool verify_eddsa_signature (eddsa_signature_type input,
typename ed25519::template g1_type<>::value_type pk,
eddsa_message_block_type M) {
        typename ed25519::template g1_type<>::value_type B = ed25519::template g1_type<>::one();
        typename ed25519::scalar_field_type::value_type k = __builtin_assigner_sha2_512_curve25519(input.R, pk, M);

        return B*input.s == (input.R + (pk*k));
}

bool verify_signature(block_data_type unconfirmed_block) {
    bool is_verified = true;
    eddsa_message_block_type message = {unconfirmed_block.prev_block_hash[0],
                                        unconfirmed_block.prev_block_hash[1], unconfirmed_block.data[0],
                                        unconfirmed_block.data[1]};
    for (int j = 0; j < 4; j++) {
        is_verified = is_verified && verify_eddsa_signature(unconfirmed_block.validators_signatures[j],
                                                        unconfirmed_block.validators_keys[j],
                                                        message);
    }
    return is_verified;
}

Rust

pub fn hash_512(r: &EdwardsAffine, pk: &EdwardsAffine, m: &EdDSAMessageBlockType) -> Fr {
    assigner_sha2_512(r.0, pk.0, [m[0].0, m[1].0, m[2].0, m[3].0]).into()
}

pub fn hash_256(block1: &BlockType, block2: &BlockType) -> BlockType {
    let sha = assigner_sha2_256([block1[0].0, block1[1].0], [block2[0].0, block2[1].0]);
    [sha[0].into(), sha[1].into()]
}

pub fn verify_eddsa_signature(
    input: &EdDSASignatureType,
    pk: &EdwardsAffine,
    m: &EdDSAMessageBlockType,
) -> bool {
    let b = EdwardsAffine::one();
    let k = hash_512(&input.r, pk, m);
    b * input.s == input.r + (pk * k)
}

pub fn is_same(x: BlockType, y: BlockType) -> bool {
    x[0] == y[0] && x[1] == y[1]
}

#[unroll_for_loops]
pub fn verify_signature(unconfirmed_block: &BlockDataType) -> bool {
    let mut is_verified: bool = true;
    let message: EdDSAMessageBlockType = [
        unconfirmed_block.prev_block_hash[0],
        unconfirmed_block.prev_block_hash[1],
        unconfirmed_block.data[0],
        unconfirmed_block.data[1],
    ];

    for i in 0..4 {
        is_verified = is_verified
            && verify_eddsa_signature(
                &unconfirmed_block.validators_signatures[i],
                &unconfirmed_block.validators_keys[i],
                &message,
            );
    }

    is_verified
}

Circuit function

C++

[[circuit]] bool verify_protocol_state_proof (
    typename sha2<256>::block_type last_confirmed_block_hash,
    std::array<block_data_type, 2> unconfirmed_blocks) {
    bool res = true;
    if (!is_same(unconfirmed_blocks[0].prev_block_hash, last_confirmed_block_hash)) {
        return false;
    }
    for (int i = 1; i < 2; i++) {
        typename sha2<256>::block_type evaluated_block_hash =
                    hash<sha2<256>>(
                        unconfirmed_blocks[i-1].prev_block_hash,
                        unconfirmed_blocks[i-1].data);
        res = res & is_same(unconfirmed_blocks[i].prev_block_hash, evaluated_block_hash);
    }  
    return res;
}

Rust

#[circuit]
#[unroll_for_loops]
pub fn verify_protocol_state_proof(
    last_confirmed_block_hash: BlockType,
    unconfirmed_blocks: [BlockDataType; 2],
) -> bool {
    let mut is_correct = is_same(
        unconfirmed_blocks[0].prev_block_hash,
        last_confirmed_block_hash,
    );
    is_correct = is_correct && verify_signature(&unconfirmed_blocks[0]);

    for i in 1..2 {
        let evaluated_block_hash: BlockType = hash_256(
            &unconfirmed_blocks[i - 1].prev_block_hash,
            &unconfirmed_blocks[i - 1].data,
        );

        is_correct =
            is_correct && is_same(unconfirmed_blocks[i].prev_block_hash, evaluated_block_hash);
        is_correct = is_correct && verify_signature(&unconfirmed_blocks[i]);
    }

    is_correct
}

Full code

C++

#include <nil/crypto3/hash/algorithm/hash.hpp>
#include <nil/crypto3/hash/sha2.hpp>
#include <nil/crypto3/algebra/curves/pallas.hpp>
#include <nil/crypto3/algebra/curves/ed25519.hpp>

using namespace nil::crypto3;
using namespace nil::crypto3::algebra::curves;

typedef __attribute__((ext_vector_type(4)))
                typename pallas::base_field_type::value_type eddsa_message_block_type;

typedef struct {
    typename ed25519::template g1_type<>::value_type R;
    typename ed25519::scalar_field_type::value_type s;
} eddsa_signature_type;

bool verify_eddsa_signature (eddsa_signature_type input,
    typename ed25519::template g1_type<>::value_type pk,
    eddsa_message_block_type M) {

        typename ed25519::template g1_type<>::value_type B = ed25519::template g1_type<>::one();
        typename ed25519::scalar_field_type::value_type k = __builtin_assigner_sha2_512_curve25519(input.R, pk, M);

        return B*input.s == (input.R + (pk*k));
}

typedef struct {
    typename hashes::sha2<256>::block_type prev_block_hash;
    typename hashes::sha2<256>::block_type data;
    std::array<eddsa_signature_type, 4> validators_signatures;
    std::array<typename ed25519::template g1_type<>::value_type, 4> validators_keys;
} block_data_type;

bool is_same(typename hashes::sha2<256>::block_type block0,
    typename hashes::sha2<256>::block_type block1){

    return block0[0] == block1[0] && block0[1] == block1[1];
}

bool verify_signature(block_data_type unconfirmed_block) {
    bool is_verified = true;
    eddsa_message_block_type message = {unconfirmed_block.prev_block_hash[0],
                                        unconfirmed_block.prev_block_hash[1], unconfirmed_block.data[0],
                                        unconfirmed_block.data[1]};
    for (int j = 0; j < 4; j++) {
        is_verified = is_verified && verify_eddsa_signature(unconfirmed_block.validators_signatures[j],
                                                        unconfirmed_block.validators_keys[j],
                                                        message);
    }
    return is_verified;
}

[[circuit]] bool verify_protocol_state_proof (
    typename hashes::sha2<256>::block_type last_confirmed_block_hash,
    std::array<block_data_type, 2> unconfirmed_blocks) {

    bool is_correct = is_same(unconfirmed_blocks[0].prev_block_hash, last_confirmed_block_hash);
    is_correct = is_correct && verify_signature(unconfirmed_blocks[0]);

    for (int i = 1; i < 2; i++) {

        typename hashes::sha2<256>::block_type evaluated_block_hash =
            hash<hashes::sha2<256>>(unconfirmed_blocks[i-1].prev_block_hash,
                unconfirmed_blocks[i-1].data);

        is_correct = is_correct && is_same(unconfirmed_blocks[i].prev_block_hash, evaluated_block_hash);

        is_correct = is_correct && verify_signature(unconfirmed_blocks[i]);
    }

    return is_correct;
}

Rust

#![no_main]

use std::intrinsics::assigner_sha2_256;
use std::intrinsics::assigner_sha2_512;

use ark_curve25519::{EdwardsAffine, Fr};
use ark_pallas::Fq;
use unroll::unroll_for_loops;

type BlockType = [Fq; 2];
type EdDSAMessageBlockType = [Fq; 4];

#[repr(C)]
pub struct BlockDataType {
    prev_block_hash: BlockType,
    data: BlockType,
    validators_signatures: [EdDSASignatureType; 4],
    validators_keys: [EdwardsAffine; 4],
}

#[repr(C)]
pub struct EdDSASignatureType {
    r: EdwardsAffine,
    s: Fr,
}

pub fn hash_512(r: &EdwardsAffine, pk: &EdwardsAffine, m: &EdDSAMessageBlockType) -> Fr {
    assigner_sha2_512(r.0, pk.0, [m[0].0, m[1].0, m[2].0, m[3].0]).into()
}

pub fn hash_256(block1: &BlockType, block2: &BlockType) -> BlockType {
    let sha = assigner_sha2_256([block1[0].0, block1[1].0], [block2[0].0, block2[1].0]);
    [sha[0].into(), sha[1].into()]
}

pub fn verify_eddsa_signature(
    input: &EdDSASignatureType,
    pk: &EdwardsAffine,
    m: &EdDSAMessageBlockType,
) -> bool {
    let b = EdwardsAffine::one();
    let k = hash_512(&input.r, pk, m);
    b * input.s == input.r + (pk * k)
}

pub fn is_same(x: BlockType, y: BlockType) -> bool {
    x[0] == y[0] && x[1] == y[1]
}

#[unroll_for_loops]
pub fn verify_signature(unconfirmed_block: &BlockDataType) -> bool {
    let mut is_verified: bool = true;
    let message: EdDSAMessageBlockType = [
        unconfirmed_block.prev_block_hash[0],
        unconfirmed_block.prev_block_hash[1],
        unconfirmed_block.data[0],
        unconfirmed_block.data[1],
    ];

    for i in 0..4 {
        is_verified = is_verified
            && verify_eddsa_signature(
                &unconfirmed_block.validators_signatures[i],
                &unconfirmed_block.validators_keys[i],
                &message,
            );
    }

    is_verified
}

#[circuit]
#[unroll_for_loops]
pub fn verify_protocol_state_proof(
    last_confirmed_block_hash: BlockType,
    unconfirmed_blocks: [BlockDataType; 2],
) -> bool {
    let mut is_correct = is_same(
        unconfirmed_blocks[0].prev_block_hash,
        last_confirmed_block_hash,
    );
    is_correct = is_correct && verify_signature(&unconfirmed_blocks[0]);

    for i in 1..2 {
        let evaluated_block_hash: BlockType = hash_256(
            &unconfirmed_blocks[i - 1].prev_block_hash,
            &unconfirmed_blocks[i - 1].data,
        );

        is_correct =
            is_correct && is_same(unconfirmed_blocks[i].prev_block_hash, evaluated_block_hash);
        is_correct = is_correct && verify_signature(&unconfirmed_blocks[i]);
    }

    is_correct
}

Public input

The public input for the circuit could look as follows:

C++

[
    {"vector":[{"field": 1}, {"field":1}]},
    {"array": [
        {"struct": [{"vector": [{"field": 1}, {"field": 1}]},
            {"vector": [{"field": 1}, {"field": 1}]},
            {"array": [
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]}
            ]},
            {"array":[
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]}
            ]}
        ]},
        {"struct": [{"vector": [{"field": 1}, {"field": 1}]},
            {"vector": [{"field": 1}, {"field": 1}]},
            {"array": [
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]},
                {"struct": [{"curve":[4,5]}, {"field": 8}]}
            ]},
            {"array":[
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec","0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]}
            ]}
        ]}
    ]}
]

Rust

[
    {
        "array": [{"field": "1"}, {"field": "1"}]
    },
    {
        "array": [
            {
                "struct": [
                    {
                        "array": [{"field": 1}, {"field": 1}]
                    },
                    {
                        "array": [{"field": 3}, {"field": 1}]
                    },
                    {
                        "array": [
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]}
                        ]
                    },
                    {
                        "array": [
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]}
                        ]
                    }
                ]
            },
            {
                "struct": [
                    {
                        "array": [{"field": 1}, {"field": 1}]
                    },
                    {
                        "array": [{"field": 1}, {"field": 1}]
                    },
                    {
                        "array": [
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]},
                            {"struct": [{"curve": [4, 5]}, {"field": 8}]}
                        ]
                    },
                    {
                        "array": [
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]},
                            {"curve": ["0x4f043d481c8f09de646b1aa05de7ebfab126fc8bbb74f42532378c4dec6e76ec", "0x58719b60b26bd8b8b76de1a886ed82aa11692b4dc5494fe96d5b31f1c63f36a8"]}
                        ]
                    }
                ]
            }
        ]
    }
]