AElf随机数合约标准（ACS6）

本文主要讨论区块链系统中随机数的常见方案，AElf中对于可提供随机数的智能合约提供的标准接口，以及AEDPoS合约对ACS6的实现。

关于ACS的说明可见这篇文章的开头。

区块链和随机数

区块链系统中，与合约相关的随机数应用大致有几种场景：抽奖、验证码、密码相关等。

而由于区块链本质上是一个分布式系统，他要求各个节点的运算结果是可验证的，传统的随机数生成结果在不同机器上基本不会一致，让所有的节点产生同样的随机数又不造成过多的延时是不可能的。

好在区块链系统中生成一个可用的随机数，我们已知有几种方案。

中心化生成随机数。随机数由可信的第三方提供，如RANDOM.ORG。
Commitment方案，或者hash-commit-reveal方案。如果读者有读过AElf白皮书会发现AElf主链共识用于确定每一轮区块生产者确定生产顺序的in_value和out_value便采用了这种方案：区块生产者在本地生成一个随机的哈希值in_value后，先公布承诺（即out_value），其中out_value = hash(in_value)，到了合适的时机再公布随机哈希值in_value，其他节点只需要验证out_value == hash(in_value)就可以了。这里的in_value可以认为是一个随机数。
采集区块链状态信息作为种子，在合约中生成随机数。万一被人知道了随机数的生成算法（智能合约的代码是公开的），再获取到正确的种子，这个方案生成的随机数就可以成功预测的。不敢相信还真有人用这种方式。

显然，站在去中心化的角度上考量，Commitment方案至少是一个可用的方案，只需要保证作出承诺（commitment）的人不会自己偷偷提前公开随机数，或者自己利用随机数作弊即可。

然而很不幸，其实在区块链系统中，这是无法保证的：我们无法保证生成随机数的人不会利用信息不对等来做出不公平的事情，比如当这个随机数被作为某次赌局开奖的依据时，随机数的生成者哪怕在赌局开始之前就做出了承诺，依然可以选择性地中止公开这个随机数——这样相当于他得到了“再玩一次”的机会，因为如果他不公开这个随机数，要么赌局会选择其他人公开的随机数，要么这个赌局会作废。

如果预防随机数生产者的选择中止攻击呢？有一系列成熟的方案，参看Secret Sharing。

简单解释一下：现在有五个人A~E，每人掌握一个公私钥对，此时A产生了一个随机数Random，生成对应的承诺Commitment，同时将随机数Random与B、C、D、E的公钥进行加密得到四个SharingPart，加密SharingPart时便保证只需要凑够B~E中两个人就可以恢复Random，将SharingPart和Commitment一起公开。这样哪怕他自己因故没有公开Random的值，B~E中任意两个人用自己的私钥分别对自己收到的SharingPart解密，凑齐两个解密后的数值（要按A加密出SharingPart的顺序），便可以恢复出Random。而万一两个SharingPart没能恢复出Random，只能认为A从一开始就决定作恶——这时候只需要在区块链经济系统的设计中，让A付出代价就行了。比如直接扣除A申请称为随机数生产者缴纳的保证金。（TODO: 画图）

此外，我们还可以选择不依赖某一个个体产生的随机数，而是选择多个个体的随机数进一步计算哈希值作为应用场景中的可用随机数。如此我们可以比较稳定、安全地在区块链系统中得到随机数。

ACS6 - Random Number Provider Contract Standard

我在之前的一篇文章中解释了AElf区块链关于共识的合约标准，实际上是作为AElf主链开发者对合约开发者实现共识机制时推荐实现的接口。而关于随机数生成，我们制定了ACS6，作为对任何提供随机数的合约推荐要实现的接口。

不出意外地，ACS6是选择对Commitment方案进行抽象，得到的合约标准。

支持使用ACS6的场景如下：

用户对实现了ACS6的合约申请一个随机数，类似于发送了一个定单；
实现了ACS6的合约给用户返回一些信息，这些信息包括用户可以在哪个区块高度（H）获取得到一个随机数，以及用户获取随机数可用的凭据T（也是一个哈希值）；
等待区块链高度到达指定高度H后，用户发送交易尝试获取随机数，凭据T需要作为该交易的参数；
实现了ACS6的合约根据凭据T返回一个随机数。
如果用户尝试在高度H之前获取随机数，本次获取随机数的交易会执行失败并抛出一个AssertionException，提示高度还没到。

基于以上场景，我们设计的ACS6如下：

service RandomNumberProviderContract {
    rpc RequestRandomNumber (google.protobuf.Empty) returns (RandomNumberOrder) {
    }
    rpc GetRandomNumber (aelf.Hash) returns (aelf.Hash) {
    }
}

message RandomNumberOrder {
    sint64 block_height = 1;// Orderer can get a random number after this height.
    aelf.Hash token_hash = 2;
}

用户发送RequestRandomNumber交易来申请一个随机数，合约需要为本次请求生成一个凭据（token_hash），然后把该凭据和用户能够获取该随机数的区块高度一起返回给用户。高度达到以后，用户利用收到的凭据（token_hash）发送GetRandomNumber交易即可得到一个可用的随机数。作为合约，在实现该方法的时候应该缓存为用户生成的凭据，作为一个Map的key，这个Map的value则应该根据合约自己对随机数的实现自行定义数据结构。

比如，AEDPoS合约在实现ACS6的时候，可以将该Map的value定义为：

message RandomNumberRequestInformation {
    sint64 round_number = 1;
    sint64 order = 2;
    sint64 expected_block_height = 3;
}

其中round_number指示为了生成该用户申请的随机数，应该使用哪一轮（及之后）各个CDC公布的previous_in_value值；order为这个用户申请随机数的RandomNumberProviderContract交易被该轮第几个CDC打包（所以需要使用该轮该次序以后公布的previous_in_value作为随机数生成的“原材料”）；expected_block_height则是要告知给用户的需要等待到的区块高度。

AEDPoS合约对ACS6的一个实现

由于AEDPoS共识本身的推进过程中就采用了hash-commit-reveal的方式，可以直接使用每个CDC的产生普通区块（区别于额外区块）时公布的previous_in_value来作为生成随机数的原材料。新公布的previous_in_value的验证（即验证hash(previous_in_value) == previous_out_value）发生于任何节点执行新的区块之前，只要该区块被成功同步上best chain，就无需担心已经公布的previous_in_value存在弄虚作假的行为。

注意，本节的实现只是在刚刚定义好ACS6后的一个尝试，之后随时可能会有大幅度改动。

唯一要担心的是CDC共谋。因此AEDPoS在实现随机数生成的时候，不会仅仅采用一个CDC的previous_in_value来生成随机数，而是设置了五个：

public static class AEDPoSContractConstants
{
    ...
    public const int RandomNumberRequestMinersCount = 5;
}

当一个用户向AEDPoS请求随机数时，他只能等到当前轮的最后一个时间槽（额外区块时间槽），才可以百分之百保证本轮可公布的previous_in_value都已经公布了。因为可能存在本轮刚刚加入（也许是刚解决完分叉）的CDC，他没有previous_in_value可公布；也可能存在一些CDC由于本地缓存问题，未能公布previous_in_value，而到了额外区块的时间槽时，他的previous_in_value随着secret sharing的reveal阶段完成被恢复——如果我们允许用户在reveal阶段之前发送GetRandomNumber交易获取随机数，那么在reveal阶段之前和之后获取到的随机数可能会不一致，这会很令人困扰。

/// <summary>
/// In AEDPoS, we calculate next several continual previous_in_values to provide random hash.
/// </summary>
/// <param name="input"></param>
/// <returns></returns>
public override RandomNumberOrder RequestRandomNumber(Empty input)
{
    var tokenHash = Context.TransactionId;
    if (TryToGetCurrentRoundInformation(out var currentRound))
    {
        var lastMinedBlockMinerInformation = currentRound.RealTimeMinersInformation.Values.OrderBy(i => i.Order)
            .LastOrDefault(i => i.OutValue != null);

        var lastMinedBlockSlotOrder = lastMinedBlockMinerInformation?.Order ?? 0;

        var minersCount = currentRound.RealTimeMinersInformation.Count;
        // At most need to wait one round.
        var waitingBlocks = minersCount.Sub(lastMinedBlockSlotOrder).Add(1).Mul(AEDPoSContractConstants.TinyBlocksNumber);
        var expectedBlockHeight = Context.CurrentHeight.Add(waitingBlocks);
        State.RandomNumberInformationMap[tokenHash] = new RandomNumberRequestInformation
        {
            RoundNumber = currentRound.RoundNumber,
            Order = lastMinedBlockSlotOrder,
            ExpectedBlockHeight = expectedBlockHeight
        };
        return new RandomNumberOrder
        {
            BlockHeight = expectedBlockHeight,
            TokenHash = tokenHash
        };
    }

    Assert(false, "Failed to get current round information");

    // Won't reach here.
    return new RandomNumberOrder
    {
        BlockHeight = long.MaxValue
    };
}

用户使用凭据试图获取随机数时，AEDPoS会收集用户申请随机数后五个由CDC公布的previous_in_value，用这五个哈希值计算出来一个哈希值，作为一个可用的随机数返回给用户。

public override Hash GetRandomNumber(Hash input)
{
    var roundNumberRequestInformation = State.RandomNumberInformationMap[input];
    if (roundNumberRequestInformation == null)
    {
        Assert(false, "Random number token not found.");
        // Won't reach here.
        return Hash.Empty;
    }

    if (roundNumberRequestInformation.ExpectedBlockHeight > Context.CurrentHeight)
    {
        Assert(false, "Still preparing random number.");
    }

    var targetRoundNumber = roundNumberRequestInformation.RoundNumber;
    if (TryToGetRoundInformation(targetRoundNumber, out var targetRound))
    {
        var neededParticipatorCount = Math.Min(AEDPoSContractConstants.RandomNumberRequestMinersCount,
            targetRound.RealTimeMinersInformation.Count);
        var participators = targetRound.RealTimeMinersInformation.Values.Where(i =>
            i.Order > roundNumberRequestInformation.Order && i.PreviousInValue != null).ToList();
        var roundNumber = targetRoundNumber;
        TryToGetRoundNumber(out var currentRoundNumber);
        while (participators.Count < neededParticipatorCount && roundNumber <= currentRoundNumber)
        {
            roundNumber++;
            if (TryToGetRoundInformation(roundNumber, out var round))
            {
                var newParticipators = round.RealTimeMinersInformation.Values.OrderBy(i => i.Order)
                    .Where(i => i.PreviousInValue != null).ToList();
                var stillNeed = neededParticipatorCount - participators.Count;
                participators.AddRange(newParticipators.Count > stillNeed
                    ? newParticipators.Take(stillNeed)
                    : newParticipators);
            }
            else
            {
                Assert(false, "Still preparing random number, try later.");
            }
        }
        
        // Now we can delete this token_hash from RandomNumberInformationMap
        // TODO: Set null if deleting key supported.
        State.RandomNumberInformationMap[input] = new RandomNumberRequestInformation();

        var inValues = participators.Select(i => i.PreviousInValue).ToList();
        var randomHash = inValues.First();
        randomHash = inValues.Skip(1).Aggregate(randomHash, Hash.FromTwoHashes);
        return randomHash;
    }

    Assert(false, "Still preparing random number, try later.");

    // Won't reach here.
    return Hash.Empty;
}

接下来对这两个方法添加BVT测试用例。（关于AElf合约的测试有一个框架来着，可以用代码生成器生成一个能够调用某个合约方法的Stub，该Stub就可以模拟一个区块链上用户发交易，每个交易会单独打包为一个区块。之后有时间写文章详细介绍一下。）

在链刚刚启动的时候，由任意一个模拟用户的Stub发送RequestRandomNumber交易，检查能不能得到一个可用的RandomNumberOrder即可。由于在测试用例执行之前通过大量交易（目前是19个）部署必备的合约，因此在执行该RequestRandomNumber时，区块高度已经达到了20。

[Fact]
internal async Task<Hash> AEDPoSContract_RequestRandomNumber()
{
    var randomNumberOrder = (await AEDPoSContractStub.RequestRandomNumber.SendAsync(new Empty())).Output;
    randomNumberOrder.TokenHash.ShouldNotBeNull();
    randomNumberOrder.BlockHeight.ShouldBeGreaterThan(
        AEDPoSContractTestConstants.InitialMinersCount.Mul(AEDPoSContractTestConstants.TinySlots));
    return randomNumberOrder.TokenHash;
}

等到一定的高度后（正好一轮时间），模拟用户发送GetRandomNumber交易来获取随机数。以下的测试用例模拟第一轮的CDC进行正常生产区块的操作，也分别在目标高度（ExpectedBlockHeight）前后尝试发送GetRandomNumber。在高度没有达到时，交易执行结果为失败，错误信息中包含“Still preparing random number.”；第二次发送GetRandomNumber时，交易执行成功并返回可用的随机数值；第三次发送GetRandomNumber，因为相关随机数的信息已经被AEDPoS合约删除（节省空间），因此返回一个空的哈希值。

[Fact]
internal async Task AEDPoSContract_GetRandomNumber()
{
    var tokenHash = await AEDPoSContract_RequestRandomNumber();

    var currentRound = await BootMiner.GetCurrentRoundInformation.CallAsync(new Empty());

    var randomHashes = Enumerable.Range(0, AEDPoSContractTestConstants.InitialMinersCount).Select(_ => Hash.Generate()).ToList();
    var triggers = Enumerable.Range(0, AEDPoSContractTestConstants.InitialMinersCount).Select(i => new AElfConsensusTriggerInformation
    {
        PublicKey = ByteString.CopyFrom(InitialMinersKeyPairs[i].PublicKey),
        RandomHash = randomHashes[i]
    }).ToDictionary(t => t.PublicKey.ToHex(), t => t);

    // Exactly one round except extra block time slot.
    foreach (var minerInRound in currentRound.RealTimeMinersInformation.Values.OrderBy(m => m.Order))
    {
        var currentKeyPair = InitialMinersKeyPairs.First(p => p.PublicKey.ToHex() == minerInRound.PublicKey);

        KeyPairProvider.SetKeyPair(currentKeyPair);

        BlockTimeProvider.SetBlockTime(minerInRound.ExpectedMiningTime);

        var tester = GetAEDPoSContractStub(currentKeyPair);
        var headerInformation =
            (await tester.GetInformationToUpdateConsensus.CallAsync(triggers[minerInRound.PublicKey]
                .ToBytesValue())).ToConsensusHeaderInformation();

        // Update consensus information.
        var toUpdate = headerInformation.Round.ExtractInformationToUpdateConsensus(minerInRound.PublicKey);
        await tester.UpdateValue.SendAsync(toUpdate);

        for (var i = 0; i < 8; i++)
        {
            await tester.UpdateTinyBlockInformation.SendAsync(new TinyBlockInput
            {
                ActualMiningTime = TimestampHelper.GetUtcNow(),
                RoundId = currentRound.RoundId
            });
        }
    }
    
    // Not enough.
    {
        var transactionResult = (await AEDPoSContractStub.GetRandomNumber.SendAsync(tokenHash)).TransactionResult;
        transactionResult.Error.ShouldContain("Still preparing random number.");
    }

    // In test framework, the execution of every transaction will generate a new block no matter the execution succeeded.
    await AEDPoSContractStub.GetRandomNumber.SendAsync(tokenHash);

    // Now it's enough.
    {
        var randomNumber = (await AEDPoSContractStub.GetRandomNumber.SendAsync(tokenHash)).Output;
        randomNumber.Value.ShouldNotBeEmpty();
    }
    
    // Then this order deleted from state.
    {
        var randomNumber = (await AEDPoSContractStub.GetRandomNumber.SendAsync(tokenHash)).Output;
        randomNumber.Value.ShouldBeEmpty();
    }
}

欢迎来找茬。