vss.rs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368
  1. use curve25519_dalek::constants::RISTRETTO_BASEPOINT_POINT;
  2. use curve25519_dalek::ristretto::RistrettoPoint;
  3. use curve25519_dalek::scalar::Scalar;
  4. use curve25519_dalek::traits::Identity;
  5. use rand::rngs::ThreadRng;
  6. pub type Secret = Scalar;
  7. #[derive(Copy, Clone)]
  8. pub struct Share {
  9. index: u32,
  10. value: Scalar,
  11. }
  12. pub struct Commitment(Vec<RistrettoPoint>);
  13. /// Create secret shares for a given secret.
  14. pub fn generate_shares(
  15. secret: Secret,
  16. numshares: u32,
  17. threshold: u32,
  18. ) -> Result<(Commitment, Vec<Share>), &'static str> {
  19. if threshold < 1 {
  20. return Err("Threshold cannot be 0");
  21. }
  22. if numshares < 1 {
  23. return Err("Number of shares cannot be 0");
  24. }
  25. if threshold > numshares {
  26. return Err("Threshold cannot exceed numshares");
  27. }
  28. let numcoeffs = (threshold - 1) as usize;
  29. let mut coefficients: Vec<Scalar> = Vec::with_capacity(numcoeffs);
  30. let mut rng: ThreadRng = rand::thread_rng();
  31. let mut shares: Vec<Share> = Vec::with_capacity(numshares as usize);
  32. let mut commitment = Commitment(Vec::with_capacity(threshold as usize));
  33. for _ in 0..numcoeffs {
  34. coefficients.push(Scalar::random(&mut rng));
  35. }
  36. for share_index in 1..numshares + 1 {
  37. // Evaluate the polynomial with `secret` as the constant term
  38. // and `coeffs` as the other coefficients at the point x=share_index
  39. // using Horner's method
  40. let scalar_index = Scalar::from(share_index);
  41. let mut value = Scalar::zero();
  42. for i in (0..numcoeffs).rev() {
  43. value += coefficients[i];
  44. value *= scalar_index;
  45. }
  46. value += secret;
  47. shares.push(Share {
  48. index: share_index,
  49. value: value,
  50. });
  51. }
  52. commitment.0.push(RISTRETTO_BASEPOINT_POINT * secret);
  53. for c in coefficients {
  54. commitment.0.push(RISTRETTO_BASEPOINT_POINT * c);
  55. }
  56. Ok((commitment, shares))
  57. }
  58. /// Verify that a share is consistent with a commitment.
  59. pub fn verify_share(share: &Share, commitment: &Commitment) -> Result<(), &'static str> {
  60. let f_result = RISTRETTO_BASEPOINT_POINT * share.value;
  61. let x = Scalar::from(share.index);
  62. let (_, result) = commitment.0.iter().fold(
  63. (Scalar::one(), RistrettoPoint::identity()),
  64. |(x_to_the_i, sum_so_far), comm_i| (x_to_the_i * x, sum_so_far + x_to_the_i * comm_i),
  65. );
  66. if f_result == result {
  67. Ok(())
  68. } else {
  69. Err("Share is inconsistent")
  70. }
  71. }
  72. /// Reconstruct the secret from enough (at least the threshold) already-verified shares.
  73. pub fn reconstruct_secret(shares: &Vec<Share>) -> Result<Secret, &'static str> {
  74. let numshares = shares.len();
  75. if numshares < 1 {
  76. return Err("No shares provided");
  77. }
  78. let mut lagrange_coeffs: Vec<Scalar> = Vec::with_capacity(numshares);
  79. for i in 0..numshares {
  80. let mut num = Scalar::one();
  81. let mut den = Scalar::one();
  82. for j in 0..numshares {
  83. if j == i {
  84. continue;
  85. }
  86. num *= Scalar::from(shares[j].index);
  87. den *= Scalar::from(shares[j].index) - Scalar::from(shares[i].index);
  88. }
  89. if den == Scalar::zero() {
  90. return Err("Duplicate shares provided");
  91. }
  92. lagrange_coeffs.push(num * den.invert());
  93. }
  94. let mut secret = Scalar::zero();
  95. for i in 0..numshares {
  96. secret += lagrange_coeffs[i] * shares[i].value;
  97. }
  98. Ok(secret)
  99. }
  100. /// Create a proactive update.
  101. pub fn create_update(
  102. num_shares: u32,
  103. threshold: u32,
  104. ) -> Result<(Commitment, Vec<Share>), &'static str> {
  105. generate_shares(Scalar::zero(), num_shares, threshold)
  106. }
  107. /// Apply the commitment for the update to the master commitment.
  108. pub fn apply_commitment_update(
  109. old_commitment: &Commitment,
  110. update: &Commitment,
  111. ) -> Result<Commitment, &'static str> {
  112. let mut new_commitments = Commitment(Vec::with_capacity(old_commitment.0.len()));
  113. for i in 0..old_commitment.0.len() {
  114. let new_commitment = old_commitment.0[i] + update.0[i];
  115. new_commitments.0.push(new_commitment);
  116. }
  117. Ok(new_commitments)
  118. }
  119. /// Apply the share update to an existing share
  120. pub fn apply_share_update(
  121. old_share: &Share,
  122. update: &Share,
  123. updated_commitment: &Commitment,
  124. ) -> Result<Share, &'static str> {
  125. let updated_share = Share {
  126. index: old_share.index,
  127. value: old_share.value + update.value,
  128. };
  129. match verify_share(&updated_share, updated_commitment) {
  130. Ok(n) => n,
  131. Err(_) => return Err("Error when validating share"),
  132. };
  133. Ok(updated_share)
  134. }
  135. #[cfg(test)]
  136. mod tests {
  137. use crate::vss::*;
  138. #[test]
  139. fn share_simple() {
  140. let s = Secret::from(42u32);
  141. let res = generate_shares(s, 5, 2);
  142. assert!(res.is_ok());
  143. let (com, shares) = res.unwrap();
  144. assert!(shares.len() == 5);
  145. assert!(com.0.len() == 2);
  146. let mut recshares: Vec<Share> = Vec::new();
  147. recshares.push(shares[1]);
  148. recshares.push(shares[3]);
  149. let recres = reconstruct_secret(&recshares);
  150. assert!(recres.is_ok());
  151. assert_eq!(recres.unwrap(), s);
  152. }
  153. #[test]
  154. fn share_not_enough() {
  155. let s = Secret::from(42u32);
  156. let res = generate_shares(s, 5, 2);
  157. assert!(res.is_ok());
  158. let (_, shares) = res.unwrap();
  159. let mut recshares: Vec<Share> = Vec::new();
  160. recshares.push(shares[1]);
  161. let recres = reconstruct_secret(&recshares);
  162. assert!(recres.is_ok());
  163. assert_ne!(recres.unwrap(), s);
  164. }
  165. #[test]
  166. fn share_dup() {
  167. let s = Secret::from(42u32);
  168. let res = generate_shares(s, 5, 2);
  169. assert!(res.is_ok());
  170. let (_, shares) = res.unwrap();
  171. let mut recshares: Vec<Share> = Vec::new();
  172. recshares.push(shares[1]);
  173. recshares.push(shares[1]);
  174. let recres = reconstruct_secret(&recshares);
  175. assert!(recres.is_err());
  176. assert_eq!(recres.err(), Some("Duplicate shares provided"));
  177. }
  178. #[test]
  179. fn share_badparams() {
  180. let s = Secret::from(42u32);
  181. {
  182. let res = generate_shares(s, 5, 0);
  183. assert!(res.is_err());
  184. assert_eq!(res.err(), Some("Threshold cannot be 0"));
  185. }
  186. {
  187. let res = generate_shares(s, 0, 3);
  188. assert!(res.is_err());
  189. assert_eq!(res.err(), Some("Number of shares cannot be 0"));
  190. }
  191. {
  192. let res = generate_shares(s, 1, 3);
  193. assert!(res.is_err());
  194. assert_eq!(res.err(), Some("Threshold cannot exceed numshares"));
  195. }
  196. }
  197. #[test]
  198. fn share_commitment_valid() {
  199. let s = Secret::from(42u32);
  200. let res = generate_shares(s, 8, 3);
  201. assert!(res.is_ok());
  202. let (com, shares) = res.unwrap();
  203. for share in shares {
  204. let is_valid = verify_share(&share, &com);
  205. assert!(is_valid.is_ok());
  206. }
  207. }
  208. #[test]
  209. fn share_commitment_invalid() {
  210. let s1 = Secret::from(42u32);
  211. let s2 = Secret::from(42u32);
  212. let res1 = generate_shares(s1, 8, 3);
  213. assert!(res1.is_ok());
  214. let (_, shares1) = res1.unwrap();
  215. let res2 = generate_shares(s2, 8, 3);
  216. assert!(res2.is_ok());
  217. let (com2, _) = res2.unwrap();
  218. for share in shares1 {
  219. // test that commitments to a different set of shares fails
  220. let is_valid = verify_share(&share, &com2);
  221. assert!(is_valid.is_err());
  222. }
  223. }
  224. #[test]
  225. fn share_update_valid() {
  226. let s = Secret::from(42u32);
  227. let res = generate_shares(s, 5, 2);
  228. assert!(res.is_ok());
  229. let (com, shares) = res.unwrap();
  230. // Create a new update
  231. let update_comm_res = create_update(5, 2);
  232. assert!(update_comm_res.is_ok());
  233. let (com_update, shares_update) = update_comm_res.unwrap();
  234. // Apply the update to previously-created committment
  235. let updated_commitment_res = apply_commitment_update(&com, &com_update);
  236. assert!(updated_commitment_res.is_ok());
  237. let updated_commitment = updated_commitment_res.unwrap();
  238. // Distribute the update to all owners of shares
  239. // Verify and apply the update
  240. // Collect updated shares to test secret reconstruction after
  241. let mut updates_to_shares = shares_update.iter();
  242. let mut updated_shares: Vec<Share> = Vec::with_capacity(5);
  243. for share in &shares {
  244. let share_update = updates_to_shares.next().unwrap();
  245. let update_share_res = apply_share_update(&share, &share_update, &updated_commitment);
  246. assert!(update_share_res.is_ok());
  247. let updated_share = update_share_res.unwrap();
  248. updated_shares.push(updated_share);
  249. }
  250. // assert that we can recover the original secret using the updated shares
  251. let recres = reconstruct_secret(&updated_shares);
  252. assert!(recres.is_ok());
  253. assert_eq!(recres.unwrap(), s);
  254. // test that the old shares are not valid with the updated commitment
  255. for share in &shares {
  256. let is_valid = verify_share(&share, &updated_commitment);
  257. assert!(is_valid.is_err());
  258. }
  259. }
  260. #[test]
  261. fn share_update_valid_multiple_updates() {
  262. let s = Secret::from(42u32);
  263. let res = generate_shares(s, 5, 2);
  264. assert!(res.is_ok());
  265. let (com, shares) = res.unwrap();
  266. // final shares to test at the end
  267. let mut updated_shares: Vec<Share> = Vec::with_capacity(5);
  268. // override these each time in the loop
  269. let mut next_shares = shares;
  270. let mut next_com = com;
  271. for i in 0..5 {
  272. // Create a new update
  273. let update_comm_res = create_update(5, 2);
  274. assert!(update_comm_res.is_ok());
  275. let (com_update, shares_update) = update_comm_res.unwrap();
  276. // Apply the update to previously-created committment
  277. let updated_commitment_res = apply_commitment_update(&next_com, &com_update);
  278. assert!(updated_commitment_res.is_ok());
  279. let updated_commitment = updated_commitment_res.unwrap();
  280. let mut iterim_shares: Vec<Share> = Vec::with_capacity(5);
  281. let mut updates_to_shares = shares_update.iter();
  282. for share in &next_shares {
  283. let share_update = updates_to_shares.next().unwrap();
  284. let update_share_res =
  285. apply_share_update(&share, &share_update, &updated_commitment);
  286. assert!(update_share_res.is_ok());
  287. let updated_share = update_share_res.unwrap();
  288. // only collect the last round of updated shares
  289. if i == 4 {
  290. updated_shares.push(updated_share);
  291. }
  292. iterim_shares.push(updated_share);
  293. }
  294. next_shares = iterim_shares;
  295. next_com = updated_commitment;
  296. }
  297. // assert that we can recover the original secret using the updated shares
  298. let recres = reconstruct_secret(&updated_shares);
  299. assert!(recres.is_ok());
  300. assert_eq!(recres.unwrap(), s);
  301. }
  302. }