hyperledger · GarmashAlex · Apr 27, 2025 · Apr 27, 2025 · Apr 27, 2025
diff --git a/docs/verkle-trie-README.md b/docs/verkle-trie-README.md
@@ -0,0 +1,45 @@
+# Verkle Trie Documentation
+
+This directory contains documentation for the Verkle trie implementation in Hyperledger Besu.
+
+## What are Verkle Tries?
+
+Verkle tries are an advancement over the traditional Merkle Patricia Tries (MPTs) currently used in Ethereum. They provide more efficient proofs and improved scalability, which is crucial for Ethereum's future growth.
+
+The name "Verkle" combines "Vector commitment" and "Merkle". Unlike Merkle trees where proof size grows linearly with tree depth, Verkle tries have nearly constant-sized proofs regardless of the trie's depth.
+
+## Documentation Index
+
+1. [Verkle Trie Implementation](./verkle-trie-implementation.md) - Technical overview of how Verkle tries are implemented in Besu
+2. [Verkle Trie Development Guide](./verkle-trie-development-guide.md) - Guide for developers working with or contributing to the Verkle trie code
+
+## Key Benefits of Verkle Tries
+
+1. **Smaller Proof Sizes**: Verkle tries significantly reduce the size of state proofs
+2. **Improved Scalability**: Support for stateless clients and reduced state size
+3. **Enhanced Performance**: More efficient state access and updates
+4. **Future-Proofing**: Part of Ethereum's roadmap for scaling and efficiency improvements
+
+## Implementation Status
+
+The Verkle trie implementation in Besu is currently in development. The codebase includes:
+
+- Core cryptographic primitives (elliptic curve operations, finite field arithmetic)
+- Bandersnatch curve implementation
+- Basic point and field operations
+
+The full trie structure, including proof generation and verification, is under active development.
+
+## Related Resources
+
+- [EIP-6800: Verkle Trees](https://eips.ethereum.org/EIPS/eip-6800)
+- [Ethereum Research - Verkle Tries](https://notes.ethereum.org/@vbuterin/verkle_tree_eip)
+- [Besu Verkle Trie Repository](https://github.com/hyperledger/besu-verkle-trie)
+
+## Contributing
+
+We welcome contributions to both the codebase and documentation. Please see the [Development Guide](./verkle-trie-development-guide.md) for information on how to contribute.
+
+## Feedback
+
+If you have any questions or feedback about this documentation or the Verkle trie implementation, please open an issue on the [Besu GitHub repository](https://github.com/hyperledger/besu/issues). 
diff --git a/docs/verkle-trie-development-guide.md b/docs/verkle-trie-development-guide.md
@@ -0,0 +1,182 @@
+# Verkle Trie Development Guide
+
+This guide provides practical information for developers who want to work with or contribute to the Verkle trie implementation in Hyperledger Besu.
+
+## Development Environment Setup
+
+1. **Prerequisites**
+   - Java JDK 17 or later
+   - Git
+   - Gradle (wrapper is included in the project)
+
+2. **Getting the Source Code**
+   ```bash
+   git clone https://github.com/hyperledger/besu.git
+   cd besu
+   ```
+
+3. **Building the Project**
+   ```bash
+   ./gradlew build
+   ```
+
+4. **Building Just the Verkle Module**
+   ```bash
+   ./gradlew :ethereum:verkletrie:build
+   ```
+
+## Project Structure
+
+The Verkle trie implementation is located in the `ethereum/verkletrie` module of the Besu codebase. Here's an overview of the key files and directories:
+
+- `ethereum/verkletrie/src/main/java/org/hyperledger/besu/ethereum/verkletrie/bandersnatch/`
+  - `fp/Element.java`: Base field implementation
+  - `fr/Element.java`: Scalar field implementation
+  - `Point.java`: Projective point representation
+  - `PointAffine.java`: Affine point representation
+
+- `ethereum/verkletrie/src/test/`: Contains test cases for the Verkle implementation
+
+## Workflow for Development
+
+### 1. Understanding the Code
+
+Before making changes, it's important to understand the current implementation:
+
+- **Field arithmetic**: Study the Element classes in both `fp` and `fr` packages
+- **Elliptic curve operations**: Review the Point and PointAffine classes
+- **Test cases**: Examine existing tests to understand expected behavior
+
+### 2. Making Changes
+
+1. **Create a Feature Branch**
+   ```bash
+   git checkout -b feature/verkle-improvement
+   ```
+
+2. **Implement Changes**
+   - Update or add code to implement new features or fix bugs
+   - Follow existing code style and patterns
+
+3. **Add Unit Tests**
+   - Add test cases to verify your changes
+   - Ensure all existing tests still pass
+
+4. **Run Tests**
+   ```bash
+   ./gradlew :ethereum:verkletrie:test
+   ```
+
+### 3. Common Development Tasks
+
+#### Adding New Field Operations
+
+1. Identify the appropriate field class (`fp/Element.java` or `fr/Element.java`)
+2. Add the new operation method
+3. Add tests to verify the operation works correctly
+4. Update documentation if necessary
+
+#### Implementing Curve Operations
+
+1. Review the existing Point and PointAffine classes
+2. Add new methods to implement required curve operations
+3. Add tests to verify correctness
+4. Consider performance optimizations
+
+#### Working with the Full Trie Implementation
+
+As the full trie implementation is developed:
+
+1. Understand how the cryptographic primitives (points, fields) are used in the trie structure
+2. Consider data structures for nodes, proofs, and commitments
+3. Follow the Ethereum specifications for Verkle tries
+
+## Debugging Tips
+
+1. **Logging**: Use appropriate logging statements for debugging complex operations
+   ```java
+   import org.slf4j.Logger;
+   import org.slf4j.LoggerFactory;
+
+   private static final Logger LOG = LoggerFactory.getLogger(YourClass.class);
+
+   // Example usage
+   LOG.debug("Field element calculation: {}", element);
+   ```
+
+2. **Unit Testing**: Create focused unit tests for specific operations
+
+3. **Debugging Tools**:
+   - Use your IDE's debugger to step through complex calculations
+   - For field arithmetic, print intermediate values in hex format for easier verification
+
+## Performance Considerations
+
+1. **Field Arithmetic Optimization**:
+   - Field arithmetic operations can be performance-critical
+   - Consider using Montgomery form for repeated operations
+   - Minimize object creation in hot loops
+
+2. **Memory Usage**:
+   - Be mindful of object creation and memory usage
+   - Consider using object pools for frequently created objects like points
+
+3. **Future Native Implementation**:
+   - Performance-critical parts may be implemented in native code in the future
+   - Design Java interfaces with potential JNI integration in mind
+
+## Contributing
+
+1. **Code Style**:
+   - Follow existing code style and formatting
+   - Add appropriate Javadoc comments
+
+2. **Pull Requests**:
+   - Create a PR against the main branch
+   - Include a clear description of changes
+   - Reference any related issues
+
+3. **Review Process**:
+   - Address feedback from code reviews
+   - Ensure CI tests pass
+
+## Resources for Verkle Trie Development
+
+1. **Specifications**:
+   - [EIP-6800: Verkle Trees](https://eips.ethereum.org/EIPS/eip-6800)
+   - [Ethereum Research - Verkle Tries](https://notes.ethereum.org/@vbuterin/verkle_tree_eip)
+
+2. **External Implementations**:
+   - [Go-Verkle](https://github.com/gballet/go-verkle)
+   - [Rust-Verkle](https://github.com/ethereum/verkle-trie-ref)
+
+3. **Mathematical Background**:
+   - [Bandersnatch Elliptic Curve](https://github.com/ethereum/research/blob/master/verkle_trie/bandersnatch.py)
+   - [KZG Polynomial Commitments](https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html)
+
+## Current Development Status
+
+The Verkle trie implementation in Besu is still in development. Current focus areas include:
+
+1. Implementing core cryptographic primitives (fields, curve operations)
+2. Designing the trie structure and node representation
+3. Implementing proof generation and verification
+4. Integration with Besu's existing state management
+
+## Future Roadmap
+
+1. **Complete Trie Implementation**
+   - Node structure implementation
+   - Trie operations (get, insert, delete, update)
+
+2. **Proof System**
+   - KZG commitment scheme implementation
+   - Proof generation and verification
+
+3. **Integration**
+   - Integration with Besu's world state
+   - Support for state transitions
+
+4. **Optimization**
+   - Performance improvements
+   - Potential native code implementation for critical paths 
diff --git a/docs/verkle-trie-implementation.md b/docs/verkle-trie-implementation.md
@@ -0,0 +1,132 @@
+# Verkle Trie Implementation in Hyperledger Besu
+
+This document provides an overview of how Verkle tries are implemented in Hyperledger Besu, including both the Java code and any native components. This documentation aims to help new developers get onboarded faster when working with the Verkle trie implementation.
+
+## Overview
+
+Verkle tries are an improvement over Merkle Patricia Tries (MPTs), providing more efficient proofs and storage. The name "Verkle" comes from "Vector commitment" and "Merkle". The primary advantages of Verkle tries include:
+
+1. Significantly smaller proof sizes
+2. Improved performance for state access and updates
+3. Better scalability for Ethereum state management
+
+## Architecture
+
+The Verkle trie implementation in Besu is organized as follows:
+
+```
+ethereum/verkletrie/
+├── src/
+│   ├── main/java/org/hyperledger/besu/ethereum/verkletrie/
+│   │   └── bandersnatch/
+│   │       ├── fp/          # Field operations for base field
+│   │       ├── fr/          # Field operations for scalar field
+│   │       ├── Point.java   # Elliptic curve point representation
+│   │       └── PointAffine.java  # Affine representation of points
+│   └── test/
+└── build.gradle
+```
+
+## Core Components
+
+### 1. Bandersnatch Elliptic Curve
+
+Verkle tries use the Bandersnatch elliptic curve for cryptographic operations. Bandersnatch is an elliptic curve designed specifically for use in vector commitments, which makes it ideal for Verkle tries.
+
+Key classes:
+- `Point.java`: Represents a point on the Bandersnatch curve in projective coordinates
+- `PointAffine.java`: Represents a point in affine coordinates (x, y)
+
+### 2. Finite Field Arithmetic
+
+Verkle tries require efficient finite field arithmetic operations. Two primary finite fields are used:
+
+- **Base Field (fp)**: 
+  - Implemented in `fp/Element.java`
+  - Used for coordinates of points on the elliptic curve
+  - Operations include addition, subtraction, multiplication, inversion, etc.
+
+- **Scalar Field (fr)**:
+  - Implemented in `fr/Element.java`
+  - Used for scalars in cryptographic operations
+  - Similar interface to the base field, but with different field parameters
+
+### 3. Field Element Implementation
+
+Both finite fields implement elements with the following key operations:
+
+- Basic arithmetic (add, subtract, multiply, divide)
+- Inversion
+- Montgomery form conversion
+- Serialization/deserialization
+- Comparison operations
+
+## Data Structures
+
+The Verkle trie implementation uses specific data structures for efficiency:
+
+1. **Points**: Represented in both projective coordinates (X:Y:Z) and affine coordinates (x,y)
+2. **Field Elements**: Represented using UInt256 for dealing with large integers efficiently
+3. **Byte Representation**: Methods to convert between byte arrays and field elements in different endianness
+
+## Key Operations
+
+### Point Operations
+
+- **Point Creation**: Creating points on the curve
+- **Point Conversion**: Converting between projective and affine coordinates
+- **Serialization**: Converting points to byte representation
+
+### Field Operations
+
+- **Field Arithmetic**: Addition, subtraction, multiplication, division in finite fields
+- **Montgomery Form**: Efficient representation for modular arithmetic
+- **Random Element Generation**: Creating random field elements for testing and key generation
+
+## Current Implementation Status
+
+The current implementation focuses on the foundational cryptographic primitives required for Verkle tries:
+
+1. Bandersnatch elliptic curve implementation
+2. Finite field arithmetic for both base and scalar fields
+3. Point representation and operations
+
+The full Verkle trie implementation including commitment schemes, proof generation, and verification is still under development.
+
+## Integration with Besu
+
+The Verkle trie implementation is designed to eventually replace or complement the existing Merkle Patricia Trie implementation for state storage in Besu. This is part of the broader Ethereum roadmap for scaling and efficiency improvements.
+
+Future versions will integrate with:
+- Besu's state management
+- Block processing
+- Storage layer
+
+## Testing
+
+Tests for the Verkle trie implementation can be found in the corresponding test directories:
+
+```
+ethereum/verkletrie/src/test/java/org/hyperledger/besu/ethereum/verkletrie/
+```
+
+Tests cover:
+- Field element operations
+- Point arithmetic
+- Curve operations
+- Serialization/deserialization
+
+## Future Development
+
+The Verkle trie implementation is part of Ethereum's ongoing development roadmap. Future work includes:
+
+1. Complete trie structure implementation
+2. Proof generation and verification
+3. Integration with Besu's consensus mechanisms
+4. Performance optimizations
+5. Support for stateless clients
+
+## References
+
+- [EIP-6800: Verkle Trees](https://eips.ethereum.org/EIPS/eip-6800)
+- [Github repository for Besu Verkle Trie](https://github.com/hyperledger/besu-verkle-trie)