Require minimal height encodings during deserialization

[teor2345]

Motivation

Zebra accepts non-minimal height encodings when deserializing, but the spec requires minimal encodings.

The serialization should be correct. But the deserialization accepts some encodings that are longer than they need to be. So they are actually invalid.

Consensus Rules

Here's the relevant consensus rule:

A coinbase transaction for a block at block height greater than 0 MUST have a script that, as its first item, encodes the block height height as follows.

For height in the range {1 .. 16}, the encoding is a single byte of value 0x50 + height.

Otherwise, let heightBytes be the signed little-endian representation of height, using the minimum nonzero number of bytes such that the most significant byte is < 0x80. The length of heightBytes MUST be in the range {1 .. 5}. Then the encoding is the length of heightBytes encoded as one byte, followed by heightBytes itself.

This matches the encoding used by Bitcoin in the implementation of [BIP-34] (but the description here is to be considered normative).

https://zips.z.cash/protocol/protocol.pdf#txnconsensus

Related Consensus Rules

Here is a related consensus rule that limits the number of bytes used by a height:

Each block in a block chain has a block height . The block height of the genesis block is 0, and the block height of each subsequent block in the block chain increments by 1. Implementations MUST support block heights up to and including 2^31 − 1.

As of NU5, there is a consensus rule that all coinbase transactions MUST have the nExpiryHeight field set to the block height , and this limits the maximum block height to 2^32 − 1, absent future consensus changes.

https://zips.z.cash/protocol/protocol.pdf#blockchain

Existing Code

zebra/zebra-chain/src/transparent/serialize.rs

Lines 44 to 53 in 24bf952

	// Coinbase inputs include block heights (BIP34). These are not encoded
	// directly, but as a Bitcoin script that pushes the block height to the stack
	// when executed. The script data is otherwise unused. Because we want to
	// *parse* transactions into an internal representation where illegal states are
	// unrepresentable, we need just enough parsing of Bitcoin scripts to parse the
	// coinbase height and split off the rest of the (inert) coinbase data.
	fn parse_coinbase_height(
	mut data: Vec<u8>,
	) -> Result<(block::Height, CoinbaseData), SerializationError> {

Tests

We don't have any proptests for height bytes round-trips (bytes to Height to bytes).

There are two different encodings we need to test:

• single byte opcodes
• 1 length byte followed by 1-5 bytes of height data

We already have height deserialization tests for every mainnet and testnet block test vector.

Context

Comment by @daira in #2225 (comment)

Support the large block heights required by the spec #1113 - out of scope for NU5

[teor2345]

Oops, this was meant to go in zcash/zips.

[teor2345]

This is a consensus rule, so I've marked it as a medium priority

[daira]

The length of heightBytes MUST be in the range {1 .. 4}.

It's { 1 .. 5 } in the current spec (which allows block heights ≥ 2³¹).

[teor2345]

The length of heightBytes MUST be in the range {1 .. 4}.

It's { 1 .. 5 } in the current spec (which allows block heights ≥ 231).

Thanks, I've updated the ticket.

[teor2345]

parse_coinbase_height allows multiple encodings of the same block height. But only the shortest encoding is allowed by the spec.

So it currently allows:

• 0x51 - the only valid height 1 encoding in the consensus rules
• 0x0101 - parsed as height 1, should be an error
• 0x020100 - parsed as height 1, should be an error
• 0x03010000 - parsed as height 1, should be an error
• 0x0401000000 - parsed as height 1, should be an error

[teor2345]

I just realised the height is little-endian, I've fixed the examples above.

Here is an example that don't use the special one-byte script opcodes:

parse_coinbase_height currently allows:

• 0x0111 - the only valid height 17 encoding in the consensus rules
• 0x021100 - parsed as height 17, should be an error
• 0x03110000 - parsed as height 17, should be an error
• 0x0411000000 - parsed as height 17, should be an error