74 lines
1.9 KiB
Go
74 lines
1.9 KiB
Go
|
package backend
|
||
|
|
|
||
|
|
import (
|
||
|
|
"crypto/sha256"
|
||
|
|
"encoding/hex"
|
||
|
|
)
|
||
|
|
|
||
|
|
// RFC 6962 §2.1 Merkle tree hashing. We use the standard CT scheme:
|
||
|
|
// leaf hash = SHA-256(0x00 || data)
|
||
|
|
// node hash = SHA-256(0x01 || left || right)
|
||
|
|
// so that an inclusion proof from this server can later be audited by
|
||
|
|
// anything that speaks the certificate-transparency merkle format.
|
||
|
|
|
||
|
|
func leafHash(data []byte) []byte {
|
||
|
|
h := sha256.New()
|
||
|
|
h.Write([]byte{0x00})
|
||
|
|
h.Write(data)
|
||
|
|
return h.Sum(nil)
|
||
|
|
}
|
||
|
|
|
||
|
|
func nodeHash(left, right []byte) []byte {
|
||
|
|
h := sha256.New()
|
||
|
|
h.Write([]byte{0x01})
|
||
|
|
h.Write(left)
|
||
|
|
h.Write(right)
|
||
|
|
return h.Sum(nil)
|
||
|
|
}
|
||
|
|
|
||
|
|
// merkleTreeHash computes the Merkle Tree Hash (MTH) of the given list of
|
||
|
|
// leaf hashes. MTH([]) is SHA-256 of the empty string per RFC 6962, but we
|
||
|
|
// never call it on an empty slice in practice.
|
||
|
|
func merkleTreeHash(leaves [][]byte) []byte {
|
||
|
|
n := len(leaves)
|
||
|
|
switch n {
|
||
|
|
case 0:
|
||
|
|
h := sha256.Sum256(nil)
|
||
|
|
return h[:]
|
||
|
|
case 1:
|
||
|
|
return append([]byte(nil), leaves[0]...)
|
||
|
|
}
|
||
|
|
k := largestPow2LessThan(n)
|
||
|
|
return nodeHash(merkleTreeHash(leaves[:k]), merkleTreeHash(leaves[k:]))
|
||
|
|
}
|
||
|
|
|
||
|
|
// auditPath returns the RFC 6962 audit path for leaf index m within the
|
||
|
|
// given leaf-hash slice (tree size n = len(leaves)). The returned slice is
|
||
|
|
// the ordered list of sibling hashes from the leaf up to (but not including)
|
||
|
|
// the root. Returns an empty slice for a single-leaf tree.
|
||
|
|
func auditPath(leaves [][]byte, m int) [][]byte {
|
||
|
|
n := len(leaves)
|
||
|
|
if n <= 1 {
|
||
|
|
return nil
|
||
|
|
}
|
||
|
|
k := largestPow2LessThan(n)
|
||
|
|
if m < k {
|
||
|
|
return append(auditPath(leaves[:k], m), merkleTreeHash(leaves[k:]))
|
||
|
|
}
|
||
|
|
return append(auditPath(leaves[k:], m-k), merkleTreeHash(leaves[:k]))
|
||
|
|
}
|
||
|
|
|
||
|
|
// largestPow2LessThan returns the largest power of two strictly smaller than
|
||
|
|
// n (n must be >= 2).
|
||
|
|
func largestPow2LessThan(n int) int {
|
||
|
|
k := 1
|
||
|
|
for k < n {
|
||
|
|
k <<= 1
|
||
|
|
}
|
||
|
|
return k >> 1
|
||
|
|
}
|
||
|
|
|
||
|
|
func sha256Hex(b []byte) string {
|
||
|
|
return "sha256:" + hex.EncodeToString(b)
|
||
|
|
}
|