use crate::{
DType, Error, Matrix, OpAttribute, Result,
runtime::{BufferBinding, ComputeDispatch, KernelId, PushConstant, SemanticDispatch},
};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[repr(u32)]
pub enum MerkleAlgorithm {
Sha256 = 0,
Sha512 = 1,
Sha3_256 = 2,
Sha3_512 = 3,
Shake128 = 4,
Shake256 = 5,
Poseidon2BabyBear16 = 6,
Poseidon2BabyBear24 = 7,
Poseidon2KoalaBear16 = 8,
Poseidon2KoalaBear24 = 9,
}
impl MerkleAlgorithm {
pub const fn digest_bytes(self) -> usize {
match self {
Self::Sha256 => 32,
Self::Sha512 => 64,
Self::Sha3_256 => 32,
Self::Sha3_512 => 64,
Self::Shake128 => 32,
Self::Shake256 => 32,
Self::Poseidon2BabyBear16 => 32,
Self::Poseidon2BabyBear24 => 32,
Self::Poseidon2KoalaBear16 => 32,
Self::Poseidon2KoalaBear24 => 32,
}
}
pub const fn dtype(self) -> DType {
match self {
Self::Sha256 => DType::U8,
Self::Sha512 => DType::U8,
Self::Sha3_256 => DType::U8,
Self::Sha3_512 => DType::U8,
Self::Shake128 => DType::U8,
Self::Shake256 => DType::U8,
Self::Poseidon2BabyBear16 => DType::U32,
Self::Poseidon2BabyBear24 => DType::U32,
Self::Poseidon2KoalaBear16 => DType::U32,
Self::Poseidon2KoalaBear24 => DType::U32,
}
}
pub const fn name(self) -> &'static str {
match self {
Self::Sha256 => "sha256",
Self::Sha512 => "sha512",
Self::Sha3_256 => "sha3_256",
Self::Sha3_512 => "sha3_512",
Self::Shake128 => "shake128",
Self::Shake256 => "shake256",
Self::Poseidon2BabyBear16 => "poseidon2_babybear16",
Self::Poseidon2BabyBear24 => "poseidon2_babybear24",
Self::Poseidon2KoalaBear16 => "poseidon2_koalabear16",
Self::Poseidon2KoalaBear24 => "poseidon2_koalabear24",
}
}
}
#[derive(Clone)]
pub struct DeviceMerkleTree {
algorithm: MerkleAlgorithm,
leaf_count: u32,
levels: Vec<Matrix>,
}
impl DeviceMerkleTree {
pub const fn algorithm(&self) -> MerkleAlgorithm {
self.algorithm
}
pub const fn leaf_count(&self) -> u32 {
self.leaf_count
}
pub fn root(&self) -> &Matrix {
&self.levels[self.levels.len() - 1]
}
}
pub fn build(leaves: &Matrix, algorithm: MerkleAlgorithm) -> Result<DeviceMerkleTree> {
let [rows, elements] = match leaves.shape() {
[rows, elements] => [*rows, *elements],
_ => {
return Err(Error::invalid_argument(
"Merkle leaves require rank-two digest rows",
));
}
};
let bytes = algorithm.digest_bytes();
if leaves.dtype() != algorithm.dtype()
|| elements != bytes / leaves.dtype().size_bytes()
|| !(1..=(1_usize << 24)).contains(&rows)
{
return Err(Error::invalid_argument(
"Merkle leaves require the selected dtype/digest extent and 1..=2^24 rows",
));
}
let input_bytes = rows
.checked_mul(bytes)
.ok_or_else(|| Error::invalid_argument("Merkle input bytes overflow usize"))?;
u32::try_from(input_bytes)
.map_err(|_| Error::invalid_argument("Merkle input bytes exceed u32"))?;
let engine = leaves.engine_handle();
let leaf_count = rows as u32;
let mut levels = vec![leaves.clone()];
let mut current = leaves.clone();
let mut source_count = leaf_count;
while source_count > 1 {
let count = source_count.div_ceil(2);
let elements_count = (count as usize)
.checked_mul(elements)
.ok_or_else(|| Error::invalid_argument("Merkle output extent overflows usize"))?;
let output = Matrix::allocate_output(
engine,
vec![count as usize, elements],
elements_count,
algorithm.dtype(),
)?;
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyMerkleTreeReduceU32;
let buffers = [
BufferBinding::read(current.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(source_count),
PushConstant::U32(algorithm as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "leaf_count".into(),
value: u64::from(source_count),
},
OpAttribute::UnsignedInteger {
name: "algorithm".into(),
value: algorithm as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::merkle::MERKLE_TREE_REDUCE,
inputs: &[¤t],
outputs: &[&output],
attributes: &attributes,
},
)?;
levels.push(output.clone());
current = output;
source_count = count;
}
Ok(DeviceMerkleTree {
algorithm,
leaf_count,
levels,
})
}
pub fn subtree_roots(
leaves: &Matrix,
algorithm: MerkleAlgorithm,
subtree_leaves: usize,
) -> Result<Matrix> {
let [rows, elements] = match leaves.shape() {
[rows, elements] => [*rows, *elements],
_ => {
return Err(Error::invalid_argument(
"Merkle subtrees require rank-two digest rows",
));
}
};
if leaves.dtype() != algorithm.dtype()
|| elements != algorithm.digest_bytes() / leaves.dtype().size_bytes()
|| !(1..=(1_usize << 24)).contains(&rows)
|| !rows.is_power_of_two()
|| subtree_leaves == 0
|| !subtree_leaves.is_power_of_two()
|| subtree_leaves > rows
{
return Err(Error::invalid_argument(
"Merkle subtrees require matching digest rows and a power-of-two partition of power-of-two leaves",
));
}
let input_bytes = rows
.checked_mul(algorithm.digest_bytes())
.ok_or_else(|| Error::invalid_argument("Merkle subtree bytes overflow usize"))?;
u32::try_from(input_bytes)
.map_err(|_| Error::invalid_argument("Merkle subtree bytes exceed u32"))?;
let engine = leaves.engine_handle();
let mut current = leaves.clone();
let mut source_count = rows as u32;
for _ in 0..subtree_leaves.trailing_zeros() {
let count = source_count / 2;
let output = Matrix::allocate_output(
engine,
vec![count as usize, elements],
count as usize * elements,
algorithm.dtype(),
)?;
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyMerkleTreeReduceU32;
let buffers = [
BufferBinding::read(current.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(source_count),
PushConstant::U32(algorithm as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "leaf_count".into(),
value: u64::from(source_count),
},
OpAttribute::UnsignedInteger {
name: "algorithm".into(),
value: algorithm as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::merkle::MERKLE_TREE_REDUCE,
inputs: &[¤t],
outputs: &[&output],
attributes: &attributes,
},
)?;
current = output;
source_count = count;
}
Ok(current)
}
pub fn proofs(tree: &DeviceMerkleTree, indices: &Matrix) -> Result<Matrix> {
let rows = match indices.shape() {
[rows] => *rows,
_ => {
return Err(Error::invalid_argument(
"Merkle proof indices require rank-one U32 values",
));
}
};
let source = &tree.levels[0];
if indices.dtype() != DType::U32 || !indices.engine_handle().same_as(source.engine_handle()) {
return Err(Error::invalid_argument(
"Merkle proof indices require matching Engine ownership",
));
}
let depth = tree.levels.len() - 1;
let bytes = tree.algorithm.digest_bytes();
let frame_bytes = 20 + depth * bytes;
let elements = rows
.checked_mul(frame_bytes)
.ok_or_else(|| Error::invalid_argument("Merkle proof bytes overflow usize"))?;
u32::try_from(elements).map_err(|_| Error::invalid_argument("Merkle proof bytes exceed u32"))?;
let count =
u32::try_from(rows).map_err(|_| Error::invalid_argument("Merkle proof batch exceeds u32"))?;
let engine = source.engine_handle();
let mut frames = Matrix::allocate_output(engine, vec![rows, frame_bytes], elements, DType::U8)?;
if rows == 0 {
return Ok(frames);
}
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyMerkleFrameInitU32;
let buffers = [
BufferBinding::read(indices.storage()),
BufferBinding::write(frames.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(tree.leaf_count),
PushConstant::U32(tree.algorithm as u32),
PushConstant::U32(frame_bytes as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "leaf_count".into(),
value: u64::from(tree.leaf_count),
},
OpAttribute::UnsignedInteger {
name: "algorithm".into(),
value: tree.algorithm as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::merkle::MERKLE_FRAME_INIT,
inputs: &[indices],
outputs: &[&frames],
attributes: &attributes,
},
)?;
for level in 0..depth {
let source = &tree.levels[level];
let output = frames.reshape_semantic_output(frames.shape().to_vec())?;
let kernel = KernelId::CryptographyMerkleFrameAppendU32;
let buffers = [
BufferBinding::read(source.storage()),
BufferBinding::read(indices.storage()),
BufferBinding::read(frames.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(tree.leaf_count),
PushConstant::U32(source.shape()[0] as u32),
PushConstant::U32(tree.algorithm as u32),
PushConstant::U32(frame_bytes as u32),
PushConstant::U32(level as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "leaf_count".into(),
value: u64::from(tree.leaf_count),
},
OpAttribute::UnsignedInteger {
name: "algorithm".into(),
value: tree.algorithm as u64,
},
OpAttribute::UnsignedInteger {
name: "level".into(),
value: level as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::merkle::MERKLE_FRAME_APPEND,
inputs: &[source, indices, &frames],
outputs: &[&output],
attributes: &attributes,
},
)?;
frames = output;
}
Ok(frames)
}
pub fn verify(
leaves: &Matrix,
frames: &Matrix,
roots: &Matrix,
algorithm: MerkleAlgorithm,
leaf_count: u32,
) -> Result<Matrix> {
let [rows, elements] = match leaves.shape() {
[rows, elements] => [*rows, *elements],
_ => {
return Err(Error::invalid_argument(
"Merkle verify leaves require rank-two digest rows",
));
}
};
if !(1..=(1_u32 << 24)).contains(&leaf_count) {
return Err(Error::invalid_argument(
"Merkle trusted leaf count is outside 1..=2^24",
));
}
let depth = (leaf_count - 1).checked_ilog2().map_or(0, |n| n + 1) as usize;
let frame_bytes = 20 + depth * algorithm.digest_bytes();
if leaves.dtype() != algorithm.dtype()
|| elements != algorithm.digest_bytes() / leaves.dtype().size_bytes()
|| frames.dtype() != DType::U8
|| frames.shape() != [rows, frame_bytes]
|| roots.dtype() != algorithm.dtype()
|| roots.shape().len() != 2
|| roots.shape()[1] != elements
|| (roots.shape()[0] != 1 && roots.shape()[0] != rows)
|| !leaves.engine_handle().same_as(frames.engine_handle())
|| !leaves.engine_handle().same_as(roots.engine_handle())
{
return Err(Error::invalid_argument(
"Merkle verify requires matching hash extents, version-two frames and Engine ownership",
));
}
let count =
u32::try_from(rows).map_err(|_| Error::invalid_argument("Merkle verify batch exceeds u32"))?;
let input_bytes = rows
.checked_mul(frame_bytes)
.ok_or_else(|| Error::invalid_argument("Merkle verify byte extent overflows usize"))?;
u32::try_from(input_bytes)
.map_err(|_| Error::invalid_argument("Merkle verify bytes exceed u32"))?;
let engine = leaves.engine_handle();
let output = Matrix::allocate_output(engine, vec![rows], rows, DType::U32)?;
if count != 0 {
let groups = engine.linear_dispatch_grid(count, 128)?;
let kernel = KernelId::CryptographyMerkleFrameVerifyU32;
let buffers = [
BufferBinding::read(leaves.storage()),
BufferBinding::read(frames.storage()),
BufferBinding::read(roots.storage()),
BufferBinding::write(output.storage()),
];
let push_constants = [
PushConstant::U32(count),
PushConstant::U32(groups[0] * 128),
PushConstant::U32(leaf_count),
PushConstant::U32(algorithm as u32),
PushConstant::U32(frame_bytes as u32),
PushConstant::U32(roots.shape()[0] as u32),
];
let attributes = [
OpAttribute::UnsignedInteger {
name: "leaf_count".into(),
value: u64::from(leaf_count),
},
OpAttribute::UnsignedInteger {
name: "algorithm".into(),
value: algorithm as u64,
},
];
engine.record_semantic(
ComputeDispatch {
kernel,
buffers: &buffers,
push_constants: &push_constants,
workgroups: groups,
},
SemanticDispatch {
contract: crate::core::operation::cryptography::merkle::MERKLE_FRAME_VERIFY,
inputs: &[leaves, frames, roots],
outputs: &[&output],
attributes: &attributes,
},
)?;
}
Ok(output)
}