chromium / chromium / src / b4d03cecf41261d71b498b3014acf2d08e67474b / . / extensions / browser / content_hash_tree.h

// Copyright 2014 The Chromium Authors. All rights reserved. | |

// Use of this source code is governed by a BSD-style license that can be | |

// found in the LICENSE file. | |

#ifndef EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_ | |

#define EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_ | |

#include <string> | |

#include <vector> | |

namespace extensions { | |

// This takes a list of sha256 hashes, considers them to be leaf nodes of a | |

// hash tree (aka Merkle tree), and computes the root node of the tree using | |

// the given branching factor to hash lower level nodes together. Tree hash | |

// implementations differ in how they handle the case where the number of | |

// leaves isn't an integral power of the branch factor. This implementation | |

// just hashes together however many are left at a given level, even if that is | |

// less than the branching factor (instead of, for instance, directly promoting | |

// elements). E.g., imagine we use a branch factor of 3 for a vector of 4 leaf | |

// nodes [A,B,C,D]. This implemention will compute the root hash G as follows: | |

// | |

// | G | | |

// | / \ | | |

// | E F | | |

// | /|\ \ | | |

// | A B C D | | |

// | |

// where E = Hash(A||B||C), F = Hash(D), and G = Hash(E||F) | |

// | |

// The one exception to this rule is when there is only one node left. This | |

// means that the root hash of any vector with just one leaf is the same as | |

// that leaf. Ie RootHash([A]) == A, not Hash(A). | |

std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes, | |

int branch_factor); | |

} // namespace extensions | |

#endif // EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_ |