go-ethereumのClique(PoA)について

go-ethereumでコンセンサスアルゴリズムにProof of Authorityを使ったときの処理を追っていきます。

## 仕様

* ノード起動時に承認者をあらかじめ設定しておかなければならない
* 承認者は連続でブロックの承認ができない
* 新たな承認者の追加や既存の承認者の削除は投票で行う
* 投票はブロックヘッダを使って行う
* 順番にブロックを作成するときに承認者の追加をvoteする
* 半数以上のvoteを得ると新しい承認者になれる( or 承認者から削除される)

```go
func (s *Ethereum) StartMining(local bool) error {
	eb, err := s.Etherbase()
	...
	if clique, ok := s.engine.(*clique.Clique); ok {
		wallet, err := s.accountManager.Find(accounts.Account{Address: eb})
		if wallet == nil || err != nil {
			log.Error("Etherbase account unavailable locally", "err", err)
			return fmt.Errorf("signer missing: %v", err)
		}
		clique.Authorize(eb, wallet.SignHash)
	}
	...
	go s.miner.Start(eb)
	return nil
}
// Etherbase (walletの最初のAccount)
func (c *Clique) Authorize(signer common.Address, signFn SignerFn) {
	c.lock.Lock()
	defer c.lock.Unlock()

	c.signer = signer
	c.signFn = signFn
}
```

```go
// Prepare コンセンサスエンジンの実装, 最新のトランザクションのためにヘッダーの全てのコンセンサスフィールドの準備をする
preparing all the consensus fields of the header for running the transactions on top.
func (c *Clique) Prepare(chain consensus.ChainReader, header *types.Header) error {
	// もし、ブロックがチェックポイントではなければ、ランダムに投票する (今のところベター)
	header.Coinbase = common.Address{}
	header.Nonce = types.BlockNonce{}

	number := header.Number.Uint64()
	// 投票のスナップショットを集めて、どの投票が正しいか確認する	
	snap, err := c.snapshot(chain, number-1, header.ParentHash, nil)
	if err != nil {
		return err
	}
	// チェックポイントでなければ処理する
	if number%c.config.Epoch != 0 {
		c.lock.RLock()
		// 正しいすべての提案を集める
		addresses := make([]common.Address, 0, len(c.proposals))
		for address, authorize := range c.proposals {
			if snap.validVote(address, authorize) {
				addresses = append(addresses, address)
			}
		}
		// ペンディングになっている提案があれば、それらに投票する
		if len(addresses) > 0 {
			header.Coinbase = addresses[rand.Intn(len(addresses))]
			if c.proposals[header.Coinbase] {
				copy(header.Nonce[:], nonceAuthVote)
			} else {
				copy(header.Nonce[:], nonceDropVote)
			}
		}
		c.lock.RUnlock()
	}
	header.Difficulty = CalcDifficulty(snap, c.signer)

	// Extraに全てのコンポーネントがあるようにする
	if len(header.Extra) < extraVanity {
		header.Extra = append(header.Extra, bytes.Repeat([]byte{0x00}, extraVanity-len(header.Extra))...)
	}
	header.Extra = header.Extra[:extraVanity]

	// チェックポイントならば、署名者をExtraに追加する
	if number%c.config.Epoch == 0 {
		for _, signer := range snap.signers() {
			header.Extra = append(header.Extra, signer[:]...)
		}
	}
	header.Extra = append(header.Extra, make([]byte, extraSeal)...)
	...
	return nil
}
```

```go
// Sealはconsensus.Engineを実装し、ローカルの署名資格情報を使用してシールされたブロックを作成しようとする。
func (c *Clique) Seal(chain consensus.ChainReader, block *types.Block, stop <-chan struct{}) (*types.Block, error) {
	header := block.Header()

	// ジェネシスブロックのシールはサポートしていない
	number := header.Number.Uint64()
	if number == 0 {
		return nil, errUnknownBlock
	}
	// ピリオードが0のチェインは空のブロックをシールすることを拒否する (報酬は無いがシールすることをスルーするため)
	if c.config.Period == 0 && len(block.Transactions()) == 0 {
		return nil, errWaitTransactions
	}
	// シール手続き中は署名者フィールドを保持してはいけない
	c.lock.RLock()
	signer, signFn := c.signer, c.signFn
	c.lock.RUnlock()

	// もしブロックブロックが未承認だったら、救済する
	snap, err := c.snapshot(chain, number-1, header.ParentHash, nil)
	if err != nil {
		return nil, err
	}
	if _, authorized := snap.Signers[signer]; !authorized {
		return nil, errUnauthorized
	}
	// 最近の署名者がいる場合は、次のブロックを待つ
	for seen, recent := range snap.Recents {
		// signerは自分のノードのEtherBase
		if recent == signer {
			// 署名者が直近も署名していて、現在のブロックもそうなりそうな時は待機する
			// numberはブロック高
			// seenは最近署名したブロック高
			if limit := uint64(len(snap.Signers)/2 + 1); number < limit || seen > number - limit {
				log.Info("Signed recently, must wait for others")
				<-stop
				return nil, nil
			}
		}
	}
	delay := time.Unix(header.Time.Int64(), 0).Sub(time.Now())
	if header.Difficulty.Cmp(diffNoTurn) == 0 {
		wiggle := time.Duration(len(snap.Signers)/2+1) * wiggleTime
		delay += time.Duration(rand.Int63n(int64(wiggle)))
	}
	select {
	case <-stop:
		return nil, nil
	case <-time.After(delay):
	}
	sighash, err := signFn(accounts.Account{Address: signer}, sigHash(header).Bytes())
	if err != nil {
		return nil, err
	}
	copy(header.Extra[len(header.Extra)-extraSeal:], sighash)

	return block.WithSeal(header), nil
}
```

```go
// snapshotは、指定された時点の承認されたスナップショットを取得する
func (c *Clique) snapshot(chain consensus.ChainReader, number uint64, hash common.Hash, parents []*types.Header) (*Snapshot, error) {
	// チェックポイントのため、メモリかディスクから探す
	var (
		headers []*types.Header
		snap    *Snapshot
	)
	for snap == nil {
		// メモリから見つかればそれを使う
		if s, ok := c.recents.Get(hash); ok {
			snap = s.(*Snapshot)
			break
		}
		// ブロック高がチェックポイントインターバルの場合、ディスクから取り出してそれを使う
		if number % checkpointInterval == 0 {
			if s, err := loadSnapshot(c.config, c.signatures, c.db, hash); err == nil {
				log.Info("Loaded voting snapshot from disk", "number", number, "hash", hash)
				snap = s
				break
			}
		}
		// 0ブロックの場合、スナップショットを作る
		if number == 0 {
			genesis := chain.GetHeaderByNumber(0)
			if err := c.VerifyHeader(chain, genesis, false); err != nil {
				return nil, err
			}
			signers := make([]common.Address, (len(genesis.Extra) - extraVanity-extraSeal) / common.AddressLength)
			for i := 0; i < len(signers); i++ {
				copy(signers[i][:], genesis.Extra[extraVanity + i * common.AddressLength:])
			}
			snap = newSnapshot(c.config, c.signatures, 0, genesis.Hash(), signers)
			if err := snap.store(c.db); err != nil {
				return nil, err
			}
			log.Trace("Stored genesis voting snapshot to disk")
			break
		}
		// このヘッダのスナップショットが無かったら過去に遡って集めてくる
		var header *types.Header
		if len(parents) > 0 {
			// もし親があれば持ってくる
			header = parents[len(parents) - 1]
			if header.Hash() != hash || header.Number.Uint64() != number {
				return nil, consensus.ErrUnknownAncestor
			}
			parents = parents[:len(parents)-1]
		} else {
			// 親が無ければデータベースから持ってくる
			header = chain.GetHeader(hash, number)
			if header == nil {
				return nil, consensus.ErrUnknownAncestor
			}
		}
		headers = append(headers, header)
		number, hash = number-1, header.ParentHash
	}
	// headersの順番を入れ替える
	for i := 0; i < len(headers) / 2; i++ {
		headers[i], headers[len(headers) - 1 - i] = headers[len(headers)-1-i], headers[i]
	}
	snap, err := snap.apply(headers)
	if err != nil {
		return nil, err
	}
	c.recents.Add(snap.Hash, snap)

	// チェックポイントインターバルの場合、ディスクに保存する
	if snap.Number % checkpointInterval == 0 && len(headers) > 0 {
		if err = snap.store(c.db); err != nil {
			return nil, err
		}
		log.Trace("Stored voting snapshot to disk", "number", snap.Number, "hash", snap.Hash)
	}
	return snap, err
}
```

```go
// Voteは、承認された署名者が承認リストを変更するために行った単一の投票を表す
type Vote struct {
	Signer    common.Address `json:"signer"`    // この投票をおこなった承認された署名者のアドレス
	Block     uint64         `json:"block"`     // 投票されたブロック高 (古い投票は消える)
	Address   common.Address `json:"address"`   // 承認を変更しようと投票されたアカウントのアドレス(承認に追加 or 承認から削除)
	Authorize bool           `json:"authorize"` // 投票したアカウントを承認するか削除するか
}

// Tallyは、投票の現在のスコアを維持するための単純な投票集計で、提案に反する投票は、投票しないことに等しいので、カウントされない
type Tally struct {
	Authorize bool `json:"authorize"` // 署名者に追加するか除名するかの投票
	Votes     int  `json:"votes"`     // 提案が通るまでの投票数
}

// Snapshotは、特定の時点における権限の投票の状態
type Snapshot struct {
	config   *params.CliqueConfig // 設定
	sigcache *lru.ARCCache        // ブロックの承認スピードを上げるためにecrecoverをキャッシュする

	Number  uint64                      `json:"number"`  // スナップショットが作られたブロック高
	Hash    common.Hash                 `json:"hash"`    // スナップショットが作られたブロック高
	Signers map[common.Address]struct{} `json:"signers"` // このときの承認された署名者の集合
	Recents map[uint64]common.Address   `json:"recents"` // spamを防ぐために最近署名した人の集合を保持する
	Votes   []*Vote                     `json:"votes"`   // 時間順の投票のリスト
	Tally   map[common.Address]Tally    `json:"tally"`   // 再計算を避けるための現在の投票集計
}

// newSnapshotは、指定された起動パラメータで新しいスナップショットを作成する。 このメソッドは最近の署名者のセットを初期化しないので、ジェネシスブロックの時だけ使う
func newSnapshot(config *params.CliqueConfig, sigcache *lru.ARCCache, number uint64, hash common.Hash, signers []common.Address) *Snapshot {
	snap := &Snapshot{
		config:   config,
		sigcache: sigcache,
		Number:   number,
		Hash:     hash,
		Signers:  make(map[common.Address]struct{}),
		Recents:  make(map[uint64]common.Address),
		Tally:    make(map[common.Address]Tally),
	}
	for _, signer := range signers {
		snap.Signers[signer] = struct{}{}
	}
	return snap
}
```

```go
// applyは、与えられたヘッダーを元のスナップショットに適用することによって、新しい承認されたスナップショットを作成する
func (s *Snapshot) apply(headers []*types.Header) (*Snapshot, error) {
	if len(headers) == 0 {
		return s, nil
	}
	// headerの並び順とかのチェック
	for i := 0; i < len(headers)-1; i++ {
		if headers[i+1].Number.Uint64() != headers[i].Number.Uint64()+1 {
			return nil, errInvalidVotingChain
		}
	}
	if headers[0].Number.Uint64() != s.Number+1 {
		return nil, errInvalidVotingChain
	}

	snap := s.copy()

	for _, header := range headers {
		// チェックポイントのブロックの場合、投票を削除する
		number := header.Number.Uint64()
		if number % s.config.Epoch == 0 {
			snap.Votes = nil
			snap.Tally = make(map[common.Address]Tally)
		}
		// 再度承認出来るようにするため直近のリストから古い署名者を削除する
		if limit := uint64(len(snap.Signers)/2 + 1); number >= limit {
			delete(snap.Recents, number-limit)
		}
		// 認証キーを復元して署名者を確認する
		signer, err := ecrecover(header, s.sigcache)
		if err != nil {
			return nil, err
		}
		if _, ok := snap.Signers[signer]; !ok {
			return nil, errUnauthorized
		}
		for _, recent := range snap.Recents {
			if recent == signer {
				return nil, errUnauthorized
			}
		}
		snap.Recents[number] = signer

		// 承認されたヘッダーをつかって、以前の署名者からの投票を破棄する
		for i, vote := range snap.Votes {
			// vote.Signer この投票をおこなった承認された署名者のアドレス
			// signer headerの署名者
			// vote.Address 承認を変更しようと投票されたアカウントのアドレス(承認に追加 or 承認から削除)
			// header.Coinbase 提案からランダムに取得したアドレス
			if vote.Signer == signer && vote.Address == header.Coinbase {
				// キャッシュされた集計から投票を破棄する
				snap.uncast(vote.Address, vote.Authorize)
				// 時系列のリストから投票を取り除く
				snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
				break // 投票は1回のみ可能
			}
		}
		// 署名者から新しい投票を集計する
		var authorize bool
		switch {
		case bytes.Equal(header.Nonce[:], nonceAuthVote):
			authorize = true
		case bytes.Equal(header.Nonce[:], nonceDropVote):
			authorize = false
		default:
			return nil, errInvalidVote
		}
		if snap.cast(header.Coinbase, authorize) {
			snap.Votes = append(snap.Votes, &Vote{
				Signer:    signer,
				Block:     number,
				Address:   header.Coinbase,
				Authorize: authorize,
			})
		}
		// 投票が通った場合、署名者のリストを更新する
		if tally := snap.Tally[header.Coinbase]; tally.Votes > len(snap.Signers)/2 {
			if tally.Authorize {
				snap.Signers[header.Coinbase] = struct{}{}
			} else {
				delete(snap.Signers, header.Coinbase)

				// 署名者リストを縮小し、残りの最近のキャッシュを削除する
				if limit := uint64(len(snap.Signers) / 2 + 1); number >= limit {
					delete(snap.Recents, number - limit)
				}
				// 認証されていない署名者が以前に行った投票を破棄する
				for i := 0; i < len(snap.Votes); i++ {
					if snap.Votes[i].Signer == header.Coinbase {
						// キャッシュされた集計から投票を破棄する
						snap.uncast(snap.Votes[i].Address, snap.Votes[i].Authorize)

						// 時系列のリストから投票を取り除く
						snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
						i--
					}
				}
			}
			// 変更されたばかりのアカウントの前回の投票を破棄する
			for i := 0; i < len(snap.Votes); i++ {
				if snap.Votes[i].Address == header.Coinbase {
					snap.Votes = append(snap.Votes[:i], snap.Votes[i+1:]...)
					i--
				}
			}
			delete(snap.Tally, header.Coinbase)
		}
	}
	snap.Number += uint64(len(headers))
	snap.Hash = headers[len(headers)-1].Hash()

	return snap, nil
}
```

```go
// validVoteはスナップショットから得られた特定の投票が正しいか返す (例えば、既に承認されている署名者は追加しようとは出来ない)
func (s *Snapshot) validVote(address common.Address, authorize bool) bool {
	_, signer := s.Signers[address]
	return (signer && !authorize) || (!signer && authorize)
}

// castはtally(投票計算?)に新しい投票を追加する
func (s *Snapshot) cast(address common.Address, authorize bool) bool {
	// 投票に意味があるか確認する
	if !s.validVote(address, authorize) {
		return false
	}
	// 投票を既存か新規のtallyに行う
	if old, ok := s.Tally[address]; ok {
		old.Votes++
		s.Tally[address] = old
	} else {
		s.Tally[address] = Tally{Authorize: authorize, Votes: 1}
	}
	return true
}

// uncastは前にtallyに投票したものを取り除く
func (s *Snapshot) uncast(address common.Address, authorize bool) bool {
	// tallyに無い場合は、宙ぶらりんな投票なのでただ無視します
	tally, ok := s.Tally[address]
	if !ok {
		return false
	}
	// 集計するべき投票だけ元に戻す
	if tally.Authorize != authorize {
		return false
	}
	// そうでなければ、元に戻す
	if tally.Votes > 1 {
		tally.Votes--
		s.Tally[address] = tally
	} else {
		delete(s.Tally, address)
	}
	return true
}
```

```go
// signersは承認された署名者のリストを昇順で取り出す
func (s *Snapshot) signers() []common.Address {
	signers := make([]common.Address, 0, len(s.Signers))
	for signer := range s.Signers {
		signers = append(signers, signer)
	}
	for i := 0; i < len(signers); i++ {
		for j := i + 1; j < len(signers); j++ {
			if bytes.Compare(signers[i][:], signers[j][:]) > 0 {
				signers[i], signers[j] = signers[j], signers[i]
			}
		}
	}
	return signers
}

// inturnは署名者がそのブロック高の署名者かどうかを返す
func (s *Snapshot) inturn(number uint64, signer common.Address) bool {
	signers, offset := s.signers(), 0
	for offset < len(signers) && signers[offset] != signer {
		offset++
	}
	return (number % uint64(len(signers))) == uint64(offset)
}
```