raiko: c-kzg failing in SP1 due to unaligned access

Describe the feature request

Following #148 #157 #162 We still have to fix kzg compilation in SP1. I’ve included example in pipeline/examples/sp1: https://github.com/taikoxyz/raiko/blob/12826f2c820346b2c42deb757b359568e7d0f793/pipeline/examples/sp1/src/kzg.rs The goal is to get the proof generated, although it seems like extern C overloading does proves & verified:

unsafe {
        let c = calloc(100);
        let m = malloc(200);
        free(c);
        free(m);
    }

Possibly a memory or stack limit issue.

Spam policy

  • I verify that this issue is NOT SPAM and understand SPAM issues will be closed and reported to GitHub, resulting in ACCOUNT TERMINATION.

About this issue

  • Original URL
  • State: closed
  • Created 3 years ago
  • Reactions: 2
  • Comments: 22 (16 by maintainers)

Most upvoted comments

From further investigation, it seems like the issue is inside the call to:

blob_to_kzg_commitment

fix: https://github.com/taikoxyz/raiko/pull/201

Backgroud

Because, we can’t use the libc in zkvms, so we hacked the malloc and calloc methods

Case

But, we had a mismatch with the calloc function’s signature.https://www.tutorialspoint.com/c_standard_library/c_function_calloc.htm

-unsafe extern "C" fn calloc(size: usize) -> *mut c_void {
+unsafe extern "C" fn calloc(nobj: usize, size: usize) -> *mut c_void {

Call in c-kzg-4844 https://github.com/smtmfft/c-kzg-4844/blob/77e9ba0a65e10e6a470832da2914b17a968da791/src/c_kzg_4844.c#L189

static C_KZG_RET c_kzg_calloc(void **out, size_t count, size_t size) {
    *out = NULL;
    if (count == 0 || size == 0) return C_KZG_BADARGS;
    // need alloc `count * size` but only get `count(4096)` in raiko
    *out = calloc(count, size);
    return *out != NULL ? C_KZG_OK : C_KZG_MALLOC;
}

static C_KZG_RET g1_lincomb_fast(
    g1_t *out, const g1_t *p, const fr_t *coeffs, uint64_t len
) {
    C_KZG_RET ret;
    void *scratch = NULL;
    blst_p1_affine *p_affine = NULL;
    blst_scalar *scalars = NULL;

    /* Tunable parameter: must be at least 2 since blst fails for 0 or 1 */
    if (len < 8) {
        g1_lincomb_naive(out, p, coeffs, len);
    } else {
        /* blst's implementation of the Pippenger method */
        size_t scratch_size = blst_p1s_mult_pippenger_scratch_sizeof(len);
        ret = c_kzg_malloc(&scratch, scratch_size);
        if (ret != C_KZG_OK) goto out;
        ret = c_kzg_calloc((void **)&p_affine, len, sizeof(blst_p1_affine));
        if (ret != C_KZG_OK) goto out;
        ret = c_kzg_calloc((void **)&scalars, len, sizeof(blst_scalar));
        if (ret != C_KZG_OK) goto out;

        /* Transform the points to affine representation */
        const blst_p1 *p_arg[2] = {p, NULL};
        blst_p1s_to_affine(p_affine, p_arg, len);

        /* Transform the field elements to 256-bit scalars */
        for (uint64_t i = 0; i < len; i++) {
            blst_scalar_from_fr(&scalars[i], &coeffs[i]);
        }

        /* Call the Pippenger implementation */
        const byte *scalars_arg[2] = {(byte *)scalars, NULL};
        const blst_p1_affine *points_arg[2] = {p_affine, NULL};
        blst_p1s_mult_pippenger(
            out, points_arg, len, scalars_arg, 255, scratch
        );
    }

    ret = C_KZG_OK;

out:
    c_kzg_free(scratch);
    c_kzg_free(p_affine);
    c_kzg_free(scalars);
    return ret;
}

So, some of the allocated memory overlapped, resulting in a UB.

I did some investigating and this is what I found. To explore @johntaiko’s hypothesis of the issue being related to compilation on 32-bit machines, I ran the following steps. Note that this isn’t a perfect scenario to test things as it isn’t being built on the RISC-V target (QEMU is a good next step IMO).

Create a 32-bit docker container and install requirements

sudo docker run --rm -it i686/ubuntu bash
apt-get update
apt-get install git
apt-get install build-essential
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Clone c-kzg taiko fork and run tests with memory/arithmetic sanitization

Clone repo

git clone https://github.com/smtmfft/c-kzg-4844.git
cd c-kzg-4844

Change bindings/rust/build.rs to compile c-kzg with C arithmetic overflow checks

cc.flag_if_supported("-ftrapv")
cc.flag_if_supported("-fsanitize=undefined")

Run tests with rust overflow checks

rustup toolchain install nightly
RUSTFLAGS="-C overflow-checks=on" cargo test --release

This seems to work FYI.

I also tried pointing raiko to this version of c-kzg-4844 to catch any arithmetic overflows, but it seems to still work on the prover when it’s set to TARGET=native and make build && RUST_BACKTRACE=1 make test.

I think a good next step could be to do some more thorough debugging with GDB with the ELFs that get built for SP1/R0.

The above address 4122387576 (aka 0xf5b6a478) looks like garbage, in r0vm, it shouldn’t be possible for a program to address anything above 0x0c000000 (max addressable range is 192MB). So this feels like a dangling pointer. Since we’re talking about C code, it’s plausible that this might be a deeper bug in c-kzg itself (or perhaps related to modifications made to get it to run in these VMs)

There’s two additional flags you might want to pass to the builder:

  • -march=rv32im
  • -falign-functions=2

I’m on mobile at the mobile so cannot test, but if you share steps to reproduce the issue I can do some more digging tonight or tomorrow 🫡

Reopen for we still meet unaligned access in ckzg lib in SP1. Add some findings here: hackmd.io/@taik0yue/B15mxaCVC

Fixed by https://github.com/smtmfft/c-kzg-4844/pull/2

Related update in blst: https://github.com/supranational/blst/compare/master...dyxushuai:blst:master

Reopen for we still meet unaligned access in ckzg lib in SP1. Add some findings here: https://hackmd.io/@taik0yue/B15mxaCVC

Here’s the memory layout in the risc0 zkvm. We only allow guest code to use 0x400 - 0x0c00_0000 between code, stack, and heap. Within this range, the stack occupies the lowest 2 mb of this range, followed by the code, and then followed by the heap. The heap starts where the code ends and grows upward on each allocation towards 0x0c00_0000. Any address above this is illegal for the guest to access and that’s what you’re seeing here.

The address being 0xf5b6_a478 makes me think that this is either a dangling pointer or a massive allocation close to 4gb. Is there something large being allocated on the heap? Does this work as expected on non-zkvm machines? I also second @intoverflow’s advice adding those two flags to the builder.