Randomness of Witness Scheduling

[cryptosile]

Given a set of active witnesses,  the witness that goes next can be calculated as:

  ACTIVE_WITNESSES[ HASH(BLOCK_TIME)%NUM_ACTIVE_WITESSES ]

This approach means witnesses cannot influence the schedule at all and that the order of witnesses will be deterministic yet random.   

In which case if I have 2 or 3 bad witnesses I can identify times in the future where I'll control 3 or 4 or 5 blocks in a row (because witnesses could be repeated) and time my attack for that pre-determined time window.  You can't really do sha256(xyz)%ACTIVE_WITNESS as that mod operation is difficult to calculate correct?


A = NUM_ACTIVE_WITESSES
What if for every A blocks the SHA256(LAST A blocks full block data) is the seed to a PRNG that is used to cycle through all witnesses in a random non-repeating order.  The last witness can influence the order of the next A blocks but only by brute forcing a ton of hashes (by slighting changing the transactions he's including i.e. a transaction back to himself) to get a couple colluding witnesses in order.  (Someone will have to run the numbers on if I have 3 colluding witnesses, how many hashes do I have to do to have a 50% chance of finding a way to get them next to each other in the upcoming block order. 

You can get maximum coverage of witness nodes, but each time you run through the witnesses it's in a unique/random order that is influenced by 100% of active nodes so the randomness can't be controlled.  The last node has some additional power here.....   You can make it so that the last node of each of these super blocks can't include any transactions but can only include a random # from 1 - 10000, or something like that.  So if the last node of a super block is a good node he will use a real random number and screw up any badness from the previous node assuming the second to last node is a bad node.  However, if the opposite is true, the last node is a bad node, he only has 10000 different combinations to pick from to try and manipulate the witness order for the next A blocks.  Additionally if the last witness can't include any transactions, then the only naturally repeating witness occurrence would be when the last and first are the same witness but only in one of those blocks would he be able to include transactions.(because of the additional restriction on being the last block) 

Then you just tweak your maintenance interval to happen on these superblock intervals so that the number of Active witness doesn't change mid superblock. 

Maybe that's too complicated.  That's the best I could come up.

[sittingduck]

Your post in a no sequitur.  This has nothing to do with the number of witnesses. 


Sent from my iPhone using Tapatalk

[VoR0220]

Yeah I have to say I don't think this is a good idea. For one, I'm beginning to think there won't be enough volume (most definitely at first) to make it worth the overhead that 1 second blocks will produce. While it is quite the technical achievement, remember, this is far more than mastercard or visa can handle combined on any given day...that's a lot of transactions going on. By all means keep the 1 second blocks. It's allowing BTS to develop an incredible niche market for high speed trading. However, with that bloat comes security issues...there are far less people running full nodes as I have expressed many times as a security flaw and that there should be a brainstormed way to incentivize non witness/delegate nodes to run full chains. Even then! I can still accept that because of the light wallet web querying. But this is really pushing the envelope here. I know you're very big on low latency environments (which I think is awesome) however I think this is really compromising security especially in a realm where not everyone is on to vote as it is, and the voting time periods have been extended, so there's even the chance that the attacker wouldn't be kicked out. I truly think that this is a flawed approach to the issue of latency as it is expecting unrealistic expectations from shareholders and from your average participant. I hope you will consider this opinion and choose not to move forward with this and find another way to reach your low latency expectations. I should also add that while it may not be your intention, it does make the witnesses look a tad greedy when it comes to their payment schedule as they're sacrificing what really makes this unique...decentralization...for more pay (I can't really blame them for wanting more pay, but I also have stake in the product, so I must make my voice heard on the issue). Thanks again.

[cube]

You're asking us to improve performance at the cost of security. If the security benefit is negligible, meaning if it has never been exploited in test nets or has a low probability of being successfully exploited in practice, then go with performance but leave in the code so that through a parameter change such as a vote it can be switched back out of performance mode.

I am not sure how this would come across to an ordinary user who is going to entrust his/her money to the bts network.  The idea that they may lose their money, though it could be a remote chance, in order to get the benefit of a faster transaction from 10sec to 1sec.  Does the few-seconds improvement worth a lower security?

It is doubtful they would lose their money but Bytemaster would have to answer that.

I would never propose or support something that I thought would cause users to be at higher risk of loss than they are today.

I am glad to know that. End-users, techies or otherwise, have the assurance of security from the leader of bts himself.

[theoretical]

I have to look more deeply to learn more about RNG's, but couldn't you use blockchain transaction events & data for entropy?

You need some kind of commit / reveal scheme.  Otherwise an attacker would be able to control several bits by repurposing some field as a nonce and grinding it.  E.g. if Eve sends 0-255 satoshis to each of her 4 sock puppets, that's 2^32 possible blocks, and she can check which is favorable.  The attacker might need to control a single malicious witness if the block signature bytes are included directly or indirectly in the hash (only the witness would be able to check several signatures for hypothetical blocks).

We've been doing a lot of thinking about this, and the hard problem is that if the last participant to act in the protocol controls N bits of entropy, they can grind those bits for a favorable result.

In BTS 1.x this is mostly (but not entirely) mitigated by the commit/reveal process, the witnesses cryptographically commit to a hash on round K and then reveal the value that produces that hash on round K+1.  The last participant (actually the last N participants' actions where N=101 is the number of witnesses in a round) is locked to producing a block.  They still control 1 bit of entropy, however, since it is possible for them to drop out.

In any gambling game where the randomness is based entirely on blockchain entropy -- on any blockchain -- a dishonest block producer would be able to cheat fairly undetectably by making a bet, producing a block without broadcasting it, checking if they like the result of the game, then throwing away their block if they don't.  In essence allowing any player who controls a block producer to take the better outcome of 2 games which would likely give the player an edge over the house (very bad for the casino's financial viability).

[bytemaster]

You're asking us to improve performance at the cost of security. If the security benefit is negligible, meaning if it has never been exploited in test nets or has a low probability of being successfully exploited in practice, then go with performance but leave in the code so that through a parameter change such as a vote it can be switched back out of performance mode.

I am not sure how this would come across to an ordinary user who is going to entrust his/her money to the bts network.  The idea that they may lose their money, though it could be a remote chance, in order to get the benefit of a faster transaction from 10sec to 1sec.  Does the few-seconds improvement worth a lower security?

It is doubtful they would lose their money but Bytemaster would have to answer that.

I would never propose or support something that I thought would cause users to be at higher risk of loss than they are today.

[mike623317]

Security comes first. If revised witness node schedule does not harm any security, it sounds great.

  ...and as long as a=its tested, retested, tested again and everyone agrees it WORKS

[luckybit]

You're asking us to improve performance at the cost of security. If the security benefit is negligible, meaning if it has never been exploited in test nets or has a low probability of being successfully exploited in practice, then go with performance but leave in the code so that through a parameter change such as a vote it can be switched back out of performance mode.

I am not sure how this would come across to an ordinary user who is going to entrust his/her money to the bts network.  The idea that they may lose their money, though it could be a remote chance, in order to get the benefit of a faster transaction from 10sec to 1sec.  Does the few-seconds improvement worth a lower security?

It is doubtful they would lose their money but Bytemaster would have to answer that.

[cube]

You're asking us to improve performance at the cost of security. If the security benefit is negligible, meaning if it has never been exploited in test nets or has a low probability of being successfully exploited in practice, then go with performance but leave in the code so that through a parameter change such as a vote it can be switched back out of performance mode.

I am not sure how this would come across to an ordinary user who is going to entrust his/her money to the bts network.  The idea that they may lose their money, though it could be a remote chance, in order to get the benefit of a faster transaction from 10sec to 1sec.  Does the few-seconds improvement worth a lower security?

[luckybit]

I have to look more deeply to learn more about RNG's, but couldn't you use blockchain transaction events & data for entropy?

It's a nice algorithm but it needs analysis to prove it is random.

I would like to revise my statements:

Ben and I have had further discussions and have managed to achieve the following:

1. removing random number generation from witnesses which will reduce block header size by 46% and saving an "empty" blockchain 1.2GB per year.
2. keep rounds and prevent the same witness from going more than once
3. dramatically improve performance.

A separate issue of whether or not to have a witness produce N blocks in a row before rotating to the next witness is something to be considered separately.   In theory, allowing each witness to produce 2 blocks in a row would allow sub-second confirmation times without impacting security so long as we enforce the simple rule that a witness cannot miss their own block.   The benefits of sub-second confirmation time are that there would be less transactions "in-flight" at any given point in time.

You're asking us to improve performance at the cost of security. If the security benefit is negligible, meaning if it has never been exploited in test nets or has a low probability of being successfully exploited in practice, then go with performance but leave in the code so that through a parameter change such as a vote it can be switched back out of performance mode.

It may also be possible that some people have plenty of performance to sacrifice and would prefer security, so if there is a measurable difference in security based on practical rather than theoretical attack data, then I would say allow the individual to choose for themselves through a parameter switch of some sort to activate or deactivate.

If it isn't practical, and if witnesses are indeed not at a high probability of being picked on, then perhaps this is mostly theoretical, and it doesn't make sense to sacrifice performance for something theoretical.

Imagine for a second that our goal is "1 second blocks" so we have "instant" confirmation.  Imagine if we simply allowed every witness to produce 10 blocks in a row and then rotate?   This would give us instant confirmations while not reducing the security from what BitShares is today and has the benefit of having 0 latency between blocks produced in "groups" of 10.

I don't like this idea from a security POV. Right now, if I wait for 10 blocks, I have 10% of the network confirming my transaction, in this new scheme, I have 1%.

I agree.  I think that 1 second blocks with the same witness doing 10 in a row is actually just the same to me as 10 second block time.

There are two factors here:

1. every block produced is irreversible so you *KNOW* your transaction has been included and is unlikely to be reversed except potentially the last block produced by the witness if the next witness didn't see it in time. 
2. you still have to wait for 10*NUM_WITNESSES blocks to know for absolute certainty.
3. for markets the witness is committing to the order of transactions sooner rather than delaying.

So there is a significant difference in the normal situation of honest witnesses.

Good point about the market.  The witness committing to the order of trades during the 10 seconds means that you can see your trade has happened within 1 second instead of 10.


What happens if the next witness plays bad and ignores the 10 blocks by this witness?

The next witness would be ignored unless the next 2 collude to ignore those 10 blocks. 

I think viewing it from the perspective of 100,000 transactions per second, or 10,000 transactions every 0.1 seconds that having witnesses produce blocks every 0.1 seconds would dramatically improve the confirmation time to the round-trip time from the user to the witness and back which could easily be 0.5 seconds.   It would reduce the "active working set" and reduce a lot of uncertainty for high frequency traders.   

When you get into sub-second performance it is clearly impossible to not have consecutive block production due to the speed of light.  All we would be doing is apply the same principle to achieve 1 second with higher reliability in a young network.

Makes sense.

Regarding the random number generation.  Is it possible to still have witnesses generate a random number, even if it isnt used for purposes of determining who generates the next block?  There are a lot of useful applications that can be built around the blockchain generated random numbers.

This is what I mean by parameterization. If some witnesses want to generate the random numbers at the cost of performance then it should be allowed and the numbers could be useful. But the numbers have to be suitably random, so not produced by a deterministic process and not pseudo-random or they will not have much utility.

[merivercap]

I have to look more deeply to learn more about RNG's, but couldn't you use blockchain transaction events & data for entropy?

[Ander]

Imagine for a second that our goal is "1 second blocks" so we have "instant" confirmation.  Imagine if we simply allowed every witness to produce 10 blocks in a row and then rotate?   This would give us instant confirmations while not reducing the security from what BitShares is today and has the benefit of having 0 latency between blocks produced in "groups" of 10.

I don't like this idea from a security POV. Right now, if I wait for 10 blocks, I have 10% of the network confirming my transaction, in this new scheme, I have 1%.

I agree.  I think that 1 second blocks with the same witness doing 10 in a row is actually just the same to me as 10 second block time.

There are two factors here:

1. every block produced is irreversible so you *KNOW* your transaction has been included and is unlikely to be reversed except potentially the last block produced by the witness if the next witness didn't see it in time. 
2. you still have to wait for 10*NUM_WITNESSES blocks to know for absolute certainty.
3. for markets the witness is committing to the order of transactions sooner rather than delaying.

So there is a significant difference in the normal situation of honest witnesses.

Good point about the market.  The witness committing to the order of trades during the 10 seconds means that you can see your trade has happened within 1 second instead of 10.


What happens if the next witness plays bad and ignores the 10 blocks by this witness?

The next witness would be ignored unless the next 2 collude to ignore those 10 blocks. 

I think viewing it from the perspective of 100,000 transactions per second, or 10,000 transactions every 0.1 seconds that having witnesses produce blocks every 0.1 seconds would dramatically improve the confirmation time to the round-trip time from the user to the witness and back which could easily be 0.5 seconds.   It would reduce the "active working set" and reduce a lot of uncertainty for high frequency traders.   

When you get into sub-second performance it is clearly impossible to not have consecutive block production due to the speed of light.  All we would be doing is apply the same principle to achieve 1 second with higher reliability in a young network.

Makes sense.

Regarding the random number generation.  Is it possible to still have witnesses generate a random number, even if it isnt used for purposes of determining who generates the next block?  There are a lot of useful applications that can be built around the blockchain generated random numbers.

[monsterer]

There are two factors here:

1. every block produced is irreversible so you *KNOW* your transaction has been included and is unlikely to be reversed except potentially the last block produced by the witness if the next witness didn't see it in time. 
2. you still have to wait for 10*NUM_WITNESSES blocks to know for absolute certainty.
3. for markets the witness is committing to the order of transactions sooner rather than delaying.

So there is a significant difference in the normal situation of honest witnesses.

Blocks are not irreversible unless you can guarantee no forking, and you can't guarantee that in a system where the block producers can change at any time?

Where is the white paper on this?

[bytemaster]

Imagine for a second that our goal is "1 second blocks" so we have "instant" confirmation.  Imagine if we simply allowed every witness to produce 10 blocks in a row and then rotate?   This would give us instant confirmations while not reducing the security from what BitShares is today and has the benefit of having 0 latency between blocks produced in "groups" of 10.

I don't like this idea from a security POV. Right now, if I wait for 10 blocks, I have 10% of the network confirming my transaction, in this new scheme, I have 1%.

I agree.  I think that 1 second blocks with the same witness doing 10 in a row is actually just the same to me as 10 second block time.

There are two factors here:

1. every block produced is irreversible so you *KNOW* your transaction has been included and is unlikely to be reversed except potentially the last block produced by the witness if the next witness didn't see it in time. 
2. you still have to wait for 10*NUM_WITNESSES blocks to know for absolute certainty.
3. for markets the witness is committing to the order of transactions sooner rather than delaying.

So there is a significant difference in the normal situation of honest witnesses.

Good point about the market.  The witness committing to the order of trades during the 10 seconds means that you can see your trade has happened within 1 second instead of 10.


What happens if the next witness plays bad and ignores the 10 blocks by this witness?

The next witness would be ignored unless the next 2 collude to ignore those 10 blocks. 

I think viewing it from the perspective of 100,000 transactions per second, or 10,000 transactions every 0.1 seconds that having witnesses produce blocks every 0.1 seconds would dramatically improve the confirmation time to the round-trip time from the user to the witness and back which could easily be 0.5 seconds.   It would reduce the "active working set" and reduce a lot of uncertainty for high frequency traders.   

When you get into sub-second performance it is clearly impossible to not have consecutive block production due to the speed of light.  All we would be doing is apply the same principle to achieve 1 second with higher reliability in a young network.

[Ander]

Imagine for a second that our goal is "1 second blocks" so we have "instant" confirmation.  Imagine if we simply allowed every witness to produce 10 blocks in a row and then rotate?   This would give us instant confirmations while not reducing the security from what BitShares is today and has the benefit of having 0 latency between blocks produced in "groups" of 10.

I don't like this idea from a security POV. Right now, if I wait for 10 blocks, I have 10% of the network confirming my transaction, in this new scheme, I have 1%.

I agree.  I think that 1 second blocks with the same witness doing 10 in a row is actually just the same to me as 10 second block time.

There are two factors here:

1. every block produced is irreversible so you *KNOW* your transaction has been included and is unlikely to be reversed except potentially the last block produced by the witness if the next witness didn't see it in time. 
2. you still have to wait for 10*NUM_WITNESSES blocks to know for absolute certainty.
3. for markets the witness is committing to the order of transactions sooner rather than delaying.

So there is a significant difference in the normal situation of honest witnesses.

Good point about the market.  The witness committing to the order of trades during the 10 seconds means that you can see your trade has happened within 1 second instead of 10.


What happens if the next witness plays bad and ignores the 10 blocks by this witness?