如何计算随机种子？

Question

如何计算随机种子？

- 6
- 81 2019-05-08
例如,在周期99中显示了126/128个随机数. /chains/main/blocks/409599/context/raw/json/cycle/98/nonces?depth=1

如果我正确理解,使用这些随机数,我们可以计算出随机种子.有人可以解释如何做到吗?

For example, we have 126/128 nonces, revealed in cycle 99. /chains/main/blocks/409599/context/raw/json/cycle/98/nonces?depth=1

If I understand correctly, using these nonces we can calculate the random seed. Can anybody explain how to do this?

protocol consensus cryptography

1 个回答

投票数

Tom · Accepted Answer · 2019-05-16

7

2019-05-16

我们将需要执行以下操作:

blake2b:大小32
concat:字节数组的串联

另外,让zero_bytes为32个零字节.

我的答案基于 seed_storage.ml 和 seed_repr.ml ,并进行了一些实验.

初始种子

让我们从头开始.

提前确定初始的preserved_cycles + 2=7个种子,如下所示.第一个种子是空消息的哈希值:

 seed[0] = blake2b([]) = 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8

剩余的6个初始种子分别从上一个计算得出:

 seed[n] = blake2b(concat(seed[n-1], zero_bytes))

这提供了以下初始种子:

 | cycle | seed                                                             |
|-------+------------------------------------------------------------------|
|     0 | 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8 |
|     1 | c8db55740733852aa18aa82e108e4475b1abcf3f1f077ac966e9cecca86612ec |
|     2 | 270da140de63850f631d09a95eab26dc39cc92f8feae73875c7cf9aaa3bf4cac |
|     3 | 97d50852c159ada8e9f107e98f693b059ba28336c723e6cd0f6353eb3c0cb415 |
|     4 | 0c7ea5ee0b25b7105f934c6511756ec20abcf5c6eea4d45721c138c3e751469b |
|     5 | beb4d79b65faa3e902e73d031ad6466299f01aab517d303151a99605a259a11e |
|     6 | 5e695ae038c2bdc54706547fc743eb3564ca5a0b4b5d8e9de2ca4780157ca61e |

下一个周期的种子

从这里,我们使用显示的随机数来计算前一个种子的下一个种子:

 seed[n] = seed[n-1]
# start with a 'zero nonce':
seed[n] = blake2b(concat(seed[n], zero_bytes))
# then use the revealed nonces:
for nonce in nonces_for[n]:
  seed[n] = blake2b(concat(seed[n], nonce))

随机数按递减级别进行.

例如,要计算周期7的随机种子,我们可以获取在周期0的过程中显示的随机数:

 # The best level seems to be ((n-5)*4096)-1?
# Warning, this is not complete, see below.
# 8191 = ((7-5)*4096)-1
# 0 = 7-7
curl -s http://localhost:18732/chains/main/blocks/8191/context/raw/json/cycle/0/nonces?depth=1 \
   | jq -r '.[] | "\(.[0])\t\(.[1])"' | sort -rnk1 | cut -f2

第一个随机数(按降序排列)是" 1ee95fe66b ...",最后一个是" d1012e79ab ...",因此我们计算:

 # seed == "5e695ae038c2bdc54706547fc743eb3564ca5a0b4b5d8e9de2ca4780157ca61e"

# zero nonce
seed = blake2b(concat(seed, "0000000000000000000000000000000000000000000000000000000000000000"))
# seed == "9b7328e5393a466fc47ef16eb74121939b06e6ec4c17295eb25611f1b76d6a33"

# first nonce
seed = blake2b(concat(seed, "1ee95fe66bb3dc2a62195dd41a07a30835e63b91db395aa64150da3decc3be1c"))
# seed == "f9b94526a502a1d8e4042eba2deb682dd752627ea6e4472187ad1c1e465be0f4")

# ... the other nonces ...
# seed == "469a48304fc415870289ac8bd875b04107381a2471a878a2a8da16e43dfc5880"

# last nonce
seed = blake2b(concat(seed, "d1012e79abc75ffc4228f69ace060e1003c8fff0aa9d58a2d78816713b72c278"))
# seed == "1bcd1d832aff2d72a8d16a9f9e5f994e177e29eac789138b019f0c4a30c4e5ec"

到目前为止很好:

 $ curl http://localhost:18732/chains/main/blocks/24575/context/raw/json/cycle/7/random_seed
"1bcd1d832aff2d72a8d16a9f9e5f994e177e29eac789138b019f0c4a30c4e5ec"

如何获得随机数?

但是,如果继续走下去,就会遇到问题.

我不认为可以使用context/raw/json/cycle/<cycle>/nonces来获取 all 所显示的随机数.如果一个随机数在周期黎明时才被发现,我相信该协议将在使用后立即被协议删除,然后再通过原始上下文RPC将其提供.

第一个问题似乎是在块200704级的启示.

当然,如果您要构建一个alt-shell,您自然会获得现成的随机数,并且,如果像我一样,您只是好奇,这没关系.

We will need these operations:

blake2b: size 32
concat: concatenation of byte arrays

Also, let zero_bytes be 32 zero bytes.

My answer is based on seed_storage.ml and seed_repr.ml, with some experimentation.

Initial seeds

Let's start at the beginning.

The initial preserved_cycles+2 = 7 seeds were determined ahead of time, as follows. The first seed is the hash of the empty message:

seed[0] = blake2b([]) = 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8

The remaining 6 initial seeds are each computed from the previous:

seed[n] = blake2b(concat(seed[n-1], zero_bytes))

This gives the following initial seeds:

| cycle | seed                                                             |
|-------+------------------------------------------------------------------|
|     0 | 0e5751c026e543b2e8ab2eb06099daa1d1e5df47778f7787faab45cdf12fe3a8 |
|     1 | c8db55740733852aa18aa82e108e4475b1abcf3f1f077ac966e9cecca86612ec |
|     2 | 270da140de63850f631d09a95eab26dc39cc92f8feae73875c7cf9aaa3bf4cac |
|     3 | 97d50852c159ada8e9f107e98f693b059ba28336c723e6cd0f6353eb3c0cb415 |
|     4 | 0c7ea5ee0b25b7105f934c6511756ec20abcf5c6eea4d45721c138c3e751469b |
|     5 | beb4d79b65faa3e902e73d031ad6466299f01aab517d303151a99605a259a11e |
|     6 | 5e695ae038c2bdc54706547fc743eb3564ca5a0b4b5d8e9de2ca4780157ca61e |

The next cycle's seed

From here, we use the revealed nonces to compute the next seed from the previous seed:

seed[n] = seed[n-1]
# start with a 'zero nonce':
seed[n] = blake2b(concat(seed[n], zero_bytes))
# then use the revealed nonces:
for nonce in nonces_for[n]:
  seed[n] = blake2b(concat(seed[n], nonce))

The nonces are taken in decreasing level order.

For example, to calculate the random seed for cycle 7, we can grab the nonces revealed over the course of cycle 0:

# The best level seems to be ((n-5)*4096)-1?
# Warning, this is not complete, see below.
# 8191 = ((7-5)*4096)-1
# 0 = 7-7
curl -s http://localhost:18732/chains/main/blocks/8191/context/raw/json/cycle/0/nonces?depth=1 \
   | jq -r '.[] | "\(.[0])\t\(.[1])"' | sort -rnk1 | cut -f2

The first nonce (in decreasing level order) is "1ee95fe66b...", and the last is "d1012e79ab...", so we compute:

# seed == "5e695ae038c2bdc54706547fc743eb3564ca5a0b4b5d8e9de2ca4780157ca61e"

# zero nonce
seed = blake2b(concat(seed, "0000000000000000000000000000000000000000000000000000000000000000"))
# seed == "9b7328e5393a466fc47ef16eb74121939b06e6ec4c17295eb25611f1b76d6a33"

# first nonce
seed = blake2b(concat(seed, "1ee95fe66bb3dc2a62195dd41a07a30835e63b91db395aa64150da3decc3be1c"))
# seed == "f9b94526a502a1d8e4042eba2deb682dd752627ea6e4472187ad1c1e465be0f4")

# ... the other nonces ...
# seed == "469a48304fc415870289ac8bd875b04107381a2471a878a2a8da16e43dfc5880"

# last nonce
seed = blake2b(concat(seed, "d1012e79abc75ffc4228f69ace060e1003c8fff0aa9d58a2d78816713b72c278"))
# seed == "1bcd1d832aff2d72a8d16a9f9e5f994e177e29eac789138b019f0c4a30c4e5ec"

So far so good:

$ curl http://localhost:18732/chains/main/blocks/24575/context/raw/json/cycle/7/random_seed
"1bcd1d832aff2d72a8d16a9f9e5f994e177e29eac789138b019f0c4a30c4e5ec"

How to get the nonces?

However, if you keep going, you will run into a problem.

I don't believe it is possible to use context/raw/json/cycle/<cycle>/nonces to get all the revealed nonces. If a nonce is revealed just at cycle dawn, I believe it will be deleted by the protocol immediately upon use, before it is made available via the raw context RPC.

The first problem seems to be the revelation in the block at level 200704.

Of course, if you are building an alt-shell, you will naturally acquire the nonces, and if, like me, you are just curious, this doesn't matter.

原文
Tom

简洁的解释,谢谢！您在这里做了错字`seed [n]=blake2b(concat(seed [n-1],nonce))`-应该是concat(seed [n],nonce)`;)顺便说一句,我在使用C#生成随机种子,也许有人会发现它有用.https://gist.github.com/Groxan/c0f11a896bcf9a43e0fff9ba2e46223b

Neat explanation, thanks! You made a typo here `seed[n] = blake2b(concat(seed[n-1], nonce))` - it should be `concat(seed[n], nonce)` ;) Btw, I created a gist on C# with generation of a random seed, maybe someone would find it useful. https://gist.github.com/Groxan/c0f11a896bcf9a43e0fff9ba2e46223b
- 1
- 2019-05-16
- Groxan
至于在级别200704的区块中的启示-这对我来说是一个惊喜=)我尝试获取种子,但在追加最后一个随机数之前是不正确的.可悲的是,文档中没有描述很多陷阱.

As for the revelation in the block at level 200704 - it was a surprise for me =) I tried to get the seed an it was incorrect until I appended the last nonce. Sadly, there are so many pitfalls that are not described in the docs.
- 1
- 2019-05-16
- Groxan
哎呀,谢谢,这就是我尝试编写命令式伪代码所得到的.;)

Whoops, thanks, that is what I get for trying to write imperative pseudocode. ;)
- 1
- 2019-05-16
- Tom