Feature request for hbbft: random numbers

[varasev]

Parity should generate twenty 32-bit 64-bit unsigned integer random numbers uniformly distributed in the range from 0 to 0xffffffff 0xffffffffffffffff and pass them into ReportingValidatorSet smart contract calling its storeRandom function. That function looks like the following:

uint256[] public currentRandom;

uint256 public constant MAX_VALIDATORS = 20;

modifier onlySystem() {
    require(msg.sender == 0xffffFFFfFFffffffffffffffFfFFFfffFFFfFFfE);
    _;
}

function storeRandom(uint256[] _random) public onlySystem {
    require(_random.length == MAX_VALIDATORS);
    currentRandom.length = 0;
    for (uint256 i = 0; i < _random.length; i++) {
        currentRandom.push(_random[i]);
    }
}

The storeRandom should be called right before a new validator set is requested (see the issue https://github.com/poanetwork/parity-ethereum/issues/33).

[afck]

The random_value option in hbbft only produces 48 random bytes, but now that I think of it, we probably don't even need that: Each validator should just add 20 random u32s to their contribution; if encryption is enabled, nobody will see each other's random numbers before the subset for the batch has been decided. After decryption, we xor the numbers in the accepted contributions. (That approach seems superior in every way: better guarantee of randomness, more efficient. Maybe we should even remove that option from hbbft again.)

[mbr]

I'm working at least 50% of this at the moment. =)

[mbr]

First half is here, I am still testing it though: #36.

[afck]

Given that, at least for these contracts, we only use the random numbers once per week, it seems wasteful to include them in every batch. To avoid this, we'd have to slightly change our criterion for calling ~requestNewValidatorSet~ newValidatorSet: Once the first block appears with a timestamp at least one week after the beginning of the staking epoch, the next block will be the one where random numbers are input and newValidatorSet is called.

(In the long term it would be nice to make the randomness available to all smart contracts; but I guess that'll be a bigger, separate issue anyway.)

[varasev]

@afck Please use the naming newValidatorSet instead of requestNewValidatorSet :) As we have agreed here: https://github.com/poanetwork/parity-ethereum/issues/33#issuecomment-440181575

[varasev]

Please expand the type of random number from u32 to u64 - now we need twenty 64-bit unsigned integer random numbers in the range from 0 to 0xffffffffffffffff: https://github.com/poanetwork/pos-contracts/blob/4299a5e33f9f8399df8aefadbb761dc44acab5aa/contracts/ReportingValidatorSet.sol#L180

[afck]

Should we use 19 instead of 20 validators? Both can tolerate 6 failures, but 6 out of 20 failing is more likely than 6 out of 19 failing, so 19 would actually be more secure, I think. (In general, numbers 3 f + 1 are best suited.)

I wonder whether we should even replace instead of remove malicious validators, to always keep the number exactly 19? That would require new random numbers, though, so we'd either have to just always include them, or wait for the next block before computing the new set, after someone has been found guilty.

Also, when discussing this issue with @mbr, I kept insisting for some reason that we need 20 (or now 19) "proper" random numbers, even though this could be much more efficient if we just produced one truly random u64 (or [u32; 4] or whatever), and then, after receiving that in a batch, use it as the seed in a deterministic RNG to create the 20 values. Now I think this wouldn't be any less secure?

[varasev]

Should we use 19 instead of 20 validators?

Technically there are no barriers to use 19 in the contract.

I wonder whether we should even replace instead of remove malicious validators, to always keep the number exactly 19?

I think we could start a new epoch in this case, but the epoch in which the malicious validator is removed will be shorter than one week. I'm not sure about that, @igorbarinov what can you say?

At the beginning of network's life there can be less than 19 validators, so the network has to work fine with less number of validators.

I kept insisting for some reason that we need 20 (or now 19) "proper" random numbers

Anyway, we need to have MAX_VALIDATORS (20 or 19) random numbers in the contract (even when there're less active validators at the moment of numbers generation): https://github.com/poanetwork/pos-contracts/blob/6991d478662ca0e9a597cb3fd6996bf2d7ea9a8a/contracts/ReportingValidatorSet.sol#L346 - please take into account this requirement.

[varasev]

The storeRandom function has been moved to Random contract: https://github.com/poanetwork/pos-contracts/commit/ab5f8d797fc1b3582f4feedada1fd6480e891f47