shine.rs 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313
  1. use crate::lagrange::*;
  2. use curve25519_dalek::constants as dalek_constants;
  3. use curve25519_dalek::ristretto::RistrettoPoint;
  4. use curve25519_dalek::ristretto::VartimeRistrettoPrecomputation;
  5. use curve25519_dalek::scalar::Scalar;
  6. use curve25519_dalek::traits::Identity;
  7. use curve25519_dalek::traits::VartimePrecomputedMultiscalarMul;
  8. use itertools::Itertools;
  9. use rand::RngCore;
  10. use sha2::digest::FixedOutput;
  11. use sha2::Digest;
  12. use sha2::Sha256;
  13. // Compute (m choose k) when m^k < 2^64
  14. fn binom(m: u32, k: u32) -> u64 {
  15. let mut numer = 1u64;
  16. let mut denom = 1u64;
  17. for i in 0u64..(k as u64) {
  18. numer *= (m as u64) - i;
  19. denom *= i + 1;
  20. }
  21. numer / denom
  22. }
  23. // The hash function used to create the coefficients for the
  24. // pseudorandom secret sharing.
  25. fn hash1(phi: &[u8; 32], w: &[u8]) -> Scalar {
  26. let mut hash = Sha256::new();
  27. hash.update(phi);
  28. hash.update(w);
  29. let mut hashval = [0u8; 32];
  30. hash.finalize_into((&mut hashval).into());
  31. Scalar::from_bytes_mod_order(hashval)
  32. }
  33. // The key for player k will consist of a vector of (v, phi) tuples,
  34. // where the v values enumerate all lists of t-1 player numbers (from
  35. // 1 to n) that do _not_ include k
  36. #[derive(Debug)]
  37. pub struct Key {
  38. pub n: u32,
  39. pub t: u32,
  40. pub k: u32,
  41. pub secrets: Vec<(Vec<u32>, [u8; 32])>,
  42. }
  43. impl Key {
  44. pub fn keygen(n: u32, t: u32) -> Vec<Self> {
  45. let delta = binom(n - 1, t - 1);
  46. let mut rng = rand::thread_rng();
  47. let mut res: Vec<Self> = Vec::with_capacity(n as usize);
  48. for k in 1..=n {
  49. res.push(Self {
  50. n,
  51. t,
  52. k,
  53. secrets: Vec::with_capacity(delta as usize),
  54. });
  55. }
  56. let si = (1..=n).combinations((t - 1) as usize);
  57. for v in si {
  58. // For each subset of size t-1, pick a random secret, and
  59. // give it to all players _not_ in that subset
  60. let mut phi: [u8; 32] = [0; 32];
  61. rng.fill_bytes(&mut phi);
  62. let mut vnextind = 0usize;
  63. let mut vnext = v[0];
  64. for i in 1..=n {
  65. if i < vnext {
  66. res[(i - 1) as usize].secrets.push((v.clone(), phi));
  67. } else {
  68. vnextind += 1;
  69. vnext = if vnextind < ((t - 1) as usize) {
  70. v[vnextind]
  71. } else {
  72. n + 1
  73. };
  74. }
  75. }
  76. }
  77. res
  78. }
  79. }
  80. #[test]
  81. pub fn test_keygen() {
  82. let keys = Key::keygen(7, 4);
  83. println!("key for player 3: {:?}", keys[2]);
  84. println!("key for player 7: {:?}", keys[6]);
  85. }
  86. #[derive(Debug)]
  87. pub struct PreprocKey {
  88. pub n: u32,
  89. pub t: u32,
  90. pub k: u32,
  91. pub secrets: Vec<([u8; 32], Scalar)>,
  92. }
  93. impl PreprocKey {
  94. pub fn preproc(key: &Key) -> Self {
  95. Self {
  96. n: key.n,
  97. t: key.t,
  98. k: key.k,
  99. secrets: key
  100. .secrets
  101. .iter()
  102. .map(|(v, phi)| (*phi, lagrange(v, 0, key.k)))
  103. .collect(),
  104. }
  105. }
  106. pub fn rand(n: u32, t: u32) -> Self {
  107. let delta = binom(n - 1, t - 1);
  108. let mut secrets: Vec<([u8; 32], Scalar)> = Vec::new();
  109. let mut rng = rand::thread_rng();
  110. for _ in 0u64..delta {
  111. let mut phi = [0u8; 32];
  112. rng.fill_bytes(&mut phi);
  113. let lagrange: Scalar = Scalar::random(&mut rng);
  114. secrets.push((phi, lagrange));
  115. }
  116. Self {
  117. n,
  118. t,
  119. k: 1,
  120. secrets,
  121. }
  122. }
  123. pub fn gen(&self, w: &[u8]) -> (Scalar, RistrettoPoint) {
  124. let d = self
  125. .secrets
  126. .iter()
  127. .map(|(phi, lagrange)| hash1(phi, w) * lagrange)
  128. .sum();
  129. (d, &d * &dalek_constants::RISTRETTO_BASEPOINT_TABLE)
  130. }
  131. pub fn delta(&self) -> usize {
  132. self.secrets.len()
  133. }
  134. }
  135. pub fn commit(evaluation: &Scalar) -> RistrettoPoint {
  136. evaluation * &dalek_constants::RISTRETTO_BASEPOINT_TABLE
  137. }
  138. // Verify that a set of commitments are consistent with a given t, using
  139. // precomputed Lagrange polynomials. Return false if the commitments
  140. // are not consistent with the given t, or true if they are. You must
  141. // pass at least 2t-1 commitments, and the same number of lag_polys.
  142. pub fn verify_polys(t: u32, lag_polys: &[ScalarPoly], commitments: &[RistrettoPoint]) -> bool {
  143. // Check if the commitments are consistent: when interpolating the
  144. // polys in the exponent, the low t coefficients can be non-0 but
  145. // the ones above that must be 0
  146. let coalition_size = commitments.len();
  147. assert!(t >= 1);
  148. assert!(coalition_size >= 2 * (t as usize) - 1);
  149. assert!(coalition_size == lag_polys.len());
  150. assert!(coalition_size == lag_polys[0].coeffs.len());
  151. // Use this to compute the multiscalar multiplications
  152. let multiscalar = VartimeRistrettoPrecomputation::new(Vec::<RistrettoPoint>::new());
  153. // Compute the B_i for i from t to coalition_size-1. All of them
  154. // should be the identity; otherwise, the commitments are
  155. // inconsistent.
  156. ((t as usize)..coalition_size)
  157. .map(|i| {
  158. // B_i = \sum_j lag_polys[j].coeffs[i] * commitments[j]
  159. multiscalar.vartime_mixed_multiscalar_mul(
  160. &Vec::<Scalar>::new(),
  161. (0..coalition_size).map(|j| lag_polys[j].coeffs[i]),
  162. commitments,
  163. )
  164. })
  165. .all(|bi: RistrettoPoint| bi == RistrettoPoint::identity())
  166. }
  167. // Verify that a set of commitments are consistent with a given t.
  168. // Return false if the commitments are not consistent with the given t,
  169. // or true if they are. You must pass at least 2t-1 commitments, and the
  170. // same number of lag_polys.
  171. pub fn verify(t: u32, coalition: &[u32], commitments: &[RistrettoPoint]) -> bool {
  172. let polys = lagrange_polys(coalition);
  173. verify_polys(t, &polys, commitments)
  174. }
  175. // Combine already-verified commitments using precomputed Lagrange
  176. // polynomials. You must pass at least 2t-1 commitments, and the same
  177. // number of lag_polys.
  178. pub fn agg_polys(
  179. t: u32,
  180. lag_polys: &[ScalarPoly],
  181. commitments: &[RistrettoPoint],
  182. ) -> RistrettoPoint {
  183. let coalition_size = commitments.len();
  184. assert!(t >= 1);
  185. assert!(coalition_size >= 2 * (t as usize) - 1);
  186. assert!(coalition_size == lag_polys.len());
  187. assert!(coalition_size == lag_polys[0].coeffs.len());
  188. // Use this to compute the multiscalar multiplications
  189. let multiscalar = VartimeRistrettoPrecomputation::new(Vec::<RistrettoPoint>::new());
  190. // Compute B_0 (which is the combined commitment) and return it
  191. multiscalar.vartime_mixed_multiscalar_mul(
  192. &Vec::<Scalar>::new(),
  193. (0..coalition_size).map(|j| lag_polys[j].coeffs[0]),
  194. commitments,
  195. )
  196. }
  197. // Combine already-verified commitments. You must pass at least 2t-1
  198. // commitments, and the same number of lag_polys.
  199. pub fn agg(t: u32, coalition: &[u32], commitments: &[RistrettoPoint]) -> RistrettoPoint {
  200. let polys = lagrange_polys(coalition);
  201. agg_polys(t, &polys, commitments)
  202. }
  203. // Combine commitments using precomputed Lagrange polynomials. Return
  204. // None if the commitments are not consistent with the given t. You
  205. // must pass at least 2t-1 commitments, and the same number of
  206. // lag_polys. This function combines verify_polys and agg_polys into a
  207. // single call that returns Option<RistrettoPoint>.
  208. pub fn combinecomm_polys(
  209. t: u32,
  210. lag_polys: &[ScalarPoly],
  211. commitments: &[RistrettoPoint],
  212. ) -> Option<RistrettoPoint> {
  213. let coalition_size = commitments.len();
  214. assert!(t >= 1);
  215. assert!(coalition_size >= 2 * (t as usize) - 1);
  216. assert!(coalition_size == lag_polys.len());
  217. assert!(coalition_size == lag_polys[0].coeffs.len());
  218. // Check if the commitments are consistent: when interpolating the
  219. // polys in the exponent, the low t coefficients can be non-0 but
  220. // the ones above that must be 0
  221. if !verify_polys(t, lag_polys, commitments) {
  222. return None;
  223. }
  224. Some(agg_polys(t, lag_polys, commitments))
  225. }
  226. // Combine commitments. Return None if the commitments are not
  227. // consistent with the given t. You must pass at least 2t-1
  228. // commitments, and the same size of coalition. This function combines
  229. // verify and agg into a single call that returns
  230. // Option<RistrettoPoint>.
  231. pub fn combinecomm(
  232. t: u32,
  233. coalition: &[u32],
  234. commitments: &[RistrettoPoint],
  235. ) -> Option<RistrettoPoint> {
  236. let polys = lagrange_polys(coalition);
  237. combinecomm_polys(t, &polys, commitments)
  238. }
  239. #[test]
  240. pub fn test_preproc() {
  241. let keys = Key::keygen(7, 4);
  242. let ppkey3 = PreprocKey::preproc(&keys[2]);
  243. let ppkey7 = PreprocKey::preproc(&keys[6]);
  244. println!("preproc key for player 3: {:?}", ppkey3);
  245. println!("preproc key for player 7: {:?}", ppkey7);
  246. }
  247. #[test]
  248. pub fn test_gen() {
  249. let keys = Key::keygen(7, 3);
  250. let ppkeys: Vec<PreprocKey> = keys.iter().map(|x| PreprocKey::preproc(x)).collect();
  251. let mut rng = rand::thread_rng();
  252. let mut w = [0u8; 32];
  253. rng.fill_bytes(&mut w);
  254. let evals: Vec<Scalar> = ppkeys.iter().map(|k| k.gen(&w).0).collect();
  255. // Try interpolating different subsets and check that the answer is
  256. // the same
  257. let interp1 = interpolate(&vec![1, 2, 3, 4, 5], &evals[0..=4], 0);
  258. let interp2 = interpolate(&vec![3, 4, 5, 6, 7], &evals[2..=6], 0);
  259. println!("interp1 = {:?}", interp1);
  260. println!("interp2 = {:?}", interp2);
  261. assert!(interp1 == interp2);
  262. }
  263. #[test]
  264. pub fn test_combinecomm() {
  265. let keys = Key::keygen(7, 3);
  266. let ppkeys: Vec<PreprocKey> = keys.iter().map(|x| PreprocKey::preproc(x)).collect();
  267. let mut rng = rand::thread_rng();
  268. let mut w = [0u8; 32];
  269. rng.fill_bytes(&mut w);
  270. let commitments: Vec<RistrettoPoint> = ppkeys.iter().map(|k| k.gen(&w).1).collect();
  271. let comm1 = combinecomm(3, &vec![1, 2, 3, 4, 5], &commitments[0..=4]);
  272. let comm2 = combinecomm(3, &vec![3, 4, 5, 6, 7], &commitments[2..=6]);
  273. assert_ne!(comm1, None);
  274. assert_ne!(comm2, None);
  275. // Test a failure case
  276. let comm3 = combinecomm(3, &vec![1, 2, 3, 4, 6], &commitments[0..=4]);
  277. assert_eq!(comm3, None);
  278. }