bitcoin-stark / khepri

STARK-proven Stateful Bitcoin client enabling hyper fast trustless sync and checkpoints.

Khepri

STARK-proven Stateful Bitcoin client enabling hyper fast trustless sync and checkpoints.

Architecture

Description

The idea of Khepri is to leverage Stark proof system in order to solve some issues in Bitcoin ecosystem or at least enhance the user experience.

With Stark proofs and Cairo, we have the ability to verify the integrity of a computation without having to naively redo all computation. Hence a verifier can be sure of the honest execution of a program, without the need of executing it and check the result.

The verification of the proof is exponentially faster than the naive execution of the program, which provide scalability.

Moreover, the overhead of generating the proof is negligible compared to the normal execution without the generation of the proof.

This mechanism can enable a lot of potential optimizations on several use cases.

What kind of problems can we solve with this super power ? Well, there are so many issues we could imagine to tackle with this approach, here are some cool features that could be enabled with this system:

• hyper fast & trustless synchronization (IBD)
• enhanced Simplified Payment Verification
• protection against DoS on the P2P layer

In short, Khepri is a proof of concept to demonstrate how STARK proofs can be leveraged for Bitcoin without changing the protocol.

Usage

⚠️ WARNING! ⚠️

This is repo contains highly experimental code. Expect rapid iteration. Use at your own risk.

Set up the project

📦 Install the requirements

• protostar 0.3.2 or above

⛏️ Compile

protostar build

🌡️ Test

protostar test

📄 License

khepri is released under the MIT.

khepri's Issues

Hardcode genesis block

The genesis block must be hardcoded and registered as the first block of the chain.

Any block with the hash of the genesis block must bypass validation rules.

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md

Proof Logic around recreating Txid

Take a JSON of data that defines the bitcoin transaction:

{
txid of input: "",
vIn of input: 0,
outputAddresses:[],
vOut Balances:[],
OP_Return: ""
}

Possibly also scriptsig/pubscriptkey of previous transaction, probably not the signature

OP_Return for future reference (such as proving a USDT send).

We should be able to take the JSON in call data and prove it checks out with the txid provided in the call data.

Proof Logic around Tx Inclusion

Having verified that the proposed payment tx is valid for our trade, we want to prove the given txid is included in the block by tracing its merkle branch of proven spends.

Compute new height based on previous height instead of accepting it as a parameter

The current implementation expect the height of the current block to be passed as a parameter.

This should be computed from the actual previous height instead (ie. previous height + 1).

Rule: Check timestamp

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md#check-timestamp

Implementation of adjusted timestamp: https://github.com/bitcoin/bitcoin/blob/aac9c259b045e3238fe4293141e29ab8f2e60f8d/src/timedata.cpp#L35

Interface for Call Data

Write a simple wrapper to take Call Data from a user including their proposed txid for payment, the JSON data about it, and pass that to the other functions in the system.

Rule: Reject blocks with outdated version

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md#reject-blocks-with-outdated-version

Tests: Generate block headers for testing

Description

Generate test block data using Python scripts for testing with protostar by hardcoding or loading a JSON block header resource.

Look for duplicates

When a new block is received, we must first look if we already treated it. If so, there is nothing to do.

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md#look-for-duplicates

Store block headers

Description

There are multiple consensus rules that require past data from previous block headers.
For convenience we will store block headers data entirely. We expect it will help reorg management later.

Acceptance Criteria

• Block headers data are stored
• Block headers data are accessible by number and by hash

Rule: Reject if timestamp is the median time of the last 11 blocks or before

See https://en.bitcoin.it/wiki/Block_timestamp

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md#check-timestamp-against-prev

Integrate proof of work target rule in process_header

The target rule must actually be used by the process_header function.

Rule: Check proof of work target (bits)

Implement the rule that checks that the block's target (the nBits field) is the one expected (ie. equals to the one of the previous block, unless there is a retargeting).

See https://github.com/bitcoin-stark/khepri-starknet/blob/main/docs/bitcoin/block_header_validation_rules.md#check-proof-of-work-target-bits

Rewrite a safe version of the SHA256 library

Description

Fix the implementation of SHA256 so that it verifies the output via finalize_sha256.

Context

The official Cairo SHA256 library only handles up to 55 bytes length inputs. Our ad-hoc version can handle input up to 80 bytes, however it is unsafe as the hint verification is skipped.

Suggestion

Write a safe Cairo SHA256 library, based on the official one, that can handle arbitrary size inputs. This could be done as an external library that would replace the one in src/utils/sha256/

Rule: Check Proof Of Work

Description

Implement a rule to check the proof of work:

• Compute the target from nBits
• Verify the block header hash is smaller than the target.