BitShares Forum
Main => General Discussion => Topic started by: bytemaster on April 07, 2015, 01:12:48 pm
-
I am looking for a shuffle algorithm for delegates that has the following inputs:
vector<delegate_id> prev_delegate_order
vector<delegate_id> top_101_delegates_sorted_by_vote
sha256 random_seed
I need to calculate the "next_delegate_order" such that the minimum distance between the same delegate is N/2 the number of delegates while maximizing the entropy and mixing.
This algorithm should be implemented in c++ using int64_t as the delegate ID. I am looking for the best algorithm based upon the consensus on this thread.
Go!
-
"order"
this word means "command" or "sequence" in the OP ?
-
"order"
this word means "command" or "sequence" in the OP ?
"sequence" in this case
-
IF(Order = out_of_whack,organize,else "$200 BitUSD" GET)
end IF
-
I think it maybe not a big problem in BTS, because only use one time random No. to make sure the turn in next round per 101 blocks, but it maybe become key point in lottery if this dac want to play per block .
I have some ways
1.
1). before beginning of new round , produce delegate turn in the new round using old methods ,
2).check the min delegate interval between previous round and next round ,if the delegate interval is small than a constant no, I call N , then replace the place with max delegate interval
3).circle
I think if the N is not a big No. it would convergence rapidly
N is the delegate interval we can set
2.
1).divide the 101 delegates to two groups Acc. to previous round turn , A group from 1-67, B group from 68-101,
2).select 33 delegates from A group by random and join them to B group
3). sort delegate turn A group by random ,and make it as 1-34 turn in new round , also sort delegate turn B group by random and make it as 35-101 turn .
if delegate want to attack the maybe need to control 33 delegates
interval=33
3.
1).delegate have to publish two hash of secret random , one is for next round ,and other is for next next round , when he first create a block .
2).delegate reveal the secret random ( its hash had been publish in previous previous round by him ) and publish a hash of secret random that would been reveal in next next round .
the min interval between one delegate publish the hash of secret random and reveal the secret is larger than 101 block ( all delegate)
so maybe he cannot attack as follow
A-2 | XXXXA-1 | A0
when the time is at A0, the hash of secret random that the delegate reveal was published in A-2 ( mean previous two round). so though in the A-1 A can know what turn he in next round , but he cannot change the secret random that its hash was was published in previous two round
equivalent interval=101
-
I need to calculate the "next_delegate_order" such that the minimum distance between the same delegate is N/2 the number of delegates while maximizing the entropy and mixing.
I'm not sure I understand your requirements. If the index (0 to 100) of delegate A is n in one round and then it is shuffled to m in the next round, it means that you require |n - m| >= N/2 = 101/2 = 50.5? If so that is impossible. Where does delegate at index 50 (delegate rank 51) go? The two possible maximum indices are 0 and 100, but |50 - 0| = 50 and |50 - 100| = 50, both of which are smaller than 50.5.
Also, even if you relaxed that minimum distance requirement so it was possible, you would be unnecessarily (to me) reducing the possible shufflings allowed, so that would not allow for maximum entropy and mixing. Why exactly is the minimum distance requirement important and what is the problem with the current shuffling algorithm? If there is some reason you need that requirement but don't want to say, then at least make the requirement more precise because as stated it is either inconsistent or is too vague that I misinterpreted it as an impossible constraint.
-
(...) it means that you require |n - m| >= N/2 = 101/2 = 50.5?
I understood it the same way at the beginning and came to the same conclusion - it's impossible to make the shuffling random this way.
However, I think BM meant the word "distance" this way: If a delegate X has index i in the previous order and index j in the next order, then | (n - i) + j | >= n/2. Imagine it as 2 sequences one after another and there should be a gap of n/2 other delegates before X can go again.
-
However, I think BM meant the word "distance" this way: If a delegate X has index i in the previous order and index j in the next order, then | (n - i) + j | >= n/2. Imagine it as 2 sequences one after another and there should be a gap of n/2 other delegates before X can go again.
Ah of course. That makes sense. Thanks. Still would be great to get clarification from bytemaster on this, but I can see why that would be useful.
-
(...) it means that you require |n - m| >= N/2 = 101/2 = 50.5?
I understood it the same way at the beginning and came to the same conclusion - it's impossible to make the shuffling random this way.
However, I think BM meant the word "distance" this way: If a delegate X has index i in the previous order and index j in the next order, then | (n - i) + j | >= n/2. Imagine it as 2 sequences one after another and there should be a gap of n/2 other delegates before X can go again.
0 ->{0, 100}
1 ->{0, 100}
...
50 ->{0, 100}
51 ->{1, 100}
...
99 ->{49, 100}
100 ->{50, 100}
-
(...) it means that you require |n - m| >= N/2 = 101/2 = 50.5?
I understood it the same way at the beginning and came to the same conclusion - it's impossible to make the shuffling random this way.
However, I think BM meant the word "distance" this way: If a delegate X has index i in the previous order and index j in the next order, then | (n - i) + j | >= n/2. Imagine it as 2 sequences one after another and there should be a gap of n/2 other delegates before X can go again.
0 ->{0, 100}
1 ->{0, 100}
...
50 ->{0, 100}
51 ->{1, 100}
...
99 ->{49, 100}
100 ->{50, 100}
Not sure that this would be correct. New position 1 could be the same as old 100. (But maybe I misunderstood that notation)
I would do the following: swap the following positions:
i <-> pseudo_random{i, min(i+N/2,N-1)}
for all i in the old delegate array.
That should work in linear time and in place.
I'm not sure though whether every legal permutation is selected equally likely.
-
0 ->{0, 100}
1 ->{0, 100}
...
50 ->{0, 100}
51 ->{1, 100}
...
99 ->{49, 100}
100 ->{50, 100}
Yes, I have exactly this on my mind, except for you start from the end.
If we have the previous order a, and the next order b, then we do this mapping f:
f: a_100 -> <b_50, b_100>
a_99 -> <b_49, b_100> \ f(a_100)
...
a_(n-x) -> < b_(n/2 - x + 1), b_(n-1)> \ all previously generated fs
a_0 -> <0, b_(n-1)> \ all previously generated fs
where "\" is the set subtraction.
You have a probability 2/n for the first half of the elements. For the other half the probability follows the geometric serie with quotient 1/2. With element a_0 having only one number to map to => probability = 1.
I am not sure yet, but it also looks like a proof you can't find any better algorithm for it.
I am leaving from work now and don't have time to put it to code... Can do it later, if it is desirable.
-
The most trivial iterative solution I thought of first is:
Define min_delegate_slot as the slot with lowest possible index for a given delegate.
Define GetNextFreeSlot(X) as function that returns X-th free slot index
Then the algorigthm should be:
Iterate through prev_delegate_order in reverse order (starting from the last delegate with index 101)
if min_delegate_slot > 0 // for current delegate
Get RND defined as random number in the interval [0..N/2] using random_seed
Assign current delegate's slot as GetNextFreeSlot(min_delegate_slot + RND) // this is always possible and each delegate has (N/2+1) possible slots
else
Get RND defined as random number in the interval [0..remaining_free_delegate_slots] using random_seed
Assign current delegate's slot as GetNextFreeSlot(RND) // obviously this is always possible
It requires N sequential calls to the random function.
It should be "fast enough" and "random enough".
PS: Alternatively you can just select a random permutation of the first N/2 delegates (placing them in the free slots only) once you've placed the last (N/2+1) delegates. In this case the "else" should just pick a random permutation for the remaining N/2 delegates and distribute them to the free slots.
-
https://github.com/pmconrad/bitshares/tree/delegate_shuffle
-
// random_shuffle example
#include <iostream> // std::cout
#include <algorithm> // std::random_shuffle
#include <vector> // std::vector
#include <ctime> // std::time
#include <cstdlib> // std::rand, std::srand
// random generator function:
int myrandom (delegate_id i) { return std::rand()%i;}
int main () {
std::srand ( unsigned ( std::time(0) ) );
std::vector<delegate_id> myvector;
// set some values:
for (delegate_id i=0; i<101; ++i) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9...
// using built-in random generator:
std::random_shuffle ( myvector.begin(), myvector.end() );
// using myrandom:
std::random_shuffle ( myvector.begin(), myvector.end(), myrandom);
// print out content:
std::cout << "myvector contains:";
for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
return 0;
}
Should probably use the myrandom function with the gen passed into srand as the best way to implement this? Then in myrandom figure out your index.. although im still not sure why you want n/2 distance, what would happen at n/2 index? you only have 2 options 0 or n.
-
Define:
ITERATION_MAX1 = 41
ITERATION_MAX2 = 84
R = random_seed as uint256 integer
H(...) = SHA256 hash function
C1 = 51^44 (which is less than 2^254)
C2 = 51^6 * 51! (which is less than 2^250)
r1 = permutation selector 1
r2 = permutation selector 2
uint256 r1 = R;
for (uint k = 0; k < ITERATION_MAX1; ++k) { // Probability of continuing loop is 5.7% for each iteration assuming ideal hash function
if (r1 < C1) break;
r1 = H(r1) >> 2;
}
if (k == ITERATION_MAX1) {
r1 = C1 - 1; // In the extremely unlikely event (less than 10^-50 with ITERATION_MAX1 == 41) of reaching maximum iteration, bias the results.
}
uint256 r2 = H(R);
for (uint k = 0; k < ITERATION_MAX2; ++k) { // Probability of continuing loop is 24.9% for each iteration assuming ideal hash function
if (r2 < C2) break;
r2 = H(r2) >> 6;
}
if (k == ITERATION_MAX2) {
r2 = C2 - 1; // In the extremely unlikely event (less than 10^-50 with ITERATION_MAX2 == 84) of reaching maximum iteration, bias the results.
}
Then r1 defines the new locations of the last 44 delegates in the previous round, and r2 defines the new locations of the first 57 delegates in the previous round.
To actually convert these two numbers into a sequence of 101 delegate ID (vector<delegate_id> new_order), it requires a helper function with the following signature:
void add(vector<delegate_id>& new_order, delegate_id d, uint offset);
This function first assumes that delegate_id can contain a value that will not be mistaken for a valid delegate ID (for example -1) to represent a free slot. In fact, initially new_order is set to a vector of 101 -1's. The function add mutates new_order by adding the delegate_id d into the free slot reached by counting up to offset starting from the end of the vector (meaning counting in reverse order).
Using the above helper function the rest of the code is:
uint k = 101 - 1;
uint256 remainder = r1;
uint256 divisor1 = C1 / 51;
for (uint quotient; k >= 57; --k) {
quotient = (uint) (remainder / divisor1);
remainder = remainder % divisor1;
divisor1 = divisor1 / 51;
add(new_order, prev_delegate_order[k], quotient);
}
uint256 divisor2 = C2 / 51;
remainder = r2;
for (uint quotient; k >= 51; --k) {
quotient = (uint) (remainder / divisor2);
remainder = remainder % divisor2;
divisor2 = divisor2 / 51;
add(new_order, prev_delegate_order[k], quotient);
}
for (uint quotient; k >= 1; --k) {
quotient = (uint) (remainder / divisor2);
remainder = remainder % divisor2;
divisor2 = divisor2 / k;
add(new_order, prev_delegate_order[k], quotient);
}
add(new_order, prev_delegate_order[0], (uint) remainder);
Warning, I have not bothered to test any of the above code! Take this as pseudocode for the idea. Be aware of likely off-by-one errors. I also have still yet to write the add helper function but that should be straightforward. Also this is hard coded for 101 delegates. I would have to tweak it a little to make it work generally for any N delegates.
-
(
3.
1).delegate have to publish two hash of secret random when he first create block, one is for next round ,and other is for next next round , when he first create a block .
2).delegate reveal the secret random ( its hash had been publish in previous previous round by him ) and publish a hash of secret random that would been reveal in next next round .
the min interval between one delegate publish the hash of secret random and reveal the secret is larger than 101 block ( all delegate)
so maybe he cannot attack as follow
A-2 | XXXXA-1 | A0
when the time is at A0, the hash of secret random that the delegate reveal was published in A-2 ( mean previous two round). so though in the A-1 A can know what turn he in next round , but he cannot change the secret random that its hash was was published in previous two round
equivalent interval=101
you are all programmer can write code , :'( who can write code acc.to up ， it`s MIN equivalent interval=101? interval from 101 to 302
-
OK let me try this.
/////Put each delegate at allowed empty spot - this is any spot where j > i-(N/2+1)
///// Use random empty spot ->random [0; total empty spots]
//// the number of empty spots = (N/2+1) for the first half of the delegates; the first empty and allowed spot is at i-(N/2+1);
//// the number of empty spots decrease by one for each consecutive delegate for the second half of the delegates ( i.e decreses from (N/2+1); )
int N = 101;
int [] delOrder = new int [N];
int [] delOrder_new = new int [N];
for (int a=0; a < N; a++) {
delOrder[a]=a;
delOrder_new [a] = -1;
}
int min_empty=0;
int nb_of_empty = (N/2+1);
for (int a=N-1; a >= 0; a--) {
if ( a-(N/2+1)>=0) min_empty = a-(N/2+1);
else {nb_of_empty --; min_empty =0;}
int spot = (int) (Math.random()* nb_of_empty);
int cnt = -1;
for (int b= min_empty; b < N; b++){
if (delOrder_new [b] == -1) cnt++;
if ( cnt == spot) delOrder_new [b] = delOrder [a] ;
} }
-
Ok, I finally got to implement my former idea.
I separate the delegates to those which are constrained by the n/2 condition and to the rest. Each constrained delegate is placed to a random place chosen out of n/2 allowed positions (which is the max randomization allowed by the constraint). i-th unconstrained delegate can be placed at X positions, where X = NUM_DELEGATES - NUM_CONSTRAINED_DELEGATES - i (which is the classical way of generating permutations, so it is also optimal). I also account for the fact that delegates to be shuffled can (but don't have to) be different than the previous delegates.
/*
* File: main.cpp
* Author: Hrossik
*
* Created on April 7, 2015, 11:27 PM
*/
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#define NUM_DELEGATES 101
#define INVALID_DELEGATE -1
#define delegate_id int64_t
#define sha256 int
using namespace std;
vector<delegate_id> delegate_shuffle(vector<delegate_id>, vector<delegate_id>, sha256);
void printVec(vector<delegate_id>);
vector<delegate_id> delegate_shuffle(vector<delegate_id> prev_delegate_order, vector<delegate_id> top_101_delegates_sorted_by_vote, sha256 random_seed) {
// init
srand(random_seed);
vector<delegate_id> result;
const int lower_half = floor(NUM_DELEGATES / 2);
const int upper_half = ceil(NUM_DELEGATES / 2);
std::set<delegate_id> remaining(top_101_delegates_sorted_by_vote.begin(),
top_101_delegates_sorted_by_vote.end());
// prefill with empty/invalid delegates
for (int i = 0; i < NUM_DELEGATES; i++) {
result.push_back(INVALID_DELEGATE);
}
vector<delegate_id> constrained_delegates;
// find the delegates, which are constrained by the n/2 distance and are at top_101_delegates_sorted_by_vote so should be placed in the result
for (int i = NUM_DELEGATES; i > lower_half; i--) {
set<delegate_id>::iterator actual = remaining.find((delegate_id)prev_delegate_order[i]);
if (actual != remaining.end()) {
remaining.erase(actual);
constrained_delegates.push_back(prev_delegate_order[i]);
}
}
// init free slots for constrained delegates
vector<int> free_slots;
for (int i = 0; i < upper_half; i++) {
free_slots.push_back(NUM_DELEGATES - 1 - i);
}
// fill the result with constrained delegates. Each of them has n/2 possible locations
for (int i = 0; i < constrained_delegates.size(); i++) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = constrained_delegates[i];
// erase used slot
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
// add new slot, because next delegate's constraint is lower
free_slots.push_back(lower_half - i);
}
// fill free slots for the rest of the delegates
for (int i = lower_half - constrained_delegates.size(); i > -1; i--) {
free_slots.push_back(i);
}
// place the rest of the delegates. i-th delegate has X possible locations, where X = NUM_DELEGATES - constrained_delegates.size() - i
for (set<delegate_id>::iterator it = remaining.begin(); it != remaining.end(); ++it) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = *it;
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
}
return result;
}
-
So I had to change it up considerably compared to the previous method to generalize to N delegates.
Instead of trying to use all 256-bits of entropy directly to select the permutation, I am resorting to generating enough pseudorandom data from the random_seed to break it up into a sequence of just the number of bits necessary to get the appropriate-sized offset for each delegate that will be added into the new order. I can then use the same process to regenerate more of that pseudorandom data to replace the original so that I can keep iterating until an offset within the appropriate limit is selected for each of the delegates or until I hit maximum iteration in which case I bias the results by selecting an offset of 0 (but that should be an incredibly low probability event: less than 2^-100 with the current selection of the MAX_ITERATION constant below).
I also now actually update the set of delegates (remove voted out delegaes, add voted in delegates). To maximize entropy and mixing, the old delegates that have not been voted out are added first in reverse order of the prev_delegate_order (because the last half of prev_delegate_order are the ones that have constraints on where they can go), and then the new delegates are added.
#include <algorithm>
#include <vector>
#include <tuple>
#include <utility>
#include <fc/crypto/sha256.hpp>
#include <fc/exception/exception.hpp>
#include <string.h>
namespace bts { namespace blockchain {
typedef int64_t delegate_id;
// Calculates minimum number of bits needed to fit n
inline uint8_t
calculate_bit_size(uint32_t n)
{
uint8_t size = 1;
for (uint32_t bound = 2; n >= bound; bound = (1 << (++size)));
return size;
}
// Fills data with pseudorandom bytes using random seed and returns updated seed.
fc::sha256 generate_random_data(std::vector<uint8_t>& data, const fc::sha256& random_seed)
{
uint64_t num_bytes = data.size();
uint8_t hash_size = sizeof(random_seed._hash);
fc::sha256 seed(random_seed.data(), (size_t) hash_size);
for (uint64_t i = 0; i < num_bytes; i += hash_size) {
memcpy(data.data() + i, seed.data(), std::min((uint64_t) hash_size, num_bytes - i));
seed = fc::sha256::hash(seed);
}
return seed;
}
std::vector< std::pair<delegate_id, bool> >
prepend_new_delegates(const std::vector<delegate_id>& prev_delegate_order,
std::vector<delegate_id> top_101_delegates)
{
std::vector< std::tuple<delegate_id, uint32_t, bool> > prev_delegates;
prev_delegates.reserve(prev_delegate_order.size());
for (uint32_t i = 0; i < prev_delegate_order.size(); ++i)
prev_delegates.emplace_back(prev_delegate_order[i], i, false);
std::sort(prev_delegates.begin(), prev_delegates.end(),
[] (const std::tuple<delegate_id, uint32_t, bool>& a,
const std::tuple<delegate_id, uint32_t, bool>& b) {
return (std::get<0>(a) < std::get<0>(b));
});
std::sort(top_101_delegates.begin(), top_101_delegates.end());
std::vector< std::pair<delegate_id, bool> > delegate_list;
delegate_list.reserve(top_101_delegates.size() + prev_delegate_order.size());
auto old_it = prev_delegates.begin();
auto new_it = top_101_delegates.begin();
while (old_it != prev_delegates.end() || new_it != top_101_delegates.end()) {
if ((new_it == top_101_delegates.end()) || (std::get<0>(*old_it) < *new_it)) {
// delegate std::get<0>(*old_it) has been removed
*old_it = std::make_tuple(std::get<0>(*old_it), std::get<1>(*old_it), true);
++old_it;
} else if ((old_it == prev_delegates.end()) || (std::get<0>(*old_it) > *new_it)) {
// delegate *new_it has been added
delegate_list.emplace_back(*new_it, false);
++new_it;
} else {
++old_it;
++new_it;
}
}
uint32_t new_delegates = delegate_list.size();
delegate_list.resize(new_delegates + prev_delegates.size());
for (auto it = prev_delegates.begin(); it != prev_delegates.end(); ++it) {
uint32_t i = new_delegates + std::get<1>(*it);
delegate_list[i].first = std::get<0>(*it);
delegate_list[i].second = std::get<2>(*it);
}
return delegate_list;
}
struct ReorderData {
enum Status : uint8_t { PENDING = 0, COMPLETE };
delegate_id d;
uint32_t offset;
uint32_t limit;
uint64_t mask;
uint64_t byte_index;
uint8_t bit_shift;
uint8_t num_bytes;
Status status;
};
std::vector<delegate_id>
next_delegate_order(const std::vector<delegate_id>& prev_delegate_order,
const std::vector<delegate_id>& top_101_delegates_sorted_by_vote,
const fc::sha256& random_seed)
{
uint32_t num_delegates = prev_delegate_order.size();
auto delegate_list = prepend_new_delegates(prev_delegate_order, top_101_delegates_sorted_by_vote);
std::vector<ReorderData> reorder(num_delegates);
uint64_t byte_index = 0, bit_index = 0;
uint32_t middle = (num_delegates + 1)/2;
uint32_t limit = middle;
uint32_t i = num_delegates;
uint32_t j = num_delegates;
for (auto it = delegate_list.rbegin(); it != delegate_list.rend(); ++it) {
if (j < middle) {
--limit;
}
if (j > 0)
--j;
if (it->second) { // if missing
++limit;
continue;
}
FC_ASSERT( i > 0 );
--i;
reorder[i].d = it->first;
reorder[i].byte_index = byte_index;
reorder[i].limit = limit;
reorder[i].num_bytes = 1;
uint8_t remaining_bits = calculate_bit_size(limit);
uint64_t mask = 0;
while ((remaining_bits + bit_index) >= 8) {
remaining_bits = remaining_bits + bit_index - 8;
mask = mask | ( ((1 << (8 - bit_index)) - 1) << remaining_bits );
bit_index = 0;
++byte_index;
++(reorder[i].num_bytes);
}
reorder[i].bit_shift = 8 - (remaining_bits + bit_index);
reorder[i].mask = (mask | ((1 << remaining_bits) - 1)) << reorder[i].bit_shift;
bit_index += remaining_bits;
}
const uint32_t MAX_ITERATION = 100; // Probability of reaching max iteration is less than 2^(-MAX_ITERATION)
fc::sha256 seed = random_seed;
std::vector<uint8_t> random_data(byte_index + 1);
for (uint32_t k = 0; k < MAX_ITERATION; ++k) {
bool repeat = false;
seed = generate_random_data(random_data, seed);
for (int64_t i = num_delegates - 1; i >= 0; --i) {
if (reorder[i].status != ReorderData::Status::PENDING)
continue;
uint64_t value = 0;
uint16_t shift = (reorder[i].num_bytes - 1) * 8;
for (uint64_t j = reorder[i].byte_index, end = j + reorder[i].num_bytes; j < end; ++j) {
value = value | (random_data[j] << shift);
shift -= 8;
}
value = (value & reorder[i].mask) >> reorder[i].bit_shift;
if (value < reorder[i].limit) {
reorder[i].offset = value;
reorder[i].status = ReorderData::Status::COMPLETE;
} else {
repeat = true;
}
}
if (!repeat)
break;
}
const delegate_id free_slot = (delegate_id) (-1);
std::vector<delegate_id> new_order(num_delegates, free_slot);
for (int64_t i = num_delegates - 1; i >= 0; --i) {
uint32_t offset = (reorder[i].status == ReorderData::Status::PENDING) ?
0 : reorder[i].offset; // Biases result in case of max iteration
uint32_t j = num_delegates - 1;
for (; offset > 0; --j) {
if (new_order[j] == free_slot)
--offset;
}
for (; new_order[j] != free_slot; --j);
new_order[j] = reorder[i].d;
}
return new_order;
}
}}
-
However, I think BM meant the word "distance" this way: If a delegate X has index i in the previous order and index j in the next order, then | (n - i) + j | >= n/2. Imagine it as 2 sequences one after another and there should be a gap of n/2 other delegates before X can go again.
Ah of course. That makes sense. Thanks. Still would be great to get clarification from bytemaster on this, but I can see why that would be useful.
I was trying to figure out how to communicate that without drawing it on a white board, I assumed you smart people would see the problem and figure out what I meant. This is a good description of what I wanted.
-
Ok, I finally got to implement my former idea.
I separate the delegates to those which are constrained by the n/2 condition and to the rest. Each constrained delegate is placed to a random place chosen out of n/2 allowed positions (which is the max randomization allowed by the constraint). i-th unconstrained delegate can be placed at X positions, where X = NUM_DELEGATES - NUM_CONSTRAINED_DELEGATES - i (which is the classical way of generating permutations, so it is also optimal). I also account for the fact that delegates to be shuffled can (but don't have to) be different than the previous delegates.
/*
* File: main.cpp
* Author: Hrossik
*
* Created on April 7, 2015, 11:27 PM
*/
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#define NUM_DELEGATES 101
#define INVALID_DELEGATE -1
#define delegate_id int64_t
#define sha256 int
using namespace std;
vector<delegate_id> delegate_shuffle(vector<delegate_id>, vector<delegate_id>, sha256);
void printVec(vector<delegate_id>);
vector<delegate_id> delegate_shuffle(vector<delegate_id> prev_delegate_order, vector<delegate_id> top_101_delegates_sorted_by_vote, sha256 random_seed) {
// init
srand(random_seed);
vector<delegate_id> result;
const int lower_half = floor(NUM_DELEGATES / 2);
const int upper_half = ceil(NUM_DELEGATES / 2);
std::set<delegate_id> remaining(top_101_delegates_sorted_by_vote.begin(),
top_101_delegates_sorted_by_vote.end());
// prefill with empty/invalid delegates
for (int i = 0; i < NUM_DELEGATES; i++) {
result.push_back(INVALID_DELEGATE);
}
vector<delegate_id> constrained_delegates;
// find the delegates, which are constrained by the n/2 distance and are at top_101_delegates_sorted_by_vote so should be placed in the result
for (int i = NUM_DELEGATES; i > lower_half; i--) {
set<delegate_id>::iterator actual = remaining.find((delegate_id)prev_delegate_order[i]);
if (actual != remaining.end()) {
remaining.erase(actual);
constrained_delegates.push_back(prev_delegate_order[i]);
}
}
// init free slots for constrained delegates
vector<int> free_slots;
for (int i = 0; i < upper_half; i++) {
free_slots.push_back(NUM_DELEGATES - 1 - i);
}
// fill the result with constrained delegates. Each of them has n/2 possible locations
for (int i = 0; i < constrained_delegates.size(); i++) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = constrained_delegates[i];
// erase used slot
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
// add new slot, because next delegate's constraint is lower
free_slots.push_back(lower_half - i);
}
// fill free slots for the rest of the delegates
for (int i = lower_half - constrained_delegates.size(); i > -1; i--) {
free_slots.push_back(i);
}
// place the rest of the delegates. i-th delegate has X possible locations, where X = NUM_DELEGATES - constrained_delegates.size() - i
for (set<delegate_id>::iterator it = remaining.begin(); it != remaining.end(); ++it) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = *it;
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
}
return result;
}
So far after a quick glance I think I like your approach the best, but I will be honest I have not evaluated it closely enough relative to the other ideas to come to a final conclusion. Would anyone like to suggest a way of judging the best solution?
1) Predictable/Constant run time is a requirement.
2) Best mixing
3) best performance.
How can we actually "TEST" these methods to see whether or not they are doing a "good job"?
-
1) and 3) are easily evaluated empirically.
2) needs to be better defined.
-
1) and 3) are easily evaluated empirically.
2) needs to be better defined.
I think we're clear about 2. The list below maps an old index to a range of possible new indices. With the special case that recently voted in delegates are also mapped to {0,100}, and those voted out aren't mapped at all.
0 ->{0, 100}
1 ->{0, 100}
...
50 ->{0, 100}
51 ->{1, 100}
...
99 ->{49, 100}
100 ->{50, 100}
I think hrossik's implementation and mine are mostly equivalent, and optimal wrt mixing. Not sure if using a set for the free slots instead of a vector is faster, but it's probably hardly measurable anyway.
I like arhag's prng best (because I also wanted to use only as many bits from the seed as absolutely required, but I chose the easy way out - call it KISS, or call is lazy ;-) ), but apart from that I think his implementation is too complicated.
-
1) and 3) are easily evaluated empirically.
2) needs to be better defined.
Actually I think 2) is pretty clear. With 1) and 3) I can not help that much, because c++ is not my native programming language. From algorithmical point of view the only unpredictable part of my code is the intersection of the set of constrained delegates and the top_101_delegates_sorted_by_vote. You never know, how big the intersection will be. But I agree, that it could be computed in a more efficient way. Top_101_delegates are sorted, so we could use binary search for the lookup instead of find(), which has linear complexity. It would have to be tested, because I am not sure if my implementation of binary search on just 101 elements will beat native find, however it has worse asymptotic complexity.
From the c++ implementation point of view there also might be a better approach of tracking unused indexes in the result. I like the free_slots in my implementation, because it allows not only the tracking, but also generating the correct random index.
Edit: Hehe, delegates are sorted by votes, not id :) Still it might be reasonable to sort them by id in order to speed up their lookup. But this really depends on implementation- and number of delegates..
Edit2: To sum up the worst case analysis for intersection, we have (n * n/2) complexity with linear find, which gives 5101 operations for 101 delegates. With logarithmic find it's n*log n + n/2 * log n , which gives approx 304 operations. This might be worth the try.
-
Ok, I added the binary search and removed the unnecessary set. Overall speedup is around 27% (measured on 10k runs of the old and new approach). New implementation is in "delegate_shuffle", the old one is in "delegate_shuffle_linear".
/*
* File: main.cpp
* Author: Hrossik
*
* Created on April 7, 2015, 11:27 PM
*/
#include <cstdlib>
#include <vector>
#include <cmath>
#include <set>
#include <stdio.h>
#include <time.h>
#include <algorithm>
#define NUM_DELEGATES 101
#define INVALID_DELEGATE -1
#define delegate_id int
#define sha256 int
using namespace std;
vector<delegate_id> delegate_shuffle(vector<delegate_id>, vector<delegate_id>, sha256);
vector<delegate_id> delegate_shuffle_linear(vector<delegate_id>, vector<delegate_id>, sha256);
int binary_search(vector<delegate_id>, delegate_id);
void print_vec(vector<delegate_id>);
/*
*
*/
int main(int argc, char** argv) {
vector<delegate_id> prev_delegate_order;
for (int i = 0; i < NUM_DELEGATES; i++) {
prev_delegate_order.push_back(i);
}
vector<delegate_id> top_101_delegates_sorted_by_vote;
for (int i = 0; i < NUM_DELEGATES; i++) {
top_101_delegates_sorted_by_vote.push_back(i);
}
const int num_of_tests = 100000;
struct timespec start, stop;
double time_bin = 0;
for (int i = 0; i < num_of_tests; i++) {
clock_gettime(CLOCK_REALTIME, &start);
delegate_shuffle(prev_delegate_order, top_101_delegates_sorted_by_vote, time(NULL));
clock_gettime(CLOCK_REALTIME, &stop);
time_bin += (stop.tv_sec - start.tv_sec)*1000.0 + (stop.tv_nsec - start.tv_nsec) / 1000000.0;
}
double time_lin = 0;
for (int i = 0; i < num_of_tests; i++) {
clock_gettime(CLOCK_REALTIME, &start);
delegate_shuffle_linear(prev_delegate_order, top_101_delegates_sorted_by_vote, time(NULL));
clock_gettime(CLOCK_REALTIME, &stop);
time_lin += (stop.tv_sec - start.tv_sec)*1000.0 + (stop.tv_nsec - start.tv_nsec) / 1000000.0;
}
printf("time_bin = %.6lf, time_lin = %.6lf", time_bin, time_lin);
// test of binary_search
/*int count = 0;
for (int i = 0; i < prev_delegate_order.size(); i++) {
int ind = binary_search(prev_delegate_order, i);
if(ind == i) {
count++;
}
}
printf("count = %d\n",count);*/
return 0;
}
vector<delegate_id> delegate_shuffle(vector<delegate_id> prev_delegate_order, vector<delegate_id> top_101_delegates_sorted_by_vote, sha256 random_seed) {
// init
srand(random_seed);
vector<delegate_id> result;
const int lower_half = floor(NUM_DELEGATES / 2);
const int upper_half = ceil(NUM_DELEGATES / 2);
// sort top_101_delegates_sorted_by_vote by delegates
sort(top_101_delegates_sorted_by_vote.begin(),top_101_delegates_sorted_by_vote.end());
// prefill with empty/invalid delegates
for (int i = 0; i < NUM_DELEGATES; i++) {
result.push_back(INVALID_DELEGATE);
}
vector<delegate_id> constrained_delegates;
// find the delegates, which are constrained by the n/2 distance and are at top_101_delegates_sorted_by_vote so should be placed in the result
for (int i = NUM_DELEGATES; i > lower_half; i--) {
int actual = binary_search(top_101_delegates_sorted_by_vote, prev_delegate_order[i]);
if (actual != -1) {
top_101_delegates_sorted_by_vote.erase(top_101_delegates_sorted_by_vote.begin() + actual);
constrained_delegates.push_back(prev_delegate_order[i]);
}
}
// init free slots for constrained delegates
vector<int> free_slots;
for (int i = 0; i < upper_half; i++) {
free_slots.push_back(NUM_DELEGATES - 1 - i);
}
// fill the result with constrained delegates. Each of them has n/2 possible locations
for (int i = 0; i < constrained_delegates.size(); i++) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = constrained_delegates[i];
// erase used slot
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
// add new slot, because next delegate's constraint is lower
free_slots.push_back(lower_half - i);
}
// fill free slots for the rest of the delegates
for (int i = lower_half - constrained_delegates.size(); i > -1; i--) {
free_slots.push_back(i);
}
// place the rest of the delegates. i-th delegate has X possible locations, where X = NUM_DELEGATES - constrained_delegates.size() - i
for (int i = 0; i < top_101_delegates_sorted_by_vote.size(); i++) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = top_101_delegates_sorted_by_vote[i];
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
}
return result;
}
void print_vec(vector<delegate_id> vec) {
for (int i = 0; i < vec.size(); i++) {
printf("%d ", vec[i]);
}
printf("\n");
}
int binary_search(vector<delegate_id> sorted_vec, delegate_id wanted) {
int lower_bound = 0;
int upper_bound = sorted_vec.size() - 1;
while (lower_bound < upper_bound) {
int mid = (lower_bound + upper_bound) / 2;
if (wanted > sorted_vec[mid]) {
lower_bound = mid + 1;
} else {
upper_bound = mid;
}
}
if (sorted_vec[lower_bound] != wanted) {
lower_bound = -1;
}
return lower_bound;
}
vector<delegate_id> delegate_shuffle_linear(vector<delegate_id> prev_delegate_order, vector<delegate_id> top_101_delegates_sorted_by_vote, sha256 random_seed) {
// init
srand(random_seed);
vector<delegate_id> result;
const int lower_half = floor(NUM_DELEGATES / 2);
const int upper_half = ceil(NUM_DELEGATES / 2);
std::set<delegate_id> remaining(top_101_delegates_sorted_by_vote.begin(),
top_101_delegates_sorted_by_vote.end());
// prefill with empty/invalid delegates
for (int i = 0; i < NUM_DELEGATES; i++) {
result.push_back(INVALID_DELEGATE);
}
vector<delegate_id> constrained_delegates;
// find the delegates, which are constrained by the n/2 distance and are at top_101_delegates_sorted_by_vote so should be placed in the result
for (int i = NUM_DELEGATES; i > lower_half; i--) {
set<delegate_id>::iterator actual = remaining.find((delegate_id) prev_delegate_order[i]);
if (actual != remaining.end()) {
remaining.erase(actual);
constrained_delegates.push_back(prev_delegate_order[i]);
}
}
// init free slots for constrained delegates
vector<int> free_slots;
for (int i = 0; i < upper_half; i++) {
free_slots.push_back(NUM_DELEGATES - 1 - i);
}
// fill the result with constrained delegates. Each of them has n/2 possible locations
for (int i = 0; i < constrained_delegates.size(); i++) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = constrained_delegates[i];
// erase used slot
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
// add new slot, because next delegate's constraint is lower
free_slots.push_back(lower_half - i);
}
// fill free slots for the rest of the delegates
for (int i = lower_half - constrained_delegates.size(); i > -1; i--) {
free_slots.push_back(i);
}
// place the rest of the delegates. i-th delegate has X possible locations, where X = NUM_DELEGATES - constrained_delegates.size() - i
for (set<delegate_id>::iterator it = remaining.begin(); it != remaining.end(); ++it) {
int uniform_rand_free_slot = rand() % free_slots.size();
result[free_slots[uniform_rand_free_slot]] = *it;
free_slots.erase(free_slots.begin() + uniform_rand_free_slot);
}
return result;
}
-
IMO It's better to just have delegates reveal the number they hashed 2 rounds ago instead of prior round. The shuffling isn't the problem. You're just trying to have a random number each block to use for gambling. This way the random number is more robust (1 honest delegate is always enough)… it's also less complicated. Your way, collusion of a large number of delegates (but not all) could still be a problem and it would be very difficult to detect. I think for most gambling applications, allowing the players to participate in the secret/reveal random number gen process is probably the way to go anyway.
-
IMO It's better to just have delegates reveal the number they hashed 2 rounds ago instead of prior round. The shuffling isn't the problem. You're just trying to have a random number each block to use for gambling. This way the random number is more robust (1 honest delegate is always enough)… it's also less complicated. Your way, collusion of a large number of delegates (but not all) could still be a problem and it would be very difficult to detect. I think for most gambling applications, allowing the players to participate in the secret/reveal random number gen process is probably the way to go anyway.
A two round history would make the blockchain take more space and would be a much more involved change than simply changing the shuffle algorithm. There are benefits beyond gambling too.
-
IMO It's better to just have delegates reveal the number they hashed 2 rounds ago instead of prior round. The shuffling isn't the problem. You're just trying to have a random number each block to use for gambling. This way the random number is more robust (1 honest delegate is always enough)… it's also less complicated. Your way, collusion of a large number of delegates (but not all) could still be a problem and it would be very difficult to detect. I think for most gambling applications, allowing the players to participate in the secret/reveal random number gen process is probably the way to go anyway.
A two round history would make the blockchain take more space and would be a much more involved change than simply changing the shuffle algorithm. There are benefits beyond gambling too.
Why would a two round history take more blockchain space? It's still only one hash and one reveal per block... You have to keep a rolling database of 303 hashes instead of 202, doesn't seem an issue. What are the benefits beyond gambling? Using prior round hash for shuffling is not an issue and the current shuffling should be more random than the proposed new shuffling. The only issue with current system is that the random numbers from early in a round could possibly be manipulated... but if you're not using them for gambling then who cares?
-
IMO It's better to just have delegates reveal the number they hashed 2 rounds ago instead of prior round. The shuffling isn't the problem. You're just trying to have a random number each block to use for gambling. This way the random number is more robust (1 honest delegate is always enough)… it's also less complicated. Your way, collusion of a large number of delegates (but not all) could still be a problem and it would be very difficult to detect. I think for most gambling applications, allowing the players to participate in the secret/reveal random number gen process is probably the way to go anyway.
A two round history would make the blockchain take more space and would be a much more involved change than simply changing the shuffle algorithm. There are benefits beyond gambling too.
Why would a two round history take more blockchain space? It's still only one hash and one reveal per block... You have to keep a rolling database of 303 hashes instead of 202, doesn't seem an issue. What are the benefits beyond gambling? Using prior round hash for shuffling is not an issue and the current shuffling should be more random than the proposed new shuffling. The only issue with current system is that the random numbers from early in a round could possibly be manipulated... but if you're not using them for gambling then who cares?
Actually no matter how you shuffle, the average interval block between public hash of secret is 101 blocks , but cannot keep all interval per delegate is 101,
because there are must have some delegates less than 101,some delegates larger than 101
if we make the MIN interval is larger than 90 by good shuffle,I think it is very easy . the random is honest and enough for BTS
but maybe not for game, it is the reason I suggest use two round history
(
3.
1).delegate have to publish two hash of secret random when he first create block, one is for next round ,and other is for next next round , when he first create a block .
2).delegate reveal the secret random ( its hash had been publish in previous previous round by him ) and publish a hash of secret random that would been reveal in next next round .
the min interval between one delegate publish the hash of secret random and reveal the secret is larger than 101 block ( all delegate)
so maybe he cannot attack as follow
A-2 | XXXXA-1 | A0
when the time is at A0, the hash of secret random that the delegate reveal was published in A-2 ( mean previous two round). so though in the A-1 A can know what turn he in next round , but he cannot change the secret random that its hash was was published in previous two round
equivalent interval=101
-
I think if we want to use random No. to play game, ,maybe we should update DPOS a little to fit the short time wait game to void the attack that delegate refuse produce block when he know he does`t win in the block his turn .
I mean though we use two round history hash. or very good shuffle, we also cannot defense this type attack
-
A A A A A
Sn-2 Sn-1 Sn Sn+1 Sn+2
H(Sn) H(Sn+1) H(Sn+2) H(Sn+3) H(Sn+4)
2 round is really simple method to solve problem AXXXA(all control by one person), not take more blockchain space.
And i like new shuffle algorithm too. Can we do both?
-
Actually no matter how you shuffle, the average interval block between public hash of secret is 101 blocks , but cannot keep all interval per delegate is 101,
because there are must have some delegates less than 101,some delegates larger than 101
so it is not really "one delegate is honest ,the random is honest" but we can very very close it . if we make the MIN interval is larger than 90 by good shuffle,I think it is very easy . the random is honest and enough for BTS
but maybe not for game, it is the reason I suggest use two round history
I might be misunderstanding you, but even though some delegates have interval more than 101 and some less than 101, the idea "one delegate is honest, the random is honest" is essentially true for the last random number of the round under the current system, because the interval for the last revealed number in the round is at least 101.
But yeah, it's a simplification and ignores intentionally not producing a block (this doesn't allow you to determine the random number but allows you to impact it). It also ignores skipping honest delegate's blocks on purpose.... At least these things might raise red flags or be detectable. Newly elected delegates would have to be handled right also.
I think if we want to use random No. to play game, ,maybe we should update DPOS a little to fit the short time wait game to void the attack that delegate refuse produce block when he know he does`t win in the block his turn .
I mean though we use two round history hash. or very good shuffle, we also cannot defense this type attack
Yea I think for gambling it's best to look at the specific application and delegate provided random numbers are likely not the best option. Maybe Dan has other things in mind.
-
Actually no matter how you shuffle, the average interval block between public hash of secret is 101 blocks , but cannot keep all interval per delegate is 101,
because there are must have some delegates less than 101,some delegates larger than 101
if we make the MIN interval is larger than 90 by good shuffle,I think it is very easy . the random is honest and enough for BTS
but maybe not for game, it is the reason I suggest use two round history
I might be misunderstanding you, but even though some delegates have interval more than 101 and some less than 101, the idea "one delegate is honest, the random is honest" is essentially true for the last random number of the round under the current system, because the interval for the last revealed number in the round is at least 101.
But yeah, it's a simplification and ignores intentionally not producing a block (this doesn't allow you to determine the random number but allows you to impact it). It also ignores skipping honest delegate's blocks on purpose.... At least these things might raise red flags or be detectable. Newly elected delegates would have to be handled right also.
I think if we want to use random No. to play game, ,maybe we should update DPOS a little to fit the short time wait game to void the attack that delegate refuse produce block when he know he does`t win in the block his turn .
I mean though we use two round history hash. or very good shuffle, we also cannot defense this type attack
Yea I think for gambling it's best to look at the specific application and delegate provided random numbers are likely not the best option. Maybe Dan has other things in mind.
yes you are right .so I edit my reply before your reply , :D :D i think there only use one time random No. in BTS per 101 block . though random of some delegate in the middle turn of round ， but the random from block in the end of round is perfect. (i hope my english can express me well :P)
-
My wish would be for DPOS to use threshold signatures to reduce a round of 101 blocks to just a single block. Then a random number is generated every block as part of the threshold signature that cannot be corrupted unless a super majority of the delegates collude. The threshold signature would always be of the block header of the previous block in the blockchain so that this way delegates have 8 seconds to generate the threshold signature rather than 2 seconds (assuming the client is designed to stop accepting new transactions into the pending block 2 seconds prior to the block-production deadline).
I would split the 101 delegates into two disjoint sequences that are updated every block. The first sequence might be as small as two delegates, while the second sequence will be the rest (e.g. 99 delegates). Each time a delegate is replaced, the delegate that was voted out of the 101 is removed from either the first or second sequences and the delegate that was voted in is appended to the second sequence. For every block (including missed ones), the head of the first sequence (the one who should be producing that block) is removed from the first sequence and appended to the second sequence (unless it was the delegate voted out in that block), and the head of the second sequence is removed and appended to the first sequence (and this is repeated again as many times as voted-out delegate in that block happened to be removed from the first sequence). And after that, for each produced block, the random number from the threshold signature of that block is used to shuffle the second sequence.
There can also be failover blocks which do not have a threshold signature (only the signature of the block producer). In the case of these blocks, the shuffling will not be done and the blockchain should behave as if the entropy source has temporary halted (only random numbers from the threshold signature should be used as the entropy source). Failover blocks are limited in the kind of transactions they can include in the block and the kind of behavior that is allowed to execute as part of the block. Only transactions that update BTS votes are allowed in failover blocks (as a means of changing the set of active delegates who can then hopefully begin produce blocks with threshold signatures again). A regular block at the same block height as a failover block is always preferred over the failover block during fork resolution.
-
The point of good entropy source is for smart contracts. I like the idea of using both two secrets and new shuffle
Sent from my iPhone using Tapatalk
-
The point of good entropy source is for smart contracts. I like the idea of using both two secrets and new shuffle
Sent from my iPhone using Tapatalk
I think we will have big announcements soon ! 8)
(http://www.overclockers.co.uk/LP/images/teaser_icon.jpg)
-
Current shuffle is "only one delegate is honest ,Random No. is honest " as BM said because we just use one time random No. at the end of per round.
so the follow methods is for the salutation we need use random No. less than 101 blocks.
Using two round history secret hash. if the random No. is combination the previous 100 blocks +current block in current system , but try to make the advantage of two
random history secret more evident, so increase the quantity more than 101 blocks , I would analyze it below. interval between secret hash published and reveal secret
is critical . it mean how many blocks delegate cannot change this secret in advance . so we want this is larger than 101 blocks that is enough in BTS because in DPOS
per round is 101 blocks include all delegates. but in DPOS each delegate know his turn in advance in next round , 10-101 blocks , for gambling there is a attack
https://bitsharestalk.org/index.php?topic=6764.0. so we have to reduce this advanced blocks , so we try to satisfy items:
1) make no one know which delegate is Nun(N1+1)th order.
2) make random No. per block released is the combination from all delegate random seed.
3)there include delegates order in the interval between secret hash published and revealed by any delegate
to achieve this aim
1) order of (N1+1) th is fixed by random No. form current block.
2) should larger than if MAX interval blocks for one delegate is small than the constant NC how many blocks infront random No. combinated by. then each delegate
must appear one time per NC blocks .
3) the MIN interval blocks between first block and third block for delegate should larger than a constant.
in DPOS of BTS, it can satisfy item 2 in most of blocks ,and 100% satisfy item 2 in the end block per round. but cannot satisfy item 1 because all delegate know his
order
at the beginning of per round. try to satisfy item 1,
but we can :
1)Does not determine the order per round , the probability delegate know his order would increase by proportion from 1/101 to 101/101, it would increase to 100% at
the
end block of per round so it cannot totally satisfy item 1
2) divide 101 delegate into several groups , order of groups is determine, but the order of delegate in group would change by per blocks how many blocks per group
include . it can reduce No. how many blocks in advance delegate know his order. but it would , if we divide 101 to ND groups , then each group have 101/ND
delegate , each delegate can know his order 101/ND blocks in advance. and he can predict his order in less than 101/ND blocks by probability ND/100
So I d like to suggeste a new mothods (there is a similar by by arhag
Actually I had publish this in QQ groups several days ago.
there are also 101 delegates ,but there only N1 delegates`s order is determine anytime . the order of (N1+1)th block would been selected from rest of delegates after
new block is released using the random No. it include .So there would been a sequences ,the delegates in this sequences all know his order. if we set N1=5 , delegate
would know his order 60 seconds ahead, so there are enough time to prepare. so there are a group include rest of delegates (101-N1) , so there is a continuous
changing sequences with N1 delegates .
if continuous miss blocks is small than N1, the block after miss block would determine all order that should been fixed by the missed blocks if the continuous miss
blocks is larger or equal than N1, the first unmissable block determine all next order until a new block is released.
then we need use a algorithm to select the delegate form candidate groups .
1) reorder the candidate groups per new block released
2) select the first one if the first one satisfy
1) interval between this order and his previous order >N2 ,
2) interval blocks between first block and third block of this delegate >N3
select this delegate as the N1+1 order ,else select the next one till satify the condition.
For example(N1=5)
current sequences is A-B-C-D-E , after delegate A release block , select a delegate from rest of delegates ,if is F then next sequences would become B-C-D-E-F, so there
is a continuous sequences any time.but there is a question if sequences like A-B-C-D-E-F-A-X1-X2-X3-X4-X5-A , delegate A produce 3 blocks in 13 blocks.
this is bad for gambling if in short wait game .so we select the MIN interval between two blocks produced by one delegate is N2. it is mean there are N3=(101-N1-N2)
delegates are candidates. probability that a delegate konw his order (N1+1)blocks in advance is 1/N3. if N3=26,it is less than 4% very small ,so this satisfy item 1) . and
probability that the max interval for one delegate small than N4=(202-N3) is 1- ((N3-1)/N3)^N4.
if we select N1=5 N2=70 then N3=26,N4=176, then this probability 98.5% ,if set NC=N4, then there are 98.5% probability each delegate appear one time per NC blocks .
it can satisfy item 2 * and item 3.
-
Only transactions that update BTS votes are allowed in failover blocks (...)
Doesn't every transaction update votes? Or you want to allow only transactions to yourself for this case?
-
Only transactions that update BTS votes are allowed in failover blocks (...)
Doesn't every transaction update votes? Or you want to allow only transactions to yourself for this case?
Yes. In failover mode, only transactions that update the delegate slate of a BTS balance (but do not change the withdraw condition) would be allowed. That means no transfers of funds, no market operations, no future smart contract transactions, etc. Failover mode basically means the DAC is temporarily not working with the exception of updating delegate votes so that it can resume normal operation. Ideally, the DAC will never have to enter failover mode because there will always be enough active delegates in the old delegate set to generate a threshold signature that signs the new block that updates the threshold public key to a new one created by the current active delegates.
-
For gambling purpose all that is necessary is to consider it an automatic loss if the prior block was skipped.
That will work for any case where one persons loss isn't someone else's gain.
Sent from my iPhone using Tapatalk
-
So what seems to be the consensus on this affair?
@bytemaster : do you need any additional analysis, improvement, info?
-
So what seems to be the consensus on this affair?
@bytemaster : do you need any additional analysis, improvement, info?
I need to take the solutions presented and integrate them into a patch for BTS. I will have Vikram look into this and make the final call. I appreciate your patience while we internalize the solutions presented.
-
Any updates so far?
-
Any updates so far?
I haven't forgotten this bounty.
-
I've been placed in charge of deciding on a winner for this thread.
This problem sounds a lot like something that might be on a final exam in a graduate level algorithms course.
Before seeing the solutions here, I came up with my own solution:
- Pick the delegate which will occupy the most constrained slot from the list of delegates which are eligible to occupy it, striking the delegate from the list of eligible delegates.
- Advance to the next-most-constrained slot, adding any additional delegate(s) which are eligible for it.
- Repeat until you run out of slots.
I also came up with some easy optimizations:
- Striking and inserting may be implemented efficiently by replacing the stricken item with the newly inserted item.
- Striking may be implemented efficiently by swapping the stricken item with the final item, then reducing the vector size by 1.
Both hrossik and pc implemented the following solution:
- Place the most constrained delegate in a slot for which it is eligible, striking the occupied slot from the list of available slots.
- Advance to the next-most-constrained delegate, adding any additional slot(s) for which it is eligible.
- Repeat until you run out of delegates.
It is clear that these community solutions are simply a "mirror" of my solution, indexing the opposite way. It is also clear that the optimizations apply equally to both solutions.
tonyk2 and arhag came to a similar solution as hrossik and pc, but tonyk2 and arhag are O(n^2) due to no explicit tracking of the free slots.
- arhag went to heroic lengths to provide high-quality uniformly distributed random numbers. I consider these efforts to be orthogonal to the task at hand, as pseudo-randomly generating integers uniformly over some range is a problem which is well-understood.
- pc's solution is more "idiomatic" C++, and written against BitShares.
- hrossik's solution was easier to read than pc's
- hrossik went the extra mile by eliminating set<> and using binary search, and measuring the performance gain.
The winner is: hrossik.
-
WOW
I am honored to even be included in the discussion...honestly I wanted to provide 3 [meaningful] lines-Java solution.
At any rate thanks for the time considering it and more importantly:
Congrats to hrossik !
-
Any updates so far?
Paid! Thanks for your effort and the great discussion in this thread!
-
I am of course aware of the not very high difficulty of the problem. I was just so curious about how it will get resolved. And I must say I am really happy with the result.
I generally like the approach of outsourcing smaller/modular jobs in the form of bounties. I hope Bytemaster is not too sad about his overestimation of the price and I also hope other bounties will be offered in the future.
With that said I am not here to earn money from the devs - once we have wallet 1.0 I intend on placing my own bounties funded from those $200.
So I would like to thank Bytemaster, Theoretical and all participants for doing this challenge and for fair resolution. It was fun!