8000 fix: section 4 files (#972) · filecoin-project/specs@79f7e84 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Commit 79f7e84

Browse files
yiannisbotyiannisbot
authored
fix: section 4 files (#972)
1 parent 22b83d4 commit 79f7e84

39 files changed

+2161
-0
lines changed

‎next/content/algorithms/crypto/_index.md

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
---
2+
title: "Cryptographic Primitives"
3+
suppressMenu: true
4+
entries:
5+
- signatures
6+
- vrf
7+
- randomness
8+
---
9+
10+
- Merkle tree/DAG
11+
- Vector commitment scheme
12+
- zkSNARK
13+
- Reliable broadcast channel (libp2p)
14+
15+
16+
- TODO: Add more detail and include references to relevant papers.

‎next/content/algorithms/crypto/bls.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package crypto
2+
3+
import util "github.com/filecoin-project/specs/util"
4+
5+
func (self *BLS_I) Verify(input util.Bytes, pk PublicKey, sig util.Bytes) bool {
6+
// blsPk := pk.(*BLSPublicKey)
7+
// 1. Verify public key according to string_to_curve section 2.6.2.1. in
8+
// https://tools.ietf.org/html/draft-boneh-bls-signature-00#page-12
9+
// 2. Verify signature according to section 2.3
10+
// https://tools.ietf.org/html/draft-boneh-bls-signature-00#page-8
11+
panic("bls.Verify TODO")
12+
return false
13+
}
14+
15+
func (self *BLS_I) MaxSigValue() util.Bytes {
16+
panic("TODO")
17+
}
18+
19+
func (self *BLS_I) Sign(input util.Bytes, sk *SecretKey) bool {
20+
panic("see 2.3 in https://tools.ietf.org/html/draft-boneh-bls-signature-00#page-8")
21+
return false
22+
}
23+
24+
func (self *BLS_I) Aggregate(sig2 util.Bytes) util.Bytes {
25+
panic("see 2.5 in https://tools.ietf.org/html/draft-boneh-bls-signature-00#page-8")
26+
var ret util.Bytes
27+
return ret
28+
}
29+
30+
func (self *BLS_I) VerifyAggregate(messages []util.Bytes, aggPk PublicKey, aggSig util.Bytes) bool {
31+
panic("see 2.5.2 in https://tools.ietf.org/html/draft-boneh-bls-signature-00#page-9")
32+
return false
33+
}

‎next/content/algorithms/crypto/bls.id

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
// BLS implements the Signature interface using the BLS signature scheme
2+
// with the BLS12-381 group of elliptic curves.
3+
type BLS struct {
4+
// This signature is the one returned from SigKeyPair.Sign(). It can be
5+
// casted to a BLS signature struct to get the additional functionalities.
6+
Signature
7+
8+
// This represents the largest potential value for a BLS signature in Bytes
9+
MaxSigValue() Bytes
10+
11+
// Aggregates this BLS signature and `sig` into one BLS signature that can
12+
// be verified against the aggregation of the two public key that signed
13+
// the aggregated signatures.
14+
Aggregate(sig2 SignatureBytes) SignatureBytes
15+
16+
// VerifyAggregate verifies the aggregate signature with the aggregate
17+
// public key over all the distinct messages given. Note that if all
18+
// messages are the same, it is sufficient and correct to only call
19+
// `Verify` since it is a subset of `VerifyAggregate`.
20+
VerifyAggregate(messages [Message], aggPk BLSPublicKey, aggSig SignatureBytes) bool
21+
}
22+
23+
// BLSPublicKey is a PublicKey with an addition method to aggregate public keys
24+
// together.
25+
type BLSPublicKey struct {
26+
PublicKey
27+
28+
// Aggregate this public key with p2 into one public key. This aggregated
29+
// public key can
30+
// - verify aggregated signatures signed by the two BLSPublicKey
31+
// - be aggregated further down with other (aggregated or not) BLSPublicKey.
32+
Aggregate(p2 BLSPublicKey) BLSPublicKey
33+
}

‎next/content/algorithms/crypto/ecdsa.id

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
// ECDSA implements the Signature interface using the ECDSA algorithm with
2+
// the Secp256k1 elliptic curve.
3+
type ECDSA struct {
4+
// The Signature object is the one returned from SigKeyPair.Sign(). It can
5+
// be casted to ECDSA to get the additional functionality described below.
6+
Signature
7+
8+
// Recover recovers a public key associated with a particular signature.
9+
//
10+
// Out:
11+
// pk - the public key associated with `M` who signed `m`
12+
// err - a standard error message indicating any process issues
13+
// **
14+
// In:
15+
// m - a series of bytes representing the signed message
16+
// sig - a series of bytes representing a signature usually `r`|`s`
17+
//
18+
Recover(m Message, sig SignatureBytes) struct {pk PublicKey, err error}
19+
}

‎next/content/algorithms/crypto/randomness.md

Lines changed: 131 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,131 @@
1+
---
2+
title: "Randomness"
3+
---
4+
5+
# Randomness
6+
---
7+
8+
{{< hint danger >}}
9+
Issues with labels and readfile throughout
10+
{{< /hint >}}
11+
12+
13+
{{< hint danger >}}
14+
Issue with label
15+
{{< /hint >}}
16+
17+
18+
{{</* label randomness */>}}
19+
20+
Randomness is used throughout the protocol in order to generate values and extend the blockchain.
21+
Random values are drawn from the [Ticket Chain](\missing-link) and appropriately formatted for usage.
22+
We describe this formatting below.
23+
24+
## Encoding On-chain data for randomness
25+
26+
Entropy from the ticket-chain can be combined with other values to generate necessary randomness that can be
27+
specific to (eg) a given miner address or epoch. To be used as part of entropy, these values are combined in
28+
objects that can then be CBOR-serialized according to their algebraic datatypes.
29+
30+
## Domain Separation Tags
31+
32+
Further, we define Domain Separation Tags with which we prepend random inputs when creating entropy.
33+
34+
All randomness used in the protocol must be generated in conjunction with a unique DST, as well as
35+
certain [Signatures](\missing-link) and [Verifiable Random Function](\missing-link) usage.
36+
37+
## Drawing tickets for randomness from the chain
38+
39+
Tickets are used as a source of on-chain randomness, generated with each new block created (see [Tickets](\missing-link)).
40+
41+
A ticket is drawn from the chain for randomness as follows, for a given epoch `n`, and ticket sought at epoch `e`:
42+
```text
43+
RandomnessSeedAtEpoch(e):
44+
While ticket is not set:
45+
Set wantedTipsetHeight = e
46+
if wantedTipsetHeight <= genesis:
47+
Set ticket = genesis ticket
48+
else if blocks were mined at wantedTipsetHeight:
49+
ReferenceTipset = TipsetAtHeight(wantedTipsetHeight)
50+
Set ticket = minTicket in ReferenceTipset
51+
If no blocks were mined at wantedTipsetHeight:
52+
wantedTipsetHeight--
53+
(Repeat)
54+
return ticket.Digest()
55+
```
56+
57+
In plain language, this means:
58+
59+
- Choose the smallest ticket in the Tipset if it contains multiple blocks.
60+
- When sampling a ticket from an epoch with no blocks, draw the min ticket from the prior epoch with blocks
61+
62+
This ticket is then combined with a Domain Separation Tag, the round number sought and appropriate entropy to form randomness for various uses in the protocol.
63+
64+
{{< hint danger >}}
65+
Issue with readfile
66+
{{< /hint >}}
67+
68+
See the `RandomnessSeedAtEpoch` method below:
69+
{{</* readfile file="../struct/chain/chain.go" code="true" lang="go" */>}}
70+
71+
## Forming Randomness Seeds
72+
73+
The drawn ticket digest is combined with a few elements to make up randomness for use as part of the protocol.
74+
75+
- a DST (domain separation tag)
76+
- Different uses of randomness are distinguished by this type of personalization which ensures that randomness used for different purposes will not conflict with randomness used elsewhere in the protocol
77+
- the epoch number, ensuring
78+
- liveness for leader election -- in the case of null rounds, the new epoch number will output new randomness for LE
79+
- distinct values for randomness sought before genesis -- where the genesis ticket will be returned
80+
- For instance, if in epoch `curr`, a miner wants randomness from `lookback` epochs back where `curr - lookback <= genesis`, the ticket randomness drawn would be based on `genesisTicket.digest` where the `genesisTicket` is the randomness included in the genesis block. Using the epoch as part of randomness composition ensures that randomness drawn at various epochs prior to genesis has different values.
81+
- other entropy,
82+
- ensuring that randomness is modified as needed by other context-dependent entropy (e.g. a miner address if we want the randomness to be different for each miner).
83+
84+
While all elements are not needed for every use of entropy (e.g. the inclusion of the round number is not necessary prior to genesis or outside of leader election, other entropy is only used sometimes, etc), we draw randomness as follows for the sake of uniformity/simplicity in the overall protocol.
85+
86+
In all cases, a ticket is used as the base of randomness (see [Tickets](\missing-link)). In order to make randomness seed creation uniform, the protocol derives all such seeds in the same way, using blake2b as a hash function to generate a 256-bit output as follows (also see [Tickets](\missing-link)):
87+
88+
In round `n`, for a given randomness lookback `l`, and serialized entropy `s`:
89+
90+
```text
91+
GetRandomness(dst, l, s):
92+
ticketDigest = RandomnessSeedAtEpoch(n-l)
93+
94+
buffer = Bytes{}
95+
buffer.append(IntToBigEndianBytes(dst))
96+
buffer.append(randSeed)
97+
buffer.append(n-l) // the sought epoch
98+
buffer.append(s)
99+
100+
return H(buffer)
101+
```
102+
103+
{{< hint danger >}}
104+
Issue with readfile
105+
{{< /hint >}}
106+
107+
{{</* readfile file="/docs/actors/actors/crypto/randomness.go" code="true" lang="go" */>}}
108+
{{</* readfile file="/docs/systems/filecoin_blockchain/struct/chain/chain.go" code="true" lang="go" */>}}
109+
110+
## Entropy to be used with randomness
111+
112+
As stated above, different uses of randomness may require added entropy. The CBOR-serialization of the inputs to this entropy must be used.
113+
114+
For instance, if using entropy from an object of type foo, its CBOR-serialization would be appended to the randomness in `GetRandomness()`. If using both an object of type foo and one of type bar for entropy, you may define an object of type baz (as below) which includes all needed entropy, and include its CBOR-serialization in `GetRandomness()`.
115+
116+
```text
117+
type baz struct {
118+
firstObject foo
119+
secondObject bar
120+
}
121+
```
122+
123+
Currently, we distinguish the following entropy needs in the Filecoin protocol (this list is not exhaustive):
124+
125+
- TicketProduction: requires MinerIDAddress
126+
- ElectionPoStChallengeSeed: requires current epoch and MinerIDAddress -- epoch is already mixed in from ticket drawing so in practice is the same as just adding MinerIDAddress as entropy
127+
- WindowedPoStChallengeSeed: requires MinerIDAddress
128+
- SealRandomness: requires MinerIDAddress
129+
- InteractiveSealChallengeSeed: requires MinerIDAddress
130+
131+
The above uses of the MinerIDAddress ensures that drawn randomness is distinct for every miner drawing this (regardless of whether they share worker keys or not, eg -- in the case of randomness that is then signed as part of leader election or ticket production).

‎next/content/algorithms/crypto/signatures.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package crypto
2+
3+
// Sign generates a proof that miner `M` generate message `m`
4+
//
5+
// Out:
6+
// sig - a signature
7+
// err - a standard error message indicating any process issues
8+
// In:
9+
// m - a series of bytes representing a message to be signed
10+
//
11+
func Sign(keyPair SigKeyPair, m Message) (Signature, error) {
12+
panic("TODO")
13+
}
14+
15+
// Verify validates the statement: only `M` could have generated `sig`
16+
// given the validator has a message `m`, a signature `sig`, and a
17+
// public key `pk`.
18+
//
19+
// Out:
20+
// valid - a boolean value indicating the signature is valid
21+
// err - a standard error message indicating any process issues
22+
// In:
23+
// pk - the public key belonging to the signer `M`
24+
// m - a series of bytes representing the signed message
25+
//
26+
func Verify(pk PublicKey, sig Signature, m Message) (valid bool, err error) {
27+
panic("TODO")
28+
}

‎next/content/algorithms/crypto/signatures.id

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
type Message Bytes
2+
type SecretKey Bytes
3+
type PublicKey Bytes
4+
type SignatureBytes Bytes
5+
6+
type SigKeyPair struct {
7+
PublicKey
8+
SecretKey
9+
}
10+
11+
type Signature struct {
12+
Type SigType @(internal)
13+
Sig SignatureBytes @(internal)
14+
}
15+
16+
type SigType enum {
17+
ECDSASigType
18+
BLSSigType
19+
}

0 commit comments

Comments
 (0)
0