1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
use super::{
chiplets::hasher::{self, Digest},
utils::{
collections::{BTreeMap, Vec},
Box,
},
Felt, Operation,
};
use core::fmt;
use winter_utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
pub mod blocks;
use blocks::CodeBlock;
mod info;
pub use info::ProgramInfo;
#[cfg(test)]
mod tests;
// PROGRAM
// ================================================================================================
/// A program which can be executed by the VM.
///
/// A program is described by a Merkelized Abstract Syntax Tree (MAST), where each node is a
/// [CodeBlock]. Internal nodes describe control flow semantics of the program, while leaf nodes
/// contain linear sequences of instructions which contain no control flow.
#[derive(Clone, Debug)]
pub struct Program {
root: CodeBlock,
kernel: Kernel,
cb_table: CodeBlockTable,
}
impl Program {
// CONSTRUCTORS
// --------------------------------------------------------------------------------------------
/// Instantiates a new [Program] from the specified code block.
pub fn new(root: CodeBlock) -> Self {
Self::with_kernel(root, Kernel::default(), CodeBlockTable::default())
}
/// Instantiates a new [Program] from the specified code block and associated code block table.
pub fn with_kernel(root: CodeBlock, kernel: Kernel, cb_table: CodeBlockTable) -> Self {
Self {
root,
kernel,
cb_table,
}
}
// PUBLIC ACCESSORS
// --------------------------------------------------------------------------------------------
/// Returns the root code block of this program.
pub fn root(&self) -> &CodeBlock {
&self.root
}
/// Returns a hash of this program.
pub fn hash(&self) -> Digest {
self.root.hash()
}
/// Returns a kernel for this program.
pub fn kernel(&self) -> &Kernel {
&self.kernel
}
/// Returns code block table for this program.
pub fn cb_table(&self) -> &CodeBlockTable {
&self.cb_table
}
}
impl fmt::Display for Program {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "begin {} end", self.root)
}
}
// CODE BLOCK TABLE
// ================================================================================================
/// A map of code block hashes to their underlying code blocks.
///
/// This table is used to hold code blocks which are referenced from the program MAST but are
/// actually not a part of the MAST itself. Thus, for example, multiple nodes in the MAST can
/// reference the same code block in the table.
#[derive(Clone, Debug, Default)]
pub struct CodeBlockTable(BTreeMap<[u8; 32], CodeBlock>);
impl CodeBlockTable {
/// Returns a code block for the specified hash, or None if the code block is not present
/// in this table.
pub fn get(&self, hash: Digest) -> Option<&CodeBlock> {
let key: [u8; 32] = hash.into();
self.0.get(&key)
}
/// Returns true if a code block with the specified hash is present in this table.
pub fn has(&self, hash: Digest) -> bool {
let key: [u8; 32] = hash.into();
self.0.contains_key(&key)
}
/// Inserts the provided code block into this table.
pub fn insert(&mut self, block: CodeBlock) {
let key: [u8; 32] = block.hash().into();
self.0.insert(key, block);
}
/// Returns true if this code block table is empty.
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
}
// KERNEL
// ================================================================================================
/// A list of procedure hashes defining a VM kernel.
///
/// The internally-stored list always has a consistent order, regardless of the order of procedure
/// list used to instantiate a kernel.
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct Kernel(Vec<Digest>);
impl Kernel {
/// Returns a new [Kernel] instantiated with the specified procedure hashes.
pub fn new(proc_hashes: &[Digest]) -> Self {
// make sure procedure roots are ordered consistently
let mut hash_map: BTreeMap<[u8; 32], Digest> = BTreeMap::new();
proc_hashes.iter().cloned().for_each(|r| {
hash_map.insert(r.into(), r);
});
Self(hash_map.values().copied().collect())
}
/// Returns true if this kernel does not contain any procedures.
pub fn is_empty(&self) -> bool {
self.0.is_empty()
}
/// Returns true if a procedure with the specified hash belongs to this kernel.
pub fn contains_proc(&self, proc_hash: Digest) -> bool {
// linear search here is OK because we expect the kernels to have a relatively small number
// of procedures (e.g., under 100)
self.0.iter().any(|&h| h == proc_hash)
}
/// Returns a list of procedure hashes contained in this kernel.
pub fn proc_hashes(&self) -> &[Digest] {
&self.0
}
}
// this is required by AIR as public inputs will be serialized with the proof
impl Serializable for Kernel {
fn write_into<W: ByteWriter>(&self, target: &mut W) {
// TODO the serialization of MAST will not support values greater than `u16::MAX`, so we
// reflect the same restriction here. however, this should be tweaked in the future. This
// value will likely be capped to `u8::MAX`.
debug_assert!(self.0.len() <= u16::MAX as usize);
target.write_u16(self.0.len() as u16);
Digest::write_batch_into(&self.0, target)
}
}
impl Deserializable for Kernel {
fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
let len = source.read_u16()?;
let kernel = (0..len).map(|_| source.read::<Digest>()).collect::<Result<_, _>>()?;
Ok(Self(kernel))
}
}