Bao

name: inverse
layout: true
class: center, middle, inverse
---
# Bao

## a general-purpose cryptographic tree hash

### and perhaps the fastest hash function in the world

.footnote[
code: https://github.com/oconnor663/bao <br/>
slides: https://jacko.io
]
---
layout: false
.left-column[
  ## Caveats
]
.right-column[
## "Fastest" is tricky.

Speed depends on your hardware and the size of your input. There is no "fastest
hash in the world" on all platforms or for all inputs.

## Bao isn't stable yet.

Version 1.0 is a couple months away, and hashes will change before then.

## Cryptography is hard.

I'm not a cryptographer, but real cryptographers are helping. Big thanks to
Zooko Wilcox-O'Hearn and Samuel Neves.
]
---
template: inverse

## What is a hash function?
---
layout: false
.left-column[
  ## Hash functions
]
.right-column[
  Turn a big file into a small.red[*] number.

```bash
$ md5sum my_big_movie.mp4
78035db461c9ebff34c6da825eb314e2  my_big_movie.mp4

$ sha1sum my_big_movie.mp4
592e98dc68ddd0fca198064a192aaf808cfea6d6  my_big_movie.mp4

$ sha256sum my_big_movie.mp4
93984073d78d2e18be8519601c051ade3796b987faa67286c3a1d5e323286892  my_big_movie.mp4
```

Different files have completely different hashes.

```bash
$ md5sum another_movie.mp4
a099223e1246644e685f8ea3365abc2c  another_movie.mp4

$ sha1sum another_movie.mp4
4de5f92070b35e8c90937c38ba1d33dcadd084a8  another_movie.mp4

$ sha256sum another_movie.mp4
50c393f158c3de2db92fa9661bfb00eda5b67c3a777c88524ed3417509631625  another_movie.mp4
```

.footnote[.red[*] Well, small by a computer's standards. But 64 digits is a pretty big number.]
]
---
.left-column[
  ## Hash functions
  ## On the internet
]
.right-column[
https://www.archlinux.org/download

.image-100[![Arch Linux download image](assets/arch_download.png)]
]
---
.left-column[
  ## Hash functions
  ## On the internet
  ## On the inside
]
.right-column[
.image-100[![SHA256 image](assets/sha256.png)]

`c` stands for the "compression function". Note how the result of each
compression is an input to the next one.

.footnote[.red[*] Image source: https://medium.com/@pkmar437/blockchain-for-layman-part-2-a8984fda0acc]
]
---
template: inverse

## Speed ~~demon~~ demo!
---
template: inverse

## What is a tree hash?
---
.left-column[
  ## Tree hashes
]
.right-column[
.image-100[![tree hash](assets/tree_hash.png)]

- downsides
    - some overhead (but not much!)
- upsides
    - parallelism (breaking speed records!)
    - streaming

.footnote[.red[*] Image source: https://en.wikipedia.org/wiki/Merkle_tree]
]
---
.left-column[
  ## Tree hashes
  ## Streaming
]
.right-column[
If we store the data blocks and all of the intermediate hashes together in an
encoded file, we can stream the data back out and verify it all as we go:

```bash
# Take a look at the hash of a movie file.
$ bao hash my_movie.mp4
51362b96d8d7f4d4ef4ff02251ccc1b03ef2989f0efbe9a7b05199f198d51727

# Encode the movie file into the Bao encoded format.
$ bao encode my_movie.mp4 my_movie.mp4.bao
$ ls -lh my_movie.mp4 my_movie.mp4.bao
-rw-r--r-- 1 jacko jacko 797K Nov 27 15:28 my_movie.mp4
-rw-r--r-- 1 jacko jacko 809K Nov 27 15:28 my_movie.mp4.bao

# Stream the movie back out of the encoding,
# while verifying its hash.
$ hash=`bao hash my_movie.mp4`
$ bao decode $hash my_movie.mp4.bao | vlc -
```
]
---
.left-column[
  ## Tree hashes
  ## Streaming
  ## Fancy streaming
]
.right-column[
```bash
$ bao --help
Usage: bao hash [<input>] [<inputs>... | --encoded
           | --outboard=<file>]

bao encode <input> (<output> | --outboard=<file>)

bao decode <hash> [<input>] [<output>]
           [--outboard=<file>] [--start=<offset>]
           [--count=<count>]

bao slice <start> <count> [<input>] [<output>]
           [--outboard=<file>]

bao decode-slice <hash> <start> <count> [<input>]
           [<output>]

bao (--help | --version)
```

`--start` lets you seek into the middle of an encoding. "Slicing" lets you
extract parts from the middle, so that they can be verified independently,
without changing the hash.
]
---
template: inverse

## Barney the Demosaur
---
template: inverse

## Parallelism in Rust
---
.left-column[
  ## Rust
]
.right-column[
.image-center[![Rust](assets/rust.svg)]

A systems programming language that runs blazingly fast, prevents segfaults,
and guarantees thread safety.

Featuring
- zero-cost abstractions
- move semantics
- guaranteed memory safety
- threads without data races
- trait-based generics
- pattern matching
- type inference
- minimal runtime
- efficient C bindings
]
---
.left-column[
  ## Rust
  ## Rayon
]
.right-column[
https://github.com/rayon-rs/rayon

<u>Data</u> parallelism made easy.

```rust
fn hash_recurse_rayon(
    input: &[u8],
    finalization: Finalization,
) -> Hash {

// The chunk case. Just hash the chunk.
    if input.len() <= CHUNK_SIZE {
        return hash_chunk(input, finalization);
    }

// The parent case. Divide the input into two parts
    // and recurse through the left and right subtrees
    // in parallel.
    let (left, right) = input.split_at(
        left_len(input.len() as u64) as usize);
    let (left_hash, right_hash) = rayon::join(
        || hash_recurse_rayon(left, NotRoot),
        || hash_recurse_rayon(right, NotRoot),
    );
    parent_hash(&left_hash, &right_hash, finalization)
}
```
]
---
.left-column[
  ## Rust
  ## Rayon
  ## SIMD
]
.right-column[
.image-100[![simd](assets/simd_add.png)]

Functions using these intrinsics need annotations like this:

```rust
#[target_feature(enable = "avx2")]
pub unsafe fn compress(
    h: &mut StateWords,
    msg: &Block,
    count: u128,
    lastblock: u64,
    lastnode: u64,
) {
    ...
}
```
]
---
.left-column[
  ## Rust
  ## Rayon
  ## SIMD
]
.right-column[
.image-100[![simd](assets/simd_add.png)]

And before you call them you need to do checks like this:

```rust
#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
{
    if is_x86_feature_detected!("avx2") {
        return avx2::compress;
    }
}
return portable::compress;
```
]
---
.left-column[
  ## Rust
  ## Rayon
  ## SIMD
  ## BLAKE2
]
.right-column[
.image-100[![blake2](assets/blake2_matrix.png)]

Each of the rows can be stored in a single vector.

But it's actually faster to hash 4 (BLAKE2b) or 8 (BLAKE2s) inputs in parallel,
using 16 vectors.

When AVX-512 comes out, the parallelism will double.

.footnote[.red[*] Image source: https://131002.net/blake/blake.pdf]
]
---
template: inverse

## Cryptographic security
---
.left-column[
  ## Preimage resistance
]
.right-column[
The only way to figure out what input generated a given hash, is to try all the
possibilities. You can't work backwards.
]
---
.left-column[
  ## Preimage resistance
  ## Collision resistance
]
.right-column[
The only way to figure out what input generated a given hash, is to try all the
possibilities. You can't work backwards.

No two different inputs ever generate the same hash.
]
---
.left-column[
  ## Preimage resistance
  ## Collision resistance
  ## Length extensions
]
.right-column[
The only way to figure out what input generated a given hash, is to try all the
possibilities. You can't work backwards.

No two different inputs ever generate the same hash.

There's no way to use the hash of one input to help you find the hash of a
related input.
]
---
.left-column[
  ## Preimage resistance
  ## Collision resistance
  ## Length extensions
  ## Attacks
]
.right-column[
A collision attack:.red[*]
.image-100[![SHA256 image](assets/collision.png)]

An extension attack:.red[*]
.image-100[![SHA256 image](assets/extension.png)]
]
---
.left-column[
  ## Preimage resistance
  ## Collision resistance
  ## Length extensions
  ## Attacks
  ## Security proof
]
.right-column[
**Sufficient conditions for sound tree and sequential hashing modes** by Guido
Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche (the Keccak/SHA3
team)

https://eprint.iacr.org/2009/210.pdf

Three conditions for security:

- **Tree decodability:** You can tell leaves and parents apart.
- **Message completeness:** You can reconstruct the original input from the tree.
- **Final-node separability:** You can tell the root apart from the rest.

.footnote[.red[*] Images on the previous slide are from the paper above.]
]
---
template: inverse

## Monster hardware demo!
---
name: last-page
template: inverse

## Future directions

BLAKE2b vs BLAKE2s

Alternative tree structures

## Thanks for listening!

## Questions?

## https://github.com/oconnor663/bao