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

0 Members and 1 Guest are viewing this topic.

Offline hrossik

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

Offline bytemaster

Any updates so far?

Paid!   Thanks for your effort and the great discussion in this thread!
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.

zerosum

  • Guest
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 !




Offline theoretical

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.
BTS- theoretical / PTS- PZxpdC8RqWsdU3pVJeobZY7JFKVPfNpy5z / BTC- 1NfGejohzoVGffAD1CnCRgo9vApjCU2viY / the delegate formerly known as drltc / Nothing said on these forums is intended to be legally binding / All opinions are my own unless otherwise noted / Take action due to my posts at your own risk

Offline bytemaster

Any updates so far?

I haven't forgotten this bounty.
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 hrossik

  • Jr. Member
  • **
  • Posts: 38
    • View Profile
Any updates so far?
BTS: hr0550

Offline bytemaster

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.
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 hrossik

  • Jr. Member
  • **
  • Posts: 38
    • View Profile
So what seems to be the consensus on this affair?

@bytemaster : do you need any additional analysis, improvement, info?
BTS: hr0550

Offline sittingduck

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

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
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.
« Last Edit: April 10, 2015, 05:12:04 pm by arhag »

Offline hrossik

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

Offline BTSdac

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

Offline liondani

  • Hero Member
  • *****
  • Posts: 3737
  • Inch by inch, play by play
    • View Profile
    • My detailed info
  • BitShares: liondani
  • GitHub: liondani
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)



Offline sittingduck

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

Offline arhag

  • Hero Member
  • *****
  • Posts: 1214
    • View Profile
    • My posts on Steem
  • BitShares: arhag
  • GitHub: arhag
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.
« Last Edit: April 09, 2015, 08:26:50 pm by arhag »