keep-starknet-strange / raito Goto Github PK

ver:
The coinbase transaction reward should not be included in the total output of the fee() function.

How to reproduce:
validate_and_apply on genesis block or block 170

The test helper used for converting hex strings into byte arrays works incorrectly

We need tests for:

• conversions u256 to Hash and Hash to u256
• bit shifts shl and shr
• fast_pow

Also need to add docstrings for every undocumented method.

All txid, best_block_hash should be of type Hash

Implement function to calculate transaction fee:

ZeroSync version:
https://github.com/ZeroSync/ZeroSync/blob/f1bd4736b0bac190ac48cbc8d5fcd92e2e1be7b9/src/transaction/transaction.cairo#L262

Implement compute_total_work function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Define a ChainState struct to represent the current state of the blockchain.

Acceptance Criteria:

• Define ChainState struct with fields:
  • block_height: u32
  • total_work: u128
  • best_block_hash: [u8; 32]
  • current_target: u32
  • epoch_start_time: u32
  • prev_timestamps: [u32; 11]
• Implement Default trait for ChainState

Resources:

• ZeroSync Cairo 0 code: block_header.cairo

Implement validate_target function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Implement validate_merkle_root function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Depends on #12

Add two verification tests of blocks from tests/blocks. Add tests to tests/blocks.cairo.

When assigned please join project tg group.

Provide python version of: #18.

It should be easy to extend it to include corresponding utxs for each tx input when we add them to the data types.

Current behavior: oldest timestamp is removed from the beginning of the array, new timestamp also added to the beginning of the array.

Expected behavior: oldest timestamp is removed from the beginning of the array, new timestamp added to the end.

Notes: in Zerosync implementation they use reversed order i.e. oldest timestamps are in the end of the array while the recent ones in the beginning. However for validation purposes (more specifically for computing the median) it does not matter.

Create a function to convert a 256-bit target back to the compact bits representation.

Acceptance Criteria:

• Implement target_to_bits(target: U256) -> Result<u32, Error>
• Calculate the appropriate exponent and mantissa
• Combine exponent and mantissa into the compact format
• Ensure the result is valid and normalized
• Handle potential overflow errors

Resources:

• ZeroSync Cairo 0 code: block_header.cairo

Implement validate_timestamp function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Prepare a script to fetch bitcoin blocks and format them as Cairo structs:

• given a block hash it should generate a Cairo file named: block_<block_hash>.cairo containing a declaration of a Block struct (see:

  raito/src/state.cairo

  Line 38 in bf58b29

  pub struct Block {

  )
• script should be integrated with scarb
• script should use sh i jq, examples here and here

ver:
The validate_coinbase function takes into account all the outputs of all the transactions in the block to verify the coinbase transaction.

How to reproduce:

Execute this function with the transactions of block 170, it reverts.
2txs:
tx1: ouput 50BTC (coinbase)
tx2: input 50
ouput (10 + 40)
fee: 0

Therefore:
total_output = 100 > 0 +50

Computer block reward function based on ZeroSync version

Create a function to compute the Merkle root of a list of transaction hashes.

Acceptance Criteria:

• Implement compute_merkle_root(leaves: Span<u256>) -> Result<u256, Error>
• Handle the case of an empty list of hashes
• Implement the Merkle tree algorithm
• Duplicate the last hash if there's an odd number of hashes
• Implement the CVE-2012-2459 fix (check for duplicate hashes)
• Return the computed Merkle root
• unit tests

Resources:

• ZeroSync Cairo 0 code: merkle_tree.cairo

Implement validate_proof_of_work function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Implement next_prev_timestamps function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Introduce Encode trait (SCALE like) for serializing Bitcoin structures (transactions, inputs, outputs, scripts) into bytes.

Create a function to read a block header from a byte stream.

Acceptance Criteria:

• Implement read_block_header(reader: &mut Reader) -> Result<BlockHeader, Error>
• Read each field of the block header in order
• Handle potential read errors
• Return a BlockHeader struct if successful

Resources:

• ZeroSync Cairo 0 code: block_header.cairo
• Shinigami codebase for error handling examples

Make shr and shl functions generic over its input types(not type). Functions are here:

Some ideas are here:

• https://github.com/keep-starknet-strange/joyboy/blob/4d747257b65cb46b6506bc65b18bbe3adff95658/onchain/src/utils.cairo#L72
• https://github.com/keep-starknet-strange/joyboy/blob/4d747257b65cb46b6506bc65b18bbe3adff95658/onchain/src/utils.cairo#L93

but note, we are using Cairo 2.7.0, wide mull is in core lib now.

#77 introduced Encode trait and implemented it for Span<T> and ByteArray types. We also need to implement it for some structs that need it

Using scarb get_block should generate interesting bitcoin blocks. What means interesting? For sure we need blocks representing all soft forks, halvings, historial blocks like block containing pizza transaction. I assume we can start with 10 - 20 blocks.

In order to use get_block you will need RPC endpoint and credentials. You will get those in pm on tg.

When assigned please join project tg group.

Current merkle_root calculation uses u256 to represent internal hashes in the tree. While this seems very natural, it is not how things work internally. Under the hood compute_sha256_u32_array which accepts Array<u32> and returns [u32; 8], so some work is wasted doing conversions. Try to optimise the process. Don't go too far though merkle_root function should still return u256 but can accept Array<Array<u32>>.

Provide speedup measurements.

Implement block_hash function:

Description:
https://learnmeabitcoin.com/technical/block/hash/

Don't forget about unit tests.

Define a BlockHeader struct to represent a Bitcoin block header.

Acceptance Criteria:

• Define BlockHeader struct with fields:
  • version: u32
  • prev_block_hash: [u8; 32]
  • merkle_root: [u8; 32]
  • timestamp: u32
  • bits: u32
  • nonce: u32
• Use appropriate types for each field
• Implement Default trait for BlockHeader

Resources:

• ZeroSync Cairo 0 code: block_header.cairo
• Bitcoin Block Header: https://developer.bitcoin.org/reference/block_chain.html#block-headers

Create a function to convert the compact bits representation to the full 256-bit target.

Acceptance Criteria:

• Implement bits_to_target(bits: u32) -> Result<U256, Error>
• Extract exponent and mantissa from bits
• Calculate the full target value
• Ensure the target doesn't exceed the maximum allowed value
• Handle potential overflow errors

Resources:

• ZeroSync Cairo 0 code: block_header.cairo

Implement adjust_difficulty function.

Acceptance Criteria:

• implement body of the function based on ZeroSync version
• write unit tests

Depends on #9, #10

Create a function to validate coinbase transaction of a block:

Create a function to calculate txid:

according to the cdescription given here:
https://learnmeabitcoin.com/technical/transaction/input/txid/