Time-Partitioned Monoid Tree for Teragrep

Time-Partitioned Monoid Tree for Teragrep is for constructing mathematical total sum of Teragrep Archive. The Monoid Tree constructs of Ristretto255 sums of the tree leaves which then form up branch sums and totally a root sum. The Tree is implemented in immutable manner using copy-on-write to allow frozen snapshots of the tree state.

Features

• Immutable via copy-on-write, each change produce a new copy of the tree.

• Idempotent, changes are versioned and old versions are skipped.

• Views are thread-safe. Writes too but versions need to be applied in order.

• Null-free. Tree nodes initialize always into identity elements.

Documentation

See the official documentation on docs.teragrep.com.

Limitations

• Tree is currently limited to Root-Year-Month-Day-Hour partitioning, however generalized implementation could be easily made that scales to desired precision.

How to [compile/use/implement]

package com.teragrep.tmt_01;

import com.goterl.lazysodium.LazySodiumJava;
import com.goterl.lazysodium.SodiumJava;
import com.goterl.lazysodium.interfaces.Ristretto255;
import com.teragrep.tmt_01.node.Root;
import org.junit.jupiter.api.Test;

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.time.Instant;
import java.util.concurrent.atomic.AtomicReference;

public class ReadmeTest {

    @Test
    void main() throws NoSuchAlgorithmException {
        // initialize first lazySodiumJava so we use only one instance
        LazySodiumJava lazySodiumJava = new LazySodiumJava(new SodiumJava());

        // our example payload to be ingested into the tree
        RistrettoPoint pointDelta = bytesToPoint(lazySodiumJava, "Hello World!".getBytes(StandardCharsets.UTF_8));

        Change change = new ChangeImpl(1L, Instant.EPOCH, pointDelta);

        // identityElement that sums up to itself
        RistrettoPoint identityElement = new LazysodiumRistrettoPoint(
                lazySodiumJava,
                new byte[Ristretto255.RISTRETTO255_BYTES]
        );

        // tree initialization
        TimePartitionedMonoidTree tree = new TimePartitionedMonoidTreeImpl(identityElement);

        // cause tree to process the change producing a new root, processChange returns a new root
        Root newRoot = tree.processChange(change);

        // new tree can be forked from an existing just as easily
        TimePartitionedMonoidTree otherTree = new TimePartitionedMonoidTreeImpl(
                identityElement,
                new AtomicReference<>(newRoot)
        );

        otherTree.processChange(change);

        // ... a forest?

        // one can search delta between the trees by point() methods
        RistrettoPoint hourPoint = tree.root().year(1970).month(0).day(0).hour(0).point();
    }

    private static RistrettoPoint bytesToPoint(LazySodiumJava lazySodiumJava, byte[] data)
            throws NoSuchAlgorithmException {
        MessageDigest digest = MessageDigest.getInstance("SHA-512");
        byte[] hash64 = digest.digest(data);
        byte[] point = new byte[Ristretto255.RISTRETTO255_BYTES];
        boolean success = lazySodiumJava.cryptoCoreRistretto255FromHash(point, hash64);
        if (!success) {
            throw new RuntimeException("Elligator 2 mapping failed");
        }
        return new LazysodiumRistrettoPoint(lazySodiumJava, point);
    }

}

Contributing

You can involve yourself with our project by opening an issue or submitting a pull request.

Contribution requirements:

1. All changes must be accompanied by a new or changed test. If you think testing is not required in your pull request, include a sufficient explanation as why you think so.

2. Security checks must pass

3. Pull requests must align with the principles and values of extreme programming.

4. Pull requests must follow the principles of Object Thinking and Elegant Objects (EO).

Read more in our Contributing Guideline.

Contributor License Agreement

Contributors must sign Teragrep Contributor License Agreement before a pull request is accepted to organization’s repositories.

You need to submit the CLA only once. After submitting the CLA you can contribute to all Teragrep’s repositories.