ulib/digest/merkle-tree.cpp

// Copyright 2017 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <digest/merkle-tree.h>

#include <stdint.h>
#include <string.h>

#include <digest/digest.h>
#include <fbl/algorithm.h>
#include <fbl/alloc_checker.h>
#include <fbl/unique_ptr.h>
#include <zircon/assert.h>
#include <zircon/errors.h>

namespace digest {

// Size of a node in bytes.  Defined in tree.h.
constexpr size_t MerkleTree::kNodeSize;

// The number of digests that fit in a node.  Importantly, if L is a
// node-aligned length in one level of the Merkle tree, |L / kDigestsPerNode| is
// the corresponding digest-aligned length in the next level up.
const size_t kDigestsPerNode = MerkleTree::kNodeSize / Digest::kLength;

namespace {

// Digest wrapper functions.  These functions implement how a node in the Merkle
// tree is hashed:
//    digest = Hash((offset | level) + length + node_data + padding)
// where:
//  * offset is from the start of the VMO.
//  * level is the height of the node in the tree (data nodes have level == 0).
//  * length is the node size, e.g kNodeSize except possibly for the last node.
//  * node_data is the actual bytes from the node.
//  * padding is |kNodeSize - length| zeros.

// Wrapper for Digest::Init.  This primes the working |digest| initializing it
// and hashing the |locality| and |length|.
zx_status_t DigestInit(Digest* digest, uint64_t locality, size_t length) {
    zx_status_t rc;
    ZX_DEBUG_ASSERT(digest);
    ZX_DEBUG_ASSERT(length < UINT32_MAX);
    if ((rc = digest->Init()) != ZX_OK) {
        return rc;
    }
    digest->Update(&locality, sizeof(locality));
    uint32_t len32 = static_cast<uint32_t>(fbl::min(length, MerkleTree::kNodeSize));
    digest->Update(&len32, sizeof(len32));
    return ZX_OK;
}

// Wrapper for Digest::Update.  This will hash data from |in|, either |length|
// bytes or up to the next node boundary, as determined from |offset|.  Returns
// the number of bytes hashed.
size_t DigestUpdate(Digest* digest, const uint8_t* in, size_t offset, size_t length) {
    ZX_DEBUG_ASSERT(digest);
    // Check if length crosses a node boundary
    length = fbl::min(length, MerkleTree::kNodeSize - (offset % MerkleTree::kNodeSize));
    digest->Update(in, length);
    return length;
}

// Wrapper for Digest::Final.  This pads the hashed data with zeros up to a
// node boundary before finalizing the digest.
void DigestFinal(Digest* digest, size_t offset) {
    offset = offset % MerkleTree::kNodeSize;
    if (offset != 0) {
        size_t pad_len = MerkleTree::kNodeSize - offset;
        uint8_t pad[pad_len];
        memset(pad, 0, pad_len);
        digest->Update(pad, pad_len);
    }
    digest->Final();
}

////////
// Helper functions for working between levels of the tree.

// Helper function to transform a length in the current level to a length in the
// next level up.
size_t NextLength(size_t length) {
    if (length > MerkleTree::kNodeSize) {
        return fbl::round_up(length, MerkleTree::kNodeSize) / kDigestsPerNode;
    } else {
        return 0;
    }
}

// Helper function to transform a length in the current level to a node-aligned
// length in the next level up.
size_t NextAligned(size_t length) {
    return fbl::round_up(NextLength(length), MerkleTree::kNodeSize);
}

} // namespace

////////
// Creation methods

size_t MerkleTree::GetTreeLength(size_t data_len) {
    size_t next_len = NextAligned(data_len);
    return (next_len == 0 ? 0 : next_len + GetTreeLength(next_len));
}

zx_status_t MerkleTree::Create(const void* data, size_t data_len, void* tree, size_t tree_len,
                               Digest* digest) {
    zx_status_t rc;
    MerkleTree mt;
    if ((rc = mt.CreateInit(data_len, tree_len)) != ZX_OK ||
        (rc = mt.CreateUpdate(data, data_len, tree)) != ZX_OK ||
        (rc = mt.CreateFinal(tree, digest)) != ZX_OK) {
        return rc;
    }
    return ZX_OK;
}

MerkleTree::MerkleTree() : initialized_(false), next_(nullptr), level_(0), offset_(0), length_(0) {}

MerkleTree::~MerkleTree() {}

zx_status_t MerkleTree::CreateInit(size_t data_len, size_t tree_len) {
    initialized_ = true;
    offset_ = 0;
    length_ = data_len;
    // Data fits in a single node, making this the top level of the tree.
    if (data_len <= kNodeSize) {
        return ZX_OK;
    }
    fbl::AllocChecker ac;
    next_.reset(new (&ac) MerkleTree());
    if (!ac.check()) {
        return ZX_ERR_NO_MEMORY;
    }
    next_->level_ = level_ + 1;
    // Ascend the tree.
    data_len = NextAligned(data_len);
    if (tree_len < data_len) {
        return ZX_ERR_BUFFER_TOO_SMALL;
    }
    tree_len -= data_len;
    return next_->CreateInit(data_len, tree_len);
}

zx_status_t MerkleTree::CreateUpdate(const void* data, size_t length, void* tree) {
    ZX_DEBUG_ASSERT(offset_ + length >= offset_);
    // Must call CreateInit first.
    if (!initialized_) {
        return ZX_ERR_BAD_STATE;
    }
    // Early exit if no work to do.
    if (length == 0) {
        return ZX_OK;
    }
    // Must not overrun expected length.
    if (offset_ + length > length_) {
        return ZX_ERR_OUT_OF_RANGE;
    }
    // Must have data to read and a tree to fill if expecting more than one
    // digest.
    if (!data || (!tree && length_ > kNodeSize)) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Save pointers to the data, digest, and the next level tree.
    const uint8_t* in = static_cast<const uint8_t*>(data);
    size_t tree_off = (offset_ - (offset_ % kNodeSize)) / kDigestsPerNode;
    uint8_t* out = static_cast<uint8_t*>(tree) + tree_off;
    void* next = static_cast<uint8_t*>(tree) + NextAligned(length_);
    // Consume the data.
    zx_status_t rc = ZX_OK;
    while (length > 0 && rc == ZX_OK) {
        // Check if this is the start of a node.
        if (offset_ % kNodeSize == 0 &&
            (rc = DigestInit(&digest_, offset_ | level_, length_ - offset_)) != ZX_OK) {
            break;
        }
        // Hash the node data.
        size_t chunk = DigestUpdate(&digest_, in, offset_, length);
        in += chunk;
        offset_ += chunk;
        length -= chunk;
        // Done if not at the end of a node.
        if (offset_ % kNodeSize != 0 && offset_ != length_) {
            break;
        }
        DigestFinal(&digest_, offset_);
        // Done if at the top of the tree.
        if (length_ <= kNodeSize) {
            break;
        }
        // If this is the first digest in a new node, first initialize it.
        if (tree_off % kNodeSize == 0) {
            memset(out, 0, kNodeSize);
        }
        // Add the digest and ascend the tree.
        digest_.CopyTo(out, Digest::kLength);
        rc = next_->CreateUpdate(out, Digest::kLength, next);
        out += Digest::kLength;
        tree_off += Digest::kLength;
    }
    return rc;
}

zx_status_t MerkleTree::CreateFinal(void* tree, Digest* root) {
    return CreateFinalInternal(nullptr, tree, root);
}

zx_status_t MerkleTree::CreateFinalInternal(const void* data, void* tree, Digest* root) {
    zx_status_t rc;
    // Must call CreateInit first.  Must call CreateUpdate with all data first.
    if (!initialized_ || (level_ == 0 && offset_ != length_)) {
        return ZX_ERR_BAD_STATE;
    }
    // Must have root to write and a tree to fill if expecting more than one
    // digest.
    if (!root || (!tree && length_ > kNodeSize)) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Special case: the level is empty.
    if (length_ == 0) {
        if ((rc = DigestInit(&digest_, 0, 0)) != ZX_OK) {
            return rc;
        }
        DigestFinal(&digest_, 0);
    }
    // Consume padding if needed.
    const uint8_t* tail = static_cast<const uint8_t*>(data) + offset_;
    if ((rc = CreateUpdate(tail, length_ - offset_, tree)) != ZX_OK) {
        return rc;
    }
    initialized_ = false;
    // If the top, save the digest as the Merkle tree root and return.
    if (length_ <= kNodeSize) {
        *root = digest_.AcquireBytes();
        digest_.ReleaseBytes();
        return ZX_OK;
    }
    // Finalize the next level up.
    uint8_t* next = static_cast<uint8_t*>(tree) + NextAligned(length_);
    return next_->CreateFinalInternal(tree, next, root);
}

////////
// Verification methods

zx_status_t MerkleTree::Verify(const void* data, size_t data_len, const void* tree, size_t tree_len,
                               size_t offset, size_t length, const Digest& root) {
    uint64_t level = 0;
    size_t root_len = data_len;
    while (data_len > kNodeSize) {
        zx_status_t rc;
        // Verify the data in this level.
        if ((rc = VerifyLevel(data, data_len, tree, offset, length, level)) != ZX_OK) {
            return rc;
        }
        // Ascend to the next level up.
        data = tree;
        root_len = NextLength(data_len);
        data_len = NextAligned(data_len);
        tree = static_cast<const uint8_t*>(tree) + data_len;
        if (tree_len < data_len) {
            return ZX_ERR_BUFFER_TOO_SMALL;
        }
        tree_len -= data_len;
        offset /= kDigestsPerNode;
        length /= kDigestsPerNode;
        ++level;
    }
    return VerifyRoot(data, root_len, level, root);
}

zx_status_t MerkleTree::VerifyRoot(const void* data, size_t root_len, uint64_t level,
                                   const Digest& expected) {
    zx_status_t rc;
    // Must have data if length isn't 0.  Must have either zero or one node.
    if ((!data && root_len != 0) || root_len > kNodeSize) {
        return ZX_ERR_INVALID_ARGS;
    }
    const uint8_t* in = static_cast<const uint8_t*>(data);
    Digest actual;
    // We have up to one node if at tree bottom, exactly one node otherwise.
    if ((rc = DigestInit(&actual, level, (level == 0 ? root_len : kNodeSize))) != ZX_OK) {
        return rc;
    }
    DigestUpdate(&actual, in, 0, root_len);
    DigestFinal(&actual, root_len);
    return (actual == expected ? ZX_OK : ZX_ERR_IO_DATA_INTEGRITY);
}

zx_status_t MerkleTree::VerifyLevel(const void* data, size_t data_len, const void* tree,
                                    size_t offset, size_t length, uint64_t level) {
    zx_status_t rc;
    ZX_DEBUG_ASSERT(offset + length >= offset);
    // Must have more than one node of data and digests to check against.
    if (!data || data_len <= kNodeSize || !tree) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Must not overrun expected length.
    if (offset + length > data_len) {
        return ZX_ERR_OUT_OF_RANGE;
    }
    // Align parameters to node boundaries, but don't exceed data_len
    offset -= offset % kNodeSize;
    size_t finish = fbl::round_up(offset + length, kNodeSize);
    length = fbl::min(finish, data_len) - offset;
    const uint8_t* in = static_cast<const uint8_t*>(data) + offset;
    // The digests are in the next level up.
    Digest actual;
    const uint8_t* expected = static_cast<const uint8_t*>(tree) + (offset / kDigestsPerNode);
    // Check the data of this level against the digests.
    while (length > 0) {
        if ((rc = DigestInit(&actual, offset | level, data_len - offset)) != ZX_OK) {
            return rc;
        }
        size_t chunk = DigestUpdate(&actual, in, offset, length);
        in += chunk;
        offset += chunk;
        length -= chunk;
        DigestFinal(&actual, offset);
        if (actual != expected) {
            return ZX_ERR_IO_DATA_INTEGRITY;
        }
        expected += Digest::kLength;
    }
    return ZX_OK;
}

} // namespace digest

////////
// C-style wrapper functions

using digest::Digest;
using digest::MerkleTree;

struct merkle_tree_t {
    MerkleTree obj;
};

size_t merkle_tree_get_tree_length(size_t data_len) {
    return MerkleTree::GetTreeLength(data_len);
}

zx_status_t merkle_tree_create_init(size_t data_len, size_t tree_len, merkle_tree_t** out) {
    zx_status_t rc;
    // Must have some where to store the wrapper.
    if (!out) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Allocate the wrapper object using a unique_ptr.  That way, if we hit an
    // error we'll clean up automatically.
    fbl::AllocChecker ac;
    fbl::unique_ptr<merkle_tree_t> mt_uniq(new (&ac) merkle_tree_t());
    if (!ac.check()) {
        return ZX_ERR_NO_MEMORY;
    }
    // Call the C++ function.
    if ((rc = mt_uniq->obj.CreateInit(data_len, tree_len)) != ZX_OK) {
        return rc;
    }
    // Release the wrapper object.
    *out = mt_uniq.release();
    return ZX_OK;
}

zx_status_t merkle_tree_create_update(merkle_tree_t* mt, const void* data, size_t length,
                                      void* tree) {
    // Must have a wrapper object.
    if (!mt) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Call the C++ function.
    zx_status_t rc;
    if ((rc = mt->obj.CreateUpdate(data, length, tree)) != ZX_OK) {
        return rc;
    }
    return ZX_OK;
}

zx_status_t merkle_tree_create_final(merkle_tree_t* mt, void* tree, void* out, size_t out_len) {
    // Must have a wrapper object.
    if (!mt) {
        return ZX_ERR_INVALID_ARGS;
    }
    // Take possession of the wrapper object. That way, we'll clean up
    // automatically.
    fbl::unique_ptr<merkle_tree_t> mt_uniq(mt);
    // Call the C++ function.
    zx_status_t rc;
    Digest digest;
    if ((rc = mt_uniq->obj.CreateFinal(tree, &digest)) != ZX_OK) {
        return rc;
    }
    return digest.CopyTo(static_cast<uint8_t*>(out), out_len);
}

zx_status_t merkle_tree_create(const void* data, size_t data_len, void* tree, size_t tree_len,
                               void* out, size_t out_len) {
    zx_status_t rc;
    Digest digest;
    if ((rc = MerkleTree::Create(data, data_len, tree, tree_len, &digest)) != ZX_OK) {
        return rc;
    }
    return digest.CopyTo(static_cast<uint8_t*>(out), out_len);
}

zx_status_t merkle_tree_verify(const void* data, size_t data_len, void* tree, size_t tree_len,
                               size_t offset, size_t length, const void* root, size_t root_len) {
    // Must have a complete root digest.
    if (root_len < Digest::kLength) {
        return ZX_ERR_INVALID_ARGS;
    }
    Digest digest(static_cast<const uint8_t*>(root));
    return MerkleTree::Verify(data, data_len, tree, tree_len, offset, length, digest);
}