Hints / Unconstrained Input

[matthiasgoergens]

This is an elaboration on #551

Guest's points of view

Inspired by SP1, we will give guests two functions to read unconstrained input (also knows as hints). The first is read, which reads in a value of a given type. The second is read_slice, which reads in a byte array.

pub fn read<T>() -> &'static T
where
    T: Portable + for<'a> CheckBytes<HighValidator<'a, rancor::Failure>>

pub fn read_slice() -> &'static [u8]

There are two main differences to SP1:

1. We are using rkyv instead of bincode. That's because rkyv is a lot faster, and we are already using it in sproll. The bounds on T in read reflect that.
2. We are returning references instead of copied values. That's because rkyv is zero-copy, and we want to take advantage of that.

Just like in SP1, the host has two corresponding functions to create that input: write and write_slice. From the user's point of view, they work exactly like you imagine they would.

Sidenote: in this model, the host has to prepare the input in exactly the order that the guest requests it. That approach works well for simple examples. If this inflexibility ever becomes a limiting factor, Matthias has a design to fix it. But it's probably overkill, given that the in-order approach works well enough for SP1.

Under the hood

Like in SP1, the typed read is implemented inside the guest on top of read_slice: it's just a wrapper that deals with deserialisation for you. In SP1 it's implemented exactly how you'd expect. The same for us:

pub fn read<'a, T>(&'a mut self) -> &'b T
where
    T: Portable + for<'c> CheckBytes<HighValidator<'c, Error>>,
{
    rkyv::access::<T, Error>(self.read_slice()).unwrap()
}

Sidenote: users who don't like rkyv can wrap their own favourite deserialiser around read_slice. Just like we used rkyv in sproll, even though SP1 uses bincode natively.

read_slice is a bit more involved:

At the start of the memory-mapped region for hints we store information that lets us find the byte slice for each of the items we want to read. We keep a mutable index to the next item to read, and we increment it each time read_slice is called. We then return the byte slice for that item.

Avid readers will notice that we essentially deserialise twice. The original design used rkyv for both layers, but now we code up the outer layer by hand, mostly because rkyv would prefer to pin the end of the buffer to a fixed known location, but our VM design prefers to pin the start of the buffer.

Another technical note: in general our memory-mapped-io region will be larger than the buffer rkvy needs for its serialised data. In that case, we will conceptually add arbitrary padding (eg all zeroes) to the end of the buffer.

Sidenote: SP1 mixes general RAM and memory-mapped-io. For that reason, they need some extra system calls (like hint_len) to tell the difference. We don't have that problem, so we can keep things simpler. This also has the benefit of only using functionality we already implemented for our VM.

Our design assumes that the memory-mapped-io region is read-only. That's a good idea for both performance and security anyway, but we can also tweak the design slightly to support read-write backing storage.

See #631 for a prototype implementation.

[matthiasgoergens]

Update (will fold into the main text later):

The above is meant mostly for private IO. But the special memory region we have is for public io. So we'd want to add one for private IO, too.

We can in principle use the same idea for public input, but we probably want to Merkle-ize that by default. The guest interface might look similar, but it would be rather different under the hood.

[lispc]

looks good for me. Just have one question: will there be a preset max total length of all unconstrained input? or as long as len(mem_map_io_region) + len(runtime_mem) <= mem_limit it is ok?

[matthiasgoergens]

Thanks.

What I would prefer for the simplest design is a fixed maximum size, say addresses 0x4000_0000..0x8000_0000 (excluding the end) to be really generous. But then have the prover decide dynamically how much they actually want to fill up. For technical reasons, the last address should always be fixed, the prover gets to decide the start, as in 0x8000_0000 - (1<<n) .. 0x8000_0000 in Rust range notation.

[matthiasgoergens]

To explain: You can then feed the memory region of 0x4000_0000..0x8000_0000 as a slice into rkyv's access function, no matter how much memory you actually initialised. Rkyv will start reading at the end, and won't care that some of the earlier memory hasn't been initialised, or might even be an error to access.

[hero78119]

What the layout of rkyv slices looks like when we serialized multiple (identical/diffrent) object in? I didn't find an example for that.
To expand, it will be helpful if you add this scenario in your example in https://github.com/scroll-tech/ceno/blob/matthias/ceno_host/ceno_host/src/lib.rs#L44

[matthiasgoergens]

@hero78119 Good idea, I'll flesh out the example some more.

[matthiasgoergens]

@hero78119 See test_prepare_and_consume_items in https://github.com/scroll-tech/ceno/blob/matthias/ceno_host/ceno_host/src/lib.rs

[kunxian-xia]

If I want to alloc n storage traces from hints in my guest program and n is not known at setup phase, then how many bytes does the slice have from calling read_slice() -> &'static [u8]?

[naure]

I think Kunxian you’re asking about the underlying segment reserved for private input. That can be a &[u8] with a constant len inside, or a [u8; LEN]. That’s the fixed maximum size.

From there, the guest/host have to agree on a data format; if that data contains some variable-size structures (e.g. Vec) they will encode their own sizes somehow (e.g. however rkyv does it).

[matthiasgoergens]

Looks like you are getting at what I am describing, despite my probably very confusing wording.

@naure You are really good with words, I love your PR descriptions. Feel free to improve the write-up at the top of this page, please! (Everyone else: also feel free to make improvements, please.)

[kunxian-xia]

@matthiasgoergens Do you mean just let rkyv to decide how many bytes it should return?
The host / prover will execute the program before proving to get how many bytes are needed and then use that data to init memory region? Then my question becomes:

let's say the guest program invokes read_slice() by three times? Where are these three fat pointers &[u8] stored in memory?

[matthiasgoergens]

Simplified: the three pointers are stored in the memory mapped private IO region.

Accurate: the pointers are calculated from information stored in the memory mapped private IO region. The main difference is that rkyv stores relative pointers there, and they are converted to absolute pointers on access.

The host / prover will execute the program before proving to get how many bytes are needed and then use that data to init memory region?

More or less, yes. But the host doesn't get the information from executing the guest program in this simplified model. It's just programmed with that knowledge already. See how https://github.com/scroll-tech/sproll-evm/blob/bd1b3b118be28d9b1bfbd544db60da7ef1e21223/host/src/runner.rs#L85 knows how many times to run write_slice in a loop, because it's aware of the logic that the guest program uses.

To quote myself:

Sidenote: in this model, the host has to prepare the input in exactly the order that the guest requests it. That approach works well for simple examples. If this inflexibility ever becomes a limiting factor, Matthias has a design to fix it. But it's probably overkill, given that the in-order approach works well enough for SP1.

[matthiasgoergens]

@kunxian-xia Based on feedback, I changed the layout. Now we (more-or-less) at the start of the hints memory region we store explicit pointers to the different items. Please see above.

[hero78119]

Have a question regarding e.g. read number of round in Fibonacchi and what happened under the hood, in inspired by sp1

let round = sp1_zkvm::io::read::<u32>();
sp1_zkvm::io::commit::<u32>(&round);

Does it means that round u32 data will appear in 2 place, one is public-input memory region, another is hint-data memory region?
Or if the commit call is happened, the data will be move to public-input (constrained data) memory region only?

[matthiasgoergens]

That's an exceedingly good question! For now, I only address the read part here. Let me try and whip up a design for the commit part next.

I suspect both the approaches you outlined are probably feasible (and a few more other approaches are feasible, too). Let me spend a bit of time thinking through them and work out the consequences.

[matthiasgoergens]

@hero78119 #627 is the sketch for public input. The suggestion there avoids the need for the committed values to appear multiple times.

[matthiasgoergens]

@kunxian-xia and me had a fruitful discussion about the approach outlined above that uses a prover initialised read-only memory region versus SP1's approach that mixes hints in with general read-write memory, but requires two system calls (hint_len and hint_read) to coordinate with the prover.

In SP1's system, if you want a 'hint' you first call hint_len to get the length of the hint, than you get memory of that length from the general purpose memory allocator. Crucially, that memory is uninitialised, as far as Rust is concerned. But we use some unsafe tags to tell the Rust compiler not to worry. Crucially, the prover decides what values unitialised memory starts with. So this way, the prover can pass you some private inputs. You then feed the slice of freshly allocated memory to the deserialiser of your choice. SP1 suggests bincode, but anything works.

Well, strictly speaking what I described above is enough to make the scheme work. But to make coordination between guest and host program simpler, SP1 has the hint_read system call that you can use to tell the prover where to write the hint. But there are no constraints associated with it as far as I can tell.

(A host program that knows its guest program well enough, could do without hint_read and just know how to initialise the memory. But that would be really annoying to program for.)

Our VM is different: our circuits guarantee that general read-write memory that our Rust allocator has access to comes zeroed out from the factory. On the downside, that means we need an extra memory region for the prover to leave hints in. But we get (at least) two upsides:

• Getting zero initialised memory from the allocator is essentially free. The Rust compiler is smart enough to make use of that for examples like let foo = vec![0_u32; 128 * 1024]; (but more practically releant for eg setting up hash tables).
• In our VM design, accessing read-only memory is cheaper for the prover than accessing read-write memory.

[kunxian-xia]

If memory regions are not disjoint, it's possible that ram circuits will generate two write records with same address and cycle = 0 (a, v, 0), (a, v', 0). Then the prover can manipulate the value that first load instruction gets (either v or v' works).

[hero78119]

The code you link here checks "verifier just assure stretching not exceeding in max_length for each region". It seems the verifier has not check all memory regions are disjoint, right?

Disjoin check are achieved by

• in "setup" phase, check each memory region offset + max_len not overlapping => haven't done, but easy, no verifier cost
• in verifier per proof, check hint_vars not exceed max_len by just one assertion

[kunxian-xia]

here the concept are mixed up.

I see.

[naure]

The verifier needs to make sure regions are disjoint, right?

Yes. It looks like this right now:

ceno/ceno_zkvm/src/instructions/riscv/rv32im/mmu.rs

Line 56 in 17a9d25

"memory addresses must be unique"

[matthiasgoergens]

The number of cycles to execute hint_len / hint_read is really neglible as it only need write at most three registers.

Yes, it's not about the cycles, is about having to implement yet another two syscalls. That adds to complexity of the design and increases attack surface.

[matthiasgoergens]

See #627 for public input / 'commit'.

[matthiasgoergens]

@hero78119 See #631 for the same code that's on the branch, but easier to view all the changes at once.