Hash Functions&Merkle Tree

对读操作进行完整性检查，通过在加载的块上重新计算一个哈希，然后根据片外地址将得到的哈希与片上哈希比较。
缺点：不可承受的片上存储开销，并假设128位哈希和512位cache line，其开销为保护内存空间的25 %。

片上存储需求是无法承受的，有必要将这些参考值"安全"地存储在片外。递归地应用认证原语，形成了一个完整性树结构，只需要将树的根存储在处理器芯片上。
Merkle tree认证过程是完全可并行的，因为这个过程所需的所有输入都可以在这个过程开始之前得到；然而更新过程不可并行。

MAC Functions&PAT (Parallelizable Authentication Tree)

写操作为每个数据块计算一个MAC，MAC计算使用的密钥被安全地存储在可信芯片上，只有片上验证引擎本身能够计算出有效的MAC，因此MAC可以存储在不可信的外部存储中。MAC计算还用nonce防止重放攻击。读操作，用nonce和data重新计算MAC，并和外部取得的MAC进行比较。
每512b cache line计算一个MAC，并且使用64比特的nonces，那么相应的片上存储开销为12.5 %

PAT使用MAC克服了不可并行更新的问题。除了最后一级，每一步的Nonce和MAC value都被送到外部。根MAC发送到外部存储器，而nonce N存储在片上；这种方式使树根具有防篡改性，因为敌手不能在没有存储在芯片上的密钥K的情况下生成新的MAC，也不能重放旧的MAC，因为它不会由当前的根节点产生。
树更新过程也是可并行化的，因为每个分支树节点都是由独立生成的输入nonces计算得到的。

Block-Level AREA&TEC-Tree(Tamper-Evident Counter Tree)

为分组加密算法增加了完整性校验功能。plaintext block P (where P=D||N)，把冗余数据N存在片上。
根据所实现的分组加密算法，相应的开销在25 % ~ 50 %之间。

将生成的加密块存储在外部存储器中，并将创建的最后一个块(即TEC - Tree的根)加密时使用的nonce保存在片上，使得根不可篡改。没有密钥的敌手不能创建树节点，而没有片上根节点，他就不能重放树根。树更新过程包括：i )加载D的分支解密节点，ii )更新nonces，iii )重加密节点。

比较

TEC - Tree还提供数据的机密性。与merkel tree相比，TEC - Tree和PAT也具有较高的片外存储开销，特别是由于它们需要存储额外的元数据nonces。

优化技术

• 缓存技术：【Caches and Merkle Trees for Efficient Memory Integrity Verification】将Merkle树的性能开销降低到25 %以下。通过改变哈希函数- -从SHA - 1到GCM，甚至声称性能开销保持在5 %以下。
• Bonsai Merkle Tree：【Using Address Independent Seed Encryption and Bonsai Merkle Trees to Make Secure Processors OS and PerformanceFriendly】平均而言，4KB内存页和64B缓存块需要一个8位的计数器。因此，与直接应用于内存块的常规Merkle树相比，使用Bonsai Merkle树进行身份验证的内存量减少了1：64。该方法将完整性树的执行时间开销从12.1 %降低到1.8 %，将节点存储的外部内存开销从33.5 %降低到21.5 %。