Skip to content

Instantly share code, notes, and snippets.

@hayeah
Created January 25, 2018 01:55
Show Gist options
  • Save hayeah/c380d3beb7d2b915723f4e9f07553437 to your computer and use it in GitHub Desktop.
Save hayeah/c380d3beb7d2b915723f4e9f07553437 to your computer and use it in GitHub Desktop.
yellopaper rewritten with source code references

4.3 The Block

The block in Ethereum is the collection of relevant pieces of information (known as the block header), together with information corresponding to the comprised transactions, and a set of other block headers that are known to have a parent equal to the present block’s parent’s parent (such blocks are known as uncles).

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/block.go#L139

type Block struct {
	header       *Header
	uncles       []*Header
	transactions Transactions

	// other fields omitted...
}

The block header contains several pieces of information:

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/block.go#L70:1

// Header represents a block header in the Ethereum blockchain.
type Header struct {
  // The Keccak 256-bit hash of the parent block’s header, in its entirety
	ParentHash  common.Hash    `json:"parentHash"       gencodec:"required"`
  // The Keccak 256-bit hash of the uncles list portion of this block
	UncleHash   common.Hash    `json:"sha3Uncles"       gencodec:"required"`
  // The 160-bit address to which all fees collected from the successful mining of this block be transferred
	Coinbase    common.Address `json:"miner"            gencodec:"required"`
  // The Keccak 256-bit hash of the root node of the state trie, after all transactions are executed and finalisations applied
	Root        common.Hash    `json:"stateRoot"        gencodec:"required"`
  // The Keccak 256-bit hash of the root node of the trie structure populated with each transaction in the transactions list portion
of the block
	TxHash      common.Hash    `json:"transactionsRoot" gencodec:"required"`
  // The Keccak 256-bit hash of the root node of the trie structure populated with the receipts of each transaction in the transactions list portion of the block
	ReceiptHash common.Hash    `json:"receiptsRoot"     gencodec:"required"`
  // The Bloom filter composed from indexable information (logger address and log topics) contained in each log entry from the receipt of each transaction in the transactions list
	Bloom       Bloom          `json:"logsBloom"        gencodec:"required"`
  // A scalar value corresponding to the difficulty level of this block. This can be calculated from the previous block’s difficulty level and the timestamp
	Difficulty  *big.Int       `json:"difficulty"       gencodec:"required"`
  // A scalar value equal to the number of ancestor blocks. The genesis block has a number of zero
	Number      *big.Int       `json:"number"           gencodec:"required"`
  // A scalar value equal to the current limit of gas expenditure per block
	GasLimit    *big.Int       `json:"gasLimit"         gencodec:"required"`
  // A scalar value equal to the total gas used in transactions in this block
	GasUsed     *big.Int       `json:"gasUsed"          gencodec:"required"`
  // A scalar value equal to the reasonable output of Unix’s time() at this block’s inception
	Time        *big.Int       `json:"timestamp"        gencodec:"required"`
  // An arbitrary byte array containing data relevant to this block. This must be 32 bytes or fewer
	Extra       []byte         `json:"extraData"        gencodec:"required"`
  // A 256-bit hash which proves combined with the nonce that a sufficient amount of computation has been carried out on this block
	MixDigest   common.Hash    `json:"mixHash"          gencodec:"required"`
  // A 64-bit hash which proves combined with the mix-hash that a sufficient amount of computation has been carried out on this block
	Nonce       BlockNonce     `json:"nonce"            gencodec:"required"`
}

4.3.1. Transaction Receipt

In order to encode information about a transaction concerning which it may be useful to form a zero-knowledge proof, or index and search, we encode a receipt of each transaction containing certain information from concerning its execution. Each receipt is placed in an index-keyed trie and the root recorded in the header ReceiptHash.

The transaction receipt is a struct of four items comprising the post-transaction state (PostState), the cumulative gas used in the block containing the transaction receipt as of immediately after the transaction has happened (CumulativeGasUsed), the set of logs created through execution of the transaction, (Logs) and the Bloom filter composed from information in those logs (Bloom):

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/receipt.go#L46:1

type Receipt struct {
	// Consensus fields
	PostState         []byte   `json:"root"`
	Status            uint     `json:"status"`
	CumulativeGasUsed *big.Int `json:"cumulativeGasUsed" gencodec:"required"`
	Bloom             Bloom    `json:"logsBloom"         gencodec:"required"`
	Logs              []*Log   `json:"logs"              gencodec:"required"`

	// Implementation fields (don't reorder!)
	TxHash          common.Hash    `json:"transactionHash" gencodec:"required"`
	ContractAddress common.Address `json:"contractAddress"`
	GasUsed         *big.Int       `json:"gasUsed" gencodec:"required"`
}

	// Bloom represents a 2048 bit bloom filter.
type Bloom [BloomByteLength]byte

The function LR trivially prepares a transaction receipt for being transformed into an RLP-serialised byte array:

(19) LR(R) ≡ (TRIE(LS(Rσ)), Ru, Rb, Rl)

thus the post-transaction state, Rσ is encoded into a trie structure, the root of which forms the first item.

what's (19) about RLP-serialization??

A log entry (Log) is a struct of a logger’s address Address, a series of 32-bytes log topics (Topics), and some number of bytes of data (Data):

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/log.go#L32

// Log represents a contract log event. These events are generated by the LOG opcode and
// stored/indexed by the node.
type Log struct {
	// address of the contract that generated the event
	Address common.Address `json:"address" gencodec:"required"`
	// list of topics provided by the contract.
	Topics []common.Hash `json:"topics" gencodec:"required"`
	// supplied by the contract, usually ABI-encoded
	Data []byte `json:"data" gencodec:"required"`

	// other internal fields omitted...
}

We define the Bloom filter function, LogsBloom, to reduce a log entry into a single 256-byte hash:

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/bloom9.go#L103:6

func LogsBloom(logs []*Log) *big.Int {
	bin := new(big.Int)
	for _, log := range logs {
		bin.Or(bin, bloom9(log.Address.Bytes()))
		for _, b := range log.Topics {
			bin.Or(bin, bloom9(b[:]))
		}
	}

	return bin
}

where bloom9 is a specialised Bloom filter that sets three bits out of 2048, given an arbitrary byte sequence. It does this through taking the low-order 11 bits of each of the first three pairs of bytes in a Keccak-256 hash of the byte sequence. In Golang:

https://sourcegraph.com/github.com/ethereum/go-ethereum@479aa61f11724560c63a7b56084259552892819d/-/blob/core/types/bloom9.go#L115

func bloom9(b []byte) *big.Int {
	b = crypto.Keccak256(b[:])

	r := new(big.Int)

	for i := 0; i < 6; i += 2 {
		t := big.NewInt(1)
		b := (uint(b[i+1]) + (uint(b[i]) << 8)) & 2047
		r.Or(r, t.Lsh(t, b))
	}

	return r
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment