Signing root problems

[protolambda]

Quick definition

• hash_tree_root merkleizes all fields
• signing_root merkleizes all fields except the last.

Example:

class BeaconBlock(Container):
    slot: Slot
    parent_root: Hash
    state_root: Hash
    body: BeaconBlockBody
    signature: BLSSignature

• hash_tree_root: H(H(slot, parent_root), H(state_root, body))
• signing_root: H(H(H(slot, parent_root), H(state_root, body)), H(H(signature, Z[0]), Z[1]))

Why?

• Consensus only cares about signing_root on-chain in case of data types with a signature, since the signature is already verified (as part of block processing)
• signing_root provides the hash to sign and create signature with.

Why not?

• Summaries/Expansions in SSZ: The state embeds a block_root, but expanding it into a block header or full block is not possible without knowing that it's a signing root.
  • Use separate type definition for the data, omitting the signature field. E.g. some_msg_root: Root[FieldTypeWithoutSig]
  • Mark the root as a signing root, and expand into the definition ignoring the signature field. E.g. some_msg_root: SigRoot[FieldTypeWithSig], some_signed_msg_root: HashRoot[FieldTypeWithSig].
• Tree representation:
  • To represent a BeaconBlock as a tree you have hash_tree_root and singing_root trees.
    • State representation as a tree is useful for:
      • Caching: lazily hash child nodes a and b, cache H(a,b) at the tree node.
      • Fork a state into two trees with common subtrees: effectively only storing the difference to pre-state with each addition. Alike to a merkle datastore.
      • Quickly respond to proof requests by having the tree ready.
  • To navigate the tree, the expansion problem repeats: again a need to separate the two different merkle tree types.
• Inconsistency: Hash-tree-root is universal: everything has a hash-tree-root. But signing-root is not, only containers can have it.
• Indexing: A signing-root db index is necessary for generally on-chain activity, and a hash-tree-root db index for off-chain (see if a block with specific signature is known)
  • Cannot convert the signing-root to hash-tree-root (except technically for BeaconBlock, but only as a by-product of current field count).

Alternatives?

1. No signing_root:
   • Define BeaconBlock and SignedBeaconBlock.

     class BeaconBlock(Container):
         slot: Slot
         parent_root: Hash
         state_root: Hash
         body: BeaconBlockBody
     
     class SignedBeaconBlock(Container):
         data: BeaconBlock
         signature: BLSSignature

     • Convenient: hash_tree_root(SignedBeaconBlock) == H(hash_tree_root(BeaconBlock), signature)
       • No need to provide the full branch to the signature to proof a hash-tree-root or convert a signing root into a hash-tree-root. Just provide the signature.
     • No two different type definitions, always one way to represent the type as a tree.
       • No SigRoot/HashRoot confusion or duplicate choices of representation.
     • No inconsistency with other types that are signed in different ways.
   • Optional: less repetitive definitions, add a Signed[MsgType] helper type to wrap any container with a signature
   • No confusion between two root types in block explorers/etc, the types have names now.
2. Type the output, work around for only some of the issues:
   • Backwards compatible, no functional change. signing_root stays.
   • Define HashRoot and SigRoot, both derived from Bytes32
   • Wherever a root needs to be expanded into a type, it can be done based on its HashRoot / SigRoot
   • Does not solve the represent-as-tree problem: BeaconBlock still has two different tree representations.
   • Does not solve the inconsistency problem: there will still be cases where a regular SigRoot does not fit due to different message / signature requirements.

Edge cases

• DepositData in the spec: hash-tree-roots with signatures included are part of the deposits list root. But processing the signature is done with signing root.
  • process_deposit: We do not like to change the spec here: but removal of signing root doesn't require a change to the deposit contract. We just need to define a DepositMsg with the fields that were signed over, functionally producing the same old signing_root behavior.
• Networking: signatures may not be changed and the appearance of a block has to be checked by.
  • Things improve here with option 1: getting a root that includes the signature is as easy as hashing the signing root with the signature.

Related

Expansions/summaries are difficult with two root variants and effectively different trees:

• SSZ summary/expansion definition should reference signing_root #1436
  • The temporary "solution" is to think of it as an implementation problem.
    • "Two options: define explicit types with/without signature yourself, or type the roots yourself"
• Light client desire for Root[UnderlyingType] to easily expand to UnderlyingType (and its further expansions). With two root types this gets difficult.
• The original introduction of "signed_root", with similar but slightly different definition, and mostly focused on unification of type definitions / line count reduction: Signature hashing proposal #625

Proposal

Since SSZ itself is not quite frozen, but the core functionality for Phase 0 was, so this proposal will go slower and through more review.

• Implement alternative 1 in a PR to the specs repo
• Personally expect that it will mostly be a welcome change for clients:
  • cost: defining a few simple containers, updating signing_root calls to hash_tree_root these signature-less containers instead.
  • benefit: less merkleization variation to worry about, enable caching/trees/more.
• Others involved with SSZ share their feedback / concerns / support.
• Decide next Eth2 implementers call (early Dec.) if it can go in.

[arnetheduck]

Yes! +1 for alternative 1

• It would potentially be nice to maintain the tuple [data, signature] throughout as a pattern, or indeed use a generic notation for it - either is fine.
• This also solves the problem of BeaconBlockHeader in BeaconState containing an always-zeroed signature
• It solves an ambiguity whether blocks should be requested by signing_root or hash_tree_root in the network protocol (there were a few back-and-forths and signing-roots were chosen)

[tkstanczak]

+1 for alternative 1

[mkalinin]

+1 for alternative 1

[vbuterin]

Support alternative 1.

Optional: less repetitive definitions, add a Signed[MsgType] helper type to wrap any container with a signature

This would definitely be useful!