AElf随机数合约标准ACS6

jiezi

5 年前

本文主要讨论区块链系统中随机数的常见方案，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: 画图）

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

我在之前的一篇文章中解释了 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 共识本身的推进过程中就采用了 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();}

}

欢迎来找茬。

AElf随机数合约标准ACS6

区块链和随机数

ACS6 – Random Number Provider Contract Standard

AEDPoS 合约对 ACS6 的一个实现