use a hashmap to represent linear combination

this MR removes the LinearCombinationElement and changes Shard.linear_combination to be a HashMap<u32, E::ScalarField> instead of a Vec<LinearCombinationElement<E>>.

• the u32 key is the index of the shard used in the linear combination
• the E::ScalarField value is the corresponding coefficient in the linear combination

the main goal is to remove duplicates on the shard indices, see this test where the shard 0 is twice

i had to

• implement CanonicalSerialize, CanonicalDeserialize and Valid for Shard according to the Arkworks documentation (scroll a bit to "implement these traits manually")
• add a test for the serialization
• fix all the usages in lib.rs and main.rs

in the end, it's not too bad, i wanted to have your input on this @j.detchart

src/fec.rs

-use std::ops::{Add, Mul};
+use std::{
+    collections::HashMap,
+    ops::{Add, Mul},
+};
 
 use ark_ec::pairing::Pairing;
-use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
+use ark_serialize::{
+    CanonicalDeserialize, CanonicalSerialize, Compress, Read, SerializationError, Valid, Validate,
+    Write,
+};
 use ark_std::{One, Zero};
 use reed_solomon_erasure::{Error, Field as GF, ReedSolomonNonSystematic};
 
 use crate::field;
 
-#[derive(Debug, Default, Clone, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
-pub struct LinearCombinationElement<E: Pairing> {
-    pub index: u32,
-    pub weight: E::ScalarField,
-}
-
-#[derive(Debug, Default, Clone, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
+#[derive(Debug, Default, Clone, PartialEq)]
 pub struct Shard<E: Pairing> {
     pub k: u32,
-    pub linear_combination: Vec<LinearCombinationElement<E>>,
+    pub linear_combination: HashMap<u32, E::ScalarField>,
     pub hash: Vec<u8>,
     pub bytes: Vec<u8>,
     pub size: usize,
 }
 
+impl<E: Pairing> CanonicalSerialize for Shard<E> {
+    fn serialize_with_mode<W: Write>(
+        &self,
+        mut writer: W,
+        mode: Compress,
+    ) -> Result<(), SerializationError> {
+        self.k.serialize_with_mode(&mut writer, mode)?;
+        self.hash.serialize_with_mode(&mut writer, mode)?;
+        self.bytes.serialize_with_mode(&mut writer, mode)?;
+        self.size.serialize_with_mode(&mut writer, mode)?;
+
+        self.linear_combination
+            .len()
+            .serialize_with_mode(&mut writer, mode)?;
+        for (k, v) in self.linear_combination.iter() {
+            k.serialize_with_mode(&mut writer, mode)?;
+            v.serialize_with_mode(&mut writer, mode)?;
+        }
+
+        Ok(())
+    }
+
+    fn serialized_size(&self, mode: Compress) -> usize {
+        let mut res = self.k.serialized_size(mode)
+            + self.hash.serialized_size(mode)
+            + self.bytes.serialized_size(mode)
+            + self.size.serialized_size(mode)
+            + self.linear_combination.len().serialized_size(mode);
+        for (k, v) in self.linear_combination.iter() {
+            res += k.serialized_size(mode) + v.serialized_size(mode);
+        }
+
+        res
+    }
+}
+
+impl<E: Pairing> CanonicalDeserialize for Shard<E> {
+    fn deserialize_with_mode<R: Read>(
+        mut reader: R,
+        compress: Compress,
+        validate: Validate,
+    ) -> Result<Self, SerializationError> {
+        let k = u32::deserialize_with_mode(&mut reader, compress, validate)?;
+        let hash = <Vec<u8>>::deserialize_with_mode(&mut reader, compress, validate)?;
+        let bytes = <Vec<u8>>::deserialize_with_mode(&mut reader, compress, validate)?;
+        let size = usize::deserialize_with_mode(&mut reader, compress, validate)?;
+
+        let lin_comb_len = usize::deserialize_with_mode(&mut reader, compress, validate)?;
+        let mut linear_combination = HashMap::new();
+        for _ in 0..lin_comb_len {
+            let k = u32::deserialize_with_mode(&mut reader, compress, validate)?;
+            let v = <E::ScalarField>::deserialize_with_mode(&mut reader, compress, validate)?;
+            linear_combination.insert(k, v);
+        }
+
+        Ok(Self {
+            k,
+            linear_combination,
+            hash,
+            bytes,
+            size,
+        })
+    }
+}
+
+impl<E: Pairing> Valid for Shard<E> {
+    fn check(&self) -> Result<(), SerializationError> {
+        self.k.check()?;
+        self.hash.check()?;
+        self.bytes.check()?;
+        self.size.check()?;
+
+        for (k, v) in self.linear_combination.iter() {
+            k.check()?;
+            v.check()?;
+        }
+
+        Ok(())
+    }
+}
+
 impl<E: Pairing> Shard<E> {
     pub fn mul(&self, alpha: E::ScalarField) -> Self {
         let bytes = if alpha.is_zero() {
@@ -37,16 +118,14 @@ impl<E: Pairing> Shard<E> {
             field::merge_elements_into_bytes::<E>(&elements)
         };
 
+        let mut linear_combination = self.linear_combination.clone();
+        for weight in linear_combination.values_mut() {
+            *weight = weight.mul(alpha);
+        }
+
         Shard {
             k: self.k,
-            linear_combination: self
-                .linear_combination
-                .iter()
-                .map(|l| LinearCombinationElement {
-                    index: l.index,
-                    weight: l.weight.mul(alpha),
-                })
-                .collect(),
+            linear_combination,
             hash: self.hash.clone(),
             bytes,
             size: self.size,
@@ -71,18 +150,28 @@ impl<E: Pairing> Shard<E> {
                 .collect::<Vec<_>>()
         };
 
-        let mut linear_combination = vec![];
-        for lce in &self.linear_combination {
-            linear_combination.push(LinearCombinationElement {
-                index: lce.index,
-                weight: lce.weight.mul(alpha),
-            });
-        }
-        for lce in &other.linear_combination {
-            linear_combination.push(LinearCombinationElement {
-                index: lce.index,
-                weight: lce.weight.mul(beta),
-            });
+        let mut linear_combination = HashMap::new();
+        let mut indices = self.linear_combination.keys().collect::<Vec<_>>();
+        indices.extend(other.linear_combination.keys());
+        indices.dedup();
+        for i in indices {
+            let weight = linear_combination
+                .get(i)
+                .unwrap_or(&E::ScalarField::zero())
+                .add(
+                    self.linear_combination
+                        .get(i)
+                        .unwrap_or(&E::ScalarField::zero())
+                        .mul(alpha),
+                )
+                .add(
+                    other
+                        .linear_combination
+                        .get(i)
+                        .unwrap_or(&E::ScalarField::zero())
+                        .mul(beta),
+                );
+            linear_combination.insert(*i, weight);
         }
 
         Shard {
@@ -100,9 +189,15 @@ pub fn decode<F: GF, E: Pairing>(blocks: Vec<Shard<E>>) -> Result<Vec<u8>, Error
     let n = blocks
         .iter()
         // FIXME: this is incorrect
-        .map(|b| b.linear_combination[0].index)
+        .map(|b| {
+            **b.linear_combination
+                .keys()
+                .collect::<Vec<_>>()
+                .get(0)
+                .unwrap()
+        })
         .max()
-        .unwrap_or(0)
+        .unwrap_or(0u32)
         + 1;
 
     if blocks.len() < k as usize {
@@ -113,7 +208,12 @@ pub fn decode<F: GF, E: Pairing>(blocks: Vec<Shard<E>>) -> Result<Vec<u8>, Error
     shards.resize(n as usize, None);
     for block in &blocks {
         // FIXME: this is incorrect
-        shards[block.linear_combination[0].index as usize] = Some(F::deserialize(&block.bytes));
+        shards[**block
+            .linear_combination
+            .keys()
+            .collect::<Vec<_>>()
+            .get(0)
+            .unwrap() as usize] = Some(F::deserialize(&block.bytes));
     }
 
     ReedSolomonNonSystematic::<F>::vandermonde(k as usize, n as usize)?.reconstruct(&mut shards)?;
@@ -126,16 +226,19 @@ pub fn decode<F: GF, E: Pairing>(blocks: Vec<Shard<E>>) -> Result<Vec<u8>, Error
 
 #[cfg(test)]
 mod tests {
+    use std::collections::HashMap;
+
     use ark_bls12_381::Bls12_381;
     use ark_ec::pairing::Pairing;
     use ark_ff::PrimeField;
+    use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Compress, Validate};
     use ark_std::One;
     use reed_solomon_erasure::galois_prime::Field as GF;
     use rs_merkle::algorithms::Sha256;
     use rs_merkle::Hasher;
 
     use crate::{
-        fec::{decode, LinearCombinationElement, Shard},
+        fec::{decode, Shard},
         field,
     };
 
@@ -181,10 +284,10 @@ mod tests {
             if let Some(bytes) = shard {
                 blocks.push(Shard {
                     k: K as u32,
-                    linear_combination: vec![LinearCombinationElement {
-                        index: i as u32,
-                        weight: <Bls12_381 as Pairing>::ScalarField::one(),
-                    }],
+                    linear_combination: HashMap::from([(
+                        i as u32,
+                        <Bls12_381 as Pairing>::ScalarField::one(),
+                    )]),
                     hash: hash.clone(),
                     bytes: field::merge_elements_into_bytes::<Bls12_381>(bytes),
                     size: DATA.len(),
@@ -196,7 +299,7 @@ mod tests {
     }
 
     fn create_fake_shard<E: Pairing>(
-        linear_combination: &[LinearCombinationElement<E>],
+        linear_combination: HashMap<u32, E::ScalarField>,
         bytes: &[u8],
     ) -> Shard<E> {
         let mut bytes = bytes.to_vec();
@@ -204,87 +307,90 @@ mod tests {
 
         Shard {
             k: 0,
-            linear_combination: linear_combination.to_vec(),
+            linear_combination,
             hash: vec![],
             bytes,
             size: 0,
         }
     }
 
-    #[test]
-    fn recoding() {
-        let a: Shard<Bls12_381> = create_fake_shard(
-            &[LinearCombinationElement {
-                index: 0,
-                weight: <Bls12_381 as Pairing>::ScalarField::one(),
-            }],
-            &[1, 2, 3],
-        );
-        let b: Shard<Bls12_381> = create_fake_shard(
-            &[LinearCombinationElement {
-                index: 1,
-                weight: <Bls12_381 as Pairing>::ScalarField::one(),
-            }],
-            &[4, 5, 6],
-        );
+    fn recoding_template<E: Pairing>() {
+        let a: Shard<E> =
+            create_fake_shard(HashMap::from([(0, E::ScalarField::one())]), &[1, 2, 3]);
+        let b: Shard<E> =
+            create_fake_shard(HashMap::from([(1, E::ScalarField::one())]), &[4, 5, 6]);
 
         assert_eq!(
-            a.mul(<Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[2])),
+            a.mul(E::ScalarField::from_le_bytes_mod_order(&[2])),
             create_fake_shard(
-                &[LinearCombinationElement {
-                    index: 0,
-                    weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[2]),
-                }],
+                HashMap::from([(0, E::ScalarField::from_le_bytes_mod_order(&[2]),)]),
                 &[2, 4, 6],
             )
         );
 
         let c = a.combine(
-            <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[3]),
+            E::ScalarField::from_le_bytes_mod_order(&[3]),
             &b,
-            <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[5]),
+            E::ScalarField::from_le_bytes_mod_order(&[5]),
         );
 
         assert_eq!(
             c,
             create_fake_shard(
-                &[
-                    LinearCombinationElement {
-                        index: 0,
-                        weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[3]),
-                    },
-                    LinearCombinationElement {
-                        index: 1,
-                        weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[5]),
-                    }
-                ],
+                HashMap::from([
+                    (0, E::ScalarField::from_le_bytes_mod_order(&[3]),),
+                    (1, E::ScalarField::from_le_bytes_mod_order(&[5]),)
+                ]),
                 &[23, 31, 39]
             )
         );
 
         assert_eq!(
             c.combine(
-                <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[2]),
+                E::ScalarField::from_le_bytes_mod_order(&[2]),
                 &a,
-                <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[4]),
+                E::ScalarField::from_le_bytes_mod_order(&[4]),
             ),
             create_fake_shard(
-                &[
-                    LinearCombinationElement {
-                        index: 0,
-                        weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[6]),
-                    },
-                    LinearCombinationElement {
-                        index: 1,
-                        weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[10]),
-                    },
-                    LinearCombinationElement {
-                        index: 0,
-                        weight: <Bls12_381 as Pairing>::ScalarField::from_le_bytes_mod_order(&[4]),
-                    }
-                ],
+                HashMap::from([
+                    (0, E::ScalarField::from_le_bytes_mod_order(&[10]),),
+                    (1, E::ScalarField::from_le_bytes_mod_order(&[10]),),
+                ]),
                 &[50, 70, 90],
             )
         );
     }
+
+    #[test]
+    fn recoding() {
+        recoding_template::<Bls12_381>();
+    }
+
+    fn serialization_template<E: Pairing>(mode: Compress, validate: Validate) {
+        let shard: Shard<E> = create_fake_shard(
+            HashMap::from([
+                (0, E::ScalarField::from_le_bytes_mod_order(&[3])),
+                (1, E::ScalarField::from_le_bytes_mod_order(&[5])),
+            ]),
+            &[23, 31, 39],
+        );
+
+        let mut serialized = vec![0; shard.serialized_size(mode)];
+        shard
+            .serialize_with_mode(&mut serialized[..], mode)
+            .unwrap();
+
+        assert_eq!(
+            shard,
+            Shard::<E>::deserialize_with_mode(&serialized[..], mode, validate).unwrap()
+        )
+    }
+
+    #[test]
+    fn serialization() {
+        serialization_template::<Bls12_381>(Compress::Yes, Validate::Yes);
+        serialization_template::<Bls12_381>(Compress::Yes, Validate::No);
+        serialization_template::<Bls12_381>(Compress::No, Validate::Yes);
+        serialization_template::<Bls12_381>(Compress::No, Validate::No);
+    }
 }