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: &mut 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: &mut 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>(
87    reader: &mut NargReader<'_>,
88) -> Result<[FieldVar; W], InvalidRelation> {
89    let mut vars = [FieldVar::ZERO; W];
90    for var in &mut vars {
91        *var = read_var(reader)?;
92    }
93    Ok(vars)
94}
95
96fn read_unit<T: FromNarg>(reader: &mut NargReader<'_>) -> Result<T, InvalidRelation> {
97    reader
98        .read::<T>()
99        .map_err(|VerificationError| malformed("unit value"))
100}
101
102/// Reads and checks a header, returning the label for an instance.
103fn read_header<T: Unit + Encoding>(
104    reader: &mut NargReader<'_>,
105    magic: [u8; 4],
106    width: usize,
107    with_label: bool,
108) -> Result<String, InvalidRelation> {
109    let found: [u8; 4] = reader
110        .take_array()
111        .map_err(|VerificationError| malformed("magic"))?;
112    if found != magic {
113        return Err(malformed("wrong magic"));
114    }
115    let version: [u8; 1] = reader
116        .take_array()
117        .map_err(|VerificationError| malformed("version"))?;
118    if version[0] != VERSION {
119        return Err(malformed("unsupported version"));
120    }
121    if read_u32(reader, "width")? != width {
122        return Err(malformed("width does not match the type"));
123    }
124    if read_u32(reader, "unit length")? != unit_len::<T>() {
125        return Err(malformed("unit length does not match the type"));
126    }
127    if !with_label {
128        return Ok(String::new());
129    }
130    let label_len = read_u32(reader, "label length")?;
131    let label = reader
132        .take(label_len)
133        .map_err(|VerificationError| malformed("label"))?;
134    String::from_utf8(label.to_vec()).map_err(|_| malformed("label is not UTF-8"))
135}
136
137impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> PermutationInstance<T, WIDTH> {
138    /// The canonical byte encoding of this instance.
139    pub fn to_bytes(&self) -> Vec<u8> {
140        let unit_len = unit_len::<T>();
141        let mut out = Vec::new();
142        out.extend_from_slice(&INSTANCE_MAGIC);
143        out.push(VERSION);
144        put_u32(&mut out, WIDTH);
145        put_u32(&mut out, unit_len);
146        put_u32(&mut out, self.label.len());
147        out.extend_from_slice(self.label.as_bytes());
148        put_u32(&mut out, self.vars_count);
149        put_u32(&mut out, self.public_values.len());
150        for (var, value) in &self.public_values {
151            put_u32(&mut out, var.index());
152            put_unit(&mut out, value, unit_len);
153        }
154        put_u32(&mut out, self.queries.len());
155        for query in &self.queries {
156            put_vars(&mut out, &query.input);
157            put_vars(&mut out, &query.output);
158        }
159        put_u32(&mut out, self.equations.len());
160        for equation in &self.equations {
161            put_u32(&mut out, equation.terms.terms().len());
162            for term in equation.terms.terms() {
163                put_u32(&mut out, term.var.index());
164                put_unit(&mut out, &term.weight, unit_len);
165            }
166            put_unit(&mut out, &equation.image, unit_len);
167        }
168        out
169    }
170
171    /// Parses [`Self::to_bytes`], running the same checks as
172    /// [`PermutationRelation::compile`][crate::PermutationRelation::compile].
173    pub fn from_bytes(bytes: &[u8]) -> Result<Self, InvalidRelation> {
174        let mut reader = NargReader::new(bytes);
175        let instance = Self::read(&mut reader)?;
176        if !reader.is_empty() {
177            return Err(malformed("trailing bytes"));
178        }
179        Ok(instance)
180    }
181
182    fn read(reader: &mut NargReader<'_>) -> Result<Self, InvalidRelation> {
183        let label = read_header::<T>(reader, INSTANCE_MAGIC, WIDTH, true)?;
184        let vars_count = read_u32(reader, "variable count")?;
185        let n_public = read_u32(reader, "public count")?;
186        let mut public_values = Vec::new();
187        for _ in 0..n_public {
188            let var = read_var(reader)?;
189            let value = read_unit::<T>(reader)?;
190            public_values.push((var, value));
191        }
192        let n_queries = read_u32(reader, "query count")?;
193        let mut queries = Vec::new();
194        for _ in 0..n_queries {
195            let input = read_vars::<WIDTH>(reader)?;
196            let output = read_vars::<WIDTH>(reader)?;
197            queries.push(QueryAnswerPair::new(input, output));
198        }
199        let n_equations = read_u32(reader, "equation count")?;
200        let mut equations = Vec::new();
201        for _ in 0..n_equations {
202            let n_terms = read_u32(reader, "term count")?;
203            let mut terms = Vec::new();
204            for _ in 0..n_terms {
205                let var = read_var(reader)?;
206                let weight = read_unit::<T>(reader)?;
207                terms.push(Weighted { var, weight });
208            }
209            let image = read_unit::<T>(reader)?;
210            equations.push(LinearEquation::new(
211                terms.into_iter().collect::<Sum<T>>(),
212                image,
213            ));
214        }
215        let public_sorted = public_values
216            .windows(2)
217            .all(|pair| pair[0].0.index() < pair[1].0.index());
218        if !public_sorted {
219            return Err(malformed("public wires must be strictly increasing"));
220        }
221        Self::validated(label, vars_count, public_values, queries, equations)
222    }
223
224    /// The 32-byte digest of [`Self::to_bytes`], for binding the statement
225    /// into a transcript.
226    pub fn digest(&self) -> [u8; 32] {
227        let session_id = derive_session_id::<DefaultHash>(DIGEST_TAG);
228        let mut sponge = DefaultHash::init(session_id.as_bytes());
229        sponge.absorb(&self.to_bytes());
230        let mut out = [0u8; 32];
231        sponge.squeeze(&mut out);
232        out
233    }
234}
235
236impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> Encoding
237    for PermutationInstance<T, WIDTH>
238{
239    fn encode(&self) -> impl AsRef<[u8]> {
240        self.to_bytes()
241    }
242}
243
244impl<T: Unit + Encoding + FromNarg + PartialEq, const WIDTH: usize> FromNarg
245    for PermutationInstance<T, WIDTH>
246{
247    fn from_narg(reader: &mut NargReader<'_>) -> Result<Self, VerificationError> {
248        Self::read(reader).map_err(|_| VerificationError)
249    }
250}
251
252impl<T: Unit + Encoding + FromNarg, const WIDTH: usize> PermutationWitness<T, WIDTH> {
253    /// The canonical byte encoding of this witness.
254    pub fn to_bytes(&self) -> Vec<u8> {
255        let unit_len = unit_len::<T>();
256        let mut out = Vec::new();
257        out.extend_from_slice(&WITNESS_MAGIC);
258        out.push(VERSION);
259        put_u32(&mut out, WIDTH);
260        put_u32(&mut out, unit_len);
261        put_u32(&mut out, self.trace.len());
262        for step in &self.trace {
263            for value in step.input.iter().chain(&step.output) {
264                put_unit(&mut out, value, unit_len);
265            }
266        }
267        out
268    }
269
270    /// Parses [`Self::to_bytes`].
271    pub fn from_bytes(bytes: &[u8]) -> Result<Self, InvalidRelation> {
272        let mut reader = NargReader::new(bytes);
273        read_header::<T>(&mut reader, WITNESS_MAGIC, WIDTH, false)?;
274        let n_steps = read_u32(&mut reader, "step count")?;
275        let mut trace = Vec::new();
276        for _ in 0..n_steps {
277            let mut input = core::array::from_fn(|_| T::ZERO);
278            let mut output = core::array::from_fn(|_| T::ZERO);
279            for value in input.iter_mut().chain(&mut output) {
280                *value = read_unit::<T>(&mut reader)?;
281            }
282            trace.push(QueryAnswerPair::new(input, output));
283        }
284        if !reader.is_empty() {
285            return Err(malformed("trailing bytes"));
286        }
287        Ok(Self { trace })
288    }
289}
spongefish_circuit/encoding.rs

spongefish_circuit/
encoding.rs
