Author Topic: Shuffle Bounty $200 BitUSD  (Read 14386 times)

0 Members and 1 Guest are viewing this topic.

Offline hrossik

  • Jr. Member
  • **
  • Posts: 38
    • View Profile
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.

Code: [Select]
/*
 * 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;
}
« Last Edit: April 08, 2015, 12:04:33 am by hrossik »
BTS: hr0550

zerosum

  • Guest
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); )
 
Code: [Select]
  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] ;
       
   }  }

Offline BTSdac

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
  • BitShares: K1
(

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
« Last Edit: April 07, 2015, 06:31:00 pm by BTSdac »
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
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

Code: [Select]
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:
Code: [Select]
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:
Code: [Select]
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.
« Last Edit: April 07, 2015, 05:44:02 pm by arhag »

Offline jsidhu

  • Hero Member
  • *****
  • Posts: 1335
    • View Profile
Code: [Select]
// 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.
« Last Edit: April 07, 2015, 05:31:18 pm by jsidhu »
Hired by blockchain | Developer
delegate: dev.sidhujag

Offline pc

  • Hero Member
  • *****
  • Posts: 1530
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BitShares: cyrano
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline emski

  • Hero Member
  • *****
  • Posts: 1282
    • View Profile
    • http://lnkd.in/nPbhxG
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.
« Last Edit: April 07, 2015, 04:28:50 pm by emski »

Offline hrossik

  • Jr. Member
  • **
  • Posts: 38
    • View Profile

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.
BTS: hr0550

Offline Frodo

  • Sr. Member
  • ****
  • Posts: 351
    • View Profile
  • BitShares: frodo
(...) 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.
« Last Edit: April 07, 2015, 04:18:33 pm by Frodo »

Offline logxing

(...) 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}
BTS Account:logxing

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
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.

Offline hrossik

  • Jr. Member
  • **
  • Posts: 38
    • View Profile
(...) 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.
BTS: hr0550

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
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.

Offline BTSdac

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
  • BitShares: K1
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
« Last Edit: April 07, 2015, 06:22:19 pm by BTSdac »
github.com :pureland
BTS2.0 API :ws://139.196.37.179:8091
BTS2.0 API 数据源ws://139.196.37.179:8091

Offline nomoreheroes7

  • Hero Member
  • *****
  • Posts: 756
  • King of all the land
    • View Profile
  • BitShares: nomoreheroes7
IF(Order = out_of_whack,organize,else "$200 BitUSD" GET)

end IF