Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: Shuffle Bounty $200 BitUSD  (Read 2384 times)

0 Members and 1 Guest are viewing this topic.

Offline bytemaster

Shuffle Bounty $200 BitUSD
« 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! 

For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline btswildpig

  • Hero Member
  • *****
  • Posts: 1424
    • View Profile
Re: Shuffle Bounty $200 BitUSD
« Reply #1 on: April 07, 2015, 02:08:41 PM »
"order"
this word means "command" or "sequence" in the OP ?
这个是私人账号,表达的一切言论均不代表任何团队和任何人。This is my personal account , anything I said with this account will be my opinion alone and has nothing to do with any group.

Offline pc

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BTS: cyrano
  • Witness: cyrano
  • Payrate: 100%
Re: Shuffle Bounty $200 BitUSD
« Reply #2 on: April 07, 2015, 02:33:42 PM »
"order"
this word means "command" or "sequence" in the OP ?
"sequence" in this case
Please vote for my BitShares witness "cyrano" and for my STEEM witness "cyrano.witness"!
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline nomoreheroes7

Re: Shuffle Bounty $200 BitUSD
« Reply #3 on: April 07, 2015, 02:44:31 PM »
IF(Order = out_of_whack,organize,else "$200 BitUSD" GET)

end IF

Offline BTSdac

Re: Shuffle Bounty $200 BitUSD
« Reply #4 on: April 07, 2015, 02:51:13 PM »
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 arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: Shuffle Bounty $200 BitUSD
« Reply #5 on: April 07, 2015, 03:35:07 PM »
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 hrossik

  • Jr. Member
  • **
  • Posts: 36
    • View Profile
Re: Shuffle Bounty $200 BitUSD
« Reply #6 on: April 07, 2015, 03:49:11 PM »
(...) 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
  • BTS: arhag
  • GitHub: arhag
Re: Shuffle Bounty $200 BitUSD
« Reply #7 on: April 07, 2015, 03:54:56 PM »
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 logxing

Re: Shuffle Bounty $200 BitUSD
« Reply #8 on: April 07, 2015, 03:59:31 PM »
(...) 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 Frodo

  • Sr. Member
  • ****
  • Posts: 342
    • View Profile
  • BTS: frodo
Re: Shuffle Bounty $200 BitUSD
« Reply #9 on: April 07, 2015, 04:11:07 PM »
(...) 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 hrossik

  • Jr. Member
  • **
  • Posts: 36
    • View Profile
Re: Shuffle Bounty $200 BitUSD
« Reply #10 on: April 07, 2015, 04:18:09 PM »

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 emski

  • Hero Member
  • *****
  • Posts: 1283
    • View Profile
    • http://lnkd.in/nPbhxG
Re: Shuffle Bounty $200 BitUSD
« Reply #11 on: April 07, 2015, 04:25:00 PM »
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 pc

  • Hero Member
  • *****
  • Posts: 1219
    • View Profile
    • Bitcoin - Perspektive oder Risiko?
  • BTS: cyrano
  • Witness: cyrano
  • Payrate: 100%
Please vote for my BitShares witness "cyrano" and for my STEEM witness "cyrano.witness"!
Bitcoin - Perspektive oder Risiko? ISBN 978-3-8442-6568-2 http://bitcoin.quisquis.de

Offline jsidhu

  • Hero Member
  • *****
  • Posts: 1337
    • View Profile
Re: Shuffle Bounty $200 BitUSD
« Reply #13 on: April 07, 2015, 05:27:54 PM »
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 arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BTS: arhag
  • GitHub: arhag
Re: Shuffle Bounty $200 BitUSD
« Reply #14 on: April 07, 2015, 05:39:38 PM »
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 »

 

Google+