Skip to content
Snippets Groups Projects

Draft: Doc joss

Closed Draft: Doc joss
doc-joss into main
Closed PERENNOU Tanguy requested to merge doc-joss into main
Viewing commit 8de24aba
Prev Next
Show latest version
1 file
+ 270
− 155
Compare changes
  • Side-by-side
  • Inline
src/semi_avid.rs
+ 270
− 155
//! Semi-AVID: a proving scheme suited for an _information dispersal_ context
//!
//! In their paper, [Nazirkhanova et al.](https://arxiv.org/abs/2111.12323) introduce a new proving
//! scheme.
//! In their paper, [Nazirkhanova et al.](https://arxiv.org/abs/2111.12323)
//! introduce a new proving scheme.
//!
//! In opposition to how it is commonly done in protocols such as
//! [KZG](https://link.springer.com/chapter/10.1007/978-3-642-17373-8_11), the data is interpreted
//! as column-oriented polynomials.
//! [KZG](https://link.springer.com/chapter/10.1007/978-3-642-17373-8_11), the
//! data is interpreted as column-oriented polynomials.
//!
//! Using FEC notations, there are $k$ such column-oriented polynomials, i.e. the $k$ source shards.
//! They are all commited using a common trusted setup and these $k$ commitments are used to prove
//! the integrity of encoded shards.
//! Using FEC notations, there are $k$ such column-oriented polynomials, i.e.
//! the $k$ source shards. They are all commited using a common trusted setup
//! and these $k$ commitments are used to prove the integrity of encoded shards.
//!
//! In order to verify this property, i.e. that a given shard has been computed as a linear
//! combination of the $k$ source shards, the _homomorphic_ property of the commit operation is
//! used: _the commitment of a linear combination of polynomials is equal to the same linear
//! combination of the commiments of the same polynomials_.
//! In order to verify this property, i.e. that a given shard has been computed
//! as a linear combination of the $k$ source shards, the _homomorphic_ property
//! of the commit operation is used: _the commitment of a linear combination of
//! polynomials is equal to the same linear combination of the commiments of the
//! same polynomials_.
//!
//! This give us a simple, lightweight and fast commitment scheme.
//! This gives us a simple, lightweight and fast commitment scheme.
//!
//! # Examples
//!
//! # Example
//! > **Note**
//! >
//! > below, `F`, `G` and `DP<F>` are explicitely specified everywhere but, in _real_ code, i.e.
//! > using generic types as it's commonly done in Arkworks, it should be possible to specify them
//! > once and Rust will take care of _carrying_ the types in the rest of the code. Also, `DP<F>`
//! > will likely be its own generic type, usually written `P` in this code base.
//! > below, `F`, `G` and `DP<F>` are explicitely specified everywhere but, in
//! > _real_ code, i.e. using generic types as it's commonly done in Arkworks,
//! > it should be possible to specify them once and Rust will take care of
//! > _carrying_ the types in the rest of the code. Also, `DP<F>` will likely be
//! > its own generic type, usually written `P` in this code base.
//! >
//! > see the Semi-AVID example for a fully-typed code.
//!
//! ## Basic usage
//!
//! - first, let's import some types...
//! ```
//! use ark_bls12_381::{Fr as F, G1Projective as G};
//! use ark_poly::univariate::DensePolynomial as DP;
//! ```
//! - and setup the input data
//! - let's define system parameters $k$ and $n$, as well as some input data
//! ```
//! # fn main() {
//! let mut rng = ark_std::test_rng();
//!
//! let (k, n) = (3, 6_usize);
//! let bytes = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! let (k, n) = (3, 6);
//! let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! # }
//! ```
//! - then, Semi-AVID requires a trusted setup to prove and verify
//! - then, Semi-AVID requires a well-dimensioned trusted setup to prove and
//! verify data integrity
//! ```
//! # use ark_bls12_381::{Fr as F, G1Projective as G};
//! # fn main() {
//! # let mut rng = ark_std::test_rng();
//! #
//! # let (k, n) = (3, 6_usize);
//! # let bytes = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! # fn main() {
//! # let (k, n) = (3, 6);
//! # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! let powers = komodo::zk::setup::<F, G>(bytes.len(), &mut rng).unwrap();
//! // minimum size of trusted setup; larger numbers also work, e.g. nb = data.len()
//! let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
//! let mut rng = ark_std::test_rng();
//! let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
//! # }
//! ```
//! - we can now build an encoding matrix, encode the data, prove the shards and build [`Block`]s
//! - we can now build an encoding matrix (here, a random one), encode the data
//! into shards, [`prove`] the data and [`build`] [`Block`]s using the encoded
//! shards and the proof
//! ```
//! # use ark_bls12_381::{Fr as F, G1Projective as G};
//! # use ark_poly::univariate::DensePolynomial as DP;
//! #
//! # use komodo::semi_avid::{build, prove, verify};
//! # use komodo::semi_avid::{build, prove};
//! #
//! # fn main() {
//! # let mut rng = ark_std::test_rng();
//! #
//! # let (k, n) = (3, 6_usize);
//! # let bytes = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! # let (k, n) = (3, 6);
//! # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! # let powers = komodo::zk::setup::<F, G>(bytes.len(), &mut rng).unwrap();
//! # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
//! # let mut rng = ark_std::test_rng();
//! # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
//! #
//! let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
//! let shards = komodo::fec::encode(&bytes, encoding_mat).unwrap();
//! let proof = prove::<F, G, DP<F>>(&bytes, &powers, encoding_mat.height).unwrap();
//! let encoding_mat = &komodo::algebra::linalg::Matrix::<F>::random(k, n, &mut rng);
//! let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
//! let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
//! let blocks = build::<F, G, DP<F>>(&shards, &proof);
//! # }
//! ```
//! - finally, each [`Block`] can be verified individually
//! - and we can [`verify`] the integrity of each [`Block`] individually before
//! decoding the data
//! ```
//! # use ark_bls12_381::{Fr as F, G1Projective as G};
//! # use ark_poly::univariate::DensePolynomial as DP;
@@ -83,24 +91,26 @@
//! # use komodo::semi_avid::{build, prove, verify};
//! #
//! # fn main() {
//! # let mut rng = ark_std::test_rng();
//! #
//! # let (k, n) = (3, 6_usize);
//! # let bytes = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! # let (k, n) = (3, 6);
//! # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! # let powers = komodo::zk::setup::<F, G>(bytes.len(), &mut rng).unwrap();
//! # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
//! # let mut rng = ark_std::test_rng();
//! # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
//! #
//! # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
//! # let shards = komodo::fec::encode(&bytes, encoding_mat).unwrap();
//! # let proof = prove::<F, G, DP<F>>(&bytes, &powers, encoding_mat.height).unwrap();
//! # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
//! # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
//! # let blocks = build::<F, G, DP<F>>(&shards, &proof);
//! #
//! for block in &blocks {
//! assert!(verify::<F, G, DP<F>>(block, &powers).unwrap());
//! let verif = verify::<F, G, DP<F>>(block, &powers).unwrap();
//! assert_eq!(verif, true);
//! }
//! # }
//! ```
//! - and decoded using any $k$ of the shards
//! - finally, we can decode the data using any $k$ of the encoded shards (here,
//! we use the shards in the first $k$ blocks)
//! ```
//! # use ark_bls12_381::{Fr as F, G1Projective as G};
//! # use ark_poly::univariate::DensePolynomial as DP;
@@ -108,31 +118,76 @@
//! # use komodo::semi_avid::{build, prove};
//! #
//! # fn main() {
//! # let mut rng = ark_std::test_rng();
//! # let (k, n) = (3, 6);
//! # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! # let (k, n) = (3, 6_usize);
//! # let bytes = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! # let powers = komodo::zk::setup::<F, G>(bytes.len(), &mut rng).unwrap();
//! # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
//! # let mut rng = ark_std::test_rng();
//! # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
//! #
//! # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
//! # let shards = komodo::fec::encode(&bytes, encoding_mat).unwrap();
//! # let proof = prove::<F, G, DP<F>>(&bytes, &powers, encoding_mat.height).unwrap();
//! # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
//! # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
//! # let blocks = build::<F, G, DP<F>>(&shards, &proof);
//! #
//! let shards = blocks[0..k].iter().cloned().map(|b| b.shard).collect();
//! assert_eq!(bytes, komodo::fec::decode(shards).unwrap());
//! let decoded = komodo::fec::decode(shards).unwrap();
//! assert_eq!(decoded, data);
//! # }
//! ```
//!
//! # Recoding
//! By constrution, Semi-AVID supports an operation on shards known as _recoding_. This allows to
//! combine an arbitrary number of shards together on the fly, without decoding the data and then
//! ## Recoding
//!
//! By construction, Semi-AVID supports an operation on shards known as
//! _recoding_. The [`recode`] operation allows to combine an arbitrary number
//! of shards together on the fly, without decoding the data and then
//! re-encoding brand new shards.
//!
//! This is great because any node in the system can locally augment its local pool of shards.
//! However, this operation will introduce linear dependencies between recoded shards and their
//! _parents_, which might decrease the diversity of shards and harm the decoding process.
//! This is great because any node in the system can locally augment its local
//! pool of shards.
//!
//! Here is an example of how to recode a block using the first two blocks, and
//! make use of the recoded block to decode the data.
//!
//! ```rust
//! # use ark_bls12_381::{Fr as F, G1Projective as G};
//! # use ark_poly::univariate::DensePolynomial as DP;
//! #
//! # use komodo::semi_avid::{build, prove, verify, recode};
//! #
//! # fn main() {
//! # let (k, n) = (3, 6);
//! # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
//! #
//! # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
//! # let mut rng = ark_std::test_rng();
//! # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
//! #
//! # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
//! # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
//! # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
//! # let blocks = build::<F, G, DP<F>>(&shards, &proof);
//! #
//! // recode using the first two blocks
//! let subset = [blocks[0].clone(), blocks[1].clone()];
//! let block01 = recode(&subset, &mut rng).unwrap().unwrap();
//!
//! // verify the recoded block
//! let verif = verify::<F, G, DP<F>>(&block01, &powers).unwrap();
//! assert_eq!(verif, true);
//!
//! // decode data with the recoded block and blocks #4 and #5
//! let shards = vec![block01.shard.clone(), blocks[4].shard.clone(), blocks[5].shard.clone()];
//! let decoded_data = komodo::fec::decode(shards).unwrap();
//! assert_eq!(decoded_data, data);
//! # }
//! ```
//!
//! > **Warning**
//! >
//! > The [`recode`] operation introduces linear dependencies between recoded
//! > shards and their _parents_, which might decrease the diversity of shards
//! > and harm the decoding process.
use ark_ec::CurveGroup;
use ark_ff::PrimeField;
use ark_poly::DenseUVPolynomial;
@@ -210,44 +265,55 @@ impl<F: PrimeField, G: CurveGroup<ScalarField = F>> std::fmt::Display for Block<
/// Compute a recoded block from an arbitrary set of blocks.
///
/// Coefficients will be drawn at random, one for each block. Blocks
/// must come from the same data.
/// Coefficients will be drawn at random, one for each block. Blocks must come
/// from the same data.
///
/// > **Note**: this is a wrapper around [`fec::recode_random`]
///
/// # Example
///
/// See [`crate::semi_avid`] for a complete example showing how to get `powers`
/// and `encoding_mat` before calling `prove()`.
///
/// # Side-effect
/// - If a recoded block is combined with its parent blocks, the resulting
/// decoding matrix will be non-invertible, and [`fec::decode`] will return
/// [`KomodoError::NonInvertibleMatrix`]. This is not a direct error happening
/// in [`recode`] but rather a _side-effect_ of the operation.
///
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// # use komodo::algebra::linalg::Matrix;
/// # use komodo::error::KomodoError;
/// # use komodo::fec::encode;
/// use komodo::semi_avid::{prove, build, recode, verify};
/// # use komodo::semi_avid::{prove, build, recode, verify};
/// # use komodo::zk::setup;
/// #
/// # let mut rng = ark_std::test_rng();
/// # let powers = setup::<F, G>(100, &mut rng).unwrap();
/// # let powers = setup::<F, G>(1000, &mut rng).unwrap();
/// #
/// # let (k, n) = (3, 6_usize);
/// # let data = b"hello world";
/// let (k, n) = (3, 6);
/// # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
/// # let encoding_mat: Matrix<F> = Matrix::random(k, n, &mut rng);
/// # let shards = encode(data, &encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(data, &powers, encoding_mat.height).unwrap();
/// # let shards = encode(&data, &encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(&data, &powers, encoding_mat.height).unwrap();
///
/// // get blocks (see the semi_avid::build example for details)
/// let blocks = build::<F, G, DP<F>>(&shards, &proof);
/// let b0 = &blocks[0];
/// let b1 = &blocks[1];
///
/// // recode a block using a subset of the blocks (blocks #0 and #2)
/// let subset = [blocks[0].clone(), blocks[2].clone()];
/// let recoded = recode(&subset, &mut rng).unwrap().unwrap();
/// // recode a block using a subset of the blocks (blocks #0 and #1)
/// let subset = [b0.clone(), b1.clone()];
/// let r01 = recode(&subset, &mut rng).unwrap().unwrap();
///
/// // verify the recoded block
/// assert!(verify::<F, G, DP<F>>(&recoded, &powers).unwrap());
/// assert_eq!(recoded.shard.hash, blocks[0].shard.hash);
/// // fail to decode due to a linear dependency (3x3 matrix to invert has only rank 2)
/// let shards = vec![r01.shard.clone(), b0.shard.clone(), b1.shard.clone()];
/// let decoded_data = komodo::fec::decode(shards);
/// assert_eq!(decoded_data, Err(KomodoError::NonInvertibleMatrix(2)));
/// ```
///
/// # Errors
/// - TODO: document errors
pub fn recode<F: PrimeField, G: CurveGroup<ScalarField = F>>(
blocks: &[Block<F, G>],
rng: &mut impl RngCore,
@@ -278,31 +344,37 @@ pub fn recode<F: PrimeField, G: CurveGroup<ScalarField = F>>(
///
/// # Example
///
/// ```rust
/// use ark_bls12_381::{Fr as F, G1Projective as G};
/// use ark_poly::univariate::DensePolynomial as DP;
/// use komodo::algebra::linalg::Matrix;
/// use komodo::fec::encode;
/// use komodo::semi_avid::prove;
/// use komodo::zk::setup;
/// See [`crate::semi_avid`] for a complete example showing how to get `powers`
/// and `encoding_mat` before calling `prove()`.
///
/// // get a trusted setup
/// let mut rng = ark_std::test_rng();
/// let powers = setup::<F, G>(100, &mut rng).unwrap();
/// # Errors
///
/// // encode some data
/// let (k, n) = (3, 6_usize);
/// let data = b"hello world";
/// let encoding_mat: Matrix<F> = Matrix::random(k, n, &mut rng);
/// let shards = encode(data, &encoding_mat).unwrap();
/// - The trusted setup used should be large enough to handle the data,
/// otherwise this function will return a
/// [`KomodoError::TooFewPowersInTrustedSetup`].
///
/// // prove the data
/// let proof = prove::<F, G, DP<F>>(data, &powers, encoding_mat.height).unwrap();
/// ```
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// #
/// # use komodo::error::KomodoError;
/// # use komodo::semi_avid::{build, prove};
/// #
/// # fn main() {
/// # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
/// # let (k, n) = (3, 6);
/// # let mut rng = ark_std::test_rng();
/// # let encoding_mat = &komodo::algebra::linalg::Matrix::<F>::random(k, n, &mut rng);
/// #
/// // get a very small trusted setup (2 powers, not enough for the data to commit)
/// let powers = komodo::zk::setup::<F, G>(1, &mut rng).unwrap();
///
/// # Errors
/// - if the setup size is too small for the data: [`KomodoError::TooFewPowersInTrustedSetup`]
/// - TODO: document other errors
/// // try to prove the data
/// let proof = prove::<F, G, DP<F>>(&data, &powers, k);
/// let needed_length = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
/// assert_eq!(proof, Err(KomodoError::TooFewPowersInTrustedSetup(2, needed_length + 1)));
/// # }
/// ```
pub fn prove<F, G, P>(
bytes: &[u8],
powers: &Powers<F, G>,
@@ -339,41 +411,9 @@ where
Ok(commits)
}
/// Attach a Semi-AVID proof to a collection of encoded shards.
///
/// # Example
///
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// # use komodo::algebra::linalg::Matrix;
/// # use komodo::fec::encode;
/// use komodo::semi_avid::{prove, build};
/// # use komodo::zk::setup;
/// #
/// # let mut rng = ark_std::test_rng();
/// # let powers = setup::<F, G>(100, &mut rng).unwrap();
/// #
/// # let (k, n) = (3, 6_usize);
/// # let data = b"hello world";
/// # let encoding_mat: Matrix<F> = Matrix::random(k, n, &mut rng);
///
/// // get shards and proofs (see the `semi_avid::prove` example for details)
/// let shards = encode(data, &encoding_mat).unwrap();
/// let proof = prove::<F, G, DP<F>>(data, &powers, encoding_mat.height).unwrap();
///
/// // build blocks made of shards and proof
/// let blocks = build::<F, G, DP<F>>(&shards, &proof);
///
/// assert_eq!(blocks.len(), shards.len());
/// for (i, block) in blocks.iter().enumerate() {
/// assert_eq!(block.shard, shards[i]);
/// // assert_eq!(block.proof, proof); // private unaccessible field
/// }
/// ```
///
/// # Errors
/// - TODO: document errors
/// Build a collection of [`Block`]s from a collection of encoded [`Shard`]s and
/// the data proof ([`Commitment`]s of the $k$ source shards). Each block is made of an
/// encoded shard and a copy of the data proof.
#[inline(always)]
pub fn build<F, G, P>(shards: &[Shard<F>], proof: &[Commitment<F, G>]) -> Vec<Block<F, G>>
where
@@ -393,37 +433,112 @@ where
/// Verify that a single block of encoded and proven data is valid.
///
/// # Example
/// # Examples
///
/// ## Basic usage, where `verify` returns `true`
///
/// See [`crate::semi_avid`] for a complete example showing how to get `powers`
/// and `block` before calling `verify()`. The same setup is used to prove and
/// verify, and the data is not altered, so `verify()` returns `true`.
///
/// ## Cases where `verify` returns `false`
///
/// - The same setup should be used to prove and verify the data, otherwise this
/// function will return `false`.
///
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// # use komodo::algebra::linalg::Matrix;
/// # use komodo::fec::encode;
/// use komodo::semi_avid::{prove, build, verify};
/// # use komodo::zk::setup;
/// #
/// # use komodo::error::KomodoError;
/// # use komodo::semi_avid::{build, prove};
/// #
/// # fn main() {
/// # let (k, n) = (3, 6);
/// # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
/// #
/// # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
/// # let mut rng = ark_std::test_rng();
/// # let powers = setup::<F, G>(100, &mut rng).unwrap();
/// # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
/// #
/// # let (k, n) = (3, 6_usize);
/// # let data = b"hello world";
/// # let encoding_mat: Matrix<F> = Matrix::random(k, n, &mut rng);
/// # let shards = encode(data, &encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(data, &powers, encoding_mat.height).unwrap();
/// # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
/// # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
/// # let blocks = build::<F, G, DP<F>>(&shards, &proof);
/// #
/// // use a different setup, still large enough to verify the data
/// let new_powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
/// let verif = komodo::semi_avid::verify::<F, G, DP<F>>(&blocks[0], &new_powers);
/// assert_eq!(verif, Ok(false));
/// # }
/// ```
///
/// // get blocks (see the `semi_avid::build` example for details)
/// let blocks = build::<F, G, DP<F>>(&shards, &proof);
/// - The data should no be altered, otherwise this function will return `false`.
///
/// // verify each block (you need the powers from the setup)
/// for block in &blocks {
/// assert!(verify::<F, G, DP<F>>(block, &powers).unwrap());
/// }
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// # use ark_std::Zero;
/// #
/// # use komodo::error::KomodoError;
/// # use komodo::semi_avid::{build, prove};
/// #
/// # fn main() {
/// # let (k, n) = (3, 6);
/// # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
/// #
/// # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
/// # let mut rng = ark_std::test_rng();
/// # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
/// #
/// # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
/// # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
/// # let blocks = build::<F, G, DP<F>>(&shards, &proof);
/// #
/// // alter first element of the data
/// # assert!(blocks[0].shard.data[0] != F::zero()); // make sure the data does not start with zero
/// let mut altered_block = &mut blocks[0].clone();
/// altered_block.shard.data[0] = F::zero(); // original data does not start with zero
/// let verif = komodo::semi_avid::verify::<F, G, DP<F>>(altered_block, &powers);
/// assert_eq!(verif, Ok(false));
/// # }
/// ```
///
/// # Errors
/// - if the setup size is too small for the data: [`KomodoError::TooFewPowersInTrustedSetup`]
/// - TODO: document other errors
///
/// - The trusted setup used should be large enough to handle the data,
/// otherwise this function will return a
/// [`KomodoError::TooFewPowersInTrustedSetup`].
///
/// ```rust
/// # use ark_bls12_381::{Fr as F, G1Projective as G};
/// # use ark_poly::univariate::DensePolynomial as DP;
/// #
/// # use komodo::error::KomodoError;
/// # use komodo::semi_avid::{build, prove};
/// #
/// # fn main() {
/// # let (k, n) = (3, 6);
/// # let data = include_bytes!("../assets/dragoon_133x133.png").to_vec();
/// #
/// # let nb = komodo::zk::nb_elements_in_setup::<F>(data.len() / k);
/// # let mut rng = ark_std::test_rng();
/// # let powers = komodo::zk::setup::<F, G>(nb, &mut rng).unwrap();
/// #
/// # let encoding_mat = &komodo::algebra::linalg::Matrix::random(k, n, &mut rng);
/// # let shards = komodo::fec::encode(&data, encoding_mat).unwrap();
/// # let proof = prove::<F, G, DP<F>>(&data, &powers, k).unwrap();
/// # let blocks = build::<F, G, DP<F>>(&shards, &proof);
/// #
/// // get a very small trusted setup (2 powers, not enough for the data to verify)
/// let powers = komodo::zk::setup::<F, G>(1, &mut rng).unwrap();
///
/// // try to prove the data
/// let verif = komodo::semi_avid::verify::<F, G, DP<F>>(&blocks[0], &powers);
/// assert_eq!(verif, Err(KomodoError::TooFewPowersInTrustedSetup(2, nb + 1)));
/// # }
/// ```
pub fn verify<F, G, P>(
block: &Block<F, G>,
verifier_key: &Powers<F, G>,