opentimestamps/ots/sequence.go

package ots

import (
	"bytes"
	"fmt"
	"io"
	"slices"

	"git.intruders.space/public/opentimestamps/varn"
	"git.intruders.space/public/opentimestamps/verifyer"
	"github.com/btcsuite/btcd/wire"
)

type Sequence []Instruction

func (seq Sequence) GetAttestation() Attestation {
	if len(seq) == 0 {
		return Attestation{}
	}
	att := seq[len(seq)-1]
	if att.Attestation == nil {
		return Attestation{}
	}
	return *att.Attestation
}

// Compute runs a sequence of operations on top of an initial digest and returns the result, which is often a
// Bitcoin block merkle root. It also tries to identify the point in the sequence in which an actual Bitcoin
// transaction is formed and parse that.
func (seq Sequence) Compute(initial []byte) (merkleRoot []byte, bitcoinTx *wire.MsgTx) {
	current := initial
	for i, inst := range seq {
		if inst.Operation == nil {
			break
		}

		// the first time we do a double-sha256 that is likely a bitcoin transaction
		if bitcoinTx == nil &&
			inst.Operation.Name == "sha256" &&
			len(seq) > i+1 && seq[i+1].Operation != nil &&
			seq[i+1].Operation.Name == "sha256" {
			tx := &wire.MsgTx{}
			tx.Deserialize(bytes.NewReader(current))
			bitcoinTx = tx
		}

		current = inst.Operation.Apply(current, inst.Argument)
	}
	return current, bitcoinTx
}

// Verify validates sequence of operations that starts with digest and ends on a Bitcoin attestation against
// an actual Bitcoin block, as given by the provided Bitcoin interface.
func (seq Sequence) Verify(bitcoin verifyer.Bitcoin, digest []byte) (*wire.MsgTx, error) {
	if len(seq) == 0 {
		return nil, fmt.Errorf("empty sequence")
	}

	att := seq[len(seq)-1]
	if att.Attestation == nil || att.BitcoinBlockHeight == 0 {
		return nil, fmt.Errorf("sequence doesn't include a bitcoin attestation")
	}

	blockHash, err := bitcoin.GetBlockHash(int64(att.BitcoinBlockHeight))
	if err != nil {
		return nil, fmt.Errorf("failed to get block %d hash: %w", att.BitcoinBlockHeight, err)
	}

	blockHeader, err := bitcoin.GetBlockHeader(blockHash)
	if err != nil {
		return nil, fmt.Errorf("failed to get block %s header: %w", blockHash, err)
	}

	merkleRoot := blockHeader.MerkleRoot[:]
	result, tx := seq.Compute(digest)

	if !bytes.Equal(result, merkleRoot) {
		return nil, fmt.Errorf("sequence result '%x' doesn't match the bitcoin merkle root for block %d: %x",
			result, att.BitcoinBlockHeight, merkleRoot)
	}

	return tx, nil
}

func ParseTimestamp(buf varn.Buffer) ([]Sequence, error) {
	// read instructions
	//   if operation = push
	//   if 0x00 = attestation
	//      read tag [8 bytes]
	//      readvarbytes
	//        interpret these depending on the type of attestation
	//          if bitcoin: readvaruint as the block height
	//          if pending from calendar: readvarbytes as the utf-8 calendar url
	//      end or go back to last continuation byte
	//   if 0xff = pick up a continuation byte (checkpoint) and add it to stack

	currInstructionsBlock := 0
	seqs := make([]Sequence, 0, 10)

	// we will store checkpoints here
	checkpoints := make([][]Instruction, 0, 4)

	// start first instruction block
	seqs = append(seqs, make([]Instruction, 0, 30))

	// go read these tags
	for {
		tag, err := buf.ReadByte()
		if err != nil {
			if err == io.EOF {
				return seqs, nil
			}
			return nil, fmt.Errorf("failed to read operation byte: %w", err)
		}

		if tag == 0x00 {
			// enter an attestation context
			magic, err := buf.ReadBytes(8)
			if err != nil {
				return nil, fmt.Errorf("failed to read attestion magic bytes: %w", err)
			}

			this, err := buf.ReadVarBytes()
			if err != nil {
				return nil, fmt.Errorf("failed to read attestation bytes: %w", err)
			}
			abuf := varn.NewBuffer(this)

			switch {
			case slices.Equal(magic, PendingMagic):
				val, err := abuf.ReadVarBytes()
				if err != nil {
					return nil, fmt.Errorf("failed reading calendar server url: %w", err)
				}
				seqs[currInstructionsBlock] = append(
					seqs[currInstructionsBlock],
					Instruction{Attestation: &Attestation{CalendarServerURL: string(val)}},
				)
			case slices.Equal(magic, BitcoinMagic):
				val, err := abuf.ReadVarUint()
				if err != nil {
					return nil, fmt.Errorf("failed reading bitcoin block number: %w", err)
				}
				seqs[currInstructionsBlock] = append(
					seqs[currInstructionsBlock],
					Instruction{Attestation: &Attestation{BitcoinBlockHeight: val}},
				)
			default:
				return nil, fmt.Errorf("unsupported attestation type '%x': %x", magic, this)
			}

			// check if we have checkpoints and, if yes, copy them in a new block of instructions
			ncheckpoints := len(checkpoints)
			if ncheckpoints > 0 {
				// use this checkpoint as the starting point for the next block
				chp := checkpoints[ncheckpoints-1]
				checkpoints = checkpoints[0 : ncheckpoints-1] // remove this from the stack
				seqs = append(seqs, chp)
				currInstructionsBlock++
			}
		} else if tag == 0xff {
			// pick up a checkpoint to be used later
			currentBlock := seqs[currInstructionsBlock]
			chp := make([]Instruction, len(currentBlock))
			copy(chp, currentBlock)
			checkpoints = append(checkpoints, chp)
		} else {
			// a new operation in this block
			inst, err := ReadInstruction(buf, tag)
			if err != nil {
				return nil, fmt.Errorf("failed to read instruction: %w", err)
			}
			seqs[currInstructionsBlock] = append(seqs[currInstructionsBlock], *inst)
		}
	}
}