diff --git a/lz4diff/lz4diff.proto b/lz4diff/lz4diff.proto
new file mode 100644
index 0000000..f1a3a36
--- /dev/null
+++ b/lz4diff/lz4diff.proto
@@ -0,0 +1,59 @@
+//
+// Copyright (C) 2021 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+syntax = "proto3";
+
+package chromeos_update_engine;
+option optimize_for = LITE_RUNTIME;
+
+message CompressionAlgorithm {
+  enum Type {
+    UNCOMPRESSED = 0;
+    LZ4 = 1;
+    LZ4HC = 2;
+  }
+  Type type = 1;
+  int32 level = 2;
+}
+
+message CompressedBlockInfo {
+  // Require fields
+  uint64 uncompressed_offset = 1;
+  uint64 uncompressed_length = 2;
+  uint64 compressed_length = 3;
+
+  // optional SHA256 hash of re-compressed blob
+  bytes sha256_hash = 4;
+  // Patch to apply to re-compressed blob
+  bytes postfix_bspatch = 5;
+}
+
+enum InnerPatchType {
+  BSDIFF = 0;
+  PUFFDIFF = 1;
+}
+
+message CompressionInfo {
+  CompressionAlgorithm algo = 1;
+  repeated CompressedBlockInfo block_info = 2;
+  bool zero_padding_enabled = 3;
+}
+
+message Lz4diffHeader {
+  CompressionInfo src_info = 1;
+  CompressionInfo dst_info = 2;
+  InnerPatchType inner_type = 3;
+}
diff --git a/lz4diff/lz4diff_format.h b/lz4diff/lz4diff_format.h
new file mode 100644
index 0000000..5b5ce40
--- /dev/null
+++ b/lz4diff/lz4diff_format.h
@@ -0,0 +1,68 @@
+//
+// Copyright (C) 2021 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#ifndef UPDATE_ENGINE_LZ4DIFF_LZ4DIFF_FORMAT_H_
+#define UPDATE_ENGINE_LZ4DIFF_LZ4DIFF_FORMAT_H_
+
+#include <string_view>
+#include <vector>
+
+#include <lz4diff/lz4diff.pb.h>
+
+namespace chromeos_update_engine {
+
+using Blob = std::vector<unsigned char>;
+
+// Format of LZ4diff patch:
+// struct lz4diff_header {
+//     char magic[8] = kLz4diffMagic;
+//     uint32_t version;
+//     uint32_t pb_header_size;         // size of protobuf message
+//     char pf_header[pb_header_size];
+// }
+
+constexpr std::string_view kLz4diffMagic = "LZ4DIFF";
+
+// 8 bytes magic + 4 bytes version + 4 bytes pb_header_size
+constexpr size_t kLz4diffHeaderSize = 8 + 4 + 4;
+
+constexpr uint32_t kLz4diffVersion = 1;
+
+struct CompressedBlock {
+  constexpr CompressedBlock() : CompressedBlock(0, 0, 0) {}
+  constexpr CompressedBlock(uint64_t offset,
+                            uint64_t length,
+                            uint64_t uncompressed_length)
+      : uncompressed_offset(offset),
+        compressed_length(length),
+        uncompressed_length(uncompressed_length) {}
+  constexpr bool IsCompressed() const noexcept {
+    return compressed_length < uncompressed_length;
+  }
+  uint64_t uncompressed_offset;
+  uint64_t compressed_length;
+  uint64_t uncompressed_length;
+};
+
+struct CompressedFile {
+  std::vector<CompressedBlock> blocks;
+  CompressionAlgorithm algo;
+  bool zero_padding_enabled{};
+};
+
+}  // namespace chromeos_update_engine
+
+#endif