spongefish_circuit/
encoding.rs

1//! The byte encoding of an instance and of a witness: the statement as a
2//! string, for a proof system in any language to read.
3//!
4//! Both encodings are versioned, little-endian, and prefix-free, so an
5//! instance can also be absorbed into a transcript as it is. Every list is
6//! preceded by its `u32` length and every wire is a `u32` index. Values of
7//! the unit type `T` are written with their spongefish [`Encoding`], and the
8//! header records their width so that a reader need not know `T`.
9//!
10//! ```text
11//! instance  "SFRI" u8:1 u32:width u32:unit_len u32:label_len label
12//!           u32:vars_count
13//!           u32:n_public  { u32:var  T:value }*
14//!           u32:n_queries { u32:var*width (input) u32:var*width (output) }*
15//!           u32:n_equations { u32:n_terms { u32:var T:weight }* T:image }*
16//! witness   "SFRW" u8:1 u32:width u32:unit_len
17//!           u32:n_steps { T*width (input) T*width (output) }*
18//! ```
19
20use alloc::{format, string::String, vec::Vec};
21
22use spongefish::{
23    derive_session_id, DefaultHash, DuplexSpongeInit, DuplexSpongeInterface, Encoding, FromNarg,
24    NargReader, Unit, VerificationError,
25};
26
27use crate::{
28    allocator::FieldVar,
29    error::InvalidRelation,
30    expr::{Sum, Weighted},
31    permutation::{LinearEquation, PermutationInstance, PermutationWitness, QueryAnswerPair},
32};
33
34/// The four bytes every encoded instance starts with.
35pub const INSTANCE_MAGIC: [u8; 4] = *b"SFRI";
36/// The four bytes every encoded witness starts with.
37pub const WITNESS_MAGIC: [u8; 4] = *b"SFRW";
38/// The encoding version this crate writes and reads.
39pub const VERSION: u8 = 1;
40
41/// The tag [`PermutationInstance::digest`] derives its session identifier from.
42pub const DIGEST_TAG: &[u8] = b"spongefish-circuit/instance/v1";
43
44/// The width, in bytes, of one encoded unit.
45fn unit_len<T: Unit + Encoding>() -> usize {
46    T::ZERO.encode().as_ref().len()
47}
48
49fn put_u32(out: &mut Vec<u8>, value: usize) {
50    let value = u32::try_from(value).expect("relation sizes fit in u32");
51    out.extend_from_slice(&value.to_le_bytes());
52}
53
54fn put_unit<T: Encoding>(out: &mut Vec<u8>, value: &T, unit_len: usize) {
55    let encoded = value.encode();
56    assert_eq!(
57        encoded.as_ref().len(),
58        unit_len,
59        "units must have a fixed-width encoding"
60    );
61    out.extend_from_slice(encoded.as_ref());
62}
63
64fn put_vars<const W: usize>(out: &mut Vec<u8>, vars: &[FieldVar; W]) {
65    for var in vars {
66        put_u32(out, var.index());
67    }
68}
69
70fn malformed(what: &str) -> InvalidRelation {
71    InvalidRelation::new(format!("malformed encoding: {what}"))
72}
73
74fn read_u32(reader: &NargReader<'_>, what: &str) -> Result<usize, InvalidRelation> {
75    reader
76        .read::<u32>()
77        .map(|value| value as usize)
78        .map_err(|VerificationError| malformed(what))
79}
80
81fn read_var(reader: &NargReader<'_>) -> Result<FieldVar, InvalidRelation> {
82    let index = read_u32(reader, "wire index")?;
83    FieldVar::try_from_index(index).ok_or_else(|| malformed("wire index out of range"))
84}
85
86fn read_vars<const W: usize>(reader: &NargReader<'_>) -> Result<[FieldVar; W], InvalidRelation> {
87    let mut vars = [FieldVar::ZERO; W];
88    for var in &mut vars {
89        *var = read_var(reader)?;
90    }
91    Ok(vars)
92}
93
94fn read_unit<T: FromNarg>(reader: &NargReader<'_>) -> Result<T, InvalidRelation> {
95    reader
96        .read::<T>()
97        .map_err(|VerificationError| malformed("unit value"))
98}
99
100/// Read and check a header, returning the label for an instance.
101fn read_header<T: Unit + Encoding>(
102    reader: &NargReader<'_>,
103    magic: [u8; 4],
104    width: usize,
105    with_label: bool,
106) -> Result<String, InvalidRelation> {
107    let found: [u8; 4] = reader
108        .take_array()
109        .map_err(|VerificationError| malformed("magic"))?;
110    if found != magic {
111        return Err(malformed("wrong magic"));
112    }
113    let version: [u8; 1] = reader
114        .take_array()
115        .map_err(|VerificationError| malformed("version"))?;
116    if version[0] != VERSION {
117        return Err(malformed("unsupported version"));
118    }
119    if read_u32(reader, "width")? != width {
120        return Err(malformed("width does not match the type"));
121    }
122    if read_u32(reader, "unit length")? != unit_len::<T>() {
123        return Err(malformed("unit length does not match the type"));
124    }
125    if !with_label {
126        return Ok(String::new());
127    }
128    let label_len = read_u32(reader, "label length")?;
129    let label = reader
130        .take(label_len)
131        .map_err(|VerificationError| malformed("label"))?;
132    String::from_utf8(label.to_vec()).map_err(|_| malformed("label is not UTF-8"))
133}
134
135impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> PermutationInstance<T, WIDTH> {
136    /// The canonical byte encoding of this instance.
137    pub fn to_bytes(&self) -> Vec<u8> {
138        let unit_len = unit_len::<T>();
139        let mut out = Vec::new();
140        out.extend_from_slice(&INSTANCE_MAGIC);
141        out.push(VERSION);
142        put_u32(&mut out, WIDTH);
143        put_u32(&mut out, unit_len);
144        put_u32(&mut out, self.label.len());
145        out.extend_from_slice(self.label.as_bytes());
146        put_u32(&mut out, self.vars_count);
147        put_u32(&mut out, self.public_values.len());
148        for (var, value) in &self.public_values {
149            put_u32(&mut out, var.index());
150            put_unit(&mut out, value, unit_len);
151        }
152        put_u32(&mut out, self.queries.len());
153        for query in &self.queries {
154            put_vars(&mut out, &query.input);
155            put_vars(&mut out, &query.output);
156        }
157        put_u32(&mut out, self.equations.len());
158        for equation in &self.equations {
159            put_u32(&mut out, equation.terms.terms().len());
160            for term in equation.terms.terms() {
161                put_u32(&mut out, term.var.index());
162                put_unit(&mut out, &term.weight, unit_len);
163            }
164            put_unit(&mut out, &equation.image, unit_len);
165        }
166        out
167    }
168
169    /// Parse [`Self::to_bytes`], running the same checks as
170    /// [`PermutationRelation::compile`][crate::PermutationRelation::compile].
171    pub fn from_bytes(bytes: &[u8]) -> Result<Self, InvalidRelation> {
172        let reader = NargReader::new(bytes);
173        let instance = Self::read(&reader)?;
174        if !reader.is_empty() {
175            return Err(malformed("trailing bytes"));
176        }
177        Ok(instance)
178    }
179
180    fn read(reader: &NargReader<'_>) -> Result<Self, InvalidRelation> {
181        let label = read_header::<T>(reader, INSTANCE_MAGIC, WIDTH, true)?;
182        let vars_count = read_u32(reader, "variable count")?;
183        let n_public = read_u32(reader, "public count")?;
184        let mut public_values = Vec::new();
185        for _ in 0..n_public {
186            let var = read_var(reader)?;
187            let value = read_unit::<T>(reader)?;
188            public_values.push((var, value));
189        }
190        let n_queries = read_u32(reader, "query count")?;
191        let mut queries = Vec::new();
192        for _ in 0..n_queries {
193            let input = read_vars::<WIDTH>(reader)?;
194            let output = read_vars::<WIDTH>(reader)?;
195            queries.push(QueryAnswerPair::new(input, output));
196        }
197        let n_equations = read_u32(reader, "equation count")?;
198        let mut equations = Vec::new();
199        for _ in 0..n_equations {
200            let n_terms = read_u32(reader, "term count")?;
201            let mut terms = Vec::new();
202            for _ in 0..n_terms {
203                let var = read_var(reader)?;
204                let weight = read_unit::<T>(reader)?;
205                terms.push(Weighted { var, weight });
206            }
207            let image = read_unit::<T>(reader)?;
208            equations.push(LinearEquation::new(
209                terms.into_iter().collect::<Sum<T>>(),
210                image,
211            ));
212        }
213        let public_sorted = public_values
214            .windows(2)
215            .all(|pair| pair[0].0.index() < pair[1].0.index());
216        if !public_sorted {
217            return Err(malformed("public wires must be strictly increasing"));
218        }
219        Self::validated(label, vars_count, public_values, queries, equations)
220    }
221
222    /// The 32-byte digest of [`Self::to_bytes`], for binding the statement
223    /// into a transcript.
224    pub fn digest(&self) -> [u8; 32] {
225        let session_id = derive_session_id::<DefaultHash>(DIGEST_TAG);
226        let mut sponge = DefaultHash::init(session_id.as_bytes());
227        sponge.absorb(&self.to_bytes());
228        let mut out = [0u8; 32];
229        sponge.squeeze(&mut out);
230        out
231    }
232}
233
234impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> Encoding
235    for PermutationInstance<T, WIDTH>
236{
237    fn encode(&self) -> impl AsRef<[u8]> {
238        self.to_bytes()
239    }
240}
241
242impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> FromNarg
243    for PermutationInstance<T, WIDTH>
244{
245    fn from_narg(reader: &NargReader<'_>) -> Result<Self, VerificationError> {
246        Self::read(reader).map_err(|_| VerificationError)
247    }
248}
249
250impl<T: Unit + Encoding + FromNarg, const WIDTH: usize> PermutationWitness<T, WIDTH> {
251    /// The canonical byte encoding of this witness.
252    pub fn to_bytes(&self) -> Vec<u8> {
253        let unit_len = unit_len::<T>();
254        let mut out = Vec::new();
255        out.extend_from_slice(&WITNESS_MAGIC);
256        out.push(VERSION);
257        put_u32(&mut out, WIDTH);
258        put_u32(&mut out, unit_len);
259        put_u32(&mut out, self.trace.len());
260        for step in &self.trace {
261            for value in step.input.iter().chain(&step.output) {
262                put_unit(&mut out, value, unit_len);
263            }
264        }
265        out
266    }
267
268    /// Parse [`Self::to_bytes`].
269    pub fn from_bytes(bytes: &[u8]) -> Result<Self, InvalidRelation> {
270        let reader = NargReader::new(bytes);
271        read_header::<T>(&reader, WITNESS_MAGIC, WIDTH, false)?;
272        let n_steps = read_u32(&reader, "step count")?;
273        let mut trace = Vec::new();
274        for _ in 0..n_steps {
275            let mut input = core::array::from_fn(|_| T::ZERO);
276            let mut output = core::array::from_fn(|_| T::ZERO);
277            for value in input.iter_mut().chain(&mut output) {
278                *value = read_unit::<T>(&reader)?;
279            }
280            trace.push(QueryAnswerPair::new(input, output));
281        }
282        if !reader.is_empty() {
283            return Err(malformed("trailing bytes"));
284        }
285        Ok(Self { trace })
286    }
287}
spongefish_circuit/encoding.rs

spongefish_circuit/
encoding.rs
