From a664783542b8819fe974d653dce3dbb9d66d7639 Mon Sep 17 00:00:00 2001 From: "zhoujun.ma" Date: Mon, 19 Feb 2024 14:57:22 -0800 Subject: [PATCH 1/5] types update from randomnet --- Cargo.lock | 20 ++++++++++++++++++++ Cargo.toml | 1 + types/Cargo.toml | 2 ++ types/src/transaction/mod.rs | 9 ++++++++- 4 files changed, 31 insertions(+), 1 deletion(-) diff --git a/Cargo.lock b/Cargo.lock index f46ddcca9e138..c780a4cc27b9c 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -4133,6 +4133,7 @@ dependencies = [ "aptos-bitvec", "aptos-crypto", "aptos-crypto-derive", + "aptos-dkg", "aptos-experimental-runtimes", "ark-bn254", "ark-ff", @@ -4148,6 +4149,7 @@ dependencies = [ "claims", "coset", "derivative", + "fixed", "hex", "itertools 0.10.5", "jsonwebtoken 8.3.0", @@ -5158,6 +5160,12 @@ dependencies = [ "tokio", ] +[[package]] +name = "az" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7b7e4c2464d97fe331d41de9d5db0def0a96f4d823b8b32a2efd503578988973" + [[package]] name = "backoff" version = "0.4.0" @@ -7852,6 +7860,18 @@ version = "1.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "8fcfdc7a0362c9f4444381a9e697c79d435fe65b52a37466fc2c1184cee9edc6" +[[package]] +name = "fixed" +version = "1.25.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e29e5681dc8556fb9df1409e95eae050e12e8776394313da3546dcb8cf390c73" +dependencies = [ + "az", + "bytemuck", + "half 2.2.1", + "typenum", +] + [[package]] name = "fixed-hash" version = "0.7.0" diff --git a/Cargo.toml b/Cargo.toml index 8ddc2fc5106fa..3874cd0802edf 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -526,6 +526,7 @@ event-listener = "2.5.3" fail = "0.5.0" ff = "0.13" field_count = "0.1.1" +fixed = "1.25.1" flate2 = "1.0.24" futures = "0.3.29" futures-channel = "0.3.29" diff --git a/types/Cargo.toml b/types/Cargo.toml index 2c2a0ae267150..4748a39d19f68 100644 --- a/types/Cargo.toml +++ b/types/Cargo.toml @@ -17,6 +17,7 @@ anyhow = { workspace = true } aptos-bitvec = { workspace = true } aptos-crypto = { workspace = true } aptos-crypto-derive = { workspace = true } +aptos-dkg = { workspace = true } aptos-experimental-runtimes = { workspace = true } ark-bn254 = { workspace = true } ark-ff = { workspace = true } @@ -28,6 +29,7 @@ bcs = { workspace = true } bytes = { workspace = true } chrono = { workspace = true } derivative = { workspace = true } +fixed = { workspace = true } hex = { workspace = true } itertools = { workspace = true } jsonwebtoken = { workspace = true } diff --git a/types/src/transaction/mod.rs b/types/src/transaction/mod.rs index c7e77c67e3f6c..6e8e574bd2ff0 100644 --- a/types/src/transaction/mod.rs +++ b/types/src/transaction/mod.rs @@ -1817,7 +1817,14 @@ impl Transaction { pub fn try_as_block_metadata(&self) -> Option<&BlockMetadata> { match self { - Transaction::BlockMetadata(v1) => Some(v1), + Transaction::BlockMetadata(bm) => Some(bm), + _ => None, + } + } + + pub fn try_as_block_metadata_ext(&self) -> Option<&BlockMetadataExt> { + match self { + Transaction::BlockMetadataExt(bme) => Some(bme), _ => None, } } From 0299d766d23ad09a753b9fa7df691aafce2773a7 Mon Sep 17 00:00:00 2001 From: "zhoujun.ma" Date: Mon, 19 Feb 2024 16:36:39 -0800 Subject: [PATCH 2/5] update --- types/src/on_chain_config/aptos_features.rs | 15 +++++++++++++-- types/src/on_chain_config/consensus_config.rs | 4 ++++ 2 files changed, 17 insertions(+), 2 deletions(-) diff --git a/types/src/on_chain_config/aptos_features.rs b/types/src/on_chain_config/aptos_features.rs index a97fefbabf3a0..91f76b3065cda 100644 --- a/types/src/on_chain_config/aptos_features.rs +++ b/types/src/on_chain_config/aptos_features.rs @@ -3,9 +3,9 @@ use crate::on_chain_config::OnChainConfig; use serde::{Deserialize, Serialize}; - +use strum_macros::FromRepr; /// The feature flags define in the Move source. This must stay aligned with the constants there. -#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)] +#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, FromRepr)] #[allow(non_camel_case_types)] pub enum FeatureFlag { CODE_DEPENDENCY_CHECK = 1, @@ -115,6 +115,17 @@ impl Features { self.features[byte_index] &= !bit_mask; } + pub fn into_flag_vec(self) -> Vec { + let Self { features } = self; + features + .into_iter() + .flat_map(|byte| (0..8).map(move |bit_idx| byte & (1 << bit_idx) != 0)) + .enumerate() + .filter(|(_feature_idx, enabled)| *enabled) + .map(|(feature_idx, _)| FeatureFlag::from_repr(feature_idx).unwrap()) + .collect() + } + pub fn is_enabled(&self, flag: FeatureFlag) -> bool { let val = flag as u64; let byte_index = (val / 8) as usize; diff --git a/types/src/on_chain_config/consensus_config.rs b/types/src/on_chain_config/consensus_config.rs index 8af9db1c62605..9392dd0f7bef8 100644 --- a/types/src/on_chain_config/consensus_config.rs +++ b/types/src/on_chain_config/consensus_config.rs @@ -237,6 +237,10 @@ impl OnChainConsensusConfig { OnChainConsensusConfig::V3 { vtxn, .. } => vtxn.clone(), } } + + pub fn is_vtxn_enabled(&self) -> bool { + self.effective_validator_txn_config().enabled() + } } /// This is used when on-chain config is not initialized. From e1a7dcb03a378b1159ebd794428571829b441ea8 Mon Sep 17 00:00:00 2001 From: "zhoujun.ma" Date: Tue, 20 Feb 2024 15:54:38 -0800 Subject: [PATCH 3/5] lint --- aptos-move/aptos-vm/src/aptos_vm.rs | 42 ++++++++++++++++-- types/src/block_metadata_ext.rs | 59 ++++--------------------- types/src/randomness.rs | 68 ++++++++++++++++++++++++++++- 3 files changed, 115 insertions(+), 54 deletions(-) diff --git a/aptos-move/aptos-vm/src/aptos_vm.rs b/aptos-move/aptos-vm/src/aptos_vm.rs index 0b4207c3d5f58..7132c8496462c 100644 --- a/aptos-move/aptos-vm/src/aptos_vm.rs +++ b/aptos-move/aptos-vm/src/aptos_vm.rs @@ -37,13 +37,15 @@ use aptos_types::{ partitioner::PartitionedTransactions, }, block_metadata::BlockMetadata, - block_metadata_ext::BlockMetadataExt, + block_metadata_ext::{BlockMetadataExt, BlockMetadataWithRandomness}, chain_id::ChainId, fee_statement::FeeStatement, + move_utils::as_move_value::AsMoveValue, on_chain_config::{ new_epoch_event_key, ConfigurationResource, FeatureFlag, Features, OnChainConfig, TimedFeatureOverride, TimedFeatures, TimedFeaturesBuilder, }, + randomness::Randomness, state_store::StateView, transaction::{ authenticator::AnySignature, signature_verified_transaction::SignatureVerifiedTransaction, @@ -1772,13 +1774,47 @@ impl AptosVM { let mut session = self.new_session(resolver, SessionId::block_meta_ext(&block_metadata_ext)); - let args = serialize_values(&block_metadata_ext.get_prologue_ext_move_args()); + let block_metadata_with_randomness = match block_metadata_ext { + BlockMetadataExt::V0(_) => unreachable!(), + BlockMetadataExt::V1(v1) => v1, + }; + + let BlockMetadataWithRandomness { + id, + epoch, + round, + proposer, + previous_block_votes_bitvec, + failed_proposer_indices, + timestamp_usecs, + randomness, + } = block_metadata_with_randomness; + + let args = vec![ + MoveValue::Signer(AccountAddress::ZERO), // Run as 0x0 + MoveValue::Address(AccountAddress::from_bytes(id.to_vec()).unwrap()), + MoveValue::U64(epoch), + MoveValue::U64(round), + MoveValue::Address(proposer), + failed_proposer_indices + .into_iter() + .map(|i| i as u64) + .collect::>() + .as_move_value(), + previous_block_votes_bitvec.as_move_value(), + MoveValue::U64(timestamp_usecs), + randomness + .as_ref() + .map(Randomness::randomness_cloned) + .as_move_value(), + ]; + session .execute_function_bypass_visibility( &BLOCK_MODULE, BLOCK_PROLOGUE_EXT, vec![], - args, + serialize_values(&args), &mut gas_meter, ) .map(|_return_vals| ()) diff --git a/types/src/block_metadata_ext.rs b/types/src/block_metadata_ext.rs index 7ae6fb22608d4..5abf5dfd1ffaa 100644 --- a/types/src/block_metadata_ext.rs +++ b/types/src/block_metadata_ext.rs @@ -2,7 +2,7 @@ use crate::{block_metadata::BlockMetadata, randomness::Randomness}; use aptos_crypto::HashValue; -use move_core_types::{account_address::AccountAddress, value::MoveValue}; +use move_core_types::account_address::AccountAddress; use serde::{Deserialize, Serialize}; /// The extended block metadata. @@ -21,15 +21,15 @@ pub enum BlockMetadataExt { #[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)] pub struct BlockMetadataWithRandomness { - id: HashValue, - epoch: u64, - round: u64, - proposer: AccountAddress, + pub id: HashValue, + pub epoch: u64, + pub round: u64, + pub proposer: AccountAddress, #[serde(with = "serde_bytes")] - previous_block_votes_bitvec: Vec, - failed_proposer_indices: Vec, - timestamp_usecs: u64, - randomness: Option, + pub previous_block_votes_bitvec: Vec, + pub failed_proposer_indices: Vec, + pub timestamp_usecs: u64, + pub randomness: Option, } impl BlockMetadataExt { @@ -62,47 +62,6 @@ impl BlockMetadataExt { } } - pub fn get_prologue_ext_move_args(self) -> Vec { - let mut ret = vec![ - MoveValue::Signer(AccountAddress::ONE), - MoveValue::Address(AccountAddress::from_bytes(self.id().to_vec()).unwrap()), - MoveValue::U64(self.epoch()), - MoveValue::U64(self.round()), - MoveValue::Address(self.proposer()), - MoveValue::Vector( - self.failed_proposer_indices() - .iter() - .map(|x| MoveValue::U64((*x) as u64)) - .collect(), - ), - MoveValue::Vector( - self.previous_block_votes_bitvec() - .iter() - .map(|x| MoveValue::U8(*x)) - .collect(), - ), - MoveValue::U64(self.timestamp_usecs()), - ]; - - match self.randomness() { - None => { - ret.push(MoveValue::Bool(false)); - ret.push(MoveValue::Vector(vec![])); - }, - Some(randomness) => { - let move_bytes = randomness - .randomness() - .iter() - .copied() - .map(MoveValue::U8) - .collect(); - ret.push(MoveValue::Bool(true)); - ret.push(MoveValue::Vector(move_bytes)); - }, - } - ret - } - pub fn timestamp_usecs(&self) -> u64 { match self { BlockMetadataExt::V0(obj) => obj.timestamp_usecs(), diff --git a/types/src/randomness.rs b/types/src/randomness.rs index 27ee7dba850d0..63b185ec0f066 100644 --- a/types/src/randomness.rs +++ b/types/src/randomness.rs @@ -2,10 +2,25 @@ // Parts of the project are originally copyright © Meta Platforms, Inc. // SPDX-License-Identifier: Apache-2.0 -use crate::block_info::Round; +use crate::{block_info::Round, on_chain_config::OnChainConfig}; use aptos_crypto::HashValue; +use aptos_crypto_derive::SilentDebug; +use aptos_dkg::{weighted_vuf, weighted_vuf::traits::WeightedVUF}; +use once_cell::sync::OnceCell; use serde::{Deserialize, Serialize}; +pub type WVUF = weighted_vuf::pinkas::PinkasWUF; +pub type WvufPP = ::PublicParameters; +pub type PK = ::PubKey; +pub type SKShare = ::SecretKeyShare; +pub type PKShare = ::PubKeyShare; +pub type ASK = ::AugmentedSecretKeyShare; +pub type APK = ::AugmentedPubKeyShare; +pub type ProofShare = ::ProofShare; +pub type Delta = ::Delta; +pub type Evaluation = ::Evaluation; +pub type Proof = ::Proof; + #[derive(Clone, Serialize, Deserialize, Debug, PartialEq, Eq, Hash)] pub struct RandMetadataToSign { pub epoch: u64, @@ -79,6 +94,10 @@ impl Randomness { pub fn randomness(&self) -> &[u8] { &self.randomness } + + pub fn randomness_cloned(&self) -> Vec { + self.randomness.clone() + } } impl Default for Randomness { @@ -91,3 +110,50 @@ impl Default for Randomness { } } } + +#[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)] +pub struct PerBlockRandomness { + pub epoch: u64, + pub round: u64, + pub seed: Option>, +} + +impl OnChainConfig for PerBlockRandomness { + const MODULE_IDENTIFIER: &'static str = "randomness"; + const TYPE_IDENTIFIER: &'static str = "PerBlockRandomness"; +} + +#[derive(Clone, SilentDebug)] +pub struct RandKeys { + // augmented secret / public key share of this validator, obtained from the DKG transcript of last epoch + pub ask: ASK, + pub apk: APK, + // certified augmented public key share of all validators, + // obtained from all validators in the new epoch, + // which necessary for verifying randomness shares + pub certified_apks: Vec>, + // public key share of all validators, obtained from the DKG transcript of last epoch + pub pk_shares: Vec, +} + +impl RandKeys { + pub fn new(ask: ASK, apk: APK, pk_shares: Vec, num_validators: usize) -> Self { + let certified_apks = vec![OnceCell::new(); num_validators]; + + Self { + ask, + apk, + certified_apks, + pk_shares, + } + } + + pub fn add_certified_apk(&self, index: usize, apk: APK) -> anyhow::Result<()> { + assert!(index < self.certified_apks.len()); + if self.certified_apks[index].get().is_some() { + return Ok(()); + } + self.certified_apks[index].set(apk).unwrap(); + Ok(()) + } +} From dbe537c889b3bf0a609fbd655f2f1d9100d32611 Mon Sep 17 00:00:00 2001 From: "zhoujun.ma" Date: Tue, 20 Feb 2024 17:36:53 -0800 Subject: [PATCH 4/5] real dkg and rounding --- aptos-move/aptos-vm/src/aptos_vm.rs | 2 +- dkg/src/dkg_manager/mod.rs | 10 +- dkg/src/transcript_aggregation/mod.rs | 3 +- .../event-notifications/src/tests.rs | 2 +- types/src/dkg/dummy_dkg/mod.rs | 49 ++-- types/src/dkg/dummy_dkg/tests.rs | 17 +- types/src/dkg/mod.rs | 94 ++++-- types/src/dkg/real_dkg/mod.rs | 254 +++++++++++++++++ types/src/dkg/real_dkg/rounding/mod.rs | 238 ++++++++++++++++ types/src/dkg/real_dkg/rounding/tests.rs | 268 ++++++++++++++++++ 10 files changed, 872 insertions(+), 65 deletions(-) create mode 100644 types/src/dkg/real_dkg/mod.rs create mode 100644 types/src/dkg/real_dkg/rounding/mod.rs create mode 100644 types/src/dkg/real_dkg/rounding/tests.rs diff --git a/aptos-move/aptos-vm/src/aptos_vm.rs b/aptos-move/aptos-vm/src/aptos_vm.rs index 5ee4bacb2bda1..9daa9b3495625 100644 --- a/aptos-move/aptos-vm/src/aptos_vm.rs +++ b/aptos-move/aptos-vm/src/aptos_vm.rs @@ -45,8 +45,8 @@ use aptos_types::{ new_epoch_event_key, ConfigurationResource, FeatureFlag, Features, OnChainConfig, TimedFeatureOverride, TimedFeatures, TimedFeaturesBuilder, }, - state_store::{StateView, TStateView}, randomness::Randomness, + state_store::{StateView, TStateView}, transaction::{ authenticator::AnySignature, signature_verified_transaction::SignatureVerifiedTransaction, BlockOutput, EntryFunction, ExecutionError, ExecutionStatus, ModuleBundle, Multisig, diff --git a/dkg/src/dkg_manager/mod.rs b/dkg/src/dkg_manager/mod.rs index 091e385ea4c41..c0193bc23ddb0 100644 --- a/dkg/src/dkg_manager/mod.rs +++ b/dkg/src/dkg_manager/mod.rs @@ -16,7 +16,7 @@ use aptos_validator_transaction_pool::{TxnGuard, VTxnPoolState}; use futures_channel::oneshot; use futures_util::{future::AbortHandle, FutureExt, StreamExt}; use move_core_types::account_address::AccountAddress; -use rand::thread_rng; +use rand::{prelude::StdRng, thread_rng, SeedableRng}; use std::sync::Arc; #[allow(dead_code)] @@ -207,12 +207,12 @@ impl DKGManager { self.state = match &self.state { InnerState::NotStarted => { let public_params = DKG::new_public_params(dkg_session_metadata); - let mut rng = thread_rng(); - let input_secret = if cfg!(feature = "smoke-test") { - DKG::generate_predictable_input_secret_for_testing(self.dealer_sk.as_ref()) + let mut rng = if cfg!(feature = "smoke-test") { + StdRng::from_seed(self.my_addr.into_bytes()) } else { - DKG::InputSecret::generate(&mut rng) + StdRng::from_rng(thread_rng()).unwrap() }; + let input_secret = DKG::InputSecret::generate(&mut rng); let trx = DKG::generate_transcript( &mut rng, diff --git a/dkg/src/transcript_aggregation/mod.rs b/dkg/src/transcript_aggregation/mod.rs index 15a970277f39f..f0d896b2dfbf7 100644 --- a/dkg/src/transcript_aggregation/mod.rs +++ b/dkg/src/transcript_aggregation/mod.rs @@ -76,8 +76,7 @@ impl BroadcastStatus for Arc::try_into(event_notification.version).unwrap() ); last_version_received = event_notification.version.try_into().unwrap(); } else { diff --git a/types/src/dkg/dummy_dkg/mod.rs b/types/src/dkg/dummy_dkg/mod.rs index eed07088221ac..3d6a3d982e192 100644 --- a/types/src/dkg/dummy_dkg/mod.rs +++ b/types/src/dkg/dummy_dkg/mod.rs @@ -14,6 +14,7 @@ pub struct DummyDKG {} impl DKGTrait for DummyDKG { type DealerPrivateKey = bls12381::PrivateKey; + type DealtPubKeyShare = (); type DealtSecret = DummySecret; type DealtSecretShare = DummySecret; type InputSecret = DummySecret; @@ -29,11 +30,14 @@ impl DKGTrait for DummyDKG { DummySecret::aggregate(secrets) } - fn dealt_secret_from_input(input: &Self::InputSecret) -> Self::DealtSecret { + fn dealt_secret_from_input( + _pub_params: &Self::PublicParams, + input: &Self::InputSecret, + ) -> Self::DealtSecret { *input } - fn generate_transcript( + fn generate_transcript( _rng: &mut R, _params: &Self::PublicParams, input_secret: &Self::InputSecret, @@ -63,22 +67,18 @@ impl DKGTrait for DummyDKG { fn aggregate_transcripts( _params: &Self::PublicParams, - transcripts: Vec, - ) -> DummyDKGTranscript { - let mut all_secrets = vec![]; - let mut agg_contributions_by_dealer = BTreeMap::new(); - for transcript in transcripts { - let DummyDKGTranscript { - secret, - contributions_by_dealer, - } = transcript; - all_secrets.push(secret); - agg_contributions_by_dealer.extend(contributions_by_dealer); - } - DummyDKGTranscript { - secret: DummySecret::aggregate(all_secrets), - contributions_by_dealer: agg_contributions_by_dealer, - } + accumulator: &mut Self::Transcript, + element: Self::Transcript, + ) { + let DummyDKGTranscript { + secret, + contributions_by_dealer, + } = element; + accumulator + .contributions_by_dealer + .extend(contributions_by_dealer); + accumulator.secret = + DummySecret::aggregate(vec![std::mem::take(&mut accumulator.secret), secret]); } fn decrypt_secret_share_from_transcript( @@ -86,8 +86,8 @@ impl DKGTrait for DummyDKG { transcript: &DummyDKGTranscript, _player_idx: u64, _dk: &Self::NewValidatorDecryptKey, - ) -> anyhow::Result { - Ok(transcript.secret) + ) -> anyhow::Result<(DummySecret, ())> { + Ok((transcript.secret, ())) } fn reconstruct_secret_from_shares( @@ -108,15 +108,6 @@ impl DKGTrait for DummyDKG { fn get_dealers(transcript: &DummyDKGTranscript) -> BTreeSet { transcript.contributions_by_dealer.keys().copied().collect() } - - fn generate_predictable_input_secret_for_testing( - dealer_sk: &bls12381::PrivateKey, - ) -> DummySecret { - let bytes_8: [u8; 8] = dealer_sk.to_bytes()[0..8].try_into().unwrap(); - DummySecret { - val: u64::from_be_bytes(bytes_8), - } - } } #[derive(Copy, Clone, Debug, Default, PartialEq, Serialize, Deserialize)] diff --git a/types/src/dkg/dummy_dkg/tests.rs b/types/src/dkg/dummy_dkg/tests.rs index e1a91ea14e039..527d3d81c8207 100644 --- a/types/src/dkg/dummy_dkg/tests.rs +++ b/types/src/dkg/dummy_dkg/tests.rs @@ -118,7 +118,11 @@ fn test_dummy_dkg_correctness() { .iter() .map(|state| state.transcript.clone().unwrap()) .collect(); - let agg_transcript = DummyDKG::aggregate_transcripts(&pub_params, all_transcripts); + let mut agg_transcript = DummyDKGTranscript::default(); + all_transcripts.into_iter().for_each(|trx| { + DummyDKG::aggregate_transcripts(&pub_params, &mut agg_transcript, trx); + }); + assert!(DummyDKG::verify_transcript(&pub_params, &agg_transcript).is_ok()); // Optional check: bad transcript should be rejected. @@ -128,13 +132,14 @@ fn test_dummy_dkg_correctness() { // Every new validator decrypt their own secret share. for (idx, nvi) in new_validator_states.iter_mut().enumerate() { - nvi.secret_share = DummyDKG::decrypt_secret_share_from_transcript( + let (secret, _pub_key) = DummyDKG::decrypt_secret_share_from_transcript( &pub_params, &agg_transcript, idx as u64, &nvi.sk, ) - .ok() + .unwrap(); + nvi.secret_share = Some(secret); } // The dealt secret should be reconstructable. @@ -147,7 +152,9 @@ fn test_dummy_dkg_correctness() { DummyDKG::reconstruct_secret_from_shares(&pub_params, player_share_pairs).unwrap(); let all_input_secrets = dealer_states.iter().map(|ds| ds.input_secret).collect(); - let dealt_secret_from_input = - DummyDKG::dealt_secret_from_input(&DummyDKG::aggregate_input_secret(all_input_secrets)); + let dealt_secret_from_input = DummyDKG::dealt_secret_from_input( + &pub_params, + &DummyDKG::aggregate_input_secret(all_input_secrets), + ); assert_eq!(dealt_secret_from_reconstruct, dealt_secret_from_input); } diff --git a/types/src/dkg/mod.rs b/types/src/dkg/mod.rs index e8340d7d4595f..36cba59e72087 100644 --- a/types/src/dkg/mod.rs +++ b/types/src/dkg/mod.rs @@ -1,8 +1,9 @@ // Copyright © Aptos Foundation use crate::{ - dkg::dummy_dkg::DummyDKG, on_chain_config::OnChainConfig, - validator_verifier::ValidatorConsensusInfoMoveStruct, + dkg::real_dkg::RealDKG, + on_chain_config::OnChainConfig, + validator_verifier::{ValidatorConsensusInfo, ValidatorConsensusInfoMoveStruct}, }; use anyhow::Result; use aptos_crypto::Uniform; @@ -12,9 +13,12 @@ use move_core_types::{ move_resource::MoveStructType, }; use once_cell::sync::Lazy; -use rand::CryptoRng; +use rand::{CryptoRng, RngCore}; use serde::{Deserialize, Serialize}; -use std::{collections::BTreeSet, fmt::Debug}; +use std::{ + collections::BTreeSet, + fmt::{Debug, Formatter}, +}; #[derive(Clone, Serialize, Deserialize, Debug, PartialEq, Eq, CryptoHasher, BCSCryptoHash)] pub struct DKGTranscriptMetadata { @@ -37,13 +41,22 @@ pub static DKG_START_EVENT_MOVE_TYPE_TAG: Lazy = Lazy::new(|| TypeTag::Struct(Box::new(DKGStartEvent::struct_tag()))); /// DKG transcript and its metadata. -#[derive(Clone, Serialize, Deserialize, Debug, PartialEq, Eq)] +#[derive(Clone, Serialize, Deserialize, PartialEq, Eq)] pub struct DKGTranscript { pub metadata: DKGTranscriptMetadata, #[serde(with = "serde_bytes")] pub transcript_bytes: Vec, } +impl Debug for DKGTranscript { + fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result { + f.debug_struct("DKGTranscript") + .field("metadata", &self.metadata) + .field("transcript_bytes_len", &self.transcript_bytes.len()) + .finish() + } +} + impl DKGTranscript { pub fn new(epoch: u64, author: AccountAddress, transcript_bytes: Vec) -> Self { Self { @@ -63,7 +76,7 @@ impl DKGTranscript { } } -// The input of DKG. +/// Reflection of `0x1::dkg::DKGSessionMetadata` in rust. #[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)] pub struct DKGSessionMetadata { pub dealer_epoch: u64, @@ -71,44 +84,80 @@ pub struct DKGSessionMetadata { pub target_validator_set: Vec, } -// The input and the run state of DKG. +impl DKGSessionMetadata { + pub fn target_validator_consensus_infos_cloned(&self) -> Vec { + self.target_validator_set + .clone() + .into_iter() + .map(|obj| obj.try_into().unwrap()) + .collect() + } + + pub fn dealer_consensus_infos_cloned(&self) -> Vec { + self.dealer_validator_set + .clone() + .into_iter() + .map(|obj| obj.try_into().unwrap()) + .collect() + } +} + /// Reflection of Move type `0x1::dkg::DKGSessionState`. #[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)] pub struct DKGSessionState { pub metadata: DKGSessionMetadata, pub start_time_us: u64, - pub result: Vec, - pub deadline_microseconds: u64, + pub transcript: Vec, } +impl DKGSessionState { + pub fn target_epoch(&self) -> u64 { + self.metadata.dealer_epoch + 1 + } +} /// Reflection of Move type `0x1::dkg::DKGState`. #[derive(Clone, Debug, Default, Eq, PartialEq, Serialize, Deserialize)] pub struct DKGState { - pub last_complete: Option, + pub last_completed: Option, pub in_progress: Option, } +impl DKGState { + pub fn maybe_last_complete(&self, epoch: u64) -> Option<&DKGSessionState> { + match &self.last_completed { + Some(session) if session.target_epoch() == epoch => Some(session), + _ => None, + } + } + + pub fn last_complete(&self) -> &DKGSessionState { + self.last_completed.as_ref().unwrap() + } +} + impl OnChainConfig for DKGState { const MODULE_IDENTIFIER: &'static str = "dkg"; const TYPE_IDENTIFIER: &'static str = "DKGState"; } +/// NOTE: this is a subset of the full scheme. Some data items/algorithms are not used in DKG and are omitted. pub trait DKGTrait: Debug { type DealerPrivateKey; type PublicParams: Clone + Debug + Send + Sync; - type Transcript: Clone + Default + Send + Sync + Serialize + for<'a> Deserialize<'a>; + type Transcript: Clone + Send + Sync + Serialize + for<'a> Deserialize<'a>; type InputSecret: Uniform; type DealtSecret; type DealtSecretShare; - type NewValidatorDecryptKey; + type DealtPubKeyShare; + type NewValidatorDecryptKey: Uniform; fn new_public_params(dkg_session_metadata: &DKGSessionMetadata) -> Self::PublicParams; - fn generate_predictable_input_secret_for_testing( - dealer_sk: &Self::DealerPrivateKey, - ) -> Self::InputSecret; fn aggregate_input_secret(secrets: Vec) -> Self::InputSecret; - fn dealt_secret_from_input(input: &Self::InputSecret) -> Self::DealtSecret; - fn generate_transcript( + fn dealt_secret_from_input( + pub_params: &Self::PublicParams, + input: &Self::InputSecret, + ) -> Self::DealtSecret; + fn generate_transcript( rng: &mut R, params: &Self::PublicParams, input_secret: &Self::InputSecret, @@ -120,14 +169,15 @@ pub trait DKGTrait: Debug { fn aggregate_transcripts( params: &Self::PublicParams, - transcripts: Vec, - ) -> Self::Transcript; + accumulator: &mut Self::Transcript, + element: Self::Transcript, + ); fn decrypt_secret_share_from_transcript( pub_params: &Self::PublicParams, trx: &Self::Transcript, player_idx: u64, dk: &Self::NewValidatorDecryptKey, - ) -> Result; + ) -> Result<(Self::DealtSecretShare, Self::DealtPubKeyShare)>; fn reconstruct_secret_from_shares( pub_params: &Self::PublicParams, player_share_pairs: Vec<(u64, Self::DealtSecretShare)>, @@ -136,6 +186,6 @@ pub trait DKGTrait: Debug { } pub mod dummy_dkg; +pub mod real_dkg; -// TODO: replace with RealDKG. -pub type DefaultDKG = DummyDKG; +pub type DefaultDKG = RealDKG; diff --git a/types/src/dkg/real_dkg/mod.rs b/types/src/dkg/real_dkg/mod.rs new file mode 100644 index 0000000000000..f99e240751a10 --- /dev/null +++ b/types/src/dkg/real_dkg/mod.rs @@ -0,0 +1,254 @@ +// Copyright © Aptos Foundation + +use crate::{ + dkg::{real_dkg::rounding::DKGRounding, DKGSessionMetadata, DKGTrait}, + validator_verifier::{ValidatorConsensusInfo, ValidatorVerifier}, +}; +use anyhow::{anyhow, ensure}; +use aptos_crypto::{bls12381, bls12381::PrivateKey}; +use aptos_dkg::{ + pvss, + pvss::{ + traits::{Convert, Reconstructable, Transcript}, + Player, + }, +}; +use num_traits::Zero; +use rand::{CryptoRng, RngCore}; +use rounding::{RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD}; +use serde::{Deserialize, Serialize}; +use std::collections::BTreeSet; + +pub mod rounding; + +pub type WTrx = pvss::das::WeightedTranscript; +pub type DkgPP = ::PublicParameters; +pub type SSConfig = ::SecretSharingConfig; +pub type EncPK = ::EncryptPubKey; + +#[derive(Deserialize, Serialize, Clone, Debug, PartialEq, Eq)] +pub struct DKGPvssConfig { + pub epoch: u64, + // weighted config for randomness generation + pub wconfig: SSConfig, + // DKG public parameters + pub pp: DkgPP, + // DKG encryption public keys + pub eks: Vec, +} + +impl DKGPvssConfig { + pub fn new(epoch: u64, wconfig: SSConfig, pp: DkgPP, eks: Vec) -> Self { + Self { + epoch, + wconfig, + pp, + eks, + } + } +} + +pub fn build_dkg_pvss_config( + cur_epoch: u64, + next_validators: &[ValidatorConsensusInfo], +) -> DKGPvssConfig { + let validator_stakes: Vec = next_validators.iter().map(|vi| vi.voting_power).collect(); + + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + + println!( + "[Randomness] rounding: epoch {} starts, profile = {:?}", + cur_epoch, dkg_rounding.profile + ); + + let validator_consensus_keys: Vec = next_validators + .iter() + .map(|vi| vi.public_key.clone()) + .collect(); + + let consensus_keys: Vec = validator_consensus_keys + .iter() + .map(|k| k.to_bytes().as_slice().try_into().unwrap()) + .collect::>(); + + let wconfig = dkg_rounding.wconfig.clone(); + + let pp = DkgPP::default_with_bls_base(); + + DKGPvssConfig::new(cur_epoch, wconfig.clone(), pp, consensus_keys) +} + +#[derive(Debug)] +pub struct RealDKG {} + +#[derive(Clone, Debug)] +pub struct RealDKGPublicParams { + pub session_metadata: DKGSessionMetadata, + pub pvss_config: DKGPvssConfig, + pub verifier: ValidatorVerifier, +} + +impl DKGTrait for RealDKG { + type DealerPrivateKey = ::SigningSecretKey; + type DealtPubKeyShare = ::DealtPubKeyShare; + type DealtSecret = ::DealtSecretKey; + type DealtSecretShare = ::DealtSecretKeyShare; + type InputSecret = ::InputSecret; + type NewValidatorDecryptKey = ::DecryptPrivKey; + type PublicParams = RealDKGPublicParams; + type Transcript = WTrx; + + fn new_public_params(dkg_session_metadata: &DKGSessionMetadata) -> RealDKGPublicParams { + let pvss_config = build_dkg_pvss_config( + dkg_session_metadata.dealer_epoch, + &dkg_session_metadata.target_validator_consensus_infos_cloned(), + ); + let verifier = ValidatorVerifier::new(dkg_session_metadata.dealer_consensus_infos_cloned()); + RealDKGPublicParams { + session_metadata: dkg_session_metadata.clone(), + pvss_config, + verifier, + } + } + + fn aggregate_input_secret(secrets: Vec) -> Self::InputSecret { + secrets + .into_iter() + .fold(::InputSecret::zero(), |acc, item| { + acc + item + }) + } + + fn dealt_secret_from_input( + pub_params: &Self::PublicParams, + input: &Self::InputSecret, + ) -> Self::DealtSecret { + input.to(&pub_params.pvss_config.pp) + } + + fn generate_transcript( + rng: &mut R, + pub_params: &Self::PublicParams, + input_secret: &Self::InputSecret, + my_index: u64, + sk: &Self::DealerPrivateKey, + ) -> Self::Transcript { + let my_index = my_index as usize; + let my_addr = pub_params.session_metadata.dealer_validator_set[my_index].addr; + let aux = (pub_params.session_metadata.dealer_epoch, my_addr); + + WTrx::deal( + &pub_params.pvss_config.wconfig, + &pub_params.pvss_config.pp, + sk, + &pub_params.pvss_config.eks, + input_secret, + &aux, + &Player { id: my_index }, + rng, + ) + } + + fn verify_transcript( + params: &Self::PublicParams, + trx: &Self::Transcript, + ) -> anyhow::Result<()> { + // Verify dealer indices are valid. + let dealers = trx + .get_dealers() + .iter() + .map(|player| player.id) + .collect::>(); + let num_validators = params.session_metadata.dealer_validator_set.len(); + ensure!( + dealers.iter().all(|id| *id < num_validators), + "real_dkg::verify_transcript failed with invalid dealer index." + ); + + let all_eks = params.pvss_config.eks.clone(); + + let addresses = params.verifier.get_ordered_account_addresses(); + let dealers_addresses = dealers + .iter() + .filter_map(|&pos| addresses.get(pos)) + .cloned() + .collect::>(); + + let spks = dealers_addresses + .iter() + .filter_map(|author| params.verifier.get_public_key(author)) + .collect::>(); + + let aux = dealers_addresses + .iter() + .map(|address| (params.pvss_config.epoch, address)) + .collect::>(); + + trx.verify( + ¶ms.pvss_config.wconfig, + ¶ms.pvss_config.pp, + &spks, + &all_eks, + &aux, + )?; + + Ok(()) + } + + fn aggregate_transcripts( + params: &Self::PublicParams, + accumulator: &mut Self::Transcript, + element: Self::Transcript, + ) { + accumulator.aggregate_with(¶ms.pvss_config.wconfig, &element); + } + + fn decrypt_secret_share_from_transcript( + pub_params: &Self::PublicParams, + trx: &Self::Transcript, + player_idx: u64, + dk: &Self::NewValidatorDecryptKey, + ) -> anyhow::Result<(Self::DealtSecretShare, Self::DealtPubKeyShare)> { + let (sk, pk) = trx.decrypt_own_share( + &pub_params.pvss_config.wconfig, + &Player { + id: player_idx as usize, + }, + dk, + ); + Ok((sk, pk)) + } + + fn reconstruct_secret_from_shares( + pub_params: &Self::PublicParams, + player_share_pairs: Vec<(u64, Self::DealtSecretShare)>, + ) -> anyhow::Result { + let player_share_pairs = player_share_pairs + .into_iter() + .map(|(x, y)| (Player { id: x as usize }, y)) + .collect(); + let reconstructed_secret = ::DealtSecretKey::reconstruct( + &pub_params.pvss_config.wconfig, + &player_share_pairs, + ); + Ok(reconstructed_secret) + } + + fn get_dealers(transcript: &Self::Transcript) -> BTreeSet { + transcript + .get_dealers() + .into_iter() + .map(|x| x.id as u64) + .collect() + } +} + +pub fn maybe_dk_from_bls_sk( + sk: &PrivateKey, +) -> anyhow::Result<::DecryptPrivKey> { + let mut bytes = sk.to_bytes(); // in big-endian + bytes.reverse(); + ::DecryptPrivKey::try_from(bytes.as_slice()) + .map_err(|e| anyhow!("dk_from_bls_sk failed with dk deserialization error: {e}")) +} diff --git a/types/src/dkg/real_dkg/rounding/mod.rs b/types/src/dkg/real_dkg/rounding/mod.rs new file mode 100644 index 0000000000000..a30a6ac0932d8 --- /dev/null +++ b/types/src/dkg/real_dkg/rounding/mod.rs @@ -0,0 +1,238 @@ +// Copyright © Aptos Foundation + +use aptos_dkg::pvss::WeightedConfig; +use fixed::types::U64F64; +use std::{ + cmp::max, + fmt, + fmt::{Debug, Formatter}, +}; + +// dkg todo: move to config file +pub const SECRECY_THRESHOLD: f64 = 0.5; +pub const RECONSTRUCT_THRESHOLD: f64 = 2.0 / 3.0; + +pub fn total_weight_lower_bound(validator_stakes: &Vec) -> usize { + // Each validator has at least 1 weight. + validator_stakes.len() +} + +pub fn total_weight_upper_bound( + validator_stakes: &Vec, + reconstruct_threshold_in_stake_ratio: f64, + secrecy_threshold_in_stake_ratio: f64, +) -> usize { + assert!(reconstruct_threshold_in_stake_ratio > secrecy_threshold_in_stake_ratio); + let bound_1 = + ((1.0 / (reconstruct_threshold_in_stake_ratio - secrecy_threshold_in_stake_ratio)) + 1.0) + * (validator_stakes.len() as f64); + + let stake_sum = validator_stakes.iter().sum::(); + let stake_min = *validator_stakes.iter().min().unwrap(); + let bound_2 = stake_sum / stake_min + 1; + + max(bound_1 as usize, bound_2 as usize) +} + +#[derive(Clone, Debug)] +pub struct DKGRounding { + pub profile: DKGRoundingProfile, + pub wconfig: WeightedConfig, +} + +impl DKGRounding { + pub fn new( + validator_stakes: &Vec, + secrecy_threshold_in_stake_ratio: f64, + reconstruct_threshold_in_stake_ratio: f64, + ) -> Self { + assert!(reconstruct_threshold_in_stake_ratio > secrecy_threshold_in_stake_ratio); + + let total_weight_min = total_weight_lower_bound(validator_stakes); + let total_weight_max = total_weight_upper_bound( + validator_stakes, + reconstruct_threshold_in_stake_ratio, + secrecy_threshold_in_stake_ratio, + ); + + let profile = DKGRoundingProfile::new( + validator_stakes, + total_weight_min, + total_weight_max, + secrecy_threshold_in_stake_ratio, + reconstruct_threshold_in_stake_ratio, + ); + + let wconfig = WeightedConfig::new( + profile.reconstruct_threshold_in_weights as usize, + profile + .validator_weights + .iter() + .map(|w| *w as usize) + .collect(), + ) + .unwrap(); + + Self { profile, wconfig } + } +} + +#[derive(Clone)] +pub struct DKGRoundingProfile { + // calculated weights for each validator after rounding + pub validator_weights: Vec, + // The ratio of stake that may reveal the randomness, e.g. 50% + pub secrecy_threshold_in_stake_ratio: f64, + // The ratio of stake that always can reconstruct the randomness, e.g. 66.67% + pub reconstruct_threshold_in_stake_ratio: f64, + // The number of weights needed to reconstruct the randomness + pub reconstruct_threshold_in_weights: u64, +} + +impl Debug for DKGRoundingProfile { + fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { + write!( + f, + "total_weight: {}, ", + self.validator_weights.iter().sum::() + )?; + write!( + f, + "secrecy_threshold_in_stake_ratio: {}, ", + self.secrecy_threshold_in_stake_ratio + )?; + write!( + f, + "reconstruct_threshold_in_stake_ratio: {}, ", + self.reconstruct_threshold_in_stake_ratio + )?; + write!( + f, + "reconstruct_threshold_in_weights: {}, ", + self.reconstruct_threshold_in_weights + )?; + writeln!(f, "validator_weights: {:?}", self.validator_weights)?; + + Ok(()) + } +} + +impl DKGRoundingProfile { + pub fn new( + validator_stakes: &Vec, + total_weight_min: usize, + total_weight_max: usize, + secrecy_threshold_in_stake_ratio: f64, + reconstruct_threshold_in_stake_ratio: f64, + ) -> Self { + assert!(total_weight_min >= validator_stakes.len()); + assert!(total_weight_max >= total_weight_min); + assert!(secrecy_threshold_in_stake_ratio > 1.0 / 3.0); + assert!(secrecy_threshold_in_stake_ratio <= reconstruct_threshold_in_stake_ratio); + assert!(reconstruct_threshold_in_stake_ratio <= 2.0 / 3.0); + + let mut weight_low = total_weight_min as u64; + let mut weight_high = total_weight_max as u64; + let mut best_profile = compute_profile_fixed_point( + validator_stakes, + weight_low, + secrecy_threshold_in_stake_ratio, + ); + + if is_valid_profile(&best_profile, reconstruct_threshold_in_stake_ratio) { + return best_profile; + } + + // binary search for the minimum weight that satisfies the conditions + while weight_low <= weight_high { + let weight_mid = weight_low + (weight_high - weight_low) / 2; + let profile = compute_profile_fixed_point( + validator_stakes, + weight_mid, + secrecy_threshold_in_stake_ratio, + ); + + // Check if the current weight satisfies the conditions + if is_valid_profile(&profile, reconstruct_threshold_in_stake_ratio) { + best_profile = profile; + weight_high = weight_mid - 1; + } else { + weight_low = weight_mid + 1; + } + } + + best_profile + } + + pub fn default( + num_validators: usize, + secrecy_threshold_in_stake_ratio: f64, + reconstruct_threshold_in_stake_ratio: f64, + ) -> Self { + Self { + validator_weights: vec![1; num_validators], + secrecy_threshold_in_stake_ratio, + reconstruct_threshold_in_stake_ratio, + reconstruct_threshold_in_weights: (num_validators as f64 * SECRECY_THRESHOLD) as u64, + } + } +} + +fn is_valid_profile( + profile: &DKGRoundingProfile, + reconstruct_threshold_in_stake_ratio: f64, +) -> bool { + // ensure the reconstruction is below threshold and all validators have at least 1 weight + profile.reconstruct_threshold_in_stake_ratio <= reconstruct_threshold_in_stake_ratio + && profile.validator_weights.iter().all(|&w| w > 0) +} + +fn compute_profile_fixed_point( + validator_stakes: &Vec, + weights_sum: u64, + secrecy_threshold_in_stake_ratio: f64, +) -> DKGRoundingProfile { + // Use fixed-point arithmetic to ensure the same result across machines. + // See paper for details of the rounding algorithm + // https://eprint.iacr.org/2024/198 + let stake_sum: u64 = validator_stakes.iter().sum::(); + let stake_sum_fixed = U64F64::from_num(stake_sum); + let stake_per_weight: u64 = max(1, stake_sum / weights_sum); + let stake_per_weight_fixed = U64F64::from_num(stake_per_weight); + let mut delta_down_fixed = U64F64::from_num(0); + let mut delta_up_fixed = U64F64::from_num(0); + let mut validator_weights: Vec = vec![]; + for stake in validator_stakes { + let ideal_weight_fixed = U64F64::from_num(*stake) / stake_per_weight_fixed; + // rounded to the nearest integer + let rounded_weight_fixed = + (U64F64::from_num(*stake) / stake_per_weight_fixed + U64F64::from_num(0.5)).floor(); + validator_weights.push(rounded_weight_fixed.to_num::()); + if ideal_weight_fixed > rounded_weight_fixed { + delta_down_fixed += ideal_weight_fixed - rounded_weight_fixed; + } else { + delta_up_fixed += rounded_weight_fixed - ideal_weight_fixed; + } + } + let delta_total_fixed = delta_down_fixed + delta_up_fixed; + let secrecy_threshold_in_stake_ratio_fixed = U64F64::from_num(secrecy_threshold_in_stake_ratio); + let reconstruct_threshold_in_weights_fixed = + (secrecy_threshold_in_stake_ratio_fixed * stake_sum_fixed / stake_per_weight_fixed + + delta_up_fixed) + .ceil(); + let reconstruct_threshold_in_weights: u64 = + reconstruct_threshold_in_weights_fixed.to_num::(); + let stake_gap_fixed = stake_per_weight_fixed * delta_total_fixed / stake_sum_fixed; + let reconstruct_threshold_in_stake_ratio: f64 = + (secrecy_threshold_in_stake_ratio_fixed + stake_gap_fixed).to_num::(); + + DKGRoundingProfile { + validator_weights, + secrecy_threshold_in_stake_ratio, + reconstruct_threshold_in_stake_ratio, + reconstruct_threshold_in_weights, + } +} + +#[cfg(test)] +mod tests; diff --git a/types/src/dkg/real_dkg/rounding/tests.rs b/types/src/dkg/real_dkg/rounding/tests.rs new file mode 100644 index 0000000000000..4281553f3c584 --- /dev/null +++ b/types/src/dkg/real_dkg/rounding/tests.rs @@ -0,0 +1,268 @@ +// Copyright © Aptos Foundation + +use crate::dkg::real_dkg::rounding::{ + is_valid_profile, total_weight_lower_bound, total_weight_upper_bound, DKGRounding, + RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD, +}; +use aptos_dkg::pvss::WeightedConfig; +use rand::Rng; + +#[test] +fn compute_mainnet_rounding() { + let validator_stakes = MAINNET_STAKES.to_vec(); + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + // println!("mainnet rounding profile: {:?}", dkg_rounding.profile); + // Result: + // mainnet rounding profile: total_weight: 437, secrecy_threshold_in_stake_ratio: 0.5, reconstruct_threshold_in_stake_ratio: 0.5859020899996102, reconstruct_threshold_in_weights: 237, validator_weights: [10, 1, 9, 9, 1, 1, 9, 9, 1, 7, 8, 5, 2, 1, 9, 7, 1, 2, 1, 9, 2, 1, 1, 9, 1, 8, 10, 1, 1, 9, 1, 1, 1, 7, 9, 1, 1, 9, 1, 9, 1, 3, 1, 8, 1, 1, 7, 10, 3, 2, 1, 9, 1, 9, 1, 3, 8, 1, 10, 1, 1, 1, 9, 3, 8, 8, 3, 10, 1, 1, 7, 9, 2, 5, 2, 9, 9, 1, 4, 1, 1, 1, 1, 1, 2, 10, 1, 1, 9, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 9, 8, 1, 1, 9, 2, 1] + + let total_weight_min = total_weight_lower_bound(&validator_stakes); + let total_weight_max = + total_weight_upper_bound(&validator_stakes, RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD); + let total_weight = dkg_rounding.profile.validator_weights.iter().sum::(); + assert!(total_weight >= total_weight_min as u64); + assert!(total_weight <= total_weight_max as u64); + + assert!(is_valid_profile( + &dkg_rounding.profile, + RECONSTRUCT_THRESHOLD + )); +} + +#[test] +fn test_rounding_single_validator() { + let validator_stakes = vec![1_000_000]; + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + let wconfig = WeightedConfig::new(1, vec![1]).unwrap(); + assert_eq!(dkg_rounding.wconfig, wconfig); +} + +#[test] +fn test_rounding_equal_stakes() { + let num_runs = 100; + let mut rng = rand::thread_rng(); + for _ in 0..num_runs { + let validator_num = rng.gen_range(100, 500); + let validator_stakes = vec![1_000_000; validator_num]; + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + let wconfig = WeightedConfig::new( + (validator_num as f64 * SECRECY_THRESHOLD).ceil() as usize, + vec![1; validator_num], + ) + .unwrap(); + assert_eq!(dkg_rounding.wconfig, wconfig); + } +} + +#[test] +fn test_rounding_small_stakes() { + let num_runs = 100; + let mut rng = rand::thread_rng(); + for _ in 0..num_runs { + let validator_num = rng.gen_range(1, 500); + let mut validator_stakes = vec![]; + for _ in 0..validator_num { + validator_stakes.push(rng.gen_range(1, 10)); + } + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + + let total_weight_min = total_weight_lower_bound(&validator_stakes); + let total_weight_max = + total_weight_upper_bound(&validator_stakes, RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD); + let total_weight = dkg_rounding.profile.validator_weights.iter().sum::(); + assert!(total_weight >= total_weight_min as u64); + assert!(total_weight <= total_weight_max as u64); + assert!(is_valid_profile( + &dkg_rounding.profile, + RECONSTRUCT_THRESHOLD + )); + } +} + +#[test] +fn test_rounding_uniform_distribution() { + let num_runs = 100; + let mut rng = rand::thread_rng(); + // assuming each validator has a stake between 1_000_000 and 50_000_000, following uniform distribution + // randomly generate 100~500 validators' stake distribution + for _ in 0..num_runs { + let validator_num = rng.gen_range(100, 500); + let mut validator_stakes = vec![]; + for _ in 0..validator_num { + validator_stakes.push(rng.gen_range(1_000_000, 50_000_000)); + } + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + + let total_weight_min = total_weight_lower_bound(&validator_stakes); + let total_weight_max = + total_weight_upper_bound(&validator_stakes, RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD); + let total_weight = dkg_rounding.profile.validator_weights.iter().sum::(); + assert!(total_weight >= total_weight_min as u64); + assert!(total_weight <= total_weight_max as u64); + assert!(is_valid_profile( + &dkg_rounding.profile, + RECONSTRUCT_THRESHOLD + )); + } +} + +#[cfg(test)] +pub fn generate_approximate_zipf(size: usize, a: u64, b: u64, exponent: f64) -> Vec { + use num_traits::Float; + + let mut rng = rand::thread_rng(); + (0..size) + .map(|_| { + let random_uniform = rng.gen_range(0.0, 1.0); + let approximate_value = + a + ((b - a + 1) as f64 * (1.0 - random_uniform).powf(exponent)) as u64; + // Adjust value to be within the specified range [a, b] + approximate_value.clamp(a, b) + }) + .collect() +} + +#[test] +fn test_rounding_zipf_distribution() { + let num_runs = 100; + let mut rng = rand::thread_rng(); + // assuming each validator has a stake between 1_000_000 and 50_000_000, following zipf distribution + // randomly generate 100~500 validators' stake distribution + for _ in 0..num_runs { + let validator_num = rng.gen_range(100, 500); + let validator_stakes = generate_approximate_zipf(validator_num, 1_000_000, 50_000_000, 5.0); + let dkg_rounding = + DKGRounding::new(&validator_stakes, SECRECY_THRESHOLD, RECONSTRUCT_THRESHOLD); + + let total_weight_min = total_weight_lower_bound(&validator_stakes); + let total_weight_max = + total_weight_upper_bound(&validator_stakes, RECONSTRUCT_THRESHOLD, SECRECY_THRESHOLD); + let total_weight = dkg_rounding.profile.validator_weights.iter().sum::(); + assert!(total_weight >= total_weight_min as u64); + assert!(total_weight <= total_weight_max as u64); + assert!(is_valid_profile( + &dkg_rounding.profile, + RECONSTRUCT_THRESHOLD + )); + } +} + +#[cfg(test)] +pub const MAINNET_STAKES: [u64; 112] = [ + 210500217584363000, + 19015034427309200, + 190269409955015000, + 190372712607660000, + 13695461583653900, + 23008441599765600, + 190710275073260000, + 190710280752007000, + 10610983628971600, + 154224802732739000, + 175900128414965000, + 99375343208846800, + 33975409124588400, + 10741696639154700, + 190296758443194000, + 146931795395201000, + 17136059081003400, + 50029051467899600, + 10610346785890000, + 190293387423510000, + 38649607904320700, + 10599959445206200, + 10741007619737700, + 181012458336443000, + 12476986507395000, + 162711519739867000, + 210473652405885000, + 17652549388174200, + 10602173827686000, + 181016968624497000, + 10741717083802200, + 10601364932429600, + 10626550439528100, + 157588554433899000, + 190368494070257000, + 10602102958015200, + 10659605390935200, + 190296749885358000, + 10602246540607000, + 190691643530347000, + 10741129232477400, + 71848511917757900, + 10741464265442800, + 167168618455916000, + 10626776626668800, + 10899006338732500, + 154355154034690000, + 200386024285735000, + 53519567070710700, + 49607201233899200, + 10601653390317000, + 190575467847849000, + 16797596395552600, + 190366710793058000, + 10602477251277100, + 62443725129072300, + 163816210803988000, + 10610954198660500, + 201023046191587000, + 10601464591446000, + 10609852486777200, + 10601487012558200, + 180360219576606000, + 70316229167094400, + 163090136300726000, + 165716856572893000, + 64007132243756300, + 210458282376492000, + 12244035421744000, + 10601711009001400, + 156908154902803000, + 190688831761348000, + 40078251173380300, + 110184163534171000, + 38221801093982600, + 190373486881563000, + 191035674729349000, + 10602120712089200, + 76636833488874800, + 10602114283230900, + 12257823010913900, + 10741509540453600, + 10602136737656500, + 10602078523390900, + 38222380945714300, + 210500003057396000, + 10789031621748400, + 10741733031173300, + 183655787790140000, + 10610791490932400, + 10602182576946400, + 10741639855953200, + 10602203255280800, + 11938813410693300, + 10741355256561700, + 68993421760499900, + 10610344082022600, + 25112384536164900, + 22886710016497000, + 10602439528909000, + 10602834493124000, + 10602101852821800, + 16812894183934200, + 46140391561066400, + 16579223362042600, + 191035150659780000, + 169268334324248000, + 10600667662818000, + 10625918567828000, + 180685941615229000, + 38221788594331900, + 10516889883063100, +]; From 86778926bde121d2186ee4742b073293cbf97043 Mon Sep 17 00:00:00 2001 From: danielxiangzl Date: Wed, 21 Feb 2024 14:03:33 -0800 Subject: [PATCH 5/5] rounding --- types/src/dkg/real_dkg/rounding/mod.rs | 24 +++++++++++++++++++----- 1 file changed, 19 insertions(+), 5 deletions(-) diff --git a/types/src/dkg/real_dkg/rounding/mod.rs b/types/src/dkg/real_dkg/rounding/mod.rs index a30a6ac0932d8..34970fa142e86 100644 --- a/types/src/dkg/real_dkg/rounding/mod.rs +++ b/types/src/dkg/real_dkg/rounding/mod.rs @@ -23,13 +23,17 @@ pub fn total_weight_upper_bound( secrecy_threshold_in_stake_ratio: f64, ) -> usize { assert!(reconstruct_threshold_in_stake_ratio > secrecy_threshold_in_stake_ratio); - let bound_1 = - ((1.0 / (reconstruct_threshold_in_stake_ratio - secrecy_threshold_in_stake_ratio)) + 1.0) - * (validator_stakes.len() as f64); + let bound_1 = ((U64F64::from_num(1) + / U64F64::from_num( + reconstruct_threshold_in_stake_ratio - secrecy_threshold_in_stake_ratio, + )) + + U64F64::from_num(1)) + .to_num::() + * (validator_stakes.len() as u64); let stake_sum = validator_stakes.iter().sum::(); let stake_min = *validator_stakes.iter().min().unwrap(); - let bound_2 = stake_sum / stake_min + 1; + let bound_2 = stake_sum / max(1, stake_min) + 1; max(bound_1 as usize, bound_2 as usize) } @@ -128,7 +132,7 @@ impl DKGRoundingProfile { assert!(total_weight_min >= validator_stakes.len()); assert!(total_weight_max >= total_weight_min); assert!(secrecy_threshold_in_stake_ratio > 1.0 / 3.0); - assert!(secrecy_threshold_in_stake_ratio <= reconstruct_threshold_in_stake_ratio); + assert!(secrecy_threshold_in_stake_ratio < reconstruct_threshold_in_stake_ratio); assert!(reconstruct_threshold_in_stake_ratio <= 2.0 / 3.0); let mut weight_low = total_weight_min as u64; @@ -161,6 +165,16 @@ impl DKGRoundingProfile { } } + // todo: remove once aptos-dkg supports 0 weights + if !is_valid_profile(&best_profile, reconstruct_threshold_in_stake_ratio) { + println!("[Randomness] Rounding error: failed to find a valid profile, using default"); + return Self::default( + validator_stakes.len(), + secrecy_threshold_in_stake_ratio, + reconstruct_threshold_in_stake_ratio, + ); + } + best_profile }