hash: add Clone

[FiloSottile]

There isn't a general way to clone the state of a hash.Hash, but #20573 introduced the concept of hash.Hash implementations also implementing encoding.BinaryMarshaler and encoding.BinaryUnmarshaler, and the hash.Hash docs commit our implementations to doing that.

Hash implementations in the standard library (e.g. hash/crc32 and crypto/sha256) implement the encoding.BinaryMarshaler and encoding.BinaryUnmarshaler interfaces.

That allows cloning the hash state without recomputing it, as done in HMAC.

go/src/crypto/hmac/hmac.go

Lines 96 to 103 in db40d1a

	marshalableInner, innerOK := h.inner.(marshalable)
	if !innerOK {
	return
	}
	marshalableOuter, outerOK := h.outer.(marshalable)
	if !outerOK {
	return
	}

However, it's obscure and pretty clunky to use.

I propose we add a hash.Clone helper function.

package hash

// Clone returns a separate Hash instance with the same state as h.
//
// h must implement encoding.BinaryMarshaler and encoding.BinaryUnmarshaler,
// or be provided by the Go standard library. Otherwise, Clone returns an error.
func Clone(h Hash) (Hash, error)

In practice, we should only fallback to BinaryMarshaler + BinaryUnmarshaler for the general case, while for standard library implementations we can do an undocumented interface upgrade to interface { Clone() Hash }. In that sense, hash.Clone is a way to hide the interface upgrade as a more discoverable and easier to use function.

(Yet another example of why we should be returning concrete types everywhere rather than interfaces.)

CloneXOF

If #69518 is accepted, I propose we also add hash.CloneXOF.

package hash

// CloneXOF returns a separate XOF instance with the same state as h.
//
// h must implement encoding.BinaryMarshaler and encoding.BinaryUnmarshaler,
// or be provided by the Go standard library or by the golang.org/x/crypto module
// (starting at version v0.x.y). Otherwise, Clone returns an error.
func CloneXOF(h XOF) (XOF, error)

None of our XOFs actually implement BinaryMarshaler + BinaryUnmarshaler, but they have their own interface methods Clone() ShakeHash and Clone() XOF that each return an interface. I can't really think of a way to use them from CloneXOF, so instead we can add hidden methods CloneXOF() hash.XOF and interface upgrade to them.

As we look at moving packages from x/crypto to the standard library (#65269) we should switch x/crypto/sha3 and x/crypto/blake2[bs] from returning interfaces to returning concrete types, at least for XOFs. Then they can have a Clone() method that returns a concrete type, and a CloneXOF() method that returns a hash.XOF interface and enables hash.CloneXOF.

(If anyone has better ideas for how to make this less redundant, I would welcome them. I considered and rejected using reflect to call the existing Clone methods because hash is a pretty core package. This sort of interface-method-that-needs-to-return-a-value-implementing-said-interface scenarios are always annoying.)

/cc @golang/security @cpu @qmuntal (who filed something similar in #69293, as I found while searching refs for this)

[gabyhelp]

Related Issues and Documentation

• proposal: hash: add HashCloner #69293 (closed)
• proposal: hash: add XOF interface #69518
• x/crypto/{blake2b,blake2s}: implement encoding.BinaryMarshaler and encoding.BinaryUnmarshaler #24548 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[magical]

How do you intend to implement the fallback path in Clone? MarshalBinary + UnmarshalBinary only gives you the ability to save and restore a Hash's state, not construct a new instance of it. You might be able to do it with reflect but it sounds like we're trying to avoid reflect.

[magical]

I'll also point out that, when using Clone to optimize repeated hashes with the same prefix, you really want to pair it with a Set method which copies the hash state from one existing instance to another.

e.g.

h := newHash()
h.Write(prefix)
h0 := h.Clone() // allocates
for _, message := range messages {
   h.Set(h0) // doesn't allocate
   h.Write(message)
   fmt.Println(h.Sum(nil))
}

Otherwise, without Set, you end up creating unavoidable garbage on every message.

h0 := newHash()
h0.Write(prefix)
for _, message := range messages {
   h := h0.Clone() // allocates
   h.Write(message)
   fmt.Println(h.Sum(nil))
}

My initial stab at the hmac optimization (before hashes implemented BinaryMarshaler and BinaryUnmarshaler) combined Clone and Set into a single method:

type HashCloner interface {
    hash.Hash

    // Clone returns a copy of its reciever, reusing the provided Hash if possible
    Clone(hash.Hash) hash.Hash
}

It looks a little odd but ends up being fairly ergonomic. One advantage this definition has over separate Clone and Set methods is that there is a nice answer for what to do when the argument and receiver types do not match: just allocate a new value. Whereas Set would have to panic.

// Example implementation for sha1.digest
func (d0 *digest) Clone(h hash.Hash) hash.Hash {
	d, ok := h.(*digest)
	if !ok {
		d = new(digest)
	}
	*d = *d0
	return d
}

h0 := newHash()
h0.Write(prefix)
var h hash.Hash
for _, message := range messages {
   h = h0.Clone(h)  // allocates on first iteration, reuses h on subsequent iterations
   h.Write(message)
   fmt.Println(h.Sum(nil))
}

[qmuntal]

This proposal tackles the same problem that made me start drafting #69293: there is no clean way to clone hashes.

About the proposed hash.Clone function, I had the same concerns as @magical. How do you instantiate a new hash before calling UnmarshalBinary? This I why in #69293 I proposed to define a hash.Cloner interface.

My motivation to have a common way to clone hash objects is to improve the compatibility of several hash implementations that I've implemented using CNG and OpenSSL with those libraries that are currently using MarshalBinary + UnmarshalBinary to clone a hash. The issue is that CNG/OpenSSL don't provide an API to serialize the internal state of a given hash, but they do provide APIs to clone a hash object.

[FiloSottile]

How do you intend to implement the fallback path in Clone? MarshalBinary + UnmarshalBinary only gives you the ability to save and restore a Hash's state, not construct a new instance of it.

Doh. Yes, that doesn't make sense, thank you.

We discussed this with @rsc and it it would make sense to follow the io/fs pattern:

package hash

// Clone returns a separate Hash instance with the same state as h.
//
// h must implement CloneHash, as all Hash implementations in the Go standard library do.
// Otherwise, Clone returns an error.
func Clone(h Hash) (Hash, error)

type CloneHash interface {
    hash.Hash
    Clone() hash.Hash
}

The question is whether we can make it not allocate by a combination of devirtualization and inlining. I think the answer is yes if either the type of the Hash passed to Clone devirtualizes or if it's a concrete type. Notably, I think the crypto/hmac use where a Hash is saved in the struct matches neither case. It would be useful if someone else could go through common cloning use cases

This isn't really urgent for Go 1.24. I don't want to add Clone methods to the new crypto/sha3 types (#69982) until we decide this, because there's a risk we'll make them not implement the interface, but crypto/sha3 can start with just MarshalBinary/UnmarshalBinary like every other stdlib Hash.

[mateusz834]

The question is whether we can make it not allocate by a combination of devirtualization and inlining. I think the answer is yes if either the type of the Hash passed to Clone devirtualizes or if it's a concrete type

Currently it would not work, see #64824.

[mateusz834]

@FiloSottile the io/fs pattern always includes the base interface, so:

type CloneHash interface {
    hash.Hash
    Clone() hash.Hash
}

What do you think?

EDIT: or even:

type CloneHash interface {
    hash.Hash
    Clone() hash.CloneHash
}

[FiloSottile]

Ah yes, that's what I meant to write. Not sure about returning a hash.CloneHash, I think it depends on whether we want users to pass the extended version around or keep it an "implementation detail" of hash.Clone.

[mateusz834]

Not sure about returning a hash.CloneHash, I think it depends on whether we want users to pass the extended version around or keep it an "implementation detail" of hash.Clone.

This way we also make sure that the returned (cloned) hash implements the hash.CloneHash, not doing so would let returning a non-cloneable hash.

[ericlagergren]

Has a generic hash.Clone been ruled out?

[mateusz834]

@FiloSottile Do we plan to implement this new interface by the crypto/hmac, this might influence the API, Clone() hash.Hash or Clone() hash.CloneHash must be allowed to return nil, because the provided hash constructor passed to hmac.New might return an hash.Hash that does not implement the interface (probably hash.Clone should treat that case as an error).

[mateusz834]

Or instead we can check whether the hash implements the new interface in hmac.New and return a different implementation that does not implement hmac.CloneHash in that case.

[FiloSottile]

Good point on crypto/hmac. I think I like the option of choosing the implementation in hmac.New the best.

[mateusz834]

Good point on crypto/hmac. I think I like the option of choosing the implementation in hmac.New the best.

This might cause issues in the future if we would like to make hmac.New alloc-free and devirtualizable. Also wouldn't this be problematic for the fips module (crypto/internal/fips/hmac)? It returns a concrete type now. But considering that crypto/hmac does not yet implement the encoding.BinaryMarshaler and Unmarshaler interfaces i assume that we don't need to make it clonable now.

go/src/crypto/hmac/hmac.go

Lines 34 to 37 in bea9b91

	// Note that unlike other hash implementations in the standard library,
	// the returned Hash does not implement [encoding.BinaryMarshaler]
	// or [encoding.BinaryUnmarshaler].
	func New(h func() hash.Hash, key []byte) hash.Hash {

[aclements]

This proposal has been added to the active column of the proposals project
and will now be reviewed at the weekly proposal review meetings.

[rsc]

Talked to @FiloSottile about this and we agreed to leave this for Go 1.25.

[rsc]

It sounds like we agree on:

package hash

// Clone returns a separate Hash instance with the same state as h.
//
// h must implement CloneHash, as all Hash implementations in the Go standard library do.
// Otherwise, Clone returns an error.
func Clone(h Hash) (Hash, error)

type CloneHash interface {
    hash.Hash
    Clone() hash.Hash
}

Do I have that right?

(I'm assuming we ignore CloneXOF until XOF is accepted, and it can be part of the XOF proposal.)

[mateusz834]

@rsc #69521 (comment)

Personally i think that we should treat nil from CloneHash.Clone as an error condition in hash.Clone and just return an error.

[aclements]

Given that we're trying to move toward concrete hash types, it would be nice if you could clone a concrete hash type and get back the same concrete hash type. However, I can't quite figure out how to make this work because CloneHash would have to be parameterized and then I'm not sure how a non-parameterized func Clone(h Hash) (Hash, error) would actually work.

General question: Why do people need to clone hash functions? I think understanding this would help us in evaluating this proposal. @magical mentioned using this to "optimize repeated hashes with the same prefix", but I don't actually know why people would want to do that either.

[aclements]

Thanks for the examples.

It sounds like getting Clone to return a concrete type is just impractical in the type system. Oh well.

I propose that instead of CloneHash for the interface we follow the example of other "-er" interfaces and call it Cloner. That also avoids stuttering on "hash".

We'll do a separate quick proposal for CloneXOF. I propose we call that XOFCloner.

[aclements]

Another question is whether the Clone function should implement a fallback if the hash implements BinaryMarshaller. There are several other places in std where we provide an "upgrade" interface along with a top-level function that uses the upgrade if possible and otherwise uses the fallback, and that pattern seems to work well. It might still fail in this case if the hash doesn't implement BinaryMarshaller.

[mateusz834]

@aclements how would that work? See the beginning of the discussion #69521 (comment).

[aclements]

@mateusz834 , I'm not sure what problem you're seeing. The top post says:

In practice, we should only fallback to BinaryMarshaler + BinaryUnmarshaler for the general case, while for standard library implementations we can do an undocumented interface upgrade to interface { Clone() Hash }.

That's exactly the pattern I'm proposing we capture in Clone. All of the std hashes would implement Cloner, so this fallback would not trigger, but it could trigger for hashes outside std that have implemented marshalling as a way to clone and haven't yet implemented Clone.

One could argue that that's too narrow to bother supporting. I'm not sure.

[mateusz834]

@aclements

How do you instantiate a new hash before calling UnmarshalBinary?

Also #69521 (comment)

[aclements]

'Doh! Thank you, @mateusz834 .

I see that the existing cloneHash function actually takes a constructor in the form of a crypto.Hash, which is how it gets a new hash to unmarshal into. I guess that must match the type of the hash.Hash or bad things will happen.

We still haven't really solved the potential performance issues with this API. I do agree that in principle, devirtualization plus inlining would often help here, though not necessarily all the time. Alternatively, we wouldn't have to inline if we included concrete return types in function summaries.

[aclements]

Have all remaining concerns about this proposal been addressed?

The proposal is to add the following to the hash package:

package hash

// Clone returns a separate Hash instance with the same state as h.
//
// h must implement Cloner, as all Hash implementations in the Go standard library do.
// Otherwise, Clone returns an error.
func Clone(h Hash) (Hash, error)

type Cloner interface {
    hash.Hash
    Clone() hash.Hash
}

And to implement the Clone method on all standard library hashes that currently implement MarshalBinary.

As a follow-on, ideally the compiler would implement optimizatoins such that, if the concrete type of the hash is fixed, it's possible to write an allocation-free Clone method.

[tmthrgd]

It feels to me like this particular version of Clone (func Clone(h Hash) (Hash, error)) is more or less pointless. If it can't fall back to encoding.BinaryMarshaler and encoding.BinaryUnmarshaler, then all it will ever do is call Cloner.Clone. You still need to check the error value, which ends up being no different to having to check the ok bool from h.(hash.Cloner).

You go from:

func doSomethingWithClonedHash(h hash.Hash) error {
	hc, ok := h.(hash.Cloner)
	if !ok {
		return errors.New("...")
	}
	h = hc.Clone()
	// use h
}

to:

func doSomethingWithClonedHash(h hash.Hash) error {
	h, err := hash.Clone(h)
	if err != nil {
		return err
	}
	// use h
}

That really doesn't seem much better to me.

I think either drop Clone function entirely, and just keep the Cloner interface, or perhaps define it like this:

package hash

// Clone returns a separate Hash instance with the same state as h.
//
// If h implements Cloner, as all Hash implementations in the Go standard library do, that
// will be used to clone the Hash.
//
// If h implements encoding.BinaryMarshaler and encoding.BinaryUnmarshaler, then a new
// Hash will be created and the state marshalled and unmarshalled into the new Hash.
//
// Otherwise, Clone returns an error.
func Clone[H hash.Hash](new func() H, h H) (H, error)

type Cloner interface {
	hash.Hash
	Clone() hash.Hash
}

It could then return h.Clone().(H) or use newH and the encoding interfaces as needed.

[mateusz834]

func Clone[H hash.Hash](newf func() H, h H) (H, error)

You do not always have a func() hash.Hash available when calling Clone, (hash.Hash is an interface), but this would work fine if we documented that newf can be nil, in which case the fallback does not happen and Clone returns an error. But also i am not sure whether this fallback is really that useful, do hash implementations outside of a std implement the encoding.BinaryMarshaler?

[aclements]

That's a great point that func Clone is pretty pointless compared with just doing the checked type assertion.

The marshal/unmarshal approach was always a bit of a hack, and it's not clear how widely supported it was outside of std, so between that and the awkwardness of implementing this fallback in a Clone function, it doesn't seem like a pattern we actually want to encourage.

Hence, it seems like we should just do the Cloner interface and leave it at that.

[aclements]

Based on the discussion above, this proposal seems like a likely accept.
— aclements for the proposal review group

The proposal is to add the following to the hash package:

package hash

// A Cloner is a hash function whose state can be cloned.
// All hashes in the standard library implement this interface.
type Cloner interface {
    hash.Hash
    Clone() hash.Hash
}

And to implement the Clone method on all standard library hashes (most, but not all of which, already implement MashalBinary/UnmarshalBinary).

As a follow-on, ideally the compiler would implement optimizatoins such that, if the concrete type of the hash is fixed, it's possible to write an allocation-free Clone method.

[gopherbot]

Change https://go.dev/cl/644275 mentions this issue: hash: add Clone interface

[gopherbot]

Change https://go.dev/cl/644315 mentions this issue: crypto,hash: implement hash.Cloner for partial hashes

[aclements]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— aclements for the proposal review group

The proposal is to add the following to the hash package:

package hash

// A Cloner is a hash function whose state can be cloned.
// All hashes in the standard library implement this interface.
type Cloner interface {
    hash.Hash
    Clone() hash.Hash
}

And to implement the Clone method on all standard library hashes (most, but not all of which, already implement MashalBinary/UnmarshalBinary).

As a follow-on, ideally the compiler would implement optimizatoins such that, if the concrete type of the hash is fixed, it's possible to write an allocation-free Clone method.

[magical]

I don't really see the point of Clone as accepted. In the long run i think we want to move towards having the hash packages return concrete types (as is done in crypto/internal/fips140). In that world, it would make more sense for Clone to return the concrete type as well (obviating any need for devirtualization). In fact, most hashes will not even need a Clone method because a shallow copy is enough. You only really need the Cloner interface for cases like crypto/hmac where the underlying hash is not known at compile time, and all the compiler optimization in the world will not help you avoid the allocations in that case. (Unless it is paired with a Set method, as i described in my earlier comment.)

[rsc]

It seems perfectly reasonable to write code that is not specific to a single hash and yet still wants to Clone the hash.

[gopherbot]

Change https://go.dev/cl/649195 mentions this issue: cmd/compile: devirtualize interface calls with type assertions