NilFoundation / zkLLVM

Zero-Knowledge Proof Systems Circuit Compiler
https://docs.nil.foundation/zkllvm
296 stars 48 forks source link

Assigner assertion fails when calling variables.find() #608

Open khannanov-nil opened 6 months ago

khannanov-nil commented 6 months ago

Describe the bug Assigner fails when it is run on the below circuit and public input.

Error message:

variables.find(call_inst->getOperand(i)) != variables.end()

To Reproduce Circuit:

#![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)]
#[derive(Copy, Clone)]
pub struct BlockDataType {
    prev_block_hash: BlockType,
    data: BlockType,
    validators_signatures: [EdDSASignatureType; 4],
    validators_keys: [EdwardsAffine; 4],
}

#[repr(C)]
#[derive(Copy, Clone)]
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:

[
    {
        "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"]}
                        ]
                    }
                ]
            }
        ]
    }
]

Expected behavior Assigner does NOT fail.

Toolchain versions 0.1.18

aleasims commented 6 months ago

@khannanov-nil could you please attach your generated .ll file as well

khannanov-nil commented 6 months ago

@aleasims sure! new_circuit.zip